src/librustc/ty/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, DepNodeIndex, SerializedDepNodeIndex};
   6 use crate::ty::query::caches::QueryCache;
   7 use crate::ty::query::config::{QueryContext, QueryDescription};
   8 use crate::ty::query::job::{QueryInfo, QueryJob, QueryJobId, QueryJobInfo, QueryShardJobId};
   9 use crate::ty::query::Query;
  10 use crate::ty::tls;
  11 use crate::ty::{self, TyCtxt};
  12
  13 #[cfg(not(parallel_compiler))]
  14 use rustc_data_structures::cold_path;
  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::{struct_span_err, Diagnostic, DiagnosticBuilder, FatalError, Handler, Level};
  20 use rustc_session::Session;
  21 use rustc_span::def_id::DefId;
  22 use rustc_span::source_map::DUMMY_SP;
  23 use rustc_span::Span;
  24 use std::collections::hash_map::Entry;
  25 use std::convert::TryFrom;
  26 use std::fmt::Debug;
  27 use std::hash::{Hash, Hasher};
  28 use std::mem;
  29 use std::num::NonZeroU32;
  30 use std::ptr;
  31 #[cfg(debug_assertions)]
  32 use std::sync::atomic::{AtomicUsize, Ordering};
  33
  34 pub(crate) struct QueryStateShard<CTX: QueryContext, K, C> {
  35     cache: C,
  36     active: FxHashMap<K, QueryResult<CTX>>,
  37
  38     /// Used to generate unique ids for active jobs.
  39     jobs: u32,
  40 }
  41
  42 impl<CTX: QueryContext, K, C> QueryStateShard<CTX, K, C> {
  43     fn get_cache(&mut self) -> &mut C {
  44         &mut self.cache
  45     }
  46 }
  47
  48 impl<CTX: QueryContext, K, C: Default> Default for QueryStateShard<CTX, K, C> {
  49     fn default() -> QueryStateShard<CTX, K, C> {
  50         QueryStateShard { cache: Default::default(), active: Default::default(), jobs: 0 }
  51     }
  52 }
  53
  54 pub(crate) struct QueryState<CTX: QueryContext, C: QueryCache> {
  55     cache: C,
  56     shards: Sharded<QueryStateShard<CTX, C::Key, C::Sharded>>,
  57     #[cfg(debug_assertions)]
  58     pub(super) cache_hits: AtomicUsize,
  59 }
  60
  61 impl<CTX: QueryContext, C: QueryCache> QueryState<CTX, C> {
  62     pub(super) fn get_lookup<K2: Hash>(
  63         &'tcx self,
  64         key: &K2,
  65     ) -> QueryLookup<'tcx, CTX, C::Key, C::Sharded> {
  66         // We compute the key's hash once and then use it for both the
  67         // shard lookup and the hashmap lookup. This relies on the fact
  68         // that both of them use `FxHasher`.
  69         let mut hasher = FxHasher::default();
  70         key.hash(&mut hasher);
  71         let key_hash = hasher.finish();
  72
  73         let shard = self.shards.get_shard_index_by_hash(key_hash);
  74         let lock = self.shards.get_shard_by_index(shard).lock();
  75         QueryLookup { key_hash, shard, lock }
  76     }
  77 }
  78
  79 /// Indicates the state of a query for a given key in a query map.
  80 enum QueryResult<CTX: QueryContext> {
  81     /// An already executing query. The query job can be used to await for its completion.
  82     Started(QueryJob<CTX>),
  83
  84     /// The query panicked. Queries trying to wait on this will raise a fatal error which will
  85     /// silently panic.
  86     Poisoned,
  87 }
  88
  89 impl<CTX: QueryContext, C: QueryCache> QueryState<CTX, C> {
  90     pub(super) fn iter_results<R>(
  91         &self,
  92         f: impl for<'a> FnOnce(
  93             Box<dyn Iterator<Item = (&'a C::Key, &'a C::Value, DepNodeIndex)> + 'a>,
  94         ) -> R,
  95     ) -> R {
  96         self.cache.iter(&self.shards, |shard| &mut shard.cache, f)
  97     }
  98     pub(super) fn all_inactive(&self) -> bool {
  99         let shards = self.shards.lock_shards();
 100         shards.iter().all(|shard| shard.active.is_empty())
 101     }
 102
 103     pub(super) fn try_collect_active_jobs(
 104         &self,
 105         kind: DepKind,
 106         make_query: fn(C::Key) -> CTX::Query,
 107         jobs: &mut FxHashMap<QueryJobId, QueryJobInfo<CTX>>,
 108     ) -> Option<()>
 109     where
 110         C::Key: Clone,
 111     {
 112         // We use try_lock_shards here since we are called from the
 113         // deadlock handler, and this shouldn't be locked.
 114         let shards = self.shards.try_lock_shards()?;
 115         let shards = shards.iter().enumerate();
 116         jobs.extend(shards.flat_map(|(shard_id, shard)| {
 117             shard.active.iter().filter_map(move |(k, v)| {
 118                 if let QueryResult::Started(ref job) = *v {
 119                     let id =
 120                         QueryJobId { job: job.id, shard: u16::try_from(shard_id).unwrap(), kind };
 121                     let info = QueryInfo { span: job.span, query: make_query(k.clone()) };
 122                     Some((id, QueryJobInfo { info, job: job.clone() }))
 123                 } else {
 124                     None
 125                 }
 126             })
 127         }));
 128
 129         Some(())
 130     }
 131 }
 132
 133 impl<CTX: QueryContext, C: QueryCache> Default for QueryState<CTX, C> {
 134     fn default() -> QueryState<CTX, C> {
 135         QueryState {
 136             cache: C::default(),
 137             shards: Default::default(),
 138             #[cfg(debug_assertions)]
 139             cache_hits: AtomicUsize::new(0),
 140         }
 141     }
 142 }
 143
 144 /// Values used when checking a query cache which can be reused on a cache-miss to execute the query.
 145 pub(crate) struct QueryLookup<'tcx, CTX: QueryContext, K, C> {
 146     pub(super) key_hash: u64,
 147     shard: usize,
 148     pub(super) lock: LockGuard<'tcx, QueryStateShard<CTX, K, C>>,
 149 }
 150
 151 /// A type representing the responsibility to execute the job in the `job` field.
 152 /// This will poison the relevant query if dropped.
 153 struct JobOwner<'tcx, CTX: QueryContext, C>
 154 where
 155     C: QueryCache,
 156     C::Key: Eq + Hash + Clone + Debug,
 157     C::Value: Clone,
 158 {
 159     state: &'tcx QueryState<CTX, C>,
 160     key: C::Key,
 161     id: QueryJobId,
 162 }
 163
 164 impl<'tcx, C: QueryCache> JobOwner<'tcx, TyCtxt<'tcx>, C>
 165 where
 166     C: QueryCache,
 167     C::Key: Eq + Hash + Clone + Debug,
 168     C::Value: Clone,
 169 {
 170     /// Either gets a `JobOwner` corresponding the query, allowing us to
 171     /// start executing the query, or returns with the result of the query.
 172     /// This function assumes that `try_get_cached` is already called and returned `lookup`.
 173     /// If the query is executing elsewhere, this will wait for it and return the result.
 174     /// If the query panicked, this will silently panic.
 175     ///
 176     /// This function is inlined because that results in a noticeable speed-up
 177     /// for some compile-time benchmarks.
 178     #[inline(always)]
 179     fn try_start<Q>(
 180         tcx: TyCtxt<'tcx>,
 181         span: Span,
 182         key: &C::Key,
 183         mut lookup: QueryLookup<'tcx, TyCtxt<'tcx>, C::Key, C::Sharded>,
 184     ) -> TryGetJob<'tcx, C>
 185     where
 186         Q: QueryDescription<TyCtxt<'tcx>, Key = C::Key, Value = C::Value, Cache = C>,
 187     {
 188         let lock = &mut *lookup.lock;
 189
 190         let (latch, mut _query_blocked_prof_timer) = match lock.active.entry((*key).clone()) {
 191             Entry::Occupied(mut entry) => {
 192                 match entry.get_mut() {
 193                     QueryResult::Started(job) => {
 194                         // For parallel queries, we'll block and wait until the query running
 195                         // in another thread has completed. Record how long we wait in the
 196                         // self-profiler.
 197                         let _query_blocked_prof_timer = if cfg!(parallel_compiler) {
 198                             Some(tcx.prof.query_blocked())
 199                         } else {
 200                             None
 201                         };
 202
 203                         // Create the id of the job we're waiting for
 204                         let id = QueryJobId::new(job.id, lookup.shard, Q::DEP_KIND);
 205
 206                         (job.latch(id), _query_blocked_prof_timer)
 207                     }
 208                     QueryResult::Poisoned => FatalError.raise(),
 209                 }
 210             }
 211             Entry::Vacant(entry) => {
 212                 // No job entry for this query. Return a new one to be started later.
 213
 214                 // Generate an id unique within this shard.
 215                 let id = lock.jobs.checked_add(1).unwrap();
 216                 lock.jobs = id;
 217                 let id = QueryShardJobId(NonZeroU32::new(id).unwrap());
 218
 219                 let global_id = QueryJobId::new(id, lookup.shard, Q::DEP_KIND);
 220
 221                 let job = tls::with_related_context(tcx, |icx| QueryJob::new(id, span, icx.query));
 222
 223                 entry.insert(QueryResult::Started(job));
 224
 225                 let owner =
 226                     JobOwner { state: Q::query_state(tcx), id: global_id, key: (*key).clone() };
 227                 return TryGetJob::NotYetStarted(owner);
 228             }
 229         };
 230         mem::drop(lookup.lock);
 231
 232         // If we are single-threaded we know that we have cycle error,
 233         // so we just return the error.
 234         #[cfg(not(parallel_compiler))]
 235         return TryGetJob::Cycle(cold_path(|| {
 236             Q::handle_cycle_error(tcx, latch.find_cycle_in_stack(tcx, span))
 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, span);
 244
 245             if let Err(cycle) = result {
 246                 return TryGetJob::Cycle(Q::handle_cycle_error(tcx, cycle));
 247             }
 248
 249             let cached = tcx.try_get_cached(
 250                 Q::query_state(tcx),
 251                 (*key).clone(),
 252                 |value, index| (value.clone(), index),
 253                 |_, _| panic!("value must be in cache after waiting"),
 254             );
 255
 256             if let Some(prof_timer) = _query_blocked_prof_timer.take() {
 257                 prof_timer.finish_with_query_invocation_id(cached.1.into());
 258             }
 259
 260             return TryGetJob::JobCompleted(cached);
 261         }
 262     }
 263 }
 264
 265 impl<'tcx, CTX: QueryContext, C: QueryCache> JobOwner<'tcx, CTX, C>
 266 where
 267     C: QueryCache,
 268     C::Key: Eq + Hash + Clone + Debug,
 269     C::Value: Clone,
 270 {
 271     /// Completes the query by updating the query cache with the `result`,
 272     /// signals the waiter and forgets the JobOwner, so it won't poison the query
 273     #[inline(always)]
 274     fn complete(self, tcx: TyCtxt<'tcx>, result: &C::Value, dep_node_index: DepNodeIndex) {
 275         // We can move out of `self` here because we `mem::forget` it below
 276         let key = unsafe { ptr::read(&self.key) };
 277         let state = self.state;
 278
 279         // Forget ourself so our destructor won't poison the query
 280         mem::forget(self);
 281
 282         let job = {
 283             let result = result.clone();
 284             let mut lock = state.shards.get_shard_by_value(&key).lock();
 285             let job = match lock.active.remove(&key).unwrap() {
 286                 QueryResult::Started(job) => job,
 287                 QueryResult::Poisoned => panic!(),
 288             };
 289             state.cache.complete(tcx, &mut lock.cache, key, result, dep_node_index);
 290             job
 291         };
 292
 293         job.signal_complete();
 294     }
 295 }
 296
 297 #[inline(always)]
 298 fn with_diagnostics<F, R>(f: F) -> (R, ThinVec<Diagnostic>)
 299 where
 300     F: FnOnce(Option<&Lock<ThinVec<Diagnostic>>>) -> R,
 301 {
 302     let diagnostics = Lock::new(ThinVec::new());
 303     let result = f(Some(&diagnostics));
 304     (result, diagnostics.into_inner())
 305 }
 306
 307 impl<'tcx, CTX: QueryContext, C: QueryCache> Drop for JobOwner<'tcx, CTX, C>
 308 where
 309     C::Key: Eq + Hash + Clone + Debug,
 310     C::Value: Clone,
 311 {
 312     #[inline(never)]
 313     #[cold]
 314     fn drop(&mut self) {
 315         // Poison the query so jobs waiting on it panic.
 316         let state = self.state;
 317         let shard = state.shards.get_shard_by_value(&self.key);
 318         let job = {
 319             let mut shard = shard.lock();
 320             let job = match shard.active.remove(&self.key).unwrap() {
 321                 QueryResult::Started(job) => job,
 322                 QueryResult::Poisoned => panic!(),
 323             };
 324             shard.active.insert(self.key.clone(), QueryResult::Poisoned);
 325             job
 326         };
 327         // Also signal the completion of the job, so waiters
 328         // will continue execution.
 329         job.signal_complete();
 330     }
 331 }
 332
 333 #[derive(Clone)]
 334 pub(crate) struct CycleError<CTX: QueryContext> {
 335     /// The query and related span that uses the cycle.
 336     pub(super) usage: Option<(Span, CTX::Query)>,
 337     pub(super) cycle: Vec<QueryInfo<CTX>>,
 338 }
 339
 340 /// The result of `try_start`.
 341 enum TryGetJob<'tcx, C: QueryCache>
 342 where
 343     C::Key: Eq + Hash + Clone + Debug,
 344     C::Value: Clone,
 345 {
 346     /// The query is not yet started. Contains a guard to the cache eventually used to start it.
 347     NotYetStarted(JobOwner<'tcx, TyCtxt<'tcx>, C>),
 348
 349     /// The query was already completed.
 350     /// Returns the result of the query and its dep-node index
 351     /// if it succeeded or a cycle error if it failed.
 352     #[cfg(parallel_compiler)]
 353     JobCompleted((C::Value, DepNodeIndex)),
 354
 355     /// Trying to execute the query resulted in a cycle.
 356     Cycle(C::Value),
 357 }
 358
 359 impl QueryContext for TyCtxt<'tcx> {
 360     type Query = Query<'tcx>;
 361
 362     fn session(&self) -> &Session {
 363         &self.sess
 364     }
 365
 366     fn def_path_str(&self, def_id: DefId) -> String {
 367         TyCtxt::def_path_str(*self, def_id)
 368     }
 369 }
 370
 371 impl<'tcx> TyCtxt<'tcx> {
 372     /// Executes a job by changing the `ImplicitCtxt` to point to the
 373     /// new query job while it executes. It returns the diagnostics
 374     /// captured during execution and the actual result.
 375     #[inline(always)]
 376     fn start_query<F, R>(
 377         self,
 378         token: QueryJobId,
 379         diagnostics: Option<&Lock<ThinVec<Diagnostic>>>,
 380         compute: F,
 381     ) -> R
 382     where
 383         F: FnOnce(TyCtxt<'tcx>) -> R,
 384     {
 385         // The `TyCtxt` stored in TLS has the same global interner lifetime
 386         // as `self`, so we use `with_related_context` to relate the 'tcx lifetimes
 387         // when accessing the `ImplicitCtxt`.
 388         tls::with_related_context(self, move |current_icx| {
 389             // Update the `ImplicitCtxt` to point to our new query job.
 390             let new_icx = tls::ImplicitCtxt {
 391                 tcx: self,
 392                 query: Some(token),
 393                 diagnostics,
 394                 layout_depth: current_icx.layout_depth,
 395                 task_deps: current_icx.task_deps,
 396             };
 397
 398             // Use the `ImplicitCtxt` while we execute the query.
 399             tls::enter_context(&new_icx, |_| compute(self))
 400         })
 401     }
 402
 403     #[inline(never)]
 404     #[cold]
 405     pub(super) fn report_cycle(
 406         self,
 407         CycleError { usage, cycle: stack }: CycleError<TyCtxt<'tcx>>,
 408     ) -> DiagnosticBuilder<'tcx> {
 409         assert!(!stack.is_empty());
 410
 411         let fix_span = |span: Span, query: &Query<'tcx>| {
 412             self.sess.source_map().guess_head_span(query.default_span(self, span))
 413         };
 414
 415         // Disable naming impls with types in this path, since that
 416         // sometimes cycles itself, leading to extra cycle errors.
 417         // (And cycle errors around impls tend to occur during the
 418         // collect/coherence phases anyhow.)
 419         ty::print::with_forced_impl_filename_line(|| {
 420             let span = fix_span(stack[1 % stack.len()].span, &stack[0].query);
 421             let mut err = struct_span_err!(
 422                 self.sess,
 423                 span,
 424                 E0391,
 425                 "cycle detected when {}",
 426                 stack[0].query.describe(self)
 427             );
 428
 429             for i in 1..stack.len() {
 430                 let query = &stack[i].query;
 431                 let span = fix_span(stack[(i + 1) % stack.len()].span, query);
 432                 err.span_note(span, &format!("...which requires {}...", query.describe(self)));
 433             }
 434
 435             err.note(&format!(
 436                 "...which again requires {}, completing the cycle",
 437                 stack[0].query.describe(self)
 438             ));
 439
 440             if let Some((span, query)) = usage {
 441                 err.span_note(
 442                     fix_span(span, &query),
 443                     &format!("cycle used when {}", query.describe(self)),
 444                 );
 445             }
 446
 447             err
 448         })
 449     }
 450
 451     pub fn try_print_query_stack(handler: &Handler) {
 452         eprintln!("query stack during panic:");
 453
 454         // Be careful reyling on global state here: this code is called from
 455         // a panic hook, which means that the global `Handler` may be in a weird
 456         // state if it was responsible for triggering the panic.
 457         tls::with_context_opt(|icx| {
 458             if let Some(icx) = icx {
 459                 let query_map = icx.tcx.queries.try_collect_active_jobs();
 460
 461                 let mut current_query = icx.query;
 462                 let mut i = 0;
 463
 464                 while let Some(query) = current_query {
 465                     let query_info =
 466                         if let Some(info) = query_map.as_ref().and_then(|map| map.get(&query)) {
 467                             info
 468                         } else {
 469                             break;
 470                         };
 471                     let mut diag = Diagnostic::new(
 472                         Level::FailureNote,
 473                         &format!(
 474                             "#{} [{}] {}",
 475                             i,
 476                             query_info.info.query.name(),
 477                             query_info.info.query.describe(icx.tcx)
 478                         ),
 479                     );
 480                     diag.span =
 481                         icx.tcx.sess.source_map().guess_head_span(query_info.info.span).into();
 482                     handler.force_print_diagnostic(diag);
 483
 484                     current_query = query_info.job.parent;
 485                     i += 1;
 486                 }
 487             }
 488         });
 489
 490         eprintln!("end of query stack");
 491     }
 492
 493     /// Checks if the query is already computed and in the cache.
 494     /// It returns the shard index and a lock guard to the shard,
 495     /// which will be used if the query is not in the cache and we need
 496     /// to compute it.
 497     #[inline(always)]
 498     fn try_get_cached<C, R, OnHit, OnMiss>(
 499         self,
 500         state: &'tcx QueryState<TyCtxt<'tcx>, C>,
 501         key: C::Key,
 502         // `on_hit` can be called while holding a lock to the query cache
 503         on_hit: OnHit,
 504         on_miss: OnMiss,
 505     ) -> R
 506     where
 507         C: QueryCache,
 508         OnHit: FnOnce(&C::Value, DepNodeIndex) -> R,
 509         OnMiss: FnOnce(C::Key, QueryLookup<'tcx, TyCtxt<'tcx>, C::Key, C::Sharded>) -> R,
 510     {
 511         state.cache.lookup(
 512             state,
 513             QueryStateShard::<TyCtxt<'tcx>, C::Key, C::Sharded>::get_cache,
 514             key,
 515             |value, index| {
 516                 if unlikely!(self.prof.enabled()) {
 517                     self.prof.query_cache_hit(index.into());
 518                 }
 519                 #[cfg(debug_assertions)]
 520                 {
 521                     state.cache_hits.fetch_add(1, Ordering::Relaxed);
 522                 }
 523                 on_hit(value, index)
 524             },
 525             on_miss,
 526         )
 527     }
 528
 529     #[inline(never)]
 530     pub(super) fn get_query<Q: QueryDescription<TyCtxt<'tcx>> + 'tcx>(
 531         self,
 532         span: Span,
 533         key: Q::Key,
 534     ) -> Q::Value {
 535         debug!("ty::query::get_query<{}>(key={:?}, span={:?})", Q::NAME, key, span);
 536
 537         self.try_get_cached(
 538             Q::query_state(self),
 539             key,
 540             |value, index| {
 541                 self.dep_graph.read_index(index);
 542                 value.clone()
 543             },
 544             |key, lookup| self.try_execute_query::<Q>(span, key, lookup),
 545         )
 546     }
 547
 548     #[inline(always)]
 549     fn try_execute_query<Q: QueryDescription<TyCtxt<'tcx>> + 'tcx>(
 550         self,
 551         span: Span,
 552         key: Q::Key,
 553         lookup: QueryLookup<'tcx, TyCtxt<'tcx>, Q::Key, <Q::Cache as QueryCache>::Sharded>,
 554     ) -> Q::Value {
 555         let job = match JobOwner::try_start::<Q>(self, span, &key, lookup) {
 556             TryGetJob::NotYetStarted(job) => job,
 557             TryGetJob::Cycle(result) => return result,
 558             #[cfg(parallel_compiler)]
 559             TryGetJob::JobCompleted((v, index)) => {
 560                 self.dep_graph.read_index(index);
 561                 return v;
 562             }
 563         };
 564
 565         // Fast path for when incr. comp. is off. `to_dep_node` is
 566         // expensive for some `DepKind`s.
 567         if !self.dep_graph.is_fully_enabled() {
 568             let null_dep_node = DepNode::new_no_params(crate::dep_graph::DepKind::Null);
 569             return self.force_query_with_job::<Q>(key, job, null_dep_node).0;
 570         }
 571
 572         if Q::ANON {
 573             let prof_timer = self.prof.query_provider();
 574
 575             let ((result, dep_node_index), diagnostics) = with_diagnostics(|diagnostics| {
 576                 self.start_query(job.id, diagnostics, |tcx| {
 577                     tcx.dep_graph.with_anon_task(Q::DEP_KIND, || Q::compute(tcx, key))
 578                 })
 579             });
 580
 581             prof_timer.finish_with_query_invocation_id(dep_node_index.into());
 582
 583             self.dep_graph.read_index(dep_node_index);
 584
 585             if unlikely!(!diagnostics.is_empty()) {
 586                 self.queries
 587                     .on_disk_cache
 588                     .store_diagnostics_for_anon_node(dep_node_index, diagnostics);
 589             }
 590
 591             job.complete(self, &result, dep_node_index);
 592
 593             return result;
 594         }
 595
 596         let dep_node = Q::to_dep_node(self, &key);
 597
 598         if !Q::EVAL_ALWAYS {
 599             // The diagnostics for this query will be
 600             // promoted to the current session during
 601             // `try_mark_green()`, so we can ignore them here.
 602             let loaded = self.start_query(job.id, None, |tcx| {
 603                 let marked = tcx.dep_graph.try_mark_green_and_read(tcx, &dep_node);
 604                 marked.map(|(prev_dep_node_index, dep_node_index)| {
 605                     (
 606                         tcx.load_from_disk_and_cache_in_memory::<Q>(
 607                             key.clone(),
 608                             prev_dep_node_index,
 609                             dep_node_index,
 610                             &dep_node,
 611                         ),
 612                         dep_node_index,
 613                     )
 614                 })
 615             });
 616             if let Some((result, dep_node_index)) = loaded {
 617                 job.complete(self, &result, dep_node_index);
 618                 return result;
 619             }
 620         }
 621
 622         let (result, dep_node_index) = self.force_query_with_job::<Q>(key, job, dep_node);
 623         self.dep_graph.read_index(dep_node_index);
 624         result
 625     }
 626
 627     fn load_from_disk_and_cache_in_memory<Q: QueryDescription<TyCtxt<'tcx>>>(
 628         self,
 629         key: Q::Key,
 630         prev_dep_node_index: SerializedDepNodeIndex,
 631         dep_node_index: DepNodeIndex,
 632         dep_node: &DepNode,
 633     ) -> Q::Value {
 634         // Note this function can be called concurrently from the same query
 635         // We must ensure that this is handled correctly.
 636
 637         debug_assert!(self.dep_graph.is_green(dep_node));
 638
 639         // First we try to load the result from the on-disk cache.
 640         let result = if Q::cache_on_disk(self, key.clone(), None) {
 641             let prof_timer = self.prof.incr_cache_loading();
 642             let result = Q::try_load_from_disk(self, prev_dep_node_index);
 643             prof_timer.finish_with_query_invocation_id(dep_node_index.into());
 644
 645             // We always expect to find a cached result for things that
 646             // can be forced from `DepNode`.
 647             debug_assert!(
 648                 !dep_node.kind.can_reconstruct_query_key() || result.is_some(),
 649                 "missing on-disk cache entry for {:?}",
 650                 dep_node
 651             );
 652             result
 653         } else {
 654             // Some things are never cached on disk.
 655             None
 656         };
 657
 658         let result = if let Some(result) = result {
 659             result
 660         } else {
 661             // We could not load a result from the on-disk cache, so
 662             // recompute.
 663             let prof_timer = self.prof.query_provider();
 664
 665             // The dep-graph for this computation is already in-place.
 666             let result = self.dep_graph.with_ignore(|| Q::compute(self, key));
 667
 668             prof_timer.finish_with_query_invocation_id(dep_node_index.into());
 669
 670             result
 671         };
 672
 673         // If `-Zincremental-verify-ich` is specified, re-hash results from
 674         // the cache and make sure that they have the expected fingerprint.
 675         if unlikely!(self.sess.opts.debugging_opts.incremental_verify_ich) {
 676             self.incremental_verify_ich::<Q>(&result, dep_node, dep_node_index);
 677         }
 678
 679         result
 680     }
 681
 682     #[inline(never)]
 683     #[cold]
 684     fn incremental_verify_ich<Q: QueryDescription<TyCtxt<'tcx>>>(
 685         self,
 686         result: &Q::Value,
 687         dep_node: &DepNode,
 688         dep_node_index: DepNodeIndex,
 689     ) {
 690         use rustc_data_structures::fingerprint::Fingerprint;
 691
 692         assert!(
 693             Some(self.dep_graph.fingerprint_of(dep_node_index))
 694                 == self.dep_graph.prev_fingerprint_of(dep_node),
 695             "fingerprint for green query instance not loaded from cache: {:?}",
 696             dep_node,
 697         );
 698
 699         debug!("BEGIN verify_ich({:?})", dep_node);
 700         let mut hcx = self.create_stable_hashing_context();
 701
 702         let new_hash = Q::hash_result(&mut hcx, result).unwrap_or(Fingerprint::ZERO);
 703         debug!("END verify_ich({:?})", dep_node);
 704
 705         let old_hash = self.dep_graph.fingerprint_of(dep_node_index);
 706
 707         assert!(new_hash == old_hash, "found unstable fingerprints for {:?}", dep_node,);
 708     }
 709
 710     #[inline(always)]
 711     fn force_query_with_job<Q: QueryDescription<TyCtxt<'tcx>> + 'tcx>(
 712         self,
 713         key: Q::Key,
 714         job: JobOwner<'tcx, TyCtxt<'tcx>, Q::Cache>,
 715         dep_node: DepNode,
 716     ) -> (Q::Value, DepNodeIndex) {
 717         // If the following assertion triggers, it can have two reasons:
 718         // 1. Something is wrong with DepNode creation, either here or
 719         //    in `DepGraph::try_mark_green()`.
 720         // 2. Two distinct query keys get mapped to the same `DepNode`
 721         //    (see for example #48923).
 722         assert!(
 723             !self.dep_graph.dep_node_exists(&dep_node),
 724             "forcing query with already existing `DepNode`\n\
 725                  - query-key: {:?}\n\
 726                  - dep-node: {:?}",
 727             key,
 728             dep_node
 729         );
 730
 731         let prof_timer = self.prof.query_provider();
 732
 733         let ((result, dep_node_index), diagnostics) = with_diagnostics(|diagnostics| {
 734             self.start_query(job.id, diagnostics, |tcx| {
 735                 if Q::EVAL_ALWAYS {
 736                     tcx.dep_graph.with_eval_always_task(
 737                         dep_node,
 738                         tcx,
 739                         key,
 740                         Q::compute,
 741                         Q::hash_result,
 742                     )
 743                 } else {
 744                     tcx.dep_graph.with_task(dep_node, tcx, key, Q::compute, Q::hash_result)
 745                 }
 746             })
 747         });
 748
 749         prof_timer.finish_with_query_invocation_id(dep_node_index.into());
 750
 751         if unlikely!(!diagnostics.is_empty()) {
 752             if dep_node.kind != crate::dep_graph::DepKind::Null {
 753                 self.queries.on_disk_cache.store_diagnostics(dep_node_index, diagnostics);
 754             }
 755         }
 756
 757         job.complete(self, &result, dep_node_index);
 758
 759         (result, dep_node_index)
 760     }
 761
 762     /// Ensure that either this query has all green inputs or been executed.
 763     /// Executing `query::ensure(D)` is considered a read of the dep-node `D`.
 764     ///
 765     /// This function is particularly useful when executing passes for their
 766     /// side-effects -- e.g., in order to report errors for erroneous programs.
 767     ///
 768     /// Note: The optimization is only available during incr. comp.
 769     pub(super) fn ensure_query<Q: QueryDescription<TyCtxt<'tcx>> + 'tcx>(self, key: Q::Key) {
 770         if Q::EVAL_ALWAYS {
 771             let _ = self.get_query::<Q>(DUMMY_SP, key);
 772             return;
 773         }
 774
 775         // Ensuring an anonymous query makes no sense
 776         assert!(!Q::ANON);
 777
 778         let dep_node = Q::to_dep_node(self, &key);
 779
 780         match self.dep_graph.try_mark_green_and_read(self, &dep_node) {
 781             None => {
 782                 // A None return from `try_mark_green_and_read` means that this is either
 783                 // a new dep node or that the dep node has already been marked red.
 784                 // Either way, we can't call `dep_graph.read()` as we don't have the
 785                 // DepNodeIndex. We must invoke the query itself. The performance cost
 786                 // this introduces should be negligible as we'll immediately hit the
 787                 // in-memory cache, or another query down the line will.
 788                 let _ = self.get_query::<Q>(DUMMY_SP, key);
 789             }
 790             Some((_, dep_node_index)) => {
 791                 self.prof.query_cache_hit(dep_node_index.into());
 792             }
 793         }
 794     }
 795
 796     #[allow(dead_code)]
 797     pub(super) fn force_query<Q: QueryDescription<TyCtxt<'tcx>> + 'tcx>(
 798         self,
 799         key: Q::Key,
 800         span: Span,
 801         dep_node: DepNode,
 802     ) {
 803         // We may be concurrently trying both execute and force a query.
 804         // Ensure that only one of them runs the query.
 805
 806         self.try_get_cached(
 807             Q::query_state(self),
 808             key,
 809             |_, _| {
 810                 // Cache hit, do nothing
 811             },
 812             |key, lookup| {
 813                 let job = match JobOwner::try_start::<Q>(self, span, &key, lookup) {
 814                     TryGetJob::NotYetStarted(job) => job,
 815                     TryGetJob::Cycle(_) => return,
 816                     #[cfg(parallel_compiler)]
 817                     TryGetJob::JobCompleted(_) => return,
 818                 };
 819                 self.force_query_with_job::<Q>(key, job, dep_node);
 820             },
 821         );
 822     }
 823 }
 824
 825 macro_rules! handle_cycle_error {
 826     ([][$tcx: expr, $error:expr]) => {{
 827         $tcx.report_cycle($error).emit();
 828         Value::from_cycle_error($tcx)
 829     }};
 830     ([fatal_cycle $($rest:tt)*][$tcx:expr, $error:expr]) => {{
 831         $tcx.report_cycle($error).emit();
 832         $tcx.sess.abort_if_errors();
 833         unreachable!()
 834     }};
 835     ([cycle_delay_bug $($rest:tt)*][$tcx:expr, $error:expr]) => {{
 836         $tcx.report_cycle($error).delay_as_bug();
 837         Value::from_cycle_error($tcx)
 838     }};
 839     ([$other:ident $(($($other_args:tt)*))* $(, $($modifiers:tt)*)*][$($args:tt)*]) => {
 840         handle_cycle_error!([$($($modifiers)*)*][$($args)*])
 841     };
 842 }
 843
 844 macro_rules! is_anon {
 845     ([]) => {{
 846         false
 847     }};
 848     ([anon $($rest:tt)*]) => {{
 849         true
 850     }};
 851     ([$other:ident $(($($other_args:tt)*))* $(, $($modifiers:tt)*)*]) => {
 852         is_anon!([$($($modifiers)*)*])
 853     };
 854 }
 855
 856 macro_rules! is_eval_always {
 857     ([]) => {{
 858         false
 859     }};
 860     ([eval_always $($rest:tt)*]) => {{
 861         true
 862     }};
 863     ([$other:ident $(($($other_args:tt)*))* $(, $($modifiers:tt)*)*]) => {
 864         is_eval_always!([$($($modifiers)*)*])
 865     };
 866 }
 867
 868 macro_rules! query_storage {
 869     ([][$K:ty, $V:ty]) => {
 870         <<$K as Key>::CacheSelector as CacheSelector<$K, $V>>::Cache
 871     };
 872     ([storage($ty:ty) $($rest:tt)*][$K:ty, $V:ty]) => {
 873         $ty
 874     };
 875     ([$other:ident $(($($other_args:tt)*))* $(, $($modifiers:tt)*)*][$($args:tt)*]) => {
 876         query_storage!([$($($modifiers)*)*][$($args)*])
 877     };
 878 }
 879
 880 macro_rules! hash_result {
 881     ([][$hcx:expr, $result:expr]) => {{
 882         dep_graph::hash_result($hcx, &$result)
 883     }};
 884     ([no_hash $($rest:tt)*][$hcx:expr, $result:expr]) => {{
 885         None
 886     }};
 887     ([$other:ident $(($($other_args:tt)*))* $(, $($modifiers:tt)*)*][$($args:tt)*]) => {
 888         hash_result!([$($($modifiers)*)*][$($args)*])
 889     };
 890 }
 891
 892 macro_rules! define_queries {
 893     (<$tcx:tt> $($category:tt {
 894         $($(#[$attr:meta])* [$($modifiers:tt)*] fn $name:ident: $node:ident($K:ty) -> $V:ty,)*
 895     },)*) => {
 896         define_queries_inner! { <$tcx>
 897             $($( $(#[$attr])* category<$category> [$($modifiers)*] fn $name: $node($K) -> $V,)*)*
 898         }
 899     }
 900 }
 901
 902 macro_rules! define_queries_inner {
 903     (<$tcx:tt>
 904      $($(#[$attr:meta])* category<$category:tt>
 905         [$($modifiers:tt)*] fn $name:ident: $node:ident($K:ty) -> $V:ty,)*) => {
 906
 907         use std::mem;
 908         use crate::{
 909             rustc_data_structures::stable_hasher::HashStable,
 910             rustc_data_structures::stable_hasher::StableHasher,
 911             ich::StableHashingContext
 912         };
 913         use rustc_data_structures::profiling::ProfileCategory;
 914
 915         define_queries_struct! {
 916             tcx: $tcx,
 917             input: ($(([$($modifiers)*] [$($attr)*] [$name]))*)
 918         }
 919
 920         #[allow(nonstandard_style)]
 921         #[derive(Clone, Debug)]
 922         pub enum Query<$tcx> {
 923             $($(#[$attr])* $name($K)),*
 924         }
 925
 926         impl<$tcx> Query<$tcx> {
 927             pub fn name(&self) -> &'static str {
 928                 match *self {
 929                     $(Query::$name(_) => stringify!($name),)*
 930                 }
 931             }
 932
 933             pub fn describe(&self, tcx: TyCtxt<$tcx>) -> Cow<'static, str> {
 934                 let (r, name) = match *self {
 935                     $(Query::$name(key) => {
 936                         (queries::$name::describe(tcx, key), stringify!($name))
 937                     })*
 938                 };
 939                 if tcx.sess.verbose() {
 940                     format!("{} [{}]", r, name).into()
 941                 } else {
 942                     r
 943                 }
 944             }
 945
 946             // FIXME(eddyb) Get more valid `Span`s on queries.
 947             pub fn default_span(&self, tcx: TyCtxt<$tcx>, span: Span) -> Span {
 948                 if !span.is_dummy() {
 949                     return span;
 950                 }
 951                 // The `def_span` query is used to calculate `default_span`,
 952                 // so exit to avoid infinite recursion.
 953                 if let Query::def_span(..) = *self {
 954                     return span
 955                 }
 956                 match *self {
 957                     $(Query::$name(key) => key.default_span(tcx),)*
 958                 }
 959             }
 960         }
 961
 962         impl<'a, $tcx> HashStable<StableHashingContext<'a>> for Query<$tcx> {
 963             fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
 964                 mem::discriminant(self).hash_stable(hcx, hasher);
 965                 match *self {
 966                     $(Query::$name(key) => key.hash_stable(hcx, hasher),)*
 967                 }
 968             }
 969         }
 970
 971         pub mod queries {
 972             use std::marker::PhantomData;
 973
 974             $(#[allow(nonstandard_style)]
 975             pub struct $name<$tcx> {
 976                 data: PhantomData<&$tcx ()>
 977             })*
 978         }
 979
 980         $(impl<$tcx> QueryConfig<TyCtxt<$tcx>> for queries::$name<$tcx> {
 981             type Key = $K;
 982             type Value = $V;
 983             const NAME: &'static str = stringify!($name);
 984             const CATEGORY: ProfileCategory = $category;
 985         }
 986
 987         impl<$tcx> QueryAccessors<TyCtxt<$tcx>> for queries::$name<$tcx> {
 988             const ANON: bool = is_anon!([$($modifiers)*]);
 989             const EVAL_ALWAYS: bool = is_eval_always!([$($modifiers)*]);
 990             const DEP_KIND: dep_graph::DepKind = dep_graph::DepKind::$node;
 991
 992             type Cache = query_storage!([$($modifiers)*][$K, $V]);
 993
 994             #[inline(always)]
 995             fn query_state<'a>(tcx: TyCtxt<$tcx>) -> &'a QueryState<TyCtxt<$tcx>, Self::Cache> {
 996                 &tcx.queries.$name
 997             }
 998
 999             #[allow(unused)]
1000             #[inline(always)]
1001             fn to_dep_node(tcx: TyCtxt<$tcx>, key: &Self::Key) -> DepNode {
1002                 DepConstructor::$node(tcx, *key)
1003             }
1004
1005             #[inline]
1006             fn compute(tcx: TyCtxt<'tcx>, key: Self::Key) -> Self::Value {
1007                 let provider = tcx.queries.providers.get(key.query_crate())
1008                     // HACK(eddyb) it's possible crates may be loaded after
1009                     // the query engine is created, and because crate loading
1010                     // is not yet integrated with the query engine, such crates
1011                     // would be missing appropriate entries in `providers`.
1012                     .unwrap_or(&tcx.queries.fallback_extern_providers)
1013                     .$name;
1014                 provider(tcx, key)
1015             }
1016
1017             fn hash_result(
1018                 _hcx: &mut StableHashingContext<'_>,
1019                 _result: &Self::Value
1020             ) -> Option<Fingerprint> {
1021                 hash_result!([$($modifiers)*][_hcx, _result])
1022             }
1023
1024             fn handle_cycle_error(
1025                 tcx: TyCtxt<'tcx>,
1026                 error: CycleError<TyCtxt<'tcx>>
1027             ) -> Self::Value {
1028                 handle_cycle_error!([$($modifiers)*][tcx, error])
1029             }
1030         })*
1031
1032         #[derive(Copy, Clone)]
1033         pub struct TyCtxtEnsure<'tcx> {
1034             pub tcx: TyCtxt<'tcx>,
1035         }
1036
1037         impl TyCtxtEnsure<$tcx> {
1038             $($(#[$attr])*
1039             #[inline(always)]
1040             pub fn $name(self, key: $K) {
1041                 self.tcx.ensure_query::<queries::$name<'_>>(key)
1042             })*
1043         }
1044
1045         #[derive(Copy, Clone)]
1046         pub struct TyCtxtAt<'tcx> {
1047             pub tcx: TyCtxt<'tcx>,
1048             pub span: Span,
1049         }
1050
1051         impl Deref for TyCtxtAt<'tcx> {
1052             type Target = TyCtxt<'tcx>;
1053             #[inline(always)]
1054             fn deref(&self) -> &Self::Target {
1055                 &self.tcx
1056             }
1057         }
1058
1059         impl TyCtxt<$tcx> {
1060             /// Returns a transparent wrapper for `TyCtxt`, which ensures queries
1061             /// are executed instead of just returning their results.
1062             #[inline(always)]
1063             pub fn ensure(self) -> TyCtxtEnsure<$tcx> {
1064                 TyCtxtEnsure {
1065                     tcx: self,
1066                 }
1067             }
1068
1069             /// Returns a transparent wrapper for `TyCtxt` which uses
1070             /// `span` as the location of queries performed through it.
1071             #[inline(always)]
1072             pub fn at(self, span: Span) -> TyCtxtAt<$tcx> {
1073                 TyCtxtAt {
1074                     tcx: self,
1075                     span
1076                 }
1077             }
1078
1079             $($(#[$attr])*
1080             #[inline(always)]
1081             pub fn $name(self, key: $K) -> $V {
1082                 self.at(DUMMY_SP).$name(key)
1083             })*
1084
1085             /// All self-profiling events generated by the query engine use
1086             /// virtual `StringId`s for their `event_id`. This method makes all
1087             /// those virtual `StringId`s point to actual strings.
1088             ///
1089             /// If we are recording only summary data, the ids will point to
1090             /// just the query names. If we are recording query keys too, we
1091             /// allocate the corresponding strings here.
1092             pub fn alloc_self_profile_query_strings(self) {
1093                 use crate::ty::query::profiling_support::{
1094                     alloc_self_profile_query_strings_for_query_cache,
1095                     QueryKeyStringCache,
1096                 };
1097
1098                 if !self.prof.enabled() {
1099                     return;
1100                 }
1101
1102                 let mut string_cache = QueryKeyStringCache::new();
1103
1104                 $({
1105                     alloc_self_profile_query_strings_for_query_cache(
1106                         self,
1107                         stringify!($name),
1108                         &self.queries.$name,
1109                         &mut string_cache,
1110                     );
1111                 })*
1112             }
1113         }
1114
1115         impl TyCtxtAt<$tcx> {
1116             $($(#[$attr])*
1117             #[inline(always)]
1118             pub fn $name(self, key: $K) -> $V {
1119                 self.tcx.get_query::<queries::$name<'_>>(self.span, key)
1120             })*
1121         }
1122
1123         define_provider_struct! {
1124             tcx: $tcx,
1125             input: ($(([$($modifiers)*] [$name] [$K] [$V]))*)
1126         }
1127
1128         impl<$tcx> Copy for Providers<$tcx> {}
1129         impl<$tcx> Clone for Providers<$tcx> {
1130             fn clone(&self) -> Self { *self }
1131         }
1132     }
1133 }
1134
1135 macro_rules! define_queries_struct {
1136     (tcx: $tcx:tt,
1137      input: ($(([$($modifiers:tt)*] [$($attr:tt)*] [$name:ident]))*)) => {
1138         pub struct Queries<$tcx> {
1139             /// This provides access to the incrimental comilation on-disk cache for query results.
1140             /// Do not access this directly. It is only meant to be used by
1141             /// `DepGraph::try_mark_green()` and the query infrastructure.
1142             pub(crate) on_disk_cache: OnDiskCache<'tcx>,
1143
1144             providers: IndexVec<CrateNum, Providers<$tcx>>,
1145             fallback_extern_providers: Box<Providers<$tcx>>,
1146
1147             $($(#[$attr])*  $name: QueryState<
1148                 TyCtxt<$tcx>,
1149                 <queries::$name<$tcx> as QueryAccessors<TyCtxt<'tcx>>>::Cache,
1150             >,)*
1151         }
1152
1153         impl<$tcx> Queries<$tcx> {
1154             pub(crate) fn new(
1155                 providers: IndexVec<CrateNum, Providers<$tcx>>,
1156                 fallback_extern_providers: Providers<$tcx>,
1157                 on_disk_cache: OnDiskCache<'tcx>,
1158             ) -> Self {
1159                 Queries {
1160                     providers,
1161                     fallback_extern_providers: Box::new(fallback_extern_providers),
1162                     on_disk_cache,
1163                     $($name: Default::default()),*
1164                 }
1165             }
1166
1167             pub(crate) fn try_collect_active_jobs(
1168                 &self
1169             ) -> Option<FxHashMap<QueryJobId, QueryJobInfo<TyCtxt<'tcx>>>> {
1170                 let mut jobs = FxHashMap::default();
1171
1172                 $(
1173                     self.$name.try_collect_active_jobs(
1174                         <queries::$name<'tcx> as QueryAccessors<TyCtxt<'tcx>>>::DEP_KIND,
1175                         Query::$name,
1176                         &mut jobs,
1177                     )?;
1178                 )*
1179
1180                 Some(jobs)
1181             }
1182         }
1183     };
1184 }
1185
1186 macro_rules! define_provider_struct {
1187     (tcx: $tcx:tt,
1188      input: ($(([$($modifiers:tt)*] [$name:ident] [$K:ty] [$R:ty]))*)) => {
1189         pub struct Providers<$tcx> {
1190             $(pub $name: fn(TyCtxt<$tcx>, $K) -> $R,)*
1191         }
1192
1193         impl<$tcx> Default for Providers<$tcx> {
1194             fn default() -> Self {
1195                 $(fn $name<$tcx>(_: TyCtxt<$tcx>, key: $K) -> $R {
1196                     bug!("`tcx.{}({:?})` unsupported by its crate",
1197                          stringify!($name), key);
1198                 })*
1199                 Providers { $($name),* }
1200             }
1201         }
1202     };
1203 }