Blog/wwwroot/jsonql-js/parser.js 12.7 K · 439 lines · raw · history

1 import { tokenize } from './lexer.js';
2 import { SqlSyntaxError } from './errors.js';
3
4 /**
5 * AST node shapes produced by the parser:
6 *
7 * @typedef {{type: 'Literal', value: string|number|boolean|null}} LiteralNode
8 * @typedef {{type: 'ArrayLiteral', elements: Expr[]}} ArrayLiteralNode
9 * @typedef {{type: 'ObjectLiteral', properties: {key: string, value: Expr}[]}} ObjectLiteralNode
10 * @typedef {{type: 'Identifier', name: string}} IdentifierNode
11 * @typedef {{type: 'Member', object: Expr, property: string}} MemberNode
12 * @typedef {{type: 'Index', object: Expr, index: Expr}} IndexNode
13 * @typedef {{type: 'Unnest', object: Expr}} UnnestNode
14 * @typedef {{type: 'Star'}} StarNode - the `*` of `COUNT(*)`; only ever a Call argument
15 * @typedef {{type: 'Call', name: string, args: (Expr|StarNode)[]}} CallNode
16 * @typedef {{type: 'Negate', expr: Expr}} NegateNode
17 * @typedef {{type: 'Not', expr: Expr}} NotNode
18 * @typedef {{type: 'Logical', op: 'AND'|'OR', left: Expr, right: Expr}} LogicalNode
19 * @typedef {{type: 'Comparison', op: '='|'!='|'<'|'>'|'<='|'>=', left: Expr, right: Expr}} ComparisonNode
20 * @typedef {{type: 'IsNull', expr: Expr, negate: boolean}} IsNullNode
21 * @typedef {{type: 'Like', expr: Expr, pattern: Expr, negate: boolean}} LikeNode
22 * @typedef {{type: 'InList', expr: Expr, items: Expr[], negate: boolean}} InListNode
23 * @typedef {{type: 'InArray', expr: Expr, array: Expr, negate: boolean}} InArrayNode
24 * @typedef {{type: 'Binary', op: '+'|'-'|'*'|'/'|'%'|'||', left: Expr, right: Expr}} BinaryNode
25 * @typedef {LiteralNode|ArrayLiteralNode|ObjectLiteralNode|IdentifierNode|MemberNode|IndexNode|UnnestNode|CallNode|StarNode|NegateNode|NotNode|LogicalNode|ComparisonNode|IsNullNode|LikeNode|InListNode|InArrayNode|BinaryNode} Expr
26 */
27
28 const COMPARISON_OPS = new Set(['=', '!=', '<>', '<', '>', '<=', '>=']);
29
30 export class Parser {
31 /** @param {import('./lexer.js').Token[]} tokens */
32 constructor(tokens) {
33 this.tokens = tokens;
34 this.pos = 0;
35 }
36
37 peek() {
38 return this.tokens[this.pos];
39 }
40
41 peekNext() {
42 return this.tokens[this.pos + 1];
43 }
44
45 next() {
46 return this.tokens[this.pos++];
47 }
48
49 /** @param {string} type */
50 check(type) {
51 return this.peek().type === type;
52 }
53
54 /** @param {string} type */
55 expect(type) {
56 const t = this.peek();
57 if (t.type !== type) {
58 throw new SqlSyntaxError(`Expected ${type} but found ${describeToken(t)}`, t);
59 }
60 return this.next();
61 }
62
63 /** @returns {Expr} */
64 parseExpression() {
65 const expr = this.parseOr();
66 this.expect('eof');
67 return expr;
68 }
69
70 /** @returns {Expr} */
71 parseOr() {
72 let node = this.parseAnd();
73 while (this.check('OR')) {
74 this.next();
75 const right = this.parseAnd();
76 node = { type: 'Logical', op: 'OR', left: node, right };
77 }
78 return node;
79 }
80
81 /** @returns {Expr} */
82 parseAnd() {
83 let node = this.parseNot();
84 while (this.check('AND')) {
85 this.next();
86 const right = this.parseNot();
87 node = { type: 'Logical', op: 'AND', left: node, right };
88 }
89 return node;
90 }
91
92 /** @returns {Expr} */
93 parseNot() {
94 if (this.check('NOT')) {
95 this.next();
96 const expr = this.parseNot();
97 return { type: 'Not', expr };
98 }
99 return this.parseComparison();
100 }
101
102 /** @returns {Expr} */
103 parseComparison() {
104 const left = this.parseAdditive();
105 const t = this.peek();
106
107 if (COMPARISON_OPS.has(t.type)) {
108 this.next();
109 const right = this.parseAdditive();
110 return { type: 'Comparison', op: t.type === '<>' ? '!=' : t.type, left, right };
111 }
112 if (t.type === 'IS') {
113 this.next();
114 let negate = false;
115 if (this.check('NOT')) {
116 negate = true;
117 this.next();
118 }
119 this.expect('NULL');
120 return { type: 'IsNull', expr: left, negate };
121 }
122 if (t.type === 'BETWEEN') {
123 this.next();
124 return this.finishBetween(left, false);
125 }
126 if (t.type === 'LIKE') {
127 this.next();
128 const pattern = this.parseAdditive();
129 return { type: 'Like', expr: left, pattern, negate: false };
130 }
131 if (t.type === 'IN') {
132 this.next();
133 return this.parseInRhs(left, false);
134 }
135 if (t.type === 'NOT') {
136 const t2 = this.peekNext();
137 if (t2.type === 'LIKE') {
138 this.next();
139 this.next();
140 const pattern = this.parseAdditive();
141 return { type: 'Like', expr: left, pattern, negate: true };
142 }
143 if (t2.type === 'IN') {
144 this.next();
145 this.next();
146 return this.parseInRhs(left, true);
147 }
148 if (t2.type === 'BETWEEN') {
149 this.next();
150 this.next();
151 return this.finishBetween(left, true);
152 }
153 }
154 return left;
155 }
156
157 /**
158 * @param {Expr} left
159 * @param {boolean} negate
160 * @returns {Expr}
161 */
162 finishBetween(left, negate) {
163 const lo = this.parseAdditive();
164 this.expect('AND');
165 const hi = this.parseAdditive();
166 if (!negate) {
167 return {
168 type: 'Logical',
169 op: 'AND',
170 left: { type: 'Comparison', op: '>=', left, right: lo },
171 right: { type: 'Comparison', op: '<=', left, right: hi },
172 };
173 }
174 return {
175 type: 'Logical',
176 op: 'OR',
177 left: { type: 'Comparison', op: '<', left, right: lo },
178 right: { type: 'Comparison', op: '>', left, right: hi },
179 };
180 }
181
182 /**
183 * @param {Expr} left
184 * @param {boolean} negate
185 * @returns {Expr}
186 */
187 parseInRhs(left, negate) {
188 if (this.check('(')) {
189 this.next();
190 const items = [this.parseOr()];
191 while (this.check(',')) {
192 this.next();
193 items.push(this.parseOr());
194 }
195 this.expect(')');
196 return { type: 'InList', expr: left, items, negate };
197 }
198 const array = this.parseAdditive();
199 return { type: 'InArray', expr: left, array, negate };
200 }
201
202 /** @returns {Expr} */
203 parseAdditive() {
204 let node = this.parseMultiplicative();
205 while (this.check('+') || this.check('-') || this.check('||')) {
206 const op = /** @type {'+'|'-'|'||'} */ (this.next().type);
207 const right = this.parseMultiplicative();
208 node = { type: 'Binary', op, left: node, right };
209 }
210 return node;
211 }
212
213 /** @returns {Expr} */
214 parseMultiplicative() {
215 let node = this.parseUnary();
216 while (this.check('*') || this.check('/') || this.check('%')) {
217 const op = /** @type {'*'|'/'|'%'} */ (this.next().type);
218 const right = this.parseUnary();
219 node = { type: 'Binary', op, left: node, right };
220 }
221 return node;
222 }
223
224 /** @returns {Expr} */
225 parseUnary() {
226 if (this.check('-')) {
227 this.next();
228 const expr = this.parseUnary();
229 return { type: 'Negate', expr };
230 }
231 return this.parsePostfix();
232 }
233
234 /** @returns {Expr} */
235 parsePostfix() {
236 let node = this.parsePrimary();
237 while (true) {
238 if (this.check('.')) {
239 this.next();
240 const idTok = this.expectIdentLike();
241 node = { type: 'Member', object: node, property: idTok.value };
242 } else if (this.check('[')) {
243 this.next();
244 if (this.check(']')) {
245 this.next();
246 node = { type: 'Unnest', object: node };
247 } else {
248 const index = this.parseOr();
249 this.expect(']');
250 node = { type: 'Index', object: node, index };
251 }
252 } else {
253 break;
254 }
255 }
256 return node;
257 }
258
259 expectIdentLike() {
260 const t = this.peek();
261 if (t.type !== 'ident') {
262 throw new SqlSyntaxError(`Expected a property name but found ${describeToken(t)}`, t);
263 }
264 return this.next();
265 }
266
267 /** @returns {ObjectLiteralNode} */
268 parseObjectLiteral() {
269 this.expect('{');
270 /** @type {{key: string, value: Expr}[]} */
271 const properties = [];
272 if (!this.check('}')) {
273 properties.push(this.parseObjectProperty());
274 while (this.check(',')) {
275 this.next();
276 properties.push(this.parseObjectProperty());
277 }
278 }
279 this.expect('}');
280 return { type: 'ObjectLiteral', properties };
281 }
282
283 /** @returns {{key: string, value: Expr}} */
284 parseObjectProperty() {
285 if (this.check('ident') && this.peekNext().type === ':') {
286 const keyTok = this.next();
287 this.next();
288 const value = this.parseOr();
289 return { key: keyTok.value, value };
290 }
291 const startTok = this.peek();
292 const value = this.parseOr();
293 return { key: inferPathKey(value, startTok), value };
294 }
295
296 /** @returns {Expr} */
297 parsePrimary() {
298 const t = this.peek();
299 switch (t.type) {
300 case 'number':
301 this.next();
302 return { type: 'Literal', value: t.value };
303 case 'string':
304 this.next();
305 return { type: 'Literal', value: t.value };
306 case 'TRUE':
307 this.next();
308 return { type: 'Literal', value: true };
309 case 'FALSE':
310 this.next();
311 return { type: 'Literal', value: false };
312 case 'NULL':
313 this.next();
314 return { type: 'Literal', value: null };
315 case '(': {
316 this.next();
317 const expr = this.parseOr();
318 this.expect(')');
319 return expr;
320 }
321 case '[': {
322 this.next();
323 /** @type {Expr[]} */
324 const elements = [];
325 if (!this.check(']')) {
326 elements.push(this.parseOr());
327 while (this.check(',')) {
328 this.next();
329 elements.push(this.parseOr());
330 }
331 }
332 this.expect(']');
333 return { type: 'ArrayLiteral', elements };
334 }
335 case '{':
336 return this.parseObjectLiteral();
337 case 'ident': {
338 this.next();
339 if (this.check('(')) {
340 this.next();
341 /** @type {(Expr|StarNode)[]} */
342 const args = [];
343 // `*` is a value nowhere else in the grammar, so it is only accepted
344 // as the whole argument list of COUNT.
345 if (this.check('*') && t.value.toUpperCase() === 'COUNT') {
346 this.next();
347 args.push({ type: 'Star' });
348 } else if (!this.check(')')) {
349 args.push(this.parseOr());
350 while (this.check(',')) {
351 this.next();
352 args.push(this.parseOr());
353 }
354 }
355 this.expect(')');
356 return { type: 'Call', name: t.value, args };
357 }
358 return { type: 'Identifier', name: t.value };
359 }
360 default:
361 throw new SqlSyntaxError(`Unexpected token ${describeToken(t)}`, t);
362 }
363 }
364 }
365
366 /** @param {import('./lexer.js').Token} t */
367 function describeToken(t) {
368 if (t.type === 'eof') return 'end of input';
369 return JSON.stringify(t.value ?? t.type);
370 }
371
372 /**
373 * Rebuilds `node` with each of its direct child expressions replaced by `fn(child)`.
374 * Leaf nodes are returned as-is; anything else is shallow-copied, so a rewrite never
375 * mutates the AST it walks (a parsed query can be executed more than once).
376 * @param {Expr} node
377 * @param {(child: Expr) => Expr} fn
378 * @returns {Expr}
379 */
380 export function mapChildren(node, fn) {
381 switch (node.type) {
382 case 'Literal':
383 case 'Identifier':
384 case 'Star':
385 return node;
386 case 'ArrayLiteral':
387 return { ...node, elements: node.elements.map(fn) };
388 case 'ObjectLiteral':
389 return { ...node, properties: node.properties.map((p) => ({ ...p, value: fn(p.value) })) };
390 case 'Member':
391 case 'Unnest':
392 return { ...node, object: fn(node.object) };
393 case 'Index':
394 return { ...node, object: fn(node.object), index: fn(node.index) };
395 case 'Call':
396 return { ...node, args: node.args.map(fn) };
397 case 'Negate':
398 case 'Not':
399 case 'IsNull':
400 return { ...node, expr: fn(node.expr) };
401 case 'Logical':
402 case 'Comparison':
403 case 'Binary':
404 return { ...node, left: fn(node.left), right: fn(node.right) };
405 case 'Like':
406 return { ...node, expr: fn(node.expr), pattern: fn(node.pattern) };
407 case 'InList':
408 return { ...node, expr: fn(node.expr), items: node.items.map(fn) };
409 case 'InArray':
410 return { ...node, expr: fn(node.expr), array: fn(node.array) };
411 default:
412 return node;
413 }
414 }
415
416 /**
417 * Infers a property/column key from a bare (unaliased) expression: an `Identifier`
418 * uses its own name, a `Member` chain uses its trailing `.property`. Anything else
419 * has no natural name and must be given one explicitly (`key: expr` / `expr AS key`).
420 * @param {Expr} expr
421 * @param {import('./lexer.js').Token} atToken - used for error position
422 * @returns {string}
423 */
424 export function inferPathKey(expr, atToken) {
425 if (expr.type === 'Identifier') return expr.name;
426 if (expr.type === 'Member') return expr.property;
427 throw new SqlSyntaxError('Cannot infer a name for this expression; give it one explicitly (`key: expr` or `expr AS key`)', atToken);
428 }
429
430 /**
431 * Parses a SQL-like expression string into an AST.
432 * @param {string} source
433 * @returns {Expr}
434 */
435 export function parseExpression(source) {
436 const tokens = tokenize(source);
437 const parser = new Parser(tokens);
438 return parser.parseExpression();
439 }