wasmer_wasix/runtime/resolver/

resolve.rs

use std::{
    collections::{BTreeMap, BTreeSet, HashSet, VecDeque},
    path::PathBuf,
};

use petgraph::{
    graph::{DiGraph, NodeIndex},
    visit::EdgeRef,
};
use semver::Version;
use wasmer_config::package::{NamedPackageIdent, PackageId, PackageSource};

use crate::runtime::resolver::{
    Dependency, DependencyGraph, ItemLocation, PackageInfo, PackageSummary, QueryError, Resolution,
    ResolvedPackage, Source,
    outputs::{Edge, Node},
    utils::cmp_version_precedence,
};

use super::ResolvedFileSystemMapping;

const MAX_DISCOVERED_PACKAGES: usize = 1_000;
const MAX_PENDING_DEPENDENCIES: usize = 4_000;
const MAX_BACKTRACK_STATES: usize = 10_000;

/// Given the [`PackageInfo`] for a root package, resolve its dependency graph
/// and figure out how it could be executed.
#[tracing::instrument(level = "debug", skip_all)]
pub async fn resolve(
    root_id: &PackageId,
    root: &PackageInfo,
    source: &dyn Source,
) -> Result<Resolution, ResolveError> {
    let graph = resolve_dependency_graph(root_id, root, source).await?;
    validate_dependency_graph(&graph)?;
    let package = resolve_package(&graph)?;

    Ok(Resolution { graph, package })
}

#[derive(Debug, thiserror::Error)]
pub enum ResolveError {
    #[error("{}", registry_error_message(.package))]
    Registry {
        package: PackageSource,
        #[source]
        error: QueryError,
    },
    #[error("Dependency cycle detected: {}", print_cycle(_0))]
    Cycle(Vec<PackageId>),
    #[error(
        "Multiple versions of {package_name} were found {}",
        versions.iter().map(|v| v.to_string()).collect::<Vec<_>>().join(", "),
    )]
    DuplicateVersions {
        package_name: String,
        versions: Vec<Version>,
    },
    #[error("Dependency resolution exceeded safety limits ({resource}={value}, limit={limit})")]
    TooComplex {
        resource: &'static str,
        value: usize,
        limit: usize,
    },
}

fn registry_error_message(specifier: &PackageSource) -> String {
    match specifier {
        PackageSource::Ident(id) => {
            format!("Unable to find \"{id}\" in the registry")
        }
        PackageSource::Url(url) => format!("Unable to resolve \"{url}\""),
        PackageSource::Path(path) => {
            format!("Unable to load \"{path}\" from disk")
        }
    }
}

impl ResolveError {
    pub fn as_cycle(&self) -> Option<&[PackageId]> {
        match self {
            ResolveError::Cycle(cycle) => Some(cycle),
            _ => None,
        }
    }
}

fn print_cycle(packages: &[PackageId]) -> String {
    packages
        .iter()
        .map(|pkg_id| pkg_id.to_string())
        .collect::<Vec<_>>()
        .join(" → ")
}

/// Given the [`PackageInfo`] for a root package, discover its dependency graph.
///
/// Unlike [`resolve()`], this only queries and links packages. It does not apply
/// runtime compatibility checks such as rejecting duplicate package versions.
#[tracing::instrument(level = "debug", skip_all)]
pub async fn resolve_dependency_graph(
    root_id: &PackageId,
    root: &PackageInfo,
    source: &dyn Source,
) -> Result<DependencyGraph, ResolveError> {
    let DiscoveredPackages {
        root,
        graph,
        packages,
        ..
    } = discover_dependencies(root_id, root, source).await?;

    log_dependencies(&graph, root);

    let graph = DependencyGraph::new(root, graph, packages);

    Ok(graph)
}

/// Validate whether a dependency graph can be unified into a runnable package.
pub fn validate_dependency_graph(graph: &DependencyGraph) -> Result<(), ResolveError> {
    let sorted =
        petgraph::algo::toposort(graph.graph(), None).map_err(|_| cycle_error(graph.graph()))?;

    check_for_duplicate_versions(sorted.iter().map(|ix| &graph[*ix].id))
}

async fn discover_dependencies(
    root_id: &PackageId,
    root: &PackageInfo,
    source: &dyn Source,
) -> Result<DiscoveredPackages, ResolveError> {
    // First try a fast fixpoint pass that merges obviously compatible versions.
    let heuristic = discover_merged_dependencies(root_id, root, source).await?;
    if discovered_packages_are_unified(&heuristic) {
        return Ok(heuristic);
    }

    // If the greedy pass still leaves duplicate named packages behind, search
    // alternate version choices so lower direct versions can win when they are
    // the only way to keep the full graph consistent.
    if let Some(discovered) = discover_dependencies_with_backtracking(root_id, root, source).await?
    {
        return Ok(discovered);
    }

    Ok(heuristic)
}

async fn discover_merged_dependencies(
    root_id: &PackageId,
    root: &PackageInfo,
    source: &dyn Source,
) -> Result<DiscoveredPackages, ResolveError> {
    let mut selected_named = BTreeMap::new();
    let mut candidate_cache = BTreeMap::new();
    let mut seen_selections = BTreeSet::from([named_selection_signature(&selected_named)]);

    loop {
        let discovered = discover_dependencies_once(root_id, root, source, &selected_named).await?;
        let constraints = named_dependency_constraints(&discovered.graph);
        let next_selected =
            select_named_dependencies(constraints, source, &mut candidate_cache).await?;

        if same_named_selection(&selected_named, &next_selected) {
            return Ok(discovered);
        }

        if !seen_selections.insert(named_selection_signature(&next_selected)) {
            return Ok(discovered);
        }

        selected_named = next_selected;
    }
}

async fn discover_dependencies_once(
    root_id: &PackageId,
    root: &PackageInfo,
    source: &dyn Source,
    selected_named: &BTreeMap<String, PackageSummary>,
) -> Result<DiscoveredPackages, ResolveError> {
    let mut nodes: BTreeMap<PackageId, NodeIndex> = BTreeMap::new();
    let mut graph: DiGraph<Node, Edge> = DiGraph::new();

    let root_index = graph.add_node(Node {
        id: root_id.clone(),
        pkg: root.clone(),
        dist: None,
    });
    nodes.insert(root_id.clone(), root_index);

    let mut to_visit = VecDeque::new();
    to_visit.push_back(root_index);

    while let Some(index) = to_visit.pop_front() {
        let mut to_add = Vec::new();

        for dep in &graph[index].pkg.dependencies {
            let dep_summary = resolve_dependency(dep, source, selected_named)
                .await
                .map_err(|error| ResolveError::Registry {
                    package: dep.pkg.clone(),
                    error,
                })?;
            let dep_id = dep_summary.package_id();

            let PackageSummary { pkg, dist } = dep_summary;

            let alias = dep.alias().to_string();
            let node = Node {
                id: dep_id.clone(),
                pkg,
                dist: Some(dist),
            };
            // Note: We can't add the node to the graph directly because we're
            // still iterating over it.
            to_add.push((alias, node));
        }

        for (alias, node) in to_add {
            let dep_id = node.id.clone();

            let dep_index = match nodes.get(&dep_id) {
                Some(&ix) => ix,
                None => {
                    if nodes.len() >= MAX_DISCOVERED_PACKAGES {
                        return Err(ResolveError::TooComplex {
                            resource: "packages",
                            value: nodes.len() + 1,
                            limit: MAX_DISCOVERED_PACKAGES,
                        });
                    }
                    // Create a new node and schedule its dependencies to be
                    // retrieved
                    let ix = graph.add_node(node);
                    nodes.insert(dep_id, ix);
                    to_visit.push_back(ix);
                    if to_visit.len() > MAX_PENDING_DEPENDENCIES {
                        return Err(ResolveError::TooComplex {
                            resource: "pending_dependencies",
                            value: to_visit.len(),
                            limit: MAX_PENDING_DEPENDENCIES,
                        });
                    }
                    ix
                }
            };

            graph.add_edge(index, dep_index, Edge { alias });
        }
    }

    petgraph::algo::toposort(&graph, None).map_err(|_| cycle_error(&graph))?;

    Ok(DiscoveredPackages {
        root: root_index,
        graph,
        packages: nodes,
    })
}

async fn resolve_dependency(
    dep: &Dependency,
    source: &dyn Source,
    selected_named: &BTreeMap<String, PackageSummary>,
) -> Result<PackageSummary, QueryError> {
    let candidates = source.query(&dep.pkg).await?;

    match dep.pkg.as_named() {
        Some(named) => {
            if let Some(selected) = selected_named.get(&named.full_name())
                && let Some(id) = selected.pkg.id.as_named()
                && named.matches_id(id)
            {
                return Ok(selected.clone());
            }

            select_latest_named_dependency(candidates, dep)
        }
        None => candidates
            .into_iter()
            .next()
            .ok_or_else(|| QueryError::NotFound {
                query: dep.pkg.clone(),
            }),
    }
}

fn select_latest_named_dependency(
    candidates: Vec<PackageSummary>,
    dep: &Dependency,
) -> Result<PackageSummary, QueryError> {
    candidates
        .into_iter()
        .max_by(|left, right| {
            let left_version = left.pkg.id.as_named().map(|id| &id.version);
            let right_version = right.pkg.id.as_named().map(|id| &id.version);

            cmp_version_precedence(left_version, right_version)
        })
        .ok_or_else(|| QueryError::NoMatches {
            query: dep.pkg.clone(),
            archived_versions: Vec::new(),
        })
}

fn named_dependency_constraints(
    graph: &DiGraph<Node, Edge>,
) -> BTreeMap<String, Vec<NamedPackageIdent>> {
    let mut constraints: BTreeMap<String, Vec<NamedPackageIdent>> = BTreeMap::new();

    graph
        .node_weights()
        .flat_map(|node| &node.pkg.dependencies)
        .filter_map(|dep| dep.pkg.as_named())
        .for_each(|named| {
            constraints
                .entry(named.full_name())
                .or_default()
                .push(named.clone());
        });

    constraints
}

async fn select_named_dependencies(
    constraints: BTreeMap<String, Vec<NamedPackageIdent>>,
    source: &dyn Source,
    candidate_cache: &mut BTreeMap<String, Vec<PackageSummary>>,
) -> Result<BTreeMap<String, PackageSummary>, ResolveError> {
    let mut selected = BTreeMap::new();

    for (full_name, constraints) in constraints {
        let Some(summary) =
            select_unified_named_dependency(&constraints, source, candidate_cache).await?
        else {
            continue;
        };
        selected.insert(full_name, summary);
    }

    Ok(selected)
}

async fn select_unified_named_dependency(
    constraints: &[NamedPackageIdent],
    source: &dyn Source,
    candidate_cache: &mut BTreeMap<String, Vec<PackageSummary>>,
) -> Result<Option<PackageSummary>, ResolveError> {
    let [first, remaining @ ..] = constraints else {
        return Ok(None);
    };

    let mut candidates = named_dependency_candidates(first, source, candidate_cache).await?;

    for constraint in remaining {
        let matching_ids: HashSet<_> =
            named_dependency_candidates(constraint, source, candidate_cache)
                .await?
                .into_iter()
                .map(|summary| summary.package_id())
                .collect();

        candidates.retain(|candidate| matching_ids.contains(&candidate.package_id()));
    }

    Ok(candidates.into_iter().max_by(|left, right| {
        let left_version = left.pkg.id.as_named().map(|id| &id.version);
        let right_version = right.pkg.id.as_named().map(|id| &id.version);

        cmp_version_precedence(left_version, right_version)
    }))
}

fn same_named_selection(
    left: &BTreeMap<String, PackageSummary>,
    right: &BTreeMap<String, PackageSummary>,
) -> bool {
    left.len() == right.len()
        && left.iter().all(|(name, summary)| {
            right
                .get(name)
                .is_some_and(|other| summary.package_id() == other.package_id())
        })
}

fn named_selection_signature(
    selected: &BTreeMap<String, PackageSummary>,
) -> Vec<(String, PackageId)> {
    selected
        .iter()
        .map(|(name, summary)| (name.clone(), summary.package_id()))
        .collect()
}

fn discovered_packages_are_unified(discovered: &DiscoveredPackages) -> bool {
    let Ok(sorted) = petgraph::algo::toposort(&discovered.graph, None) else {
        return false;
    };

    check_for_duplicate_versions(sorted.iter().map(|ix| &discovered.graph[*ix].id)).is_ok()
}

async fn discover_dependencies_with_backtracking(
    root_id: &PackageId,
    root: &PackageInfo,
    source: &dyn Source,
) -> Result<Option<DiscoveredPackages>, ResolveError> {
    let mut candidate_cache = BTreeMap::new();
    let mut stack = vec![PartialDiscovery::new(root_id, root)];
    let mut states_explored = 0usize;

    while let Some(state) = stack.pop() {
        states_explored += 1;
        if states_explored > MAX_BACKTRACK_STATES {
            return Err(ResolveError::TooComplex {
                resource: "backtrack_states",
                value: states_explored,
                limit: MAX_BACKTRACK_STATES,
            });
        }

        let Some((task, remaining)) = state.pending.split_first() else {
            if petgraph::algo::toposort(&state.graph, None).is_ok() {
                let discovered = state.finish();
                if discovered_packages_are_unified(&discovered) {
                    return Ok(Some(discovered));
                }
            }
            continue;
        };

        let candidates = dependency_candidates(
            task.dep(),
            source,
            &state.selected_named,
            &mut candidate_cache,
        )
        .await?;

        for candidate in candidates.into_iter().rev() {
            // This still clones the graph state per candidate, but the clone is
            // bounded by the state, package, and pending-dependency limits.
            let mut next = state.clone();
            next.pending = remaining.to_vec();
            next.add_dependency(task.parent(), task.dep(), candidate)?;
            stack.push(next);
        }
    }

    Ok(None)
}

async fn dependency_candidates(
    dep: &Dependency,
    source: &dyn Source,
    selected_named: &BTreeMap<String, PackageSummary>,
    candidate_cache: &mut BTreeMap<String, Vec<PackageSummary>>,
) -> Result<Vec<PackageSummary>, ResolveError> {
    match dep.pkg.as_named() {
        Some(named) => {
            if let Some(selected) = selected_named.get(&named.full_name()) {
                let matches = if named
                    .tag
                    .as_ref()
                    .is_some_and(|tag| tag.as_named().is_some())
                {
                    named_dependency_candidates(named, source, candidate_cache)
                        .await?
                        .into_iter()
                        .any(|candidate| candidate.package_id() == selected.package_id())
                } else {
                    selected
                        .pkg
                        .id
                        .as_named()
                        .is_some_and(|id| named.matches_id(id))
                };
                return Ok(if matches {
                    vec![selected.clone()]
                } else {
                    Vec::new()
                });
            }

            let candidates = named_dependency_candidates(named, source, candidate_cache).await?;
            Ok(candidates
                .into_iter()
                .filter(|candidate| candidate_matches_named_query(named, candidate))
                .collect())
        }
        None => Ok(vec![
            source
                .query(&dep.pkg)
                .await
                .map_err(|error| ResolveError::Registry {
                    package: dep.pkg.clone(),
                    error,
                })?
                .into_iter()
                .next()
                .ok_or_else(|| ResolveError::Registry {
                    package: dep.pkg.clone(),
                    error: QueryError::NotFound {
                        query: dep.pkg.clone(),
                    },
                })?,
        ]),
    }
}

async fn named_dependency_candidates(
    named: &NamedPackageIdent,
    source: &dyn Source,
    candidate_cache: &mut BTreeMap<String, Vec<PackageSummary>>,
) -> Result<Vec<PackageSummary>, ResolveError> {
    let cache_key = named.build();

    let candidates = match candidate_cache.get(&cache_key) {
        Some(candidates) => candidates.clone(),
        None => {
            let query = PackageSource::from(named.clone());

            let mut candidates =
                source
                    .query(&query)
                    .await
                    .map_err(|error| ResolveError::Registry {
                        package: query.clone(),
                        error,
                    })?;
            sort_named_candidates_desc(&mut candidates);
            candidate_cache.insert(cache_key, candidates.clone());
            candidates
        }
    };

    Ok(candidates)
}

fn candidate_matches_named_query(named: &NamedPackageIdent, candidate: &PackageSummary) -> bool {
    let Some(id) = candidate.pkg.id.as_named() else {
        return false;
    };

    if named
        .tag
        .as_ref()
        .is_some_and(|tag| tag.as_named().is_some())
    {
        named.full_name() == id.full_name
    } else {
        named.matches_id(id)
    }
}

fn sort_named_candidates_desc(candidates: &mut [PackageSummary]) {
    candidates.sort_by(|left, right| {
        let left_version = left.pkg.id.as_named().map(|id| &id.version);
        let right_version = right.pkg.id.as_named().map(|id| &id.version);

        cmp_version_precedence(right_version, left_version)
    });
}

fn cycle_error(graph: &petgraph::Graph<Node, Edge>) -> ResolveError {
    // We know the graph has at least one cycle, so use SCC to find it.
    let mut cycle = petgraph::algo::kosaraju_scc(graph)
        .into_iter()
        .find(|cycle| {
            cycle.len() > 1
                || cycle
                    .first()
                    .is_some_and(|node| graph.edges(*node).any(|edge| edge.target() == *node))
        })
        .expect("We know there is at least one cycle");

    // we want the loop's starting node to be deterministic (for tests), and
    // nodes with lower indices are normally closer to the root of the
    // dependency tree.
    let lowest_index_node = cycle.iter().copied().min().expect("Cycle is non-empty");

    // We want the cycle vector to start with that node, so let's do a bit of
    // shuffling
    let offset = cycle
        .iter()
        .position(|&node| node == lowest_index_node)
        .unwrap();
    cycle.rotate_left(offset);

    // Don't forget to make the cycle start and end with the same node
    cycle.push(lowest_index_node);

    let package_ids = cycle.into_iter().map(|ix| graph[ix].id.clone()).collect();
    ResolveError::Cycle(package_ids)
}

#[derive(Debug)]
struct DiscoveredPackages {
    root: NodeIndex,
    graph: DiGraph<Node, Edge>,
    packages: BTreeMap<PackageId, NodeIndex>,
}

#[derive(Debug, Clone)]
struct PartialDiscovery {
    root: NodeIndex,
    graph: DiGraph<Node, Edge>,
    packages: BTreeMap<PackageId, NodeIndex>,
    pending: Vec<PendingDependency>,
    selected_named: BTreeMap<String, PackageSummary>,
}

impl PartialDiscovery {
    fn new(root_id: &PackageId, root: &PackageInfo) -> Self {
        let mut graph = DiGraph::new();
        let root_index = graph.add_node(Node {
            id: root_id.clone(),
            pkg: root.clone(),
            dist: None,
        });

        let packages = BTreeMap::from([(root_id.clone(), root_index)]);
        let pending = root
            .dependencies
            .iter()
            .cloned()
            .map(|dep| PendingDependency {
                parent: root_index,
                dep,
            })
            .collect();

        PartialDiscovery {
            root: root_index,
            graph,
            packages,
            pending,
            selected_named: BTreeMap::new(),
        }
    }

    fn add_dependency(
        &mut self,
        parent: NodeIndex,
        dep: &Dependency,
        summary: PackageSummary,
    ) -> Result<(), ResolveError> {
        let package_id = summary.package_id();
        let PackageSummary { pkg, dist } = summary.clone();

        if let Some(id) = pkg.id.as_named() {
            self.selected_named
                .entry(id.full_name.clone())
                .or_insert(summary);
        }

        let child = match self.packages.get(&package_id) {
            Some(&index) => index,
            None => {
                if self.packages.len() >= MAX_DISCOVERED_PACKAGES {
                    return Err(ResolveError::TooComplex {
                        resource: "packages",
                        value: self.packages.len() + 1,
                        limit: MAX_DISCOVERED_PACKAGES,
                    });
                }

                let pending_len = self.pending.len() + pkg.dependencies.len();
                if pending_len > MAX_PENDING_DEPENDENCIES {
                    return Err(ResolveError::TooComplex {
                        resource: "pending_dependencies",
                        value: pending_len,
                        limit: MAX_PENDING_DEPENDENCIES,
                    });
                }

                let index = self.graph.add_node(Node {
                    id: package_id.clone(),
                    pkg: pkg.clone(),
                    dist: Some(dist),
                });
                self.packages.insert(package_id, index);
                self.pending.extend(
                    pkg.dependencies
                        .iter()
                        .cloned()
                        .map(|dep| PendingDependency { parent: index, dep }),
                );
                index
            }
        };

        self.graph.add_edge(
            parent,
            child,
            Edge {
                alias: dep.alias().to_string(),
            },
        );

        Ok(())
    }

    fn finish(self) -> DiscoveredPackages {
        DiscoveredPackages {
            root: self.root,
            graph: self.graph,
            packages: self.packages,
        }
    }
}

#[derive(Debug, Clone)]
struct PendingDependency {
    parent: NodeIndex,
    dep: Dependency,
}

impl PendingDependency {
    fn parent(&self) -> NodeIndex {
        self.parent
    }

    fn dep(&self) -> &Dependency {
        &self.dep
    }
}

#[tracing::instrument(level = "debug", name = "dependencies", skip_all)]
fn log_dependencies(graph: &DiGraph<Node, Edge>, root: NodeIndex) {
    tracing::debug!(
        root = root.index(),
        dependency_count = graph.node_count(),
        "Resolved dependencies",
    );

    if tracing::enabled!(tracing::Level::TRACE) {
        petgraph::visit::depth_first_search(graph, [root], |event| {
            if let petgraph::visit::DfsEvent::Discover(n, _) = event {
                let package = &graph[n].id;
                let dependencies: BTreeMap<_, _> = graph
                    .edges(n)
                    .map(|edge_ref| (&edge_ref.weight().alias, &graph[edge_ref.target()].id))
                    .collect();

                tracing::trace!(%package, ?dependencies);
            }
        });
    }
}

/// As a workaround for the lack of "proper" dependency merging, we'll make sure
/// only one copy of each package is in the dependency tree. If the same package
/// is included in the tree multiple times, they all need to use the exact same
/// version otherwise it's an error.
fn check_for_duplicate_versions<'a, I>(package_ids: I) -> Result<(), ResolveError>
where
    I: Iterator<Item = &'a PackageId>,
{
    let mut package_versions: BTreeMap<&str, HashSet<&Version>> = BTreeMap::new();

    for id in package_ids {
        let Some(id) = id.as_named() else {
            continue;
        };
        package_versions
            .entry(&id.full_name)
            .or_default()
            .insert(&id.version);
    }

    for (package_name, versions) in package_versions {
        if versions.len() > 1 {
            let mut versions: Vec<_> = versions.into_iter().cloned().collect();
            versions.sort();
            return Err(ResolveError::DuplicateVersions {
                package_name: package_name.to_string(),
                versions,
            });
        }
    }

    Ok(())
}

/// Given some [`DiscoveredPackages`], figure out how the resulting "package"
/// would look when loaded at runtime.
fn resolve_package(dependency_graph: &DependencyGraph) -> Result<ResolvedPackage, ResolveError> {
    // FIXME: This code is all super naive and will break the moment there
    // are any conflicts or duplicate names.
    tracing::trace!("Resolving the package");

    let mut commands = BTreeMap::new();
    let mut filesystem = Vec::new();

    let mut entrypoint = dependency_graph.root_info().entrypoint.clone();

    for index in petgraph::algo::toposort(dependency_graph.graph(), None).expect("acyclic") {
        let node = &dependency_graph[index];
        let id = &node.id;
        let pkg = &node.pkg;

        // update the entrypoint, if necessary
        if entrypoint.is_none()
            && let Some(entry) = &pkg.entrypoint
        {
            tracing::trace!(
                entrypoint = entry.as_str(),
                parent=%id,
                "Inheriting the entrypoint",
            );

            entrypoint = Some(entry.clone());
        }

        for cmd in &pkg.commands {
            // Note: We are traversing in topological order with the root at the
            // start, so if we ever see any duplicates we should prefer the
            // earlier copy and skip the later one.

            match commands.entry(cmd.name.clone()) {
                std::collections::btree_map::Entry::Vacant(entry) => {
                    let resolved = ItemLocation {
                        name: cmd.name.clone(),
                        package: id.clone(),
                    };
                    entry.insert(resolved);
                    tracing::trace!(
                        command.name=cmd.name.as_str(),
                        pkg=%id,
                        "Discovered command",
                    );
                }
                std::collections::btree_map::Entry::Occupied(_) => {
                    tracing::trace!(
                        command.name=cmd.name.as_str(),
                        pkg=%id,
                        "Ignoring duplicate command",
                    );
                }
            }
        }

        for mapping in &pkg.filesystem {
            let dep = match &mapping.dependency_name {
                Some(name) => {
                    let dep_index = dependency_graph
                        .graph()
                        .edges(index)
                        .find(|edge| edge.weight().alias == *name)
                        .unwrap()
                        .target();
                    &dependency_graph[dep_index].id
                }
                None => id,
            };
            filesystem.push(ResolvedFileSystemMapping {
                mount_path: PathBuf::from(&mapping.mount_path),
                original_path: mapping.original_path.clone(),
                volume_name: mapping.volume_name.clone(),
                package: dep.clone(),
            })
        }
    }

    if entrypoint.is_none() {
        // We *still* haven't been able to figure out what the entrypoint for the
        // resolved package should be. If there is only one command in the main
        // package, let's assume they want to use that.
        //
        // This works around packages like saghul/quickjs and syrusakbary/cowsay
        // which don't specify their entrypoints explicitly.
        if let [cmd] = dependency_graph.root_info().commands.as_slice() {
            tracing::debug!(
                command = cmd.name.as_str(),
                "No entrypoint specified. Falling back to the root package's only command.",
            );
            entrypoint = Some(cmd.name.clone());
        }
    }

    tracing::debug!("resolved filesystem: {:?}", &filesystem);

    Ok(ResolvedPackage {
        root_package: dependency_graph.id().clone(),
        commands,
        entrypoint,
        filesystem,
    })
}

#[cfg(test)]
mod tests {
    use std::{path::PathBuf, time::Duration};

    use wasmer_config::package::{NamedPackageIdent, PackageIdent, Tag};

    use crate::runtime::resolver::{
        Dependency, InMemorySource, MultiSource,
        inputs::{DistributionInfo, FileSystemMapping, PackageInfo},
    };

    use super::*;

    struct RegistryBuilder(InMemorySource);

    impl RegistryBuilder {
        fn new() -> Self {
            RegistryBuilder(InMemorySource::new())
        }

        fn register(&mut self, name: &str, version: &str) -> AddPackageVersion<'_> {
            let pkg = PackageInfo {
                id: PackageId::new_named(name, version.parse().unwrap()),
                dependencies: Vec::new(),
                commands: Vec::new(),
                entrypoint: None,
                filesystem: Vec::new(),
            };
            let dist = DistributionInfo {
                webc: format!("http://localhost/{name}@{version}")
                    .parse()
                    .unwrap(),
                webc_sha256: [0; 32].into(),
            };
            let summary = PackageSummary { pkg, dist };

            AddPackageVersion {
                builder: &mut self.0,
                summary,
            }
        }

        fn finish(&self) -> MultiSource {
            let mut registry = MultiSource::default();
            registry.add_source(self.0.clone());
            registry
        }

        fn finish_with_tags(&self, tags: BTreeMap<(String, String), String>) -> TagResolvingSource {
            TagResolvingSource {
                inner: self.finish(),
                tags,
            }
        }

        fn get(&self, id: &PackageId) -> &PackageSummary {
            self.0.get(id).unwrap()
        }

        // fn get_named(&self, name: &str, version: &str) -> &PackageSummary {
        //     let id = PackageId::new_named(name, version.parse().unwrap());
        //     self.get(&id)
        // }

        fn start_dependency_graph(&self) -> DependencyGraphBuilder<'_> {
            DependencyGraphBuilder {
                dependencies: BTreeMap::new(),
                source: &self.0,
            }
        }
    }

    #[derive(Debug)]
    struct AddPackageVersion<'builder> {
        builder: &'builder mut InMemorySource,
        summary: PackageSummary,
    }

    impl AddPackageVersion<'_> {
        fn with_dependency(&mut self, name: &str, version_constraint: &str) -> &mut Self {
            self.with_aliased_dependency(name, name, version_constraint)
        }

        fn with_tagged_dependency(&mut self, name: &str, tag: &str) -> &mut Self {
            let pkg = PackageSource::from(NamedPackageIdent {
                registry: None,
                namespace: None,
                name: name.to_string(),
                tag: Some(Tag::Named(tag.to_string())),
            });

            self.summary.pkg.dependencies.push(Dependency {
                alias: name.to_string(),
                pkg,
            });

            self
        }

        fn with_aliased_dependency(
            &mut self,
            alias: &str,
            name: &str,
            version_constraint: &str,
        ) -> &mut Self {
            let pkg = PackageSource::from(
                NamedPackageIdent::try_from_full_name_and_version(name, version_constraint)
                    .unwrap(),
            );

            self.summary.pkg.dependencies.push(Dependency {
                alias: alias.to_string(),
                pkg,
            });

            self
        }

        fn with_command(&mut self, name: &str) -> &mut Self {
            self.summary
                .pkg
                .commands
                .push(crate::runtime::resolver::Command {
                    name: name.to_string(),
                });
            self
        }

        fn with_entrypoint(&mut self, name: &str) -> &mut Self {
            self.summary.pkg.entrypoint = Some(name.to_string());
            self
        }

        fn with_fs_mapping(
            &mut self,
            volume_name: &str,
            original_path: &str,
            mount_path: &str,
        ) -> &mut Self {
            self.summary.pkg.filesystem.push(FileSystemMapping {
                volume_name: volume_name.to_string(),
                mount_path: mount_path.to_string(),
                original_path: Some(original_path.to_string()),
                dependency_name: None,
            });
            self
        }

        fn with_fs_mapping_from_dependency(
            &mut self,
            volume_name: &str,
            mount_path: &str,
            original_path: &str,
            dependency: &str,
        ) -> &mut Self {
            self.summary.pkg.filesystem.push(FileSystemMapping {
                volume_name: volume_name.to_string(),
                mount_path: mount_path.to_string(),
                original_path: Some(original_path.to_string()),
                dependency_name: Some(dependency.to_string()),
            });
            self
        }
    }

    #[derive(Debug)]
    struct TagResolvingSource {
        inner: MultiSource,
        tags: BTreeMap<(String, String), String>,
    }

    #[async_trait::async_trait]
    impl Source for TagResolvingSource {
        async fn query(&self, package: &PackageSource) -> Result<Vec<PackageSummary>, QueryError> {
            let rewritten = match package {
                PackageSource::Ident(PackageIdent::Named(named)) => {
                    match named.tag.as_ref().and_then(|tag| tag.as_named()) {
                        Some(tag) => {
                            let version = self
                                .tags
                                .get(&(named.full_name(), tag.clone()))
                                .ok_or_else(|| QueryError::NotFound {
                                    query: package.clone(),
                                })?;
                            PackageSource::from(
                                NamedPackageIdent::try_from_full_name_and_version(
                                    &named.full_name(),
                                    &format!("={version}"),
                                )
                                .unwrap(),
                            )
                        }
                        None => package.clone(),
                    }
                }
                _ => package.clone(),
            };

            self.inner.query(&rewritten).await
        }
    }

    impl Drop for AddPackageVersion<'_> {
        fn drop(&mut self) {
            let summary = self.summary.clone();
            self.builder.add(summary);
        }
    }

    #[derive(Debug)]
    struct DependencyGraphBuilder<'source> {
        dependencies: BTreeMap<PackageId, BTreeMap<String, PackageId>>,
        source: &'source InMemorySource,
    }

    impl<'source> DependencyGraphBuilder<'source> {
        fn insert(&mut self, id: PackageId) -> DependencyGraphEntryBuilder<'source, '_> {
            let _ = self.source.get(&id).unwrap();
            DependencyGraphEntryBuilder {
                builder: self,
                pkg_id: id,
                dependencies: BTreeMap::new(),
            }
        }

        fn finish(self) -> BTreeMap<PackageId, BTreeMap<String, PackageId>> {
            self.dependencies
        }

        /// Using the dependency mapping that we've been building up, construct
        /// a dependency graph using the specified root package.
        fn graph(self, root_id: PackageId) -> DependencyGraph {
            let _ = self.source.get(&root_id).unwrap();

            let mut graph = DiGraph::new();
            let mut nodes = BTreeMap::new();

            for id in self.dependencies.keys() {
                let PackageSummary { pkg, dist } = self.source.get(id).unwrap();
                let index = graph.add_node(Node {
                    id: pkg.id(),
                    pkg: pkg.clone(),
                    dist: Some(dist.clone()),
                });
                nodes.insert(id.clone(), index);
            }

            for (id, deps) in &self.dependencies {
                let index = nodes[id];
                for (dep_name, dep_id) in deps {
                    let dep_index = nodes[dep_id];
                    graph.add_edge(
                        index,
                        dep_index,
                        Edge {
                            alias: dep_name.clone(),
                        },
                    );
                }
            }

            let root_index = nodes[&root_id];

            DependencyGraph::new(root_index, graph, nodes)
        }
    }

    #[derive(Debug)]
    struct DependencyGraphEntryBuilder<'source, 'builder> {
        builder: &'builder mut DependencyGraphBuilder<'source>,
        pkg_id: PackageId,
        dependencies: BTreeMap<String, PackageId>,
    }

    impl DependencyGraphEntryBuilder<'_, '_> {
        fn with_dependency(&mut self, id: &PackageId) -> &mut Self {
            let name = &id.as_named().unwrap().full_name;
            self.with_aliased_dependency(name, id)
        }

        fn with_aliased_dependency(&mut self, alias: &str, id: &PackageId) -> &mut Self {
            let dep_id = self.builder.source.get(id).unwrap().package_id();
            self.dependencies.insert(alias.to_string(), dep_id);
            self
        }
    }

    impl Drop for DependencyGraphEntryBuilder<'_, '_> {
        fn drop(&mut self) {
            self.builder
                .dependencies
                .insert(self.pkg_id.clone(), self.dependencies.clone());
        }
    }

    macro_rules! map {
        (
            $(
                $key:expr => $value:expr
            ),*
            $(,)?
        ) => {
            vec![
                $( ($key.into(), $value.into()) ),*
            ]
            .into_iter()
            .collect()
        }
    }

    fn deps(resolution: &Resolution) -> BTreeMap<PackageId, BTreeMap<String, PackageId>> {
        resolution
            .graph
            .iter_dependencies()
            .map(|(id, deps)| {
                let deps = deps
                    .into_iter()
                    .map(|(name, dep_id)| (name.to_string(), dep_id.clone()))
                    .collect();
                (id.clone(), deps)
            })
            .collect()
    }

    #[tokio::test]
    async fn no_deps_and_no_commands() {
        let mut builder = RegistryBuilder::new();
        builder.register("root", "1.0.0");
        let registry = builder.finish();
        let id = PackageId::new_named("root", Version::parse("1.0.0").unwrap());
        let root = builder.get(&id);

        let resolution = resolve(&root.package_id(), &root.pkg, &registry)
            .await
            .unwrap();

        let mut dependency_graph = builder.start_dependency_graph();
        dependency_graph.insert(id);
        assert_eq!(deps(&resolution), dependency_graph.finish());
        assert_eq!(
            resolution.package,
            ResolvedPackage {
                root_package: root.package_id(),
                commands: BTreeMap::new(),
                entrypoint: None,
                filesystem: Vec::new(),
            }
        );
    }

    #[tokio::test]
    async fn no_deps_one_command() {
        let mut builder = RegistryBuilder::new();
        builder.register("root", "1.0.0").with_command("asdf");
        let registry = builder.finish();
        let id = PackageId::new_named("root", "1.0.0".parse().unwrap());
        let root = builder.get(&id);

        let resolution = resolve(&root.package_id(), &root.pkg, &registry)
            .await
            .unwrap();

        let mut dependency_graph = builder.start_dependency_graph();
        dependency_graph.insert(id.clone());
        assert_eq!(deps(&resolution), dependency_graph.finish());
        assert_eq!(
            resolution.package,
            ResolvedPackage {
                root_package: root.package_id(),
                commands: map! {
                    "asdf" => ItemLocation {
                        name: "asdf".to_string(),
                        package: root.package_id(),
                    },
                },
                entrypoint: Some("asdf".to_string()),
                filesystem: Vec::new(),
            }
        );
    }

    #[tokio::test]
    async fn single_dependency() {
        let mut builder = RegistryBuilder::new();
        builder
            .register("root", "1.0.0")
            .with_dependency("dep", "=1.0.0");
        builder.register("dep", "1.0.0");
        let registry = builder.finish();
        let id = PackageId::new_named("root", "1.0.0".parse().unwrap());
        let root = builder.get(&id);

        let resolution = resolve(&root.package_id(), &root.pkg, &registry)
            .await
            .unwrap();
        let dep_id = PackageId::new_named("dep", "1.0.0".parse().unwrap());

        let mut dependency_graph = builder.start_dependency_graph();
        dependency_graph.insert(id.clone()).with_dependency(&dep_id);
        dependency_graph.insert(dep_id.clone());
        assert_eq!(deps(&resolution), dependency_graph.finish());
        assert_eq!(
            resolution.package,
            ResolvedPackage {
                root_package: root.package_id(),
                commands: BTreeMap::new(),
                entrypoint: None,
                filesystem: Vec::new(),
            }
        );
    }

    #[tokio::test]
    async fn linear_dependency_chain() {
        let first_id = PackageId::new_named("first", "1.0.0".parse().unwrap());
        let second_id = PackageId::new_named("second", "1.0.0".parse().unwrap());
        let third_id = PackageId::new_named("third", "1.0.0".parse().unwrap());

        let mut builder = RegistryBuilder::new();
        builder
            .register("first", "1.0.0")
            .with_dependency("second", "=1.0.0");
        builder
            .register("second", "1.0.0")
            .with_dependency("third", "=1.0.0");
        builder.register("third", "1.0.0");
        let registry = builder.finish();
        let root = builder.get(&first_id);

        let resolution = resolve(&root.package_id(), &root.pkg, &registry)
            .await
            .unwrap();

        let mut dependency_graph = builder.start_dependency_graph();
        dependency_graph
            .insert(first_id.clone())
            .with_dependency(&second_id);
        dependency_graph
            .insert(second_id.clone())
            .with_dependency(&third_id);
        dependency_graph.insert(third_id.clone());
        assert_eq!(deps(&resolution), dependency_graph.finish());
        assert_eq!(
            resolution.package,
            ResolvedPackage {
                root_package: root.package_id(),
                commands: BTreeMap::new(),
                entrypoint: None,
                filesystem: Vec::new(),
            }
        );
    }

    #[tokio::test]
    async fn pick_the_latest_dependency_when_multiple_are_possible() {
        let root_id = PackageId::new_named("root", "1.0.0".parse().unwrap());
        let mut builder = RegistryBuilder::new();
        builder
            .register("root", "1.0.0")
            .with_dependency("dep", "^1.0.0");
        builder.register("dep", "1.0.0");
        builder.register("dep", "1.0.1");
        builder.register("dep", "1.0.2");
        let registry = builder.finish();
        let root = builder.get(&root_id);

        let resolution = resolve(&root.package_id(), &root.pkg, &registry)
            .await
            .unwrap();
        let dep_id = PackageId::new_named("dep", "1.0.2".parse().unwrap());

        let mut dependency_graph = builder.start_dependency_graph();
        dependency_graph
            .insert(root_id.clone())
            .with_dependency(&dep_id);
        dependency_graph.insert(dep_id.clone());
        assert_eq!(deps(&resolution), dependency_graph.finish());
        assert_eq!(
            resolution.package,
            ResolvedPackage {
                root_package: root.package_id(),
                commands: BTreeMap::new(),
                entrypoint: None,
                filesystem: Vec::new(),
            }
        );
    }

    #[tokio::test]
    async fn merge_compatible_versions() {
        let root_id = PackageId::new_named("root", "1.0.0".parse().unwrap());
        let first_id = PackageId::new_named("first", "1.0.0".parse().unwrap());
        let second_id = PackageId::new_named("second", "1.0.0".parse().unwrap());
        let common_id = PackageId::new_named("common", "1.2.0".parse().unwrap());

        let mut builder = RegistryBuilder::new();
        builder
            .register("root", "1.0.0")
            .with_dependency("first", "=1.0.0")
            .with_dependency("second", "=1.0.0");
        builder
            .register("first", "1.0.0")
            .with_dependency("common", "^1.0.0");
        builder
            .register("second", "1.0.0")
            .with_dependency("common", ">1.1,<1.3");
        builder.register("common", "1.0.0");
        builder.register("common", "1.1.0");
        builder.register("common", "1.2.0");
        builder.register("common", "1.5.0");
        let registry = builder.finish();
        let root = builder.get(&root_id);

        let resolution = resolve(&root.package_id(), &root.pkg, &registry)
            .await
            .unwrap();

        let mut dependency_graph = builder.start_dependency_graph();
        dependency_graph
            .insert(root_id.clone())
            .with_dependency(&first_id)
            .with_dependency(&second_id);
        dependency_graph
            .insert(first_id.clone())
            .with_dependency(&common_id);
        dependency_graph
            .insert(second_id.clone())
            .with_dependency(&common_id);
        dependency_graph.insert(common_id.clone());
        assert_eq!(deps(&resolution), dependency_graph.finish());
        assert_eq!(
            resolution.package,
            ResolvedPackage {
                root_package: root.package_id(),
                commands: BTreeMap::new(),
                entrypoint: None,
                filesystem: Vec::new(),
            }
        );
    }

    #[tokio::test]
    async fn merge_compatible_versions_when_constraints_appear_later() {
        let root_id = PackageId::new_named("root", "1.0.0".parse().unwrap());
        let first_id = PackageId::new_named("first", "1.0.0".parse().unwrap());
        let second_id = PackageId::new_named("second", "1.0.0".parse().unwrap());
        let mid_id = PackageId::new_named("mid", "1.0.0".parse().unwrap());
        let common_id = PackageId::new_named("common", "1.2.0".parse().unwrap());

        let mut builder = RegistryBuilder::new();
        builder
            .register("root", "1.0.0")
            .with_dependency("first", "=1.0.0")
            .with_dependency("second", "=1.0.0");
        builder
            .register("first", "1.0.0")
            .with_dependency("common", "^1.0.0");
        builder
            .register("second", "1.0.0")
            .with_dependency("mid", "=1.0.0");
        builder
            .register("mid", "1.0.0")
            .with_dependency("common", "<=1.2.0");
        builder.register("common", "1.2.0");
        builder.register("common", "1.5.0");
        let registry = builder.finish();
        let root = builder.get(&root_id);

        let resolution = resolve(&root.package_id(), &root.pkg, &registry)
            .await
            .unwrap();

        let mut dependency_graph = builder.start_dependency_graph();
        dependency_graph
            .insert(root_id.clone())
            .with_dependency(&first_id)
            .with_dependency(&second_id);
        dependency_graph
            .insert(first_id.clone())
            .with_dependency(&common_id);
        dependency_graph
            .insert(second_id.clone())
            .with_dependency(&mid_id);
        dependency_graph
            .insert(mid_id.clone())
            .with_dependency(&common_id);
        dependency_graph.insert(common_id.clone());
        assert_eq!(deps(&resolution), dependency_graph.finish());
    }

    #[tokio::test]
    async fn pick_a_lower_direct_dependency_to_preserve_transitive_unification() {
        let root_id = PackageId::new_named("root", "1.0.0".parse().unwrap());
        let feature_id = PackageId::new_named("feature", "1.0.0".parse().unwrap());
        let common_id = PackageId::new_named("common", "1.5.0".parse().unwrap());
        let shared_id = PackageId::new_named("shared", "1.0.0".parse().unwrap());

        let mut builder = RegistryBuilder::new();
        builder
            .register("root", "1.0.0")
            .with_dependency("feature", "^1.0.0")
            .with_dependency("shared", "=1.0.0");
        builder
            .register("feature", "1.0.0")
            .with_dependency("common", "^1.0.0");
        builder
            .register("feature", "1.1.0")
            .with_dependency("common", "^2.0.0");
        builder
            .register("shared", "1.0.0")
            .with_dependency("common", "=1.5.0");
        builder.register("common", "1.5.0");
        builder.register("common", "2.1.0");
        let registry = builder.finish();
        let root = builder.get(&root_id);

        let resolution = resolve(&root.package_id(), &root.pkg, &registry)
            .await
            .unwrap();

        let mut dependency_graph = builder.start_dependency_graph();
        dependency_graph
            .insert(root_id.clone())
            .with_dependency(&feature_id)
            .with_dependency(&shared_id);
        dependency_graph
            .insert(feature_id.clone())
            .with_dependency(&common_id);
        dependency_graph
            .insert(shared_id.clone())
            .with_dependency(&common_id);
        dependency_graph.insert(common_id.clone());
        assert_eq!(deps(&resolution), dependency_graph.finish());
    }

    #[tokio::test]
    async fn pick_a_lower_dependency_after_branching_transitive_constraints() {
        let root_id = PackageId::new_named("root", "1.0.0".parse().unwrap());
        let feature_id = PackageId::new_named("feature", "1.0.0".parse().unwrap());
        let aggregator_id = PackageId::new_named("aggregator", "1.0.0".parse().unwrap());
        let leaf_id = PackageId::new_named("leaf", "1.0.0".parse().unwrap());
        let common_id = PackageId::new_named("common", "1.4.0".parse().unwrap());

        let mut builder = RegistryBuilder::new();
        builder
            .register("root", "1.0.0")
            .with_dependency("feature", "^1.0.0")
            .with_dependency("aggregator", "=1.0.0");
        builder
            .register("feature", "1.0.0")
            .with_dependency("common", "^1.0.0");
        builder
            .register("feature", "1.1.0")
            .with_dependency("common", "^2.0.0");
        builder
            .register("aggregator", "1.0.0")
            .with_dependency("leaf", "=1.0.0");
        builder
            .register("leaf", "1.0.0")
            .with_dependency("common", "<=1.4.0");
        builder.register("common", "1.4.0");
        builder.register("common", "2.0.0");
        let registry = builder.finish();
        let root = builder.get(&root_id);

        let resolution = resolve(&root.package_id(), &root.pkg, &registry)
            .await
            .unwrap();

        let mut dependency_graph = builder.start_dependency_graph();
        dependency_graph
            .insert(root_id.clone())
            .with_dependency(&feature_id)
            .with_dependency(&aggregator_id);
        dependency_graph
            .insert(feature_id.clone())
            .with_dependency(&common_id);
        dependency_graph
            .insert(aggregator_id.clone())
            .with_dependency(&leaf_id);
        dependency_graph
            .insert(leaf_id.clone())
            .with_dependency(&common_id);
        dependency_graph.insert(common_id.clone());
        assert_eq!(deps(&resolution), dependency_graph.finish());
    }

    #[tokio::test]
    async fn backtracking_skips_acyclic_graphs_that_are_not_unified() {
        let root_id = PackageId::new_named("root", "1.0.0".parse().unwrap());
        let feature_id = PackageId::new_named("feature", "1.0.0".parse().unwrap());

        let mut builder = RegistryBuilder::new();
        builder
            .register("root", "1.0.0")
            .with_dependency("feature", "^1.0.0");
        builder.register("root", "1.1.0");
        builder.register("feature", "1.0.0");
        builder
            .register("feature", "1.1.0")
            .with_dependency("root", "^1.0.0");
        let registry = builder.finish();
        let root = builder.get(&root_id);

        let resolution = resolve(&root.package_id(), &root.pkg, &registry)
            .await
            .unwrap();

        let mut dependency_graph = builder.start_dependency_graph();
        dependency_graph
            .insert(root_id.clone())
            .with_dependency(&feature_id);
        dependency_graph.insert(feature_id.clone());
        assert_eq!(deps(&resolution), dependency_graph.finish());
    }

    #[tokio::test]
    async fn oscillating_greedy_selection_falls_back_to_backtracking() {
        let root_id = PackageId::new_named("root", "1.0.0".parse().unwrap());
        let a_id = PackageId::new_named("a", "1.0.0".parse().unwrap());

        let mut builder = RegistryBuilder::new();
        builder
            .register("root", "1.0.0")
            .with_dependency("a", "^1.0.0");
        builder.register("a", "1.0.0");
        builder
            .register("a", "2.0.0")
            .with_dependency("x", "=1.0.0");
        builder
            .register("x", "1.0.0")
            .with_dependency("a", "=1.0.0");
        let registry = builder.finish();
        let root = builder.get(&root_id);

        tokio::time::timeout(
            Duration::from_secs(1),
            discover_merged_dependencies(&root.package_id(), &root.pkg, &registry),
        )
        .await
        .expect("greedy dependency discovery did not terminate")
        .unwrap();

        let resolution = resolve(&root.package_id(), &root.pkg, &registry)
            .await
            .unwrap();

        let mut dependency_graph = builder.start_dependency_graph();
        dependency_graph
            .insert(root_id.clone())
            .with_dependency(&a_id);
        dependency_graph.insert(a_id.clone());
        assert_eq!(deps(&resolution), dependency_graph.finish());
    }

    #[tokio::test]
    async fn named_tags_are_resolved_through_the_source_during_backtracking() {
        let root_id = PackageId::new_named("root", "1.0.0".parse().unwrap());
        let feature_id = PackageId::new_named("feature", "1.0.0".parse().unwrap());
        let common_id = PackageId::new_named("common", "1.5.0".parse().unwrap());
        let shared_id = PackageId::new_named("shared", "1.0.0".parse().unwrap());

        let mut builder = RegistryBuilder::new();
        builder
            .register("root", "1.0.0")
            .with_dependency("feature", "^1.0.0")
            .with_dependency("shared", "=1.0.0");
        builder
            .register("feature", "1.0.0")
            .with_tagged_dependency("common", "stable");
        builder
            .register("feature", "1.1.0")
            .with_dependency("common", "^2.0.0");
        builder
            .register("shared", "1.0.0")
            .with_dependency("common", "=1.5.0");
        builder.register("common", "1.5.0");
        builder.register("common", "2.1.0");
        let registry = builder.finish_with_tags(BTreeMap::from([(
            ("common".to_string(), "stable".to_string()),
            "1.5.0".to_string(),
        )]));
        let root = builder.get(&root_id);

        let resolution = resolve(&root.package_id(), &root.pkg, &registry)
            .await
            .unwrap();

        let mut dependency_graph = builder.start_dependency_graph();
        dependency_graph
            .insert(root_id.clone())
            .with_dependency(&feature_id)
            .with_dependency(&shared_id);
        dependency_graph
            .insert(feature_id.clone())
            .with_dependency(&common_id);
        dependency_graph
            .insert(shared_id.clone())
            .with_dependency(&common_id);
        dependency_graph.insert(common_id.clone());
        assert_eq!(deps(&resolution), dependency_graph.finish());
    }

    #[tokio::test]
    async fn incompatible_versions_still_report_duplicates() {
        let root_id = PackageId::new_named("root", "1.0.0".parse().unwrap());

        let mut builder = RegistryBuilder::new();
        builder
            .register("root", "1.0.0")
            .with_dependency("first", "=1.0.0")
            .with_dependency("second", "=1.0.0");
        builder
            .register("first", "1.0.0")
            .with_dependency("common", "=1.0.0");
        builder
            .register("second", "1.0.0")
            .with_dependency("common", "=2.0.0");
        builder.register("common", "1.0.0");
        builder.register("common", "2.0.0");
        let registry = builder.finish();
        let root = builder.get(&root_id);

        let result = resolve(&root.package_id(), &root.pkg, &registry).await;

        match result {
            Err(ResolveError::DuplicateVersions {
                package_name,
                versions,
            }) => {
                assert_eq!(package_name, "common");
                assert_eq!(
                    versions,
                    [
                        Version::parse("1.0.0").unwrap(),
                        Version::parse("2.0.0").unwrap(),
                    ]
                );
            }
            _ => unreachable!("Expected a duplicate versions error, found {:?}", result),
        }
    }

    #[tokio::test]
    async fn incompatible_parent_versions_still_report_duplicates_when_no_solution_exists() {
        let root_id = PackageId::new_named("root", "1.0.0".parse().unwrap());

        let mut builder = RegistryBuilder::new();
        builder
            .register("root", "1.0.0")
            .with_dependency("feature", "^1.0.0")
            .with_dependency("shared", "=1.0.0");
        builder
            .register("feature", "1.0.0")
            .with_dependency("common", "^1.0.0");
        builder
            .register("feature", "1.1.0")
            .with_dependency("common", "^2.0.0");
        builder
            .register("shared", "1.0.0")
            .with_dependency("common", "=3.0.0");
        builder.register("common", "1.5.0");
        builder.register("common", "2.1.0");
        builder.register("common", "3.0.0");
        let registry = builder.finish();
        let root = builder.get(&root_id);

        let result = resolve(&root.package_id(), &root.pkg, &registry).await;

        match result {
            Err(ResolveError::DuplicateVersions {
                package_name,
                versions,
            }) => {
                assert_eq!(package_name, "common");
                assert_eq!(
                    versions,
                    [
                        Version::parse("2.1.0").unwrap(),
                        Version::parse("3.0.0").unwrap(),
                    ]
                );
            }
            _ => unreachable!("Expected a duplicate versions error, found {:?}", result),
        }
    }

    #[tokio::test]
    async fn very_large_dependency_graphs_fail_with_a_clear_limit_error() {
        let root_id = PackageId::new_named("pkg0", "1.0.0".parse().unwrap());

        let mut builder = RegistryBuilder::new();
        for ix in 0..=MAX_DISCOVERED_PACKAGES {
            let name = format!("pkg{ix}");
            let version = "1.0.0";
            let mut pkg = builder.register(&name, version);
            if ix < MAX_DISCOVERED_PACKAGES {
                let dep_name = format!("pkg{}", ix + 1);
                pkg.with_dependency(&dep_name, "=1.0.0");
            }
        }

        let registry = builder.finish();
        let root = builder.get(&root_id);

        let result = resolve(&root.package_id(), &root.pkg, &registry).await;

        match result {
            Err(ResolveError::TooComplex {
                resource,
                value,
                limit,
            }) => {
                assert_eq!(resource, "packages");
                assert_eq!(limit, MAX_DISCOVERED_PACKAGES);
                assert!(value > limit);
            }
            _ => unreachable!("Expected a complexity limit error, found {:?}", result),
        }
    }

    #[test]
    fn validate_dependency_graph_reports_cycles_without_panicking() {
        let mut builder = RegistryBuilder::new();
        builder.register("root", "1.0.0");
        builder.register("dep", "1.0.0");

        let root_id = PackageId::new_named("root", "1.0.0".parse().unwrap());
        let dep_id = PackageId::new_named("dep", "1.0.0".parse().unwrap());

        let root = builder.get(&root_id);
        let dep = builder.get(&dep_id);

        let mut graph = DiGraph::new();
        let root_ix = graph.add_node(Node {
            id: root_id.clone(),
            pkg: root.pkg.clone(),
            dist: Some(root.dist.clone()),
        });
        let dep_ix = graph.add_node(Node {
            id: dep_id.clone(),
            pkg: dep.pkg.clone(),
            dist: Some(dep.dist.clone()),
        });

        graph.add_edge(
            root_ix,
            dep_ix,
            Edge {
                alias: "dep".to_string(),
            },
        );
        graph.add_edge(
            dep_ix,
            root_ix,
            Edge {
                alias: "root".to_string(),
            },
        );

        let graph = DependencyGraph::new(
            root_ix,
            graph,
            BTreeMap::from([(root_id, root_ix), (dep_id, dep_ix)]),
        );

        assert!(matches!(
            validate_dependency_graph(&graph),
            Err(ResolveError::Cycle(_))
        ));
    }

    #[test]
    fn backtracking_partial_discovery_enforces_pending_dependency_limit() {
        let root_id = PackageId::new_named("root", "1.0.0".parse().unwrap());
        let child_id = PackageId::new_named("child", "1.0.0".parse().unwrap());

        let root = PackageInfo {
            id: root_id.clone(),
            dependencies: vec![Dependency {
                alias: "child".to_string(),
                pkg: PackageSource::from(
                    NamedPackageIdent::try_from_full_name_and_version("child", "=1.0.0").unwrap(),
                ),
            }],
            commands: Vec::new(),
            entrypoint: None,
            filesystem: Vec::new(),
        };
        let mut child = PackageInfo {
            id: child_id.clone(),
            dependencies: Vec::new(),
            commands: Vec::new(),
            entrypoint: None,
            filesystem: Vec::new(),
        };
        for ix in 0..=MAX_PENDING_DEPENDENCIES {
            let name = format!("leaf{ix}");
            child.dependencies.push(Dependency {
                alias: name.clone(),
                pkg: PackageSource::from(
                    NamedPackageIdent::try_from_full_name_and_version(&name, "=1.0.0").unwrap(),
                ),
            });
        }
        let dist = DistributionInfo {
            webc: "http://localhost/child@1.0.0".parse().unwrap(),
            webc_sha256: [0; 32].into(),
        };

        let mut discovery = PartialDiscovery::new(&root_id, &root);
        let task = discovery.pending.remove(0);
        let result = discovery.add_dependency(
            task.parent(),
            task.dep(),
            PackageSummary { pkg: child, dist },
        );

        match result {
            Err(ResolveError::TooComplex {
                resource,
                value,
                limit,
            }) => {
                assert_eq!(resource, "pending_dependencies");
                assert_eq!(limit, MAX_PENDING_DEPENDENCIES);
                assert!(value > limit);
            }
            _ => unreachable!("Expected a complexity limit error, found {:?}", result),
        }
    }

    #[tokio::test]
    async fn backtracking_handles_deep_incompatible_candidate_tree_with_state_limit() {
        let root_id = PackageId::new_named("root", "1.0.0".parse().unwrap());

        let mut builder = RegistryBuilder::new();
        builder
            .register("root", "1.0.0")
            .with_dependency("branch0", "^1.0.0")
            .with_dependency("pinner", "=1.0.0");

        for branch in 0..8 {
            for version in 0..8 {
                let name = format!("branch{branch}");
                let version = format!("1.{version}.0");
                let mut pkg = builder.register(&name, &version);
                pkg.with_dependency("common", "=2.0.0");
                if branch < 7 {
                    pkg.with_dependency(&format!("branch{}", branch + 1), "^1.0.0");
                }
            }
        }

        builder
            .register("pinner", "1.0.0")
            .with_dependency("common", "=1.0.0");
        builder.register("common", "1.0.0");
        builder.register("common", "2.0.0");

        let registry = builder.finish();
        let root = builder.get(&root_id);

        let result = tokio::time::timeout(
            Duration::from_secs(1),
            resolve(&root.package_id(), &root.pkg, &registry),
        )
        .await
        .expect("backtracking did not finish within the test budget");

        assert!(matches!(
            result,
            Err(ResolveError::DuplicateVersions { .. })
                | Err(ResolveError::TooComplex {
                    resource: "backtrack_states",
                    ..
                })
        ));
    }

    #[tokio::test]
    async fn commands_from_dependencies_end_up_in_the_package() {
        let root_id = PackageId::new_named("root", "1.0.0".parse().unwrap());
        let first_id = PackageId::new_named("first", "1.0.0".parse().unwrap());
        let second_id = PackageId::new_named("second", "1.0.0".parse().unwrap());
        let mut builder = RegistryBuilder::new();
        builder
            .register("root", "1.0.0")
            .with_dependency("first", "=1.0.0")
            .with_dependency("second", "=1.0.0");
        builder
            .register("first", "1.0.0")
            .with_command("first-command");
        builder
            .register("second", "1.0.0")
            .with_command("second-command");
        let registry = builder.finish();
        let root = builder.get(&root_id);

        let resolution = resolve(&root.package_id(), &root.pkg, &registry)
            .await
            .unwrap();

        let mut dependency_graph = builder.start_dependency_graph();
        dependency_graph
            .insert(root_id.clone())
            .with_dependency(&first_id)
            .with_dependency(&second_id);
        dependency_graph.insert(first_id.clone());
        dependency_graph.insert(second_id.clone());
        assert_eq!(deps(&resolution), dependency_graph.finish());
        assert_eq!(
            resolution.package,
            ResolvedPackage {
                root_package: root.package_id(),
                commands: map! {
                    "first-command" => ItemLocation {
                        name: "first-command".to_string(),
                        package: builder.get(&first_id).package_id(),
                     },
                    "second-command" => ItemLocation {
                        name: "second-command".to_string(),
                        package: builder.get(&second_id).package_id(),
                     },
                },
                entrypoint: None,
                filesystem: Vec::new(),
            }
        );
    }

    #[tokio::test]
    async fn commands_in_root_shadow_their_dependencies() {
        let root_id = PackageId::new_named("root", "1.0.0".parse().unwrap());
        let dep_id = PackageId::new_named("dep", "1.0.0".parse().unwrap());
        let mut builder = RegistryBuilder::new();
        builder
            .register("root", "1.0.0")
            .with_dependency("dep", "=1.0.0")
            .with_command("command");
        builder.register("dep", "1.0.0").with_command("command");
        let registry = builder.finish();
        let root = builder.get(&root_id);

        let resolution = resolve(&root.package_id(), &root.pkg, &registry)
            .await
            .unwrap();

        let mut dependency_graph = builder.start_dependency_graph();
        dependency_graph
            .insert(root_id.clone())
            .with_dependency(&dep_id);
        dependency_graph.insert(dep_id.clone());
        assert_eq!(deps(&resolution), dependency_graph.finish());
        assert_eq!(
            resolution.package,
            ResolvedPackage {
                root_package: root.package_id(),
                commands: map! {
                    "command" => ItemLocation {
                        name: "command".to_string(),
                        package: builder.get(&root_id).package_id(),
                     },
                },
                entrypoint: Some("command".to_string()),
                filesystem: Vec::new(),
            }
        );
    }

    #[tokio::test]
    async fn cyclic_dependencies() {
        let root_id = PackageId::new_named("root", "1.0.0".parse().unwrap());
        let dep_id = PackageId::new_named("dep", "1.0.0".parse().unwrap());

        let mut builder = RegistryBuilder::new();
        builder
            .register("root", "1.0.0")
            .with_dependency("dep", "=1.0.0");
        builder
            .register("dep", "1.0.0")
            .with_dependency("root", "=1.0.0");
        let registry = builder.finish();
        let root = builder.get(&root_id);

        let err = resolve(&root.package_id(), &root.pkg, &registry)
            .await
            .unwrap_err();

        let cycle = err.as_cycle().unwrap().to_vec();
        assert_eq!(
            cycle,
            [
                builder.get(&root_id).package_id(),
                builder.get(&dep_id).package_id(),
                builder.get(&root_id).package_id(),
            ]
        );
    }

    #[tokio::test]
    async fn entrypoint_is_inherited() {
        let root_id = PackageId::new_named("root", "1.0.0".parse().unwrap());
        let dep_id = PackageId::new_named("dep", "1.0.0".parse().unwrap());

        let mut builder = RegistryBuilder::new();
        builder
            .register("root", "1.0.0")
            .with_dependency("dep", "=1.0.0");
        builder
            .register("dep", "1.0.0")
            .with_command("entry")
            .with_entrypoint("entry");
        let registry = builder.finish();
        let root = builder.get(&root_id);

        let resolution = resolve(&root.package_id(), &root.pkg, &registry)
            .await
            .unwrap();

        assert_eq!(
            resolution.package,
            ResolvedPackage {
                root_package: root.package_id(),
                commands: map! {
                    "entry" => ItemLocation {
                        name: "entry".to_string(),
                        package: builder.get(&dep_id).package_id(),
                     },
                },
                entrypoint: Some("entry".to_string()),
                filesystem: Vec::new(),
            }
        );
    }

    #[tokio::test]
    async fn infer_entrypoint_if_unspecified_and_only_one_command_in_root_package() {
        let root_id = PackageId::new_named("root", "1.0.0".parse().unwrap());
        let mut builder = RegistryBuilder::new();
        builder
            .register("root", "1.0.0")
            .with_command("root-cmd")
            .with_dependency("dep", "=1.0.0");
        builder.register("dep", "1.0.0").with_command("entry");
        let registry = builder.finish();
        let root = builder.get(&root_id);

        let resolution = resolve(&root.package_id(), &root.pkg, &registry)
            .await
            .unwrap();

        assert_eq!(resolution.package.entrypoint.as_deref(), Some("root-cmd"));
    }

    #[test]
    fn cyclic_error_message() {
        let cycle = [
            PackageId::new_named("root", "1.0.0".parse().unwrap()),
            PackageId::new_named("dep", "1.0.0".parse().unwrap()),
            PackageId::new_named("root", "1.0.0".parse().unwrap()),
        ];

        let message = print_cycle(&cycle);

        assert_eq!(message, "root@1.0.0 → dep@1.0.0 → root@1.0.0");
    }

    #[test]
    fn filesystem_with_one_package_and_no_fs_tables() {
        let root_id = PackageId::new_named("root", "1.0.0".parse().unwrap());
        let mut builder = RegistryBuilder::new();
        builder.register("root", "1.0.0");
        let mut dep_builder = builder.start_dependency_graph();
        dep_builder.insert(root_id.clone());
        let graph = dep_builder.graph(root_id.clone());

        let pkg = resolve_package(&graph).unwrap();

        assert!(pkg.filesystem.is_empty());
    }

    #[test]
    fn filesystem_with_one_package_and_one_fs_tables() {
        let root_id = PackageId::new_named("root", "1.0.0".parse().unwrap());
        let mut builder = RegistryBuilder::new();
        builder
            .register("root", "1.0.0")
            .with_fs_mapping("atom", "/publisher/lib", "/lib");
        let mut dep_builder = builder.start_dependency_graph();
        dep_builder.insert(root_id.clone());
        let graph = dep_builder.graph(root_id.clone());

        let pkg = resolve_package(&graph).unwrap();

        assert_eq!(
            pkg.filesystem,
            vec![ResolvedFileSystemMapping {
                mount_path: PathBuf::from("/lib"),
                original_path: Some("/publisher/lib".to_string()),
                volume_name: "atom".to_string(),
                package: builder.get(&root_id).package_id(),
            }]
        );
    }

    #[test]
    fn merge_fs_mappings_from_multiple_packages() {
        let root_id = PackageId::new_named("root", "1.0.0".parse().unwrap());
        let first_id = PackageId::new_named("first", "1.0.0".parse().unwrap());
        let second_id = PackageId::new_named("second", "1.0.0".parse().unwrap());

        let mut builder = RegistryBuilder::new();
        builder
            .register("root", "1.0.0")
            .with_dependency("first", "=1.0.0")
            .with_dependency("second", "=1.0.0")
            .with_fs_mapping("atom", "/root", "/root");
        builder.register("first", "1.0.0").with_fs_mapping(
            "atom",
            "/usr/local/lib/first",
            "/usr/local/lib/first",
        );
        builder.register("second", "1.0.0").with_fs_mapping(
            "atom",
            "/usr/local/lib/second",
            "/usr/local/lib/second",
        );
        let mut dep_builder = builder.start_dependency_graph();
        dep_builder
            .insert(root_id.clone())
            .with_dependency(&first_id)
            .with_dependency(&second_id);
        dep_builder.insert(first_id.clone());
        dep_builder.insert(second_id.clone());
        let graph = dep_builder.graph(root_id.clone());

        let pkg = resolve_package(&graph).unwrap();

        assert_eq!(
            pkg.filesystem,
            vec![
                ResolvedFileSystemMapping {
                    mount_path: PathBuf::from("/root"),
                    original_path: Some("/root".to_string()),
                    volume_name: "atom".to_string(),
                    package: builder.get(&root_id).package_id(),
                },
                ResolvedFileSystemMapping {
                    mount_path: PathBuf::from("/usr/local/lib/second"),
                    original_path: Some("/usr/local/lib/second".to_string()),
                    volume_name: "atom".to_string(),
                    package: builder.get(&second_id).package_id(),
                },
                ResolvedFileSystemMapping {
                    mount_path: PathBuf::from("/usr/local/lib/first"),
                    volume_name: "atom".to_string(),
                    original_path: Some("/usr/local/lib/first".to_string()),
                    package: builder.get(&first_id).package_id(),
                }
            ]
        );
    }

    #[test]
    fn use_fs_mapping_from_dependency() {
        let root_id = PackageId::new_named("root", "1.0.0".parse().unwrap());
        let dep_id = PackageId::new_named("dep", "1.0.0".parse().unwrap());
        let mut builder = RegistryBuilder::new();
        builder
            .register("root", "1.0.0")
            .with_dependency("dep", "=1.0.0")
            .with_fs_mapping_from_dependency("dep-volume", "/root", "/root", "dep");
        builder.register("dep", "1.0.0");
        let mut dep_builder = builder.start_dependency_graph();
        dep_builder.insert(root_id.clone()).with_dependency(&dep_id);
        dep_builder.insert(dep_id.clone());
        let graph = dep_builder.graph(root_id.clone());

        let pkg = resolve_package(&graph).unwrap();

        assert_eq!(
            pkg.filesystem,
            vec![ResolvedFileSystemMapping {
                mount_path: PathBuf::from("/root"),
                original_path: Some("/root".to_string()),
                volume_name: "dep-volume".to_string(),
                package: builder.get(&dep_id).package_id(),
            }]
        );
    }
}