hugr_model/v0/scope/
link.rs

1use std::hash::{BuildHasherDefault, Hash};
2
3use indexmap::IndexSet;
4use rustc_hash::FxHasher;
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    #[must_use]
56    pub fn new() -> Self {
57        Self {
58            links: FxIndexSet::default(),
59            scopes: Vec::new(),
60        }
61    }
62
63    /// Enter a new scope for the given closed region.
64    pub fn enter(&mut self, region: RegionId) {
65        self.scopes.push(LinkScope {
66            link_stack: self.links.len(),
67            link_count: 0,
68            port_count: 0,
69            region,
70        });
71    }
72
73    /// Exit a previously entered scope, returning the number of links and ports in the scope.
74    pub fn exit(&mut self) -> (u32, u32) {
75        let scope = self.scopes.pop().unwrap();
76        self.links.drain(scope.link_stack..);
77        debug_assert_eq!(self.links.len(), scope.link_stack);
78        (scope.link_count, scope.port_count)
79    }
80
81    /// Resolve a link key to a link index, adding one more port to the current scope.
82    ///
83    /// If the key has not been used in the current scope before, it will be added to the link table.
84    ///
85    /// # Panics
86    ///
87    /// Panics if there are no open scopes.
88    pub fn use_link(&mut self, key: K) -> LinkIndex {
89        let scope = self.scopes.last_mut().unwrap();
90        let (map_index, inserted) = self.links.insert_full((scope.region, key));
91
92        if inserted {
93            scope.link_count += 1;
94        }
95
96        scope.port_count += 1;
97        LinkIndex::new(map_index - scope.link_stack)
98    }
99
100    /// Reset the link table to an empty state while preserving allocated memory.
101    pub fn clear(&mut self) {
102        self.links.clear();
103        self.scopes.clear();
104    }
105}
106
107impl<K> Default for LinkTable<K>
108where
109    K: Copy + Eq + Hash,
110{
111    fn default() -> Self {
112        Self::new()
113    }
114}
115
116#[derive(Debug, Clone)]
117struct LinkScope {
118    /// The length of `LinkTable::links` when the scope was opened.
119    link_stack: usize,
120    /// The number of links in this scope.
121    link_count: u32,
122    /// The number of ports in this scope.
123    port_count: u32,
124    /// The region that introduces this scope.
125    region: RegionId,
126}
hugr_model/v0/scope/link.rs

hugr_model/v0/scope/
link.rs
