GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
alex/bounds

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

473lines · 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 the same, single 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 pub fn iter(&self) -> std::collections::btree_map::IntoValues<NamespaceId, Vec<Vec<Rc<str>>>> {
250 let mut stack = vec![(vec![], self.tree.clone())];
251 let mut result: Vec<(NamespaceId, Vec<Rc<str>>)> = vec![];
252 while let Some((names, node)) = stack.pop() {
253 result.push((node.borrow().id, names.clone()));
254 for (name, child) in node.borrow().children() {
255 let mut new_names = names.clone();
256 new_names.push(name.clone());
257 stack.push((new_names, child.clone()));
258 }
259 if node.borrow().children().is_empty() {
260 result.push((node.borrow().id, names));
261 }
262 }
263
264 // flatten the result into a list of paths
265
266 // use a btree map here instead of a hash map for deterministic iteration --
267 // while it shouldn't be consequential, any nondeterminism in a compiler makes
268 // things more difficult to track down then they go wrong.
269 let mut flattened_result = BTreeMap::default();
270 for (id, names) in result {
271 let entry = flattened_result.entry(id).or_insert_with(Vec::new);
272 entry.push(names);
273 }
274
275 flattened_result.into_values()
276 }
277}
278
279impl IntoIterator for &NamespaceTreeRoot {
280 type Item = Vec<Vec<Rc<str>>>;
281 type IntoIter = std::collections::btree_map::IntoValues<NamespaceId, Vec<Vec<Rc<str>>>>;
282
283 fn into_iter(self) -> Self::IntoIter {
284 self.iter()
285 }
286}
287
288impl Default for NamespaceTreeRoot {
289 fn default() -> Self {
290 Self {
291 assigner: 0,
292 tree: Rc::new(RefCell::new(NamespaceTreeNode {
293 children: FxHashMap::default(),
294 id: NamespaceId::new(0),
295 })),
296 memo: RefCell::new(FxHashMap::default()),
297 }
298 }
299}
300
301/// A node in the namespace tree. Each node has a unique ID and a map of children.
302/// Supports interior mutability of children for inserting new nodes.
303#[derive(Clone)]
304pub struct NamespaceTreeNode {
305 pub children: FxHashMap<Rc<str>, NamespaceTreeCell>,
306 pub id: NamespaceId,
307}
308
309impl NamespaceTreeNode {
310 /// Create a new namespace tree node with the given ID and children. The `id` should come from the `NamespaceTreeRoot` assigner.
311 #[must_use]
312 fn new(id: NamespaceId, children: FxHashMap<Rc<str>, NamespaceTreeCell>) -> Self {
313 Self { children, id }
314 }
315
316 /// Get a reference to the children of the namespace tree node.
317 #[must_use]
318 pub fn children(&self) -> &FxHashMap<Rc<str>, NamespaceTreeCell> {
319 &self.children
320 }
321
322 /// See [`FxHashMap::get`] for more information.
323 fn get(&self, component: &Rc<str>) -> Option<NamespaceTreeCell> {
324 self.children.get(component).cloned()
325 }
326
327 /// Get the ID of this namespace tree node.
328 #[must_use]
329 pub fn id(&self) -> NamespaceId {
330 self.id
331 }
332
333 /// Check if this namespace tree node contains a given namespace as a child.
334 #[must_use]
335 pub fn contains<'a>(&self, ns: impl IntoIterator<Item = &'a str>) -> bool {
336 self.get_namespace_id(ns).is_some()
337 }
338
339 /// Finds the ID of a namespace given its string name. This function is generally more efficient
340 /// than [`NamespaceTreeNode::find_namespace_by_id`], as it utilizes the prefix tree structure to
341 /// find the ID in `O(n)` time, where `n` is the number of components in the namespace name.
342 pub fn get_namespace_id<'a>(
343 &self,
344 ns: impl IntoIterator<Item = &'a str>,
345 ) -> Option<NamespaceId> {
346 let mut rover: Option<NamespaceTreeCell> = None;
347 for component in ns {
348 if let Some(next_ns) = match rover {
349 None => self.get(&Rc::from(component)),
350 Some(buf) => buf.borrow().get(&Rc::from(component)),
351 } {
352 rover = Some(next_ns);
353 } else {
354 return None;
355 }
356 }
357 Some(rover.map_or_else(|| self.id, |x| x.borrow().id))
358 }
359
360 /// Inserts a new namespace into the tree, if it does not yet exist.
361 /// Returns the ID of the namespace.
362 /// Returns `None` if an empty iterator is passed in.
363 pub fn insert_or_find_namespace<I>(
364 &mut self,
365 mut iter: Peekable<I>,
366 assigner: &mut usize,
367 ) -> Option<NamespaceId>
368 where
369 I: Iterator<Item = Rc<str>>,
370 {
371 let next_item = iter.next()?;
372 let next_node = self.children.get_mut(&next_item);
373 match (next_node, iter.peek()) {
374 (Some(next_node), Some(_)) => {
375 return next_node
376 .borrow_mut()
377 .insert_or_find_namespace(iter, assigner);
378 }
379 (Some(next_node), None) => {
380 return Some(next_node.borrow().id);
381 }
382 _ => {}
383 }
384 *assigner += 1;
385 let mut new_node =
386 NamespaceTreeNode::new(NamespaceId::new(*assigner), FxHashMap::default());
387 if iter.peek().is_none() {
388 let new_node_id = new_node.id;
389 self.children
390 .insert(next_item, Rc::new(RefCell::new(new_node)));
391 Some(new_node_id)
392 } else {
393 let id = new_node.insert_or_find_namespace(iter, assigner);
394 self.children
395 .insert(next_item, Rc::new(RefCell::new(new_node)));
396 id
397 }
398 }
399
400 fn find_namespace_by_id(
401 &self,
402 id: NamespaceId,
403 names_buf: &[Rc<str>],
404 // `ids_visited` is used to avoid infinite loops in the case of cycles in the namespace tree.
405 ids_visited: &mut FxHashSet<NamespaceId>,
406 ) -> Option<(Vec<Rc<str>>, NamespaceTreeCell)> {
407 if ids_visited.contains(&self.id) {
408 return None;
409 }
410 ids_visited.insert(self.id);
411 // first, check if any children are the one we are looking for
412 for (name, node) in &self.children {
413 if node.borrow().id == id {
414 let mut names = names_buf.to_vec();
415 names.push(name.clone());
416 return Some((names, node.clone()));
417 }
418 }
419
420 // if it wasn't found, recurse into children
421 for (name, node) in &self.children {
422 let mut names = names_buf.to_vec();
423 names.push(name.clone());
424 let Some((names, node)) = node.borrow().find_namespace_by_id(id, &names, ids_visited)
425 else {
426 continue;
427 };
428 return Some((names, node));
429 }
430
431 None
432 }
433
434 fn debug_print(
435 &self,
436 indentation_level: usize,
437 visited_nodes: &mut FxHashSet<NamespaceId>,
438 ) -> String {
439 let indentation = " ".repeat(indentation_level);
440
441 if visited_nodes.contains(&self.id) {
442 return format!("\n{indentation}Cycle Detected");
443 }
444
445 visited_nodes.insert(self.id);
446
447 let mut result = String::new();
448
449 if self.children.is_empty() {
450 result.push_str("empty node");
451 } else {
452 result.push_str(&format!("\n{indentation} children: ["));
453 for (name, node) in &self.children {
454 result.push_str(&format!(
455 "\n{} {}(id {}) {{",
456 indentation,
457 name,
458 Into::<usize>::into(node.borrow().id)
459 ));
460 result.push_str(
461 node.borrow()
462 .debug_print(indentation_level + 2, visited_nodes)
463 .as_str(),
464 );
465 result.push(',');
466 }
467 result.push_str(&format!("\n{indentation} ]"));
468 result.push_str(&format!("\n{indentation}"));
469 }
470 result.push('}');
471 result
472 }
473}
474