Auto merge of #101620 - cjgillot:compute_lint_levels_by_def, r=oli-obk

Compute lint levels by definition

Lint levels are currently computed once for the whole crate. Any code that wants to emit a lint depends on this single `lint_levels(())` query. This query contains the `Span` for each attribute that participates in the lint level tree, so any code that wants to emit a lint basically depends on the spans in all files in the crate.

Contrary to hard errors, we do not clear the incremental session on lints, so this implicit world dependency pessimizes incremental reuse. (And is furthermore invisible for allowed lints.)

This PR completes https://github.com/rust-lang/rust/pull/99634 (thanks for the initial work `@fee1-dead)` and includes it in the dependency graph.

The design is based on 2 queries:
1. `lint_levels_on(HirId) -> FxHashMap<LintId, LevelAndSource>` which accesses the attributes at the given `HirId` and processes them into lint levels.  The `TyCtxt` is responsible for probing the HIR tree to find the user-visible level.
2. `lint_expectations(())` which lists all the `#[expect]` attributes in the crate.

This PR also introduces the ability to reconstruct a `HirId` from a `DepNode` by encoding the local part of the `DefPathHash` and the `ItemLocalId` in the two `u64` of the fingerprint.  This allows for the dep-graph to directly recompute `lint_levels_on` directly, without having to force the calling query.

Closes https://github.com/rust-lang/rust/issues/95094.
Supersedes https://github.com/rust-lang/rust/pull/99634.

5 files changed, 142 insertions, 174 deletions

diff --git a/compiler/rustc_middle/src/dep_graph/dep_node.rs b/compiler/rustc_middle/src/dep_graph/dep_node.rs
index 7718906ac4e..aae12705e3d 100644
--- a/compiler/rustc_middle/src/dep_graph/dep_node.rs
+++ b/compiler/rustc_middle/src/dep_graph/dep_node.rs
@@ -62,7 +62,7 @@ use crate::ty::TyCtxt;
 use rustc_data_structures::fingerprint::Fingerprint;
 use rustc_hir::def_id::{CrateNum, DefId, LocalDefId};
 use rustc_hir::definitions::DefPathHash;
-use rustc_hir::HirId;
+use rustc_hir::{HirId, ItemLocalId};
 use rustc_query_system::dep_graph::FingerprintStyle;
 use rustc_span::symbol::Symbol;
 use std::hash::Hash;
@@ -289,7 +289,7 @@ impl DepNodeExt for DepNode {
         let kind = dep_kind_from_label_string(label)?;
 
         match kind.fingerprint_style(tcx) {
-            FingerprintStyle::Opaque => Err(()),
+            FingerprintStyle::Opaque | FingerprintStyle::HirId => Err(()),
             FingerprintStyle::Unit => Ok(DepNode::new_no_params(tcx, kind)),
             FingerprintStyle::DefPathHash => {
                 Ok(DepNode::from_def_path_hash(tcx, def_path_hash, kind))
@@ -417,7 +417,7 @@ impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for (DefId, DefId) {
 impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for HirId {
     #[inline(always)]
     fn fingerprint_style() -> FingerprintStyle {
-        FingerprintStyle::Opaque
+        FingerprintStyle::HirId
     }
 
     // We actually would not need to specialize the implementation of this
@@ -426,10 +426,36 @@ impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for HirId {
     #[inline(always)]
     fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint {
         let HirId { owner, local_id } = *self;
-
         let def_path_hash = tcx.def_path_hash(owner.to_def_id());
-        let local_id = Fingerprint::from_smaller_hash(local_id.as_u32().into());
+        Fingerprint::new(
+            // `owner` is local, so is completely defined by the local hash
+            def_path_hash.local_hash(),
+            local_id.as_u32().into(),
+        )
+    }
 
-        def_path_hash.0.combine(local_id)
+    #[inline(always)]
+    fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String {
+        let HirId { owner, local_id } = *self;
+        format!("{}.{}", tcx.def_path_str(owner.to_def_id()), local_id.as_u32())
+    }
+
+    #[inline(always)]
+    fn recover(tcx: TyCtxt<'tcx>, dep_node: &DepNode) -> Option<Self> {
+        if dep_node.kind.fingerprint_style(tcx) == FingerprintStyle::HirId {
+            let (local_hash, local_id) = Fingerprint::from(dep_node.hash).as_value();
+            let def_path_hash = DefPathHash::new(tcx.sess.local_stable_crate_id(), local_hash);
+            let owner = tcx
+                .def_path_hash_to_def_id(def_path_hash, &mut || {
+                    panic!("Failed to extract HirId: {:?} {}", dep_node.kind, dep_node.hash)
+                })
+                .expect_local();
+            let local_id = local_id
+                .try_into()
+                .unwrap_or_else(|_| panic!("local id should be u32, found {:?}", local_id));
+            Some(HirId { owner, local_id: ItemLocalId::from_u32(local_id) })
+        } else {
+            None
+        }
     }
 }
diff --git a/compiler/rustc_middle/src/lint.rs b/compiler/rustc_middle/src/lint.rs
index 2f45222de47..4cb5ef79177 100644
--- a/compiler/rustc_middle/src/lint.rs
+++ b/compiler/rustc_middle/src/lint.rs
@@ -1,20 +1,19 @@
 use std::cmp;
 
 use rustc_data_structures::fx::FxHashMap;
-use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
 use rustc_errors::{Diagnostic, DiagnosticId, LintDiagnosticBuilder, MultiSpan};
 use rustc_hir::HirId;
-use rustc_index::vec::IndexVec;
-use rustc_query_system::ich::StableHashingContext;
 use rustc_session::lint::{
     builtin::{self, FORBIDDEN_LINT_GROUPS},
-    FutureIncompatibilityReason, Level, Lint, LintExpectationId, LintId,
+    FutureIncompatibilityReason, Level, Lint, LintId,
 };
 use rustc_session::Session;
 use rustc_span::hygiene::MacroKind;
 use rustc_span::source_map::{DesugaringKind, ExpnKind};
 use rustc_span::{symbol, Span, Symbol, DUMMY_SP};
 
+use crate::ty::TyCtxt;
+
 /// How a lint level was set.
 #[derive(Clone, Copy, PartialEq, Eq, HashStable, Debug)]
 pub enum LintLevelSource {
@@ -23,7 +22,12 @@ pub enum LintLevelSource {
     Default,
 
     /// Lint level was set by an attribute.
-    Node(Symbol, Span, Option<Symbol> /* RFC 2383 reason */),
+    Node {
+        name: Symbol,
+        span: Span,
+        /// RFC 2383 reason
+        reason: Option<Symbol>,
+    },
 
     /// Lint level was set by a command-line flag.
     /// The provided `Level` is the level specified on the command line.
@@ -35,7 +39,7 @@ impl LintLevelSource {
     pub fn name(&self) -> Symbol {
         match *self {
             LintLevelSource::Default => symbol::kw::Default,
-            LintLevelSource::Node(name, _, _) => name,
+            LintLevelSource::Node { name, .. } => name,
             LintLevelSource::CommandLine(name, _) => name,
         }
     }
@@ -43,7 +47,7 @@ impl LintLevelSource {
     pub fn span(&self) -> Span {
         match *self {
             LintLevelSource::Default => DUMMY_SP,
-            LintLevelSource::Node(_, span, _) => span,
+            LintLevelSource::Node { span, .. } => span,
             LintLevelSource::CommandLine(_, _) => DUMMY_SP,
         }
     }
@@ -52,145 +56,115 @@ impl LintLevelSource {
 /// A tuple of a lint level and its source.
 pub type LevelAndSource = (Level, LintLevelSource);
 
-#[derive(Debug, HashStable)]
-pub struct LintLevelSets {
-    pub list: IndexVec<LintStackIndex, LintSet>,
-    pub lint_cap: Level,
-}
-
-rustc_index::newtype_index! {
-    #[derive(HashStable)]
-    pub struct LintStackIndex {
-        const COMMAND_LINE = 0,
-    }
-}
-
-#[derive(Debug, HashStable)]
-pub struct LintSet {
-    // -A,-W,-D flags, a `Symbol` for the flag itself and `Level` for which
-    // flag.
+/// Return type for the `shallow_lint_levels_on` query.
+///
+/// This map represents the set of allowed lints and allowance levels given
+/// by the attributes for *a single HirId*.
+#[derive(Default, Debug, HashStable)]
+pub struct ShallowLintLevelMap {
     pub specs: FxHashMap<LintId, LevelAndSource>,
-
-    pub parent: LintStackIndex,
 }
 
-impl LintLevelSets {
-    pub fn new() -> Self {
-        LintLevelSets { list: IndexVec::new(), lint_cap: Level::Forbid }
-    }
-
-    pub fn get_lint_level(
-        &self,
-        lint: &'static Lint,
-        idx: LintStackIndex,
-        aux: Option<&FxHashMap<LintId, LevelAndSource>>,
-        sess: &Session,
-    ) -> LevelAndSource {
-        let (level, mut src) = self.get_lint_id_level(LintId::of(lint), idx, aux);
-
-        // If `level` is none then we actually assume the default level for this
-        // lint.
-        let mut level = level.unwrap_or_else(|| lint.default_level(sess.edition()));
-
-        // If we're about to issue a warning, check at the last minute for any
-        // directives against the warnings "lint". If, for example, there's an
-        // `allow(warnings)` in scope then we want to respect that instead.
-        //
-        // We exempt `FORBIDDEN_LINT_GROUPS` from this because it specifically
-        // triggers in cases (like #80988) where you have `forbid(warnings)`,
-        // and so if we turned that into an error, it'd defeat the purpose of the
-        // future compatibility warning.
-        if level == Level::Warn && LintId::of(lint) != LintId::of(FORBIDDEN_LINT_GROUPS) {
-            let (warnings_level, warnings_src) =
-                self.get_lint_id_level(LintId::of(builtin::WARNINGS), idx, aux);
-            if let Some(configured_warning_level) = warnings_level {
-                if configured_warning_level != Level::Warn {
-                    level = configured_warning_level;
-                    src = warnings_src;
-                }
+/// From an initial level and source, verify the effect of special annotations:
+/// `warnings` lint level and lint caps.
+///
+/// The return of this function is suitable for diagnostics.
+pub fn reveal_actual_level(
+    level: Option<Level>,
+    src: &mut LintLevelSource,
+    sess: &Session,
+    lint: LintId,
+    probe_for_lint_level: impl FnOnce(LintId) -> (Option<Level>, LintLevelSource),
+) -> Level {
+    // If `level` is none then we actually assume the default level for this lint.
+    let mut level = level.unwrap_or_else(|| lint.lint.default_level(sess.edition()));
+
+    // If we're about to issue a warning, check at the last minute for any
+    // directives against the warnings "lint". If, for example, there's an
+    // `allow(warnings)` in scope then we want to respect that instead.
+    //
+    // We exempt `FORBIDDEN_LINT_GROUPS` from this because it specifically
+    // triggers in cases (like #80988) where you have `forbid(warnings)`,
+    // and so if we turned that into an error, it'd defeat the purpose of the
+    // future compatibility warning.
+    if level == Level::Warn && lint != LintId::of(FORBIDDEN_LINT_GROUPS) {
+        let (warnings_level, warnings_src) = probe_for_lint_level(LintId::of(builtin::WARNINGS));
+        if let Some(configured_warning_level) = warnings_level {
+            if configured_warning_level != Level::Warn {
+                level = configured_warning_level;
+                *src = warnings_src;
             }
         }
+    }
 
-        // Ensure that we never exceed the `--cap-lints` argument
-        // unless the source is a --force-warn
-        level = if let LintLevelSource::CommandLine(_, Level::ForceWarn(_)) = src {
-            level
-        } else {
-            cmp::min(level, self.lint_cap)
-        };
-
-        if let Some(driver_level) = sess.driver_lint_caps.get(&LintId::of(lint)) {
-            // Ensure that we never exceed driver level.
-            level = cmp::min(*driver_level, level);
-        }
+    // Ensure that we never exceed the `--cap-lints` argument unless the source is a --force-warn
+    level = if let LintLevelSource::CommandLine(_, Level::ForceWarn(_)) = src {
+        level
+    } else {
+        cmp::min(level, sess.opts.lint_cap.unwrap_or(Level::Forbid))
+    };
 
-        (level, src)
+    if let Some(driver_level) = sess.driver_lint_caps.get(&lint) {
+        // Ensure that we never exceed driver level.
+        level = cmp::min(*driver_level, level);
     }
 
-    pub fn get_lint_id_level(
+    level
+}
+
+impl ShallowLintLevelMap {
+    /// Perform a deep probe in the HIR tree looking for the actual level for the lint.
+    /// This lint level is not usable for diagnostics, it needs to be corrected by
+    /// `reveal_actual_level` beforehand.
+    fn probe_for_lint_level(
         &self,
+        tcx: TyCtxt<'_>,
         id: LintId,
-        mut idx: LintStackIndex,
-        aux: Option<&FxHashMap<LintId, LevelAndSource>>,
+        start: HirId,
     ) -> (Option<Level>, LintLevelSource) {
-        if let Some(specs) = aux {
-            if let Some(&(level, src)) = specs.get(&id) {
-                return (Some(level), src);
-            }
+        if let Some(&(level, src)) = self.specs.get(&id) {
+            return (Some(level), src);
         }
-        loop {
-            let LintSet { ref specs, parent } = self.list[idx];
-            if let Some(&(level, src)) = specs.get(&id) {
+
+        for (parent, _) in tcx.hir().parent_iter(start) {
+            let specs = tcx.shallow_lint_levels_on(parent);
+            if let Some(&(level, src)) = specs.specs.get(&id) {
                 return (Some(level), src);
             }
-            if idx == COMMAND_LINE {
-                return (None, LintLevelSource::Default);
-            }
-            idx = parent;
         }
+        (None, LintLevelSource::Default)
     }
-}
-
-#[derive(Debug)]
-pub struct LintLevelMap {
-    /// This is a collection of lint expectations as described in RFC 2383, that
-    /// can be fulfilled during this compilation session. This means that at least
-    /// one expected lint is currently registered in the lint store.
-    ///
-    /// The [`LintExpectationId`] is stored as a part of the [`Expect`](Level::Expect)
-    /// lint level.
-    pub lint_expectations: Vec<(LintExpectationId, LintExpectation)>,
-    pub sets: LintLevelSets,
-    pub id_to_set: FxHashMap<HirId, LintStackIndex>,
-}
 
-impl LintLevelMap {
-    /// If the `id` was previously registered with `register_id` when building
-    /// this `LintLevelMap` this returns the corresponding lint level and source
-    /// of the lint level for the lint provided.
-    ///
-    /// If the `id` was not previously registered, returns `None`. If `None` is
-    /// returned then the parent of `id` should be acquired and this function
-    /// should be called again.
-    pub fn level_and_source(
+    /// Fetch and return the user-visible lint level for the given lint at the given HirId.
+    pub fn lint_level_id_at_node(
         &self,
-        lint: &'static Lint,
+        tcx: TyCtxt<'_>,
+        lint: LintId,
         id: HirId,
-        session: &Session,
-    ) -> Option<LevelAndSource> {
-        self.id_to_set.get(&id).map(|idx| self.sets.get_lint_level(lint, *idx, None, session))
+    ) -> (Level, LintLevelSource) {
+        let (level, mut src) = self.probe_for_lint_level(tcx, lint, id);
+        let level = reveal_actual_level(level, &mut src, tcx.sess, lint, |lint| {
+            self.probe_for_lint_level(tcx, lint, id)
+        });
+        debug!(?id, ?level, ?src);
+        (level, src)
     }
 }
 
-impl<'a> HashStable<StableHashingContext<'a>> for LintLevelMap {
-    #[inline]
-    fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
-        let LintLevelMap { ref sets, ref id_to_set, ref lint_expectations } = *self;
-
-        id_to_set.hash_stable(hcx, hasher);
-        lint_expectations.hash_stable(hcx, hasher);
+impl TyCtxt<'_> {
+    /// Fetch and return the user-visible lint level for the given lint at the given HirId.
+    pub fn lint_level_at_node(self, lint: &'static Lint, id: HirId) -> (Level, LintLevelSource) {
+        self.shallow_lint_levels_on(id).lint_level_id_at_node(self, LintId::of(lint), id)
+    }
 
-        hcx.while_hashing_spans(true, |hcx| sets.hash_stable(hcx, hasher))
+    /// Walks upwards from `id` to find a node which might change lint levels with attributes.
+    /// It stops at `bound` and just returns it if reached.
+    pub fn maybe_lint_level_root_bounded(self, mut id: HirId, bound: HirId) -> HirId {
+        let hir = self.hir();
+        while id != bound && self.shallow_lint_levels_on(id).specs.is_empty() {
+            id = hir.get_parent_node(id)
+        }
+        id
     }
 }
 
@@ -261,11 +235,11 @@ pub fn explain_lint_level_source(
                 ));
             }
         }
-        LintLevelSource::Node(lint_attr_name, src, reason) => {
+        LintLevelSource::Node { name: lint_attr_name, span, reason, .. } => {
             if let Some(rationale) = reason {
                 err.note(rationale.as_str());
             }
-            err.span_note_once(src, "the lint level is defined here");
+            err.span_note_once(span, "the lint level is defined here");
             if lint_attr_name.as_str() != name {
                 let level_str = level.as_str();
                 err.note_once(&format!(
diff --git a/compiler/rustc_middle/src/query/mod.rs b/compiler/rustc_middle/src/query/mod.rs
index 9cb19583121..312777230aa 100644
--- a/compiler/rustc_middle/src/query/mod.rs
+++ b/compiler/rustc_middle/src/query/mod.rs
@@ -273,10 +273,14 @@ rustc_queries! {
         separate_provide_extern
     }
 
-    query lint_levels(_: ()) -> LintLevelMap {
+    query shallow_lint_levels_on(key: HirId) -> rustc_middle::lint::ShallowLintLevelMap {
         arena_cache
-        eval_always
-        desc { "computing the lint levels for items in this crate" }
+        desc { |tcx| "looking up lint levels for `{}`", key }
+    }
+
+    query lint_expectations(_: ()) -> Vec<(LintExpectationId, LintExpectation)> {
+        arena_cache
+        desc { "computing `#[expect]`ed lints in this crate" }
     }
 
     query parent_module_from_def_id(key: LocalDefId) -> LocalDefId {
diff --git a/compiler/rustc_middle/src/ty/context.rs b/compiler/rustc_middle/src/ty/context.rs
index d0b49c4ee9e..c70478d0daa 100644
--- a/compiler/rustc_middle/src/ty/context.rs
+++ b/compiler/rustc_middle/src/ty/context.rs
@@ -4,7 +4,7 @@ use crate::arena::Arena;
 use crate::dep_graph::{DepGraph, DepKind, DepKindStruct};
 use crate::hir::place::Place as HirPlace;
 use crate::infer::canonical::{Canonical, CanonicalVarInfo, CanonicalVarInfos};
-use crate::lint::{struct_lint_level, LintLevelSource};
+use crate::lint::struct_lint_level;
 use crate::middle::codegen_fn_attrs::CodegenFnAttrs;
 use crate::middle::resolve_lifetime;
 use crate::middle::stability;
@@ -53,7 +53,7 @@ use rustc_query_system::ich::StableHashingContext;
 use rustc_serialize::opaque::{FileEncodeResult, FileEncoder};
 use rustc_session::config::{CrateType, OutputFilenames};
 use rustc_session::cstore::CrateStoreDyn;
-use rustc_session::lint::{Level, Lint};
+use rustc_session::lint::Lint;
 use rustc_session::Limit;
 use rustc_session::Session;
 use rustc_span::def_id::{DefPathHash, StableCrateId};
@@ -2810,44 +2810,6 @@ impl<'tcx> TyCtxt<'tcx> {
         iter.intern_with(|xs| self.intern_bound_variable_kinds(xs))
     }
 
-    /// Walks upwards from `id` to find a node which might change lint levels with attributes.
-    /// It stops at `bound` and just returns it if reached.
-    pub fn maybe_lint_level_root_bounded(self, mut id: HirId, bound: HirId) -> HirId {
-        let hir = self.hir();
-        loop {
-            if id == bound {
-                return bound;
-            }
-
-            if hir.attrs(id).iter().any(|attr| Level::from_attr(attr).is_some()) {
-                return id;
-            }
-            let next = hir.get_parent_node(id);
-            if next == id {
-                bug!("lint traversal reached the root of the crate");
-            }
-            id = next;
-        }
-    }
-
-    pub fn lint_level_at_node(
-        self,
-        lint: &'static Lint,
-        mut id: hir::HirId,
-    ) -> (Level, LintLevelSource) {
-        let sets = self.lint_levels(());
-        loop {
-            if let Some(pair) = sets.level_and_source(lint, id, self.sess) {
-                return pair;
-            }
-            let next = self.hir().get_parent_node(id);
-            if next == id {
-                bug!("lint traversal reached the root of the crate");
-            }
-            id = next;
-        }
-    }
-
     /// Emit a lint at `span` from a lint struct (some type that implements `DecorateLint`,
     /// typically generated by `#[derive(LintDiagnostic)]`).
     pub fn emit_spanned_lint(
diff --git a/compiler/rustc_middle/src/ty/query.rs b/compiler/rustc_middle/src/ty/query.rs
index a300a8df23d..36ea7946e9a 100644
--- a/compiler/rustc_middle/src/ty/query.rs
+++ b/compiler/rustc_middle/src/ty/query.rs
@@ -1,6 +1,6 @@
 use crate::dep_graph;
 use crate::infer::canonical::{self, Canonical};
-use crate::lint::LintLevelMap;
+use crate::lint::LintExpectation;
 use crate::metadata::ModChild;
 use crate::middle::codegen_fn_attrs::CodegenFnAttrs;
 use crate::middle::exported_symbols::{ExportedSymbol, SymbolExportInfo};
@@ -44,12 +44,14 @@ use rustc_errors::ErrorGuaranteed;
 use rustc_hir as hir;
 use rustc_hir::def::DefKind;
 use rustc_hir::def_id::{CrateNum, DefId, DefIdMap, DefIdSet, LocalDefId};
+use rustc_hir::hir_id::HirId;
 use rustc_hir::lang_items::{LangItem, LanguageItems};
 use rustc_hir::{Crate, ItemLocalId, TraitCandidate};
 use rustc_index::{bit_set::FiniteBitSet, vec::IndexVec};
 use rustc_session::config::{EntryFnType, OptLevel, OutputFilenames, SymbolManglingVersion};
 use rustc_session::cstore::{CrateDepKind, CrateSource};
 use rustc_session::cstore::{ExternCrate, ForeignModule, LinkagePreference, NativeLib};
+use rustc_session::lint::LintExpectationId;
 use rustc_session::utils::NativeLibKind;
 use rustc_session::Limits;
 use rustc_span::symbol::Symbol;