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<CTX>> {
  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<CTX>> 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<CTX>> 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<CTX>> 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<CTX>,
 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> JobOwner<'tcx, TyCtxt<'tcx>, C>
 165 where
 166     C: QueryCache<TyCtxt<'tcx>> + 'tcx,
 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<'a, 'b, Q>(
 180         tcx: TyCtxt<'tcx>,
 181         span: Span,
 182         key: &C::Key,
 183         mut lookup: QueryLookup<'a, TyCtxt<'tcx>, C::Key, C::Sharded>,
 184     ) -> TryGetJob<'b, TyCtxt<'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> JobOwner<'tcx, CTX, C>
 266 where
 267     C: QueryCache<CTX>,
 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: CTX, 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<CTX>> 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, CTX: QueryContext, C: QueryCache<CTX>>
 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, CTX, 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<TyCtxt<'tcx>>,
 508         OnHit: FnOnce(&C::Value, DepNodeIndex) -> R,
 509         OnMiss: FnOnce(C::Key, QueryLookup<'_, 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<
 554             '_,
 555             TyCtxt<'tcx>,
 556             Q::Key,
 557             <Q::Cache as QueryCache<TyCtxt<'tcx>>>::Sharded,
 558         >,
 559     ) -> Q::Value {
 560         let job = match JobOwner::try_start::<Q>(self, span, &key, lookup) {
 561             TryGetJob::NotYetStarted(job) => job,
 562             TryGetJob::Cycle(result) => return result,
 563             #[cfg(parallel_compiler)]
 564             TryGetJob::JobCompleted((v, index)) => {
 565                 self.dep_graph.read_index(index);
 566                 return v;
 567             }
 568         };
 569
 570         // Fast path for when incr. comp. is off. `to_dep_node` is
 571         // expensive for some `DepKind`s.
 572         if !self.dep_graph.is_fully_enabled() {
 573             let null_dep_node = DepNode::new_no_params(crate::dep_graph::DepKind::Null);
 574             return self.force_query_with_job::<Q>(key, job, null_dep_node).0;
 575         }
 576
 577         if Q::ANON {
 578             let prof_timer = self.prof.query_provider();
 579
 580             let ((result, dep_node_index), diagnostics) = with_diagnostics(|diagnostics| {
 581                 self.start_query(job.id, diagnostics, |tcx| {
 582                     tcx.dep_graph.with_anon_task(Q::DEP_KIND, || Q::compute(tcx, key))
 583                 })
 584             });
 585
 586             prof_timer.finish_with_query_invocation_id(dep_node_index.into());
 587
 588             self.dep_graph.read_index(dep_node_index);
 589
 590             if unlikely!(!diagnostics.is_empty()) {
 591                 self.queries
 592                     .on_disk_cache
 593                     .store_diagnostics_for_anon_node(dep_node_index, diagnostics);
 594             }
 595
 596             job.complete(self, &result, dep_node_index);
 597
 598             return result;
 599         }
 600
 601         let dep_node = Q::to_dep_node(self, &key);
 602
 603         if !Q::EVAL_ALWAYS {
 604             // The diagnostics for this query will be
 605             // promoted to the current session during
 606             // `try_mark_green()`, so we can ignore them here.
 607             let loaded = self.start_query(job.id, None, |tcx| {
 608                 let marked = tcx.dep_graph.try_mark_green_and_read(tcx, &dep_node);
 609                 marked.map(|(prev_dep_node_index, dep_node_index)| {
 610                     (
 611                         tcx.load_from_disk_and_cache_in_memory::<Q>(
 612                             key.clone(),
 613                             prev_dep_node_index,
 614                             dep_node_index,
 615                             &dep_node,
 616                         ),
 617                         dep_node_index,
 618                     )
 619                 })
 620             });
 621             if let Some((result, dep_node_index)) = loaded {
 622                 job.complete(self, &result, dep_node_index);
 623                 return result;
 624             }
 625         }
 626
 627         let (result, dep_node_index) = self.force_query_with_job::<Q>(key, job, dep_node);
 628         self.dep_graph.read_index(dep_node_index);
 629         result
 630     }
 631
 632     fn load_from_disk_and_cache_in_memory<Q: QueryDescription<TyCtxt<'tcx>>>(
 633         self,
 634         key: Q::Key,
 635         prev_dep_node_index: SerializedDepNodeIndex,
 636         dep_node_index: DepNodeIndex,
 637         dep_node: &DepNode,
 638     ) -> Q::Value {
 639         // Note this function can be called concurrently from the same query
 640         // We must ensure that this is handled correctly.
 641
 642         debug_assert!(self.dep_graph.is_green(dep_node));
 643
 644         // First we try to load the result from the on-disk cache.
 645         let result = if Q::cache_on_disk(self, key.clone(), None) {
 646             let prof_timer = self.prof.incr_cache_loading();
 647             let result = Q::try_load_from_disk(self, prev_dep_node_index);
 648             prof_timer.finish_with_query_invocation_id(dep_node_index.into());
 649
 650             // We always expect to find a cached result for things that
 651             // can be forced from `DepNode`.
 652             debug_assert!(
 653                 !dep_node.kind.can_reconstruct_query_key() || result.is_some(),
 654                 "missing on-disk cache entry for {:?}",
 655                 dep_node
 656             );
 657             result
 658         } else {
 659             // Some things are never cached on disk.
 660             None
 661         };
 662
 663         let result = if let Some(result) = result {
 664             result
 665         } else {
 666             // We could not load a result from the on-disk cache, so
 667             // recompute.
 668             let prof_timer = self.prof.query_provider();
 669
 670             // The dep-graph for this computation is already in-place.
 671             let result = self.dep_graph.with_ignore(|| Q::compute(self, key));
 672
 673             prof_timer.finish_with_query_invocation_id(dep_node_index.into());
 674
 675             result
 676         };
 677
 678         // If `-Zincremental-verify-ich` is specified, re-hash results from
 679         // the cache and make sure that they have the expected fingerprint.
 680         if unlikely!(self.sess.opts.debugging_opts.incremental_verify_ich) {
 681             self.incremental_verify_ich::<Q>(&result, dep_node, dep_node_index);
 682         }
 683
 684         result
 685     }
 686
 687     #[inline(never)]
 688     #[cold]
 689     fn incremental_verify_ich<Q: QueryDescription<TyCtxt<'tcx>>>(
 690         self,
 691         result: &Q::Value,
 692         dep_node: &DepNode,
 693         dep_node_index: DepNodeIndex,
 694     ) {
 695         use rustc_data_structures::fingerprint::Fingerprint;
 696
 697         assert!(
 698             Some(self.dep_graph.fingerprint_of(dep_node_index))
 699                 == self.dep_graph.prev_fingerprint_of(dep_node),
 700             "fingerprint for green query instance not loaded from cache: {:?}",
 701             dep_node,
 702         );
 703
 704         debug!("BEGIN verify_ich({:?})", dep_node);
 705         let mut hcx = self.create_stable_hashing_context();
 706
 707         let new_hash = Q::hash_result(&mut hcx, result).unwrap_or(Fingerprint::ZERO);
 708         debug!("END verify_ich({:?})", dep_node);
 709
 710         let old_hash = self.dep_graph.fingerprint_of(dep_node_index);
 711
 712         assert!(new_hash == old_hash, "found unstable fingerprints for {:?}", dep_node,);
 713     }
 714
 715     #[inline(always)]
 716     fn force_query_with_job<Q: QueryDescription<TyCtxt<'tcx>> + 'tcx>(
 717         self,
 718         key: Q::Key,
 719         job: JobOwner<'tcx, TyCtxt<'tcx>, Q::Cache>,
 720         dep_node: DepNode,
 721     ) -> (Q::Value, DepNodeIndex) {
 722         // If the following assertion triggers, it can have two reasons:
 723         // 1. Something is wrong with DepNode creation, either here or
 724         //    in `DepGraph::try_mark_green()`.
 725         // 2. Two distinct query keys get mapped to the same `DepNode`
 726         //    (see for example #48923).
 727         assert!(
 728             !self.dep_graph.dep_node_exists(&dep_node),
 729             "forcing query with already existing `DepNode`\n\
 730                  - query-key: {:?}\n\
 731                  - dep-node: {:?}",
 732             key,
 733             dep_node
 734         );
 735
 736         let prof_timer = self.prof.query_provider();
 737
 738         let ((result, dep_node_index), diagnostics) = with_diagnostics(|diagnostics| {
 739             self.start_query(job.id, diagnostics, |tcx| {
 740                 if Q::EVAL_ALWAYS {
 741                     tcx.dep_graph.with_eval_always_task(
 742                         dep_node,
 743                         tcx,
 744                         key,
 745                         Q::compute,
 746                         Q::hash_result,
 747                     )
 748                 } else {
 749                     tcx.dep_graph.with_task(dep_node, tcx, key, Q::compute, Q::hash_result)
 750                 }
 751             })
 752         });
 753
 754         prof_timer.finish_with_query_invocation_id(dep_node_index.into());
 755
 756         if unlikely!(!diagnostics.is_empty()) {
 757             if dep_node.kind != crate::dep_graph::DepKind::Null {
 758                 self.queries.on_disk_cache.store_diagnostics(dep_node_index, diagnostics);
 759             }
 760         }
 761
 762         job.complete(self, &result, dep_node_index);
 763
 764         (result, dep_node_index)
 765     }
 766
 767     /// Ensure that either this query has all green inputs or been executed.
 768     /// Executing `query::ensure(D)` is considered a read of the dep-node `D`.
 769     ///
 770     /// This function is particularly useful when executing passes for their
 771     /// side-effects -- e.g., in order to report errors for erroneous programs.
 772     ///
 773     /// Note: The optimization is only available during incr. comp.
 774     pub(super) fn ensure_query<Q: QueryDescription<TyCtxt<'tcx>> + 'tcx>(self, key: Q::Key) {
 775         if Q::EVAL_ALWAYS {
 776             let _ = self.get_query::<Q>(DUMMY_SP, key);
 777             return;
 778         }
 779
 780         // Ensuring an anonymous query makes no sense
 781         assert!(!Q::ANON);
 782
 783         let dep_node = Q::to_dep_node(self, &key);
 784
 785         match self.dep_graph.try_mark_green_and_read(self, &dep_node) {
 786             None => {
 787                 // A None return from `try_mark_green_and_read` means that this is either
 788                 // a new dep node or that the dep node has already been marked red.
 789                 // Either way, we can't call `dep_graph.read()` as we don't have the
 790                 // DepNodeIndex. We must invoke the query itself. The performance cost
 791                 // this introduces should be negligible as we'll immediately hit the
 792                 // in-memory cache, or another query down the line will.
 793                 let _ = self.get_query::<Q>(DUMMY_SP, key);
 794             }
 795             Some((_, dep_node_index)) => {
 796                 self.prof.query_cache_hit(dep_node_index.into());
 797             }
 798         }
 799     }
 800
 801     #[allow(dead_code)]
 802     pub(super) fn force_query<Q: QueryDescription<TyCtxt<'tcx>> + 'tcx>(
 803         self,
 804         key: Q::Key,
 805         span: Span,
 806         dep_node: DepNode,
 807     ) {
 808         // We may be concurrently trying both execute and force a query.
 809         // Ensure that only one of them runs the query.
 810
 811         self.try_get_cached(
 812             Q::query_state(self),
 813             key,
 814             |_, _| {
 815                 // Cache hit, do nothing
 816             },
 817             |key, lookup| {
 818                 let job = match JobOwner::try_start::<Q>(self, span, &key, lookup) {
 819                     TryGetJob::NotYetStarted(job) => job,
 820                     TryGetJob::Cycle(_) => return,
 821                     #[cfg(parallel_compiler)]
 822                     TryGetJob::JobCompleted(_) => return,
 823                 };
 824                 self.force_query_with_job::<Q>(key, job, dep_node);
 825             },
 826         );
 827     }
 828 }
 829
 830 macro_rules! handle_cycle_error {
 831     ([][$tcx: expr, $error:expr]) => {{
 832         $tcx.report_cycle($error).emit();
 833         Value::from_cycle_error($tcx)
 834     }};
 835     ([fatal_cycle $($rest:tt)*][$tcx:expr, $error:expr]) => {{
 836         $tcx.report_cycle($error).emit();
 837         $tcx.sess.abort_if_errors();
 838         unreachable!()
 839     }};
 840     ([cycle_delay_bug $($rest:tt)*][$tcx:expr, $error:expr]) => {{
 841         $tcx.report_cycle($error).delay_as_bug();
 842         Value::from_cycle_error($tcx)
 843     }};
 844     ([$other:ident $(($($other_args:tt)*))* $(, $($modifiers:tt)*)*][$($args:tt)*]) => {
 845         handle_cycle_error!([$($($modifiers)*)*][$($args)*])
 846     };
 847 }
 848
 849 macro_rules! is_anon {
 850     ([]) => {{
 851         false
 852     }};
 853     ([anon $($rest:tt)*]) => {{
 854         true
 855     }};
 856     ([$other:ident $(($($other_args:tt)*))* $(, $($modifiers:tt)*)*]) => {
 857         is_anon!([$($($modifiers)*)*])
 858     };
 859 }
 860
 861 macro_rules! is_eval_always {
 862     ([]) => {{
 863         false
 864     }};
 865     ([eval_always $($rest:tt)*]) => {{
 866         true
 867     }};
 868     ([$other:ident $(($($other_args:tt)*))* $(, $($modifiers:tt)*)*]) => {
 869         is_eval_always!([$($($modifiers)*)*])
 870     };
 871 }
 872
 873 macro_rules! query_storage {
 874     (<$tcx:tt>[][$K:ty, $V:ty]) => {
 875         <<$K as Key>::CacheSelector as CacheSelector<TyCtxt<$tcx>, $K, $V>>::Cache
 876     };
 877     (<$tcx:tt>[storage($ty:ty) $($rest:tt)*][$K:ty, $V:ty]) => {
 878         $ty
 879     };
 880     (<$tcx:tt>[$other:ident $(($($other_args:tt)*))* $(, $($modifiers:tt)*)*][$($args:tt)*]) => {
 881         query_storage!(<$tcx>[$($($modifiers)*)*][$($args)*])
 882     };
 883 }
 884
 885 macro_rules! hash_result {
 886     ([][$hcx:expr, $result:expr]) => {{
 887         dep_graph::hash_result($hcx, &$result)
 888     }};
 889     ([no_hash $($rest:tt)*][$hcx:expr, $result:expr]) => {{
 890         None
 891     }};
 892     ([$other:ident $(($($other_args:tt)*))* $(, $($modifiers:tt)*)*][$($args:tt)*]) => {
 893         hash_result!([$($($modifiers)*)*][$($args)*])
 894     };
 895 }
 896
 897 macro_rules! define_queries {
 898     (<$tcx:tt> $($category:tt {
 899         $($(#[$attr:meta])* [$($modifiers:tt)*] fn $name:ident: $node:ident($K:ty) -> $V:ty,)*
 900     },)*) => {
 901         define_queries_inner! { <$tcx>
 902             $($( $(#[$attr])* category<$category> [$($modifiers)*] fn $name: $node($K) -> $V,)*)*
 903         }
 904     }
 905 }
 906
 907 macro_rules! define_queries_inner {
 908     (<$tcx:tt>
 909      $($(#[$attr:meta])* category<$category:tt>
 910         [$($modifiers:tt)*] fn $name:ident: $node:ident($K:ty) -> $V:ty,)*) => {
 911
 912         use std::mem;
 913         use crate::{
 914             rustc_data_structures::stable_hasher::HashStable,
 915             rustc_data_structures::stable_hasher::StableHasher,
 916             ich::StableHashingContext
 917         };
 918         use rustc_data_structures::profiling::ProfileCategory;
 919
 920         define_queries_struct! {
 921             tcx: $tcx,
 922             input: ($(([$($modifiers)*] [$($attr)*] [$name]))*)
 923         }
 924
 925         #[allow(nonstandard_style)]
 926         #[derive(Clone, Debug)]
 927         pub enum Query<$tcx> {
 928             $($(#[$attr])* $name($K)),*
 929         }
 930
 931         impl<$tcx> Query<$tcx> {
 932             pub fn name(&self) -> &'static str {
 933                 match *self {
 934                     $(Query::$name(_) => stringify!($name),)*
 935                 }
 936             }
 937
 938             pub fn describe(&self, tcx: TyCtxt<$tcx>) -> Cow<'static, str> {
 939                 let (r, name) = match *self {
 940                     $(Query::$name(key) => {
 941                         (queries::$name::describe(tcx, key), stringify!($name))
 942                     })*
 943                 };
 944                 if tcx.sess.verbose() {
 945                     format!("{} [{}]", r, name).into()
 946                 } else {
 947                     r
 948                 }
 949             }
 950
 951             // FIXME(eddyb) Get more valid `Span`s on queries.
 952             pub fn default_span(&self, tcx: TyCtxt<$tcx>, span: Span) -> Span {
 953                 if !span.is_dummy() {
 954                     return span;
 955                 }
 956                 // The `def_span` query is used to calculate `default_span`,
 957                 // so exit to avoid infinite recursion.
 958                 if let Query::def_span(..) = *self {
 959                     return span
 960                 }
 961                 match *self {
 962                     $(Query::$name(key) => key.default_span(tcx),)*
 963                 }
 964             }
 965         }
 966
 967         impl<'a, $tcx> HashStable<StableHashingContext<'a>> for Query<$tcx> {
 968             fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
 969                 mem::discriminant(self).hash_stable(hcx, hasher);
 970                 match *self {
 971                     $(Query::$name(key) => key.hash_stable(hcx, hasher),)*
 972                 }
 973             }
 974         }
 975
 976         pub mod queries {
 977             use std::marker::PhantomData;
 978
 979             $(#[allow(nonstandard_style)]
 980             pub struct $name<$tcx> {
 981                 data: PhantomData<&$tcx ()>
 982             })*
 983         }
 984
 985         $(impl<$tcx> QueryConfig<TyCtxt<$tcx>> for queries::$name<$tcx> {
 986             type Key = $K;
 987             type Value = $V;
 988             const NAME: &'static str = stringify!($name);
 989             const CATEGORY: ProfileCategory = $category;
 990         }
 991
 992         impl<$tcx> QueryAccessors<TyCtxt<$tcx>> for queries::$name<$tcx> {
 993             const ANON: bool = is_anon!([$($modifiers)*]);
 994             const EVAL_ALWAYS: bool = is_eval_always!([$($modifiers)*]);
 995             const DEP_KIND: dep_graph::DepKind = dep_graph::DepKind::$node;
 996
 997             type Cache = query_storage!(<$tcx>[$($modifiers)*][$K, $V]);
 998
 999             #[inline(always)]
1000             fn query_state<'a>(tcx: TyCtxt<$tcx>) -> &'a QueryState<TyCtxt<$tcx>, Self::Cache> {
1001                 &tcx.queries.$name
1002             }
1003
1004             #[allow(unused)]
1005             #[inline(always)]
1006             fn to_dep_node(tcx: TyCtxt<$tcx>, key: &Self::Key) -> DepNode {
1007                 DepConstructor::$node(tcx, *key)
1008             }
1009
1010             #[inline]
1011             fn compute(tcx: TyCtxt<'tcx>, key: Self::Key) -> Self::Value {
1012                 let provider = tcx.queries.providers.get(key.query_crate())
1013                     // HACK(eddyb) it's possible crates may be loaded after
1014                     // the query engine is created, and because crate loading
1015                     // is not yet integrated with the query engine, such crates
1016                     // would be missing appropriate entries in `providers`.
1017                     .unwrap_or(&tcx.queries.fallback_extern_providers)
1018                     .$name;
1019                 provider(tcx, key)
1020             }
1021
1022             fn hash_result(
1023                 _hcx: &mut StableHashingContext<'_>,
1024                 _result: &Self::Value
1025             ) -> Option<Fingerprint> {
1026                 hash_result!([$($modifiers)*][_hcx, _result])
1027             }
1028
1029             fn handle_cycle_error(
1030                 tcx: TyCtxt<'tcx>,
1031                 error: CycleError<TyCtxt<'tcx>>
1032             ) -> Self::Value {
1033                 handle_cycle_error!([$($modifiers)*][tcx, error])
1034             }
1035         })*
1036
1037         #[derive(Copy, Clone)]
1038         pub struct TyCtxtEnsure<'tcx> {
1039             pub tcx: TyCtxt<'tcx>,
1040         }
1041
1042         impl TyCtxtEnsure<$tcx> {
1043             $($(#[$attr])*
1044             #[inline(always)]
1045             pub fn $name(self, key: $K) {
1046                 self.tcx.ensure_query::<queries::$name<'_>>(key)
1047             })*
1048         }
1049
1050         #[derive(Copy, Clone)]
1051         pub struct TyCtxtAt<'tcx> {
1052             pub tcx: TyCtxt<'tcx>,
1053             pub span: Span,
1054         }
1055
1056         impl Deref for TyCtxtAt<'tcx> {
1057             type Target = TyCtxt<'tcx>;
1058             #[inline(always)]
1059             fn deref(&self) -> &Self::Target {
1060                 &self.tcx
1061             }
1062         }
1063
1064         impl TyCtxt<$tcx> {
1065             /// Returns a transparent wrapper for `TyCtxt`, which ensures queries
1066             /// are executed instead of just returning their results.
1067             #[inline(always)]
1068             pub fn ensure(self) -> TyCtxtEnsure<$tcx> {
1069                 TyCtxtEnsure {
1070                     tcx: self,
1071                 }
1072             }
1073
1074             /// Returns a transparent wrapper for `TyCtxt` which uses
1075             /// `span` as the location of queries performed through it.
1076             #[inline(always)]
1077             pub fn at(self, span: Span) -> TyCtxtAt<$tcx> {
1078                 TyCtxtAt {
1079                     tcx: self,
1080                     span
1081                 }
1082             }
1083
1084             $($(#[$attr])*
1085             #[inline(always)]
1086             pub fn $name(self, key: $K) -> $V {
1087                 self.at(DUMMY_SP).$name(key)
1088             })*
1089
1090             /// All self-profiling events generated by the query engine use
1091             /// virtual `StringId`s for their `event_id`. This method makes all
1092             /// those virtual `StringId`s point to actual strings.
1093             ///
1094             /// If we are recording only summary data, the ids will point to
1095             /// just the query names. If we are recording query keys too, we
1096             /// allocate the corresponding strings here.
1097             pub fn alloc_self_profile_query_strings(self) {
1098                 use crate::ty::query::profiling_support::{
1099                     alloc_self_profile_query_strings_for_query_cache,
1100                     QueryKeyStringCache,
1101                 };
1102
1103                 if !self.prof.enabled() {
1104                     return;
1105                 }
1106
1107                 let mut string_cache = QueryKeyStringCache::new();
1108
1109                 $({
1110                     alloc_self_profile_query_strings_for_query_cache(
1111                         self,
1112                         stringify!($name),
1113                         &self.queries.$name,
1114                         &mut string_cache,
1115                     );
1116                 })*
1117             }
1118         }
1119
1120         impl TyCtxtAt<$tcx> {
1121             $($(#[$attr])*
1122             #[inline(always)]
1123             pub fn $name(self, key: $K) -> $V {
1124                 self.tcx.get_query::<queries::$name<'_>>(self.span, key)
1125             })*
1126         }
1127
1128         define_provider_struct! {
1129             tcx: $tcx,
1130             input: ($(([$($modifiers)*] [$name] [$K] [$V]))*)
1131         }
1132
1133         impl<$tcx> Copy for Providers<$tcx> {}
1134         impl<$tcx> Clone for Providers<$tcx> {
1135             fn clone(&self) -> Self { *self }
1136         }
1137     }
1138 }
1139
1140 macro_rules! define_queries_struct {
1141     (tcx: $tcx:tt,
1142      input: ($(([$($modifiers:tt)*] [$($attr:tt)*] [$name:ident]))*)) => {
1143         pub struct Queries<$tcx> {
1144             /// This provides access to the incrimental comilation on-disk cache for query results.
1145             /// Do not access this directly. It is only meant to be used by
1146             /// `DepGraph::try_mark_green()` and the query infrastructure.
1147             pub(crate) on_disk_cache: OnDiskCache<'tcx>,
1148
1149             providers: IndexVec<CrateNum, Providers<$tcx>>,
1150             fallback_extern_providers: Box<Providers<$tcx>>,
1151
1152             $($(#[$attr])*  $name: QueryState<
1153                 TyCtxt<$tcx>,
1154                 <queries::$name<$tcx> as QueryAccessors<TyCtxt<'tcx>>>::Cache,
1155             >,)*
1156         }
1157
1158         impl<$tcx> Queries<$tcx> {
1159             pub(crate) fn new(
1160                 providers: IndexVec<CrateNum, Providers<$tcx>>,
1161                 fallback_extern_providers: Providers<$tcx>,
1162                 on_disk_cache: OnDiskCache<'tcx>,
1163             ) -> Self {
1164                 Queries {
1165                     providers,
1166                     fallback_extern_providers: Box::new(fallback_extern_providers),
1167                     on_disk_cache,
1168                     $($name: Default::default()),*
1169                 }
1170             }
1171
1172             pub(crate) fn try_collect_active_jobs(
1173                 &self
1174             ) -> Option<FxHashMap<QueryJobId, QueryJobInfo<TyCtxt<'tcx>>>> {
1175                 let mut jobs = FxHashMap::default();
1176
1177                 $(
1178                     self.$name.try_collect_active_jobs(
1179                         <queries::$name<'tcx> as QueryAccessors<TyCtxt<'tcx>>>::DEP_KIND,
1180                         Query::$name,
1181                         &mut jobs,
1182                     )?;
1183                 )*
1184
1185                 Some(jobs)
1186             }
1187         }
1188     };
1189 }
1190
1191 macro_rules! define_provider_struct {
1192     (tcx: $tcx:tt,
1193      input: ($(([$($modifiers:tt)*] [$name:ident] [$K:ty] [$R:ty]))*)) => {
1194         pub struct Providers<$tcx> {
1195             $(pub $name: fn(TyCtxt<$tcx>, $K) -> $R,)*
1196         }
1197
1198         impl<$tcx> Default for Providers<$tcx> {
1199             fn default() -> Self {
1200                 $(fn $name<$tcx>(_: TyCtxt<$tcx>, key: $K) -> $R {
1201                     bug!("`tcx.{}({:?})` unsupported by its crate",
1202                          stringify!($name), key);
1203                 })*
1204                 Providers { $($name),* }
1205             }
1206         }
1207     };
1208 }