GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
iadavis/openqasm-extern-compilation

Branches

Tags

  • No tags available.
0Branches0Tags
Go to file
Add file
Code

Clone

HTTPS

Download ZIP

qdk/source/language_service/src/completion

source/language_service/src/completion/global_items.rs

523lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4use super::{Completion, text_edits::TextEditRange};
5use crate::{
6 compilation::Compilation,
7 protocol::{CompletionItemKind, TextEdit},
8};
9use qsc::{
10 NamespaceId, PRELUDE,
11 display::{CodeDisplay, Lookup},
12 hir::{CallableDecl, ItemId, ItemKind, ty::Udt},
13 resolve::{Local, NameKind},
14};
15use rustc_hash::FxHashSet;
16use std::{cmp::Ordering, mem::take, rc::Rc};
17
18/// Provides the globals that are visible or importable at the cursor offset.
19pub(super) struct Globals<'a> {
20 compilation: &'a Compilation,
21 locals: Vec<Local>,
22}
23
24impl<'a> Globals<'a> {
25 pub fn init(offset: u32, compilation: &'a Compilation) -> Self {
26 let global_scope = &compilation.user_unit().ast.globals;
27 let mut locals = compilation.user_unit().ast.locals.get_all_at_offset(offset);
28
29 // Always include the prelude as an imported namespace as well
30 locals.extend(PRELUDE.iter().filter_map(|ns| {
31 let namespace_id = global_scope.find_namespace(ns.iter().copied(), None);
32 namespace_id.map(|namespace_id| Local::NamespaceImport(namespace_id, None))
33 }));
34
35 Self {
36 compilation,
37 locals,
38 }
39 }
40
41 /// Returns all terms, and any namespaces that may lead to terms, that
42 /// are available at the current offset.
43 ///
44 /// If an item's name is not in scope, includes the item with any
45 /// text edits (auto-imports, etc.) to bring it into scope.
46 pub fn expr_names(&self, edit_range: &TextEditRange) -> Vec<Vec<Completion>> {
47 // include UDTs as well since they can be constructors
48 let mut completions = self.items(
49 NameKind::Term,
50 false, // in_scope_only
51 Some(edit_range),
52 );
53
54 completions.push(self.namespaces());
55
56 completions
57 }
58
59 /// Returns all types, and any namespaces that may lead to types, that
60 /// are available at the current offset.
61 ///
62 /// If an item's name is not in scope, includes the item with any
63 /// text edits (auto-imports, etc.) to bring it into scope.
64 pub fn type_names(&self, edit_range: &TextEditRange) -> Vec<Vec<Completion>> {
65 let mut completions = self.items(
66 NameKind::Ty,
67 false, // in_scope_only
68 Some(edit_range),
69 );
70
71 completions.push(self.namespaces());
72
73 completions
74 }
75
76 /// Returns all importables, and any namespaces that may lead to importables,
77 /// that are available at the current offset.
78 ///
79 /// If an item's name is not in scope, the item is *not* included,
80 /// as it wouldn't quite make sense, for an `import` completion to
81 /// bring in text edits that auto-import other items.
82 pub fn importable_names(&self) -> Vec<Vec<Completion>> {
83 // include UDTs as well since they can be constructors
84 let mut completions = self.items(
85 NameKind::Importable,
86 true, // in_scope_only
87 None,
88 );
89
90 completions.push(self.namespaces());
91
92 completions
93 }
94
95 /// Returns all namespaces that are available at the current offset.
96 pub fn namespaces(&self) -> Vec<Completion> {
97 self.namespaces_in(&[]).into_iter().flatten().collect()
98 }
99
100 /// Returns all terms, and any namespaces that may lead to terms, that
101 /// match the given qualifier prefix.
102 pub fn expr_names_in(&self, qualifier: &[Rc<str>]) -> Vec<Vec<Completion>> {
103 let mut groups = self.items_in(qualifier, NameKind::Term);
104
105 groups.extend(self.namespaces_in(qualifier));
106 groups
107 }
108
109 /// Returns all types, and any namespaces that may lead to types, that
110 /// match the given qualifier prefix.
111 pub fn type_names_in(&self, qualifier: &[Rc<str>]) -> Vec<Vec<Completion>> {
112 let mut groups = self.items_in(qualifier, NameKind::Ty);
113
114 groups.extend(self.namespaces_in(qualifier));
115 groups
116 }
117
118 /// Returns all importables, and any namespaces that may lead to importables, that
119 /// match the given qualifier prefix.
120 pub fn importable_names_in(&self, qualifier: &[Rc<str>]) -> Vec<Vec<Completion>> {
121 let mut groups = self.items_in(qualifier, NameKind::Importable);
122
123 groups.extend(self.namespaces_in(qualifier));
124 groups
125 }
126
127 /// Returns all namespaces that match the given qualifier prefix.
128 pub fn namespaces_in(&self, qualifier: &[Rc<str>]) -> Vec<Vec<Completion>> {
129 let namespaces_matching_qualifier = self.namespaces_matching_qualifier(qualifier);
130
131 let mut children = namespaces_matching_qualifier
132 .flat_map(|namespace| self.global_scope().namespace_children(namespace))
133 .collect::<Vec<_>>();
134
135 children.sort();
136 children.dedup();
137
138 vec![
139 children
140 .into_iter()
141 .map(|name| Completion::new(name.to_string(), CompletionItemKind::Module))
142 .collect(),
143 ]
144 }
145
146 /// Returns all item names that are available at the current offset,
147 /// taking into account any imports that are in scope.
148 ///
149 /// If the item name is not in scope, and `in_scope_only` is false,
150 /// includes the item with text edits (auto-imports, etc.) to bring the item into scope.
151 ///
152 /// e.g. if the following imports are in scope:
153 /// `import A.*;`
154 /// `import B as C;`
155 ///
156 /// Then, if `in_scope_only` is false:
157 /// - Items from namespace `A` will be included without any edits
158 /// - Items from `B` will be included as `C.<item_name>`
159 /// - Items will any other namespace will include an auto-import edit,
160 /// `import D.<item_name>;` to bring the item into scope.
161 ///
162 /// If `in_scope_only` is true, then only items from `A` will be included.
163 fn items(
164 &self,
165 name_kind: NameKind,
166 in_scope_only: bool,
167 edit_range: Option<&TextEditRange>,
168 ) -> Vec<Vec<Completion>> {
169 let namespaces = self.namespaces_to_search(name_kind, in_scope_only);
170 self.items_in_namespaces(namespaces, name_kind, edit_range)
171 }
172
173 /// Returns all items that match the given qualifier prefix.
174 ///
175 /// The qualifier is resolved taking into account any imports that are in scope.
176 /// e.g. `A.` will return items in:
177 /// - namespace `A`
178 /// - namespace `B` if an `import B as A;` is in scope
179 /// - namespace `C.A` if an `import C.*` is in scope
180 fn items_in(&'a self, qualifier: &[Rc<str>], name_kind: NameKind) -> Vec<Vec<Completion>> {
181 let namespaces = self
182 .namespaces_matching_qualifier(qualifier)
183 .map(|namespace_id| (namespace_id, Availability::Qualified));
184
185 self.items_in_namespaces(namespaces, name_kind, None)
186 }
187
188 /// Gathers all namespaces and their availability information, i.e. whether
189 /// they are already open in the current scope or need a text edit to bring them into scope.
190 fn namespaces_to_search(
191 &self,
192 name_kind: NameKind,
193 in_scope_only: bool,
194 ) -> impl Iterator<Item = (NamespaceId, Availability)> {
195 let open_namespaces = self.namespaces_matching_qualifier(&[]).collect::<Vec<_>>();
196
197 let namespaces: FxHashSet<NamespaceId> = if in_scope_only {
198 // Only include already open namespaces
199 open_namespaces.iter().copied().collect()
200 } else {
201 // Include all known namespaces
202 self.global_scope()
203 .table(name_kind)
204 .iter()
205 .map(|(namespace_id, _)| namespace_id)
206 .collect()
207 };
208
209 namespaces.into_iter().filter_map(move |namespace| {
210 if open_namespaces.contains(&namespace) {
211 // Namespace already in open in the current scope
212 Some((namespace, Availability::InScope))
213 } else if let Some(alias) = self.locals.iter().find_map(|local| {
214 if let Local::NamespaceImport(imported, Some(alias)) = local {
215 if namespace == *imported {
216 return Some(alias.clone());
217 }
218 }
219 None
220 }) {
221 // Namespace is imported with an alias
222 Some((namespace, Availability::InAliasedNamespace(alias)))
223 } else if self
224 .global_scope()
225 .format_namespace_name(namespace)
226 .starts_with("Std.OpenQASM")
227 {
228 // Don't suggest auto-imports for OpenQASM namespaces
229 None
230 } else {
231 // If there are no existing exact or glob imports of the item,
232 // no open aliases for the namespace it's in,
233 // and we are not in the same namespace as the item,
234 // we need to add an import for it.
235 Some((namespace, Availability::NeedImport(namespace)))
236 }
237 })
238 }
239
240 /// Returns all namespaces that match the given qualifier prefix.
241 /// The qualifier can be empty, in which case only top-level and open namespaces
242 /// are returned.
243 ///
244 /// The qualifier is resolved taking into account any imports that are in scope.
245 /// e.g.:
246 ///
247 /// namespace A.B {}
248 /// namespace C.D {}
249 /// namespace E.A.G {}
250 /// namespace H { import C as A; import E.*; }
251 ///
252 /// `A.` inside of the namespace `H` will return `B`, `D` and `G`.
253 fn namespaces_matching_qualifier(
254 &self,
255 qualifier: &[Rc<str>],
256 ) -> impl Iterator<Item = NamespaceId> {
257 let global_scope = &self.compilation.user_unit().ast.globals;
258 self.locals
259 .iter()
260 .filter_map(|local| match local {
261 Local::NamespaceImport(namespace_id, None) => global_scope
262 .find_namespace(qualifier.iter().map(AsRef::as_ref), Some(*namespace_id)),
263 Local::NamespaceImport(namespace_id, Some(alias))
264 if Some(alias) == qualifier.first() =>
265 {
266 global_scope.find_namespace(
267 qualifier[1..].iter().map(AsRef::as_ref),
268 Some(*namespace_id),
269 )
270 }
271 _ => None,
272 })
273 .chain(global_scope.find_namespace(qualifier.iter().map(AsRef::as_ref), None))
274 }
275
276 /// Collects all matching items in the given namespaces and returns
277 /// them as completions.
278 fn items_in_namespaces(
279 &self,
280 namespaces: impl IntoIterator<Item = (NamespaceId, Availability)>,
281 name_kind: NameKind,
282 edit_range: Option<&TextEditRange>,
283 ) -> Vec<Vec<Completion>> {
284 let mut candidates = Vec::new();
285 let global_scope = self.global_scope();
286 let names_table = global_scope.table(name_kind);
287
288 for (namespace_id, namespace_availability) in namespaces {
289 if let Some(names) = names_table.get(namespace_id) {
290 for (name, res) in names {
291 if let Some(item_id) = res.item_id() {
292 let (item, _, _) = self
293 .compilation
294 .resolve_item_relative_to_user_package(&item_id);
295 let decl = match &item.kind {
296 ItemKind::Callable(callable_decl) => {
297 ItemDecl::Callable(callable_decl.as_ref())
298 }
299 ItemKind::Ty(_ident, udt) => ItemDecl::Udt(udt),
300 ItemKind::Export(..) | ItemKind::Namespace(..) => continue,
301 };
302
303 let availability = if namespace_availability != Availability::Qualified
304 && self.locals.iter().any(|local| {
305 if let Local::Item(import_item_id, ..) = local {
306 if *import_item_id == item_id {
307 return true;
308 }
309 }
310 false
311 }) {
312 // Item is available in the local scope through a direct import.
313 Availability::Local
314 } else {
315 namespace_availability.clone()
316 };
317
318 let item = ItemInfo {
319 item_id,
320 namespace_id,
321 name: name.clone(),
322 decl,
323 availability,
324 };
325 candidates.push(item);
326 }
327 }
328 }
329 }
330
331 // Remove duplicate paths to the same item. The same item may be available
332 // by multiple names by way of imports/exports.
333 // e.g.
334 // `namespace A { function B() : Unit {}; export B; export B as C; }`
335 // `namespace D { export A.B; }`
336 // `namespace E { open A; import A.B as X }`
337 // Makes the same item available as `A.B`, `A.C`, `D.B`, `B` and `X`
338 // when in `namespace E`.
339
340 // We want to keep distinct names to the same item (`B`, `C`) but
341 // not distinct paths to the same item (`A.B`, `D.B`).
342
343 // Sort by availability so that direct imports and in-scope names
344 // are preferred when de-duping.
345
346 // When tied, prefer the smaller namespace ID, assuming that that's the "original" namespace,
347 // but really that's just a heuristic when we don't have much else to go on.
348 candidates.sort_by_key(|i| {
349 (
350 i.item_id,
351 i.name.clone(),
352 i.availability.clone(),
353 i.namespace_id,
354 )
355 });
356
357 candidates.dedup_by_key(|i| (i.item_id, i.name.clone()));
358
359 // Drop any items that were direct local imports, since the locals completion module
360 // would have already included them in the ultimate completion list
361 candidates.retain(|item| !matches!(item.availability, Availability::Local));
362
363 self.to_completions(candidates, edit_range)
364 }
365
366 /// Turns the final list of items into completion items, filling in
367 /// details and including any text edits if requested.
368 ///
369 /// Items are sorted by package, with the user package (`None`)
370 /// coming first, with the dependencies in reverse order, so
371 /// that the "closer" dependencies are listed first in the completion list.
372 fn to_completions(
373 &self,
374 mut items: Vec<ItemInfo<'_>>,
375 edit_range: Option<&TextEditRange>,
376 ) -> Vec<Vec<Completion>> {
377 items.sort_by(|a, b| match (a.item_id.package, b.item_id.package) {
378 (None, Some(_)) => Ordering::Greater,
379 (Some(_), None) => Ordering::Less,
380 (a, b) => a.cmp(&b),
381 });
382 items.reverse();
383
384 let mut groups = Vec::new();
385 let mut group = Vec::new();
386 let mut last_package_id = items.first().and_then(|item| item.item_id.package);
387
388 for item in items {
389 let curr_package_id = item.item_id.package;
390 if curr_package_id != last_package_id {
391 // push the group to the groups
392 if !group.is_empty() {
393 groups.push(take(&mut group));
394 }
395 }
396 let completion = self.to_completion(&item, edit_range);
397
398 group.push(completion);
399 last_package_id = curr_package_id;
400 }
401
402 if !group.is_empty() {
403 groups.push(take(&mut group));
404 }
405
406 groups
407 }
408
409 /// Creates a completion list entry for the given item, including
410 /// any text edits that would bring the item into scope, if requested.
411 fn to_completion(&self, item: &ItemInfo<'a>, text_edits: Option<&TextEditRange>) -> Completion {
412 let display = CodeDisplay {
413 compilation: self.compilation,
414 };
415 let (kind, display) = match &item.decl {
416 ItemDecl::Callable(callable_decl) => (
417 CompletionItemKind::Function,
418 display.hir_callable_decl(callable_decl).to_string(),
419 ),
420 ItemDecl::Udt(udt) => (
421 CompletionItemKind::Interface,
422 display.hir_udt(udt).to_string(),
423 ),
424 };
425
426 // Deprioritize names starting with "__" in the completion list
427 let mut sort_priority = u32::from(item.name.starts_with("__"));
428
429 match &item.availability {
430 Availability::Local | Availability::InScope | Availability::Qualified => {
431 Completion::with_text_edits(
432 item.name.to_string(),
433 kind,
434 Some(display),
435 None,
436 sort_priority,
437 )
438 }
439 Availability::NeedImport(namespace) => {
440 // Deprioritize auto-import items
441 sort_priority += 1;
442
443 let text_edits = text_edits.expect(
444 "a text edit range should have been provided if `in_scope_only` is false",
445 );
446 // if there is no place to insert an import, then we can't add an import.
447 let edits = text_edits.insert_import_at.as_ref().map(|range| {
448 vec![TextEdit {
449 new_text: format!(
450 "import {}.{};{}",
451 self.global_scope().format_namespace_name(*namespace),
452 item.name,
453 &text_edits.indent
454 ),
455 range: *range,
456 }]
457 });
458
459 Completion::with_text_edits(
460 item.name.to_string(),
461 kind,
462 Some(display),
463 edits,
464 sort_priority,
465 )
466 }
467 Availability::InAliasedNamespace(prefix) => Completion::with_text_edits(
468 format!("{}.{}", prefix, item.name),
469 kind,
470 Some(display),
471 None,
472 sort_priority,
473 ),
474 }
475 }
476
477 fn global_scope(&self) -> &qsc::resolve::GlobalScope {
478 &self.compilation.user_unit().ast.globals
479 }
480}
481
482/// The global item that backs a completion item.
483struct ItemInfo<'a> {
484 item_id: ItemId,
485 namespace_id: NamespaceId,
486 /// Can be the original name for the decl,
487 /// or the alias if this item is found through an import.
488 name: Rc<str>,
489 decl: ItemDecl<'a>,
490 availability: Availability,
491}
492
493/// The declaration, used to format completion item details.
494#[derive(Debug)]
495enum ItemDecl<'a> {
496 Callable(&'a CallableDecl),
497 Udt(&'a Udt),
498}
499
500/// How the item name is available in the current scope.
501///
502/// The order here is important, as it's used when de-duping.
503/// We prefer the first kind of import if there are multiple
504/// paths leading to the same item.
505#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone)]
506enum Availability {
507 /// Available through a direct local import.
508 Local,
509 /// In scope because of open namespaces.
510 /// Safe to include without any additional edits.
511 InScope,
512 /// In scope because of preceding qualifier.
513 /// Safe to include without any additional edits.
514 Qualified,
515 /// In a namespace that is open with a local alias.
516 /// The name should be prefixed with the namespace alias.
517 ///
518 /// e.g. `Foo` will appear as `Bar.Foo` if it's under an open
519 /// namespace that is aliased as `Bar`.
520 InAliasedNamespace(Rc<str>),
521 /// Not in scope at all. Needs an auto-import entry.
522 NeedImport(NamespaceId),
523}
524