wasmtime_environ/
graphs.rs

1//! Generic graph traits, traversals, and data structures for use in Wasmtime.
2
3mod dfs;
4mod entity_graph;
5mod scc;
6use core::{fmt, iter};
7
8pub use dfs::*;
9pub use entity_graph::*;
10pub use scc::*;
11
12use crate::prelude::*;
13
14/// A trait for any kind of graph data structure.
15pub 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.
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`.
30    fn successors(&self, node: Node) -> Self::SuccessorsIter<'_>;
31
32    // Provided Methods.
33
34    /// Like `Iterator::by_ref` but for `Graph`.
35    fn by_ref(&self) -> &Self {
36        self
37    }
38
39    /// Use the given predicate to filter out certain nodes from the graph.
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
52impl<T, Node> Graph<Node> for &'_ T
53where
54    T: ?Sized + Graph<Node>,
55{
56    type NodesIter<'a>
57        = T::NodesIter<'a>
58    where
59        Self: 'a;
60
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
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.
78pub struct FilterNodes<G, F> {
79    graph: G,
80    predicate: F,
81}
82
83impl<G, F> fmt::Debug for FilterNodes<G, F>
84where
85    G: fmt::Debug,
86{
87    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
95impl<G, F, Node> Graph<Node> for FilterNodes<G, F>
96where
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
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
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.
121fn 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}
wasmtime_environ/graphs.rs

wasmtime_environ/
graphs.rs
