bonsai-ninja-security 0.2.2

//! Dependency / package inventory built from rule metadata + workspace imports.
//!
//! A rule is considered "evident" in the workspace when any of its
//! `imports` / `modules` / `packages` strings appears in:
//!
//! * An import fact emitted by the language adapter's indexer
//!   (via `decl_index.refs` of kind `Import`, or the
//!   `import_index` the workspace computes).
//! * A manifest / lockfile declared under the workspace root whose
//!   basename matches one of the rule's `manifests` / `lockfiles`
//!   entries.
//! * A dependency manifest under the workspace root whose content
//!   names one of the rule's `packages` entries. This catches
//!   first-party scans where the workspace itself is the flagged
//!   package, so the package name appears in `pom.xml`,
//!   `package.json`, `Cargo.toml`, etc. rather than in an import.
//!
//! Output rows unify the three signals so reviewers see WHAT is present
//! and WHY the wrapper flagged it.

use crate::loader::Rulepack;
use crate::rule::{Rule, Severity};
use ahash::{AHashMap, AHashSet};
use bonsai_common::dependency_metadata::dependency_metadata_dir_skipped;
use bonsai_common::workspace_relative_filter_path;
use bonsai_workspace::Workspace;
use serde::Serialize;
use std::path::Path;
use std::sync::Arc;

#[derive(Clone, Debug, Serialize)]
pub struct DependencyRow {
    pub language: String,
    pub key: String,
    /// The rule ids that claimed this dependency — source & sink both.
    pub rule_ids: Vec<String>,
    /// `frameworks` / `packages` / `imports` / `modules` / `manifests` /
    /// `lockfiles` signals that fired, from most- to least-specific.
    pub signals: Vec<String>,
    /// The files that carry matching manifests / lockfiles / imports.
    pub evidence_files: Vec<String>,
    /// Severity of the highest-severity rule that claimed this entry.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub severity: Option<Severity>,
    /// Unique tags from the claiming rules.
    pub tags: Vec<String>,
}

#[derive(Clone, Debug, Default, Serialize)]
pub struct DependencyInventory {
    pub rows: Vec<DependencyRow>,
}

/// Build the inventory. Scans the workspace root for manifest / lockfile
/// basenames and the workspace index for import / module facts.
pub fn build_inventory(pack: &Rulepack, ws: &Workspace, root: &Path) -> DependencyInventory {
    let manifest_files = scan_manifest_files(root, pack);
    let import_evidence_by_lang = collect_workspace_import_evidence(ws, pack);
    let manifest_package_evidence_by_lang = collect_manifest_package_evidence(pack, &manifest_files);

    let mut by_key: AHashMap<(String, String), DependencyRow> = AHashMap::new();
    for rule in pack.all_rules() {
        if !rule.enabled {
            continue;
        }
        for key in rule_signal_keys(rule) {
            let (signals, evidence) = rule_key_evidence(
                rule,
                &key,
                &manifest_files,
                &import_evidence_by_lang,
                &manifest_package_evidence_by_lang,
            );
            if signals.is_empty() {
                continue;
            }
            let entry = by_key
                .entry((rule.language.clone(), key.clone()))
                .or_insert(DependencyRow {
                    language: rule.language.clone(),
                    key,
                    rule_ids: Vec::new(),
                    signals: Vec::new(),
                    evidence_files: Vec::new(),
                    severity: None,
                    tags: Vec::new(),
                });
            if !entry.rule_ids.contains(&rule.id) {
                entry.rule_ids.push(rule.id.clone());
            }
            for s in signals {
                if !entry.signals.contains(&s) {
                    entry.signals.push(s);
                }
            }
            for e in evidence {
                let e = workspace_relative_filter_path(Some(root), &e);
                if !entry.evidence_files.contains(&e) {
                    entry.evidence_files.push(e);
                }
            }
            match (entry.severity, rule.severity) {
                (None, Some(s)) => entry.severity = Some(s),
                (Some(prev), Some(s)) if s > prev => entry.severity = Some(s),
                _ => {}
            }
            if let Some(tag) = &rule.tag {
                if !entry.tags.contains(tag) {
                    entry.tags.push(tag.clone());
                }
            }
        }
    }

    let mut rows: Vec<DependencyRow> = by_key.into_values().collect();
    rows.sort_by(|a, b| (a.language.as_str(), a.key.as_str()).cmp(&(b.language.as_str(), b.key.as_str())));
    DependencyInventory { rows }
}

#[derive(Clone, Debug)]
pub(crate) struct WorkspaceDependencyPackages {
    pub fingerprint: u64,
    pub packages: Arc<AHashSet<String>>,
}

#[derive(Clone, Debug)]
pub(crate) struct WorkspaceDependencyPackageContext {
    fingerprint: u64,
    by_language: AHashMap<String, Arc<AHashSet<String>>>,
}

static WORKSPACE_DEPENDENCY_PACKAGE_SCAN_LOCKS: std::sync::LazyLock<
    parking_lot::Mutex<AHashMap<String, std::sync::Weak<parking_lot::Mutex<()>>>>,
> = std::sync::LazyLock::new(|| parking_lot::Mutex::new(AHashMap::new()));
type WorkspaceDependencyPackageRoots = AHashMap<String, std::sync::Weak<WorkspaceDependencyPackageContext>>;
type ActiveWorkspaceDependencyPackages = AHashMap<u64, WorkspaceDependencyPackageRoots>;
static ACTIVE_WORKSPACE_DEPENDENCY_PACKAGES: std::sync::LazyLock<
    parking_lot::RwLock<ActiveWorkspaceDependencyPackages>,
> = std::sync::LazyLock::new(|| parking_lot::RwLock::new(AHashMap::new()));

/// Own one immutable dependency-manifest snapshot for a complete analysis run.
///
/// The workspace id separates two SDK workspaces opened on the same root.
/// Point constraint rechecks can therefore reuse the exact package facts
/// proved by endpoint discovery even if a manifest is saved concurrently.
pub(crate) struct WorkspaceDependencyPackageSnapshot {
    workspace_id: u64,
    root_key: String,
    context: Arc<WorkspaceDependencyPackageContext>,
}

impl Drop for WorkspaceDependencyPackageSnapshot {
    fn drop(&mut self) {
        let mut active = ACTIVE_WORKSPACE_DEPENDENCY_PACKAGES.write();
        if let Some(workspace) = active.get_mut(&self.workspace_id) {
            if workspace
                .get(&self.root_key)
                .and_then(std::sync::Weak::upgrade)
                .is_some_and(|context| Arc::ptr_eq(&context, &self.context))
            {
                workspace.remove(&self.root_key);
            }
            if workspace.is_empty() {
                active.remove(&self.workspace_id);
            }
        }
    }
}

/// Return package/dependency names declared in workspace-level manifests
/// for `language`.
///
/// Per-file imports are still the strongest evidence used by the matcher,
/// but framework template files often do not contain an import for the
/// runtime package they execute under (Rails ERB / ActionView is the
/// canonical case). This language-scoped manifest context lets package gates
/// accept those real project dependencies without letting one language's
/// manifest satisfy another language's package-scoped rules in a monorepo.
pub(crate) fn workspace_dependency_packages_for_language_in_workspace(
    root: &Path,
    language: &str,
    workspace_id: u64,
) -> WorkspaceDependencyPackages {
    let root_key = workspace_dependency_root_key(root);
    if let Some(context) = active_workspace_dependency_package_context(workspace_id, &root_key) {
        return workspace_dependency_packages_from_context(&context, language);
    }
    WorkspaceDependencyPackages {
        fingerprint: 0,
        packages: Arc::new(AHashSet::new()),
    }
}

fn workspace_dependency_packages_from_context(
    context: &WorkspaceDependencyPackageContext,
    language: &str,
) -> WorkspaceDependencyPackages {
    WorkspaceDependencyPackages {
        fingerprint: context.fingerprint,
        packages: context
            .by_language
            .get(language)
            .cloned()
            .unwrap_or_else(|| Arc::new(AHashSet::new())),
    }
}

pub(crate) fn begin_workspace_dependency_package_snapshot(
    root: &Path,
    workspace_id: u64,
    pack: &Rulepack,
) -> WorkspaceDependencyPackageSnapshot {
    let root_key = workspace_dependency_root_key(root);
    let context = Arc::new(build_workspace_dependency_package_context(root, &pack.metadata));
    let mut active = ACTIVE_WORKSPACE_DEPENDENCY_PACKAGES.write();
    active.retain(|_, roots| {
        roots.retain(|_, context| context.strong_count() != 0);
        !roots.is_empty()
    });
    active
        .entry(workspace_id)
        .or_default()
        .insert(root_key.clone(), Arc::downgrade(&context));
    WorkspaceDependencyPackageSnapshot {
        workspace_id,
        root_key,
        context,
    }
}

pub(crate) fn workspace_dependency_package_context_for_scan(
    root: &Path,
    workspace_id: u64,
) -> Arc<WorkspaceDependencyPackageContext> {
    let root_key = workspace_dependency_root_key(root);
    active_workspace_dependency_package_context(workspace_id, &root_key).unwrap_or_else(|| {
        Arc::new(WorkspaceDependencyPackageContext {
            fingerprint: 0,
            by_language: AHashMap::new(),
        })
    })
}

fn active_workspace_dependency_package_context(
    workspace_id: u64,
    root_key: &str,
) -> Option<Arc<WorkspaceDependencyPackageContext>> {
    ACTIVE_WORKSPACE_DEPENDENCY_PACKAGES
        .read()
        .get(&workspace_id)
        .and_then(|workspace| workspace.get(root_key))
        .and_then(std::sync::Weak::upgrade)
}

/// Return per-root ownership for one immutable broad-match manifest snapshot.
///
/// Weak entries avoid retaining every workspace path ever opened by a
/// long-lived service. Callers hold the returned `Arc` and its mutex guard
/// across matching; a concurrent scan of another root remains independent.
pub(crate) fn workspace_dependency_package_scan_lock(root: &Path) -> Arc<parking_lot::Mutex<()>> {
    let root_key = workspace_dependency_root_key(root);
    let mut locks = WORKSPACE_DEPENDENCY_PACKAGE_SCAN_LOCKS.lock();
    locks.retain(|_, lock| lock.strong_count() != 0);
    if let Some(lock) = locks.get(&root_key).and_then(std::sync::Weak::upgrade) {
        return lock;
    }
    let lock = Arc::new(parking_lot::Mutex::new(()));
    locks.insert(root_key, Arc::downgrade(&lock));
    lock
}

fn workspace_dependency_root_key(root: &Path) -> String {
    root.canonicalize()
        .unwrap_or_else(|_| root.to_path_buf())
        .to_string_lossy()
        .into_owned()
}

fn build_workspace_dependency_package_context(
    root: &Path,
    metadata: &crate::loader::RulepackMetadata,
) -> WorkspaceDependencyPackageContext {
    let mut by_language: AHashMap<String, AHashSet<String>> = AHashMap::new();
    let mut fingerprint_parts = dependency_metadata_fingerprint_parts(metadata);
    let _ = walk_rulepack_dependency_files(root, metadata, |path, rel| {
        let bytes = std::fs::read(path)?;
        fingerprint_parts.push(format!("{rel}:{}", bonsai_hash::fnv1a_bytes64(&bytes)));
        let text = String::from_utf8_lossy(&bytes);
        let packages = dependency_manifest_package_tokens(&text);
        if !packages.is_empty() {
            for language in dependency_manifest_languages(path, metadata) {
                let packages = dependency_manifest_packages_for_language(&packages, language, metadata);
                by_language
                    .entry(language.to_string())
                    .or_default()
                    .extend(packages.into_iter());
            }
        }
        Ok(())
    });
    fingerprint_parts.sort();
    let fingerprint = bonsai_hash::fnv1a_names64(&fingerprint_parts);
    let by_language = by_language
        .into_iter()
        .map(|(language, packages)| (language, Arc::new(packages)))
        .collect();
    WorkspaceDependencyPackageContext {
        fingerprint,
        by_language,
    }
}

fn dependency_metadata_fingerprint_parts(metadata: &crate::loader::RulepackMetadata) -> Vec<String> {
    let mut languages = metadata.languages.iter().collect::<Vec<_>>();
    languages.sort_by_key(|(language, _)| language.as_str());
    let mut parts = Vec::new();
    for (language, values) in languages {
        let mut patterns = values.dependency_manifest_patterns.clone();
        patterns.sort();
        for pattern in patterns {
            parts.push(format!("metadata:{language}:manifest:{pattern}"));
        }
        parts.push(format!(
            "metadata:{language}:hyphen:{}",
            values.normalize_hyphen_to_underscore
        ));
        let mut aliases = values.package_aliases.iter().collect::<Vec<_>>();
        aliases.sort_by_key(|(distribution, _)| distribution.as_str());
        for (distribution, imports) in aliases {
            let mut imports = imports.clone();
            imports.sort();
            for import in imports {
                parts.push(format!("metadata:{language}:alias:{distribution}:{import}"));
            }
        }
        for prefix in &values.package_matching.strip_import_prefixes {
            parts.push(format!("metadata:{language}:package-strip-prefix:{prefix}"));
        }
        for suffix in &values.package_matching.strip_import_suffixes {
            parts.push(format!("metadata:{language}:package-strip-suffix:{suffix}"));
        }
        for separator in &values.package_matching.package_separators {
            parts.push(format!("metadata:{language}:package-separator:{separator}"));
        }
        if let Some(binding) = &values.package_matching.call_qualifier_from_package_tail {
            parts.push(format!(
                "metadata:{language}:package-tail-separator:{}",
                binding.package_separator
            ));
            for separator in &binding.call_separators {
                parts.push(format!("metadata:{language}:call-separator:{separator}"));
            }
        }
    }
    parts
}

fn walk_rulepack_dependency_files(
    root: &Path,
    metadata: &crate::loader::RulepackMetadata,
    mut visit: impl FnMut(&Path, &str) -> std::io::Result<()>,
) -> std::io::Result<()> {
    let stable_root = root.canonicalize().unwrap_or_else(|_| root.to_path_buf());
    let mut pending = vec![stable_root.clone()];
    while let Some(dir) = pending.pop() {
        let entries = match std::fs::read_dir(&dir) {
            Ok(entries) => entries,
            Err(error)
                if matches!(
                    error.kind(),
                    std::io::ErrorKind::NotFound | std::io::ErrorKind::PermissionDenied
                ) =>
            {
                continue;
            }
            Err(error) => return Err(error),
        };
        for entry in entries {
            let entry = match entry {
                Ok(entry) => entry,
                Err(error)
                    if matches!(
                        error.kind(),
                        std::io::ErrorKind::NotFound | std::io::ErrorKind::PermissionDenied
                    ) =>
                {
                    continue;
                }
                Err(error) => return Err(error),
            };
            let file_type = match entry.file_type() {
                Ok(file_type) => file_type,
                Err(error)
                    if matches!(
                        error.kind(),
                        std::io::ErrorKind::NotFound | std::io::ErrorKind::PermissionDenied
                    ) =>
                {
                    continue;
                }
                Err(error) => return Err(error),
            };
            if file_type.is_symlink() {
                continue;
            }
            let path = entry.path();
            let name = path
                .file_name()
                .and_then(|name| name.to_str())
                .unwrap_or_default();
            if file_type.is_dir() {
                if !dependency_metadata_dir_skipped(name) {
                    pending.push(path);
                }
                continue;
            }
            if file_type.is_file() && !dependency_manifest_languages(&path, metadata).is_empty() {
                let relative = path
                    .strip_prefix(&stable_root)
                    .unwrap_or(&path)
                    .to_string_lossy()
                    .replace('\\', "/");
                visit(&path, &relative)?;
            }
        }
    }
    Ok(())
}

fn dependency_manifest_languages<'a>(
    path: &Path,
    metadata: &'a crate::loader::RulepackMetadata,
) -> Vec<&'a str> {
    let basename = path.file_name().and_then(|name| name.to_str()).unwrap_or("");
    let mut languages = metadata
        .languages
        .iter()
        .filter(|(_, language)| {
            language
                .dependency_manifest_patterns
                .iter()
                .any(|pattern| dependency_manifest_pattern_matches(pattern, basename))
        })
        .map(|(language, _)| language.as_str())
        .collect::<Vec<_>>();
    languages.sort_unstable();
    languages
}

fn dependency_manifest_pattern_matches(pattern: &str, basename: &str) -> bool {
    let pattern = pattern.to_ascii_lowercase();
    let basename = basename.to_ascii_lowercase();
    let Some(star) = pattern.find('*') else {
        return pattern == basename;
    };
    if pattern[star + 1..].contains('*') {
        return false;
    }
    basename.starts_with(&pattern[..star]) && basename.ends_with(&pattern[star + 1..])
}

fn dependency_manifest_package_tokens(text: &str) -> AHashSet<String> {
    let mut out = AHashSet::new();
    let mut token = String::new();
    for ch in text.chars() {
        if dependency_package_token_char(ch) {
            token.push(ch);
            continue;
        }
        insert_dependency_package_token(&mut out, &token);
        token.clear();
    }
    insert_dependency_package_token(&mut out, &token);
    out
}

fn dependency_package_token_char(ch: char) -> bool {
    ch.is_ascii_alphanumeric() || matches!(ch, '_' | '-' | '.' | '/' | '@' | ':' | '+')
}

fn insert_dependency_package_token(out: &mut AHashSet<String>, token: &str) {
    let token = token.trim_matches(|ch: char| matches!(ch, '.' | '/' | ':' | '+' | '-' | '_'));
    if token.len() < 2 || !token.chars().any(|ch| ch.is_ascii_alphabetic()) {
        return;
    }
    out.insert(token.to_string());
    let lower = token.to_ascii_lowercase();
    out.insert(lower);
}

fn dependency_manifest_packages_for_language(
    packages: &AHashSet<String>,
    language: &str,
    metadata: &crate::loader::RulepackMetadata,
) -> AHashSet<String> {
    let mut out = packages.clone();
    let Some(language_metadata) = metadata.languages.get(language) else {
        return out;
    };
    for package in packages {
        if language_metadata.normalize_hyphen_to_underscore && package.contains('-') {
            insert_dependency_package_token(&mut out, &package.replace('-', "_"));
        }
        if let Some(aliases) = language_metadata
            .package_aliases
            .get(&package.to_ascii_lowercase())
        {
            for alias in aliases {
                insert_dependency_package_token(&mut out, alias);
            }
        }
    }
    out
}

/// Collect every distinct signal key the rule advertises across the
/// `frameworks` / `packages` / `modules` / `imports` fields. The
/// dedup keeps the inventory's row keys stable when a rule mentions
/// the same package across multiple field families.
fn rule_signal_keys(rule: &Rule) -> Vec<String> {
    let mut keys = Vec::new();
    keys.extend(rule.frameworks.iter().cloned());
    keys.extend(rule.packages.iter().cloned());
    keys.extend(rule.modules.iter().cloned());
    keys.extend(rule.imports.iter().cloned());
    keys.sort();
    keys.dedup();
    keys
}

/// Gather signal labels and evidence file paths showing where one
/// dependency key is grounded — manifest filenames, lockfile filenames,
/// adapter-visible imports, or package names mentioned in dependency
/// manifests. Keeping this key-scoped prevents one matching package signal
/// from making every package/import listed on a broad multi-framework rule
/// look present in the workspace.
fn rule_key_evidence(
    rule: &Rule,
    key: &str,
    manifest_files: &[String],
    import_evidence_by_lang: &AHashMap<String, AHashMap<String, String>>,
    manifest_package_evidence_by_lang: &AHashMap<String, AHashMap<String, String>>,
) -> (Vec<String>, Vec<String>) {
    let mut signals = Vec::new();
    let mut evidence = Vec::new();
    // Manifest basename match: rule lists `pom.xml` / `Cargo.toml` / etc.
    for manifest_name in &rule.manifests {
        if let Some(path) = manifest_files.iter().find(|file_path| {
            Path::new(file_path.as_str())
                .file_name()
                .and_then(|name| name.to_str())
                == Some(manifest_name.as_str())
        }) {
            signals.push(format!("manifests:{manifest_name}"));
            evidence.push(path.clone());
        }
    }
    // Lockfile basename match: rule lists `Cargo.lock` / `pnpm-lock.yaml` / etc.
    for lockfile_name in &rule.lockfiles {
        if let Some(path) = manifest_files.iter().find(|file_path| {
            Path::new(file_path.as_str())
                .file_name()
                .and_then(|name| name.to_str())
                == Some(lockfile_name.as_str())
        }) {
            signals.push(format!("lockfiles:{lockfile_name}"));
            evidence.push(path.clone());
        }
    }
    if let Some(lang_import_evidence) = import_evidence_by_lang.get(&rule.language) {
        // Both `imports:` / `modules:` and `packages:` go through the
        // shared `import_matches_package` predicate (see `pkg.rs`).
        // The runtime matcher uses the same helper, so dependency
        // inventory and per-file package context gate cannot drift on what
        // counts as "this file imports package X" — including PHP
        // namespaces (`Cake\\Datasource`), Perl scope (`DBI::db`),
        // C/C++ header forms (`sqlite3.h`), and dotted prefixes.
        if rule.imports.iter().any(|needle| needle == key) {
            push_import_signal_for_key(&mut signals, &mut evidence, lang_import_evidence, "imports", key);
        }
        if rule.modules.iter().any(|needle| needle == key) {
            push_import_signal_for_key(&mut signals, &mut evidence, lang_import_evidence, "modules", key);
        }
        if rule.packages.iter().any(|needle| needle == key) {
            push_import_signal_for_key(&mut signals, &mut evidence, lang_import_evidence, "packages", key);
        }
        if rule.frameworks.iter().any(|needle| needle == key) {
            push_import_signal_for_key(
                &mut signals,
                &mut evidence,
                lang_import_evidence,
                "frameworks",
                key,
            );
        }
    }
    // Manifest-content scan: catches first-party packages that ARE the
    // workspace (e.g. a Java project whose own `pom.xml` declares
    // `<artifactId>log4j-core</artifactId>`) without an import line
    // anywhere in the source tree.
    if let Some(manifest_package_evidence) = manifest_package_evidence_by_lang.get(&rule.language) {
        if rule.packages.iter().any(|needle| needle == key) {
            if let Some(path) = manifest_package_evidence.get(key) {
                signals.push(format!("packages:{key}"));
                evidence.push(path.clone());
            }
        }
        if rule.frameworks.iter().any(|needle| needle == key) {
            if let Some(path) = manifest_package_evidence.get(key) {
                signals.push(format!("frameworks:{key}"));
                evidence.push(path.clone());
            }
        }
    }
    signals.sort();
    signals.dedup();
    evidence.sort();
    evidence.dedup();
    (signals, evidence)
}

fn push_import_signal_for_key(
    signals: &mut Vec<String>,
    evidence: &mut Vec<String>,
    lang_import_evidence: &AHashMap<String, String>,
    signal_prefix: &str,
    key: &str,
) {
    if let Some(file) = lang_import_evidence.get(key) {
        signals.push(format!("{signal_prefix}:{key}"));
        evidence.push(file.clone());
    }
}

/// True when `path` is a recognised package-manager manifest whose
/// content the inventory should scan for package-name evidence.
/// Anything not on this list (random YAML, dotenv, prose) is skipped
/// to avoid false positives from prose mentioning a package name.
fn is_dependency_manifest_file(path: &str, metadata: &crate::loader::RulepackMetadata) -> bool {
    let Some(basename) = Path::new(path).file_name().and_then(|name| name.to_str()) else {
        return false;
    };
    is_dependency_manifest_basename(basename, metadata)
}

fn is_dependency_manifest_basename(basename: &str, metadata: &crate::loader::RulepackMetadata) -> bool {
    !dependency_manifest_languages(Path::new(basename), metadata).is_empty()
}

fn collect_manifest_package_evidence(
    pack: &Rulepack,
    manifest_files: &[String],
) -> AHashMap<String, AHashMap<String, String>> {
    let target_keys_by_lang = dependency_target_keys_by_language(pack);
    let mut evidence_by_language: AHashMap<String, AHashMap<String, String>> = AHashMap::new();
    for path in manifest_files {
        if !is_dependency_manifest_file(path, &pack.metadata) {
            continue;
        }
        let languages = dependency_manifest_languages(Path::new(path), &pack.metadata);
        if languages.is_empty() {
            continue;
        }
        let text = match std::fs::read_to_string(path) {
            Ok(text) => text,
            Err(error) if error.kind() == std::io::ErrorKind::NotFound => {
                tracing::debug!(path, "manifest disappeared while scanning dependency inventory");
                continue;
            }
            Err(error) => {
                tracing::warn!(
                    path,
                    error_kind = ?error.kind(),
                    error = %error,
                    "failed to read manifest while scanning dependency inventory"
                );
                continue;
            }
        };
        let packages = dependency_manifest_package_tokens(&text);
        for language in languages {
            let Some(target_keys) = target_keys_by_lang.get(language) else {
                continue;
            };
            let language_packages =
                dependency_manifest_packages_for_language(&packages, language, &pack.metadata);
            for package in language_packages {
                if target_keys.contains(package.as_str()) {
                    evidence_by_language
                        .entry(language.to_string())
                        .or_default()
                        .entry(package)
                        .or_insert_with(|| path.clone());
                }
            }
        }
    }
    evidence_by_language
}

/// Walk `root` collecting relevant manifest and lockfile paths. The
/// traversal is intentionally not depth-limited: monorepos commonly place
/// package manifests many levels below the workspace root, and missing one
/// would make dependency evidence incomplete. The basename filter keeps the
/// inventory from retaining every regular file path in large repositories.
fn scan_manifest_files(root: &Path, pack: &Rulepack) -> Vec<String> {
    let target_names = manifest_target_names(pack);
    let mut paths = Vec::new();
    walk_dir(root, &target_names, &pack.metadata, &mut paths);
    paths.sort();
    paths.dedup();
    paths
}

fn manifest_target_names(pack: &Rulepack) -> AHashSet<String> {
    let mut target_names = AHashSet::new();
    for rule in pack.all_rules() {
        if !rule.enabled {
            continue;
        }
        target_names.extend(rule.manifests.iter().cloned());
        target_names.extend(rule.lockfiles.iter().cloned());
    }
    target_names
}

/// Explicit-stack directory walker. Skips known vendored / build / cache
/// directory names so dependency inventory doesn't pick up evidence from
/// `node_modules/`, `target/`, `.venv/`, etc. — these would mistake
/// third-party manifests for first-party project evidence.
///
/// Directory symlinks are not followed. Besides keeping evidence inside the
/// selected workspace, this prevents cycles without imposing a semantic
/// depth cap.
fn walk_dir(
    root: &Path,
    target_names: &AHashSet<String>,
    metadata: &crate::loader::RulepackMetadata,
    out: &mut Vec<String>,
) {
    let mut pending = vec![root.to_path_buf()];
    while let Some(dir) = pending.pop() {
        let rd = match std::fs::read_dir(&dir) {
            Ok(rd) => rd,
            Err(error) if error.kind() == std::io::ErrorKind::NotFound => {
                tracing::debug!(
                    path = %dir.display(),
                    "dependency inventory directory disappeared while scanning"
                );
                continue;
            }
            Err(error) => {
                tracing::warn!(
                    path = %dir.display(),
                    error_kind = ?error.kind(),
                    error = %error,
                    "failed to read dependency inventory directory"
                );
                continue;
            }
        };
        for entry in rd.flatten() {
            let name = match entry.file_name().to_str() {
                Some(name) => name.to_string(),
                None => continue,
            };
            if dependency_metadata_dir_skipped(&name) {
                continue;
            }
            let Ok(file_type) = entry.file_type() else {
                continue;
            };
            let path = entry.path();
            if file_type.is_dir() {
                pending.push(path);
            } else if file_type.is_file()
                && (target_names.contains(&name) || is_dependency_manifest_basename(&name, metadata))
            {
                out.push(path.display().to_string());
            }
        }
    }
}

/// Collect the first evidence file for every rule dependency key present in
/// workspace imports, keyed by language. The candidate generator mirrors
/// `import_matches_package` but runs once per import target instead of once
/// per `(rule key, import target)` pair.
fn collect_workspace_import_evidence(
    ws: &Workspace,
    pack: &Rulepack,
) -> AHashMap<String, AHashMap<String, String>> {
    let target_keys_by_lang = dependency_target_keys_by_language(pack);
    let db = ws.db();
    let mut evidence_by_language: AHashMap<String, AHashMap<String, String>> = AHashMap::new();
    for file in ws.vfs().all_files() {
        let Some(adapter) = db.adapter_for(file) else {
            continue;
        };
        let language = adapter.language_id().as_str().to_string();
        let Some(target_keys) = target_keys_by_lang.get(&language) else {
            continue;
        };
        let package_matching = pack
            .metadata
            .languages
            .get(&language)
            .map(|metadata| &metadata.package_matching)
            .cloned()
            .unwrap_or_default();
        let file_path = ws
            .vfs()
            .path(file)
            .map(|p| p.to_string_lossy().into_owned())
            .unwrap_or_default();
        if let Some(import_index) = db.import_index_uncached(file) {
            for import_spec in import_index.imports {
                for candidate in import_package_candidates(&import_spec.module, &package_matching) {
                    if target_keys.contains(candidate.as_str()) {
                        evidence_by_language
                            .entry(language.clone())
                            .or_default()
                            .entry(candidate)
                            .or_insert_with(|| file_path.clone());
                    }
                }
            }
        }
    }
    evidence_by_language
}

fn dependency_target_keys_by_language(pack: &Rulepack) -> AHashMap<String, AHashSet<String>> {
    let mut out: AHashMap<String, AHashSet<String>> = AHashMap::new();
    for rule in pack.all_rules() {
        if !rule.enabled {
            continue;
        }
        out.entry(rule.language.clone())
            .or_default()
            .extend(rule_signal_keys(rule));
    }
    out
}

fn import_package_candidates(
    imported: &str,
    semantics: &crate::loader::PackageMatchSemantics,
) -> Vec<String> {
    let imported = semantics
        .strip_import_prefixes
        .iter()
        .find_map(|prefix| imported.strip_prefix(prefix))
        .unwrap_or(imported);
    let mut out = Vec::new();
    push_import_candidate(&mut out, imported);
    let suffix_stripped = semantics
        .strip_import_suffixes
        .iter()
        .find_map(|suffix| imported.strip_suffix(suffix))
        .unwrap_or(imported);
    push_import_candidate(&mut out, suffix_stripped);
    for separator in &semantics.package_separators {
        push_prefix_candidates(&mut out, imported, separator);
        if suffix_stripped != imported {
            push_prefix_candidates(&mut out, suffix_stripped, separator);
        }
    }
    out
}

fn push_prefix_candidates(out: &mut Vec<String>, imported: &str, sep: &str) {
    let mut search_start = 0usize;
    while let Some(offset) = imported[search_start..].find(sep) {
        let absolute = search_start + offset;
        if absolute > 0 {
            push_import_candidate(out, &imported[..absolute]);
        }
        search_start = absolute + sep.len();
        if search_start >= imported.len() {
            break;
        }
    }
}

fn push_import_candidate(out: &mut Vec<String>, candidate: &str) {
    if candidate.is_empty() || out.iter().any(|existing| existing == candidate) {
        return;
    }
    out.push(candidate.to_string());
}

#[cfg(test)]
#[path = "deps_tests.rs"]
mod tests;