1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
//! Tokens to a syntax tree.
//!
//! # How the goal symbol is chosen
//!
//! The lexer refuses to guess whether a `/` is division or a regular expression, and hands the
//! question to whoever knows ([`Goal`]). This is that caller, and the rule it uses is a single
//! invariant, stated here once because every `Parser::advance` call depends on it:
//!
//! > **The goal is chosen when advancing *past* a token, by what may legally follow it.**
//!
//! A token that completes an operand is followed by an operator, so the parser advances past it
//! under [`Goal::Div`]. A token that demands an operand — an operator, an opening parenthesis,
//! the start of a statement — is followed by one, so the parser advances under [`Goal::RegExp`].
//! There is no lookahead buffer to invalidate and no rescanning, because a position is never
//! read twice: by the time the parser knows what a token is, it has already decided what may
//! come after it.
//!
//! # Recursion is bounded here, not by the operating system
//!
//! DR-0002 requires it, and requires it in the same commit as the recursion itself: a
//! recursive-descent parser handed `((((…` recurses once per bracket, and a stack overflow is
//! not a failure any `Result` can rescue — it takes the embedder's process with it. So every
//! recursive entry is counted, and refused past [`MAX_NESTING_DEPTH`]. The cap is a number we
//! chose rather than one the specification has an opinion about, and it is chosen from a
//! measurement of what a level of nesting actually costs — see the constant.
//! # How this module is laid out
//!
//! - `error` — [`ParseError`] and its kinds.
//! - `operator` — precedence, associativity, and the pairs §13 keeps apart.
//! - `expression` — the operator ladder of §13.4 – §13.16.
//! - `member` — `LeftHandSideExpression` (§13.3): member access, calls and `new`.
//! - `primary` — `PrimaryExpression` (§13.2), the operands everything else is built from.
//! - `array_literal` — `[…]` (§13.2.4), and the two different things a comma does inside one.
//! - `object_literal` — `{…}` (§13.2.5), which has no elisions and one rule about `__proto__`.
//! - `pattern` — refining either literal into the assignment pattern it covered (§13.15.5).
//! - `binding` — binding patterns (§14.3.3), which need no cover grammar and say so.
//! - `function` — function definitions (§15.2), and the `return` they make legal (§14.10).
//! - `strict` — where strict mode starts (§11.2.1) and what it takes away (§13.1.1).
//! - `method` — method definitions (§15.4), the last `PropertyDefinition` alternative.
//! - `arrow` — arrow functions (§15.3), and the cover grammar that reaches them.
//! - `template` — template literals (§13.2.8) and the tags that take them (§13.3).
//! - `statement` — the grammar of §14, and automatic semicolon insertion (§12.10).
//! - `declaration` — `var`, `let` and `const` (§14.3), and the early errors on them.
//! - `control` — conditionals, loops, `throw`, `break` and `continue` (§14.6 – §14.14).
//! - `for_statement` — the three-part `for` (§14.7.4), the one header read under `[~In]`.
//! - `for_in_of` — `for`-`in` and `for`-`of` (§14.7.5), which share that header.
//! - `labelled` — labelled statements (§14.13), the second and last place two tokens decide.
//! - `scope` — the early errors a statement list has about the names it declares (§14.2.1).
//! - `try_catch` — `try`, `catch` and `finally` (§14.15), and the early errors on a handler.
//! - `switch` — `switch` (§14.12), whose CaseBlock is one scope across all its clauses.
//! - `body` — what a function body inherits from the production that opened it.
//! - `class` — class definitions (§15.7), and the `super` they make legal (§13.3.7, §13.3.5).
//! - `class_element` — what a class body is made of: methods, fields and static blocks.
//! - `generator` — generators (§15.5), and the `[Yield]` grammar parameter they turn on.
//! - `asynchronous` — everything `async`: functions (§15.8), generators (§15.6), arrows (§15.9).
//! - `module` — the `Module` goal symbol and the `import` declarations only it admits (§16.2).
//! - `export` — §16.2.3's declarations, and the two rules that read the finished list.
//! - here — the `Parser` itself: the token it is looking at, how it advances, and the count
//! that bounds its recursion.
pub use EvalContext;
pub use ;
pub use parse_module;
pub use parse_script_with_label_rules_unchecked;
pub use ;
use crateExpr;
use crate;
use crateSpan;
/// How deeply the grammar may nest before the parser gives up.
///
/// ECMAScript sets no limit, so this is our refusal rather than the grammar's — which is the
/// point of giving it its own [`ParseErrorKind::TooDeeplyNested`] instead of dressing it up as a
/// syntax error.
///
/// # Where the number comes from
///
/// Measured in a debug build against a one-mebibyte stack — the smallest in common use — and
/// re-measured every time the grammar grows, because it falls every time the grammar grows:
///
/// | after | levels a mebibyte holds | cap |
/// | --- | --- | --- |
/// | primary expressions | 928 | 512 |
/// | prefix and binary operators | 304 | 128 |
/// | conditional, assignment, comma | 168 | 64 |
/// | member access, calls, `new`, update | 112 | 48 |
/// | conditionals and loops | 114 | 48 |
/// | `try`, `catch` and `finally` | 114 | 48 |
/// | `switch` | 114 | 48 |
/// | the `[In]` parameter, and `for` | 113 | 48 |
/// | `for`-`in` and `for`-`of` | 113 | 48 |
/// | labelled statements, and `with` | 113 | 48 |
/// | array literals | 82 | 48 |
/// | object literals | 73 | 48 |
/// | destructuring assignment patterns | 67 | 48 |
/// | functions, and `return` | 67 | 48 |
/// | arrow functions | 61 | 48 |
///
/// Each slice put another function between one bracket and the next. That is the trajectory to
/// expect, and it is why keeping the recursive path narrow counts as correctness work rather
/// than optimisation: every frame removed is nesting a real program is allowed to have. Two
/// slices have now bought depth back by moving locals out of a frame the recursion passes
/// through — the trick works because a debug build reuses no stack slots between match arms, so
/// an arm that cannot recurse is still paid for by every level that does.
///
/// The last row is the first in four slices to cost anything, and it cost one level: threading
/// the `[In]` grammar parameter through the five functions between `Expression` and
/// `RelationalExpression` puts one more local in each of their frames. That is what a grammar
/// parameter costs, it was paid knowingly, and the alternative — holding the flag on the parser —
/// would have saved it by making every place that resets `[+In]` a thing to remember rather than
/// a thing the compiler asks about.
///
/// The three before it cost nothing, and the reason is worth keeping: the count is one budget
/// shared by every kind of nesting, so what bounds it is whichever kind spends the most stack per
/// level. Statements are cheap next to expressions — a level of `if` is three frames where a
/// level of `(` is the whole precedence ladder — and measured alone they afford 339 levels,
/// `with` 508, `while` 504, a label 476, a block 392, a `for` 254, a `try` 221, a `for`-`in`
/// 202, a `switch` 185. None of them came near the expressions.
///
/// The array literal is the first thing that did, and it took the lead: `[[[…]]]` recurses
/// through the whole precedence ladder *and* two frames of its own, so it affords 82 levels where
/// `(((…)))` affords 113. The object literal then took it from the array. Expressions no longer
/// set this number — the narrowest bracket does, and every literal with a bracket in it is a
/// candidate, which is now most of them.
///
/// As of the arrows, the standings are: object literal 61, array literal 77, an arrow 130, a
/// parenthesized expression 138, a function 251. The parentheses got *cheaper*: an assignment
/// level now opens them itself, looking for a `=>`, which is a shallower path than the operand
/// ladder they used to be read through. The refinement is not the binding one and was never likely to be — it
/// recurses over a tree the parse has already finished with, so its frames replace the parse's
/// rather than adding to them.
///
/// Stack is not the only thing a level spends, though, and the two newest forms show it. A `try`
/// takes *two* of the count on each level, one for the statement and one for its guarded `Block`,
/// so `try {` nests 32 deep against a cap of 64 where `{` nests 64. A `switch` takes one for its
/// CaseBlock and borrows a second while it reads the expression after `case`, so it nests 63. In
/// both the count is doing exactly what it should: those really are separate scopes and separate
/// descents, and the cap is about what the machine can afford rather than about tidy numbers.
///
/// A class costs one level for the whole definition, which bounds both of its recursions at
/// once: `class C extends class … {}` through the heritage, and `class C { m() { class D …`
/// through the method bodies. Nothing else was counting the second — a class body is not a
/// `Block` and a function body does not count either — so it was unbounded until this slice.
///
/// `parsing_at_the_cap_fits_in_the_stack_it_claims_to_need` runs a full-depth parse of each
/// recursive path in a thread with exactly one mebibyte. That test is the real specification of
/// this constant: raise the cap, or make a level cost more stack, and it fails.
///
/// # What the measurement says, and why the number is 64
///
/// It was 48, and a sweep of real code is what moved it: a generated protobuf file writes fifty
/// `exports.A = exports.B = … = void 0` assignments in one statement, which right-associate into
/// fifty levels. Every engine takes it and this one refused it. Nothing about 48 was measured — it
/// was a first guess that never had a program argue with it.
///
/// So each path was bisected against one mebibyte in a *debug* build, one process per candidate,
/// because a stack overflow aborts and cannot be caught. Per level:
///
/// | shape | levels in 1 MiB | per level |
/// | --- | --- | --- |
/// | `{` a block | 327 | 3.1 KiB |
/// | `(` a parenthesized expression | 152 | 6.7 KiB |
/// | `[` an array literal | 71 | 14.4 KiB |
/// | `[` refined into a pattern | 70 | 14.6 KiB |
///
/// Seventy is the ceiling, so 64 is the cap: it clears the evidence with thirteen levels to
/// spare and leaves the narrowest path a margin of 1.09×. That margin is thin and is stated
/// rather than hidden — the ratio is comfort and the test below is the guarantee, which is the
/// same position this note took when the margin was 1.3×. A debug build is what is being measured
/// and a release one is several times cheaper, so an embedder's real margin is far larger; the
/// thin number is a warning about *this repository's* CI, not about shipped code.
///
/// The array literal looked like the outlier and is not, which `lab/`'s `nesting-cost` experiment
/// settled: `a[0][0]…` costs the same 14.6 KiB and never touches `parse_array_literal`. What both
/// pay for is the descent `parse_assignment -> parse_binary -> parse_unary -> parse_member ->
/// parse_primary`, about six frames at the 2.5 KiB one frame costs — and `(` is cheap for the
/// complementary reason, being intercepted at the assignment level before the ladder starts.
///
/// So there is nothing here to make cheaper: no frame is fat, and shaving two of them off the
/// path measured *worse* than leaving them. The same experiment found that release is 5.5× cheaper
/// than debug, which is where the headroom actually is — the cap could be around 260 at a
/// comfortable margin if it were allowed to depend on the build, and DR-0006 says it may not. The
/// lab notebook has the numbers and the argument.
///
/// # What real code asks for
///
/// 64 is a number this repository chose; the number the world asks for was measured separately,
/// by sweeping 4,733 minified files — 120 MB of what npm actually ships, plus every built library
/// WordPress and Moodle vendor. Two files went past the cap. They are two copies of the same
/// Emscripten-generated Draco decoder, and bisecting the constant against one of them says it
/// needs **77**: thirteen more than there is.
///
/// That is close enough to be worth stating precisely and still out of reach, because 77 is past
/// the 70 the narrowest path survives in the build being asserted against. Nothing else came
/// near: WordPress's and Moodle's 4,589 built files all parse, and so does every other bundle
/// fetched. The shape is not "minified code nests deeply" — it is one code generator emitting
/// labelled blocks where a person would write anything else.
///
/// # Why a count and not a stack measurement
///
/// Because a stack measurement would make which programs parse depend on how the engine was
/// compiled, and this project's whole premise is a conformance number that does not drift.
/// DR-0006 has the argument, including what it costs — a release build could afford several
/// times this and is not allowed to. The limit becomes an embedder-set value at M3, where
/// somebody knows how much stack there actually is; the default stays conservative.
pub const MAX_NESTING_DEPTH: u32 = 64;
/// Parse `source` as a single expression, which must be all of it.
///
/// A convenience beside [`parse_script`], which is the entry point a program goes through.
/// Useful where an expression is all there is — and, more often, in tests about one.
///
/// ```
/// use viperjs::ast::ExprKind;
/// use viperjs::parser::parse_expression;
///
/// let expr = parse_expression("(1)").expect("this parses");
/// assert_eq!(expr.kind, ExprKind::Number(1.0));
/// assert!(expr.parenthesized);
/// ```
/// A rule an `ObjectLiteral` owes, held until something says whether it is still a literal.
///
/// See [`Parser::unrefined_covers`] for what is recorded and [`Parser::discard_refined_covers`]
/// for how one settles.
pub
/// A recursive-descent parser over one source text.
/// Whether a `LabelledStatement` beginning here may label a `FunctionDeclaration` — §B.3.2.
///
/// Annex B's labelled function is conditioned on more than strictness, and this is the more.
/// §14.6.1, §14.7.2.1, §14.7.3.1, §14.7.4.1, §14.7.5.1 and §14.11.1 each state "It is a Syntax
/// Error if `IsLabelledFunction(Statement)` is true" of a position whose body is a `Statement`
/// rather than a `StatementList` — so `{ a: function f() {} }` is B.3.2's to take and
/// `while (x) a: function f() {}` stays refused, sloppy though both are.
///
/// An argument to [`Parser::parse_statement`] rather than a field on the parser, so that each body
/// position states the rule where the specification states it. A field would have had an initial
/// value that no input could reach — every entry point goes through a statement list first — which
/// is a value that cannot be got wrong and cannot be shown right either.
pub