diff options
Diffstat (limited to 'cli/npm/resolution')
| -rw-r--r-- | cli/npm/resolution/graph.rs | 2033 | ||||
| -rw-r--r-- | cli/npm/resolution/mod.rs | 676 | ||||
| -rw-r--r-- | cli/npm/resolution/snapshot.rs | 470 |
3 files changed, 3179 insertions, 0 deletions
diff --git a/cli/npm/resolution/graph.rs b/cli/npm/resolution/graph.rs new file mode 100644 index 000000000..497067925 --- /dev/null +++ b/cli/npm/resolution/graph.rs @@ -0,0 +1,2033 @@ +// Copyright 2018-2022 the Deno authors. All rights reserved. MIT license. + +use std::borrow::Cow; +use std::collections::BTreeMap; +use std::collections::BTreeSet; +use std::collections::HashMap; +use std::collections::VecDeque; +use std::sync::Arc; + +use deno_core::anyhow::bail; +use deno_core::anyhow::Context; +use deno_core::error::AnyError; +use deno_core::futures; +use deno_core::parking_lot::Mutex; +use deno_core::parking_lot::MutexGuard; +use log::debug; + +use crate::npm::cache::should_sync_download; +use crate::npm::registry::NpmDependencyEntry; +use crate::npm::registry::NpmDependencyEntryKind; +use crate::npm::registry::NpmPackageInfo; +use crate::npm::registry::NpmPackageVersionInfo; +use crate::npm::semver::NpmVersion; +use crate::npm::semver::NpmVersionReq; +use crate::npm::NpmRegistryApi; + +use super::snapshot::NpmResolutionSnapshot; +use super::snapshot::SnapshotPackageCopyIndexResolver; +use super::NpmPackageId; +use super::NpmPackageReq; +use super::NpmResolutionPackage; +use super::NpmVersionMatcher; + +/// A memory efficient path of visited name and versions in the graph +/// which is used to detect cycles. +/// +/// note(dsherret): although this is definitely more memory efficient +/// than a HashSet, I haven't done any tests about whether this is +/// faster in practice. +#[derive(Default, Clone)] +struct VisitedVersionsPath { + previous_node: Option<Arc<VisitedVersionsPath>>, + visited_version_key: String, +} + +impl VisitedVersionsPath { + pub fn new(id: &NpmPackageId) -> Arc<Self> { + Arc::new(Self { + previous_node: None, + visited_version_key: Self::id_to_key(id), + }) + } + + pub fn with_parent( + self: &Arc<VisitedVersionsPath>, + parent: &NodeParent, + ) -> Option<Arc<Self>> { + match parent { + NodeParent::Node(id) => self.with_id(id), + NodeParent::Req => Some(self.clone()), + } + } + + pub fn with_id( + self: &Arc<VisitedVersionsPath>, + id: &NpmPackageId, + ) -> Option<Arc<Self>> { + if self.has_visited(id) { + None + } else { + Some(Arc::new(Self { + previous_node: Some(self.clone()), + visited_version_key: Self::id_to_key(id), + })) + } + } + + pub fn has_visited(self: &Arc<Self>, id: &NpmPackageId) -> bool { + let mut maybe_next_node = Some(self); + let key = Self::id_to_key(id); + while let Some(next_node) = maybe_next_node { + if next_node.visited_version_key == key { + return true; + } + maybe_next_node = next_node.previous_node.as_ref(); + } + false + } + + fn id_to_key(id: &NpmPackageId) -> String { + format!("{}@{}", id.name, id.version) + } +} + +/// A memory efficient path of the visited specifiers in the tree. +#[derive(Default, Clone)] +struct GraphSpecifierPath { + previous_node: Option<Arc<GraphSpecifierPath>>, + specifier: String, +} + +impl GraphSpecifierPath { + pub fn new(specifier: String) -> Arc<Self> { + Arc::new(Self { + previous_node: None, + specifier, + }) + } + + pub fn with_specifier(self: &Arc<Self>, specifier: String) -> Arc<Self> { + Arc::new(Self { + previous_node: Some(self.clone()), + specifier, + }) + } + + pub fn pop(&self) -> Option<&Arc<Self>> { + self.previous_node.as_ref() + } +} + +#[derive(Debug, Clone, PartialEq, Eq, Hash, Ord, PartialOrd)] +enum NodeParent { + /// These are top of the graph npm package requirements + /// as specified in Deno code. + Req, + /// A reference to another node, which is a resolved package. + Node(NpmPackageId), +} + +/// A resolved package in the resolution graph. +#[derive(Debug)] +struct Node { + pub id: NpmPackageId, + /// If the node was forgotten due to having no parents. + pub forgotten: bool, + // Use BTreeMap and BTreeSet in order to create determinism + // when going up and down the tree + pub parents: BTreeMap<String, BTreeSet<NodeParent>>, + pub children: BTreeMap<String, NpmPackageId>, + pub deps: Arc<Vec<NpmDependencyEntry>>, +} + +impl Node { + pub fn add_parent(&mut self, specifier: String, parent: NodeParent) { + self.parents.entry(specifier).or_default().insert(parent); + } + + pub fn remove_parent(&mut self, specifier: &str, parent: &NodeParent) { + if let Some(parents) = self.parents.get_mut(specifier) { + parents.remove(parent); + if parents.is_empty() { + self.parents.remove(specifier); + } + } + } +} + +#[derive(Debug, Default)] +pub struct Graph { + package_reqs: HashMap<String, NpmPackageId>, + packages_by_name: HashMap<String, Vec<NpmPackageId>>, + // Ideally this value would be Rc<RefCell<Node>>, but we need to use a Mutex + // because the lsp requires Send and this code is executed in the lsp. + // Would be nice if the lsp wasn't Send. + packages: HashMap<NpmPackageId, Arc<Mutex<Node>>>, + // This will be set when creating from a snapshot, then + // inform the final snapshot creation. + packages_to_copy_index: HashMap<NpmPackageId, usize>, +} + +impl Graph { + pub fn from_snapshot(snapshot: NpmResolutionSnapshot) -> Self { + fn fill_for_id( + graph: &mut Graph, + id: &NpmPackageId, + packages: &HashMap<NpmPackageId, NpmResolutionPackage>, + ) -> Arc<Mutex<Node>> { + let resolution = packages.get(id).unwrap(); + let (created, node) = graph.get_or_create_for_id(id); + if created { + for (name, child_id) in &resolution.dependencies { + let child_node = fill_for_id(graph, child_id, packages); + graph.set_child_parent_node(name, &child_node, id); + } + } + node + } + + let mut graph = Self { + // Note: It might be more correct to store the copy index + // from past resolutions with the node somehow, but maybe not. + packages_to_copy_index: snapshot + .packages + .iter() + .map(|(id, p)| (id.clone(), p.copy_index)) + .collect(), + ..Default::default() + }; + for (package_req, id) in &snapshot.package_reqs { + let node = fill_for_id(&mut graph, id, &snapshot.packages); + let package_req_text = package_req.to_string(); + (*node) + .lock() + .add_parent(package_req_text.clone(), NodeParent::Req); + graph.package_reqs.insert(package_req_text, id.clone()); + } + graph + } + + pub fn has_package_req(&self, req: &NpmPackageReq) -> bool { + self.package_reqs.contains_key(&req.to_string()) + } + + fn get_or_create_for_id( + &mut self, + id: &NpmPackageId, + ) -> (bool, Arc<Mutex<Node>>) { + if let Some(node) = self.packages.get(id) { + (false, node.clone()) + } else { + let node = Arc::new(Mutex::new(Node { + id: id.clone(), + forgotten: false, + parents: Default::default(), + children: Default::default(), + deps: Default::default(), + })); + self + .packages_by_name + .entry(id.name.clone()) + .or_default() + .push(id.clone()); + self.packages.insert(id.clone(), node.clone()); + (true, node) + } + } + + fn borrow_node(&self, id: &NpmPackageId) -> MutexGuard<Node> { + (**self.packages.get(id).unwrap_or_else(|| { + panic!("could not find id {} in the tree", id.as_serialized()) + })) + .lock() + } + + fn forget_orphan(&mut self, node_id: &NpmPackageId) { + if let Some(node) = self.packages.remove(node_id) { + let mut node = (*node).lock(); + node.forgotten = true; + assert_eq!(node.parents.len(), 0); + + // Remove the id from the list of packages by name. + let packages_with_name = + self.packages_by_name.get_mut(&node.id.name).unwrap(); + let remove_index = packages_with_name + .iter() + .position(|id| id == &node.id) + .unwrap(); + packages_with_name.remove(remove_index); + + let parent = NodeParent::Node(node.id.clone()); + for (specifier, child_id) in &node.children { + let mut child = self.borrow_node(child_id); + child.remove_parent(specifier, &parent); + if child.parents.is_empty() { + drop(child); // stop borrowing from self + self.forget_orphan(child_id); + } + } + } + } + + fn set_child_parent( + &mut self, + specifier: &str, + child: &Mutex<Node>, + parent: &NodeParent, + ) { + match parent { + NodeParent::Node(parent_id) => { + self.set_child_parent_node(specifier, child, parent_id); + } + NodeParent::Req => { + let mut node = (*child).lock(); + node.add_parent(specifier.to_string(), parent.clone()); + self + .package_reqs + .insert(specifier.to_string(), node.id.clone()); + } + } + } + + fn set_child_parent_node( + &mut self, + specifier: &str, + child: &Mutex<Node>, + parent_id: &NpmPackageId, + ) { + let mut child = (*child).lock(); + let mut parent = (**self.packages.get(parent_id).unwrap_or_else(|| { + panic!( + "could not find {} in list of packages when setting child {}", + parent_id.as_serialized(), + child.id.as_serialized() + ) + })) + .lock(); + assert_ne!(parent.id, child.id); + parent + .children + .insert(specifier.to_string(), child.id.clone()); + child + .add_parent(specifier.to_string(), NodeParent::Node(parent.id.clone())); + } + + fn remove_child_parent( + &mut self, + specifier: &str, + child_id: &NpmPackageId, + parent: &NodeParent, + ) { + match parent { + NodeParent::Node(parent_id) => { + let mut node = self.borrow_node(parent_id); + if let Some(removed_child_id) = node.children.remove(specifier) { + assert_eq!(removed_child_id, *child_id); + } + } + NodeParent::Req => { + if let Some(removed_child_id) = self.package_reqs.remove(specifier) { + assert_eq!(removed_child_id, *child_id); + } + } + } + self.borrow_node(child_id).remove_parent(specifier, parent); + } + + pub async fn into_snapshot( + self, + api: &impl NpmRegistryApi, + ) -> Result<NpmResolutionSnapshot, AnyError> { + let mut copy_index_resolver = + SnapshotPackageCopyIndexResolver::from_map_with_capacity( + self.packages_to_copy_index, + self.packages.len(), + ); + + // Iterate through the packages vector in each packages_by_name in order + // to set the copy index as this will be deterministic rather than + // iterating over the hashmap below. + for packages in self.packages_by_name.values() { + if packages.len() > 1 { + for id in packages { + copy_index_resolver.resolve(id); + } + } + } + + let mut packages = HashMap::with_capacity(self.packages.len()); + for (id, node) in self.packages { + let dist = api + .package_version_info(&id.name, &id.version) + .await? + .unwrap() + .dist; + let node = node.lock(); + packages.insert( + id.clone(), + NpmResolutionPackage { + copy_index: copy_index_resolver.resolve(&id), + id, + dist, + dependencies: node + .children + .iter() + .map(|(key, value)| (key.clone(), value.clone())) + .collect(), + }, + ); + } + + Ok(NpmResolutionSnapshot { + package_reqs: self + .package_reqs + .into_iter() + .map(|(specifier, id)| { + (NpmPackageReq::from_str(&specifier).unwrap(), id) + }) + .collect(), + packages_by_name: self.packages_by_name, + packages, + }) + } +} + +pub struct GraphDependencyResolver<'a, TNpmRegistryApi: NpmRegistryApi> { + graph: &'a mut Graph, + api: &'a TNpmRegistryApi, + pending_unresolved_nodes: + VecDeque<(Arc<VisitedVersionsPath>, Arc<Mutex<Node>>)>, +} + +impl<'a, TNpmRegistryApi: NpmRegistryApi> + GraphDependencyResolver<'a, TNpmRegistryApi> +{ + pub fn new(graph: &'a mut Graph, api: &'a TNpmRegistryApi) -> Self { + Self { + graph, + api, + pending_unresolved_nodes: Default::default(), + } + } + + fn resolve_best_package_version_and_info( + &self, + name: &str, + version_matcher: &impl NpmVersionMatcher, + package_info: NpmPackageInfo, + ) -> Result<VersionAndInfo, AnyError> { + if let Some(version) = + self.resolve_best_package_version(name, version_matcher) + { + match package_info.versions.get(&version.to_string()) { + Some(version_info) => Ok(VersionAndInfo { + version, + info: version_info.clone(), + }), + None => { + bail!("could not find version '{}' for '{}'", version, name) + } + } + } else { + // get the information + get_resolved_package_version_and_info( + name, + version_matcher, + package_info, + None, + ) + } + } + + fn resolve_best_package_version( + &self, + name: &str, + version_matcher: &impl NpmVersionMatcher, + ) -> Option<NpmVersion> { + let mut maybe_best_version: Option<&NpmVersion> = None; + if let Some(ids) = self.graph.packages_by_name.get(name) { + for version in ids.iter().map(|id| &id.version) { + if version_matcher.matches(version) { + let is_best_version = maybe_best_version + .as_ref() + .map(|best_version| (*best_version).cmp(version).is_lt()) + .unwrap_or(true); + if is_best_version { + maybe_best_version = Some(version); + } + } + } + } + maybe_best_version.cloned() + } + + pub fn add_package_req( + &mut self, + package_req: &NpmPackageReq, + package_info: NpmPackageInfo, + ) -> Result<(), AnyError> { + let node = self.resolve_node_from_info( + &package_req.name, + package_req, + package_info, + )?; + self.graph.set_child_parent( + &package_req.to_string(), + &node, + &NodeParent::Req, + ); + self.try_add_pending_unresolved_node(None, &node); + Ok(()) + } + + fn analyze_dependency( + &mut self, + entry: &NpmDependencyEntry, + package_info: NpmPackageInfo, + parent_id: &NpmPackageId, + visited_versions: &Arc<VisitedVersionsPath>, + ) -> Result<(), AnyError> { + let node = self.resolve_node_from_info( + &entry.name, + match entry.kind { + NpmDependencyEntryKind::Dep => &entry.version_req, + // when resolving a peer dependency as a dependency, it should + // use the "dependencies" entry version requirement if it exists + NpmDependencyEntryKind::Peer | NpmDependencyEntryKind::OptionalPeer => { + entry + .peer_dep_version_req + .as_ref() + .unwrap_or(&entry.version_req) + } + }, + package_info, + )?; + self.graph.set_child_parent( + &entry.bare_specifier, + &node, + &NodeParent::Node(parent_id.clone()), + ); + self.try_add_pending_unresolved_node(Some(visited_versions), &node); + Ok(()) + } + + fn try_add_pending_unresolved_node( + &mut self, + maybe_previous_visited_versions: Option<&Arc<VisitedVersionsPath>>, + node: &Arc<Mutex<Node>>, + ) { + let node_id = node.lock().id.clone(); + let visited_versions = match maybe_previous_visited_versions { + Some(previous_visited_versions) => { + match previous_visited_versions.with_id(&node_id) { + Some(visited_versions) => visited_versions, + None => return, // circular, don't visit this node + } + } + None => VisitedVersionsPath::new(&node_id), + }; + self + .pending_unresolved_nodes + .push_back((visited_versions, node.clone())); + } + + fn resolve_node_from_info( + &mut self, + name: &str, + version_matcher: &impl NpmVersionMatcher, + package_info: NpmPackageInfo, + ) -> Result<Arc<Mutex<Node>>, AnyError> { + let version_and_info = self.resolve_best_package_version_and_info( + name, + version_matcher, + package_info, + )?; + let id = NpmPackageId { + name: name.to_string(), + version: version_and_info.version.clone(), + peer_dependencies: Vec::new(), + }; + debug!( + "Resolved {}@{} to {}", + name, + version_matcher.version_text(), + id.as_serialized() + ); + let (created, node) = self.graph.get_or_create_for_id(&id); + if created { + let mut node = (*node).lock(); + let mut deps = version_and_info + .info + .dependencies_as_entries() + .with_context(|| format!("npm package: {}", id.display()))?; + // Ensure name alphabetical and then version descending + // so these are resolved in that order + deps.sort(); + node.deps = Arc::new(deps); + } + + Ok(node) + } + + pub async fn resolve_pending(&mut self) -> Result<(), AnyError> { + while !self.pending_unresolved_nodes.is_empty() { + // now go down through the dependencies by tree depth + while let Some((visited_versions, parent_node)) = + self.pending_unresolved_nodes.pop_front() + { + let (mut parent_id, deps) = { + let parent_node = parent_node.lock(); + if parent_node.forgotten { + // todo(dsherret): we should try to reproduce this scenario and write a test + continue; + } + (parent_node.id.clone(), parent_node.deps.clone()) + }; + + // cache all the dependencies' registry infos in parallel if should + if !should_sync_download() { + let handles = deps + .iter() + .map(|dep| { + let name = dep.name.clone(); + let api = self.api.clone(); + tokio::task::spawn(async move { + // it's ok to call this without storing the result, because + // NpmRegistryApi will cache the package info in memory + api.package_info(&name).await + }) + }) + .collect::<Vec<_>>(); + let results = futures::future::join_all(handles).await; + for result in results { + result??; // surface the first error + } + } + + // resolve the dependencies + for dep in deps.iter() { + let package_info = self.api.package_info(&dep.name).await?; + + match dep.kind { + NpmDependencyEntryKind::Dep => { + self.analyze_dependency( + dep, + package_info, + &parent_id, + &visited_versions, + )?; + } + NpmDependencyEntryKind::Peer + | NpmDependencyEntryKind::OptionalPeer => { + let maybe_new_parent_id = self.resolve_peer_dep( + &dep.bare_specifier, + &parent_id, + dep, + package_info, + &visited_versions, + )?; + if let Some(new_parent_id) = maybe_new_parent_id { + assert_eq!( + (&new_parent_id.name, &new_parent_id.version), + (&parent_id.name, &parent_id.version) + ); + parent_id = new_parent_id; + } + } + } + } + } + } + Ok(()) + } + + fn resolve_peer_dep( + &mut self, + specifier: &str, + parent_id: &NpmPackageId, + peer_dep: &NpmDependencyEntry, + peer_package_info: NpmPackageInfo, + visited_ancestor_versions: &Arc<VisitedVersionsPath>, + ) -> Result<Option<NpmPackageId>, AnyError> { + fn find_matching_child<'a>( + peer_dep: &NpmDependencyEntry, + children: impl Iterator<Item = &'a NpmPackageId>, + ) -> Option<NpmPackageId> { + for child_id in children { + if child_id.name == peer_dep.name + && peer_dep.version_req.satisfies(&child_id.version) + { + return Some(child_id.clone()); + } + } + None + } + + // Peer dependencies are resolved based on its ancestors' siblings. + // If not found, then it resolves based on the version requirement if non-optional. + let mut pending_ancestors = VecDeque::new(); // go up the tree by depth + let path = GraphSpecifierPath::new(specifier.to_string()); + let visited_versions = VisitedVersionsPath::new(parent_id); + + // skip over the current node + for (specifier, grand_parents) in + self.graph.borrow_node(parent_id).parents.clone() + { + let path = path.with_specifier(specifier); + for grand_parent in grand_parents { + if let Some(visited_versions) = + visited_versions.with_parent(&grand_parent) + { + pending_ancestors.push_back(( + grand_parent, + path.clone(), + visited_versions, + )); + } + } + } + + while let Some((ancestor, path, visited_versions)) = + pending_ancestors.pop_front() + { + match &ancestor { + NodeParent::Node(ancestor_node_id) => { + let maybe_peer_dep_id = if ancestor_node_id.name == peer_dep.name + && peer_dep.version_req.satisfies(&ancestor_node_id.version) + { + Some(ancestor_node_id.clone()) + } else { + let ancestor = self.graph.borrow_node(ancestor_node_id); + for (specifier, parents) in &ancestor.parents { + let new_path = path.with_specifier(specifier.clone()); + for parent in parents { + if let Some(visited_versions) = + visited_versions.with_parent(parent) + { + pending_ancestors.push_back(( + parent.clone(), + new_path.clone(), + visited_versions, + )); + } + } + } + find_matching_child(peer_dep, ancestor.children.values()) + }; + if let Some(peer_dep_id) = maybe_peer_dep_id { + let parents = + self.graph.borrow_node(ancestor_node_id).parents.clone(); + return Ok(Some(self.set_new_peer_dep( + parents, + ancestor_node_id, + &peer_dep_id, + &path, + visited_ancestor_versions, + ))); + } + } + NodeParent::Req => { + // in this case, the parent is the root so the children are all the package requirements + if let Some(child_id) = + find_matching_child(peer_dep, self.graph.package_reqs.values()) + { + let specifier = path.specifier.to_string(); + let path = path.pop().unwrap(); // go back down one level from the package requirement + let old_id = + self.graph.package_reqs.get(&specifier).unwrap().clone(); + return Ok(Some(self.set_new_peer_dep( + BTreeMap::from([(specifier, BTreeSet::from([NodeParent::Req]))]), + &old_id, + &child_id, + path, + visited_ancestor_versions, + ))); + } + } + } + } + + // We didn't find anything by searching the ancestor siblings, so we need + // to resolve based on the package info and will treat this just like any + // other dependency when not optional + if !peer_dep.kind.is_optional() { + self.analyze_dependency( + peer_dep, + peer_package_info, + parent_id, + visited_ancestor_versions, + )?; + } + + Ok(None) + } + + fn set_new_peer_dep( + &mut self, + previous_parents: BTreeMap<String, BTreeSet<NodeParent>>, + node_id: &NpmPackageId, + peer_dep_id: &NpmPackageId, + path: &Arc<GraphSpecifierPath>, + visited_ancestor_versions: &Arc<VisitedVersionsPath>, + ) -> NpmPackageId { + let mut peer_dep_id = Cow::Borrowed(peer_dep_id); + let old_id = node_id; + let (new_id, old_node_children) = + if old_id.peer_dependencies.contains(&peer_dep_id) { + // the parent has already resolved to using this peer dependency + // via some other path, so we don't need to update its ids, + // but instead only make a link to it + ( + old_id.clone(), + self.graph.borrow_node(old_id).children.clone(), + ) + } else { + let mut new_id = old_id.clone(); + new_id.peer_dependencies.push(peer_dep_id.as_ref().clone()); + + // this will happen for circular dependencies + if *old_id == *peer_dep_id { + peer_dep_id = Cow::Owned(new_id.clone()); + } + + // remove the previous parents from the old node + let old_node_children = { + for (specifier, parents) in &previous_parents { + for parent in parents { + self.graph.remove_child_parent(specifier, old_id, parent); + } + } + let old_node = self.graph.borrow_node(old_id); + old_node.children.clone() + }; + + let (_, new_node) = self.graph.get_or_create_for_id(&new_id); + + // update the previous parent to point to the new node + // and this node to point at those parents + for (specifier, parents) in previous_parents { + for parent in parents { + self.graph.set_child_parent(&specifier, &new_node, &parent); + } + } + + // now add the previous children to this node + let new_id_as_parent = NodeParent::Node(new_id.clone()); + for (specifier, child_id) in &old_node_children { + let child = self.graph.packages.get(child_id).unwrap().clone(); + self + .graph + .set_child_parent(specifier, &child, &new_id_as_parent); + } + (new_id, old_node_children) + }; + + // this is the parent id found at the bottom of the path + let mut bottom_parent_id = new_id.clone(); + + // continue going down the path + let next_specifier = &path.specifier; + if let Some(path) = path.pop() { + let next_node_id = old_node_children.get(next_specifier).unwrap(); + bottom_parent_id = self.set_new_peer_dep( + BTreeMap::from([( + next_specifier.to_string(), + BTreeSet::from([NodeParent::Node(new_id.clone())]), + )]), + next_node_id, + &peer_dep_id, + path, + visited_ancestor_versions, + ); + } else { + // this means we're at the peer dependency now + debug!( + "Resolved peer dependency for {} in {} to {}", + next_specifier, + &new_id.as_serialized(), + &peer_dep_id.as_serialized(), + ); + assert!(!old_node_children.contains_key(next_specifier)); + let node = self.graph.get_or_create_for_id(&peer_dep_id).1; + self.try_add_pending_unresolved_node( + Some(visited_ancestor_versions), + &node, + ); + self + .graph + .set_child_parent_node(next_specifier, &node, &new_id); + } + + // forget the old node at this point if it has no parents + if new_id != *old_id { + let old_node = self.graph.borrow_node(old_id); + if old_node.parents.is_empty() { + drop(old_node); // stop borrowing + self.graph.forget_orphan(old_id); + } + } + + bottom_parent_id + } +} + +#[derive(Clone)] +struct VersionAndInfo { + version: NpmVersion, + info: NpmPackageVersionInfo, +} + +fn get_resolved_package_version_and_info( + pkg_name: &str, + version_matcher: &impl NpmVersionMatcher, + info: NpmPackageInfo, + parent: Option<&NpmPackageId>, +) -> Result<VersionAndInfo, AnyError> { + let mut maybe_best_version: Option<VersionAndInfo> = None; + if let Some(tag) = version_matcher.tag() { + // For when someone just specifies @types/node, we want to pull in a + // "known good" version of @types/node that works well with Deno and + // not necessarily the latest version. For example, we might only be + // compatible with Node vX, but then Node vY is published so we wouldn't + // want to pull that in. + // Note: If the user doesn't want this behavior, then they can specify an + // explicit version. + if tag == "latest" && pkg_name == "@types/node" { + return get_resolved_package_version_and_info( + pkg_name, + &NpmVersionReq::parse("18.0.0 - 18.8.2").unwrap(), + info, + parent, + ); + } + + if let Some(version) = info.dist_tags.get(tag) { + match info.versions.get(version) { + Some(info) => { + return Ok(VersionAndInfo { + version: NpmVersion::parse(version)?, + info: info.clone(), + }); + } + None => { + bail!( + "Could not find version '{}' referenced in dist-tag '{}'.", + version, + tag, + ) + } + } + } else { + bail!("Could not find dist-tag '{}'.", tag) + } + } else { + for (_, version_info) in info.versions.into_iter() { + let version = NpmVersion::parse(&version_info.version)?; + if version_matcher.matches(&version) { + let is_best_version = maybe_best_version + .as_ref() + .map(|best_version| best_version.version.cmp(&version).is_lt()) + .unwrap_or(true); + if is_best_version { + maybe_best_version = Some(VersionAndInfo { + version, + info: version_info, + }); + } + } + } + } + + match maybe_best_version { + Some(v) => Ok(v), + // If the package isn't found, it likely means that the user needs to use + // `--reload` to get the latest npm package information. Although it seems + // like we could make this smart by fetching the latest information for + // this package here, we really need a full restart. There could be very + // interesting bugs that occur if this package's version was resolved by + // something previous using the old information, then now being smart here + // causes a new fetch of the package information, meaning this time the + // previous resolution of this package's version resolved to an older + // version, but next time to a different version because it has new information. + None => bail!( + concat!( + "Could not find npm package '{}' matching {}{}. ", + "Try retrieving the latest npm package information by running with --reload", + ), + pkg_name, + version_matcher.version_text(), + match parent { + Some(id) => format!(" as specified in {}", id.display()), + None => String::new(), + } + ), + } +} + +#[cfg(test)] +mod test { + use pretty_assertions::assert_eq; + + use crate::npm::registry::TestNpmRegistryApi; + use crate::npm::NpmPackageReference; + + use super::*; + + #[test] + fn test_get_resolved_package_version_and_info() { + // dist tag where version doesn't exist + let package_ref = NpmPackageReference::from_str("npm:test").unwrap(); + let result = get_resolved_package_version_and_info( + "test", + &package_ref.req, + NpmPackageInfo { + name: "test".to_string(), + versions: HashMap::new(), + dist_tags: HashMap::from([( + "latest".to_string(), + "1.0.0-alpha".to_string(), + )]), + }, + None, + ); + assert_eq!( + result.err().unwrap().to_string(), + "Could not find version '1.0.0-alpha' referenced in dist-tag 'latest'." + ); + + // dist tag where version is a pre-release + let package_ref = NpmPackageReference::from_str("npm:test").unwrap(); + let result = get_resolved_package_version_and_info( + "test", + &package_ref.req, + NpmPackageInfo { + name: "test".to_string(), + versions: HashMap::from([ + ("0.1.0".to_string(), NpmPackageVersionInfo::default()), + ( + "1.0.0-alpha".to_string(), + NpmPackageVersionInfo { + version: "0.1.0-alpha".to_string(), + ..Default::default() + }, + ), + ]), + dist_tags: HashMap::from([( + "latest".to_string(), + "1.0.0-alpha".to_string(), + )]), + }, + None, + ); + assert_eq!(result.unwrap().version.to_string(), "1.0.0-alpha"); + } + + #[tokio::test] + async fn resolve_deps_no_peer() { + let api = TestNpmRegistryApi::default(); + api.ensure_package_version("package-a", "1.0.0"); + api.ensure_package_version("package-b", "2.0.0"); + api.ensure_package_version("package-c", "0.1.0"); + api.ensure_package_version("package-c", "0.0.10"); + api.ensure_package_version("package-d", "3.2.1"); + api.ensure_package_version("package-d", "3.2.0"); + api.add_dependency(("package-a", "1.0.0"), ("package-b", "^2")); + api.add_dependency(("package-a", "1.0.0"), ("package-c", "^0.1")); + api.add_dependency(("package-c", "0.1.0"), ("package-d", "*")); + + let (packages, package_reqs) = + run_resolver_and_get_output(api, vec!["npm:package-a@1"]).await; + assert_eq!( + packages, + vec![ + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-a@1.0.0").unwrap(), + copy_index: 0, + dependencies: HashMap::from([ + ( + "package-b".to_string(), + NpmPackageId::from_serialized("package-b@2.0.0").unwrap(), + ), + ( + "package-c".to_string(), + NpmPackageId::from_serialized("package-c@0.1.0").unwrap(), + ), + ]), + dist: Default::default(), + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-b@2.0.0").unwrap(), + copy_index: 0, + dist: Default::default(), + dependencies: Default::default(), + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-c@0.1.0").unwrap(), + copy_index: 0, + dist: Default::default(), + dependencies: HashMap::from([( + "package-d".to_string(), + NpmPackageId::from_serialized("package-d@3.2.1").unwrap(), + )]) + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-d@3.2.1").unwrap(), + copy_index: 0, + dist: Default::default(), + dependencies: Default::default(), + }, + ] + ); + assert_eq!( + package_reqs, + vec![("package-a@1".to_string(), "package-a@1.0.0".to_string())] + ); + } + + #[tokio::test] + async fn resolve_deps_circular() { + let api = TestNpmRegistryApi::default(); + api.ensure_package_version("package-a", "1.0.0"); + api.ensure_package_version("package-b", "2.0.0"); + api.add_dependency(("package-a", "1.0.0"), ("package-b", "*")); + api.add_dependency(("package-b", "2.0.0"), ("package-a", "1")); + + let (packages, package_reqs) = + run_resolver_and_get_output(api, vec!["npm:package-a@1.0"]).await; + assert_eq!( + packages, + vec![ + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-a@1.0.0").unwrap(), + copy_index: 0, + dependencies: HashMap::from([( + "package-b".to_string(), + NpmPackageId::from_serialized("package-b@2.0.0").unwrap(), + )]), + dist: Default::default(), + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-b@2.0.0").unwrap(), + copy_index: 0, + dependencies: HashMap::from([( + "package-a".to_string(), + NpmPackageId::from_serialized("package-a@1.0.0").unwrap(), + )]), + dist: Default::default(), + }, + ] + ); + assert_eq!( + package_reqs, + vec![("package-a@1.0".to_string(), "package-a@1.0.0".to_string())] + ); + } + + #[tokio::test] + async fn resolve_with_peer_deps_top_tree() { + let api = TestNpmRegistryApi::default(); + api.ensure_package_version("package-a", "1.0.0"); + api.ensure_package_version("package-b", "2.0.0"); + api.ensure_package_version("package-c", "3.0.0"); + api.ensure_package_version("package-peer", "4.0.0"); + api.ensure_package_version("package-peer", "4.1.0"); + api.add_dependency(("package-a", "1.0.0"), ("package-b", "^2")); + api.add_dependency(("package-a", "1.0.0"), ("package-c", "^3")); + api.add_peer_dependency(("package-b", "2.0.0"), ("package-peer", "4")); + api.add_peer_dependency(("package-c", "3.0.0"), ("package-peer", "*")); + + let (packages, package_reqs) = run_resolver_and_get_output( + api, + // the peer dependency is specified here at the top of the tree + // so it should resolve to 4.0.0 instead of 4.1.0 + vec!["npm:package-a@1", "npm:package-peer@4.0.0"], + ) + .await; + assert_eq!( + packages, + vec![ + NpmResolutionPackage { + id: NpmPackageId::from_serialized( + "package-a@1.0.0_package-peer@4.0.0" + ) + .unwrap(), + copy_index: 0, + dependencies: HashMap::from([ + ( + "package-b".to_string(), + NpmPackageId::from_serialized( + "package-b@2.0.0_package-peer@4.0.0" + ) + .unwrap(), + ), + ( + "package-c".to_string(), + NpmPackageId::from_serialized( + "package-c@3.0.0_package-peer@4.0.0" + ) + .unwrap(), + ), + ]), + dist: Default::default(), + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized( + "package-b@2.0.0_package-peer@4.0.0" + ) + .unwrap(), + copy_index: 0, + dist: Default::default(), + dependencies: HashMap::from([( + "package-peer".to_string(), + NpmPackageId::from_serialized("package-peer@4.0.0").unwrap(), + )]) + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized( + "package-c@3.0.0_package-peer@4.0.0" + ) + .unwrap(), + copy_index: 0, + dist: Default::default(), + dependencies: HashMap::from([( + "package-peer".to_string(), + NpmPackageId::from_serialized("package-peer@4.0.0").unwrap(), + )]) + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-peer@4.0.0").unwrap(), + copy_index: 0, + dist: Default::default(), + dependencies: Default::default(), + }, + ] + ); + assert_eq!( + package_reqs, + vec![ + ( + "package-a@1".to_string(), + "package-a@1.0.0_package-peer@4.0.0".to_string() + ), + ( + "package-peer@4.0.0".to_string(), + "package-peer@4.0.0".to_string() + ) + ] + ); + } + + #[tokio::test] + async fn resolve_with_peer_deps_ancestor_sibling_not_top_tree() { + let api = TestNpmRegistryApi::default(); + api.ensure_package_version("package-0", "1.1.1"); + api.ensure_package_version("package-a", "1.0.0"); + api.ensure_package_version("package-b", "2.0.0"); + api.ensure_package_version("package-c", "3.0.0"); + api.ensure_package_version("package-peer", "4.0.0"); + api.ensure_package_version("package-peer", "4.1.0"); + api.add_dependency(("package-0", "1.1.1"), ("package-a", "1")); + api.add_dependency(("package-a", "1.0.0"), ("package-b", "^2")); + api.add_dependency(("package-a", "1.0.0"), ("package-c", "^3")); + // the peer dependency is specified here as a sibling of "a" and "b" + // so it should resolve to 4.0.0 instead of 4.1.0 + api.add_dependency(("package-a", "1.0.0"), ("package-peer", "4.0.0")); + api.add_peer_dependency(("package-b", "2.0.0"), ("package-peer", "4")); + api.add_peer_dependency(("package-c", "3.0.0"), ("package-peer", "*")); + + let (packages, package_reqs) = + run_resolver_and_get_output(api, vec!["npm:package-0@1.1.1"]).await; + assert_eq!( + packages, + vec![ + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-0@1.1.1").unwrap(), + copy_index: 0, + dependencies: HashMap::from([( + "package-a".to_string(), + NpmPackageId::from_serialized("package-a@1.0.0_package-peer@4.0.0") + .unwrap(), + ),]), + dist: Default::default(), + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized( + "package-a@1.0.0_package-peer@4.0.0" + ) + .unwrap(), + copy_index: 0, + dependencies: HashMap::from([ + ( + "package-b".to_string(), + NpmPackageId::from_serialized( + "package-b@2.0.0_package-peer@4.0.0" + ) + .unwrap(), + ), + ( + "package-c".to_string(), + NpmPackageId::from_serialized( + "package-c@3.0.0_package-peer@4.0.0" + ) + .unwrap(), + ), + ( + "package-peer".to_string(), + NpmPackageId::from_serialized("package-peer@4.0.0").unwrap(), + ), + ]), + dist: Default::default(), + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized( + "package-b@2.0.0_package-peer@4.0.0" + ) + .unwrap(), + copy_index: 0, + dist: Default::default(), + dependencies: HashMap::from([( + "package-peer".to_string(), + NpmPackageId::from_serialized("package-peer@4.0.0").unwrap(), + )]) + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized( + "package-c@3.0.0_package-peer@4.0.0" + ) + .unwrap(), + copy_index: 0, + dist: Default::default(), + dependencies: HashMap::from([( + "package-peer".to_string(), + NpmPackageId::from_serialized("package-peer@4.0.0").unwrap(), + )]) + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-peer@4.0.0").unwrap(), + copy_index: 0, + dist: Default::default(), + dependencies: Default::default(), + }, + ] + ); + assert_eq!( + package_reqs, + vec![("package-0@1.1.1".to_string(), "package-0@1.1.1".to_string())] + ); + } + + #[tokio::test] + async fn resolve_with_peer_deps_auto_resolved() { + // in this case, the peer dependency is not found in the tree + // so it's auto-resolved based on the registry + let api = TestNpmRegistryApi::default(); + api.ensure_package_version("package-a", "1.0.0"); + api.ensure_package_version("package-b", "2.0.0"); + api.ensure_package_version("package-c", "3.0.0"); + api.ensure_package_version("package-peer", "4.0.0"); + api.ensure_package_version("package-peer", "4.1.0"); + api.add_dependency(("package-a", "1.0.0"), ("package-b", "^2")); + api.add_dependency(("package-a", "1.0.0"), ("package-c", "^3")); + api.add_peer_dependency(("package-b", "2.0.0"), ("package-peer", "4")); + api.add_peer_dependency(("package-c", "3.0.0"), ("package-peer", "*")); + + let (packages, package_reqs) = + run_resolver_and_get_output(api, vec!["npm:package-a@1"]).await; + assert_eq!( + packages, + vec![ + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-a@1.0.0").unwrap(), + copy_index: 0, + dependencies: HashMap::from([ + ( + "package-b".to_string(), + NpmPackageId::from_serialized("package-b@2.0.0").unwrap(), + ), + ( + "package-c".to_string(), + NpmPackageId::from_serialized("package-c@3.0.0").unwrap(), + ), + ]), + dist: Default::default(), + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-b@2.0.0").unwrap(), + copy_index: 0, + dist: Default::default(), + dependencies: HashMap::from([( + "package-peer".to_string(), + NpmPackageId::from_serialized("package-peer@4.1.0").unwrap(), + )]) + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-c@3.0.0").unwrap(), + copy_index: 0, + dist: Default::default(), + dependencies: HashMap::from([( + "package-peer".to_string(), + NpmPackageId::from_serialized("package-peer@4.1.0").unwrap(), + )]) + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-peer@4.1.0").unwrap(), + copy_index: 0, + dist: Default::default(), + dependencies: Default::default(), + }, + ] + ); + assert_eq!( + package_reqs, + vec![("package-a@1".to_string(), "package-a@1.0.0".to_string())] + ); + } + + #[tokio::test] + async fn resolve_with_optional_peer_dep_not_resolved() { + // in this case, the peer dependency is not found in the tree + // so it's auto-resolved based on the registry + let api = TestNpmRegistryApi::default(); + api.ensure_package_version("package-a", "1.0.0"); + api.ensure_package_version("package-b", "2.0.0"); + api.ensure_package_version("package-c", "3.0.0"); + api.ensure_package_version("package-peer", "4.0.0"); + api.ensure_package_version("package-peer", "4.1.0"); + api.add_dependency(("package-a", "1.0.0"), ("package-b", "^2")); + api.add_dependency(("package-a", "1.0.0"), ("package-c", "^3")); + api.add_optional_peer_dependency( + ("package-b", "2.0.0"), + ("package-peer", "4"), + ); + api.add_optional_peer_dependency( + ("package-c", "3.0.0"), + ("package-peer", "*"), + ); + + let (packages, package_reqs) = + run_resolver_and_get_output(api, vec!["npm:package-a@1"]).await; + assert_eq!( + packages, + vec![ + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-a@1.0.0").unwrap(), + copy_index: 0, + dependencies: HashMap::from([ + ( + "package-b".to_string(), + NpmPackageId::from_serialized("package-b@2.0.0").unwrap(), + ), + ( + "package-c".to_string(), + NpmPackageId::from_serialized("package-c@3.0.0").unwrap(), + ), + ]), + dist: Default::default(), + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-b@2.0.0").unwrap(), + copy_index: 0, + dist: Default::default(), + dependencies: HashMap::new(), + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-c@3.0.0").unwrap(), + copy_index: 0, + dist: Default::default(), + dependencies: HashMap::new(), + }, + ] + ); + assert_eq!( + package_reqs, + vec![("package-a@1".to_string(), "package-a@1.0.0".to_string())] + ); + } + + #[tokio::test] + async fn resolve_with_optional_peer_found() { + let api = TestNpmRegistryApi::default(); + api.ensure_package_version("package-a", "1.0.0"); + api.ensure_package_version("package-b", "2.0.0"); + api.ensure_package_version("package-c", "3.0.0"); + api.ensure_package_version("package-peer", "4.0.0"); + api.ensure_package_version("package-peer", "4.1.0"); + api.add_dependency(("package-a", "1.0.0"), ("package-b", "^2")); + api.add_dependency(("package-a", "1.0.0"), ("package-c", "^3")); + api.add_optional_peer_dependency( + ("package-b", "2.0.0"), + ("package-peer", "4"), + ); + api.add_optional_peer_dependency( + ("package-c", "3.0.0"), + ("package-peer", "*"), + ); + + let (packages, package_reqs) = run_resolver_and_get_output( + api, + vec!["npm:package-a@1", "npm:package-peer@4.0.0"], + ) + .await; + assert_eq!( + packages, + vec![ + NpmResolutionPackage { + id: NpmPackageId::from_serialized( + "package-a@1.0.0_package-peer@4.0.0" + ) + .unwrap(), + copy_index: 0, + dependencies: HashMap::from([ + ( + "package-b".to_string(), + NpmPackageId::from_serialized( + "package-b@2.0.0_package-peer@4.0.0" + ) + .unwrap(), + ), + ( + "package-c".to_string(), + NpmPackageId::from_serialized( + "package-c@3.0.0_package-peer@4.0.0" + ) + .unwrap(), + ), + ]), + dist: Default::default(), + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized( + "package-b@2.0.0_package-peer@4.0.0" + ) + .unwrap(), + copy_index: 0, + dist: Default::default(), + dependencies: HashMap::from([( + "package-peer".to_string(), + NpmPackageId::from_serialized("package-peer@4.0.0").unwrap(), + )]) + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized( + "package-c@3.0.0_package-peer@4.0.0" + ) + .unwrap(), + copy_index: 0, + dist: Default::default(), + dependencies: HashMap::from([( + "package-peer".to_string(), + NpmPackageId::from_serialized("package-peer@4.0.0").unwrap(), + )]) + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-peer@4.0.0").unwrap(), + copy_index: 0, + dist: Default::default(), + dependencies: Default::default(), + }, + ] + ); + assert_eq!( + package_reqs, + vec![ + ( + "package-a@1".to_string(), + "package-a@1.0.0_package-peer@4.0.0".to_string() + ), + ( + "package-peer@4.0.0".to_string(), + "package-peer@4.0.0".to_string() + ) + ] + ); + } + + #[tokio::test] + async fn resolve_nested_peer_deps_auto_resolved() { + let api = TestNpmRegistryApi::default(); + api.ensure_package_version("package-0", "1.0.0"); + api.ensure_package_version("package-peer-a", "2.0.0"); + api.ensure_package_version("package-peer-b", "3.0.0"); + api.add_peer_dependency(("package-0", "1.0.0"), ("package-peer-a", "2")); + api.add_peer_dependency( + ("package-peer-a", "2.0.0"), + ("package-peer-b", "3"), + ); + + let (packages, package_reqs) = + run_resolver_and_get_output(api, vec!["npm:package-0@1.0"]).await; + assert_eq!( + packages, + vec![ + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-0@1.0.0").unwrap(), + copy_index: 0, + dependencies: HashMap::from([( + "package-peer-a".to_string(), + NpmPackageId::from_serialized("package-peer-a@2.0.0").unwrap(), + )]), + dist: Default::default(), + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-peer-a@2.0.0").unwrap(), + copy_index: 0, + dependencies: HashMap::from([( + "package-peer-b".to_string(), + NpmPackageId::from_serialized("package-peer-b@3.0.0").unwrap(), + )]), + dist: Default::default(), + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-peer-b@3.0.0").unwrap(), + copy_index: 0, + dependencies: HashMap::new(), + dist: Default::default(), + }, + ] + ); + assert_eq!( + package_reqs, + vec![("package-0@1.0".to_string(), "package-0@1.0.0".to_string())] + ); + } + + #[tokio::test] + async fn resolve_nested_peer_deps_ancestor_sibling_deps() { + let api = TestNpmRegistryApi::default(); + api.ensure_package_version("package-0", "1.0.0"); + api.ensure_package_version("package-peer-a", "2.0.0"); + api.ensure_package_version("package-peer-b", "3.0.0"); + api.add_dependency(("package-0", "1.0.0"), ("package-peer-b", "*")); + api.add_peer_dependency(("package-0", "1.0.0"), ("package-peer-a", "2")); + api.add_peer_dependency( + ("package-peer-a", "2.0.0"), + ("package-peer-b", "3"), + ); + + let (packages, package_reqs) = run_resolver_and_get_output( + api, + vec![ + "npm:package-0@1.0", + "npm:package-peer-a@2", + "npm:package-peer-b@3", + ], + ) + .await; + assert_eq!( + packages, + vec![ + NpmResolutionPackage { + id: NpmPackageId::from_serialized( + "package-0@1.0.0_package-peer-a@2.0.0_package-peer-b@3.0.0" + ) + .unwrap(), + copy_index: 0, + dependencies: HashMap::from([ + ( + "package-peer-a".to_string(), + NpmPackageId::from_serialized( + "package-peer-a@2.0.0_package-peer-b@3.0.0" + ) + .unwrap(), + ), + ( + "package-peer-b".to_string(), + NpmPackageId::from_serialized("package-peer-b@3.0.0").unwrap(), + ) + ]), + dist: Default::default(), + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized( + "package-peer-a@2.0.0_package-peer-b@3.0.0" + ) + .unwrap(), + copy_index: 0, + dependencies: HashMap::from([( + "package-peer-b".to_string(), + NpmPackageId::from_serialized("package-peer-b@3.0.0").unwrap(), + )]), + dist: Default::default(), + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-peer-b@3.0.0").unwrap(), + copy_index: 0, + dependencies: HashMap::new(), + dist: Default::default(), + }, + ] + ); + assert_eq!( + package_reqs, + vec![ + ( + "package-0@1.0".to_string(), + "package-0@1.0.0_package-peer-a@2.0.0_package-peer-b@3.0.0" + .to_string() + ), + ( + "package-peer-a@2".to_string(), + "package-peer-a@2.0.0_package-peer-b@3.0.0".to_string() + ), + ( + "package-peer-b@3".to_string(), + "package-peer-b@3.0.0".to_string() + ) + ] + ); + } + + #[tokio::test] + async fn resolve_with_peer_deps_multiple() { + let api = TestNpmRegistryApi::default(); + api.ensure_package_version("package-0", "1.1.1"); + api.ensure_package_version("package-a", "1.0.0"); + api.ensure_package_version("package-b", "2.0.0"); + api.ensure_package_version("package-c", "3.0.0"); + api.ensure_package_version("package-d", "3.5.0"); + api.ensure_package_version("package-e", "3.6.0"); + api.ensure_package_version("package-peer-a", "4.0.0"); + api.ensure_package_version("package-peer-a", "4.1.0"); + api.ensure_package_version("package-peer-b", "5.3.0"); + api.ensure_package_version("package-peer-b", "5.4.1"); + api.ensure_package_version("package-peer-c", "6.2.0"); + api.add_dependency(("package-0", "1.1.1"), ("package-a", "1")); + api.add_dependency(("package-a", "1.0.0"), ("package-b", "^2")); + api.add_dependency(("package-a", "1.0.0"), ("package-c", "^3")); + api.add_dependency(("package-a", "1.0.0"), ("package-d", "^3")); + api.add_dependency(("package-a", "1.0.0"), ("package-peer-a", "4.0.0")); + api.add_peer_dependency(("package-b", "2.0.0"), ("package-peer-a", "4")); + api.add_peer_dependency( + ("package-b", "2.0.0"), + ("package-peer-c", "=6.2.0"), + ); + api.add_peer_dependency(("package-c", "3.0.0"), ("package-peer-a", "*")); + api.add_peer_dependency( + ("package-peer-a", "4.0.0"), + ("package-peer-b", "^5.4"), // will be auto-resolved + ); + + let (packages, package_reqs) = run_resolver_and_get_output( + api, + vec!["npm:package-0@1.1.1", "npm:package-e@3"], + ) + .await; + assert_eq!( + packages, + vec![ + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-0@1.1.1").unwrap(), + copy_index: 0, + dependencies: HashMap::from([( + "package-a".to_string(), + NpmPackageId::from_serialized( + "package-a@1.0.0_package-peer-a@4.0.0" + ) + .unwrap(), + ),]), + dist: Default::default(), + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized( + "package-a@1.0.0_package-peer-a@4.0.0" + ) + .unwrap(), + copy_index: 0, + dependencies: HashMap::from([ + ( + "package-b".to_string(), + NpmPackageId::from_serialized( + "package-b@2.0.0_package-peer-a@4.0.0" + ) + .unwrap(), + ), + ( + "package-c".to_string(), + NpmPackageId::from_serialized( + "package-c@3.0.0_package-peer-a@4.0.0" + ) + .unwrap(), + ), + ( + "package-d".to_string(), + NpmPackageId::from_serialized("package-d@3.5.0").unwrap(), + ), + ( + "package-peer-a".to_string(), + NpmPackageId::from_serialized("package-peer-a@4.0.0").unwrap(), + ), + ]), + dist: Default::default(), + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized( + "package-b@2.0.0_package-peer-a@4.0.0" + ) + .unwrap(), + copy_index: 0, + dist: Default::default(), + dependencies: HashMap::from([ + ( + "package-peer-a".to_string(), + NpmPackageId::from_serialized("package-peer-a@4.0.0").unwrap(), + ), + ( + "package-peer-c".to_string(), + NpmPackageId::from_serialized("package-peer-c@6.2.0").unwrap(), + ) + ]) + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized( + "package-c@3.0.0_package-peer-a@4.0.0" + ) + .unwrap(), + copy_index: 0, + dist: Default::default(), + dependencies: HashMap::from([( + "package-peer-a".to_string(), + NpmPackageId::from_serialized("package-peer-a@4.0.0").unwrap(), + )]) + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-d@3.5.0").unwrap(), + copy_index: 0, + dependencies: HashMap::from([]), + dist: Default::default(), + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-e@3.6.0").unwrap(), + copy_index: 0, + dependencies: HashMap::from([]), + dist: Default::default(), + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-peer-a@4.0.0").unwrap(), + copy_index: 0, + dist: Default::default(), + dependencies: HashMap::from([( + "package-peer-b".to_string(), + NpmPackageId::from_serialized("package-peer-b@5.4.1").unwrap(), + )]) + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-peer-b@5.4.1").unwrap(), + copy_index: 0, + dist: Default::default(), + dependencies: Default::default(), + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-peer-c@6.2.0").unwrap(), + copy_index: 0, + dist: Default::default(), + dependencies: Default::default(), + }, + ] + ); + assert_eq!( + package_reqs, + vec![ + ("package-0@1.1.1".to_string(), "package-0@1.1.1".to_string()), + ("package-e@3".to_string(), "package-e@3.6.0".to_string()), + ] + ); + } + + #[tokio::test] + async fn resolve_peer_deps_circular() { + let api = TestNpmRegistryApi::default(); + api.ensure_package_version("package-a", "1.0.0"); + api.ensure_package_version("package-b", "2.0.0"); + api.add_dependency(("package-a", "1.0.0"), ("package-b", "*")); + api.add_peer_dependency(("package-b", "2.0.0"), ("package-a", "1")); + + let (packages, package_reqs) = + run_resolver_and_get_output(api, vec!["npm:package-a@1.0"]).await; + assert_eq!( + packages, + vec![ + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-a@1.0.0_package-a@1.0.0") + .unwrap(), + copy_index: 0, + dependencies: HashMap::from([( + "package-b".to_string(), + NpmPackageId::from_serialized( + "package-b@2.0.0_package-a@1.0.0__package-a@1.0.0" + ) + .unwrap(), + )]), + dist: Default::default(), + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized( + "package-b@2.0.0_package-a@1.0.0__package-a@1.0.0" + ) + .unwrap(), + copy_index: 0, + dependencies: HashMap::from([( + "package-a".to_string(), + NpmPackageId::from_serialized("package-a@1.0.0_package-a@1.0.0") + .unwrap(), + )]), + dist: Default::default(), + }, + ] + ); + assert_eq!( + package_reqs, + vec![( + "package-a@1.0".to_string(), + "package-a@1.0.0_package-a@1.0.0".to_string() + )] + ); + } + + #[tokio::test] + async fn resolve_peer_deps_multiple_copies() { + // repeat this a few times to have a higher probability of surfacing indeterminism + for _ in 0..3 { + let api = TestNpmRegistryApi::default(); + api.ensure_package_version("package-a", "1.0.0"); + api.ensure_package_version("package-b", "2.0.0"); + api.ensure_package_version("package-dep", "3.0.0"); + api.ensure_package_version("package-peer", "4.0.0"); + api.ensure_package_version("package-peer", "5.0.0"); + api.add_dependency(("package-a", "1.0.0"), ("package-dep", "*")); + api.add_dependency(("package-a", "1.0.0"), ("package-peer", "4")); + api.add_dependency(("package-b", "2.0.0"), ("package-dep", "*")); + api.add_dependency(("package-b", "2.0.0"), ("package-peer", "5")); + api.add_peer_dependency(("package-dep", "3.0.0"), ("package-peer", "*")); + + let (packages, package_reqs) = run_resolver_and_get_output( + api, + vec!["npm:package-a@1", "npm:package-b@2"], + ) + .await; + assert_eq!( + packages, + vec![ + NpmResolutionPackage { + id: NpmPackageId::from_serialized( + "package-a@1.0.0_package-peer@4.0.0" + ) + .unwrap(), + copy_index: 0, + dependencies: HashMap::from([ + ( + "package-dep".to_string(), + NpmPackageId::from_serialized( + "package-dep@3.0.0_package-peer@4.0.0" + ) + .unwrap(), + ), + ( + "package-peer".to_string(), + NpmPackageId::from_serialized("package-peer@4.0.0").unwrap(), + ), + ]), + dist: Default::default(), + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized( + "package-b@2.0.0_package-peer@5.0.0" + ) + .unwrap(), + copy_index: 0, + dependencies: HashMap::from([ + ( + "package-dep".to_string(), + NpmPackageId::from_serialized( + "package-dep@3.0.0_package-peer@5.0.0" + ) + .unwrap(), + ), + ( + "package-peer".to_string(), + NpmPackageId::from_serialized("package-peer@5.0.0").unwrap(), + ), + ]), + dist: Default::default(), + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized( + "package-dep@3.0.0_package-peer@4.0.0" + ) + .unwrap(), + copy_index: 0, + dependencies: HashMap::from([( + "package-peer".to_string(), + NpmPackageId::from_serialized("package-peer@4.0.0").unwrap(), + )]), + dist: Default::default(), + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized( + "package-dep@3.0.0_package-peer@5.0.0" + ) + .unwrap(), + copy_index: 1, + dependencies: HashMap::from([( + "package-peer".to_string(), + NpmPackageId::from_serialized("package-peer@5.0.0").unwrap(), + )]), + dist: Default::default(), + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-peer@4.0.0").unwrap(), + copy_index: 0, + dependencies: HashMap::new(), + dist: Default::default(), + }, + NpmResolutionPackage { + id: NpmPackageId::from_serialized("package-peer@5.0.0").unwrap(), + copy_index: 0, + dependencies: HashMap::new(), + dist: Default::default(), + }, + ] + ); + assert_eq!( + package_reqs, + vec![ + ( + "package-a@1".to_string(), + "package-a@1.0.0_package-peer@4.0.0".to_string() + ), + ( + "package-b@2".to_string(), + "package-b@2.0.0_package-peer@5.0.0".to_string() + ) + ] + ); + } + } + + async fn run_resolver_and_get_output( + api: TestNpmRegistryApi, + reqs: Vec<&str>, + ) -> (Vec<NpmResolutionPackage>, Vec<(String, String)>) { + let mut graph = Graph::default(); + let mut resolver = GraphDependencyResolver::new(&mut graph, &api); + + for req in reqs { + let req = NpmPackageReference::from_str(req).unwrap().req; + resolver + .add_package_req(&req, api.package_info(&req.name).await.unwrap()) + .unwrap(); + } + + resolver.resolve_pending().await.unwrap(); + let snapshot = graph.into_snapshot(&api).await.unwrap(); + let mut packages = snapshot.all_packages(); + packages.sort_by(|a, b| a.id.cmp(&b.id)); + let mut package_reqs = snapshot + .package_reqs + .into_iter() + .map(|(a, b)| (a.to_string(), b.as_serialized())) + .collect::<Vec<_>>(); + package_reqs.sort_by(|a, b| a.0.to_string().cmp(&b.0.to_string())); + (packages, package_reqs) + } +} diff --git a/cli/npm/resolution/mod.rs b/cli/npm/resolution/mod.rs new file mode 100644 index 000000000..934cfb59b --- /dev/null +++ b/cli/npm/resolution/mod.rs @@ -0,0 +1,676 @@ +// Copyright 2018-2022 the Deno authors. All rights reserved. MIT license. + +use std::collections::HashMap; +use std::collections::HashSet; + +use deno_ast::ModuleSpecifier; +use deno_core::anyhow::bail; +use deno_core::anyhow::Context; +use deno_core::error::generic_error; +use deno_core::error::AnyError; +use deno_core::futures; +use deno_core::parking_lot::RwLock; +use serde::Deserialize; +use serde::Serialize; + +use crate::lockfile::Lockfile; + +use self::graph::GraphDependencyResolver; +use self::snapshot::NpmPackagesPartitioned; + +use super::cache::should_sync_download; +use super::cache::NpmPackageCacheFolderId; +use super::registry::NpmPackageVersionDistInfo; +use super::registry::RealNpmRegistryApi; +use super::semver::NpmVersion; +use super::semver::SpecifierVersionReq; +use super::NpmRegistryApi; + +mod graph; +mod snapshot; + +use graph::Graph; +pub use snapshot::NpmResolutionSnapshot; + +/// The version matcher used for npm schemed urls is more strict than +/// the one used by npm packages and so we represent either via a trait. +pub trait NpmVersionMatcher { + fn tag(&self) -> Option<&str>; + fn matches(&self, version: &NpmVersion) -> bool; + fn version_text(&self) -> String; +} + +#[derive(Clone, Debug, Default, PartialEq, Eq)] +pub struct NpmPackageReference { + pub req: NpmPackageReq, + pub sub_path: Option<String>, +} + +impl NpmPackageReference { + pub fn from_specifier( + specifier: &ModuleSpecifier, + ) -> Result<NpmPackageReference, AnyError> { + Self::from_str(specifier.as_str()) + } + + pub fn from_str(specifier: &str) -> Result<NpmPackageReference, AnyError> { + let specifier = match specifier.strip_prefix("npm:") { + Some(s) => s, + None => { + bail!("Not an npm specifier: {}", specifier); + } + }; + let parts = specifier.split('/').collect::<Vec<_>>(); + let name_part_len = if specifier.starts_with('@') { 2 } else { 1 }; + if parts.len() < name_part_len { + return Err(generic_error(format!("Not a valid package: {}", specifier))); + } + let name_parts = &parts[0..name_part_len]; + let last_name_part = &name_parts[name_part_len - 1]; + let (name, version_req) = if let Some(at_index) = last_name_part.rfind('@') + { + let version = &last_name_part[at_index + 1..]; + let last_name_part = &last_name_part[..at_index]; + let version_req = SpecifierVersionReq::parse(version) + .with_context(|| "Invalid version requirement.")?; + let name = if name_part_len == 1 { + last_name_part.to_string() + } else { + format!("{}/{}", name_parts[0], last_name_part) + }; + (name, Some(version_req)) + } else { + (name_parts.join("/"), None) + }; + let sub_path = if parts.len() == name_parts.len() { + None + } else { + Some(parts[name_part_len..].join("/")) + }; + + if let Some(sub_path) = &sub_path { + if let Some(at_index) = sub_path.rfind('@') { + let (new_sub_path, version) = sub_path.split_at(at_index); + let msg = format!( + "Invalid package specifier 'npm:{}/{}'. Did you mean to write 'npm:{}{}/{}'?", + name, sub_path, name, version, new_sub_path + ); + return Err(generic_error(msg)); + } + } + + Ok(NpmPackageReference { + req: NpmPackageReq { name, version_req }, + sub_path, + }) + } +} + +impl std::fmt::Display for NpmPackageReference { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + if let Some(sub_path) = &self.sub_path { + write!(f, "npm:{}/{}", self.req, sub_path) + } else { + write!(f, "npm:{}", self.req) + } + } +} + +#[derive( + Clone, Debug, Default, PartialEq, Eq, Hash, Serialize, Deserialize, +)] +pub struct NpmPackageReq { + pub name: String, + pub version_req: Option<SpecifierVersionReq>, +} + +impl std::fmt::Display for NpmPackageReq { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + match &self.version_req { + Some(req) => write!(f, "{}@{}", self.name, req), + None => write!(f, "{}", self.name), + } + } +} + +impl NpmPackageReq { + pub fn from_str(text: &str) -> Result<Self, AnyError> { + // probably should do something more targetted in the future + let reference = NpmPackageReference::from_str(&format!("npm:{}", text))?; + Ok(reference.req) + } +} + +impl NpmVersionMatcher for NpmPackageReq { + fn tag(&self) -> Option<&str> { + match &self.version_req { + Some(version_req) => version_req.tag(), + None => Some("latest"), + } + } + + fn matches(&self, version: &NpmVersion) -> bool { + match self.version_req.as_ref() { + Some(req) => { + assert_eq!(self.tag(), None); + match req.range() { + Some(range) => range.satisfies(version), + None => false, + } + } + None => version.pre.is_empty(), + } + } + + fn version_text(&self) -> String { + self + .version_req + .as_ref() + .map(|v| format!("{}", v)) + .unwrap_or_else(|| "non-prerelease".to_string()) + } +} + +#[derive( + Debug, Clone, PartialOrd, Ord, PartialEq, Eq, Hash, Serialize, Deserialize, +)] +pub struct NpmPackageId { + pub name: String, + pub version: NpmVersion, + pub peer_dependencies: Vec<NpmPackageId>, +} + +impl NpmPackageId { + #[allow(unused)] + pub fn scope(&self) -> Option<&str> { + if self.name.starts_with('@') && self.name.contains('/') { + self.name.split('/').next() + } else { + None + } + } + + pub fn as_serialized(&self) -> String { + self.as_serialized_with_level(0) + } + + fn as_serialized_with_level(&self, level: usize) -> String { + // WARNING: This should not change because it's used in the lockfile + let mut result = format!( + "{}@{}", + if level == 0 { + self.name.to_string() + } else { + self.name.replace('/', "+") + }, + self.version + ); + for peer in &self.peer_dependencies { + // unfortunately we can't do something like `_3` when + // this gets deep because npm package names can start + // with a number + result.push_str(&"_".repeat(level + 1)); + result.push_str(&peer.as_serialized_with_level(level + 1)); + } + result + } + + pub fn from_serialized(id: &str) -> Result<Self, AnyError> { + use monch::*; + + fn parse_name(input: &str) -> ParseResult<&str> { + if_not_empty(substring(move |input| { + for (pos, c) in input.char_indices() { + // first character might be a scope, so skip it + if pos > 0 && c == '@' { + return Ok((&input[pos..], ())); + } + } + ParseError::backtrace() + }))(input) + } + + fn parse_version(input: &str) -> ParseResult<&str> { + if_not_empty(substring(skip_while(|c| c != '_')))(input) + } + + fn parse_name_and_version( + input: &str, + ) -> ParseResult<(String, NpmVersion)> { + let (input, name) = parse_name(input)?; + let (input, _) = ch('@')(input)?; + let at_version_input = input; + let (input, version) = parse_version(input)?; + match NpmVersion::parse(version) { + Ok(version) => Ok((input, (name.to_string(), version))), + Err(err) => ParseError::fail(at_version_input, format!("{:#}", err)), + } + } + + fn parse_level_at_level<'a>( + level: usize, + ) -> impl Fn(&'a str) -> ParseResult<'a, ()> { + fn parse_level(input: &str) -> ParseResult<usize> { + let level = input.chars().take_while(|c| *c == '_').count(); + Ok((&input[level..], level)) + } + + move |input| { + let (input, parsed_level) = parse_level(input)?; + if parsed_level == level { + Ok((input, ())) + } else { + ParseError::backtrace() + } + } + } + + fn parse_peers_at_level<'a>( + level: usize, + ) -> impl Fn(&'a str) -> ParseResult<'a, Vec<NpmPackageId>> { + move |mut input| { + let mut peers = Vec::new(); + while let Ok((level_input, _)) = parse_level_at_level(level)(input) { + input = level_input; + let peer_result = parse_id_at_level(level)(input)?; + input = peer_result.0; + peers.push(peer_result.1); + } + Ok((input, peers)) + } + } + + fn parse_id_at_level<'a>( + level: usize, + ) -> impl Fn(&'a str) -> ParseResult<'a, NpmPackageId> { + move |input| { + let (input, (name, version)) = parse_name_and_version(input)?; + let name = if level > 0 { + name.replace('+', "/") + } else { + name + }; + let (input, peer_dependencies) = + parse_peers_at_level(level + 1)(input)?; + Ok(( + input, + NpmPackageId { + name, + version, + peer_dependencies, + }, + )) + } + } + + with_failure_handling(parse_id_at_level(0))(id) + .with_context(|| format!("Invalid npm package id '{}'.", id)) + } + + pub fn display(&self) -> String { + // Don't implement std::fmt::Display because we don't + // want this to be used by accident in certain scenarios. + format!("{}@{}", self.name, self.version) + } +} + +#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)] +pub struct NpmResolutionPackage { + pub id: NpmPackageId, + /// The peer dependency resolution can differ for the same + /// package (name and version) depending on where it is in + /// the resolution tree. This copy index indicates which + /// copy of the package this is. + pub copy_index: usize, + pub dist: NpmPackageVersionDistInfo, + /// Key is what the package refers to the other package as, + /// which could be different from the package name. + pub dependencies: HashMap<String, NpmPackageId>, +} + +impl NpmResolutionPackage { + pub fn get_package_cache_folder_id(&self) -> NpmPackageCacheFolderId { + NpmPackageCacheFolderId { + name: self.id.name.clone(), + version: self.id.version.clone(), + copy_index: self.copy_index, + } + } +} + +pub struct NpmResolution { + api: RealNpmRegistryApi, + snapshot: RwLock<NpmResolutionSnapshot>, + update_sempahore: tokio::sync::Semaphore, +} + +impl std::fmt::Debug for NpmResolution { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + let snapshot = self.snapshot.read(); + f.debug_struct("NpmResolution") + .field("snapshot", &snapshot) + .finish() + } +} + +impl NpmResolution { + pub fn new( + api: RealNpmRegistryApi, + initial_snapshot: Option<NpmResolutionSnapshot>, + ) -> Self { + Self { + api, + snapshot: RwLock::new(initial_snapshot.unwrap_or_default()), + update_sempahore: tokio::sync::Semaphore::new(1), + } + } + + pub async fn add_package_reqs( + &self, + package_reqs: Vec<NpmPackageReq>, + ) -> Result<(), AnyError> { + // only allow one thread in here at a time + let _permit = self.update_sempahore.acquire().await.unwrap(); + let snapshot = self.snapshot.read().clone(); + + let snapshot = self + .add_package_reqs_to_snapshot(package_reqs, snapshot) + .await?; + + *self.snapshot.write() = snapshot; + Ok(()) + } + + pub async fn set_package_reqs( + &self, + package_reqs: HashSet<NpmPackageReq>, + ) -> Result<(), AnyError> { + // only allow one thread in here at a time + let _permit = self.update_sempahore.acquire().await.unwrap(); + let snapshot = self.snapshot.read().clone(); + + let has_removed_package = !snapshot + .package_reqs + .keys() + .all(|req| package_reqs.contains(req)); + // if any packages were removed, we need to completely recreate the npm resolution snapshot + let snapshot = if has_removed_package { + NpmResolutionSnapshot::default() + } else { + snapshot + }; + let snapshot = self + .add_package_reqs_to_snapshot( + package_reqs.into_iter().collect(), + snapshot, + ) + .await?; + + *self.snapshot.write() = snapshot; + + Ok(()) + } + + async fn add_package_reqs_to_snapshot( + &self, + mut package_reqs: Vec<NpmPackageReq>, + snapshot: NpmResolutionSnapshot, + ) -> Result<NpmResolutionSnapshot, AnyError> { + // convert the snapshot to a traversable graph + let mut graph = Graph::from_snapshot(snapshot); + + // multiple packages are resolved in alphabetical order + package_reqs.sort_by(|a, b| a.name.cmp(&b.name)); + + // go over the top level packages first, then down the + // tree one level at a time through all the branches + let mut unresolved_tasks = Vec::with_capacity(package_reqs.len()); + for package_req in package_reqs { + if graph.has_package_req(&package_req) { + // skip analyzing this package, as there's already a matching top level package + continue; + } + + // no existing best version, so resolve the current packages + let api = self.api.clone(); + let maybe_info = if should_sync_download() { + // for deterministic test output + Some(api.package_info(&package_req.name).await) + } else { + None + }; + unresolved_tasks.push(tokio::task::spawn(async move { + let info = match maybe_info { + Some(info) => info?, + None => api.package_info(&package_req.name).await?, + }; + Result::<_, AnyError>::Ok((package_req, info)) + })); + } + + let mut resolver = GraphDependencyResolver::new(&mut graph, &self.api); + + for result in futures::future::join_all(unresolved_tasks).await { + let (package_req, info) = result??; + resolver.add_package_req(&package_req, info)?; + } + + resolver.resolve_pending().await?; + + graph.into_snapshot(&self.api).await + } + + pub fn resolve_package_from_id( + &self, + id: &NpmPackageId, + ) -> Option<NpmResolutionPackage> { + self.snapshot.read().package_from_id(id).cloned() + } + + pub fn resolve_package_cache_folder_id_from_id( + &self, + id: &NpmPackageId, + ) -> Option<NpmPackageCacheFolderId> { + self + .snapshot + .read() + .package_from_id(id) + .map(|p| p.get_package_cache_folder_id()) + } + + pub fn resolve_package_from_package( + &self, + name: &str, + referrer: &NpmPackageCacheFolderId, + ) -> Result<NpmResolutionPackage, AnyError> { + self + .snapshot + .read() + .resolve_package_from_package(name, referrer) + .cloned() + } + + /// Resolve a node package from a deno module. + pub fn resolve_package_from_deno_module( + &self, + package: &NpmPackageReq, + ) -> Result<NpmResolutionPackage, AnyError> { + self + .snapshot + .read() + .resolve_package_from_deno_module(package) + .cloned() + } + + pub fn all_packages(&self) -> Vec<NpmResolutionPackage> { + self.snapshot.read().all_packages() + } + + pub fn all_packages_partitioned(&self) -> NpmPackagesPartitioned { + self.snapshot.read().all_packages_partitioned() + } + + pub fn has_packages(&self) -> bool { + !self.snapshot.read().packages.is_empty() + } + + pub fn snapshot(&self) -> NpmResolutionSnapshot { + self.snapshot.read().clone() + } + + pub fn lock( + &self, + lockfile: &mut Lockfile, + snapshot: &NpmResolutionSnapshot, + ) -> Result<(), AnyError> { + for (package_req, package_id) in snapshot.package_reqs.iter() { + lockfile.insert_npm_specifier(package_req, package_id); + } + for package in self.all_packages() { + lockfile.check_or_insert_npm_package(&package)?; + } + Ok(()) + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn parse_npm_package_ref() { + assert_eq!( + NpmPackageReference::from_str("npm:@package/test").unwrap(), + NpmPackageReference { + req: NpmPackageReq { + name: "@package/test".to_string(), + version_req: None, + }, + sub_path: None, + } + ); + + assert_eq!( + NpmPackageReference::from_str("npm:@package/test@1").unwrap(), + NpmPackageReference { + req: NpmPackageReq { + name: "@package/test".to_string(), + version_req: Some(SpecifierVersionReq::parse("1").unwrap()), + }, + sub_path: None, + } + ); + + assert_eq!( + NpmPackageReference::from_str("npm:@package/test@~1.1/sub_path").unwrap(), + NpmPackageReference { + req: NpmPackageReq { + name: "@package/test".to_string(), + version_req: Some(SpecifierVersionReq::parse("~1.1").unwrap()), + }, + sub_path: Some("sub_path".to_string()), + } + ); + + assert_eq!( + NpmPackageReference::from_str("npm:@package/test/sub_path").unwrap(), + NpmPackageReference { + req: NpmPackageReq { + name: "@package/test".to_string(), + version_req: None, + }, + sub_path: Some("sub_path".to_string()), + } + ); + + assert_eq!( + NpmPackageReference::from_str("npm:test").unwrap(), + NpmPackageReference { + req: NpmPackageReq { + name: "test".to_string(), + version_req: None, + }, + sub_path: None, + } + ); + + assert_eq!( + NpmPackageReference::from_str("npm:test@^1.2").unwrap(), + NpmPackageReference { + req: NpmPackageReq { + name: "test".to_string(), + version_req: Some(SpecifierVersionReq::parse("^1.2").unwrap()), + }, + sub_path: None, + } + ); + + assert_eq!( + NpmPackageReference::from_str("npm:test@~1.1/sub_path").unwrap(), + NpmPackageReference { + req: NpmPackageReq { + name: "test".to_string(), + version_req: Some(SpecifierVersionReq::parse("~1.1").unwrap()), + }, + sub_path: Some("sub_path".to_string()), + } + ); + + assert_eq!( + NpmPackageReference::from_str("npm:@package/test/sub_path").unwrap(), + NpmPackageReference { + req: NpmPackageReq { + name: "@package/test".to_string(), + version_req: None, + }, + sub_path: Some("sub_path".to_string()), + } + ); + + assert_eq!( + NpmPackageReference::from_str("npm:@package") + .err() + .unwrap() + .to_string(), + "Not a valid package: @package" + ); + } + + #[test] + fn serialize_npm_package_id() { + let id = NpmPackageId { + name: "pkg-a".to_string(), + version: NpmVersion::parse("1.2.3").unwrap(), + peer_dependencies: vec![ + NpmPackageId { + name: "pkg-b".to_string(), + version: NpmVersion::parse("3.2.1").unwrap(), + peer_dependencies: vec![ + NpmPackageId { + name: "pkg-c".to_string(), + version: NpmVersion::parse("1.3.2").unwrap(), + peer_dependencies: vec![], + }, + NpmPackageId { + name: "pkg-d".to_string(), + version: NpmVersion::parse("2.3.4").unwrap(), + peer_dependencies: vec![], + }, + ], + }, + NpmPackageId { + name: "pkg-e".to_string(), + version: NpmVersion::parse("2.3.1").unwrap(), + peer_dependencies: vec![NpmPackageId { + name: "pkg-f".to_string(), + version: NpmVersion::parse("2.3.1").unwrap(), + peer_dependencies: vec![], + }], + }, + ], + }; + let serialized = id.as_serialized(); + assert_eq!(serialized, "pkg-a@1.2.3_pkg-b@3.2.1__pkg-c@1.3.2__pkg-d@2.3.4_pkg-e@2.3.1__pkg-f@2.3.1"); + assert_eq!(NpmPackageId::from_serialized(&serialized).unwrap(), id); + } +} diff --git a/cli/npm/resolution/snapshot.rs b/cli/npm/resolution/snapshot.rs new file mode 100644 index 000000000..d76ba8b1a --- /dev/null +++ b/cli/npm/resolution/snapshot.rs @@ -0,0 +1,470 @@ +// Copyright 2018-2022 the Deno authors. All rights reserved. MIT license. + +use std::collections::HashMap; +use std::collections::HashSet; +use std::sync::Arc; + +use deno_core::anyhow::anyhow; +use deno_core::anyhow::bail; +use deno_core::anyhow::Context; +use deno_core::error::AnyError; +use deno_core::futures; +use deno_core::parking_lot::Mutex; +use serde::Deserialize; +use serde::Serialize; + +use crate::lockfile::Lockfile; +use crate::npm::cache::should_sync_download; +use crate::npm::cache::NpmPackageCacheFolderId; +use crate::npm::registry::NpmPackageVersionDistInfo; +use crate::npm::registry::NpmRegistryApi; +use crate::npm::registry::RealNpmRegistryApi; + +use super::NpmPackageId; +use super::NpmPackageReq; +use super::NpmResolutionPackage; +use super::NpmVersionMatcher; + +/// Packages partitioned by if they are "copy" packages or not. +pub struct NpmPackagesPartitioned { + pub packages: Vec<NpmResolutionPackage>, + /// Since peer dependency resolution occurs based on ancestors and ancestor + /// siblings, this may sometimes cause the same package (name and version) + /// to have different dependencies based on where it appears in the tree. + /// For these packages, we create a "copy package" or duplicate of the package + /// whose dependencies are that of where in the tree they've resolved to. + pub copy_packages: Vec<NpmResolutionPackage>, +} + +impl NpmPackagesPartitioned { + pub fn into_all(self) -> Vec<NpmResolutionPackage> { + let mut packages = self.packages; + packages.extend(self.copy_packages); + packages + } +} + +#[derive(Debug, Clone, Default, Serialize, Deserialize)] +pub struct NpmResolutionSnapshot { + #[serde(with = "map_to_vec")] + pub(super) package_reqs: HashMap<NpmPackageReq, NpmPackageId>, + pub(super) packages_by_name: HashMap<String, Vec<NpmPackageId>>, + #[serde(with = "map_to_vec")] + pub(super) packages: HashMap<NpmPackageId, NpmResolutionPackage>, +} + +// This is done so the maps with non-string keys get serialized and deserialized as vectors. +// Adapted from: https://github.com/serde-rs/serde/issues/936#issuecomment-302281792 +mod map_to_vec { + use std::collections::HashMap; + + use serde::de::Deserialize; + use serde::de::Deserializer; + use serde::ser::Serializer; + use serde::Serialize; + + pub fn serialize<S, K: Serialize, V: Serialize>( + map: &HashMap<K, V>, + serializer: S, + ) -> Result<S::Ok, S::Error> + where + S: Serializer, + { + serializer.collect_seq(map.iter()) + } + + pub fn deserialize< + 'de, + D, + K: Deserialize<'de> + Eq + std::hash::Hash, + V: Deserialize<'de>, + >( + deserializer: D, + ) -> Result<HashMap<K, V>, D::Error> + where + D: Deserializer<'de>, + { + let mut map = HashMap::new(); + for (key, value) in Vec::<(K, V)>::deserialize(deserializer)? { + map.insert(key, value); + } + Ok(map) + } +} + +impl NpmResolutionSnapshot { + /// Resolve a node package from a deno module. + pub fn resolve_package_from_deno_module( + &self, + req: &NpmPackageReq, + ) -> Result<&NpmResolutionPackage, AnyError> { + match self.package_reqs.get(req) { + Some(id) => Ok(self.packages.get(id).unwrap()), + None => bail!("could not find npm package directory for '{}'", req), + } + } + + pub fn top_level_packages(&self) -> Vec<NpmPackageId> { + self + .package_reqs + .values() + .cloned() + .collect::<HashSet<_>>() + .into_iter() + .collect::<Vec<_>>() + } + + pub fn package_from_id( + &self, + id: &NpmPackageId, + ) -> Option<&NpmResolutionPackage> { + self.packages.get(id) + } + + pub fn resolve_package_from_package( + &self, + name: &str, + referrer: &NpmPackageCacheFolderId, + ) -> Result<&NpmResolutionPackage, AnyError> { + // todo(dsherret): do we need an additional hashmap to get this quickly? + let referrer_package = self + .packages_by_name + .get(&referrer.name) + .and_then(|packages| { + packages + .iter() + .filter(|p| p.version == referrer.version) + .filter_map(|id| { + let package = self.packages.get(id)?; + if package.copy_index == referrer.copy_index { + Some(package) + } else { + None + } + }) + .next() + }) + .ok_or_else(|| { + anyhow!("could not find referrer npm package '{}'", referrer) + })?; + + let name = name_without_path(name); + if let Some(id) = referrer_package.dependencies.get(name) { + return Ok(self.packages.get(id).unwrap()); + } + + if referrer_package.id.name == name { + return Ok(referrer_package); + } + + // TODO(bartlomieju): this should use a reverse lookup table in the + // snapshot instead of resolving best version again. + let req = NpmPackageReq { + name: name.to_string(), + version_req: None, + }; + + if let Some(id) = self.resolve_best_package_id(name, &req) { + if let Some(pkg) = self.packages.get(&id) { + return Ok(pkg); + } + } + + bail!( + "could not find npm package '{}' referenced by '{}'", + name, + referrer + ) + } + + pub fn all_packages(&self) -> Vec<NpmResolutionPackage> { + self.packages.values().cloned().collect() + } + + pub fn all_packages_partitioned(&self) -> NpmPackagesPartitioned { + let mut packages = self.all_packages(); + let mut copy_packages = Vec::with_capacity(packages.len() / 2); // at most 1 copy for every package + + // partition out any packages that are "copy" packages + for i in (0..packages.len()).rev() { + if packages[i].copy_index > 0 { + copy_packages.push(packages.swap_remove(i)); + } + } + + NpmPackagesPartitioned { + packages, + copy_packages, + } + } + + pub fn resolve_best_package_id( + &self, + name: &str, + version_matcher: &impl NpmVersionMatcher, + ) -> Option<NpmPackageId> { + // todo(dsherret): this is not exactly correct because some ids + // will be better than others due to peer dependencies + let mut maybe_best_id: Option<&NpmPackageId> = None; + if let Some(ids) = self.packages_by_name.get(name) { + for id in ids { + if version_matcher.matches(&id.version) { + let is_best_version = maybe_best_id + .as_ref() + .map(|best_id| best_id.version.cmp(&id.version).is_lt()) + .unwrap_or(true); + if is_best_version { + maybe_best_id = Some(id); + } + } + } + } + maybe_best_id.cloned() + } + + pub async fn from_lockfile( + lockfile: Arc<Mutex<Lockfile>>, + api: &RealNpmRegistryApi, + ) -> Result<Self, AnyError> { + let mut package_reqs: HashMap<NpmPackageReq, NpmPackageId>; + let mut packages_by_name: HashMap<String, Vec<NpmPackageId>>; + let mut packages: HashMap<NpmPackageId, NpmResolutionPackage>; + let mut copy_index_resolver: SnapshotPackageCopyIndexResolver; + + { + let lockfile = lockfile.lock(); + + // pre-allocate collections + package_reqs = + HashMap::with_capacity(lockfile.content.npm.specifiers.len()); + let packages_len = lockfile.content.npm.packages.len(); + packages = HashMap::with_capacity(packages_len); + packages_by_name = HashMap::with_capacity(packages_len); // close enough + copy_index_resolver = + SnapshotPackageCopyIndexResolver::with_capacity(packages_len); + let mut verify_ids = HashSet::with_capacity(packages_len); + + // collect the specifiers to version mappings + for (key, value) in &lockfile.content.npm.specifiers { + let package_req = NpmPackageReq::from_str(key) + .with_context(|| format!("Unable to parse npm specifier: {}", key))?; + let package_id = NpmPackageId::from_serialized(value)?; + package_reqs.insert(package_req, package_id.clone()); + verify_ids.insert(package_id.clone()); + } + + // then the packages + for (key, value) in &lockfile.content.npm.packages { + let package_id = NpmPackageId::from_serialized(key)?; + + // collect the dependencies + let mut dependencies = HashMap::default(); + + packages_by_name + .entry(package_id.name.to_string()) + .or_default() + .push(package_id.clone()); + + for (name, specifier) in &value.dependencies { + let dep_id = NpmPackageId::from_serialized(specifier)?; + dependencies.insert(name.to_string(), dep_id.clone()); + verify_ids.insert(dep_id); + } + + let package = NpmResolutionPackage { + id: package_id.clone(), + copy_index: copy_index_resolver.resolve(&package_id), + // temporary dummy value + dist: NpmPackageVersionDistInfo { + tarball: "foobar".to_string(), + shasum: "foobar".to_string(), + integrity: Some("foobar".to_string()), + }, + dependencies, + }; + + packages.insert(package_id, package); + } + + // verify that all these ids exist in packages + for id in &verify_ids { + if !packages.contains_key(id) { + bail!( + "the lockfile is corrupt. You can recreate it with --lock-write" + ); + } + } + } + + let mut unresolved_tasks = Vec::with_capacity(packages_by_name.len()); + + // cache the package names in parallel in the registry api + // unless synchronous download should occur + if should_sync_download() { + let mut package_names = packages_by_name.keys().collect::<Vec<_>>(); + package_names.sort(); + for package_name in package_names { + api.package_info(package_name).await?; + } + } else { + for package_name in packages_by_name.keys() { + let package_name = package_name.clone(); + let api = api.clone(); + unresolved_tasks.push(tokio::task::spawn(async move { + api.package_info(&package_name).await?; + Result::<_, AnyError>::Ok(()) + })); + } + } + for result in futures::future::join_all(unresolved_tasks).await { + result??; + } + + // ensure the dist is set for each package + for package in packages.values_mut() { + // this will read from the memory cache now + let version_info = match api + .package_version_info(&package.id.name, &package.id.version) + .await? + { + Some(version_info) => version_info, + None => { + bail!("could not find '{}' specified in the lockfile. Maybe try again with --reload", package.id.display()); + } + }; + package.dist = version_info.dist; + } + + Ok(Self { + package_reqs, + packages_by_name, + packages, + }) + } +} + +pub struct SnapshotPackageCopyIndexResolver { + packages_to_copy_index: HashMap<NpmPackageId, usize>, + package_name_version_to_copy_count: HashMap<(String, String), usize>, +} + +impl SnapshotPackageCopyIndexResolver { + pub fn with_capacity(capacity: usize) -> Self { + Self { + packages_to_copy_index: HashMap::with_capacity(capacity), + package_name_version_to_copy_count: HashMap::with_capacity(capacity), // close enough + } + } + + pub fn from_map_with_capacity( + mut packages_to_copy_index: HashMap<NpmPackageId, usize>, + capacity: usize, + ) -> Self { + let mut package_name_version_to_copy_count = + HashMap::with_capacity(capacity); // close enough + if capacity > packages_to_copy_index.len() { + packages_to_copy_index.reserve(capacity - packages_to_copy_index.len()); + } + + for (id, index) in &packages_to_copy_index { + let entry = package_name_version_to_copy_count + .entry((id.name.to_string(), id.version.to_string())) + .or_insert(0); + if *entry < *index { + *entry = *index; + } + } + Self { + packages_to_copy_index, + package_name_version_to_copy_count, + } + } + + pub fn resolve(&mut self, id: &NpmPackageId) -> usize { + if let Some(index) = self.packages_to_copy_index.get(id) { + *index + } else { + let index = *self + .package_name_version_to_copy_count + .entry((id.name.to_string(), id.version.to_string())) + .and_modify(|count| { + *count += 1; + }) + .or_insert(0); + self.packages_to_copy_index.insert(id.clone(), index); + index + } + } +} + +fn name_without_path(name: &str) -> &str { + let mut search_start_index = 0; + if name.starts_with('@') { + if let Some(slash_index) = name.find('/') { + search_start_index = slash_index + 1; + } + } + if let Some(slash_index) = &name[search_start_index..].find('/') { + // get the name up until the path slash + &name[0..search_start_index + slash_index] + } else { + name + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_name_without_path() { + assert_eq!(name_without_path("foo"), "foo"); + assert_eq!(name_without_path("@foo/bar"), "@foo/bar"); + assert_eq!(name_without_path("@foo/bar/baz"), "@foo/bar"); + assert_eq!(name_without_path("@hello"), "@hello"); + } + + #[test] + fn test_copy_index_resolver() { + let mut copy_index_resolver = + SnapshotPackageCopyIndexResolver::with_capacity(10); + assert_eq!( + copy_index_resolver + .resolve(&NpmPackageId::from_serialized("package@1.0.0").unwrap()), + 0 + ); + assert_eq!( + copy_index_resolver + .resolve(&NpmPackageId::from_serialized("package@1.0.0").unwrap()), + 0 + ); + assert_eq!( + copy_index_resolver.resolve( + &NpmPackageId::from_serialized("package@1.0.0_package-b@1.0.0") + .unwrap() + ), + 1 + ); + assert_eq!( + copy_index_resolver.resolve( + &NpmPackageId::from_serialized( + "package@1.0.0_package-b@1.0.0__package-c@2.0.0" + ) + .unwrap() + ), + 2 + ); + assert_eq!( + copy_index_resolver.resolve( + &NpmPackageId::from_serialized("package@1.0.0_package-b@1.0.0") + .unwrap() + ), + 1 + ); + assert_eq!( + copy_index_resolver + .resolve(&NpmPackageId::from_serialized("package-b@1.0.0").unwrap()), + 0 + ); + } +} |