The bytes-optimal pick is not the parse-time-optimal pick. CSR uses
O(log n) binary search; Small uses an O(group_count + nnz) linear
scan over grouped sections. The unbiased picker put ~50% of states
into Small, causing parse-time regressions of up to +24% on grammars
like kotlin and javascript.
Add a SMALL_VS_CSR_BIAS constant (0.6) that requires Small to be at
least 40% smaller than CSR before the picker prefers it, applied both
to the per-state argmin and the canonical-group dedup-promotion pass.
This keeps each grammar's parse-time delta within roughly the ±10%
band that csr-clean already occupies vs master, while still
delivering ~7pp of the ~11pp size win available from the unbiased
picker (~38% .so reduction vs master across the corpus).
Replace the per-grammar CSR-vs-hybrid choice with a per-state picker
that places each state in the smallest of dense / CSR / small. State
ids are partitioned into contiguous tiers [Dense | CSR | Small] driven
by `large_state_count` and a new `csr_state_count` field on
TSLanguage. The runtime dispatches on two range checks; the rest of
the lookup logic per tier is unchanged.
States 0 (error) and 1 (start state) are pinned to the Dense tier so
they remain at indices 0 and 1, matching the runtime's hard-coded
expectations. Cost is bounded at ~2 * SYMBOL_COUNT * 2 bytes per
grammar.
Cleanup: drop --table-fmt CLI, OptLevel::ForceHybridTable /
ForceCompressedTable, RenderError::ConflictingParseTableFlags,
heuristic_should_compress, and use_compressed_tables since the free
picker provably picks the smallest representation per state.
Tests pass against the regenerated fixtures. The size savings are
measured in a follow-up corpus run.
Add `assign_initial_state_repr` + `reorder_states_by_repr` so the
picker output drives a contiguous [Dense | CSR | Small] tier layout
with all Shift/Goto state references remapped through the new ids,
plus parallel state-indexed arrays permuted to match.
Step 2 wires this with the existing 2-way decision as input, so the
permutation is the identity and parser.c output is byte-identical
across the 320-grammar corpus. Step 3 will switch the input to the
free 3-way picker and add three-way emission.
Add dense/CSR/small picker keyed on overhead-aware per-state cost
plus a dedup-promotion pass for canonical small-table groups. Emits
PER_STATE_* defines for corpus-runner CSV. No emission change yet:
the picker only reports stats while the existing 2-way path drives
parser.c output.
When generating the hybrid format's small parse table, some grammars
emit many states with identical grouped (symbol, action) data.Detect
duplicates and reuse a single table offset for them.
Co-authored-by: Tuomas Hietanen <thorium@iki.fi>
Apply Compressed Sparse Row (CSR) compression to the parse table for
grammars that benefit, replacing the original dense + small split with
three flat arrays:
uint32_t parse_table_row_offsets[STATE_COUNT + 1]
uint16_t parse_table_columns[TOTAL_NNZ]
uint16_t parse_table_values[TOTAL_NNZ]
Heuristic for enabling CSR (per grammar, all three must hold):
1. LARGE_STATE_COUNT * SYMBOL_COUNT > STATE_COUNT * 40
Ensures the dense table is large enough relative to total state
count that savings outweigh the small-state grouping penalty.
2. dense table density < 45%
Ensures CSR actually saves space. Above ~50% density, CSR's
per-entry column indices cost more than the zeros they eliminate.
45% adds margin below the theoretical crossover.
3. LARGE_STATE_COUNT * SYMBOL_COUNT > 50,000
Avoids applying a format change to tiny grammars where fixed
overhead dominates.
Co-authored-by: Tuomas Hietanen <thorium@iki.fi>
Several test functions compile the same grammar fixture.
Tests sharing a grammar name also share a src_dir. Each test also
unconditionally writes the three tree-sitter headers into
src_dir/tree_sitter/, leading to a race.
Write the three headers exactly once per src_dir, controlled via a
global `HashSet`.
The previous implementation of `InputGrammar::normalize` (inlined in
`parse_grammar` iterated over every variable, checking whether it was
reachable _backwards_ from teh root by recursing over rules that
referenced it.
This means that each and every top level call re-traversed the entire
graph. The runtime performance of this backwards walk was dependent on
the _order_ of rules as declared in `grammar.js`. All existing grammars
have an ordering that's reasonably friendly to this iteration pattern
(BFS-ish order, top down from the start rule), but this leaves us open
to a catastrophic performance cliff.
Instead, seed a `used` set with the start rule, the word token, and an
names referenced from `extras`/`externals`. Then propagate via direct rule
references. This yields anywhere from a 2-~2200x speedup for
`parse_grammar`. This greatly speeds up `--no-parser` runs, but is
relatively unimportant for `parser.c` generation for _existing_
grammars. The important piece is eliminating the potential cliff.
debug output.
The initial implementation of `--debug pretty` assumed process version
was bounded by `MAX_VERSION_COUNT`. However, we also have to account for
`MAX_VERSION_COUNT_OVERFLOW` as well as `halted_version_count`.
`ts_decode_utf16_le` and `ts_decode_utf16_be` passed a byte length to
`U16_NEXT_LE` and `U16_NEXT_BE`, but those macros count `uint16_t` code
units. If a lead surrogate was the last code unit in a chunk, the decoder
could peek past the chunk and combine it with adjacent memory.
This commit passes the code-unit length to the UTF-16 macros, and fails
with `TS_DECODE_ERROR` when a chunk is too short to contain even one full
code unit. This lets the lexer retry with a fresh chunk or advance through
the invalid byte as it already does.
Co-authored-by: Will Lillis <will.lillis24@gmail.com>
Co-authored-by: Amaan Qureshi <git@amaanq.com>
- replace `Vec<Vec<ParseStateId>>` with a flat bitset in
`CoincidentTokenIndex` for membership queries
The previous representation stored full lists of parse state IDs for
each token pair. Since only membership (yes/no) is needed for most
queries, a flat bitset (`Vec<u64>` indexed as `a * n + b`) is
better. Both `(a,b)` and `(b,a)` bits are set during construction
so `contains()` needs no min/max normalization. The original
`entries: Vec<Vec<ParseStateId>>` and `states_with()` method are
retained alongside the bitset, because `identify_keywords` needs
to iterate over the specific parse states where two tokens co-occur
rather than scanning all states. ~8% walltime reduction for
tree-sitter-bash.
- add word-aligned per-row bitsets to `CoincidentTokenIndex` for
vectorized intersection checks
Row `a` spans `[a * row_words .. (a+1) * row_words]` where
`row_words = n.div_ceil(64)`. This enables callers in
`build_lex_table` to perform word-level AND operations against
`TokenSet::terminal_bits_words()` instead of iterating individual
token indices. ~6% walltime reduction on tree-sitter-bash.
- add `TokenSet::terminal_bits_words()` accessor and `#[inline]` on
`BitVec::insert_all`
Expose the raw `&[u64]` backing the terminal bitset so callers can
perform word-level bitwise intersection. Mark `insert_all` as
`#[inline]` to allow the compiler to optimize the hot OR loop.
- precompute a flat NFA-state-to-variable-index lookup table
Build a `Vec<usize>` mapping each NFA state ID to its owning
variable index up front in `TokenConflictMap::new`, replacing
repeated binary searches in `compute_conflict_status` with
array lookups. Also simplifies `mark_fragile_tokens` to
collect terminal indices into a `Vec` rather than maintaining
a boolean mask.
- replace `FxHashSet<Vec<u32>>` visited set with `FxHashSet<u64>`
using a hash-of-states key
In `compute_conflict_status`, the visited-state-set previously
stored cloned `Vec<u32>` NFA state sets. Replace this with an
`FxHashSet<u64>` keyed by hashing the sorted state slice via
`FxHasher`. This eliminates the `Vec` clone on every BFS step.
- reduce allocations in `NfaCursor::group_transitions`
Reuse a single `CharacterSet` buffer across iterations via `assign`
and `mem::take` instead of cloning the input on every raw
transition. Also, replace `Vec::insert` with `Vec::push` when
splitting intersection transitions. The final sort makes
mid-loop ordering irrelevant, and the disjointness of the split
sets guarantees correctness.
- pre-allocate `NfaTransition` result vectors with a capacity of 8
and use `swap_remove` instead of `remove` when merging duplicate
transition entries
- lazily compute `within_separator` in `compute_conflict_status`
Most BFS states have no completions, so the separator check
(which iterates all cursor transitions) is never needed in those
iterations. Wrap it in `Option::get_or_insert_with` to defer
computation until first use.
- add `NfaCursor::transitions_and_any_sep` to fuse the transitions
and separator-check passes
Callers like `build_lex_table::add_state` previously called
`transitions()` and then `transition_chars().any(|sep|)` separately,
iterating the raw NFA transitions twice. The fused method computes
both in a single pass.
Replace `std::collections::{HashMap, HashSet}` with
`rustc_hash::{FxHashMap, FxHashSet}` throughout `generate`. `FxHash`
is _much_ faster than the default SipHash for small integer keys,
which are used extensively through `generate`. The one "risk" here is
that `FxHash` is more vulnerable to DDOS attacks, but that isn't as much
of a concern for us here.
- use bitflags for `TokenConflictStatus`
Replace the individual boolean fields on the conflict status type
with a `bitflags!` representation. This takes up significantly less
space and allows for faster combination/testing in `token_conflicts`.
- hoist loop bounds in the merge-join loops of `states_conflict`
Extract `Vec::len()` outside of `while` loops to avoid recomputing
bounds on every iteration. Remove the now-unused `row_offset` /
`does_conflict_at` indirection on `TokenConflictMap`, inlining the
conflict check directly.
- optimize `variable_index_for_nfa_state` in `grammars.rs`
Small optimization to the NFA state-to-variable index mapping.
- refactor symbol key into a proper newtype
Extract the raw `u64` symbol key bit manipulation into a `key_index`
helper function for some extra type safety.
- use a boolean `Vec` instead of `Vec::contains` in `dedup`
Replace linear containment checks (`split_state_ids.contains()`)
with a constant lookup indexed by state ID.
- narrow parse state IDs from `usize` to `u16`
Reduces memory footprint and improves packing in `ParseTable` and
`build_parse_table`. This is more cache-friendly and reduces peak rss by
~1-2%.
- precompute lookup tables for parse table minimization
Build several maps up front (symbol-to-action, nonterminal indices,
symbol keys) rather than recomputing them in the hot minimization
loop. The `SymbolKey` optimization is the largest single win: it
packs each `Symbol`'s type tag and index into a single u64, enabling
single-instruction comparisons in the merge-join that dominates
`states_conflict`. This gives a significant speedup for larger
grammars.
- store ParseTableEntry` refs in the precomputed entry maps to
avoid `IndexMap::get_index` lookups in the inner loop of
`states_conflict`
This eliminates an indirect lookup per comparison in the merge-join.
- use unchecked array accesses in hot loops
Where indices are known valid from construction (e.g. the merge-join
in `states_conflict` and dedup), skip bounds checks in the innermost
loops. The compiler can _usually_ prove this and remove the checks
itself, but not always.
Problem: Many parser projects (about 100 out of ~330 tracked by
nvim-treesitter) still do not contain a `tree-sitter.json` config file,
so `tree-sitter generate` refuses to generate ABI 15 parsers due to the
lack of version information. This prevents these parsers from profiting
from other improvements in ABI 15+ and will eventually make them
unusable when ABI 14 support is dropped.
Solution: Simply use a default version `0.0.0` if no `tree-sitter.json`
is found.
The previous two-phase locking scheme (probe existing lock file, then
create and compile) had TOCTOU races between phases that caused
spurious failures in CI when tests compiled grammars concurrently.
Replace with a single-phase approach using `create_new` as the sole
synchronization primitive. An RAII `LockFile` guard ensures cleanup
on drop (including panics). Only "builders" attempt to acquire the
lock. Loaders simply load the file. Builders compile a temporary path
and then rename, so loaders are guaranteed a valid shared library.
The winning builder compiles and then drops the lock. Losers poll for
lock file removal, then load. Stale locks from killed processes are
detected via a timeout and an appropriate error message is displayed
to the user.
This started as a simple one to one rewrite, just removing the regexes,
and quickly devolved into a rewrite of the test parsing logic. In
addition to the memory enhancements, the general flow should be much
clearer now. A few data points:
- JS: walltime -1.3%, peak rss -10.2%
- C: walltime -5.7%, peak rss -4.5%
- Rust: walltime -3.8%, peak rss -2.2%
This commit skips adding entries to the subtype map when the subtypes
list is empty to avoid a lookup failure in the topological sort during
node type generation.
Co-authored-by: Amaan Qureshi <git@amaanq.com>
- Cache tree byte range length to avoid redundant FFI calls per test
- Combine 5 separate XML attribute write! calls into one
- Pre-allocate format_sexp output buffer to avoid repeated growth
Wrap stdout in a 64KB BufWriter when writing `parse` output. The tree
walking loop makes many small write calls (parentheses, indentation,
node kinds, ranges, etc.) which are expensive without buffering.
When parsing the jquery.js corpus file, cuts the total time roughly in
half. These savings only show when piping the result to a file,
otherwise terminal rendering time usually dominates, hiding all gains.
Also do the same for the `query` command's output.
We have to pay the cost of compiling the regex at runtime, and the
`LazyLock` overhead for each access. The pattern is simple enough that
we can manually parse and extract.
`grammar_json_name` is now ~116x faster on cold start, ~5.6x faster warm
(after the regex has been compiled). Both are fast enough to not matter
much in practice, but some perf gains and eliminating global state is a
win.
The workspace dependency for `tree-sitter-generate` did not set
`default-features = false`, so Cargo always enabled its default
features (including `qjs-rt` and thus `rquickjs`) regardless of
the CLI's `--no-default-features` flag.
Additionally, `tree-sitter-generate` failed to compile without the
`load` feature due to unconditional references to `cfg`-gated items.
- Set `default-features = false` on the workspace `tree-sitter-generate`
dependency so the CLI's feature forwarding actually takes effect.
- Explicitly enable the `load` feature in the CLI's dependency on
`tree-sitter-generate`, since the CLI needs `load`-gated functions
unconditionally.
- Gate necessary imports behind `#[cfg(feature = "load")]` to fix
`tree-sitter-generate`'s build without the `load` feature.
