Merge #7145

7145: Proper handling $crate Take 2 [DO NOT MERGE] r=edwin0cheng a=edwin0cheng

Similar to previous PR (#7133) , but improved the following things :

1. Instead of storing the whole `ExpansionInfo`, we store a similar but stripped version `HygieneInfo`.
2. Instread of storing the `SyntaxNode` (because every token we are interested are IDENT), we store the `TextRange` only.
3. Because of 2, we now can put it in Salsa.
4. And most important improvement: Instead of computing the whole frames every single time, we compute it recursively through salsa: (Such that in the best scenario, we only need to compute the first layer of frame)

```rust
        let def_site = db.hygiene_frame(info.def.file_id);
        let call_site = db.hygiene_frame(info.arg.file_id);

        HygieneFrame { expansion: Some(info), local_inner, krate, call_site, def_site }
```

The overall speed compared to previous PR is much faster (65s vs 45s) :
```
[WITH old PR]
Database loaded 644.86ms, 284mi
Crates in this dir: 36
Total modules found: 576
Total declarations: 11153
Total functions: 8715
Item Collection: 15.78s, 91562mi
Total expressions: 240721
Expressions of unknown type: 2635 (1%)
Expressions of partially unknown type: 2064 (0%)
Type mismatches: 865
Inference: 49.84s, 250747mi
Total: 65.62s, 342310mi
rust-analyzer -q analysis-stats .  66.72s user 0.57s system 99% cpu 1:07.40 total

[WITH this PR]
Database loaded 665.83ms, 284mi
Crates in this dir: 36
Total modules found: 577
Total declarations: 11188
Total functions: 8743
Item Collection: 15.28s, 84919mi
Total expressions: 241229
Expressions of unknown type: 2637 (1%)
Expressions of partially unknown type: 2064 (0%)
Type mismatches: 868
Inference: 30.15s, 135293mi
Total: 45.43s, 220213mi   
rust-analyzer -q analysis-stats .  46.26s user 0.74s system 99% cpu 47.294 total
```

*HOWEVER*,  it is still a perf regression (35s vs 45s):
```
[WITHOUT this PR]
Database loaded 657.42ms, 284mi
Crates in this dir: 36
Total modules found: 577
Total declarations: 11177
Total functions: 8735
Item Collection: 12.87s, 72407mi
Total expressions: 239380
Expressions of unknown type: 2643 (1%)
Expressions of partially unknown type: 2064 (0%)
Type mismatches: 868
Inference: 22.88s, 97889mi
Total: 35.74s, 170297mi
rust-analyzer -q analysis-stats .  36.71s user 0.63s system 99% cpu 37.498 total
```



Co-authored-by: Edwin Cheng <[email protected]>

9 files changed, 235 insertions, 58 deletions

diff --git a/crates/hir/src/db.rs b/crates/hir/src/db.rs
index d01e1b33d..d5d4cf5b6 100644
--- a/crates/hir/src/db.rs
+++ b/crates/hir/src/db.rs
@@ -10,8 +10,8 @@ pub use hir_def::db::{
     TypeAliasDataQuery, UnionDataQuery,
 };
 pub use hir_expand::db::{
-    AstDatabase, AstDatabaseStorage, AstIdMapQuery, InternEagerExpansionQuery, InternMacroQuery,
-    MacroArgTextQuery, MacroDefQuery, MacroExpandQuery, ParseMacroExpansionQuery,
+    AstDatabase, AstDatabaseStorage, AstIdMapQuery, HygieneFrameQuery, InternEagerExpansionQuery,
+    InternMacroQuery, MacroArgTextQuery, MacroDefQuery, MacroExpandQuery, ParseMacroExpansionQuery,
 };
 pub use hir_ty::db::*;
 
diff --git a/crates/hir_def/src/path/lower.rs b/crates/hir_def/src/path/lower.rs
index 8a01e6eea..9518ac109 100644
--- a/crates/hir_def/src/path/lower.rs
+++ b/crates/hir_def/src/path/lower.rs
@@ -123,7 +123,7 @@ pub(super) fn lower_path(mut path: ast::Path, hygiene: &Hygiene) -> Option<Path>
     // We follow what it did anyway :)
     if segments.len() == 1 && kind == PathKind::Plain {
         if let Some(_macro_call) = path.syntax().parent().and_then(ast::MacroCall::cast) {
-            if let Some(crate_id) = hygiene.local_inner_macros() {
+            if let Some(crate_id) = hygiene.local_inner_macros(path) {
                 kind = PathKind::DollarCrate(crate_id);
             }
         }
diff --git a/crates/hir_expand/src/db.rs b/crates/hir_expand/src/db.rs
index 0a0d021e0..ab2637b8c 100644
--- a/crates/hir_expand/src/db.rs
+++ b/crates/hir_expand/src/db.rs
@@ -8,9 +8,9 @@ use parser::FragmentKind;
 use syntax::{algo::diff, ast::NameOwner, AstNode, GreenNode, Parse, SyntaxKind::*, SyntaxNode};
 
 use crate::{
-    ast_id_map::AstIdMap, BuiltinDeriveExpander, BuiltinFnLikeExpander, EagerCallLoc, EagerMacroId,
-    HirFileId, HirFileIdRepr, LazyMacroId, MacroCallId, MacroCallLoc, MacroDefId, MacroDefKind,
-    MacroFile, ProcMacroExpander,
+    ast_id_map::AstIdMap, hygiene::HygieneFrame, BuiltinDeriveExpander, BuiltinFnLikeExpander,
+    EagerCallLoc, EagerMacroId, HirFileId, HirFileIdRepr, LazyMacroId, MacroCallId, MacroCallLoc,
+    MacroDefId, MacroDefKind, MacroFile, ProcMacroExpander,
 };
 
 /// Total limit on the number of tokens produced by any macro invocation.
@@ -94,6 +94,8 @@ pub trait AstDatabase: SourceDatabase {
     fn intern_eager_expansion(&self, eager: EagerCallLoc) -> EagerMacroId;
 
     fn expand_proc_macro(&self, call: MacroCallId) -> Result<tt::Subtree, mbe::ExpandError>;
+
+    fn hygiene_frame(&self, file_id: HirFileId) -> Arc<HygieneFrame>;
 }
 
 /// This expands the given macro call, but with different arguments. This is
@@ -369,6 +371,10 @@ fn parse_macro_with_arg(
     }
 }
 
+fn hygiene_frame(db: &dyn AstDatabase, file_id: HirFileId) -> Arc<HygieneFrame> {
+    Arc::new(HygieneFrame::new(db, file_id))
+}
+
 /// Given a `MacroCallId`, return what `FragmentKind` it belongs to.
 /// FIXME: Not completed
 fn to_fragment_kind(db: &dyn AstDatabase, id: MacroCallId) -> FragmentKind {
diff --git a/crates/hir_expand/src/hygiene.rs b/crates/hir_expand/src/hygiene.rs
index 7ab0a5e52..8db581b77 100644
--- a/crates/hir_expand/src/hygiene.rs
+++ b/crates/hir_expand/src/hygiene.rs
@@ -2,65 +2,209 @@
 //!
 //! Specifically, `ast` + `Hygiene` allows you to create a `Name`. Note that, at
 //! this moment, this is horribly incomplete and handles only `$crate`.
+use std::sync::Arc;
+
 use base_db::CrateId;
 use either::Either;
-use syntax::ast;
+use mbe::Origin;
+use parser::SyntaxKind;
+use syntax::{ast, AstNode, SyntaxNode, TextRange, TextSize};
 
 use crate::{
-    db::AstDatabase,
+    db::{self, AstDatabase},
     name::{AsName, Name},
-    HirFileId, HirFileIdRepr, MacroCallId, MacroDefKind,
+    HirFileId, HirFileIdRepr, InFile, MacroCallId, MacroCallLoc, MacroDefKind, MacroFile,
 };
 
 #[derive(Clone, Debug)]
 pub struct Hygiene {
-    // This is what `$crate` expands to
-    def_crate: Option<CrateId>,
-
-    // Indicate this is a local inner macro
-    local_inner: bool,
+    frames: Option<HygieneFrames>,
 }
 
 impl Hygiene {
     pub fn new(db: &dyn AstDatabase, file_id: HirFileId) -> Hygiene {
-        let (def_crate, local_inner) = match file_id.0 {
-            HirFileIdRepr::FileId(_) => (None, false),
-            HirFileIdRepr::MacroFile(macro_file) => match macro_file.macro_call_id {
-                MacroCallId::LazyMacro(id) => {
-                    let loc = db.lookup_intern_macro(id);
-                    match loc.def.kind {
-                        MacroDefKind::Declarative => (Some(loc.def.krate), loc.def.local_inner),
-                        MacroDefKind::BuiltIn(_) => (Some(loc.def.krate), false),
-                        MacroDefKind::BuiltInDerive(_) => (None, false),
-                        MacroDefKind::BuiltInEager(_) => (None, false),
-                        MacroDefKind::ProcMacro(_) => (None, false),
-                    }
-                }
-                MacroCallId::EagerMacro(_id) => (None, false),
-            },
-        };
-        Hygiene { def_crate, local_inner }
+        Hygiene { frames: Some(HygieneFrames::new(db, file_id.clone())) }
     }
 
     pub fn new_unhygienic() -> Hygiene {
-        Hygiene { def_crate: None, local_inner: false }
+        Hygiene { frames: None }
     }
 
     // FIXME: this should just return name
     pub fn name_ref_to_name(&self, name_ref: ast::NameRef) -> Either<Name, CrateId> {
-        if let Some(def_crate) = self.def_crate {
+        if let Some(frames) = &self.frames {
             if name_ref.text() == "$crate" {
-                return Either::Right(def_crate);
+                if let Some(krate) = frames.root_crate(name_ref.syntax()) {
+                    return Either::Right(krate);
+                }
             }
         }
+
         Either::Left(name_ref.as_name())
     }
 
-    pub fn local_inner_macros(&self) -> Option<CrateId> {
-        if self.local_inner {
-            self.def_crate
-        } else {
-            None
+    pub fn local_inner_macros(&self, path: ast::Path) -> Option<CrateId> {
+        let mut token = path.syntax().first_token()?.text_range();
+        let frames = self.frames.as_ref()?;
+        let mut current = frames.0.clone();
+
+        loop {
+            let (mapped, origin) = current.expansion.as_ref()?.map_ident_up(token)?;
+            if origin == Origin::Def {
+                return if current.local_inner { frames.root_crate(path.syntax()) } else { None };
+            }
+            current = current.call_site.as_ref()?.clone();
+            token = mapped.value;
+        }
+    }
+}
+
+#[derive(Clone, Debug)]
+struct HygieneFrames(Arc<HygieneFrame>);
+
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct HygieneFrame {
+    expansion: Option<HygieneInfo>,
+
+    // Indicate this is a local inner macro
+    local_inner: bool,
+    krate: Option<CrateId>,
+
+    call_site: Option<Arc<HygieneFrame>>,
+    def_site: Option<Arc<HygieneFrame>>,
+}
+
+impl HygieneFrames {
+    fn new(db: &dyn AstDatabase, file_id: HirFileId) -> Self {
+        HygieneFrames(Arc::new(HygieneFrame::new(db, file_id)))
+    }
+
+    fn root_crate(&self, node: &SyntaxNode) -> Option<CrateId> {
+        let mut token = node.first_token()?.text_range();
+        let mut result = self.0.krate;
+        let mut current = self.0.clone();
+
+        while let Some((mapped, origin)) =
+            current.expansion.as_ref().and_then(|it| it.map_ident_up(token))
+        {
+            result = current.krate;
+
+            let site = match origin {
+                Origin::Def => &current.def_site,
+                Origin::Call => &current.call_site,
+            };
+
+            let site = match site {
+                None => break,
+                Some(it) => it,
+            };
+
+            current = site.clone();
+            token = mapped.value;
         }
+
+        result
+    }
+}
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+struct HygieneInfo {
+    arg_start: InFile<TextSize>,
+    /// The `macro_rules!` arguments.
+    def_start: Option<InFile<TextSize>>,
+
+    macro_def: Arc<(db::TokenExpander, mbe::TokenMap)>,
+    macro_arg: Arc<(tt::Subtree, mbe::TokenMap)>,
+    exp_map: Arc<mbe::TokenMap>,
+}
+
+impl HygieneInfo {
+    fn map_ident_up(&self, token: TextRange) -> Option<(InFile<TextRange>, Origin)> {
+        let token_id = self.exp_map.token_by_range(token)?;
+
+        let (token_id, origin) = self.macro_def.0.map_id_up(token_id);
+        let (token_map, tt) = match origin {
+            mbe::Origin::Call => (&self.macro_arg.1, self.arg_start),
+            mbe::Origin::Def => (
+                &self.macro_def.1,
+                self.def_start
+                    .as_ref()
+                    .expect("`Origin::Def` used with non-`macro_rules!` macro")
+                    .clone(),
+            ),
+        };
+
+        let range = token_map.range_by_token(token_id)?.by_kind(SyntaxKind::IDENT)?;
+        Some((tt.with_value(range + tt.value), origin))
+    }
+}
+
+fn make_hygiene_info(
+    db: &dyn AstDatabase,
+    macro_file: MacroFile,
+    loc: &MacroCallLoc,
+) -> Option<HygieneInfo> {
+    let arg_tt = loc.kind.arg(db)?;
+
+    let def_offset = loc.def.ast_id.and_then(|id| {
+        let def_tt = match id.to_node(db) {
+            ast::Macro::MacroRules(mac) => mac.token_tree()?.syntax().text_range().start(),
+            ast::Macro::MacroDef(_) => return None,
+        };
+        Some(InFile::new(id.file_id, def_tt))
+    });
+
+    let macro_def = db.macro_def(loc.def)?;
+    let (_, exp_map) = db.parse_macro_expansion(macro_file).value?;
+    let macro_arg = db.macro_arg(macro_file.macro_call_id)?;
+
+    Some(HygieneInfo {
+        arg_start: InFile::new(loc.kind.file_id(), arg_tt.text_range().start()),
+        def_start: def_offset,
+        macro_arg,
+        macro_def,
+        exp_map,
+    })
+}
+
+impl HygieneFrame {
+    pub(crate) fn new(db: &dyn AstDatabase, file_id: HirFileId) -> HygieneFrame {
+        let (info, krate, local_inner) = match file_id.0 {
+            HirFileIdRepr::FileId(_) => (None, None, false),
+            HirFileIdRepr::MacroFile(macro_file) => match macro_file.macro_call_id {
+                MacroCallId::EagerMacro(_id) => (None, None, false),
+                MacroCallId::LazyMacro(id) => {
+                    let loc = db.lookup_intern_macro(id);
+                    let info = make_hygiene_info(db, macro_file, &loc);
+                    match loc.def.kind {
+                        MacroDefKind::Declarative => {
+                            (info, Some(loc.def.krate), loc.def.local_inner)
+                        }
+                        MacroDefKind::BuiltIn(_) => (info, Some(loc.def.krate), false),
+                        MacroDefKind::BuiltInDerive(_) => (info, None, false),
+                        MacroDefKind::BuiltInEager(_) => (info, None, false),
+                        MacroDefKind::ProcMacro(_) => (info, None, false),
+                    }
+                }
+            },
+        };
+
+        let info = match info {
+            None => {
+                return HygieneFrame {
+                    expansion: None,
+                    local_inner,
+                    krate,
+                    call_site: None,
+                    def_site: None,
+                };
+            }
+            Some(it) => it,
+        };
+
+        let def_site = info.def_start.map(|it| db.hygiene_frame(it.file_id));
+        let call_site = Some(db.hygiene_frame(info.arg_start.file_id));
+
+        HygieneFrame { expansion: Some(info), local_inner, krate, call_site, def_site }
     }
 }
diff --git a/crates/hir_ty/src/tests/macros.rs b/crates/hir_ty/src/tests/macros.rs
index 1953da7be..c64f0b5b5 100644
--- a/crates/hir_ty/src/tests/macros.rs
+++ b/crates/hir_ty/src/tests/macros.rs
@@ -371,6 +371,37 @@ expand!();
 }
 
 #[test]
+fn infer_macro_with_dollar_crate_in_def_site() {
+    check_types(
+        r#"
+//- /main.rs crate:main deps:foo
+use foo::expand;
+
+macro_rules! list {
+    ($($tt:tt)*) => { $($tt)* }
+}
+
+fn test() {
+    let r = expand!();
+    r;
+  //^ u128
+}
+
+//- /lib.rs crate:foo
+#[macro_export]
+macro_rules! expand {
+    () => { list!($crate::m!()) };
+}
+
+#[macro_export]
+macro_rules! m {
+    () => { 0u128 };
+}
+"#,
+    );
+}
+
+#[test]
 fn infer_type_value_non_legacy_macro_use_as() {
     check_infer(
         r#"
diff --git a/crates/ide_db/src/apply_change.rs b/crates/ide_db/src/apply_change.rs
index 71c19ed13..c770a236b 100644
--- a/crates/ide_db/src/apply_change.rs
+++ b/crates/ide_db/src/apply_change.rs
@@ -145,6 +145,7 @@ impl RootDatabase {
             hir::db::MacroDefQuery
             hir::db::ParseMacroExpansionQuery
             hir::db::MacroExpandQuery
+            hir::db::HygieneFrameQuery
 
             // DefDatabase
             hir::db::ItemTreeQuery
diff --git a/crates/mbe/src/mbe_expander/matcher.rs b/crates/mbe/src/mbe_expander/matcher.rs
index fdc8844ce..c6d615c81 100644
--- a/crates/mbe/src/mbe_expander/matcher.rs
+++ b/crates/mbe/src/mbe_expander/matcher.rs
@@ -150,7 +150,7 @@ fn match_subtree(
                     res.add_err(err!("leftover tokens"));
                 }
             }
-            Op::Var { name, kind } => {
+            Op::Var { name, kind, .. } => {
                 let kind = match kind {
                     Some(k) => k,
                     None => {
diff --git a/crates/mbe/src/mbe_expander/transcriber.rs b/crates/mbe/src/mbe_expander/transcriber.rs
index 720531237..57f3f104d 100644
--- a/crates/mbe/src/mbe_expander/transcriber.rs
+++ b/crates/mbe/src/mbe_expander/transcriber.rs
@@ -100,8 +100,8 @@ fn expand_subtree(
                 err = err.or(e);
                 arena.push(tt.into());
             }
-            Op::Var { name, .. } => {
-                let ExpandResult { value: fragment, err: e } = expand_var(ctx, &name);
+            Op::Var { name, id, .. } => {
+                let ExpandResult { value: fragment, err: e } = expand_var(ctx, &name, *id);
                 err = err.or(e);
                 push_fragment(arena, fragment);
             }
@@ -118,12 +118,10 @@ fn expand_subtree(
     ExpandResult { value: tt::Subtree { delimiter: template.delimiter, token_trees: tts }, err }
 }
 
-fn expand_var(ctx: &mut ExpandCtx, v: &SmolStr) -> ExpandResult<Fragment> {
+fn expand_var(ctx: &mut ExpandCtx, v: &SmolStr, id: tt::TokenId) -> ExpandResult<Fragment> {
     if v == "crate" {
         // We simply produce identifier `$crate` here. And it will be resolved when lowering ast to Path.
-        let tt =
-            tt::Leaf::from(tt::Ident { text: "$crate".into(), id: tt::TokenId::unspecified() })
-                .into();
+        let tt = tt::Leaf::from(tt::Ident { text: "$crate".into(), id }).into();
         ExpandResult::ok(Fragment::Tokens(tt))
     } else if !ctx.bindings.contains(v) {
         // Note that it is possible to have a `$var` inside a macro which is not bound.
@@ -142,14 +140,8 @@ fn expand_var(ctx: &mut ExpandCtx, v: &SmolStr) -> ExpandResult<Fragment> {
         let tt = tt::Subtree {
             delimiter: None,
             token_trees: vec![
-                tt::Leaf::from(tt::Punct {
-                    char: '$',
-                    spacing: tt::Spacing::Alone,
-                    id: tt::TokenId::unspecified(),
-                })
-                .into(),
-                tt::Leaf::from(tt::Ident { text: v.clone(), id: tt::TokenId::unspecified() })
-                    .into(),
+                tt::Leaf::from(tt::Punct { char: '$', spacing: tt::Spacing::Alone, id }).into(),
+                tt::Leaf::from(tt::Ident { text: v.clone(), id }).into(),
             ],
         }
         .into();
diff --git a/crates/mbe/src/parser.rs b/crates/mbe/src/parser.rs
index 2f3ebc831..77cc739b6 100644
--- a/crates/mbe/src/parser.rs
+++ b/crates/mbe/src/parser.rs
@@ -8,7 +8,7 @@ use crate::{tt_iter::TtIter, ExpandError, MetaTemplate};
 
 #[derive(Clone, Debug, PartialEq, Eq)]
 pub(crate) enum Op {
-    Var { name: SmolStr, kind: Option<SmolStr> },
+    Var { name: SmolStr, kind: Option<SmolStr>, id: tt::TokenId },
     Repeat { subtree: MetaTemplate, kind: RepeatKind, separator: Option<Separator> },
     Leaf(tt::Leaf),
     Subtree(MetaTemplate),
@@ -106,18 +106,21 @@ fn next_op<'a>(first: &tt::TokenTree, src: &mut TtIter<'a>, mode: Mode) -> Resul
                         }
                         let name = UNDERSCORE.clone();
                         let kind = eat_fragment_kind(src, mode)?;
-                        Op::Var { name, kind }
+                        let id = punct.id;
+                        Op::Var { name, kind, id }
                     }
                     tt::Leaf::Ident(ident) => {
                         let name = ident.text.clone();
                         let kind = eat_fragment_kind(src, mode)?;
-                        Op::Var { name, kind }
+                        let id = ident.id;
+                        Op::Var { name, kind, id }
                     }
                     tt::Leaf::Literal(lit) => {
                         if is_boolean_literal(&lit) {
                             let name = lit.text.clone();
                             let kind = eat_fragment_kind(src, mode)?;
-                            Op::Var { name, kind }
+                            let id = lit.id;
+                            Op::Var { name, kind, id }
                         } else {
                             bail!("bad var 2");
                         }