Blog/wwwroot/jsonql-js/query.js 11 K · 371 lines · raw · history

1 import { tokenize } from './lexer.js';
2 import { Parser, inferPathKey } from './parser.js';
3 import { SqlSyntaxError, SqlEvaluationError } from './errors.js';
4 import { evaluate } from './evaluate.js';
5
6 /**
7 * @typedef {{kind: 'Star'}} StarSelect
8 * @typedef {{kind: 'Shape', expr: import('./parser.js').ObjectLiteralNode}} ShapeSelect
9 * @typedef {{kind: 'Columns', items: {expr: import('./parser.js').Expr, key: string}[]}} ColumnsSelect
10 * @typedef {StarSelect|ShapeSelect|ColumnsSelect} Select
11 * @typedef {{kind: 'Source', expr: import('./parser.js').Expr, alias: string|null}} SourceFromItem
12 * @typedef {{kind: 'Unnest', expr: import('./parser.js').Expr, alias: string|null}} UnnestFromItem
13 * @typedef {SourceFromItem|UnnestFromItem} FromItem
14 * @typedef {{type: 'INNER'|'LEFT'|'CROSS', item: FromItem, on: import('./parser.js').Expr|null}} JoinClause
15 * @typedef {{first: FromItem, joins: JoinClause[]}} From
16 * @typedef {{expr: import('./parser.js').Expr, dir: 'ASC'|'DESC'}} OrderItem
17 * @typedef {{type: 'Query', select: Select, from: From, where: import('./parser.js').Expr|null, orderBy: OrderItem[]|null, limit: import('./parser.js').Expr|null}} Query
18 */
19
20 class QueryParser extends Parser {
21 /** @returns {Query} */
22 parseQuery() {
23 this.expect('SELECT');
24 const select = this.parseSelect();
25 this.expect('FROM');
26 const from = this.parseFrom();
27 let where = null;
28 if (this.check('WHERE')) {
29 this.next();
30 where = this.parseOr();
31 }
32 let orderBy = null;
33 if (this.check('ORDER')) {
34 this.next();
35 this.expect('BY');
36 orderBy = this.parseOrderByList();
37 }
38 let limit = null;
39 if (this.check('LIMIT')) {
40 this.next();
41 limit = this.parseOr();
42 }
43 this.expect('eof');
44 return { type: 'Query', select, from, where, orderBy, limit };
45 }
46
47 /** @returns {OrderItem[]} */
48 parseOrderByList() {
49 const items = [this.parseOrderByItem()];
50 while (this.check(',')) {
51 this.next();
52 items.push(this.parseOrderByItem());
53 }
54 return items;
55 }
56
57 /** @returns {OrderItem} */
58 parseOrderByItem() {
59 const expr = this.parseOr();
60 let dir = 'ASC';
61 if (this.check('ASC')) {
62 this.next();
63 } else if (this.check('DESC')) {
64 this.next();
65 dir = 'DESC';
66 }
67 return { expr, dir };
68 }
69
70 /** @returns {Select} */
71 parseSelect() {
72 if (this.check('*')) {
73 this.next();
74 return { kind: 'Star' };
75 }
76 if (this.check('{')) {
77 const expr = this.parseObjectLiteral();
78 return { kind: 'Shape', expr };
79 }
80 const items = [this.parseSelectItem()];
81 while (this.check(',')) {
82 this.next();
83 items.push(this.parseSelectItem());
84 }
85 return { kind: 'Columns', items };
86 }
87
88 /** @returns {{expr: import('./parser.js').Expr, key: string}} */
89 parseSelectItem() {
90 const startTok = this.peek();
91 const expr = this.parseOr();
92 if (this.check('AS')) {
93 this.next();
94 const key = this.expectIdentLike().value;
95 return { expr, key };
96 }
97 return { expr, key: inferPathKey(expr, startTok) };
98 }
99
100 /** @returns {From} */
101 parseFrom() {
102 const first = this.parseFromItem();
103 /** @type {JoinClause[]} */
104 const joins = [];
105 while (this.isJoinStart()) {
106 joins.push(this.parseJoinClause());
107 }
108 validateFromAliases(first, joins);
109 return { first, joins };
110 }
111
112 /** @returns {boolean} */
113 isJoinStart() {
114 return this.check('JOIN') || this.check('INNER') || this.check('LEFT') || this.check('CROSS');
115 }
116
117 /** @returns {FromItem} */
118 parseFromItem() {
119 if (this.check('UNNEST')) {
120 this.next();
121 this.expect('(');
122 const expr = this.parseOr();
123 this.expect(')');
124 let alias = null;
125 if (this.check('AS')) {
126 this.next();
127 alias = this.expectIdentLike().value;
128 }
129 return { kind: 'Unnest', expr, alias };
130 }
131 const expr = this.parsePostfix();
132 let alias = null;
133 if (this.check('AS')) {
134 this.next();
135 alias = this.expectIdentLike().value;
136 }
137 return { kind: 'Source', expr, alias };
138 }
139
140 /** @returns {JoinClause} */
141 parseJoinClause() {
142 const startTok = this.peek();
143 /** @type {'INNER'|'LEFT'|'CROSS'} */
144 let type = 'INNER';
145 if (this.check('INNER')) {
146 this.next();
147 this.expect('JOIN');
148 } else if (this.check('LEFT')) {
149 this.next();
150 this.expect('JOIN');
151 type = 'LEFT';
152 } else if (this.check('CROSS')) {
153 this.next();
154 this.expect('JOIN');
155 type = 'CROSS';
156 } else {
157 this.expect('JOIN');
158 }
159
160 const item = this.parseFromItem();
161
162 let on = null;
163 if (this.check('ON')) {
164 this.next();
165 on = this.parseOr();
166 }
167
168 if (type === 'CROSS' && on) {
169 throw new SqlSyntaxError('CROSS JOIN cannot have an ON condition', startTok);
170 }
171 if (type !== 'CROSS' && item.kind !== 'Unnest' && !on) {
172 throw new SqlSyntaxError('JOIN requires an ON condition (except CROSS JOIN or JOIN UNNEST(...))', startTok);
173 }
174
175 return { type, item, on };
176 }
177 }
178
179 /**
180 * @param {FromItem} first
181 * @param {JoinClause[]} joins
182 */
183 function validateFromAliases(first, joins) {
184 const hasJoins = joins.length > 0;
185 if (first.kind === 'Unnest' && !first.alias) {
186 throw new SqlSyntaxError('UNNEST(...) in FROM requires AS alias');
187 }
188 if (hasJoins && !first.alias) {
189 throw new SqlSyntaxError('FROM sources must be aliased when using JOIN');
190 }
191 for (const join of joins) {
192 if (!join.item.alias) {
193 throw new SqlSyntaxError('Joined sources must be aliased');
194 }
195 }
196 }
197
198 /**
199 * Parses a `SELECT ... FROM ... [WHERE ...] [ORDER BY ...] [LIMIT ...]` query string into an AST.
200 * @param {string} source
201 * @returns {Query}
202 */
203 export function parseQuery(source) {
204 const tokens = tokenize(source);
205 const parser = new QueryParser(tokens);
206 return parser.parseQuery();
207 }
208
209 /**
210 * Executes a parsed query against a JSON context object.
211 * @param {Query} ast
212 * @param {Record<string, any>} context
213 * @param {{functions?: Record<string, (...args: any[]) => any>}} [options]
214 * @returns {any[]}
215 */
216 export function executeQuery(ast, context, options = {}) {
217 const hasJoins = ast.from.joins.length > 0;
218 const firstArray = resolveFromItemArray(ast.from.first, context, options);
219
220 /** @type {{ctx: any, pristineRow: any}[]} */
221 let rows = firstArray.map((row) => ({
222 ctx: ast.from.first.alias ? bind({}, row, ast.from.first.alias) : row,
223 pristineRow: row,
224 }));
225
226 for (const join of ast.from.joins) {
227 /** @type {{ctx: any, pristineRow: any}[]} */
228 const nextRows = [];
229 for (const left of rows) {
230 const scopeCtx = { ...context, ...left.ctx };
231 const rightArray = resolveFromItemArray(join.item, scopeCtx, options);
232 let matchedAny = false;
233 for (const rightRow of rightArray) {
234 const ctx = bind(left.ctx, rightRow, /** @type {string} */ (join.item.alias));
235 if (join.on && evaluate(join.on, ctx, options) !== true) continue;
236 nextRows.push({ ctx, pristineRow: undefined });
237 matchedAny = true;
238 }
239 if (!matchedAny && join.type === 'LEFT') {
240 nextRows.push({ ctx: bind(left.ctx, null, /** @type {string} */ (join.item.alias)), pristineRow: undefined });
241 }
242 }
243 rows = nextRows;
244 }
245
246 /** @type {{ctx: any, pristineRow: any}[]} */
247 let matched = [];
248 for (const r of rows) {
249 if (ast.where && evaluate(ast.where, r.ctx, options) !== true) continue;
250 matched.push(r);
251 }
252
253 if (ast.orderBy) {
254 const comparator = makeRowComparator(ast.orderBy, options);
255 matched = matched.slice().sort(comparator);
256 }
257
258 if (ast.limit) {
259 const n = evaluate(ast.limit, context, options);
260 if (n !== null) {
261 if (typeof n !== 'number' || !Number.isInteger(n) || n < 0) {
262 throw new SqlEvaluationError('LIMIT must be a non-negative integer or NULL');
263 }
264 matched = matched.slice(0, n);
265 }
266 }
267
268 return matched.map((r) =>
269 ast.select.kind === 'Star' && !hasJoins ? r.pristineRow : project(ast.select, r.ctx, options),
270 );
271 }
272
273 /**
274 * @param {FromItem} item
275 * @param {Record<string, any>} scopeCtx
276 * @param {{functions?: Record<string, (...args: any[]) => any>}} options
277 */
278 function resolveFromItemArray(item, scopeCtx, options) {
279 const value = evaluate(item.expr, scopeCtx, options);
280 if (item.kind === 'Unnest') {
281 if (value === null || value === undefined) return [];
282 if (!Array.isArray(value)) throw new SqlEvaluationError('UNNEST requires an array value');
283 return value;
284 }
285 if (!Array.isArray(value)) throw new SqlEvaluationError('FROM/JOIN source must reference an array');
286 return value;
287 }
288
289 /**
290 * Binds a row into a context: its own fields (if it's a plain object) plus its alias.
291 * @param {Record<string, any>} baseCtx
292 * @param {any} row
293 * @param {string} alias
294 */
295 function bind(baseCtx, row, alias) {
296 const flat = isPlainObject(row) ? row : {};
297 return { ...baseCtx, ...flat, [alias]: row };
298 }
299
300 /** @param {any} v */
301 function isPlainObject(v) {
302 return typeof v === 'object' && v !== null && !Array.isArray(v);
303 }
304
305 /**
306 * @param {OrderItem[]} orderBy
307 * @param {{functions?: Record<string, (...args: any[]) => any>}} options
308 */
309 function makeRowComparator(orderBy, options) {
310 return (a, b) => {
311 for (const item of orderBy) {
312 const va = evaluate(item.expr, a.ctx, options);
313 const vb = evaluate(item.expr, b.ctx, options);
314 // Nulls always sort last, regardless of ASC/DESC - checked before the
315 // direction flip below, so DESC never pulls nulls back to the front.
316 if (va === null && vb === null) continue;
317 if (va === null) return 1;
318 if (vb === null) return -1;
319 const cmp = compareForOrder(va, vb);
320 if (cmp !== 0) return item.dir === 'DESC' ? -cmp : cmp;
321 }
322 return 0;
323 };
324 }
325
326 /** @param {any} a @param {any} b */
327 function compareForOrder(a, b) {
328 const ta = typeof a;
329 const tb = typeof b;
330 if (ta !== tb || (ta !== 'number' && ta !== 'string' && ta !== 'boolean')) {
331 throw new SqlEvaluationError(`Cannot compare ${orderTypeName(a)} and ${orderTypeName(b)} in ORDER BY`);
332 }
333 if (a < b) return -1;
334 if (a > b) return 1;
335 return 0;
336 }
337
338 /** @param {any} v */
339 function orderTypeName(v) {
340 if (v === null) return 'null';
341 if (Array.isArray(v)) return 'array';
342 return typeof v;
343 }
344
345 /**
346 * @param {Select} select
347 * @param {Record<string, any>} ctx
348 * @param {{functions?: Record<string, (...args: any[]) => any>}} options
349 */
350 function project(select, ctx, options) {
351 if (select.kind === 'Star') return ctx;
352 if (select.kind === 'Shape') return evaluate(select.expr, ctx, options);
353 /** @type {Record<string, any>} */
354 const out = {};
355 for (const item of select.items) {
356 out[item.key] = evaluate(item.expr, ctx, options);
357 }
358 return out;
359 }
360
361 /**
362 * Parses (if needed) and executes a `SELECT ... FROM ... [WHERE ...] [ORDER BY ...] [LIMIT ...]` query.
363 * @param {string|Query} source - query text, or an already-parsed AST
364 * @param {Record<string, any>} context
365 * @param {{functions?: Record<string, (...args: any[]) => any>}} [options]
366 * @returns {any[]}
367 */
368 export function query(source, context, options) {
369 const ast = typeof source === 'string' ? parseQuery(source) : source;
370 return executeQuery(ast, context, options);
371 }