objects/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//! the symbols a file defines and a normalization-stable fingerprint of each —
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-v1`, `hd-sem-dir-v1`)
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/// Coarse symbol classification carried by the index. Mirrors the
35/// `semantic::symbol_resolver::DefinitionKind` taxonomy so types, traits,
36/// enums, modules and the rest are first-class in the index — not just
37/// functions.
38///
39/// The `snake_case` serde spelling is the durable wire form; the [`tag_byte`]
40/// value is the durable *hashing* form and must never be renumbered (doing so
41/// would silently change every `semantic_hash`/`semantic_digest`).
42///
43/// [`tag_byte`]: SymbolKindTag::tag_byte
44#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize, Deserialize)]
45#[serde(rename_all = "snake_case")]
46pub enum SymbolKindTag {
47    /// Function / method / free function body.
48    Function,
49    /// Struct or record type definition.
50    Type,
51    /// Enum definition.
52    Enum,
53    /// Trait declaration (Rust).
54    Trait,
55    /// Class declaration (Python / JS / TS / Java / C++).
56    Class,
57    /// Interface declaration (TS / Java / Go).
58    Interface,
59    /// Type alias (`type Foo = ...`).
60    TypeAlias,
61    /// Constant or static at module scope.
62    Const,
63    /// Module / namespace.
64    Module,
65    /// Parseable but unclassified definition.
66    Other,
67}
68
69impl SymbolKindTag {
70    /// Stable single-byte tag used in the canonical digest byte streams.
71    /// NEVER renumber — the values are baked into every stored digest.
72    pub fn tag_byte(self) -> u8 {
73        match self {
74            SymbolKindTag::Function => 1,
75            SymbolKindTag::Type => 2,
76            SymbolKindTag::Enum => 3,
77            SymbolKindTag::Trait => 4,
78            SymbolKindTag::Class => 5,
79            SymbolKindTag::Interface => 6,
80            SymbolKindTag::TypeAlias => 7,
81            SymbolKindTag::Const => 8,
82            SymbolKindTag::Module => 9,
83            SymbolKindTag::Other => 10,
84        }
85    }
86}
87
88/// The kind of a [`SemanticTreeEntry`]'s target.
89#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
90#[serde(rename_all = "snake_case")]
91pub enum SemanticEntryKind {
92    /// A subdirectory — `node` is a [`SemanticTreeNode`].
93    Dir,
94    /// A parsed source file — `node` is a [`SemanticFileNode`].
95    File,
96    /// Unsupported language, parse failure, or over-budget file. Carries no
97    /// semantic node: `node` and `semantic_digest` both equal the raw source
98    /// blob hash, so a content change to an opaque file still perturbs the
99    /// digest chain.
100    Opaque,
101}
102
103impl SemanticEntryKind {
104    /// Stable single-byte tag used in the canonical dir-digest byte stream.
105    pub fn tag_byte(self) -> u8 {
106        match self {
107            SemanticEntryKind::Dir => 1,
108            SemanticEntryKind::File => 2,
109            SemanticEntryKind::Opaque => 3,
110        }
111    }
112}
113
114/// One symbol defined in a source file.
115#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
116pub struct SymbolEntry {
117    /// Bare symbol name as it appears in the AST.
118    pub name: String,
119    /// Coarse classification.
120    pub kind: SymbolKindTag,
121    /// Enclosing scope path (impl block, class, module, ...), outermost first.
122    pub container_path: Vec<String>,
123    /// Normalization-stable fingerprint of the symbol's definition — a pure
124    /// function of `(bytes, grammar, extractor_version)` that is invariant
125    /// under reformatting and comment edits. See [`compute_symbol_semantic_hash`].
126    pub semantic_hash: ContentHash,
127    /// `(start_line, end_line)`, 1-indexed inclusive. PROVENANCE ONLY — the
128    /// span is deliberately excluded from every digest so a reformat that moves
129    /// the symbol leaves the fingerprint stable.
130    pub span: (u32, u32),
131}
132
133impl SymbolEntry {
134    /// Canonical address spelling: `container::path::name`, or just `name`
135    /// when the symbol is at file scope.
136    pub fn address(&self) -> String {
137        if self.container_path.is_empty() {
138            self.name.clone()
139        } else {
140            format!("{}::{}", self.container_path.join("::"), self.name)
141        }
142    }
143
144    /// Sort key: `(container_path, name, kind, span.0)`.
145    fn sort_key(&self) -> (&[String], &str, u8, u32) {
146        (
147            &self.container_path,
148            self.name.as_str(),
149            self.kind.tag_byte(),
150            self.span.0,
151        )
152    }
153}
154
155/// Compute a symbol's normalization-stable `semantic_hash`.
156///
157/// Canonical layout `hd-sem-sym-v1`:
158/// `kind_tag ‖ 0x00 ‖ token_stream`.
159///
160/// `token_stream` is produced by a DFS in document order over the symbol's
161/// definition node, skipping comment-kind subtrees, emitting for each remaining
162/// leaf `u32-LE(byte_len) ‖ exact source bytes`. Length-prefixed rather than
163/// space-joined so token boundaries are unambiguous. Callers assemble the
164/// stream (they hold the tree); this owns the framing.
165pub fn compute_symbol_semantic_hash(kind: SymbolKindTag, token_stream: &[u8]) -> ContentHash {
166    let mut buf = Vec::with_capacity(2 + token_stream.len());
167    buf.push(kind.tag_byte());
168    buf.push(0x00);
169    buf.extend_from_slice(token_stream);
170    ContentHash::compute_typed("hd-sem-sym-v1", &buf)
171}
172
173/// Hash the file's *scaffold*: the residual non-definition top-level token
174/// stream (every leaf under the file root not covered by an extracted symbol's
175/// span). This is what binds `use`-decl swaps, `impl Trait` headers, attribute
176/// edits, `macro_rules!` bodies and definition-free files (re-export-only libs,
177/// top-level statements) into the file digest — semantic content that lives
178/// *outside* any extracted symbol.
179///
180/// Canonical layout `hd-sem-scaffold-v1`: the length-prefixed leaf token stream
181/// (same framing as a symbol hash's token stream), comments excluded.
182pub fn compute_file_scaffold_hash(token_stream: &[u8]) -> ContentHash {
183    ContentHash::compute_typed("hd-sem-scaffold-v1", token_stream)
184}
185
186/// Compute a file node's `semantic_digest` over its scaffold and (already
187/// sorted) symbols — so the digest covers ALL of a file's semantic content,
188/// not just its extracted definitions.
189///
190/// Canonical layout `hd-sem-file-v2`: `scaffold_hash`, then per symbol
191/// `u32-LE(container element count) ‖ (u32-LE-len ‖ bytes)* ‖ u32-LE(name len) ‖
192/// name ‖ kind_tag ‖ semantic_hash`. Every variable-length field is
193/// length-framed (no record-boundary ambiguity; `["a::b"]` no longer aliases
194/// `["a","b"]`). Spans are EXCLUDED — that is what makes the digest
195/// reformat-stable.
196pub fn compute_file_semantic_digest(
197    scaffold_hash: ContentHash,
198    symbols: &[SymbolEntry],
199) -> ContentHash {
200    let mut buf = Vec::new();
201    buf.extend_from_slice(scaffold_hash.as_bytes());
202    for symbol in symbols {
203        buf.extend_from_slice(&(symbol.container_path.len() as u32).to_le_bytes());
204        for segment in &symbol.container_path {
205            buf.extend_from_slice(&(segment.len() as u32).to_le_bytes());
206            buf.extend_from_slice(segment.as_bytes());
207        }
208        buf.extend_from_slice(&(symbol.name.len() as u32).to_le_bytes());
209        buf.extend_from_slice(symbol.name.as_bytes());
210        buf.push(symbol.kind.tag_byte());
211        buf.extend_from_slice(symbol.semantic_hash.as_bytes());
212    }
213    ContentHash::compute_typed("hd-sem-file-v2", &buf)
214}
215
216/// Compute a directory node's `semantic_digest` over its entries.
217///
218/// Canonical layout `hd-sem-dir-v2`, per entry:
219/// `u32-LE(name len) ‖ name ‖ kind_tag ‖ child semantic_digest`. The name is
220/// length-framed so entry boundaries are unambiguous.
221pub fn compute_dir_semantic_digest(entries: &[SemanticTreeEntry]) -> ContentHash {
222    let mut buf = Vec::new();
223    for entry in entries {
224        buf.extend_from_slice(&(entry.name.len() as u32).to_le_bytes());
225        buf.extend_from_slice(entry.name.as_bytes());
226        buf.push(entry.kind.tag_byte());
227        buf.extend_from_slice(entry.semantic_digest.as_bytes());
228    }
229    ContentHash::compute_typed("hd-sem-dir-v2", &buf)
230}
231
232/// The per-file semantic node: the symbols a source blob defines plus the
233/// reformat-stable digest over them.
234#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
235pub struct SemanticFileNode {
236    pub format_version: u8,
237    pub language: String,
238    pub grammar_version: String,
239    pub extractor_version: u32,
240    /// Content hash of the raw source blob this node was extracted from.
241    pub source_blob: ContentHash,
242    /// Hash of the file's residual non-definition token stream — see
243    /// [`compute_file_scaffold_hash`]. Binds semantic content that lives outside
244    /// any extracted symbol into the file digest.
245    pub scaffold_hash: ContentHash,
246    /// Symbols sorted by `(container_path, name, kind, span.0)`.
247    pub symbols: Vec<SymbolEntry>,
248    /// Reformat-stable digest — see [`compute_file_semantic_digest`].
249    pub semantic_digest: ContentHash,
250}
251
252impl SemanticFileNode {
253    pub const FORMAT_VERSION: u8 = 1;
254
255    /// Build a node, sorting the symbols canonically and computing the digest
256    /// over the scaffold plus the symbols.
257    pub fn new(
258        language: impl Into<String>,
259        grammar_version: impl Into<String>,
260        extractor_version: u32,
261        source_blob: ContentHash,
262        scaffold_hash: ContentHash,
263        mut symbols: Vec<SymbolEntry>,
264    ) -> Self {
265        symbols.sort_by(|a, b| a.sort_key().cmp(&b.sort_key()));
266        let semantic_digest = compute_file_semantic_digest(scaffold_hash, &symbols);
267        Self {
268            format_version: Self::FORMAT_VERSION,
269            language: language.into(),
270            grammar_version: grammar_version.into(),
271            extractor_version,
272            source_blob,
273            scaffold_hash,
274            symbols,
275            semantic_digest,
276        }
277    }
278
279    pub fn encode(&self) -> Result<Vec<u8>, SemanticIndexError> {
280        rmp_serde::to_vec_named(self).map_err(|err| SemanticIndexError::Encoding(err.to_string()))
281    }
282
283    pub fn decode(bytes: &[u8]) -> Result<Self, SemanticIndexError> {
284        let node: Self =
285            rmp_serde::from_slice(bytes).map_err(|err| SemanticIndexError::Encoding(err.to_string()))?;
286        if node.format_version != Self::FORMAT_VERSION {
287            return Err(SemanticIndexError::UnsupportedVersion(node.format_version));
288        }
289        Ok(node)
290    }
291
292    /// Find a symbol by its canonical address (`container::name`).
293    pub fn symbol_by_address(&self, address: &str) -> Option<&SymbolEntry> {
294        self.symbols.iter().find(|s| s.address() == address)
295    }
296}
297
298/// One child edge of a [`SemanticTreeNode`].
299#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
300pub struct SemanticTreeEntry {
301    pub name: String,
302    pub kind: SemanticEntryKind,
303    /// Storage hash of the child node (a [`SemanticFileNode`] or
304    /// [`SemanticTreeNode`] blob), or — for [`SemanticEntryKind::Opaque`] — the
305    /// raw source blob hash.
306    pub node: ContentHash,
307    /// The child's `semantic_digest` (its reformat-stable identity).
308    pub semantic_digest: ContentHash,
309}
310
311/// A semantic directory node mirroring a source [`Tree`](super::Tree).
312#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
313pub struct SemanticTreeNode {
314    pub format_version: u8,
315    /// Entries sorted by `name` (mirrors the source tree's ordering).
316    pub entries: Vec<SemanticTreeEntry>,
317}
318
319impl SemanticTreeNode {
320    pub const FORMAT_VERSION: u8 = 1;
321
322    /// Build a node, sorting entries by name and computing the dir digest,
323    /// which is returned alongside the node.
324    pub fn new(mut entries: Vec<SemanticTreeEntry>) -> (Self, ContentHash) {
325        entries.sort_by(|a, b| a.name.cmp(&b.name));
326        let digest = compute_dir_semantic_digest(&entries);
327        (
328            Self {
329                format_version: Self::FORMAT_VERSION,
330                entries,
331            },
332            digest,
333        )
334    }
335
336    /// The node's reformat-stable digest.
337    pub fn semantic_digest(&self) -> ContentHash {
338        compute_dir_semantic_digest(&self.entries)
339    }
340
341    pub fn encode(&self) -> Result<Vec<u8>, SemanticIndexError> {
342        rmp_serde::to_vec_named(self).map_err(|err| SemanticIndexError::Encoding(err.to_string()))
343    }
344
345    pub fn decode(bytes: &[u8]) -> Result<Self, SemanticIndexError> {
346        let node: Self =
347            rmp_serde::from_slice(bytes).map_err(|err| SemanticIndexError::Encoding(err.to_string()))?;
348        if node.format_version != Self::FORMAT_VERSION {
349            return Err(SemanticIndexError::UnsupportedVersion(node.format_version));
350        }
351        Ok(node)
352    }
353
354    pub fn get(&self, name: &str) -> Option<&SemanticTreeEntry> {
355        self.entries
356            .binary_search_by(|e| e.name.as_str().cmp(name))
357            .ok()
358            .map(|i| &self.entries[i])
359    }
360}
361
362/// Root of a state's semantic index. Attached to a state via
363/// `StateAttachmentBody::SemanticIndex`.
364#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
365pub struct SemanticIndexRoot {
366    pub format_version: u8,
367    pub extractor_version: u32,
368    /// Language → grammar version, for every language present in the tree.
369    pub grammars: BTreeMap<String, String>,
370    /// Storage hash of the top [`SemanticTreeNode`].
371    pub tree: ContentHash,
372    /// The top tree node's `semantic_digest` — the whole-tree fingerprint.
373    pub semantic_digest: ContentHash,
374}
375
376impl SemanticIndexRoot {
377    pub const FORMAT_VERSION: u8 = 1;
378
379    pub fn new(
380        extractor_version: u32,
381        grammars: BTreeMap<String, String>,
382        tree: ContentHash,
383        semantic_digest: ContentHash,
384    ) -> Self {
385        Self {
386            format_version: Self::FORMAT_VERSION,
387            extractor_version,
388            grammars,
389            tree,
390            semantic_digest,
391        }
392    }
393
394    pub fn encode(&self) -> Result<Vec<u8>, SemanticIndexError> {
395        rmp_serde::to_vec_named(self).map_err(|err| SemanticIndexError::Encoding(err.to_string()))
396    }
397
398    pub fn decode(bytes: &[u8]) -> Result<Self, SemanticIndexError> {
399        let root: Self =
400            rmp_serde::from_slice(bytes).map_err(|err| SemanticIndexError::Encoding(err.to_string()))?;
401        if root.format_version != Self::FORMAT_VERSION {
402            return Err(SemanticIndexError::UnsupportedVersion(root.format_version));
403        }
404        Ok(root)
405    }
406}
407
408#[derive(Debug, thiserror::Error)]
409pub enum SemanticIndexError {
410    #[error("unsupported semantic index node version {0}")]
411    UnsupportedVersion(u8),
412    #[error("semantic index node encoding error: {0}")]
413    Encoding(String),
414}
415
416#[cfg(test)]
417mod tests {
418    use super::*;
419
420    fn h(seed: u8) -> ContentHash {
421        ContentHash::from_bytes([seed; 32])
422    }
423
424    fn sym(name: &str, container: &[&str], kind: SymbolKindTag, span: (u32, u32)) -> SymbolEntry {
425        SymbolEntry {
426            name: name.to_string(),
427            kind,
428            container_path: container.iter().map(|s| s.to_string()).collect(),
429            semantic_hash: ContentHash::compute(name.as_bytes()),
430            span,
431        }
432    }
433
434    #[test]
435    fn file_digest_excludes_span() {
436        let a = SemanticFileNode::new(
437            "rust",
438            "0.24",
439            1,
440            h(1),
441            h(0),
442            vec![sym("foo", &[], SymbolKindTag::Function, (10, 20))],
443        );
444        // Same symbol, moved by a reformat (span shifted).
445        let b = SemanticFileNode::new(
446            "rust",
447            "0.24",
448            1,
449            h(1),
450            h(0),
451            vec![sym("foo", &[], SymbolKindTag::Function, (99, 120))],
452        );
453        assert_eq!(
454            a.semantic_digest, b.semantic_digest,
455            "span must not affect the file semantic_digest"
456        );
457    }
458
459    #[test]
460    fn file_digest_changes_on_symbol_hash_change() {
461        let mut s = sym("foo", &[], SymbolKindTag::Function, (1, 2));
462        let d1 = compute_file_semantic_digest(h(0), std::slice::from_ref(&s));
463        s.semantic_hash = ContentHash::compute(b"different-body");
464        let d2 = compute_file_semantic_digest(h(0), std::slice::from_ref(&s));
465        assert_ne!(d1, d2);
466    }
467
468    #[test]
469    fn file_digest_changes_on_scaffold_change() {
470        let syms = [sym("foo", &[], SymbolKindTag::Function, (1, 2))];
471        let d1 = compute_file_semantic_digest(compute_file_scaffold_hash(b"use a;"), &syms);
472        let d2 = compute_file_semantic_digest(compute_file_scaffold_hash(b"use b;"), &syms);
473        assert_ne!(
474            d1, d2,
475            "scaffold (non-definition top-level tokens) must affect the file digest"
476        );
477    }
478
479    #[test]
480    fn file_digest_framing_is_unambiguous() {
481        // `["a::b"]` must NOT collide with `["a","b"]` (per-element framing),
482        // and a name boundary shift must not alias across symbols.
483        let one = sym("f", &["a::b"], SymbolKindTag::Function, (0, 0));
484        let two = sym("f", &["a", "b"], SymbolKindTag::Function, (0, 0));
485        assert_ne!(
486            compute_file_semantic_digest(h(0), &[one]),
487            compute_file_semantic_digest(h(0), &[two]),
488        );
489    }
490
491    #[test]
492    fn symbol_hash_stable_and_kind_sensitive() {
493        let ts = b"some token stream";
494        let a = compute_symbol_semantic_hash(SymbolKindTag::Function, ts);
495        let b = compute_symbol_semantic_hash(SymbolKindTag::Function, ts);
496        assert_eq!(a, b);
497        let c = compute_symbol_semantic_hash(SymbolKindTag::Type, ts);
498        assert_ne!(a, c, "kind participates in the symbol hash");
499    }
500
501    #[test]
502    fn symbols_sorted_canonically() {
503        let node = SemanticFileNode::new(
504            "rust",
505            "0.24",
506            1,
507            h(1),
508            h(0),
509            vec![
510                sym("zed", &[], SymbolKindTag::Function, (1, 1)),
511                sym("abe", &["Impl"], SymbolKindTag::Function, (2, 2)),
512                sym("abe", &[], SymbolKindTag::Function, (3, 3)),
513            ],
514        );
515        let names: Vec<_> = node.symbols.iter().map(|s| s.address()).collect();
516        assert_eq!(names, vec!["abe", "zed", "Impl::abe"]);
517    }
518
519    #[test]
520    fn dir_digest_stable_and_roundtrip() {
521        let e = SemanticTreeEntry {
522            name: "a.rs".to_string(),
523            kind: SemanticEntryKind::File,
524            node: h(5),
525            semantic_digest: h(6),
526        };
527        let (node, digest) = SemanticTreeNode::new(vec![e.clone()]);
528        assert_eq!(node.semantic_digest(), digest);
529        let bytes = node.encode().unwrap();
530        assert_eq!(SemanticTreeNode::decode(&bytes).unwrap(), node);
531    }
532
533    #[test]
534    fn address_spelling() {
535        assert_eq!(sym("foo", &[], SymbolKindTag::Function, (0, 0)).address(), "foo");
536        assert_eq!(
537            sym("open", &["Repository"], SymbolKindTag::Function, (0, 0)).address(),
538            "Repository::open"
539        );
540    }
541}
objects/object/semantic_index.rs

objects/object/
semantic_index.rs
