Line data Source code
1 : import * as core from '@ankoh/dashql-core';
2 :
3 : import { isSystemSchema } from '../connections/catalog/system_schemas.js';
4 :
5 : /// Shorter words are never treated as identifiers in natural language
6 1 : const MIN_IDENTIFIER_LENGTH = 3;
7 :
8 : /// Function words that are never treated as identifiers in natural language, even if a table or column has that name
9 1 : const STOP_WORDS = new Set([
10 1 : 'all', 'and', 'any', 'are', 'but', 'can', 'could', 'did', 'does', 'each', 'find', 'for', 'from', 'get', 'give',
11 1 : 'had', 'has', 'have', 'here', 'how', 'into', 'its', 'list', 'many', 'much', 'not', 'our', 'over', 'per', 'show',
12 1 : 'should', 'some', 'than', 'that', 'the', 'their', 'then', 'there', 'these', 'this', 'those', 'top', 'was',
13 1 : 'were', 'what', 'when', 'where', 'which', 'who', 'why', 'will', 'with', 'would', 'your',
14 1 : ]);
15 :
16 : /// A word, optionally qualified with a dot (orders.amount)
17 1 : const WORD_REGEX = /[\p{L}_][\p{L}\p{N}_$]*(?:\.[\p{L}_][\p{L}\p{N}_$]*)?/gu;
18 :
19 : /// The kind of a catalog name
20 1 : export enum CatalogNameKind {
21 1 : Table,
22 1 : Column,
23 1 : }
24 :
25 : /// A table or column name in the catalog
26 : export interface CatalogName {
27 : /// The name as stored in the catalog
28 : name: string;
29 : /// The kind of the named object
30 : kind: CatalogNameKind;
31 : /// The table of a column, null for tables
32 : table: string | null;
33 : }
34 :
35 : /// A lookup structure for the table and column names of a catalog
36 : export interface CatalogNameIndex {
37 : /// The distinct lowercase names, sorted for prefix searches
38 : keys: string[];
39 : /// The catalog names per lowercase name
40 : byKey: Map<string, CatalogName[]>;
41 : /// The lowercase column names per lowercase table name
42 : columnsByTable: Map<string, Set<string>>;
43 : }
44 :
45 : /// A word of a text that names a catalog object
46 : export interface IdentifierMatch {
47 : /// The begin of the word
48 : from: number;
49 : /// The end of the word
50 : to: number;
51 : /// The kind of the named object, a qualified column is a column
52 : kind: CatalogNameKind;
53 : /// The matched catalog names
54 : names: CatalogName[];
55 : }
56 :
57 : /// An index without names
58 1 : export const EMPTY_CATALOG_NAME_INDEX: CatalogNameIndex = { keys: [], byKey: new Map(), columnsByTable: new Map() };
59 :
60 : /// Build the name index of a catalog, skipping the schemas of the database system.
61 1 : export function buildCatalogNameIndex(catalog: core.DashQLCatalog): CatalogNameIndex {
62 1 : const byKey = new Map<string, CatalogName[]>();
63 1 : const columnsByTable = new Map<string, Set<string>>();
64 1 : const add = (name: CatalogName) => {
65 1 : const key = name.name.toLowerCase();
66 1 : const names = byKey.get(key);
67 1 : if (names == null) {
68 1 : byKey.set(key, [name]);
69 : } else {
70 1 : names.push(name);
71 : }
72 1 : };
73 1 : const snapshot = catalog.createSnapshot();
74 1 : const reader = snapshot.read();
75 1 : const flat = reader.catalogReader;
76 1 : const entry = new core.buffers.catalog.FlatCatalogEntry();
77 : // Every level references its parent by the index into the flat array of the level above
78 1 : const systemSchemas: boolean[] = [];
79 1 : for (let i = 0; i < flat.schemasLength(); ++i) {
80 1 : systemSchemas.push(isSystemSchema(reader.readName(flat.schemas(i, entry)!.nameId())));
81 : }
82 1 : const tableNames: (string | null)[] = [];
83 1 : for (let i = 0; i < flat.tablesLength(); ++i) {
84 1 : const table = flat.tables(i, entry)!;
85 1 : const name = reader.readName(table.nameId());
86 1 : if (systemSchemas[table.flatParentIdx()] || name.length === 0) {
87 1 : tableNames.push(null);
88 1 : continue;
89 1 : }
90 1 : tableNames.push(name);
91 1 : add({ name, kind: CatalogNameKind.Table, table: null });
92 1 : }
93 1 : for (let i = 0; i < flat.columnsLength(); ++i) {
94 1 : const column = flat.columns(i, entry)!;
95 1 : const table = tableNames[column.flatParentIdx()];
96 1 : const name = reader.readName(column.nameId());
97 1 : if (table == null || name.length === 0) {
98 1 : continue;
99 : }
100 1 : add({ name, kind: CatalogNameKind.Column, table });
101 1 : const tableKey = table.toLowerCase();
102 1 : let columns = columnsByTable.get(tableKey);
103 1 : if (columns == null) {
104 1 : columns = new Set();
105 1 : columnsByTable.set(tableKey, columns);
106 1 : }
107 1 : columns.add(name.toLowerCase());
108 1 : }
109 1 : const keys = [...byKey.keys()].sort();
110 1 : return { keys, byKey, columnsByTable };
111 1 : }
112 :
113 : /// Could a word be an identifier in natural language at all?
114 1 : export function isIdentifierCandidate(word: string): boolean {
115 1 : return word.length >= MIN_IDENTIFIER_LENGTH && !STOP_WORDS.has(word.toLowerCase());
116 1 : }
117 :
118 : /// Find the catalog names of a word, dotted words must name a column of a table
119 1 : export function lookupIdentifier(index: CatalogNameIndex, word: string): IdentifierMatch['names'] | null {
120 1 : const dot = word.indexOf('.');
121 1 : if (dot >= 0) {
122 1 : const table = word.substring(0, dot).toLowerCase();
123 1 : const column = word.substring(dot + 1).toLowerCase();
124 1 : if (!index.columnsByTable.get(table)?.has(column)) {
125 1 : return null;
126 : }
127 1 : return index.byKey.get(column)!.filter(name => name.kind === CatalogNameKind.Column && name.table?.toLowerCase() === table);
128 1 : }
129 1 : if (!isIdentifierCandidate(word)) {
130 1 : return null;
131 : }
132 1 : return index.byKey.get(word.toLowerCase()) ?? null;
133 1 : }
134 :
135 : /// Find the distinct lowercase names that start with a prefix, at most limit many
136 1 : export function lookupPrefix(index: CatalogNameIndex, prefix: string, limit: number): string[] {
137 1 : const lower = prefix.toLowerCase();
138 : // Binary search the first key that is not smaller than the prefix
139 1 : let lo = 0;
140 1 : let hi = index.keys.length;
141 1 : while (lo < hi) {
142 1 : const mid = (lo + hi) >>> 1;
143 1 : if (index.keys[mid] < lower) {
144 1 : lo = mid + 1;
145 : } else {
146 1 : hi = mid;
147 : }
148 1 : }
149 1 : const matches: string[] = [];
150 1 : for (let i = lo; i < index.keys.length && matches.length < limit && index.keys[i].startsWith(lower); ++i) {
151 1 : matches.push(index.keys[i]);
152 : }
153 1 : return matches;
154 1 : }
155 :
156 : /// Find the words of a text that name catalog objects
157 1 : export function findIdentifierMatches(index: CatalogNameIndex, text: string): IdentifierMatch[] {
158 1 : const matches: IdentifierMatch[] = [];
159 1 : for (const word of text.matchAll(WORD_REGEX)) {
160 1 : const names = lookupIdentifier(index, word[0]);
161 1 : if (names == null || names.length === 0) {
162 1 : continue;
163 : }
164 1 : matches.push({
165 1 : from: word.index,
166 1 : to: word.index + word[0].length,
167 1 : kind: names.some(name => name.kind === CatalogNameKind.Table) ? CatalogNameKind.Table : CatalogNameKind.Column,
168 1 : names,
169 1 : });
170 1 : }
171 1 : return matches;
172 1 : }
173 :
174 : /// Describe the catalog objects that a text mentions, e.g. "orders (table)" or "amount (column of orders)"
175 1 : export function collectMentionedIdentifiers(index: CatalogNameIndex, text: string): string[] {
176 1 : const mentioned = new Set<string>();
177 1 : for (const match of findIdentifierMatches(index, text)) {
178 1 : const tables = new Set<string>();
179 1 : const columns = new Map<string, Set<string>>();
180 1 : for (const name of match.names) {
181 1 : if (name.kind === CatalogNameKind.Table) {
182 1 : tables.add(name.name);
183 1 : } else {
184 1 : let owners = columns.get(name.name);
185 1 : if (owners == null) {
186 1 : owners = new Set();
187 1 : columns.set(name.name, owners);
188 1 : }
189 1 : if (name.table != null) owners.add(name.table);
190 1 : }
191 : }
192 1 : for (const table of tables) {
193 1 : mentioned.add(`${table} (table)`);
194 : }
195 1 : for (const [column, owners] of columns) {
196 1 : mentioned.add(owners.size > 0 ? `${column} (column of ${[...owners].join(', ')})` : `${column} (column)`);
197 : }
198 1 : }
199 1 : return [...mentioned];
200 1 : }
|
