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>
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`.
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>
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%
- 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.
This commit just refactors the init command's update code, as it's quite messy. The main changes are that most bindings now go through their own generate_{lang} function.
The template used `FileManager.default.fileExists(atPath: "src/scanner.c")` with a relative path, which resolves against the process cwd. When SwiftPM evaluates a dependency's manifest, the cwd is the consumer's directory, so the check returns `false` even when `scanner.c` exists, causing undefined symbol linker errors.
This commit uses `Context.packageDirectory`, which is available since `swift-tools-version:5.6`, to resolve the path against the package root. This does bump the minimum tools version from 5.3 to 5.6.
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>
This displays the working directory of the command (if present),
compiler used, all of its arguments, any environment variables set,
and anything written to stdout/stderr by the compilation tool.
the region in place.
Previous changes to `malloc` caused `realloc` to sometimes pull regions
off of the free list during this optimization. Because no `memcpy` is
performed, this resulted in corrupted data returning to the caller.
Co-authored-by: trim21 <i@trim21.me>
- free memory if 0 size is passed in
- Don't `memcpy` contents if new pointer is `NULL`
- Copy old region's contents only up to size of new region
- free old region
Co-authored-by: trim21 <i@trim21.me>
- One has to think about lifetimes if a type has one:
- `<&'a Node<'tree>>::language` now returns `LanguageRef<'tree>` instead of
`LanguageRef<'a>`, as it should;
- Remove explicit "outlives" requirements from `QueryMatches`, `QueryCaptures`,
and their impl blocks, because they're inferred
- Removed unnecessary `&mut` from `cst_render_node`'s `cursor` parameter
Problem:
After commit f02d7e7e33
the `tree-sitter test` command no longer printed the final test summary,
leaving empty line. The `Stats` struct was embedded into `TestSummary`,
and the explicit call to print it was removed.
Solution:
Print `parse_stats` from `TestSummary.fmt()` implementation.
