noirc_errors/
call_stack.rs

1use fxhash::FxHashMap;
2use serde::{Deserialize, Serialize};
3
4use crate::Location;
5
6pub type CallStack = Vec<Location>;
7#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
8pub struct CallStackId(u32);
9
10impl CallStackId {
11    pub fn root() -> Self {
12        Self::new(0)
13    }
14
15    pub fn new(id: usize) -> Self {
16        Self(id as u32)
17    }
18
19    pub fn index(&self) -> usize {
20        self.0 as usize
21    }
22
23    pub fn is_root(&self) -> bool {
24        self.0 == 0
25    }
26}
27
28#[derive(Debug, Clone, Serialize, Deserialize, Hash)]
29pub struct LocationNodeDebugInfo {
30    pub parent: Option<CallStackId>,
31    pub value: Location,
32}
33
34#[derive(Debug, Clone, Serialize, Deserialize, Default, Hash)]
35pub struct LocationTree {
36    pub locations: Vec<LocationNodeDebugInfo>,
37}
38
39impl LocationTree {
40    /// Construct a CallStack from a CallStackId
41    pub fn get_call_stack(&self, mut call_stack: CallStackId) -> CallStack {
42        let mut result = Vec::new();
43        while let Some(parent) = self.locations[call_stack.index()].parent {
44            result.push(self.locations[call_stack.index()].value);
45            call_stack = parent;
46        }
47        result.reverse();
48        result
49    }
50}
51
52#[derive(Debug, Clone, Serialize, Deserialize)]
53pub struct LocationNode {
54    pub parent: Option<CallStackId>,
55    pub children: Vec<CallStackId>,
56    pub children_hash: FxHashMap<u64, CallStackId>,
57    pub value: Location,
58}
59
60impl LocationNode {
61    pub fn new(parent: Option<CallStackId>, value: Location) -> Self {
62        LocationNode { parent, children: Vec::new(), children_hash: FxHashMap::default(), value }
63    }
64}
65
66#[derive(Debug, Clone, Serialize, Deserialize)]
67pub struct CallStackHelper {
68    pub locations: Vec<LocationNode>,
69}
70
71impl Default for CallStackHelper {
72    /// Generates a new helper, with an empty location tree
73    fn default() -> Self {
74        let mut result = CallStackHelper { locations: Vec::new() };
75        result.add_location_to_root(Location::dummy());
76        result
77    }
78}
79
80impl CallStackHelper {
81    /// Construct a CallStack from a CallStackId
82    pub fn get_call_stack(&self, mut call_stack: CallStackId) -> CallStack {
83        let mut result = Vec::new();
84        while let Some(parent) = self.locations[call_stack.index()].parent {
85            result.push(self.locations[call_stack.index()].value);
86            call_stack = parent;
87        }
88        result.reverse();
89        result
90    }
91
92    /// Returns a new CallStackId which extends the call_stack with the provided call_stack.
93    pub fn extend_call_stack(
94        &mut self,
95        mut call_stack: CallStackId,
96        locations: &CallStack,
97    ) -> CallStackId {
98        for location in locations {
99            call_stack = self.add_child(call_stack, *location);
100        }
101        call_stack
102    }
103
104    /// Adds a location to the call stack
105    pub fn add_child(&mut self, call_stack: CallStackId, location: Location) -> CallStackId {
106        let key = fxhash::hash64(&location);
107        if let Some(result) = self.locations[call_stack.index()].children_hash.get(&key) {
108            if self.locations[result.index()].value == location {
109                return *result;
110            }
111        }
112        let new_location = LocationNode::new(Some(call_stack), location);
113        let key = fxhash::hash64(&new_location.value);
114        self.locations.push(new_location);
115        let new_location_id = CallStackId::new(self.locations.len() - 1);
116
117        self.locations[call_stack.index()].children.push(new_location_id);
118        self.locations[call_stack.index()].children_hash.insert(key, new_location_id);
119        new_location_id
120    }
121
122    /// Retrieve the CallStackId corresponding to call_stack with the last 'len' locations removed.
123    pub fn unwind_call_stack(&self, mut call_stack: CallStackId, mut len: usize) -> CallStackId {
124        while len > 0 {
125            if let Some(parent) = self.locations[call_stack.index()].parent {
126                len -= 1;
127                call_stack = parent;
128            } else {
129                break;
130            }
131        }
132        call_stack
133    }
134
135    pub fn add_location_to_root(&mut self, location: Location) -> CallStackId {
136        if self.locations.is_empty() {
137            self.locations.push(LocationNode::new(None, location));
138            CallStackId::root()
139        } else {
140            self.add_child(CallStackId::root(), location)
141        }
142    }
143
144    /// Get (or create) a CallStackId corresponding to the given locations
145    pub fn get_or_insert_locations(&mut self, locations: &CallStack) -> CallStackId {
146        self.extend_call_stack(CallStackId::root(), locations)
147    }
148
149    // Clone the locations into a LocationTree
150    pub fn to_location_tree(&self) -> LocationTree {
151        LocationTree {
152            locations: self
153                .locations
154                .iter()
155                .map(|node| LocationNodeDebugInfo { value: node.value, parent: node.parent })
156                .collect(),
157        }
158    }
159}
noirc_errors/call_stack.rs

noirc_errors/
call_stack.rs
