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_query_cursor_next_capture` linearly scanned all finished states to
find the one with the earliest next capture byte offset. With deeply
nested code, this O(n) scan per capture caused the highlight crate to
hang for minutes on large files.
Replace the linear scan with a min-heap over the finished_states array,
keyed by (next_capture_byte_offset, pattern_index, id). The heap is
maintained lazily: ts_query_cursor__advance uses plain array_push
(preserving FIFO insertion order), and next_capture sifts new elements
into the heap on entry via a tracked heap_size boundary. This preserves
the documented "order found" guarantee for next_match while giving
next_capture O(log n) per call.
Commit 1f6eac55 ("query: Use uint32_t for capture list IDs") widened
QueryState.capture_list_id to uint32_t and removed the 65536 pool cap,
but left the pool function signatures as uint16_t. This caused silent
truncation when the pool exceeded 65535 entries, leading to a segfault.
Solaris does not provide <endian.h> or <sys/endian.h>, but it does expose
byte-order definitions and conversion helpers via <sys/isa_defs.h> and
<sys/byteorder.h>.
Add a __sun branch so the portable header defines __BYTE_ORDER and the
htobe*/le*toh conversions on Solaris.
Co-authored-by: Amaan Qureshi <git@amaanq.com>
`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>
