heddle_object_model/object/
semantic_index.rs

1// SPDX-License-Identifier: Apache-2.0
2//! Content-addressed merkle semantic index (heddle#1067).
3//!
4//! A parallel merkle DAG over the source tree that stores *semantic* facts —
5//! definitions, scopes, imports, and symbol occurrences —
6//! rather than raw bytes. It mirrors the blob/tree/state DAG so semantic data
7//! over all of history costs about as much to maintain as the source history
8//! itself, and queries short-circuit on hash equality without re-parsing.
9//!
10//! ## The two-hash crux
11//!
12//! Every node carries two identities:
13//!
14//! - Its **storage hash** — the content-address of the encoded node blob. This
15//!   changes whenever the node bytes change, including when a symbol's span
16//!   moves under a reformat. It is the object-store key.
17//! - Its **`semantic_digest`** — a fingerprint computed over the *meaning* of
18//!   the node with spans deliberately excluded. Reformatting a file (which
19//!   moves every span) leaves the `semantic_digest` untouched, so a top-down
20//!   digest compare prunes reformatted-but-semantically-identical subtrees
21//!   with zero re-parse.
22//!
23//! The digest byte layouts (`hd-sem-sym-v1`, `hd-sem-file-v3`, `hd-sem-dir-v2`)
24//! are the canonical, cross-language-reproducible definitions. A verifier in
25//! any language that reproduces these byte streams computes byte-identical
26//! digests.
27
28use std::collections::BTreeMap;
29
30use serde::{Deserialize, Serialize};
31
32use super::ContentHash;
33
34/// Durable symbol classification shared by semantic extraction, indexes, and
35/// review payloads so types, traits, enums, modules and the rest remain
36/// first-class without conversion tables.
37///
38/// The `snake_case` serde spelling is the durable wire form; the [`tag_byte`]
39/// value is the durable *hashing* form and must never be renumbered (doing so
40/// would silently change every `semantic_hash`/`semantic_digest`).
41///
42/// [`tag_byte`]: SymbolKindTag::tag_byte
43#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize, Deserialize)]
44#[serde(rename_all = "snake_case")]
45pub enum SymbolKindTag {
46    /// Function / method / free function body.
47    Function,
48    /// Struct or record type definition.
49    Type,
50    /// Enum definition.
51    Enum,
52    /// Trait declaration (Rust).
53    Trait,
54    /// Class declaration (Python / JS / TS / Java / C++).
55    Class,
56    /// Interface declaration (TS / Java / Go).
57    Interface,
58    /// Type alias (`type Foo = ...`).
59    TypeAlias,
60    /// Constant or static at module scope.
61    Const,
62    /// Module / namespace.
63    Module,
64    /// Parseable but unclassified definition.
65    Other,
66}
67
68impl SymbolKindTag {
69    /// Stable single-byte tag used in the canonical digest byte streams.
70    /// NEVER renumber — the values are baked into every stored digest.
71    pub fn tag_byte(self) -> u8 {
72        match self {
73            SymbolKindTag::Function => 1,
74            SymbolKindTag::Type => 2,
75            SymbolKindTag::Enum => 3,
76            SymbolKindTag::Trait => 4,
77            SymbolKindTag::Class => 5,
78            SymbolKindTag::Interface => 6,
79            SymbolKindTag::TypeAlias => 7,
80            SymbolKindTag::Const => 8,
81            SymbolKindTag::Module => 9,
82            SymbolKindTag::Other => 10,
83        }
84    }
85}
86
87/// The kind of a [`SemanticTreeEntry`]'s target.
88#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
89#[serde(rename_all = "snake_case")]
90pub enum SemanticEntryKind {
91    /// A subdirectory — `node` is a [`SemanticTreeNode`].
92    Dir,
93    /// A parsed source file — `node` is a [`SemanticFileNode`].
94    File,
95    /// Unsupported language, parse failure, or over-budget file. Carries no
96    /// semantic node: `node` and `semantic_digest` both equal the raw source
97    /// blob hash, so a content change to an opaque file still perturbs the
98    /// digest chain.
99    Opaque,
100}
101
102impl SemanticEntryKind {
103    /// Stable single-byte tag used in the canonical dir-digest byte stream.
104    pub fn tag_byte(self) -> u8 {
105        match self {
106            SemanticEntryKind::Dir => 1,
107            SemanticEntryKind::File => 2,
108            SemanticEntryKind::Opaque => 3,
109        }
110    }
111}
112
113/// One symbol defined in a source file.
114#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
115pub struct SymbolEntry {
116    /// Bare symbol name as it appears in the AST.
117    pub name: String,
118    /// Coarse classification.
119    pub kind: SymbolKindTag,
120    /// Enclosing scope path (impl block, class, module, ...), outermost first.
121    pub container_path: Vec<String>,
122    /// Normalization-stable fingerprint of the symbol's definition — a pure
123    /// function of `(bytes, grammar, extractor_version)` that is invariant
124    /// under reformatting and comment edits. See [`compute_symbol_semantic_hash`].
125    pub semantic_hash: ContentHash,
126    /// `(start_line, end_line)`, 1-indexed inclusive. PROVENANCE ONLY — the
127    /// span is deliberately excluded from every digest so a reformat that moves
128    /// the symbol leaves the fingerprint stable.
129    pub span: (u32, u32),
130}
131
132impl SymbolEntry {
133    /// Canonical address spelling: `container::path::name`, or just `name`
134    /// when the symbol is at file scope.
135    pub fn address(&self) -> String {
136        if self.container_path.is_empty() {
137            self.name.clone()
138        } else {
139            format!("{}::{}", self.container_path.join("::"), self.name)
140        }
141    }
142
143    /// Span-free sort key: `(container_path, name, kind, semantic_hash)`.
144    fn sort_key(&self) -> (&[String], &str, u8, ContentHash) {
145        (
146            &self.container_path,
147            self.name.as_str(),
148            self.kind.tag_byte(),
149            self.semantic_hash,
150        )
151    }
152}
153
154/// Half-open byte range in the source blob. Spans are provenance metadata:
155/// they are encoded for navigation, but excluded from semantic digests.
156#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize, Deserialize)]
157pub struct ByteSpan {
158    pub start: u32,
159    pub end: u32,
160}
161
162impl ByteSpan {
163    pub fn new(start: u32, end: u32) -> Self {
164        Self { start, end }
165    }
166}
167
168/// Source-local lexical scope classification.
169#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize, Deserialize)]
170#[serde(rename_all = "snake_case")]
171pub enum ScopeKind {
172    Module,
173    Type,
174    Function,
175    Block,
176}
177
178impl ScopeKind {
179    fn tag_byte(self) -> u8 {
180        match self {
181            Self::Module => 1,
182            Self::Type => 2,
183            Self::Function => 3,
184            Self::Block => 4,
185        }
186    }
187}
188
189/// A deterministic source-local scope. `local_id` is assigned in preorder.
190#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
191pub struct ScopeEntry {
192    pub local_id: u32,
193    pub parent: Option<u32>,
194    pub kind: ScopeKind,
195    pub span: ByteSpan,
196}
197
198/// Source-level import form. Resolution to repository paths happens later.
199#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize, Deserialize)]
200#[serde(rename_all = "snake_case")]
201pub enum ImportKindTag {
202    Use,
203    Import,
204    Reexport,
205    Dynamic,
206}
207
208impl ImportKindTag {
209    fn tag_byte(self) -> u8 {
210        match self {
211            Self::Use => 1,
212            Self::Import => 2,
213            Self::Reexport => 3,
214            Self::Dynamic => 4,
215        }
216    }
217}
218
219/// Namespace in which a binding or occurrence participates.
220#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize, Deserialize)]
221#[serde(rename_all = "snake_case")]
222pub enum SymbolNamespace {
223    Value,
224    Type,
225    Both,
226}
227
228impl SymbolNamespace {
229    fn tag_byte(self) -> u8 {
230        match self {
231            Self::Value => 1,
232            Self::Type => 2,
233            Self::Both => 3,
234        }
235    }
236}
237
238/// One name introduced by an import, in canonical source order.
239#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
240pub struct ImportBinding {
241    pub imported: String,
242    pub local: String,
243    pub namespace: SymbolNamespace,
244}
245
246/// One unresolved, source-local import record.
247#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
248pub struct ImportEntry {
249    pub kind: ImportKindTag,
250    pub module_specifier: String,
251    pub bindings: Vec<ImportBinding>,
252    pub scope: u32,
253    pub span: ByteSpan,
254}
255
256/// Role played by a source-level symbol occurrence.
257#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize, Deserialize)]
258#[serde(rename_all = "snake_case")]
259pub enum OccurrenceRole {
260    Definition,
261    Reference,
262    Call,
263    TypeReference,
264}
265
266impl OccurrenceRole {
267    fn tag_byte(self) -> u8 {
268        match self {
269            Self::Definition => 1,
270            Self::Reference => 2,
271            Self::Call => 3,
272            Self::TypeReference => 4,
273        }
274    }
275}
276
277/// One unresolved symbol occurrence, numbered in source order.
278#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
279pub struct OccurrenceEntry {
280    pub local_id: u32,
281    pub role: OccurrenceRole,
282    pub name: String,
283    pub qualifier: Vec<String>,
284    pub namespace: SymbolNamespace,
285    pub scope: u32,
286    pub span: ByteSpan,
287}
288
289/// Canonical source-local facts assembled into a [`SemanticFileNode`].
290#[derive(Clone, Debug, Default, PartialEq, Eq)]
291pub struct SemanticFileFacts {
292    pub symbols: Vec<SymbolEntry>,
293    pub scopes: Vec<ScopeEntry>,
294    pub imports: Vec<ImportEntry>,
295    pub occurrences: Vec<OccurrenceEntry>,
296}
297
298/// Compute a symbol's normalization-stable `semantic_hash`.
299///
300/// Canonical layout `hd-sem-sym-v1`:
301/// `kind_tag ‖ 0x00 ‖ token_stream`.
302///
303/// `token_stream` is produced by a DFS in document order over the symbol's
304/// definition node, skipping comment-kind subtrees, emitting for each remaining
305/// leaf `u32-LE(byte_len) ‖ exact source bytes`. Length-prefixed rather than
306/// space-joined so token boundaries are unambiguous. Callers assemble the
307/// stream (they hold the tree); this owns the framing.
308pub fn compute_symbol_semantic_hash(kind: SymbolKindTag, token_stream: &[u8]) -> ContentHash {
309    let mut buf = Vec::with_capacity(2 + token_stream.len());
310    buf.push(kind.tag_byte());
311    buf.push(0x00);
312    buf.extend_from_slice(token_stream);
313    ContentHash::compute_typed("hd-sem-sym-v1", &buf)
314}
315
316/// Hash the file's *scaffold*: the residual non-definition top-level token
317/// stream (every leaf under the file root not covered by an extracted symbol's
318/// span). This is what binds `use`-decl swaps, `impl Trait` headers, attribute
319/// edits, `macro_rules!` bodies and definition-free files (re-export-only libs,
320/// top-level statements) into the file digest — semantic content that lives
321/// *outside* any extracted symbol.
322///
323/// Canonical layout `hd-sem-scaffold-v1`: the length-prefixed leaf token stream
324/// (same framing as a symbol hash's token stream), comments excluded.
325pub fn compute_file_scaffold_hash(token_stream: &[u8]) -> ContentHash {
326    ContentHash::compute_typed("hd-sem-scaffold-v1", token_stream)
327}
328
329/// Compute a file node's `semantic_digest` over its scaffold and canonical
330/// source-local facts. Spans are deliberately excluded from this identity.
331///
332/// Canonical layout `hd-sem-file-v3`: `scaffold_hash`, then per symbol
333/// `u32-LE(container element count) ‖ (u32-LE-len ‖ bytes)* ‖ u32-LE(name len) ‖
334/// name ‖ kind_tag ‖ semantic_hash`. Every variable-length field is
335/// length-framed (no record-boundary ambiguity; `["a::b"]` no longer aliases
336/// `["a","b"]`). Scope, import, and occurrence records use count-framed
337/// fields and stable one-byte enum tags. All spans are EXCLUDED.
338pub fn compute_file_semantic_digest(
339    scaffold_hash: ContentHash,
340    symbols: &[SymbolEntry],
341    scopes: &[ScopeEntry],
342    imports: &[ImportEntry],
343    occurrences: &[OccurrenceEntry],
344) -> ContentHash {
345    let mut buf = Vec::new();
346    buf.extend_from_slice(scaffold_hash.as_bytes());
347    buf.extend_from_slice(&(symbols.len() as u32).to_le_bytes());
348    for symbol in symbols {
349        buf.extend_from_slice(&(symbol.container_path.len() as u32).to_le_bytes());
350        for segment in &symbol.container_path {
351            buf.extend_from_slice(&(segment.len() as u32).to_le_bytes());
352            buf.extend_from_slice(segment.as_bytes());
353        }
354        buf.extend_from_slice(&(symbol.name.len() as u32).to_le_bytes());
355        buf.extend_from_slice(symbol.name.as_bytes());
356        buf.push(symbol.kind.tag_byte());
357        buf.extend_from_slice(symbol.semantic_hash.as_bytes());
358    }
359    buf.extend_from_slice(&(scopes.len() as u32).to_le_bytes());
360    for scope in scopes {
361        buf.extend_from_slice(&scope.local_id.to_le_bytes());
362        match scope.parent {
363            Some(parent) => {
364                buf.push(1);
365                buf.extend_from_slice(&parent.to_le_bytes());
366            }
367            None => buf.push(0),
368        }
369        buf.push(scope.kind.tag_byte());
370    }
371    buf.extend_from_slice(&(imports.len() as u32).to_le_bytes());
372    for import in imports {
373        buf.push(import.kind.tag_byte());
374        push_str(&mut buf, &import.module_specifier);
375        buf.extend_from_slice(&(import.bindings.len() as u32).to_le_bytes());
376        for binding in &import.bindings {
377            push_str(&mut buf, &binding.imported);
378            push_str(&mut buf, &binding.local);
379            buf.push(binding.namespace.tag_byte());
380        }
381        buf.extend_from_slice(&import.scope.to_le_bytes());
382    }
383    buf.extend_from_slice(&(occurrences.len() as u32).to_le_bytes());
384    for occurrence in occurrences {
385        buf.extend_from_slice(&occurrence.local_id.to_le_bytes());
386        buf.push(occurrence.role.tag_byte());
387        push_str(&mut buf, &occurrence.name);
388        buf.extend_from_slice(&(occurrence.qualifier.len() as u32).to_le_bytes());
389        for segment in &occurrence.qualifier {
390            push_str(&mut buf, segment);
391        }
392        buf.push(occurrence.namespace.tag_byte());
393        buf.extend_from_slice(&occurrence.scope.to_le_bytes());
394    }
395    ContentHash::compute_typed("hd-sem-file-v3", &buf)
396}
397
398fn push_str(buf: &mut Vec<u8>, value: &str) {
399    buf.extend_from_slice(&(value.len() as u32).to_le_bytes());
400    buf.extend_from_slice(value.as_bytes());
401}
402
403/// Compute a directory node's `semantic_digest` over its entries.
404///
405/// Canonical layout `hd-sem-dir-v2`, per entry:
406/// `u32-LE(name len) ‖ name ‖ kind_tag ‖ child semantic_digest`. The name is
407/// length-framed so entry boundaries are unambiguous.
408pub fn compute_dir_semantic_digest(entries: &[SemanticTreeEntry]) -> ContentHash {
409    let mut buf = Vec::new();
410    for entry in entries {
411        buf.extend_from_slice(&(entry.name.len() as u32).to_le_bytes());
412        buf.extend_from_slice(entry.name.as_bytes());
413        buf.push(entry.kind.tag_byte());
414        buf.extend_from_slice(entry.semantic_digest.as_bytes());
415    }
416    ContentHash::compute_typed("hd-sem-dir-v2", &buf)
417}
418
419/// The per-file semantic node: deterministic source-local facts extracted from
420/// one source blob plus their reformat-stable digest.
421#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
422pub struct SemanticFileNode {
423    pub format_version: u8,
424    pub language: String,
425    pub grammar_version: String,
426    pub extractor_version: u32,
427    /// Content hash of the raw source blob this node was extracted from.
428    pub source_blob: ContentHash,
429    /// Hash of the file's residual non-definition token stream — see
430    /// [`compute_file_scaffold_hash`]. Binds semantic content that lives outside
431    /// any extracted symbol into the file digest.
432    pub scaffold_hash: ContentHash,
433    /// Symbols sorted by the span-free semantic key.
434    pub symbols: Vec<SymbolEntry>,
435    /// Scopes sorted by deterministic preorder `local_id`.
436    pub scopes: Vec<ScopeEntry>,
437    /// Imports sorted by their span-free semantic key; bindings retain source order.
438    pub imports: Vec<ImportEntry>,
439    /// Occurrences sorted by deterministic source-order `local_id`.
440    pub occurrences: Vec<OccurrenceEntry>,
441    /// Reformat-stable digest — see [`compute_file_semantic_digest`].
442    pub semantic_digest: ContentHash,
443}
444
445impl SemanticFileNode {
446    pub const FORMAT_VERSION: u8 = 2;
447
448    /// Build a node, sorting the symbols canonically and computing the digest
449    /// over the scaffold plus the symbols.
450    pub fn new(
451        language: impl Into<String>,
452        grammar_version: impl Into<String>,
453        extractor_version: u32,
454        source_blob: ContentHash,
455        scaffold_hash: ContentHash,
456        facts: SemanticFileFacts,
457    ) -> Self {
458        let SemanticFileFacts {
459            mut symbols,
460            mut scopes,
461            mut imports,
462            mut occurrences,
463        } = facts;
464        symbols.sort_by(|a, b| a.sort_key().cmp(&b.sort_key()));
465        scopes.sort_by_key(|scope| scope.local_id);
466        imports.sort_by(|a, b| {
467            (a.kind, &a.module_specifier, a.scope, &a.bindings).cmp(&(
468                b.kind,
469                &b.module_specifier,
470                b.scope,
471                &b.bindings,
472            ))
473        });
474        occurrences.sort_by_key(|occurrence| occurrence.local_id);
475        let semantic_digest =
476            compute_file_semantic_digest(scaffold_hash, &symbols, &scopes, &imports, &occurrences);
477        Self {
478            format_version: Self::FORMAT_VERSION,
479            language: language.into(),
480            grammar_version: grammar_version.into(),
481            extractor_version,
482            source_blob,
483            scaffold_hash,
484            symbols,
485            scopes,
486            imports,
487            occurrences,
488            semantic_digest,
489        }
490    }
491
492    pub fn encode(&self) -> Result<Vec<u8>, SemanticIndexError> {
493        rmp_serde::to_vec_named(self).map_err(|err| SemanticIndexError::Encoding(err.to_string()))
494    }
495
496    pub fn decode(bytes: &[u8]) -> Result<Self, SemanticIndexError> {
497        let node: Self = rmp_serde::from_slice(bytes)
498            .map_err(|err| SemanticIndexError::Encoding(err.to_string()))?;
499        if node.format_version != Self::FORMAT_VERSION {
500            return Err(SemanticIndexError::UnsupportedVersion(node.format_version));
501        }
502        Ok(node)
503    }
504
505    /// Find a symbol by its canonical address (`container::name`).
506    pub fn symbol_by_address(&self, address: &str) -> Option<&SymbolEntry> {
507        self.symbols.iter().find(|s| s.address() == address)
508    }
509}
510
511/// One child edge of a [`SemanticTreeNode`].
512#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
513pub struct SemanticTreeEntry {
514    pub name: String,
515    pub kind: SemanticEntryKind,
516    /// Storage hash of the child node (a [`SemanticFileNode`] or
517    /// [`SemanticTreeNode`] blob), or — for [`SemanticEntryKind::Opaque`] — the
518    /// raw source blob hash.
519    pub node: ContentHash,
520    /// The child's `semantic_digest` (its reformat-stable identity).
521    pub semantic_digest: ContentHash,
522}
523
524/// A semantic directory node mirroring a source [`Tree`](super::Tree).
525#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
526pub struct SemanticTreeNode {
527    pub format_version: u8,
528    /// Entries sorted by `name` (mirrors the source tree's ordering).
529    pub entries: Vec<SemanticTreeEntry>,
530}
531
532impl SemanticTreeNode {
533    pub const FORMAT_VERSION: u8 = 1;
534
535    /// Build a node, sorting entries by name and computing the dir digest,
536    /// which is returned alongside the node.
537    pub fn new(mut entries: Vec<SemanticTreeEntry>) -> (Self, ContentHash) {
538        entries.sort_by(|a, b| a.name.cmp(&b.name));
539        let digest = compute_dir_semantic_digest(&entries);
540        (
541            Self {
542                format_version: Self::FORMAT_VERSION,
543                entries,
544            },
545            digest,
546        )
547    }
548
549    /// The node's reformat-stable digest.
550    pub fn semantic_digest(&self) -> ContentHash {
551        compute_dir_semantic_digest(&self.entries)
552    }
553
554    pub fn encode(&self) -> Result<Vec<u8>, SemanticIndexError> {
555        rmp_serde::to_vec_named(self).map_err(|err| SemanticIndexError::Encoding(err.to_string()))
556    }
557
558    pub fn decode(bytes: &[u8]) -> Result<Self, SemanticIndexError> {
559        let node: Self = rmp_serde::from_slice(bytes)
560            .map_err(|err| SemanticIndexError::Encoding(err.to_string()))?;
561        if node.format_version != Self::FORMAT_VERSION {
562            return Err(SemanticIndexError::UnsupportedVersion(node.format_version));
563        }
564        Ok(node)
565    }
566
567    pub fn get(&self, name: &str) -> Option<&SemanticTreeEntry> {
568        self.entries
569            .binary_search_by(|e| e.name.as_str().cmp(name))
570            .ok()
571            .map(|i| &self.entries[i])
572    }
573}
574
575/// Root of a state's semantic index. Attached to a state via
576/// `StateAttachmentBody::SemanticIndex`.
577#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
578pub struct SemanticIndexRoot {
579    pub format_version: u8,
580    pub extractor_version: u32,
581    /// Language → grammar version, for every language present in the tree.
582    pub grammars: BTreeMap<String, String>,
583    /// Storage hash of the top [`SemanticTreeNode`].
584    pub tree: ContentHash,
585    /// The top tree node's `semantic_digest` — the whole-tree fingerprint.
586    pub semantic_digest: ContentHash,
587    /// State-scoped resolved-edge delta rooted at this state. This is separate
588    /// from `tree`: syntax remains Merkle-shareable while bindings may depend
589    /// on repository placement and the first parent's edge set.
590    #[serde(default)]
591    pub binding_delta: Option<ContentHash>,
592    /// Heddle-owned resolver policy version used to produce `binding_delta`.
593    #[serde(default)]
594    pub resolver_version: u32,
595}
596
597impl SemanticIndexRoot {
598    pub const FORMAT_VERSION: u8 = 1;
599
600    pub fn new(
601        extractor_version: u32,
602        grammars: BTreeMap<String, String>,
603        tree: ContentHash,
604        semantic_digest: ContentHash,
605    ) -> Self {
606        Self {
607            format_version: Self::FORMAT_VERSION,
608            extractor_version,
609            grammars,
610            tree,
611            semantic_digest,
612            binding_delta: None,
613            resolver_version: 0,
614        }
615    }
616
617    /// Attach a resolved-edge delta to this state-scoped root.
618    pub fn with_binding_delta(mut self, binding_delta: ContentHash, resolver_version: u32) -> Self {
619        self.binding_delta = Some(binding_delta);
620        self.resolver_version = resolver_version;
621        self
622    }
623
624    pub fn encode(&self) -> Result<Vec<u8>, SemanticIndexError> {
625        rmp_serde::to_vec_named(self).map_err(|err| SemanticIndexError::Encoding(err.to_string()))
626    }
627
628    pub fn decode(bytes: &[u8]) -> Result<Self, SemanticIndexError> {
629        let root: Self = rmp_serde::from_slice(bytes)
630            .map_err(|err| SemanticIndexError::Encoding(err.to_string()))?;
631        if root.format_version != Self::FORMAT_VERSION {
632            return Err(SemanticIndexError::UnsupportedVersion(root.format_version));
633        }
634        Ok(root)
635    }
636}
637
638#[derive(Debug, thiserror::Error)]
639pub enum SemanticIndexError {
640    #[error("unsupported semantic index node version {0}")]
641    UnsupportedVersion(u8),
642    #[error("semantic index node encoding error: {0}")]
643    Encoding(String),
644}
645
646#[cfg(test)]
647mod tests {
648    use super::*;
649
650    fn h(seed: u8) -> ContentHash {
651        ContentHash::from_bytes([seed; 32])
652    }
653
654    fn sym(name: &str, container: &[&str], kind: SymbolKindTag, span: (u32, u32)) -> SymbolEntry {
655        SymbolEntry {
656            name: name.to_string(),
657            kind,
658            container_path: container.iter().map(|s| s.to_string()).collect(),
659            semantic_hash: ContentHash::compute(name.as_bytes()),
660            span,
661        }
662    }
663
664    #[test]
665    fn file_digest_excludes_span() {
666        let a = SemanticFileNode::new(
667            "rust",
668            "0.24",
669            1,
670            h(1),
671            h(0),
672            SemanticFileFacts {
673                symbols: vec![sym("foo", &[], SymbolKindTag::Function, (10, 20))],
674                ..SemanticFileFacts::default()
675            },
676        );
677        // Same symbol, moved by a reformat (span shifted).
678        let b = SemanticFileNode::new(
679            "rust",
680            "0.24",
681            1,
682            h(1),
683            h(0),
684            SemanticFileFacts {
685                symbols: vec![sym("foo", &[], SymbolKindTag::Function, (99, 120))],
686                ..SemanticFileFacts::default()
687            },
688        );
689        assert_eq!(
690            a.semantic_digest, b.semantic_digest,
691            "span must not affect the file semantic_digest"
692        );
693    }
694
695    #[test]
696    fn semantic_content_hash_excludes_all_provenance_spans() {
697        let source_blob = ContentHash::compute(b"use crate::api::greet; greet();");
698        let scope = |span| ScopeEntry {
699            local_id: 0,
700            parent: None,
701            kind: ScopeKind::Module,
702            span,
703        };
704        let import = |module_specifier: &str, span| ImportEntry {
705            kind: ImportKindTag::Use,
706            module_specifier: module_specifier.to_string(),
707            bindings: vec![ImportBinding {
708                imported: "greet".to_string(),
709                local: "greet".to_string(),
710                namespace: SymbolNamespace::Both,
711            }],
712            scope: 0,
713            span,
714        };
715        let occurrence = |span| OccurrenceEntry {
716            local_id: 0,
717            role: OccurrenceRole::Call,
718            name: "greet".to_string(),
719            qualifier: Vec::new(),
720            namespace: SymbolNamespace::Value,
721            scope: 0,
722            span,
723        };
724        let node = |scope_span, import_spans: [ByteSpan; 2], occurrence_span| {
725            SemanticFileNode::new(
726                "rust",
727                "0.24",
728                4,
729                source_blob,
730                h(0),
731                SemanticFileFacts {
732                    symbols: vec![],
733                    scopes: vec![scope(scope_span)],
734                    imports: vec![
735                        import("crate::api", import_spans[0]),
736                        import("crate::util", import_spans[1]),
737                    ],
738                    occurrences: vec![occurrence(occurrence_span)],
739                },
740            )
741        };
742        let a = node(
743            ByteSpan::new(0, 38),
744            [ByteSpan::new(0, 22), ByteSpan::new(23, 32)],
745            ByteSpan::new(23, 30),
746        );
747        let b = node(
748            ByteSpan::new(10, 48),
749            [ByteSpan::new(33, 42), ByteSpan::new(10, 32)],
750            ByteSpan::new(33, 40),
751        );
752
753        assert_eq!(
754            a.semantic_digest, b.semantic_digest,
755            "span-only differences must not affect semantic content identity"
756        );
757        assert_ne!(
758            a.encode().unwrap(),
759            b.encode().unwrap(),
760            "encoded provenance still records the distinct spans"
761        );
762    }
763
764    #[test]
765    fn file_node_roundtrip_preserves_source_local_facts() {
766        let node = SemanticFileNode::new(
767            "typescript",
768            "0.23",
769            4,
770            h(1),
771            h(0),
772            SemanticFileFacts {
773                symbols: vec![sym("run", &[], SymbolKindTag::Function, (2, 4))],
774                scopes: vec![ScopeEntry {
775                    local_id: 0,
776                    parent: None,
777                    kind: ScopeKind::Module,
778                    span: ByteSpan::new(0, 64),
779                }],
780                imports: vec![ImportEntry {
781                    kind: ImportKindTag::Import,
782                    module_specifier: "./api".to_string(),
783                    bindings: vec![ImportBinding {
784                        imported: "greet".to_string(),
785                        local: "hello".to_string(),
786                        namespace: SymbolNamespace::Value,
787                    }],
788                    scope: 0,
789                    span: ByteSpan::new(0, 39),
790                }],
791                occurrences: vec![OccurrenceEntry {
792                    local_id: 0,
793                    role: OccurrenceRole::Call,
794                    name: "hello".to_string(),
795                    qualifier: Vec::new(),
796                    namespace: SymbolNamespace::Value,
797                    scope: 0,
798                    span: ByteSpan::new(50, 55),
799                }],
800            },
801        );
802
803        assert_eq!(
804            SemanticFileNode::decode(&node.encode().unwrap()).unwrap(),
805            node
806        );
807    }
808
809    #[test]
810    fn file_digest_changes_on_symbol_hash_change() {
811        let mut s = sym("foo", &[], SymbolKindTag::Function, (1, 2));
812        let d1 = compute_file_semantic_digest(h(0), std::slice::from_ref(&s), &[], &[], &[]);
813        s.semantic_hash = ContentHash::compute(b"different-body");
814        let d2 = compute_file_semantic_digest(h(0), std::slice::from_ref(&s), &[], &[], &[]);
815        assert_ne!(d1, d2);
816    }
817
818    #[test]
819    fn file_digest_changes_on_scaffold_change() {
820        let syms = [sym("foo", &[], SymbolKindTag::Function, (1, 2))];
821        let d1 = compute_file_semantic_digest(
822            compute_file_scaffold_hash(b"use a;"),
823            &syms,
824            &[],
825            &[],
826            &[],
827        );
828        let d2 = compute_file_semantic_digest(
829            compute_file_scaffold_hash(b"use b;"),
830            &syms,
831            &[],
832            &[],
833            &[],
834        );
835        assert_ne!(
836            d1, d2,
837            "scaffold (non-definition top-level tokens) must affect the file digest"
838        );
839    }
840
841    #[test]
842    fn file_digest_framing_is_unambiguous() {
843        // `["a::b"]` must NOT collide with `["a","b"]` (per-element framing),
844        // and a name boundary shift must not alias across symbols.
845        let one = sym("f", &["a::b"], SymbolKindTag::Function, (0, 0));
846        let two = sym("f", &["a", "b"], SymbolKindTag::Function, (0, 0));
847        assert_ne!(
848            compute_file_semantic_digest(h(0), &[one], &[], &[], &[]),
849            compute_file_semantic_digest(h(0), &[two], &[], &[], &[]),
850        );
851    }
852
853    #[test]
854    fn symbol_hash_stable_and_kind_sensitive() {
855        let ts = b"some token stream";
856        let a = compute_symbol_semantic_hash(SymbolKindTag::Function, ts);
857        let b = compute_symbol_semantic_hash(SymbolKindTag::Function, ts);
858        assert_eq!(a, b);
859        let c = compute_symbol_semantic_hash(SymbolKindTag::Type, ts);
860        assert_ne!(a, c, "kind participates in the symbol hash");
861    }
862
863    #[test]
864    fn symbols_sorted_canonically() {
865        let node = SemanticFileNode::new(
866            "rust",
867            "0.24",
868            1,
869            h(1),
870            h(0),
871            SemanticFileFacts {
872                symbols: vec![
873                    sym("zed", &[], SymbolKindTag::Function, (1, 1)),
874                    sym("abe", &["Impl"], SymbolKindTag::Function, (2, 2)),
875                    sym("abe", &[], SymbolKindTag::Function, (3, 3)),
876                ],
877                ..SemanticFileFacts::default()
878            },
879        );
880        let names: Vec<_> = node.symbols.iter().map(|s| s.address()).collect();
881        assert_eq!(names, vec!["abe", "zed", "Impl::abe"]);
882    }
883
884    #[test]
885    fn dir_digest_stable_and_roundtrip() {
886        let e = SemanticTreeEntry {
887            name: "a.rs".to_string(),
888            kind: SemanticEntryKind::File,
889            node: h(5),
890            semantic_digest: h(6),
891        };
892        let (node, digest) = SemanticTreeNode::new(vec![e.clone()]);
893        assert_eq!(node.semantic_digest(), digest);
894        let bytes = node.encode().unwrap();
895        assert_eq!(SemanticTreeNode::decode(&bytes).unwrap(), node);
896    }
897
898    #[test]
899    fn address_spelling() {
900        assert_eq!(
901            sym("foo", &[], SymbolKindTag::Function, (0, 0)).address(),
902            "foo"
903        );
904        assert_eq!(
905            sym("open", &["Repository"], SymbolKindTag::Function, (0, 0)).address(),
906            "Repository::open"
907        );
908    }
909}
heddle_object_model/object/semantic_index.rs

heddle_object_model/object/
semantic_index.rs
