GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
efd6847eb3bce5324ed84e4e62df6dd188278813

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

394lines · 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 /// 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 should not be passed into namespace insertion")
200 }
201}
202
203impl Default for NamespaceTreeRoot {
204 fn default() -> Self {
205 let mut tree = Self {
206 assigner: 0,
207 tree: Rc::new(RefCell::new(NamespaceTreeNode {
208 children: FxHashMap::default(),
209 id: NamespaceId::new(0),
210 })),
211 memo: RefCell::new(FxHashMap::default()),
212 };
213 // insert the prelude namespaces using the `NamespaceTreeRoot` API
214 for ns in &PRELUDE {
215 let iter = ns.iter().map(|s| Rc::from(*s)).peekable();
216 let _ = tree.insert_or_find_namespace(iter);
217 }
218 tree
219 }
220}
221
222/// A node in the namespace tree. Each node has a unique ID and a map of children.
223/// Supports interior mutability of children for inserting new nodes.
224#[derive(Clone)]
225pub struct NamespaceTreeNode {
226 pub children: FxHashMap<Rc<str>, NamespaceTreeCell>,
227 pub id: NamespaceId,
228}
229
230impl NamespaceTreeNode {
231 /// Create a new namespace tree node with the given ID and children. The `id` should come from the `NamespaceTreeRoot` assigner.
232 #[must_use]
233 fn new(id: NamespaceId, children: FxHashMap<Rc<str>, NamespaceTreeCell>) -> Self {
234 Self { children, id }
235 }
236
237 /// Get a reference to the children of the namespace tree node.
238 #[must_use]
239 pub fn children(&self) -> &FxHashMap<Rc<str>, NamespaceTreeCell> {
240 &self.children
241 }
242
243 /// See [`FxHashMap::get`] for more information.
244 fn get(&self, component: &Rc<str>) -> Option<NamespaceTreeCell> {
245 self.children.get(component).cloned()
246 }
247
248 /// Get the ID of this namespace tree node.
249 #[must_use]
250 pub fn id(&self) -> NamespaceId {
251 self.id
252 }
253
254 /// Check if this namespace tree node contains a given namespace as a child.
255 #[must_use]
256 pub fn contains<'a>(&self, ns: impl IntoIterator<Item = &'a str>) -> bool {
257 self.get_namespace_id(ns).is_some()
258 }
259
260 /// Finds the ID of a namespace given its string name. This function is generally more efficient
261 /// than [`NamespaceTreeNode::find_namespace_by_id`], as it utilizes the prefix tree structure to
262 /// find the ID in `O(n)` time, where `n` is the number of components in the namespace name.
263 pub fn get_namespace_id<'a>(
264 &self,
265 ns: impl IntoIterator<Item = &'a str>,
266 ) -> Option<NamespaceId> {
267 let mut rover: Option<NamespaceTreeCell> = None;
268 for component in ns {
269 if let Some(next_ns) = match rover {
270 None => self.get(&Rc::from(component)),
271 Some(buf) => buf.borrow().get(&Rc::from(component)),
272 } {
273 rover = Some(next_ns);
274 } else {
275 return None;
276 }
277 }
278 Some(rover.map_or_else(|| self.id, |x| x.borrow().id))
279 }
280
281 /// Inserts a new namespace into the tree, if it does not yet exist.
282 /// Returns the ID of the namespace.
283 /// Returns `None` if an empty iterator is passed in.
284 pub fn insert_or_find_namespace<I>(
285 &mut self,
286 mut iter: Peekable<I>,
287 assigner: &mut usize,
288 ) -> Option<NamespaceId>
289 where
290 I: Iterator<Item = Rc<str>>,
291 {
292 let next_item = iter.next()?;
293 let next_node = self.children.get_mut(&next_item);
294 match (next_node, iter.peek()) {
295 (Some(next_node), Some(_)) => {
296 return next_node
297 .borrow_mut()
298 .insert_or_find_namespace(iter, assigner);
299 }
300 (Some(next_node), None) => {
301 return Some(next_node.borrow().id);
302 }
303 _ => {}
304 }
305 *assigner += 1;
306 let mut new_node =
307 NamespaceTreeNode::new(NamespaceId::new(*assigner), FxHashMap::default());
308 if iter.peek().is_none() {
309 let new_node_id = new_node.id;
310 self.children
311 .insert(next_item, Rc::new(RefCell::new(new_node)));
312 Some(new_node_id)
313 } else {
314 let id = new_node.insert_or_find_namespace(iter, assigner);
315 self.children
316 .insert(next_item, Rc::new(RefCell::new(new_node)));
317 id
318 }
319 }
320
321 fn find_namespace_by_id(
322 &self,
323 id: NamespaceId,
324 names_buf: &[Rc<str>],
325 // `ids_visited` is used to avoid infinite loops in the case of cycles in the namespace tree.
326 ids_visited: &mut FxHashSet<NamespaceId>,
327 ) -> Option<(Vec<Rc<str>>, NamespaceTreeCell)> {
328 if ids_visited.contains(&self.id) {
329 return None;
330 }
331 ids_visited.insert(self.id);
332 // first, check if any children are the one we are looking for
333 for (name, node) in &self.children {
334 if node.borrow().id == id {
335 let mut names = names_buf.to_vec();
336 names.push(name.clone());
337 return Some((names, node.clone()));
338 }
339 }
340
341 // if it wasn't found, recurse into children
342 for (name, node) in &self.children {
343 let mut names = names_buf.to_vec();
344 names.push(name.clone());
345 let Some((names, node)) = node.borrow().find_namespace_by_id(id, &names, ids_visited)
346 else {
347 continue;
348 };
349 return Some((names, node));
350 }
351
352 None
353 }
354
355 fn debug_print(
356 &self,
357 indentation_level: usize,
358 visited_nodes: &mut FxHashSet<NamespaceId>,
359 ) -> String {
360 let indentation = " ".repeat(indentation_level);
361
362 if visited_nodes.contains(&self.id) {
363 return format!("\n{indentation}Cycle Detected");
364 }
365
366 visited_nodes.insert(self.id);
367
368 let mut result = String::new();
369
370 if self.children.is_empty() {
371 result.push_str("empty node");
372 } else {
373 result.push_str(&format!("\n{indentation} children: ["));
374 for (name, node) in &self.children {
375 result.push_str(&format!(
376 "\n{} {}(id {}) {{",
377 indentation,
378 name,
379 Into::<usize>::into(node.borrow().id)
380 ));
381 result.push_str(
382 node.borrow()
383 .debug_print(indentation_level + 2, visited_nodes)
384 .as_str(),
385 );
386 result.push(',');
387 }
388 result.push_str(&format!("\n{indentation} ]"));
389 result.push_str(&format!("\n{indentation}"));
390 }
391 result.push('}');
392 result
393 }
394}
395