clang-tools-extra/pseudo/DesignNotes.md

   1 # Error recovery (2022-05-07)
   2
   3 Problem: we have two fairly generic cases of recovery bounded within a range:
   4  - sequences: `int x; this is absolute garbage; x++;`
   5  - brackets: `void foo() { this is garbage too }`
   6
   7 So far, we've thought of these as different, and had precise ideas about
   8 brackets ("lazy parsing") and vague ones about sequences.
   9 Con we unify them instead?
  10
  11 In both cases we want to recognize the bounds of the garbage item based on
  12 basic token-level features of the surrounding code, and avoid any interference
  13 with the surrounding code.
  14
  15 ## Brackets
  16
  17 Consider a rule like `compound-stmt := { stmt-seq }`.
  18
  19 The desired recovery is:
  20 - if we fail at `{ . stmt-seq }`
  21 - ... and we can find for the matching `}`
  22 - then consume up to that token as an opaque broken `stmt-seq`
  23 - ... and advance state to `{ stmt-seq . }`
  24
  25 We can annotate the rule to describe this: `{ stmt-seq [recovery] }`.
  26 We can generalize as `{ stmt-seq [recovery=rbrace] }`, allowing for different
  27 **strategies** to find the resume point.
  28
  29 (It's OK to assume we're skipping over one RHS nonterminal, we can always
  30 introduce a nonterminal for the bracket contents if necessary).
  31
  32 ## Sequences
  33
  34 Can we apply the same technique to sequences?
  35 Simplest case: delimited right-recursive sequence.
  36
  37 ```
  38 param-list := param
  39 param-list := param , param-list
  40 ```
  41
  42 We need recovery in **both** rules.
  43 `param` in the first rule matches the *last* param in a list,
  44 in the second rule it matches all others. We want to recover in any position.
  45
  46 If we want to be able to recovery `int x int y` as two parameters, then we
  47 should extract a `param-and-comma` rule that recovery could operate on.
  48
  49 ### Last vs not-last elements
  50
  51 Sequences will usually have two rules with recovery, we discussed:
  52  - how to pick the correct one to recover with
  53  - in a left-recursive rule they correspond to last & not-last elements
  54  - the recovery strategy knows whether we're recoverying last or not-last
  55  - we could have the strategy return (pos, symbol parsed), and artificially
  56    require distinct symbols (e.g. `stmt` vs `last_stmt`).
  57  - we can rewrite left-recursion in the grammar as right-recursion
  58
  59 However, on reflection I think we can simply allow recovery according to both
  60 rules. The "wrong" recovery will produce a parse head that dies.
  61
  62 ## How recovery fits into GLR
  63
  64 Recovery should kick in at the point where we would otherwise abandon all
  65 variants of an high-level parse.
  66
  67 e.g. Suppose we're parsing `static_cast<foo bar baz>(1)` and are up to `bar`.
  68 Our GSS looks something like:
  69
  70 ```
  71      "the static cast's type starts at foo"
  72 ---> {expr := static_cast < . type > ( expr )}
  73          |     "foo... is a class name"
  74          +---- {type := identifier .}
  75          |     "foo... is a template ID"
  76          +---- {type := identifier . < template-arg-list >}
  77 ```
  78
  79 Since `foo bar baz` isn't a valid class name or template ID, both active heads
  80 will soon die, as will the parent GSS Node - the latter should trigger recovery.
  81
  82 - we need a refcount in GSS nodes so we can recognize never-reduced node death
  83 - when a node dies, we look up its recovery actions (symbol, strategy).
  84   These are the union of the recovery actions for each item.
  85   They can be stored in the action table.
  86   Here: `actions[State, death] = Recovery(type, matching-angle-bracket)`
  87 - we try each strategy: feeding in the start position = token of the dying node
  88   (`foo`) getting out the end position (`>`).
  89 - We form an opaque forest node with the correct symbol (`type`) spanning
  90   [start, end)
  91 - We create a GSS node to represent the state after recovery.
  92   The new state is found in the Goto table in the usual way.
  93
  94 ```
  95      "the static cast's type starts at foo"
  96 ---> {expr := static_cast < . type > ( expr )}
  97          |     "`foo bar baz` is an unparseable type"
  98          +---- {expr := static_cast < type . > (expr)}
  99 ```
 100
 101 ## Which recovery heads to activate
 102
 103 We probably shouldn't *always* create active recovery heads when a recoverable
 104 node dies (and thus keep it alive).
 105 By design GLR creates multiple speculative parse heads and lets incorrect heads
 106 disappear.
 107
 108 Concretely, the expression `(int *)(x)` is a valid cast, we probably shouldn't
 109 also parse it as a call whose callee is a broken expr.
 110
 111 The simplest solution is to only create recovery heads if there are no normal
 112 heads remaining, i.e. if parsing is completely stuck. This is vulnerable if the
 113 "wrong" parse makes slightly more progress than the "right" parse which has
 114 better error recovery.
 115
 116 A sophisticated variant might record recovery opportunities and pick the one
 117 with the rightmost *endpoint* when the last parse head dies.
 118
 119 We should consider whether including every recovery in the parse forest might
 120 work after all - this would let disambiguation choose "broken" but likely parses
 121 over "valid" but unlikely ones.
 122
 123