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::{DepGraph, DepNode, DepTrackingMap, DepTrackingMapConfig};
  12 use hir::def_id::{CrateNum, DefId, LOCAL_CRATE};
  13 use hir;
  14 use middle::const_val;
  15 use middle::privacy::AccessLevels;
  16 use mir;
  17 use session::CompileResult;
  18 use ty::{self, CrateInherentImpls, Ty, TyCtxt};
  19 use ty::subst::Substs;
  20 use util::nodemap::NodeSet;
  21
  22 use rustc_data_structures::indexed_vec::IndexVec;
  23 use std::cell::{RefCell, RefMut};
  24 use std::ops::Deref;
  25 use std::rc::Rc;
  26 use syntax_pos::{Span, DUMMY_SP};
  27
  28 trait Key {
  29     fn map_crate(&self) -> CrateNum;
  30     fn default_span(&self, tcx: TyCtxt) -> Span;
  31 }
  32
  33 impl<'tcx> Key for ty::InstanceDef<'tcx> {
  34     fn map_crate(&self) -> CrateNum {
  35         LOCAL_CRATE
  36     }
  37
  38     fn default_span(&self, tcx: TyCtxt) -> Span {
  39         tcx.def_span(self.def_id())
  40     }
  41 }
  42
  43 impl Key for CrateNum {
  44     fn map_crate(&self) -> CrateNum {
  45         *self
  46     }
  47     fn default_span(&self, _: TyCtxt) -> Span {
  48         DUMMY_SP
  49     }
  50 }
  51
  52 impl Key for DefId {
  53     fn map_crate(&self) -> CrateNum {
  54         self.krate
  55     }
  56     fn default_span(&self, tcx: TyCtxt) -> Span {
  57         tcx.def_span(*self)
  58     }
  59 }
  60
  61 impl Key for (DefId, DefId) {
  62     fn map_crate(&self) -> CrateNum {
  63         self.0.krate
  64     }
  65     fn default_span(&self, tcx: TyCtxt) -> Span {
  66         self.1.default_span(tcx)
  67     }
  68 }
  69
  70 impl Key for (CrateNum, DefId) {
  71     fn map_crate(&self) -> CrateNum {
  72         self.0
  73     }
  74     fn default_span(&self, tcx: TyCtxt) -> Span {
  75         self.1.default_span(tcx)
  76     }
  77 }
  78
  79 impl<'tcx> Key for (DefId, &'tcx Substs<'tcx>) {
  80     fn map_crate(&self) -> CrateNum {
  81         self.0.krate
  82     }
  83     fn default_span(&self, tcx: TyCtxt) -> Span {
  84         self.0.default_span(tcx)
  85     }
  86 }
  87
  88 trait Value<'tcx>: Sized {
  89     fn from_cycle_error<'a>(tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Self;
  90 }
  91
  92 impl<'tcx, T> Value<'tcx> for T {
  93     default fn from_cycle_error<'a>(tcx: TyCtxt<'a, 'tcx, 'tcx>) -> T {
  94         tcx.sess.abort_if_errors();
  95         bug!("Value::from_cycle_error called without errors");
  96     }
  97 }
  98
  99 impl<'tcx, T: Default> Value<'tcx> for T {
 100     default fn from_cycle_error<'a>(_: TyCtxt<'a, 'tcx, 'tcx>) -> T {
 101         T::default()
 102     }
 103 }
 104
 105 impl<'tcx> Value<'tcx> for Ty<'tcx> {
 106     fn from_cycle_error<'a>(tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Ty<'tcx> {
 107         tcx.types.err
 108     }
 109 }
 110
 111
 112 impl<'tcx> Value<'tcx> for ty::DtorckConstraint<'tcx> {
 113     fn from_cycle_error<'a>(_: TyCtxt<'a, 'tcx, 'tcx>) -> Self {
 114         Self::empty()
 115     }
 116 }
 117
 118 pub struct CycleError<'a, 'tcx: 'a> {
 119     span: Span,
 120     cycle: RefMut<'a, [(Span, Query<'tcx>)]>,
 121 }
 122
 123 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
 124     pub fn report_cycle(self, CycleError { span, cycle }: CycleError) {
 125         assert!(!cycle.is_empty());
 126
 127         let mut err = struct_span_err!(self.sess, span, E0391,
 128             "unsupported cyclic reference between types/traits detected");
 129         err.span_label(span, &format!("cyclic reference"));
 130
 131         err.span_note(cycle[0].0, &format!("the cycle begins when {}...",
 132                                            cycle[0].1.describe(self)));
 133
 134         for &(span, ref query) in &cycle[1..] {
 135             err.span_note(span, &format!("...which then requires {}...",
 136                                          query.describe(self)));
 137         }
 138
 139         err.note(&format!("...which then again requires {}, completing the cycle.",
 140                           cycle[0].1.describe(self)));
 141
 142         err.emit();
 143     }
 144
 145     fn cycle_check<F, R>(self, span: Span, query: Query<'gcx>, compute: F)
 146                          -> Result<R, CycleError<'a, 'gcx>>
 147         where F: FnOnce() -> R
 148     {
 149         {
 150             let mut stack = self.maps.query_stack.borrow_mut();
 151             if let Some((i, _)) = stack.iter().enumerate().rev()
 152                                        .find(|&(_, &(_, ref q))| *q == query) {
 153                 return Err(CycleError {
 154                     span: span,
 155                     cycle: RefMut::map(stack, |stack| &mut stack[i..])
 156                 });
 157             }
 158             stack.push((span, query));
 159         }
 160
 161         let result = compute();
 162
 163         self.maps.query_stack.borrow_mut().pop();
 164
 165         Ok(result)
 166     }
 167 }
 168
 169 trait QueryDescription: DepTrackingMapConfig {
 170     fn describe(tcx: TyCtxt, key: Self::Key) -> String;
 171 }
 172
 173 impl<M: DepTrackingMapConfig<Key=DefId>> QueryDescription for M {
 174     default fn describe(tcx: TyCtxt, def_id: DefId) -> String {
 175         format!("processing `{}`", tcx.item_path_str(def_id))
 176     }
 177 }
 178
 179 impl<'tcx> QueryDescription for queries::super_predicates_of<'tcx> {
 180     fn describe(tcx: TyCtxt, def_id: DefId) -> String {
 181         format!("computing the supertraits of `{}`",
 182                 tcx.item_path_str(def_id))
 183     }
 184 }
 185
 186 impl<'tcx> QueryDescription for queries::type_param_predicates<'tcx> {
 187     fn describe(tcx: TyCtxt, (_, def_id): (DefId, DefId)) -> String {
 188         let id = tcx.hir.as_local_node_id(def_id).unwrap();
 189         format!("computing the bounds for type parameter `{}`",
 190                 tcx.hir.ty_param_name(id))
 191     }
 192 }
 193
 194 impl<'tcx> QueryDescription for queries::coherent_trait<'tcx> {
 195     fn describe(tcx: TyCtxt, (_, def_id): (CrateNum, DefId)) -> String {
 196         format!("coherence checking all impls of trait `{}`",
 197                 tcx.item_path_str(def_id))
 198     }
 199 }
 200
 201 impl<'tcx> QueryDescription for queries::crate_inherent_impls<'tcx> {
 202     fn describe(_: TyCtxt, k: CrateNum) -> String {
 203         format!("all inherent impls defined in crate `{:?}`", k)
 204     }
 205 }
 206
 207 impl<'tcx> QueryDescription for queries::crate_inherent_impls_overlap_check<'tcx> {
 208     fn describe(_: TyCtxt, _: CrateNum) -> String {
 209         format!("check for overlap between inherent impls defined in this crate")
 210     }
 211 }
 212
 213 impl<'tcx> QueryDescription for queries::mir_shims<'tcx> {
 214     fn describe(tcx: TyCtxt, def: ty::InstanceDef<'tcx>) -> String {
 215         format!("generating MIR shim for `{}`",
 216                 tcx.item_path_str(def.def_id()))
 217     }
 218 }
 219
 220 impl<'tcx> QueryDescription for queries::privacy_access_levels<'tcx> {
 221     fn describe(_: TyCtxt, _: CrateNum) -> String {
 222         format!("privacy access levels")
 223     }
 224 }
 225
 226 impl<'tcx> QueryDescription for queries::typeck_item_bodies<'tcx> {
 227     fn describe(_: TyCtxt, _: CrateNum) -> String {
 228         format!("type-checking all item bodies")
 229     }
 230 }
 231
 232 impl<'tcx> QueryDescription for queries::reachable_set<'tcx> {
 233     fn describe(_: TyCtxt, _: CrateNum) -> String {
 234         format!("reachability")
 235     }
 236 }
 237
 238 impl<'tcx> QueryDescription for queries::const_eval<'tcx> {
 239     fn describe(tcx: TyCtxt, (def_id, _): (DefId, &'tcx Substs<'tcx>)) -> String {
 240         format!("const-evaluating `{}`",
 241                 tcx.item_path_str(def_id))
 242     }
 243 }
 244
 245 macro_rules! define_maps {
 246     (<$tcx:tt>
 247      $($(#[$attr:meta])*
 248        pub $name:ident: $node:ident($K:ty) -> $V:ty),*) => {
 249         pub struct Maps<$tcx> {
 250             providers: IndexVec<CrateNum, Providers<$tcx>>,
 251             query_stack: RefCell<Vec<(Span, Query<$tcx>)>>,
 252             $($(#[$attr])* pub $name: RefCell<DepTrackingMap<queries::$name<$tcx>>>),*
 253         }
 254
 255         impl<$tcx> Maps<$tcx> {
 256             pub fn new(dep_graph: DepGraph,
 257                        providers: IndexVec<CrateNum, Providers<$tcx>>)
 258                        -> Self {
 259                 Maps {
 260                     providers,
 261                     query_stack: RefCell::new(vec![]),
 262                     $($name: RefCell::new(DepTrackingMap::new(dep_graph.clone()))),*
 263                 }
 264             }
 265         }
 266
 267         #[allow(bad_style)]
 268         #[derive(Copy, Clone, Debug, PartialEq, Eq)]
 269         pub enum Query<$tcx> {
 270             $($(#[$attr])* $name($K)),*
 271         }
 272
 273         impl<$tcx> Query<$tcx> {
 274             pub fn describe(&self, tcx: TyCtxt) -> String {
 275                 match *self {
 276                     $(Query::$name(key) => queries::$name::describe(tcx, key)),*
 277                 }
 278             }
 279         }
 280
 281         pub mod queries {
 282             use std::marker::PhantomData;
 283
 284             $(#[allow(bad_style)]
 285             pub struct $name<$tcx> {
 286                 data: PhantomData<&$tcx ()>
 287             })*
 288         }
 289
 290         $(impl<$tcx> DepTrackingMapConfig for queries::$name<$tcx> {
 291             type Key = $K;
 292             type Value = $V;
 293
 294             #[allow(unused)]
 295             fn to_dep_node(key: &$K) -> DepNode<DefId> {
 296                 use dep_graph::DepNode::*;
 297
 298                 $node(*key)
 299             }
 300         }
 301         impl<'a, $tcx, 'lcx> queries::$name<$tcx> {
 302             fn try_get_with<F, R>(tcx: TyCtxt<'a, $tcx, 'lcx>,
 303                                   mut span: Span,
 304                                   key: $K,
 305                                   f: F)
 306                                   -> Result<R, CycleError<'a, $tcx>>
 307                 where F: FnOnce(&$V) -> R
 308             {
 309                 if let Some(result) = tcx.maps.$name.borrow().get(&key) {
 310                     return Ok(f(result));
 311                 }
 312
 313                 // FIXME(eddyb) Get more valid Span's on queries.
 314                 if span == DUMMY_SP {
 315                     span = key.default_span(tcx);
 316                 }
 317
 318                 let _task = tcx.dep_graph.in_task(Self::to_dep_node(&key));
 319
 320                 let result = tcx.cycle_check(span, Query::$name(key), || {
 321                     let provider = tcx.maps.providers[key.map_crate()].$name;
 322                     provider(tcx.global_tcx(), key)
 323                 })?;
 324
 325                 Ok(f(&tcx.maps.$name.borrow_mut().entry(key).or_insert(result)))
 326             }
 327
 328             pub fn try_get(tcx: TyCtxt<'a, $tcx, 'lcx>, span: Span, key: $K)
 329                            -> Result<$V, CycleError<'a, $tcx>> {
 330                 Self::try_get_with(tcx, span, key, Clone::clone)
 331             }
 332
 333             pub fn force(tcx: TyCtxt<'a, $tcx, 'lcx>, span: Span, key: $K) {
 334                 // FIXME(eddyb) Move away from using `DepTrackingMap`
 335                 // so we don't have to explicitly ignore a false edge:
 336                 // we can't observe a value dependency, only side-effects,
 337                 // through `force`, and once everything has been updated,
 338                 // perhaps only diagnostics, if those, will remain.
 339                 let _ignore = tcx.dep_graph.in_ignore();
 340                 match Self::try_get_with(tcx, span, key, |_| ()) {
 341                     Ok(()) => {}
 342                     Err(e) => tcx.report_cycle(e)
 343                 }
 344             }
 345         })*
 346
 347         #[derive(Copy, Clone)]
 348         pub struct TyCtxtAt<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
 349             pub tcx: TyCtxt<'a, 'gcx, 'tcx>,
 350             pub span: Span,
 351         }
 352
 353         impl<'a, 'gcx, 'tcx> Deref for TyCtxtAt<'a, 'gcx, 'tcx> {
 354             type Target = TyCtxt<'a, 'gcx, 'tcx>;
 355             fn deref(&self) -> &Self::Target {
 356                 &self.tcx
 357             }
 358         }
 359
 360         impl<'a, $tcx, 'lcx> TyCtxt<'a, $tcx, 'lcx> {
 361             /// Return a transparent wrapper for `TyCtxt` which uses
 362             /// `span` as the location of queries performed through it.
 363             pub fn at(self, span: Span) -> TyCtxtAt<'a, $tcx, 'lcx> {
 364                 TyCtxtAt {
 365                     tcx: self,
 366                     span
 367                 }
 368             }
 369
 370             $($(#[$attr])*
 371             pub fn $name(self, key: $K) -> $V {
 372                 self.at(DUMMY_SP).$name(key)
 373             })*
 374         }
 375
 376         impl<'a, $tcx, 'lcx> TyCtxtAt<'a, $tcx, 'lcx> {
 377             $($(#[$attr])*
 378             pub fn $name(self, key: $K) -> $V {
 379                 queries::$name::try_get(self.tcx, self.span, key).unwrap_or_else(|e| {
 380                     self.report_cycle(e);
 381                     Value::from_cycle_error(self.global_tcx())
 382                 })
 383             })*
 384         }
 385
 386         pub struct Providers<$tcx> {
 387             $(pub $name: for<'a> fn(TyCtxt<'a, $tcx, $tcx>, $K) -> $V),*
 388         }
 389
 390         impl<$tcx> Copy for Providers<$tcx> {}
 391         impl<$tcx> Clone for Providers<$tcx> {
 392             fn clone(&self) -> Self { *self }
 393         }
 394
 395         impl<$tcx> Default for Providers<$tcx> {
 396             fn default() -> Self {
 397                 $(fn $name<'a, $tcx>(_: TyCtxt<'a, $tcx, $tcx>, key: $K) -> $V {
 398                     bug!("tcx.maps.{}({:?}) unsupported by its crate",
 399                          stringify!($name), key);
 400                 })*
 401                 Providers { $($name),* }
 402             }
 403         }
 404     }
 405 }
 406
 407 // Each of these maps also corresponds to a method on a
 408 // `Provider` trait for requesting a value of that type,
 409 // and a method on `Maps` itself for doing that in a
 410 // a way that memoizes and does dep-graph tracking,
 411 // wrapping around the actual chain of providers that
 412 // the driver creates (using several `rustc_*` crates).
 413 define_maps! { <'tcx>
 414     /// Records the type of every item.
 415     pub type_of: ItemSignature(DefId) -> Ty<'tcx>,
 416
 417     /// Maps from the def-id of an item (trait/struct/enum/fn) to its
 418     /// associated generics and predicates.
 419     pub generics_of: ItemSignature(DefId) -> &'tcx ty::Generics,
 420     pub predicates_of: ItemSignature(DefId) -> ty::GenericPredicates<'tcx>,
 421
 422     /// Maps from the def-id of a trait to the list of
 423     /// super-predicates. This is a subset of the full list of
 424     /// predicates. We store these in a separate map because we must
 425     /// evaluate them even during type conversion, often before the
 426     /// full predicates are available (note that supertraits have
 427     /// additional acyclicity requirements).
 428     pub super_predicates_of: ItemSignature(DefId) -> ty::GenericPredicates<'tcx>,
 429
 430     /// To avoid cycles within the predicates of a single item we compute
 431     /// per-type-parameter predicates for resolving `T::AssocTy`.
 432     pub type_param_predicates: TypeParamPredicates((DefId, DefId))
 433         -> ty::GenericPredicates<'tcx>,
 434
 435     pub trait_def: ItemSignature(DefId) -> &'tcx ty::TraitDef,
 436     pub adt_def: ItemSignature(DefId) -> &'tcx ty::AdtDef,
 437     pub adt_destructor: AdtDestructor(DefId) -> Option<ty::Destructor>,
 438     pub adt_sized_constraint: SizedConstraint(DefId) -> &'tcx [Ty<'tcx>],
 439     pub adt_dtorck_constraint: DtorckConstraint(DefId) -> ty::DtorckConstraint<'tcx>,
 440
 441     /// True if this is a foreign item (i.e., linked via `extern { ... }`).
 442     pub is_foreign_item: IsForeignItem(DefId) -> bool,
 443
 444     /// Maps from def-id of a type or region parameter to its
 445     /// (inferred) variance.
 446     pub variances_of: ItemSignature(DefId) -> Rc<Vec<ty::Variance>>,
 447
 448     /// Maps from an impl/trait def-id to a list of the def-ids of its items
 449     pub associated_item_def_ids: AssociatedItemDefIds(DefId) -> Rc<Vec<DefId>>,
 450
 451     /// Maps from a trait item to the trait item "descriptor"
 452     pub associated_item: AssociatedItems(DefId) -> ty::AssociatedItem,
 453
 454     pub impl_trait_ref: ItemSignature(DefId) -> Option<ty::TraitRef<'tcx>>,
 455     pub impl_polarity: ItemSignature(DefId) -> hir::ImplPolarity,
 456
 457     /// Maps a DefId of a type to a list of its inherent impls.
 458     /// Contains implementations of methods that are inherent to a type.
 459     /// Methods in these implementations don't need to be exported.
 460     pub inherent_impls: InherentImpls(DefId) -> Rc<Vec<DefId>>,
 461
 462     /// Maps from the def-id of a function/method or const/static
 463     /// to its MIR. Mutation is done at an item granularity to
 464     /// allow MIR optimization passes to function and still
 465     /// access cross-crate MIR (e.g. inlining or const eval).
 466     ///
 467     /// Note that cross-crate MIR appears to be always borrowed
 468     /// (in the `RefCell` sense) to prevent accidental mutation.
 469     pub mir: Mir(DefId) -> &'tcx RefCell<mir::Mir<'tcx>>,
 470
 471     /// Maps DefId's that have an associated Mir to the result
 472     /// of the MIR qualify_consts pass. The actual meaning of
 473     /// the value isn't known except to the pass itself.
 474     pub mir_const_qualif: Mir(DefId) -> u8,
 475
 476     /// Records the type of each closure. The def ID is the ID of the
 477     /// expression defining the closure.
 478     pub closure_kind: ItemSignature(DefId) -> ty::ClosureKind,
 479
 480     /// Records the type of each closure. The def ID is the ID of the
 481     /// expression defining the closure.
 482     pub closure_type: ItemSignature(DefId) -> ty::PolyFnSig<'tcx>,
 483
 484     /// Caches CoerceUnsized kinds for impls on custom types.
 485     pub coerce_unsized_info: ItemSignature(DefId)
 486         -> ty::adjustment::CoerceUnsizedInfo,
 487
 488     pub typeck_item_bodies: typeck_item_bodies_dep_node(CrateNum) -> CompileResult,
 489
 490     pub typeck_tables_of: TypeckTables(DefId) -> &'tcx ty::TypeckTables<'tcx>,
 491
 492     pub coherent_trait: coherent_trait_dep_node((CrateNum, DefId)) -> (),
 493
 494     pub borrowck: BorrowCheck(DefId) -> (),
 495
 496     /// Gets a complete map from all types to their inherent impls.
 497     /// Not meant to be used directly outside of coherence.
 498     /// (Defined only for LOCAL_CRATE)
 499     pub crate_inherent_impls: crate_inherent_impls_dep_node(CrateNum) -> CrateInherentImpls,
 500
 501     /// Checks all types in the krate for overlap in their inherent impls. Reports errors.
 502     /// Not meant to be used directly outside of coherence.
 503     /// (Defined only for LOCAL_CRATE)
 504     pub crate_inherent_impls_overlap_check: crate_inherent_impls_dep_node(CrateNum) -> (),
 505
 506     /// Results of evaluating const items or constants embedded in
 507     /// other items (such as enum variant explicit discriminants).
 508     pub const_eval: const_eval_dep_node((DefId, &'tcx Substs<'tcx>))
 509         -> const_val::EvalResult<'tcx>,
 510
 511     /// Performs the privacy check and computes "access levels".
 512     pub privacy_access_levels: PrivacyAccessLevels(CrateNum) -> Rc<AccessLevels>,
 513
 514     pub reachable_set: reachability_dep_node(CrateNum) -> Rc<NodeSet>,
 515
 516     pub mir_shims: mir_shim_dep_node(ty::InstanceDef<'tcx>) -> &'tcx RefCell<mir::Mir<'tcx>>
 517 }
 518
 519 fn coherent_trait_dep_node((_, def_id): (CrateNum, DefId)) -> DepNode<DefId> {
 520     DepNode::CoherenceCheckTrait(def_id)
 521 }
 522
 523 fn crate_inherent_impls_dep_node(_: CrateNum) -> DepNode<DefId> {
 524     DepNode::Coherence
 525 }
 526
 527 fn reachability_dep_node(_: CrateNum) -> DepNode<DefId> {
 528     DepNode::Reachability
 529 }
 530
 531 fn mir_shim_dep_node(instance: ty::InstanceDef) -> DepNode<DefId> {
 532     instance.dep_node()
 533 }
 534
 535 fn typeck_item_bodies_dep_node(_: CrateNum) -> DepNode<DefId> {
 536     DepNode::TypeckBodiesKrate
 537 }
 538
 539 fn const_eval_dep_node((def_id, _): (DefId, &Substs)) -> DepNode<DefId> {
 540     DepNode::ConstEval(def_id)
 541 }