uv_resolver/lock/

installable.rs

use std::collections::BTreeSet;
use std::collections::VecDeque;
use std::collections::hash_map::Entry;
use std::path::Path;
use std::sync::Arc;

use either::Either;
use itertools::Itertools;
use petgraph::Graph;
use rustc_hash::{FxHashMap, FxHashSet};

use uv_configuration::{
    BuildOptions, DependencyGroupsWithDefaults, ExtrasSpecification,
    ExtrasSpecificationWithDefaults, InstallOptions,
};
use uv_distribution_types::{Edge, FirstParty, Node, Resolution, ResolvedDist};
use uv_normalize::{DefaultExtras, ExtraName, GroupName, PackageName};
use uv_platform_tags::Tags;
use uv_pypi_types::{ConflictKind, ConflictSet, ResolverMarkerEnvironment};

use crate::lock::{
    Dependency, DependencySelectionContext, HashedDist, LockErrorKind, Package, PackageIndex,
    SelectedDependency, TagPolicy,
};
use crate::universal_marker::ActivatedConflictItems;
use crate::{Lock, LockError, UniversalMarker};

fn newly_activated_extras<'lock>(
    dep: &'lock Dependency,
    activated_extras: &[(&'lock PackageName, &'lock ExtraName)],
) -> Vec<(&'lock PackageName, &'lock ExtraName)> {
    dep.extra
        .iter()
        .filter_map(|extra| {
            let key = (&dep.package_id.name, extra);
            (!activated_extras.contains(&key)).then_some(key)
        })
        .collect()
}

/// Record another condition under which a locked package and optional extra are reachable.
///
/// Returns `true` when the combined reachability changed.
fn add_reachability<'lock>(
    reachability: &mut FxHashMap<(PackageIndex, Option<&'lock ExtraName>), UniversalMarker>,
    key: (PackageIndex, Option<&'lock ExtraName>),
    marker: UniversalMarker,
) -> bool {
    match reachability.entry(key) {
        Entry::Occupied(mut entry) => {
            let mut combined = *entry.get();
            combined.or(marker);
            if combined == *entry.get() {
                false
            } else {
                entry.insert(combined);
                true
            }
        }
        Entry::Vacant(entry) => {
            entry.insert(marker);
            true
        }
    }
}

/// Returns the dependencies a queued package contributes, either its own or those of one extra.
fn package_dependencies<'a>(
    package: &'a Package,
    extra: Option<&ExtraName>,
) -> impl Iterator<Item = &'a Dependency> {
    if let Some(extra) = extra {
        Either::Left(
            package
                .optional_dependencies
                .get(extra)
                .into_iter()
                .flatten(),
        )
    } else {
        Either::Right(package.dependencies.iter())
    }
}

/// Determines which dependencies are included from an install target root.
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum InstallableRootKind {
    /// Include the root's production dependencies and selected dependency groups.
    Production,
    /// Include only the root's selected dependency groups.
    DependencyGroups,
}

pub trait Installable<'lock> {
    /// Return the root install path.
    fn install_path(&self) -> &'lock Path;

    /// Return the [`Lock`] to install.
    fn lock(&self) -> &'lock Lock;

    /// Return the [`PackageName`] of the root packages in the target.
    fn roots(&self) -> impl Iterator<Item = &PackageName>;

    /// Return the package whose dependency groups, but not production dependencies, are included.
    fn group_root(&self, _groups: &DependencyGroupsWithDefaults) -> Option<&PackageName> {
        None
    }

    /// Return whether a dependency group should be included for its owning package.
    ///
    /// A `None` package represents groups defined directly on a non-project workspace root.
    fn includes_group(
        &self,
        _package: Option<&PackageName>,
        group: &GroupName,
        groups: &DependencyGroupsWithDefaults,
    ) -> bool {
        groups.contains(group)
    }

    /// Return the [`PackageName`] of the target, if available.
    fn project_name(&self) -> Option<&PackageName>;

    /// Convert the [`Lock`] to a [`Resolution`] using the given marker environment, tags, and root.
    fn to_resolution(
        &self,
        marker_env: &ResolverMarkerEnvironment,
        tags: &Tags,
        extras: &ExtrasSpecificationWithDefaults,
        groups: &DependencyGroupsWithDefaults,
        build_options: &BuildOptions,
        install_options: &InstallOptions,
    ) -> Result<Resolution, LockError> {
        let resolve_root = |root_name: &PackageName| {
            self.lock()
                .find_by_name(root_name)
                .map_err(|_| LockErrorKind::MultipleRootPackages {
                    name: root_name.clone(),
                })?
                .ok_or_else(|| {
                    LockError::from(LockErrorKind::MissingRootPackage {
                        name: root_name.clone(),
                    })
                })
        };
        let roots = self
            .roots()
            .map(&resolve_root)
            .collect::<Result<Vec<_>, LockError>>()?;
        let group_root = self.group_root(groups).map(resolve_root).transpose()?;

        InstallableExt::to_resolution_from_packages(
            self,
            &roots,
            group_root,
            true,
            DependencySelectionContext::None,
            marker_env,
            tags,
            extras,
            groups,
            build_options,
            install_options,
        )
    }

    /// Create an installable [`Node`] from a [`Package`].
    fn installable_node(
        &self,
        package: &Package,
        tags: &Tags,
        marker_env: &ResolverMarkerEnvironment,
        build_options: &BuildOptions,
    ) -> Result<Node, LockError> {
        let tag_policy = TagPolicy::Required(tags);
        let HashedDist { dist, hashes } = package.to_dist(
            self.install_path(),
            tag_policy,
            build_options,
            marker_env,
            if self.lock().is_workspace_member(package) {
                FirstParty::Yes
            } else {
                FirstParty::No
            },
        )?;
        let version = package.version().cloned();
        let dist = ResolvedDist::Installable {
            dist: Arc::new(dist),
            version,
        };
        Ok(Node::Dist {
            dist,
            hashes,
            install: true,
        })
    }

    /// Create a non-installable [`Node`] from a [`Package`].
    fn non_installable_node(
        &self,
        package: &Package,
        tags: &Tags,
        marker_env: &ResolverMarkerEnvironment,
    ) -> Result<Node, LockError> {
        let HashedDist { dist, .. } = package.to_dist(
            self.install_path(),
            TagPolicy::Preferred(tags),
            &BuildOptions::default(),
            marker_env,
            FirstParty::No,
        )?;
        let version = package.version().cloned();
        let dist = ResolvedDist::Installable {
            dist: Arc::new(dist),
            version,
        };
        let hashes = package.hashes();
        Ok(Node::Dist {
            dist,
            hashes,
            install: false,
        })
    }

    /// Convert a lockfile entry to a graph [`Node`].
    fn package_to_node(
        &self,
        package: &Package,
        tags: &Tags,
        build_options: &BuildOptions,
        install_options: &InstallOptions,
        marker_env: &ResolverMarkerEnvironment,
    ) -> Result<Node, LockError> {
        if install_options.include_package(
            package.as_install_target(),
            self.project_name(),
            self.lock().members(),
        ) {
            self.installable_node(package, tags, marker_env, build_options)
        } else {
            self.non_installable_node(package, tags, marker_env)
        }
    }
}

/// Internal lock-to-resolution implementation shared by [`Installable`] and [`Lock`].
trait InstallableExt<'lock>: Installable<'lock> {
    /// Convert concrete locked packages to a [`Resolution`].
    ///
    /// `include_manifest` controls whether requirements attached directly to the lock target are
    /// included in addition to `roots`.
    fn to_resolution_from_packages(
        &self,
        roots: &[&Package],
        group_root: Option<&Package>,
        include_manifest: bool,
        selection_context: DependencySelectionContext<'lock>,
        marker_env: &ResolverMarkerEnvironment,
        tags: &Tags,
        extras: &ExtrasSpecificationWithDefaults,
        groups: &DependencyGroupsWithDefaults,
        build_options: &BuildOptions,
        install_options: &InstallOptions,
    ) -> Result<Resolution, LockError> {
        let size_guess = self.lock().packages.len();
        let mut petgraph = Graph::with_capacity(size_guess, size_guess);
        let mut inverse = vec![None; size_guess];

        let mut queue: VecDeque<(PackageIndex, Option<&ExtraName>)> = VecDeque::new();
        let mut seen = FxHashSet::default();
        let mut conflict_reachability = FxHashMap::default();
        let mut activated_projects: Vec<&PackageName> = vec![];
        let mut activated_extras: Vec<(&PackageName, &ExtraName)> = vec![];
        let mut activated_groups: Vec<(&PackageName, &GroupName)> = vec![];
        let has_conflicts = !self.lock().conflicts().is_empty();
        let validate_conflicts = !include_manifest && has_conflicts;
        let mut dependencies_for_conflict_validation = vec![];

        let root = petgraph.add_node(Node::Root);

        match selection_context {
            DependencySelectionContext::None => {}
            DependencySelectionContext::Production(project) => {
                activated_projects.push(project);
            }
            DependencySelectionContext::Group(project, group) => {
                activated_groups.push((project, group));
            }
        }

        // Determine the set of activated extras and groups, from the root.
        //
        // Extras activated by dependency groups (via `pkg[extra]` entries in the group) are
        // accumulated below, when we process the groups themselves. This ensures that when we
        // later evaluate conflict markers on transitive dependencies, self-extras enabled by an
        // active group are treated as enabled.
        //
        // TODO(zanieb): For completeness, the group-dep loop below still has two structural
        // soundness gaps. Neither is reachable through lockfiles the resolver currently
        // produces — they'd require a group-dep entry with a strict positive conflict marker
        // referencing an extra *other* than the entry's own self-extra, and the resolver
        // either emits self-extra markers (handled by `newly_activated_extras` below) or
        // markers with vacuously-true disjuncts. But the code should still handle them:
        //
        // 1. Ordering: an earlier group-dep entry whose marker references an extra activated
        //    by a later entry is evaluated with an incomplete `activated_extras` set.
        // 2. Transitive self-extras: a group dep `pkg[a]` where `pkg.optional_dependencies.a`
        //    includes `pkg[b]` only activates `(pkg, b)` during the first-pass traversal
        //    below, so any group dep whose marker needs `(pkg, b)` is evaluated too early.
        //
        // Fixing these correctly likely means iterating group-dep activation to a fixed point
        // or interleaving it with the first-pass traversal.
        if has_conflicts {
            for dist in roots.iter().copied() {
                // Track the activated extras.
                if groups.prod() {
                    activated_projects.push(&dist.id.name);
                    for extra in extras.extra_names(dist.optional_dependencies.keys()) {
                        activated_extras.push((&dist.id.name, extra));
                    }
                }
            }

            for dist in roots.iter().copied().chain(group_root) {
                for group in dist
                    .dependency_groups
                    .keys()
                    .filter(|group| self.includes_group(Some(&dist.id.name), group, groups))
                {
                    activated_groups.push((&dist.id.name, group));
                }
            }
        }

        // Initialize the workspace roots.
        let mut initialized_roots = vec![];
        for (dist, root_kind) in roots
            .iter()
            .copied()
            .map(|dist| (dist, InstallableRootKind::Production))
            .chain(group_root.map(|dist| (dist, InstallableRootKind::DependencyGroups)))
        {
            // Add the workspace package to the graph.
            let package_index = self.lock().by_id[&dist.id];
            let index = petgraph.add_node(
                if root_kind == InstallableRootKind::Production && groups.prod() {
                    self.package_to_node(dist, tags, build_options, install_options, marker_env)?
                } else {
                    self.non_installable_node(dist, tags, marker_env)?
                },
            );
            inverse[package_index.0] = Some(index);

            // Add an edge from the root.
            petgraph.add_edge(root, index, Edge::Prod);

            // Push the package onto the queue.
            initialized_roots.push((dist, package_index, index, root_kind));
        }

        // Add the workspace dependencies to the queue.
        for (dist, package_index, index, root_kind) in initialized_roots {
            if root_kind == InstallableRootKind::Production && groups.prod() {
                // Push its dependencies onto the queue.
                queue.push_back((package_index, None));
                add_reachability(
                    &mut conflict_reachability,
                    (package_index, None),
                    UniversalMarker::TRUE,
                );
                for extra in extras.extra_names(dist.optional_dependencies.keys()) {
                    queue.push_back((package_index, Some(extra)));
                    add_reachability(
                        &mut conflict_reachability,
                        (package_index, Some(extra)),
                        UniversalMarker::TRUE,
                    );
                }
            }

            // Add any dev dependencies.
            for (group, dep) in dist
                .dependency_groups
                .iter()
                .filter_map(|(group, deps)| {
                    if self.includes_group(Some(&dist.id.name), group, groups) {
                        Some(deps.iter().map(move |dep| (group, dep)))
                    } else {
                        None
                    }
                })
                .flatten()
            {
                if validate_conflicts && dep.complexified_marker.has_conflict_marker() {
                    dependencies_for_conflict_validation.push((dist, dep));
                }
                let additional_activated_extras = newly_activated_extras(dep, &activated_extras);
                if !dep.complexified_marker.evaluate(
                    marker_env,
                    activated_projects.iter().copied(),
                    activated_extras
                        .iter()
                        .chain(additional_activated_extras.iter())
                        .copied(),
                    activated_groups.iter().copied(),
                ) {
                    continue;
                }

                let dep_dist = self.lock().package(dep.index);

                // Add the package to the graph.
                let dep_index = match inverse[dep.index.0] {
                    None => {
                        let index = petgraph.add_node(self.package_to_node(
                            dep_dist,
                            tags,
                            build_options,
                            install_options,
                            marker_env,
                        )?);
                        inverse[dep.index.0] = Some(index);
                        index
                    }
                    Some(index) => {
                        // Critically, if the package is already in the graph, then it's a workspace
                        // member. If it was omitted due to, e.g., `--only-dev`, but is itself
                        // referenced as a development dependency, then we need to re-enable it.
                        let node = &mut petgraph[index];
                        if !groups.prod() || matches!(node, Node::Dist { install: false, .. }) {
                            *node = self.package_to_node(
                                dep_dist,
                                tags,
                                build_options,
                                install_options,
                                marker_env,
                            )?;
                        }
                        index
                    }
                };

                petgraph.add_edge(
                    index,
                    dep_index,
                    // This is OK because we are resolving to a resolution for
                    // a specific marker environment and set of extras/groups.
                    // So at this point, we know the extras/groups have been
                    // satisfied, so we can safely drop the conflict marker.
                    Edge::Dev(group.clone()),
                );

                // Persist any self-extras activated by this group dependency (e.g., a group
                // that references `pkg[extra]`). Without this, conflict markers on transitive
                // dependencies gated by the activated extra would not evaluate to `true`
                // during the graph traversals below.
                for key in additional_activated_extras {
                    activated_extras.push(key);
                }

                // Push its dependencies on the queue.
                add_reachability(
                    &mut conflict_reachability,
                    (dep.index, None),
                    dep.complexified_marker,
                );
                if seen.insert((dep.index, None)) {
                    queue.push_back((dep.index, None));
                }
                for extra in &dep.extra {
                    add_reachability(
                        &mut conflict_reachability,
                        (dep.index, Some(extra)),
                        dep.complexified_marker,
                    );
                    if seen.insert((dep.index, Some(extra))) {
                        queue.push_back((dep.index, Some(extra)));
                    }
                }
            }
        }

        if include_manifest {
            // Add any requirements that are exclusive to the workspace root (e.g., dependencies in
            // PEP 723 scripts).
            for dependency in self.lock().requirements() {
                if !dependency.marker.evaluate(marker_env, &[]) {
                    continue;
                }

                let root_name = &dependency.name;
                let dist = self
                    .lock()
                    .find_by_markers(root_name, marker_env)
                    .map_err(|_| LockErrorKind::MultipleRootPackages {
                        name: root_name.clone(),
                    })?
                    .ok_or_else(|| LockErrorKind::MissingRootPackage {
                        name: root_name.clone(),
                    })?;

                // Add the package to the graph.
                let package_index = self.lock().by_id[&dist.id];
                let index = petgraph.add_node(if groups.prod() {
                    self.package_to_node(dist, tags, build_options, install_options, marker_env)?
                } else {
                    self.non_installable_node(dist, tags, marker_env)?
                });
                inverse[package_index.0] = Some(index);

                // Add the edge.
                petgraph.add_edge(root, index, Edge::Prod);

                // Push its dependencies on the queue.
                add_reachability(
                    &mut conflict_reachability,
                    (package_index, None),
                    UniversalMarker::TRUE,
                );
                if seen.insert((package_index, None)) {
                    queue.push_back((package_index, None));
                }
                for extra in &dependency.extras {
                    add_reachability(
                        &mut conflict_reachability,
                        (package_index, Some(extra)),
                        UniversalMarker::TRUE,
                    );
                    if seen.insert((package_index, Some(extra))) {
                        queue.push_back((package_index, Some(extra)));
                    }
                }
            }

            // Add any dependency groups that are exclusive to the workspace root (e.g., dev
            // dependencies in non-project workspace roots).
            for (group, dependency) in self
                .lock()
                .dependency_groups()
                .iter()
                .filter_map(|(group, deps)| {
                    if self.includes_group(None, group, groups) {
                        Some(deps.iter().map(move |dep| (group, dep)))
                    } else {
                        None
                    }
                })
                .flatten()
            {
                if !dependency.marker.evaluate(marker_env, &[]) {
                    continue;
                }

                let root_name = &dependency.name;
                let dist = self
                    .lock()
                    .find_by_markers(root_name, marker_env)
                    .map_err(|_| LockErrorKind::MultipleRootPackages {
                        name: root_name.clone(),
                    })?
                    .ok_or_else(|| LockErrorKind::MissingRootPackage {
                        name: root_name.clone(),
                    })?;

                // Add the package to the graph.
                let package_index = self.lock().by_id[&dist.id];
                let index = match inverse[package_index.0] {
                    None => {
                        let index = petgraph.add_node(self.package_to_node(
                            dist,
                            tags,
                            build_options,
                            install_options,
                            marker_env,
                        )?);
                        inverse[package_index.0] = Some(index);
                        index
                    }
                    Some(index) => {
                        // Critically, if the package is already in the graph, then it's a workspace
                        // member. If it was omitted due to, e.g., `--only-dev`, but is itself
                        // referenced as a development dependency, then we need to re-enable it.
                        let node = &mut petgraph[index];
                        if !groups.prod() {
                            *node = self.package_to_node(
                                dist,
                                tags,
                                build_options,
                                install_options,
                                marker_env,
                            )?;
                        }
                        index
                    }
                };

                // Add the edge.
                petgraph.add_edge(root, index, Edge::Dev(group.clone()));

                // Persist any self-extras activated by this group dependency. Mirrors the
                // handling in the package-level `dependency_groups` loop above; without this,
                // conflict markers on transitive dependencies gated by the activated extra
                // would not evaluate to `true` during the graph traversals below.
                for extra in &dependency.extras {
                    let key = (&dist.id.name, extra);
                    if !activated_extras.contains(&key) {
                        activated_extras.push(key);
                    }
                }

                // Push its dependencies on the queue.
                add_reachability(
                    &mut conflict_reachability,
                    (package_index, None),
                    UniversalMarker::TRUE,
                );
                if seen.insert((package_index, None)) {
                    queue.push_back((package_index, None));
                }
                for extra in &dependency.extras {
                    add_reachability(
                        &mut conflict_reachability,
                        (package_index, Some(extra)),
                        UniversalMarker::TRUE,
                    );
                    if seen.insert((package_index, Some(extra))) {
                        queue.push_back((package_index, Some(extra)));
                    }
                }
            }
        }

        // Below, we traverse the dependency graph in a breadth first manner
        // twice. It's only in the second traversal that we actually build
        // up our resolution graph. In the first traversal, we accumulate all
        // activated extras. This includes the extras explicitly enabled on
        // the CLI (which were gathered above) and the extras enabled via
        // dependency specifications like `foo[extra]`. We need to do this
        // to correctly support conflicting extras.
        //
        // In particular, the way conflicting extras works is by forking the
        // resolver based on the extras that are declared as conflicting. But
        // this forking needs to be made manifest somehow in the lock file to
        // avoid multiple versions of the same package being installed into the
        // environment. This is why "conflict markers" were invented. For
        // example, you might have both `torch` and `torch+cpu` in your
        // dependency graph, where the latter is only enabled when the `cpu`
        // extra is enabled, and the former is specifically *not* enabled
        // when the `cpu` extra is enabled.
        //
        // In order to evaluate these conflict markers correctly, we need to
        // know whether the `cpu` extra is enabled when we visit the `torch`
        // dependency. If we think it's disabled, then we'll erroneously
        // include it if the extra is actually enabled. But in order to tell
        // if it's enabled, we need to traverse the entire dependency graph
        // first to inspect which extras are enabled!
        //
        // Of course, we don't need to do this at all if there aren't any
        // conflicts. In which case, we skip all of this and just do the one
        // traversal below.
        if has_conflicts {
            let mut activated_extras_set: BTreeSet<(&PackageName, &ExtraName)> =
                activated_extras.iter().copied().collect();
            let mut queue = queue.clone();
            let mut reachability = conflict_reachability;
            while let Some((package_index, extra)) = queue.pop_front() {
                let package = self.lock().package(package_index);
                let Some(parent_reachability) = reachability.get(&(package_index, extra)).copied()
                else {
                    continue;
                };
                for dep in package_dependencies(package, extra) {
                    let mut dep_reachability = dep.complexified_marker;
                    dep_reachability.and(parent_reachability);
                    let additional_activated_extras =
                        newly_activated_extras(dep, &activated_extras);
                    if !dep_reachability.evaluate(
                        marker_env,
                        activated_projects.iter().copied(),
                        activated_extras
                            .iter()
                            .chain(additional_activated_extras.iter())
                            .copied(),
                        activated_groups.iter().copied(),
                    ) {
                        continue;
                    }
                    // The dependency can still be visited provisionally before all activated
                    // extras are known. The second traversal below will exclude it once those
                    // extras are available. Crucially, `dep_reachability` includes the conditions
                    // required to reach the parent package: dependency markers may have been
                    // simplified under those conditions and cannot stand alone during this
                    // preliminary traversal. Otherwise, an unreachable package could activate an
                    // extra and cause the conflict check below to report a false positive.

                    for key in additional_activated_extras {
                        activated_extras_set.insert(key);
                        activated_extras.push(key);
                    }
                    // Push its dependencies on the queue.
                    if add_reachability(&mut reachability, (dep.index, None), dep_reachability) {
                        queue.push_back((dep.index, None));
                    }
                    for extra in &dep.extra {
                        if add_reachability(
                            &mut reachability,
                            (dep.index, Some(extra)),
                            dep_reachability,
                        ) {
                            queue.push_back((dep.index, Some(extra)));
                        }
                    }
                }
            }
            // At time of writing, it's somewhat expected that the set of
            // conflicting extras is pretty small. With that said, the
            // time complexity of the following routine is pretty gross.
            // Namely, `set.contains` is linear in the size of the set,
            // iteration over all conflicts is also obviously linear in
            // the number of conflicting sets and then for each of those,
            // we visit every possible pair of activated extra from above,
            // which is quadratic in the total number of extras enabled. I
            // believe the simplest improvement here, if it's necessary, is
            // to adjust the `Conflicts` internals to own these sorts of
            // checks. ---AG
            for set in self.lock().conflicts().iter() {
                for ((pkg1, extra1), (pkg2, extra2)) in
                    activated_extras_set.iter().tuple_combinations()
                {
                    if set.contains(pkg1, *extra1) && set.contains(pkg2, *extra2) {
                        return Err(LockErrorKind::ConflictingExtra {
                            package1: (*pkg1).clone(),
                            extra1: (*extra1).clone(),
                            package2: (*pkg2).clone(),
                            extra2: (*extra2).clone(),
                        }
                        .into());
                    }
                }
            }
        }

        // Unlike the traversals above, this one never activates an extra, so the activated set is
        // fixed for its duration and can be encoded once instead of once per dependency.
        let activated = ActivatedConflictItems::new(
            activated_projects.iter().copied(),
            activated_extras.iter().copied(),
            activated_groups.iter().copied(),
        );

        while let Some((package_index, extra)) = queue.pop_front() {
            let package = self.lock().package(package_index);
            for dep in package_dependencies(package, extra) {
                if validate_conflicts && dep.complexified_marker.has_conflict_marker() {
                    dependencies_for_conflict_validation.push((package, dep));
                }
                if !dep
                    .complexified_marker
                    .evaluate_activated(marker_env, &activated)
                {
                    continue;
                }

                let dep_dist = self.lock().package(dep.index);

                // Add the dependency to the graph.
                let dep_index = match inverse[dep.index.0] {
                    None => {
                        let index = petgraph.add_node(self.package_to_node(
                            dep_dist,
                            tags,
                            build_options,
                            install_options,
                            marker_env,
                        )?);
                        inverse[dep.index.0] = Some(index);
                        index
                    }
                    Some(index) => {
                        if matches!(&petgraph[index], Node::Dist { install: false, .. }) {
                            petgraph[index] = self.package_to_node(
                                dep_dist,
                                tags,
                                build_options,
                                install_options,
                                marker_env,
                            )?;
                        }
                        index
                    }
                };

                // Add the edge.
                let index = inverse[package_index.0].expect("queued package has a graph node");
                petgraph.add_edge(
                    index,
                    dep_index,
                    if let Some(extra) = extra {
                        Edge::Optional(extra.clone())
                    } else {
                        Edge::Prod
                    },
                );

                // Push its dependencies on the queue.
                if seen.insert((dep.index, None)) {
                    queue.push_back((dep.index, None));
                }
                for extra in &dep.extra {
                    if seen.insert((dep.index, Some(extra))) {
                        queue.push_back((dep.index, Some(extra)));
                    }
                }
            }
        }

        // Evaluate conflict markers from concrete roots, not from workspace members that depend on
        // them. Reject markers that still depend on conflict items outside the resulting subgraph.
        if !dependencies_for_conflict_validation.is_empty() {
            let subgraph_packages = inverse
                .iter()
                .enumerate()
                .filter_map(|(package_index, index)| {
                    index.map(|_| &self.lock().packages[package_index].id.name)
                })
                .collect::<FxHashSet<_>>();
            let selection_context_package = selection_context.package();

            // The environment and conflict state are shared by every dependency, so repeated
            // markers have the same result.
            let mut validated_markers = FxHashSet::default();
            for (package, dependency) in dependencies_for_conflict_validation {
                if !validated_markers.insert(dependency.complexified_marker) {
                    continue;
                }
                let mut marker = dependency.complexified_marker;
                for item in self.lock().conflicts().iter().flat_map(ConflictSet::iter) {
                    if selection_context_package != Some(item.package())
                        && !subgraph_packages.contains(item.package())
                    {
                        continue;
                    }

                    let active = match item.kind() {
                        ConflictKind::Project => activated_projects.contains(&item.package()),
                        ConflictKind::Extra(extra) => {
                            activated_extras.contains(&(item.package(), extra))
                        }
                        ConflictKind::Group(group) => {
                            activated_groups.contains(&(item.package(), group))
                        }
                    };
                    if active {
                        marker.assume_conflict_item(item);
                    } else {
                        marker.assume_not_conflict_item(item);
                    }
                }

                let conflict = marker.conflict_for_environment(marker_env);
                // All in-subgraph conflict items were resolved above, so a non-constant marker
                // still depends on a package outside the subgraph.
                if !conflict.is_constant() {
                    return Err(LockErrorKind::DependencyConflictOutsideSubgraph {
                        package: package.id.clone(),
                        dependency: dependency.package_id.clone(),
                    }
                    .into());
                }
            }
        }

        Ok(Resolution::new(petgraph))
    }
}

impl<'lock, T> InstallableExt<'lock> for T where T: Installable<'lock> + ?Sized {}

/// An [`Installable`] adapter for materializing concrete packages directly from a [`Lock`].
struct LockedPackages<'lock> {
    lock: &'lock Lock,
    install_path: &'lock Path,
    project_name: Option<&'lock PackageName>,
}

impl<'lock> Installable<'lock> for LockedPackages<'lock> {
    fn install_path(&self) -> &'lock Path {
        self.install_path
    }

    fn lock(&self) -> &'lock Lock {
        self.lock
    }

    fn roots(&self) -> impl Iterator<Item = &PackageName> {
        std::iter::empty()
    }

    fn project_name(&self) -> Option<&PackageName> {
        self.project_name
    }
}

impl Lock {
    /// Materialize a direct dependency selection from this lock.
    ///
    /// Like [`Self::to_resolution`], this materializes the selected dependency's subgraph. It also
    /// preserves the extras activated by the direct edge and the project production or group
    /// context used to select a conflict fork.
    pub fn to_resolution_from_dependency<'lock>(
        &'lock self,
        install_path: &'lock Path,
        dependency: &SelectedDependency<'lock>,
        project_name: Option<&'lock PackageName>,
        marker_env: &ResolverMarkerEnvironment,
        tags: &Tags,
        build_options: &BuildOptions,
        install_options: &InstallOptions,
    ) -> Result<Resolution, LockError> {
        let selected_package = dependency.package();
        let Some(index) = self.by_id.get(&selected_package.id) else {
            return Err(LockErrorKind::RootPackageMissingFromLock {
                id: selected_package.id.clone(),
            }
            .into());
        };
        let Some(package) = self.packages.get(index.0) else {
            return Err(LockErrorKind::RootPackageMissingFromLock {
                id: selected_package.id.clone(),
            }
            .into());
        };
        let extras = ExtrasSpecification::from_extra(dependency.extras().cloned().collect())
            .with_defaults(DefaultExtras::default());
        let groups = DependencyGroupsWithDefaults::none();

        LockedPackages {
            lock: self,
            install_path,
            project_name,
        }
        .to_resolution_from_packages(
            &[package],
            None,
            false,
            dependency.context(),
            marker_env,
            tags,
            &extras,
            &groups,
            build_options,
            install_options,
        )
    }

    /// Materialize the exact dependency subgraph reachable from concrete locked `roots`.
    ///
    /// Each root must be a [`Package`] from this lock. Unlike [`Installable::to_resolution`], this
    /// method does not include requirements or dependency groups attached directly to the lock
    /// manifest. Extras and dependency groups on the concrete roots are still included according
    /// to `extras` and `groups`.
    ///
    /// Conflict-marker evaluation starts from `roots` and their requested `extras` and `groups`,
    /// not from workspace members that depend on those roots. The method returns an error if a
    /// dependency marker still depends on a conflict item outside the resulting subgraph. Use
    /// [`Installable::to_resolution`] when materializing an existing lock target.
    ///
    /// `project_name` identifies the project for project-specific [`InstallOptions`] filters, if
    /// applicable. Callers are responsible for selecting roots that apply to `marker_env`.
    pub fn to_resolution<'lock>(
        &'lock self,
        install_path: &'lock Path,
        roots: impl IntoIterator<Item = &'lock Package>,
        project_name: Option<&'lock PackageName>,
        marker_env: &ResolverMarkerEnvironment,
        tags: &Tags,
        extras: &ExtrasSpecificationWithDefaults,
        groups: &DependencyGroupsWithDefaults,
        build_options: &BuildOptions,
        install_options: &InstallOptions,
    ) -> Result<Resolution, LockError> {
        let mut seen = FxHashSet::default();
        let mut concrete_roots = Vec::new();
        for root in roots {
            let Some(index) = self.by_id.get(&root.id) else {
                return Err(LockErrorKind::RootPackageMissingFromLock {
                    id: root.id.clone(),
                }
                .into());
            };
            if seen.insert(&root.id) {
                let Some(root) = self.packages.get(index.0) else {
                    return Err(LockErrorKind::RootPackageMissingFromLock {
                        id: root.id.clone(),
                    }
                    .into());
                };
                concrete_roots.push(root);
            }
        }

        LockedPackages {
            lock: self,
            install_path,
            project_name,
        }
        .to_resolution_from_packages(
            &concrete_roots,
            None,
            false,
            DependencySelectionContext::None,
            marker_env,
            tags,
            extras,
            groups,
            build_options,
            install_options,
        )
    }
}

#[cfg(test)]
mod tests {
    use std::cell::Cell;
    use std::cmp::Ordering;
    use std::str::FromStr;
    use std::sync::LazyLock;

    use petgraph::visit::EdgeRef;
    use uv_configuration::{DependencyGroups, ExtrasSpecification};
    use uv_distribution_types::Name;
    use uv_normalize::{DefaultExtras, DefaultGroups};
    use uv_pep508::{MarkerEnvironment, MarkerEnvironmentBuilder};
    use uv_platform_tags::{Arch, Os, Platform, TagsOptions};
    use uv_warnings::anstream;

    use super::*;

    static TAGS: LazyLock<Tags> = LazyLock::new(|| {
        Tags::from_env(
            Platform::new(
                Os::Macos {
                    major: 14,
                    minor: 0,
                },
                Arch::Aarch64,
            ),
            (3, 11),
            "cpython",
            (3, 11),
            TagsOptions::default(),
        )
        .expect("valid tags")
    });

    static DARWIN_MARKERS: LazyLock<ResolverMarkerEnvironment> =
        LazyLock::new(|| ResolverMarkerEnvironment::from(marker_environment("darwin", "Darwin")));

    static LINUX_MARKERS: LazyLock<ResolverMarkerEnvironment> =
        LazyLock::new(|| ResolverMarkerEnvironment::from(marker_environment("linux", "Linux")));

    fn marker_environment(
        sys_platform: &'static str,
        platform_system: &'static str,
    ) -> MarkerEnvironment {
        MarkerEnvironment::try_from(MarkerEnvironmentBuilder {
            implementation_name: "cpython",
            implementation_version: "3.11.5",
            os_name: "posix",
            platform_machine: "arm64",
            platform_python_implementation: "CPython",
            platform_release: "23.0.0",
            platform_system,
            platform_version: "test",
            python_full_version: "3.11.5",
            python_version: "3.11",
            sys_platform,
        })
        .expect("valid marker environment")
    }

    fn lock() -> Lock {
        toml::from_str(
            r#"
version = 1
revision = 3
requires-python = ">=3.11"
resolution-markers = [
    "sys_platform == 'darwin'",
    "sys_platform != 'darwin'",
]

[manifest]
requirements = [{ name = "unrelated" }]

[[package]]
name = "dev-dependency"
version = "1.0.0"
source = { registry = "https://example.com/simple" }
sdist = { url = "https://example.com/dev_dependency-1.0.0.tar.gz", hash = "sha256:1111111111111111111111111111111111111111111111111111111111111111" }

[[package]]
name = "forked"
version = "1.0.0"
source = { registry = "https://example.com/simple" }
resolution-markers = ["sys_platform == 'darwin'"]
sdist = { url = "https://example.com/forked-1.0.0.tar.gz", hash = "sha256:2222222222222222222222222222222222222222222222222222222222222222" }

[[package]]
name = "forked"
version = "2.0.0"
source = { registry = "https://example.com/simple" }
resolution-markers = ["sys_platform != 'darwin'"]
sdist = { url = "https://example.com/forked-2.0.0.tar.gz", hash = "sha256:3333333333333333333333333333333333333333333333333333333333333333" }

[[package]]
name = "optional-dependency"
version = "1.0.0"
source = { registry = "https://example.com/simple" }
sdist = { url = "https://example.com/optional_dependency-1.0.0.tar.gz", hash = "sha256:4444444444444444444444444444444444444444444444444444444444444444" }

[[package]]
name = "root-a"
version = "1.0.0"
source = { registry = "https://example.com/simple" }
dependencies = [
    { name = "forked", version = "1.0.0", source = { registry = "https://example.com/simple" }, marker = "sys_platform == 'darwin'" },
    { name = "forked", version = "2.0.0", source = { registry = "https://example.com/simple" }, marker = "sys_platform != 'darwin'" },
    { name = "shared" },
]
sdist = { url = "https://example.com/root_a-1.0.0.tar.gz", hash = "sha256:5555555555555555555555555555555555555555555555555555555555555555" }

[package.optional-dependencies]
feature = [{ name = "optional-dependency" }]

[package.dependency-groups]
dev = [{ name = "dev-dependency" }]

[package.metadata]
provides-extras = ["feature"]

[[package]]
name = "root-b"
version = "1.0.0"
source = { registry = "https://example.com/simple" }
dependencies = [{ name = "shared" }]
sdist = { url = "https://example.com/root_b-1.0.0.tar.gz", hash = "sha256:6666666666666666666666666666666666666666666666666666666666666666" }

[[package]]
name = "shared"
version = "1.0.0"
source = { registry = "https://example.com/simple" }
sdist = { url = "https://example.com/shared-1.0.0.tar.gz", hash = "sha256:7777777777777777777777777777777777777777777777777777777777777777" }

[[package]]
name = "unrelated"
version = "1.0.0"
source = { registry = "https://example.com/simple" }
sdist = { url = "https://example.com/unrelated-1.0.0.tar.gz", hash = "sha256:8888888888888888888888888888888888888888888888888888888888888888" }
"#,
        )
        .expect("valid lock")
    }

    fn conflict_lock() -> Lock {
        toml::from_str(
            r#"
version = 1
revision = 3
requires-python = ">=3.11"
conflicts = [
    [
        { package = "tool", extra = "cpu" },
        { package = "tool", extra = "gpu" },
    ],
    [
        { package = "project", extra = "foo" },
        { package = "project", extra = "bar" },
    ],
]

[[package]]
name = "contextual-dependency"
version = "1.0.0"
source = { registry = "https://example.com/simple" }
sdist = { url = "https://example.com/contextual_dependency-1.0.0.tar.gz", hash = "sha256:1111111111111111111111111111111111111111111111111111111111111111" }

[[package]]
name = "contextual-tool"
version = "1.0.0"
source = { registry = "https://example.com/simple" }
dependencies = [
    { name = "contextual-dependency", marker = "sys_platform == 'linux' or (sys_platform == 'darwin' and extra == 'extra-7-project-foo')" },
]
sdist = { url = "https://example.com/contextual_tool-1.0.0.tar.gz", hash = "sha256:2222222222222222222222222222222222222222222222222222222222222222" }

[[package]]
name = "cpu-backend"
version = "1.0.0"
source = { registry = "https://example.com/simple" }
sdist = { url = "https://example.com/cpu_backend-1.0.0.tar.gz", hash = "sha256:3333333333333333333333333333333333333333333333333333333333333333" }

[[package]]
name = "gpu-backend"
version = "1.0.0"
source = { registry = "https://example.com/simple" }
sdist = { url = "https://example.com/gpu_backend-1.0.0.tar.gz", hash = "sha256:4444444444444444444444444444444444444444444444444444444444444444" }

[[package]]
name = "project"
version = "1.0.0"
source = { registry = "https://example.com/simple" }
sdist = { url = "https://example.com/project-1.0.0.tar.gz", hash = "sha256:5555555555555555555555555555555555555555555555555555555555555555" }

[package.optional-dependencies]
foo = []
bar = []

[package.metadata]
provides-extras = ["foo", "bar"]

[[package]]
name = "runtime"
version = "1.0.0"
source = { registry = "https://example.com/simple" }
dependencies = [
    { name = "cpu-backend", marker = "extra == 'extra-4-tool-cpu'" },
    { name = "gpu-backend", marker = "extra == 'extra-4-tool-gpu'" },
]
sdist = { url = "https://example.com/runtime-1.0.0.tar.gz", hash = "sha256:6666666666666666666666666666666666666666666666666666666666666666" }

[[package]]
name = "tool"
version = "1.0.0"
source = { registry = "https://example.com/simple" }
dependencies = [{ name = "runtime" }]
sdist = { url = "https://example.com/tool-1.0.0.tar.gz", hash = "sha256:7777777777777777777777777777777777777777777777777777777777777777" }

[package.optional-dependencies]
cpu = []
gpu = []

[package.metadata]
provides-extras = ["cpu", "gpu"]
"#,
        )
        .expect("valid lock")
    }

    fn dependency_selection_lock() -> Lock {
        toml::from_str(
            r#"
version = 1
revision = 3
requires-python = ">=3.11"
conflicts = [[
    { package = "project", group = "dev" },
    { package = "project", group = "other" },
]]

[[package]]
name = "contextual-dev-dependency"
version = "1.0.0"
source = { registry = "https://example.com/simple" }
sdist = { url = "https://example.com/contextual_dev_dependency-1.0.0.tar.gz", hash = "sha256:1111111111111111111111111111111111111111111111111111111111111111" }

[[package]]
name = "contextual-other-dependency"
version = "1.0.0"
source = { registry = "https://example.com/simple" }
sdist = { url = "https://example.com/contextual_other_dependency-1.0.0.tar.gz", hash = "sha256:2222222222222222222222222222222222222222222222222222222222222222" }

[[package]]
name = "optional-dependency"
version = "1.0.0"
source = { registry = "https://example.com/simple" }
sdist = { url = "https://example.com/optional_dependency-1.0.0.tar.gz", hash = "sha256:3333333333333333333333333333333333333333333333333333333333333333" }

[[package]]
name = "project"
version = "1.0.0"
source = { virtual = "." }

[package.dependency-groups]
dev = [{ name = "tool", extra = ["cli"] }]
other = [{ name = "tool" }]

[[package]]
name = "tool"
version = "1.0.0"
source = { registry = "https://example.com/simple" }
dependencies = [
    { name = "contextual-dev-dependency", marker = "extra == 'group-7-project-dev'" },
    { name = "contextual-other-dependency", marker = "extra == 'group-7-project-other'" },
]
sdist = { url = "https://example.com/tool-1.0.0.tar.gz", hash = "sha256:4444444444444444444444444444444444444444444444444444444444444444" }

[package.optional-dependencies]
cli = [{ name = "optional-dependency" }]

[package.metadata]
provides-extras = ["cli"]
"#,
        )
        .expect("valid lock")
    }

    fn package<'lock>(lock: &'lock Lock, name: &str, version: &str) -> &'lock Package {
        lock.packages()
            .iter()
            .find(|package| {
                package.name().as_ref() == name
                    && package
                        .version()
                        .is_some_and(|package_version| package_version.to_string() == version)
            })
            .expect("locked package")
    }

    fn materialize(
        lock: &Lock,
        roots: &[&Package],
        marker_env: &ResolverMarkerEnvironment,
    ) -> Resolution {
        let extras = ExtrasSpecification::from_all_extras().with_defaults(DefaultExtras::default());
        let groups = DependencyGroups::from_all_groups().with_defaults(DefaultGroups::default());
        lock.to_resolution(
            Path::new("."),
            roots.iter().copied(),
            None,
            marker_env,
            &TAGS,
            &extras,
            &groups,
            &BuildOptions::default(),
            &InstallOptions::default(),
        )
        .expect("valid resolution")
    }

    fn materialize_with_extras(
        lock: &Lock,
        roots: &[&Package],
        marker_env: &ResolverMarkerEnvironment,
        extras: &ExtrasSpecification,
    ) -> Result<Resolution, LockError> {
        let extras = extras.with_defaults(DefaultExtras::default());
        let groups = DependencyGroupsWithDefaults::none();
        lock.to_resolution(
            Path::new("."),
            roots.iter().copied(),
            None,
            marker_env,
            &TAGS,
            &extras,
            &groups,
            &BuildOptions::default(),
            &InstallOptions::default(),
        )
    }

    fn materialize_selected_dependency(lock: &Lock, group: &str) -> Resolution {
        let project_name = PackageName::from_str("project").expect("valid package name");
        let dependency_name = PackageName::from_str("tool").expect("valid package name");
        let group = GroupName::from_str(group).expect("valid group name");
        let selection = lock
            .dependency_selection(
                Some(&project_name),
                &dependency_name,
                DARWIN_MARKERS.markers(),
            )
            .expect("unique dependency selection");
        let dependency = selection.group(&group).expect("group dependency");

        lock.to_resolution_from_dependency(
            Path::new("."),
            dependency,
            Some(&project_name),
            &DARWIN_MARKERS,
            &TAGS,
            &BuildOptions::default(),
            &InstallOptions::default(),
        )
        .expect("valid resolution")
    }

    #[test]
    fn unrelated_packages_do_not_change_dependency_identity() {
        let original = lock();
        let input = format!(
            "{}\n{}",
            original.to_toml().expect("valid lock TOML"),
            r#"
[[package]]
name = "aaa-unrelated"
version = "1.0.0"
source = { registry = "https://example.com/simple" }
"#
        );
        let extended = Lock::from_toml(&input).expect("valid extended lock");
        let original_root = package(&original, "root-a", "1.0.0");
        let extended_root = package(&extended, "root-a", "1.0.0");

        assert_eq!(original_root, extended_root);
        assert_eq!(
            original_root.dependencies.cmp(&extended_root.dependencies),
            Ordering::Equal,
        );
        assert_eq!(
            graph_snapshot(&materialize(&original, &[original_root], &DARWIN_MARKERS)),
            graph_snapshot(&materialize(&extended, &[extended_root], &DARWIN_MARKERS)),
        );
    }

    struct OverridingInstallable<'lock> {
        lock: &'lock Lock,
        root_name: &'lock PackageName,
        package_to_node_calls: Cell<usize>,
    }

    impl<'lock> Installable<'lock> for OverridingInstallable<'lock> {
        fn install_path(&self) -> &'lock Path {
            Path::new(".")
        }

        fn lock(&self) -> &'lock Lock {
            self.lock
        }

        fn roots(&self) -> impl Iterator<Item = &PackageName> {
            std::iter::once(self.root_name)
        }

        fn project_name(&self) -> Option<&PackageName> {
            None
        }

        fn package_to_node(
            &self,
            _package: &Package,
            _tags: &Tags,
            _build_options: &BuildOptions,
            _install_options: &InstallOptions,
            _marker_env: &ResolverMarkerEnvironment,
        ) -> Result<Node, LockError> {
            self.package_to_node_calls
                .set(self.package_to_node_calls.get() + 1);
            Ok(Node::Root)
        }
    }

    fn graph_snapshot(resolution: &Resolution) -> (Vec<String>, Vec<String>) {
        let graph = resolution.graph();
        let labels = graph
            .node_weights()
            .map(|node| match node {
                Node::Root => "root".to_string(),
                Node::Dist {
                    dist,
                    hashes,
                    install,
                } => format!(
                    "{}=={} (install: {install}, hashes: {})",
                    dist.name(),
                    dist.version()
                        .map(ToString::to_string)
                        .unwrap_or_else(|| "<dynamic>".to_string()),
                    hashes.iter().map(ToString::to_string).join(", ")
                ),
            })
            .collect::<Vec<_>>();
        let mut nodes = labels.clone();
        nodes.sort_unstable();
        let mut edges = graph
            .edge_references()
            .map(|edge| {
                format!(
                    "{} --{:?}--> {}",
                    labels[edge.source().index()],
                    edge.weight(),
                    labels[edge.target().index()]
                )
            })
            .collect::<Vec<_>>();
        edges.sort_unstable();
        (nodes, edges)
    }

    #[test]
    fn materializes_multiple_concrete_roots_with_shared_dependencies() {
        let lock = lock();
        let resolution = materialize(
            &lock,
            &[
                package(&lock, "root-a", "1.0.0"),
                package(&lock, "root-b", "1.0.0"),
            ],
            &DARWIN_MARKERS,
        );

        insta::with_settings!({
            filters => [(r"sha256:[0-9a-f]{64}", "sha256:[HASH]")],
        }, {
            insta::assert_debug_snapshot!(graph_snapshot(&resolution), @r#"
        (
            [
                "dev-dependency==1.0.0 (install: true, hashes: sha256:[HASH])",
                "forked==1.0.0 (install: true, hashes: sha256:[HASH])",
                "optional-dependency==1.0.0 (install: true, hashes: sha256:[HASH])",
                "root",
                "root-a==1.0.0 (install: true, hashes: sha256:[HASH])",
                "root-b==1.0.0 (install: true, hashes: sha256:[HASH])",
                "shared==1.0.0 (install: true, hashes: sha256:[HASH])",
            ],
            [
                "root --Prod--> root-a==1.0.0 (install: true, hashes: sha256:[HASH])",
                "root --Prod--> root-b==1.0.0 (install: true, hashes: sha256:[HASH])",
                "root-a==1.0.0 (install: true, hashes: sha256:[HASH]) --Dev(GroupName(\"dev\"))--> dev-dependency==1.0.0 (install: true, hashes: sha256:[HASH])",
                "root-a==1.0.0 (install: true, hashes: sha256:[HASH]) --Optional(ExtraName(\"feature\"))--> optional-dependency==1.0.0 (install: true, hashes: sha256:[HASH])",
                "root-a==1.0.0 (install: true, hashes: sha256:[HASH]) --Prod--> forked==1.0.0 (install: true, hashes: sha256:[HASH])",
                "root-a==1.0.0 (install: true, hashes: sha256:[HASH]) --Prod--> shared==1.0.0 (install: true, hashes: sha256:[HASH])",
                "root-b==1.0.0 (install: true, hashes: sha256:[HASH]) --Prod--> shared==1.0.0 (install: true, hashes: sha256:[HASH])",
            ],
        )
            "#);
        });
    }

    #[test]
    fn materializes_group_root_referenced_by_production_dependency() {
        let lock = lock();
        let project = package(&lock, "root-a", "1.0.0");
        let group_root = package(&lock, "shared", "1.0.0");
        let extras = ExtrasSpecification::default().with_defaults(DefaultExtras::default());
        let groups = DependencyGroupsWithDefaults::none();

        let resolution = LockedPackages {
            lock: &lock,
            install_path: Path::new("."),
            project_name: Some(project.name()),
        }
        .to_resolution_from_packages(
            &[project],
            Some(group_root),
            false,
            DependencySelectionContext::None,
            &DARWIN_MARKERS,
            &TAGS,
            &extras,
            &groups,
            &BuildOptions::default(),
            &InstallOptions::default(),
        )
        .expect("valid resolution");

        assert!(
            resolution
                .distributions()
                .any(|distribution| distribution.name() == group_root.name())
        );
    }

    #[test]
    fn materializes_the_selected_universal_lock_fork() {
        let lock = lock();
        let root = package(&lock, "root-a", "1.0.0");
        let darwin = materialize(&lock, &[root], &DARWIN_MARKERS);
        let linux = materialize(&lock, &[root], &LINUX_MARKERS);
        let concrete_fork =
            materialize(&lock, &[package(&lock, "forked", "1.0.0")], &DARWIN_MARKERS);

        insta::with_settings!({
            filters => [(r"sha256:[0-9a-f]{64}", "sha256:[HASH]")],
        }, {
            insta::assert_debug_snapshot!(graph_snapshot(&darwin), @r#"
        (
            [
                "dev-dependency==1.0.0 (install: true, hashes: sha256:[HASH])",
                "forked==1.0.0 (install: true, hashes: sha256:[HASH])",
                "optional-dependency==1.0.0 (install: true, hashes: sha256:[HASH])",
                "root",
                "root-a==1.0.0 (install: true, hashes: sha256:[HASH])",
                "shared==1.0.0 (install: true, hashes: sha256:[HASH])",
            ],
            [
                "root --Prod--> root-a==1.0.0 (install: true, hashes: sha256:[HASH])",
                "root-a==1.0.0 (install: true, hashes: sha256:[HASH]) --Dev(GroupName(\"dev\"))--> dev-dependency==1.0.0 (install: true, hashes: sha256:[HASH])",
                "root-a==1.0.0 (install: true, hashes: sha256:[HASH]) --Optional(ExtraName(\"feature\"))--> optional-dependency==1.0.0 (install: true, hashes: sha256:[HASH])",
                "root-a==1.0.0 (install: true, hashes: sha256:[HASH]) --Prod--> forked==1.0.0 (install: true, hashes: sha256:[HASH])",
                "root-a==1.0.0 (install: true, hashes: sha256:[HASH]) --Prod--> shared==1.0.0 (install: true, hashes: sha256:[HASH])",
            ],
        )
        "#);
            insta::assert_debug_snapshot!(graph_snapshot(&linux), @r#"
        (
            [
                "dev-dependency==1.0.0 (install: true, hashes: sha256:[HASH])",
                "forked==2.0.0 (install: true, hashes: sha256:[HASH])",
                "optional-dependency==1.0.0 (install: true, hashes: sha256:[HASH])",
                "root",
                "root-a==1.0.0 (install: true, hashes: sha256:[HASH])",
                "shared==1.0.0 (install: true, hashes: sha256:[HASH])",
            ],
            [
                "root --Prod--> root-a==1.0.0 (install: true, hashes: sha256:[HASH])",
                "root-a==1.0.0 (install: true, hashes: sha256:[HASH]) --Dev(GroupName(\"dev\"))--> dev-dependency==1.0.0 (install: true, hashes: sha256:[HASH])",
                "root-a==1.0.0 (install: true, hashes: sha256:[HASH]) --Optional(ExtraName(\"feature\"))--> optional-dependency==1.0.0 (install: true, hashes: sha256:[HASH])",
                "root-a==1.0.0 (install: true, hashes: sha256:[HASH]) --Prod--> forked==2.0.0 (install: true, hashes: sha256:[HASH])",
                "root-a==1.0.0 (install: true, hashes: sha256:[HASH]) --Prod--> shared==1.0.0 (install: true, hashes: sha256:[HASH])",
            ],
        )
        "#);
            insta::assert_debug_snapshot!(graph_snapshot(&concrete_fork), @r#"
        (
            [
                "forked==1.0.0 (install: true, hashes: sha256:[HASH])",
                "root",
            ],
            [
                "root --Prod--> forked==1.0.0 (install: true, hashes: sha256:[HASH])",
            ],
        )
            "#);
        });
    }

    #[test]
    fn materializes_conflicting_extras_within_the_synthetic_root() {
        let lock = conflict_lock();
        let extras =
            ExtrasSpecification::from_extra(vec!["cpu".parse().expect("valid extra name")]);
        let resolution = materialize_with_extras(
            &lock,
            &[package(&lock, "tool", "1.0.0")],
            &DARWIN_MARKERS,
            &extras,
        )
        .expect("conflict markers are resolved within the subgraph");

        insta::with_settings!({
            filters => [(r"sha256:[0-9a-f]{64}", "sha256:[HASH]")],
        }, {
            insta::assert_debug_snapshot!(graph_snapshot(&resolution), @r#"
        (
            [
                "cpu-backend==1.0.0 (install: true, hashes: sha256:[HASH])",
                "root",
                "runtime==1.0.0 (install: true, hashes: sha256:[HASH])",
                "tool==1.0.0 (install: true, hashes: sha256:[HASH])",
            ],
            [
                "root --Prod--> tool==1.0.0 (install: true, hashes: sha256:[HASH])",
                "runtime==1.0.0 (install: true, hashes: sha256:[HASH]) --Prod--> cpu-backend==1.0.0 (install: true, hashes: sha256:[HASH])",
                "tool==1.0.0 (install: true, hashes: sha256:[HASH]) --Prod--> runtime==1.0.0 (install: true, hashes: sha256:[HASH])",
            ],
        )
        "#);
        });
    }

    #[test]
    fn materializes_selected_dependency_extras() {
        let resolution = materialize_selected_dependency(&dependency_selection_lock(), "dev");

        insta::with_settings!({
            filters => [(r"sha256:[0-9a-f]{64}", "sha256:[HASH]")],
        }, {
            insta::assert_debug_snapshot!(graph_snapshot(&resolution), @r#"
        (
            [
                "contextual-dev-dependency==1.0.0 (install: true, hashes: sha256:[HASH])",
                "optional-dependency==1.0.0 (install: true, hashes: sha256:[HASH])",
                "root",
                "tool==1.0.0 (install: true, hashes: sha256:[HASH])",
            ],
            [
                "root --Prod--> tool==1.0.0 (install: true, hashes: sha256:[HASH])",
                "tool==1.0.0 (install: true, hashes: sha256:[HASH]) --Optional(ExtraName(\"cli\"))--> optional-dependency==1.0.0 (install: true, hashes: sha256:[HASH])",
                "tool==1.0.0 (install: true, hashes: sha256:[HASH]) --Prod--> contextual-dev-dependency==1.0.0 (install: true, hashes: sha256:[HASH])",
            ],
        )
        "#);
        });
    }

    #[test]
    fn materializes_selected_dependency_project_conflict_context() {
        let resolution = materialize_selected_dependency(&dependency_selection_lock(), "other");

        insta::with_settings!({
            filters => [(r"sha256:[0-9a-f]{64}", "sha256:[HASH]")],
        }, {
            insta::assert_debug_snapshot!(graph_snapshot(&resolution), @r#"
        (
            [
                "contextual-other-dependency==1.0.0 (install: true, hashes: sha256:[HASH])",
                "root",
                "tool==1.0.0 (install: true, hashes: sha256:[HASH])",
            ],
            [
                "root --Prod--> tool==1.0.0 (install: true, hashes: sha256:[HASH])",
                "tool==1.0.0 (install: true, hashes: sha256:[HASH]) --Prod--> contextual-other-dependency==1.0.0 (install: true, hashes: sha256:[HASH])",
            ],
        )
        "#);
        });
    }

    #[test]
    fn rejects_conflicts_outside_the_synthetic_root() {
        let lock = conflict_lock();
        let root = package(&lock, "contextual-tool", "1.0.0");
        let extras = ExtrasSpecification::default();

        let error = materialize_with_extras(&lock, &[root], &DARWIN_MARKERS, &extras)
            .expect_err("Darwin dependency depends on the project extra");
        let error = error.to_string();
        let error = anstream::adapter::strip_str(&error);
        insta::assert_snapshot!(error, @"Cannot materialize dependency `contextual-dependency==1.0.0 @ registry+https://example.com/simple` of `contextual-tool==1.0.0 @ registry+https://example.com/simple` because its conflict marker depends on a package outside the selected subgraph");

        let linux = materialize_with_extras(&lock, &[root], &LINUX_MARKERS, &extras)
            .expect("the dependency is unconditional on Linux");
        insta::with_settings!({
            filters => [(r"sha256:[0-9a-f]{64}", "sha256:[HASH]")],
        }, {
            insta::assert_debug_snapshot!(graph_snapshot(&linux), @r#"
        (
            [
                "contextual-dependency==1.0.0 (install: true, hashes: sha256:[HASH])",
                "contextual-tool==1.0.0 (install: true, hashes: sha256:[HASH])",
                "root",
            ],
            [
                "contextual-tool==1.0.0 (install: true, hashes: sha256:[HASH]) --Prod--> contextual-dependency==1.0.0 (install: true, hashes: sha256:[HASH])",
                "root --Prod--> contextual-tool==1.0.0 (install: true, hashes: sha256:[HASH])",
            ],
        )
        "#);
        });
    }

    #[test]
    fn installable_to_resolution_preserves_node_overrides() {
        let mut lock = lock();
        lock.manifest.requirements.clear();
        let target = OverridingInstallable {
            root_name: package(&lock, "root-a", "1.0.0").name(),
            lock: &lock,
            package_to_node_calls: Cell::new(0),
        };
        let extras = ExtrasSpecification::from_all_extras().with_defaults(DefaultExtras::default());
        let groups = DependencyGroups::from_all_groups().with_defaults(DefaultGroups::default());

        target
            .to_resolution(
                &DARWIN_MARKERS,
                &TAGS,
                &extras,
                &groups,
                &BuildOptions::default(),
                &InstallOptions::default(),
            )
            .expect("valid resolution");

        assert!(target.package_to_node_calls.get() > 0);
    }
}