Also use `IoError` more consistently throughout the rest of the project
where its straightforward to do so.
BREAKING CHANGE: Changes public error types for config, generate, and
loader crates.
In a future feature, `RulePool` nodes can be shared between lexical and
syntax roots. No grammars generated by grammar.js/grammra.json are affected
by this issue, as they lead to a tree pool rather than a DAG.
With a DAG `RulePool` representation, however, rewriting tokens during
extraction can destroy a token body before lexical expansion consumes
it and can renumber shared syntax nodes more than once.
Record terminal rewrites while inspecting the original pool, expand tokens
and separators first, then commit the rewrites and renumber each reachable
syntax node once. Resolve grammar metadata against the pending rewrites
before mutating the pool.
`try_seq` reserves a `Seq`'s child range up front and fills slots as
recursion produces each member. The `Repeat` arm builds
`Choice(repeat(x), blank)` directly, skipping the `choice` helper.
Slightly faster and less memory used.
Require `word`, `conflicts`, `inline`, and `supertypes` callbacks
to return named grammar symbols instead of silently accepting values
that produce undefined names.
Restrict `precedences` lists to named rules and precedence names, and
preserve the existing handling of undefined and duplicate `inline`
rules.
Some node-types bookkeeping still used the type name without its named
status. This caused anonymous nodes to inherit extra metadata from named
nodes with the same text, and could create false supertype cycles when a
named supertype and anonymous alias shared a name.
Key extra metadata and supertype dependencies by the complete
(type, named) identity.
Reject named aliases that collide with a canonical supertype. Such an
identity cannot be represented as both a concrete node and an abstract
supertype in node-types.json, and previously caused generation to panic.
All output entries now come from the map keyed by (type, named), so no
two entries can reach the final sort with the same identity. Remove the
unreachable root and extra tie-breakers and the now-redundant deduplication.
BREAKING CHANGE: Alters a public error enum for the generate crate.
When an anonymous token alias and an anonymous syntax-node alias have
the same name, node-types.json emits two entries with the same type and
named status. For example,
```
alias($._node, "same")
```
and
```
alias("!", "same")
```
produce separate anonymous "same" entries. Add anonymous tokens to
the node-type map instead. When a token shares an identity with a
structured node, retain its possible children and fields but mark
them as optional because the token appearance is a leaf.
A node-types entry is identified by both its type name and its `named`
value. The generator only keyed accumulated entries by name, so aliases
like
alias($._node, $.same)
alias($._node, "same")
were incorrectly merged into one entry. Whichever alias was processed
first determined the entry's `named` value, and the structures of two
distinct node types could be combined.
Key accumulated entries by `NodeTypeRef` so named and anonymous nodes
with the same type name remain separate.
Aliasing a supertype makes the aliased occurrence appear as a regular
node in the syntax tree. For example,
```
alias($.expression, $.expression_target)
```
can produce:
```
(expression_target (identifier))
```
Previously, node-types generation skipped the source supertype entirely.
It could reference `expression_target` as a field or child type without
emitting a corresponding top-level entry for it.
Continue emitting the canonical `expression` entry with its `subtypes`,
but pass aliased appearances through regular node generation so their
children and fields are recorded and merged normally.
This commit adds an `eof()` function for grammars, which is easier to
use than the NUL byte directly. It compiles down to a constraint that
the enclosing production can only reduce at end of input, not to a
shiftable token.
BREAKING CHANGE: Public error types for `tree-sitter-generate` were modified.
Co-authored-by: Will Lillis <will.lillis24@gmail.com>
* build(deps): upgrade wasmtime C API to 48.0.0
Upgrade the Rust and Zig Wasmtime dependencies and enable reference values with the null GC collector.
Wasmtime 48 requires a newer Rust toolchain, whose Clippy version identifies three item helpers that can be const. Mark them const so the workspace continues to pass Clippy with warnings denied.
* feat(benchmark): support Wasm grammars
* perf(wasm): cache language function handles
* fix(wasm): improve validation and failure cleanup
Bounds-check dylink metadata parsing, require exact import and export names, and restore memory and function-table allocation offsets when language loading fails.
* fix(wasm): copy the complete supertype map
The JSON output types now hold ids from the string pool instead of
cloning into owned `String`s, which makes `NodeTypeJSON` `Copy` and
drops most allocations when building the output.
Co-authored-by: Will Lillis <will.lillis24@gmail.com>
Currently, a symbol listed in both `supertypes` and `inline` produces
a phantom supertype entry in `node-types.json` for a rule that can
never appear in a tree. `intern_symbols` now drops the supertype with
a warning. A hard error would break 29 published grammars, including
python, go, ruby, rust, and scala, so that that decision is deferred
to the next breaking release. Fixes#5218
`(?-u:...)` switches `regex_syntax` to matching raw bytes, but the lexer
dispatches on decoded characters, so `expand_regex` converted the byte
class with a u8 cast. This is exact for ASCII bytes, and silently
misleading for anything aboove 0x80.
This is not reachable from grammar.js (node and QuickJS both reject
`(?-u:...)`). This change is to guard against future JS runtime changes,
as well as alternative frontends to the generate crate.
A previous fix moved case folding for `/i` patterns out of `regex_syntax` and
into `expand_regex`, so folding could drop the two non-ASCII code points
Unicode simple folding maps onto ASCII letters: the long s `ſ` (U+017F)
onto `s`, and the Kelvin sign `K` (U+212A) onto `k`. Left in, they leak
into otherwise-ASCII tokens and stop those tokens from being extracted as
keywords.
By that point, though, the HIR has already turned a negated class into a
complement, so folding it applies the fold on the wrong side of the
negation. `(?i)[^a-z]` folds a set that contains `A-Z`, which re-admits
`a-z` and leaves a class matching very nearly everything.
`regex_syntax` folds each leaf of a class expression before applying that
leaf's negation and the set algebra above it. Keep that order and change
only the fold: walk the AST, replace each leaf with its fold, and translate
with `case_insensitive(false)`.
Every (state, terminal) parse-table entry stored its action list inline as a
32-byte `ParseTableEntry`, but across a grammar those lists are ~98-99% _duplicates_.
The number of distinct lists is a few thousand regardless of grammar size, while
total entries scale into the hundreds of thousands.
Store each unique action list once in a shared `ActionListPool` (a flat arena of
actions plus `(offset, len)` ranges) and replace the inline entry with a 4-byte
`ActionListId` (a pool index with the `reusable` flag packed into the high bit).
- intern_table converts the freshly built `ParseTable<ParseTableEntry>` into
`ParseTable<ActionListId>`.
- minimize carries and operates on the 4-byte ids. The three global state
renumberings rewrite Shift targets once at the pool level
(`remap_terminal_references`), while the per-state unit-reduction redirects
copy the changed list into a new slot (COW). `mark_fragile_tokens` becomes a
free bit flip on the id.
- `canonicalize` dedups and compacts the pool once before `render`, dropping the
dead and duplicate slots the remaps and COW leave behind. `render` assigns the
output action-list offsets directly.
Yields ~7% wall time reduction, ~12% peak rss reduction.
`ParseStateId`, `LexStateId`, `ProductionInfoId`, and `ReservedWordSetId`
each held a `usize`, while the runtime stores state/field ids as `u16` (so
`u32` has plenty of headroom). Shrinking them saves space for every parse-table
entry, and a number of other data structures.
Reduces wall time by 2-5%, peak rss by 9-12%.
`get_auxiliary_node_info` scans every entry in the item set to collect the
non-auxiliary parents of a given auxiliary symbol. It was called once per
entry whose next symbol is auxiliary, and the same auxiliary symbol recurs
across many entries in a single state (a state's GOTO on a repeat symbol is
shared by every item advancing over it), so the same full scan was repeated
many times per state. Memoize the result per symbol within a single
`add_actions` call.
Reduces wall time 1-4%, rss flat.
`ParseTableEntry` held a `Vec<ParseAction>` per entry. `ActionList` keeps up
to one action inline and spills to a Vec only for conflict entries.
Reduces walltime by >20%, peak rss by ~30%.
The production info depends only on the production, but was recomputed and
deduplicated via a linear deep-equality scan over production_infos for every
reduce item in every state. Cache `prod_id` -> `ProductionInfoId`.
Wall time reduction 0-3%, peak rss neutral.
`ParseItemSetEntry` stores a `LookaheadSetId` into a `LookaheadSetPool` instead
of an owned `TokenSet`. Ids are canonical, so entry hash/eq/clone are integer
ops and state dedup stops walking set words. Unions and single-token inserts
are memoized by id, so the transitive closure and successor-kernel construction
stop re-materializing the same unions per state. Closure additions carry interned
ids with word-token membership precomputed.
For cpp, 3566 distinct lookahead sets back all 49,992 states. For ruby 2000 sets
for 91,991 states, and rust 646 for 16,796.
Reduces wall time by 10-15%, peak rss by 3-5%.
The state-merge pass's `token_conflicts` scanned every terminal entry of the
other state per non-shared token. Precompute flat, word-aligned bitsets,
`ConflictBits`, so each call is a handful of word ANDs.
Yields a 5-6% wall time reduction on large grammars, and flat to ~1%
loss on small grammers. Peak RSS unchanged.
Every state's kernel set was cloned into `parse_state_info` even though the
identical set already lives as the state-dedup map key at the same index
(state ids are the map's insertion order). `ParseStateInfo` now holds the
preceding-symbol sequences plus the dedup map moved out of the builder,
allowing the report path to read kernels via `get_index`. Drops the
duplicate kernel storage, allowing for a small reduction in wall time
and peak rss (1-3%).
`CoincidentTokenIndex` kept a `Vec<ParseStateId>` per token pair whose
only user was keyword identification asking one question: "do all states
where a given pair coincides also allow the word token?" Track that
directly as a second bitset built in the same pass.
Reduces walltime by ~7% for small grammars (i.e. Go), and 20-25% for
larger grammars (i.e. Rust, cpp). Reduces peak rss by ~20% for smaller
grammars and ~40-50% for larger grammars.
Replace the owned `Rule`-tree grammar with a flat, pooled representation. `Rule`
nodes live in a `RulePool` arena and reference their children and params by
index (`RuleId`). Strings are interned in a `StrPool` and referred to by `StrId`.
Productions are stored as flat `ProductionStep`/`Production` slices indexed per
variable, rather than as nested vectors hanging off each `SyntaxVariable`. This
drops the per-rule heap allocation of the owned-tree form and is the groundwork
for the later table-building optimizations.
`parse_grammar` builds the pool, the prepare passes rewrite nodes in place, and
`prepare_grammar` returns a `PreparedGrammar` bundle that owns the run's `StrPool`
alongside the grammars. `build_tables`, `node_types`, and `render` borrow that
pool and resolve `StrId`s only at the output boundary.
Shows an average ~10% walltime reduction when combined with the previous
commit, with nearly all of the savings in `build_tables`. The `prepare`
stage is also ~70% faster and much more stable, but this contributes
much less to overall generate time. Improving early stages such as
`prepare` will be important for future interactive uses.
Parse-item identity dominates parse-table construction. `ParseItem`'s
`Hash`, `Eq`, and `Ord` walk the entire production on every call,
comparing per-step precedence, aliases, and field names. These are
stored as strings for named precedences and for every alias and field.
Precompute, once per table build, two dense `u32` ids for every
`(production, dot)` slot by ranking the whole slot universe with the
item-content comparator, now extracted as `ItemContent`. Equal-content
slots are adjacent after sorting and the id increments only at content
boundaries, so comparing the `cmp` id reproduces the structural order
exactly (both an ordering and an equality). A second id, `eq_with_syms`,
refines `cmp` by the preceding symbols, which enter equality only for
items with `has_preceding_inherited_fields`.
`ParseItem` now carries its production's key slice, and `Hash`/`Eq`/`Ord`
become integer ops.
On the current string-based production storage this is performance-neutral
in isolation (the up-front ranking pays back the per-comparison savings).
It is the foundation for the following change to a pooled, integer-keyed
production representation, which makes both the ranking and the item
comparisons cheaper integer work.
A SHIFT/REDUCE conflict can bundle several shift interpretations with
different precedences against a single reduce. `handle_conflict` weighed them
with only `shift_is_less` and `shift_is_more`, so a lone lower-precedence
shift set `shift_is_less` and the REDUCE won outright, even when another
interpretation tied the REDUCE in precedence and the REDUCE was declared
right-associative. That tie's associativity should have won by shifting, so a
right-associative rule silently became left-associative as soon as an
unrelated lower-precedence rule was added to the grammar.
Track the equal-precedence case explicitly, and in the reduce-wins branch
shift instead when a tying interpretation exists and the reduce actions are
purely right-associative.
Co-authored-by: Will Lillis <will.lillis24@gmail.com>
Unicode simple case folding maps two non-ASCII code points onto ASCII
letters: the long s `ſ` (U+017F) onto `s`, and the Kelvin sign `K` (U+212A)
onto `k`. So `regex_syntax` pulls them into any case-insensitive pattern,
which is virtually never intended and has two bad effects:
* such tokens can no longer be extracted as keywords, because they are not
a subset of an ASCII `word` token (#5607)
* a broad class like `[^"]` or `\p{L}` carrying `/i` loses `ſ`/`K`, even
though it legitimately contains them (#5755)
Rather than let `regex_syntax` fold, parse patterns unfolded and fold them
ourselves in `case_fold_ascii_safe`: fold via `regex_syntax`, then drop
`ſ`/`K` only when folding introduced them (they were not already in the
base set). A class that already contains them keeps them.
Regexes with the case-insensitive 'i' flag caused unicode simple case folding,
which maps two non-ASCII code points onto ASCII letters:
- `ſ` (U+017F) onto `s`
- the Kelvin sign `K` (U+212A) onto `k`
This pushed such tokens outside an ASCII `word` token, so they failed to
extract as keywords.
Problem: A set of `array_*` macros (`array_push`, `array_extend`, etc) implicitly convert a `void*` into a different pointer type. In environments that compile these headers as C++, this implicit conversion is an error.
Solution: This commit adds an `_array_cast` macro that uses `decltype` to cast the `void*` to the proper type when compiling as C++.
