Blog/wwwroot/jsonql-js/query.js 19.1 K · 578 lines · raw · history

1 import { tokenize } from './lexer.js';
2 import { Parser, inferPathKey, mapChildren } from './parser.js';
3 import { SqlSyntaxError, SqlEvaluationError } from './errors.js';
4 import { evaluate } from './evaluate.js';
5 import { aggregates, isAggregateName } from './aggregates.js';
6
7 /**
8 * @typedef {{kind: 'Star'}} StarSelect
9 * @typedef {{kind: 'Shape', expr: import('./parser.js').ObjectLiteralNode}} ShapeSelect
10 * @typedef {{kind: 'Columns', items: {expr: import('./parser.js').Expr, key: string}[]}} ColumnsSelect
11 * @typedef {StarSelect|ShapeSelect|ColumnsSelect} Select
12 * @typedef {{kind: 'Source', expr: import('./parser.js').Expr, alias: string|null}} SourceFromItem
13 * @typedef {{kind: 'Unnest', expr: import('./parser.js').Expr, alias: string|null}} UnnestFromItem
14 * @typedef {SourceFromItem|UnnestFromItem} FromItem
15 * @typedef {{type: 'INNER'|'LEFT'|'CROSS', item: FromItem, on: import('./parser.js').Expr|null}} JoinClause
16 * @typedef {{first: FromItem, joins: JoinClause[]}} From
17 * @typedef {{expr: import('./parser.js').Expr, dir: 'ASC'|'DESC'}} OrderItem
18 * @typedef {{type: 'Query', select: Select, from: From, where: import('./parser.js').Expr|null, groupBy: import('./parser.js').Expr[]|null, having: import('./parser.js').Expr|null, orderBy: OrderItem[]|null, limit: import('./parser.js').Expr|null}} Query
19 * @typedef {{key: string, fold: (values: any[]) => any, arg: import('./parser.js').Expr|import('./parser.js').StarNode}} PlannedAggregate
20 * @typedef {{select: Select, having: import('./parser.js').Expr|null, orderBy: OrderItem[]|null, groupBy: import('./parser.js').Expr[]|null, aggregates: PlannedAggregate[], grouped: boolean}} Plan
21 */
22
23 class QueryParser extends Parser {
24 /** @returns {Query} */
25 parseQuery() {
26 this.expect('SELECT');
27 const select = this.parseSelect();
28 this.expect('FROM');
29 const from = this.parseFrom();
30 let where = null;
31 if (this.check('WHERE')) {
32 this.next();
33 where = this.parseOr();
34 }
35 let groupBy = null;
36 if (this.check('GROUP')) {
37 this.next();
38 this.expect('BY');
39 groupBy = this.parseGroupByList();
40 }
41 let having = null;
42 if (this.check('HAVING')) {
43 this.next();
44 having = this.parseOr();
45 }
46 let orderBy = null;
47 if (this.check('ORDER')) {
48 this.next();
49 this.expect('BY');
50 orderBy = this.parseOrderByList();
51 }
52 let limit = null;
53 if (this.check('LIMIT')) {
54 this.next();
55 limit = this.parseOr();
56 }
57 this.expect('eof');
58 /** @type {Query} */
59 const ast = { type: 'Query', select, from, where, groupBy, having, orderBy, limit };
60 // Planning is what rejects misplaced/nested aggregates and SELECT * with
61 // GROUP BY; running it here surfaces those at parse time. The result is
62 // recomputed (cheaply) by executeQuery, which also accepts hand-built ASTs.
63 planQuery(ast);
64 return ast;
65 }
66
67 /** @returns {import('./parser.js').Expr[]} */
68 parseGroupByList() {
69 const items = [this.parseOr()];
70 while (this.check(',')) {
71 this.next();
72 items.push(this.parseOr());
73 }
74 return items;
75 }
76
77 /** @returns {OrderItem[]} */
78 parseOrderByList() {
79 const items = [this.parseOrderByItem()];
80 while (this.check(',')) {
81 this.next();
82 items.push(this.parseOrderByItem());
83 }
84 return items;
85 }
86
87 /** @returns {OrderItem} */
88 parseOrderByItem() {
89 const expr = this.parseOr();
90 let dir = 'ASC';
91 if (this.check('ASC')) {
92 this.next();
93 } else if (this.check('DESC')) {
94 this.next();
95 dir = 'DESC';
96 }
97 return { expr, dir };
98 }
99
100 /** @returns {Select} */
101 parseSelect() {
102 if (this.check('*')) {
103 this.next();
104 return { kind: 'Star' };
105 }
106 if (this.check('{')) {
107 const expr = this.parseObjectLiteral();
108 return { kind: 'Shape', expr };
109 }
110 const items = [this.parseSelectItem()];
111 while (this.check(',')) {
112 this.next();
113 items.push(this.parseSelectItem());
114 }
115 return { kind: 'Columns', items };
116 }
117
118 /** @returns {{expr: import('./parser.js').Expr, key: string}} */
119 parseSelectItem() {
120 const startTok = this.peek();
121 const expr = this.parseOr();
122 if (this.check('AS')) {
123 this.next();
124 const key = this.expectIdentLike().value;
125 return { expr, key };
126 }
127 return { expr, key: inferPathKey(expr, startTok) };
128 }
129
130 /** @returns {From} */
131 parseFrom() {
132 const first = this.parseFromItem();
133 /** @type {JoinClause[]} */
134 const joins = [];
135 while (this.isJoinStart()) {
136 joins.push(this.parseJoinClause());
137 }
138 validateFromAliases(first, joins);
139 return { first, joins };
140 }
141
142 /** @returns {boolean} */
143 isJoinStart() {
144 return this.check('JOIN') || this.check('INNER') || this.check('LEFT') || this.check('CROSS');
145 }
146
147 /** @returns {FromItem} */
148 parseFromItem() {
149 if (this.check('UNNEST')) {
150 this.next();
151 this.expect('(');
152 const expr = this.parseOr();
153 this.expect(')');
154 let alias = null;
155 if (this.check('AS')) {
156 this.next();
157 alias = this.expectIdentLike().value;
158 }
159 return { kind: 'Unnest', expr, alias };
160 }
161 const expr = this.parsePostfix();
162 let alias = null;
163 if (this.check('AS')) {
164 this.next();
165 alias = this.expectIdentLike().value;
166 }
167 return { kind: 'Source', expr, alias };
168 }
169
170 /** @returns {JoinClause} */
171 parseJoinClause() {
172 const startTok = this.peek();
173 /** @type {'INNER'|'LEFT'|'CROSS'} */
174 let type = 'INNER';
175 if (this.check('INNER')) {
176 this.next();
177 this.expect('JOIN');
178 } else if (this.check('LEFT')) {
179 this.next();
180 this.expect('JOIN');
181 type = 'LEFT';
182 } else if (this.check('CROSS')) {
183 this.next();
184 this.expect('JOIN');
185 type = 'CROSS';
186 } else {
187 this.expect('JOIN');
188 }
189
190 const item = this.parseFromItem();
191
192 let on = null;
193 if (this.check('ON')) {
194 this.next();
195 on = this.parseOr();
196 }
197
198 if (type === 'CROSS' && on) {
199 throw new SqlSyntaxError('CROSS JOIN cannot have an ON condition', startTok);
200 }
201 if (type !== 'CROSS' && item.kind !== 'Unnest' && !on) {
202 throw new SqlSyntaxError('JOIN requires an ON condition (except CROSS JOIN or JOIN UNNEST(...))', startTok);
203 }
204
205 return { type, item, on };
206 }
207 }
208
209 /**
210 * Works out how a query has to be run: which aggregates it computes, what the
211 * SELECT/HAVING/ORDER BY expressions look like once those aggregates have been
212 * lifted out, and whether the query is grouped at all. Pure - it never mutates
213 * `ast`, so a parsed query can be executed repeatedly.
214 * @param {Query} ast
215 * @returns {Plan}
216 */
217 function planQuery(ast) {
218 assertNoAggregates(ast.where, 'WHERE');
219 assertNoAggregates(ast.from.first.expr, 'FROM');
220 for (const expr of ast.groupBy ?? []) assertNoAggregates(expr, 'GROUP BY');
221 for (const join of ast.from.joins) {
222 assertNoAggregates(join.item.expr, 'JOIN');
223 assertNoAggregates(join.on, 'JOIN ... ON');
224 }
225
226 /** @type {PlannedAggregate[]} */
227 const found = [];
228 const select = mapSelect(ast.select, (expr) => extractAggregates(expr, found));
229 const having = ast.having === null ? null : extractAggregates(ast.having, found);
230 const orderBy =
231 ast.orderBy === null
232 ? null
233 : resolveOrderAliases(ast.orderBy, ast.select).map((item) => ({
234 ...item,
235 expr: extractAggregates(item.expr, found),
236 }));
237
238 const grouped = ast.groupBy !== null || found.length > 0;
239 if (grouped && ast.select.kind === 'Star') {
240 throw new SqlSyntaxError('SELECT * cannot be combined with GROUP BY or aggregate functions; list the columns instead');
241 }
242 if (ast.having !== null && !grouped) {
243 throw new SqlSyntaxError('HAVING requires GROUP BY or an aggregate function; use WHERE to filter rows');
244 }
245
246 return { select, having, orderBy, groupBy: ast.groupBy, aggregates: found, grouped };
247 }
248
249 /**
250 * Replaces every aggregate call in `node` with a reference to a generated `$aggN`
251 * binding, recording in `sink` how to compute it. `$` is not a legal identifier
252 * character in the lexer, so these names can never collide with anything the
253 * query itself could have written.
254 * @param {import('./parser.js').Expr} node
255 * @param {PlannedAggregate[]} sink
256 * @returns {import('./parser.js').Expr}
257 */
258 function extractAggregates(node, sink) {
259 if (node.type === 'Call' && isAggregateName(node.name)) {
260 const name = node.name.toUpperCase();
261 if (node.args.length !== 1) {
262 throw new SqlSyntaxError(`${name} takes exactly one argument`);
263 }
264 const [arg] = node.args;
265 if (arg.type !== 'Star' && containsAggregate(arg)) {
266 throw new SqlSyntaxError('Aggregate functions cannot be nested');
267 }
268 const key = `$agg${sink.length}`;
269 sink.push({ key, fold: aggregates[name], arg });
270 return { type: 'Identifier', name: key };
271 }
272 return mapChildren(node, (child) => extractAggregates(child, sink));
273 }
274
275 /** @param {import('./parser.js').Expr} node */
276 function containsAggregate(node) {
277 if (node.type === 'Call' && isAggregateName(node.name)) return true;
278 let found = false;
279 mapChildren(node, (child) => {
280 if (containsAggregate(child)) found = true;
281 return child;
282 });
283 return found;
284 }
285
286 /** @param {import('./parser.js').Expr|null} node @param {string} clause */
287 function assertNoAggregates(node, clause) {
288 if (node !== null && containsAggregate(node)) {
289 throw new SqlSyntaxError(`Aggregate functions are not allowed in ${clause}`);
290 }
291 }
292
293 /**
294 * @param {Select} select
295 * @param {(expr: import('./parser.js').Expr) => import('./parser.js').Expr} fn
296 * @returns {Select}
297 */
298 function mapSelect(select, fn) {
299 if (select.kind === 'Star') return select;
300 if (select.kind === 'Shape') {
301 return { kind: 'Shape', expr: /** @type {import('./parser.js').ObjectLiteralNode} */ (fn(select.expr)) };
302 }
303 return { kind: 'Columns', items: select.items.map((item) => ({ ...item, expr: fn(item.expr) })) };
304 }
305
306 /**
307 * Lets ORDER BY name an output column, as SQL does, so `COUNT(*) AS aantal ...
308 * ORDER BY aantal DESC` sorts by the aggregate instead of silently finding
309 * nothing. Only bare identifiers are resolved - `ORDER BY p.aantal` stays a path
310 * into the row.
311 * @param {OrderItem[]} orderBy
312 * @param {Select} select
313 * @returns {OrderItem[]}
314 */
315 function resolveOrderAliases(orderBy, select) {
316 const outputs = selectOutputs(select);
317 if (outputs === null) return orderBy;
318 return orderBy.map((item) => {
319 if (item.expr.type !== 'Identifier') return item;
320 const aliased = outputs.get(item.expr.name);
321 return aliased === undefined ? item : { ...item, expr: aliased };
322 });
323 }
324
325 /** @param {Select} select @returns {Map<string, import('./parser.js').Expr>|null} */
326 function selectOutputs(select) {
327 if (select.kind === 'Star') return null;
328 if (select.kind === 'Shape') return new Map(select.expr.properties.map((p) => [p.key, p.value]));
329 return new Map(select.items.map((item) => [item.key, item.expr]));
330 }
331
332 /**
333 * @param {FromItem} first
334 * @param {JoinClause[]} joins
335 */
336 function validateFromAliases(first, joins) {
337 const hasJoins = joins.length > 0;
338 if (first.kind === 'Unnest' && !first.alias) {
339 throw new SqlSyntaxError('UNNEST(...) in FROM requires AS alias');
340 }
341 if (hasJoins && !first.alias) {
342 throw new SqlSyntaxError('FROM sources must be aliased when using JOIN');
343 }
344 for (const join of joins) {
345 if (!join.item.alias) {
346 throw new SqlSyntaxError('Joined sources must be aliased');
347 }
348 }
349 }
350
351 /**
352 * Parses a `SELECT ... FROM ... [WHERE ...] [GROUP BY ...] [HAVING ...] [ORDER BY ...] [LIMIT ...]`
353 * query string into an AST.
354 * @param {string} source
355 * @returns {Query}
356 */
357 export function parseQuery(source) {
358 const tokens = tokenize(source);
359 const parser = new QueryParser(tokens);
360 return parser.parseQuery();
361 }
362
363 /**
364 * Executes a parsed query against a JSON context object.
365 * @param {Query} ast
366 * @param {Record<string, any>} context
367 * @param {{functions?: Record<string, (...args: any[]) => any>}} [options]
368 * @returns {any[]}
369 */
370 export function executeQuery(ast, context, options = {}) {
371 const hasJoins = ast.from.joins.length > 0;
372 const firstArray = resolveFromItemArray(ast.from.first, context, options);
373
374 /** @type {{ctx: any, pristineRow: any}[]} */
375 let rows = firstArray.map((row) => ({
376 ctx: ast.from.first.alias ? bind({}, row, ast.from.first.alias) : row,
377 pristineRow: row,
378 }));
379
380 for (const join of ast.from.joins) {
381 /** @type {{ctx: any, pristineRow: any}[]} */
382 const nextRows = [];
383 for (const left of rows) {
384 const scopeCtx = { ...context, ...left.ctx };
385 const rightArray = resolveFromItemArray(join.item, scopeCtx, options);
386 let matchedAny = false;
387 for (const rightRow of rightArray) {
388 const ctx = bind(left.ctx, rightRow, /** @type {string} */ (join.item.alias));
389 if (join.on && evaluate(join.on, ctx, options) !== true) continue;
390 nextRows.push({ ctx, pristineRow: undefined });
391 matchedAny = true;
392 }
393 if (!matchedAny && join.type === 'LEFT') {
394 nextRows.push({ ctx: bind(left.ctx, null, /** @type {string} */ (join.item.alias)), pristineRow: undefined });
395 }
396 }
397 rows = nextRows;
398 }
399
400 const plan = planQuery(ast);
401
402 /** @type {{ctx: any, pristineRow: any}[]} */
403 let matched = [];
404 for (const r of rows) {
405 if (ast.where && evaluate(ast.where, r.ctx, options) !== true) continue;
406 matched.push(r);
407 }
408
409 if (plan.grouped) {
410 matched = groupRows(matched, plan, context, options);
411 if (plan.having) {
412 matched = matched.filter((r) => evaluate(plan.having, r.ctx, options) === true);
413 }
414 }
415
416 if (plan.orderBy) {
417 const comparator = makeRowComparator(plan.orderBy, options);
418 matched = matched.slice().sort(comparator);
419 }
420
421 if (ast.limit) {
422 const n = evaluate(ast.limit, context, options);
423 if (n !== null) {
424 if (typeof n !== 'number' || !Number.isInteger(n) || n < 0) {
425 throw new SqlEvaluationError('LIMIT must be a non-negative integer or NULL');
426 }
427 matched = matched.slice(0, n);
428 }
429 }
430
431 return matched.map((r) =>
432 plan.select.kind === 'Star' && !hasJoins ? r.pristineRow : project(plan.select, r.ctx, options),
433 );
434 }
435
436 /**
437 * Folds the matched rows into one row per distinct GROUP BY key - or a single row
438 * when the query has no GROUP BY but does use aggregates. A group's context is its
439 * first row's context plus the computed `$aggN` bindings, so expressions that
440 * aren't aggregated still resolve: against an arbitrary row of the group, the way
441 * SQLite treats bare columns, rather than being rejected outright.
442 * @param {{ctx: any, pristineRow: any}[]} rows
443 * @param {Plan} plan
444 * @param {Record<string, any>} context
445 * @param {{functions?: Record<string, (...args: any[]) => any>}} options
446 * @returns {{ctx: any, pristineRow: any}[]}
447 */
448 function groupRows(rows, plan, context, options) {
449 /** @type {Map<string, {ctx: any, pristineRow: any}[]>} */
450 const groups = new Map();
451 for (const r of rows) {
452 // Serializing the key values is what makes grouping by an object or array
453 // (not just a scalar) work at all; it costs key-order sensitivity, which
454 // only shows up for objects built with their keys in differing orders.
455 const key = plan.groupBy === null ? '' : JSON.stringify(plan.groupBy.map((e) => evaluate(e, r.ctx, options)));
456 const group = groups.get(key);
457 if (group) group.push(r);
458 else groups.set(key, [r]);
459 }
460
461 // `SELECT COUNT(*) AS n FROM empty` is still one row (n = 0), but grouping an
462 // empty set of rows yields no groups at all.
463 if (plan.groupBy === null && groups.size === 0) groups.set('', []);
464
465 const out = [];
466 for (const group of groups.values()) {
467 const ctx = { ...(group.length > 0 ? group[0].ctx : context) };
468 for (const agg of plan.aggregates) {
469 // COUNT(*) has no expression to evaluate; a non-null placeholder per row
470 // is what turns "count non-nulls" into "count rows".
471 const values = group.map((r) => (agg.arg.type === 'Star' ? true : evaluate(agg.arg, r.ctx, options)));
472 ctx[agg.key] = agg.fold(values);
473 }
474 out.push({ ctx, pristineRow: undefined });
475 }
476 return out;
477 }
478
479 /**
480 * @param {FromItem} item
481 * @param {Record<string, any>} scopeCtx
482 * @param {{functions?: Record<string, (...args: any[]) => any>}} options
483 */
484 function resolveFromItemArray(item, scopeCtx, options) {
485 const value = evaluate(item.expr, scopeCtx, options);
486 if (item.kind === 'Unnest') {
487 if (value === null || value === undefined) return [];
488 if (!Array.isArray(value)) throw new SqlEvaluationError('UNNEST requires an array value');
489 return value;
490 }
491 if (!Array.isArray(value)) throw new SqlEvaluationError('FROM/JOIN source must reference an array');
492 return value;
493 }
494
495 /**
496 * Binds a row into a context: its own fields (if it's a plain object) plus its alias.
497 * @param {Record<string, any>} baseCtx
498 * @param {any} row
499 * @param {string} alias
500 */
501 function bind(baseCtx, row, alias) {
502 const flat = isPlainObject(row) ? row : {};
503 return { ...baseCtx, ...flat, [alias]: row };
504 }
505
506 /** @param {any} v */
507 function isPlainObject(v) {
508 return typeof v === 'object' && v !== null && !Array.isArray(v);
509 }
510
511 /**
512 * @param {OrderItem[]} orderBy
513 * @param {{functions?: Record<string, (...args: any[]) => any>}} options
514 */
515 function makeRowComparator(orderBy, options) {
516 return (a, b) => {
517 for (const item of orderBy) {
518 const va = evaluate(item.expr, a.ctx, options);
519 const vb = evaluate(item.expr, b.ctx, options);
520 // Nulls always sort last, regardless of ASC/DESC - checked before the
521 // direction flip below, so DESC never pulls nulls back to the front.
522 if (va === null && vb === null) continue;
523 if (va === null) return 1;
524 if (vb === null) return -1;
525 const cmp = compareForOrder(va, vb);
526 if (cmp !== 0) return item.dir === 'DESC' ? -cmp : cmp;
527 }
528 return 0;
529 };
530 }
531
532 /** @param {any} a @param {any} b */
533 function compareForOrder(a, b) {
534 const ta = typeof a;
535 const tb = typeof b;
536 if (ta !== tb || (ta !== 'number' && ta !== 'string' && ta !== 'boolean')) {
537 throw new SqlEvaluationError(`Cannot compare ${orderTypeName(a)} and ${orderTypeName(b)} in ORDER BY`);
538 }
539 if (a < b) return -1;
540 if (a > b) return 1;
541 return 0;
542 }
543
544 /** @param {any} v */
545 function orderTypeName(v) {
546 if (v === null) return 'null';
547 if (Array.isArray(v)) return 'array';
548 return typeof v;
549 }
550
551 /**
552 * @param {Select} select
553 * @param {Record<string, any>} ctx
554 * @param {{functions?: Record<string, (...args: any[]) => any>}} options
555 */
556 function project(select, ctx, options) {
557 if (select.kind === 'Star') return ctx;
558 if (select.kind === 'Shape') return evaluate(select.expr, ctx, options);
559 /** @type {Record<string, any>} */
560 const out = {};
561 for (const item of select.items) {
562 out[item.key] = evaluate(item.expr, ctx, options);
563 }
564 return out;
565 }
566
567 /**
568 * Parses (if needed) and executes a
569 * `SELECT ... FROM ... [WHERE ...] [GROUP BY ...] [HAVING ...] [ORDER BY ...] [LIMIT ...]` query.
570 * @param {string|Query} source - query text, or an already-parsed AST
571 * @param {Record<string, any>} context
572 * @param {{functions?: Record<string, (...args: any[]) => any>}} [options]
573 * @returns {any[]}
574 */
575 export function query(source, context, options) {
576 const ast = typeof source === 'string' ? parseQuery(source) : source;
577 return executeQuery(ast, context, options);
578 }