GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

mirrored from https://github.com/microsoft/qdkAvailable

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
00152589a34aaa1d8ec3117bf9be2b6cf204b77e

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

293lines · 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;
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(Debug, Clone)]
80pub struct NamespaceTreeRoot {
81 assigner: usize,
82 tree: NamespaceTreeCell,
83 memo: RefCell<FxHashMap<NamespaceId, MemoEntry>>,
84}
85
86impl NamespaceTreeRoot {
87 /// Create a new namespace tree root. The assigner is used to assign new namespace IDs.
88 #[must_use]
89 pub fn new_from_parts(assigner: usize, tree: NamespaceTreeNode) -> Self {
90 Self {
91 assigner,
92 tree: Rc::new(RefCell::new(tree)),
93 memo: RefCell::new(FxHashMap::default()),
94 }
95 }
96
97 /// Get the namespace tree field. This is the root of the namespace tree.
98 #[must_use]
99 pub fn tree(&self) -> NamespaceTreeCell {
100 self.tree.clone()
101 }
102
103 /// Insert a namespace into the tree. If the namespace already exists, return its ID.
104 /// Panics if the `ns` iterator is empty.
105 #[must_use]
106 pub fn insert_or_find_namespace(
107 &mut self,
108 ns: impl IntoIterator<Item = Rc<str>>,
109 ) -> NamespaceId {
110 self.tree
111 .borrow_mut()
112 .insert_or_find_namespace(ns.into_iter().peekable(), &mut self.assigner)
113 .expect("namespace creation should not fail")
114 }
115
116 /// Get the ID of a namespace given its name.
117 pub fn get_namespace_id<'a>(
118 &self,
119 ns: impl IntoIterator<Item = &'a str>,
120 ) -> Option<NamespaceId> {
121 self.tree.borrow().get_namespace_id(ns)
122 }
123
124 /// Given a [`NamespaceId`], find the namespace in the tree. Note that this function is not
125 /// particularly efficient, as it performs a breadth-first search. The results of this search
126 /// are memoized to avoid repeated lookups, reducing the impact of the BFS.
127 #[must_use]
128 pub fn find_namespace_by_id(&self, id: &NamespaceId) -> (Vec<Rc<str>>, NamespaceTreeCell) {
129 if let Some(res) = self.memo.borrow().get(id) {
130 return res.clone();
131 }
132 let (names, node) = self
133 .tree
134 .borrow()
135 .find_namespace_by_id(*id, &[])
136 .unwrap_or_else(|| (vec![], self.tree.clone()));
137
138 self.memo
139 .borrow_mut()
140 .insert(*id, (names.clone(), node.clone()));
141 (names, node.clone())
142 }
143
144 #[must_use]
145 pub fn root_id(&self) -> NamespaceId {
146 self.tree.borrow().id
147 }
148}
149
150impl Default for NamespaceTreeRoot {
151 fn default() -> Self {
152 let mut tree = Self {
153 assigner: 0,
154 tree: Rc::new(RefCell::new(NamespaceTreeNode {
155 children: FxHashMap::default(),
156 id: NamespaceId::new(0),
157 })),
158 memo: RefCell::new(FxHashMap::default()),
159 };
160 // insert the prelude namespaces using the `NamespaceTreeRoot` API
161 for ns in &PRELUDE {
162 let iter = ns.iter().map(|s| Rc::from(*s)).peekable();
163 let _ = tree.insert_or_find_namespace(iter);
164 }
165 tree
166 }
167}
168
169/// A node in the namespace tree. Each node has a unique ID and a map of children.
170/// Supports interior mutability of children for inserting new nodes.
171#[derive(Debug, Clone)]
172pub struct NamespaceTreeNode {
173 pub children: FxHashMap<Rc<str>, NamespaceTreeCell>,
174 pub id: NamespaceId,
175}
176impl NamespaceTreeNode {
177 /// Create a new namespace tree node with the given ID and children. The `id` should come from the `NamespaceTreeRoot` assigner.
178 #[must_use]
179 fn new(id: NamespaceId, children: FxHashMap<Rc<str>, NamespaceTreeCell>) -> Self {
180 Self { children, id }
181 }
182
183 /// Get a reference to the children of the namespace tree node.
184 #[must_use]
185 pub fn children(&self) -> &FxHashMap<Rc<str>, NamespaceTreeCell> {
186 &self.children
187 }
188
189 /// See [`FxHashMap::get`] for more information.
190 fn get(&self, component: &Rc<str>) -> Option<NamespaceTreeCell> {
191 self.children.get(component).cloned()
192 }
193
194 /// Get the ID of this namespace tree node.
195 #[must_use]
196 pub fn id(&self) -> NamespaceId {
197 self.id
198 }
199
200 /// Check if this namespace tree node contains a given namespace as a child.
201 #[must_use]
202 pub fn contains<'a>(&self, ns: impl IntoIterator<Item = &'a str>) -> bool {
203 self.get_namespace_id(ns).is_some()
204 }
205
206 /// Finds the ID of a namespace given its string name. This function is generally more efficient
207 /// than [`NamespaceTreeNode::find_namespace_by_id`], as it utilizes the prefix tree structure to
208 /// find the ID in `O(n)` time, where `n` is the number of components in the namespace name.
209 pub fn get_namespace_id<'a>(
210 &self,
211 ns: impl IntoIterator<Item = &'a str>,
212 ) -> Option<NamespaceId> {
213 let mut buf: Option<NamespaceTreeCell> = None;
214 for component in ns {
215 if let Some(next_ns) = match buf {
216 None => self.get(&Rc::from(component)),
217 Some(buf) => buf.borrow().get(&Rc::from(component)),
218 } {
219 buf = Some(next_ns);
220 } else {
221 return None;
222 }
223 }
224 Some(buf.map_or_else(|| self.id, |x| x.borrow().id))
225 }
226
227 /// Inserts a new namespace into the tree, if it does not yet exist.
228 /// Returns the ID of the namespace.
229 /// Returns `None` if an empty iterator is passed in.
230 pub fn insert_or_find_namespace<I>(
231 &mut self,
232 mut iter: Peekable<I>,
233 assigner: &mut usize,
234 ) -> Option<NamespaceId>
235 where
236 I: Iterator<Item = Rc<str>>,
237 {
238 let next_item = iter.next()?;
239 let next_node = self.children.get_mut(&next_item);
240 match (next_node, iter.peek()) {
241 (Some(next_node), Some(_)) => {
242 return next_node
243 .borrow_mut()
244 .insert_or_find_namespace(iter, assigner);
245 }
246 (Some(next_node), None) => {
247 return Some(next_node.borrow().id);
248 }
249 _ => {}
250 }
251 *assigner += 1;
252 let mut new_node =
253 NamespaceTreeNode::new(NamespaceId::new(*assigner), FxHashMap::default());
254 if iter.peek().is_none() {
255 let new_node_id = new_node.id;
256 self.children
257 .insert(next_item, Rc::new(RefCell::new(new_node)));
258 Some(new_node_id)
259 } else {
260 let id = new_node.insert_or_find_namespace(iter, assigner);
261 self.children
262 .insert(next_item, Rc::new(RefCell::new(new_node)));
263 id
264 }
265 }
266
267 fn find_namespace_by_id(
268 &self,
269 id: NamespaceId,
270 names_buf: &[Rc<str>],
271 ) -> Option<(Vec<Rc<str>>, NamespaceTreeCell)> {
272 // first, check if any children are the one we are looking for
273 for (name, node) in &self.children {
274 if node.borrow().id == id {
275 let mut names = names_buf.to_vec();
276 names.push(name.clone());
277 return Some((names, node.clone()));
278 }
279 }
280
281 // if it wasn't found, recurse into children
282 for (name, node) in &self.children {
283 let mut names = names_buf.to_vec();
284 names.push(name.clone());
285 let Some((names, node)) = node.borrow().find_namespace_by_id(id, &names) else {
286 continue;
287 };
288 return Some((names, node));
289 }
290
291 None
292 }
293}
294