semantic/

semantic_index.rs

// SPDX-License-Identifier: Apache-2.0
//! Semantic-index *extraction*: turning a source blob into the per-file symbol
//! list the merkle semantic index (heddle#1067) stores.
//!
//! The index node types and the canonical digest/hash byte layouts live in the
//! `objects` crate ([`objects::object::semantic_index`]); this module owns the
//! grammar-facing half — walking the AST to produce [`SymbolEntry`] values with
//! their normalization-stable `semantic_hash`. Assembly of the tree and the
//! store wiring live in the `repo` crate.
//!
//! A symbol's `semantic_hash` is a pure function of
//! `(source bytes, grammar, extractor_version)`: a DFS in document order over
//! the definition's node, comment subtrees skipped, each remaining leaf emitted
//! as `u32-LE(byte_len) ‖ exact source bytes`. Whitespace and comments are not
//! leaves, so reformatting and comment edits leave the hash untouched — while a
//! one-token change perturbs exactly the symbols that contain it.

use objects::object::{
    ContentHash, ImportEntry, OccurrenceEntry, ScopeEntry, SymbolEntry, SymbolKindTag,
    compute_file_scaffold_hash, compute_symbol_semantic_hash,
};

use crate::{
    parser::{Language, ParsedFile, walk_non_comment_leaves},
    symbol_resolver::visit_definitions,
};

/// Version of the extraction logic itself. Bump when the taxonomy, source-fact
/// extraction, container resolution, or token-stream framing changes the
/// durable file artifact for unchanged source. It participates in file-node
/// identity so a bump forces a clean recompute via the supersedes chain.
///
/// v2: `hd-sem-file-v2`/`hd-sem-dir-v2` framed layouts, the `scaffold_hash`
/// (non-definition file content), and mod-qualified `container_path`. Bumped so
/// any same-version-but-old-layout nodes written by a pre-fix branch checkout
/// are treated as stale and recomputed rather than digest-compared.
///
/// v3: Zig extraction added. `parent_is_reusable` only validates grammars
/// *present* in the parent's map, so a pre-Zig index (no `"zig"` entry) would
/// otherwise carry `.zig` files forward as `Opaque` indefinitely. The bump
/// forces those to recompute so imported Zig repos gain granularity.
///
/// v4: Persist deterministic source-local scopes, imports, and symbol
/// occurrences alongside definitions in each semantic file node.
///
/// v5: JavaScript and TypeScript object-literal function properties are
/// extracted from `pair` nodes. The added symbols and covered ranges alter
/// both the symbol list and scaffold hash for unchanged source, so v4 nodes
/// must not be reused.
pub const EXTRACTOR_VERSION: u32 = 5;

/// Stable lowercase language name recorded in file nodes and the root's
/// grammar map.
pub fn language_name(language: Language) -> &'static str {
    match language {
        Language::Rust => "rust",
        Language::Python => "python",
        Language::JavaScript => "javascript",
        Language::TypeScript => "typescript",
        Language::Go => "go",
        Language::C => "c",
        Language::Cpp => "cpp",
        Language::Java => "java",
        Language::Zig => "zig",
        Language::Unknown => "unknown",
    }
}

/// Grammar version string for a language — the tree-sitter grammar crate
/// version. Participates in node identity so a grammar bump recomputes cleanly.
pub fn grammar_version(language: Language) -> &'static str {
    match language {
        Language::Rust => "tree-sitter-rust@0.24",
        Language::Python => "tree-sitter-python@0.25",
        Language::JavaScript => "tree-sitter-javascript@0.25",
        Language::TypeScript => "tree-sitter-typescript@0.23",
        Language::Go => "tree-sitter-go@0.25",
        Language::C => "tree-sitter-c@0.24",
        Language::Cpp => "tree-sitter-cpp@0.23",
        Language::Java => "tree-sitter-java@0.23",
        Language::Zig => "tree-sitter-zig@1.1",
        Language::Unknown => "none",
    }
}

/// The current grammar version for a language *name* (as recorded in a
/// [`SemanticIndexRoot`](objects::object::SemanticIndexRoot)'s grammar map).
/// Used by the builder to detect a grammar bump and refuse stale node reuse.
pub fn grammar_version_by_name(name: &str) -> Option<&'static str> {
    let language = match name {
        "rust" => Language::Rust,
        "python" => Language::Python,
        "javascript" => Language::JavaScript,
        "typescript" => Language::TypeScript,
        "go" => Language::Go,
        "c" => Language::C,
        "cpp" => Language::Cpp,
        "java" => Language::Java,
        "zig" => Language::Zig,
        _ => return None,
    };
    Some(grammar_version(language))
}

/// The symbols extracted from one source file, plus the file scaffold hash,
/// ready to be assembled into a
/// [`SemanticFileNode`](objects::object::SemanticFileNode).
pub struct ExtractedFile {
    pub language: Language,
    /// Hash of the residual non-definition top-level token stream — binds
    /// use-decls, impl/attribute/macro tokens and definition-free files into
    /// the file digest. See [`compute_file_scaffold_hash`].
    pub scaffold_hash: ContentHash,
    pub symbols: Vec<SymbolEntry>,
    pub scopes: Vec<ScopeEntry>,
    pub imports: Vec<ImportEntry>,
    pub occurrences: Vec<OccurrenceEntry>,
}

/// Parse `source` (as `language`) and extract its symbols with per-symbol
/// normalization-stable hashes, plus the file scaffold hash.
///
/// Returns `None` when the language is unsupported or the file fails to parse —
/// the caller records those as `Opaque` in the index (fingerprint = raw source
/// blob hash).
pub fn extract_semantic_file(source: &[u8], language: Language) -> Option<ExtractedFile> {
    // Unsupported language → no grammar → Opaque.
    language.parser_handle()?;
    let source_text = std::str::from_utf8(source).ok()?;
    let parsed = ParsedFile::parse(source_text, language)?;

    let mut symbols = Vec::new();
    // Byte ranges of every extracted definition node — used to carve the
    // residual scaffold (everything NOT covered by a symbol).
    let mut covered: Vec<(usize, usize)> = Vec::new();
    visit_definitions(parsed.root_node(), source, &mut |site| {
        let kind = site.kind;
        let semantic_hash = symbol_semantic_hash(site.node, source, kind);
        let container_path = site.parent_name.map(|p| vec![p]).unwrap_or_default();
        let range = site.node.byte_range();
        covered.push((range.start, range.end));
        symbols.push(SymbolEntry {
            name: site.name,
            kind,
            container_path,
            semantic_hash,
            span: (site.start_line, site.end_line),
        });
    });

    let scaffold_hash = compute_scaffold(parsed.root_node(), source, covered);
    let syntax_index = parsed.syntax_index();

    Some(ExtractedFile {
        language,
        scaffold_hash,
        symbols,
        scopes: syntax_index.semantic_scopes().to_vec(),
        imports: syntax_index.semantic_imports().to_vec(),
        occurrences: syntax_index.occurrences().to_vec(),
    })
}

/// Hash the file scaffold: every non-comment leaf under the root NOT covered by
/// an extracted symbol's byte range, length-prefixed in document order. This is
/// what carries use-decl swaps, `impl Trait` headers, attribute edits,
/// `macro_rules!` bodies and definition-free files into the file digest.
fn compute_scaffold(
    root: tree_sitter::Node<'_>,
    source: &[u8],
    mut covered: Vec<(usize, usize)>,
) -> ContentHash {
    // Merge symbol ranges into disjoint sorted intervals (they nest — a module
    // covers its children).
    covered.sort_by_key(|&(start, _)| start);
    let mut merged: Vec<(usize, usize)> = Vec::with_capacity(covered.len());
    for (start, end) in covered {
        match merged.last_mut() {
            Some(last) if start <= last.1 => last.1 = last.1.max(end),
            _ => merged.push((start, end)),
        }
    }

    let mut stream: Vec<u8> = Vec::new();
    walk_non_comment_leaves(root, |leaf| {
        let range = leaf.byte_range();
        if is_covered(&merged, range.start, range.end) {
            return;
        }
        let bytes = &source[range];
        stream.extend_from_slice(&(bytes.len() as u32).to_le_bytes());
        stream.extend_from_slice(bytes);
    });
    compute_file_scaffold_hash(&stream)
}

/// Whether `[start, end)` lies fully within one of the disjoint sorted
/// intervals in `merged`.
fn is_covered(merged: &[(usize, usize)], start: usize, end: usize) -> bool {
    match merged.binary_search_by(|&(interval_start, _)| interval_start.cmp(&start)) {
        Ok(i) => merged[i].1 >= end,
        Err(0) => false,
        Err(i) => merged[i - 1].1 >= end,
    }
}

/// Build the canonical `hd-sem-sym-v1` token stream for a definition node and
/// hash it. Length-prefixed leaves in document order, comment subtrees skipped.
fn symbol_semantic_hash(
    node: tree_sitter::Node<'_>,
    source: &[u8],
    kind: SymbolKindTag,
) -> ContentHash {
    let mut token_stream: Vec<u8> = Vec::new();
    walk_non_comment_leaves(node, |leaf| {
        let bytes = &source[leaf.byte_range()];
        token_stream.extend_from_slice(&(bytes.len() as u32).to_le_bytes());
        token_stream.extend_from_slice(bytes);
    });
    compute_symbol_semantic_hash(kind, &token_stream)
}

#[cfg(test)]
mod tests {
    use super::*;

    fn extract(src: &str) -> Vec<SymbolEntry> {
        extract_semantic_file(src.as_bytes(), Language::Rust)
            .expect("rust parse")
            .symbols
    }

    fn scaffold(src: &str) -> ContentHash {
        extract_semantic_file(src.as_bytes(), Language::Rust)
            .expect("rust parse")
            .scaffold_hash
    }

    /// DEFECT 1: content that lives OUTSIDE any extracted symbol must still
    /// perturb the file scaffold (and therefore the file digest). Covers all
    /// five classes Fable flagged as digest false-negatives.
    #[test]
    fn scaffold_binds_non_definition_content() {
        // 1. use-decl swap (same fn body)
        assert_ne!(
            scaffold("use a::x;\nfn f() { g(); }\n"),
            scaffold("use b::x;\nfn f() { g(); }\n"),
            "use-decl swap"
        );
        // 2. impl-trait change, identical method body
        assert_ne!(
            scaffold("struct S;\nimpl Display for S { fn fmt(&self) {} }\n"),
            scaffold("struct S;\nimpl Debug for S { fn fmt(&self) {} }\n"),
            "impl trait change"
        );
        // 3. attribute add/remove (attribute_item is a sibling of function_item)
        assert_ne!(
            scaffold("fn f() { g(); }\n"),
            scaffold("#[inline]\nfn f() { g(); }\n"),
            "attribute add"
        );
        // 4. macro_rules! body edit
        assert_ne!(
            scaffold("macro_rules! m { () => { 1 }; }\n"),
            scaffold("macro_rules! m { () => { 2 }; }\n"),
            "macro_rules body edit"
        );
        // 5. definition-free files (re-export only) — two different such files
        //    must not share a digest.
        assert_ne!(
            scaffold("pub use crate::a::Foo;\n"),
            scaffold("pub use crate::b::Bar;\n"),
            "definition-free re-export files"
        );
    }

    /// The scaffold must stay reformat- and comment-stable, like symbol hashes.
    #[test]
    fn scaffold_is_reformat_and_comment_stable() {
        assert_eq!(
            scaffold("use a::x;\nfn f() { g(); }\n"),
            scaffold("use   a::x;\n\n// note\nfn f() {\n    g();\n}\n"),
        );
    }

    #[test]
    fn reformat_leaves_symbol_hash_stable() {
        let a = "fn add(a: i32, b: i32) -> i32 { a + b }\n";
        let b = "fn add(a: i32,   b: i32) -> i32 {\n    a + b\n}\n";
        let sa = extract(a);
        let sb = extract(b);
        assert_eq!(sa.len(), 1);
        assert_eq!(sb.len(), 1);
        assert_eq!(
            sa[0].semantic_hash, sb[0].semantic_hash,
            "reformatting must not change the symbol semantic_hash"
        );
    }

    #[test]
    fn comment_edit_leaves_symbol_hash_stable() {
        let a = "fn f() {\n    // old comment\n    g();\n}\n";
        let b = "fn f() {\n    // a completely different comment\n    g();\n}\n";
        assert_eq!(extract(a)[0].semantic_hash, extract(b)[0].semantic_hash);
    }

    #[test]
    fn one_token_change_perturbs_only_that_symbol() {
        let a = "fn f() -> i32 { 1 }\nfn g() -> i32 { 2 }\n";
        let b = "fn f() -> i32 { 1 }\nfn g() -> i32 { 3 }\n";
        let sa = extract(a);
        let sb = extract(b);
        let f_a = sa.iter().find(|s| s.name == "f").unwrap();
        let f_b = sb.iter().find(|s| s.name == "f").unwrap();
        let g_a = sa.iter().find(|s| s.name == "g").unwrap();
        let g_b = sb.iter().find(|s| s.name == "g").unwrap();
        assert_eq!(
            f_a.semantic_hash, f_b.semantic_hash,
            "untouched symbol stable"
        );
        assert_ne!(
            g_a.semantic_hash, g_b.semantic_hash,
            "edited symbol changes"
        );
    }

    #[test]
    fn string_literal_contents_included() {
        let a = "fn f() { let s = \"hello\"; }\n";
        let b = "fn f() { let s = \"world\"; }\n";
        assert_ne!(
            extract(a)[0].semantic_hash,
            extract(b)[0].semantic_hash,
            "string literal contents are part of the fingerprint"
        );
    }

    #[test]
    fn types_are_first_class() {
        let src = "struct S { x: u32 }\nenum E { A, B }\ntrait T { fn m(&self); }\n";
        let names: Vec<_> = extract(src).into_iter().map(|s| (s.name, s.kind)).collect();
        assert!(names.contains(&("S".to_string(), SymbolKindTag::Type)));
        assert!(names.contains(&("E".to_string(), SymbolKindTag::Enum)));
        assert!(names.contains(&("T".to_string(), SymbolKindTag::Trait)));
    }

    #[test]
    fn unsupported_language_is_none() {
        assert!(extract_semantic_file(b"whatever", Language::Unknown).is_none());
    }

    #[cfg(feature = "lang-javascript")]
    #[test]
    fn javascript_object_function_property_is_part_of_v5_index() {
        let src = b"const handlers = { save: async (value) => value };\n";
        let extracted = extract_semantic_file(src, Language::JavaScript).expect("javascript parse");
        assert_eq!(EXTRACTOR_VERSION, 5);
        assert!(
            extracted
                .symbols
                .iter()
                .any(|symbol| symbol.name == "save" && symbol.kind == SymbolKindTag::Function),
            "v5 must index object-literal function properties"
        );
    }

    #[test]
    fn extracts_structured_imports_and_symbol_occurrences() {
        use objects::object::{ImportKindTag, OccurrenceRole, SymbolNamespace};

        let source = "pub use crate::api::{greet as hello, User};\nfn run(user: User) { crate::api::greet(); hello(); }\n";
        let extracted = extract_semantic_file(source.as_bytes(), Language::Rust).unwrap();

        assert_eq!(extracted.imports.len(), 1);
        let import = &extracted.imports[0];
        assert_eq!(import.kind, ImportKindTag::Reexport);
        assert_eq!(import.module_specifier, "crate::api");
        assert_eq!(
            import
                .bindings
                .iter()
                .map(|binding| (&*binding.imported, &*binding.local))
                .collect::<Vec<_>>(),
            vec![("greet", "hello"), ("User", "User")]
        );

        assert!(extracted.occurrences.iter().any(|occurrence| {
            occurrence.role == OccurrenceRole::Call
                && occurrence.name == "greet"
                && occurrence.qualifier == ["crate", "api"]
        }));
        assert!(extracted.occurrences.iter().any(|occurrence| {
            occurrence.role == OccurrenceRole::Call && occurrence.name == "hello"
        }));
        assert!(extracted.occurrences.iter().any(|occurrence| {
            occurrence.role == OccurrenceRole::TypeReference
                && occurrence.name == "User"
                && occurrence.namespace == SymbolNamespace::Type
        }));
        assert!(extracted.occurrences.iter().any(|occurrence| {
            occurrence.role == OccurrenceRole::Definition
                && occurrence.name == "run"
                && occurrence.scope == 0
        }));
        assert_eq!(extracted.scopes[0].local_id, 0);
    }

    #[cfg(feature = "lang-typescript")]
    #[test]
    fn typescript_import_bindings_reexports_and_calls_are_source_local() {
        use objects::object::{ImportKindTag, OccurrenceRole, SymbolNamespace};

        let source = "import type { Request as Req } from './types';\nimport client, { run as execute } from './client';\nexport { User } from './models';\nexport function handle(req: Req) { client.run(); execute(); }\n";
        let extracted = extract_semantic_file(source.as_bytes(), Language::TypeScript).unwrap();

        let types = extracted
            .imports
            .iter()
            .find(|import| import.module_specifier == "./types")
            .unwrap();
        assert_eq!(types.bindings[0].imported, "Request");
        assert_eq!(types.bindings[0].local, "Req");
        assert_eq!(types.bindings[0].namespace, SymbolNamespace::Type);

        let client = extracted
            .imports
            .iter()
            .find(|import| import.module_specifier == "./client")
            .unwrap();
        assert_eq!(
            client
                .bindings
                .iter()
                .map(|binding| (&*binding.imported, &*binding.local))
                .collect::<Vec<_>>(),
            vec![("default", "client"), ("run", "execute")]
        );
        assert_eq!(
            extracted
                .imports
                .iter()
                .find(|import| import.module_specifier == "./models")
                .unwrap()
                .kind,
            ImportKindTag::Reexport
        );
        assert!(extracted.occurrences.iter().any(|occurrence| {
            occurrence.role == OccurrenceRole::Call
                && occurrence.name == "run"
                && occurrence.qualifier == ["client"]
        }));
    }

    // ── Zig (heddle#1068) ────────────────────────────────────────────────

    /// A `.zig` blob must extract a real file node — symbols with per-symbol
    /// `semantic_hash`es — not the `Opaque` fallback that `Language::Unknown`
    /// produced before Zig support.
    #[cfg(feature = "lang-zig")]
    #[test]
    fn zig_blob_extracts_real_symbols_with_hashes() {
        let src = "pub const Point = struct {\n    x: f64,\n    pub fn dist(self: Point) f64 { return self.x; }\n};\n\ntest \"works\" { _ = 1; }\n";
        let extracted = extract_semantic_file(src.as_bytes(), Language::Zig)
            .expect("zig parses to a real node");
        assert_eq!(language_name(extracted.language), "zig");

        let by_name = |n: &str| extracted.symbols.iter().find(|s| s.name == n);
        let point = by_name("Point").expect("Point type extracted");
        assert_eq!(point.kind, SymbolKindTag::Type);
        let dist = by_name("dist").expect("method extracted");
        assert_eq!(dist.kind, SymbolKindTag::Function);
        assert_eq!(dist.container_path, vec!["Point".to_string()]);
        let test = by_name("test:\"works\"").expect("test block extracted");
        assert_eq!(test.kind, SymbolKindTag::Function);

        // Every symbol carries a non-degenerate per-symbol semantic_hash.
        assert!(
            extracted
                .symbols
                .iter()
                .all(|s| s.semantic_hash != ContentHash::compute(b"")),
            "symbols must carry real semantic hashes"
        );
    }

    /// Reformatting a Zig file — whitespace + comments only — must leave the
    /// file node's `semantic_digest` (and every symbol hash + the scaffold)
    /// byte-identical.
    #[cfg(feature = "lang-zig")]
    #[test]
    fn zig_reformat_leaves_semantic_digest_stable() {
        use objects::object::SemanticFileNode;

        let tight = "const std = @import(\"std\");\npub fn add(a: i32, b: i32) i32 { return a + b; }\npub const Point = struct { x: f64, pub fn dist(self: Point) f64 { return self.x; } };\n";
        let loose = "const std = @import(\"std\");\n\n// a comment\npub fn add(a: i32,   b: i32) i32 {\n    return a + b;\n}\n\npub const Point = struct {\n    // fields\n    x: f64,\n    pub fn dist(self: Point) f64 {\n        return self.x;\n    }\n};\n";

        let ea = extract_semantic_file(tight.as_bytes(), Language::Zig).expect("tight parses");
        let eb = extract_semantic_file(loose.as_bytes(), Language::Zig).expect("loose parses");

        assert_eq!(ea.imports.len(), 1);
        assert_eq!(ea.imports[0].module_specifier, "std");
        assert_eq!(ea.imports[0].kind, objects::object::ImportKindTag::Dynamic);

        assert_eq!(
            ea.scaffold_hash, eb.scaffold_hash,
            "scaffold must be reformat/comment stable"
        );

        let node = |e: &ExtractedFile, src: &str| {
            SemanticFileNode::new(
                language_name(e.language),
                grammar_version(e.language),
                EXTRACTOR_VERSION,
                ContentHash::compute(src.as_bytes()),
                e.scaffold_hash,
                objects::object::SemanticFileFacts {
                    symbols: e.symbols.clone(),
                    scopes: e.scopes.clone(),
                    imports: e.imports.clone(),
                    occurrences: e.occurrences.clone(),
                },
            )
        };
        // The source blobs differ, but the reformat-stable digest must not.
        assert_eq!(
            node(&ea, tight).semantic_digest,
            node(&eb, loose).semantic_digest,
            "reformatting must not perturb the file semantic_digest"
        );
    }
}