1 //! Generic graph traits, traversals, and data structures for use in Wasmtime.
2
3 mod dfs;
4 mod entity_graph;
5 mod scc;
6 use core::{fmt, iter};
7
8 pub use dfs::*;
9 pub use entity_graph::*;
10 pub use scc::*;
11
12 use crate::prelude::*;
13
14 /// A trait for any kind of graph data structure.
15 pub trait Graph<Node> {
16 /// The iterator type returned by `Nodes::nodes`.
17 type NodesIter<'a>: Iterator<Item = Node>
18 where
19 Self: 'a;
20
21 /// Iterate over the nodes in this graph.
nodes(&self) -> Self::NodesIter<'_>22 fn nodes(&self) -> Self::NodesIter<'_>;
23
24 /// The iterator type returned by `Successors::successors`.
25 type SuccessorsIter<'a>: Iterator<Item = Node>
26 where
27 Self: 'a;
28
29 /// Iterate over the successors of the given `node`.
successors(&self, node: Node) -> Self::SuccessorsIter<'_>30 fn successors(&self, node: Node) -> Self::SuccessorsIter<'_>;
31
32 // Provided Methods.
33
34 /// Like `Iterator::by_ref` but for `Graph`.
by_ref(&self) -> &Self35 fn by_ref(&self) -> &Self {
36 self
37 }
38
39 /// Use the given predicate to filter out certain nodes from the graph.
filter_nodes<F>(self, predicate: F) -> FilterNodes<Self, F> where Self: Sized, F: Fn(&Node) -> bool,40 fn filter_nodes<F>(self, predicate: F) -> FilterNodes<Self, F>
41 where
42 Self: Sized,
43 F: Fn(&Node) -> bool,
44 {
45 FilterNodes {
46 graph: self,
47 predicate,
48 }
49 }
50 }
51
52 impl<T, Node> Graph<Node> for &'_ T
53 where
54 T: ?Sized + Graph<Node>,
55 {
56 type NodesIter<'a>
57 = T::NodesIter<'a>
58 where
59 Self: 'a;
60
nodes(&self) -> Self::NodesIter<'_>61 fn nodes(&self) -> Self::NodesIter<'_> {
62 (*self).nodes()
63 }
64
65 type SuccessorsIter<'a>
66 = T::SuccessorsIter<'a>
67 where
68 Self: 'a;
69
successors(&self, node: Node) -> Self::SuccessorsIter<'_>70 fn successors(&self, node: Node) -> Self::SuccessorsIter<'_> {
71 (*self).successors(node)
72 }
73 }
74
75 /// A graph whose nodes are being filtered by the predicate `F`.
76 ///
77 /// Created by the `Graph::filter_nodes` trait method.
78 pub struct FilterNodes<G, F> {
79 graph: G,
80 predicate: F,
81 }
82
83 impl<G, F> fmt::Debug for FilterNodes<G, F>
84 where
85 G: fmt::Debug,
86 {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result87 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
88 f.debug_struct("Filter")
89 .field("graph", &self.graph)
90 .field("predicate", &"..")
91 .finish()
92 }
93 }
94
95 impl<G, F, Node> Graph<Node> for FilterNodes<G, F>
96 where
97 G: Graph<Node>,
98 F: Fn(&Node) -> bool,
99 {
100 type NodesIter<'a>
101 = iter::Filter<G::NodesIter<'a>, &'a F>
102 where
103 Self: 'a;
104
nodes(&self) -> Self::NodesIter<'_>105 fn nodes(&self) -> Self::NodesIter<'_> {
106 self.graph.nodes().filter(&self.predicate)
107 }
108
109 type SuccessorsIter<'a>
110 = iter::Filter<G::SuccessorsIter<'a>, &'a F>
111 where
112 Self: 'a;
113
successors(&self, node: Node) -> Self::SuccessorsIter<'_>114 fn successors(&self, node: Node) -> Self::SuccessorsIter<'_> {
115 self.graph.successors(node).filter(&self.predicate)
116 }
117 }
118
119 /// Extend `dest` with `items` and return the range of indices in `dest` where
120 /// they ended up.
extend_with_range<T>( dest: &mut Vec<T>, items: impl IntoIterator<Item = T>, ) -> core::ops::Range<u32>121 fn extend_with_range<T>(
122 dest: &mut Vec<T>,
123 items: impl IntoIterator<Item = T>,
124 ) -> core::ops::Range<u32> {
125 let start = dest.len();
126 let start = u32::try_from(start).unwrap();
127
128 dest.extend(items);
129
130 let end = dest.len();
131 let end = u32::try_from(end).unwrap();
132
133 start..end
134 }
135