1 files changed, 151 insertions, 13 deletions

diff --git a/crates/hir_def/src/item_tree.rs b/crates/hir_def/src/item_tree.rs
index 528270d49..227337a8d 100644
--- a/crates/hir_def/src/item_tree.rs
+++ b/crates/hir_def/src/item_tree.rs
@@ -1,4 +1,34 @@
 //! A simplified AST that only contains items.
+//!
+//! This is the primary IR used throughout `hir_def`. It is the input to the name resolution
+//! algorithm, as well as to the queries defined in `adt.rs`, `data.rs`, and most things in
+//! `attr.rs`.
+//!
+//! `ItemTree`s are built per `HirFileId`, from the syntax tree of the parsed file. This means that
+//! they are crate-independent: they don't know which `#[cfg]`s are active or which module they
+//! belong to, since those concepts don't exist at this level (a single `ItemTree` might be part of
+//! multiple crates, or might be included into the same crate twice via `#[path]`).
+//!
+//! One important purpose of this layer is to provide an "invalidation barrier" for incremental
+//! computations: when typing inside an item body, the `ItemTree` of the modified file is typically
+//! unaffected, so we don't have to recompute name resolution results or item data (see `data.rs`).
+//!
+//! The `ItemTree` for the currently open file can be displayed by using the VS Code command
+//! "Rust Analyzer: Debug ItemTree".
+//!
+//! Compared to rustc's architecture, `ItemTree` has properties from both rustc's AST and HIR: many
+//! syntax-level Rust features are already desugared to simpler forms in the `ItemTree`, but name
+//! resolution has not yet been performed. `ItemTree`s are per-file, while rustc's AST and HIR are
+//! per-crate, because we are interested in incrementally computing it.
+//!
+//! The representation of items in the `ItemTree` should generally mirror the surface syntax: it is
+//! usually a bad idea to desugar a syntax-level construct to something that is structurally
+//! different here. Name resolution needs to be able to process attributes and expand macros
+//! (including attribute macros), and having a 1-to-1 mapping between syntax and the `ItemTree`
+//! avoids introducing subtle bugs.
+//!
+//! In general, any item in the `ItemTree` stores its `AstId`, which allows mapping it back to its
+//! surface syntax.
 
 mod lower;
 mod pretty;
@@ -493,21 +523,38 @@ impl<N: ItemTreeNode> Index<FileItemTreeId<N>> for ItemTree {
     }
 }
 
-/// A desugared `use` import.
 #[derive(Debug, Clone, Eq, PartialEq)]
 pub struct Import {
-    pub path: Interned<ModPath>,
-    pub alias: Option<ImportAlias>,
     pub visibility: RawVisibilityId,
-    pub is_glob: bool,
-    /// AST ID of the `use` or `extern crate` item this import was derived from. Note that many
-    /// `Import`s can map to the same `use` item.
     pub ast_id: FileAstId<ast::Use>,
-    /// Index of this `Import` when the containing `Use` is visited via `ModPath::expand_use_item`.
-    ///
-    /// This can be used to get the `UseTree` this `Import` corresponds to and allows emitting
-    /// precise diagnostics.
-    pub index: usize,
+    pub use_tree: UseTree,
+}
+
+#[derive(Debug, Clone, Eq, PartialEq)]
+pub struct UseTree {
+    pub index: Idx<ast::UseTree>,
+    kind: UseTreeKind,
+}
+
+#[derive(Debug, Clone, Eq, PartialEq)]
+pub enum UseTreeKind {
+    /// ```
+    /// use path::to::Item;
+    /// use path::to::Item as Renamed;
+    /// use path::to::Trait as _;
+    /// ```
+    Single { path: Interned<ModPath>, alias: Option<ImportAlias> },
+
+    /// ```
+    /// use *;  // (invalid, but can occur in nested tree)
+    /// use path::*;
+    /// ```
+    Glob { path: Option<Interned<ModPath>> },
+
+    /// ```
+    /// use prefix::{self, Item, ...};
+    /// ```
+    Prefixed { prefix: Option<Interned<ModPath>>, list: Box<[UseTree]> },
 }
 
 #[derive(Debug, Clone, Eq, PartialEq)]
@@ -533,6 +580,7 @@ pub struct Function {
     pub abi: Option<Interned<str>>,
     pub params: IdRange<Param>,
     pub ret_type: Interned<TypeRef>,
+    pub async_ret_type: Option<Interned<TypeRef>>,
     pub ast_id: FileAstId<ast::Fn>,
     pub(crate) flags: FnFlags,
 }
@@ -614,7 +662,6 @@ pub struct Trait {
     pub generic_params: Interned<GenericParams>,
     pub is_auto: bool,
     pub is_unsafe: bool,
-    pub bounds: Box<[TypeBound]>,
     pub items: Box<[AssocItem]>,
     pub ast_id: FileAstId<ast::Trait>,
 }
@@ -634,7 +681,7 @@ pub struct TypeAlias {
     pub name: Name,
     pub visibility: RawVisibilityId,
     /// Bounds on the type alias itself. Only valid in trait declarations, eg. `type Assoc: Copy;`.
-    pub bounds: Box<[TypeBound]>,
+    pub bounds: Box<[Interned<TypeBound>]>,
     pub generic_params: Interned<GenericParams>,
     pub type_ref: Option<Interned<TypeRef>>,
     pub is_extern: bool,
@@ -681,6 +728,97 @@ pub struct MacroDef {
     pub ast_id: FileAstId<ast::MacroDef>,
 }
 
+impl Import {
+    /// Maps a `UseTree` contained in this import back to its AST node.
+    pub fn use_tree_to_ast(
+        &self,
+        db: &dyn DefDatabase,
+        file_id: HirFileId,
+        index: Idx<ast::UseTree>,
+    ) -> ast::UseTree {
+        // Re-lower the AST item and get the source map.
+        // Note: The AST unwraps are fine, since if they fail we should have never obtained `index`.
+        let ast = InFile::new(file_id, self.ast_id).to_node(db.upcast());
+        let ast_use_tree = ast.use_tree().expect("missing `use_tree`");
+        let hygiene = Hygiene::new(db.upcast(), file_id);
+        let (_, source_map) =
+            lower::lower_use_tree(db, &hygiene, ast_use_tree).expect("failed to lower use tree");
+        source_map[index].clone()
+    }
+}
+
+impl UseTree {
+    /// Expands the `UseTree` into individually imported `ModPath`s.
+    pub fn expand(
+        &self,
+        mut cb: impl FnMut(Idx<ast::UseTree>, ModPath, /* is_glob */ bool, Option<ImportAlias>),
+    ) {
+        self.expand_impl(None, &mut cb)
+    }
+
+    fn expand_impl(
+        &self,
+        prefix: Option<ModPath>,
+        cb: &mut dyn FnMut(
+            Idx<ast::UseTree>,
+            ModPath,
+            /* is_glob */ bool,
+            Option<ImportAlias>,
+        ),
+    ) {
+        fn concat_mod_paths(prefix: Option<ModPath>, path: &ModPath) -> Option<ModPath> {
+            match (prefix, &path.kind) {
+                (None, _) => Some(path.clone()),
+                (Some(mut prefix), PathKind::Plain) => {
+                    for segment in path.segments() {
+                        prefix.push_segment(segment.clone());
+                    }
+                    Some(prefix)
+                }
+                (Some(prefix), PathKind::Super(0)) => {
+                    // `some::path::self` == `some::path`
+                    if path.segments().is_empty() {
+                        Some(prefix)
+                    } else {
+                        None
+                    }
+                }
+                (Some(_), _) => None,
+            }
+        }
+
+        match &self.kind {
+            UseTreeKind::Single { path, alias } => {
+                if let Some(path) = concat_mod_paths(prefix, path) {
+                    cb(self.index, path, false, alias.clone());
+                }
+            }
+            UseTreeKind::Glob { path: Some(path) } => {
+                if let Some(path) = concat_mod_paths(prefix, path) {
+                    cb(self.index, path, true, None);
+                }
+            }
+            UseTreeKind::Glob { path: None } => {
+                if let Some(prefix) = prefix {
+                    cb(self.index, prefix, true, None);
+                }
+            }
+            UseTreeKind::Prefixed { prefix: additional_prefix, list } => {
+                let prefix = match additional_prefix {
+                    Some(path) => match concat_mod_paths(prefix, path) {
+                        Some(path) => Some(path),
+                        None => return,
+                    },
+                    None => prefix,
+                };
+                for tree in &**list {
+                    tree.expand_impl(prefix.clone(), cb);
+                }
+            }
+        }
+    }
+}
+
 macro_rules! impl_froms {
     ($e:ident { $($v:ident ($t:ty)),* $(,)? }) => {
         $(