GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

mirrored fromhttps://github.com/microsoft/qdkAvailable

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
alex/merge-mines-changes

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

462lines · 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, collections::BTreeMap, 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, PartialOrd, Ord)]
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 /// Inserts (or finds) a new namespace as a child of an existing namespace.
184 /// Primarily used for appending namespaces to a parent namespace which represents a module/external package..
185 pub fn insert_or_find_namespace_from_root(
186 &mut self,
187 ns: impl Into<Vec<Rc<str>>>,
188 root: NamespaceId,
189 ) -> NamespaceId {
190 let ns = ns.into();
191 if ns.is_empty() {
192 return root;
193 }
194 let (_root_name, root_contents) = self.find_namespace_by_id(&root);
195 let id = root_contents
196 .borrow_mut()
197 .insert_or_find_namespace(ns.into_iter().peekable(), &mut self.assigner);
198
199 id.expect("empty name checked for above")
200 }
201
202 pub fn insert_or_find_namespace_from_root_with_id(
203 &mut self,
204 mut ns: Vec<Rc<str>>,
205 root: NamespaceId,
206 base_id: NamespaceId,
207 ) {
208 if ns.is_empty() {
209 return;
210 }
211 let (_root_name, root_contents) = self.find_namespace_by_id(&root);
212 // split `ns` into [0..len - 1] and [len - 1]
213 let suffix = ns.split_off(ns.len() - 1)[0].clone();
214 let prefix = ns;
215
216 // if the prefix is empty, we are inserting into the root
217 if prefix.is_empty() {
218 self.insert_with_id(Some(root), base_id, &suffix);
219 } else {
220 let prefix_id = root_contents
221 .borrow_mut()
222 .insert_or_find_namespace(prefix.into_iter().peekable(), &mut self.assigner)
223 .expect("empty name checked for above");
224
225 self.insert_with_id(Some(prefix_id), base_id, &suffix);
226 }
227 }
228
229 /// Each item in this iterator is the same, single namespace. The reason there are multiple paths for it,
230 /// each represented by a `Vec<Rc<str>>`, is because there may be multiple paths to the same
231 /// namespace, through aliasing or re-exports.
232 pub fn iter(&self) -> std::collections::btree_map::IntoValues<NamespaceId, Vec<Vec<Rc<str>>>> {
233 let mut stack = vec![(vec![], self.tree.clone())];
234 let mut result: Vec<(NamespaceId, Vec<Rc<str>>)> = vec![];
235 while let Some((names, node)) = stack.pop() {
236 result.push((node.borrow().id, names.clone()));
237 for (name, child) in node.borrow().children() {
238 let mut new_names = names.clone();
239 new_names.push(name.clone());
240 stack.push((new_names, child.clone()));
241 }
242 if node.borrow().children().is_empty() {
243 result.push((node.borrow().id, names));
244 }
245 }
246
247 // flatten the result into a list of paths
248
249 // use a btree map here instead of a hash map for deterministic iteration --
250 // while it shouldn't be consequential, any nondeterminism in a compiler makes
251 // things more difficult to track down then they go wrong.
252 let mut flattened_result = BTreeMap::default();
253 for (id, names) in result {
254 let entry = flattened_result.entry(id).or_insert_with(Vec::new);
255 entry.push(names);
256 }
257
258 flattened_result.into_values()
259 }
260}
261
262impl IntoIterator for &NamespaceTreeRoot {
263 type Item = Vec<Vec<Rc<str>>>;
264 type IntoIter = std::collections::btree_map::IntoValues<NamespaceId, Vec<Vec<Rc<str>>>>;
265
266 fn into_iter(self) -> Self::IntoIter {
267 self.iter()
268 }
269}
270
271impl Default for NamespaceTreeRoot {
272 fn default() -> Self {
273 let mut tree = Self {
274 assigner: 0,
275 tree: Rc::new(RefCell::new(NamespaceTreeNode {
276 children: FxHashMap::default(),
277 id: NamespaceId::new(0),
278 })),
279 memo: RefCell::new(FxHashMap::default()),
280 };
281 // insert the prelude namespaces using the `NamespaceTreeRoot` API
282 for ns in &PRELUDE {
283 let iter = ns.iter().map(|s| Rc::from(*s)).peekable();
284 let _ = tree.insert_or_find_namespace(iter);
285 }
286 tree
287 }
288}
289
290/// A node in the namespace tree. Each node has a unique ID and a map of children.
291/// Supports interior mutability of children for inserting new nodes.
292#[derive(Clone)]
293pub struct NamespaceTreeNode {
294 pub children: FxHashMap<Rc<str>, NamespaceTreeCell>,
295 pub id: NamespaceId,
296}
297
298impl NamespaceTreeNode {
299 /// Create a new namespace tree node with the given ID and children. The `id` should come from the `NamespaceTreeRoot` assigner.
300 #[must_use]
301 fn new(id: NamespaceId, children: FxHashMap<Rc<str>, NamespaceTreeCell>) -> Self {
302 Self { children, id }
303 }
304
305 /// Get a reference to the children of the namespace tree node.
306 #[must_use]
307 pub fn children(&self) -> &FxHashMap<Rc<str>, NamespaceTreeCell> {
308 &self.children
309 }
310
311 /// See [`FxHashMap::get`] for more information.
312 fn get(&self, component: &Rc<str>) -> Option<NamespaceTreeCell> {
313 self.children.get(component).cloned()
314 }
315
316 /// Get the ID of this namespace tree node.
317 #[must_use]
318 pub fn id(&self) -> NamespaceId {
319 self.id
320 }
321
322 /// Check if this namespace tree node contains a given namespace as a child.
323 #[must_use]
324 pub fn contains<'a>(&self, ns: impl IntoIterator<Item = &'a str>) -> bool {
325 self.get_namespace_id(ns).is_some()
326 }
327
328 /// Finds the ID of a namespace given its string name. This function is generally more efficient
329 /// than [`NamespaceTreeNode::find_namespace_by_id`], as it utilizes the prefix tree structure to
330 /// find the ID in `O(n)` time, where `n` is the number of components in the namespace name.
331 pub fn get_namespace_id<'a>(
332 &self,
333 ns: impl IntoIterator<Item = &'a str>,
334 ) -> Option<NamespaceId> {
335 let mut rover: Option<NamespaceTreeCell> = None;
336 for component in ns {
337 if let Some(next_ns) = match rover {
338 None => self.get(&Rc::from(component)),
339 Some(buf) => buf.borrow().get(&Rc::from(component)),
340 } {
341 rover = Some(next_ns);
342 } else {
343 return None;
344 }
345 }
346 Some(rover.map_or_else(|| self.id, |x| x.borrow().id))
347 }
348
349 /// Inserts a new namespace into the tree, if it does not yet exist.
350 /// Returns the ID of the namespace.
351 /// Returns `None` if an empty iterator is passed in.
352 pub fn insert_or_find_namespace<I>(
353 &mut self,
354 mut iter: Peekable<I>,
355 assigner: &mut usize,
356 ) -> Option<NamespaceId>
357 where
358 I: Iterator<Item = Rc<str>>,
359 {
360 let next_item = iter.next()?;
361 let next_node = self.children.get_mut(&next_item);
362 match (next_node, iter.peek()) {
363 (Some(next_node), Some(_)) => {
364 return next_node
365 .borrow_mut()
366 .insert_or_find_namespace(iter, assigner);
367 }
368 (Some(next_node), None) => {
369 return Some(next_node.borrow().id);
370 }
371 _ => {}
372 }
373 *assigner += 1;
374 let mut new_node =
375 NamespaceTreeNode::new(NamespaceId::new(*assigner), FxHashMap::default());
376 if iter.peek().is_none() {
377 let new_node_id = new_node.id;
378 self.children
379 .insert(next_item, Rc::new(RefCell::new(new_node)));
380 Some(new_node_id)
381 } else {
382 let id = new_node.insert_or_find_namespace(iter, assigner);
383 self.children
384 .insert(next_item, Rc::new(RefCell::new(new_node)));
385 id
386 }
387 }
388
389 fn find_namespace_by_id(
390 &self,
391 id: NamespaceId,
392 names_buf: &[Rc<str>],
393 // `ids_visited` is used to avoid infinite loops in the case of cycles in the namespace tree.
394 ids_visited: &mut FxHashSet<NamespaceId>,
395 ) -> Option<(Vec<Rc<str>>, NamespaceTreeCell)> {
396 if ids_visited.contains(&self.id) {
397 return None;
398 }
399 ids_visited.insert(self.id);
400 // first, check if any children are the one we are looking for
401 for (name, node) in &self.children {
402 if node.borrow().id == id {
403 let mut names = names_buf.to_vec();
404 names.push(name.clone());
405 return Some((names, node.clone()));
406 }
407 }
408
409 // if it wasn't found, recurse into children
410 for (name, node) in &self.children {
411 let mut names = names_buf.to_vec();
412 names.push(name.clone());
413 let Some((names, node)) = node.borrow().find_namespace_by_id(id, &names, ids_visited)
414 else {
415 continue;
416 };
417 return Some((names, node));
418 }
419
420 None
421 }
422
423 fn debug_print(
424 &self,
425 indentation_level: usize,
426 visited_nodes: &mut FxHashSet<NamespaceId>,
427 ) -> String {
428 let indentation = " ".repeat(indentation_level);
429
430 if visited_nodes.contains(&self.id) {
431 return format!("\n{indentation}Cycle Detected");
432 }
433
434 visited_nodes.insert(self.id);
435
436 let mut result = String::new();
437
438 if self.children.is_empty() {
439 result.push_str("empty node");
440 } else {
441 result.push_str(&format!("\n{indentation} children: ["));
442 for (name, node) in &self.children {
443 result.push_str(&format!(
444 "\n{} {}(id {}) {{",
445 indentation,
446 name,
447 Into::<usize>::into(node.borrow().id)
448 ));
449 result.push_str(
450 node.borrow()
451 .debug_print(indentation_level + 2, visited_nodes)
452 .as_str(),
453 );
454 result.push(',');
455 }
456 result.push_str(&format!("\n{indentation} ]"));
457 result.push_str(&format!("\n{indentation}"));
458 }
459 result.push('}');
460 result
461 }
462}
463