use std::path::{Path, PathBuf};

use rustc_hash::{FxHashMap, FxHashSet};

use fallow_config::{PackageJson, ResolvedConfig};

use crate::discover::FileId;
use crate::graph::ModuleGraph;
use crate::resolve::ResolvedModule;
use crate::results::{
    DependencyLocation, ImportSite, TestOnlyDependency, TypeOnlyDependency, UnlistedDependency,
    UnresolvedImport, UnusedDependency,
};
use crate::suppress::{IssueKind, SuppressionContext};

use super::package_json_utils::{find_dep_line_in_json, read_pkg_json_content};
use super::predicates::{
    is_builtin_module, is_config_file, is_implicit_dependency, is_path_alias, is_virtual_module,
};
use super::{LineOffsetsMap, byte_offset_to_line_col};

use crate::plugins::{CompiledPathRule, ProvidedDependencyRule};

/// Return `true` if a virtual-module `prefix` from the active plugin set covers
/// `spec`. Two shapes are recognised:
///
/// - **Plain prefix match** (`@docusaurus/`, `@theme/`, `#imports`, `$app/`):
///   any specifier that `starts_with(prefix)` is covered. This handles the
///   common case where a plugin registers an entire namespace.
/// - **Trailing-slash exact-bare match** (`ember/`): the bare specifier `ember`
///   also matches (via the second branch's `strip_suffix('/')` shortcut),
///   while real npm packages like `ember-cli` and `ember-data` deliberately
///   do not. A no-slash entry would prefix-match them and silence legitimate
///   missing-dep reports.
///
/// Centralised here so the `unresolved-import` and `unlisted-dependency`
/// suppression sites use the same matcher as plugin test helpers (see
/// `Plugin::virtual_module_prefixes` consumers in `crates/core/src/plugins/`).
#[must_use]
pub fn matches_virtual_prefix(prefix: &str, spec: &str) -> bool {
    spec.starts_with(prefix) || prefix.strip_suffix('/').is_some_and(|base| spec == base)
}

/// Return `true` if a workspace `package.json` path is covered by `ignorePatterns`.
///
/// Mirrors the source-walker behavior in `fallow_core::discover::walk`: the glob
/// is matched against the project-root-relative path so relative patterns like
/// `**/dist/**` work as users expect. Without this check, workspace discovery
/// would include build-artifact `package.json` files (e.g., `dist/package.json`
/// generated by ng-packagr / tsc) and report their dependencies as unused.
/// See issue #124.
fn is_package_json_ignored(ws_pkg_path: &Path, config: &ResolvedConfig) -> bool {
    let relative = ws_pkg_path
        .strip_prefix(&config.root)
        .unwrap_or(ws_pkg_path);
    config.ignore_patterns.is_match(relative)
}

/// Per-category configuration for unused dependency detection.
///
/// Each dependency category (prod, dev, optional) has slightly different
/// filter rules. This struct captures those differences so a single helper
/// can handle all three categories.
pub struct DepCategoryConfig {
    /// Which `DependencyLocation` variant to tag results with.
    pub location: DependencyLocation,
    /// Whether to check `is_implicit_dependency` (prod + optional = true, dev = false).
    pub check_implicit: bool,
    /// Whether to check `is_known_tooling_dependency` (dev = true, others = false).
    pub check_known_tooling: bool,
    /// Whether to check `plugin_tooling` set (prod + dev = true, optional = false).
    pub check_plugin_tooling: bool,
}

/// Shared sets used by `collect_unused_for_category` to filter dependencies.
pub struct SharedDepSets<'a> {
    pub plugin_referenced: &'a FxHashSet<&'a str>,
    pub plugin_tooling: &'a FxHashSet<&'a str>,
    pub script_used: &'a FxHashSet<&'a str>,
    pub ignore_deps: &'a FxHashSet<&'a str>,
}

struct PeerDependencyResolver {
    cache: FxHashMap<(PathBuf, String), Vec<String>>,
}

impl PeerDependencyResolver {
    fn new() -> Self {
        Self {
            cache: FxHashMap::default(),
        }
    }

    fn peer_dependency_closure<'b>(
        &mut self,
        package_root: &Path,
        seeds: impl IntoIterator<Item = &'b str>,
    ) -> FxHashSet<String> {
        let mut peer_used = FxHashSet::default();
        let mut expanded = FxHashSet::default();
        let mut queue: Vec<String> = seeds.into_iter().map(str::to_string).collect();

        while let Some(package_name) = queue.pop() {
            if !expanded.insert(package_name.clone()) {
                continue;
            }

            for peer in self.peer_dependencies_for(package_root, &package_name) {
                if peer_used.insert(peer.clone()) {
                    queue.push(peer);
                }
            }
        }

        peer_used
    }

    fn peer_dependencies_for(&mut self, package_root: &Path, package_name: &str) -> Vec<String> {
        let key = (package_root.to_path_buf(), package_name.to_string());
        if let Some(cached) = self.cache.get(&key) {
            return cached.clone();
        }

        let peer_dependencies: Vec<String> =
            find_installed_package_json(package_root, package_name)
                .and_then(|path| PackageJson::load(&path).ok())
                .map(|pkg| pkg.required_peer_dependency_names())
                .unwrap_or_default();

        self.cache.insert(key, peer_dependencies.clone());
        peer_dependencies
    }
}

fn find_installed_package_json(package_root: &Path, package_name: &str) -> Option<PathBuf> {
    for base in package_root.ancestors() {
        let candidate = node_modules_package_json(base, package_name);
        if candidate.is_file() {
            return Some(candidate);
        }
    }
    None
}

fn node_modules_package_json(base: &Path, package_name: &str) -> PathBuf {
    let mut path = base.join("node_modules");
    for segment in package_name.split('/') {
        path.push(segment);
    }
    path.join("package.json")
}

/// Reverse index: workspace root -> packages with ANY file under that root using
/// them (prefix-match attribution, mirroring the original `packages_used_in_workspace`).
/// Each module's matching workspace roots are pre-computed once in parallel so the
/// package_usage walk costs O(packages * avg_files_per_package) instead of
/// O(packages * files * workspaces).
fn collect_workspace_used_packages<'a>(
    graph: &'a ModuleGraph,
    workspaces: &'a [fallow_config::WorkspaceInfo],
) -> FxHashMap<&'a Path, FxHashSet<&'a str>> {
    use rayon::prelude::*;
    let module_workspaces: Vec<Vec<&Path>> = graph
        .modules
        .par_iter()
        .map(|module| {
            workspaces
                .iter()
                .filter(|ws| module.path.starts_with(&ws.root))
                .map(|ws| ws.root.as_path())
                .collect()
        })
        .collect();
    let mut by_ws: FxHashMap<&Path, FxHashSet<&str>> = workspaces
        .iter()
        .map(|ws| (ws.root.as_path(), FxHashSet::default()))
        .collect();
    for (package_name, file_ids) in &graph.package_usage {
        for id in file_ids {
            if let Some(ws_paths) = module_workspaces.get(id.0 as usize) {
                for ws_path in ws_paths {
                    by_ws
                        .entry(*ws_path)
                        .or_default()
                        .insert(package_name.as_str());
                }
            }
        }
    }
    by_ws
}

/// Collect unused dependencies for a single category (prod, dev, or optional).
///
/// Filters `dep_names` against usage data and category-specific rules, returning
/// `UnusedDependency` entries for deps that are unused.
pub fn collect_unused_for_category(
    dep_names: Vec<String>,
    category: &DepCategoryConfig,
    shared: &SharedDepSets<'_>,
    is_used: impl Fn(&str) -> bool,
    used_in_workspaces: impl Fn(&str) -> Vec<PathBuf>,
    pkg_path: &Path,
    pkg_content: Option<&str>,
) -> Vec<UnusedDependency> {
    dep_names
        .into_iter()
        .filter(|dep| !is_used(dep))
        .filter(|dep| !shared.script_used.contains(dep.as_str()))
        .filter(|dep| !category.check_implicit || !is_implicit_dependency(dep))
        .filter(|dep| {
            !category.check_known_tooling || !crate::plugins::is_known_tooling_dependency(dep)
        })
        .filter(|dep| {
            !category.check_plugin_tooling || !shared.plugin_tooling.contains(dep.as_str())
        })
        .filter(|dep| !shared.plugin_referenced.contains(dep.as_str()))
        .filter(|dep| !shared.ignore_deps.contains(dep.as_str()))
        .map(|dep| {
            let line = pkg_content.map_or(1, |c| find_dep_line_in_json(c, &dep));
            let used_in_workspaces = used_in_workspaces(&dep);
            UnusedDependency {
                package_name: dep,
                location: category.location.clone(),
                path: pkg_path.to_path_buf(),
                line,
                used_in_workspaces,
            }
        })
        .collect()
}

/// Build a reverse index from package name to workspace roots that import it.
fn collect_package_workspace_usage(
    graph: &ModuleGraph,
    workspaces: &[fallow_config::WorkspaceInfo],
) -> FxHashMap<String, Vec<PathBuf>> {
    let mut usage: FxHashMap<String, Vec<PathBuf>> = FxHashMap::default();

    for (package_name, file_ids) in &graph.package_usage {
        for id in file_ids {
            let Some(module) = graph.modules.get(id.0 as usize) else {
                continue;
            };
            let Some(ws) = workspaces
                .iter()
                .find(|workspace| module.path.starts_with(&workspace.root))
            else {
                continue;
            };
            usage
                .entry(package_name.clone())
                .or_default()
                .push(ws.root.clone());
        }
    }

    for roots in usage.values_mut() {
        roots.sort();
        roots.dedup();
    }

    usage
}

fn used_in_other_workspaces(
    package_workspace_usage: &FxHashMap<String, Vec<PathBuf>>,
    dep: &str,
    declaring_workspace_root: &Path,
) -> Vec<PathBuf> {
    package_workspace_usage
        .get(dep)
        .map_or_else(Vec::new, |roots| {
            roots
                .iter()
                .filter(|root| root.as_path() != declaring_workspace_root)
                .cloned()
                .collect()
        })
}

/// Category configs for the three dependency types.
const fn prod_category() -> DepCategoryConfig {
    DepCategoryConfig {
        location: DependencyLocation::Dependencies,
        check_implicit: true,
        check_known_tooling: false,
        check_plugin_tooling: true,
    }
}

const fn dev_category() -> DepCategoryConfig {
    DepCategoryConfig {
        location: DependencyLocation::DevDependencies,
        check_implicit: false,
        check_known_tooling: true,
        check_plugin_tooling: true,
    }
}

const fn optional_category() -> DepCategoryConfig {
    DepCategoryConfig {
        location: DependencyLocation::OptionalDependencies,
        check_implicit: true,
        check_known_tooling: false,
        check_plugin_tooling: false,
    }
}

/// Find dependencies in package.json that are never imported.
///
/// Checks both the root package.json and each workspace's package.json.
/// For workspace deps, only files within that workspace are considered when
/// determining whether a dependency is used (mirroring `find_unlisted_dependencies`).
#[deprecated(
    since = "2.76.0",
    note = "fallow_core is internal; use fallow_cli::programmatic::detect_dead_code instead. NOTE: replacement returns serde_json::Value, not typed AnalysisResults. See docs/fallow-core-migration.md and ADR-008."
)]
pub fn find_unused_dependencies(
    graph: &ModuleGraph,
    pkg: &PackageJson,
    config: &ResolvedConfig,
    plugin_result: Option<&crate::plugins::AggregatedPluginResult>,
    workspaces: &[fallow_config::WorkspaceInfo],
) -> (
    Vec<UnusedDependency>,
    Vec<UnusedDependency>,
    Vec<UnusedDependency>,
) {
    let plugin_referenced: FxHashSet<&str> = plugin_result
        .map(|pr| {
            pr.referenced_dependencies
                .iter()
                .map(String::as_str)
                .collect()
        })
        .unwrap_or_default();

    let plugin_tooling: FxHashSet<&str> = plugin_result
        .map(|pr| pr.tooling_dependencies.iter().map(String::as_str).collect())
        .unwrap_or_default();

    let script_used: FxHashSet<&str> = plugin_result
        .map(|pr| pr.script_used_packages.iter().map(String::as_str).collect())
        .unwrap_or_default();

    let ignore_deps: FxHashSet<&str> = config
        .ignore_dependencies
        .iter()
        .map(String::as_str)
        .collect();

    let used_packages: FxHashSet<&str> = graph.package_usage.keys().map(String::as_str).collect();
    let package_workspace_usage = collect_package_workspace_usage(graph, workspaces);
    let workspace_used_packages = collect_workspace_used_packages(graph, workspaces);
    let root_peer_used = PeerDependencyResolver::new()
        .peer_dependency_closure(&config.root, used_packages.iter().copied());

    let root_pkg_path = config.root.join("package.json");
    let root_pkg_content = read_pkg_json_content(&root_pkg_path);

    let shared = SharedDepSets {
        plugin_referenced: &plugin_referenced,
        plugin_tooling: &plugin_tooling,
        script_used: &script_used,
        ignore_deps: &ignore_deps,
    };

    let is_used_globally = |dep: &str| used_packages.contains(dep) || root_peer_used.contains(dep);
    let no_workspace_context = |_dep: &str| Vec::new();

    let mut unused_deps = collect_unused_for_category(
        pkg.production_dependency_names(),
        &prod_category(),
        &shared,
        is_used_globally,
        no_workspace_context,
        &root_pkg_path,
        root_pkg_content.as_deref(),
    );

    let mut unused_dev_deps = collect_unused_for_category(
        pkg.dev_dependency_names(),
        &dev_category(),
        &shared,
        is_used_globally,
        no_workspace_context,
        &root_pkg_path,
        root_pkg_content.as_deref(),
    );

    let mut unused_optional_deps = collect_unused_for_category(
        pkg.optional_dependency_names(),
        &optional_category(),
        &shared,
        is_used_globally,
        no_workspace_context,
        &root_pkg_path,
        root_pkg_content.as_deref(),
    );

    let root_flagged: FxHashSet<String> = unused_deps
        .iter()
        .chain(unused_dev_deps.iter())
        .chain(unused_optional_deps.iter())
        .map(|d| d.package_name.clone())
        .collect();

    use rayon::prelude::*;
    let workspace_findings: Vec<(
        Vec<UnusedDependency>,
        Vec<UnusedDependency>,
        Vec<UnusedDependency>,
    )> = workspaces
        .par_iter()
        .map(|ws| {
            let ws_pkg_path = ws.root.join("package.json");
            if is_package_json_ignored(&ws_pkg_path, config) {
                return (Vec::new(), Vec::new(), Vec::new());
            }
            let Some(ws_pkg_content) = std::fs::read_to_string(&ws_pkg_path).ok() else {
                return (Vec::new(), Vec::new(), Vec::new());
            };
            let Ok(ws_pkg) = serde_json::from_str::<PackageJson>(&ws_pkg_content) else {
                return (Vec::new(), Vec::new(), Vec::new());
            };

            let ws_root = ws.root.as_path();
            let ws_used_packages: FxHashSet<&str> = workspace_used_packages
                .get(&ws_root)
                .cloned()
                .unwrap_or_default();
            let ws_peer_used = PeerDependencyResolver::new()
                .peer_dependency_closure(ws_root, ws_used_packages.iter().copied());
            let is_used_in_workspace = |dep: &str| -> bool {
                root_flagged.contains(dep)
                    || ws_peer_used.contains(dep)
                    || package_workspace_usage
                        .get(dep)
                        .is_some_and(|roots| roots.iter().any(|root| root == ws_root))
            };
            let used_in_workspaces =
                |dep: &str| used_in_other_workspaces(&package_workspace_usage, dep, ws_root);

            let prod = collect_unused_for_category(
                ws_pkg.production_dependency_names(),
                &prod_category(),
                &shared,
                is_used_in_workspace,
                used_in_workspaces,
                &ws_pkg_path,
                Some(&ws_pkg_content),
            );

            let dev = collect_unused_for_category(
                ws_pkg.dev_dependency_names(),
                &dev_category(),
                &shared,
                is_used_in_workspace,
                used_in_workspaces,
                &ws_pkg_path,
                Some(&ws_pkg_content),
            );

            let optional = collect_unused_for_category(
                ws_pkg.optional_dependency_names(),
                &optional_category(),
                &shared,
                is_used_in_workspace,
                used_in_workspaces,
                &ws_pkg_path,
                Some(&ws_pkg_content),
            );

            (prod, dev, optional)
        })
        .collect();

    for (prod, dev, optional) in workspace_findings {
        unused_deps.extend(prod);
        unused_dev_deps.extend(dev);
        unused_optional_deps.extend(optional);
    }

    (unused_deps, unused_dev_deps, unused_optional_deps)
}

/// Check if a dependency should be skipped during unused dependency analysis.
///
/// Shared guard conditions for both production and dev dependency loops:
/// already flagged from root, used in scripts, referenced by plugins, in ignore list,
/// is a workspace package, or used by files in the workspace.
///
/// Retained for test coverage of the individual guard logic.
#[cfg(test)]
fn should_skip_dependency(
    dep: &str,
    root_flagged: &FxHashSet<String>,
    script_used: &FxHashSet<&str>,
    plugin_referenced: &FxHashSet<&str>,
    ignore_deps: &FxHashSet<&str>,
    workspace_names: &FxHashSet<&str>,
    is_used_in_workspace: impl Fn(&str) -> bool,
) -> bool {
    root_flagged.contains(dep)
        || script_used.contains(dep)
        || plugin_referenced.contains(dep)
        || ignore_deps.contains(dep)
        || workspace_names.contains(dep)
        || is_used_in_workspace(dep)
}

/// Find production dependencies that are only imported via type-only imports.
///
/// In production mode, `import type { Foo } from 'pkg'` is erased at compile time,
/// meaning the dependency is not needed at runtime. Such dependencies should be
/// moved to devDependencies.
pub fn find_type_only_dependencies(
    graph: &ModuleGraph,
    pkg: &PackageJson,
    config: &ResolvedConfig,
    workspaces: &[fallow_config::WorkspaceInfo],
) -> Vec<TypeOnlyDependency> {
    let root_pkg_path = config.root.join("package.json");
    let root_pkg_content = read_pkg_json_content(&root_pkg_path);
    let workspace_names: FxHashSet<&str> = workspaces.iter().map(|ws| ws.name.as_str()).collect();

    let mut type_only_deps = Vec::new();

    for dep in pkg.production_dependency_names() {
        if workspace_names.contains(dep.as_str()) {
            continue;
        }
        if config.ignore_dependencies.iter().any(|d| d == &dep) {
            continue;
        }

        let has_any_usage = graph.package_usage.contains_key(dep.as_str());
        let has_type_only_usage = graph.type_only_package_usage.contains_key(dep.as_str());

        if !has_any_usage {
            continue;
        }

        let total_count = graph.package_usage.get(dep.as_str()).map_or(0, Vec::len);
        let type_only_count = graph
            .type_only_package_usage
            .get(dep.as_str())
            .map_or(0, Vec::len);

        if has_type_only_usage && type_only_count == total_count {
            let line = root_pkg_content
                .as_deref()
                .map_or(1, |c| find_dep_line_in_json(c, &dep));
            type_only_deps.push(TypeOnlyDependency {
                package_name: dep,
                path: root_pkg_path.clone(),
                line,
            });
        }
    }

    type_only_deps
}

/// Find production dependencies that are only imported by test/dev files.
///
/// When NOT in production mode (where test files are still discovered), a dep
/// that appears exclusively in test/story/config files should be a devDependency.
pub fn find_test_only_dependencies(
    graph: &ModuleGraph,
    pkg: &PackageJson,
    config: &ResolvedConfig,
    workspaces: &[fallow_config::WorkspaceInfo],
) -> Vec<TestOnlyDependency> {
    let test_globs = {
        let mut builder = globset::GlobSetBuilder::new();
        for pattern in crate::discover::PRODUCTION_EXCLUDE_PATTERNS {
            if let Ok(glob) = globset::GlobBuilder::new(pattern)
                .literal_separator(true)
                .build()
            {
                builder.add(glob);
            }
        }
        match builder.build() {
            Ok(set) => set,
            Err(_) => return Vec::new(),
        }
    };

    let root_pkg_path = config.root.join("package.json");
    let root_pkg_content = read_pkg_json_content(&root_pkg_path);
    let workspace_names: FxHashSet<&str> = workspaces.iter().map(|ws| ws.name.as_str()).collect();
    let ignore_deps: FxHashSet<&str> = config
        .ignore_dependencies
        .iter()
        .map(String::as_str)
        .collect();

    let mut test_only_deps = Vec::new();

    for dep in pkg.production_dependency_names() {
        if workspace_names.contains(dep.as_str()) {
            continue;
        }
        if ignore_deps.contains(dep.as_str()) {
            continue;
        }

        let Some(file_ids) = graph.package_usage.get(dep.as_str()) else {
            continue;
        };

        let total_count = file_ids.len();
        let type_only_count = graph
            .type_only_package_usage
            .get(dep.as_str())
            .map_or(0, Vec::len);
        if type_only_count == total_count {
            continue;
        }

        let all_test_only = file_ids.iter().all(|id| {
            graph.modules.get(id.0 as usize).is_some_and(|module| {
                let relative = module
                    .path
                    .strip_prefix(&config.root)
                    .unwrap_or(&module.path);
                test_globs.is_match(relative) || is_config_file(&module.path)
            })
        });

        if all_test_only {
            let line = root_pkg_content
                .as_deref()
                .map_or(1, |c| find_dep_line_in_json(c, &dep));
            test_only_deps.push(TestOnlyDependency {
                package_name: dep,
                path: root_pkg_path.clone(),
                line,
            });
        }
    }

    test_only_deps
}

/// Check whether a package is listed in root deps or in the workspace that owns `file_path`.
pub fn is_package_listed_for_file(
    file_path: &Path,
    package_name: &str,
    root_deps: &FxHashSet<String>,
    ws_dep_map: &[(PathBuf, FxHashSet<String>)],
) -> bool {
    if let Some(ws_deps) = owning_workspace_deps(file_path, ws_dep_map) {
        return ws_deps.contains(package_name);
    }

    root_deps.contains(package_name)
}

fn owning_workspace_deps<'a>(
    file_path: &Path,
    ws_dep_map: &'a [(PathBuf, FxHashSet<String>)],
) -> Option<&'a FxHashSet<String>> {
    ws_dep_map
        .iter()
        .filter(|(ws_root, _)| file_path.starts_with(ws_root))
        .max_by_key(|(ws_root, _)| ws_root.components().count())
        .map(|(_, ws_deps)| ws_deps)
}

/// Check if a corresponding `@types/<package>` is listed in dependencies.
///
/// When `@types/X` is installed but `X` itself is not, the dependency is used for types
/// only (e.g., `@types/geojson` for `import { Feature } from 'geojson'`). TypeScript
/// resolves types from `@types/X` automatically, and the import is erased at compile time
/// regardless of whether it uses the `import type` syntax.
///
/// For scoped packages like `@scope/pkg`, the DefinitelyTyped convention is `@types/scope__pkg`.
fn types_package_name(package_name: &str) -> String {
    package_name.strip_prefix('@').map_or_else(
        || format!("@types/{package_name}"),
        |scoped| format!("@types/{}", scoped.replacen('/', "__", 1)),
    )
}

fn has_types_package_for_file(
    file_path: &Path,
    package_name: &str,
    root_deps: &FxHashSet<String>,
    ws_dep_map: &[(PathBuf, FxHashSet<String>)],
) -> bool {
    let types_name = types_package_name(package_name);
    is_package_listed_for_file(file_path, &types_name, root_deps, ws_dep_map)
}

/// Look up the import location (line, col) for a given package in a given file.
///
/// Falls back to `(1, 0)` when no source edge span is found.
#[cfg(test)]
pub fn find_import_location(
    import_spans_by_file: &FxHashMap<FileId, Vec<(&str, &str, u32)>>,
    line_offsets_by_file: &LineOffsetsMap<'_>,
    file_id: FileId,
    package_name: &str,
) -> (u32, u32) {
    import_spans_by_file
        .get(&file_id)
        .and_then(|spans| {
            spans
                .iter()
                .find(|(name, source, _)| *name == package_name && !is_builtin_module(source))
                .or_else(|| spans.iter().find(|(name, _, _)| *name == package_name))
                .map(|(_, _, span_start)| {
                    byte_offset_to_line_col(line_offsets_by_file, file_id, *span_start)
                })
        })
        .unwrap_or((1, 0))
}

fn relative_module_path(module_path: &Path, root: &Path) -> String {
    module_path
        .strip_prefix(root)
        .unwrap_or(module_path)
        .to_string_lossy()
        .into_owned()
}

struct CompiledProvidedDependencyRule<'a> {
    rule: &'a ProvidedDependencyRule,
    path_matcher: CompiledPathRule,
}

fn compile_provided_dependency_rules(
    rules: &[ProvidedDependencyRule],
) -> Vec<CompiledProvidedDependencyRule<'_>> {
    rules
        .iter()
        .filter_map(|rule| {
            CompiledPathRule::for_used_export_rule(&rule.path, "provided dependency")
                .map(|path_matcher| CompiledProvidedDependencyRule { rule, path_matcher })
        })
        .collect()
}

fn import_is_provided(
    rules: &[CompiledProvidedDependencyRule<'_>],
    relative_path: &str,
    source_specifier: &str,
) -> bool {
    rules.iter().any(|rule| {
        rule.path_matcher.matches(relative_path) && rule.rule.covers_specifier(source_specifier)
    })
}

fn package_has_file_scoped_provider(rules: &[ProvidedDependencyRule], package_name: &str) -> bool {
    rules
        .iter()
        .any(|rule| rule.may_cover_package(package_name))
}

fn find_unprovided_import_location(
    import_spans_by_file: &FxHashMap<FileId, Vec<(&str, &str, u32)>>,
    line_offsets_by_file: &LineOffsetsMap<'_>,
    provided_rules: &[CompiledProvidedDependencyRule<'_>],
    relative_path: &str,
    file_id: FileId,
    package_name: &str,
) -> Option<(u32, u32)> {
    import_spans_by_file.get(&file_id).and_then(|spans| {
        spans
            .iter()
            .filter(|(name, _, _)| *name == package_name)
            .find(|(_, source, _)| {
                !is_builtin_module(source)
                    && !import_is_provided(provided_rules, relative_path, source)
            })
            .or_else(|| {
                spans.iter().find(|(name, source, _)| {
                    *name == package_name
                        && !import_is_provided(provided_rules, relative_path, source)
                })
            })
            .map(|(_, _, span_start)| {
                byte_offset_to_line_col(line_offsets_by_file, file_id, *span_start)
            })
    })
}

fn package_imports_are_all_builtin(
    import_spans_by_file: &FxHashMap<FileId, Vec<(&str, &str, u32)>>,
    file_id: FileId,
    package_name: &str,
) -> bool {
    let Some(imports) = import_spans_by_file.get(&file_id) else {
        return false;
    };

    let mut saw_package = false;
    for (name, source, _) in imports {
        if *name == package_name {
            saw_package = true;
            if !is_builtin_module(source) {
                return false;
            }
        }
    }

    saw_package
}

/// A package whose every import in this file used the Deno `npm:` scheme is
/// self-declaring: Supabase Edge Functions and Deno deliberately inline the
/// dependency in the specifier instead of listing it in package.json, so it
/// must not surface as an unlisted dependency. Mirrors the per-file `bun:`
/// carve-out (`package_imports_are_all_builtin`) and stays conservative: a
/// package also imported via a bare specifier (e.g. `import 'foo'` in a Node
/// file) is NOT all-`npm:`, so the genuine missing-dependency report survives.
/// The resolver normalizes `npm:<pkg>` to its package name for usage crediting
/// but leaves the original `npm:` prefix on `ImportInfo.source`, which is the
/// string compared here. See issue #624.
fn package_imports_are_all_npm_scheme(
    import_spans_by_file: &FxHashMap<FileId, Vec<(&str, &str, u32)>>,
    file_id: FileId,
    package_name: &str,
) -> bool {
    let Some(imports) = import_spans_by_file.get(&file_id) else {
        return false;
    };

    let mut saw_package = false;
    for (name, source, _) in imports {
        if *name == package_name {
            saw_package = true;
            if !source.starts_with("npm:") {
                return false;
            }
        }
    }

    saw_package
}

/// Find dependencies used in imports but not listed in package.json.
pub fn find_unlisted_dependencies(
    graph: &ModuleGraph,
    pkg: &PackageJson,
    config: &ResolvedConfig,
    workspaces: &[fallow_config::WorkspaceInfo],
    plugin_result: Option<&crate::plugins::AggregatedPluginResult>,
    resolved_modules: &[ResolvedModule],
    line_offsets_by_file: &LineOffsetsMap<'_>,
) -> Vec<UnlistedDependency> {
    let mut all_deps: FxHashSet<String> = pkg.all_dependency_names().into_iter().collect();
    if let Some(root_name) = &pkg.name {
        all_deps.insert(root_name.clone());
    }

    let mut ws_dep_map: Vec<(PathBuf, FxHashSet<String>)> = Vec::new();

    for ws in workspaces {
        let ws_pkg_path = ws.root.join("package.json");
        if is_package_json_ignored(&ws_pkg_path, config) {
            continue;
        }
        if let Ok(ws_pkg) = PackageJson::load(&ws_pkg_path) {
            let mut ws_deps: FxHashSet<String> =
                ws_pkg.all_dependency_names().into_iter().collect();
            ws_deps.insert(ws.name.clone());
            ws_dep_map.push((ws.root.clone(), ws_deps));
        }
    }

    let virtual_prefixes: Vec<&str> = plugin_result
        .map(|pr| {
            pr.virtual_module_prefixes
                .iter()
                .map(String::as_str)
                .collect()
        })
        .unwrap_or_default();

    let virtual_suffixes: Vec<&str> = plugin_result
        .map(|pr| {
            pr.virtual_package_suffixes
                .iter()
                .map(String::as_str)
                .collect()
        })
        .unwrap_or_default();

    let plugin_tooling: FxHashSet<&str> = plugin_result
        .map(|pr| pr.tooling_dependencies.iter().map(String::as_str).collect())
        .unwrap_or_default();
    let provided_dependency_rules: &[ProvidedDependencyRule] =
        plugin_result.map_or(&[], |pr| pr.provided_dependencies.as_slice());
    let compiled_provided_dependency_rules =
        compile_provided_dependency_rules(provided_dependency_rules);

    let mut import_spans_by_file: FxHashMap<FileId, Vec<(&str, &str, u32)>> = FxHashMap::default();
    for rm in resolved_modules {
        for edge in rm.all_resolved_source_edges() {
            if let Some(name) = edge.target().package_usage_name() {
                import_spans_by_file.entry(rm.file_id).or_default().push((
                    name,
                    edge.source_specifier(),
                    edge.span().start,
                ));
            }
        }
    }

    let ignore_deps: FxHashSet<&str> = config
        .ignore_dependencies
        .iter()
        .map(String::as_str)
        .collect();

    let mut unlisted: FxHashMap<String, Vec<ImportSite>> = FxHashMap::default();

    for (package_name, file_ids) in &graph.package_usage {
        if (package_name != "bun" && is_builtin_module(package_name)) || is_path_alias(package_name)
        {
            continue;
        }
        if is_virtual_module(package_name) {
            continue;
        }
        if ignore_deps.contains(package_name.as_str()) {
            continue;
        }
        if plugin_tooling.contains(package_name.as_str())
            && !package_has_file_scoped_provider(provided_dependency_rules, package_name)
        {
            continue;
        }
        if virtual_prefixes
            .iter()
            .any(|prefix| matches_virtual_prefix(prefix, package_name))
        {
            continue;
        }
        if virtual_suffixes
            .iter()
            .any(|suffix| package_name.ends_with(suffix))
        {
            continue;
        }
        let mut unlisted_sites: Vec<ImportSite> = Vec::new();
        for id in file_ids {
            let Some(module) = graph.modules.get(id.0 as usize) else {
                continue;
            };
            if package_name == "bun"
                && package_imports_are_all_builtin(&import_spans_by_file, *id, package_name)
            {
                continue;
            }
            if package_imports_are_all_npm_scheme(&import_spans_by_file, *id, package_name) {
                continue;
            }
            if is_package_listed_for_file(&module.path, package_name, &all_deps, &ws_dep_map) {
                continue;
            }
            if has_types_package_for_file(&module.path, package_name, &all_deps, &ws_dep_map) {
                continue;
            }
            let relative_path = relative_module_path(&module.path, &config.root);
            let Some((line, col)) = find_unprovided_import_location(
                &import_spans_by_file,
                line_offsets_by_file,
                &compiled_provided_dependency_rules,
                &relative_path,
                *id,
                package_name,
            ) else {
                continue;
            };
            unlisted_sites.push(ImportSite {
                path: module.path.clone(),
                line,
                col,
            });
        }

        if !unlisted_sites.is_empty() {
            unlisted_sites.sort_by(|a, b| a.path.cmp(&b.path).then(a.line.cmp(&b.line)));
            unlisted_sites.dedup_by(|a, b| a.path == b.path);
            unlisted.insert(package_name.clone(), unlisted_sites);
        }
    }

    unlisted
        .into_iter()
        .map(|(name, sites)| UnlistedDependency {
            package_name: name,
            imported_from: sites,
        })
        .collect()
}

/// Find imports that could not be resolved.
pub fn find_unresolved_imports(
    resolved_modules: &[ResolvedModule],
    config: &ResolvedConfig,
    suppressions: &SuppressionContext<'_>,
    virtual_prefixes: &[&str],
    generated_patterns: &[&str],
    generated_type_prefixes: &[&str],
    line_offsets_by_file: &LineOffsetsMap<'_>,
) -> Vec<UnresolvedImport> {
    let mut unresolved = Vec::new();

    for module in resolved_modules {
        for edge in module.all_resolved_source_edges() {
            if let crate::resolve::ResolveResult::Unresolvable(spec) = edge.target() {
                if is_builtin_module(spec) {
                    continue;
                }
                if is_virtual_module(spec) {
                    continue;
                }
                if virtual_prefixes
                    .iter()
                    .any(|prefix| matches_virtual_prefix(prefix, spec))
                {
                    continue;
                }
                if !generated_patterns.is_empty() {
                    let bare = spec
                        .strip_suffix(".js")
                        .or_else(|| spec.strip_suffix(".ts"))
                        .unwrap_or(spec);
                    if generated_patterns.iter().any(|pat| bare.ends_with(pat)) {
                        continue;
                    }
                }
                if edge.is_type_only()
                    && generated_type_prefixes
                        .iter()
                        .any(|prefix| spec.starts_with(prefix))
                {
                    continue;
                }
                if config
                    .ignore_unresolved_imports
                    .iter()
                    .any(|matcher| matcher.is_match(spec))
                {
                    continue;
                }
                let (line, col) = byte_offset_to_line_col(
                    line_offsets_by_file,
                    module.file_id,
                    edge.span().start,
                );

                let source_span = edge.source_span();
                let specifier_col = if source_span.end > source_span.start {
                    let (_, sc) = byte_offset_to_line_col(
                        line_offsets_by_file,
                        module.file_id,
                        source_span.start,
                    );
                    sc
                } else {
                    col
                };

                if suppressions.is_suppressed(module.file_id, line, IssueKind::UnresolvedImport) {
                    continue;
                }

                unresolved.push(UnresolvedImport {
                    path: module.path.clone(),
                    specifier: spec.clone(),
                    line,
                    col,
                    specifier_col,
                });
            }
        }
    }

    unresolved
}

#[cfg(test)]
#[expect(
    deprecated,
    reason = "ADR-008 keeps direct detector unit tests while the public warning targets external callers"
)]
#[path = "unused_deps_tests/mod.rs"]
mod tests;
