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.
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>
`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>
- 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
The `LookaheadIterator` visits symbols in group order for small parse
states, which can produce `reduce_actions` in a different order than the
original linear symbol scan (pre c1379718). Since reductions are applied
sequentially and the last reduction version survives, different orderings
lead to different error recovery outcomes (e.g. losing nodes from ERROR
trees).
Sort the reduce_actions array by symbol (descending) after collection.
The array is typically 1-5 entries, so the insertion sort cost is
negligible and the full optimization speedup is preserved.
In `ts_parser__do_all_potential_reductions`, when `lookahead_symbol` is
0 (error recovery), the code scanned every symbol from 1 to
`token_count` calling ts_language_table_entry for each with most returning
empty. Replace with `LookaheadIterator` which efficiently visits only symbols
with valid actions, yielding 7-20x fewer lookups for typical grammars.
Error recovery throughput improves ~29% (JS) / ~39% (C). Valid-code
parsing is unaffected.
Since v0.26.1, `tree-sitter build --wasm` uses wasi-sdk instead of
Emscripten. The CLI automatically downloads wasi-sdk on first use,
so Emscripten, Docker, and Podman are no longer required.
Update the web binding README to reflect this change.
See #4393 for the original switch to wasi-sdk.
Explicitly casting NULL to (Subtree *) in the ternary expression ensures
type consistency. This resolves ambiguous type inference issues encountered
by strict static analysis tools and C-to-Go transpilers (like ccgo).
Signed-off-by: lucasew <lucas59356@gmail.com>
Wasmtime v34 introduced breaking ABI changes to `wasmtime_func_t` and
`wasmtime_table_t` structures. The `__private` field changed from
`size_t` to `void*`, requiring code updates to store complete
`wasmtime_func_t` structures instead of raw indices.
Changes:
- `BuiltinFunctionIndices`: `uint32_t` -> `wasmtime_func_t`
- `stdlib_fn_indices`: `uint32_t*` -> `wasmtime_func_t*`
- `FunctionDefinition.storage_location`: `uint32_t*` -> `void*`
- `get_builtin_extern()`: simplified to return stored func directly
- Lexer functions: use temp array for func storage, store table index
- Zero-initialize `builtin_fn_indices` so `store_id == 0` sentinel
reliably detects missing stdlib exports
- Free `lexer_funcs` on error paths in `ts_wasm_store_new`
- Remove stale `(uint32_t *)` casts from `lexer_definitions`
Co-Authored-By: Amaan Qureshi <git@amaanq.com>
Co-Authored-By: nzinfo <li.monan@gmail.com>
When a branch inside an alternation has a + or * quantifier, the
quantifier's pass_through step loops back to the branch's first step.
The alternation linking also sets that step's alternative_index to
point to the next branch. This causes the quantifier loop-back to
incorrectly explore other branches in the case of a failed match that
follows a successful match, contaminating captures.
This is corrected by redirecting the quantifier loop-back to a
"clean" copy of the target step without the alternative index pointing
to the next alternation branch.
Co-authored-by: Riley Bruins <ribru17@hotmail.com>
