[pseudo] Add error-recovery framework & brace-based recovery
authorSam McCall <sam.mccall@gmail.com>
Wed, 29 Jun 2022 11:48:00 +0000 (13:48 +0200)
committerSam McCall <sam.mccall@gmail.com>
Tue, 5 Jul 2022 18:49:41 +0000 (20:49 +0200)
commit31211674889095299eb817d7be034fde23f7b00a
tree092521f78290f22ad10d609f4711a90c8dbc9bd7
parent1562b1dcb978153b274fcee61b12b0a8dd80afe6
[pseudo] Add error-recovery framework & brace-based recovery

The idea is:

- a parse failure is detected when all heads die when trying to shift the next token
- we can recover by choosing a nonterminal we're partway through parsing, and
  determining where it ends through nonlocal means (e.g. matching brackets)
- we can find candidates by walking up the stack from the (ex-)heads
- the token range is defined using heuristics attached to grammar rules
- the unparsed region is represented in the forest by an Opaque node

This patch has the core GLR functionality.
It does not allow recovery heuristics to be attached as extensions to
the grammar, but rather infers a brace-based heuristic.

Expected followups:

- make recovery heuristics grammar extensions (depends on D127448)
- add recovery to our grammar for bracketed constructs and sequence nodes
- change the structure of our augmented `_ := start` rules to eliminate some
  special-cases in glrParse.
- (if I can work out how): avoid some spurious recovery cases described in comments

(Previously mistakenly committed as a0f4c10ae227a62c2a63611e64eba83f0ff0f577)

Differential Revision: https://reviews.llvm.org/D128486
12 files changed:
clang-tools-extra/pseudo/include/clang-pseudo/GLR.h
clang-tools-extra/pseudo/include/clang-pseudo/grammar/Grammar.h
clang-tools-extra/pseudo/include/clang-pseudo/grammar/LRGraph.h
clang-tools-extra/pseudo/include/clang-pseudo/grammar/LRTable.h
clang-tools-extra/pseudo/lib/GLR.cpp
clang-tools-extra/pseudo/lib/grammar/Grammar.cpp
clang-tools-extra/pseudo/lib/grammar/GrammarBNF.cpp
clang-tools-extra/pseudo/lib/grammar/LRGraph.cpp
clang-tools-extra/pseudo/lib/grammar/LRTableBuild.cpp
clang-tools-extra/pseudo/test/cxx/empty-member-spec.cpp
clang-tools-extra/pseudo/test/cxx/recovery-init-list.cpp [new file with mode: 0644]
clang-tools-extra/pseudo/unittests/GLRTest.cpp