GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
alex/reexports-fixes

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

475lines · 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; 2]; 5] = [
11 ["Std", "Canon"],
12 ["Std", "Core"],
13 ["Std", "Intrinsic"],
14 ["Std", "Measurement"],
15 ["Std", "Range"],
16];
17
18/// An ID that corresponds to a namespace in the global scope.
19#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq, Default, PartialOrd, Ord)]
20pub struct NamespaceId(usize);
21impl NamespaceId {
22 /// Create a new namespace ID.
23 #[must_use]
24 pub fn new(value: usize) -> Self {
25 Self(value)
26 }
27}
28
29impl From<usize> for NamespaceId {
30 fn from(value: usize) -> Self {
31 Self::new(value)
32 }
33}
34
35impl From<NamespaceId> for usize {
36 fn from(value: NamespaceId) -> Self {
37 value.0
38 }
39}
40
41impl From<&NamespaceId> for usize {
42 fn from(value: &NamespaceId) -> Self {
43 value.0
44 }
45}
46
47impl Deref for NamespaceId {
48 type Target = usize;
49 fn deref(&self) -> &Self::Target {
50 &self.0
51 }
52}
53
54impl Display for NamespaceId {
55 fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
56 write!(f, "Namespace {}", self.0)
57 }
58}
59
60/// A reference counted cell that supports interior mutability for namespace tree nodes.
61/// Interior mutability is required to update the tree when inserting new data structures.
62type NamespaceTreeCell = Rc<RefCell<NamespaceTreeNode>>;
63
64/// An entry in the memoization table for namespace ID lookups.
65type MemoEntry = (Vec<Rc<str>>, NamespaceTreeCell);
66
67/// Denotes that a namespace from an external package has been overridden by a local package namespace.
68/// This renders the contents of the foreign namespace unaccessible.
69/// E.g. a user explicitly creating a namespace called `namespace Std.Diagnostics`, where `Std` is the
70/// standard library.
71#[derive(Debug)]
72pub struct ClobberedNamespace;
73
74/// The root of the data structure that represents the namespaces in a program.
75/// The tree is a trie (prefix tree) where each node is a namespace and the children are the sub-namespaces.
76/// For example, the namespace `Microsoft.Quantum.Canon` would be represented as a traversal from the root node:
77/// ```
78/// root
79/// └ Microsoft
80/// └ Quantum
81/// └ Canon
82/// ```
83/// This data structure is optimized for looking up namespace IDs by a given name. Looking up a namespace name by ID is
84/// less efficient, as it performs a breadth-first search. Because of this inefficiency, the results of this lookup are memoized.
85/// [`NamespaceTreeNode`]s are all stored in [`NamespaceTreeCell`]s, which are reference counted and support interior mutability for namespace
86/// insertions and clone-free lookups.
87#[derive(Clone)]
88pub struct NamespaceTreeRoot {
89 assigner: usize,
90 tree: NamespaceTreeCell,
91 memo: RefCell<FxHashMap<NamespaceId, MemoEntry>>,
92}
93
94impl std::fmt::Debug for NamespaceTreeRoot {
95 // manual implementation to avoid infinite loops in printing
96 fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
97 write!(
98 f,
99 "NamespaceTreeRoot\n{}",
100 self.tree.borrow().debug_print(0, &mut FxHashSet::default())
101 )
102 }
103}
104
105impl std::fmt::Debug for NamespaceTreeNode {
106 // manual implementation to avoid infinite loops in printing
107 fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
108 write!(f, "{}", self.debug_print(0, &mut FxHashSet::default()))
109 }
110}
111
112impl NamespaceTreeRoot {
113 /// Create a new namespace tree root. The assigner is used to assign new namespace IDs.
114 #[must_use]
115 pub fn new_from_parts(assigner: usize, tree: NamespaceTreeNode) -> Self {
116 Self {
117 assigner,
118 tree: Rc::new(RefCell::new(tree)),
119 memo: RefCell::new(FxHashMap::default()),
120 }
121 }
122
123 /// Get the namespace tree field. This is the root of the namespace tree.
124 #[must_use]
125 pub fn tree(&self) -> NamespaceTreeCell {
126 self.tree.clone()
127 }
128
129 /// Insert a namespace into the tree. If the namespace already exists, return its ID.
130 /// Panics if the `ns` iterator is empty.
131 #[must_use]
132 pub fn insert_or_find_namespace(
133 &mut self,
134 ns: impl IntoIterator<Item = Rc<str>>,
135 ) -> NamespaceId {
136 self.tree
137 .borrow_mut()
138 .insert_or_find_namespace(ns.into_iter().peekable(), &mut self.assigner)
139 .expect("namespace creation should not fail")
140 }
141
142 /// Get the ID of a namespace given its name.
143 pub fn get_namespace_id<'a>(
144 &self,
145 ns: impl IntoIterator<Item = &'a str>,
146 ) -> Option<NamespaceId> {
147 self.tree.borrow().get_namespace_id(ns)
148 }
149
150 /// Given a [`NamespaceId`], find the namespace in the tree. Note that this function is not
151 /// particularly efficient, as it performs a breadth-first search. The results of this search
152 /// are memoized to avoid repeated lookups, reducing the impact of the BFS.
153 #[must_use]
154 pub fn find_namespace_by_id(&self, id: &NamespaceId) -> (Vec<Rc<str>>, NamespaceTreeCell) {
155 if let Some(res) = self.memo.borrow().get(id) {
156 return res.clone();
157 }
158 let (names, node) = self
159 .tree
160 .borrow()
161 .find_namespace_by_id(*id, &[], &mut FxHashSet::default())
162 .unwrap_or_else(|| (vec![], self.tree.clone()));
163
164 self.memo
165 .borrow_mut()
166 .insert(*id, (names.clone(), node.clone()));
167 (names, node.clone())
168 }
169
170 #[must_use]
171 pub fn root_id(&self) -> NamespaceId {
172 self.tree.borrow().id
173 }
174
175 /// Inserts an alias for an existing namespace into the tree, where the child namespace already exists.
176 pub fn insert_with_id(
177 &mut self,
178 parent: Option<NamespaceId>,
179 new_child: NamespaceId,
180 alias: &str,
181 ) -> Result<(), ClobberedNamespace> {
182 let parent = parent.unwrap_or_else(|| self.root_id());
183 let (_, parent_node) = self.find_namespace_by_id(&parent);
184 let (_, existing_ns) = self.find_namespace_by_id(&new_child);
185 if let Some(val) = parent_node.borrow().children.get(&Rc::from(alias)) {
186 if val.borrow().id != existing_ns.borrow().id {
187 return Err(ClobberedNamespace);
188 }
189 }
190
191 parent_node
192 .borrow_mut()
193 .children
194 .insert(Rc::from(alias), existing_ns);
195
196 Ok(())
197 }
198
199 /// Inserts (or finds) a new namespace as a child of an existing namespace.
200 /// Primarily used for appending namespaces to a parent namespace which represents a module/external package..
201 pub fn insert_or_find_namespace_from_root(
202 &mut self,
203 ns: impl Into<Vec<Rc<str>>>,
204 root: NamespaceId,
205 ) -> NamespaceId {
206 let ns = ns.into();
207 if ns.is_empty() {
208 return root;
209 }
210 let (_root_name, root_contents) = self.find_namespace_by_id(&root);
211 let id = root_contents
212 .borrow_mut()
213 .insert_or_find_namespace(ns.into_iter().peekable(), &mut self.assigner);
214
215 id.expect("empty name checked for above")
216 }
217
218 pub fn insert_or_find_namespace_from_root_with_id(
219 &mut self,
220 mut ns: Vec<Rc<str>>,
221 root: NamespaceId,
222 base_id: NamespaceId,
223 ) -> Result<(), ClobberedNamespace> {
224 if ns.is_empty() {
225 return Ok(());
226 }
227 let (_root_name, root_contents) = self.find_namespace_by_id(&root);
228 // split `ns` into [0..len - 1] and [len - 1]
229 let suffix = ns.split_off(ns.len() - 1)[0].clone();
230 let prefix = ns;
231
232 // if the prefix is empty, we are inserting into the root
233 if prefix.is_empty() {
234 self.insert_with_id(Some(root), base_id, &suffix)?;
235 } else {
236 let prefix_id = root_contents
237 .borrow_mut()
238 .insert_or_find_namespace(prefix.into_iter().peekable(), &mut self.assigner)
239 .expect("empty name checked for above");
240
241 self.insert_with_id(Some(prefix_id), base_id, &suffix)?;
242 }
243 Ok(())
244 }
245
246 /// Each item in this iterator is one singluar namespace. The reason there are multiple paths for it,
247 /// each represented by a `Vec<Rc<str>>`, is because there may be multiple paths to the same
248 /// namespace, through aliasing or re-exports.
249 /// For example, the first item yielded may be the namespace 0, but it could be referred to by
250 /// A.B.C or D.E.F, so both are included.
251 pub fn iter(&self) -> std::collections::btree_map::IntoValues<NamespaceId, Vec<Vec<Rc<str>>>> {
252 let mut stack = vec![(vec![], self.tree.clone())];
253 let mut result: Vec<(NamespaceId, Vec<Rc<str>>)> = vec![];
254 while let Some((names, node)) = stack.pop() {
255 result.push((node.borrow().id, names.clone()));
256 for (name, child) in node.borrow().children() {
257 let mut new_names = names.clone();
258 new_names.push(name.clone());
259 stack.push((new_names, child.clone()));
260 }
261 if node.borrow().children().is_empty() {
262 result.push((node.borrow().id, names));
263 }
264 }
265
266 // flatten the result into a list of paths
267
268 // use a btree map here instead of a hash map for deterministic iteration --
269 // while it shouldn't be consequential, any nondeterminism in a compiler makes
270 // things more difficult to track down then they go wrong.
271 let mut flattened_result = BTreeMap::default();
272 for (id, names) in result {
273 let entry = flattened_result.entry(id).or_insert_with(Vec::new);
274 entry.push(names);
275 }
276
277 flattened_result.into_values()
278 }
279}
280
281impl IntoIterator for &NamespaceTreeRoot {
282 type Item = Vec<Vec<Rc<str>>>;
283 type IntoIter = std::collections::btree_map::IntoValues<NamespaceId, Vec<Vec<Rc<str>>>>;
284
285 fn into_iter(self) -> Self::IntoIter {
286 self.iter()
287 }
288}
289
290impl Default for NamespaceTreeRoot {
291 fn default() -> Self {
292 Self {
293 assigner: 0,
294 tree: Rc::new(RefCell::new(NamespaceTreeNode {
295 children: FxHashMap::default(),
296 id: NamespaceId::new(0),
297 })),
298 memo: RefCell::new(FxHashMap::default()),
299 }
300 }
301}
302
303/// A node in the namespace tree. Each node has a unique ID and a map of children.
304/// Supports interior mutability of children for inserting new nodes.
305#[derive(Clone)]
306pub struct NamespaceTreeNode {
307 pub children: FxHashMap<Rc<str>, NamespaceTreeCell>,
308 pub id: NamespaceId,
309}
310
311impl NamespaceTreeNode {
312 /// Create a new namespace tree node with the given ID and children. The `id` should come from the `NamespaceTreeRoot` assigner.
313 #[must_use]
314 fn new(id: NamespaceId, children: FxHashMap<Rc<str>, NamespaceTreeCell>) -> Self {
315 Self { children, id }
316 }
317
318 /// Get a reference to the children of the namespace tree node.
319 #[must_use]
320 pub fn children(&self) -> &FxHashMap<Rc<str>, NamespaceTreeCell> {
321 &self.children
322 }
323
324 /// See [`FxHashMap::get`] for more information.
325 fn get(&self, component: &Rc<str>) -> Option<NamespaceTreeCell> {
326 self.children.get(component).cloned()
327 }
328
329 /// Get the ID of this namespace tree node.
330 #[must_use]
331 pub fn id(&self) -> NamespaceId {
332 self.id
333 }
334
335 /// Check if this namespace tree node contains a given namespace as a child.
336 #[must_use]
337 pub fn contains<'a>(&self, ns: impl IntoIterator<Item = &'a str>) -> bool {
338 self.get_namespace_id(ns).is_some()
339 }
340
341 /// Finds the ID of a namespace given its string name. This function is generally more efficient
342 /// than [`NamespaceTreeNode::find_namespace_by_id`], as it utilizes the prefix tree structure to
343 /// find the ID in `O(n)` time, where `n` is the number of components in the namespace name.
344 pub fn get_namespace_id<'a>(
345 &self,
346 ns: impl IntoIterator<Item = &'a str>,
347 ) -> Option<NamespaceId> {
348 let mut rover: Option<NamespaceTreeCell> = None;
349 for component in ns {
350 if let Some(next_ns) = match rover {
351 None => self.get(&Rc::from(component)),
352 Some(buf) => buf.borrow().get(&Rc::from(component)),
353 } {
354 rover = Some(next_ns);
355 } else {
356 return None;
357 }
358 }
359 Some(rover.map_or_else(|| self.id, |x| x.borrow().id))
360 }
361
362 /// Inserts a new namespace into the tree, if it does not yet exist.
363 /// Returns the ID of the namespace.
364 /// Returns `None` if an empty iterator is passed in.
365 pub fn insert_or_find_namespace<I>(
366 &mut self,
367 mut iter: Peekable<I>,
368 assigner: &mut usize,
369 ) -> Option<NamespaceId>
370 where
371 I: Iterator<Item = Rc<str>>,
372 {
373 let next_item = iter.next()?;
374 let next_node = self.children.get_mut(&next_item);
375 match (next_node, iter.peek()) {
376 (Some(next_node), Some(_)) => {
377 return next_node
378 .borrow_mut()
379 .insert_or_find_namespace(iter, assigner);
380 }
381 (Some(next_node), None) => {
382 return Some(next_node.borrow().id);
383 }
384 _ => {}
385 }
386 *assigner += 1;
387 let mut new_node =
388 NamespaceTreeNode::new(NamespaceId::new(*assigner), FxHashMap::default());
389 if iter.peek().is_none() {
390 let new_node_id = new_node.id;
391 self.children
392 .insert(next_item, Rc::new(RefCell::new(new_node)));
393 Some(new_node_id)
394 } else {
395 let id = new_node.insert_or_find_namespace(iter, assigner);
396 self.children
397 .insert(next_item, Rc::new(RefCell::new(new_node)));
398 id
399 }
400 }
401
402 fn find_namespace_by_id(
403 &self,
404 id: NamespaceId,
405 names_buf: &[Rc<str>],
406 // `ids_visited` is used to avoid infinite loops in the case of cycles in the namespace tree.
407 ids_visited: &mut FxHashSet<NamespaceId>,
408 ) -> Option<(Vec<Rc<str>>, NamespaceTreeCell)> {
409 if ids_visited.contains(&self.id) {
410 return None;
411 }
412 ids_visited.insert(self.id);
413 // first, check if any children are the one we are looking for
414 for (name, node) in &self.children {
415 if node.borrow().id == id {
416 let mut names = names_buf.to_vec();
417 names.push(name.clone());
418 return Some((names, node.clone()));
419 }
420 }
421
422 // if it wasn't found, recurse into children
423 for (name, node) in &self.children {
424 let mut names = names_buf.to_vec();
425 names.push(name.clone());
426 let Some((names, node)) = node.borrow().find_namespace_by_id(id, &names, ids_visited)
427 else {
428 continue;
429 };
430 return Some((names, node));
431 }
432
433 None
434 }
435
436 fn debug_print(
437 &self,
438 indentation_level: usize,
439 visited_nodes: &mut FxHashSet<NamespaceId>,
440 ) -> String {
441 let indentation = " ".repeat(indentation_level);
442
443 if visited_nodes.contains(&self.id) {
444 return format!("\n{indentation}Cycle Detected");
445 }
446
447 visited_nodes.insert(self.id);
448
449 let mut result = String::new();
450
451 if self.children.is_empty() {
452 result.push_str("empty node");
453 } else {
454 result.push_str(&format!("\n{indentation} children: ["));
455 for (name, node) in &self.children {
456 result.push_str(&format!(
457 "\n{} {}(id {}) {{",
458 indentation,
459 name,
460 Into::<usize>::into(node.borrow().id)
461 ));
462 result.push_str(
463 node.borrow()
464 .debug_print(indentation_level + 2, visited_nodes)
465 .as_str(),
466 );
467 result.push(',');
468 }
469 result.push_str(&format!("\n{indentation} ]"));
470 result.push_str(&format!("\n{indentation}"));
471 }
472 result.push('}');
473 result
474 }
475}
476