rch_common/

cargo_path_deps.rs

//! Cargo local path-dependency graph resolver.
//!
//! The resolver builds a deterministic active graph of local `path` dependencies
//! using a two-phase strategy:
//! 1. `cargo metadata --locked` (primary source of truth when a valid
//!    `Cargo.lock` is present)
//! 2. Recursive manifest parsing fallback (for malformed metadata, metadata
//!    failures, and projects whose lockfile is stale, incompatible, or absent)
//!
//! Dependency planning is strictly NON-MUTATING
//! (bd-rch-pinned-metadata-lock-ytkda): plain `cargo metadata` creates or
//! rewrites the project's `Cargo.lock` as a side effect, which silently
//! mutated user checkouts every time the hook planned a sync closure. The
//! resolver therefore always passes `--locked`; when cargo refuses (stale or
//! missing lockfile) it falls through to the manifest-only fallback, which
//! never writes anything. Lockfile bytes and mtimes are preserved in every
//! case.
//!
//! This invariant is about the ambient checkout passed to dependency planning.
//! Clean-overlay execution materializes a pinned Git archive into a private
//! remote root and deliberately does not run this ambient dependency planner.
//! Mutation inside that private archive would be a separate defect and is not
//! evidence that the ambient checkout changed; conversely, archive-only checks
//! cannot prove this checkout-level invariant.
//!
//! A separate manifest-derived materialization closure covers every local path
//! that Cargo may need under another feature, target, or test selection. Keeping
//! that closure separate preserves Cargo's cycle-free active execution graph
//! while still making inactive optional cycles available to remote workers.
//!
//! Every discovered path is normalized through [`PathTopologyPolicy`] to enforce
//! canonical-root safety and stable path identity.

use serde::{Deserialize, Serialize};
use std::collections::{BTreeMap, BTreeSet};
use std::fmt;
use std::path::{Path, PathBuf};
use std::process::Command;

use crate::{PathNormalizationErrorKind, PathTopologyPolicy, normalize_project_path_with_policy};

/// Deterministic graph of local Cargo path dependencies.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct CargoPathDependencyGraph {
    /// Canonical path to the entry manifest used for resolution.
    pub entry_manifest_path: PathBuf,
    /// Canonical workspace root when entrypoint is a workspace manifest.
    pub workspace_root: Option<PathBuf>,
    /// Canonical root packages used as traversal roots (sorted).
    pub root_packages: Vec<PathBuf>,
    /// Reachable local packages in deterministic order.
    pub packages: Vec<CargoPathDependencyPackage>,
    /// Reachable path-dependency edges in deterministic order.
    pub edges: Vec<CargoPathDependencyEdge>,
}

/// Deterministic, cycle-tolerant closure of local Cargo packages that must be
/// materialized on a remote worker.
///
/// Unlike [`CargoPathDependencyGraph`], this closure includes inactive optional,
/// development, build, target-specific, workspace-inherited, and path-patched
/// edges. Its edges are evidence, not an execution DAG, and may contain cycles.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct CargoPathMaterializationClosure {
    /// Canonical path to the entry manifest used for resolution.
    pub entry_manifest_path: PathBuf,
    /// Canonical workspace root when entrypoint is a workspace manifest.
    pub workspace_root: Option<PathBuf>,
    /// Canonical root packages used as traversal roots (sorted).
    pub root_packages: Vec<PathBuf>,
    /// Every reachable local package in deterministic order.
    pub packages: Vec<CargoPathDependencyPackage>,
    /// Every reachable path-dependency edge in deterministic order.
    /// Cycles are retained and do not make the closure invalid.
    pub edges: Vec<CargoPathDependencyEdge>,
}

/// One package node in the resolved path-dependency graph.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct CargoPathDependencyPackage {
    /// Canonical package root directory.
    pub package_root: PathBuf,
    /// Canonical package manifest path.
    pub manifest_path: PathBuf,
    /// Package name (best effort, deterministic fallback if missing).
    pub package_name: String,
    /// Whether this package is a workspace member/root.
    pub workspace_member: bool,
}

/// One directed path-dependency edge.
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
pub struct CargoPathDependencyEdge {
    /// Canonical source package root.
    pub from: PathBuf,
    /// Canonical dependency package root.
    pub to: PathBuf,
    /// Dependency key from manifest (`[dependencies] <name> = { path = ... }`).
    pub dependency_name: String,
}

/// Taxonomy for local path-dependency resolution failures.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum CargoPathDependencyErrorKind {
    ManifestParseFailure,
    MissingPathDependency,
    CyclicDependency,
    PathPolicyViolation,
    MetadataParseFailure,
    MetadataInvocationFailure,
}

impl fmt::Display for CargoPathDependencyErrorKind {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::ManifestParseFailure => write!(f, "manifest parse failure"),
            Self::MissingPathDependency => write!(f, "missing path dependency"),
            Self::CyclicDependency => write!(f, "cyclic path dependency"),
            Self::PathPolicyViolation => write!(f, "path policy violation"),
            Self::MetadataParseFailure => write!(f, "metadata parse failure"),
            Self::MetadataInvocationFailure => write!(f, "metadata invocation failure"),
        }
    }
}

/// Structured error with explicit diagnostics.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CargoPathDependencyError {
    kind: CargoPathDependencyErrorKind,
    detail: String,
    manifest_path: Option<Box<PathBuf>>,
    dependency_name: Option<Box<str>>,
    dependency_path: Option<Box<PathBuf>>,
    cycle: Vec<PathBuf>,
    diagnostics: Vec<String>,
}

impl CargoPathDependencyError {
    pub(crate) fn new(kind: CargoPathDependencyErrorKind, detail: impl Into<String>) -> Self {
        Self {
            kind,
            detail: detail.into(),
            manifest_path: None,
            dependency_name: None,
            dependency_path: None,
            cycle: Vec::new(),
            diagnostics: Vec::new(),
        }
    }

    pub(crate) fn with_manifest_path(mut self, manifest_path: impl Into<PathBuf>) -> Self {
        self.manifest_path = Some(Box::new(manifest_path.into()));
        self
    }

    pub(crate) fn with_dependency_name(mut self, dependency_name: impl Into<String>) -> Self {
        self.dependency_name = Some(dependency_name.into().into_boxed_str());
        self
    }

    pub(crate) fn with_dependency_path(mut self, dependency_path: impl Into<PathBuf>) -> Self {
        self.dependency_path = Some(Box::new(dependency_path.into()));
        self
    }

    fn with_cycle(mut self, cycle: Vec<PathBuf>) -> Self {
        self.cycle = cycle;
        self
    }

    fn with_diagnostic(mut self, diagnostic: impl Into<String>) -> Self {
        self.diagnostics.push(diagnostic.into());
        self
    }

    fn with_diagnostics<I>(mut self, diagnostics: I) -> Self
    where
        I: IntoIterator,
        I::Item: Into<String>,
    {
        self.diagnostics
            .extend(diagnostics.into_iter().map(Into::into));
        self
    }

    fn push_diagnostic(&mut self, diagnostic: impl Into<String>) {
        self.diagnostics.push(diagnostic.into());
    }

    /// Error category.
    pub fn kind(&self) -> &CargoPathDependencyErrorKind {
        &self.kind
    }

    /// Human-readable detail.
    pub fn detail(&self) -> &str {
        &self.detail
    }

    /// Manifest path associated with the error when available.
    pub fn manifest_path(&self) -> Option<&Path> {
        self.manifest_path.as_deref().map(PathBuf::as_path)
    }

    /// Dependency key associated with the error when available.
    pub fn dependency_name(&self) -> Option<&str> {
        self.dependency_name.as_deref()
    }

    /// Dependency path associated with the error when available.
    pub fn dependency_path(&self) -> Option<&Path> {
        self.dependency_path.as_deref().map(PathBuf::as_path)
    }

    /// Cycle path for cyclic failures (ordered, includes repeated terminal node).
    pub fn cycle(&self) -> &[PathBuf] {
        &self.cycle
    }

    /// Structured diagnostic lines.
    pub fn diagnostics(&self) -> &[String] {
        &self.diagnostics
    }
}

impl fmt::Display for CargoPathDependencyError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}: {}", self.kind, self.detail)?;
        if let Some(manifest_path) = &self.manifest_path {
            write!(f, " (manifest: {})", manifest_path.display())?;
        }
        if let Some(dependency_name) = &self.dependency_name {
            write!(f, " (dependency: {dependency_name})")?;
        }
        if let Some(dependency_path) = &self.dependency_path {
            write!(f, " (path: {})", dependency_path.display())?;
        }
        Ok(())
    }
}

impl std::error::Error for CargoPathDependencyError {}

/// One entry in a complete, repository-relative selected source inventory.
///
/// Retain text for every `Cargo.toml` and `.cargo/config[.toml]`; other regular
/// files need only their presence. Symlink text is its selected target, never a
/// target read from the ambient filesystem.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum SelectedCargoEntry {
    File(Option<String>),
    Symlink(String),
}

/// Resolve a CLI-selected path without collapsing `..` across symlinks.
///
/// Inventory structure and symlinks are validated, but metadata text is not
/// required: loaders use this before hydrating selected manifests/configs.
/// Absolute and missing paths are refused without filesystem I/O. Call
/// [`validate_selected_cargo_tree`] after hydration to validate Cargo references.
pub fn validate_selected_cargo_path(
    entries: &BTreeMap<PathBuf, SelectedCargoEntry>,
    path: &Path,
) -> Result<PathBuf, CargoPathDependencyError> {
    let tree = SelectedCargoTree::from_inventory(entries);
    tree.check_inventory()?;
    let raw = path.to_str().ok_or_else(|| {
        CargoPathDependencyError::new(
            CargoPathDependencyErrorKind::PathPolicyViolation,
            "selected Cargo path is not UTF-8",
        )
        .with_dependency_path(path)
    })?;
    tree.resolve(Path::new(""), raw).map_err(|detail| {
        CargoPathDependencyError::new(CargoPathDependencyErrorKind::PathPolicyViolation, detail)
            .with_dependency_path(path)
    })
}

/// Check an inline Cargo configuration override against selected source bytes.
///
/// `base` is its repository-relative resolution directory (empty for the root),
/// not a fabricated configuration filename. Existing selected configs are
/// validated separately; no synthetic inventory entry can mask a symlink.
pub fn validate_selected_cargo_config(
    entries: &BTreeMap<PathBuf, SelectedCargoEntry>,
    base: &Path,
    contents: &str,
) -> Result<(), CargoPathDependencyError> {
    validate_selected_cargo_config_at(entries, Path::new("Cargo.toml"), base, contents)
}

/// Validate an inline override within a combined committed-source inventory.
///
/// `primary_manifest` identifies the selected Cargo entrypoint, while `base`
/// identifies the configuration's resolution directory within the container.
/// Every selected manifest/config is validated before applying the override.
pub fn validate_selected_cargo_config_at(
    entries: &BTreeMap<PathBuf, SelectedCargoEntry>,
    primary_manifest: &Path,
    base: &Path,
    contents: &str,
) -> Result<(), CargoPathDependencyError> {
    validate_selected_cargo_tree_at(entries, primary_manifest)?;
    let resolved_base = validate_selected_cargo_path(
        entries,
        if base.as_os_str().is_empty() {
            Path::new(".")
        } else {
            base
        },
    )?;
    let mut tree = SelectedCargoTree::from_inventory(entries);
    if !tree.directories.contains(&resolved_base) {
        return Err(CargoPathDependencyError::new(
            CargoPathDependencyErrorKind::PathPolicyViolation,
            "Cargo configuration base is not a selected directory",
        )
        .with_dependency_path(base));
    }
    let document = toml::from_str::<toml::Table>(contents).map_err(|error| {
        CargoPathDependencyError::new(
            CargoPathDependencyErrorKind::ManifestParseFailure,
            format!("invalid inline Cargo configuration: {error}"),
        )
    })?;
    tree.config_at(
        Path::new("<command-line-config>"),
        &resolved_base,
        &document,
    );
    if tree.diagnostics.is_empty() {
        Ok(())
    } else {
        Err(CargoPathDependencyError::new(
            CargoPathDependencyErrorKind::PathPolicyViolation,
            format!(
                "inline Cargo configuration is not contained: {}",
                tree.diagnostics.join("; ")
            ),
        )
        .with_diagnostics(tree.diagnostics))
    }
}

/// Refuse Cargo source references outside an explicitly selected source tree.
///
/// This is deliberately conservative: every selected manifest/config and every
/// symlink is checked, including inactive dependencies and fixture manifests.
/// It performs no filesystem reads or Cargo invocations. It does not inspect
/// command-line overrides, worker/home configuration, or arbitrary file reads
/// performed by build scripts; callers must admit those separately. External
/// roots are refused here, not silently substituted with ambient worker copies.
pub fn validate_selected_cargo_tree(
    entries: &BTreeMap<PathBuf, SelectedCargoEntry>,
) -> Result<(), CargoPathDependencyError> {
    validate_selected_cargo_tree_at(entries, Path::new("Cargo.toml"))
}

/// Validate a selected Cargo entrypoint inside a combined source container.
///
/// For example, `app/Cargo.toml` may reference `../dep` when `dep/Cargo.toml`
/// is also selected. The container boundary, not the primary repository's
/// boundary, limits resolution. All selected metadata and symlinks retain the
/// same conservative checks as [`validate_selected_cargo_tree`]. The caller
/// must bind and materialize the complete inventory; this API reads no ambient
/// files and does not stage external repositories itself.
pub fn validate_selected_cargo_tree_at(
    entries: &BTreeMap<PathBuf, SelectedCargoEntry>,
    primary_manifest: &Path,
) -> Result<(), CargoPathDependencyError> {
    let mut tree = SelectedCargoTree::from_inventory(entries);
    let primary = primary_manifest
        .to_str()
        .ok_or_else(|| "primary manifest path is not UTF-8".to_string())
        .and_then(|raw| {
            if primary_manifest
                .file_name()
                .is_none_or(|name| name != "Cargo.toml")
            {
                return Err("primary manifest must be named Cargo.toml".to_string());
            }
            let resolved = tree.resolve(Path::new(""), raw)?;
            if !matches!(
                entries.get(&resolved),
                Some(SelectedCargoEntry::File(Some(_)))
            ) {
                return Err("selected primary manifest text is unavailable".to_string());
            }
            Ok(())
        });
    if let Err(error) = primary {
        tree.diagnostics.push(format!(
            "selected primary {}: {error}; ambient ancestor discovery is not admitted",
            primary_manifest.display()
        ));
    }
    for path in entries.keys() {
        let is_manifest = path.file_name().is_some_and(|name| name == "Cargo.toml");
        let is_config = path
            .parent()
            .is_some_and(|parent| parent.file_name().is_some_and(|name| name == ".cargo"))
            && path
                .file_name()
                .is_some_and(|name| name == "config" || name == "config.toml");
        if !is_manifest && !is_config {
            continue;
        }
        let contents = tree
            .resolve(Path::new(""), &path.to_string_lossy())
            .and_then(|resolved| match entries.get(&resolved) {
                Some(SelectedCargoEntry::File(Some(text))) => Ok(text),
                _ => Err("selected manifest/config text is unavailable".to_string()),
            });
        match contents.and_then(|text| {
            toml::from_str::<toml::Table>(text)
                .map_err(|error| format!("invalid selected TOML: {error}"))
        }) {
            Ok(document) => {
                if is_manifest {
                    tree.manifest(path, &document);
                } else {
                    tree.config(path, &document);
                }
            }
            Err(error) => tree
                .diagnostics
                .push(format!("{}: {error}", path.display())),
        }
    }
    // A selected `.cargo` directory symlink has no `.cargo/config` inventory
    // entry of its own. Cargo still reads that alias, relative to this project,
    // so validate its resolved text without substituting the target's parent.
    for (path, entry) in entries {
        if !matches!(entry, SelectedCargoEntry::Symlink(_))
            || !path.file_name().is_some_and(|name| name == ".cargo")
        {
            continue;
        }
        for filename in ["config", "config.toml"] {
            let logical = path.join(filename);
            let Ok(resolved) = tree.resolve(Path::new(""), &logical.to_string_lossy()) else {
                // Missing config is allowed; malformed/dangling links themselves
                // have already been checked across the entire inventory.
                continue;
            };
            let parsed = match entries.get(&resolved) {
                Some(SelectedCargoEntry::File(Some(text))) => toml::from_str::<toml::Table>(text)
                    .map_err(|error| format!("invalid selected TOML: {error}")),
                _ => Err("selected config alias text is unavailable".to_string()),
            };
            match parsed {
                Ok(document) => tree.config(&logical, &document),
                Err(error) => tree
                    .diagnostics
                    .push(format!("{}: {error}", logical.display())),
            }
        }
    }
    if tree.diagnostics.is_empty() {
        Ok(())
    } else {
        tree.diagnostics.sort();
        tree.diagnostics.dedup();
        Err(CargoPathDependencyError::new(
            CargoPathDependencyErrorKind::PathPolicyViolation,
            format!(
                "selected Cargo source tree is not contained: {}",
                tree.diagnostics.join("; ")
            ),
        )
        .with_diagnostics(tree.diagnostics))
    }
}

struct SelectedCargoTree<'a> {
    entries: &'a BTreeMap<PathBuf, SelectedCargoEntry>,
    directories: BTreeSet<PathBuf>,
    diagnostics: Vec<String>,
}

#[derive(Clone, Copy)]
enum SelectedCargoPathKind {
    Package,
    File,
    Directory,
}

impl<'a> SelectedCargoTree<'a> {
    fn from_inventory(entries: &'a BTreeMap<PathBuf, SelectedCargoEntry>) -> Self {
        let mut tree = Self {
            entries,
            directories: BTreeSet::from([PathBuf::new()]),
            diagnostics: Vec::new(),
        };
        for path in entries.keys() {
            // On Unix a colon in a leaf filename is inert (for example a
            // checked-in source excerpt named `model.rs:6150-6230`). Cargo
            // references and symlink targets still go through `components`,
            // which refuses colons. A colon in a directory can affect Cargo's
            // ancestor search, and Windows cannot materialize these names.
            let colon_in_directory = path
                .parent()
                .is_some_and(|parent| parent.to_string_lossy().contains(':'));
            if path.as_os_str().is_empty()
                || path.to_str().is_none()
                || path
                    .components()
                    .any(|part| !matches!(part, std::path::Component::Normal(_)))
                || path.to_string_lossy().contains('\\')
                || (path.to_string_lossy().contains(':') && (cfg!(windows) || colon_in_directory))
            {
                tree.diagnostics.push(format!(
                    "invalid selected inventory path: {}",
                    path.display()
                ));
                continue;
            }
            for parent in path.ancestors().skip(1) {
                tree.directories.insert(parent.to_path_buf());
            }
        }
        for (path, entry) in entries {
            if tree.directories.contains(path) {
                tree.diagnostics.push(format!(
                    "selected file also has descendants: {}",
                    path.display()
                ));
            }
            if matches!(entry, SelectedCargoEntry::Symlink(_))
                && let Err(error) = tree.resolve(Path::new(""), &path.to_string_lossy())
            {
                tree.diagnostics
                    .push(format!("{}: symlink: {error}", path.display()));
            }
        }
        tree
    }

    fn check_inventory(&self) -> Result<(), CargoPathDependencyError> {
        if self.diagnostics.is_empty() {
            Ok(())
        } else {
            Err(CargoPathDependencyError::new(
                CargoPathDependencyErrorKind::PathPolicyViolation,
                format!(
                    "invalid selected inventory: {}",
                    self.diagnostics.join("; ")
                ),
            )
            .with_diagnostics(self.diagnostics.iter().cloned()))
        }
    }

    fn components(raw: &str) -> Result<std::collections::VecDeque<String>, String> {
        if raw.is_empty()
            || raw.starts_with('/')
            || raw.contains(['\\', ':'])
            || raw.chars().any(char::is_control)
        {
            return Err(format!("unsupported or absolute path {raw:?}"));
        }
        Ok(raw.split('/').map(ToOwned::to_owned).collect())
    }

    fn resolve(&self, base: &Path, raw: &str) -> Result<PathBuf, String> {
        if !self.directories.contains(base) {
            return Err(format!("non-directory resolution base {}", base.display()));
        }
        let mut pending = Self::components(raw)?;
        let mut resolved = base.to_path_buf();
        let mut links = 0;
        while let Some(component) = pending.pop_front() {
            match component.as_str() {
                "" | "." => continue,
                ".." => {
                    if !resolved.pop() {
                        return Err(format!("path {raw:?} escapes the selected root"));
                    }
                }
                _ => resolved.push(&component),
            }
            match self.entries.get(&resolved) {
                Some(SelectedCargoEntry::Symlink(target)) => {
                    links += 1;
                    if links > 64 {
                        return Err(format!(
                            "symlink cycle or expansion limit at {}",
                            resolved.display()
                        ));
                    }
                    let mut target_components = Self::components(target)?;
                    target_components.append(&mut pending);
                    pending = target_components;
                    resolved.pop();
                }
                Some(SelectedCargoEntry::File(_)) if !pending.is_empty() => {
                    return Err(format!(
                        "non-directory path component {}",
                        resolved.display()
                    ));
                }
                Some(SelectedCargoEntry::File(_)) => {}
                None if self.directories.contains(&resolved) => {}
                None => return Err(format!("missing selected path {}", resolved.display())),
            }
        }
        Ok(resolved)
    }

    fn reference(
        &mut self,
        declaring: &Path,
        base: &Path,
        key: &str,
        value: &toml::Value,
        kind: SelectedCargoPathKind,
    ) {
        let result = value
            .as_str()
            .ok_or_else(|| "path must be a string".to_string())
            .and_then(|raw| {
                let resolved = self.resolve(base, raw)?;
                match kind {
                    SelectedCargoPathKind::Package => {
                        let manifest = self.resolve(&resolved, "Cargo.toml")?;
                        if !matches!(
                            self.entries.get(&manifest),
                            Some(SelectedCargoEntry::File(Some(_)))
                        ) {
                            return Err(format!(
                                "selected package manifest text missing: {}",
                                manifest.display()
                            ));
                        }
                    }
                    SelectedCargoPathKind::File => {
                        if !matches!(
                            self.entries.get(&resolved),
                            Some(SelectedCargoEntry::File(_))
                        ) {
                            return Err(format!(
                                "selected regular file missing: {}",
                                resolved.display()
                            ));
                        }
                    }
                    SelectedCargoPathKind::Directory => {
                        if !self.directories.contains(&resolved) {
                            return Err(format!(
                                "selected directory missing: {}",
                                resolved.display()
                            ));
                        }
                    }
                }
                Ok(())
            });
        if let Err(error) = result {
            self.diagnostics
                .push(format!("{}: {key}={value}: {error}", declaring.display()));
        }
    }

    fn dependencies(&mut self, declaring: &Path, base: &Path, key: &str, table: &toml::Table) {
        for (name, dependency) in table {
            if let Some(path) = dependency.as_table().and_then(|value| value.get("path")) {
                self.reference(
                    declaring,
                    base,
                    &format!("{key}.{name}.path"),
                    path,
                    SelectedCargoPathKind::Package,
                );
            }
        }
    }

    fn dependency_tables(
        &mut self,
        declaring: &Path,
        base: &Path,
        prefix: &str,
        table: &toml::Table,
    ) {
        for key in ["dependencies", "dev-dependencies", "build-dependencies"] {
            if let Some(dependencies) = table.get(key).and_then(toml::Value::as_table) {
                self.dependencies(declaring, base, &format!("{prefix}{key}"), dependencies);
            }
        }
    }

    fn overrides(&mut self, declaring: &Path, base: &Path, table: &toml::Table) {
        if let Some(patches) = table.get("patch").and_then(toml::Value::as_table) {
            for (registry, patch) in patches {
                if let Some(patch) = patch.as_table() {
                    self.dependencies(declaring, base, &format!("patch.{registry}"), patch);
                }
            }
        }
        if let Some(replacements) = table.get("replace").and_then(toml::Value::as_table) {
            self.dependencies(declaring, base, "replace", replacements);
        }
    }

    fn members(&mut self, declaring: &Path, base: &Path, key: &str, value: &toml::Value) {
        let Some(members) = value.as_array() else {
            self.diagnostics
                .push(format!("{}: {key} must be an array", declaring.display()));
            return;
        };
        for member in members {
            let Some(pattern) = member.as_str() else {
                self.diagnostics.push(format!(
                    "{}: {key} member must be a string",
                    declaring.display()
                ));
                continue;
            };
            if !contains_glob(pattern) {
                self.reference(declaring, base, key, member, SelectedCargoPathKind::Package);
                continue;
            }
            let result = self.member_pattern(base, pattern);
            match result {
                Ok(paths) => {
                    for path in paths {
                        self.reference(
                            declaring,
                            &path,
                            key,
                            &toml::Value::String(".".into()),
                            SelectedCargoPathKind::Package,
                        );
                    }
                }
                Err(error) => self.diagnostics.push(format!(
                    "{}: {key}={pattern:?}: {error}",
                    declaring.display()
                )),
            }
        }
    }

    fn member_pattern(&self, base: &Path, pattern: &str) -> Result<BTreeSet<PathBuf>, String> {
        if pattern.contains('[') || pattern.contains("**") {
            return Err("unsupported workspace glob; explicit selected members required".into());
        }
        let components = Self::components(pattern)?;
        let mut candidates = BTreeSet::from([base.to_path_buf()]);
        for component in components {
            let mut next = BTreeSet::new();
            for candidate in candidates {
                if contains_wildcard(&component) {
                    for path in self.directories.iter().chain(self.entries.keys()) {
                        if path.parent() == Some(candidate.as_path())
                            && let Some(name) = path.file_name().and_then(|name| name.to_str())
                            && wildcard_match(&component, name)
                        {
                            next.insert(self.resolve(&candidate, name)?);
                        }
                    }
                } else if component.is_empty() {
                    next.insert(candidate);
                } else {
                    next.insert(self.resolve(&candidate, &component)?);
                }
            }
            candidates = next;
        }
        if candidates.is_empty() {
            return Err("workspace glob matches no selected members".into());
        }
        Ok(candidates)
    }

    fn manifest(&mut self, declaring: &Path, table: &toml::Table) {
        let base = declaring.parent().unwrap_or(Path::new(""));
        if Self::inherits_workspace(&toml::Value::Table(table.clone())) {
            let workspace = self.selected_workspace(declaring, table);
            if let Err(error) = workspace {
                self.diagnostics.push(format!(
                    "{}: workspace inheritance: {error}",
                    declaring.display()
                ));
            }
        }
        self.dependency_tables(declaring, base, "", table);
        self.overrides(declaring, base, table);
        if let Some(targets) = table.get("target").and_then(toml::Value::as_table) {
            for (name, target) in targets {
                if let Some(target) = target.as_table() {
                    self.dependency_tables(declaring, base, &format!("target.{name}."), target);
                }
            }
        }
        if let Some(workspace) = table.get("workspace").and_then(toml::Value::as_table) {
            self.dependency_tables(declaring, base, "workspace.", workspace);
            for key in ["members", "default-members"] {
                if let Some(value) = workspace.get(key) {
                    self.members(declaring, base, &format!("workspace.{key}"), value);
                }
            }
        }
        if let Some(package) = table.get("package").and_then(toml::Value::as_table) {
            if let Some(workspace) = package.get("workspace") {
                self.reference(
                    declaring,
                    base,
                    "package.workspace",
                    workspace,
                    SelectedCargoPathKind::Package,
                );
            }
            if let Some(build) = package.get("build") {
                match build {
                    toml::Value::Boolean(false) => {}
                    toml::Value::Boolean(true) => self.reference(
                        declaring,
                        base,
                        "package.build",
                        &toml::Value::String("build.rs".into()),
                        SelectedCargoPathKind::File,
                    ),
                    _ => self.reference(
                        declaring,
                        base,
                        "package.build",
                        build,
                        SelectedCargoPathKind::File,
                    ),
                }
            }
        }
        if let Some(path) = table
            .get("lib")
            .and_then(toml::Value::as_table)
            .and_then(|lib| lib.get("path"))
        {
            self.reference(
                declaring,
                base,
                "lib.path",
                path,
                SelectedCargoPathKind::File,
            );
        }
        for kind in ["bin", "test", "bench", "example"] {
            if let Some(targets) = table.get(kind).and_then(toml::Value::as_array) {
                for target in targets {
                    if let Some(path) = target.as_table().and_then(|target| target.get("path")) {
                        self.reference(
                            declaring,
                            base,
                            &format!("{kind}.path"),
                            path,
                            SelectedCargoPathKind::File,
                        );
                    }
                }
            }
        }
    }

    fn inherits_workspace(value: &toml::Value) -> bool {
        match value {
            toml::Value::Table(table) => {
                table.get("workspace").and_then(toml::Value::as_bool) == Some(true)
                    || table.values().any(Self::inherits_workspace)
            }
            toml::Value::Array(values) => values.iter().any(Self::inherits_workspace),
            _ => false,
        }
    }

    fn selected_workspace(&self, declaring: &Path, table: &toml::Table) -> Result<(), String> {
        let base = declaring.parent().unwrap_or(Path::new(""));
        let explicit = table
            .get("package")
            .and_then(toml::Value::as_table)
            .and_then(|package| package.get("workspace"));
        let candidates = if let Some(explicit) = explicit {
            let path = explicit
                .as_str()
                .ok_or_else(|| "package.workspace must be a path string".to_string())?;
            vec![self.resolve(base, path)?]
        } else {
            base.ancestors().map(Path::to_path_buf).collect()
        };
        for candidate in candidates {
            let manifest = candidate.join("Cargo.toml");
            if !self.entries.contains_key(&manifest) {
                continue;
            }
            let resolved = self.resolve(&candidate, "Cargo.toml")?;
            let Some(SelectedCargoEntry::File(Some(text))) = self.entries.get(&resolved) else {
                return Err(format!(
                    "selected workspace text missing: {}",
                    manifest.display()
                ));
            };
            let document = toml::from_str::<toml::Table>(text)
                .map_err(|error| format!("invalid workspace {}: {error}", manifest.display()))?;
            if document.get("workspace").is_some_and(toml::Value::is_table) {
                return Ok(());
            }
        }
        Err("no selected enclosing workspace; ambient ancestor lookup is not admitted".into())
    }

    fn config(&mut self, declaring: &Path, table: &toml::Table) {
        let base = declaring
            .parent()
            .and_then(Path::parent)
            .unwrap_or(Path::new(""));
        self.config_at(declaring, base, table);
    }

    fn config_at(&mut self, declaring: &Path, base: &Path, table: &toml::Table) {
        self.overrides(declaring, base, table);
        if table.contains_key("include") {
            self.diagnostics.push(format!(
                "{}: config includes are not admitted in a selected tree",
                declaring.display()
            ));
        }
        if let Some(paths) = table.get("paths") {
            if let Some(paths) = paths.as_array() {
                for path in paths {
                    self.reference(
                        declaring,
                        base,
                        "paths",
                        path,
                        SelectedCargoPathKind::Package,
                    );
                }
            } else {
                self.diagnostics.push(format!(
                    "{}: config paths must be an array",
                    declaring.display()
                ));
            }
        }
        if let Some(sources) = table.get("source").and_then(toml::Value::as_table) {
            for (name, source) in sources {
                for key in ["directory", "local-registry"] {
                    if let Some(path) = source.as_table().and_then(|source| source.get(key)) {
                        self.reference(
                            declaring,
                            base,
                            &format!("source.{name}.{key}"),
                            path,
                            SelectedCargoPathKind::Directory,
                        );
                    }
                }
            }
        }
    }
}

/// Resolve local Cargo path dependencies for `entrypoint` using the default topology policy.
pub fn resolve_cargo_path_dependency_graph(
    entrypoint: &Path,
) -> Result<CargoPathDependencyGraph, CargoPathDependencyError> {
    resolve_cargo_path_dependency_graph_with_policy(entrypoint, &PathTopologyPolicy::default())
}

/// Resolve local Cargo path dependencies for `entrypoint` with explicit topology policy.
pub fn resolve_cargo_path_dependency_graph_with_policy(
    entrypoint: &Path,
    policy: &PathTopologyPolicy,
) -> Result<CargoPathDependencyGraph, CargoPathDependencyError> {
    resolve_cargo_path_dependency_graph_with_policy_and_provider(
        entrypoint,
        policy,
        invoke_cargo_metadata,
    )
}

/// Resolve every local Cargo package that may need source materialization using
/// the default topology policy.
pub fn resolve_cargo_path_materialization_closure(
    entrypoint: &Path,
) -> Result<CargoPathMaterializationClosure, CargoPathDependencyError> {
    resolve_cargo_path_materialization_closure_with_policy(
        entrypoint,
        &PathTopologyPolicy::default(),
    )
}

/// Resolve every local Cargo package that may need source materialization using
/// an explicit topology policy.
///
/// Resolution is manifest-only by design: it never imports user-home Cargo
/// configuration, and it includes inactive edges that `cargo metadata` omits.
pub fn resolve_cargo_path_materialization_closure_with_policy(
    entrypoint: &Path,
    policy: &PathTopologyPolicy,
) -> Result<CargoPathMaterializationClosure, CargoPathDependencyError> {
    let entry_manifest = resolve_entry_manifest(entrypoint, policy)?;
    resolve_materialization_from_manifests(&entry_manifest, policy)
}

fn resolve_cargo_path_dependency_graph_with_policy_and_provider<F>(
    entrypoint: &Path,
    policy: &PathTopologyPolicy,
    metadata_provider: F,
) -> Result<CargoPathDependencyGraph, CargoPathDependencyError>
where
    F: Fn(&Path) -> Result<String, CargoPathDependencyError>,
{
    resolve_cargo_path_dependency_graph_with_cargo_home(
        entrypoint,
        policy,
        metadata_provider,
        default_cargo_home().as_deref(),
    )
}

/// The Cargo home `cargo metadata` resolves against: `$CARGO_HOME`, else
/// `~/.cargo` (cargo's own default), canonicalized when it exists so it
/// compares against canonical package roots.
fn default_cargo_home() -> Option<PathBuf> {
    let cargo_home = std::env::var_os("CARGO_HOME")
        .filter(|value| !value.is_empty())
        .map(PathBuf::from)
        .or_else(|| dirs::home_dir().map(|home| home.join(".cargo")))?;
    Some(cargo_home.canonicalize().unwrap_or(cargo_home))
}

fn resolve_cargo_path_dependency_graph_with_cargo_home<F>(
    entrypoint: &Path,
    policy: &PathTopologyPolicy,
    metadata_provider: F,
    cargo_home: Option<&Path>,
) -> Result<CargoPathDependencyGraph, CargoPathDependencyError>
where
    F: Fn(&Path) -> Result<String, CargoPathDependencyError>,
{
    let entry_manifest = resolve_entry_manifest(entrypoint, policy)?;

    match resolve_from_metadata(&entry_manifest, policy, &metadata_provider, cargo_home) {
        Ok(graph) => Ok(graph),
        Err(metadata_error) => match resolve_from_manifest_fallback(&entry_manifest, policy) {
            Ok(graph) => Ok(graph),
            Err(mut error) => {
                error.push_diagnostic(format!("metadata phase failure: {metadata_error}"));
                if !metadata_error.diagnostics().is_empty() {
                    error.push_diagnostic("metadata diagnostics follow".to_string());
                    error
                        .diagnostics
                        .extend(metadata_error.diagnostics().iter().cloned());
                }
                Err(error)
            }
        },
    }
}

fn resolve_entry_manifest(
    entrypoint: &Path,
    policy: &PathTopologyPolicy,
) -> Result<PathBuf, CargoPathDependencyError> {
    let maybe_manifest = entrypoint
        .file_name()
        .is_some_and(|name| name == "Cargo.toml");
    let root_candidate = if maybe_manifest {
        entrypoint.parent().ok_or_else(|| {
            CargoPathDependencyError::new(
                CargoPathDependencyErrorKind::ManifestParseFailure,
                format!("invalid manifest path: {}", entrypoint.display()),
            )
        })?
    } else {
        entrypoint
    };

    let normalized_root = normalize_path_for_policy(
        root_candidate,
        policy,
        None,
        None,
        "resolve entrypoint root",
    )?;
    let manifest_path = normalized_root.join("Cargo.toml");
    if !manifest_path.is_file() {
        return Err(CargoPathDependencyError::new(
            CargoPathDependencyErrorKind::ManifestParseFailure,
            format!("manifest does not exist: {}", manifest_path.display()),
        )
        .with_manifest_path(manifest_path));
    }

    Ok(manifest_path)
}

/// Maximum time to wait for `cargo metadata` before killing the process.
const CARGO_METADATA_TIMEOUT: std::time::Duration = std::time::Duration::from_secs(30);

fn invoke_cargo_metadata(manifest_path: &Path) -> Result<String, CargoPathDependencyError> {
    use std::io::Read;

    // `--locked` is load-bearing (bd-rch-pinned-metadata-lock-ytkda): without
    // it, `cargo metadata` creates or rewrites the project's `Cargo.lock` as
    // a side effect, mutating the very checkout RCH is only supposed to
    // read. With `--locked`, a valid lockfile succeeds byte-for-byte
    // untouched, while a stale or missing lockfile makes cargo REFUSE
    // without writing — and that refusal flows into the manifest-only
    // fallback, which is non-mutating by construction.
    let mut child = Command::new("cargo")
        .arg("metadata")
        .arg("--locked")
        .arg("--format-version")
        .arg("1")
        .arg("--manifest-path")
        .arg(manifest_path)
        .stdout(std::process::Stdio::piped())
        .stderr(std::process::Stdio::piped())
        .spawn()
        .map_err(|error| {
            CargoPathDependencyError::new(
                CargoPathDependencyErrorKind::MetadataInvocationFailure,
                format!("failed to spawn cargo metadata: {error}"),
            )
            .with_manifest_path(manifest_path)
        })?;

    // Drain stdout and stderr concurrently in background threads.
    //
    // The previous implementation polled `try_wait` without ever reading from
    // the pipes, which deadlocked for any project whose `cargo metadata` JSON
    // exceeded the OS pipe capacity (~64KB on Linux). The child blocked on
    // `write()` to a full pipe, never exited, and we always hit the 30s
    // timeout. The RCH workspace itself emits ~2.5MB of metadata, so this
    // function timed out for *its own callers*. Concurrent draining keeps
    // the pipe flowing so the child can complete normally; on timeout we
    // still kill+reap below, after which the drain threads see EOF and exit.
    let mut stdout_pipe = child
        .stdout
        .take()
        .expect("child spawned with piped stdout");
    let mut stderr_pipe = child
        .stderr
        .take()
        .expect("child spawned with piped stderr");

    let stdout_thread = std::thread::spawn(move || -> std::io::Result<Vec<u8>> {
        let mut buf = Vec::new();
        stdout_pipe.read_to_end(&mut buf)?;
        Ok(buf)
    });
    let stderr_thread = std::thread::spawn(move || -> std::io::Result<Vec<u8>> {
        let mut buf = Vec::new();
        stderr_pipe.read_to_end(&mut buf)?;
        Ok(buf)
    });

    // Poll `try_wait` with a small sleep. On timeout we kill the child and
    // reap it so the process + OS resources don't leak.
    let deadline = std::time::Instant::now() + CARGO_METADATA_TIMEOUT;
    loop {
        match child.try_wait() {
            Ok(Some(_)) => break,
            Ok(None) => {
                if std::time::Instant::now() >= deadline {
                    let kill_err = child.kill().err();
                    let reap_deadline =
                        std::time::Instant::now() + std::time::Duration::from_secs(2);
                    let reaped = loop {
                        match child.try_wait() {
                            Ok(Some(_)) => break true,
                            Ok(None) => {
                                if std::time::Instant::now() >= reap_deadline {
                                    break false;
                                }
                                std::thread::sleep(std::time::Duration::from_millis(20));
                            }
                            Err(_) => break false,
                        }
                    };
                    // Reap the drain threads now that the pipes are closed
                    // (kill closed them, or EOF arrived). Discard their output
                    // — we have a timeout error to return either way.
                    let _ = stdout_thread.join();
                    let _ = stderr_thread.join();

                    let mut err = CargoPathDependencyError::new(
                        CargoPathDependencyErrorKind::MetadataInvocationFailure,
                        format!(
                            "cargo metadata timed out after {}s for {}",
                            CARGO_METADATA_TIMEOUT.as_secs(),
                            manifest_path.display()
                        ),
                    )
                    .with_manifest_path(manifest_path)
                    .with_diagnostic(format!("timeout_secs={}", CARGO_METADATA_TIMEOUT.as_secs()));
                    if let Some(ke) = kill_err {
                        err = err.with_diagnostic(format!("kill_failed={ke}"));
                    }
                    if !reaped {
                        err = err.with_diagnostic("reap_failed=true".to_string());
                    }
                    return Err(err);
                }
                std::thread::sleep(std::time::Duration::from_millis(50));
            }
            Err(error) => {
                let _ = child.kill();
                let _ = child.wait();
                let _ = stdout_thread.join();
                let _ = stderr_thread.join();
                return Err(CargoPathDependencyError::new(
                    CargoPathDependencyErrorKind::MetadataInvocationFailure,
                    format!("failed to poll cargo metadata: {error}"),
                )
                .with_manifest_path(manifest_path));
            }
        }
    }

    let status = child.wait().map_err(|error| {
        CargoPathDependencyError::new(
            CargoPathDependencyErrorKind::MetadataInvocationFailure,
            format!("failed to wait on cargo metadata: {error}"),
        )
        .with_manifest_path(manifest_path)
    })?;

    let stdout_bytes = stdout_thread
        .join()
        .map_err(|_| {
            CargoPathDependencyError::new(
                CargoPathDependencyErrorKind::MetadataInvocationFailure,
                "stdout drain thread panicked".to_string(),
            )
            .with_manifest_path(manifest_path)
        })?
        .map_err(|error| {
            CargoPathDependencyError::new(
                CargoPathDependencyErrorKind::MetadataInvocationFailure,
                format!("failed to read cargo metadata stdout: {error}"),
            )
            .with_manifest_path(manifest_path)
        })?;
    let stderr_bytes = stderr_thread
        .join()
        .map_err(|_| {
            CargoPathDependencyError::new(
                CargoPathDependencyErrorKind::MetadataInvocationFailure,
                "stderr drain thread panicked".to_string(),
            )
            .with_manifest_path(manifest_path)
        })?
        .map_err(|error| {
            CargoPathDependencyError::new(
                CargoPathDependencyErrorKind::MetadataInvocationFailure,
                format!("failed to read cargo metadata stderr: {error}"),
            )
            .with_manifest_path(manifest_path)
        })?;

    if !status.success() {
        let stderr = String::from_utf8_lossy(&stderr_bytes).to_string();
        let detail = if stderr.trim().is_empty() {
            format!("cargo metadata exited with status {status}")
        } else {
            stderr.trim().to_string()
        };
        return Err(CargoPathDependencyError::new(
            CargoPathDependencyErrorKind::MetadataInvocationFailure,
            detail,
        )
        .with_manifest_path(manifest_path));
    }

    String::from_utf8(stdout_bytes).map_err(|error| {
        CargoPathDependencyError::new(
            CargoPathDependencyErrorKind::MetadataParseFailure,
            format!("metadata stdout is not valid UTF-8: {error}"),
        )
        .with_manifest_path(manifest_path)
    })
}

#[derive(Debug, Default)]
struct PartialGraph {
    workspace_root: Option<PathBuf>,
    roots: BTreeSet<PathBuf>,
    packages: BTreeMap<PathBuf, PackageRecord>,
    adjacency: BTreeMap<PathBuf, BTreeSet<EdgeTail>>,
}

impl PartialGraph {
    fn add_root(&mut self, root: PathBuf) {
        self.roots.insert(root);
    }

    fn add_package(
        &mut self,
        package_root: PathBuf,
        manifest_path: PathBuf,
        package_name: String,
        workspace_member: bool,
    ) {
        self.packages
            .entry(package_root.clone())
            .and_modify(|existing| {
                if existing.package_name == default_package_name(&package_root)
                    && package_name != existing.package_name
                {
                    existing.package_name = package_name.clone();
                }
                existing.workspace_member |= workspace_member;
                existing.manifest_path = manifest_path.clone();
            })
            .or_insert(PackageRecord {
                manifest_path,
                package_name,
                workspace_member,
            });
        self.adjacency.entry(package_root).or_default();
    }

    fn add_edge(&mut self, from: PathBuf, to: PathBuf, dependency_name: String) {
        self.adjacency.entry(from).or_default().insert(EdgeTail {
            to,
            dependency_name,
        });
    }
}

#[derive(Debug, Clone)]
struct PackageRecord {
    manifest_path: PathBuf,
    package_name: String,
    workspace_member: bool,
}

#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
struct EdgeTail {
    to: PathBuf,
    dependency_name: String,
}

#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
struct EdgeRecord {
    from: PathBuf,
    to: PathBuf,
    dependency_name: String,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum VisitState {
    Visiting,
    Visited,
}

fn finalize_graph(
    entry_manifest_path: PathBuf,
    partial: PartialGraph,
) -> Result<CargoPathDependencyGraph, CargoPathDependencyError> {
    let mut states: BTreeMap<PathBuf, VisitState> = BTreeMap::new();
    let mut stack: Vec<PathBuf> = Vec::new();
    let mut reachable_nodes: BTreeSet<PathBuf> = BTreeSet::new();
    let mut reachable_edges: BTreeSet<EdgeRecord> = BTreeSet::new();

    for root in &partial.roots {
        traverse_for_reachable(
            root,
            &partial.adjacency,
            &mut states,
            &mut stack,
            &mut reachable_nodes,
            &mut reachable_edges,
        )?;
    }

    let packages = reachable_nodes
        .iter()
        .map(|root| {
            if let Some(package) = partial.packages.get(root) {
                CargoPathDependencyPackage {
                    package_root: root.clone(),
                    manifest_path: package.manifest_path.clone(),
                    package_name: package.package_name.clone(),
                    workspace_member: package.workspace_member,
                }
            } else {
                CargoPathDependencyPackage {
                    package_root: root.clone(),
                    manifest_path: root.join("Cargo.toml"),
                    package_name: default_package_name(root),
                    workspace_member: partial.roots.contains(root),
                }
            }
        })
        .collect::<Vec<_>>();

    let edges = reachable_edges
        .into_iter()
        .map(|edge| CargoPathDependencyEdge {
            from: edge.from,
            to: edge.to,
            dependency_name: edge.dependency_name,
        })
        .collect::<Vec<_>>();

    Ok(CargoPathDependencyGraph {
        entry_manifest_path,
        workspace_root: partial.workspace_root,
        root_packages: partial.roots.into_iter().collect(),
        packages,
        edges,
    })
}

fn traverse_for_reachable(
    node: &Path,
    adjacency: &BTreeMap<PathBuf, BTreeSet<EdgeTail>>,
    states: &mut BTreeMap<PathBuf, VisitState>,
    stack: &mut Vec<PathBuf>,
    reachable_nodes: &mut BTreeSet<PathBuf>,
    reachable_edges: &mut BTreeSet<EdgeRecord>,
) -> Result<(), CargoPathDependencyError> {
    match states.get(node).copied() {
        Some(VisitState::Visited) => return Ok(()),
        Some(VisitState::Visiting) => {
            let cycle = cycle_from_stack(stack, node);
            return Err(CargoPathDependencyError::new(
                CargoPathDependencyErrorKind::CyclicDependency,
                "cycle detected while traversing dependency graph",
            )
            .with_cycle(cycle));
        }
        None => {}
    }

    states.insert(node.to_path_buf(), VisitState::Visiting);
    stack.push(node.to_path_buf());
    reachable_nodes.insert(node.to_path_buf());

    if let Some(edges) = adjacency.get(node) {
        for edge in edges {
            reachable_edges.insert(EdgeRecord {
                from: node.to_path_buf(),
                to: edge.to.clone(),
                dependency_name: edge.dependency_name.clone(),
            });
            if states.get(&edge.to) == Some(&VisitState::Visiting) {
                let cycle = cycle_from_stack(stack, &edge.to);
                return Err(CargoPathDependencyError::new(
                    CargoPathDependencyErrorKind::CyclicDependency,
                    format!(
                        "cycle detected between {} and {}",
                        node.display(),
                        edge.to.display()
                    ),
                )
                .with_cycle(cycle));
            }
            traverse_for_reachable(
                &edge.to,
                adjacency,
                states,
                stack,
                reachable_nodes,
                reachable_edges,
            )?;
        }
    }

    stack.pop();
    states.insert(node.to_path_buf(), VisitState::Visited);
    Ok(())
}

fn cycle_from_stack(stack: &[PathBuf], terminal: &Path) -> Vec<PathBuf> {
    if let Some(position) = stack.iter().position(|entry| entry == terminal) {
        let mut cycle = stack[position..].to_vec();
        cycle.push(terminal.to_path_buf());
        cycle
    } else {
        vec![terminal.to_path_buf()]
    }
}

fn default_package_name(root: &Path) -> String {
    root.file_name()
        .and_then(|segment| segment.to_str())
        .map(ToOwned::to_owned)
        .unwrap_or_else(|| root.display().to_string())
}

fn allowed_dependency_roots(policy: &PathTopologyPolicy) -> Vec<PathBuf> {
    let mut roots = vec![
        policy.canonical_root().to_path_buf(),
        policy.alias_root().to_path_buf(),
    ];

    for candidate in [policy.canonical_root(), policy.alias_root()] {
        if let Ok(resolved) = std::fs::canonicalize(candidate)
            && !roots.iter().any(|root| root == &resolved)
        {
            roots.push(resolved);
        }
    }

    roots
}

fn validate_absolute_dependency_scope(
    dependency_candidate: &Path,
    policy: &PathTopologyPolicy,
    manifest_path: &Path,
    dependency_name: &str,
    context: &str,
) -> Result<(), CargoPathDependencyError> {
    if !dependency_candidate.is_absolute() {
        return Ok(());
    }
    if normalize_project_path_with_policy(dependency_candidate, policy).is_ok() {
        return Ok(());
    }

    let allowed_roots = allowed_dependency_roots(policy);
    if allowed_roots
        .iter()
        .any(|root| dependency_candidate.starts_with(root))
    {
        return Ok(());
    }

    let mut error = CargoPathDependencyError::new(
        CargoPathDependencyErrorKind::PathPolicyViolation,
        format!("{context}: {}", dependency_candidate.display()),
    )
    .with_manifest_path(manifest_path)
    .with_dependency_name(dependency_name.to_string())
    .with_dependency_path(dependency_candidate.to_path_buf());

    for root in &allowed_roots {
        error = error.with_diagnostic(format!("allowed root: {}", root.display()));
    }

    Err(error)
}

fn normalize_path_for_policy(
    path: &Path,
    policy: &PathTopologyPolicy,
    manifest_path: Option<&Path>,
    dependency_name: Option<&str>,
    context: &str,
) -> Result<PathBuf, CargoPathDependencyError> {
    normalize_project_path_with_policy(path, policy)
        .map(|normalized| normalized.canonical_path().to_path_buf())
        .map_err(|error| {
            let mapped_kind = if error.kind() == &PathNormalizationErrorKind::InputResolveFailed {
                CargoPathDependencyErrorKind::MissingPathDependency
            } else {
                CargoPathDependencyErrorKind::PathPolicyViolation
            };
            let mut mapped = CargoPathDependencyError::new(
                mapped_kind,
                format!("{context}: {} ({})", error.kind(), error.detail()),
            )
            .with_diagnostic(format!("normalization_error_kind={}", error.kind()))
            .with_diagnostic(format!("normalization_detail={}", error.detail()))
            .with_diagnostics(error.decision_trace().iter().map(ToString::to_string));

            if let Some(manifest_path) = manifest_path {
                mapped = mapped.with_manifest_path(manifest_path);
            }
            if let Some(dependency_name) = dependency_name {
                mapped = mapped.with_dependency_name(dependency_name.to_string());
            }
            mapped.with_dependency_path(path)
        })
}

#[derive(Debug, Deserialize)]
struct MetadataDocument {
    #[serde(default)]
    packages: Vec<MetadataPackage>,
    #[serde(default)]
    workspace_members: Vec<String>,
    workspace_root: Option<String>,
    resolve: Option<MetadataResolve>,
}

#[derive(Debug, Deserialize)]
struct MetadataResolve {
    root: Option<String>,
    #[serde(default)]
    nodes: Vec<MetadataResolveNode>,
}

#[derive(Debug, Deserialize)]
struct MetadataResolveNode {
    id: String,
    #[serde(default)]
    deps: Vec<MetadataResolveDep>,
}

#[derive(Debug, Deserialize)]
struct MetadataResolveDep {
    name: String,
    pkg: String,
    #[serde(default)]
    dep_kinds: Vec<MetadataResolveDepKind>,
}

#[derive(Debug, Deserialize)]
struct MetadataResolveDepKind {
    kind: Option<String>,
}

impl MetadataResolveDep {
    fn is_runtime_relevant(&self) -> bool {
        if self.dep_kinds.is_empty() {
            return true;
        }

        self.dep_kinds
            .iter()
            .any(|dep_kind| dep_kind.kind.as_deref() != Some("dev"))
    }
}

#[derive(Debug, Deserialize)]
struct MetadataPackage {
    id: String,
    name: String,
    manifest_path: String,
    /// `null` for local path packages; `registry+…` / `git+…` otherwise.
    /// Vendored (`[source] directory`) crates keep their original source id.
    #[serde(default)]
    source: Option<String>,
    #[serde(default)]
    dependencies: Vec<MetadataDependency>,
}

#[derive(Debug, Deserialize)]
struct MetadataDependency {
    name: String,
    path: Option<String>,
    #[serde(default)]
    optional: bool,
}

#[derive(Debug)]
struct MetadataPackageRecord {
    package_id: String,
    package_root: PathBuf,
    manifest_path: PathBuf,
    dependencies: Vec<MetadataDependency>,
}

fn resolve_from_metadata<F>(
    entry_manifest_path: &Path,
    policy: &PathTopologyPolicy,
    metadata_provider: &F,
    cargo_home: Option<&Path>,
) -> Result<CargoPathDependencyGraph, CargoPathDependencyError>
where
    F: Fn(&Path) -> Result<String, CargoPathDependencyError>,
{
    let raw_metadata = metadata_provider(entry_manifest_path)?;
    let metadata = serde_json::from_str::<MetadataDocument>(&raw_metadata).map_err(|error| {
        CargoPathDependencyError::new(
            CargoPathDependencyErrorKind::MetadataParseFailure,
            format!("failed to parse cargo metadata JSON: {error}"),
        )
        .with_manifest_path(entry_manifest_path)
    })?;

    let mut partial = PartialGraph::default();
    let workspace_member_ids = metadata
        .workspace_members
        .iter()
        .cloned()
        .collect::<BTreeSet<_>>();
    let mut id_to_root: BTreeMap<String, PathBuf> = BTreeMap::new();
    let mut package_records: Vec<MetadataPackageRecord> = Vec::new();

    for package in metadata.packages {
        let manifest_path = PathBuf::from(&package.manifest_path);
        let manifest_dir = manifest_path.parent().ok_or_else(|| {
            CargoPathDependencyError::new(
                CargoPathDependencyErrorKind::MetadataParseFailure,
                format!(
                    "metadata package has invalid manifest path: {}",
                    manifest_path.display()
                ),
            )
            .with_manifest_path(entry_manifest_path)
        })?;
        let workspace_member = workspace_member_ids.contains(&package.id);
        let package_root = match normalize_path_for_policy(
            manifest_dir,
            policy,
            Some(entry_manifest_path),
            None,
            "normalize metadata package root",
        ) {
            Ok(root) => root,
            Err(error)
                if !workspace_member
                    && error.kind() == &CargoPathDependencyErrorKind::PathPolicyViolation =>
            {
                continue;
            }
            Err(error) => return Err(error),
        };
        // Registry and git packages unpacked into Cargo's own caches are not
        // local inputs: the worker resolves them through its own isolated
        // CARGO_HOME. They only look local when CARGO_HOME happens to sit under
        // the topology root (e.g. `canonical_root = $HOME`), so exclude them
        // explicitly (issue #77). Sourced packages elsewhere — vendored
        // `[source] directory` trees — stay in the closure.
        if !workspace_member
            && package.source.is_some()
            && cargo_home.is_some_and(|cargo_home| package_root.starts_with(cargo_home))
        {
            continue;
        }
        let canonical_manifest_path = package_root.join("Cargo.toml");

        partial.add_package(
            package_root.clone(),
            canonical_manifest_path.clone(),
            package.name.clone(),
            workspace_member,
        );

        id_to_root.insert(package.id.clone(), package_root.clone());
        package_records.push(MetadataPackageRecord {
            package_id: package.id,
            package_root,
            manifest_path: canonical_manifest_path,
            dependencies: package.dependencies,
        });
    }

    let resolve_nodes = metadata
        .resolve
        .as_ref()
        .map(|resolve| {
            resolve
                .nodes
                .iter()
                .map(|node| (node.id.clone(), node))
                .collect::<BTreeMap<_, _>>()
        })
        .unwrap_or_default();

    for package in &package_records {
        if let Some(node) = resolve_nodes.get(&package.package_id) {
            for dependency in &node.deps {
                if !dependency.is_runtime_relevant() {
                    continue;
                }
                let Some(dependency_root) = id_to_root.get(&dependency.pkg) else {
                    continue;
                };
                let dependency_manifest = dependency_root.join("Cargo.toml");
                partial.add_package(
                    dependency_root.clone(),
                    dependency_manifest,
                    dependency.name.clone(),
                    false,
                );
                partial.add_edge(
                    package.package_root.clone(),
                    dependency_root.clone(),
                    dependency.name.clone(),
                );
            }
            continue;
        }

        for dependency in &package.dependencies {
            if dependency.optional {
                continue;
            }
            let Some(raw_path) = dependency.path.as_deref() else {
                continue;
            };

            let dependency_candidate =
                resolve_dependency_candidate(&package.package_root, raw_path);
            validate_absolute_dependency_scope(
                &dependency_candidate,
                policy,
                &package.manifest_path,
                &dependency.name,
                "metadata dependency path policy violation",
            )?;
            if !dependency_candidate.exists() {
                return Err(CargoPathDependencyError::new(
                    CargoPathDependencyErrorKind::MissingPathDependency,
                    format!(
                        "metadata dependency path does not exist: {}",
                        dependency_candidate.display()
                    ),
                )
                .with_manifest_path(package.manifest_path.clone())
                .with_dependency_name(dependency.name.clone())
                .with_dependency_path(dependency_candidate));
            }

            let dependency_root = normalize_path_for_policy(
                &dependency_candidate,
                policy,
                Some(&package.manifest_path),
                Some(&dependency.name),
                "normalize metadata dependency path",
            )?;
            let dependency_manifest = dependency_root.join("Cargo.toml");
            if !dependency_manifest.is_file() {
                return Err(CargoPathDependencyError::new(
                    CargoPathDependencyErrorKind::MissingPathDependency,
                    format!(
                        "dependency manifest is missing: {}",
                        dependency_manifest.display()
                    ),
                )
                .with_manifest_path(package.manifest_path.clone())
                .with_dependency_name(dependency.name.clone())
                .with_dependency_path(dependency_manifest));
            }

            partial.add_package(
                dependency_root.clone(),
                dependency_manifest,
                dependency.name.clone(),
                false,
            );
            partial.add_edge(
                package.package_root.clone(),
                dependency_root,
                dependency.name.clone(),
            );
        }
    }

    if let Some(workspace_root) = metadata.workspace_root {
        let workspace_root = normalize_path_for_policy(
            Path::new(&workspace_root),
            policy,
            Some(entry_manifest_path),
            None,
            "normalize metadata workspace root",
        )?;
        partial.workspace_root = Some(workspace_root);
    }

    if !workspace_member_ids.is_empty() {
        for workspace_id in &workspace_member_ids {
            let root = id_to_root.get(workspace_id).ok_or_else(|| {
                CargoPathDependencyError::new(
                    CargoPathDependencyErrorKind::MetadataParseFailure,
                    format!("workspace member id missing from package list: {workspace_id}"),
                )
                .with_manifest_path(entry_manifest_path)
            })?;
            partial.add_root(root.clone());
            if let Some(package) = partial.packages.get_mut(root) {
                package.workspace_member = true;
            }
        }
    } else if let Some(resolve_root) = metadata.resolve.and_then(|resolve| resolve.root) {
        let root = id_to_root.get(&resolve_root).ok_or_else(|| {
            CargoPathDependencyError::new(
                CargoPathDependencyErrorKind::MetadataParseFailure,
                format!("resolve root id missing from package list: {resolve_root}"),
            )
            .with_manifest_path(entry_manifest_path)
        })?;
        partial.add_root(root.clone());
    } else {
        let entry_root = entry_manifest_path.parent().ok_or_else(|| {
            CargoPathDependencyError::new(
                CargoPathDependencyErrorKind::MetadataParseFailure,
                format!(
                    "entry manifest has no parent: {}",
                    entry_manifest_path.display()
                ),
            )
            .with_manifest_path(entry_manifest_path)
        })?;
        partial.add_root(entry_root.to_path_buf());
    }

    for root in partial.roots.clone() {
        partial
            .packages
            .entry(root.clone())
            .or_insert(PackageRecord {
                manifest_path: root.join("Cargo.toml"),
                package_name: default_package_name(&root),
                workspace_member: true,
            });
    }

    finalize_graph(entry_manifest_path.to_path_buf(), partial)
}

#[derive(Debug, Clone)]
struct ManifestDocument {
    package_name: Option<String>,
    has_workspace: bool,
    workspace_members: Vec<String>,
    workspace_dependency_names: BTreeSet<String>,
    workspace_path_dependencies: BTreeMap<String, String>,
    patch_path_dependencies: BTreeMap<String, String>,
    path_dependencies: Vec<ManifestDependency>,
    materialization_path_dependencies: Vec<ManifestDependency>,
}

#[derive(Debug, Clone)]
struct ManifestDependency {
    dependency_name: String,
    dependency_path: Option<String>,
    uses_workspace_inheritance: bool,
}

fn resolve_from_manifest_fallback(
    entry_manifest_path: &Path,
    policy: &PathTopologyPolicy,
) -> Result<CargoPathDependencyGraph, CargoPathDependencyError> {
    let entry_manifest = read_manifest_document(entry_manifest_path)?;
    let entry_root = entry_manifest_path.parent().ok_or_else(|| {
        CargoPathDependencyError::new(
            CargoPathDependencyErrorKind::ManifestParseFailure,
            format!(
                "entry manifest has no parent: {}",
                entry_manifest_path.display()
            ),
        )
        .with_manifest_path(entry_manifest_path)
    })?;
    let entry_root = normalize_path_for_policy(
        entry_root,
        policy,
        Some(entry_manifest_path),
        None,
        "normalize fallback entry root",
    )?;

    let mut partial = PartialGraph::default();
    if entry_manifest.has_workspace {
        partial.workspace_root = Some(entry_root.clone());
    }
    let workspace_path_dependencies = entry_manifest.workspace_path_dependencies.clone();
    let patch_path_dependencies = entry_manifest.patch_path_dependencies.clone();

    let workspace_member_manifests = expand_workspace_members(
        &entry_root,
        &entry_manifest.workspace_members,
        entry_manifest_path,
    )?;
    let workspace_member_set = workspace_member_manifests
        .iter()
        .cloned()
        .collect::<BTreeSet<_>>();
    let include_entry_manifest =
        entry_manifest.package_name.is_some() || workspace_member_set.is_empty();

    let mut manifest_cache: BTreeMap<PathBuf, ManifestDocument> = BTreeMap::new();
    let mut states: BTreeMap<PathBuf, VisitState> = BTreeMap::new();
    let mut stack: Vec<PathBuf> = Vec::new();

    for manifest_path in &workspace_member_set {
        visit_manifest_recursive(
            manifest_path,
            policy,
            &entry_root,
            &workspace_member_set,
            &workspace_path_dependencies,
            &patch_path_dependencies,
            true,
            &mut partial,
            &mut manifest_cache,
            &mut states,
            &mut stack,
        )?;
    }
    if include_entry_manifest {
        visit_manifest_recursive(
            entry_manifest_path,
            policy,
            &entry_root,
            &workspace_member_set,
            &workspace_path_dependencies,
            &patch_path_dependencies,
            true,
            &mut partial,
            &mut manifest_cache,
            &mut states,
            &mut stack,
        )?;
    }

    finalize_graph(entry_manifest_path.to_path_buf(), partial)
}

fn resolve_materialization_from_manifests(
    entry_manifest_path: &Path,
    policy: &PathTopologyPolicy,
) -> Result<CargoPathMaterializationClosure, CargoPathDependencyError> {
    let entry_manifest = read_manifest_document(entry_manifest_path)?;
    let entry_root = entry_manifest_path.parent().ok_or_else(|| {
        CargoPathDependencyError::new(
            CargoPathDependencyErrorKind::ManifestParseFailure,
            format!(
                "entry manifest has no parent: {}",
                entry_manifest_path.display()
            ),
        )
        .with_manifest_path(entry_manifest_path)
    })?;
    let entry_root = normalize_path_for_policy(
        entry_root,
        policy,
        Some(entry_manifest_path),
        None,
        "normalize materialization entry root",
    )?;

    let mut partial = PartialGraph::default();
    if entry_manifest.has_workspace {
        partial.workspace_root = Some(entry_root.clone());
    }
    let workspace_path_dependencies = entry_manifest.workspace_path_dependencies.clone();
    let patch_path_dependencies = entry_manifest.patch_path_dependencies.clone();
    let workspace_member_manifests = expand_workspace_members(
        &entry_root,
        &entry_manifest.workspace_members,
        entry_manifest_path,
    )?;
    let workspace_member_set = workspace_member_manifests
        .iter()
        .cloned()
        .collect::<BTreeSet<_>>();
    let include_entry_manifest =
        entry_manifest.package_name.is_some() || workspace_member_set.is_empty();

    let mut manifest_cache = BTreeMap::from([(entry_manifest_path.to_path_buf(), entry_manifest)]);
    let mut visited = BTreeSet::new();

    for manifest_path in &workspace_member_set {
        visit_manifest_for_materialization(
            manifest_path,
            policy,
            &entry_root,
            &workspace_member_set,
            &workspace_path_dependencies,
            &patch_path_dependencies,
            true,
            &mut partial,
            &mut manifest_cache,
            &mut visited,
        )?;
    }
    if include_entry_manifest {
        visit_manifest_for_materialization(
            entry_manifest_path,
            policy,
            &entry_root,
            &workspace_member_set,
            &workspace_path_dependencies,
            &patch_path_dependencies,
            true,
            &mut partial,
            &mut manifest_cache,
            &mut visited,
        )?;
    }

    for (dependency_name, raw_dependency_path) in workspace_path_dependencies
        .iter()
        .chain(patch_path_dependencies.iter())
    {
        let dependency_candidate = resolve_dependency_candidate(&entry_root, raw_dependency_path);
        let (_, dependency_manifest) = resolve_materialization_dependency_manifest(
            &dependency_candidate,
            policy,
            entry_manifest_path,
            dependency_name,
        )?;
        visit_manifest_for_materialization(
            &dependency_manifest,
            policy,
            &entry_root,
            &workspace_member_set,
            &workspace_path_dependencies,
            &patch_path_dependencies,
            false,
            &mut partial,
            &mut manifest_cache,
            &mut visited,
        )?;
    }

    Ok(finalize_materialization_closure(
        entry_manifest_path.to_path_buf(),
        partial,
    ))
}

#[allow(clippy::too_many_arguments)]
fn visit_manifest_for_materialization(
    manifest_path: &Path,
    policy: &PathTopologyPolicy,
    workspace_root: &Path,
    workspace_member_manifests: &BTreeSet<PathBuf>,
    workspace_path_dependencies: &BTreeMap<String, String>,
    patch_path_dependencies: &BTreeMap<String, String>,
    mark_workspace_member: bool,
    partial: &mut PartialGraph,
    manifest_cache: &mut BTreeMap<PathBuf, ManifestDocument>,
    visited: &mut BTreeSet<PathBuf>,
) -> Result<(), CargoPathDependencyError> {
    let manifest_root = manifest_path.parent().ok_or_else(|| {
        CargoPathDependencyError::new(
            CargoPathDependencyErrorKind::ManifestParseFailure,
            format!("manifest has no parent: {}", manifest_path.display()),
        )
        .with_manifest_path(manifest_path)
    })?;
    let package_root = normalize_path_for_policy(
        manifest_root,
        policy,
        Some(manifest_path),
        None,
        "normalize materialization package root",
    )?;
    let canonical_manifest = package_root.join("Cargo.toml");
    if !canonical_manifest.is_file() {
        return Err(CargoPathDependencyError::new(
            CargoPathDependencyErrorKind::ManifestParseFailure,
            format!("manifest file missing: {}", canonical_manifest.display()),
        )
        .with_manifest_path(canonical_manifest));
    }

    if !visited.insert(package_root.clone()) {
        if mark_workspace_member {
            partial.add_root(package_root.clone());
            if let Some(package) = partial.packages.get_mut(&package_root) {
                package.workspace_member = true;
            }
        }
        return Ok(());
    }

    let manifest = if let Some(cached) = manifest_cache.get(&canonical_manifest) {
        cached.clone()
    } else {
        let parsed = read_manifest_document(&canonical_manifest)?;
        manifest_cache.insert(canonical_manifest.clone(), parsed.clone());
        parsed
    };

    let workspace_member =
        mark_workspace_member || workspace_member_manifests.contains(&canonical_manifest);
    partial.add_package(
        package_root.clone(),
        canonical_manifest.clone(),
        manifest
            .package_name
            .clone()
            .unwrap_or_else(|| default_package_name(&package_root)),
        workspace_member,
    );
    if workspace_member {
        partial.add_root(package_root.clone());
    }

    for dependency in &manifest.materialization_path_dependencies {
        let Some(dependency_candidate) = resolve_manifest_dependency_candidate(
            &package_root,
            workspace_root,
            dependency,
            workspace_path_dependencies,
            patch_path_dependencies,
            &canonical_manifest,
        )?
        else {
            continue;
        };
        let (dependency_root, dependency_manifest) = resolve_materialization_dependency_manifest(
            &dependency_candidate,
            policy,
            &canonical_manifest,
            &dependency.dependency_name,
        )?;

        partial.add_edge(
            package_root.clone(),
            dependency_root,
            dependency.dependency_name.clone(),
        );
        visit_manifest_for_materialization(
            &dependency_manifest,
            policy,
            workspace_root,
            workspace_member_manifests,
            workspace_path_dependencies,
            patch_path_dependencies,
            false,
            partial,
            manifest_cache,
            visited,
        )?;
    }

    Ok(())
}

fn resolve_materialization_dependency_manifest(
    dependency_candidate: &Path,
    policy: &PathTopologyPolicy,
    declaring_manifest: &Path,
    dependency_name: &str,
) -> Result<(PathBuf, PathBuf), CargoPathDependencyError> {
    validate_absolute_dependency_scope(
        dependency_candidate,
        policy,
        declaring_manifest,
        dependency_name,
        "materialization dependency path policy violation",
    )?;
    if !dependency_candidate.exists() {
        return Err(CargoPathDependencyError::new(
            CargoPathDependencyErrorKind::MissingPathDependency,
            format!(
                "materialization dependency path does not exist: {}",
                dependency_candidate.display()
            ),
        )
        .with_manifest_path(declaring_manifest)
        .with_dependency_name(dependency_name.to_string())
        .with_dependency_path(dependency_candidate));
    }

    let dependency_root = normalize_path_for_policy(
        dependency_candidate,
        policy,
        Some(declaring_manifest),
        Some(dependency_name),
        "normalize materialization dependency path",
    )?;
    let dependency_manifest = dependency_root.join("Cargo.toml");
    if !dependency_manifest.is_file() {
        return Err(CargoPathDependencyError::new(
            CargoPathDependencyErrorKind::MissingPathDependency,
            format!(
                "materialization dependency manifest missing: {}",
                dependency_manifest.display()
            ),
        )
        .with_manifest_path(declaring_manifest)
        .with_dependency_name(dependency_name.to_string())
        .with_dependency_path(dependency_manifest.clone()));
    }

    Ok((dependency_root, dependency_manifest))
}

fn finalize_materialization_closure(
    entry_manifest_path: PathBuf,
    partial: PartialGraph,
) -> CargoPathMaterializationClosure {
    let packages = partial
        .packages
        .iter()
        .map(|(root, package)| CargoPathDependencyPackage {
            package_root: root.clone(),
            manifest_path: package.manifest_path.clone(),
            package_name: package.package_name.clone(),
            workspace_member: package.workspace_member,
        })
        .collect();
    let edges = partial
        .adjacency
        .iter()
        .flat_map(|(from, tails)| {
            tails.iter().map(|tail| CargoPathDependencyEdge {
                from: from.clone(),
                to: tail.to.clone(),
                dependency_name: tail.dependency_name.clone(),
            })
        })
        .collect();

    CargoPathMaterializationClosure {
        entry_manifest_path,
        workspace_root: partial.workspace_root,
        root_packages: partial.roots.into_iter().collect(),
        packages,
        edges,
    }
}

#[allow(clippy::too_many_arguments)]
fn visit_manifest_recursive(
    manifest_path: &Path,
    policy: &PathTopologyPolicy,
    workspace_root: &Path,
    workspace_member_manifests: &BTreeSet<PathBuf>,
    workspace_path_dependencies: &BTreeMap<String, String>,
    patch_path_dependencies: &BTreeMap<String, String>,
    mark_workspace_member: bool,
    partial: &mut PartialGraph,
    manifest_cache: &mut BTreeMap<PathBuf, ManifestDocument>,
    states: &mut BTreeMap<PathBuf, VisitState>,
    stack: &mut Vec<PathBuf>,
) -> Result<PathBuf, CargoPathDependencyError> {
    let manifest_root = manifest_path.parent().ok_or_else(|| {
        CargoPathDependencyError::new(
            CargoPathDependencyErrorKind::ManifestParseFailure,
            format!("manifest has no parent: {}", manifest_path.display()),
        )
        .with_manifest_path(manifest_path)
    })?;
    let package_root = normalize_path_for_policy(
        manifest_root,
        policy,
        Some(manifest_path),
        None,
        "normalize manifest package root",
    )?;
    let canonical_manifest = package_root.join("Cargo.toml");
    if !canonical_manifest.is_file() {
        return Err(CargoPathDependencyError::new(
            CargoPathDependencyErrorKind::ManifestParseFailure,
            format!("manifest file missing: {}", canonical_manifest.display()),
        )
        .with_manifest_path(canonical_manifest));
    }

    if states.get(&package_root) == Some(&VisitState::Visiting) {
        let cycle = cycle_from_stack(stack, &package_root);
        return Err(CargoPathDependencyError::new(
            CargoPathDependencyErrorKind::CyclicDependency,
            format!(
                "cyclic path dependency detected at {}",
                package_root.display()
            ),
        )
        .with_cycle(cycle));
    }
    if states.get(&package_root) == Some(&VisitState::Visited) {
        if mark_workspace_member {
            partial.add_root(package_root.clone());
            if let Some(package) = partial.packages.get_mut(&package_root) {
                package.workspace_member = true;
            }
        }
        return Ok(package_root);
    }

    states.insert(package_root.clone(), VisitState::Visiting);
    stack.push(package_root.clone());

    let manifest = if let Some(cached) = manifest_cache.get(&canonical_manifest) {
        cached.clone()
    } else {
        let parsed = read_manifest_document(&canonical_manifest)?;
        manifest_cache.insert(canonical_manifest.clone(), parsed.clone());
        parsed
    };

    let workspace_member =
        mark_workspace_member || workspace_member_manifests.contains(&canonical_manifest);
    partial.add_package(
        package_root.clone(),
        canonical_manifest.clone(),
        manifest
            .package_name
            .clone()
            .unwrap_or_else(|| default_package_name(&package_root)),
        workspace_member,
    );
    if workspace_member {
        partial.add_root(package_root.clone());
    }

    for dependency in &manifest.path_dependencies {
        let Some(dependency_candidate) = resolve_manifest_dependency_candidate(
            &package_root,
            workspace_root,
            dependency,
            workspace_path_dependencies,
            patch_path_dependencies,
            &canonical_manifest,
        )?
        else {
            continue;
        };
        validate_absolute_dependency_scope(
            &dependency_candidate,
            policy,
            &canonical_manifest,
            &dependency.dependency_name,
            "manifest dependency path policy violation",
        )?;
        if !dependency_candidate.exists() {
            return Err(CargoPathDependencyError::new(
                CargoPathDependencyErrorKind::MissingPathDependency,
                format!(
                    "dependency path does not exist: {}",
                    dependency_candidate.display()
                ),
            )
            .with_manifest_path(canonical_manifest.clone())
            .with_dependency_name(dependency.dependency_name.clone())
            .with_dependency_path(dependency_candidate));
        }

        let dependency_root = normalize_path_for_policy(
            &dependency_candidate,
            policy,
            Some(&canonical_manifest),
            Some(&dependency.dependency_name),
            "normalize manifest dependency path",
        )?;
        let dependency_manifest = dependency_root.join("Cargo.toml");
        if !dependency_manifest.is_file() {
            return Err(CargoPathDependencyError::new(
                CargoPathDependencyErrorKind::MissingPathDependency,
                format!(
                    "dependency manifest missing: {}",
                    dependency_manifest.display()
                ),
            )
            .with_manifest_path(canonical_manifest.clone())
            .with_dependency_name(dependency.dependency_name.clone())
            .with_dependency_path(dependency_manifest));
        }

        partial.add_edge(
            package_root.clone(),
            dependency_root.clone(),
            dependency.dependency_name.clone(),
        );
        visit_manifest_recursive(
            &dependency_manifest,
            policy,
            workspace_root,
            workspace_member_manifests,
            workspace_path_dependencies,
            patch_path_dependencies,
            false,
            partial,
            manifest_cache,
            states,
            stack,
        )?;
    }

    stack.pop();
    states.insert(package_root, VisitState::Visited);
    Ok(canonical_manifest
        .parent()
        .unwrap_or_else(|| Path::new("/"))
        .to_path_buf())
}

fn resolve_dependency_candidate(base_root: &Path, raw_dependency_path: &str) -> PathBuf {
    let raw = PathBuf::from(raw_dependency_path);
    let resolved = if raw.is_absolute() {
        raw
    } else {
        base_root.join(raw)
    };
    if resolved
        .file_name()
        .is_some_and(|file_name| file_name == "Cargo.toml")
    {
        resolved.parent().map(Path::to_path_buf).unwrap_or(resolved)
    } else {
        resolved
    }
}

fn resolve_manifest_dependency_candidate(
    package_root: &Path,
    workspace_root: &Path,
    dependency: &ManifestDependency,
    workspace_path_dependencies: &BTreeMap<String, String>,
    patch_path_dependencies: &BTreeMap<String, String>,
    declaring_manifest: &Path,
) -> Result<Option<PathBuf>, CargoPathDependencyError> {
    if let Some(raw_dependency_path) = dependency.dependency_path.as_deref() {
        return Ok(Some(resolve_dependency_candidate(
            package_root,
            raw_dependency_path,
        )));
    }

    if dependency.uses_workspace_inheritance {
        if let Some(raw_dependency_path) =
            workspace_path_dependencies.get(&dependency.dependency_name)
        {
            return Ok(Some(resolve_dependency_candidate(
                workspace_root,
                raw_dependency_path,
            )));
        }

        // A direct path dependency can itself be a member of a different
        // workspace. When cargo metadata is unavailable, its `{ workspace =
        // true }` dependencies must be resolved against that enclosing
        // workspace, not the entry package's workspace. Otherwise the fallback
        // stops at the directly named member and omits active transitive local
        // crates (for example fastapi -> fastapi-core).
        for ancestor in package_root.ancestors() {
            let candidate_manifest = ancestor.join("Cargo.toml");
            if candidate_manifest == declaring_manifest || !candidate_manifest.is_file() {
                continue;
            }
            let candidate = read_manifest_document(&candidate_manifest)?;
            if !candidate.has_workspace {
                continue;
            }
            let Some(raw_dependency_path) = candidate
                .workspace_path_dependencies
                .get(&dependency.dependency_name)
            else {
                if candidate
                    .workspace_dependency_names
                    .contains(&dependency.dependency_name)
                {
                    if let Some(raw_dependency_path) =
                        patch_path_dependencies.get(&dependency.dependency_name)
                    {
                        return Ok(Some(resolve_dependency_candidate(
                            workspace_root,
                            raw_dependency_path,
                        )));
                    }
                    // The dependency is inherited from the enclosing
                    // workspace, but resolves from a registry or Git rather
                    // than a local path. It is outside the source-sync closure.
                    return Ok(None);
                }
                return Err(CargoPathDependencyError::new(
                    CargoPathDependencyErrorKind::ManifestParseFailure,
                    format!(
                        "workspace-inherited dependency '{}' is not defined by {}",
                        dependency.dependency_name,
                        candidate_manifest.display()
                    ),
                )
                .with_manifest_path(declaring_manifest)
                .with_dependency_name(dependency.dependency_name.clone()));
            };
            return Ok(Some(resolve_dependency_candidate(
                ancestor,
                raw_dependency_path,
            )));
        }
        return Err(CargoPathDependencyError::new(
            CargoPathDependencyErrorKind::ManifestParseFailure,
            format!(
                "workspace-inherited dependency '{}' has no enclosing workspace",
                dependency.dependency_name
            ),
        )
        .with_manifest_path(declaring_manifest)
        .with_dependency_name(dependency.dependency_name.clone()));
    }

    Ok(patch_path_dependencies
        .get(&dependency.dependency_name)
        .map(|raw_dependency_path| {
            resolve_dependency_candidate(workspace_root, raw_dependency_path)
        }))
}

fn read_manifest_document(
    manifest_path: &Path,
) -> Result<ManifestDocument, CargoPathDependencyError> {
    let contents = std::fs::read_to_string(manifest_path).map_err(|error| {
        CargoPathDependencyError::new(
            CargoPathDependencyErrorKind::ManifestParseFailure,
            format!(
                "failed to read manifest {}: {error}",
                manifest_path.display()
            ),
        )
        .with_manifest_path(manifest_path)
    })?;
    let table = toml::from_str::<toml::Table>(&contents).map_err(|error| {
        CargoPathDependencyError::new(
            CargoPathDependencyErrorKind::ManifestParseFailure,
            format!(
                "failed to parse manifest {}: {error}",
                manifest_path.display()
            ),
        )
        .with_manifest_path(manifest_path)
    })?;

    let package_name = table
        .get("package")
        .and_then(toml::Value::as_table)
        .and_then(|package| package.get("name"))
        .and_then(toml::Value::as_str)
        .map(ToOwned::to_owned);
    let has_workspace = table.contains_key("workspace");
    let workspace_members = table
        .get("workspace")
        .and_then(toml::Value::as_table)
        .and_then(|workspace| workspace.get("members"))
        .and_then(toml::Value::as_array)
        .map(|members| {
            members
                .iter()
                .filter_map(toml::Value::as_str)
                .map(ToOwned::to_owned)
                .collect::<Vec<_>>()
        })
        .unwrap_or_default();
    let workspace_dependencies = table
        .get("workspace")
        .and_then(toml::Value::as_table)
        .and_then(|workspace| workspace.get("dependencies"));
    let workspace_dependency_names = workspace_dependencies
        .and_then(toml::Value::as_table)
        .map(|dependencies| dependencies.keys().cloned().collect())
        .unwrap_or_default();
    let workspace_path_dependencies = workspace_dependencies
        .map(collect_named_path_dependencies)
        .unwrap_or_default();
    let patch_path_dependencies = table
        .get("patch")
        .and_then(toml::Value::as_table)
        .map(collect_patch_path_dependencies)
        .unwrap_or_default();

    let mut path_dependencies = Vec::new();
    collect_dependency_specs(table.get("dependencies"), &mut path_dependencies, false);
    collect_dependency_specs(
        table.get("build-dependencies"),
        &mut path_dependencies,
        false,
    );

    if let Some(targets) = table.get("target").and_then(toml::Value::as_table) {
        for target_config in targets.values() {
            if let Some(target_table) = target_config.as_table() {
                collect_dependency_specs(
                    target_table.get("dependencies"),
                    &mut path_dependencies,
                    false,
                );
                collect_dependency_specs(
                    target_table.get("build-dependencies"),
                    &mut path_dependencies,
                    false,
                );
            }
        }
    }

    let mut materialization_path_dependencies = Vec::new();
    for dependency_table in ["dependencies", "build-dependencies", "dev-dependencies"] {
        collect_dependency_specs(
            table.get(dependency_table),
            &mut materialization_path_dependencies,
            true,
        );
    }
    if let Some(targets) = table.get("target").and_then(toml::Value::as_table) {
        for target_config in targets.values() {
            if let Some(target_table) = target_config.as_table() {
                for dependency_table in ["dependencies", "build-dependencies", "dev-dependencies"] {
                    collect_dependency_specs(
                        target_table.get(dependency_table),
                        &mut materialization_path_dependencies,
                        true,
                    );
                }
            }
        }
    }

    Ok(ManifestDocument {
        package_name,
        has_workspace,
        workspace_members,
        workspace_dependency_names,
        workspace_path_dependencies,
        patch_path_dependencies,
        path_dependencies,
        materialization_path_dependencies,
    })
}

fn collect_dependency_specs(
    maybe_table_value: Option<&toml::Value>,
    collector: &mut Vec<ManifestDependency>,
    include_optional: bool,
) {
    let Some(table) = maybe_table_value.and_then(toml::Value::as_table) else {
        return;
    };
    for (dependency_name, dependency_value) in table {
        match dependency_value {
            toml::Value::String(_) => {
                collector.push(ManifestDependency {
                    dependency_name: dependency_name.clone(),
                    dependency_path: None,
                    uses_workspace_inheritance: false,
                });
            }
            toml::Value::Table(dependency_table) => {
                if !include_optional
                    && dependency_table
                        .get("optional")
                        .and_then(toml::Value::as_bool)
                        .unwrap_or(false)
                {
                    continue;
                }
                collector.push(ManifestDependency {
                    dependency_name: dependency_name.clone(),
                    dependency_path: dependency_table
                        .get("path")
                        .and_then(toml::Value::as_str)
                        .map(ToOwned::to_owned),
                    uses_workspace_inheritance: dependency_table
                        .get("workspace")
                        .and_then(toml::Value::as_bool)
                        .unwrap_or(false),
                });
            }
            _ => {}
        }
    }
}

fn collect_named_path_dependencies(maybe_table_value: &toml::Value) -> BTreeMap<String, String> {
    let Some(table) = maybe_table_value.as_table() else {
        return BTreeMap::new();
    };

    let mut dependencies = BTreeMap::new();
    for (dependency_name, dependency_value) in table {
        let Some(dependency_table) = dependency_value.as_table() else {
            continue;
        };
        let Some(path) = dependency_table.get("path").and_then(toml::Value::as_str) else {
            continue;
        };
        dependencies.insert(dependency_name.clone(), path.to_string());
    }
    dependencies
}

fn collect_patch_path_dependencies(patch_table: &toml::value::Table) -> BTreeMap<String, String> {
    let mut dependencies = BTreeMap::new();
    for patch_source in patch_table.values() {
        dependencies.extend(collect_named_path_dependencies(patch_source));
    }
    dependencies
}

fn expand_workspace_members(
    workspace_root: &Path,
    members: &[String],
    manifest_path: &Path,
) -> Result<Vec<PathBuf>, CargoPathDependencyError> {
    let mut manifests = BTreeSet::new();
    for member in members {
        let expanded_paths = expand_member_pattern(workspace_root, member).map_err(|error| {
            CargoPathDependencyError::new(
                CargoPathDependencyErrorKind::ManifestParseFailure,
                format!("failed to expand workspace member '{member}': {error}"),
            )
            .with_manifest_path(manifest_path)
        })?;
        for candidate in expanded_paths {
            let manifest_candidate = if candidate
                .file_name()
                .is_some_and(|file_name| file_name == "Cargo.toml")
            {
                candidate
            } else {
                candidate.join("Cargo.toml")
            };
            if !manifest_candidate.is_file() {
                return Err(CargoPathDependencyError::new(
                    CargoPathDependencyErrorKind::MissingPathDependency,
                    format!(
                        "workspace member manifest missing: {}",
                        manifest_candidate.display()
                    ),
                )
                .with_manifest_path(manifest_path)
                .with_dependency_name(member.clone())
                .with_dependency_path(manifest_candidate));
            }
            manifests.insert(manifest_candidate);
        }
    }
    Ok(manifests.into_iter().collect())
}

fn expand_member_pattern(base: &Path, pattern: &str) -> Result<Vec<PathBuf>, std::io::Error> {
    if !contains_glob(pattern) {
        return Ok(vec![base.join(pattern)]);
    }

    let mut candidates = vec![base.to_path_buf()];
    let normalized_pattern = pattern.replace('\\', "/");
    for segment in normalized_pattern.split('/') {
        if segment.is_empty() || segment == "." {
            continue;
        }
        if segment == ".." {
            candidates = candidates
                .into_iter()
                .map(|candidate| {
                    candidate
                        .parent()
                        .unwrap_or_else(|| Path::new("/"))
                        .to_path_buf()
                })
                .collect();
            continue;
        }

        let wildcard_segment = contains_wildcard(segment);
        let mut next_candidates = Vec::new();
        for candidate in &candidates {
            if wildcard_segment {
                if !candidate.is_dir() {
                    continue;
                }
                for entry in std::fs::read_dir(candidate)? {
                    let entry = entry?;
                    let file_name = entry.file_name();
                    let Some(file_name) = file_name.to_str() else {
                        continue;
                    };
                    if wildcard_match(segment, file_name) {
                        next_candidates.push(entry.path());
                    }
                }
            } else {
                next_candidates.push(candidate.join(segment));
            }
        }
        candidates = next_candidates;
    }

    Ok(candidates)
}

fn contains_glob(pattern: &str) -> bool {
    pattern.chars().any(|ch| matches!(ch, '*' | '?' | '['))
}

fn contains_wildcard(segment: &str) -> bool {
    segment.contains('*') || segment.contains('?')
}

fn wildcard_match(pattern: &str, value: &str) -> bool {
    wildcard_match_bytes(pattern.as_bytes(), value.as_bytes())
}

fn wildcard_match_bytes(pattern: &[u8], value: &[u8]) -> bool {
    if pattern.is_empty() {
        return value.is_empty();
    }
    if pattern[0] == b'*' {
        for index in 0..=value.len() {
            if wildcard_match_bytes(&pattern[1..], &value[index..]) {
                return true;
            }
        }
        return false;
    }
    if value.is_empty() {
        return false;
    }
    if pattern[0] == b'?' || pattern[0] == value[0] {
        return wildcard_match_bytes(&pattern[1..], &value[1..]);
    }
    false
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::e2e::{MultiRepoFixtureConfig, reset_multi_repo_fixtures};
    use std::fs;
    use std::sync::atomic::{AtomicU64, Ordering};

    #[cfg(unix)]
    use std::os::unix::fs::symlink;

    static FIXTURE_COUNTER: AtomicU64 = AtomicU64::new(0);

    fn selected_tree(files: &[(&str, &str)]) -> BTreeMap<PathBuf, SelectedCargoEntry> {
        files
            .iter()
            .map(|(path, text)| {
                (
                    PathBuf::from(path),
                    SelectedCargoEntry::File(Some((*text).into())),
                )
            })
            .collect()
    }

    #[test]
    fn selected_cargo_combined_tree_accepts_only_selected_sibling_roots() {
        let mut entries = selected_tree(&[
            (
                "app/Cargo.toml",
                "[package]\nname='app'\n[dependencies]\ndep={path='../dep'}",
            ),
            ("dep/Cargo.toml", "[package]\nname='dep'"),
        ]);
        validate_selected_cargo_tree_at(&entries, Path::new("app/Cargo.toml")).unwrap();
        // The original API still requires an actual selected root manifest.
        assert!(validate_selected_cargo_tree(&entries).is_err());
        entries.insert(
            PathBuf::from("app/Cargo.toml"),
            SelectedCargoEntry::File(Some("[dependencies]\ndep={path='../../outside'}".into())),
        );
        let error =
            validate_selected_cargo_tree_at(&entries, Path::new("app/Cargo.toml")).unwrap_err();
        assert!(error.detail().contains("../../outside"), "{error}");
        assert!(error.detail().contains("escapes"), "{error}");
    }

    #[test]
    fn selected_cargo_combined_tree_requires_entrypoint_and_checks_unrelated_metadata() {
        let mut entries = selected_tree(&[
            ("app/Cargo.toml", "[workspace]"),
            (
                "other/Cargo.toml",
                "[dependencies]\nstale={path='../../stale'}",
            ),
        ]);
        let error =
            validate_selected_cargo_tree_at(&entries, Path::new("app/Cargo.toml")).unwrap_err();
        assert!(error.detail().contains("other/Cargo.toml"), "{error}");
        entries.insert(
            PathBuf::from("other/Cargo.toml"),
            SelectedCargoEntry::File(Some("[workspace]".into())),
        );
        for primary in [
            "missing/Cargo.toml",
            "../app/Cargo.toml",
            "/app/Cargo.toml",
            "app",
        ] {
            assert!(
                validate_selected_cargo_tree_at(&entries, Path::new(primary)).is_err(),
                "{primary}"
            );
        }
        entries.insert(
            PathBuf::from("app/Cargo.toml"),
            SelectedCargoEntry::File(None),
        );
        assert!(
            validate_selected_cargo_tree_at(&entries, Path::new("app/Cargo.toml"))
                .unwrap_err()
                .detail()
                .contains("primary manifest text")
        );
    }

    #[test]
    fn selected_cargo_combined_config_resolves_from_its_selected_base() {
        let entries = selected_tree(&[
            ("app/Cargo.toml", "[workspace]"),
            ("dep/Cargo.toml", "[package]\nname='dep'"),
        ]);
        let primary = Path::new("app/Cargo.toml");
        validate_selected_cargo_config_at(&entries, primary, Path::new("app"), "paths=['../dep']")
            .unwrap();
        validate_selected_cargo_config_at(&entries, primary, Path::new(""), "paths=['dep']")
            .unwrap();
        assert!(
            validate_selected_cargo_config_at(
                &entries,
                primary,
                Path::new("app"),
                "paths=['../../outside']"
            )
            .is_err()
        );
        assert!(
            validate_selected_cargo_config_at(
                &entries,
                Path::new("missing/Cargo.toml"),
                Path::new("app"),
                "[build]\njobs=1"
            )
            .is_err()
        );
        assert!(
            validate_selected_cargo_config_at(
                &entries,
                primary,
                Path::new("app/Cargo.toml"),
                "[build]\njobs=1"
            )
            .is_err()
        );
    }

    #[test]
    fn selected_cargo_tree_allows_internal_parent_dependencies_and_workspace_globs() {
        let entries = selected_tree(&[
            (
                "Cargo.toml",
                "[workspace]\nmembers=['crates/*']\n[workspace.dependencies]\nshared={path='crates/dep'}\n",
            ),
            (
                "crates/app/Cargo.toml",
                "[package]\nname='app'\nworkspace='../..'\n[dependencies]\nshared={workspace=true}\n[dev-dependencies]\ndep={path='../dep'}\n[lib]\npath='src/lib.rs'\n",
            ),
            ("crates/app/src/lib.rs", ""),
            ("crates/dep/Cargo.toml", "[package]\nname='dep'\n"),
        ]);
        validate_selected_cargo_tree(&entries).unwrap();
        assert_eq!(
            validate_selected_cargo_path(&entries, Path::new("crates/app/../dep/Cargo.toml"))
                .unwrap(),
            Path::new("crates/dep/Cargo.toml")
        );
    }

    #[test]
    fn selected_cargo_tree_aggregates_external_roots_and_declaring_manifests() {
        let entries = selected_tree(&[
            (
                "Cargo.toml",
                "[dependencies]\none={path='../one'}\n[patch.crates-io]\ntwo={path='../two'}\n",
            ),
            (
                "nested/Cargo.toml",
                "[target.'cfg(windows)'.build-dependencies]\nthree={path='../../three',optional=true}\n",
            ),
        ]);
        let error = validate_selected_cargo_tree(&entries).unwrap_err();
        assert_eq!(
            error.kind(),
            &CargoPathDependencyErrorKind::PathPolicyViolation
        );
        for expected in [
            "../one",
            "../two",
            "../../three",
            "nested/Cargo.toml",
            "target.cfg(windows).build-dependencies.three.path",
        ] {
            assert!(error.detail().contains(expected), "{error}");
        }
        assert_eq!(error.diagnostics().len(), 3);
    }

    #[test]
    fn selected_cargo_tree_checks_replace_workspace_and_compiler_source_paths() {
        let invalid = [
            "[replace]\n'old:1.0.0'={path='../external'}\n",
            "[package]\nworkspace='../external'\n",
            "[workspace]\nmembers=['../external']\n",
            "[workspace]\ndefault-members=['../external']\n",
            "[workspace.dependencies]\nexternal={path='../external'}\n",
            "[lib]\npath='../external.rs'\n",
            "[[bin]]\npath='../external.rs'\n",
            "[[test]]\npath='../external.rs'\n",
            "[[example]]\npath='../external.rs'\n",
            "[[bench]]\npath='../external.rs'\n",
            "[package]\nbuild='../external.rs'\n",
            "[dependencies]\nexternal={path='/existing/on/worker'}\n",
            "[dependencies]\nexternal={path='C:\\existing'}\n",
        ];
        for manifest in invalid {
            let error = validate_selected_cargo_tree(&selected_tree(&[("Cargo.toml", manifest)]))
                .unwrap_err();
            assert_eq!(
                error.kind(),
                &CargoPathDependencyErrorKind::PathPolicyViolation,
                "{manifest}"
            );
            assert!(error.detail().contains("Cargo.toml"), "{error}");
        }
        validate_selected_cargo_tree(&selected_tree(&[
            (
                "Cargo.toml",
                "[package]\nbuild=true\n[replace]\n'old:1.0.0'={path='dep'}\n",
            ),
            ("build.rs", ""),
            ("dep/Cargo.toml", "[package]\nname='dep'\n"),
        ]))
        .unwrap();
    }

    #[test]
    fn selected_cargo_tree_resolves_symlinks_before_parent_components() {
        let mut entries = selected_tree(&[
            ("Cargo.toml", "[dependencies]\ndep={path='alias/..'}\n"),
            ("a/Cargo.toml", "[package]\nname='a'\n"),
            ("a/nested/anchor", ""),
        ]);
        entries.insert(
            PathBuf::from("alias"),
            SelectedCargoEntry::Symlink("a/nested".into()),
        );
        validate_selected_cargo_tree(&entries).unwrap();
        assert_eq!(
            validate_selected_cargo_path(&entries, Path::new("alias/../Cargo.toml")).unwrap(),
            Path::new("a/Cargo.toml")
        );
        entries.insert(
            PathBuf::from("alias"),
            SelectedCargoEntry::Symlink("../outside".into()),
        );
        assert!(
            validate_selected_cargo_tree(&entries)
                .unwrap_err()
                .detail()
                .contains("escapes")
        );
        entries.insert(
            PathBuf::from("alias"),
            SelectedCargoEntry::Symlink("other".into()),
        );
        entries.insert(
            PathBuf::from("other"),
            SelectedCargoEntry::Symlink("alias".into()),
        );
        assert!(
            validate_selected_cargo_tree(&entries)
                .unwrap_err()
                .detail()
                .contains("cycle")
        );
    }

    #[test]
    fn selected_cargo_tree_checks_selected_config_overrides_and_refuses_includes() {
        let invalid = [
            "paths=['../external']",
            "[patch.crates-io]\nexternal={path='../external'}",
            "[replace]\n'old:1.0.0'={path='../external'}",
            "[source.local]\ndirectory='../external'",
            "[source.local]\nlocal-registry='../external'",
            "include=['extra.toml']",
        ];
        for config in invalid {
            for name in [".cargo/config", ".cargo/config.toml"] {
                let entries = selected_tree(&[("Cargo.toml", "[workspace]"), (name, config)]);
                let error = validate_selected_cargo_tree(&entries).unwrap_err();
                assert!(error.detail().contains(name), "{error}");
            }
        }
        validate_selected_cargo_tree(&selected_tree(&[
            ("Cargo.toml", "[workspace]"),
            (".cargo/config.toml", "paths=['dep']\n[source.local]\ndirectory='vendor'\n[build]\nbuild-dir='/managed/cache'"),
            ("dep/Cargo.toml", "[package]\nname='dep'"),
            ("vendor/entry", ""),
        ])).unwrap();
        let entries = selected_tree(&[
            ("Cargo.toml", "[workspace]"),
            ("dep/Cargo.toml", "[package]\nname='dep'"),
            ("nested/anchor", ""),
        ]);
        validate_selected_cargo_config(&entries, Path::new(""), "paths=['dep']").unwrap();
        validate_selected_cargo_config(&entries, Path::new("nested"), "paths=['../dep']").unwrap();
        assert!(
            validate_selected_cargo_config(&entries, Path::new(""), "paths=['../dep']").is_err()
        );
        assert!(
            validate_selected_cargo_config(&entries, Path::new("nested/anchor"), "[build]\njobs=1")
                .is_err()
        );
        let mut alias = selected_tree(&[
            ("Cargo.toml", "[workspace]"),
            ("settings/config.toml", "paths=['../external']"),
        ]);
        alias.insert(
            PathBuf::from(".cargo"),
            SelectedCargoEntry::Symlink("settings".into()),
        );
        assert!(
            validate_selected_cargo_tree(&alias)
                .unwrap_err()
                .detail()
                .contains(".cargo/config.toml")
        );
        alias.insert(
            PathBuf::from("settings/config.toml"),
            SelectedCargoEntry::File(None),
        );
        assert!(
            validate_selected_cargo_tree(&alias)
                .unwrap_err()
                .detail()
                .contains("alias text")
        );
    }

    #[test]
    fn selected_cargo_tree_refuses_missing_text_paths_and_invalid_inventory() {
        assert!(validate_selected_cargo_tree(&BTreeMap::new()).is_err());
        let mut unloaded = BTreeMap::from([
            (PathBuf::from("Cargo.toml"), SelectedCargoEntry::File(None)),
            (
                PathBuf::from("settings/config.toml"),
                SelectedCargoEntry::File(None),
            ),
            (
                PathBuf::from(".cargo"),
                SelectedCargoEntry::Symlink("settings".into()),
            ),
        ]);
        assert_eq!(
            validate_selected_cargo_path(&unloaded, Path::new("Cargo.toml")).unwrap(),
            Path::new("Cargo.toml")
        );
        let config_target =
            validate_selected_cargo_path(&unloaded, Path::new(".cargo/config.toml")).unwrap();
        assert_eq!(config_target, Path::new("settings/config.toml"));
        assert!(
            validate_selected_cargo_tree(&unloaded)
                .unwrap_err()
                .detail()
                .contains("text")
        );
        unloaded.insert(
            PathBuf::from("Cargo.toml"),
            SelectedCargoEntry::File(Some("[workspace]".into())),
        );
        unloaded.insert(
            config_target,
            SelectedCargoEntry::File(Some("[build]\njobs=1".into())),
        );
        validate_selected_cargo_tree(&unloaded).unwrap();
        let mut entries = selected_tree(&[("Cargo.toml", "[dependencies]\ndep={path='dep'}")]);
        // A real ambient dep directory cannot satisfy a selected inventory.
        assert!(
            validate_selected_cargo_tree(&entries)
                .unwrap_err()
                .detail()
                .contains("missing selected path dep")
        );
        entries.insert(
            PathBuf::from("dep/Cargo.toml"),
            SelectedCargoEntry::File(None),
        );
        assert!(
            validate_selected_cargo_tree(&entries)
                .unwrap_err()
                .detail()
                .contains("text")
        );
        let mut entries = selected_tree(&[("Cargo.toml", "[workspace]")]);
        entries.insert(PathBuf::from("file"), SelectedCargoEntry::File(None));
        assert!(validate_selected_cargo_path(&entries, Path::new("file/../Cargo.toml")).is_err());
        assert!(validate_selected_cargo_path(&entries, Path::new("../Cargo.toml")).is_err());
        entries.insert(PathBuf::from("file/child"), SelectedCargoEntry::File(None));
        assert!(
            validate_selected_cargo_tree(&entries)
                .unwrap_err()
                .detail()
                .contains("descendants")
        );
        entries.insert(PathBuf::from("../outside"), SelectedCargoEntry::File(None));
        assert!(validate_selected_cargo_path(&entries, Path::new("Cargo.toml")).is_err());
        assert!(
            validate_selected_cargo_tree(&entries)
                .unwrap_err()
                .detail()
                .contains("invalid selected inventory")
        );
    }

    #[test]
    fn selected_cargo_tree_accepts_inert_unix_colon_leaf_but_not_colon_paths() {
        let mut entries = selected_tree(&[("Cargo.toml", "[workspace]")]);
        entries.insert(
            PathBuf::from("crates/fs-evidence/src/vv/model.rs:6150-6230"),
            SelectedCargoEntry::File(None),
        );
        if cfg!(unix) {
            validate_selected_cargo_tree(&entries).unwrap();
        } else {
            assert!(validate_selected_cargo_tree(&entries).is_err());
        }
        entries.insert(
            PathBuf::from("crates/fs-evidence:outside/src/lib.rs"),
            SelectedCargoEntry::File(None),
        );
        assert!(
            validate_selected_cargo_tree(&entries)
                .unwrap_err()
                .detail()
                .contains("invalid selected inventory path")
        );
        let referenced = selected_tree(&[(
            "Cargo.toml",
            "[package]\nname='root'\nversion='0.1.0'\n[dependencies]\ndep={path='dep:elsewhere'}",
        )]);
        assert!(
            validate_selected_cargo_tree(&referenced)
                .unwrap_err()
                .detail()
                .contains("unsupported or absolute path")
        );
        let mut linked = selected_tree(&[("Cargo.toml", "[workspace]")]);
        linked.insert(
            PathBuf::from("alias"),
            SelectedCargoEntry::Symlink("target:elsewhere".into()),
        );
        assert!(
            validate_selected_cargo_tree(&linked)
                .unwrap_err()
                .detail()
                .contains("unsupported or absolute path")
        );
    }

    #[test]
    fn selected_cargo_tree_does_not_skip_nested_inactive_manifests_or_bad_globs() {
        let entries = selected_tree(&[
            ("Cargo.toml", "[workspace]\nmembers=['app']"),
            ("app/Cargo.toml", "[package]\nname='app'"),
            (
                "fixtures/unused/Cargo.toml",
                "[dev-dependencies]\nexternal={path='../../../external'}",
            ),
        ]);
        assert!(
            validate_selected_cargo_tree(&entries)
                .unwrap_err()
                .detail()
                .contains("fixtures/unused/Cargo.toml")
        );
        for pattern in ["crates/**", "crates/[ab]", "missing/*"] {
            let manifest = format!("[workspace]\nmembers=['{pattern}']");
            assert!(
                validate_selected_cargo_tree(&selected_tree(&[("Cargo.toml", &manifest)])).is_err()
            );
        }
        let inherited = selected_tree(&[
            ("Cargo.toml", "[package]\nname='root'"),
            (
                "nested/Cargo.toml",
                "[package]\nversion.workspace=true\n[dependencies]\nshared.workspace=true",
            ),
        ]);
        assert!(
            validate_selected_cargo_tree(&inherited)
                .unwrap_err()
                .detail()
                .contains("no selected enclosing workspace")
        );
        let selected_workspace = selected_tree(&[
            (
                "Cargo.toml",
                "[workspace]\n[workspace.dependencies]\nshared={path='dep'}",
            ),
            ("dep/Cargo.toml", "[package]\nname='dep'"),
            (
                "nested/Cargo.toml",
                "[package]\nversion.workspace=true\n[dependencies]\nshared.workspace=true",
            ),
        ]);
        validate_selected_cargo_tree(&selected_workspace).unwrap();
    }

    #[cfg(unix)]
    struct TopologyFixture {
        root: PathBuf,
        canonical_root: PathBuf,
        alias_root: PathBuf,
    }

    #[cfg(unix)]
    impl TopologyFixture {
        fn new(prefix: &str) -> Self {
            let id = FIXTURE_COUNTER.fetch_add(1, Ordering::SeqCst);
            let root = std::env::temp_dir().join(format!(
                "rch-cargo-path-deps-{}-{}-{}",
                prefix,
                std::process::id(),
                id
            ));
            let canonical_root = root.join("data/projects");
            let alias_root = root.join("dp");
            fs::create_dir_all(&canonical_root).expect("create canonical root");
            symlink(&canonical_root, &alias_root).expect("create alias symlink");

            Self {
                root,
                canonical_root,
                alias_root,
            }
        }

        fn policy(&self) -> PathTopologyPolicy {
            PathTopologyPolicy::new(self.canonical_root.clone(), self.alias_root.clone())
        }
    }

    #[cfg(unix)]
    impl Drop for TopologyFixture {
        fn drop(&mut self) {
            let _ = fs::remove_dir_all(&self.root);
        }
    }

    #[cfg(unix)]
    fn write_lib_crate(root: &Path, crate_name: &str, deps: &[(&str, &str)]) {
        fs::create_dir_all(root.join("src")).expect("create crate src");
        fs::write(root.join("Cargo.toml"), crate_manifest(crate_name, deps))
            .expect("write manifest");
        fs::write(
            root.join("src/lib.rs"),
            format!(
                "pub fn {}() -> &'static str {{ \"{}\" }}\n",
                crate_name, crate_name
            ),
        )
        .expect("write lib.rs");
    }

    #[cfg(unix)]
    fn write_bin_crate(root: &Path, crate_name: &str, deps: &[(&str, &str)]) {
        fs::create_dir_all(root.join("src")).expect("create crate src");
        fs::write(root.join("Cargo.toml"), crate_manifest(crate_name, deps))
            .expect("write manifest");
        fs::write(
            root.join("src/main.rs"),
            format!("fn main() {{ println!(\"{}\"); }}\n", crate_name),
        )
        .expect("write main.rs");
    }

    #[cfg(unix)]
    fn crate_manifest(crate_name: &str, deps: &[(&str, &str)]) -> String {
        let mut dependencies = String::new();
        for (name, path) in deps {
            dependencies.push_str(&format!("{name} = {{ path = \"{path}\" }}\n"));
        }
        format!(
            "[package]\nname = \"{crate_name}\"\nversion = \"0.1.0\"\nedition = \"2024\"\n\n[dependencies]\n{dependencies}"
        )
    }

    #[cfg(unix)]
    struct LockPlanningFixture {
        _fixture: TopologyFixture,
        workspace_root: PathBuf,
        app_root: PathBuf,
        late_dep_root: PathBuf,
        cargo_home: PathBuf,
        expected_roots: BTreeSet<PathBuf>,
        policy: PathTopologyPolicy,
    }

    #[cfg(unix)]
    impl LockPlanningFixture {
        fn new(prefix: &str) -> Self {
            let fixture = TopologyFixture::new(prefix);
            let scenario_root = fixture.canonical_root.join(prefix);
            let workspace_root = scenario_root.join("ambient_checkout");
            let app_root = workspace_root.join("app");
            let normal_dep_root = scenario_root.join("normal_dep");
            let build_dep_root = scenario_root.join("build_dep");
            let dev_dep_root = scenario_root.join("dev_dep");
            let optional_dep_root = scenario_root.join("optional_dep");
            let target_dep_root = scenario_root.join("target_dep");
            let transitive_dep_root = scenario_root.join("transitive_dep");
            let workspace_dep_root = scenario_root.join("workspace_dep");
            let patch_only_dep_root = scenario_root.join("patch_only_dep");
            let late_dep_root = scenario_root.join("late_dep");
            let cargo_home = scenario_root.join("cargo_home");

            write_lib_crate(&normal_dep_root, "normal_dep", &[]);
            write_lib_crate(&build_dep_root, "build_dep", &[]);
            write_lib_crate(&dev_dep_root, "dev_dep", &[]);
            write_lib_crate(
                &optional_dep_root,
                "optional_dep",
                &[("transitive_dep", "../transitive_dep")],
            );
            write_lib_crate(&target_dep_root, "target_dep", &[]);
            write_lib_crate(&transitive_dep_root, "transitive_dep", &[]);
            write_lib_crate(&workspace_dep_root, "workspace_dep", &[]);
            write_lib_crate(&patch_only_dep_root, "patch_only_dep", &[]);
            fs::create_dir_all(app_root.join("src")).expect("create app source root");
            fs::write(app_root.join("src/main.rs"), "fn main() {}\n").expect("write app main");
            Self::write_app_manifest(&app_root, false);
            fs::write(
                workspace_root.join("Cargo.toml"),
                r#"[workspace]
members = ["app"]
resolver = "3"

[workspace.dependencies]
workspace_dep = { path = "../workspace_dep" }

[patch.crates-io]
patch_only_dep = { path = "../patch_only_dep" }
"#,
            )
            .expect("write workspace manifest");
            fs::create_dir_all(&cargo_home).expect("create isolated Cargo home");

            let expected_roots = [
                &app_root,
                &normal_dep_root,
                &build_dep_root,
                &dev_dep_root,
                &optional_dep_root,
                &target_dep_root,
                &transitive_dep_root,
                &workspace_dep_root,
                &patch_only_dep_root,
            ]
            .into_iter()
            .map(|root| root.canonicalize().expect("canonical fixture package"))
            .collect();
            let policy = fixture.policy();
            Self {
                _fixture: fixture,
                workspace_root,
                app_root,
                late_dep_root,
                cargo_home,
                expected_roots,
                policy,
            }
        }

        fn write_app_manifest(app_root: &Path, include_late_dependency: bool) {
            let late_dependency = if include_late_dependency {
                "late_dep = { path = \"../../late_dep\" }\n"
            } else {
                ""
            };
            fs::write(
                app_root.join("Cargo.toml"),
                format!(
                    r#"[package]
name = "lock_invariant_app"
version = "0.1.0"
edition = "2024"

[dependencies]
normal_dep = {{ path = "../../normal_dep" }}
optional_dep = {{ path = "../../optional_dep", optional = true }}
workspace_dep = {{ workspace = true, optional = true }}
{late_dependency}
[build-dependencies]
build_dep = {{ path = "../../build_dep" }}

[dev-dependencies]
dev_dep = {{ path = "../../dev_dep" }}

[target.'cfg(target_os = "linux")'.dependencies]
target_dep = {{ path = "../../target_dep" }}
"#
                ),
            )
            .expect("write app manifest");
        }

        fn lock_path(&self) -> PathBuf {
            self.workspace_root.join("Cargo.lock")
        }

        fn manifest_path(&self) -> PathBuf {
            self.workspace_root.join("Cargo.toml")
        }

        fn generate_valid_lockfile(&self) {
            let output = Command::new("cargo")
                .arg("generate-lockfile")
                .arg("--offline")
                .arg("--manifest-path")
                .arg(self.manifest_path())
                .env("CARGO_HOME", &self.cargo_home)
                .output()
                .expect("run real cargo generate-lockfile");
            assert!(
                output.status.success(),
                "cargo generate-lockfile failed: {}",
                String::from_utf8_lossy(&output.stderr)
            );
            assert!(self.lock_path().is_file(), "Cargo generated the lockfile");
        }

        fn make_generated_lock_stale(&mut self) {
            write_lib_crate(&self.late_dep_root, "late_dep", &[]);
            self.expected_roots.insert(
                self.late_dep_root
                    .canonicalize()
                    .expect("canonical late dependency"),
            );
            Self::write_app_manifest(&self.app_root, true);
        }

        fn resolve_planned_roots(&self) -> BTreeSet<PathBuf> {
            let plan = crate::build_dependency_closure_plan_with_policy(
                &self.workspace_root,
                &self.policy,
            );
            assert!(
                plan.is_ready(),
                "dependency plan must be ready; reason={:?}, issues={:?}",
                plan.fail_open_reason,
                plan.issues
            );
            plan.sync_order
                .iter()
                .map(|action| action.package_root.clone())
                .collect()
        }

        fn assert_discovers_every_path_root(&self) {
            assert_eq!(
                self.resolve_planned_roots(),
                self.expected_roots,
                "locked-metadata success or manifest fallback must preserve the complete path-root closure"
            );
        }
    }

    #[cfg(unix)]
    struct LockfileSnapshot {
        bytes: Vec<u8>,
        modified: std::time::SystemTime,
    }

    #[cfg(unix)]
    impl LockfileSnapshot {
        fn capture(path: &Path) -> Self {
            Self {
                bytes: fs::read(path).expect("read lockfile snapshot"),
                modified: fs::metadata(path)
                    .and_then(|metadata| metadata.modified())
                    .expect("read lockfile mtime"),
            }
        }

        fn arm_mtime_detection() {
            // Keep the pre-plan mtime outside common one-second timestamp
            // granularity. A byte-identical rewrite must still fail the mtime
            // assertion below instead of disappearing inside one clock tick.
            std::thread::sleep(std::time::Duration::from_millis(1100));
        }

        fn assert_unchanged(&self, path: &Path, scenario: &str) {
            assert_eq!(
                fs::read(path).expect("read lockfile after planning"),
                self.bytes,
                "{scenario}: dependency planning changed Cargo.lock bytes"
            );
            assert_eq!(
                fs::metadata(path)
                    .and_then(|metadata| metadata.modified())
                    .expect("read lockfile mtime after planning"),
                self.modified,
                "{scenario}: dependency planning changed Cargo.lock mtime"
            );
        }
    }

    /// bd-rch-pinned-metadata-lock-ytkda: with a VALID lockfile, dependency
    /// planning uses `cargo metadata --locked` and leaves the lockfile
    /// byte-for-byte and mtime-for-mtime untouched.
    #[cfg(unix)]
    #[test]
    fn valid_lockfile_planning_discovers_roots_without_mutating_the_lock() {
        let fixture = LockPlanningFixture::new("lock-valid");
        let lock_path = fixture.lock_path();
        fixture.generate_valid_lockfile();
        let snapshot = LockfileSnapshot::capture(&lock_path);
        LockfileSnapshot::arm_mtime_detection();

        invoke_cargo_metadata(&fixture.manifest_path())
            .expect("real cargo metadata --locked accepts the generated valid lock");
        fixture.assert_discovers_every_path_root();

        snapshot.assert_unchanged(&lock_path, "valid lockfile");
    }

    /// bd-rch-pinned-metadata-lock-ytkda: a STALE lockfile makes
    /// `cargo metadata --locked` refuse; planning falls back to manifest-only
    /// discovery, still finds the path roots, and never rewrites the stale
    /// lock (bytes and mtime preserved).
    #[cfg(unix)]
    #[test]
    fn stale_lockfile_planning_falls_back_without_rewriting_the_lock() {
        let mut fixture = LockPlanningFixture::new("lock-stale");
        fixture.generate_valid_lockfile();
        let lock_path = fixture.lock_path();
        fixture.make_generated_lock_stale();
        let snapshot = LockfileSnapshot::capture(&lock_path);
        LockfileSnapshot::arm_mtime_detection();

        let refusal = invoke_cargo_metadata(&fixture.manifest_path())
            .expect_err("real cargo metadata --locked must refuse a generated stale lock");
        assert_eq!(
            refusal.kind(),
            &CargoPathDependencyErrorKind::MetadataInvocationFailure
        );
        snapshot.assert_unchanged(&lock_path, "locked metadata refusal");

        fixture.assert_discovers_every_path_root();
        snapshot.assert_unchanged(&lock_path, "stale-lock fallback planning");
    }

    /// bd-rch-pinned-metadata-lock-ytkda: with NO lockfile, planning stays
    /// discoverable through the manifest-only fallback and must not create a
    /// `Cargo.lock` as a side effect (the historical mutation bug).
    #[cfg(unix)]
    #[test]
    fn missing_lockfile_planning_discovers_roots_without_creating_a_lock() {
        let fixture = LockPlanningFixture::new("lock-missing");
        let lock_path = fixture.lock_path();
        assert!(!lock_path.exists(), "fixture starts without a lockfile");

        let refusal = invoke_cargo_metadata(&fixture.manifest_path())
            .expect_err("real cargo metadata --locked must refuse an absent lock");
        assert_eq!(
            refusal.kind(),
            &CargoPathDependencyErrorKind::MetadataInvocationFailure
        );
        assert!(
            !lock_path.exists(),
            "locked metadata refusal must not create Cargo.lock"
        );

        fixture.assert_discovers_every_path_root();

        assert!(
            !lock_path.exists(),
            "dependency planning must never create a Cargo.lock in the user checkout"
        );
    }

    #[cfg(unix)]
    #[test]
    fn resolves_workspace_transitive_path_dependencies() {
        let fixture = TopologyFixture::new("workspace");
        let scenario_root = fixture.canonical_root.join("workspace_transitive");
        let workspace_root = scenario_root.join("workspace");
        let shared_root = scenario_root.join("shared/shared_lib");
        let util_root = workspace_root.join("crates/util");
        let app_root = workspace_root.join("crates/app");

        write_lib_crate(&shared_root, "workspace_shared", &[]);
        write_lib_crate(
            &util_root,
            "workspace_util",
            &[("workspace_shared", "../../../shared/shared_lib")],
        );
        write_bin_crate(&app_root, "workspace_app", &[("workspace_util", "../util")]);
        fs::create_dir_all(&workspace_root).expect("create workspace root");
        fs::write(
            workspace_root.join("Cargo.toml"),
            "[workspace]\nmembers = [\"crates/app\", \"crates/util\"]\nresolver = \"3\"\n",
        )
        .expect("write workspace manifest");

        let graph =
            resolve_cargo_path_dependency_graph_with_policy(&workspace_root, &fixture.policy())
                .expect("resolve workspace graph");

        let app_root = app_root.canonicalize().expect("canonical app root");
        let util_root = util_root.canonicalize().expect("canonical util root");
        let shared_root = shared_root.canonicalize().expect("canonical shared root");
        assert_eq!(
            graph.root_packages,
            vec![app_root.clone(), util_root.clone()]
        );
        let package_roots = graph
            .packages
            .iter()
            .map(|package| package.package_root.clone())
            .collect::<Vec<_>>();
        assert!(
            package_roots
                .windows(2)
                .all(|window| window[0] <= window[1]),
            "packages should be deterministically sorted"
        );
        assert_eq!(
            package_roots.into_iter().collect::<BTreeSet<_>>(),
            BTreeSet::from([app_root.clone(), shared_root.clone(), util_root.clone()])
        );
        assert_eq!(
            graph.edges,
            vec![
                CargoPathDependencyEdge {
                    from: app_root,
                    to: util_root.clone(),
                    dependency_name: "workspace_util".to_string(),
                },
                CargoPathDependencyEdge {
                    from: util_root,
                    to: shared_root,
                    dependency_name: "workspace_shared".to_string(),
                },
            ]
        );
    }

    #[cfg(unix)]
    #[test]
    fn resolves_virtual_workspace_members_from_alias_path() {
        let fixture = TopologyFixture::new("virtual-workspace");
        let scenario_root = fixture.canonical_root.join("virtual_workspace");
        let workspace_root = scenario_root.join("ws");
        let member_a = workspace_root.join("members/a");
        let member_b = workspace_root.join("members/b");

        write_lib_crate(&member_b, "virtual_b", &[]);
        write_lib_crate(&member_a, "virtual_a", &[("virtual_b", "../b")]);
        fs::create_dir_all(&workspace_root).expect("create workspace root");
        fs::write(
            workspace_root.join("Cargo.toml"),
            "[workspace]\nmembers = [\"members/a\", \"members/b\"]\nresolver = \"3\"\n",
        )
        .expect("write workspace manifest");

        let relative = workspace_root
            .strip_prefix(&fixture.canonical_root)
            .expect("workspace under canonical root");
        let alias_workspace = fixture.alias_root.join(relative);

        let graph =
            resolve_cargo_path_dependency_graph_with_policy(&alias_workspace, &fixture.policy())
                .expect("resolve virtual workspace graph");

        let member_a = member_a.canonicalize().expect("canonical member a");
        let member_b = member_b.canonicalize().expect("canonical member b");
        assert_eq!(
            graph.workspace_root,
            Some(
                workspace_root
                    .canonicalize()
                    .expect("canonical workspace root")
            )
        );
        assert_eq!(
            graph.root_packages,
            vec![member_a.clone(), member_b.clone()]
        );
        assert_eq!(
            graph.edges,
            vec![CargoPathDependencyEdge {
                from: member_a,
                to: member_b,
                dependency_name: "virtual_b".to_string(),
            }]
        );
    }

    #[cfg(unix)]
    #[test]
    fn resolves_nested_manifest_transitive_closure() {
        let fixture = TopologyFixture::new("nested");
        let scenario_root = fixture.canonical_root.join("nested_manifests");
        let app_root = scenario_root.join("app");
        let util_root = scenario_root.join("libs/util");
        let core_root = scenario_root.join("libs/core");

        write_lib_crate(&core_root, "nested_core", &[]);
        write_lib_crate(&util_root, "nested_util", &[("nested_core", "../core")]);
        write_bin_crate(&app_root, "nested_app", &[("nested_util", "../libs/util")]);

        let graph = resolve_cargo_path_dependency_graph_with_policy(
            &app_root.join("Cargo.toml"),
            &fixture.policy(),
        )
        .expect("resolve nested manifest graph");

        let app_root = app_root.canonicalize().expect("canonical app");
        let util_root = util_root.canonicalize().expect("canonical util");
        let core_root = core_root.canonicalize().expect("canonical core");
        assert_eq!(graph.root_packages, vec![app_root.clone()]);
        assert_eq!(
            graph.edges,
            vec![
                CargoPathDependencyEdge {
                    from: app_root,
                    to: util_root.clone(),
                    dependency_name: "nested_util".to_string(),
                },
                CargoPathDependencyEdge {
                    from: util_root,
                    to: core_root,
                    dependency_name: "nested_core".to_string(),
                },
            ]
        );
    }

    #[cfg(unix)]
    #[test]
    fn malformed_metadata_uses_manifest_fallback() {
        let fixture = TopologyFixture::new("malformed-metadata");
        let scenario_root = fixture.canonical_root.join("metadata_fallback");
        let app_root = scenario_root.join("app");
        let dep_root = scenario_root.join("dep");

        write_lib_crate(&dep_root, "fallback_dep", &[]);
        write_bin_crate(&app_root, "fallback_app", &[("fallback_dep", "../dep")]);

        let graph = resolve_cargo_path_dependency_graph_with_policy_and_provider(
            &app_root,
            &fixture.policy(),
            |_| Ok("{not-json".to_string()),
        )
        .expect("resolver should recover using fallback");

        let app_root = app_root.canonicalize().expect("canonical app");
        let dep_root = dep_root.canonicalize().expect("canonical dep");
        assert_eq!(graph.root_packages, vec![app_root.clone()]);
        assert_eq!(
            graph.edges,
            vec![CargoPathDependencyEdge {
                from: app_root,
                to: dep_root,
                dependency_name: "fallback_dep".to_string(),
            }]
        );
    }

    #[cfg(unix)]
    #[test]
    fn malformed_manifest_reports_manifest_parse_failure() {
        let fixture = TopologyFixture::new("manifest-error");
        let config = MultiRepoFixtureConfig::new(
            fixture.canonical_root.clone(),
            fixture.alias_root.clone(),
            "resolver_manifest_error",
        );
        let fixtures = reset_multi_repo_fixtures(&config).expect("generate fixture set");
        let invalid = fixtures
            .fixture("fail_invalid_manifest")
            .expect("invalid fixture metadata");

        let error = resolve_cargo_path_dependency_graph_with_policy(
            &invalid.canonical_entrypoint,
            &fixture.policy(),
        )
        .expect_err("invalid manifest must fail");
        assert_eq!(
            error.kind(),
            &CargoPathDependencyErrorKind::ManifestParseFailure
        );
    }

    #[cfg(unix)]
    #[test]
    fn missing_path_reports_missing_dependency_kind() {
        let fixture = TopologyFixture::new("missing-path");
        let config = MultiRepoFixtureConfig::new(
            fixture.canonical_root.clone(),
            fixture.alias_root.clone(),
            "resolver_missing_path",
        );
        let fixtures = reset_multi_repo_fixtures(&config).expect("generate fixture set");
        let missing = fixtures
            .fixture("fail_missing_path_dep")
            .expect("missing fixture metadata");

        let error = resolve_cargo_path_dependency_graph_with_policy(
            &missing.canonical_entrypoint,
            &fixture.policy(),
        )
        .expect_err("missing dependency must fail");
        assert_eq!(
            error.kind(),
            &CargoPathDependencyErrorKind::MissingPathDependency
        );
    }

    #[cfg(unix)]
    #[test]
    fn outside_root_reports_path_policy_violation() {
        let fixture = TopologyFixture::new("outside-root");
        let config = MultiRepoFixtureConfig::new(
            fixture.canonical_root.clone(),
            fixture.alias_root.clone(),
            "resolver_outside_root",
        );
        let fixtures = reset_multi_repo_fixtures(&config).expect("generate fixture set");
        let outside = fixtures
            .fixture("fail_outside_canonical_dep")
            .expect("outside fixture metadata");

        let error = resolve_cargo_path_dependency_graph_with_policy(
            &outside.canonical_entrypoint,
            &fixture.policy(),
        )
        .expect_err("outside root dependency must fail");
        assert_eq!(
            error.kind(),
            &CargoPathDependencyErrorKind::PathPolicyViolation
        );
    }

    #[cfg(unix)]
    #[test]
    fn resolved_alias_target_is_allowed_for_absolute_dependency_scope() {
        let fixture = TopologyFixture::new("resolved-alias-target");
        let alias_target_root = fixture
            .alias_root
            .canonicalize()
            .expect("resolve alias target root");
        let dependency_candidate = alias_target_root.join("repo/crate_dep");

        validate_absolute_dependency_scope(
            &dependency_candidate,
            &fixture.policy(),
            Path::new("/tmp/Cargo.toml"),
            "crate_dep",
            "metadata dependency path policy violation",
        )
        .expect("resolved alias target should be accepted");
    }

    #[cfg(unix)]
    #[test]
    fn cyclic_path_dependencies_report_cycle_kind() {
        let fixture = TopologyFixture::new("cycle");
        let scenario_root = fixture.canonical_root.join("cycle");
        let crate_a = scenario_root.join("a");
        let crate_b = scenario_root.join("b");

        write_lib_crate(&crate_a, "cycle_a", &[("cycle_b", "../b")]);
        write_lib_crate(&crate_b, "cycle_b", &[("cycle_a", "../a")]);

        let error = resolve_cargo_path_dependency_graph_with_policy(&crate_a, &fixture.policy())
            .expect_err("cyclic path dependencies must fail");
        assert_eq!(
            error.kind(),
            &CargoPathDependencyErrorKind::CyclicDependency
        );
        assert!(
            error.cycle().len() >= 3,
            "cycle path should include repeated terminal node"
        );
    }

    #[cfg(unix)]
    #[test]
    fn optional_path_dependency_cycle_is_ignored_for_active_closure() {
        let fixture = TopologyFixture::new("optional-cycle");
        let scenario_root = fixture.canonical_root.join("optional_cycle");
        let app_root = scenario_root.join("app");
        let real_dep_root = scenario_root.join("real_dep");
        let optional_a_root = scenario_root.join("optional_a");
        let optional_b_root = scenario_root.join("optional_b");

        write_lib_crate(&real_dep_root, "real_dep", &[]);
        write_lib_crate(
            &optional_a_root,
            "optional_a",
            &[("optional_b", "../optional_b")],
        );
        write_lib_crate(
            &optional_b_root,
            "optional_b",
            &[("optional_a", "../optional_a")],
        );

        fs::create_dir_all(app_root.join("src")).expect("create app src");
        fs::write(
            app_root.join("Cargo.toml"),
            r#"[package]
name = "optional_cycle_app"
version = "0.1.0"
edition = "2024"

[dependencies]
real_dep = { path = "../real_dep" }
optional_a = { path = "../optional_a", optional = true }
"#,
        )
        .expect("write app manifest");
        fs::write(app_root.join("src/main.rs"), "fn main() {}\n").expect("write app main");

        let graph = resolve_cargo_path_dependency_graph_with_policy(&app_root, &fixture.policy())
            .expect("optional cycle should not poison active dependency closure");
        let materialization =
            resolve_cargo_path_materialization_closure_with_policy(&app_root, &fixture.policy())
                .expect("optional cycle should terminate in materialization closure");

        let app_root = app_root.canonicalize().expect("canonical app");
        let real_dep_root = real_dep_root.canonicalize().expect("canonical real dep");
        let optional_a_root = optional_a_root
            .canonicalize()
            .expect("canonical optional a");
        let optional_b_root = optional_b_root
            .canonicalize()
            .expect("canonical optional b");
        assert_eq!(graph.root_packages, vec![app_root.clone()]);
        assert_eq!(
            graph.edges,
            vec![CargoPathDependencyEdge {
                from: app_root.clone(),
                to: real_dep_root.clone(),
                dependency_name: "real_dep".to_string(),
            }]
        );

        let materialized_roots = materialization
            .packages
            .iter()
            .map(|package| package.package_root.clone())
            .collect::<BTreeSet<_>>();
        assert_eq!(
            materialized_roots,
            BTreeSet::from([
                app_root.clone(),
                real_dep_root.clone(),
                optional_a_root.clone(),
                optional_b_root.clone(),
            ]),
            "inactive optional packages must still be available for remote materialization"
        );
        assert_eq!(
            materialization
                .edges
                .iter()
                .cloned()
                .collect::<BTreeSet<_>>(),
            BTreeSet::from([
                CargoPathDependencyEdge {
                    from: app_root.clone(),
                    to: real_dep_root,
                    dependency_name: "real_dep".to_string(),
                },
                CargoPathDependencyEdge {
                    from: optional_a_root.clone(),
                    to: optional_b_root.clone(),
                    dependency_name: "optional_b".to_string(),
                },
                CargoPathDependencyEdge {
                    from: optional_b_root,
                    to: optional_a_root.clone(),
                    dependency_name: "optional_a".to_string(),
                },
                CargoPathDependencyEdge {
                    from: app_root,
                    to: optional_a_root,
                    dependency_name: "optional_a".to_string(),
                },
            ]),
            "materialization evidence should retain the optional cycle without traversing forever"
        );
    }

    #[cfg(unix)]
    #[test]
    fn materialization_closure_covers_every_manifest_path_dependency_class() {
        let fixture = TopologyFixture::new("materialization-all-kinds");
        let scenario_root = fixture
            .canonical_root
            .join("materialization_all_dependency_kinds");
        let workspace_root = scenario_root.join("workspace");
        let app_root = workspace_root.join("app");
        let build_dep_root = scenario_root.join("build_dep");
        let dev_dep_root = scenario_root.join("dev_dep");
        let optional_dep_root = scenario_root.join("optional_dep");
        let patched_dep_root = scenario_root.join("patched_dep");
        let target_dep_root = scenario_root.join("target_dep");
        let transitive_dep_root = scenario_root.join("transitive_dep");
        let unused_patch_dep_root = scenario_root.join("unused_patch_dep");
        let workspace_dep_root = scenario_root.join("workspace_dep");

        write_lib_crate(&build_dep_root, "build_dep", &[]);
        write_lib_crate(&dev_dep_root, "dev_dep", &[]);
        write_lib_crate(
            &optional_dep_root,
            "optional_dep",
            &[("transitive_dep", "../transitive_dep")],
        );
        write_lib_crate(&patched_dep_root, "patched_dep", &[]);
        write_lib_crate(&target_dep_root, "target_dep", &[]);
        write_lib_crate(&transitive_dep_root, "transitive_dep", &[]);
        write_lib_crate(&unused_patch_dep_root, "unused_patch_dep", &[]);
        write_lib_crate(&workspace_dep_root, "workspace_dep", &[]);

        fs::create_dir_all(app_root.join("src")).expect("create app src");
        fs::write(
            app_root.join("Cargo.toml"),
            r#"[package]
name = "materialization_app"
version = "0.1.0"
edition = "2024"

[dependencies]
optional_dep = { path = "../../optional_dep", optional = true }
patched_dep = "0.1"
workspace_dep = { workspace = true, optional = true }

[build-dependencies]
build_dep = { path = "../../build_dep" }

[dev-dependencies]
dev_dep = { path = "../../dev_dep" }

[target.'cfg(target_os = "linux")'.dependencies]
target_dep = { path = "../../target_dep" }
"#,
        )
        .expect("write app manifest");
        fs::write(app_root.join("src/lib.rs"), "pub fn app() {}\n").expect("write app lib");
        fs::create_dir_all(&workspace_root).expect("create workspace root");
        fs::write(
            workspace_root.join("Cargo.toml"),
            r#"[workspace]
members = ["app"]
resolver = "3"

[workspace.dependencies]
workspace_dep = { path = "../workspace_dep" }

[patch.crates-io]
patched_dep = { path = "../patched_dep" }
unused_patch_dep = { path = "../unused_patch_dep" }
"#,
        )
        .expect("write workspace manifest");

        let first = resolve_cargo_path_materialization_closure_with_policy(
            &workspace_root,
            &fixture.policy(),
        )
        .expect("resolve complete materialization closure");
        let second = resolve_cargo_path_materialization_closure_with_policy(
            &workspace_root,
            &fixture.policy(),
        )
        .expect("repeat complete materialization closure");
        assert_eq!(first, second, "materialization must be deterministic");

        let expected_roots = [
            &app_root,
            &build_dep_root,
            &dev_dep_root,
            &optional_dep_root,
            &patched_dep_root,
            &target_dep_root,
            &transitive_dep_root,
            &unused_patch_dep_root,
            &workspace_dep_root,
        ]
        .into_iter()
        .map(|root| root.canonicalize().expect("canonical fixture package"))
        .collect::<BTreeSet<_>>();
        let observed_roots = first
            .packages
            .iter()
            .map(|package| package.package_root.clone())
            .collect::<BTreeSet<_>>();
        assert_eq!(observed_roots, expected_roots);

        let dependency_names = first
            .edges
            .iter()
            .map(|edge| edge.dependency_name.as_str())
            .collect::<BTreeSet<_>>();
        assert_eq!(
            dependency_names,
            BTreeSet::from([
                "build_dep",
                "dev_dep",
                "optional_dep",
                "patched_dep",
                "target_dep",
                "transitive_dep",
                "workspace_dep",
            ]),
            "normal, build, dev, target, optional, workspace, patch, and transitive paths must all materialize"
        );
    }

    // ── Error type construction and accessor tests ──

    #[test]
    fn error_kind_display_all_variants() {
        let variants = [
            (
                CargoPathDependencyErrorKind::ManifestParseFailure,
                "manifest parse failure",
            ),
            (
                CargoPathDependencyErrorKind::MissingPathDependency,
                "missing path dependency",
            ),
            (
                CargoPathDependencyErrorKind::CyclicDependency,
                "cyclic path dependency",
            ),
            (
                CargoPathDependencyErrorKind::PathPolicyViolation,
                "path policy violation",
            ),
            (
                CargoPathDependencyErrorKind::MetadataParseFailure,
                "metadata parse failure",
            ),
            (
                CargoPathDependencyErrorKind::MetadataInvocationFailure,
                "metadata invocation failure",
            ),
        ];
        for (kind, expected) in variants {
            assert_eq!(kind.to_string(), expected, "Display for {kind:?}");
        }
    }

    #[test]
    fn error_accessors_return_builder_values() {
        let error = CargoPathDependencyError::new(
            CargoPathDependencyErrorKind::MissingPathDependency,
            "test detail",
        )
        .with_manifest_path("/a/Cargo.toml")
        .with_dependency_name("dep_x")
        .with_dependency_path("/b/dep_x");

        assert_eq!(
            error.kind(),
            &CargoPathDependencyErrorKind::MissingPathDependency
        );
        assert_eq!(error.detail(), "test detail");
        assert_eq!(error.manifest_path(), Some(Path::new("/a/Cargo.toml")));
        assert_eq!(error.dependency_name(), Some("dep_x"));
        assert_eq!(error.dependency_path(), Some(Path::new("/b/dep_x")));
        assert!(error.cycle().is_empty());
        assert!(error.diagnostics().is_empty());
    }

    #[test]
    fn error_display_includes_all_fields() {
        let error = CargoPathDependencyError::new(
            CargoPathDependencyErrorKind::MissingPathDependency,
            "not found",
        )
        .with_manifest_path("/a/Cargo.toml")
        .with_dependency_name("missing_dep")
        .with_dependency_path("/b/missing");

        let display = error.to_string();
        assert!(
            display.contains("missing path dependency"),
            "should contain kind"
        );
        assert!(display.contains("not found"), "should contain detail");
        assert!(
            display.contains("/a/Cargo.toml"),
            "should contain manifest path"
        );
        assert!(
            display.contains("missing_dep"),
            "should contain dependency name"
        );
        assert!(
            display.contains("/b/missing"),
            "should contain dependency path"
        );
    }

    #[test]
    fn error_diagnostics_accumulate() {
        let error = CargoPathDependencyError::new(
            CargoPathDependencyErrorKind::MetadataParseFailure,
            "parse error",
        )
        .with_diagnostic("line 1")
        .with_diagnostics(["line 2", "line 3"]);

        assert_eq!(error.diagnostics().len(), 3);
        assert_eq!(error.diagnostics()[0], "line 1");
        assert_eq!(error.diagnostics()[1], "line 2");
        assert_eq!(error.diagnostics()[2], "line 3");
    }

    #[test]
    fn error_implements_std_error() {
        let error = CargoPathDependencyError::new(
            CargoPathDependencyErrorKind::ManifestParseFailure,
            "bad toml",
        );
        let _: &dyn std::error::Error = &error;
    }

    // ── Internal helper function tests ──

    #[test]
    fn default_package_name_uses_last_component() {
        assert_eq!(default_package_name(Path::new("/a/b/my_crate")), "my_crate");
        assert_eq!(default_package_name(Path::new("/single")), "single");
    }

    #[test]
    fn default_package_name_root_path_uses_display() {
        let name = default_package_name(Path::new("/"));
        assert!(
            !name.is_empty(),
            "root path should produce a non-empty name"
        );
    }

    #[test]
    fn resolve_dependency_candidate_relative_path() {
        let result = resolve_dependency_candidate(Path::new("/project/app"), "../lib");
        assert_eq!(result, PathBuf::from("/project/app/../lib"));
    }

    #[test]
    fn resolve_dependency_candidate_absolute_path() {
        let result = resolve_dependency_candidate(Path::new("/project/app"), "/other/lib");
        assert_eq!(result, PathBuf::from("/other/lib"));
    }

    #[test]
    fn resolve_dependency_candidate_strips_cargo_toml_suffix() {
        let result = resolve_dependency_candidate(Path::new("/project/app"), "../lib/Cargo.toml");
        assert_eq!(result, PathBuf::from("/project/app/../lib"));
    }

    #[test]
    fn resolve_dependency_candidate_preserves_non_cargo_toml() {
        let result = resolve_dependency_candidate(Path::new("/project/app"), "../lib/src");
        assert_eq!(result, PathBuf::from("/project/app/../lib/src"));
    }

    // ── Wildcard / glob helper tests ──

    #[test]
    fn contains_glob_detects_patterns() {
        assert!(contains_glob("crates/*"));
        assert!(contains_glob("lib?"));
        assert!(contains_glob("[abc]"));
        assert!(!contains_glob("plain_path"));
        assert!(!contains_glob(""));
    }

    #[test]
    fn contains_wildcard_detects_star_and_question() {
        assert!(contains_wildcard("*"));
        assert!(contains_wildcard("foo*"));
        assert!(contains_wildcard("fo?"));
        assert!(!contains_wildcard("plain"));
        assert!(!contains_wildcard("[abc]"));
    }

    #[test]
    fn wildcard_match_exact() {
        assert!(wildcard_match("hello", "hello"));
        assert!(!wildcard_match("hello", "world"));
    }

    #[test]
    fn wildcard_match_star_patterns() {
        assert!(wildcard_match("*", "anything"));
        assert!(wildcard_match("*", ""));
        assert!(wildcard_match("he*o", "hello"));
        assert!(wildcard_match("he*o", "heo"));
        assert!(!wildcard_match("he*o", "hex"));
        assert!(wildcard_match("*.*", "file.rs"));
        assert!(!wildcard_match("*.*", "nodot"));
    }

    #[test]
    fn wildcard_match_question_mark() {
        assert!(wildcard_match("h?llo", "hello"));
        assert!(wildcard_match("h?llo", "hallo"));
        assert!(!wildcard_match("h?llo", "hllo"));
        assert!(!wildcard_match("?", ""));
    }

    #[test]
    fn wildcard_match_combined() {
        assert!(wildcard_match("rch-*", "rch-common"));
        assert!(wildcard_match("rch-*", "rch-"));
        assert!(!wildcard_match("rch-*", "rch"));
    }

    #[test]
    fn wildcard_match_empty_pattern_and_value() {
        assert!(wildcard_match("", ""));
        assert!(!wildcard_match("", "x"));
        assert!(wildcard_match("*", ""));
    }

    // ── cycle_from_stack tests ──

    #[test]
    fn cycle_from_stack_extracts_cycle_segment() {
        let stack = vec![
            PathBuf::from("/a"),
            PathBuf::from("/b"),
            PathBuf::from("/c"),
        ];
        let cycle = cycle_from_stack(&stack, Path::new("/b"));
        assert_eq!(
            cycle,
            vec![
                PathBuf::from("/b"),
                PathBuf::from("/c"),
                PathBuf::from("/b"),
            ]
        );
    }

    #[test]
    fn cycle_from_stack_terminal_not_in_stack() {
        let stack = vec![PathBuf::from("/a")];
        let cycle = cycle_from_stack(&stack, Path::new("/z"));
        assert_eq!(cycle, vec![PathBuf::from("/z")]);
    }

    #[test]
    fn cycle_from_stack_single_node_self_cycle() {
        let stack = vec![PathBuf::from("/a")];
        let cycle = cycle_from_stack(&stack, Path::new("/a"));
        assert_eq!(cycle, vec![PathBuf::from("/a"), PathBuf::from("/a")]);
    }

    #[test]
    fn cycle_from_stack_empty_stack() {
        let stack: Vec<PathBuf> = vec![];
        let cycle = cycle_from_stack(&stack, Path::new("/a"));
        assert_eq!(cycle, vec![PathBuf::from("/a")]);
    }

    // ── finalize_graph tests ──

    #[test]
    fn finalize_empty_graph() {
        let partial = PartialGraph::default();
        let graph =
            finalize_graph(PathBuf::from("/fake/Cargo.toml"), partial).expect("should succeed");
        assert!(graph.packages.is_empty());
        assert!(graph.edges.is_empty());
        assert!(graph.root_packages.is_empty());
        assert!(graph.workspace_root.is_none());
    }

    #[test]
    fn finalize_graph_single_root_no_edges() {
        let mut partial = PartialGraph::default();
        partial.add_root(PathBuf::from("/project"));
        partial.add_package(
            PathBuf::from("/project"),
            PathBuf::from("/project/Cargo.toml"),
            "my_project".to_string(),
            true,
        );

        let graph =
            finalize_graph(PathBuf::from("/project/Cargo.toml"), partial).expect("should succeed");
        assert_eq!(graph.packages.len(), 1);
        assert_eq!(graph.packages[0].package_name, "my_project");
        assert!(graph.packages[0].workspace_member);
        assert!(graph.edges.is_empty());
        assert_eq!(graph.root_packages, vec![PathBuf::from("/project")]);
    }

    #[test]
    fn finalize_graph_unreachable_packages_excluded() {
        let mut partial = PartialGraph::default();
        partial.add_root(PathBuf::from("/root"));
        partial.add_package(
            PathBuf::from("/root"),
            PathBuf::from("/root/Cargo.toml"),
            "root_pkg".to_string(),
            true,
        );
        // Add an unreachable package (no edge from root)
        partial.add_package(
            PathBuf::from("/orphan"),
            PathBuf::from("/orphan/Cargo.toml"),
            "orphan_pkg".to_string(),
            false,
        );

        let graph =
            finalize_graph(PathBuf::from("/root/Cargo.toml"), partial).expect("should succeed");
        assert_eq!(graph.packages.len(), 1, "orphan should be excluded");
        assert_eq!(graph.packages[0].package_name, "root_pkg");
    }

    #[test]
    fn finalize_graph_detects_cycle() {
        let mut partial = PartialGraph::default();
        partial.add_root(PathBuf::from("/a"));
        partial.add_package(
            PathBuf::from("/a"),
            PathBuf::from("/a/Cargo.toml"),
            "a".to_string(),
            true,
        );
        partial.add_package(
            PathBuf::from("/b"),
            PathBuf::from("/b/Cargo.toml"),
            "b".to_string(),
            false,
        );
        partial.add_edge(PathBuf::from("/a"), PathBuf::from("/b"), "b".to_string());
        partial.add_edge(PathBuf::from("/b"), PathBuf::from("/a"), "a".to_string());

        let error = finalize_graph(PathBuf::from("/a/Cargo.toml"), partial)
            .expect_err("should detect cycle");
        assert_eq!(
            error.kind(),
            &CargoPathDependencyErrorKind::CyclicDependency
        );
        assert!(
            error.cycle().len() >= 2,
            "cycle should include at least the two nodes"
        );
    }

    #[test]
    fn finalize_graph_diamond_reachable() {
        // A -> B, A -> C, B -> D, C -> D
        let mut partial = PartialGraph::default();
        partial.add_root(PathBuf::from("/a"));
        for (name, root) in [("a", "/a"), ("b", "/b"), ("c", "/c"), ("d", "/d")] {
            partial.add_package(
                PathBuf::from(root),
                PathBuf::from(format!("{root}/Cargo.toml")),
                name.to_string(),
                name == "a",
            );
        }
        partial.add_edge(PathBuf::from("/a"), PathBuf::from("/b"), "b".to_string());
        partial.add_edge(PathBuf::from("/a"), PathBuf::from("/c"), "c".to_string());
        partial.add_edge(PathBuf::from("/b"), PathBuf::from("/d"), "d".to_string());
        partial.add_edge(PathBuf::from("/c"), PathBuf::from("/d"), "d".to_string());

        let graph =
            finalize_graph(PathBuf::from("/a/Cargo.toml"), partial).expect("should succeed");
        assert_eq!(graph.packages.len(), 4, "all 4 nodes reachable in diamond");
        assert_eq!(graph.edges.len(), 4, "all 4 edges present");
        // Packages should be sorted by BTreeSet order
        let names: Vec<_> = graph
            .packages
            .iter()
            .map(|p| p.package_name.as_str())
            .collect();
        assert_eq!(names, vec!["a", "b", "c", "d"]);
    }

    // ── Graph serialization round-trip ──

    #[test]
    fn graph_serialization_round_trip() {
        let graph = CargoPathDependencyGraph {
            entry_manifest_path: PathBuf::from("/project/Cargo.toml"),
            workspace_root: Some(PathBuf::from("/project")),
            root_packages: vec![PathBuf::from("/project/app")],
            packages: vec![
                CargoPathDependencyPackage {
                    package_root: PathBuf::from("/project/app"),
                    manifest_path: PathBuf::from("/project/app/Cargo.toml"),
                    package_name: "app".to_string(),
                    workspace_member: true,
                },
                CargoPathDependencyPackage {
                    package_root: PathBuf::from("/project/lib"),
                    manifest_path: PathBuf::from("/project/lib/Cargo.toml"),
                    package_name: "lib".to_string(),
                    workspace_member: true,
                },
            ],
            edges: vec![CargoPathDependencyEdge {
                from: PathBuf::from("/project/app"),
                to: PathBuf::from("/project/lib"),
                dependency_name: "lib".to_string(),
            }],
        };

        let json = serde_json::to_string(&graph).expect("serialize");
        let deserialized: CargoPathDependencyGraph =
            serde_json::from_str(&json).expect("deserialize");
        assert_eq!(graph, deserialized);
    }

    // ── Edge type ordering ──

    #[test]
    fn edge_ordering_is_deterministic() {
        let edge_a = CargoPathDependencyEdge {
            from: PathBuf::from("/a"),
            to: PathBuf::from("/b"),
            dependency_name: "b".to_string(),
        };
        let edge_b = CargoPathDependencyEdge {
            from: PathBuf::from("/a"),
            to: PathBuf::from("/c"),
            dependency_name: "c".to_string(),
        };
        let edge_c = CargoPathDependencyEdge {
            from: PathBuf::from("/b"),
            to: PathBuf::from("/c"),
            dependency_name: "c".to_string(),
        };

        let mut edges = vec![edge_c.clone(), edge_a.clone(), edge_b.clone()];
        edges.sort();
        assert_eq!(edges, vec![edge_a, edge_b, edge_c]);
    }

    // ── Metadata provider fallback tests ──

    #[cfg(unix)]
    #[test]
    fn metadata_error_then_fallback_success() {
        let fixture = TopologyFixture::new("meta-err-fallback");
        let scenario_root = fixture.canonical_root.join("meta_fallback");
        let app_root = scenario_root.join("app");
        let dep_root = scenario_root.join("dep");

        write_lib_crate(&dep_root, "fb_dep", &[]);
        write_bin_crate(&app_root, "fb_app", &[("fb_dep", "../dep")]);

        // Metadata provider returns an error, fallback should recover
        let graph = resolve_cargo_path_dependency_graph_with_policy_and_provider(
            &app_root,
            &fixture.policy(),
            |_| {
                Err(CargoPathDependencyError::new(
                    CargoPathDependencyErrorKind::MetadataInvocationFailure,
                    "simulated cargo metadata failure",
                ))
            },
        )
        .expect("should recover via manifest fallback");

        let app_root = app_root.canonicalize().expect("canonical app");
        let dep_root = dep_root.canonicalize().expect("canonical dep");
        assert_eq!(graph.root_packages, vec![app_root.clone()]);
        assert_eq!(graph.edges.len(), 1);
        assert_eq!(graph.edges[0].from, app_root);
        assert_eq!(graph.edges[0].to, dep_root);
    }

    #[cfg(unix)]
    #[test]
    fn metadata_provider_with_synthetic_json() {
        let fixture = TopologyFixture::new("synthetic-meta");
        let scenario_root = fixture.canonical_root.join("synth_meta");
        let app_root = scenario_root.join("app");
        let dep_root = scenario_root.join("dep");

        write_lib_crate(&dep_root, "synth_dep", &[]);
        write_bin_crate(&app_root, "synth_app", &[("synth_dep", "../dep")]);

        // Provide well-formed synthetic metadata JSON
        let app_canonical = app_root.canonicalize().expect("canonical app");
        let dep_canonical = dep_root.canonicalize().expect("canonical dep");
        let app_manifest = app_canonical.join("Cargo.toml");
        let dep_manifest = dep_canonical.join("Cargo.toml");

        let metadata_json = format!(
            r#"{{
                "packages": [
                    {{
                        "id": "synth_app 0.1.0 (path+file://{})",
                        "name": "synth_app",
                        "manifest_path": "{}",
                        "dependencies": [
                            {{"name": "synth_dep", "path": "{}"}}
                        ]
                    }},
                    {{
                        "id": "synth_dep 0.1.0 (path+file://{})",
                        "name": "synth_dep",
                        "manifest_path": "{}",
                        "dependencies": []
                    }}
                ],
                "workspace_members": [],
                "workspace_root": null,
                "resolve": {{
                    "root": "synth_app 0.1.0 (path+file://{})"
                }}
            }}"#,
            app_canonical.display(),
            app_manifest.display(),
            dep_canonical.display(),
            dep_canonical.display(),
            dep_manifest.display(),
            app_canonical.display(),
        );

        let json_clone = metadata_json.clone();
        let graph = resolve_cargo_path_dependency_graph_with_policy_and_provider(
            &app_root,
            &fixture.policy(),
            move |_| Ok(json_clone.clone()),
        )
        .expect("synthetic metadata should resolve");

        assert_eq!(graph.root_packages, vec![app_canonical.clone()]);
        assert_eq!(graph.edges.len(), 1);
        assert_eq!(graph.edges[0].dependency_name, "synth_dep");
    }

    #[cfg(unix)]
    #[test]
    fn metadata_resolve_ignores_pure_dev_path_edges() {
        let fixture = TopologyFixture::new("synthetic-meta-dev-filter");
        let scenario_root = fixture.canonical_root.join("synth_meta_dev_filter");
        let app_root = scenario_root.join("app");
        let dep_root = scenario_root.join("dep");
        let dev_dep_root = scenario_root.join("dev_dep");

        write_lib_crate(&dep_root, "runtime_dep", &[]);
        write_lib_crate(&dev_dep_root, "dev_only_dep", &[]);
        write_bin_crate(&app_root, "dev_filter_app", &[]);

        let app_canonical = app_root.canonicalize().expect("canonical app");
        let dep_canonical = dep_root.canonicalize().expect("canonical dep");
        let dev_dep_canonical = dev_dep_root.canonicalize().expect("canonical dev dep");
        let app_manifest = app_canonical.join("Cargo.toml");
        let dep_manifest = dep_canonical.join("Cargo.toml");
        let dev_dep_manifest = dev_dep_canonical.join("Cargo.toml");

        let metadata_json = format!(
            r#"{{
                "packages": [
                    {{
                        "id": "dev_filter_app 0.1.0 (path+file://{app_root})",
                        "name": "dev_filter_app",
                        "manifest_path": "{app_manifest}",
                        "dependencies": [
                            {{"name": "runtime_dep", "path": "{dep_root}"}},
                            {{"name": "dev_only_dep", "path": "{dev_dep_root}"}}
                        ]
                    }},
                    {{
                        "id": "runtime_dep 0.1.0 (path+file://{dep_root})",
                        "name": "runtime_dep",
                        "manifest_path": "{dep_manifest}",
                        "dependencies": []
                    }},
                    {{
                        "id": "dev_only_dep 0.1.0 (path+file://{dev_dep_root})",
                        "name": "dev_only_dep",
                        "manifest_path": "{dev_dep_manifest}",
                        "dependencies": []
                    }}
                ],
                "workspace_members": [],
                "workspace_root": null,
                "resolve": {{
                    "root": "dev_filter_app 0.1.0 (path+file://{app_root})",
                    "nodes": [
                        {{
                            "id": "dev_filter_app 0.1.0 (path+file://{app_root})",
                            "deps": [
                                {{
                                    "name": "runtime_dep",
                                    "pkg": "runtime_dep 0.1.0 (path+file://{dep_root})",
                                    "dep_kinds": [{{"kind": null, "target": null}}]
                                }},
                                {{
                                    "name": "dev_only_dep",
                                    "pkg": "dev_only_dep 0.1.0 (path+file://{dev_dep_root})",
                                    "dep_kinds": [{{"kind": "dev", "target": null}}]
                                }}
                            ]
                        }},
                        {{
                            "id": "runtime_dep 0.1.0 (path+file://{dep_root})",
                            "deps": []
                        }},
                        {{
                            "id": "dev_only_dep 0.1.0 (path+file://{dev_dep_root})",
                            "deps": []
                        }}
                    ]
                }}
            }}"#,
            app_root = app_canonical.display(),
            app_manifest = app_manifest.display(),
            dep_root = dep_canonical.display(),
            dep_manifest = dep_manifest.display(),
            dev_dep_root = dev_dep_canonical.display(),
            dev_dep_manifest = dev_dep_manifest.display(),
        );

        let json_clone = metadata_json.clone();
        let graph = resolve_cargo_path_dependency_graph_with_policy_and_provider(
            &app_root,
            &fixture.policy(),
            move |_| Ok(json_clone.clone()),
        )
        .expect("synthetic metadata with dev-only edge should resolve");

        assert_eq!(graph.root_packages, vec![app_canonical.clone()]);
        assert_eq!(
            graph.edges.len(),
            1,
            "pure dev-only path edges must be ignored"
        );
        assert_eq!(graph.edges[0].dependency_name, "runtime_dep");
        assert_eq!(graph.edges[0].from, app_canonical);
        assert_eq!(graph.edges[0].to, dep_canonical);
        assert!(
            graph
                .packages
                .iter()
                .all(|pkg| pkg.package_root != dev_dep_canonical),
            "dev-only dependency package should not be pulled into runtime closure"
        );
    }

    #[cfg(unix)]
    #[test]
    fn metadata_resolve_excludes_cargo_home_packages_inside_topology_root() {
        // Issue #77: with CARGO_HOME under canonical_root, registry and git
        // packages from Cargo's caches must not become closure packages. A
        // vendored (`[source] directory`) crate keeps its registry source id
        // but is a real local input, so it stays.
        let fixture = TopologyFixture::new("synthetic-meta-cargo-home");
        let scenario_root = fixture.canonical_root.join("synth_meta_cargo_home");
        let app_root = scenario_root.join("app");
        let cargo_home = scenario_root.join(".cargo");
        let registry_root = cargo_home.join("registry/src/index.crates.io-abc/itoa-1.0.15");
        let git_root = cargo_home.join("git/checkouts/gitdep-0123/abcdef0");
        let vendor_root = scenario_root.join("vendor/ryu");

        write_bin_crate(&app_root, "cargo_home_app", &[]);
        write_lib_crate(&registry_root, "itoa", &[]);
        write_lib_crate(&git_root, "gitdep", &[]);
        write_lib_crate(&vendor_root, "ryu", &[]);

        let app = app_root.canonicalize().expect("canonical app");
        let registry = registry_root.canonicalize().expect("canonical registry");
        let git = git_root.canonicalize().expect("canonical git");
        let vendor = vendor_root.canonicalize().expect("canonical vendor");
        let cargo_home = cargo_home.canonicalize().expect("canonical cargo home");
        let crates_io = "registry+https://github.com/rust-lang/crates.io-index";

        let metadata_json = format!(
            r#"{{
                "packages": [
                    {{"id": "app", "name": "cargo_home_app", "source": null,
                      "manifest_path": "{app}/Cargo.toml", "dependencies": []}},
                    {{"id": "itoa", "name": "itoa", "source": "{crates_io}",
                      "manifest_path": "{registry}/Cargo.toml", "dependencies": []}},
                    {{"id": "gitdep", "name": "gitdep", "source": "git+https://example.com/gitdep#abcdef0",
                      "manifest_path": "{git}/Cargo.toml", "dependencies": []}},
                    {{"id": "ryu", "name": "ryu", "source": "{crates_io}",
                      "manifest_path": "{vendor}/Cargo.toml", "dependencies": []}}
                ],
                "workspace_members": ["app"],
                "workspace_root": "{app}",
                "resolve": {{
                    "root": "app",
                    "nodes": [
                        {{"id": "app", "deps": [
                            {{"name": "itoa", "pkg": "itoa", "dep_kinds": [{{"kind": null, "target": null}}]}},
                            {{"name": "gitdep", "pkg": "gitdep", "dep_kinds": [{{"kind": null, "target": null}}]}},
                            {{"name": "ryu", "pkg": "ryu", "dep_kinds": [{{"kind": null, "target": null}}]}}
                        ]}},
                        {{"id": "itoa", "deps": []}},
                        {{"id": "gitdep", "deps": []}},
                        {{"id": "ryu", "deps": []}}
                    ]
                }}
            }}"#,
            app = app.display(),
            registry = registry.display(),
            git = git.display(),
            vendor = vendor.display(),
        );

        let package_roots = |cargo_home: Option<&Path>| {
            let json = metadata_json.clone();
            let graph = resolve_cargo_path_dependency_graph_with_cargo_home(
                &app_root,
                &fixture.policy(),
                move |_| Ok(json.clone()),
                cargo_home,
            )
            .expect("synthetic metadata should resolve");
            graph
                .packages
                .iter()
                .map(|package| package.package_root.clone())
                .collect::<BTreeSet<_>>()
        };

        assert_eq!(
            package_roots(Some(&cargo_home)),
            BTreeSet::from([app.clone(), vendor.clone()]),
            "Cargo-home registry/git packages must not enter the closure"
        );
        // Control: a Cargo home elsewhere leaves in-root sourced packages alone.
        assert_eq!(
            package_roots(Some(&fixture.root.join("elsewhere-cargo-home"))),
            BTreeSet::from([app, registry, git, vendor]),
        );
    }

    #[cfg(unix)]
    #[test]
    fn metadata_resolve_skips_non_local_packages_and_keeps_local_edges() {
        let fixture = TopologyFixture::new("synthetic-meta-nonlocal");
        let scenario_root = fixture.canonical_root.join("synth_meta_nonlocal");
        let app_root = scenario_root.join("app");
        let dep_root = scenario_root.join("dep");
        let external_root = fixture.root.join("external_registry/serde");

        write_lib_crate(&dep_root, "local_dep", &[]);
        write_bin_crate(&app_root, "meta_nonlocal_app", &[]);
        write_lib_crate(&external_root, "serde", &[]);

        let app_canonical = app_root.canonicalize().expect("canonical app");
        let dep_canonical = dep_root.canonicalize().expect("canonical dep");
        let external_canonical = external_root
            .canonicalize()
            .expect("canonical external dep");
        let app_manifest = app_canonical.join("Cargo.toml");
        let dep_manifest = dep_canonical.join("Cargo.toml");
        let external_manifest = external_canonical.join("Cargo.toml");

        let metadata_json = format!(
            r#"{{
                "packages": [
                    {{
                        "id": "meta_nonlocal_app 0.1.0 (path+file://{app_root})",
                        "name": "meta_nonlocal_app",
                        "manifest_path": "{app_manifest}",
                        "dependencies": [
                            {{"name": "local_dep", "path": "{dep_root}"}},
                            {{"name": "serde", "path": null}}
                        ]
                    }},
                    {{
                        "id": "local_dep 0.1.0 (path+file://{dep_root})",
                        "name": "local_dep",
                        "manifest_path": "{dep_manifest}",
                        "dependencies": []
                    }},
                    {{
                        "id": "serde 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
                        "name": "serde",
                        "manifest_path": "{external_manifest}",
                        "dependencies": []
                    }}
                ],
                "workspace_members": [
                    "meta_nonlocal_app 0.1.0 (path+file://{app_root})"
                ],
                "workspace_root": null,
                "resolve": {{
                    "root": "meta_nonlocal_app 0.1.0 (path+file://{app_root})",
                    "nodes": [
                        {{
                            "id": "meta_nonlocal_app 0.1.0 (path+file://{app_root})",
                            "deps": [
                                {{
                                    "name": "local_dep",
                                    "pkg": "local_dep 0.1.0 (path+file://{dep_root})",
                                    "dep_kinds": [{{"kind": null, "target": null}}]
                                }},
                                {{
                                    "name": "serde",
                                    "pkg": "serde 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
                                    "dep_kinds": [{{"kind": null, "target": null}}]
                                }}
                            ]
                        }},
                        {{
                            "id": "local_dep 0.1.0 (path+file://{dep_root})",
                            "deps": []
                        }},
                        {{
                            "id": "serde 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
                            "deps": []
                        }}
                    ]
                }}
            }}"#,
            app_root = app_canonical.display(),
            app_manifest = app_manifest.display(),
            dep_root = dep_canonical.display(),
            dep_manifest = dep_manifest.display(),
            external_manifest = external_manifest.display(),
        );

        let json_clone = metadata_json.clone();
        let graph = resolve_cargo_path_dependency_graph_with_policy_and_provider(
            &app_root,
            &fixture.policy(),
            move |_| Ok(json_clone.clone()),
        )
        .expect("synthetic metadata with non-local packages should still resolve");

        assert_eq!(graph.root_packages, vec![app_canonical.clone()]);
        assert_eq!(
            graph.edges,
            vec![CargoPathDependencyEdge {
                from: app_canonical.clone(),
                to: dep_canonical.clone(),
                dependency_name: "local_dep".to_string(),
            }]
        );
        assert!(
            graph
                .packages
                .iter()
                .all(|package| package.package_root != external_canonical),
            "non-local registry packages must not be pulled into the sync closure"
        );
    }

    #[cfg(unix)]
    #[test]
    fn manifest_fallback_ignores_pure_dev_path_edges() {
        let fixture = TopologyFixture::new("manifest-fallback-dev-filter");
        let scenario_root = fixture.canonical_root.join("manifest_fallback_dev_filter");
        let app_root = scenario_root.join("app");
        let dep_root = scenario_root.join("dep");
        let dev_dep_root = scenario_root.join("dev_dep");

        write_lib_crate(&dep_root, "runtime_dep", &[]);
        write_lib_crate(&dev_dep_root, "dev_only_dep", &[]);

        std::fs::create_dir_all(app_root.join("src")).expect("create app src");
        std::fs::write(
            app_root.join("Cargo.toml"),
            r#"[package]
name = "manifest_dev_filter_app"
version = "0.1.0"
edition = "2024"

[dependencies]
runtime_dep = { path = "../dep" }

[dev-dependencies]
dev_only_dep = { path = "../dev_dep" }
"#,
        )
        .expect("write app manifest");
        std::fs::write(app_root.join("src/main.rs"), "fn main() {}\n").expect("write app main");

        let graph = resolve_cargo_path_dependency_graph_with_policy_and_provider(
            &app_root,
            &fixture.policy(),
            |_| {
                Err(CargoPathDependencyError::new(
                    CargoPathDependencyErrorKind::MetadataInvocationFailure,
                    "force manifest fallback",
                ))
            },
        )
        .expect("manifest fallback should ignore pure dev-only path edges");

        let app_canonical = app_root.canonicalize().expect("canonical app");
        let dep_canonical = dep_root.canonicalize().expect("canonical dep");
        let dev_dep_canonical = dev_dep_root.canonicalize().expect("canonical dev dep");

        assert_eq!(graph.root_packages, vec![app_canonical.clone()]);
        assert_eq!(graph.edges.len(), 1);
        assert_eq!(graph.edges[0].dependency_name, "runtime_dep");
        assert_eq!(graph.edges[0].from, app_canonical);
        assert_eq!(graph.edges[0].to, dep_canonical);
        assert!(
            graph
                .packages
                .iter()
                .all(|pkg| pkg.package_root != dev_dep_canonical),
            "manifest fallback must not pull pure dev-only path deps into runtime closure"
        );
    }

    #[cfg(unix)]
    #[test]
    fn manifest_fallback_resolves_workspace_shared_path_dependencies() {
        let fixture = TopologyFixture::new("manifest-workspace-shared");
        let scenario_root = fixture.canonical_root.join("manifest_workspace_shared");
        let workspace_root = scenario_root.join("workspace");
        let app_root = workspace_root.join("crates/app");
        let shared_root = scenario_root.join("shared/shared_dep");

        write_lib_crate(&shared_root, "shared_dep", &[]);
        std::fs::create_dir_all(app_root.join("src")).expect("create app src");
        std::fs::write(
            app_root.join("Cargo.toml"),
            r#"[package]
name = "workspace_shared_app"
version = "0.1.0"
edition = "2024"

[dependencies]
shared_dep = { workspace = true }
"#,
        )
        .expect("write app manifest");
        std::fs::write(app_root.join("src/main.rs"), "fn main() {}\n").expect("write app main");
        std::fs::create_dir_all(&workspace_root).expect("create workspace root");
        std::fs::write(
            workspace_root.join("Cargo.toml"),
            r#"[workspace]
members = ["crates/app"]
resolver = "3"

[workspace.dependencies]
shared_dep = { path = "../shared/shared_dep" }
"#,
        )
        .expect("write workspace manifest");

        let graph = resolve_cargo_path_dependency_graph_with_policy_and_provider(
            &workspace_root,
            &fixture.policy(),
            |_| {
                Err(CargoPathDependencyError::new(
                    CargoPathDependencyErrorKind::MetadataInvocationFailure,
                    "force manifest fallback",
                ))
            },
        )
        .expect("manifest fallback should resolve workspace-shared path dependencies");

        let app_canonical = app_root.canonicalize().expect("canonical app");
        let shared_canonical = shared_root.canonicalize().expect("canonical shared dep");
        assert_eq!(graph.root_packages, vec![app_canonical.clone()]);
        assert_eq!(
            graph.edges,
            vec![CargoPathDependencyEdge {
                from: app_canonical,
                to: shared_canonical,
                dependency_name: "shared_dep".to_string(),
            }]
        );
    }

    #[cfg(unix)]
    #[test]
    fn manifest_fallback_resolves_foreign_workspace_inherited_path_dependencies() {
        let fixture = TopologyFixture::new("manifest-foreign-workspace-shared");
        let scenario_root = fixture
            .canonical_root
            .join("manifest_foreign_workspace_shared");
        let app_root = scenario_root.join("app");
        let foreign_workspace = scenario_root.join("foreign");
        let api_root = foreign_workspace.join("crates/api");
        let core_root = foreign_workspace.join("crates/core");

        write_lib_crate(&core_root, "foreign_core", &[]);
        std::fs::create_dir_all(api_root.join("src")).expect("create foreign api src");
        std::fs::write(
            api_root.join("Cargo.toml"),
            r#"[package]
name = "foreign_api"
version = "0.1.0"
edition = "2024"

[dependencies]
foreign_core = { workspace = true }
asupersync = { workspace = true }
"#,
        )
        .expect("write foreign api manifest");
        std::fs::write(api_root.join("src/lib.rs"), "pub fn api() {}\n")
            .expect("write foreign api lib");
        std::fs::write(
            foreign_workspace.join("Cargo.toml"),
            r#"[workspace]
members = ["crates/api", "crates/core"]
resolver = "3"

[workspace.dependencies]
foreign_core = { path = "crates/core" }
asupersync = "0.3.9"
"#,
        )
        .expect("write foreign workspace manifest");
        write_bin_crate(
            &app_root,
            "foreign_workspace_app",
            &[("foreign_api", "../foreign/crates/api")],
        );

        let graph = resolve_cargo_path_dependency_graph_with_policy_and_provider(
            &app_root,
            &fixture.policy(),
            |_| {
                Err(CargoPathDependencyError::new(
                    CargoPathDependencyErrorKind::MetadataInvocationFailure,
                    "force manifest fallback",
                ))
            },
        )
        .expect("manifest fallback should traverse the foreign workspace dependency");

        let app = app_root.canonicalize().expect("canonical app");
        let api = api_root.canonicalize().expect("canonical api");
        let core = core_root.canonicalize().expect("canonical core");
        assert_eq!(graph.root_packages, vec![app.clone()]);
        assert_eq!(
            graph.edges,
            vec![
                CargoPathDependencyEdge {
                    from: app,
                    to: api.clone(),
                    dependency_name: "foreign_api".to_string(),
                },
                CargoPathDependencyEdge {
                    from: api,
                    to: core,
                    dependency_name: "foreign_core".to_string(),
                },
            ]
        );
        let materialization =
            resolve_materialization_from_manifests(&app_root.join("Cargo.toml"), &fixture.policy())
                .expect("materialization fallback should retain the same foreign path closure");
        assert_eq!(materialization.edges, graph.edges);

        std::fs::write(
            foreign_workspace.join("Cargo.toml"),
            "[workspace]\nmembers = [\"crates/api\", \"crates/core\"]\nresolver = \"3\"\n\n[workspace.dependencies]\nasupersync = \"0.3.9\"\n",
        )
        .expect("remove inherited dependency declaration");
        let refusal = resolve_cargo_path_dependency_graph_with_policy_and_provider(
            &app_root,
            &fixture.policy(),
            |_| {
                Err(CargoPathDependencyError::new(
                    CargoPathDependencyErrorKind::MetadataInvocationFailure,
                    "force manifest fallback",
                ))
            },
        )
        .expect_err("missing foreign workspace dependency must fail closed");
        assert_eq!(
            refusal.kind(),
            &CargoPathDependencyErrorKind::ManifestParseFailure
        );
        assert!(
            refusal
                .detail()
                .contains("workspace-inherited dependency 'foreign_core' is not defined")
        );
    }

    #[cfg(unix)]
    #[test]
    fn manifest_fallback_resolves_patch_path_dependencies() {
        let fixture = TopologyFixture::new("manifest-patch-shared");
        let scenario_root = fixture.canonical_root.join("manifest_patch_shared");
        let workspace_root = scenario_root.join("workspace");
        let app_root = workspace_root.join("app");
        let patched_root = scenario_root.join("patched/patched_dep");

        write_lib_crate(&patched_root, "patched_dep", &[]);
        std::fs::create_dir_all(app_root.join("src")).expect("create app src");
        std::fs::write(
            app_root.join("Cargo.toml"),
            r#"[package]
name = "patched_app"
version = "0.1.0"
edition = "2024"

[dependencies]
patched_dep = "0.1"
"#,
        )
        .expect("write app manifest");
        std::fs::write(app_root.join("src/main.rs"), "fn main() {}\n").expect("write app main");
        std::fs::create_dir_all(&workspace_root).expect("create workspace root");
        std::fs::write(
            workspace_root.join("Cargo.toml"),
            r#"[workspace]
members = ["app"]
resolver = "3"

[patch.crates-io]
patched_dep = { path = "../patched/patched_dep" }
"#,
        )
        .expect("write workspace manifest");

        let graph = resolve_cargo_path_dependency_graph_with_policy_and_provider(
            &workspace_root,
            &fixture.policy(),
            |_| {
                Err(CargoPathDependencyError::new(
                    CargoPathDependencyErrorKind::MetadataInvocationFailure,
                    "force manifest fallback",
                ))
            },
        )
        .expect("manifest fallback should resolve patch path dependencies");

        let app_canonical = app_root.canonicalize().expect("canonical app");
        let patched_canonical = patched_root.canonicalize().expect("canonical patched dep");
        assert_eq!(graph.root_packages, vec![app_canonical.clone()]);
        assert_eq!(
            graph.edges,
            vec![CargoPathDependencyEdge {
                from: app_canonical,
                to: patched_canonical,
                dependency_name: "patched_dep".to_string(),
            }]
        );
    }

    #[cfg(unix)]
    #[test]
    fn manifest_fallback_accepts_absolute_deps_that_normalize_under_policy() {
        let id = FIXTURE_COUNTER.fetch_add(1, Ordering::SeqCst);
        let root = std::env::temp_dir().join(format!(
            "rch-cargo-path-deps-mixed-roots-{}-{}",
            std::process::id(),
            id
        ));
        let user_root = root.join("users/jemanuel");
        let user_projects = user_root.join("projects");
        let user_dp = user_root.join("dp");
        let dp_alias = root.join("dp");
        let data_projects = root.join("data/projects");
        let app_root = user_projects.join("app");
        let data_dep_link = data_projects.join("asupersync");
        let projects_dep_link = user_projects.join("asupersync");
        let asupersync_root = user_dp.join("asupersync");
        let frankentui_root = user_dp.join("frankentui");

        fs::create_dir_all(&app_root).expect("create app root");
        fs::create_dir_all(&data_projects).expect("create data projects root");
        write_lib_crate(&asupersync_root, "asupersync", &[]);
        write_lib_crate(&frankentui_root, "frankentui", &[]);
        symlink(&user_dp, &dp_alias).expect("create /dp-style alias");
        symlink(&asupersync_root, &projects_dep_link).expect("create canonical project symlink");
        symlink(&projects_dep_link, &data_dep_link).expect("create /data/projects symlink entry");

        let manifest = format!(
            "[package]\nname = \"mixed_roots_app\"\nversion = \"0.1.0\"\nedition = \"2024\"\n\n[dependencies]\nasupersync = {{ path = \"{}\" }}\nfrankentui = {{ path = \"{}\" }}\n",
            data_dep_link.display(),
            dp_alias.join("frankentui").display(),
        );
        fs::create_dir_all(app_root.join("src")).expect("create app src");
        fs::write(app_root.join("Cargo.toml"), manifest).expect("write app manifest");
        fs::write(app_root.join("src/lib.rs"), "pub fn app() {}\n").expect("write app lib");

        let policy = PathTopologyPolicy::new(user_root.clone(), dp_alias);
        let graph = resolve_cargo_path_dependency_graph_with_policy_and_provider(
            &app_root,
            &policy,
            |_| {
                Err(CargoPathDependencyError::new(
                    CargoPathDependencyErrorKind::MetadataInvocationFailure,
                    "force manifest fallback",
                ))
            },
        )
        .expect("mixed absolute dependency roots should normalize under policy");

        let dependency_roots = graph
            .edges
            .iter()
            .map(|edge| (edge.dependency_name.as_str(), edge.to.clone()))
            .collect::<BTreeMap<_, _>>();
        assert_eq!(
            dependency_roots.get("asupersync"),
            Some(
                &asupersync_root
                    .canonicalize()
                    .expect("canonical asupersync")
            )
        );
        assert_eq!(
            dependency_roots.get("frankentui"),
            Some(
                &frankentui_root
                    .canonicalize()
                    .expect("canonical frankentui")
            )
        );

        let _ = fs::remove_dir_all(root);
    }

    #[cfg(unix)]
    #[test]
    fn standalone_crate_no_dependencies() {
        let fixture = TopologyFixture::new("standalone");
        let crate_root = fixture.canonical_root.join("standalone_crate");

        write_bin_crate(&crate_root, "standalone", &[]);

        let graph = resolve_cargo_path_dependency_graph_with_policy_and_provider(
            &crate_root,
            &fixture.policy(),
            |_| Ok("{not-json".to_string()), // force fallback
        )
        .expect("standalone crate should resolve");

        assert_eq!(graph.packages.len(), 1);
        assert_eq!(graph.packages[0].package_name, "standalone");
        assert!(graph.edges.is_empty());
    }

    // ── PartialGraph internal behavior ──

    #[test]
    fn partial_graph_deduplicates_edges() {
        let mut partial = PartialGraph::default();
        partial.add_edge(PathBuf::from("/a"), PathBuf::from("/b"), "b".to_string());
        partial.add_edge(PathBuf::from("/a"), PathBuf::from("/b"), "b".to_string());

        let edges = partial.adjacency.get(Path::new("/a")).unwrap();
        assert_eq!(
            edges.len(),
            1,
            "duplicate edge should be deduplicated by BTreeSet"
        );
    }

    #[test]
    fn partial_graph_add_package_updates_name_from_default() {
        let mut partial = PartialGraph::default();
        let root = PathBuf::from("/project/my_crate");

        // First add with default name
        partial.add_package(
            root.clone(),
            root.join("Cargo.toml"),
            default_package_name(&root),
            false,
        );
        assert_eq!(
            partial.packages.get(&root).unwrap().package_name,
            "my_crate"
        );

        // Second add with real name should update
        partial.add_package(
            root.clone(),
            root.join("Cargo.toml"),
            "real_name".to_string(),
            false,
        );
        assert_eq!(
            partial.packages.get(&root).unwrap().package_name,
            "real_name"
        );
    }

    #[test]
    fn partial_graph_add_package_or_promotes_workspace_member() {
        let mut partial = PartialGraph::default();
        let root = PathBuf::from("/project");

        partial.add_package(
            root.clone(),
            root.join("Cargo.toml"),
            "pkg".to_string(),
            false,
        );
        assert!(!partial.packages.get(&root).unwrap().workspace_member);

        // Adding again with workspace_member=true should promote
        partial.add_package(
            root.clone(),
            root.join("Cargo.toml"),
            "pkg".to_string(),
            true,
        );
        assert!(partial.packages.get(&root).unwrap().workspace_member);
    }

    /// Regression: `invoke_cargo_metadata` previously deadlocked when the JSON
    /// output exceeded the OS pipe capacity (~64 KB on Linux). The poll loop
    /// never read stdout, so the child blocked on `write()` and we always hit
    /// the 30s timeout. We now drain stdout/stderr concurrently in background
    /// threads. This test forces a large output by pulling in dozens of
    /// crates.io dependencies and asserting the call returns successfully
    /// well under the timeout.
    #[cfg(unix)]
    #[test]
    fn invoke_cargo_metadata_handles_output_larger_than_pipe_buffer() {
        let fixture = TopologyFixture::new("metadata-large");
        let project_root = fixture.canonical_root.join("metadata_pipe");
        fs::create_dir_all(project_root.join("src")).expect("create src");

        // 60+ small dependencies inflate the cargo metadata JSON well past
        // the 64KB pipe buffer once each is resolved with version, source,
        // checksum, and feature lists.
        let mut deps = String::new();
        for name in [
            "serde",
            "serde_json",
            "anyhow",
            "thiserror",
            "tokio",
            "futures",
            "log",
            "tracing",
            "regex",
            "chrono",
            "uuid",
            "rand",
            "base64",
            "hex",
            "url",
            "bytes",
            "clap",
            "rusqlite",
            "blake3",
            "sha2",
            "reqwest",
            "tempfile",
            "directories",
            "dirs",
            "shellexpand",
            "shell-escape",
            "which",
            "openssh",
            "schemars",
            "indexmap",
            "lazy_static",
            "once_cell",
            "parking_lot",
            "toml",
            "shell-words",
            "globset",
            "walkdir",
            "ignore",
            "crossbeam-channel",
            "rayon",
            "memchr",
            "smallvec",
            "ahash",
            "fnv",
            "itertools",
            "num_cpus",
            "humantime",
            "humansize",
            "ratatui",
            "crossterm",
        ] {
            deps.push_str(&format!("{name} = \"*\"\n"));
        }

        fs::write(
            project_root.join("Cargo.toml"),
            format!(
                "[package]\nname = \"metadata_pipe\"\nversion = \"0.1.0\"\nedition = \"2021\"\n\n[workspace]\nresolver = \"2\"\n\n[dependencies]\n{deps}",
            ),
        )
        .expect("write manifest");
        fs::write(project_root.join("src/lib.rs"), "").expect("write lib.rs");

        let manifest_path = project_root.join("Cargo.toml");
        let start = std::time::Instant::now();
        match invoke_cargo_metadata(&manifest_path) {
            Ok(json) => {
                let elapsed = start.elapsed();
                // Without the fix the function would either time out at 30s
                // or (depending on dependency cache) produce a truncated
                // result; both paths fail this assertion.
                assert!(
                    elapsed < CARGO_METADATA_TIMEOUT,
                    "metadata took {elapsed:?}, near the {CARGO_METADATA_TIMEOUT:?} timeout"
                );
                assert!(
                    json.len() > 64 * 1024,
                    "test fixture too small to exercise the pipe-buffer path: {} bytes",
                    json.len()
                );
                assert!(
                    json.starts_with('{'),
                    "metadata stdout should be JSON; got: {:.120}",
                    json
                );
            }
            Err(e) => {
                // Skip on machines without network access to crates.io or
                // without registry caches — we only care about the
                // *deadlock* regression, not about resolver outcomes.
                let detail = e.detail().to_lowercase();
                let offline = detail.contains("network")
                    || detail.contains("dns")
                    || detail.contains("registry")
                    || detail.contains("connection")
                    || detail.contains("not found")
                    || detail.contains("offline")
                    || detail.contains("could not")
                    || detail.contains("failed to fetch")
                    || detail.contains("no such file");
                assert!(
                    offline,
                    "invoke_cargo_metadata failed for non-network reason: {e}"
                );
            }
        }
    }
}