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        struct Edges<'a, Node: EntityRef + Debug>(&'a EntityGraph<Node>);
28
29        impl<'a, Node: EntityRef + Debug> Debug for Edges<'a, Node> {
30            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
31                f.debug_map()
32                    .entries(
33                        self.0
34                            .nodes()
35                            .map(|n| (n, self.0.successors(n).collect::<Box<[_]>>())),
36                    )
37                    .finish()
38            }
39        }
40
41        f.debug_struct("Graph")
42            .field("edges", &Edges(self))
43            .finish()
44    }
45}
46
47impl<Node> EntityGraph<Node>
48where
49    Node: EntityRef + Debug,
50{
51    /// Construct a new, concrete `EntityGraph`.
52    pub fn new<E>(
53        nodes: impl IntoIterator<Item = Node>,
54        mut successors: impl FnMut(Node, &mut Vec<Node>) -> Result<(), E>,
55    ) -> Result<Self, E> {
56        let nodes = nodes.into_iter();
57
58        let (min, max) = nodes.size_hint();
59        let capacity = max.unwrap_or_else(|| 2 * min);
60
61        let mut edges = SecondaryMap::with_capacity(capacity);
62        let mut edge_elems = vec![];
63
64        let mut succs = vec![];
65        for v in nodes {
66            debug_assert!(succs.is_empty());
67            successors(v, &mut succs)?;
68
69            debug_assert_eq!(edges[v], Range::default());
70            edges[v] = extend_with_range(&mut edge_elems, succs.drain(..));
71        }
72
73        Ok(EntityGraph { edges, edge_elems })
74    }
75}
76
77impl<Node> Graph<Node> for EntityGraph<Node>
78where
79    Node: EntityRef,
80{
81    type NodesIter<'a>
82        = cranelift_entity::Keys<Node>
83    where
84        Self: 'a;
85
86    #[inline]
87    fn nodes(&self) -> Self::NodesIter<'_> {
88        self.edges.keys()
89    }
90
91    type SuccessorsIter<'a>
92        = iter::Copied<core::slice::Iter<'a, Node>>
93    where
94        Self: 'a;
95
96    fn successors(&self, node: Node) -> Self::SuccessorsIter<'_> {
97        let Range { start, end } = self.edges[node].clone();
98        let start = usize::try_from(start).unwrap();
99        let end = usize::try_from(end).unwrap();
100        self.edge_elems[start..end].iter().copied()
101    }
102}
wasmtime_environ/graphs/entity_graph.rs

wasmtime_environ/graphs/
entity_graph.rs
