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 reader = catalog.flatten().read();
74 1 : const flat = reader.catalogReader;
75 1 : const entry = new core.buffers.catalog.FlatCatalogEntry();
76 : // Every level references its parent by the index into the flat array of the level above
77 1 : const systemSchemas: boolean[] = [];
78 1 : for (let i = 0; i < flat.schemasLength(); ++i) {
79 1 : systemSchemas.push(isSystemSchema(reader.readName(flat.schemas(i, entry)!.nameId())));
80 : }
81 1 : const tableNames: (string | null)[] = [];
82 1 : for (let i = 0; i < flat.tablesLength(); ++i) {
83 1 : const table = flat.tables(i, entry)!;
84 1 : const name = reader.readName(table.nameId());
85 1 : if (systemSchemas[table.flatParentIdx()] || name.length === 0) {
86 1 : tableNames.push(null);
87 1 : continue;
88 1 : }
89 1 : tableNames.push(name);
90 1 : add({ name, kind: CatalogNameKind.Table, table: null });
91 1 : }
92 1 : for (let i = 0; i < flat.columnsLength(); ++i) {
93 1 : const column = flat.columns(i, entry)!;
94 1 : const table = tableNames[column.flatParentIdx()];
95 1 : const name = reader.readName(column.nameId());
96 1 : if (table == null || name.length === 0) {
97 1 : continue;
98 : }
99 1 : add({ name, kind: CatalogNameKind.Column, table });
100 1 : const tableKey = table.toLowerCase();
101 1 : let columns = columnsByTable.get(tableKey);
102 1 : if (columns == null) {
103 1 : columns = new Set();
104 1 : columnsByTable.set(tableKey, columns);
105 1 : }
106 1 : columns.add(name.toLowerCase());
107 1 : }
108 1 : const keys = [...byKey.keys()].sort();
109 1 : return { keys, byKey, columnsByTable };
110 1 : }
111 :
112 : /// Could a word be an identifier in natural language at all?
113 1 : export function isIdentifierCandidate(word: string): boolean {
114 1 : return word.length >= MIN_IDENTIFIER_LENGTH && !STOP_WORDS.has(word.toLowerCase());
115 1 : }
116 :
117 : /// Find the catalog names of a word, dotted words must name a column of a table
118 1 : export function lookupIdentifier(index: CatalogNameIndex, word: string): IdentifierMatch['names'] | null {
119 1 : const dot = word.indexOf('.');
120 1 : if (dot >= 0) {
121 1 : const table = word.substring(0, dot).toLowerCase();
122 1 : const column = word.substring(dot + 1).toLowerCase();
123 1 : if (!index.columnsByTable.get(table)?.has(column)) {
124 1 : return null;
125 : }
126 1 : return index.byKey.get(column)!.filter(name => name.kind === CatalogNameKind.Column && name.table?.toLowerCase() === table);
127 1 : }
128 1 : if (!isIdentifierCandidate(word)) {
129 1 : return null;
130 : }
131 1 : return index.byKey.get(word.toLowerCase()) ?? null;
132 1 : }
133 :
134 : /// Find the distinct lowercase names that start with a prefix, at most limit many
135 1 : export function lookupPrefix(index: CatalogNameIndex, prefix: string, limit: number): string[] {
136 1 : const lower = prefix.toLowerCase();
137 : // Binary search the first key that is not smaller than the prefix
138 1 : let lo = 0;
139 1 : let hi = index.keys.length;
140 1 : while (lo < hi) {
141 1 : const mid = (lo + hi) >>> 1;
142 1 : if (index.keys[mid] < lower) {
143 1 : lo = mid + 1;
144 : } else {
145 1 : hi = mid;
146 : }
147 1 : }
148 1 : const matches: string[] = [];
149 1 : for (let i = lo; i < index.keys.length && matches.length < limit && index.keys[i].startsWith(lower); ++i) {
150 1 : matches.push(index.keys[i]);
151 : }
152 1 : return matches;
153 1 : }
154 :
155 : /// Find the words of a text that name catalog objects
156 1 : export function findIdentifierMatches(index: CatalogNameIndex, text: string): IdentifierMatch[] {
157 1 : const matches: IdentifierMatch[] = [];
158 1 : for (const word of text.matchAll(WORD_REGEX)) {
159 1 : const names = lookupIdentifier(index, word[0]);
160 1 : if (names == null || names.length === 0) {
161 1 : continue;
162 : }
163 1 : matches.push({
164 1 : from: word.index,
165 1 : to: word.index + word[0].length,
166 1 : kind: names.some(name => name.kind === CatalogNameKind.Table) ? CatalogNameKind.Table : CatalogNameKind.Column,
167 1 : names,
168 1 : });
169 1 : }
170 1 : return matches;
171 1 : }
172 :
173 : /// Describe the catalog objects that a text mentions, e.g. "orders (table)" or "amount (column of orders)"
174 1 : export function collectMentionedIdentifiers(index: CatalogNameIndex, text: string): string[] {
175 1 : const mentioned = new Set<string>();
176 1 : for (const match of findIdentifierMatches(index, text)) {
177 1 : const tables = new Set<string>();
178 1 : const columns = new Map<string, Set<string>>();
179 1 : for (const name of match.names) {
180 1 : if (name.kind === CatalogNameKind.Table) {
181 1 : tables.add(name.name);
182 1 : } else {
183 1 : let owners = columns.get(name.name);
184 1 : if (owners == null) {
185 1 : owners = new Set();
186 1 : columns.set(name.name, owners);
187 1 : }
188 1 : if (name.table != null) owners.add(name.table);
189 1 : }
190 : }
191 1 : for (const table of tables) {
192 1 : mentioned.add(`${table} (table)`);
193 : }
194 1 : for (const [column, owners] of columns) {
195 1 : mentioned.add(owners.size > 0 ? `${column} (column of ${[...owners].join(', ')})` : `${column} (column)`);
196 : }
197 1 : }
198 1 : return [...mentioned];
199 1 : }
|
