microsoft/qdk
Publicmirrored from https://github.com/microsoft/qdkAvailable
source/compiler/qsc_frontend/src/resolve/imports.rs
524lines · modecode
| 1 | // Copyright (c) Microsoft Corporation. |
| 2 | // Licensed under the MIT License. |
| 3 | |
| 4 | use super::{Error, Importable, NameKind, Res, Resolver, ScopeKind}; |
| 5 | use crate::compile::preprocess::TrackedName; |
| 6 | use qsc_ast::ast::{ |
| 7 | Block, Ident, Idents as _, ImportKind, ImportOrExportDecl, Item, ItemKind, NodeId, Package, |
| 8 | Path, PathKind, StmtKind, TopLevelNode, |
| 9 | }; |
| 10 | use qsc_data_structures::{namespaces::NamespaceId, span::Span}; |
| 11 | use rustc_hash::FxHashMap; |
| 12 | use std::{collections::hash_map::Entry, rc::Rc}; |
| 13 | |
| 14 | const MAX_ITERATIONS: usize = 100; |
| 15 | |
| 16 | /// Resolves all imports and exports declared in namespace scopes in the package. |
| 17 | /// Exports are then made available in the global scope, whereas imports are made |
| 18 | /// available in the namespace scope they are declared in. |
| 19 | pub(super) fn resolve_all_namespace_imports_and_exports( |
| 20 | resolver: &mut Resolver, |
| 21 | package: &Package, |
| 22 | ) { |
| 23 | let errors = iterate_until_done(|attempted_imports| { |
| 24 | let mut new_imports_were_added = false; |
| 25 | |
| 26 | for node in &package.nodes { |
| 27 | if let TopLevelNode::Namespace(namespace) = node { |
| 28 | let namespace_id = resolver |
| 29 | .globals |
| 30 | .find_namespace(namespace.name.str_iter(), None) |
| 31 | .expect("expected to find namespace"); // namespace name should have been added in the name binding pass |
| 32 | |
| 33 | resolver.push_scope(namespace.span, ScopeKind::Namespace(namespace_id)); |
| 34 | |
| 35 | resolver.resolve_and_add_open(&namespace.name, None); |
| 36 | |
| 37 | if try_resolve_imports_and_exports( |
| 38 | resolver, |
| 39 | || namespace.items.iter().map(AsRef::as_ref), |
| 40 | attempted_imports, |
| 41 | ) { |
| 42 | new_imports_were_added = true; |
| 43 | } |
| 44 | |
| 45 | resolver.pop_scope(); |
| 46 | } |
| 47 | } |
| 48 | |
| 49 | new_imports_were_added |
| 50 | }); |
| 51 | resolver.errors.extend(errors); |
| 52 | } |
| 53 | |
| 54 | /// Resolve all imports declared in top-level statements. |
| 55 | /// Imports are then made available in the persistent local scope. |
| 56 | pub(super) fn resolve_top_level_imports(resolver: &mut Resolver, package: &Package) { |
| 57 | let errors = iterate_until_done(|attempted_imports| { |
| 58 | try_resolve_imports_and_exports( |
| 59 | resolver, |
| 60 | || { |
| 61 | package.nodes.iter().filter_map(|node| { |
| 62 | if let TopLevelNode::Stmt(stmt) = node |
| 63 | && let StmtKind::Item(item) = &*stmt.kind |
| 64 | { |
| 65 | return Some(item.as_ref()); |
| 66 | } |
| 67 | None |
| 68 | }) |
| 69 | }, |
| 70 | attempted_imports, |
| 71 | ) |
| 72 | }); |
| 73 | resolver.errors.extend(errors); |
| 74 | } |
| 75 | |
| 76 | /// Resolve all imports declared in a block. |
| 77 | /// Imports are then made available in that block's scope. |
| 78 | pub(super) fn resolve_block_imports(resolver: &mut Resolver, block: &Block) { |
| 79 | let errors = iterate_until_done(|attempted_imports| { |
| 80 | try_resolve_imports_and_exports( |
| 81 | resolver, |
| 82 | || { |
| 83 | block.stmts.iter().filter_map(|stmt| { |
| 84 | if let StmtKind::Item(item) = &*stmt.kind { |
| 85 | Some(item.as_ref()) |
| 86 | } else { |
| 87 | None |
| 88 | } |
| 89 | }) |
| 90 | }, |
| 91 | attempted_imports, |
| 92 | ) |
| 93 | }); |
| 94 | resolver.errors.extend(errors); |
| 95 | } |
| 96 | |
| 97 | /// Makes a single pass over the imports and exports in the current scope, |
| 98 | /// attempting to resolve them. |
| 99 | /// |
| 100 | /// Once an import has been successfully resolved, its name is made available |
| 101 | /// in the current scope. |
| 102 | /// |
| 103 | /// Exports are only handled if the current scope is a namespace, and |
| 104 | /// once successfully resolved, their names will be added to the global scope. |
| 105 | /// |
| 106 | /// Note that this single pass may not result in all imports being resolved. |
| 107 | /// Multiple passes will ensure that any imports referencing other imports |
| 108 | /// in the same scope are resolved. |
| 109 | /// |
| 110 | /// For this reason, resolution errors are not reported immediately, but |
| 111 | /// instead stored in `attempted_imports` to be retried later. Returns |
| 112 | /// `true` if any new imports or exports were bound in the current scope, |
| 113 | /// as a signal that we should continue iterating. |
| 114 | fn try_resolve_imports_and_exports<'a, I>( |
| 115 | resolver: &mut Resolver, |
| 116 | scope_items_iter: impl Fn() -> I, |
| 117 | attempted_imports: &mut FxHashMap<NodeId, Result<(), Error>>, |
| 118 | ) -> bool |
| 119 | where |
| 120 | I: Iterator<Item = &'a Item>, |
| 121 | { |
| 122 | if scope_items_iter().count() == 0 { |
| 123 | // If there are no items in this scope, short-circuit. |
| 124 | return false; |
| 125 | } |
| 126 | |
| 127 | let mut new_imports_added = false; |
| 128 | |
| 129 | // Start by adding the opens and wildcard imports in this scope |
| 130 | |
| 131 | // Handle all opens first |
| 132 | for item in scope_items_iter() { |
| 133 | if let ItemKind::Open(PathKind::Ok(path), alias) = &*item.kind { |
| 134 | resolver.resolve_and_add_open(path.as_ref(), alias.as_deref()); |
| 135 | } |
| 136 | } |
| 137 | |
| 138 | // Wildcard imports are treated as opens, handle them too |
| 139 | for item in scope_items_iter() { |
| 140 | if let ItemKind::ImportOrExport(decl) = &*item.kind { |
| 141 | for item in iter_valid_items(decl) { |
| 142 | if let ImportKind::Wildcard = item.kind { |
| 143 | resolver.resolve_and_add_open(item.path, None); |
| 144 | } |
| 145 | } |
| 146 | } |
| 147 | } |
| 148 | |
| 149 | // Now, attempt to resolve all imports, and exports if we're in a namespace scope |
| 150 | for item in scope_items_iter() { |
| 151 | if let ItemKind::ImportOrExport(decl) = &*item.kind |
| 152 | && try_resolve_import_or_export_decl(resolver, decl, attempted_imports) |
| 153 | { |
| 154 | new_imports_added = true; |
| 155 | } |
| 156 | } |
| 157 | |
| 158 | new_imports_added |
| 159 | } |
| 160 | |
| 161 | /// Returns `true` if this call caused new imports to become available in the scope. |
| 162 | /// This is used to decide whether we should keep iterating and resolving imports. |
| 163 | fn try_resolve_import_or_export_decl( |
| 164 | resolver: &mut Resolver, |
| 165 | decl: &ImportOrExportDecl, |
| 166 | attempted_imports: &mut FxHashMap<NodeId, Result<(), Error>>, |
| 167 | ) -> bool { |
| 168 | // The current namespace, if we're in a namespace scope. |
| 169 | let current_namespace = { |
| 170 | let current_scope = resolver.current_scope_mut(); |
| 171 | if let ScopeKind::Namespace(ns_id) = current_scope.kind { |
| 172 | Some(ns_id) |
| 173 | } else { |
| 174 | None |
| 175 | } |
| 176 | }; |
| 177 | |
| 178 | // If we're not in a namespace scope, exports are not allowed. |
| 179 | if decl.is_export() && current_namespace.is_none() { |
| 180 | resolver.errors.push(Error::ExportFromLocalScope(decl.span)); |
| 181 | return false; |
| 182 | } |
| 183 | |
| 184 | let mut any_names_were_added = false; |
| 185 | for valid_item in iter_valid_items(decl) { |
| 186 | match &valid_item.kind { |
| 187 | ImportKind::Wildcard => { |
| 188 | // We handled wildcard imports already as open statements |
| 189 | } |
| 190 | ImportKind::Direct { .. } => { |
| 191 | if attempted_imports |
| 192 | .get(&valid_item.name().id) |
| 193 | .is_some_and(Result::is_ok) |
| 194 | { |
| 195 | // If this item has already been bound, skip it. |
| 196 | continue; |
| 197 | } |
| 198 | |
| 199 | // filter out any dropped names |
| 200 | // this is so you can still export an item that has been conditionally removed from compilation |
| 201 | // without a resolution error in the export statement itself |
| 202 | // This is not a perfect solution, re-exporting an aliased name from another namespace that has been |
| 203 | // conditionally compiled out will still fail. However, this is the only way to solve this |
| 204 | // problem without upleveling the preprocessor into the resolver, so it can do resolution-aware |
| 205 | // dropped_names population. |
| 206 | if valid_item.is_export |
| 207 | && let Some(current_namespace) = ¤t_namespace |
| 208 | { |
| 209 | let current_namespace_name = |
| 210 | resolver.globals.format_namespace_name(*current_namespace); |
| 211 | if resolver.dropped_names.contains(&TrackedName { |
| 212 | name: valid_item.path.name.name.clone(), |
| 213 | namespace: Rc::from(current_namespace_name), |
| 214 | }) { |
| 215 | continue; |
| 216 | } |
| 217 | } |
| 218 | |
| 219 | let (resolution_result, name_was_added) = |
| 220 | try_resolve_import_or_export(resolver, current_namespace, &valid_item); |
| 221 | |
| 222 | attempted_imports.insert(valid_item.name().id, resolution_result); |
| 223 | |
| 224 | if name_was_added { |
| 225 | any_names_were_added = true; |
| 226 | } |
| 227 | } |
| 228 | } |
| 229 | } |
| 230 | any_names_were_added |
| 231 | } |
| 232 | |
| 233 | /// Returns the resolution result, and whether the import was successfully |
| 234 | /// resolved *and* bound. |
| 235 | fn try_resolve_import_or_export( |
| 236 | resolver: &mut Resolver, |
| 237 | current_namespace: Option<NamespaceId>, |
| 238 | valid_item: &ValidImportOrExportItem<'_>, |
| 239 | ) -> (Result<(), Error>, bool) { |
| 240 | match resolver.resolve_path(NameKind::Importable, valid_item.path) { |
| 241 | Ok(Res::Importable(ref imported_item_kind)) => { |
| 242 | // Successfully resolved. Proceed with binding the import/export name |
| 243 | // to the original item. |
| 244 | let bind_result = if valid_item.is_export { |
| 245 | // If this an export, we bind the name in the global scope. |
| 246 | bind_export( |
| 247 | resolver, |
| 248 | valid_item.name(), |
| 249 | imported_item_kind, |
| 250 | current_namespace.expect("current namespace should be set for exports"), |
| 251 | ) |
| 252 | } else { |
| 253 | // If this is an import, we bind in the current scope (block or namespace) |
| 254 | bind_import(resolver, valid_item, imported_item_kind, current_namespace) |
| 255 | }; |
| 256 | |
| 257 | let new_import_was_added = bind_result.is_ok(); |
| 258 | |
| 259 | if let Err(err) = bind_result { |
| 260 | // Report name binding errors straight away, since |
| 261 | // unlike resolution errors, these are not retried. |
| 262 | resolver.errors.push(err); |
| 263 | } |
| 264 | |
| 265 | (Ok(()), new_import_was_added) |
| 266 | } |
| 267 | Err(err) => (Err(err), false), |
| 268 | Ok(res) => { |
| 269 | unreachable!("unexpected resolution kind for importable: {res:?}",); |
| 270 | } |
| 271 | } |
| 272 | } |
| 273 | |
| 274 | /// Binds a successfully resolved export's name in the global scope. |
| 275 | fn bind_export( |
| 276 | resolver: &mut Resolver, |
| 277 | name: &Ident, |
| 278 | imported_item: &Importable, |
| 279 | namespace: NamespaceId, |
| 280 | ) -> Result<(), Error> { |
| 281 | let global_scope = &mut resolver.globals; |
| 282 | |
| 283 | // Add the name as an importable in the global scope |
| 284 | match global_scope |
| 285 | .importables |
| 286 | .get_mut_or_default(namespace) |
| 287 | .entry(Rc::clone(&name.name)) |
| 288 | { |
| 289 | Entry::Vacant(entry) => { |
| 290 | entry.insert(Res::Importable(*imported_item)); |
| 291 | } |
| 292 | Entry::Occupied(existing) => { |
| 293 | if let Importable::Callable(imported_item_id, _) | Importable::Ty(imported_item_id, _) = |
| 294 | imported_item |
| 295 | && existing.get().item_id() == Some(*imported_item_id) |
| 296 | { |
| 297 | // This is just a self-export, e.g. |
| 298 | // |
| 299 | // struct Foo {} |
| 300 | // export Foo; |
| 301 | // |
| 302 | // This is not considered a duplicate name. |
| 303 | // We won't bind the name here since it's already |
| 304 | // bound to the original item. But we do |
| 305 | // still need to check for duplicate self-exports. |
| 306 | if let Some(existing_span) = global_scope |
| 307 | .self_exported_item_ids |
| 308 | .insert(*imported_item_id, name.span) |
| 309 | { |
| 310 | return Err(Error::DuplicateExport { |
| 311 | name: name.name.to_string(), |
| 312 | span: name.span, |
| 313 | existing_span, |
| 314 | }); |
| 315 | } |
| 316 | return Ok(()); |
| 317 | } |
| 318 | |
| 319 | return Err(Error::Duplicate( |
| 320 | name.name.to_string(), |
| 321 | global_scope.format_namespace_name(namespace), |
| 322 | name.span, |
| 323 | )); |
| 324 | } |
| 325 | } |
| 326 | |
| 327 | // Also make the name available in the proper lookup tables |
| 328 | // so it can be used during name resolution in expressions, etc. |
| 329 | match *imported_item { |
| 330 | Importable::Callable(imported_item_id, status) => { |
| 331 | global_scope |
| 332 | .terms |
| 333 | .get_mut_or_default(namespace) |
| 334 | .insert(Rc::clone(&name.name), Res::Item(imported_item_id, status)); |
| 335 | } |
| 336 | Importable::Ty(imported_item_id, status) => { |
| 337 | let res = Res::Item(imported_item_id, status); |
| 338 | global_scope |
| 339 | .terms |
| 340 | .get_mut_or_default(namespace) |
| 341 | .insert(Rc::clone(&name.name), res.clone()); |
| 342 | global_scope |
| 343 | .tys |
| 344 | .get_mut_or_default(namespace) |
| 345 | .insert(Rc::clone(&name.name), res); |
| 346 | } |
| 347 | Importable::Namespace(original_namespace_id, _) => { |
| 348 | global_scope.insert_alias_for_namespace(original_namespace_id, &name.name, namespace); |
| 349 | } |
| 350 | } |
| 351 | Ok(()) |
| 352 | } |
| 353 | |
| 354 | fn bind_import( |
| 355 | resolver: &mut Resolver, |
| 356 | valid_item: &ValidImportOrExportItem<'_>, |
| 357 | imported_item: &Importable, |
| 358 | current_namespace: Option<NamespaceId>, |
| 359 | ) -> Result<(), Error> { |
| 360 | let name = valid_item.name(); |
| 361 | |
| 362 | if let Some(current_namespace) = current_namespace { |
| 363 | // Even though imports aren't bound as globals |
| 364 | // (they're only bound in the current scope), |
| 365 | // if we're in a namespace, still check for collisions |
| 366 | // with the global scope. e.g. |
| 367 | // |
| 368 | // namespace A { |
| 369 | // operation Foo() : Unit {} |
| 370 | // import Bar as Foo; // not allowed to shadow `Foo` |
| 371 | // } |
| 372 | if resolver |
| 373 | .globals |
| 374 | .importables |
| 375 | .get_mut_or_default(current_namespace) |
| 376 | .contains_key(&name.name) |
| 377 | { |
| 378 | return Err(Error::Duplicate( |
| 379 | name.name.to_string(), |
| 380 | resolver.globals.format_namespace_name(current_namespace), |
| 381 | name.span, |
| 382 | )); |
| 383 | } |
| 384 | } |
| 385 | |
| 386 | let scope = resolver.current_scope_mut(); |
| 387 | match ( |
| 388 | scope.importables.entry(name.name.clone()), |
| 389 | current_namespace, |
| 390 | ) { |
| 391 | (Entry::Vacant(entry), _) => { |
| 392 | entry.insert(Res::Importable(*imported_item)); |
| 393 | } |
| 394 | (Entry::Occupied(mut entry), None) => { |
| 395 | // allow shadowing in non-namespace (block) scopes |
| 396 | entry.insert(Res::Importable(*imported_item)); |
| 397 | } |
| 398 | (Entry::Occupied(_), Some(namespace_id)) => { |
| 399 | // collision within the namespace scope |
| 400 | return Err(Error::Duplicate( |
| 401 | name.name.to_string(), |
| 402 | resolver.globals.format_namespace_name(namespace_id), |
| 403 | name.span, |
| 404 | )); |
| 405 | } |
| 406 | } |
| 407 | |
| 408 | match *imported_item { |
| 409 | Importable::Callable(imported_item_id, status) => { |
| 410 | scope |
| 411 | .terms |
| 412 | .insert(name.name.clone(), Res::Item(imported_item_id, status)); |
| 413 | } |
| 414 | Importable::Ty(imported_item_id, status) => { |
| 415 | scope |
| 416 | .terms |
| 417 | .insert(name.name.clone(), Res::Item(imported_item_id, status)); |
| 418 | scope |
| 419 | .tys |
| 420 | .insert(name.name.clone(), Res::Item(imported_item_id, status)); |
| 421 | } |
| 422 | Importable::Namespace(namespace_id, _) => { |
| 423 | // A direct import of a namespace is the same as an open with an alias |
| 424 | resolver.bind_open( |
| 425 | valid_item.path, |
| 426 | namespace_id, |
| 427 | Some(valid_item.name().name.clone()), |
| 428 | ); |
| 429 | } |
| 430 | } |
| 431 | Ok(()) |
| 432 | } |
| 433 | |
| 434 | /// Iterative resolution wrapper that handles the common pattern of |
| 435 | /// running resolution attempts in a loop until convergence or maximum iterations. |
| 436 | /// |
| 437 | /// The iterative approach allows imports and exports to refer to each other |
| 438 | /// regardless of the order that they are declared in the source code. |
| 439 | /// |
| 440 | /// Consider this example: |
| 441 | /// ```qsharp |
| 442 | /// namespace A { |
| 443 | /// function B() : Unit {} |
| 444 | /// } |
| 445 | /// |
| 446 | /// namespace D { |
| 447 | /// export C.B; // Depends on C.B being available |
| 448 | /// } |
| 449 | /// |
| 450 | /// namespace C { |
| 451 | /// export A.B; // Makes A.B available as C.B |
| 452 | /// } |
| 453 | /// ``` |
| 454 | /// |
| 455 | /// Here, `D.B` depends on `C.B`, which depends on `A.B`. |
| 456 | /// The iterative approach resolves these dependencies in multiple passes. |
| 457 | #[must_use] |
| 458 | fn iterate_until_done<F>(mut resolver_fn: F) -> Vec<Error> |
| 459 | where |
| 460 | F: FnMut(&mut FxHashMap<NodeId, Result<(), Error>>) -> bool, |
| 461 | { |
| 462 | let mut errors = Vec::new(); |
| 463 | let mut attempted_items = FxHashMap::default(); |
| 464 | for i in 1..=MAX_ITERATIONS { |
| 465 | if !resolver_fn(&mut attempted_items) { |
| 466 | // If no new imports were made available in this pass, we can stop. |
| 467 | break; |
| 468 | } |
| 469 | |
| 470 | if i >= MAX_ITERATIONS { |
| 471 | errors.push(Error::ImportResolutionLimitExceeded(i)); |
| 472 | return errors; |
| 473 | } |
| 474 | } |
| 475 | |
| 476 | for (_, result) in attempted_items.drain() { |
| 477 | if let Err(err) = result { |
| 478 | errors.push(err); |
| 479 | } |
| 480 | } |
| 481 | |
| 482 | errors |
| 483 | } |
| 484 | |
| 485 | /// Iterates over the items in an import or export declaration, yielding only those |
| 486 | /// that were parsed successfully. |
| 487 | pub fn iter_valid_items( |
| 488 | decl: &ImportOrExportDecl, |
| 489 | ) -> impl Iterator<Item = ValidImportOrExportItem<'_>> + '_ { |
| 490 | decl.items.iter().filter_map(move |item| { |
| 491 | if let PathKind::Ok(path) = &item.path { |
| 492 | Some(ValidImportOrExportItem { |
| 493 | span: item.span, |
| 494 | path, |
| 495 | kind: &item.kind, |
| 496 | is_export: decl.is_export(), |
| 497 | }) |
| 498 | } else { |
| 499 | None |
| 500 | } |
| 501 | }) |
| 502 | } |
| 503 | |
| 504 | #[derive(Clone, Debug, Eq, PartialEq)] |
| 505 | pub struct ValidImportOrExportItem<'a> { |
| 506 | pub span: Span, |
| 507 | pub path: &'a Path, |
| 508 | pub kind: &'a ImportKind, |
| 509 | pub is_export: bool, |
| 510 | } |
| 511 | |
| 512 | impl ValidImportOrExportItem<'_> { |
| 513 | pub fn name(&self) -> &Ident { |
| 514 | let alias = match &self.kind { |
| 515 | ImportKind::Wildcard => None, |
| 516 | ImportKind::Direct { alias, .. } => alias.as_ref(), |
| 517 | }; |
| 518 | |
| 519 | match alias { |
| 520 | Some(alias) => alias, |
| 521 | None => &self.path.name, |
| 522 | } |
| 523 | } |
| 524 | } |
| 525 | |