workspace_node_tools/
dependency.rs

1use petgraph::{stable_graph::StableDiGraph, Direction};
2
3/// Must be implemented by the type you wish
4/// to build a dependency graph for. See the README.md for an example
5pub trait Node {
6    /// Encodes a dependency relationship. In a Package Manager dependency graph for intance, this might be a (package name, version) tuple.
7    /// It might also just be the exact same type as the one that implements the Node trait, in which case `Node::matches` can be implemented through simple equality.
8    type DependencyType;
9
10    /// Returns a slice of dependencies for this Node
11    fn dependencies(&self) -> &[Self::DependencyType];
12
13    /// Returns true if the `dependency` can be met by us.
14    fn matches(&self, dependency: &Self::DependencyType) -> bool;
15}
16
17/// Wrapper around dependency graph nodes.
18/// Since a graph might have dependencies that cannot be resolved internally,
19/// this wrapper is necessary to differentiate between internally resolved and
20/// externally (unresolved) dependencies.
21/// An Unresolved dependency does not necessarily mean that it *cannot* be resolved,
22/// only that no Node within the graph fulfills it.
23pub enum Step<'a, N: Node> {
24    Resolved(&'a N),
25    Unresolved(&'a N::DependencyType),
26}
27
28impl<'a, N: Node> Step<'a, N> {
29    pub fn is_resolved(&self) -> bool {
30        match self {
31            Step::Resolved(_) => true,
32            Step::Unresolved(_) => false,
33        }
34    }
35
36    pub fn as_resolved(&self) -> Option<&N> {
37        match self {
38            Step::Resolved(node) => Some(node),
39            Step::Unresolved(_) => None,
40        }
41    }
42
43    pub fn as_unresolved(&self) -> Option<&N::DependencyType> {
44        match self {
45            Step::Resolved(_) => None,
46            Step::Unresolved(dependency) => Some(dependency),
47        }
48    }
49}
50
51/// The [`DependencyGraph`] structure builds an internal [Directed Graph](`petgraph::stable_graph::StableDiGraph`), which can then be traversed
52/// in an order which ensures that dependent Nodes are visited before their parents.
53pub struct DependencyGraph<'a, N: Node> {
54    graph: StableDiGraph<Step<'a, N>, &'a N::DependencyType>,
55}
56
57/// The only way to build a [`DependencyGraph`] is from a slice of objects implementing [`Node`].
58/// The graph references the original items, meaning the objects cannot be modified while
59/// the [`DependencyGraph`] holds a reference to them.
60impl<'a, N> From<&'a [N]> for DependencyGraph<'a, N>
61where
62    N: Node,
63{
64    fn from(nodes: &'a [N]) -> Self {
65        let mut graph = StableDiGraph::<Step<'a, N>, &'a N::DependencyType>::new();
66
67        // Insert the input nodes into the graph, and record their positions.
68        // We'll be adding the edges next, and filling in any unresolved
69        // steps we find along the way.
70        let nodes: Vec<(_, _)> = nodes
71            .iter()
72            .map(|node| (node, graph.add_node(Step::Resolved(node))))
73            .collect();
74
75        for (node, index) in nodes.iter() {
76            for dependency in node.dependencies() {
77                // Check to see if we can resolve this dependency internally.
78                if let Some((_, dependent)) = nodes.iter().find(|(dep, _)| dep.matches(dependency))
79                {
80                    // If we can, just add an edge between the two nodes.
81                    graph.add_edge(*index, *dependent, dependency);
82                } else {
83                    // If not, create a new "Unresolved" node, and create an edge to that.
84                    let unresolved = graph.add_node(Step::Unresolved(dependency));
85                    graph.add_edge(*index, unresolved, dependency);
86                }
87            }
88        }
89
90        Self { graph }
91    }
92}
93
94impl<'a, N> DependencyGraph<'a, N>
95where
96    N: Node,
97{
98    /// True if all graph [`Node`]s have only references to other internal [`Node`]s.
99    /// That is, there are no unresolved dependencies between nodes.
100    pub fn is_internally_resolvable(&self) -> bool {
101        self.graph.node_weights().all(Step::is_resolved)
102    }
103
104    /// Get an iterator over unresolved dependencies, without traversing the whole graph.
105    /// Useful for doing pre-validation or pre-fetching of external dependencies before
106    /// starting to resolve internal dependencies.
107    pub fn unresolved_dependencies(&self) -> impl Iterator<Item = &N::DependencyType> {
108        self.graph.node_weights().filter_map(Step::as_unresolved)
109    }
110}
111
112/// Iterate over the DependencyGraph in an order which ensures dependencies are resolved before each Node is visited.
113/// Note: If a `Step::Unresolved` node is returned, it is the caller's responsibility to ensure the dependency is resolved
114/// before continuing.
115impl<'a, N> Iterator for DependencyGraph<'a, N>
116where
117    N: Node,
118{
119    type Item = Step<'a, N>;
120
121    fn next(&mut self) -> Option<Self::Item> {
122        // Returns the first node, which does not have any Outgoing
123        // edges, which means it is terminal.
124        for index in self.graph.node_indices().rev() {
125            if self
126                .graph
127                .neighbors_directed(index, Direction::Outgoing)
128                .count()
129                == 0
130            {
131                return self.graph.remove_node(index);
132            }
133        }
134
135        None
136    }
137}
138
139#[cfg(test)]
140mod tests {
141
142    use super::{DependencyGraph, Node, Step};
143    use semver::{BuildMetadata, Prerelease, Version, VersionReq};
144
145    #[derive(Debug)]
146    struct Package {
147        name: &'static str,
148        version: Version,
149        dependencies: Vec<Dependency>,
150    }
151
152    #[derive(Debug)]
153    struct Dependency {
154        name: &'static str,
155        version: VersionReq,
156    }
157
158    impl Node for Package {
159        type DependencyType = Dependency;
160
161        fn dependencies(&self) -> &[Self::DependencyType] {
162            &self.dependencies[..]
163        }
164
165        fn matches(&self, dependency: &Self::DependencyType) -> bool {
166            self.name == dependency.name && dependency.version.matches(&self.version)
167        }
168    }
169
170    #[test]
171    fn test_dependencies_synchronous() {
172        let build = build_test_graph();
173        let graph = DependencyGraph::from(&build[..]);
174
175        assert!(!graph.is_internally_resolvable());
176
177        for node in graph {
178            match node {
179                Step::Resolved(build) => println!("build: {:?}", build.name),
180                Step::Unresolved(lookup) => println!("lookup: {:?}", lookup.name),
181            }
182        }
183    }
184
185    #[test]
186    fn test_unresolved_dependencies() {
187        let build = build_test_graph();
188        let graph = DependencyGraph::from(&build[..]);
189
190        assert!(!graph.is_internally_resolvable());
191
192        let unresolved_dependencies: Vec<_> = graph
193            .unresolved_dependencies()
194            .map(|dep| dep.name)
195            .collect();
196
197        assert_eq!(
198            unresolved_dependencies,
199            vec!["@scope/unknown", "@scope/remote"]
200        );
201    }
202
203    #[test]
204    fn test_generate_dependency_graph() {
205        let _ = DependencyGraph::from(&build_test_graph()[..]);
206    }
207
208    fn build_test_graph() -> Vec<Package> {
209        vec![
210            Package {
211                name: "@scope/package-a",
212                version: semver::Version {
213                    major: 1,
214                    minor: 2,
215                    patch: 3,
216                    pre: Prerelease::new("").unwrap(),
217                    build: BuildMetadata::EMPTY,
218                },
219                dependencies: vec![],
220            },
221            Package {
222                name: "@scope/package-b",
223                version: semver::Version {
224                    major: 1,
225                    minor: 2,
226                    patch: 3,
227                    pre: Prerelease::new("").unwrap(),
228                    build: BuildMetadata::EMPTY,
229                },
230                dependencies: vec![Dependency {
231                    name: "@scope/package-a",
232                    version: ">=1.0.0".parse().unwrap(),
233                }],
234            },
235            Package {
236                name: "@scope/package-c",
237                version: semver::Version {
238                    major: 1,
239                    minor: 2,
240                    patch: 3,
241                    pre: Prerelease::new("").unwrap(),
242                    build: BuildMetadata::EMPTY,
243                },
244                dependencies: vec![Dependency {
245                    name: "@scope/package-b",
246                    version: ">=1.0.0".parse().unwrap(),
247                }],
248            },
249            Package {
250                name: "@scope/package-d",
251                version: semver::Version {
252                    major: 1,
253                    minor: 2,
254                    patch: 3,
255                    pre: Prerelease::new("").unwrap(),
256                    build: BuildMetadata::EMPTY,
257                },
258                dependencies: vec![
259                    Dependency {
260                        name: "@scope/package-a",
261                        version: ">=1.0.0".parse().unwrap(),
262                    },
263                    Dependency {
264                        name: "@scope/package-b",
265                        version: ">=1.0.0".parse().unwrap(),
266                    },
267                ],
268            },
269            Package {
270                name: "@scope/package-e",
271                version: semver::Version {
272                    major: 1,
273                    minor: 2,
274                    patch: 3,
275                    pre: Prerelease::new("").unwrap(),
276                    build: BuildMetadata::EMPTY,
277                },
278                dependencies: vec![],
279            },
280            Package {
281                name: "@scope/package-f",
282                version: semver::Version {
283                    major: 1,
284                    minor: 2,
285                    patch: 3,
286                    pre: Prerelease::new("").unwrap(),
287                    build: BuildMetadata::EMPTY,
288                },
289                dependencies: vec![
290                    Dependency {
291                        name: "@scope/unknown",
292                        version: ">=1.0.0".parse().unwrap(),
293                    },
294                    Dependency {
295                        name: "@scope/remote",
296                        version: "=3.0.0".parse().unwrap(),
297                    },
298                ],
299            },
300        ]
301    }
302
303    #[test]
304    fn test_internally_resolved() {
305        let packages = vec![
306            Package {
307                name: "@scope/package-a",
308                version: semver::Version {
309                    major: 1,
310                    minor: 2,
311                    patch: 3,
312                    pre: Prerelease::new("").unwrap(),
313                    build: BuildMetadata::EMPTY,
314                },
315                dependencies: vec![],
316            },
317            Package {
318                name: "@scope/package-b",
319                version: semver::Version {
320                    major: 3,
321                    minor: 2,
322                    patch: 0,
323                    pre: Prerelease::new("").unwrap(),
324                    build: BuildMetadata::EMPTY,
325                },
326                dependencies: vec![Dependency {
327                    name: "@scope/package-a",
328                    version: "=1.2.3".parse().unwrap(),
329                }],
330            },
331            Package {
332                name: "@scope/package-c",
333                version: semver::Version {
334                    major: 11,
335                    minor: 2,
336                    patch: 4,
337                    pre: Prerelease::new("").unwrap(),
338                    build: BuildMetadata::EMPTY,
339                },
340                dependencies: vec![Dependency {
341                    name: "@scope/package-b",
342                    version: ">=3.0.0".parse().unwrap(),
343                }],
344            },
345        ];
346
347        let graph = DependencyGraph::from(&packages[..]);
348
349        for package in graph {
350            match package {
351                // Print out the package name so we can verify the order ourselves
352                Step::Resolved(package) => println!("Building {}!", package.name),
353
354                // Since we know that all our Packages only have internal references to each other,
355                // we can safely ignore any Unresolved steps in the graph.
356                //
357                // If for example `second_order` required some unknown package `external_package`,
358                // iterating over our graph would yield that as a Step::Unresolved *before*
359                // the `second_order` package.
360                Step::Unresolved(_) => unreachable!(),
361            }
362        }
363    }
364}
workspace_node_tools/dependency.rs

workspace_node_tools/
dependency.rs
