[pseudo] Allow opaque nodes to represent terminals

This allows incomplete code such as `namespace foo {` to be modeled as a
normal sequence with the missing } represented by an empty opaque node.

D

[pseudo] Allow opaque nodes to represent terminals

This allows incomplete code such as `namespace foo {` to be modeled as a
normal sequence with the missing } represented by an empty opaque node.

Differential Revision: https://reviews.llvm.org/D130551

show more ...

[pseudo] Eliminate the dangling-else syntax ambiguity.

- the grammar ambiguity is eliminated by a guard;
- modify the guard function signatures, now all parameters are folded in
to a single object

[pseudo] Eliminate the dangling-else syntax ambiguity.

- the grammar ambiguity is eliminated by a guard;
- modify the guard function signatures, now all parameters are folded in
to a single object, avoid a long parameter list (as we will add more
parameters in the near future);

Reviewed By: sammccall

Differential Revision: https://reviews.llvm.org/D130160

show more ...

[pseudo] Key guards by RuleID, add guards to literals (and 0).

After this, NUMERIC_CONSTANT and strings should parse only one way.

There are 8 types of literals, and 24 valid (literal, TokenKind) p

[pseudo] Key guards by RuleID, add guards to literals (and 0).

After this, NUMERIC_CONSTANT and strings should parse only one way.

There are 8 types of literals, and 24 valid (literal, TokenKind) pairs.
This means adding 8 new named guards (or 24, if we want to assert the token).

It seems fairly clear to me at this point that the guard names are unneccesary
indirection: the guards are in fact coupled to the rule signature.

(Also add the zero guard I forgot in the previous patch.)

Differential Revision: https://reviews.llvm.org/D130066

show more ...

[clang, clang-tools-extra] Use has_value instead of hasValue (NFC)

[pseudo] Define recovery strategy as grammar extension.

Differential Revision: https://reviews.llvm.org/D129158

[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 nonterm

[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

show more ...

[pseudo] Implement guard extension.

- Extend the GLR parser to allow conditional reduction based on the
guard functions;
- Implement two simple guards (contextual-override/final) for cxx.bnf;
- la

[pseudo] Implement guard extension.

- Extend the GLR parser to allow conditional reduction based on the
guard functions;
- Implement two simple guards (contextual-override/final) for cxx.bnf;
- layering: clangPseudoCXX depends on clangPseudo (as the guard function need
to access the TokenStream);

Differential Revision: https://reviews.llvm.org/D127448

show more ...

[pseudo] Store shift and goto actions in a compact structure with faster lookup.

The actions table is very compact but the binary search to find the
correct action is relatively expensive.
A hashtab

[pseudo] Store shift and goto actions in a compact structure with faster lookup.

The actions table is very compact but the binary search to find the
correct action is relatively expensive.
A hashtable is faster but pretty large (64 bits per value, plus empty
slots, and lookup is constant time but not trivial due to collisions).

The structure in this patch uses 1.25 bits per entry (whether present or absent)
plus the size of the values, and lookup is trivial.

The Shift table is 119KB = 27KB values + 92KB keys.
The Goto table is 86KB = 30KB values + 57KB keys.
(Goto has a smaller keyspace as #nonterminals < #terminals, and more entries).

This patch improves glrParse speed by 28%: 4.69 => 5.99 MB/s
Overall the table grows by 60%: 142 => 228KB.

By comparison, DenseMap<unsigned, StateID> is "only" 16% faster (5.43 MB/s),
and results in a 285% larger table (547 KB) vs the baseline.

Differential Revision: https://reviews.llvm.org/D128485

show more ...

Revert "[pseudo] Add error-recovery framework & brace-based recovery"

This reverts commit a0f4c10ae227a62c2a63611e64eba83f0ff0f577.
This commit hadn't been reviewed yet, and was unintentionally incl

Revert "[pseudo] Add error-recovery framework & brace-based recovery"

This reverts commit a0f4c10ae227a62c2a63611e64eba83f0ff0f577.
This commit hadn't been reviewed yet, and was unintentionally included
on another branch.

show more ...

[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 non

[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 recover 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
- grammar changes to eliminate the hard distinction between init-list
and designated-init-list shown in the recovery-init-list.cpp testcase

Differential Revision: https://reviews.llvm.org/D128486

show more ...

[pseudo] Check follow-sets instead of tying reduce actions to lookahead tokens.

Previously, the action table stores a reduce action for each lookahead
token it should allow. These tokens are the fol

[pseudo] Check follow-sets instead of tying reduce actions to lookahead tokens.

Previously, the action table stores a reduce action for each lookahead
token it should allow. These tokens are the followSet(action.rule.target).

In practice, the follow sets are large, so we spend a bunch of time binary
searching around all these essentially-duplicates to check whether our lookahead
token is there.
However the number of reduces for a given state is very small, so we're
much better off linear scanning over them and performing a fast check for each.

D128318 was an attempt at this, storing a bitmap for each reduce.
However it's even more compact just to use the follow sets directly, as
there are fewer nonterminals than (state, rule) pairs. It's also faster.

This specialized approach means unbundling Reduce from other actions in
LRTable, so it's no longer useful to support it in Action. I suspect
Action will soon go away, as we store each kind of action separately.

This improves glrParse speed by 42% (3.30 -> 4.69 MB/s).
It also reduces LR table size by 59% (343 -> 142kB).

Differential Revision: https://reviews.llvm.org/D128472

show more ...

Don't use Optional::hasValue (NFC)

This patch replaces x.hasValue() with x where x is contextually
convertible to bool.

Revert "Don't use Optional::hasValue (NFC)"

This reverts commit aa8feeefd3ac6c78ee8f67bf033976fc7d68bc6d.

Don't use Optional::hasValue (NFC)

[pseudo] Handle no-reductions-available on the fastpath. NFC

This is a ~2% speedup.

[pseudo] Store last node popped in the queue, not its parent(s). NFC

We have to walk up to the last node to find the start token, but no need
to go even one node further.

This is one node fewer to

[pseudo] Store last node popped in the queue, not its parent(s). NFC

We have to walk up to the last node to find the start token, but no need
to go even one node further.

This is one node fewer to store, but more importantly if the last node
happens to have multiple parents we avoid storing the sequence multiple times.

This saves ~5% on glrParse.
Based on a comment by hokein@ on https://reviews.llvm.org/D128307

show more ...

[pseudo] Store reduction sequences by pointer in heaps, instead of by value.

Copying sequences around as the heap resized is significantly expensive.

This speeds up glrParse by ~35% (2.4 => 3.25 MB

[pseudo] Store reduction sequences by pointer in heaps, instead of by value.

Copying sequences around as the heap resized is significantly expensive.

This speeds up glrParse by ~35% (2.4 => 3.25 MB/s)

Differential Revision: https://reviews.llvm.org/D128307

show more ...

[pseudo] Turn glrReduce into a class, reuse storage across calls.

This is a ~5% speedup, we no longer have to allocate the priority queues and
other collections for each reduction step where we use

[pseudo] Turn glrReduce into a class, reuse storage across calls.

This is a ~5% speedup, we no longer have to allocate the priority queues and
other collections for each reduction step where we use them.

It's also IMO easier to understand the structure of a class with methods vs a
function with nested lambdas.

Differential Revision: https://reviews.llvm.org/D128301

show more ...

[pseudo] Add a fast-path to GLR reduce when both pop and push are trivial

In general we split a reduce into pop/push, so concurrently-available reductions
can run in the correct order. The data stru

[pseudo] Add a fast-path to GLR reduce when both pop and push are trivial

In general we split a reduce into pop/push, so concurrently-available reductions
can run in the correct order. The data structures for this are expensive.

When only one reduction is possible at a time, we need not do this: we can pop
and immediately push instead.
Strictly this is correct whenever we yield one concurrent PushSpec.

This patch recognizes a trivial but common subset of these cases:
- there must be no pending pushes and only one head available to pop
- the head must have only one reduction rule
- the reduction path must be a straight line (no multiple parents)

On my machine this speeds up by 2.12 -> 2.30 MB/s = 8%

Differential Revision: https://reviews.llvm.org/D128299

show more ...

Reland "[pseudo] Track heads as GSS nodes, rather than as "pending actions"."

This reverts commit 2c80b5319870b57fbdbb6c9cef9c86c26c65371d.

Fixes LRTable::buildForTest to create states that are ref

Reland "[pseudo] Track heads as GSS nodes, rather than as "pending actions"."

This reverts commit 2c80b5319870b57fbdbb6c9cef9c86c26c65371d.

Fixes LRTable::buildForTest to create states that are referenced but
have no actions.

show more ...

Revert "[pseudo] Track heads as GSS nodes, rather than as "pending actions"."

This reverts commit e3ec054dfdf48f19cb6726cb3f4965b9ab320ed9.

Tests fail in asserts mode: https://lab.llvm.org/buildbot

Revert "[pseudo] Track heads as GSS nodes, rather than as "pending actions"."

This reverts commit e3ec054dfdf48f19cb6726cb3f4965b9ab320ed9.

Tests fail in asserts mode: https://lab.llvm.org/buildbot/#/builders/109/builds/41217

show more ...

[pseudo] Track heads as GSS nodes, rather than as "pending actions".

IMO this model is simpler to understand (borrowed from the LR0 patch D127357).
It also makes error recovery easier to implement,

[pseudo] Track heads as GSS nodes, rather than as "pending actions".

IMO this model is simpler to understand (borrowed from the LR0 patch D127357).
It also makes error recovery easier to implement, as we have a simple list of
head nodes lying around to recover from when needed.
(It's not quite as nice as LR0 in this respect though).

It's slightly slower (2.24 -> 2.12 MB/S on my machine = 5%) but nothing close
to as bad as LR0.
However
- I think we'd have to eat a litle performance loss otherwise to implement
error recovery.
- this frees up some complexity budget for optimizations like fastpath push/pop
(this + fastpath is already faster than head)
- I haven't changed the data structure here and it's now pretty dumb, we can
make it faster

Differential Revision: https://reviews.llvm.org/D128297

show more ...

[pseudo] Move grammar-related headers to a separate dir, NFC.

We did that for .cpp, but forgot the headers.

Differential Revision: https://reviews.llvm.org/D127388

[pseudo] Simplify the glrReduce implementation.

glrReduce maintains two priority queues (one for bases, and the other
for Sequence), these queues are in parallel with each other, corresponding to a

[pseudo] Simplify the glrReduce implementation.

glrReduce maintains two priority queues (one for bases, and the other
for Sequence), these queues are in parallel with each other, corresponding to a
single family. They can be folded into one.

This patch removes the bases priority queue, which improves the glrParse by
10%.

ASTReader.cpp: 2.03M/s (before) vs 2.26M/s (after)

Differential Revision: https://reviews.llvm.org/D127283

show more ...

[pseudo] Remove the explicit Accept actions.

As pointed out in the previous review section, having a dedicated accept
action doesn't seem to be necessary. This patch implements the the same behavior

[pseudo] Remove the explicit Accept actions.

As pointed out in the previous review section, having a dedicated accept
action doesn't seem to be necessary. This patch implements the the same behavior
without accept acction, which will save some code complexity.

Reviewed By: sammccall

Differential Revision: https://reviews.llvm.org/D125677

show more ...