hugr_model/v0/scope/
link.rs

1use std::hash::{BuildHasherDefault, Hash};
2
3use fxhash::FxHasher;
4use indexmap::IndexSet;
5
6use crate::v0::table::{LinkIndex, RegionId};
7
8type FxIndexSet<K> = IndexSet<K, BuildHasherDefault<FxHasher>>;
9
10/// Table for tracking links between ports.
11///
12/// Two ports are connected when they share the same link. Links are named and
13/// scoped via closed regions. Links from one closed region are not visible
14/// in another. Open regions are considered to form the same scope as their
15/// parent region. Links do not have a unique point of declaration.
16///
17/// The link table keeps track of an association between a key of type `K` and
18/// the link indices within each closed region. When resolving links from a text format,
19/// `K` is the name of the link as a string slice. However the link table might
20/// is also useful in other contexts where the key is not a string when constructing
21/// a module from a different representation.
22///
23/// # Examples
24///
25/// ```
26/// # pub use hugr_model::v0::table::RegionId;
27/// # pub use hugr_model::v0::scope::LinkTable;
28/// let mut links = LinkTable::new();
29/// links.enter(RegionId(0));
30/// let foo_0 = links.use_link("foo");
31/// let bar_0 = links.use_link("bar");
32/// assert_eq!(foo_0, links.use_link("foo"));
33/// assert_eq!(bar_0, links.use_link("bar"));
34/// let (num_links, num_ports) = links.exit();
35/// assert_eq!(num_links, 2);
36/// assert_eq!(num_ports, 4);
37/// ```
38#[derive(Debug, Clone)]
39pub struct LinkTable<K> {
40    /// The set of links in the currently active region and all parent regions.
41    ///
42    /// The order in this index set is the order in which links were added to the table.
43    /// This is used to efficiently remove all links from the current region when exiting a scope.
44    links: FxIndexSet<(RegionId, K)>,
45
46    /// The stack of scopes that are currently open.
47    scopes: Vec<LinkScope>,
48}
49
50impl<K> LinkTable<K>
51where
52    K: Copy + Eq + Hash,
53{
54    /// Create a new empty link table.
55    pub fn new() -> Self {
56        Self {
57            links: FxIndexSet::default(),
58            scopes: Vec::new(),
59        }
60    }
61
62    /// Enter a new scope for the given closed region.
63    pub fn enter(&mut self, region: RegionId) {
64        self.scopes.push(LinkScope {
65            link_stack: self.links.len(),
66            link_count: 0,
67            port_count: 0,
68            region,
69        });
70    }
71
72    /// Exit a previously entered scope, returning the number of links and ports in the scope.
73    pub fn exit(&mut self) -> (u32, u32) {
74        let scope = self.scopes.pop().unwrap();
75        self.links.drain(scope.link_stack..);
76        debug_assert_eq!(self.links.len(), scope.link_stack);
77        (scope.link_count, scope.port_count)
78    }
79
80    /// Resolve a link key to a link index, adding one more port to the current scope.
81    ///
82    /// If the key has not been used in the current scope before, it will be added to the link table.
83    ///
84    /// # Panics
85    ///
86    /// Panics if there are no open scopes.
87    pub fn use_link(&mut self, key: K) -> LinkIndex {
88        let scope = self.scopes.last_mut().unwrap();
89        let (map_index, inserted) = self.links.insert_full((scope.region, key));
90
91        if inserted {
92            scope.link_count += 1;
93        }
94
95        scope.port_count += 1;
96        LinkIndex::new(map_index - scope.link_stack)
97    }
98
99    /// Reset the link table to an empty state while preserving allocated memory.
100    pub fn clear(&mut self) {
101        self.links.clear();
102        self.scopes.clear();
103    }
104}
105
106impl<K> Default for LinkTable<K>
107where
108    K: Copy + Eq + Hash,
109{
110    fn default() -> Self {
111        Self::new()
112    }
113}
114
115#[derive(Debug, Clone)]
116struct LinkScope {
117    /// The length of `LinkTable::links` when the scope was opened.
118    link_stack: usize,
119    /// The number of links in this scope.
120    link_count: u32,
121    /// The number of ports in this scope.
122    port_count: u32,
123    /// The region that introduces this scope.
124    region: RegionId,
125}
hugr_model/v0/scope/link.rs

hugr_model/v0/scope/
link.rs
