DOCSEARCHbyAlgolia
Submit Docs

gotreesitter Documentation

repository·main·Indexed 19 days ago

https://github.com/odvcencio/gotreesitter

A pure-Go implementation of the tree-sitter runtime designed to eliminate the need for CGo and C toolchains in Go projects. The documentation includes detailed guides on using the perf_scan performance measurement tool to compare Go performance against the C tree-sitter reference implementation, including configuration via environment variables, measurement protocols, verdict buckets, and authoritative full performance sweeps.

Tokens
63.7K
Snippets
131
Records
230
Agent score
66%

What's inside gotreesitter

  1. What is gotreesitter?

    main

    gotreesitter is a pure-Go implementation of the tree-sitter runtime. Unlike traditional Go bindings that rely on CGo, gotreesitter implements the parser, lexer, query engine, incremental reparsing, arena allocator, external scanners, and tree cursor entirely in Go.

    Key features:

    • No CGo dependency: Eliminates the need for a C toolchain or cross-compilers.
    • Cross-compilation support: Works with any GOOS/GOARCH target supported by Go (e.g., wasip1).
    • Grammar Loading: It uses the same parse-table format as the C runtime. Grammars are extracted from upstream parser.c files via ts2go, compressed into binary blobs, and deserialized on first use. The registry includes 206 grammars.

  2. Overview of grammargen

    main

    grammargen is a pure-Go grammar compiler used by gotreesitter. It transforms grammar definitions into several types of artifacts:

    • A *gotreesitter.Language object.
    • A serialized .bin blob.
    • A tree-sitter-compatible parser.c file.
    • Generated Go DSL source code.

    The tool is input-neutral and supports three primary input formats:

    1. Go DSL: Grammars built using gotreesitter's Go constructors.
    2. grammar.json: Resolved upstream tree-sitter files (the preferred import format).
    3. .grammar files: A compact, ecosystem-agnostic text format.

    Note on JavaScript imports:

    • Use the -js flag for a best-effort pure-Go import (does not execute JS).
    • Use the -js-cli flag to resolve helpers and imports using Tree-sitter 0.26+ (requires Node.js and Tree-sitter on PATH). Warning: -js-cli evaluates the grammar as JavaScript; use it only with trusted code.

  3. Navigate the gotreesitter repository structure

    main

    The gotreesitter project keeps its public runtime in a single root Go package to maintain a simple import surface. Because of this, the repository root contains many production and test files. When navigating the codebase, you should follow subsystem names rather than directory depth to find specific logic.

    Key Directories

    PathPurpose
    grammars/Embedded grammar registry, generated blobs, scanners, and runtime profiles
    grammargen/Grammar import, table construction, minimization, and blob generation
    internal/parsercorephase0/Internal compact-parser implementation
    cgo_harness/C oracle, parity, race, corpus, work-count, and certified timing harnesses
    cmd/Maintainer and user CLIs (e.g., ts2go, tsquery, benchgate, parity_report)
    taproot/, grep/Higher-level consumers and helper packages
    wasm/Browser runtimes and grammargen WebAssembly targets
    scripts/Bounded host-side maintenance helpers
    testdata/Checked-in regression fixtures and ratchet manifests

  4. Understand the Root and Result-Normalization Retirement Plan

    main

    The gotreesitter repository is undergoing a structural transition to reduce the maintenance liability of the root Go package. The goal is to move away from generic 'root-and-result-normalization' (which uses parser_result*.go compatibility files) and instead move parser behavior and invariants upstream into core subsystems like materialization, scheduler, and recovery.

    Key objectives of the retirement plan:

    • Clear Ownership: Public API files and parser-engine subsystems must have clear ownership as defined in the repository map.
    • Upstream Invariants: Generic returned-tree repair and post-finalization fixpoint logic are being replaced. The materialization subsystem is taking ownership of node, field, alias, trivia, and span invariants before publication.
    • Language-Neutral Implementation: New parser behaviors should be implemented in core subsystems (scheduler, recovery, derivation election, etc.) rather than as new language-specific patches or allowlists.
    • Artifact Management: Generated binaries, corpora, profiles, and run receipts must follow the repository's artifact policy to prevent root clutter.

  5. Understand the Wave 3 Perf Sweep Status report

    main

    The Wave 3 Perf Sweep Status report tracks the performance ratio budgets for various programming languages when using gotreesitter compared to C. It serves as a 'ratchet' and evidence ledger to monitor how close Go-based parsing performance is to C-based parsing.

    Key Metrics & Measurement Basis:

    • reps: 5
    • warmup: 1
    • file_budget_ms: 10000
    • max_files: 8
    • order: largest
    • axes: full,noedit
    • Hard full-parse ceiling: Every measured file must be <=10.0x the C performance. Files at <=0.10x are reported as '10x-or-better wins'.

    Budget Statuses:

    • green: Language meets performance budget.
    • green_with_caveat: Language meets budget but has known issues or specific file exclusions.
    • wave2b_pending: Language is still undergoing throughput or memory validation.

    Important Files Referenced:

    • Budget configuration: perf_scan/perf_ratio_budgets.json
    • Fleet catalog: tier_scan/exts.tsv

  6. Understand the C-faithful result-compatibility tier

    main

    The parser_result_<language>*.go tier in the root package is a post-parse compatibility layer. It exists because different GLR parsers (like gotreesitter vs. the original C implementation) might return different trees for the same input due to differences in ambiguity handling, error recovery, aliasing, or trivia attachment.

    This tier reconciles the gotreesitter tree with a C oracle (provided by cgo_harness/) to ensure byte-exact agreement in tree selection, error shapes, and recovered spans. This layer is internal and operates on arena and node internals before the tree is returned to the user.

  7. Understand the performance attribution components

    main

    Performance attribution in gotreesitter is broken down into specific components to identify where wall time is spent. When reading attribution tables, note that component shares are computed to sum to exactly 100% (with other absorbing the remainder).

    Core Components:

    • scheduler-dispatch: Time spent in the scheduler dispatch loop.
    • elections: Time spent in conflict/election logic.
    • reductions-and-pops: Time spent in reduction and stack pop operations.
    • canonicalization: Time spent in canonicalization bookkeeping.
    • lexing: Time spent in the lexer.
    • materialization: Time spent materializing nodes.
    • compat-tail: Measures work related to correctness parity on error/recovery paths (often 0.0% on clean paths).
    • recovery: (Added in later stages) Measures error-cost and recovery engine logic.
    • other: Small residual costs (e.g., (*nodeArena).reset, hiddenTreeHasFieldIDs).

    Coverage %: This is the profiled CPU time divided by measured wall time. In single-core-bound runs (GOMAXPROCS=1), this value often exceeds 100% (e.g., 105-106%) because the Go runtime's background workers (GC assist, sweep) add concurrent on-CPU time within the profiled window.

  8. Understand upstream grammar patches in gotreesitter

    main

    Upstream grammar patches are narrow, pinned overlays applied by the cmd/ts2go tool during the grammar table extraction process. They are used to address confirmed correctness gaps in upstream grammars that must be resolved before the next official upstream release.

    Key characteristics:

    • They are applied specifically before cmd/ts2go extracts a grammar table.
    • They are pinned to specific upstream commits (e.g., via languages.lock).
    • They are intended to be temporary; once an upstream release includes the fix, the patch should be removed.

    Example: tree-sitter-typescript-import-type.patch This specific patch addresses three gaps in TypeScript:

    1. Adds the import_type production.
    2. Adds TypeScript variance annotations.
    3. Separates adjacent generic call signatures at a newline (using a dedicated automatic-semicolon token without affecting the generic automatic-semicolon rule).

  9. Understand corpus policy and file classification

    main

    Each file in the corpus is classified based on whether it is considered a "clean" parse. This classification is used for reporting and determining if a file contributes to timing totals.

    Clean vs. Non-Clean

    • clean: A successful Go parse where the root spans the entire source [0, len(source)), did not stop early, and contains no ERROR nodes.
    • error: Ordinary full-span error trees.
    • stopped: Files that resulted in a timeout, memory issue, node/iteration/stack error, or other early-stop results. These are a subset of the error side.

    Reporting

    • full_parse_split: Reports clean and non-clean/error files separately.
    • error_share: The ratio of non-clean files divided by all classified files.

  10. Understand benchmark methodology and comparison caveats

    main

    The project uses two distinct benchmarking methods that are not directly comparable:

    1. Enclave Method (Current/Authoritative): Uses a single-run ns/op measurement at GOMAXPROCS=1 with a 10-second benchtime floor. This is used for the current sealed epochs.
    2. Bare-metal Method (Historical): Uses the median of ten process-isolated samples.

    Important Caveats:

    • A higher ratio in the enclave method compared to historical bare-metal receipts does not necessarily indicate a Go performance regression; it is a result of different measurement methodologies.
    • The enclave image itself is not reproducible outside of Confidential Space; treat its output as an attested measurement rather than a locally runnable script.
    • Benchmark ratios are sensitive to benchtime. For historical runs like run6, the ratio decreases as benchtime increases (e.g., 6.07x at 750ms vs 5.62x at 10s).

  11. Understand the noise floor protocol

    main

    The noise floor is calculated to provide a baseline for measurement variance.

    Protocol:

    1. The tool uses the BenchmarkParserCoreFreshFullCanonical benchmark.
    2. It invokes the benchmark binary in interleaved pairs (A, B, A, B...) for $n$ pairs (where $n \ge 10$).
    3. Each invocation runs with GOMAXPROCS=1 and times all four fixtures in a single process.
    4. For each fixture and pair $i$, the delta is calculated as: $delta_i = |A_i - B_i|$.
    5. The reported noise floor is the 95th percentile (via linear interpolation over sorted deltas) of $delta_i$.

    Note on Host Class: On shared or busy hosts (like WSL2), absolute ns/op values may be affected by wall-clock contention. However, relative component-share percentages remain reliable because the Go CPU profiler samples on-CPU time (SIGPROF/ITIMER_PROF), which is less sensitive to host contention than wall-clock time.

  12. Understand the real-corpus fallback taxonomy

    main

    When the real-corpus matrix run encounters files that do not follow the direct route, they are categorized into a fallback taxonomy. Understanding these classes helps in debugging parser divergence or errors.

    Fallback Classes

    • Recovery handoff: Occurs when the elected token has no table action at end-of-file. These must preserve production error-tree ownership; do not convert a failed compact acceptance into a clean result.
    • Selected-lineage ownership: Occurs when a converged split drop lacks one selected-lineage proof. This must identify the exact surviving reduction path.
    • Certified repetition conflicts: Occurs when the generic scheduler declines a repetition shift. These require one reusable conflict rule or exact artifact evidence.
    • Acceptance-frontier ownership: Occurs when the end-of-file frontier has more than one active head. Post-accept continuation must preserve an accepted result while live end-of-file reductions finish.