Rewrite package organizational structure using DAG

This patch reimplements the package orchestration functionality to rely
on a DAG rather than a tree.

        A
       / \
      B   E
     / \   \
    C   D   F

Before this change, the structure the packages were organized in for a
build was a tree.
That did work reasonable well for initial development of butido, because
this is a simple case and the implementation is rather simple, too.

But, packages and their dependencies are not always organized in a tree.
Most of the time, they are organized in a DAG:

      .-> C -,
     /        \
    D          > A
     \        /
      `-> B -´

This is a real-world example: A could be a common crypto-library that I
do not want to name here.
B and C could be libraries that use the said crypto-library and D could
be a program that use B and C.
Because said crypto-library builds rather long, building it twice and
throwing one result away is a no-go.
A DAG as organizational structure makes that issue go away entirely.

Also, we can later implement checks whether the DAG contains multiple
versions of the same library, if that is undesireable.

The change itself is rather big, frankly because it is a non-trivial
change the replace the whole data structure and its handling in the
orchestrator code.

First of all, we introduce the "daggy" library, which provides the DAG
implementation on top of the popular "petgraph" library.

The package `Tree` datastructure was replaced by a package `Dag`
datastructure. This type implements the heavy-lifting that is needed to
load a package and all its dependencies from the `Repository` object.

The `JobTree` was also reimplemented, but as `daggy::Dag` provides a
convenient `map()` function, its implementation which transforms the
package `Dag` into a job `Dag` is rather trivial.
`crate::job::Dag` then provides the convenience `iter()` function to
iterate over all elements in the DAG and providing a `JobDefinition`
object for each node.
The topology in which we traverse the DAG is not an issue, as we need to
create tasks for all `JobDefinition`s anyways, so we do not care about
traversal topology at all.

The `crate::package::Package` type got an `Hash` implementation, which
is necessary to keep track of the mappings while reading the DAG from
the repository.
The implementation does not create the edges between the nodes in the
DAG right when inserting, but afterwards.
To keep track of the `daggy::NodeIndex`es, it keeps a mapping

    Package -> NodeIndex

in a Hashmap. Thus, `Package` must implement `std::hash::Hash`

Signed-off-by: Matthias Beyer <mail@beyermatthias.de>
Tested-by: Matthias Beyer <mail@beyermatthias.de>

squash! Reimplement as DAG

11 files changed, 276 insertions, 675 deletions

diff --git a/Cargo.toml b/Cargo.toml
index b2dc1dc..52c0122 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -21,6 +21,7 @@ clap_generate  = "3.0.0-beta.2"
 colored        = "2"
 config         = "0.10"
 csv            = "1.1"
+daggy          = { version = "0.7", features = [ "serde" ] }
 diesel         = { version = "1.4", features = ["postgres", "chrono", "uuid", "serde_json"] }
 env_logger     = "0.8"
 filters        = "0.4.0"
diff --git a/src/commands/build.rs b/src/commands/build.rs
index b1d3e58..f5c9b5a 100644
--- a/src/commands/build.rs
+++ b/src/commands/build.rs
@@ -38,7 +38,7 @@ use crate::orchestrator::OrchestratorSetup;
 use crate::package::PackageName;
 use crate::package::PackageVersion;
 use crate::package::Shebang;
-use crate::package::Tree;
+use crate::package::Dag;
 use crate::repository::Repository;
 use crate::schema;
 use crate::source::SourceCache;
@@ -195,15 +195,12 @@ pub async fn build(
         r.map(RwLock::new).map(Arc::new).map(|store| (store, p))?
     };
 
-    let tree = {
+    let dag = {
         let bar_tree_building = progressbars.bar();
         bar_tree_building.set_length(max_packages);
-
-        let mut tree = Tree::default();
-        tree.add_package(package.clone(), &repo, bar_tree_building.clone())?;
-
-        bar_tree_building.finish_with_message("Finished loading Tree");
-        tree
+        let dag = Dag::for_root_package(package.clone(), &repo, bar_tree_building.clone())?;
+        bar_tree_building.finish_with_message("Finished loading Dag");
+        dag
     };
 
     let source_cache = SourceCache::new(config.source_cache_root().clone());
@@ -212,7 +209,7 @@ pub async fn build(
         warn!("No hash verification will be performed");
     } else {
         crate::commands::source::verify_impl(
-            tree.all_packages().into_iter(),
+            dag.all_packages().into_iter(),
             &source_cache,
             &progressbars,
         )
@@ -223,7 +220,7 @@ pub async fn build(
     if matches.is_present("no_lint") {
         warn!("No script linting will be performed!");
     } else if let Some(linter) = crate::ui::find_linter_command(repo_root, config)? {
-        let all_packages = tree.all_packages();
+        let all_packages = dag.all_packages();
         let bar = progressbars.bar();
         bar.set_length(all_packages.len() as u64);
         bar.set_message("Linting package scripts...");
@@ -234,7 +231,7 @@ pub async fn build(
         warn!("No linter set in configuration, no script linting will be performed!");
     } // linting
 
-    tree.all_packages()
+    dag.all_packages()
         .into_iter()
         .map(|pkg| {
             if let Some(allowlist) = pkg.allowed_images() {
@@ -304,7 +301,7 @@ pub async fn build(
 
     trace!("Setting up job sets");
     let resources: Vec<JobResource> = additional_env.into_iter().map(JobResource::from).collect();
-    let jobtree = crate::job::Tree::from_package_tree(tree, shebang, image_name, phases.clone(), resources);
+    let jobdag = crate::job::Dag::from_package_dag(dag, shebang, image_name, phases.clone(), resources);
     trace!("Setting up job sets finished successfully");
 
     trace!("Setting up Orchestrator");
@@ -322,7 +319,7 @@ pub async fn build(
         } else {
             None
         })
-        .jobtree(jobtree)
+        .jobdag(jobdag)
         .config(config)
         .build()
         .setup()
diff --git a/src/commands/tree_of.rs b/src/commands/tree_of.rs
index f07a303..df3a6cf 100644
--- a/src/commands/tree_of.rs
+++ b/src/commands/tree_of.rs
@@ -15,7 +15,7 @@ use resiter::AndThen;
 
 use crate::package::PackageName;
 use crate::package::PackageVersionConstraint;
-use crate::package::Tree;
+use crate::package::Dag;
 use crate::repository::Repository;
 use crate::util::progress::ProgressBars;
 
@@ -45,8 +45,7 @@ pub async fn tree_of(
         })
         .map(|package| {
             let bar_tree_building = progressbars.bar();
-            let mut tree = Tree::default();
-            let _ = tree.add_package(package.clone(), &repo, bar_tree_building.clone())?;
+            let tree = Dag::for_root_package(package.clone(), &repo, bar_tree_building.clone())?;
             bar_tree_building.finish_with_message("Finished loading Tree");
             Ok(tree)
         })
@@ -54,9 +53,7 @@ pub async fn tree_of(
             let stdout = std::io::stdout();
             let mut outlock = stdout.lock();
 
-            tree.display()
-                .iter()
-                .try_for_each(|d| ptree::write_tree(d, &mut outlock).map_err(Error::from))
+            ptree::write_tree(&tree.display(), &mut outlock).map_err(Error::from)
         })
         .collect::<Result<()>>()
 }
diff --git a/src/job/dag.rs b/src/job/dag.rs
new file mode 100644
index 0000000..ebc49e2
--- /dev/null
+++ b/src/job/dag.rs
@@ -0,0 +1,86 @@
+//
+// 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 daggy::Dag as DaggyDag;
+use daggy::NodeIndex;
+use daggy::Walker;
+use getset::Getters;
+use uuid::Uuid;
+
+use crate::job::Job;
+use crate::job::JobResource;
+use crate::package::Package;
+use crate::package::PhaseName;
+use crate::package::Shebang;
+use crate::util::docker::ImageName;
+
+#[derive(Debug, Getters)]
+pub struct Dag {
+    #[getset(get = "pub")]
+    dag: DaggyDag<Job, i8>,
+
+    #[getset(get = "pub")]
+    root_idx: NodeIndex,
+}
+
+impl Dag {
+    pub fn from_package_dag(
+        dag: crate::package::Dag,
+        script_shebang: Shebang,
+        image: ImageName,
+        phases: Vec<PhaseName>,
+        resources: Vec<JobResource>,
+    ) -> Self {
+        let build_job = |_, p: &Package| {
+            Job::new(
+                p.clone(),
+                script_shebang.clone(),
+                image.clone(),
+                phases.clone(),
+                resources.clone(),
+            )
+        };
+
+        Dag {
+            dag: dag.dag().map(build_job, |_, e| *e),
+            root_idx: *dag.root_idx(),
+        }
+    }
+
+    pub fn iter<'a>(&'a self) -> impl Iterator<Item = JobDefinition> + 'a {
+        self.dag
+            .graph()
+            .node_indices()
+            .map(move |idx| {
+                let job = self.dag.graph().node_weight(idx).unwrap(); // TODO
+                let children = self.dag.children(idx);
+                let children_uuids = children.iter(&self.dag)
+                    .filter_map(|(_, node_idx)| {
+                        self.dag.graph().node_weight(node_idx)
+                    })
+                    .map(Job::uuid)
+                    .cloned()
+                    .collect();
+
+                JobDefinition {
+                    job,
+                    dependencies: children_uuids
+                }
+            })
+    }
+
+}
+
+#[derive(Debug)]
+pub struct JobDefinition<'a> {
+    pub job: &'a Job,
+    pub dependencies: Vec<Uuid>,
+}
+
diff --git a/src/job/mod.rs b/src/job/mod.rs
index e684935..666f42e 100644
--- a/src/job/mod.rs
+++ b/src/job/mod.rs
@@ -12,8 +12,8 @@
 mod job;
 pub use job::*;
 
-mod tree;
-pub use tree::*;
+mod dag;
+pub use dag::*;
 
 mod resource;
 pub use resource::*;
diff --git a/src/job/tree.rs b/src/job/tree.rs
deleted file mode 100644
index d7c0751..0000000
--- a/src/job/tree.rs
+++ /dev/null
@@ -1,80 +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::collections::BTreeMap;
-
-use uuid::Uuid;
-use getset::Getters;
-
-use crate::job::Job;
-use crate::job::JobResource;
-use crate::package::PhaseName;
-use crate::package::Shebang;
-use crate::util::docker::ImageName;
-
-#[derive(Debug, Getters)]
-pub struct Tree {
-    #[getset(get = "pub")]
-    inner: BTreeMap<Uuid, JobDefinition>,
-}
-
-impl Tree {
-    pub fn from_package_tree(pt: crate::package::Tree,
-        script_shebang: Shebang,
-        image: ImageName,
-        phases: Vec<PhaseName>,
-        resources: Vec<JobResource>,
-    ) -> Self {
-        Tree { inner: Self::build_tree(pt, script_shebang, image, phases, resources) }
-    }
-
-    fn build_tree(pt: crate::package::Tree,
-        script_shebang: Shebang,
-        image: ImageName,
-        phases: Vec<PhaseName>,
-        resources: Vec<JobResource>,
-    ) -> BTreeMap<Uuid, JobDefinition> {
-        let mut tree = BTreeMap::new();
-
-        for (package, dependencies) in pt.into_iter() {
-            let mut deps = Self::build_tree(dependencies,
-                script_shebang.clone(),
-                image.clone(),
-                phases.clone(),
-                resources.clone());
-
-            let deps_uuids = deps.keys().cloned().collect();
-            tree.append(&mut deps);
-
-            let job = Job::new(package,
-                script_shebang.clone(),
-                image.clone(),
-                phases.clone(),
-                resources.clone());
-
-            let job_uuid = *job.uuid();
-            let jdef = JobDefinition { job, dependencies: deps_uuids };
-
-            tree.insert(job_uuid, jdef);
-        }
-
-        tree
-    }
-
-}
-
-/// A job definition is the job itself and all UUIDs from jobs this job depends on.
-#[derive(Debug)]
-pub struct JobDefinition {
-    pub job: Job,
-
-    /// Uuids of the jobs where this job depends on the outputs
-    pub dependencies: Vec<Uuid>,
-}
diff --git a/src/orchestrator/orchestrator.rs b/src/orchestrator/orchestrator.rs
index cedc549..bed2195 100644
--- a/src/orchestrator/orchestrator.rs
+++ b/src/orchestrator/orchestrator.rs
@@ -37,7 +37,7 @@ use crate::filestore::ReleaseStore;
 use crate::filestore::StagingStore;
 use crate::job::JobDefinition;
 use crate::job::RunnableJob;
-use crate::job::Tree as JobTree;
+use crate::job::Dag;
 use crate::source::SourceCache;
 use crate::util::progress::ProgressBars;
 
@@ -45,7 +45,7 @@ use crate::util::progress::ProgressBars;
 /// The Orchestrator
 ///
 /// The Orchestrator is used to orchestrate the work on one submit.
-/// On a very high level: It uses a [JobTree](crate::job::Tree) to build a number (list) of
+/// On a very high level: It uses a [Dag](crate::job::Dag) to build a number (list) of
 /// [JobTasks](crate::orchestrator::JobTask) that is then run concurrently.
 ///
 /// Because of the implementation of [JobTask], the work happens in
@@ -153,7 +153,7 @@ pub struct Orchestrator<'a> {
     progress_generator: ProgressBars,
     merged_stores: MergedStores,
     source_cache: SourceCache,
-    jobtree: JobTree,
+    jobdag: Dag,
     config: &'a Configuration,
     database: Arc<PgConnection>,
 }
@@ -165,7 +165,7 @@ pub struct OrchestratorSetup<'a> {
     staging_store: Arc<RwLock<StagingStore>>,
     release_store: Arc<RwLock<ReleaseStore>>,
     source_cache: SourceCache,
-    jobtree: JobTree,
+    jobdag: Dag,
     database: Arc<PgConnection>,
     submit: dbmodels::Submit,
     log_dir: Option<PathBuf>,
@@ -188,7 +188,7 @@ impl<'a> OrchestratorSetup<'a> {
             progress_generator: self.progress_generator,
             merged_stores: MergedStores::new(self.release_store, self.staging_store),
             source_cache: self.source_cache,
-            jobtree: self.jobtree,
+            jobdag: self.jobdag,
             config: self.config,
             database: self.database,
         })
@@ -214,7 +214,7 @@ impl<'a> Orchestrator<'a> {
     async fn run_tree(self) -> Result<(Vec<Artifact>, Vec<(Uuid, Error)>)> {
         let multibar = Arc::new(indicatif::MultiProgress::new());
 
-        // For each job in the jobtree, built a tuple with
+        // For each job in the jobdag, built a tuple with
         //
         // 1. The receiver that is used by the task to receive results from dependency tasks from
         // 2. The task itself (as a TaskPreparation object)
@@ -223,16 +223,15 @@ impl<'a> Orchestrator<'a> {
         //    This is an Option<> because we need to set it later and the root of the tree needs a
         //    special handling, as this very function will wait on a receiver that gets the results
         //    of the root task
-        let jobs: Vec<(Receiver<JobResult>, TaskPreparation, Sender<JobResult>, _)> = self.jobtree
-            .inner()
+        let jobs: Vec<(Receiver<JobResult>, TaskPreparation, Sender<JobResult>, _)> = self.jobdag
             .iter()
-            .map(|(uuid, jobdef)| {
+            .map(|jobdef| {
                 // We initialize the channel with 100 elements here, as there is unlikely a task
                 // that depends on 100 other tasks.
                 // Either way, this might be increased in future.
                 let (sender, receiver) = tokio::sync::mpsc::channel(100);
 
-                trace!("Creating TaskPreparation object for job {}", uuid);
+                trace!("Creating TaskPreparation object for job {}", jobdef.job.uuid());
                 let bar = self.progress_generator.bar();
                 let bar = multibar.add(bar);
                 bar.set_length(100);
@@ -337,8 +336,7 @@ impl<'a> Orchestrator<'a> {
 ///
 /// This simply holds data and does not contain any more functionality
 struct TaskPreparation<'a> {
-    /// The UUID of this job
-    jobdef: &'a JobDefinition,
+    jobdef: JobDefinition<'a>,
 
     bar: ProgressBar,
 
@@ -353,8 +351,7 @@ struct TaskPreparation<'a> {
 ///
 /// This type represents a task for a job that can immediately be executed (see `JobTask::run()`).
 struct JobTask<'a> {
-    /// The UUID of this job
-    jobdef: &'a JobDefinition,
+    jobdef: JobDefinition<'a>,
 
     bar: ProgressBar,
 
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]);