wasmtime_environ/graphs/
entity_graph.rs

1use super::*;
2use crate::{EntityRef, SecondaryMap, prelude::*};
3use core::{
4    fmt::{self, Debug},
5    iter,
6    ops::Range,
7};
8
9/// A graph of `EntityRef` nodes reified into a densely packed representation.
10pub struct EntityGraph<Node>
11where
12    Node: EntityRef,
13{
14    /// A map from each node to the subslice of `self.edge_elems` that are its
15    /// edges.
16    edges: SecondaryMap<Node, Range<u32>>,
17
18    /// Densely packed edge elements for `self.edges`.
19    edge_elems: Vec<Node>,
20}
21
22impl<Node> Debug for EntityGraph<Node>
23where
24    Node: EntityRef + Debug,
25{
26    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
27        f.debug_struct("Graph")
28            .field(
29                "edges",
30                &fmt::from_fn(|f| {
31                    f.debug_map()
32                        .entries(
33                            self.nodes()
34                                .map(|n| (n, self.successors(n).collect::<Box<[_]>>())),
35                        )
36                        .finish()
37                }),
38            )
39            .finish()
40    }
41}
42
43impl<Node> EntityGraph<Node>
44where
45    Node: EntityRef + Debug,
46{
47    /// Construct a new, concrete `EntityGraph`.
48    pub fn new<E>(
49        nodes: impl IntoIterator<Item = Node>,
50        mut successors: impl FnMut(Node, &mut Vec<Node>) -> Result<(), E>,
51    ) -> Result<Self, E> {
52        let nodes = nodes.into_iter();
53
54        let (min, max) = nodes.size_hint();
55        let capacity = max.unwrap_or_else(|| 2 * min);
56
57        let mut edges = SecondaryMap::with_capacity(capacity);
58        let mut edge_elems = vec![];
59
60        let mut succs = vec![];
61        for v in nodes {
62            debug_assert!(succs.is_empty());
63            successors(v, &mut succs)?;
64
65            debug_assert_eq!(edges[v], Range::default());
66            edges[v] = extend_with_range(&mut edge_elems, succs.drain(..));
67        }
68
69        Ok(EntityGraph { edges, edge_elems })
70    }
71}
72
73impl<Node> Graph<Node> for EntityGraph<Node>
74where
75    Node: EntityRef,
76{
77    type NodesIter<'a>
78        = cranelift_entity::Keys<Node>
79    where
80        Self: 'a;
81
82    #[inline]
83    fn nodes(&self) -> Self::NodesIter<'_> {
84        self.edges.keys()
85    }
86
87    type SuccessorsIter<'a>
88        = iter::Copied<core::slice::Iter<'a, Node>>
89    where
90        Self: 'a;
91
92    fn successors(&self, node: Node) -> Self::SuccessorsIter<'_> {
93        let Range { start, end } = self.edges[node].clone();
94        let start = usize::try_from(start).unwrap();
95        let end = usize::try_from(end).unwrap();
96        self.edge_elems[start..end].iter().copied()
97    }
98}
wasmtime_environ/graphs/entity_graph.rs

wasmtime_environ/graphs/
entity_graph.rs
