[P1] Add incremental Tree-sitter reparsing, changed-range invalidation, and source freshness #99

New issue

Open

opened 2026-08-18 14:16:19 +00:00 by lost-rob0t · 0 comments

lost-rob0t commented

2026-08-18 14:16:19 +00:00

(Migrated from github.com)

Parent: #93
Depends on: #94, #95, #96, #97, #98

Goal

Use Tree-sitter's incremental parsing model to update Project source observations efficiently and, more importantly, make freshness/invalidation semantics explicit so stale AST/symbol/reference facts never silently satisfy current queries or SPEC verification.

Required update flow

Model the update path semantically as:

old file generation + old TSTree
        |
        +-- apply edit metadata
        |
        v
incremental reparse new source
        |
        v
changed ranges
        |
        +-- invalidate affected current observations
        +-- retain old generation as historical/provenance if configured
        +-- rerun relevant query/extraction packs
        v
new current parse/extraction generation

Do not make raw Tree-sitter node identity the freshness mechanism.

Edit model

Expose a Prolog representation equivalent to Tree-sitter input edits, including:

start byte;
old end byte;
new end byte;
start point;
old end point;
new end point.

Provide semantics equivalent to:

ts_tree_edit(+Tree, +Edit, -Outcome).
ts_reparse(+Parser, +OldTree, +NewSource, -NewTree).
ts_changed_ranges(+OldTree, +NewTree, -Ranges).

Exact API may differ, but sync operations should remain ordinary local predicates unless implementation evidence shows meaningful latency requiring the existing async contract.

Current / stale observation semantics

Define explicit generation state for:

file content;
parse;
materialized syntax facts;
query/extraction facts.

A public "current" Project/source query must never merge facts from incompatible generations.

Historical observations may remain queryable through explicit generation/provenance APIs.

States must distinguish at least:

current
stale
invalidated
partial/incomplete
failed/error

where useful. Do not silently delete the evidence trail merely because a new parse exists.

Invalidation

Use changed ranges to identify observations that may require recomputation, but do not overclaim semantic locality.

Some changes can affect facts outside the textual changed range, for example imports, scope/binding relationships, grammar/extractor behavior, or language-specific semantics. Language adapters must be able to declare conservative invalidation scope such as:

range-local
containing declaration
whole file
project resolution phase

Correctness wins over incremental cleverness.

Query/extractor versions

A grammar upgrade or query-pack/extractor change must also invalidate/recompute the corresponding current observations even if source bytes did not change.

Currentness therefore depends on more than file mtime:

file content generation/hash
parser runtime/grammar identity
query/extractor identity/version
normalization schema version

Atomic publication

Do not expose a half-reindexed generation as the complete current Project state.

Prefer staging the new parse/extraction generation and publishing it as current only after required indexing phases complete or publishing an explicit partial(...) state that VERIFY cannot mistake for complete evidence.

Document the linearization/publication semantics for concurrent readers and file updates.

Resource lifecycle

Old native trees must be released when no current operation/reference needs them. Historical KB provenance must not require retaining every native TSTree forever.

Persisted historical observations should use normalized Prolog evidence, not native pointer lifetime.

Acceptance criteria

A single-byte edit can reuse the old Tree-sitter tree and produce a new parse generation.
changed_ranges is exposed as structured Prolog data.
Facts from the old parse generation cannot satisfy a query explicitly requesting current source observations.
Unaffected observations may be reused only under a documented safe invalidation policy.
Language adapters can request broader invalidation than the raw changed range.
A grammar/query-pack/extractor version change forces appropriate re-extraction even with unchanged source bytes.
Concurrent readers never observe a mixed generation presented as complete current state.
Partial/reindexing/error state cannot be mistaken for complete verified evidence.
Old native trees are reclaimable without losing normalized provenance/history.
Repeated edits do not cause unbounded retention of native parser/tree/query objects.
Deterministic tests cover insertion, deletion, replacement, Unicode byte/point edits, edit near syntax error, scope-changing edit, grammar/query upgrade, concurrent read/update, failed reindex, and fallback full-file invalidation.

Non-goals

No promise that all semantic extraction is range-local.
No requirement to persist native Tree-sitter trees across process restart in the first slice.
No filesystem watcher/UI requirement here; callers may supply changed source explicitly.
No weakening of evidence freshness for performance.

Refs #93 #94 #95 #96 #97 #98

Parent: #93 Depends on: #94, #95, #96, #97, #98 ## Goal Use Tree-sitter's incremental parsing model to update Project source observations efficiently and, more importantly, make freshness/invalidation semantics explicit so stale AST/symbol/reference facts never silently satisfy current queries or SPEC verification. ## Required update flow Model the update path semantically as: ```text old file generation + old TSTree | +-- apply edit metadata | v incremental reparse new source | v changed ranges | +-- invalidate affected current observations +-- retain old generation as historical/provenance if configured +-- rerun relevant query/extraction packs v new current parse/extraction generation ``` Do not make raw Tree-sitter node identity the freshness mechanism. ## Edit model Expose a Prolog representation equivalent to Tree-sitter input edits, including: - start byte; - old end byte; - new end byte; - start point; - old end point; - new end point. Provide semantics equivalent to: ```prolog ts_tree_edit(+Tree, +Edit, -Outcome). ts_reparse(+Parser, +OldTree, +NewSource, -NewTree). ts_changed_ranges(+OldTree, +NewTree, -Ranges). ``` Exact API may differ, but sync operations should remain ordinary local predicates unless implementation evidence shows meaningful latency requiring the existing async contract. ## Current / stale observation semantics Define explicit generation state for: - file content; - parse; - materialized syntax facts; - query/extraction facts. A public "current" Project/source query must never merge facts from incompatible generations. Historical observations may remain queryable through explicit generation/provenance APIs. States must distinguish at least: ```text current stale invalidated partial/incomplete failed/error ``` where useful. Do not silently delete the evidence trail merely because a new parse exists. ## Invalidation Use changed ranges to identify observations that may require recomputation, but do not overclaim semantic locality. Some changes can affect facts outside the textual changed range, for example imports, scope/binding relationships, grammar/extractor behavior, or language-specific semantics. Language adapters must be able to declare conservative invalidation scope such as: ```text range-local containing declaration whole file project resolution phase ``` Correctness wins over incremental cleverness. ## Query/extractor versions A grammar upgrade or query-pack/extractor change must also invalidate/recompute the corresponding current observations even if source bytes did not change. Currentness therefore depends on more than file mtime: ```text file content generation/hash parser runtime/grammar identity query/extractor identity/version normalization schema version ``` ## Atomic publication Do not expose a half-reindexed generation as the complete current Project state. Prefer staging the new parse/extraction generation and publishing it as current only after required indexing phases complete or publishing an explicit `partial(...)` state that VERIFY cannot mistake for complete evidence. Document the linearization/publication semantics for concurrent readers and file updates. ## Resource lifecycle Old native trees must be released when no current operation/reference needs them. Historical KB provenance must not require retaining every native `TSTree` forever. Persisted historical observations should use normalized Prolog evidence, not native pointer lifetime. ## Acceptance criteria - [ ] A single-byte edit can reuse the old Tree-sitter tree and produce a new parse generation. - [ ] `changed_ranges` is exposed as structured Prolog data. - [ ] Facts from the old parse generation cannot satisfy a query explicitly requesting current source observations. - [ ] Unaffected observations may be reused only under a documented safe invalidation policy. - [ ] Language adapters can request broader invalidation than the raw changed range. - [ ] A grammar/query-pack/extractor version change forces appropriate re-extraction even with unchanged source bytes. - [ ] Concurrent readers never observe a mixed generation presented as complete current state. - [ ] Partial/reindexing/error state cannot be mistaken for complete verified evidence. - [ ] Old native trees are reclaimable without losing normalized provenance/history. - [ ] Repeated edits do not cause unbounded retention of native parser/tree/query objects. - [ ] Deterministic tests cover insertion, deletion, replacement, Unicode byte/point edits, edit near syntax error, scope-changing edit, grammar/query upgrade, concurrent read/update, failed reindex, and fallback full-file invalidation. ## Non-goals - No promise that all semantic extraction is range-local. - No requirement to persist native Tree-sitter trees across process restart in the first slice. - No filesystem watcher/UI requirement here; callers may supply changed source explicitly. - No weakening of evidence freshness for performance. Refs #93 #94 #95 #96 #97 #98