src/librustc/ty/maps.rs

   1 // Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use dep_graph::{DepConstructor, DepNode, DepNodeIndex};
  12 use errors::{Diagnostic, DiagnosticBuilder};
  13 use hir::def_id::{CrateNum, DefId, LOCAL_CRATE};
  14 use hir::def::{Def, Export};
  15 use hir::{self, TraitCandidate, HirId};
  16 use hir::svh::Svh;
  17 use lint;
  18 use middle::const_val;
  19 use middle::cstore::{ExternCrate, LinkagePreference, NativeLibrary};
  20 use middle::privacy::AccessLevels;
  21 use middle::region;
  22 use mir;
  23 use mir::transform::{MirSuite, MirPassIndex};
  24 use session::CompileResult;
  25 use traits::specialization_graph;
  26 use ty::{self, CrateInherentImpls, Ty, TyCtxt};
  27 use ty::layout::{Layout, LayoutError};
  28 use ty::item_path;
  29 use ty::steal::Steal;
  30 use ty::subst::Substs;
  31 use ty::fast_reject::SimplifiedType;
  32 use util::nodemap::{DefIdSet, NodeSet};
  33 use util::common::{profq_msg, ProfileQueriesMsg};
  34
  35 use rustc_data_structures::indexed_set::IdxSetBuf;
  36 use rustc_back::PanicStrategy;
  37 use rustc_data_structures::indexed_vec::IndexVec;
  38 use rustc_data_structures::fx::FxHashMap;
  39 use std::cell::{RefCell, RefMut, Cell};
  40 use std::fmt::Debug;
  41 use std::hash::Hash;
  42 use std::marker::PhantomData;
  43 use std::mem;
  44 use std::collections::BTreeMap;
  45 use std::ops::Deref;
  46 use std::rc::Rc;
  47 use syntax_pos::{Span, DUMMY_SP};
  48 use syntax::attr;
  49 use syntax::ast;
  50 use syntax::symbol::Symbol;
  51
  52 pub trait Key: Clone + Hash + Eq + Debug {
  53     fn map_crate(&self) -> CrateNum;
  54     fn default_span(&self, tcx: TyCtxt) -> Span;
  55 }
  56
  57 impl<'tcx> Key for ty::InstanceDef<'tcx> {
  58     fn map_crate(&self) -> CrateNum {
  59         LOCAL_CRATE
  60     }
  61
  62     fn default_span(&self, tcx: TyCtxt) -> Span {
  63         tcx.def_span(self.def_id())
  64     }
  65 }
  66
  67 impl<'tcx> Key for ty::Instance<'tcx> {
  68     fn map_crate(&self) -> CrateNum {
  69         LOCAL_CRATE
  70     }
  71
  72     fn default_span(&self, tcx: TyCtxt) -> Span {
  73         tcx.def_span(self.def_id())
  74     }
  75 }
  76
  77 impl Key for CrateNum {
  78     fn map_crate(&self) -> CrateNum {
  79         *self
  80     }
  81     fn default_span(&self, _: TyCtxt) -> Span {
  82         DUMMY_SP
  83     }
  84 }
  85
  86 impl Key for HirId {
  87     fn map_crate(&self) -> CrateNum {
  88         LOCAL_CRATE
  89     }
  90     fn default_span(&self, _tcx: TyCtxt) -> Span {
  91         DUMMY_SP
  92     }
  93 }
  94
  95 impl Key for DefId {
  96     fn map_crate(&self) -> CrateNum {
  97         self.krate
  98     }
  99     fn default_span(&self, tcx: TyCtxt) -> Span {
 100         tcx.def_span(*self)
 101     }
 102 }
 103
 104 impl Key for (DefId, DefId) {
 105     fn map_crate(&self) -> CrateNum {
 106         self.0.krate
 107     }
 108     fn default_span(&self, tcx: TyCtxt) -> Span {
 109         self.1.default_span(tcx)
 110     }
 111 }
 112
 113 impl Key for (CrateNum, DefId) {
 114     fn map_crate(&self) -> CrateNum {
 115         self.0
 116     }
 117     fn default_span(&self, tcx: TyCtxt) -> Span {
 118         self.1.default_span(tcx)
 119     }
 120 }
 121
 122 impl Key for (DefId, SimplifiedType) {
 123     fn map_crate(&self) -> CrateNum {
 124         self.0.krate
 125     }
 126     fn default_span(&self, tcx: TyCtxt) -> Span {
 127         self.0.default_span(tcx)
 128     }
 129 }
 130
 131 impl<'tcx> Key for (DefId, &'tcx Substs<'tcx>) {
 132     fn map_crate(&self) -> CrateNum {
 133         self.0.krate
 134     }
 135     fn default_span(&self, tcx: TyCtxt) -> Span {
 136         self.0.default_span(tcx)
 137     }
 138 }
 139
 140 impl Key for (MirSuite, DefId) {
 141     fn map_crate(&self) -> CrateNum {
 142         self.1.map_crate()
 143     }
 144     fn default_span(&self, tcx: TyCtxt) -> Span {
 145         self.1.default_span(tcx)
 146     }
 147 }
 148
 149 impl Key for (MirSuite, MirPassIndex, DefId) {
 150     fn map_crate(&self) -> CrateNum {
 151         self.2.map_crate()
 152     }
 153     fn default_span(&self, tcx: TyCtxt) -> Span {
 154         self.2.default_span(tcx)
 155     }
 156 }
 157
 158 impl<'tcx, T: Clone + Hash + Eq + Debug> Key for ty::ParamEnvAnd<'tcx, T> {
 159     fn map_crate(&self) -> CrateNum {
 160         LOCAL_CRATE
 161     }
 162     fn default_span(&self, _: TyCtxt) -> Span {
 163         DUMMY_SP
 164     }
 165 }
 166
 167 trait Value<'tcx>: Sized {
 168     fn from_cycle_error<'a>(tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Self;
 169 }
 170
 171 impl<'tcx, T> Value<'tcx> for T {
 172     default fn from_cycle_error<'a>(tcx: TyCtxt<'a, 'tcx, 'tcx>) -> T {
 173         tcx.sess.abort_if_errors();
 174         bug!("Value::from_cycle_error called without errors");
 175     }
 176 }
 177
 178 impl<'tcx, T: Default> Value<'tcx> for T {
 179     default fn from_cycle_error<'a>(_: TyCtxt<'a, 'tcx, 'tcx>) -> T {
 180         T::default()
 181     }
 182 }
 183
 184 impl<'tcx> Value<'tcx> for Ty<'tcx> {
 185     fn from_cycle_error<'a>(tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Ty<'tcx> {
 186         tcx.types.err
 187     }
 188 }
 189
 190 impl<'tcx> Value<'tcx> for ty::DtorckConstraint<'tcx> {
 191     fn from_cycle_error<'a>(_: TyCtxt<'a, 'tcx, 'tcx>) -> Self {
 192         Self::empty()
 193     }
 194 }
 195
 196 impl<'tcx> Value<'tcx> for ty::SymbolName {
 197     fn from_cycle_error<'a>(_: TyCtxt<'a, 'tcx, 'tcx>) -> Self {
 198         ty::SymbolName { name: Symbol::intern("<error>").as_str() }
 199     }
 200 }
 201
 202 struct QueryMap<D: QueryDescription> {
 203     phantom: PhantomData<D>,
 204     map: FxHashMap<D::Key, QueryValue<D::Value>>,
 205 }
 206
 207 struct QueryValue<T> {
 208     value: T,
 209     index: DepNodeIndex,
 210     diagnostics: Option<Box<QueryDiagnostics>>,
 211 }
 212
 213 struct QueryDiagnostics {
 214     diagnostics: Vec<Diagnostic>,
 215     emitted_diagnostics: Cell<bool>,
 216 }
 217
 218 impl<M: QueryDescription> QueryMap<M> {
 219     fn new() -> QueryMap<M> {
 220         QueryMap {
 221             phantom: PhantomData,
 222             map: FxHashMap(),
 223         }
 224     }
 225 }
 226
 227 struct CycleError<'a, 'tcx: 'a> {
 228     span: Span,
 229     cycle: RefMut<'a, [(Span, Query<'tcx>)]>,
 230 }
 231
 232 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
 233     fn report_cycle(self, CycleError { span, cycle }: CycleError)
 234         -> DiagnosticBuilder<'a>
 235     {
 236         // Subtle: release the refcell lock before invoking `describe()`
 237         // below by dropping `cycle`.
 238         let stack = cycle.to_vec();
 239         mem::drop(cycle);
 240
 241         assert!(!stack.is_empty());
 242
 243         // Disable naming impls with types in this path, since that
 244         // sometimes cycles itself, leading to extra cycle errors.
 245         // (And cycle errors around impls tend to occur during the
 246         // collect/coherence phases anyhow.)
 247         item_path::with_forced_impl_filename_line(|| {
 248             let mut err =
 249                 struct_span_err!(self.sess, span, E0391,
 250                                  "unsupported cyclic reference between types/traits detected");
 251             err.span_label(span, "cyclic reference");
 252
 253             err.span_note(stack[0].0, &format!("the cycle begins when {}...",
 254                                                stack[0].1.describe(self)));
 255
 256             for &(span, ref query) in &stack[1..] {
 257                 err.span_note(span, &format!("...which then requires {}...",
 258                                              query.describe(self)));
 259             }
 260
 261             err.note(&format!("...which then again requires {}, completing the cycle.",
 262                               stack[0].1.describe(self)));
 263
 264             return err
 265         })
 266     }
 267
 268     fn cycle_check<F, R>(self, span: Span, query: Query<'gcx>, compute: F)
 269                          -> Result<R, CycleError<'a, 'gcx>>
 270         where F: FnOnce() -> R
 271     {
 272         {
 273             let mut stack = self.maps.query_stack.borrow_mut();
 274             if let Some((i, _)) = stack.iter().enumerate().rev()
 275                                        .find(|&(_, &(_, ref q))| *q == query) {
 276                 return Err(CycleError {
 277                     span,
 278                     cycle: RefMut::map(stack, |stack| &mut stack[i..])
 279                 });
 280             }
 281             stack.push((span, query));
 282         }
 283
 284         let result = compute();
 285
 286         self.maps.query_stack.borrow_mut().pop();
 287
 288         Ok(result)
 289     }
 290 }
 291
 292 pub trait QueryConfig {
 293     type Key: Eq + Hash + Clone;
 294     type Value;
 295 }
 296
 297 trait QueryDescription: QueryConfig {
 298     fn describe(tcx: TyCtxt, key: Self::Key) -> String;
 299 }
 300
 301 impl<M: QueryConfig<Key=DefId>> QueryDescription for M {
 302     default fn describe(tcx: TyCtxt, def_id: DefId) -> String {
 303         format!("processing `{}`", tcx.item_path_str(def_id))
 304     }
 305 }
 306
 307 impl<'tcx> QueryDescription for queries::is_copy_raw<'tcx> {
 308     fn describe(_tcx: TyCtxt, env: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> String {
 309         format!("computing whether `{}` is `Copy`", env.value)
 310     }
 311 }
 312
 313 impl<'tcx> QueryDescription for queries::is_sized_raw<'tcx> {
 314     fn describe(_tcx: TyCtxt, env: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> String {
 315         format!("computing whether `{}` is `Sized`", env.value)
 316     }
 317 }
 318
 319 impl<'tcx> QueryDescription for queries::is_freeze_raw<'tcx> {
 320     fn describe(_tcx: TyCtxt, env: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> String {
 321         format!("computing whether `{}` is freeze", env.value)
 322     }
 323 }
 324
 325 impl<'tcx> QueryDescription for queries::needs_drop_raw<'tcx> {
 326     fn describe(_tcx: TyCtxt, env: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> String {
 327         format!("computing whether `{}` needs drop", env.value)
 328     }
 329 }
 330
 331 impl<'tcx> QueryDescription for queries::layout_raw<'tcx> {
 332     fn describe(_tcx: TyCtxt, env: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> String {
 333         format!("computing layout of `{}`", env.value)
 334     }
 335 }
 336
 337 impl<'tcx> QueryDescription for queries::super_predicates_of<'tcx> {
 338     fn describe(tcx: TyCtxt, def_id: DefId) -> String {
 339         format!("computing the supertraits of `{}`",
 340                 tcx.item_path_str(def_id))
 341     }
 342 }
 343
 344 impl<'tcx> QueryDescription for queries::type_param_predicates<'tcx> {
 345     fn describe(tcx: TyCtxt, (_, def_id): (DefId, DefId)) -> String {
 346         let id = tcx.hir.as_local_node_id(def_id).unwrap();
 347         format!("computing the bounds for type parameter `{}`",
 348                 tcx.hir.ty_param_name(id))
 349     }
 350 }
 351
 352 impl<'tcx> QueryDescription for queries::coherent_trait<'tcx> {
 353     fn describe(tcx: TyCtxt, (_, def_id): (CrateNum, DefId)) -> String {
 354         format!("coherence checking all impls of trait `{}`",
 355                 tcx.item_path_str(def_id))
 356     }
 357 }
 358
 359 impl<'tcx> QueryDescription for queries::crate_inherent_impls<'tcx> {
 360     fn describe(_: TyCtxt, k: CrateNum) -> String {
 361         format!("all inherent impls defined in crate `{:?}`", k)
 362     }
 363 }
 364
 365 impl<'tcx> QueryDescription for queries::crate_inherent_impls_overlap_check<'tcx> {
 366     fn describe(_: TyCtxt, _: CrateNum) -> String {
 367         format!("check for overlap between inherent impls defined in this crate")
 368     }
 369 }
 370
 371 impl<'tcx> QueryDescription for queries::crate_variances<'tcx> {
 372     fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
 373         format!("computing the variances for items in this crate")
 374     }
 375 }
 376
 377 impl<'tcx> QueryDescription for queries::mir_shims<'tcx> {
 378     fn describe(tcx: TyCtxt, def: ty::InstanceDef<'tcx>) -> String {
 379         format!("generating MIR shim for `{}`",
 380                 tcx.item_path_str(def.def_id()))
 381     }
 382 }
 383
 384 impl<'tcx> QueryDescription for queries::privacy_access_levels<'tcx> {
 385     fn describe(_: TyCtxt, _: CrateNum) -> String {
 386         format!("privacy access levels")
 387     }
 388 }
 389
 390 impl<'tcx> QueryDescription for queries::typeck_item_bodies<'tcx> {
 391     fn describe(_: TyCtxt, _: CrateNum) -> String {
 392         format!("type-checking all item bodies")
 393     }
 394 }
 395
 396 impl<'tcx> QueryDescription for queries::reachable_set<'tcx> {
 397     fn describe(_: TyCtxt, _: CrateNum) -> String {
 398         format!("reachability")
 399     }
 400 }
 401
 402 impl<'tcx> QueryDescription for queries::const_eval<'tcx> {
 403     fn describe(tcx: TyCtxt, key: ty::ParamEnvAnd<'tcx, (DefId, &'tcx Substs<'tcx>)>) -> String {
 404         format!("const-evaluating `{}`", tcx.item_path_str(key.value.0))
 405     }
 406 }
 407
 408 impl<'tcx> QueryDescription for queries::mir_keys<'tcx> {
 409     fn describe(_: TyCtxt, _: CrateNum) -> String {
 410         format!("getting a list of all mir_keys")
 411     }
 412 }
 413
 414 impl<'tcx> QueryDescription for queries::symbol_name<'tcx> {
 415     fn describe(_tcx: TyCtxt, instance: ty::Instance<'tcx>) -> String {
 416         format!("computing the symbol for `{}`", instance)
 417     }
 418 }
 419
 420 impl<'tcx> QueryDescription for queries::describe_def<'tcx> {
 421     fn describe(_: TyCtxt, _: DefId) -> String {
 422         bug!("describe_def")
 423     }
 424 }
 425
 426 impl<'tcx> QueryDescription for queries::def_span<'tcx> {
 427     fn describe(_: TyCtxt, _: DefId) -> String {
 428         bug!("def_span")
 429     }
 430 }
 431
 432
 433 impl<'tcx> QueryDescription for queries::stability<'tcx> {
 434     fn describe(_: TyCtxt, _: DefId) -> String {
 435         bug!("stability")
 436     }
 437 }
 438
 439 impl<'tcx> QueryDescription for queries::deprecation<'tcx> {
 440     fn describe(_: TyCtxt, _: DefId) -> String {
 441         bug!("deprecation")
 442     }
 443 }
 444
 445 impl<'tcx> QueryDescription for queries::item_attrs<'tcx> {
 446     fn describe(_: TyCtxt, _: DefId) -> String {
 447         bug!("item_attrs")
 448     }
 449 }
 450
 451 impl<'tcx> QueryDescription for queries::is_exported_symbol<'tcx> {
 452     fn describe(_: TyCtxt, _: DefId) -> String {
 453         bug!("is_exported_symbol")
 454     }
 455 }
 456
 457 impl<'tcx> QueryDescription for queries::fn_arg_names<'tcx> {
 458     fn describe(_: TyCtxt, _: DefId) -> String {
 459         bug!("fn_arg_names")
 460     }
 461 }
 462
 463 impl<'tcx> QueryDescription for queries::impl_parent<'tcx> {
 464     fn describe(_: TyCtxt, _: DefId) -> String {
 465         bug!("impl_parent")
 466     }
 467 }
 468
 469 impl<'tcx> QueryDescription for queries::trait_of_item<'tcx> {
 470     fn describe(_: TyCtxt, _: DefId) -> String {
 471         bug!("trait_of_item")
 472     }
 473 }
 474
 475 impl<'tcx> QueryDescription for queries::item_body_nested_bodies<'tcx> {
 476     fn describe(tcx: TyCtxt, def_id: DefId) -> String {
 477         format!("nested item bodies of `{}`", tcx.item_path_str(def_id))
 478     }
 479 }
 480
 481 impl<'tcx> QueryDescription for queries::const_is_rvalue_promotable_to_static<'tcx> {
 482     fn describe(tcx: TyCtxt, def_id: DefId) -> String {
 483         format!("const checking if rvalue is promotable to static `{}`",
 484             tcx.item_path_str(def_id))
 485     }
 486 }
 487
 488 impl<'tcx> QueryDescription for queries::is_mir_available<'tcx> {
 489     fn describe(tcx: TyCtxt, def_id: DefId) -> String {
 490         format!("checking if item is mir available: `{}`",
 491             tcx.item_path_str(def_id))
 492     }
 493 }
 494
 495 impl<'tcx> QueryDescription for queries::trait_impls_of<'tcx> {
 496     fn describe(tcx: TyCtxt, def_id: DefId) -> String {
 497         format!("trait impls of `{}`", tcx.item_path_str(def_id))
 498     }
 499 }
 500
 501 impl<'tcx> QueryDescription for queries::is_object_safe<'tcx> {
 502     fn describe(tcx: TyCtxt, def_id: DefId) -> String {
 503         format!("determine object safety of trait `{}`", tcx.item_path_str(def_id))
 504     }
 505 }
 506
 507 impl<'tcx> QueryDescription for queries::is_const_fn<'tcx> {
 508     fn describe(tcx: TyCtxt, def_id: DefId) -> String {
 509         format!("checking if item is const fn: `{}`", tcx.item_path_str(def_id))
 510     }
 511 }
 512
 513 impl<'tcx> QueryDescription for queries::dylib_dependency_formats<'tcx> {
 514     fn describe(_: TyCtxt, _: CrateNum) -> String {
 515         "dylib dependency formats of crate".to_string()
 516     }
 517 }
 518
 519 impl<'tcx> QueryDescription for queries::is_panic_runtime<'tcx> {
 520     fn describe(_: TyCtxt, _: CrateNum) -> String {
 521         "checking if the crate is_panic_runtime".to_string()
 522     }
 523 }
 524
 525 impl<'tcx> QueryDescription for queries::is_compiler_builtins<'tcx> {
 526     fn describe(_: TyCtxt, _: CrateNum) -> String {
 527         "checking if the crate is_compiler_builtins".to_string()
 528     }
 529 }
 530
 531 impl<'tcx> QueryDescription for queries::has_global_allocator<'tcx> {
 532     fn describe(_: TyCtxt, _: CrateNum) -> String {
 533         "checking if the crate has_global_allocator".to_string()
 534     }
 535 }
 536
 537 impl<'tcx> QueryDescription for queries::extern_crate<'tcx> {
 538     fn describe(_: TyCtxt, _: DefId) -> String {
 539         "getting crate's ExternCrateData".to_string()
 540     }
 541 }
 542
 543 impl<'tcx> QueryDescription for queries::lint_levels<'tcx> {
 544     fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
 545         format!("computing the lint levels for items in this crate")
 546     }
 547 }
 548
 549 impl<'tcx> QueryDescription for queries::specializes<'tcx> {
 550     fn describe(_tcx: TyCtxt, _: (DefId, DefId)) -> String {
 551         format!("computing whether impls specialize one another")
 552     }
 553 }
 554
 555 impl<'tcx> QueryDescription for queries::in_scope_traits<'tcx> {
 556     fn describe(_tcx: TyCtxt, _: HirId) -> String {
 557         format!("fetching the traits in scope at a particular ast node")
 558     }
 559 }
 560
 561 impl<'tcx> QueryDescription for queries::module_exports<'tcx> {
 562     fn describe(_tcx: TyCtxt, _: HirId) -> String {
 563         format!("fetching the exported items for a module")
 564     }
 565 }
 566
 567 impl<'tcx> QueryDescription for queries::is_no_builtins<'tcx> {
 568     fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
 569         format!("test whether a crate has #![no_builtins]")
 570     }
 571 }
 572
 573 impl<'tcx> QueryDescription for queries::panic_strategy<'tcx> {
 574     fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
 575         format!("query a crate's configured panic strategy")
 576     }
 577 }
 578
 579 impl<'tcx> QueryDescription for queries::is_profiler_runtime<'tcx> {
 580     fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
 581         format!("query a crate is #![profiler_runtime]")
 582     }
 583 }
 584
 585 impl<'tcx> QueryDescription for queries::is_sanitizer_runtime<'tcx> {
 586     fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
 587         format!("query a crate is #![sanitizer_runtime]")
 588     }
 589 }
 590
 591 impl<'tcx> QueryDescription for queries::exported_symbols<'tcx> {
 592     fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
 593         format!("looking up the exported symbols of a crate")
 594     }
 595 }
 596
 597 impl<'tcx> QueryDescription for queries::native_libraries<'tcx> {
 598     fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
 599         format!("looking up the native libraries of a linked crate")
 600     }
 601 }
 602
 603 impl<'tcx> QueryDescription for queries::plugin_registrar_fn<'tcx> {
 604     fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
 605         format!("looking up the plugin registrar for a crate")
 606     }
 607 }
 608
 609 impl<'tcx> QueryDescription for queries::derive_registrar_fn<'tcx> {
 610     fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
 611         format!("looking up the derive registrar for a crate")
 612     }
 613 }
 614
 615 impl<'tcx> QueryDescription for queries::crate_disambiguator<'tcx> {
 616     fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
 617         format!("looking up the disambiguator a crate")
 618     }
 619 }
 620
 621 impl<'tcx> QueryDescription for queries::crate_hash<'tcx> {
 622     fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
 623         format!("looking up the hash a crate")
 624     }
 625 }
 626
 627 impl<'tcx> QueryDescription for queries::original_crate_name<'tcx> {
 628     fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
 629         format!("looking up the original name a crate")
 630     }
 631 }
 632
 633 impl<'tcx> QueryDescription for queries::implementations_of_trait<'tcx> {
 634     fn describe(_tcx: TyCtxt, _: (CrateNum, DefId)) -> String {
 635         format!("looking up implementations of a trait in a crate")
 636     }
 637 }
 638
 639 impl<'tcx> QueryDescription for queries::all_trait_implementations<'tcx> {
 640     fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
 641         format!("looking up all (?) trait implementations")
 642     }
 643 }
 644
 645 // If enabled, send a message to the profile-queries thread
 646 macro_rules! profq_msg {
 647     ($tcx:expr, $msg:expr) => {
 648         if cfg!(debug_assertions) {
 649             if  $tcx.sess.profile_queries() {
 650                 profq_msg($msg)
 651             }
 652         }
 653     }
 654 }
 655
 656 // If enabled, format a key using its debug string, which can be
 657 // expensive to compute (in terms of time).
 658 macro_rules! profq_key {
 659     ($tcx:expr, $key:expr) => {
 660         if cfg!(debug_assertions) {
 661             if $tcx.sess.profile_queries_and_keys() {
 662                 Some(format!("{:?}", $key))
 663             } else { None }
 664         } else { None }
 665     }
 666 }
 667
 668 macro_rules! define_maps {
 669     (<$tcx:tt>
 670      $($(#[$attr:meta])*
 671        [$($modifiers:tt)*] fn $name:ident: $node:ident($K:ty) -> $V:ty,)*) => {
 672         define_map_struct! {
 673             tcx: $tcx,
 674             input: ($(([$($modifiers)*] [$($attr)*] [$name]))*)
 675         }
 676
 677         impl<$tcx> Maps<$tcx> {
 678             pub fn new(providers: IndexVec<CrateNum, Providers<$tcx>>)
 679                        -> Self {
 680                 Maps {
 681                     providers,
 682                     query_stack: RefCell::new(vec![]),
 683                     $($name: RefCell::new(QueryMap::new())),*
 684                 }
 685             }
 686         }
 687
 688         #[allow(bad_style)]
 689         #[derive(Copy, Clone, Debug, PartialEq, Eq)]
 690         pub enum Query<$tcx> {
 691             $($(#[$attr])* $name($K)),*
 692         }
 693
 694         #[allow(bad_style)]
 695         #[derive(Clone, Debug, PartialEq, Eq)]
 696         pub enum QueryMsg {
 697             $($name(Option<String>)),*
 698         }
 699
 700         impl<$tcx> Query<$tcx> {
 701             pub fn describe(&self, tcx: TyCtxt) -> String {
 702                 let (r, name) = match *self {
 703                     $(Query::$name(key) => {
 704                         (queries::$name::describe(tcx, key), stringify!($name))
 705                     })*
 706                 };
 707                 if tcx.sess.verbose() {
 708                     format!("{} [{}]", r, name)
 709                 } else {
 710                     r
 711                 }
 712             }
 713         }
 714
 715         pub mod queries {
 716             use std::marker::PhantomData;
 717
 718             $(#[allow(bad_style)]
 719             pub struct $name<$tcx> {
 720                 data: PhantomData<&$tcx ()>
 721             })*
 722         }
 723
 724         $(impl<$tcx> QueryConfig for queries::$name<$tcx> {
 725             type Key = $K;
 726             type Value = $V;
 727         }
 728
 729         impl<'a, $tcx, 'lcx> queries::$name<$tcx> {
 730             #[allow(unused)]
 731             fn to_dep_node(tcx: TyCtxt<'a, $tcx, 'lcx>, key: &$K) -> DepNode {
 732                 use dep_graph::DepConstructor::*;
 733
 734                 DepNode::new(tcx, $node(*key))
 735             }
 736
 737             fn try_get_with<F, R>(tcx: TyCtxt<'a, $tcx, 'lcx>,
 738                                   mut span: Span,
 739                                   key: $K,
 740                                   f: F)
 741                                   -> Result<R, CycleError<'a, $tcx>>
 742                 where F: FnOnce(&$V) -> R
 743             {
 744                 debug!("ty::queries::{}::try_get_with(key={:?}, span={:?})",
 745                        stringify!($name),
 746                        key,
 747                        span);
 748
 749                 profq_msg!(tcx,
 750                     ProfileQueriesMsg::QueryBegin(
 751                         span.clone(),
 752                         QueryMsg::$name(profq_key!(tcx, key))
 753                     )
 754                 );
 755
 756                 if let Some(value) = tcx.maps.$name.borrow().map.get(&key) {
 757                     if let Some(ref d) = value.diagnostics {
 758                         if !d.emitted_diagnostics.get() {
 759                             d.emitted_diagnostics.set(true);
 760                             let handle = tcx.sess.diagnostic();
 761                             for diagnostic in d.diagnostics.iter() {
 762                                 DiagnosticBuilder::new_diagnostic(handle, diagnostic.clone())
 763                                     .emit();
 764                             }
 765                         }
 766                     }
 767                     profq_msg!(tcx, ProfileQueriesMsg::CacheHit);
 768                     tcx.dep_graph.read_index(value.index);
 769                     return Ok(f(&value.value));
 770                 }
 771                 // else, we are going to run the provider:
 772                 profq_msg!(tcx, ProfileQueriesMsg::ProviderBegin);
 773
 774                 // FIXME(eddyb) Get more valid Span's on queries.
 775                 // def_span guard is necessary to prevent a recursive loop,
 776                 // default_span calls def_span query internally.
 777                 if span == DUMMY_SP && stringify!($name) != "def_span" {
 778                     span = key.default_span(tcx)
 779                 }
 780
 781                 let res = tcx.cycle_check(span, Query::$name(key), || {
 782                     let dep_node = Self::to_dep_node(tcx, &key);
 783
 784                     tcx.sess.diagnostic().track_diagnostics(|| {
 785                         if dep_node.kind.is_anon() {
 786                             tcx.dep_graph.with_anon_task(dep_node.kind, || {
 787                                 let provider = tcx.maps.providers[key.map_crate()].$name;
 788                                 provider(tcx.global_tcx(), key)
 789                             })
 790                         } else {
 791                             fn run_provider<'a, 'tcx, 'lcx>(tcx: TyCtxt<'a, 'tcx, 'lcx>,
 792                                                             key: $K)
 793                                                             -> $V {
 794                                 let provider = tcx.maps.providers[key.map_crate()].$name;
 795                                 provider(tcx.global_tcx(), key)
 796                             }
 797
 798                             tcx.dep_graph.with_task(dep_node, tcx, key, run_provider)
 799                         }
 800                     })
 801                 })?;
 802                 profq_msg!(tcx, ProfileQueriesMsg::ProviderEnd);
 803                 let ((result, dep_node_index), diagnostics) = res;
 804
 805                 tcx.dep_graph.read_index(dep_node_index);
 806
 807                 let value = QueryValue {
 808                     value: result,
 809                     index: dep_node_index,
 810                     diagnostics: if diagnostics.len() == 0 {
 811                         None
 812                     } else {
 813                         Some(Box::new(QueryDiagnostics {
 814                             diagnostics,
 815                             emitted_diagnostics: Cell::new(true),
 816                         }))
 817                     },
 818                 };
 819
 820                 Ok(f(&tcx.maps
 821                          .$name
 822                          .borrow_mut()
 823                          .map
 824                          .entry(key)
 825                          .or_insert(value)
 826                          .value))
 827             }
 828
 829             pub fn try_get(tcx: TyCtxt<'a, $tcx, 'lcx>, span: Span, key: $K)
 830                            -> Result<$V, DiagnosticBuilder<'a>> {
 831                 match Self::try_get_with(tcx, span, key, Clone::clone) {
 832                     Ok(e) => Ok(e),
 833                     Err(e) => Err(tcx.report_cycle(e)),
 834                 }
 835             }
 836
 837             pub fn force(tcx: TyCtxt<'a, $tcx, 'lcx>, span: Span, key: $K) {
 838                 // Ignore dependencies, since we not reading the computed value
 839                 let _task = tcx.dep_graph.in_ignore();
 840
 841                 match Self::try_get_with(tcx, span, key, |_| ()) {
 842                     Ok(()) => {}
 843                     Err(e) => tcx.report_cycle(e).emit(),
 844                 }
 845             }
 846         })*
 847
 848         #[derive(Copy, Clone)]
 849         pub struct TyCtxtAt<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
 850             pub tcx: TyCtxt<'a, 'gcx, 'tcx>,
 851             pub span: Span,
 852         }
 853
 854         impl<'a, 'gcx, 'tcx> Deref for TyCtxtAt<'a, 'gcx, 'tcx> {
 855             type Target = TyCtxt<'a, 'gcx, 'tcx>;
 856             fn deref(&self) -> &Self::Target {
 857                 &self.tcx
 858             }
 859         }
 860
 861         impl<'a, $tcx, 'lcx> TyCtxt<'a, $tcx, 'lcx> {
 862             /// Return a transparent wrapper for `TyCtxt` which uses
 863             /// `span` as the location of queries performed through it.
 864             pub fn at(self, span: Span) -> TyCtxtAt<'a, $tcx, 'lcx> {
 865                 TyCtxtAt {
 866                     tcx: self,
 867                     span
 868                 }
 869             }
 870
 871             $($(#[$attr])*
 872             pub fn $name(self, key: $K) -> $V {
 873                 self.at(DUMMY_SP).$name(key)
 874             })*
 875         }
 876
 877         impl<'a, $tcx, 'lcx> TyCtxtAt<'a, $tcx, 'lcx> {
 878             $($(#[$attr])*
 879             pub fn $name(self, key: $K) -> $V {
 880                 queries::$name::try_get(self.tcx, self.span, key).unwrap_or_else(|mut e| {
 881                     e.emit();
 882                     Value::from_cycle_error(self.global_tcx())
 883                 })
 884             })*
 885         }
 886
 887         define_provider_struct! {
 888             tcx: $tcx,
 889             input: ($(([$($modifiers)*] [$name] [$K] [$V]))*),
 890             output: ()
 891         }
 892
 893         impl<$tcx> Copy for Providers<$tcx> {}
 894         impl<$tcx> Clone for Providers<$tcx> {
 895             fn clone(&self) -> Self { *self }
 896         }
 897     }
 898 }
 899
 900 macro_rules! define_map_struct {
 901     // Initial state
 902     (tcx: $tcx:tt,
 903      input: $input:tt) => {
 904         define_map_struct! {
 905             tcx: $tcx,
 906             input: $input,
 907             output: ()
 908         }
 909     };
 910
 911     // Final output
 912     (tcx: $tcx:tt,
 913      input: (),
 914      output: ($($output:tt)*)) => {
 915         pub struct Maps<$tcx> {
 916             providers: IndexVec<CrateNum, Providers<$tcx>>,
 917             query_stack: RefCell<Vec<(Span, Query<$tcx>)>>,
 918             $($output)*
 919         }
 920     };
 921
 922     // Field recognized and ready to shift into the output
 923     (tcx: $tcx:tt,
 924      ready: ([$($pub:tt)*] [$($attr:tt)*] [$name:ident]),
 925      input: $input:tt,
 926      output: ($($output:tt)*)) => {
 927         define_map_struct! {
 928             tcx: $tcx,
 929             input: $input,
 930             output: ($($output)*
 931                      $(#[$attr])* $($pub)* $name: RefCell<QueryMap<queries::$name<$tcx>>>,)
 932         }
 933     };
 934
 935     // No modifiers left? This is a private item.
 936     (tcx: $tcx:tt,
 937      input: (([] $attrs:tt $name:tt) $($input:tt)*),
 938      output: $output:tt) => {
 939         define_map_struct! {
 940             tcx: $tcx,
 941             ready: ([] $attrs $name),
 942             input: ($($input)*),
 943             output: $output
 944         }
 945     };
 946
 947     // Skip other modifiers
 948     (tcx: $tcx:tt,
 949      input: (([$other_modifier:tt $($modifiers:tt)*] $($fields:tt)*) $($input:tt)*),
 950      output: $output:tt) => {
 951         define_map_struct! {
 952             tcx: $tcx,
 953             input: (([$($modifiers)*] $($fields)*) $($input)*),
 954             output: $output
 955         }
 956     };
 957 }
 958
 959 macro_rules! define_provider_struct {
 960     // Initial state:
 961     (tcx: $tcx:tt, input: $input:tt) => {
 962         define_provider_struct! {
 963             tcx: $tcx,
 964             input: $input,
 965             output: ()
 966         }
 967     };
 968
 969     // Final state:
 970     (tcx: $tcx:tt,
 971      input: (),
 972      output: ($(([$name:ident] [$K:ty] [$R:ty]))*)) => {
 973         pub struct Providers<$tcx> {
 974             $(pub $name: for<'a> fn(TyCtxt<'a, $tcx, $tcx>, $K) -> $R,)*
 975         }
 976
 977         impl<$tcx> Default for Providers<$tcx> {
 978             fn default() -> Self {
 979                 $(fn $name<'a, $tcx>(_: TyCtxt<'a, $tcx, $tcx>, key: $K) -> $R {
 980                     bug!("tcx.maps.{}({:?}) unsupported by its crate",
 981                          stringify!($name), key);
 982                 })*
 983                 Providers { $($name),* }
 984             }
 985         }
 986     };
 987
 988     // Something ready to shift:
 989     (tcx: $tcx:tt,
 990      ready: ($name:tt $K:tt $V:tt),
 991      input: $input:tt,
 992      output: ($($output:tt)*)) => {
 993         define_provider_struct! {
 994             tcx: $tcx,
 995             input: $input,
 996             output: ($($output)* ($name $K $V))
 997         }
 998     };
 999
1000     // Regular queries produce a `V` only.
1001     (tcx: $tcx:tt,
1002      input: (([] $name:tt $K:tt $V:tt) $($input:tt)*),
1003      output: $output:tt) => {
1004         define_provider_struct! {
1005             tcx: $tcx,
1006             ready: ($name $K $V),
1007             input: ($($input)*),
1008             output: $output
1009         }
1010     };
1011
1012     // Skip modifiers.
1013     (tcx: $tcx:tt,
1014      input: (([$other_modifier:tt $($modifiers:tt)*] $($fields:tt)*) $($input:tt)*),
1015      output: $output:tt) => {
1016         define_provider_struct! {
1017             tcx: $tcx,
1018             input: (([$($modifiers)*] $($fields)*) $($input)*),
1019             output: $output
1020         }
1021     };
1022 }
1023
1024 // Each of these maps also corresponds to a method on a
1025 // `Provider` trait for requesting a value of that type,
1026 // and a method on `Maps` itself for doing that in a
1027 // a way that memoizes and does dep-graph tracking,
1028 // wrapping around the actual chain of providers that
1029 // the driver creates (using several `rustc_*` crates).
1030 define_maps! { <'tcx>
1031     /// Records the type of every item.
1032     [] fn type_of: TypeOfItem(DefId) -> Ty<'tcx>,
1033
1034     /// Maps from the def-id of an item (trait/struct/enum/fn) to its
1035     /// associated generics and predicates.
1036     [] fn generics_of: GenericsOfItem(DefId) -> &'tcx ty::Generics,
1037     [] fn predicates_of: PredicatesOfItem(DefId) -> ty::GenericPredicates<'tcx>,
1038
1039     /// Maps from the def-id of a trait to the list of
1040     /// super-predicates. This is a subset of the full list of
1041     /// predicates. We store these in a separate map because we must
1042     /// evaluate them even during type conversion, often before the
1043     /// full predicates are available (note that supertraits have
1044     /// additional acyclicity requirements).
1045     [] fn super_predicates_of: SuperPredicatesOfItem(DefId) -> ty::GenericPredicates<'tcx>,
1046
1047     /// To avoid cycles within the predicates of a single item we compute
1048     /// per-type-parameter predicates for resolving `T::AssocTy`.
1049     [] fn type_param_predicates: type_param_predicates((DefId, DefId))
1050         -> ty::GenericPredicates<'tcx>,
1051
1052     [] fn trait_def: TraitDefOfItem(DefId) -> &'tcx ty::TraitDef,
1053     [] fn adt_def: AdtDefOfItem(DefId) -> &'tcx ty::AdtDef,
1054     [] fn adt_destructor: AdtDestructor(DefId) -> Option<ty::Destructor>,
1055     [] fn adt_sized_constraint: SizedConstraint(DefId) -> &'tcx [Ty<'tcx>],
1056     [] fn adt_dtorck_constraint: DtorckConstraint(DefId) -> ty::DtorckConstraint<'tcx>,
1057
1058     /// True if this is a const fn
1059     [] fn is_const_fn: IsConstFn(DefId) -> bool,
1060
1061     /// True if this is a foreign item (i.e., linked via `extern { ... }`).
1062     [] fn is_foreign_item: IsForeignItem(DefId) -> bool,
1063
1064     /// True if this is a default impl (aka impl Foo for ..)
1065     [] fn is_default_impl: IsDefaultImpl(DefId) -> bool,
1066
1067     /// Get a map with the variance of every item; use `item_variance`
1068     /// instead.
1069     [] fn crate_variances: crate_variances(CrateNum) -> Rc<ty::CrateVariancesMap>,
1070
1071     /// Maps from def-id of a type or region parameter to its
1072     /// (inferred) variance.
1073     [] fn variances_of: ItemVariances(DefId) -> Rc<Vec<ty::Variance>>,
1074
1075     /// Maps from an impl/trait def-id to a list of the def-ids of its items
1076     [] fn associated_item_def_ids: AssociatedItemDefIds(DefId) -> Rc<Vec<DefId>>,
1077
1078     /// Maps from a trait item to the trait item "descriptor"
1079     [] fn associated_item: AssociatedItems(DefId) -> ty::AssociatedItem,
1080
1081     [] fn impl_trait_ref: ImplTraitRef(DefId) -> Option<ty::TraitRef<'tcx>>,
1082     [] fn impl_polarity: ImplPolarity(DefId) -> hir::ImplPolarity,
1083
1084     /// Maps a DefId of a type to a list of its inherent impls.
1085     /// Contains implementations of methods that are inherent to a type.
1086     /// Methods in these implementations don't need to be exported.
1087     [] fn inherent_impls: InherentImpls(DefId) -> Rc<Vec<DefId>>,
1088
1089     /// Set of all the def-ids in this crate that have MIR associated with
1090     /// them. This includes all the body owners, but also things like struct
1091     /// constructors.
1092     [] fn mir_keys: mir_keys(CrateNum) -> Rc<DefIdSet>,
1093
1094     /// Maps DefId's that have an associated Mir to the result
1095     /// of the MIR qualify_consts pass. The actual meaning of
1096     /// the value isn't known except to the pass itself.
1097     [] fn mir_const_qualif: MirConstQualif(DefId) -> (u8, Rc<IdxSetBuf<mir::Local>>),
1098
1099     /// Fetch the MIR for a given def-id up till the point where it is
1100     /// ready for const evaluation.
1101     ///
1102     /// See the README for the `mir` module for details.
1103     [] fn mir_const: MirConst(DefId) -> &'tcx Steal<mir::Mir<'tcx>>,
1104
1105     [] fn mir_validated: MirValidated(DefId) -> &'tcx Steal<mir::Mir<'tcx>>,
1106
1107     /// MIR after our optimization passes have run. This is MIR that is ready
1108     /// for trans. This is also the only query that can fetch non-local MIR, at present.
1109     [] fn optimized_mir: MirOptimized(DefId) -> &'tcx mir::Mir<'tcx>,
1110
1111     /// Type of each closure. The def ID is the ID of the
1112     /// expression defining the closure.
1113     [] fn closure_kind: ClosureKind(DefId) -> ty::ClosureKind,
1114
1115     /// The signature of functions and closures.
1116     [] fn fn_sig: FnSignature(DefId) -> ty::PolyFnSig<'tcx>,
1117
1118     /// Records the signature of each generator. The def ID is the ID of the
1119     /// expression defining the closure.
1120     [] fn generator_sig: GenSignature(DefId) -> Option<ty::PolyGenSig<'tcx>>,
1121
1122     /// Caches CoerceUnsized kinds for impls on custom types.
1123     [] fn coerce_unsized_info: CoerceUnsizedInfo(DefId)
1124         -> ty::adjustment::CoerceUnsizedInfo,
1125
1126     [] fn typeck_item_bodies: typeck_item_bodies_dep_node(CrateNum) -> CompileResult,
1127
1128     [] fn typeck_tables_of: TypeckTables(DefId) -> &'tcx ty::TypeckTables<'tcx>,
1129
1130     [] fn has_typeck_tables: HasTypeckTables(DefId) -> bool,
1131
1132     [] fn coherent_trait: coherent_trait_dep_node((CrateNum, DefId)) -> (),
1133
1134     [] fn borrowck: BorrowCheck(DefId) -> (),
1135     // FIXME: shouldn't this return a `Result<(), BorrowckErrors>` instead?
1136     [] fn mir_borrowck: MirBorrowCheck(DefId) -> (),
1137
1138     /// Gets a complete map from all types to their inherent impls.
1139     /// Not meant to be used directly outside of coherence.
1140     /// (Defined only for LOCAL_CRATE)
1141     [] fn crate_inherent_impls: crate_inherent_impls_dep_node(CrateNum) -> CrateInherentImpls,
1142
1143     /// Checks all types in the krate for overlap in their inherent impls. Reports errors.
1144     /// Not meant to be used directly outside of coherence.
1145     /// (Defined only for LOCAL_CRATE)
1146     [] fn crate_inherent_impls_overlap_check: inherent_impls_overlap_check_dep_node(CrateNum) -> (),
1147
1148     /// Results of evaluating const items or constants embedded in
1149     /// other items (such as enum variant explicit discriminants).
1150     [] fn const_eval: const_eval_dep_node(ty::ParamEnvAnd<'tcx, (DefId, &'tcx Substs<'tcx>)>)
1151         -> const_val::EvalResult<'tcx>,
1152
1153     /// Performs the privacy check and computes "access levels".
1154     [] fn privacy_access_levels: PrivacyAccessLevels(CrateNum) -> Rc<AccessLevels>,
1155
1156     [] fn reachable_set: reachability_dep_node(CrateNum) -> Rc<NodeSet>,
1157
1158     /// Per-body `region::ScopeTree`. The `DefId` should be the owner-def-id for the body;
1159     /// in the case of closures, this will be redirected to the enclosing function.
1160     [] fn region_scope_tree: RegionScopeTree(DefId) -> Rc<region::ScopeTree>,
1161
1162     [] fn mir_shims: mir_shim_dep_node(ty::InstanceDef<'tcx>) -> &'tcx mir::Mir<'tcx>,
1163
1164     [] fn def_symbol_name: SymbolName(DefId) -> ty::SymbolName,
1165     [] fn symbol_name: symbol_name_dep_node(ty::Instance<'tcx>) -> ty::SymbolName,
1166
1167     [] fn describe_def: DescribeDef(DefId) -> Option<Def>,
1168     [] fn def_span: DefSpan(DefId) -> Span,
1169     [] fn stability: Stability(DefId) -> Option<attr::Stability>,
1170     [] fn deprecation: Deprecation(DefId) -> Option<attr::Deprecation>,
1171     [] fn item_attrs: ItemAttrs(DefId) -> Rc<[ast::Attribute]>,
1172     [] fn fn_arg_names: FnArgNames(DefId) -> Vec<ast::Name>,
1173     [] fn impl_parent: ImplParent(DefId) -> Option<DefId>,
1174     [] fn trait_of_item: TraitOfItem(DefId) -> Option<DefId>,
1175     [] fn is_exported_symbol: IsExportedSymbol(DefId) -> bool,
1176     [] fn item_body_nested_bodies: ItemBodyNestedBodies(DefId)
1177         -> Rc<BTreeMap<hir::BodyId, hir::Body>>,
1178     [] fn const_is_rvalue_promotable_to_static: ConstIsRvaluePromotableToStatic(DefId) -> bool,
1179     [] fn is_mir_available: IsMirAvailable(DefId) -> bool,
1180
1181     [] fn trait_impls_of: TraitImpls(DefId) -> Rc<ty::trait_def::TraitImpls>,
1182     [] fn specialization_graph_of: SpecializationGraph(DefId) -> Rc<specialization_graph::Graph>,
1183     [] fn is_object_safe: ObjectSafety(DefId) -> bool,
1184
1185     // Get the ParameterEnvironment for a given item; this environment
1186     // will be in "user-facing" mode, meaning that it is suitabe for
1187     // type-checking etc, and it does not normalize specializable
1188     // associated types. This is almost always what you want,
1189     // unless you are doing MIR optimizations, in which case you
1190     // might want to use `reveal_all()` method to change modes.
1191     [] fn param_env: ParamEnv(DefId) -> ty::ParamEnv<'tcx>,
1192
1193     // Trait selection queries. These are best used by invoking `ty.moves_by_default()`,
1194     // `ty.is_copy()`, etc, since that will prune the environment where possible.
1195     [] fn is_copy_raw: is_copy_dep_node(ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> bool,
1196     [] fn is_sized_raw: is_sized_dep_node(ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> bool,
1197     [] fn is_freeze_raw: is_freeze_dep_node(ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> bool,
1198     [] fn needs_drop_raw: needs_drop_dep_node(ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> bool,
1199     [] fn layout_raw: layout_dep_node(ty::ParamEnvAnd<'tcx, Ty<'tcx>>)
1200                                   -> Result<&'tcx Layout, LayoutError<'tcx>>,
1201
1202     [] fn dylib_dependency_formats: DylibDepFormats(CrateNum)
1203                                     -> Rc<Vec<(CrateNum, LinkagePreference)>>,
1204
1205     [] fn is_panic_runtime: IsPanicRuntime(CrateNum) -> bool,
1206     [] fn is_compiler_builtins: IsCompilerBuiltins(CrateNum) -> bool,
1207     [] fn has_global_allocator: HasGlobalAllocator(CrateNum) -> bool,
1208     [] fn is_sanitizer_runtime: IsSanitizerRuntime(CrateNum) -> bool,
1209     [] fn is_profiler_runtime: IsProfilerRuntime(CrateNum) -> bool,
1210     [] fn panic_strategy: GetPanicStrategy(CrateNum) -> PanicStrategy,
1211     [] fn is_no_builtins: IsNoBuiltins(CrateNum) -> bool,
1212
1213     [] fn extern_crate: ExternCrate(DefId) -> Rc<Option<ExternCrate>>,
1214
1215     [] fn specializes: specializes_node((DefId, DefId)) -> bool,
1216     [] fn in_scope_traits: InScopeTraits(HirId) -> Option<Rc<Vec<TraitCandidate>>>,
1217     [] fn module_exports: ModuleExports(HirId) -> Option<Rc<Vec<Export>>>,
1218     [] fn lint_levels: lint_levels_node(CrateNum) -> Rc<lint::LintLevelMap>,
1219
1220     [] fn impl_defaultness: ImplDefaultness(DefId) -> hir::Defaultness,
1221     [] fn exported_symbols: ExportedSymbols(CrateNum) -> Rc<Vec<DefId>>,
1222     [] fn native_libraries: NativeLibraries(CrateNum) -> Rc<Vec<NativeLibrary>>,
1223     [] fn plugin_registrar_fn: PluginRegistrarFn(CrateNum) -> Option<DefId>,
1224     [] fn derive_registrar_fn: DeriveRegistrarFn(CrateNum) -> Option<DefId>,
1225     [] fn crate_disambiguator: CrateDisambiguator(CrateNum) -> Symbol,
1226     [] fn crate_hash: CrateHash(CrateNum) -> Svh,
1227     [] fn original_crate_name: OriginalCrateName(CrateNum) -> Symbol,
1228
1229     [] fn implementations_of_trait: implementations_of_trait_node((CrateNum, DefId))
1230         -> Rc<Vec<DefId>>,
1231     [] fn all_trait_implementations: AllTraitImplementations(CrateNum)
1232         -> Rc<Vec<DefId>>,
1233 }
1234
1235 fn type_param_predicates<'tcx>((item_id, param_id): (DefId, DefId)) -> DepConstructor<'tcx> {
1236     DepConstructor::TypeParamPredicates {
1237         item_id,
1238         param_id
1239     }
1240 }
1241
1242 fn coherent_trait_dep_node<'tcx>((_, def_id): (CrateNum, DefId)) -> DepConstructor<'tcx> {
1243     DepConstructor::CoherenceCheckTrait(def_id)
1244 }
1245
1246 fn crate_inherent_impls_dep_node<'tcx>(_: CrateNum) -> DepConstructor<'tcx> {
1247     DepConstructor::Coherence
1248 }
1249
1250 fn inherent_impls_overlap_check_dep_node<'tcx>(_: CrateNum) -> DepConstructor<'tcx> {
1251     DepConstructor::CoherenceInherentImplOverlapCheck
1252 }
1253
1254 fn reachability_dep_node<'tcx>(_: CrateNum) -> DepConstructor<'tcx> {
1255     DepConstructor::Reachability
1256 }
1257
1258 fn mir_shim_dep_node<'tcx>(instance_def: ty::InstanceDef<'tcx>) -> DepConstructor<'tcx> {
1259     DepConstructor::MirShim {
1260         instance_def
1261     }
1262 }
1263
1264 fn symbol_name_dep_node<'tcx>(instance: ty::Instance<'tcx>) -> DepConstructor<'tcx> {
1265     DepConstructor::InstanceSymbolName { instance }
1266 }
1267
1268 fn typeck_item_bodies_dep_node<'tcx>(_: CrateNum) -> DepConstructor<'tcx> {
1269     DepConstructor::TypeckBodiesKrate
1270 }
1271
1272 fn const_eval_dep_node<'tcx>(_: ty::ParamEnvAnd<'tcx, (DefId, &'tcx Substs<'tcx>)>)
1273                              -> DepConstructor<'tcx> {
1274     DepConstructor::ConstEval
1275 }
1276
1277 fn mir_keys<'tcx>(_: CrateNum) -> DepConstructor<'tcx> {
1278     DepConstructor::MirKeys
1279 }
1280
1281 fn crate_variances<'tcx>(_: CrateNum) -> DepConstructor<'tcx> {
1282     DepConstructor::CrateVariances
1283 }
1284
1285 fn is_copy_dep_node<'tcx>(_: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> DepConstructor<'tcx> {
1286     DepConstructor::IsCopy
1287 }
1288
1289 fn is_sized_dep_node<'tcx>(_: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> DepConstructor<'tcx> {
1290     DepConstructor::IsSized
1291 }
1292
1293 fn is_freeze_dep_node<'tcx>(_: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> DepConstructor<'tcx> {
1294     DepConstructor::IsFreeze
1295 }
1296
1297 fn needs_drop_dep_node<'tcx>(_: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> DepConstructor<'tcx> {
1298     DepConstructor::NeedsDrop
1299 }
1300
1301 fn layout_dep_node<'tcx>(_: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> DepConstructor<'tcx> {
1302     DepConstructor::Layout
1303 }
1304
1305 fn lint_levels_node<'tcx>(_: CrateNum) -> DepConstructor<'tcx> {
1306     DepConstructor::LintLevels
1307 }
1308
1309 fn specializes_node<'tcx>((a, b): (DefId, DefId)) -> DepConstructor<'tcx> {
1310     DepConstructor::Specializes { impl1: a, impl2: b }
1311 }
1312
1313 fn implementations_of_trait_node<'tcx>((krate, trait_id): (CrateNum, DefId))
1314     -> DepConstructor<'tcx>
1315 {
1316     DepConstructor::ImplementationsOfTrait { krate, trait_id }
1317 }