compiler/rustc_query_system/src/query/plumbing.rs

   1 //! The implementation of the query system itself. This defines the macros that
   2 //! generate the actual methods on tcx which find and execute the provider,
   3 //! manage the caches, and so forth.
   4
   5 use crate::dep_graph::{DepContext, DepKind, DepNode, DepNodeParams};
   6 use crate::dep_graph::{DepNodeIndex, SerializedDepNodeIndex};
   7 use crate::query::caches::QueryCache;
   8 use crate::query::config::{QueryDescription, QueryVtable, QueryVtableExt};
   9 use crate::query::job::{
  10     report_cycle, QueryInfo, QueryJob, QueryJobId, QueryJobInfo, QueryShardJobId,
  11 };
  12 use crate::query::{QueryContext, QueryMap, QueryStackFrame};
  13
  14 use rustc_data_structures::fingerprint::Fingerprint;
  15 use rustc_data_structures::fx::{FxHashMap, FxHasher};
  16 use rustc_data_structures::sharded::{get_shard_index_by_hash, Sharded};
  17 use rustc_data_structures::sync::{Lock, LockGuard};
  18 use rustc_data_structures::thin_vec::ThinVec;
  19 #[cfg(not(parallel_compiler))]
  20 use rustc_errors::DiagnosticBuilder;
  21 use rustc_errors::{Diagnostic, FatalError};
  22 use rustc_span::{Span, DUMMY_SP};
  23 use std::collections::hash_map::Entry;
  24 use std::fmt::Debug;
  25 use std::hash::{Hash, Hasher};
  26 use std::mem;
  27 use std::num::NonZeroU32;
  28 use std::ptr;
  29 #[cfg(debug_assertions)]
  30 use std::sync::atomic::{AtomicUsize, Ordering};
  31
  32 pub struct QueryCacheStore<C: QueryCache> {
  33     cache: C,
  34     shards: Sharded<C::Sharded>,
  35     #[cfg(debug_assertions)]
  36     pub cache_hits: AtomicUsize,
  37 }
  38
  39 impl<C: QueryCache + Default> Default for QueryCacheStore<C> {
  40     fn default() -> Self {
  41         Self {
  42             cache: C::default(),
  43             shards: Default::default(),
  44             #[cfg(debug_assertions)]
  45             cache_hits: AtomicUsize::new(0),
  46         }
  47     }
  48 }
  49
  50 /// Values used when checking a query cache which can be reused on a cache-miss to execute the query.
  51 pub struct QueryLookup {
  52     pub(super) key_hash: u64,
  53     shard: usize,
  54 }
  55
  56 // We compute the key's hash once and then use it for both the
  57 // shard lookup and the hashmap lookup. This relies on the fact
  58 // that both of them use `FxHasher`.
  59 fn hash_for_shard<K: Hash>(key: &K) -> u64 {
  60     let mut hasher = FxHasher::default();
  61     key.hash(&mut hasher);
  62     hasher.finish()
  63 }
  64
  65 impl<C: QueryCache> QueryCacheStore<C> {
  66     pub(super) fn get_lookup<'tcx>(
  67         &'tcx self,
  68         key: &C::Key,
  69     ) -> (QueryLookup, LockGuard<'tcx, C::Sharded>) {
  70         let key_hash = hash_for_shard(key);
  71         let shard = get_shard_index_by_hash(key_hash);
  72         let lock = self.shards.get_shard_by_index(shard).lock();
  73         (QueryLookup { key_hash, shard }, lock)
  74     }
  75
  76     pub fn iter_results(&self, f: &mut dyn FnMut(&C::Key, &C::Value, DepNodeIndex)) {
  77         self.cache.iter(&self.shards, f)
  78     }
  79 }
  80
  81 struct QueryStateShard<D, K> {
  82     active: FxHashMap<K, QueryResult<D>>,
  83
  84     /// Used to generate unique ids for active jobs.
  85     jobs: u32,
  86 }
  87
  88 impl<D, K> Default for QueryStateShard<D, K> {
  89     fn default() -> QueryStateShard<D, K> {
  90         QueryStateShard { active: Default::default(), jobs: 0 }
  91     }
  92 }
  93
  94 pub struct QueryState<D, K> {
  95     shards: Sharded<QueryStateShard<D, K>>,
  96 }
  97
  98 /// Indicates the state of a query for a given key in a query map.
  99 enum QueryResult<D> {
 100     /// An already executing query. The query job can be used to await for its completion.
 101     Started(QueryJob<D>),
 102
 103     /// The query panicked. Queries trying to wait on this will raise a fatal error which will
 104     /// silently panic.
 105     Poisoned,
 106 }
 107
 108 impl<D, K> QueryState<D, K>
 109 where
 110     D: Copy + Clone + Eq + Hash,
 111     K: Eq + Hash + Clone + Debug,
 112 {
 113     pub fn all_inactive(&self) -> bool {
 114         let shards = self.shards.lock_shards();
 115         shards.iter().all(|shard| shard.active.is_empty())
 116     }
 117
 118     pub fn try_collect_active_jobs<CTX: Copy>(
 119         &self,
 120         tcx: CTX,
 121         kind: D,
 122         make_query: fn(CTX, K) -> QueryStackFrame,
 123         jobs: &mut QueryMap<D>,
 124     ) -> Option<()> {
 125         // We use try_lock_shards here since we are called from the
 126         // deadlock handler, and this shouldn't be locked.
 127         let shards = self.shards.try_lock_shards()?;
 128         for (shard_id, shard) in shards.iter().enumerate() {
 129             for (k, v) in shard.active.iter() {
 130                 if let QueryResult::Started(ref job) = *v {
 131                     let id = QueryJobId::new(job.id, shard_id, kind);
 132                     let info = QueryInfo { span: job.span, query: make_query(tcx, k.clone()) };
 133                     jobs.insert(id, QueryJobInfo { info, job: job.clone() });
 134                 }
 135             }
 136         }
 137
 138         Some(())
 139     }
 140 }
 141
 142 impl<D, K> Default for QueryState<D, K> {
 143     fn default() -> QueryState<D, K> {
 144         QueryState { shards: Default::default() }
 145     }
 146 }
 147
 148 /// A type representing the responsibility to execute the job in the `job` field.
 149 /// This will poison the relevant query if dropped.
 150 struct JobOwner<'tcx, D, C>
 151 where
 152     D: Copy + Clone + Eq + Hash,
 153     C: QueryCache,
 154 {
 155     state: &'tcx QueryState<D, C::Key>,
 156     cache: &'tcx QueryCacheStore<C>,
 157     key: C::Key,
 158     id: QueryJobId<D>,
 159 }
 160
 161 #[cold]
 162 #[inline(never)]
 163 #[cfg(not(parallel_compiler))]
 164 fn mk_cycle<CTX, V, R>(
 165     tcx: CTX,
 166     root: QueryJobId<CTX::DepKind>,
 167     span: Span,
 168     handle_cycle_error: fn(CTX, DiagnosticBuilder<'_>) -> V,
 169     cache: &dyn crate::query::QueryStorage<Value = V, Stored = R>,
 170 ) -> R
 171 where
 172     CTX: QueryContext,
 173     V: std::fmt::Debug,
 174     R: Clone,
 175 {
 176     let error: CycleError = root.find_cycle_in_stack(
 177         tcx.try_collect_active_jobs().unwrap(),
 178         &tcx.current_query_job(),
 179         span,
 180     );
 181     let error = report_cycle(tcx.dep_context().sess(), error);
 182     let value = handle_cycle_error(tcx, error);
 183     cache.store_nocache(value)
 184 }
 185
 186 impl<'tcx, D, C> JobOwner<'tcx, D, C>
 187 where
 188     D: Copy + Clone + Eq + Hash,
 189     C: QueryCache,
 190 {
 191     /// Either gets a `JobOwner` corresponding the query, allowing us to
 192     /// start executing the query, or returns with the result of the query.
 193     /// This function assumes that `try_get_cached` is already called and returned `lookup`.
 194     /// If the query is executing elsewhere, this will wait for it and return the result.
 195     /// If the query panicked, this will silently panic.
 196     ///
 197     /// This function is inlined because that results in a noticeable speed-up
 198     /// for some compile-time benchmarks.
 199     #[inline(always)]
 200     fn try_start<'b, CTX>(
 201         tcx: CTX,
 202         state: &'b QueryState<CTX::DepKind, C::Key>,
 203         cache: &'b QueryCacheStore<C>,
 204         span: Span,
 205         key: C::Key,
 206         lookup: QueryLookup,
 207         query: &QueryVtable<CTX, C::Key, C::Value>,
 208     ) -> TryGetJob<'b, CTX::DepKind, C>
 209     where
 210         CTX: QueryContext,
 211     {
 212         let shard = lookup.shard;
 213         let mut state_lock = state.shards.get_shard_by_index(shard).lock();
 214         let lock = &mut *state_lock;
 215
 216         match lock.active.entry(key) {
 217             Entry::Vacant(entry) => {
 218                 // Generate an id unique within this shard.
 219                 let id = lock.jobs.checked_add(1).unwrap();
 220                 lock.jobs = id;
 221                 let id = QueryShardJobId(NonZeroU32::new(id).unwrap());
 222
 223                 let job = tcx.current_query_job();
 224                 let job = QueryJob::new(id, span, job);
 225
 226                 let key = entry.key().clone();
 227                 entry.insert(QueryResult::Started(job));
 228
 229                 let global_id = QueryJobId::new(id, shard, query.dep_kind);
 230                 let owner = JobOwner { state, cache, id: global_id, key };
 231                 return TryGetJob::NotYetStarted(owner);
 232             }
 233             Entry::Occupied(mut entry) => {
 234                 match entry.get_mut() {
 235                     #[cfg(not(parallel_compiler))]
 236                     QueryResult::Started(job) => {
 237                         let id = QueryJobId::new(job.id, shard, query.dep_kind);
 238
 239                         drop(state_lock);
 240
 241                         // If we are single-threaded we know that we have cycle error,
 242                         // so we just return the error.
 243                         return TryGetJob::Cycle(mk_cycle(
 244                             tcx,
 245                             id,
 246                             span,
 247                             query.handle_cycle_error,
 248                             &cache.cache,
 249                         ));
 250                     }
 251                     #[cfg(parallel_compiler)]
 252                     QueryResult::Started(job) => {
 253                         // For parallel queries, we'll block and wait until the query running
 254                         // in another thread has completed. Record how long we wait in the
 255                         // self-profiler.
 256                         let query_blocked_prof_timer = tcx.dep_context().profiler().query_blocked();
 257
 258                         // Get the latch out
 259                         let latch = job.latch();
 260                         let key = entry.key().clone();
 261
 262                         drop(state_lock);
 263
 264                         // With parallel queries we might just have to wait on some other
 265                         // thread.
 266                         let result = latch.wait_on(tcx.current_query_job(), span);
 267
 268                         if let Err(cycle) = result {
 269                             let cycle = report_cycle(tcx.dep_context().sess(), cycle);
 270                             let value = (query.handle_cycle_error)(tcx, cycle);
 271                             let value = cache.cache.store_nocache(value);
 272                             return TryGetJob::Cycle(value);
 273                         }
 274
 275                         let cached = cache
 276                             .cache
 277                             .lookup(cache, &key, |value, index| {
 278                                 if unlikely!(tcx.dep_context().profiler().enabled()) {
 279                                     tcx.dep_context().profiler().query_cache_hit(index.into());
 280                                 }
 281                                 #[cfg(debug_assertions)]
 282                                 {
 283                                     cache.cache_hits.fetch_add(1, Ordering::Relaxed);
 284                                 }
 285                                 (value.clone(), index)
 286                             })
 287                             .unwrap_or_else(|_| panic!("value must be in cache after waiting"));
 288
 289                         query_blocked_prof_timer.finish_with_query_invocation_id(cached.1.into());
 290
 291                         return TryGetJob::JobCompleted(cached);
 292                     }
 293                     QueryResult::Poisoned => FatalError.raise(),
 294                 }
 295             }
 296         }
 297     }
 298
 299     /// Completes the query by updating the query cache with the `result`,
 300     /// signals the waiter and forgets the JobOwner, so it won't poison the query
 301     fn complete(self, result: C::Value, dep_node_index: DepNodeIndex) -> C::Stored {
 302         // We can move out of `self` here because we `mem::forget` it below
 303         let key = unsafe { ptr::read(&self.key) };
 304         let state = self.state;
 305         let cache = self.cache;
 306
 307         // Forget ourself so our destructor won't poison the query
 308         mem::forget(self);
 309
 310         let (job, result) = {
 311             let key_hash = hash_for_shard(&key);
 312             let shard = get_shard_index_by_hash(key_hash);
 313             let job = {
 314                 let mut lock = state.shards.get_shard_by_index(shard).lock();
 315                 match lock.active.remove(&key).unwrap() {
 316                     QueryResult::Started(job) => job,
 317                     QueryResult::Poisoned => panic!(),
 318                 }
 319             };
 320             let result = {
 321                 let mut lock = cache.shards.get_shard_by_index(shard).lock();
 322                 cache.cache.complete(&mut lock, key, result, dep_node_index)
 323             };
 324             (job, result)
 325         };
 326
 327         job.signal_complete();
 328         result
 329     }
 330 }
 331
 332 fn with_diagnostics<F, R>(f: F) -> (R, ThinVec<Diagnostic>)
 333 where
 334     F: FnOnce(Option<&Lock<ThinVec<Diagnostic>>>) -> R,
 335 {
 336     let diagnostics = Lock::new(ThinVec::new());
 337     let result = f(Some(&diagnostics));
 338     (result, diagnostics.into_inner())
 339 }
 340
 341 impl<'tcx, D, C> Drop for JobOwner<'tcx, D, C>
 342 where
 343     D: Copy + Clone + Eq + Hash,
 344     C: QueryCache,
 345 {
 346     #[inline(never)]
 347     #[cold]
 348     fn drop(&mut self) {
 349         // Poison the query so jobs waiting on it panic.
 350         let state = self.state;
 351         let shard = state.shards.get_shard_by_value(&self.key);
 352         let job = {
 353             let mut shard = shard.lock();
 354             let job = match shard.active.remove(&self.key).unwrap() {
 355                 QueryResult::Started(job) => job,
 356                 QueryResult::Poisoned => panic!(),
 357             };
 358             shard.active.insert(self.key.clone(), QueryResult::Poisoned);
 359             job
 360         };
 361         // Also signal the completion of the job, so waiters
 362         // will continue execution.
 363         job.signal_complete();
 364     }
 365 }
 366
 367 #[derive(Clone)]
 368 pub(crate) struct CycleError {
 369     /// The query and related span that uses the cycle.
 370     pub usage: Option<(Span, QueryStackFrame)>,
 371     pub cycle: Vec<QueryInfo>,
 372 }
 373
 374 /// The result of `try_start`.
 375 enum TryGetJob<'tcx, D, C>
 376 where
 377     D: Copy + Clone + Eq + Hash,
 378     C: QueryCache,
 379 {
 380     /// The query is not yet started. Contains a guard to the cache eventually used to start it.
 381     NotYetStarted(JobOwner<'tcx, D, C>),
 382
 383     /// The query was already completed.
 384     /// Returns the result of the query and its dep-node index
 385     /// if it succeeded or a cycle error if it failed.
 386     #[cfg(parallel_compiler)]
 387     JobCompleted((C::Stored, DepNodeIndex)),
 388
 389     /// Trying to execute the query resulted in a cycle.
 390     Cycle(C::Stored),
 391 }
 392
 393 /// Checks if the query is already computed and in the cache.
 394 /// It returns the shard index and a lock guard to the shard,
 395 /// which will be used if the query is not in the cache and we need
 396 /// to compute it.
 397 #[inline]
 398 pub fn try_get_cached<'a, CTX, C, R, OnHit>(
 399     tcx: CTX,
 400     cache: &'a QueryCacheStore<C>,
 401     key: &C::Key,
 402     // `on_hit` can be called while holding a lock to the query cache
 403     on_hit: OnHit,
 404 ) -> Result<R, QueryLookup>
 405 where
 406     C: QueryCache,
 407     CTX: DepContext,
 408     OnHit: FnOnce(&C::Stored) -> R,
 409 {
 410     cache.cache.lookup(cache, &key, |value, index| {
 411         if unlikely!(tcx.profiler().enabled()) {
 412             tcx.profiler().query_cache_hit(index.into());
 413         }
 414         #[cfg(debug_assertions)]
 415         {
 416             cache.cache_hits.fetch_add(1, Ordering::Relaxed);
 417         }
 418         tcx.dep_graph().read_index(index);
 419         on_hit(value)
 420     })
 421 }
 422
 423 fn try_execute_query<CTX, C>(
 424     tcx: CTX,
 425     state: &QueryState<CTX::DepKind, C::Key>,
 426     cache: &QueryCacheStore<C>,
 427     span: Span,
 428     key: C::Key,
 429     lookup: QueryLookup,
 430     query: &QueryVtable<CTX, C::Key, C::Value>,
 431     compute: fn(CTX::DepContext, C::Key) -> C::Value,
 432 ) -> C::Stored
 433 where
 434     C: QueryCache,
 435     C::Key: DepNodeParams<CTX::DepContext>,
 436     CTX: QueryContext,
 437 {
 438     let job = match JobOwner::<'_, CTX::DepKind, C>::try_start(
 439         tcx,
 440         state,
 441         cache,
 442         span,
 443         key.clone(),
 444         lookup,
 445         query,
 446     ) {
 447         TryGetJob::NotYetStarted(job) => job,
 448         TryGetJob::Cycle(result) => return result,
 449         #[cfg(parallel_compiler)]
 450         TryGetJob::JobCompleted((v, index)) => {
 451             tcx.dep_context().dep_graph().read_index(index);
 452             return v;
 453         }
 454     };
 455
 456     let dep_graph = tcx.dep_context().dep_graph();
 457
 458     // Fast path for when incr. comp. is off.
 459     if !dep_graph.is_fully_enabled() {
 460         let prof_timer = tcx.dep_context().profiler().query_provider();
 461         let result = tcx.start_query(job.id, None, || compute(*tcx.dep_context(), key));
 462         let dep_node_index = dep_graph.next_virtual_depnode_index();
 463         prof_timer.finish_with_query_invocation_id(dep_node_index.into());
 464         return job.complete(result, dep_node_index);
 465     }
 466
 467     if query.anon {
 468         let prof_timer = tcx.dep_context().profiler().query_provider();
 469
 470         let ((result, dep_node_index), diagnostics) = with_diagnostics(|diagnostics| {
 471             tcx.start_query(job.id, diagnostics, || {
 472                 dep_graph.with_anon_task(*tcx.dep_context(), query.dep_kind, || {
 473                     compute(*tcx.dep_context(), key)
 474                 })
 475             })
 476         });
 477
 478         prof_timer.finish_with_query_invocation_id(dep_node_index.into());
 479
 480         dep_graph.read_index(dep_node_index);
 481
 482         if unlikely!(!diagnostics.is_empty()) {
 483             tcx.store_diagnostics_for_anon_node(dep_node_index, diagnostics);
 484         }
 485
 486         return job.complete(result, dep_node_index);
 487     }
 488
 489     let dep_node = query.to_dep_node(*tcx.dep_context(), &key);
 490
 491     if !query.eval_always {
 492         // The diagnostics for this query will be
 493         // promoted to the current session during
 494         // `try_mark_green()`, so we can ignore them here.
 495         let loaded = tcx.start_query(job.id, None, || {
 496             let marked = dep_graph.try_mark_green_and_read(tcx, &dep_node);
 497             marked.map(|(prev_dep_node_index, dep_node_index)| {
 498                 (
 499                     load_from_disk_and_cache_in_memory(
 500                         tcx,
 501                         key.clone(),
 502                         prev_dep_node_index,
 503                         dep_node_index,
 504                         &dep_node,
 505                         query,
 506                         compute,
 507                     ),
 508                     dep_node_index,
 509                 )
 510             })
 511         });
 512         if let Some((result, dep_node_index)) = loaded {
 513             return job.complete(result, dep_node_index);
 514         }
 515     }
 516
 517     let (result, dep_node_index) = force_query_with_job(tcx, key, job, dep_node, query, compute);
 518     dep_graph.read_index(dep_node_index);
 519     result
 520 }
 521
 522 fn load_from_disk_and_cache_in_memory<CTX, K, V: Debug>(
 523     tcx: CTX,
 524     key: K,
 525     prev_dep_node_index: SerializedDepNodeIndex,
 526     dep_node_index: DepNodeIndex,
 527     dep_node: &DepNode<CTX::DepKind>,
 528     query: &QueryVtable<CTX, K, V>,
 529     compute: fn(CTX::DepContext, K) -> V,
 530 ) -> V
 531 where
 532     CTX: QueryContext,
 533 {
 534     // Note this function can be called concurrently from the same query
 535     // We must ensure that this is handled correctly.
 536
 537     debug_assert!(tcx.dep_context().dep_graph().is_green(dep_node));
 538
 539     // First we try to load the result from the on-disk cache.
 540     let result = if query.cache_on_disk(tcx, &key, None) {
 541         let prof_timer = tcx.dep_context().profiler().incr_cache_loading();
 542         let result = query.try_load_from_disk(tcx, prev_dep_node_index);
 543         prof_timer.finish_with_query_invocation_id(dep_node_index.into());
 544
 545         // We always expect to find a cached result for things that
 546         // can be forced from `DepNode`.
 547         debug_assert!(
 548             !dep_node.kind.can_reconstruct_query_key() || result.is_some(),
 549             "missing on-disk cache entry for {:?}",
 550             dep_node
 551         );
 552         result
 553     } else {
 554         // Some things are never cached on disk.
 555         None
 556     };
 557
 558     if let Some(result) = result {
 559         // If `-Zincremental-verify-ich` is specified, re-hash results from
 560         // the cache and make sure that they have the expected fingerprint.
 561         if unlikely!(tcx.dep_context().sess().opts.debugging_opts.incremental_verify_ich) {
 562             incremental_verify_ich(*tcx.dep_context(), &result, dep_node, query);
 563         }
 564
 565         result
 566     } else {
 567         // We could not load a result from the on-disk cache, so
 568         // recompute.
 569         let prof_timer = tcx.dep_context().profiler().query_provider();
 570
 571         // The dep-graph for this computation is already in-place.
 572         let result = tcx.dep_context().dep_graph().with_ignore(|| compute(*tcx.dep_context(), key));
 573
 574         prof_timer.finish_with_query_invocation_id(dep_node_index.into());
 575
 576         // Verify that re-running the query produced a result with the expected hash
 577         // This catches bugs in query implementations, turning them into ICEs.
 578         // For example, a query might sort its result by `DefId` - since `DefId`s are
 579         // not stable across compilation sessions, the result could get up getting sorted
 580         // in a different order when the query is re-run, even though all of the inputs
 581         // (e.g. `DefPathHash` values) were green.
 582         //
 583         // See issue #82920 for an example of a miscompilation that would get turned into
 584         // an ICE by this check
 585         incremental_verify_ich(*tcx.dep_context(), &result, dep_node, query);
 586
 587         result
 588     }
 589 }
 590
 591 fn incremental_verify_ich<CTX, K, V: Debug>(
 592     tcx: CTX::DepContext,
 593     result: &V,
 594     dep_node: &DepNode<CTX::DepKind>,
 595     query: &QueryVtable<CTX, K, V>,
 596 ) where
 597     CTX: QueryContext,
 598 {
 599     assert!(
 600         tcx.dep_graph().is_green(dep_node),
 601         "fingerprint for green query instance not loaded from cache: {:?}",
 602         dep_node,
 603     );
 604
 605     debug!("BEGIN verify_ich({:?})", dep_node);
 606     let mut hcx = tcx.create_stable_hashing_context();
 607
 608     let new_hash = query.hash_result(&mut hcx, result).unwrap_or(Fingerprint::ZERO);
 609     debug!("END verify_ich({:?})", dep_node);
 610
 611     let old_hash = tcx.dep_graph().prev_fingerprint_of(dep_node);
 612
 613     if Some(new_hash) != old_hash {
 614         let run_cmd = if let Some(crate_name) = &tcx.sess().opts.crate_name {
 615             format!("`cargo clean -p {}` or `cargo clean`", crate_name)
 616         } else {
 617             "`cargo clean`".to_string()
 618         };
 619         tcx.sess().struct_err(&format!("internal compiler error: encountered incremental compilation error with {:?}", dep_node))
 620             .help(&format!("This is a known issue with the compiler. Run {} to allow your project to compile", run_cmd))
 621             .note(&format!("Please follow the instructions below to create a bug report with the provided information"))
 622             .note(&format!("See <https://github.com/rust-lang/rust/issues/84970> for more information"))
 623             .emit();
 624         panic!("Found unstable fingerprints for {:?}: {:?}", dep_node, result);
 625     }
 626 }
 627
 628 fn force_query_with_job<C, CTX>(
 629     tcx: CTX,
 630     key: C::Key,
 631     job: JobOwner<'_, CTX::DepKind, C>,
 632     dep_node: DepNode<CTX::DepKind>,
 633     query: &QueryVtable<CTX, C::Key, C::Value>,
 634     compute: fn(CTX::DepContext, C::Key) -> C::Value,
 635 ) -> (C::Stored, DepNodeIndex)
 636 where
 637     C: QueryCache,
 638     CTX: QueryContext,
 639 {
 640     // If the following assertion triggers, it can have two reasons:
 641     // 1. Something is wrong with DepNode creation, either here or
 642     //    in `DepGraph::try_mark_green()`.
 643     // 2. Two distinct query keys get mapped to the same `DepNode`
 644     //    (see for example #48923).
 645     assert!(
 646         !tcx.dep_context().dep_graph().dep_node_exists(&dep_node),
 647         "forcing query with already existing `DepNode`\n\
 648                  - query-key: {:?}\n\
 649                  - dep-node: {:?}",
 650         key,
 651         dep_node
 652     );
 653
 654     let prof_timer = tcx.dep_context().profiler().query_provider();
 655
 656     let ((result, dep_node_index), diagnostics) = with_diagnostics(|diagnostics| {
 657         tcx.start_query(job.id, diagnostics, || {
 658             if query.eval_always {
 659                 tcx.dep_context().dep_graph().with_eval_always_task(
 660                     dep_node,
 661                     *tcx.dep_context(),
 662                     key,
 663                     compute,
 664                     query.hash_result,
 665                 )
 666             } else {
 667                 tcx.dep_context().dep_graph().with_task(
 668                     dep_node,
 669                     *tcx.dep_context(),
 670                     key,
 671                     compute,
 672                     query.hash_result,
 673                 )
 674             }
 675         })
 676     });
 677
 678     prof_timer.finish_with_query_invocation_id(dep_node_index.into());
 679
 680     if unlikely!(!diagnostics.is_empty()) && dep_node.kind != DepKind::NULL {
 681         tcx.store_diagnostics(dep_node_index, diagnostics);
 682     }
 683
 684     let result = job.complete(result, dep_node_index);
 685
 686     (result, dep_node_index)
 687 }
 688
 689 #[inline(never)]
 690 fn get_query_impl<CTX, C>(
 691     tcx: CTX,
 692     state: &QueryState<CTX::DepKind, C::Key>,
 693     cache: &QueryCacheStore<C>,
 694     span: Span,
 695     key: C::Key,
 696     lookup: QueryLookup,
 697     query: &QueryVtable<CTX, C::Key, C::Value>,
 698     compute: fn(CTX::DepContext, C::Key) -> C::Value,
 699 ) -> C::Stored
 700 where
 701     CTX: QueryContext,
 702     C: QueryCache,
 703     C::Key: DepNodeParams<CTX::DepContext>,
 704 {
 705     try_execute_query(tcx, state, cache, span, key, lookup, query, compute)
 706 }
 707
 708 /// Ensure that either this query has all green inputs or been executed.
 709 /// Executing `query::ensure(D)` is considered a read of the dep-node `D`.
 710 /// Returns true if the query should still run.
 711 ///
 712 /// This function is particularly useful when executing passes for their
 713 /// side-effects -- e.g., in order to report errors for erroneous programs.
 714 ///
 715 /// Note: The optimization is only available during incr. comp.
 716 #[inline(never)]
 717 fn ensure_must_run<CTX, K, V>(tcx: CTX, key: &K, query: &QueryVtable<CTX, K, V>) -> bool
 718 where
 719     K: crate::dep_graph::DepNodeParams<CTX::DepContext>,
 720     CTX: QueryContext,
 721 {
 722     if query.eval_always {
 723         return true;
 724     }
 725
 726     // Ensuring an anonymous query makes no sense
 727     assert!(!query.anon);
 728
 729     let dep_node = query.to_dep_node(*tcx.dep_context(), key);
 730
 731     match tcx.dep_context().dep_graph().try_mark_green_and_read(tcx, &dep_node) {
 732         None => {
 733             // A None return from `try_mark_green_and_read` means that this is either
 734             // a new dep node or that the dep node has already been marked red.
 735             // Either way, we can't call `dep_graph.read()` as we don't have the
 736             // DepNodeIndex. We must invoke the query itself. The performance cost
 737             // this introduces should be negligible as we'll immediately hit the
 738             // in-memory cache, or another query down the line will.
 739             true
 740         }
 741         Some((_, dep_node_index)) => {
 742             tcx.dep_context().profiler().query_cache_hit(dep_node_index.into());
 743             false
 744         }
 745     }
 746 }
 747
 748 #[inline(never)]
 749 fn force_query_impl<CTX, C>(
 750     tcx: CTX,
 751     state: &QueryState<CTX::DepKind, C::Key>,
 752     cache: &QueryCacheStore<C>,
 753     key: C::Key,
 754     dep_node: DepNode<CTX::DepKind>,
 755     query: &QueryVtable<CTX, C::Key, C::Value>,
 756     compute: fn(CTX::DepContext, C::Key) -> C::Value,
 757 ) -> bool
 758 where
 759     C: QueryCache,
 760     C::Key: DepNodeParams<CTX::DepContext>,
 761     CTX: QueryContext,
 762 {
 763     debug_assert!(!query.anon);
 764
 765     // We may be concurrently trying both execute and force a query.
 766     // Ensure that only one of them runs the query.
 767     let cached = cache.cache.lookup(cache, &key, |_, index| {
 768         if unlikely!(tcx.dep_context().profiler().enabled()) {
 769             tcx.dep_context().profiler().query_cache_hit(index.into());
 770         }
 771         #[cfg(debug_assertions)]
 772         {
 773             cache.cache_hits.fetch_add(1, Ordering::Relaxed);
 774         }
 775     });
 776
 777     let lookup = match cached {
 778         Ok(()) => return true,
 779         Err(lookup) => lookup,
 780     };
 781
 782     let job = match JobOwner::<'_, CTX::DepKind, C>::try_start(
 783         tcx,
 784         state,
 785         cache,
 786         DUMMY_SP,
 787         key.clone(),
 788         lookup,
 789         query,
 790     ) {
 791         TryGetJob::NotYetStarted(job) => job,
 792         TryGetJob::Cycle(_) => return true,
 793         #[cfg(parallel_compiler)]
 794         TryGetJob::JobCompleted(_) => return true,
 795     };
 796
 797     force_query_with_job(tcx, key, job, dep_node, query, compute);
 798
 799     true
 800 }
 801
 802 pub enum QueryMode {
 803     Get,
 804     Ensure,
 805 }
 806
 807 pub fn get_query<Q, CTX>(
 808     tcx: CTX,
 809     span: Span,
 810     key: Q::Key,
 811     lookup: QueryLookup,
 812     mode: QueryMode,
 813 ) -> Option<Q::Stored>
 814 where
 815     Q: QueryDescription<CTX>,
 816     Q::Key: DepNodeParams<CTX::DepContext>,
 817     CTX: QueryContext,
 818 {
 819     let query = &Q::VTABLE;
 820     if let QueryMode::Ensure = mode {
 821         if !ensure_must_run(tcx, &key, query) {
 822             return None;
 823         }
 824     }
 825
 826     debug!("ty::query::get_query<{}>(key={:?}, span={:?})", Q::NAME, key, span);
 827     let compute = Q::compute_fn(tcx, &key);
 828     let value = get_query_impl(
 829         tcx,
 830         Q::query_state(tcx),
 831         Q::query_cache(tcx),
 832         span,
 833         key,
 834         lookup,
 835         query,
 836         compute,
 837     );
 838     Some(value)
 839 }
 840
 841 pub fn force_query<Q, CTX>(tcx: CTX, dep_node: &DepNode<CTX::DepKind>) -> bool
 842 where
 843     Q: QueryDescription<CTX>,
 844     Q::Key: DepNodeParams<CTX::DepContext>,
 845     CTX: QueryContext,
 846 {
 847     if Q::ANON {
 848         return false;
 849     }
 850
 851     if !<Q::Key as DepNodeParams<CTX::DepContext>>::can_reconstruct_query_key() {
 852         return false;
 853     }
 854
 855     let key = if let Some(key) =
 856         <Q::Key as DepNodeParams<CTX::DepContext>>::recover(*tcx.dep_context(), &dep_node)
 857     {
 858         key
 859     } else {
 860         return false;
 861     };
 862
 863     let compute = Q::compute_fn(tcx, &key);
 864     force_query_impl(
 865         tcx,
 866         Q::query_state(tcx),
 867         Q::query_cache(tcx),
 868         key,
 869         *dep_node,
 870         &Q::VTABLE,
 871         compute,
 872     )
 873 }