fallow_core/

trace.rs

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

use fallow_types::serde_path;
use rustc_hash::FxHashSet;
use serde::Serialize;

use crate::duplicates::{
    CloneFingerprintSet, CloneGroup, CloneInstance, DuplicationReport, RefactoringSuggestion,
    dominant_identifier, group_refactoring_suggestion,
};
use crate::graph::{ModuleGraph, ReferenceKind};

/// Match a user-provided file path against a module's actual path.
///
/// Handles monorepo scenarios where module paths may be canonicalized
/// (symlinks resolved) while user-provided paths are not.
fn path_matches(module_path: &Path, root: &Path, user_path: &str) -> bool {
    let user_path_norm = user_path.replace('\\', "/");
    let rel = module_path.strip_prefix(root).unwrap_or(module_path);
    let rel_str = rel.to_string_lossy().replace('\\', "/");
    let module_str = module_path.to_string_lossy().replace('\\', "/");
    if rel_str == user_path_norm || module_str == user_path_norm {
        return true;
    }
    if dunce::canonicalize(root).is_ok_and(|canonical_root| {
        module_path
            .strip_prefix(&canonical_root)
            .is_ok_and(|rel| rel.to_string_lossy().replace('\\', "/") == user_path_norm)
    }) {
        return true;
    }
    module_str.ends_with(&format!("/{user_path_norm}"))
}

/// Result of tracing an export: why is it considered used or unused?
#[derive(Debug, Serialize)]
pub struct ExportTrace {
    /// The file containing the export.
    #[serde(serialize_with = "serde_path::serialize")]
    pub file: PathBuf,
    /// The export name being traced.
    pub export_name: String,
    /// Whether the file is reachable from an entry point.
    pub file_reachable: bool,
    /// Whether the file is an entry point.
    pub is_entry_point: bool,
    /// Whether the export is considered used.
    pub is_used: bool,
    /// Files that reference this export directly.
    pub direct_references: Vec<ExportReference>,
    /// Re-export chains that pass through this export.
    pub re_export_chains: Vec<ReExportChain>,
    /// Reason summary.
    pub reason: String,
}

/// A direct reference to an export.
#[derive(Debug, Serialize)]
pub struct ExportReference {
    #[serde(serialize_with = "serde_path::serialize")]
    pub from_file: PathBuf,
    pub kind: String,
}

/// A re-export chain showing how an export is propagated.
#[derive(Debug, Serialize)]
pub struct ReExportChain {
    /// The barrel file that re-exports this symbol.
    #[serde(serialize_with = "serde_path::serialize")]
    pub barrel_file: PathBuf,
    /// The name it's re-exported as.
    pub exported_as: String,
    /// Number of references on the barrel's re-exported symbol.
    pub reference_count: usize,
}

/// Result of tracing all edges for a file.
#[derive(Debug, Serialize)]
pub struct FileTrace {
    /// The traced file.
    #[serde(serialize_with = "serde_path::serialize")]
    pub file: PathBuf,
    /// Whether this file is reachable from entry points.
    pub is_reachable: bool,
    /// Whether this file is an entry point.
    pub is_entry_point: bool,
    /// Exports declared by this file.
    pub exports: Vec<TracedExport>,
    /// Files that this file imports from.
    #[serde(serialize_with = "serde_path::serialize_vec")]
    pub imports_from: Vec<PathBuf>,
    /// Files that import from this file.
    #[serde(serialize_with = "serde_path::serialize_vec")]
    pub imported_by: Vec<PathBuf>,
    /// Re-exports declared by this file.
    pub re_exports: Vec<TracedReExport>,
}

/// An export with its usage info.
#[derive(Debug, Serialize)]
pub struct TracedExport {
    pub name: String,
    pub is_type_only: bool,
    pub reference_count: usize,
    pub referenced_by: Vec<ExportReference>,
}

/// A re-export with source info.
#[derive(Debug, Serialize)]
pub struct TracedReExport {
    #[serde(serialize_with = "serde_path::serialize")]
    pub source_file: PathBuf,
    pub imported_name: String,
    pub exported_name: String,
}

/// Result of tracing a dependency: where is it used?
#[derive(Debug, Serialize)]
pub struct DependencyTrace {
    /// The dependency name being traced.
    pub package_name: String,
    /// Files that import this dependency.
    #[serde(serialize_with = "serde_path::serialize_vec")]
    pub imported_by: Vec<PathBuf>,
    /// Files that import this dependency with type-only imports.
    #[serde(serialize_with = "serde_path::serialize_vec")]
    pub type_only_imported_by: Vec<PathBuf>,
    /// Whether the dependency is invoked from package.json scripts or CI configs
    /// (e.g., `microbundle build`, `vitest run` in `scripts`, or binary names in
    /// `.github/workflows/*.yml` / `.gitlab-ci.yml`). Mirrors how the unused-deps
    /// detector classifies tooling usage so trace output stays consistent with it.
    pub used_in_scripts: bool,
    /// Whether the dependency is used at all (imports OR script/CI invocations).
    pub is_used: bool,
    /// Total import count.
    pub import_count: usize,
}

/// Pipeline performance timings.
#[derive(Debug, Clone, Serialize)]
pub struct PipelineTimings {
    pub discover_files_ms: f64,
    pub file_count: usize,
    pub workspaces_ms: f64,
    pub workspace_count: usize,
    pub plugins_ms: f64,
    pub script_analysis_ms: f64,
    pub parse_extract_ms: f64,
    /// Summed wall-clock time of the actual AST parses across all rayon
    /// workers (the parse stage's CPU cost). `parse_extract_ms` is the
    /// stage's wall-clock time; this is the work done in parallel within it.
    /// Observational and non-deterministic (varies run to run); do not assert
    /// against it.
    pub parse_cpu_ms: f64,
    pub module_count: usize,
    /// Number of files whose parse results were loaded from cache (skipped parsing).
    pub cache_hits: usize,
    /// Number of files that required a full parse (new or changed content).
    pub cache_misses: usize,
    pub cache_update_ms: f64,
    pub entry_points_ms: f64,
    pub entry_point_count: usize,
    pub resolve_imports_ms: f64,
    pub build_graph_ms: f64,
    pub analyze_ms: f64,
    #[serde(skip_serializing_if = "Option::is_none")]
    pub duplication_ms: Option<f64>,
    pub total_ms: f64,
}

/// Map a reference's `from_file` id to a root-relative [`ExportReference`].
fn reference_to_export_reference(
    graph: &ModuleGraph,
    root: &Path,
    r: &crate::graph::SymbolReference,
) -> ExportReference {
    let from_path = graph.modules.get(r.from_file.0 as usize).map_or_else(
        || PathBuf::from(format!("<unknown:{}>", r.from_file.0)),
        |m| m.path.strip_prefix(root).unwrap_or(&m.path).to_path_buf(),
    );
    ExportReference {
        from_file: from_path,
        kind: format_reference_kind(r.kind),
    }
}

/// Collect every re-export chain across the graph that re-exports `export_name`
/// from the module identified by `target_file_id`.
fn collect_re_export_chains(
    graph: &ModuleGraph,
    root: &Path,
    target_file_id: crate::discover::FileId,
    export_name: &str,
) -> Vec<ReExportChain> {
    graph
        .modules
        .iter()
        .flat_map(|m| {
            m.re_exports
                .iter()
                .filter(move |re| {
                    re.source_file == target_file_id
                        && (re.imported_name == export_name || re.imported_name == "*")
                })
                .map(move |re| {
                    let barrel_export = m.exports.iter().find(|e| {
                        if re.exported_name == "*" {
                            e.name.to_string() == export_name
                        } else {
                            e.name.to_string() == re.exported_name
                        }
                    });
                    ReExportChain {
                        barrel_file: m.path.strip_prefix(root).unwrap_or(&m.path).to_path_buf(),
                        exported_as: re.exported_name.clone(),
                        reference_count: barrel_export.map_or(0, |e| e.references.len()),
                    }
                })
        })
        .collect()
}

/// Build the human-readable reason string explaining an export's used/unused state.
fn export_trace_reason(
    module: &crate::graph::ModuleNode,
    reference_count: usize,
    is_used: bool,
    re_export_chains: &[ReExportChain],
) -> String {
    if !module.is_reachable() {
        "File is unreachable from any entry point".to_string()
    } else if is_used {
        format!(
            "Used by {} file(s){}",
            reference_count,
            if re_export_chains.is_empty() {
                String::new()
            } else {
                format!(", re-exported through {} barrel(s)", re_export_chains.len())
            }
        )
    } else if module.is_entry_point() {
        "No internal references, but file is an entry point (export is externally accessible)"
            .to_string()
    } else if !re_export_chains.is_empty() {
        format!(
            "Re-exported through {} barrel(s) but no consumer imports it through the barrel",
            re_export_chains.len()
        )
    } else {
        "No references found, export is unused".to_string()
    }
}

/// Trace why an export is considered used or unused.
#[must_use]
pub fn trace_export(
    graph: &ModuleGraph,
    root: &Path,
    file_path: &str,
    export_name: &str,
) -> Option<ExportTrace> {
    let module = graph
        .modules
        .iter()
        .find(|m| path_matches(&m.path, root, file_path))?;

    let export = module.exports.iter().find(|e| {
        let name_str = e.name.to_string();
        name_str == export_name || (export_name == "default" && name_str == "default")
    })?;

    let direct_references: Vec<ExportReference> = export
        .references
        .iter()
        .map(|r| reference_to_export_reference(graph, root, r))
        .collect();

    let re_export_chains = collect_re_export_chains(graph, root, module.file_id, export_name);

    let is_used = !export.references.is_empty();
    let reason = export_trace_reason(module, export.references.len(), is_used, &re_export_chains);

    Some(ExportTrace {
        file: module
            .path
            .strip_prefix(root)
            .unwrap_or(&module.path)
            .to_path_buf(),
        export_name: export_name.to_string(),
        file_reachable: module.is_reachable(),
        is_entry_point: module.is_entry_point(),
        is_used,
        direct_references,
        re_export_chains,
        reason,
    })
}

/// Map a module's exports to [`TracedExport`] entries with relativized references.
fn traced_exports(
    graph: &ModuleGraph,
    root: &Path,
    module: &crate::graph::ModuleNode,
) -> Vec<TracedExport> {
    module
        .exports
        .iter()
        .map(|e| TracedExport {
            name: e.name.to_string(),
            is_type_only: e.is_type_only,
            reference_count: e.references.len(),
            referenced_by: e
                .references
                .iter()
                .map(|r| reference_to_export_reference(graph, root, r))
                .collect(),
        })
        .collect()
}

/// Collect the root-relative paths a file imports from (forward graph edges).
fn traced_imports_from(
    graph: &ModuleGraph,
    root: &Path,
    module: &crate::graph::ModuleNode,
) -> Vec<PathBuf> {
    graph
        .edges_for(module.file_id)
        .iter()
        .filter_map(|target_id| {
            graph
                .modules
                .get(target_id.0 as usize)
                .map(|m| m.path.strip_prefix(root).unwrap_or(&m.path).to_path_buf())
        })
        .collect()
}

/// Collect the root-relative paths that import a file (reverse graph edges).
fn traced_imported_by(
    graph: &ModuleGraph,
    root: &Path,
    module: &crate::graph::ModuleNode,
) -> Vec<PathBuf> {
    graph
        .reverse_deps
        .get(module.file_id.0 as usize)
        .map(|deps| {
            deps.iter()
                .filter_map(|fid| {
                    graph
                        .modules
                        .get(fid.0 as usize)
                        .map(|m| m.path.strip_prefix(root).unwrap_or(&m.path).to_path_buf())
                })
                .collect()
        })
        .unwrap_or_default()
}

/// Map a module's re-exports to [`TracedReExport`] entries with relativized source paths.
fn traced_re_exports(
    graph: &ModuleGraph,
    root: &Path,
    module: &crate::graph::ModuleNode,
) -> Vec<TracedReExport> {
    module
        .re_exports
        .iter()
        .map(|re| {
            let source_path = graph.modules.get(re.source_file.0 as usize).map_or_else(
                || PathBuf::from(format!("<unknown:{}>", re.source_file.0)),
                |m| m.path.strip_prefix(root).unwrap_or(&m.path).to_path_buf(),
            );
            TracedReExport {
                source_file: source_path,
                imported_name: re.imported_name.clone(),
                exported_name: re.exported_name.clone(),
            }
        })
        .collect()
}

/// Trace all edges for a file.
#[must_use]
pub fn trace_file(graph: &ModuleGraph, root: &Path, file_path: &str) -> Option<FileTrace> {
    let module = graph
        .modules
        .iter()
        .find(|m| path_matches(&m.path, root, file_path))?;

    Some(FileTrace {
        file: module
            .path
            .strip_prefix(root)
            .unwrap_or(&module.path)
            .to_path_buf(),
        is_reachable: module.is_reachable(),
        is_entry_point: module.is_entry_point(),
        exports: traced_exports(graph, root, module),
        imports_from: traced_imports_from(graph, root, module),
        imported_by: traced_imported_by(graph, root, module),
        re_exports: traced_re_exports(graph, root, module),
    })
}

/// Trace where a dependency is used.
///
/// `script_used_packages` carries the package names recorded as binary invocations
/// in package.json scripts (`build: microbundle ...`) and CI configs
/// (`.github/workflows/*.yml`, `.gitlab-ci.yml`). The same set the unused-deps
/// detector consults; passing it in lets the trace output match the detector's
/// view of "used" instead of reporting `is_used=false` for tools invoked only
/// through scripts.
#[expect(
    clippy::implicit_hasher,
    reason = "fallow standardizes on FxHashSet across the workspace"
)]
#[must_use]
pub fn trace_dependency(
    graph: &ModuleGraph,
    root: &Path,
    package_name: &str,
    script_used_packages: &FxHashSet<String>,
) -> DependencyTrace {
    let imported_by: Vec<PathBuf> = graph
        .package_usage
        .get(package_name)
        .map(|ids| {
            ids.iter()
                .filter_map(|fid| {
                    graph
                        .modules
                        .get(fid.0 as usize)
                        .map(|m| m.path.strip_prefix(root).unwrap_or(&m.path).to_path_buf())
                })
                .collect()
        })
        .unwrap_or_default();

    let type_only_imported_by: Vec<PathBuf> = graph
        .type_only_package_usage
        .get(package_name)
        .map(|ids| {
            ids.iter()
                .filter_map(|fid| {
                    graph
                        .modules
                        .get(fid.0 as usize)
                        .map(|m| m.path.strip_prefix(root).unwrap_or(&m.path).to_path_buf())
                })
                .collect()
        })
        .unwrap_or_default();

    let import_count = imported_by.len();
    let used_in_scripts = script_used_packages.contains(package_name);
    DependencyTrace {
        package_name: package_name.to_string(),
        imported_by,
        type_only_imported_by,
        used_in_scripts,
        is_used: import_count > 0 || used_in_scripts,
        import_count,
    }
}

fn format_reference_kind(kind: ReferenceKind) -> String {
    match kind {
        ReferenceKind::NamedImport => "named import".to_string(),
        ReferenceKind::DefaultImport => "default import".to_string(),
        ReferenceKind::NamespaceImport => "namespace import".to_string(),
        ReferenceKind::ReExport => "re-export".to_string(),
        ReferenceKind::DynamicImport => "dynamic import".to_string(),
        ReferenceKind::SideEffectImport => "side-effect import".to_string(),
    }
}

/// Result of tracing a clone: all groups containing the code at a given location.
#[derive(Debug, Serialize)]
pub struct CloneTrace {
    #[serde(serialize_with = "serde_path::serialize")]
    pub file: PathBuf,
    pub line: usize,
    pub matched_instance: Option<CloneInstance>,
    pub clone_groups: Vec<TracedCloneGroup>,
}

#[derive(Debug, Serialize)]
pub struct TracedCloneGroup {
    /// Stable content fingerprint, usually `dup:<8hex>` and widened on rare
    /// report collisions; addressable via `fallow dupes --trace dup:<fp>` and
    /// shown in the `dupes` listing.
    pub fingerprint: String,
    pub token_count: usize,
    pub line_count: usize,
    pub instances: Vec<CloneInstance>,
    /// Group-level extract-function suggestion with estimated line savings.
    pub suggestion: RefactoringSuggestion,
    /// Best-effort name for the extracted function, derived from the dominant
    /// non-generic identifier. `null` when no confident name exists; advisory
    /// only (verify before applying).
    #[serde(skip_serializing_if = "Option::is_none")]
    pub suggested_name: Option<String>,
}

/// Build a [`TracedCloneGroup`] from a raw clone group, computing the
/// fingerprint, group-level suggestion, and dominant-identifier name and
/// relativizing every instance path against `root`.
fn build_traced_group(
    group: &CloneGroup,
    root: &Path,
    fingerprints: &CloneFingerprintSet,
) -> TracedCloneGroup {
    TracedCloneGroup {
        fingerprint: fingerprints.fingerprint_for_group(group),
        token_count: group.token_count,
        line_count: group.line_count,
        instances: group
            .instances
            .iter()
            .map(|inst| relativize_instance(inst, root))
            .collect(),
        suggestion: group_refactoring_suggestion(group),
        suggested_name: dominant_identifier(group),
    }
}

#[must_use]
pub fn trace_clone(
    report: &DuplicationReport,
    root: &Path,
    file_path: &str,
    line: usize,
) -> CloneTrace {
    let resolved = root.join(file_path);
    let mut matched_instance = None;
    let mut clone_groups = Vec::new();
    let fingerprints = CloneFingerprintSet::from_groups(&report.clone_groups);

    for group in &report.clone_groups {
        let matching = group.instances.iter().find(|inst| {
            let inst_matches = inst.file == resolved
                || inst.file.strip_prefix(root).unwrap_or(&inst.file) == Path::new(file_path);
            inst_matches && inst.start_line <= line && line <= inst.end_line
        });

        if let Some(matched) = matching {
            if matched_instance.is_none() {
                matched_instance = Some(relativize_instance(matched, root));
            }
            clone_groups.push(build_traced_group(group, root, &fingerprints));
        }
    }

    CloneTrace {
        file: PathBuf::from(file_path),
        line,
        matched_instance,
        clone_groups,
    }
}

/// Trace a clone group by its stable content fingerprint.
///
/// Fingerprints are usually `dup:<8hex>` and widen only when needed to avoid a
/// collision inside the same report.
///
/// Returns a [`CloneTrace`] whose single `clone_groups` entry is the matched
/// group and whose `file` / `line` / `matched_instance` come from that group's
/// representative (first) instance. `matched_instance` is `None` (and
/// `clone_groups` empty) when no group matches the fingerprint.
#[must_use]
pub fn trace_clone_by_fingerprint(
    report: &DuplicationReport,
    root: &Path,
    fingerprint: &str,
) -> CloneTrace {
    let fingerprints = CloneFingerprintSet::from_groups(&report.clone_groups);
    let matched = fingerprints.find_group(&report.clone_groups, fingerprint);

    let Some(group) = matched else {
        return CloneTrace {
            file: PathBuf::new(),
            line: 0,
            matched_instance: None,
            clone_groups: Vec::new(),
        };
    };

    let representative = group
        .instances
        .first()
        .map(|inst| relativize_instance(inst, root));
    let (file, line) = representative.as_ref().map_or_else(
        || (PathBuf::new(), 0),
        |inst| (inst.file.clone(), inst.start_line),
    );

    CloneTrace {
        file,
        line,
        matched_instance: representative,
        clone_groups: vec![build_traced_group(group, root, &fingerprints)],
    }
}

/// Return a copy of `inst` with `file` rewritten relative to `root` (forward-slash normalized
/// for cross-platform JSON parity with `serde_path::serialize`). If `inst.file` is already
/// outside `root`, the path is left unchanged.
fn relativize_instance(inst: &CloneInstance, root: &Path) -> CloneInstance {
    let rel = inst.file.strip_prefix(root).map_or_else(
        |_| inst.file.clone(),
        |p| PathBuf::from(p.to_string_lossy().replace('\\', "/")),
    );
    CloneInstance {
        file: rel,
        ..inst.clone()
    }
}

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

    use crate::discover::{DiscoveredFile, EntryPoint, EntryPointSource, FileId};
    use crate::extract::{ExportInfo, ExportName, ImportInfo, ImportedName, VisibilityTag};
    use crate::resolve::{ResolveResult, ResolvedImport, ResolvedModule};

    fn build_test_graph() -> ModuleGraph {
        let files = vec![
            DiscoveredFile {
                id: FileId(0),
                path: PathBuf::from("/project/src/entry.ts"),
                size_bytes: 100,
            },
            DiscoveredFile {
                id: FileId(1),
                path: PathBuf::from("/project/src/utils.ts"),
                size_bytes: 50,
            },
            DiscoveredFile {
                id: FileId(2),
                path: PathBuf::from("/project/src/unused.ts"),
                size_bytes: 30,
            },
        ];

        let entry_points = vec![EntryPoint {
            path: PathBuf::from("/project/src/entry.ts"),
            source: EntryPointSource::PackageJsonMain,
        }];

        let resolved_modules = vec![
            ResolvedModule {
                file_id: FileId(0),
                path: PathBuf::from("/project/src/entry.ts"),
                resolved_imports: vec![ResolvedImport {
                    info: ImportInfo {
                        source: "./utils".to_string(),
                        imported_name: ImportedName::Named("foo".to_string()),
                        local_name: "foo".to_string(),
                        is_type_only: false,
                        from_style: false,
                        span: oxc_span::Span::new(0, 10),
                        source_span: oxc_span::Span::default(),
                    },
                    target: ResolveResult::InternalModule(FileId(1)),
                }],
                ..Default::default()
            },
            ResolvedModule {
                file_id: FileId(1),
                path: PathBuf::from("/project/src/utils.ts"),
                exports: vec![
                    ExportInfo {
                        name: ExportName::Named("foo".to_string()),
                        local_name: Some("foo".to_string()),
                        is_type_only: false,
                        visibility: VisibilityTag::None,
                        expected_unused_reason: None,
                        span: oxc_span::Span::new(0, 20),
                        members: vec![],
                        is_side_effect_used: false,
                        super_class: None,
                    },
                    ExportInfo {
                        name: ExportName::Named("bar".to_string()),
                        local_name: Some("bar".to_string()),
                        is_type_only: false,
                        visibility: VisibilityTag::None,
                        expected_unused_reason: None,
                        span: oxc_span::Span::new(21, 40),
                        members: vec![],
                        is_side_effect_used: false,
                        super_class: None,
                    },
                ],
                ..Default::default()
            },
            ResolvedModule {
                file_id: FileId(2),
                path: PathBuf::from("/project/src/unused.ts"),
                exports: vec![ExportInfo {
                    name: ExportName::Named("baz".to_string()),
                    local_name: Some("baz".to_string()),
                    is_type_only: false,
                    visibility: VisibilityTag::None,
                    expected_unused_reason: None,
                    span: oxc_span::Span::new(0, 15),
                    members: vec![],
                    is_side_effect_used: false,
                    super_class: None,
                }],
                ..Default::default()
            },
        ];

        ModuleGraph::build(&resolved_modules, &entry_points, &files)
    }

    #[test]
    fn trace_used_export() {
        let graph = build_test_graph();
        let root = Path::new("/project");

        let trace = trace_export(&graph, root, "src/utils.ts", "foo").unwrap();
        assert!(trace.is_used);
        assert!(trace.file_reachable);
        assert_eq!(trace.direct_references.len(), 1);
        assert_eq!(
            trace.direct_references[0].from_file,
            PathBuf::from("src/entry.ts")
        );
        assert_eq!(trace.direct_references[0].kind, "named import");
    }

    #[test]
    fn trace_unused_export() {
        let graph = build_test_graph();
        let root = Path::new("/project");

        let trace = trace_export(&graph, root, "src/utils.ts", "bar").unwrap();
        assert!(!trace.is_used);
        assert!(trace.file_reachable);
        assert!(trace.direct_references.is_empty());
    }

    #[test]
    fn trace_unreachable_file_export() {
        let graph = build_test_graph();
        let root = Path::new("/project");

        let trace = trace_export(&graph, root, "src/unused.ts", "baz").unwrap();
        assert!(!trace.is_used);
        assert!(!trace.file_reachable);
        assert!(trace.reason.contains("unreachable"));
    }

    #[test]
    fn trace_nonexistent_export() {
        let graph = build_test_graph();
        let root = Path::new("/project");

        let trace = trace_export(&graph, root, "src/utils.ts", "nonexistent");
        assert!(trace.is_none());
    }

    #[test]
    fn trace_nonexistent_file() {
        let graph = build_test_graph();
        let root = Path::new("/project");

        let trace = trace_export(&graph, root, "src/nope.ts", "foo");
        assert!(trace.is_none());
    }

    #[test]
    fn trace_file_edges() {
        let graph = build_test_graph();
        let root = Path::new("/project");

        let trace = trace_file(&graph, root, "src/entry.ts").unwrap();
        assert!(trace.is_entry_point);
        assert!(trace.is_reachable);
        assert_eq!(trace.imports_from.len(), 1);
        assert_eq!(trace.imports_from[0], PathBuf::from("src/utils.ts"));
        assert!(trace.imported_by.is_empty());
    }

    #[test]
    fn trace_file_imported_by() {
        let graph = build_test_graph();
        let root = Path::new("/project");

        let trace = trace_file(&graph, root, "src/utils.ts").unwrap();
        assert!(!trace.is_entry_point);
        assert!(trace.is_reachable);
        assert_eq!(trace.exports.len(), 2);
        assert_eq!(trace.imported_by.len(), 1);
        assert_eq!(trace.imported_by[0], PathBuf::from("src/entry.ts"));
    }

    #[test]
    fn trace_unreachable_file() {
        let graph = build_test_graph();
        let root = Path::new("/project");

        let trace = trace_file(&graph, root, "src/unused.ts").unwrap();
        assert!(!trace.is_reachable);
        assert!(!trace.is_entry_point);
        assert!(trace.imported_by.is_empty());
    }

    #[test]
    fn trace_dependency_used() {
        let files = vec![DiscoveredFile {
            id: FileId(0),
            path: PathBuf::from("/project/src/app.ts"),
            size_bytes: 100,
        }];
        let entry_points = vec![EntryPoint {
            path: PathBuf::from("/project/src/app.ts"),
            source: EntryPointSource::PackageJsonMain,
        }];
        let resolved_modules = vec![ResolvedModule {
            file_id: FileId(0),
            path: PathBuf::from("/project/src/app.ts"),
            resolved_imports: vec![ResolvedImport {
                info: ImportInfo {
                    source: "lodash".to_string(),
                    imported_name: ImportedName::Named("get".to_string()),
                    local_name: "get".to_string(),
                    is_type_only: false,
                    from_style: false,
                    span: oxc_span::Span::new(0, 10),
                    source_span: oxc_span::Span::default(),
                },
                target: ResolveResult::NpmPackage("lodash".to_string()),
            }],
            ..Default::default()
        }];

        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
        let root = Path::new("/project");

        let trace = trace_dependency(&graph, root, "lodash", &FxHashSet::default());
        assert!(trace.is_used);
        assert!(!trace.used_in_scripts);
        assert_eq!(trace.import_count, 1);
        assert_eq!(trace.imported_by[0], PathBuf::from("src/app.ts"));
    }

    #[test]
    fn trace_dependency_unused() {
        let files = vec![DiscoveredFile {
            id: FileId(0),
            path: PathBuf::from("/project/src/app.ts"),
            size_bytes: 100,
        }];
        let entry_points = vec![EntryPoint {
            path: PathBuf::from("/project/src/app.ts"),
            source: EntryPointSource::PackageJsonMain,
        }];
        let resolved_modules = vec![ResolvedModule {
            file_id: FileId(0),
            path: PathBuf::from("/project/src/app.ts"),
            ..Default::default()
        }];

        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
        let root = Path::new("/project");

        let trace = trace_dependency(&graph, root, "nonexistent-pkg", &FxHashSet::default());
        assert!(!trace.is_used);
        assert!(!trace.used_in_scripts);
        assert_eq!(trace.import_count, 0);
        assert!(trace.imported_by.is_empty());
    }

    #[test]
    fn trace_dependency_used_only_in_scripts() {
        let files = vec![DiscoveredFile {
            id: FileId(0),
            path: PathBuf::from("/project/src/app.ts"),
            size_bytes: 100,
        }];
        let entry_points = vec![EntryPoint {
            path: PathBuf::from("/project/src/app.ts"),
            source: EntryPointSource::PackageJsonMain,
        }];
        let resolved_modules = vec![ResolvedModule {
            file_id: FileId(0),
            path: PathBuf::from("/project/src/app.ts"),
            ..Default::default()
        }];

        let graph = ModuleGraph::build(&resolved_modules, &entry_points, &files);
        let root = Path::new("/project");
        let mut script_used = FxHashSet::default();
        script_used.insert("microbundle".to_string());

        let trace = trace_dependency(&graph, root, "microbundle", &script_used);
        assert!(
            trace.is_used,
            "is_used must be true when the package is referenced from package.json scripts"
        );
        assert!(trace.used_in_scripts);
        assert_eq!(trace.import_count, 0);
        assert!(trace.imported_by.is_empty());
    }

    #[test]
    fn trace_clone_finds_matching_group() {
        use crate::duplicates::{CloneGroup, CloneInstance, DuplicationReport, DuplicationStats};
        let report = DuplicationReport {
            clone_groups: vec![CloneGroup {
                instances: vec![
                    CloneInstance {
                        file: PathBuf::from("/project/src/a.ts"),
                        start_line: 10,
                        end_line: 20,
                        start_col: 0,
                        end_col: 0,
                        fragment: "fn foo() {}".to_string(),
                    },
                    CloneInstance {
                        file: PathBuf::from("/project/src/b.ts"),
                        start_line: 5,
                        end_line: 15,
                        start_col: 0,
                        end_col: 0,
                        fragment: "fn foo() {}".to_string(),
                    },
                ],
                token_count: 60,
                line_count: 11,
            }],
            clone_families: vec![],
            mirrored_directories: vec![],
            stats: DuplicationStats {
                total_files: 2,
                files_with_clones: 2,
                total_lines: 100,
                duplicated_lines: 22,
                total_tokens: 200,
                duplicated_tokens: 120,
                clone_groups: 1,
                clone_instances: 2,
                duplication_percentage: 22.0,
                clone_groups_below_min_occurrences: 0,
            },
        };
        let trace = trace_clone(&report, Path::new("/project"), "src/a.ts", 15);
        assert!(trace.matched_instance.is_some());
        assert_eq!(trace.clone_groups.len(), 1);
        assert_eq!(trace.clone_groups[0].instances.len(), 2);
        assert!(trace.clone_groups[0].fingerprint.starts_with("dup:"));
        assert_eq!(trace.clone_groups[0].suggestion.estimated_savings, 11);
    }

    #[test]
    fn trace_clone_by_fingerprint_resolves_and_misses() {
        use crate::duplicates::{
            CloneGroup, CloneInstance, DuplicationReport, DuplicationStats, clone_fingerprint,
        };
        let report = DuplicationReport {
            clone_groups: vec![CloneGroup {
                instances: vec![
                    CloneInstance {
                        file: PathBuf::from("/project/src/a.ts"),
                        start_line: 10,
                        end_line: 20,
                        start_col: 0,
                        end_col: 0,
                        fragment: "fn buildInvoice() {}".to_string(),
                    },
                    CloneInstance {
                        file: PathBuf::from("/project/src/b.ts"),
                        start_line: 5,
                        end_line: 15,
                        start_col: 0,
                        end_col: 0,
                        fragment: "fn buildInvoice() {}".to_string(),
                    },
                ],
                token_count: 60,
                line_count: 11,
            }],
            clone_families: vec![],
            mirrored_directories: vec![],
            stats: DuplicationStats::default(),
        };
        let fp = clone_fingerprint(&report.clone_groups[0].instances);

        let hit = trace_clone_by_fingerprint(&report, Path::new("/project"), &fp);
        assert!(hit.matched_instance.is_some());
        assert_eq!(hit.clone_groups.len(), 1);
        assert_eq!(hit.clone_groups[0].fingerprint, fp);
        assert_eq!(hit.line, 10);

        let miss = trace_clone_by_fingerprint(&report, Path::new("/project"), "dup:deadbeef");
        assert!(miss.matched_instance.is_none());
        assert!(miss.clone_groups.is_empty());
    }

    #[test]
    fn trace_clone_no_match() {
        use crate::duplicates::{CloneGroup, CloneInstance, DuplicationReport, DuplicationStats};
        let report = DuplicationReport {
            clone_groups: vec![CloneGroup {
                instances: vec![CloneInstance {
                    file: PathBuf::from("/project/src/a.ts"),
                    start_line: 10,
                    end_line: 20,
                    start_col: 0,
                    end_col: 0,
                    fragment: "fn foo() {}".to_string(),
                }],
                token_count: 60,
                line_count: 11,
            }],
            clone_families: vec![],
            mirrored_directories: vec![],
            stats: DuplicationStats {
                total_files: 1,
                files_with_clones: 1,
                total_lines: 50,
                duplicated_lines: 11,
                total_tokens: 100,
                duplicated_tokens: 60,
                clone_groups: 1,
                clone_instances: 1,
                duplication_percentage: 22.0,
                clone_groups_below_min_occurrences: 0,
            },
        };
        let trace = trace_clone(&report, Path::new("/project"), "src/a.ts", 25);
        assert!(trace.matched_instance.is_none());
        assert!(trace.clone_groups.is_empty());
    }

    #[test]
    fn trace_clone_line_boundary() {
        use crate::duplicates::{CloneGroup, CloneInstance, DuplicationReport, DuplicationStats};
        let report = DuplicationReport {
            clone_groups: vec![CloneGroup {
                instances: vec![
                    CloneInstance {
                        file: PathBuf::from("/project/src/a.ts"),
                        start_line: 10,
                        end_line: 20,
                        start_col: 0,
                        end_col: 0,
                        fragment: "code".to_string(),
                    },
                    CloneInstance {
                        file: PathBuf::from("/project/src/b.ts"),
                        start_line: 1,
                        end_line: 11,
                        start_col: 0,
                        end_col: 0,
                        fragment: "code".to_string(),
                    },
                ],
                token_count: 50,
                line_count: 11,
            }],
            clone_families: vec![],
            mirrored_directories: vec![],
            stats: DuplicationStats {
                total_files: 2,
                files_with_clones: 2,
                total_lines: 100,
                duplicated_lines: 22,
                total_tokens: 200,
                duplicated_tokens: 100,
                clone_groups: 1,
                clone_instances: 2,
                duplication_percentage: 22.0,
                clone_groups_below_min_occurrences: 0,
            },
        };
        let root = Path::new("/project");
        assert!(
            trace_clone(&report, root, "src/a.ts", 10)
                .matched_instance
                .is_some()
        );
        assert!(
            trace_clone(&report, root, "src/a.ts", 20)
                .matched_instance
                .is_some()
        );
        assert!(
            trace_clone(&report, root, "src/a.ts", 21)
                .matched_instance
                .is_none()
        );
    }

    #[test]
    fn trace_clone_returns_relative_instance_paths() {
        use crate::duplicates::{CloneGroup, CloneInstance, DuplicationReport, DuplicationStats};
        let report = DuplicationReport {
            clone_groups: vec![CloneGroup {
                instances: vec![
                    CloneInstance {
                        file: PathBuf::from("/project/src/a.ts"),
                        start_line: 1,
                        end_line: 10,
                        start_col: 0,
                        end_col: 0,
                        fragment: "code".to_string(),
                    },
                    CloneInstance {
                        file: PathBuf::from("/project/src/b.ts"),
                        start_line: 1,
                        end_line: 10,
                        start_col: 0,
                        end_col: 0,
                        fragment: "code".to_string(),
                    },
                ],
                token_count: 50,
                line_count: 10,
            }],
            clone_families: vec![],
            mirrored_directories: vec![],
            stats: DuplicationStats {
                total_files: 2,
                files_with_clones: 2,
                total_lines: 50,
                duplicated_lines: 20,
                total_tokens: 100,
                duplicated_tokens: 100,
                clone_groups: 1,
                clone_instances: 2,
                duplication_percentage: 40.0,
                clone_groups_below_min_occurrences: 0,
            },
        };
        let trace = trace_clone(&report, Path::new("/project"), "src/a.ts", 5);
        let matched = trace.matched_instance.as_ref().expect("match expected");
        assert_eq!(matched.file, PathBuf::from("src/a.ts"));
        for group in &trace.clone_groups {
            for inst in &group.instances {
                let as_str = inst.file.to_string_lossy();
                assert!(
                    !as_str.starts_with('/'),
                    "instance file should be relative, got {as_str}",
                );
                assert!(
                    !as_str.contains(":\\") && !as_str.contains(":/"),
                    "instance file should not have a drive letter, got {as_str}",
                );
            }
        }

        let json = serde_json::to_string(&trace).expect("serializes");
        assert!(
            !json.contains("\"/project/"),
            "serialized trace should not leak absolute paths: {json}",
        );
    }

    /// Regression for the MCP e2e `trace_export` / `trace_file` Windows
    /// failures: the MCP layer passes forward-slashed user input
    /// (`src/utils.ts`) but `module_path` on Windows uses backslash
    /// separators (`D:\a\fallow\...\src\utils.ts`). The byte-level
    /// equality check missed every match. The helper now normalises
    /// both sides to forward slashes before comparing.
    #[test]
    fn path_matches_normalises_windows_module_path_against_posix_user_path() {
        let root = Path::new(r"D:\a\fallow\fallow\tests\fixtures\basic-project");
        let module_path =
            PathBuf::from(r"D:\a\fallow\fallow\tests\fixtures\basic-project\src\utils.ts");
        assert!(path_matches(&module_path, root, "src/utils.ts"));
        assert!(path_matches(&module_path, root, r"src\utils.ts"));
    }

    #[test]
    fn path_matches_ends_with_fallback_handles_mixed_separators() {
        let root = Path::new("/some/other/root");
        let module_path =
            PathBuf::from(r"D:\a\fallow\fallow\tests\fixtures\basic-project\src\utils.ts");
        assert!(path_matches(&module_path, root, "src/utils.ts"));
    }

    /// Regression for the MCP e2e trace_export / trace_file failures: even
    /// after `path_matches` correctly identified the file on Windows, the
    /// trace output struct's `file: PathBuf` field serialized the stored
    /// backslash-shaped path verbatim. JSON consumers (MCP agents, CI
    /// pipelines, the cross-platform trace_file assertion in
    /// `e2e_trace_file_returns_json`) expect forward-slash. Pin the
    /// contract via raw-string Windows-shaped `PathBuf::from` so the test
    /// runs cross-platform.
    #[test]
    fn export_trace_serializes_windows_path_with_forward_slashes() {
        let trace = ExportTrace {
            file: PathBuf::from(r"src\utils.ts"),
            export_name: "foo".to_string(),
            file_reachable: true,
            is_entry_point: false,
            is_used: true,
            direct_references: vec![ExportReference {
                from_file: PathBuf::from(r"src\entry.ts"),
                kind: "named import".to_string(),
            }],
            re_export_chains: vec![ReExportChain {
                barrel_file: PathBuf::from(r"src\index.ts"),
                exported_as: "foo".to_string(),
                reference_count: 1,
            }],
            reason: "ok".to_string(),
        };
        let json = serde_json::to_string(&trace).expect("serializes");
        assert!(
            json.contains("\"file\":\"src/utils.ts\""),
            "ExportTrace.file must serialize with forward slashes: {json}"
        );
        assert!(
            json.contains("\"from_file\":\"src/entry.ts\""),
            "ExportReference.from_file must serialize with forward slashes: {json}"
        );
        assert!(
            json.contains("\"barrel_file\":\"src/index.ts\""),
            "ReExportChain.barrel_file must serialize with forward slashes: {json}"
        );
        assert!(
            !json.contains(r"\\"),
            "no backslash sequence should remain anywhere in the JSON: {json}"
        );
    }

    #[test]
    fn file_trace_serializes_windows_paths_with_forward_slashes() {
        let trace = FileTrace {
            file: PathBuf::from(r"src\utils.ts"),
            is_reachable: true,
            is_entry_point: false,
            exports: vec![],
            imports_from: vec![PathBuf::from(r"src\helpers.ts")],
            imported_by: vec![PathBuf::from(r"src\entry.ts")],
            re_exports: vec![TracedReExport {
                source_file: PathBuf::from(r"src\source.ts"),
                imported_name: "foo".to_string(),
                exported_name: "foo".to_string(),
            }],
        };
        let json = serde_json::to_string(&trace).expect("serializes");
        assert!(json.contains("\"file\":\"src/utils.ts\""), "got {json}");
        assert!(
            json.contains("\"imports_from\":[\"src/helpers.ts\"]"),
            "got {json}"
        );
        assert!(
            json.contains("\"imported_by\":[\"src/entry.ts\"]"),
            "got {json}"
        );
        assert!(
            json.contains("\"source_file\":\"src/source.ts\""),
            "got {json}"
        );
        assert!(!json.contains(r"\\"), "no backslash should remain: {json}");
    }
}