codingest 0.1.5

//! Builder: orchestrates parse → model → load phases.

pub mod call_edges;
pub mod js_workspace;
pub mod load;
pub mod other_edges;
pub mod routes;
pub mod semantic_edges;
pub mod type_edges;

use crate::models::{ParseResult, ProjectInfo, SourceRoot};
use crate::parsers::{detect_languages, get_parser, language_for_path};
// builder + load both return `Arc<DirGraph>` (not the pyapi
// `KnowledgeGraph` wrapper) so this subtree stays engine-only.
// The pyapi callsite (`code_tree.build()` pyfunction) wraps the
// result via `KnowledgeGraph::from_arc`.
use kglite::api::DirGraph;
use std::collections::{BTreeMap, BTreeSet, HashSet};
use std::path::{Path, PathBuf};
use std::sync::Arc;
use walkdir::WalkDir;

/// Graph node label for a `ClassInfo`, keyed on its `kind` discriminator.
/// `struct` → `Struct`, `mixin` (Dart) → `Mixin`; everything else →
/// `Class` (covers `class`, `extension` / `extension_type`, Swift `actor`,
/// …, all distinguished further by the node's `kind` property).
///
/// Single source of truth for the `ClassInfo.kind` → label mapping —
/// used by node creation and by the DEFINES / HAS_METHOD / IMPLEMENTS /
/// USES_TYPE edge routers, which must all agree on the endpoint label.
pub(crate) fn class_node_type(kind: &str) -> &'static str {
    match kind {
        "struct" => "Struct",
        "mixin" => "Mixin",
        _ => "Class",
    }
}

/// Public `build()` entry point matching the Python API — returns just the
/// graph. Thin wrapper over [`run_with_options_stats`]; the stats it drops
/// are the CALLS-resolution counters consumed by the `code_tree_stats` dev
/// bin and the re-resolution phases. Single implementation, two entry points.
#[allow(clippy::too_many_arguments)]
pub fn run_with_options(
    input: &Path,
    verbose: bool,
    include_tests: bool,
    save_to: Option<&Path>,
    max_loc_per_file: Option<usize>,
    include_docs: bool,
) -> Result<Arc<DirGraph>, String> {
    run_with_options_stats(
        input,
        verbose,
        include_tests,
        save_to,
        max_loc_per_file,
        include_docs,
    )
    .map(|(graph, _stats)| graph)
}

/// Full `build()` implementation — also returns [`call_edges::CallResolutionStats`].
///
/// Accepts either a directory or an explicit manifest file. When given a
/// manifest (or when one is auto-detected in the directory) the parser
/// uses manifest-declared source/test roots; otherwise it falls back to a
/// recursive directory scan.
///
/// `max_loc_per_file`, when set, skips files whose newline count exceeds
/// the threshold — they get a `FileInfo` with `skip_reason="too_large"`
/// so paths remain queryable, but no AST is parsed. Useful for repos
/// like dotnet/runtime where ~80 autogenerated test files (89k LOC each)
/// dominate parse time without contributing structural information.
#[allow(clippy::too_many_arguments)]
pub fn run_with_options_stats(
    input: &Path,
    verbose: bool,
    include_tests: bool,
    save_to: Option<&Path>,
    max_loc_per_file: Option<usize>,
    include_docs: bool,
) -> Result<(Arc<DirGraph>, call_edges::CallResolutionStats), String> {
    let input = input.canonicalize().unwrap_or_else(|_| input.to_path_buf());

    let (project_root, mut project_info) = if input.is_file() {
        let project_root = input
            .parent()
            .map(PathBuf::from)
            .unwrap_or_else(|| input.clone());
        let info =
            crate::manifest::try_read_manifest_file(&input, &project_root)?.ok_or_else(|| {
                format!(
                    "Not a recognised manifest file: {}",
                    input.file_name().and_then(|o| o.to_str()).unwrap_or(""),
                )
            })?;
        (project_root, Some(info))
    } else if input.is_dir() {
        let info = crate::manifest::try_read_manifest(&input)?;
        (input.clone(), info)
    } else {
        return Err(format!("Not a file or directory: {}", input.display()));
    };

    let mut combined = ParseResult::new();
    let mut parsed_any = false;

    if let Some(info) = &mut project_info {
        if info.source_roots.is_empty() {
            // Manifest exists but declared no primary source roots (e.g. a
            // tooling-only pyproject.toml in a C/C++ repo). Don't parse just
            // tests — fall through to the whole-repo scan below so the
            // primary codebase isn't silently skipped.
            if verbose {
                eprintln!(
                    "Manifest: {} ({}) — no source roots declared, scanning whole repo",
                    info.manifest_path,
                    info.build_system.as_deref().unwrap_or("")
                );
            }
        } else {
            let mut roots: Vec<_> = info.source_roots.clone();
            if include_tests {
                roots.extend(info.test_roots.iter().cloned());
            }
            let roots = collapse_covered_roots(roots);
            if verbose {
                eprintln!(
                    "Manifest: {} ({})",
                    info.manifest_path,
                    info.build_system.as_deref().unwrap_or("")
                );
                let labels: Vec<String> = roots
                    .iter()
                    .map(|r| {
                        r.path
                            .strip_prefix(&project_root)
                            .map(|p| p.display().to_string())
                            .unwrap_or_else(|_| r.path.display().to_string())
                    })
                    .collect();
                eprintln!("Source roots: {}", labels.join(", "));
            }
            let t_parse = std::time::Instant::now();
            for root in &roots {
                if !root.path.is_dir() {
                    continue;
                }
                let result = parse_directory(&root.path, &project_root, verbose, max_loc_per_file);
                combined.merge(result);
                parsed_any = true;
            }
            if verbose && parsed_any {
                eprintln!("[timing] parse: {:.3}s", t_parse.elapsed().as_secs_f64());
            }
        }
    }

    if !parsed_any {
        if !project_root.is_dir() {
            return Err(format!("Not a directory: {}", project_root.display()));
        }
        let t_parse = std::time::Instant::now();
        let result = parse_directory(&project_root, &project_root, verbose, max_loc_per_file);
        combined.merge(result);
        if verbose {
            eprintln!("[timing] parse: {:.3}s", t_parse.elapsed().as_secs_f64());
        }
    }

    if !include_tests {
        retain_non_test_entities(&mut combined);
    }
    if let Some(info) = &mut project_info {
        reconcile_project_languages(info, &combined);
    }

    finalize_and_load(
        combined,
        project_info,
        &project_root,
        include_docs,
        verbose,
        save_to,
    )
}

/// Remove roots already covered by an ancestor walk. Manifest discovery can
/// legitimately report both `.` and `tests/`; walking both emits duplicate
/// entities before graph loading.
fn collapse_covered_roots(roots: Vec<SourceRoot>) -> Vec<SourceRoot> {
    let mut kept: Vec<(PathBuf, SourceRoot)> = Vec::new();
    for root in roots {
        let path = root
            .path
            .canonicalize()
            .unwrap_or_else(|_| root.path.clone());
        if kept.iter().any(|(ancestor, _)| path.starts_with(ancestor)) {
            continue;
        }
        kept.retain(|(candidate, _)| !candidate.starts_with(&path));
        kept.push((path, root));
    }
    kept.into_iter().map(|(_, root)| root).collect()
}

/// Enforce `include_tests=false` after parsing so it also applies to broad
/// manifest roots and the whole-repository fallback, not only declared test
/// roots.
fn retain_non_test_entities(result: &mut ParseResult) {
    let test_paths: HashSet<String> = result
        .files
        .iter()
        .filter(|file| file.is_test)
        .map(|file| file.path.clone())
        .collect();
    if test_paths.is_empty() {
        return;
    }

    let removed_types: HashSet<String> = result
        .classes
        .iter()
        .filter(|item| test_paths.contains(&item.file_path))
        .map(|item| item.qualified_name.clone())
        .chain(
            result
                .interfaces
                .iter()
                .filter(|item| test_paths.contains(&item.file_path))
                .map(|item| item.qualified_name.clone()),
        )
        .collect();

    result.files.retain(|item| !item.is_test);
    result
        .functions
        .retain(|item| !test_paths.contains(&item.file_path));
    result
        .classes
        .retain(|item| !test_paths.contains(&item.file_path));
    result
        .enums
        .retain(|item| !test_paths.contains(&item.file_path));
    result
        .interfaces
        .retain(|item| !test_paths.contains(&item.file_path));
    result
        .attributes
        .retain(|item| !test_paths.contains(&item.file_path));
    result
        .constants
        .retain(|item| !test_paths.contains(&item.file_path));
    result
        .elements
        .retain(|item| !test_paths.contains(&item.file_path));
    result
        .selectors
        .retain(|item| !test_paths.contains(&item.file_path));

    let retained_functions: HashSet<&str> = result
        .functions
        .iter()
        .map(|item| item.qualified_name.as_str())
        .collect();
    let retained_constants: HashSet<&str> = result
        .constants
        .iter()
        .map(|item| item.qualified_name.as_str())
        .collect();
    result.control_transfers.retain(|site| {
        retained_functions.contains(site.caller.as_str())
            && site
                .target
                .as_deref()
                .is_none_or(|target| retained_functions.contains(target))
    });
    result.reference_sites.retain(|site| {
        retained_functions.contains(site.caller.as_str())
            && retained_constants.contains(site.target.as_str())
    });
    result.symbol_relationships.retain(|relationship| {
        retained_constants.contains(relationship.source.as_str())
            && match relationship.target_kind {
                crate::models::SymbolTargetKind::Constant => {
                    retained_constants.contains(relationship.target.as_str())
                }
                crate::models::SymbolTargetKind::Function => {
                    retained_functions.contains(relationship.target.as_str())
                }
            }
    });

    let retained_types: HashSet<&str> = result
        .classes
        .iter()
        .map(|item| item.qualified_name.as_str())
        .chain(
            result
                .interfaces
                .iter()
                .map(|item| item.qualified_name.as_str()),
        )
        .collect();
    result.type_relationships.retain_mut(|relationship| {
        relationship
            .methods
            .retain(|method| !test_paths.contains(&method.file_path));
        !removed_types.contains(&relationship.source_type)
            || retained_types.contains(relationship.source_type.as_str())
    });
}

/// Manifest-declared languages are useful intent, but the graph metadata must
/// also describe every language actually retained in the parsed file set.
fn reconcile_project_languages(project: &mut ProjectInfo, result: &ParseResult) {
    let present: BTreeSet<&str> = result
        .files
        .iter()
        .map(|file| file.language.as_str())
        .filter(|language| !language.is_empty())
        .collect();
    let mut known: HashSet<String> = project.languages.iter().cloned().collect();
    for language in crate::parsers::registry::LANGUAGES {
        if present.contains(language.id) && known.insert(language.id.to_string()) {
            project.languages.push(language.id.to_string());
        }
    }
    for language in present {
        if known.insert(language.to_string()) {
            project.languages.push(language.to_string());
        }
    }
}

/// Walk `walk_dir` for source files and parse them; resulting File-node
/// paths are computed relative to `project_root`, not `walk_dir`. This
/// matters when multiple source roots share a common file name at matching
/// depths (e.g. Cargo workspace crates each with `src/lib.rs`) — keying
/// dedup on a `walk_dir`-relative `rel_path` would collapse them.
fn parse_directory(
    walk_dir: &Path,
    project_root: &Path,
    verbose: bool,
    max_loc_per_file: Option<usize>,
) -> ParseResult {
    // One walk, partition by language. The previous implementation walked
    // `dir` once for `detect_languages` and again per-language inside each
    // parser's `parse_directory` — N+1 traversals of the same tree. On
    // dotnet/runtime that was 8 walks of 57k entries; consolidating shaves
    // ~1–2s off the parse phase before any per-file work begins.
    let t_walk = std::time::Instant::now();
    let mut by_lang: BTreeMap<&'static str, Vec<PathBuf>> = BTreeMap::new();
    // Skip VCS / build-output / virtualenv / package-cache subdirs at
    // any depth (`.venv`, `target`, `node_modules`, `__pycache__`, …).
    // Without this, a supplemental source root pointing to a directory
    // with a nested venv would index every site-package's Python source.
    for entry in WalkDir::new(walk_dir)
        .into_iter()
        .filter_entry(crate::manifest::walk_filter)
        .filter_map(Result::ok)
    {
        if !entry.file_type().is_file() {
            continue;
        }
        if let Some(lang) = language_for_path(entry.path()) {
            by_lang
                .entry(lang)
                .or_default()
                .push(entry.path().to_path_buf());
        }
    }

    // `.h` is ambiguous: C or C++. `language_for_path` maps it to C, but many
    // C++ engines (kuzu, LevelDB, …) use `.h` for their C++ headers — parsed by
    // the C grammar, every `class` / `namespace` / `template` is dropped (the
    // dominant cause of kuzu's empty type layer). If the repo contains any
    // definitively-C++ source, route its `.h` files to the C++ parser, which is
    // a superset of C and still extracts any genuine C headers correctly. `.c`
    // files stay C.
    if by_lang.contains_key("cpp") {
        if let Some(c_files) = by_lang.remove("c") {
            let (h_files, c_only): (Vec<PathBuf>, Vec<PathBuf>) = c_files
                .into_iter()
                .partition(|p| p.extension().and_then(|e| e.to_str()) == Some("h"));
            if !h_files.is_empty() {
                by_lang.entry("cpp").or_default().extend(h_files);
            }
            if !c_only.is_empty() {
                by_lang.insert("c", c_only);
            }
        }
    }

    // WalkDir follows the host filesystem's directory-entry order, which is
    // not stable across platforms. Parsing in path order keeps graph node
    // insertion (and therefore unsorted query results) reproducible.
    for files in by_lang.values_mut() {
        files.sort();
    }

    if verbose {
        let langs: Vec<&'static str> = by_lang.keys().copied().collect();
        eprintln!(
            "  Detected languages in {}: {:?}",
            walk_dir.display(),
            langs
        );
        for lang in &langs {
            eprintln!("  Found {} {} files", by_lang[lang].len(), lang);
        }
        eprintln!("[timing] walk: {:.3}s", t_walk.elapsed().as_secs_f64());
    }

    let mut combined = ParseResult::new();
    for (lang, files) in by_lang {
        let Some(parser) = get_parser(lang) else {
            continue;
        };
        // Optional pre-filter: split files whose newline count exceeds
        // `max_loc_per_file` into a "skipped" pile that's recorded as
        // FileInfo without invoking the parser.
        let (to_parse, skipped) = match max_loc_per_file {
            Some(threshold) => prefilter_oversized(&files, threshold, project_root, lang),
            None => (files.clone(), Vec::new()),
        };
        if verbose && !skipped.is_empty() {
            eprintln!(
                "  Skipped {} {} files over max_loc_per_file (threshold {})",
                skipped.len(),
                lang,
                max_loc_per_file.unwrap_or(0)
            );
        }
        let t_lang = std::time::Instant::now();
        let mut result = parser.parse_files(&to_parse, project_root);
        result.files.extend(skipped);
        if verbose {
            eprintln!(
                "[timing] parse {}: {:.3}s ({} files)",
                lang,
                t_lang.elapsed().as_secs_f64(),
                to_parse.len()
            );
        }
        combined.merge(result);
    }
    combined
}

/// Split a slice of file paths into (under-threshold, oversized-skipped).
/// For each oversized file, build a synthetic [`FileInfo`] with
/// `skip_reason = "too_large"` so the caller can record it without
/// invoking the parser. Counts newlines via a single read (the byte-size
/// pre-filter avoids reading files that can't possibly exceed the
/// threshold — a file with fewer bytes than the LOC cap can't have more
/// lines than the cap).
fn prefilter_oversized(
    files: &[PathBuf],
    threshold: usize,
    src_root: &Path,
    language: &str,
) -> (Vec<PathBuf>, Vec<crate::models::FileInfo>) {
    use std::io::{BufRead, BufReader};
    let mut to_parse = Vec::with_capacity(files.len());
    let mut skipped = Vec::new();
    for fp in files {
        // Cheap byte-size pre-filter: a file with fewer bytes than
        // `threshold` cannot have more newlines than `threshold`.
        let size_bytes = std::fs::metadata(fp).map(|m| m.len() as usize).unwrap_or(0);
        if size_bytes <= threshold {
            to_parse.push(fp.clone());
            continue;
        }
        // Accurate newline count: bail as soon as we exceed the threshold.
        let Ok(file) = std::fs::File::open(fp) else {
            to_parse.push(fp.clone());
            continue;
        };
        let mut reader = BufReader::new(file);
        let mut buf = Vec::new();
        let mut loc: usize = 0;
        let mut over = false;
        while let Ok(n) = reader.read_until(b'\n', &mut buf) {
            if n == 0 {
                break;
            }
            loc += 1;
            buf.clear();
            if loc > threshold {
                over = true;
                break;
            }
        }
        if over {
            // Drain remaining lines to get a final count. Bounded by
            // file size, so this is O(file_size) with no parsing.
            while let Ok(n) = reader.read_until(b'\n', &mut buf) {
                if n == 0 {
                    break;
                }
                loc += 1;
                buf.clear();
            }
            let rel_path = fp.strip_prefix(src_root).unwrap_or(fp);
            let filename = fp
                .file_name()
                .and_then(|s| s.to_str())
                .unwrap_or("")
                .to_string();
            skipped.push(crate::models::FileInfo {
                path: rel_path.display().to_string(),
                filename,
                loc: loc as u32,
                module_path: String::new(),
                language: language.to_string(),
                submodule_declarations: Vec::new(),
                imports: Vec::new(),
                exports: Vec::new(),
                annotations: None,
                is_test: false,
                skip_reason: Some("too_large".into()),
            });
        } else {
            to_parse.push(fp.clone());
        }
    }
    (to_parse, skipped)
}

#[allow(clippy::too_many_arguments)]
fn finalize_and_load(
    mut combined: ParseResult,
    project_info: Option<crate::models::ProjectInfo>,
    project_root: &Path,
    include_docs: bool,
    verbose: bool,
    save_to: Option<&Path>,
) -> Result<(Arc<DirGraph>, call_edges::CallResolutionStats), String> {
    if verbose {
        eprintln!(
            "Parsed: {} files, {} functions, {} classes, {} enums, {} interfaces, {} attributes, {} constants",
            combined.files.len(),
            combined.functions.len(),
            combined.classes.len(),
            combined.enums.len(),
            combined.interfaces.len(),
            combined.attributes.len(),
            combined.constants.len()
        );
    }

    let t_dedup = std::time::Instant::now();
    dedup_by_key(&mut combined.files, |f| f.path.clone());
    preserve_overloaded_function_ids(&mut combined.functions, &mut combined.type_relationships);
    dedup_by_key(&mut combined.functions, |f| f.qualified_name.clone());
    dedup_by_key(&mut combined.classes, |c| c.qualified_name.clone());
    dedup_by_key(&mut combined.enums, |e| e.qualified_name.clone());
    dedup_by_key(&mut combined.interfaces, |i| i.qualified_name.clone());
    dedup_by_key(&mut combined.constants, |c| c.qualified_name.clone());
    combined.control_transfers.sort();
    combined.control_transfers.dedup();
    combined.reference_sites.sort();
    combined.reference_sites.dedup();
    combined.symbol_relationships.sort();
    combined.symbol_relationships.dedup();
    if verbose {
        eprintln!("[timing] dedup: {:.3}s", t_dedup.elapsed().as_secs_f64());
    }

    let t_load = std::time::Instant::now();
    // tsconfig `paths` + workspace-package table. Discovered only when the
    // parse actually produced TS/JS sources, so no other ecosystem pays for
    // the extra small-file walk.
    let t_ws = std::time::Instant::now();
    let js_workspace = if combined
        .files
        .iter()
        .any(|f| crate::parsers::registry::uses_module_path_imports(&f.language))
    {
        js_workspace::JsWorkspace::discover(project_root)
    } else {
        js_workspace::JsWorkspace::default()
    };
    if verbose || std::env::var_os("KGLITE_CODE_TREE_VERBOSE").is_some() {
        eprintln!(
            "[timing] js workspace discovery: {:.3}s",
            t_ws.elapsed().as_secs_f64()
        );
    }
    // `mut` is consumed by the cross-language pass below (and the okf docs pass).
    let (mut graph, call_stats) =
        load::load_into_graph(&combined, project_info.as_ref(), &js_workspace)?;
    if verbose {
        eprintln!("[timing] load: {:.3}s", t_load.elapsed().as_secs_f64());
    }

    // Optional docs pass: ingest the repo's markdown as `:Doc` nodes and link
    // them to the code symbols they mention. Runs after all code nodes exist so
    // symbol resolution can find them. Reuses the OKF parser (gated `okf`).
    if include_docs {
        let t_docs = std::time::Instant::now();
        #[cfg(feature = "docs")]
        {
            let g =
                std::sync::Arc::get_mut(&mut graph).expect("graph is uniquely owned during build");
            crate::docs::ingest_and_link(g, project_root, verbose)?;
            if verbose {
                eprintln!("[timing] docs: {:.3}s", t_docs.elapsed().as_secs_f64());
            }
        }
        #[cfg(not(feature = "docs"))]
        {
            let _ = (project_root, t_docs);
            return Err("include_docs=true requires the 'okf' Cargo feature".into());
        }
    }

    // Cross-language HTTP boundary edges: link client HTTP calls to the server
    // Route nodes they target (by normalized path), so impact analysis crosses
    // the client/server (and language) boundary. Runs after load so Route nodes
    // exist; a no-op when the graph has none.
    {
        let g = std::sync::Arc::get_mut(&mut graph).expect("graph is uniquely owned during build");
        let t_xlang = std::time::Instant::now();
        crate::cross_lang::ingest_http_cross_edges(g, project_root, verbose)?;
        if verbose {
            eprintln!(
                "[timing] cross-lang: {:.3}s",
                t_xlang.elapsed().as_secs_f64()
            );
        }
    }

    if let Some(dest) = save_to {
        // Mirror the prep that `KnowledgeGraph.save()` does — without these
        // steps, property column stores aren't materialised before
        // serialisation and only `id`/`title`/`type` survive the round-trip.
        let mut graph = graph;
        kglite::api::io::prepare_save(&mut graph);
        std::sync::Arc::make_mut(&mut graph).enable_columnar();
        let dest_str = dest.to_string_lossy();
        kglite::api::io::write_kgl(&graph, &dest_str).map_err(|e| e.to_string())?;
        return Ok((graph, call_stats));
    }
    Ok((graph, call_stats))
}

/// Legacy entry — directory-only, used by the initial smoke test.
pub fn run(src_dir: &Path, verbose: bool) -> Result<Arc<DirGraph>, String> {
    let mut combined = ParseResult::new();
    let languages = detect_languages(src_dir);
    if verbose {
        eprintln!("Detected languages: {:?}", languages);
    }
    for lang in languages {
        let Some(parser) = get_parser(lang) else {
            if verbose {
                eprintln!("  (no Rust parser yet for {lang})");
            }
            continue;
        };
        if verbose {
            eprintln!("Parsing {} files...", lang);
        }
        let result = parser.parse_directory(src_dir, verbose);
        combined.merge(result);
    }

    // Dedup — overlapping source/test roots can parse the same file twice.
    // Last-seen wins so test-root flags take priority (matches builder.py).
    dedup_by_key(&mut combined.files, |f| f.path.clone());
    dedup_by_key(&mut combined.functions, |f| f.qualified_name.clone());
    dedup_by_key(&mut combined.classes, |c| c.qualified_name.clone());
    dedup_by_key(&mut combined.enums, |e| e.qualified_name.clone());
    dedup_by_key(&mut combined.interfaces, |i| i.qualified_name.clone());
    dedup_by_key(&mut combined.constants, |c| c.qualified_name.clone());
    combined.control_transfers.sort();
    combined.control_transfers.dedup();
    combined.reference_sites.sort();
    combined.reference_sites.dedup();
    combined.symbol_relationships.sort();
    combined.symbol_relationships.dedup();

    if verbose {
        eprintln!(
            "Parsed: {} files, {} functions, {} classes, {} enums, {} interfaces, {} attributes, {} constants",
            combined.files.len(),
            combined.functions.len(),
            combined.classes.len(),
            combined.enums.len(),
            combined.interfaces.len(),
            combined.attributes.len(),
            combined.constants.len()
        );
    }

    load::load_into_graph(&combined, None, &js_workspace::JsWorkspace::default())
        .map(|(graph, _stats)| graph)
}

/// Keep the last occurrence of each key, preserving encounter order otherwise.
fn dedup_by_key<T, K, F>(items: &mut Vec<T>, mut key: F)
where
    K: Eq + std::hash::Hash,
    F: FnMut(&T) -> K,
{
    let mut seen: std::collections::HashMap<K, usize> = std::collections::HashMap::new();
    for (idx, item) in items.iter().enumerate() {
        seen.insert(key(item), idx);
    }
    if seen.len() == items.len() {
        return;
    }
    let mut keep: Vec<usize> = seen.into_values().collect();
    keep.sort_unstable();
    let mut out: Vec<T> = Vec::with_capacity(keep.len());
    for (idx, item) in std::mem::take(items).into_iter().enumerate() {
        if keep.binary_search(&idx).is_ok() {
            out.push(item);
        }
    }
    *items = out;
}

const OVERLOAD_ID_SEPARATOR: char = '#';
const SHA256_HEX_LEN: usize = 64;

/// Preserve same-scope overloads without changing any ordinary function ID.
///
/// Parsers can legitimately emit several functions with the same qualified
/// name. Exact `(qualified_name, signature)` duplicates are still parser
/// duplicates and retain the builder's established last-wins behavior. Only a
/// base ID with more than one distinct signature is decorated.
fn preserve_overloaded_function_ids(
    functions: &mut Vec<crate::models::FunctionInfo>,
    type_relationships: &mut [crate::models::TypeRelationship],
) {
    dedup_by_key(functions, |function| {
        (function.qualified_name.clone(), function.signature.clone())
    });

    let mut signatures_by_id: std::collections::HashMap<&str, HashSet<&str>> =
        std::collections::HashMap::new();
    for function in functions.iter() {
        signatures_by_id
            .entry(function.qualified_name.as_str())
            .or_default()
            .insert(function.signature.as_str());
    }
    let overloaded: HashSet<String> = signatures_by_id
        .into_iter()
        .filter_map(|(qualified_name, signatures)| {
            (signatures.len() > 1).then(|| qualified_name.to_string())
        })
        .collect();
    if overloaded.is_empty() {
        return;
    }

    let replacements: std::collections::HashMap<(String, String), String> = functions
        .iter_mut()
        .filter(|function| overloaded.contains(function.qualified_name.as_str()))
        .map(|function| {
            let base = function.qualified_name.clone();
            let signature = function.signature.clone();
            let qualified_name = overloaded_qualified_name(&base, &signature);
            function.qualified_name.clone_from(&qualified_name);
            ((base, signature), qualified_name)
        })
        .collect();

    for relationship in type_relationships {
        for method in &mut relationship.methods {
            if let Some(qualified_name) =
                replacements.get(&(method.qualified_name.clone(), method.signature.clone()))
            {
                method.qualified_name.clone_from(qualified_name);
            }
        }
    }
}

fn overloaded_qualified_name(base: &str, signature: &str) -> String {
    use sha2::{Digest, Sha256};

    let discriminator: String = Sha256::digest(signature)
        .iter()
        .map(|byte| format!("{byte:02x}"))
        .collect();
    format!("{base}{OVERLOAD_ID_SEPARATOR}{discriminator}")
}

pub(super) fn overload_base_qualified_name(qualified_name: &str) -> Option<&str> {
    let (base, discriminator) = qualified_name.rsplit_once(OVERLOAD_ID_SEPARATOR)?;
    (discriminator.len() == SHA256_HEX_LEN
        && discriminator.bytes().all(|byte| byte.is_ascii_hexdigit()))
    .then_some(base)
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::models::{ClassInfo, FileInfo, FunctionInfo, TypeRelationship};
    use crate::parsers::get_parser;
    use kglite::api::GraphRead;
    use kglite::datatypes::Value;

    #[test]
    fn overlapping_roots_collapse_to_the_covering_ancestor() {
        let temp = tempfile::tempdir().expect("tempdir");
        let project = temp.path().join("project");
        std::fs::create_dir_all(project.join("tests")).expect("create tests dir");
        std::fs::write(
            project.join("pyproject.toml"),
            "[project]\nname = \"demo\"\n[tool.setuptools.packages.find]\nwhere = [\".\"]\n",
        )
        .expect("write manifest");
        let info = crate::manifest::try_read_manifest(&project)
            .expect("read manifest")
            .expect("manifest exists");
        assert_eq!(info.source_roots.len(), 1);
        assert_eq!(info.test_roots.len(), 1);

        let collapsed = collapse_covered_roots(
            info.source_roots
                .into_iter()
                .chain(info.test_roots)
                .collect(),
        );
        assert_eq!(collapsed.len(), 1);
        assert_eq!(collapsed[0].label.as_deref(), Some("setuptools-find"));
    }

    #[test]
    fn test_filter_removes_test_files_and_every_owned_entity() {
        let source = FileInfo {
            path: "src/app.py".into(),
            language: "python".into(),
            ..FileInfo::default()
        };
        let test = FileInfo {
            path: "tests/test_app.py".into(),
            language: "python".into(),
            is_test: true,
            ..FileInfo::default()
        };
        let source_fn = FunctionInfo {
            qualified_name: "app.run".into(),
            file_path: source.path.clone(),
            ..FunctionInfo::default()
        };
        let test_fn = FunctionInfo {
            qualified_name: "test_app.test_run".into(),
            file_path: test.path.clone(),
            ..FunctionInfo::default()
        };
        let test_class = ClassInfo {
            qualified_name: "test_app.Case".into(),
            file_path: test.path.clone(),
            ..ClassInfo::default()
        };
        let mut result = ParseResult {
            files: vec![source, test],
            functions: vec![source_fn, test_fn.clone()],
            classes: vec![test_class],
            type_relationships: vec![TypeRelationship {
                source_type: "test_app.Case".into(),
                relationship: "inherent".into(),
                methods: vec![test_fn],
                ..TypeRelationship::default()
            }],
            ..ParseResult::default()
        };

        retain_non_test_entities(&mut result);
        assert_eq!(result.files.len(), 1);
        assert_eq!(result.functions.len(), 1);
        assert!(result.classes.is_empty());
        assert!(result.type_relationships.is_empty());
    }

    #[test]
    fn fallback_scan_honours_include_tests_false() {
        let temp = tempfile::tempdir().expect("tempdir");
        let project = temp.path().join("project");
        std::fs::create_dir_all(project.join("tests")).expect("create tests dir");
        std::fs::write(project.join("app.py"), "def run():\n    return 1\n").expect("write source");
        std::fs::write(
            project.join("tests/test_app.py"),
            "def test_run():\n    assert True\n",
        )
        .expect("write test");

        let graph = run_with_options(&project, false, false, None, None, false)
            .expect("build fallback project");
        let nodes: Vec<(String, String)> = graph
            .graph
            .node_indices()
            .filter_map(|index| graph.graph.node_weight(index))
            .map(|node| {
                (
                    node.node_type_str(&graph.interner).to_string(),
                    node.id().to_string(),
                )
            })
            .collect();
        assert!(
            nodes
                .iter()
                .any(|(kind, id)| kind == "File" && id.contains("app.py")),
            "{nodes:?}"
        );
        assert!(nodes.iter().all(|(_, id)| !id.contains("test_app")));
    }

    #[test]
    fn malformed_manifest_fails_directory_and_explicit_file_builds() {
        let temp = tempfile::tempdir().expect("tempdir");
        let project = temp.path().join("project");
        std::fs::create_dir(&project).expect("create project");
        let manifest = project.join("pyproject.toml");
        std::fs::write(&manifest, "[project\nname = broken").expect("write manifest");

        for input in [&project, &manifest] {
            let error = match run_with_options(input, false, false, None, None, false) {
                Ok(_) => panic!("malformed manifest must fail"),
                Err(error) => error,
            };
            assert!(error.contains("pyproject.toml"), "{error}");
        }
    }

    #[test]
    fn project_languages_include_parsed_polyglot_files_in_registry_order() {
        let temp = tempfile::tempdir().expect("tempdir");
        let project = temp.path().join("project");
        std::fs::create_dir_all(project.join("demo")).expect("create Python package");
        std::fs::write(
            project.join("pyproject.toml"),
            "[project]\nname = \"demo\"\n[tool.setuptools.packages.find]\nwhere = [\".\"]\n",
        )
        .expect("write manifest");
        std::fs::write(
            project.join("demo/__init__.py"),
            "def run():\n    return 1\n",
        )
        .expect("write Python");
        std::fs::write(
            project.join("app.ts"),
            "export function render() { return 1; }\n",
        )
        .expect("write TypeScript");
        std::fs::write(project.join("style.css"), ".app { color: red; }\n").expect("write CSS");

        let graph = run_with_options(&project, false, false, None, None, false)
            .expect("build polyglot project");
        let languages = graph
            .graph
            .node_indices()
            .filter_map(|index| graph.graph.node_weight(index))
            .find(|node| node.node_type_str(&graph.interner) == "Project")
            .and_then(|node| node.get_property("languages"))
            .expect("Project.languages");
        assert_eq!(
            languages.as_ref(),
            &Value::String("python, typescript, css".into())
        );
    }

    #[test]
    fn fallback_parsers_keep_nested_same_stem_module_identity() {
        let temp = tempfile::tempdir().expect("tempdir");
        let project = temp.path().join("project");
        for dir in ["a", "b"] {
            std::fs::create_dir_all(project.join(dir)).expect("create fixture dir");
        }
        let fixtures = [
            ("html", "html", "<!doctype html><h1>Title</h1>\n", "."),
            ("css", "css", ".item { color: red; }\n", "."),
            ("php", "php", "<?php function run() { return 1; }\n", "\\"),
            ("swift", "swift", "func run() -> Int { return 1 }\n", "."),
            ("dart", "dart", "int run() { return 1; }\n", "."),
        ];
        for (language, extension, source, separator) in fixtures {
            for dir in ["a", "b"] {
                std::fs::write(project.join(format!("{dir}/index.{extension}")), source)
                    .expect("write fixture");
            }
            let result = get_parser(language)
                .expect("registered parser")
                .parse_directory(&project, false);
            let mut modules: Vec<_> = result
                .files
                .iter()
                .filter(|file| file.filename == format!("index.{extension}"))
                .map(|file| file.module_path.clone())
                .collect();
            modules.sort();
            assert_eq!(
                modules,
                [
                    format!("project{separator}a{separator}index"),
                    format!("project{separator}b{separator}index"),
                ],
                "{language}"
            );

            let leaf_modules: HashSet<_> = load::build_modules(&result.files)
                .into_iter()
                .map(|module| module.qualified_name)
                .collect();
            assert!(modules.iter().all(|module| leaf_modules.contains(module)));
            let contains = other_edges::build_module_contains_file_edges(&result.files);
            assert!(modules
                .iter()
                .all(|module| contains.iter().any(|edge| &edge.module == module)));
        }
    }

    #[test]
    fn nested_html_and_css_imports_resolve_to_sibling_directories() {
        let temp = tempfile::tempdir().expect("tempdir");
        let project = temp.path().join("project");
        for dir in ["a", "b"] {
            std::fs::create_dir_all(project.join(dir)).expect("create fixture dir");
            std::fs::write(
                project.join(format!("{dir}/index.html")),
                "<!doctype html><link rel=\"stylesheet\" href=\"theme.css\">\n",
            )
            .expect("write HTML");
            std::fs::write(
                project.join(format!("{dir}/index.css")),
                "@import \"theme.css\";\n.item { color: red; }\n",
            )
            .expect("write CSS index");
            std::fs::write(
                project.join(format!("{dir}/theme.css")),
                ".theme { color: blue; }\n",
            )
            .expect("write CSS target");
        }

        let mut result = get_parser("html")
            .expect("HTML parser")
            .parse_directory(&project, false);
        result.merge(
            get_parser("css")
                .expect("CSS parser")
                .parse_directory(&project, false),
        );
        let known_modules: HashSet<_> = result
            .files
            .iter()
            .map(|file| file.module_path.clone())
            .collect();
        let module_pairs: HashSet<_> = other_edges::build_import_edges(
            &result.files,
            &known_modules,
            &js_workspace::JsWorkspace::default(),
        )
        .into_iter()
        .map(|edge| (edge.file_path, edge.module))
        .collect();
        let module_to_file = result
            .files
            .iter()
            .map(|file| (file.module_path.clone(), file.path.clone()))
            .collect();
        let file_pairs: HashSet<_> = other_edges::build_file_import_edges(
            &result.files,
            &module_to_file,
            &js_workspace::JsWorkspace::default(),
        )
        .into_iter()
        .map(|edge| (edge.source, edge.target))
        .collect();

        for dir in ["a", "b"] {
            for source in [format!("{dir}/index.html"), format!("{dir}/index.css")] {
                assert!(module_pairs.contains(&(source.clone(), format!("project.{dir}.theme"))));
                assert!(file_pairs.contains(&(source, format!("{dir}/theme.css"))));
            }
        }
    }

    #[test]
    fn overload_identity_keeps_last_exact_duplicate_and_leaves_ordinary_ids_alone() {
        let ordinary = FunctionInfo {
            name: "run".into(),
            qualified_name: "demo.run".into(),
            signature: "run()".into(),
            ..FunctionInfo::default()
        };
        let first = FunctionInfo {
            name: "pick".into(),
            qualified_name: "demo.Picker.pick".into(),
            signature: "pick(int)".into(),
            line_number: 1,
            ..FunctionInfo::default()
        };
        let duplicate = FunctionInfo {
            line_number: 2,
            ..first.clone()
        };
        let second = FunctionInfo {
            signature: "pick(string)".into(),
            line_number: 3,
            ..first.clone()
        };
        let mut functions = vec![ordinary, first, duplicate, second];
        let mut relationships = vec![TypeRelationship {
            source_type: "demo.Picker".into(),
            relationship: "inherent".into(),
            methods: functions[1..].to_vec(),
            ..TypeRelationship::default()
        }];

        preserve_overloaded_function_ids(&mut functions, &mut relationships);

        assert_eq!(functions.len(), 3);
        assert_eq!(functions[0].qualified_name, "demo.run");
        let overloads: Vec<_> = functions
            .iter()
            .filter(|function| function.name == "pick")
            .collect();
        assert_eq!(overloads.len(), 2);
        assert!(overloads.iter().any(|function| function.line_number == 2));
        assert!(!overloads.iter().any(|function| function.line_number == 1));
        for function in overloads {
            assert_eq!(
                overload_base_qualified_name(&function.qualified_name),
                Some("demo.Picker.pick")
            );
        }
        assert!(relationships[0]
            .methods
            .iter()
            .all(
                |method| overload_base_qualified_name(&method.qualified_name)
                    == Some("demo.Picker.pick")
            ));
    }

    #[test]
    fn polyglot_overloads_have_stable_nodes_and_conservative_calls() {
        let fixtures = [
            (
                "cpp",
                "Picker.cpp",
                r#"class Picker {
public:
  int pick(int value) { return value; }
  int pick(double value) { return static_cast<int>(value); }
  int run() { return pick(1); }
};
"#,
            ),
            (
                "java",
                "Picker.java",
                r#"class Picker {
  int pick(int value) { return value; }
  int pick(long value) { return (int) value; }
  int run() { return pick(1); }
}
"#,
            ),
            (
                "csharp",
                "Picker.cs",
                r#"class Picker {
  public int pick(int value) { return value; }
  public int pick(string value) { return value.Length; }
  public int run() { return pick(1); }
}
"#,
            ),
            (
                "typescript",
                "Picker.ts",
                r#"class Picker {
  pick(value: number) { return value; }
  pick(value: string) { return value.length; }
  run() { return this.pick(1); }
}
"#,
            ),
        ];

        for (language, filename, source) in fixtures {
            let temp = tempfile::tempdir().expect("tempdir");
            let project = temp.path().join("project");
            std::fs::create_dir(&project).expect("create fixture root");
            std::fs::write(project.join(filename), source).expect("write overload fixture");

            let first = run_with_options(&project, false, false, None, None, false)
                .unwrap_or_else(|error| panic!("{language} first build: {error}"));
            let second = run_with_options(&project, false, false, None, None, false)
                .unwrap_or_else(|error| panic!("{language} second build: {error}"));

            let overload_rows = |graph: &DirGraph| {
                let mut rows: Vec<(String, String)> = graph
                    .graph
                    .node_indices()
                    .filter_map(|index| graph.graph.node_weight(index))
                    .filter(|node| {
                        node.node_type_str(&graph.interner) == "Function"
                            && node.title().as_ref() == &Value::String("pick".into())
                    })
                    .map(|node| {
                        let signature = match node.get_property_value("signature") {
                            Some(Value::String(value)) => value,
                            value => panic!("{language} signature missing: {value:?}"),
                        };
                        let qualified_name = match node.id().as_ref() {
                            Value::String(value) => value.clone(),
                            value => panic!("{language} function ID is not text: {value:?}"),
                        };
                        (qualified_name, signature)
                    })
                    .collect();
                rows.sort();
                rows
            };
            let first_rows = overload_rows(&first);
            let second_rows = overload_rows(&second);
            assert_eq!(first_rows.len(), 2, "{language}: {first_rows:?}");
            assert_eq!(first_rows, second_rows, "{language} IDs changed");
            assert_ne!(first_rows[0].0, first_rows[1].0, "{language}");
            assert_ne!(first_rows[0].1, first_rows[1].1, "{language}");
            for (qualified_name, _) in &first_rows {
                let (_, discriminator) = qualified_name
                    .rsplit_once(OVERLOAD_ID_SEPARATOR)
                    .unwrap_or_else(|| {
                        panic!("{language} ID lacks discriminator: {qualified_name}")
                    });
                assert_eq!(discriminator.len(), SHA256_HEX_LEN, "{language}");
                assert!(discriminator.bytes().all(|byte| byte.is_ascii_hexdigit()));
            }

            let calls_to_overloads = first
                .graph
                .edge_indices()
                .filter(|&edge_index| {
                    let Some(edge) = first.graph.edge_weight(edge_index) else {
                        return false;
                    };
                    if edge.connection_type_str(&first.interner) != "CALLS" {
                        return false;
                    }
                    let Some((source, target)) = first.graph.edge_endpoints(edge_index) else {
                        return false;
                    };
                    let (Some(source), Some(target)) = (
                        first.graph.node_weight(source),
                        first.graph.node_weight(target),
                    ) else {
                        return false;
                    };
                    source.title().as_ref() == &Value::String("run".into())
                        && target.title().as_ref() == &Value::String("pick".into())
                })
                .count();
            assert_eq!(calls_to_overloads, 2, "{language}");
        }
    }
}