hugr_model/v0/scope/
vars.rs

1use fxhash::FxHasher;
2use indexmap::IndexSet;
3use std::hash::BuildHasherDefault;
4use thiserror::Error;
5
6use crate::v0::table::{NodeId, VarId};
7
8type FxIndexSet<K> = IndexSet<K, BuildHasherDefault<FxHasher>>;
9
10/// Table for keeping track of node parameters.
11///
12/// Variables refer to the parameters of a node which introduces a symbol.
13/// Variables have an associated name and are scoped via nodes. The types of
14/// parameters of a node may only refer to earlier parameters in the same node
15/// in the order they are defined. A variable name must be unique within a
16/// single node. Each node that introduces a symbol introduces a new isolated
17/// scope for variables.
18///
19/// # Examples
20///
21/// ```
22/// # pub use hugr_model::v0::table::{NodeId, VarId};
23/// # pub use hugr_model::v0::scope::VarTable;
24/// let mut vars = VarTable::new();
25/// vars.enter(NodeId(0));
26/// vars.insert("foo").unwrap();
27/// assert_eq!(vars.resolve("foo").unwrap(), VarId(NodeId(0), 0));
28/// assert!(!vars.is_visible(VarId(NodeId(0), 1)));
29/// vars.insert("bar").unwrap();
30/// assert!(vars.is_visible(VarId(NodeId(0), 1)));
31/// assert_eq!(vars.resolve("bar").unwrap(), VarId(NodeId(0), 1));
32/// vars.enter(NodeId(1));
33/// assert!(vars.resolve("foo").is_err());
34/// assert!(!vars.is_visible(VarId(NodeId(0), 0)));
35/// vars.exit();
36/// assert_eq!(vars.resolve("foo").unwrap(), VarId(NodeId(0), 0));
37/// assert!(vars.is_visible(VarId(NodeId(0), 0)));
38/// ```
39#[derive(Debug, Clone, Default)]
40pub struct VarTable<'a> {
41    /// The set of variables in the currently active node and all its parent nodes.
42    ///
43    /// The order in this index set is the order in which variables were added to the table.
44    /// This is used to efficiently remove all variables from the current node when exiting a scope.
45    vars: FxIndexSet<(NodeId, &'a str)>,
46    /// The stack of scopes that are currently open.
47    scopes: Vec<VarScope>,
48}
49
50impl<'a> VarTable<'a> {
51    /// Create a new empty variable table.
52    pub fn new() -> Self {
53        Self::default()
54    }
55
56    /// Enter a new scope for the given node.
57    pub fn enter(&mut self, node: NodeId) {
58        self.scopes.push(VarScope {
59            node,
60            var_count: 0,
61            var_stack: self.vars.len(),
62        })
63    }
64
65    /// Exit a previously entered scope.
66    ///
67    /// # Panics
68    ///
69    /// Panics if there are no open scopes.
70    pub fn exit(&mut self) {
71        let scope = self.scopes.pop().unwrap();
72        self.vars.drain(scope.var_stack..);
73    }
74
75    /// Resolve a variable name to a node and variable index.
76    ///
77    /// # Errors
78    ///
79    /// Returns an error if the variable is not defined in the current scope.
80    ///
81    /// # Panics
82    ///
83    /// Panics if there are no open scopes.
84    pub fn resolve(&self, name: &'a str) -> Result<VarId, UnknownVarError<'a>> {
85        let scope = self.scopes.last().unwrap();
86        let set_index = self
87            .vars
88            .get_index_of(&(scope.node, name))
89            .ok_or(UnknownVarError(scope.node, name))?;
90        let var_index = (set_index - scope.var_stack) as u16;
91        Ok(VarId(scope.node, var_index))
92    }
93
94    /// Check if a variable is visible in the current scope.
95    ///
96    /// # Panics
97    ///
98    /// Panics if there are no open scopes.
99    pub fn is_visible(&self, var: VarId) -> bool {
100        let scope = self.scopes.last().unwrap();
101        scope.node == var.0 && var.1 < scope.var_count
102    }
103
104    /// Insert a new variable into the current scope.
105    ///
106    /// # Errors
107    ///
108    /// Returns an error if the variable is already defined in the current scope.
109    ///
110    /// # Panics
111    ///
112    /// Panics if there are no open scopes.
113    pub fn insert(&mut self, name: &'a str) -> Result<VarId, DuplicateVarError<'a>> {
114        let scope = self.scopes.last_mut().unwrap();
115        let inserted = self.vars.insert((scope.node, name));
116
117        if !inserted {
118            return Err(DuplicateVarError(scope.node, name));
119        }
120
121        let var_index = scope.var_count;
122        scope.var_count += 1;
123        Ok(VarId(scope.node, var_index))
124    }
125
126    /// Reset the variable table to an empty state while preserving the allocations.
127    pub fn clear(&mut self) {
128        self.vars.clear();
129        self.scopes.clear();
130    }
131}
132
133#[derive(Debug, Clone)]
134struct VarScope {
135    /// The node that introduces this scope.
136    node: NodeId,
137    /// The number of variables in this scope.
138    var_count: u16,
139    /// The length of `VarTable::vars` when the scope was opened.
140    var_stack: usize,
141}
142
143/// Error that occurs when a node defines two parameters with the same name.
144#[derive(Debug, Clone, Error)]
145#[error("node {0} already has a variable named `{1}`")]
146pub struct DuplicateVarError<'a>(NodeId, &'a str);
147
148/// Error that occurs when a variable is not defined in the current scope.
149#[derive(Debug, Clone, Error)]
150#[error("can not resolve variable `{1}` in node {0}")]
151pub struct UnknownVarError<'a>(NodeId, &'a str);
hugr_model/v0/scope/vars.rs

hugr_model/v0/scope/
vars.rs
