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