dep_tree/
lib.rs

1use std::{
2  cell::RefCell,
3  collections::{btree_map::Entry, BTreeMap, BTreeSet},
4  rc::Rc,
5};
6use thiserror::Error;
7
8pub type DepId = (u64, usize);
9
10#[derive(Clone, Debug, Error)]
11pub enum DepTreeBuilderError {
12  #[error("unit `{0:?}` depends on itself")]
13  SelfDependency(DepId),
14  #[error("unit `{0:?}` recurses when depending on `{1:?}`, `{2}`")]
15  CircularDependency(DepId, DepId, String),
16}
17
18pub type DepTreeBuilderResult<T> = Result<T, DepTreeBuilderError>;
19
20#[derive(Clone, Debug, Default)]
21pub struct DepTreeBuilder {
22  inner: Rc<RefCell<Box<BTreeMap<DepId, Vec<DepId>>>>>,
23}
24
25impl DepTreeBuilder {
26  pub fn new() -> Self {
27    Self::default()
28  }
29
30  pub fn with_dep(&mut self, id: DepId, deps: Vec<DepId>) -> Self {
31    let mut inner_lock = self.inner.try_borrow_mut().unwrap();
32    match inner_lock.entry(id) {
33      Entry::Vacant(entry) => {
34        entry.insert(deps);
35      }
36      Entry::Occupied(mut entry) => {
37        entry.get_mut().extend(deps);
38      }
39    }
40    self.clone()
41  }
42  
43  pub fn build(self) -> DepTreeBuilderResult<Box<DepTree>> {
44    let inner = self.inner.try_borrow().unwrap();
45    let (mut visited, mut resolved): (
46      Vec<DepId>,
47      BTreeMap<DepId, Vec<DepId>>,
48    ) = (
49      Vec::new(),
50      BTreeMap::new(),
51    );
52    for (unit, deps) in inner.clone().into_iter() {
53      if deps.contains(&unit) {
54        return Err(DepTreeBuilderError::SelfDependency(unit));
55      }
56      let mut stack = Vec::new();
57      if self.has_circular_dependency(unit, &inner, &mut visited, &mut stack) {
58        return Err(DepTreeBuilderError::CircularDependency(
59          *stack.first().unwrap(),
60          *stack.last().unwrap(),
61          stack
62            .iter()
63            .map(|(id, version)| format!("({id}, {version})"))
64            .collect::<Vec<_>>()
65            .join(" -> ")
66        ));
67      }
68      resolved.insert(unit, deps);
69    }
70    Ok(Box::new(DepTree::new(Rc::new(resolved))))
71  }
72
73  fn has_circular_dependency(
74    &self,
75    unit: DepId,
76    tree: &BTreeMap<DepId, Vec<DepId>>,
77    visited: &mut Vec<DepId>,
78    stack: &mut Vec<DepId>,
79  ) -> bool {
80    if visited.contains(&unit) {
81      return false;
82    }
83    if stack.contains(&unit) {
84      return true;
85    }
86    stack.push(unit);
87    if let Some(deps) = tree.get(&unit) {
88      for &dep in deps {
89        if self.has_circular_dependency(dep, tree, visited, stack) {
90          return true;
91        }
92      }
93    }
94    stack.pop();
95    visited.push(unit);
96    false
97  }
98}
99
100#[derive(Clone, Debug, Default)]
101pub struct DepTree {
102  inner: Rc<BTreeMap<DepId, Vec<DepId>>>,
103}
104
105impl DepTree {
106  pub fn new(inner: Rc<BTreeMap<DepId, Vec<DepId>>>) -> Self {
107    Self { inner }
108  }
109  
110  pub fn most_dependencies(&self) -> Vec<(DepId, usize)> {
111    let mut dependency_counts = self.inner.keys().map(|id| {
112      let count = self.count_dependencies(id, &mut BTreeSet::new());
113      (*id, count)
114    }).collect::<Vec<_>>();
115
116    dependency_counts.sort_by(|a, b| b.1.cmp(&a.1));
117    dependency_counts
118  }
119
120  pub fn most_dependents(&self) -> Vec<(DepId, usize)> {
121    let mut dependent_counts = self.calculate_dependents();
122    dependent_counts.sort_by(|a, b| b.1.cmp(&a.1));
123    dependent_counts
124  }
125
126  pub fn least_dependencies(&self) -> Vec<(DepId, usize)> {
127    let mut dependency_counts = self.inner.keys().map(|id| {
128      let count = self.count_dependencies(id, &mut BTreeSet::new());
129      (*id, count)
130    }).collect::<Vec<_>>();
131
132    dependency_counts.sort_by(|a, b| a.1.cmp(&b.1));
133    dependency_counts
134  }
135
136  pub fn least_dependents(&self) -> Vec<(DepId, usize)> {
137    let mut dependent_counts = self.calculate_dependents();
138    dependent_counts.sort_by(|a, b| a.1.cmp(&b.1));
139    dependent_counts
140  }
141
142  pub fn dependencies_of(&self, unit: DepId) -> Vec<DepId> {
143    let mut visited = BTreeSet::new();
144    let mut dependencies = Vec::new();
145    self.collect_dependencies(&unit, &mut visited, &mut dependencies);
146    dependencies
147  }
148
149  pub fn dependents_of(&self, unit: DepId) -> Vec<DepId> {
150    self.inner
151      .iter()
152      .filter_map(|(&key, deps)| {
153        if deps.contains(&unit) {
154          Some(key)
155        } else {
156          None
157        }
158      })
159      .collect()
160  }
161
162  fn count_dependencies(&self, id: &DepId, visited: &mut BTreeSet<DepId>) -> usize {
163    if !visited.insert(*id) {
164      return 0;
165    }
166    self.inner
167      .get(id)
168      .map(|deps| {
169        deps
170          .iter()
171          .map(|dep| 1 + self.count_dependencies(dep, visited))
172          .sum()
173      })
174      .unwrap_or(0)
175  }
176
177  fn collect_dependencies(&self, id: &DepId, visited: &mut BTreeSet<DepId>, dependencies: &mut Vec<DepId>) {
178    if !visited.insert(*id) {
179      return;
180    }
181    if let Some(deps) = self.inner.get(id) {
182      for dep in deps {
183        dependencies.push(*dep);
184        self.collect_dependencies(dep, visited, dependencies);
185      }
186    }
187  }
188
189  fn calculate_dependents(&self) -> Vec<(DepId, usize)> {
190    let mut dependent_map: BTreeMap<DepId, usize> = BTreeMap::new();
191    
192    for (&key, deps) in self.inner.iter() {
193      for &dep in deps {
194        *dependent_map.entry(dep).or_insert(0) += 1;
195      }
196      dependent_map.entry(key).or_insert(0);
197    }
198
199    dependent_map.into_iter().collect()
200  }
201}
dep_tree/lib.rs

dep_tree/
lib.rs
