hugr_model/v0/scope/
vars.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
use fxhash::FxHasher;
use indexmap::IndexSet;
use std::hash::BuildHasherDefault;
use thiserror::Error;

use crate::v0::{NodeId, VarId};

type FxIndexSet<K> = IndexSet<K, BuildHasherDefault<FxHasher>>;

/// Table for keeping track of node parameters.
///
/// Variables refer to the parameters of a node which introduces a symbol.
/// Variables have an associated name and are scoped via nodes. The types of
/// parameters of a node may only refer to earlier parameters in the same node
/// in the order they are defined. A variable name must be unique within a
/// single node. Each node that introduces a symbol introduces a new isolated
/// scope for variables.
///
/// # Examples
///
/// ```
/// # pub use hugr_model::v0::{NodeId, VarId};
/// # pub use hugr_model::v0::scope::VarTable;
/// let mut vars = VarTable::new();
/// vars.enter(NodeId(0));
/// vars.insert("foo").unwrap();
/// assert_eq!(vars.resolve("foo").unwrap(), VarId(NodeId(0), 0));
/// assert!(!vars.is_visible(VarId(NodeId(0), 1)));
/// vars.insert("bar").unwrap();
/// assert!(vars.is_visible(VarId(NodeId(0), 1)));
/// assert_eq!(vars.resolve("bar").unwrap(), VarId(NodeId(0), 1));
/// vars.enter(NodeId(1));
/// assert!(vars.resolve("foo").is_err());
/// assert!(!vars.is_visible(VarId(NodeId(0), 0)));
/// vars.exit();
/// assert_eq!(vars.resolve("foo").unwrap(), VarId(NodeId(0), 0));
/// assert!(vars.is_visible(VarId(NodeId(0), 0)));
/// ```
#[derive(Debug, Clone, Default)]
pub struct VarTable<'a> {
    /// The set of variables in the currently active node and all its parent nodes.
    ///
    /// The order in this index set is the order in which variables were added to the table.
    /// This is used to efficiently remove all variables from the current node when exiting a scope.
    vars: FxIndexSet<(NodeId, &'a str)>,
    /// The stack of scopes that are currently open.
    scopes: Vec<VarScope>,
}

impl<'a> VarTable<'a> {
    /// Create a new empty variable table.
    pub fn new() -> Self {
        Self::default()
    }

    /// Enter a new scope for the given node.
    pub fn enter(&mut self, node: NodeId) {
        self.scopes.push(VarScope {
            node,
            var_count: 0,
            var_stack: self.vars.len(),
        })
    }

    /// Exit a previously entered scope.
    ///
    /// # Panics
    ///
    /// Panics if there are no open scopes.
    pub fn exit(&mut self) {
        let scope = self.scopes.pop().unwrap();
        self.vars.drain(scope.var_stack..);
    }

    /// Resolve a variable name to a node and variable index.
    ///
    /// # Errors
    ///
    /// Returns an error if the variable is not defined in the current scope.
    ///
    /// # Panics
    ///
    /// Panics if there are no open scopes.
    pub fn resolve(&self, name: &'a str) -> Result<VarId, UnknownVarError<'a>> {
        let scope = self.scopes.last().unwrap();
        let set_index = self
            .vars
            .get_index_of(&(scope.node, name))
            .ok_or(UnknownVarError(scope.node, name))?;
        let var_index = (set_index - scope.var_stack) as u16;
        Ok(VarId(scope.node, var_index))
    }

    /// Check if a variable is visible in the current scope.
    ///
    /// # Panics
    ///
    /// Panics if there are no open scopes.
    pub fn is_visible(&self, var: VarId) -> bool {
        let scope = self.scopes.last().unwrap();
        scope.node == var.0 && var.1 < scope.var_count
    }

    /// Insert a new variable into the current scope.
    ///
    /// # Errors
    ///
    /// Returns an error if the variable is already defined in the current scope.
    ///
    /// # Panics
    ///
    /// Panics if there are no open scopes.
    pub fn insert(&mut self, name: &'a str) -> Result<VarId, DuplicateVarError<'a>> {
        let scope = self.scopes.last_mut().unwrap();
        let inserted = self.vars.insert((scope.node, name));

        if !inserted {
            return Err(DuplicateVarError(scope.node, name));
        }

        let var_index = scope.var_count;
        scope.var_count += 1;
        Ok(VarId(scope.node, var_index))
    }

    /// Reset the variable table to an empty state while preserving the allocations.
    pub fn clear(&mut self) {
        self.vars.clear();
        self.scopes.clear();
    }
}

#[derive(Debug, Clone)]
struct VarScope {
    /// The node that introduces this scope.
    node: NodeId,
    /// The number of variables in this scope.
    var_count: u16,
    /// The length of `VarTable::vars` when the scope was opened.
    var_stack: usize,
}

/// Error that occurs when a node defines two parameters with the same name.
#[derive(Debug, Clone, Error)]
#[error("node {0} already has a variable named `{1}`")]
pub struct DuplicateVarError<'a>(NodeId, &'a str);

/// Error that occurs when a variable is not defined in the current scope.
#[derive(Debug, Clone, Error)]
#[error("can not resolve variable `{1}` in node {0}")]
pub struct UnknownVarError<'a>(NodeId, &'a str);