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