GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

mirrored from https://github.com/microsoft/qdkAvailable

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
81001ecf81637fe00d1bfe83949dfd84d92de951

Branches

Tags

  • No tags available.
0Branches0Tags
Go to file
Add file
Code

Clone

HTTPS

Download ZIP

qdk/compiler/qsc_data_structures/src

compiler/qsc_data_structures/src/namespaces.rs

375lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4#[cfg(test)]
5mod tests;
6
7use rustc_hash::{FxHashMap, FxHashSet};
8use std::{cell::RefCell, fmt::Display, iter::Peekable, ops::Deref, rc::Rc};
9
10pub const PRELUDE: [[&str; 3]; 4] = [
11 ["Microsoft", "Quantum", "Canon"],
12 ["Microsoft", "Quantum", "Core"],
13 ["Microsoft", "Quantum", "Intrinsic"],
14 ["Microsoft", "Quantum", "Measurement"],
15];
16
17/// An ID that corresponds to a namespace in the global scope.
18#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq, Default)]
19pub struct NamespaceId(usize);
20impl NamespaceId {
21 /// Create a new namespace ID.
22 #[must_use]
23 pub fn new(value: usize) -> Self {
24 Self(value)
25 }
26}
27
28impl From<usize> for NamespaceId {
29 fn from(value: usize) -> Self {
30 Self::new(value)
31 }
32}
33
34impl From<NamespaceId> for usize {
35 fn from(value: NamespaceId) -> Self {
36 value.0
37 }
38}
39
40impl From<&NamespaceId> for usize {
41 fn from(value: &NamespaceId) -> Self {
42 value.0
43 }
44}
45
46impl Deref for NamespaceId {
47 type Target = usize;
48 fn deref(&self) -> &Self::Target {
49 &self.0
50 }
51}
52
53impl Display for NamespaceId {
54 fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
55 write!(f, "Namespace {}", self.0)
56 }
57}
58
59/// A reference counted cell that supports interior mutability for namespace tree nodes.
60/// Interior mutability is required to update the tree when inserting new data structures.
61type NamespaceTreeCell = Rc<RefCell<NamespaceTreeNode>>;
62
63/// An entry in the memoization table for namespace ID lookups.
64type MemoEntry = (Vec<Rc<str>>, NamespaceTreeCell);
65
66/// The root of the data structure that represents the namespaces in a program.
67/// The tree is a trie (prefix tree) where each node is a namespace and the children are the sub-namespaces.
68/// For example, the namespace `Microsoft.Quantum.Canon` would be represented as a traversal from the root node:
69/// ```
70/// root
71/// └ Microsoft
72/// └ Quantum
73/// └ Canon
74/// ```
75/// This data structure is optimized for looking up namespace IDs by a given name. Looking up a namespace name by ID is
76/// less efficient, as it performs a breadth-first search. Because of this inefficiency, the results of this lookup are memoized.
77/// [`NamespaceTreeNode`]s are all stored in [`NamespaceTreeCell`]s, which are reference counted and support interior mutability for namespace
78/// insertions and clone-free lookups.
79#[derive(Clone)]
80pub struct NamespaceTreeRoot {
81 assigner: usize,
82 tree: NamespaceTreeCell,
83 memo: RefCell<FxHashMap<NamespaceId, MemoEntry>>,
84}
85
86impl std::fmt::Debug for NamespaceTreeRoot {
87 // manual implementation to avoid infinite loops in printing
88 fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
89 write!(
90 f,
91 "NamespaceTreeRoot\n{}",
92 self.tree.borrow().debug_print(0, &mut FxHashSet::default())
93 )
94 }
95}
96
97impl std::fmt::Debug for NamespaceTreeNode {
98 // manual implementation to avoid infinite loops in printing
99 fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
100 write!(f, "{}", self.debug_print(0, &mut FxHashSet::default()))
101 }
102}
103
104impl NamespaceTreeRoot {
105 /// Create a new namespace tree root. The assigner is used to assign new namespace IDs.
106 #[must_use]
107 pub fn new_from_parts(assigner: usize, tree: NamespaceTreeNode) -> Self {
108 Self {
109 assigner,
110 tree: Rc::new(RefCell::new(tree)),
111 memo: RefCell::new(FxHashMap::default()),
112 }
113 }
114
115 /// Get the namespace tree field. This is the root of the namespace tree.
116 #[must_use]
117 pub fn tree(&self) -> NamespaceTreeCell {
118 self.tree.clone()
119 }
120
121 /// Insert a namespace into the tree. If the namespace already exists, return its ID.
122 /// Panics if the `ns` iterator is empty.
123 #[must_use]
124 pub fn insert_or_find_namespace(
125 &mut self,
126 ns: impl IntoIterator<Item = Rc<str>>,
127 ) -> NamespaceId {
128 self.tree
129 .borrow_mut()
130 .insert_or_find_namespace(ns.into_iter().peekable(), &mut self.assigner)
131 .expect("namespace creation should not fail")
132 }
133
134 /// Get the ID of a namespace given its name.
135 pub fn get_namespace_id<'a>(
136 &self,
137 ns: impl IntoIterator<Item = &'a str>,
138 ) -> Option<NamespaceId> {
139 self.tree.borrow().get_namespace_id(ns)
140 }
141
142 /// Given a [`NamespaceId`], find the namespace in the tree. Note that this function is not
143 /// particularly efficient, as it performs a breadth-first search. The results of this search
144 /// are memoized to avoid repeated lookups, reducing the impact of the BFS.
145 #[must_use]
146 pub fn find_namespace_by_id(&self, id: &NamespaceId) -> (Vec<Rc<str>>, NamespaceTreeCell) {
147 if let Some(res) = self.memo.borrow().get(id) {
148 return res.clone();
149 }
150 let (names, node) = self
151 .tree
152 .borrow()
153 .find_namespace_by_id(*id, &[], &mut FxHashSet::default())
154 .unwrap_or_else(|| (vec![], self.tree.clone()));
155
156 self.memo
157 .borrow_mut()
158 .insert(*id, (names.clone(), node.clone()));
159 (names, node.clone())
160 }
161
162 #[must_use]
163 pub fn root_id(&self) -> NamespaceId {
164 self.tree.borrow().id
165 }
166
167 /// Inserts an alias for an existing namespace into the tree, where the child namespace already exists.
168 pub fn insert_with_id(
169 &mut self,
170 parent: Option<NamespaceId>,
171 new_child: NamespaceId,
172 alias: &str,
173 ) {
174 let parent = parent.unwrap_or_else(|| self.root_id());
175 let (_, parent_node) = self.find_namespace_by_id(&parent);
176 let (_, existing_ns) = self.find_namespace_by_id(&new_child);
177 parent_node
178 .borrow_mut()
179 .children
180 .insert(Rc::from(alias), existing_ns);
181 }
182}
183
184impl Default for NamespaceTreeRoot {
185 fn default() -> Self {
186 let mut tree = Self {
187 assigner: 0,
188 tree: Rc::new(RefCell::new(NamespaceTreeNode {
189 children: FxHashMap::default(),
190 id: NamespaceId::new(0),
191 })),
192 memo: RefCell::new(FxHashMap::default()),
193 };
194 // insert the prelude namespaces using the `NamespaceTreeRoot` API
195 for ns in &PRELUDE {
196 let iter = ns.iter().map(|s| Rc::from(*s)).peekable();
197 let _ = tree.insert_or_find_namespace(iter);
198 }
199 tree
200 }
201}
202
203/// A node in the namespace tree. Each node has a unique ID and a map of children.
204/// Supports interior mutability of children for inserting new nodes.
205#[derive(Clone)]
206pub struct NamespaceTreeNode {
207 pub children: FxHashMap<Rc<str>, NamespaceTreeCell>,
208 pub id: NamespaceId,
209}
210
211impl NamespaceTreeNode {
212 /// Create a new namespace tree node with the given ID and children. The `id` should come from the `NamespaceTreeRoot` assigner.
213 #[must_use]
214 fn new(id: NamespaceId, children: FxHashMap<Rc<str>, NamespaceTreeCell>) -> Self {
215 Self { children, id }
216 }
217
218 /// Get a reference to the children of the namespace tree node.
219 #[must_use]
220 pub fn children(&self) -> &FxHashMap<Rc<str>, NamespaceTreeCell> {
221 &self.children
222 }
223
224 /// See [`FxHashMap::get`] for more information.
225 fn get(&self, component: &Rc<str>) -> Option<NamespaceTreeCell> {
226 self.children.get(component).cloned()
227 }
228
229 /// Get the ID of this namespace tree node.
230 #[must_use]
231 pub fn id(&self) -> NamespaceId {
232 self.id
233 }
234
235 /// Check if this namespace tree node contains a given namespace as a child.
236 #[must_use]
237 pub fn contains<'a>(&self, ns: impl IntoIterator<Item = &'a str>) -> bool {
238 self.get_namespace_id(ns).is_some()
239 }
240
241 /// Finds the ID of a namespace given its string name. This function is generally more efficient
242 /// than [`NamespaceTreeNode::find_namespace_by_id`], as it utilizes the prefix tree structure to
243 /// find the ID in `O(n)` time, where `n` is the number of components in the namespace name.
244 pub fn get_namespace_id<'a>(
245 &self,
246 ns: impl IntoIterator<Item = &'a str>,
247 ) -> Option<NamespaceId> {
248 let mut rover: Option<NamespaceTreeCell> = None;
249 for component in ns {
250 if let Some(next_ns) = match rover {
251 None => self.get(&Rc::from(component)),
252 Some(buf) => buf.borrow().get(&Rc::from(component)),
253 } {
254 rover = Some(next_ns);
255 } else {
256 return None;
257 }
258 }
259 Some(rover.map_or_else(|| self.id, |x| x.borrow().id))
260 }
261
262 /// Inserts a new namespace into the tree, if it does not yet exist.
263 /// Returns the ID of the namespace.
264 /// Returns `None` if an empty iterator is passed in.
265 pub fn insert_or_find_namespace<I>(
266 &mut self,
267 mut iter: Peekable<I>,
268 assigner: &mut usize,
269 ) -> Option<NamespaceId>
270 where
271 I: Iterator<Item = Rc<str>>,
272 {
273 let next_item = iter.next()?;
274 let next_node = self.children.get_mut(&next_item);
275 match (next_node, iter.peek()) {
276 (Some(next_node), Some(_)) => {
277 return next_node
278 .borrow_mut()
279 .insert_or_find_namespace(iter, assigner);
280 }
281 (Some(next_node), None) => {
282 return Some(next_node.borrow().id);
283 }
284 _ => {}
285 }
286 *assigner += 1;
287 let mut new_node =
288 NamespaceTreeNode::new(NamespaceId::new(*assigner), FxHashMap::default());
289 if iter.peek().is_none() {
290 let new_node_id = new_node.id;
291 self.children
292 .insert(next_item, Rc::new(RefCell::new(new_node)));
293 Some(new_node_id)
294 } else {
295 let id = new_node.insert_or_find_namespace(iter, assigner);
296 self.children
297 .insert(next_item, Rc::new(RefCell::new(new_node)));
298 id
299 }
300 }
301
302 fn find_namespace_by_id(
303 &self,
304 id: NamespaceId,
305 names_buf: &[Rc<str>],
306 // `ids_visited` is used to avoid infinite loops in the case of cycles in the namespace tree.
307 ids_visited: &mut FxHashSet<NamespaceId>,
308 ) -> Option<(Vec<Rc<str>>, NamespaceTreeCell)> {
309 if ids_visited.contains(&self.id) {
310 return None;
311 }
312 ids_visited.insert(self.id);
313 // first, check if any children are the one we are looking for
314 for (name, node) in &self.children {
315 if node.borrow().id == id {
316 let mut names = names_buf.to_vec();
317 names.push(name.clone());
318 return Some((names, node.clone()));
319 }
320 }
321
322 // if it wasn't found, recurse into children
323 for (name, node) in &self.children {
324 let mut names = names_buf.to_vec();
325 names.push(name.clone());
326 let Some((names, node)) = node.borrow().find_namespace_by_id(id, &names, ids_visited)
327 else {
328 continue;
329 };
330 return Some((names, node));
331 }
332
333 None
334 }
335
336 fn debug_print(
337 &self,
338 indentation_level: usize,
339 visited_nodes: &mut FxHashSet<NamespaceId>,
340 ) -> String {
341 let indentation = " ".repeat(indentation_level);
342
343 if visited_nodes.contains(&self.id) {
344 return format!("\n{indentation}Cycle Detected");
345 }
346
347 visited_nodes.insert(self.id);
348
349 let mut result = String::new();
350
351 if self.children.is_empty() {
352 result.push_str("empty node");
353 } else {
354 result.push_str(&format!("\n{indentation} children: ["));
355 for (name, node) in &self.children {
356 result.push_str(&format!(
357 "\n{} {}(id {}) {{",
358 indentation,
359 name,
360 Into::<usize>::into(node.borrow().id)
361 ));
362 result.push_str(
363 node.borrow()
364 .debug_print(indentation_level + 2, visited_nodes)
365 .as_str(),
366 );
367 result.push(',');
368 }
369 result.push_str(&format!("\n{indentation} ]"));
370 result.push_str(&format!("\n{indentation}"));
371 }
372 result.push('}');
373 result
374 }
375}