summaryrefslogtreecommitdiffstats
path: root/src/package
diff options
context:
space:
mode:
Diffstat (limited to 'src/package')
-rw-r--r--src/package/dag.rs154
-rw-r--r--src/package/mod.rs4
-rw-r--r--src/package/package.rs7
-rw-r--r--src/package/tree.rs558
4 files changed, 163 insertions, 560 deletions
diff --git a/src/package/dag.rs b/src/package/dag.rs
new file mode 100644
index 0000000..a4596aa
--- /dev/null
+++ b/src/package/dag.rs
@@ -0,0 +1,154 @@
+//
+// Copyright (c) 2020-2021 science+computing ag and other contributors
+//
+// This program and the accompanying materials are made
+// available under the terms of the Eclipse Public License 2.0
+// which is available at https://www.eclipse.org/legal/epl-2.0/
+//
+// SPDX-License-Identifier: EPL-2.0
+//
+
+use std::borrow::Cow;
+use std::collections::HashMap;
+use std::io::Result as IoResult;
+use std::io::Write;
+
+use anyhow::Error;
+use anyhow::Result;
+use anyhow::anyhow;
+use daggy::Walker;
+use indicatif::ProgressBar;
+use log::trace;
+use ptree::Style;
+use ptree::TreeItem;
+use resiter::AndThen;
+use getset::Getters;
+
+use crate::package::Package;
+use crate::repository::Repository;
+
+#[derive(Debug, Getters)]
+pub struct Dag {
+ #[getset(get = "pub")]
+ dag: daggy::Dag<Package, i8>,
+
+ #[getset(get = "pub")]
+ root_idx: daggy::NodeIndex,
+}
+
+impl Dag {
+ pub fn for_root_package(
+ p: Package,
+ repo: &Repository,
+ progress: ProgressBar,
+ ) -> Result<Self> {
+ fn add_sub_packages<'a>(
+ repo: &'a Repository,
+ mappings: &mut HashMap<&'a Package, daggy::NodeIndex>,
+ dag: &mut daggy::Dag<&'a Package, i8>,
+ p: &'a Package,
+ progress: &ProgressBar
+ ) -> Result<()> {
+ p.get_self_packaged_dependencies()
+ .and_then_ok(|(name, constr)| {
+ trace!("Dependency: {:?}", name);
+ let packs = repo.find_with_version(&name, &constr);
+ trace!("Found: {:?}", packs);
+
+ if mappings.keys().any(|p| packs.iter().any(|pk| pk.name() == p.name() && pk.version() == p.version())) {
+ return Err(anyhow!(
+ "Duplicate version of some package in {:?} found",
+ packs
+ ));
+ }
+ trace!("All dependecies available...");
+
+ packs.into_iter()
+ .map(|p| {
+ progress.tick();
+ trace!("Following dependecy: {:?}", p);
+
+ let idx = dag.add_node(p);
+ mappings.insert(p, idx);
+ add_sub_packages(repo, mappings, dag, p, progress)
+ })
+ .collect()
+ })
+ .collect::<Result<()>>()
+ }
+
+ fn add_edges(mappings: &HashMap<&Package, daggy::NodeIndex>, dag: &mut daggy::Dag<&Package, i8>) -> Result<()> {
+ for (package, idx) in mappings {
+ package.get_self_packaged_dependencies()
+ .and_then_ok(|(name, constr)| {
+ mappings
+ .iter()
+ .filter(|(package, _)| *package.name() == name && constr.matches(package.version()))
+ .try_for_each(|(_, dep_idx)| {
+ dag.add_edge(*idx, *dep_idx, 0)
+ .map(|_| ())
+ .map_err(Error::from)
+ })
+ })
+ .collect::<Result<()>>()?
+ }
+
+ Ok(())
+ }
+
+ let mut dag: daggy::Dag<&Package, i8> = daggy::Dag::new();
+ let mut mappings = HashMap::new();
+
+ trace!("Making package Tree for {:?}", p);
+ let root_idx = dag.add_node(&p);
+ mappings.insert(&p, root_idx);
+ add_sub_packages(repo, &mut mappings, &mut dag, &p, &progress)?;
+ add_edges(&mappings, &mut dag)?;
+ trace!("Finished makeing package Tree");
+
+ Ok(Dag {
+ dag: dag.map(|_, p: &&Package| -> Package { (*p).clone() }, |_, e| *e),
+ root_idx
+ })
+ }
+
+ /// Get all packages in the tree by reference
+ ///
+ /// # Warning
+ ///
+ /// The order of the packages is _NOT_ guaranteed by the implementation
+ pub fn all_packages(&self) -> Vec<&Package> {
+ self.dag
+ .graph()
+ .node_indices()
+ .filter_map(|idx| self.dag.graph().node_weight(idx))
+ .collect()
+ }
+
+ pub fn display(&self) -> DagDisplay {
+ DagDisplay(self, self.root_idx)
+ }
+}
+
+#[derive(Clone)]
+pub struct DagDisplay<'a>(&'a Dag, daggy::NodeIndex);
+
+impl<'a> TreeItem for DagDisplay<'a> {
+ type Child = Self;
+
+ fn write_self<W: Write>(&self, f: &mut W, _: &Style) -> IoResult<()> {
+ let p = self.0.dag.graph().node_weight(self.1)
+ .ok_or_else(|| anyhow!("Error finding node: {:?}", self.1))
+ .map_err(|e| std::io::Error::new(std::io::ErrorKind::Other, e))?;
+ write!(f, "{} {}", p.name(), p.version())
+ }
+
+ fn children(&self) -> Cow<[Self::Child]> {
+ let c = self.0.dag.children(self.1);
+ Cow::from(c.iter(&self.0.dag)
+ .map(|(_, idx)| DagDisplay(self.0, idx))
+ .collect::<Vec<_>>()
+ )
+ }
+}
+
diff --git a/src/package/mod.rs b/src/package/mod.rs
index 88486a3..ad226c1 100644
--- a/src/package/mod.rs
+++ b/src/package/mod.rs
@@ -29,8 +29,8 @@ pub use script::*;
mod source;
pub use source::*;
-mod tree;
-pub use tree::*;
+mod dag;
+pub use dag::*;
mod version;
pub use version::*;
diff --git a/src/package/package.rs b/src/package/package.rs
index 59c1d55..b9b2251 100644
--- a/src/package/package.rs
+++ b/src/package/package.rs
@@ -75,6 +75,13 @@ pub struct Package {
meta: Option<HashMap<String, String>>,
}
+impl std::hash::Hash for Package {
+ fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
+ self.name.hash(state);
+ self.version.hash(state);
+ }
+}
+
impl Package {
#[cfg(test)]
pub fn new(
diff --git a/src/package/tree.rs b/src/package/tree.rs
deleted file mode 100644
index 40cab90..0000000
--- a/src/package/tree.rs
+++ /dev/null
@@ -1,558 +0,0 @@
-//
-// Copyright (c) 2020-2021 science+computing ag and other contributors
-//
-// This program and the accompanying materials are made
-// available under the terms of the Eclipse Public License 2.0
-// which is available at https://www.eclipse.org/legal/epl-2.0/
-//
-// SPDX-License-Identifier: EPL-2.0
-//
-
-use std::borrow::Cow;
-use std::io::Result as IoResult;
-use std::io::Write;
-
-use anyhow::anyhow;
-use anyhow::Result;
-use indicatif::ProgressBar;
-use log::trace;
-use ptree::Style;
-use ptree::TreeItem;
-use resiter::AndThen;
-use serde::Deserialize;
-use serde::Serialize;
-
-use crate::package::Package;
-use crate::repository::Repository;
-
-#[derive(Debug, Serialize, Deserialize)]
-pub struct Tree {
- root: Vec<Mapping>,
-}
-
-/// Helper type
-///
-/// This helper type is required so that the serialized JSON is a bit more readable.
-#[derive(Debug, Serialize, Deserialize)]
-struct Mapping {
- package: Package,
- dependencies: Tree,
-}
-
-impl Tree {
- pub fn add_package(
- &mut self,
- p: Package,
- repo: &Repository,
- progress: ProgressBar,
- ) -> Result<()> {
- macro_rules! mk_add_package_tree {
- ($this:ident, $pack:ident, $repo:ident, $root:ident, $progress:ident) => {{
- let mut subtree = Tree::default();
- ($pack)
- .get_self_packaged_dependencies()
- .and_then_ok(|(name, constr)| {
- trace!("Dependency: {:?}", name);
- let pack = ($repo).find_with_version(&name, &constr);
- trace!("Found: {:?}", pack);
-
- if pack.iter().any(|p| ($root).has_package(p)) {
- return Err(anyhow!(
- "Duplicate version of some package in {:?} found",
- pack
- ));
- }
- trace!("All dependecies available...");
-
- pack.into_iter()
- .map(|p| {
- ($progress).tick();
- trace!("Following dependecy: {:?}", p);
- add_package_tree(
- &mut subtree,
- p.clone(),
- ($repo),
- ($root),
- ($progress).clone(),
- )
- })
- .collect()
- })
- .collect::<Result<Vec<()>>>()?;
-
- trace!("Inserting subtree: {:?} -> {:?}", ($pack), subtree);
- ($this).root.push(Mapping {
- package: ($pack),
- dependencies: subtree,
- });
- Ok(())
- }};
- };
-
- fn add_package_tree(
- this: &mut Tree,
- p: Package,
- repo: &Repository,
- root: &mut Tree,
- progress: ProgressBar,
- ) -> Result<()> {
- mk_add_package_tree!(this, p, repo, root, progress)
- }
-
- trace!("Making package Tree for {:?}", p);
- let r = mk_add_package_tree!(self, p, repo, self, progress);
- trace!("Finished makeing package Tree");
- r
- }
-
- /// Get packages of the tree
- ///
- /// This does not yield packages which are dependencies of this tree node.
- /// It yields only packages for this particular Tree instance.
- pub fn packages(&self) -> impl Iterator<Item = &Package> {
- self.root.iter().map(|mapping| &mapping.package)
- }
-
- /// Get all packages in the tree by reference
- ///
- /// # Warning
- ///
- /// The order of the packages is _NOT_ guaranteed by the implementation
- pub fn all_packages(&self) -> Vec<&Package> {
- self.root
- .iter()
- .map(|m| m.dependencies.all_packages())
- .flatten()
- .chain(self.root.iter().map(|m| &m.package))
- .collect()
- }
-
- /// Get dependencies stored in this tree
- pub fn dependencies(&self) -> impl Iterator<Item = &Tree> {
- self.root.iter().map(|mapping| &mapping.dependencies)
- }
-
- pub fn into_iter(self) -> impl IntoIterator<Item = (Package, Tree)> {
- self.root.into_iter().map(|m| (m.package, m.dependencies))
- }
-
- pub fn has_package(&self, p: &Package) -> bool {
- let name_eq = |k: &Package| k.name() == p.name();
- self.packages().any(name_eq) || self.dependencies().any(|t| t.has_package(p))
- }
-
- pub fn display(&self) -> Vec<DisplayTree> {
- self.root.iter().map(DisplayTree).collect()
- }
-}
-
-#[derive(Clone)]
-pub struct DisplayTree<'a>(&'a Mapping);
-
-impl<'a> TreeItem for DisplayTree<'a> {
- type Child = Self;
-
- fn write_self<W: Write>(&self, f: &mut W, _: &Style) -> IoResult<()> {
- write!(f, "{} {}", self.0.package.name(), self.0.package.version())
- }
-
- fn children(&self) -> Cow<[Self::Child]> {
- Cow::from(
- self.0
- .dependencies
- .root
- .iter()
- .map(DisplayTree)
- .collect::<Vec<_>>(),
- )
- }
-}
-
-impl Default for Tree {
- fn default() -> Tree {
- Tree {
- root: Vec::default(),
- }
- }
-}
-
-#[cfg(test)]
-mod tests {
- use super::*;
-
- use std::collections::BTreeMap;
-
- use crate::package::tests::package;
- use crate::package::tests::pname;
- use crate::package::tests::pversion;
- use crate::package::Dependencies;
- use crate::package::Dependency;
-
- use indicatif::ProgressBar;
-
- #[test]
- fn test_add_package() {
- let mut btree = BTreeMap::new();
-
- let p1 = {
- let name = "a";
- let vers = "1";
- let pack = package(name, vers, "https://rust-lang.org", "123");
- btree.insert((pname(name), pversion(vers)), pack.clone());
- pack
- };
-
- let repo = Repository::from(btree);
- let progress = ProgressBar::hidden();
-
- let mut tree = Tree::default();
- let r = tree.add_package(p1, &repo, progress);
- assert!(r.is_ok());
- }
-
- #[test]
- fn test_add_two_packages() {
- let mut btree = BTreeMap::new();
-
- let p1 = {
- let name = "a";
- let vers = "1";
- let pack = package(name, vers, "https://rust-lang.org", "123");
- btree.insert((pname(name), pversion(vers)), pack.clone());
- pack
- };
- let p2 = {
- let name = "b";
- let vers = "2";
- let pack = package(name, vers, "https://rust-lang.org", "124");
- btree.insert((pname(name), pversion(vers)), pack.clone());
- pack
- };
-
- let repo = Repository::from(btree);
- let progress = ProgressBar::hidden();
-
- let mut tree = Tree::default();
- let r = tree.add_package(p1, &repo, progress.clone());
- assert!(r.is_ok());
-
- let r = tree.add_package(p2, &repo, progress);
- assert!(r.is_ok());
- }
-
- #[test]
- fn test_add_two_dependent_packages() {
- let mut btree = BTreeMap::new();
-
- let mut p1 = {
- let name = "a";
- let vers = "1";
- let pack = package(name, vers, "https://rust-lang.org", "123");
- btree.insert((pname(name), pversion(vers)), pack.clone());
- pack
- };
-
- {
- let name = "b";
- let vers = "2";
- let pack = package(name, vers, "https://rust-lang.org", "124");
- btree.insert((pname(name), pversion(vers)), pack);
- }
-
- {
- let d = Dependency::from(String::from("b =2"));
- let ds = Dependencies::with_runtime_dependency(d);
- p1.set_dependencies(ds);
- }
-
- let repo = Repository::from(btree);
- let progress = ProgressBar::hidden();
-
- let mut tree = Tree::default();
- let r = tree.add_package(p1, &repo, progress);
- assert!(r.is_ok());
- assert!(tree.packages().all(|p| *p.name() == pname("a")));
- assert!(tree.packages().all(|p| *p.version() == pversion("1")));
-
- let subtree: Vec<&Tree> = tree.dependencies().collect();
- assert_eq!(subtree.len(), 1);
- let subtree = subtree[0];
- assert!(subtree.packages().all(|p| *p.name() == pname("b")));
- assert!(subtree.packages().all(|p| *p.version() == pversion("2")));
- }
-
- #[test]
- fn test_add_deep_package_tree() {
- let mut btree = BTreeMap::new();
-
- //
- // Test the following (made up) tree:
- //
- // p1
- // - p2
- // - p3
- // - p4
- // - p5
- // - p6
- //
-
- let p1 = {
- let name = "p1";
- let vers = "1";
- let mut pack = package(name, vers, "https://rust-lang.org", "123");
- {
- let d1 = Dependency::from(String::from("p2 =2"));
- let d2 = Dependency::from(String::from("p4 =4"));
- let ds = Dependencies::with_runtime_dependencies(vec![d1, d2]);
- pack.set_dependencies(ds);
- }
- btree.insert((pname(name), pversion(vers)), pack.clone());
- pack
- };
-
- {
- let name = "p2";
- let vers = "2";
- let mut pack = package(name, vers, "https://rust-lang.org", "124");
- {
- let d1 = Dependency::from(String::from("p3 =3"));
- let ds = Dependencies::with_runtime_dependencies(vec![d1]);
- pack.set_dependencies(ds);
- }
- btree.insert((pname(name), pversion(vers)), pack);
- }
-
- {
- let name = "p3";
- let vers = "3";
- let pack = package(name, vers, "https://rust-lang.org", "125");
- btree.insert((pname(name), pversion(vers)), pack);
- }
-
- {
- let name = "p4";
- let vers = "4";
- let mut pack = package(name, vers, "https://rust-lang.org", "125");
- {
- let d1 = Dependency::from(String::from("p5 =5"));
- let d2 = Dependency::from(String::from("p6 =66.6.6"));
- let ds = Dependencies::with_runtime_dependencies(vec![d1, d2]);
- pack.set_dependencies(ds);
- }
- btree.insert((pname(name), pversion(vers)), pack);
- }
-
- {
- let name = "p5";
- let vers = "5";
- let pack = package(name, vers, "https://rust-lang.org", "129");
- btree.insert((pname(name), pversion(vers)), pack);
- }
-
- {
- let name = "p6";
- let vers = "66.6.6";
- let pack = package(name, vers, "https://rust-lang.org", "666");
- btree.insert((pname(name), pversion(vers)), pack);
- }
-
- let repo = Repository::from(btree);
- let progress = ProgressBar::hidden();
-
- let mut tree = Tree::default();
- let r = tree.add_package(p1, &repo, progress);
- assert!(r.is_ok());
- assert!(tree.packages().all(|p| *p.name() == pname("p1")));
- assert!(tree.packages().all(|p| *p.version() == pversion("1")));
-
- let subtrees: Vec<&Tree> = tree.dependencies().collect();
- assert_eq!(subtrees.len(), 1);
-
- let subtree = subtrees[0];
- assert_eq!(subtree.packages().count(), 2);
-
- assert!(subtree
- .packages()
- .all(|p| { *p.name() == pname("p2") || *p.name() == pname("p4") }));
-
- let subsubtrees: Vec<&Tree> = subtree.dependencies().collect();
- assert_eq!(subsubtrees.len(), 2);
-
- assert!(subsubtrees.iter().any(|st| { st.packages().count() == 1 }));
-
- assert!(subsubtrees.iter().any(|st| { st.packages().count() == 2 }));
-
- assert!(subsubtrees
- .iter()
- .any(|st| { st.packages().all(|p| *p.name() == pname("p3")) }));
-
- assert!(subsubtrees.iter().any(|st| {
- st.packages()
- .all(|p| *p.name() == pname("p5") || *p.name() == pname("p6"))
- }));
- }
-
- #[test]
- fn test_add_deep_package_tree_with_irrelevant_packages() {
- // this is the same test as test_add_deep_package_tree(), but with a bunch of irrelevant
- // packages added to the repository, so that we can be sure that the algorithm finds the
- // actually required packages
- //
- // The irrelevant packages are all packages that already exist, but with different versions
-
- let mut btree = BTreeMap::new();
-
- //
- // Test the following (made up) tree:
- //
- // p1
- // - p2
- // - p3
- // - p4
- // - p5
- // - p6
- //
-
- let p1 = {
- let name = "p1";
- let vers = "1";
- let mut pack = package(name, vers, "https://rust-lang.org", "123");
- {
- let d1 = Dependency::from(String::from("p2 =2"));
- let d2 = Dependency::from(String::from("p4 =4"));
- let ds = Dependencies::with_runtime_dependencies(vec![d1, d2]);
- pack.set_dependencies(ds);
- }
- btree.insert((pname(name), pversion(vers)), pack.clone());
- pack
- };
-
- {
- let name = "p1";
- let vers = "2";
- let mut pack = package(name, vers, "https://rust-lang.org", "123");
- {
- let d1 = Dependency::from(String::from("p2 =2"));
- let d2 = Dependency::from(String::from("p4 =5"));
- let ds = Dependencies::with_runtime_dependencies(vec![d1, d2]);
- pack.set_dependencies(ds);
- }
- btree.insert((pname(name), pversion(vers)), pack);
- }
-
- {
- let name = "p2";
- let vers = "2";
- let mut pack = package(name, vers, "https://rust-lang.org", "124");
- {
- let d1 = Dependency::from(String::from("p3 =3"));
- let ds = Dependencies::with_runtime_dependencies(vec![d1]);
- pack.set_dependencies(ds);
- }
- btree.insert((pname(name), pversion(vers)), pack);
- }
-
- {
- let name = "p3";
- let vers = "3";
- let pack = package(name, vers, "https://rust-lang.org", "125");
- btree.insert((pname(name), pversion(vers)), pack);
- }
-
- {
- let name = "p3";
- let vers = "1";
- let pack = package(name, vers, "https://rust-lang.org", "128");
- btree.insert((pname(name), pversion(vers)), pack);
- }
-
- {
- let name = "p3";
- let vers = "3.1";
- let pack = package(name, vers, "https://rust-lang.org", "118");
- btree.insert((pname(name), pversion(vers)), pack);
- }
-
- {
- let name = "p4";
- let vers = "4";
- let mut pack = package(name, vers, "https://rust-lang.org", "125");
- {
- let d1 = Dependency::from(String::from("p5 =5"));
- let d2 = Dependency::from(String::from("p6 =66.6.6"));
- let ds = Dependencies::with_runtime_dependencies(vec![d1, d2]);
- pack.set_dependencies(ds);
- }
- btree.insert((pname(name), pversion(vers)), pack);
- }
-
- {
- let name = "p4";
- let vers = "5";
- let mut pack = package(name, vers, "https://rust-lang.org", "125");
- {
- let d1 = Dependency::from(String::from("p5 =5"));
- let d2 = Dependency::from(String::from("p6 =66.6.8"));
- let ds = Dependencies::with_runtime_dependencies(vec![d1, d2]);
- pack.set_dependencies(ds);
- }
- btree.insert((pname(name), pversion(vers)), pack);
- }
-
- {
- let name = "p5";
- let vers = "5";
- let pack = package(name, vers, "https://rust-lang.org", "129");
- btree.insert((pname(name), pversion(vers)), pack);
- }
-
- {
- let name = "p6";
- let vers = "66.6.6";
- let pack = package(name, vers, "https://rust-lang.org", "666");
- btree.insert((pname(name), pversion(vers)), pack);
- }
-
- {
- let name = "p6";
- let vers = "66.6.8";
- let pack = package(name, vers, "https://rust-lang.org", "666");
- btree.insert((pname(name), pversion(vers)), pack);
- }
-
- let repo = Repository::from(btree);
- let progress = ProgressBar::hidden();
-
- let mut tree = Tree::default();
- let r = tree.add_package(p1, &repo, progress);
- assert!(r.is_ok());
- assert!(tree.packages().all(|p| *p.name() == pname("p1")));
- assert!(tree.packages().all(|p| *p.version() == pversion("1")));
-
- let subtrees: Vec<&Tree> = tree.dependencies().collect();
- assert_eq!(subtrees.len(), 1);
-
- let subtree = subtrees[0];
- assert_eq!(subtree.packages().count(), 2);
-
- assert!(subtree
- .packages()
- .all(|p| { *p.name() == pname("p2") || *p.name() == pname("p4") }));
-
- let subsubtrees: Vec<&Tree> = subtree.dependencies().collect();
- assert_eq!(subsubtrees.len(), 2);
-
- assert!(subsubtrees.iter().any(|st| { st.packages().count() == 1 }));
-
- assert!(subsubtrees.iter().any(|st| { st.packages().count() == 2 }));
-
- assert!(subsubtrees
- .iter()
- .any(|st| { st.packages().all(|p| *p.name() == pname("p3")) }));
-
- assert!(subsubtrees.iter().any(|st| {
- st.packages()
- .all(|p| *p.name() == pname("p5") || *p.name() == pname("p6"))
- }));
- }
-}
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-29 14:49:18 +0000