GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
copilot/fix-2145

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

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