src/librustc_typeck/variance/terms.rs

   1 // Representing terms
   2 //
   3 // Terms are structured as a straightforward tree. Rather than rely on
   4 // GC, we allocate terms out of a bounded arena (the lifetime of this
   5 // arena is the lifetime 'a that is threaded around).
   6 //
   7 // We assign a unique index to each type/region parameter whose variance
   8 // is to be inferred. We refer to such variables as "inferreds". An
   9 // `InferredIndex` is a newtype'd int representing the index of such
  10 // a variable.
  11
  12 use arena::TypedArena;
  13 use rustc::hir::itemlikevisit::ItemLikeVisitor;
  14 use rustc::hir::{self, HirIdMap};
  15 use rustc::ty::{self, TyCtxt};
  16 use std::fmt;
  17
  18 use self::VarianceTerm::*;
  19
  20 pub type VarianceTermPtr<'a> = &'a VarianceTerm<'a>;
  21
  22 #[derive(Copy, Clone, Debug)]
  23 pub struct InferredIndex(pub usize);
  24
  25 #[derive(Copy, Clone)]
  26 pub enum VarianceTerm<'a> {
  27     ConstantTerm(ty::Variance),
  28     TransformTerm(VarianceTermPtr<'a>, VarianceTermPtr<'a>),
  29     InferredTerm(InferredIndex),
  30 }
  31
  32 impl<'a> fmt::Debug for VarianceTerm<'a> {
  33     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  34         match *self {
  35             ConstantTerm(c1) => write!(f, "{:?}", c1),
  36             TransformTerm(v1, v2) => write!(f, "({:?} \u{00D7} {:?})", v1, v2),
  37             InferredTerm(id) => write!(f, "[{}]", {
  38                 let InferredIndex(i) = id;
  39                 i
  40             }),
  41         }
  42     }
  43 }
  44
  45 // The first pass over the crate simply builds up the set of inferreds.
  46
  47 pub struct TermsContext<'a, 'tcx> {
  48     pub tcx: TyCtxt<'tcx>,
  49     pub arena: &'a TypedArena<VarianceTerm<'a>>,
  50
  51     // For marker types, UnsafeCell, and other lang items where
  52     // variance is hardcoded, records the item-id and the hardcoded
  53     // variance.
  54     pub lang_items: Vec<(hir::HirId, Vec<ty::Variance>)>,
  55
  56     // Maps from the node id of an item to the first inferred index
  57     // used for its type & region parameters.
  58     pub inferred_starts: HirIdMap<InferredIndex>,
  59
  60     // Maps from an InferredIndex to the term for that variable.
  61     pub inferred_terms: Vec<VarianceTermPtr<'a>>,
  62 }
  63
  64 pub fn determine_parameters_to_be_inferred<'a, 'tcx>(
  65     tcx: TyCtxt<'tcx>,
  66     arena: &'a mut TypedArena<VarianceTerm<'a>>,
  67 ) -> TermsContext<'a, 'tcx> {
  68     let mut terms_cx = TermsContext {
  69         tcx,
  70         arena,
  71         inferred_starts: Default::default(),
  72         inferred_terms: vec![],
  73
  74         lang_items: lang_items(tcx),
  75     };
  76
  77     // See the following for a discussion on dep-graph management.
  78     //
  79     // - https://rust-lang.github.io/rustc-guide/query.html
  80     // - https://rust-lang.github.io/rustc-guide/variance.html
  81     tcx.hir().krate().visit_all_item_likes(&mut terms_cx);
  82
  83     terms_cx
  84 }
  85
  86 fn lang_items(tcx: TyCtxt<'_>) -> Vec<(hir::HirId, Vec<ty::Variance>)> {
  87     let lang_items = tcx.lang_items();
  88     let all = vec![
  89         (lang_items.phantom_data(), vec![ty::Covariant]),
  90         (lang_items.unsafe_cell_type(), vec![ty::Invariant]),
  91     ];
  92
  93     all.into_iter() // iterating over (Option<DefId>, Variance)
  94         .filter(|&(ref d, _)| d.is_some())
  95         .map(|(d, v)| (d.unwrap(), v)) // (DefId, Variance)
  96         .filter_map(|(d, v)| tcx.hir().as_local_hir_id(d).map(|n| (n, v))) // (HirId, Variance)
  97         .collect()
  98 }
  99
 100 impl<'a, 'tcx> TermsContext<'a, 'tcx> {
 101     fn add_inferreds_for_item(&mut self, id: hir::HirId) {
 102         let tcx = self.tcx;
 103         let def_id = tcx.hir().local_def_id(id);
 104         let count = tcx.generics_of(def_id).count();
 105
 106         if count == 0 {
 107             return;
 108         }
 109
 110         // Record the start of this item's inferreds.
 111         let start = self.inferred_terms.len();
 112         let newly_added = self.inferred_starts.insert(id, InferredIndex(start)).is_none();
 113         assert!(newly_added);
 114
 115         // N.B., in the code below for writing the results back into the
 116         // `CrateVariancesMap`, we rely on the fact that all inferreds
 117         // for a particular item are assigned continuous indices.
 118
 119         let arena = self.arena;
 120         self.inferred_terms.extend(
 121             (start..(start + count)).map(|i| &*arena.alloc(InferredTerm(InferredIndex(i)))),
 122         );
 123     }
 124 }
 125
 126 impl<'a, 'tcx, 'v> ItemLikeVisitor<'v> for TermsContext<'a, 'tcx> {
 127     fn visit_item(&mut self, item: &hir::Item<'_>) {
 128         debug!("add_inferreds for item {}", self.tcx.hir().node_to_string(item.hir_id));
 129
 130         match item.kind {
 131             hir::ItemKind::Struct(ref struct_def, _) | hir::ItemKind::Union(ref struct_def, _) => {
 132                 self.add_inferreds_for_item(item.hir_id);
 133
 134                 if let hir::VariantData::Tuple(..) = *struct_def {
 135                     self.add_inferreds_for_item(struct_def.ctor_hir_id().unwrap());
 136                 }
 137             }
 138
 139             hir::ItemKind::Enum(ref enum_def, _) => {
 140                 self.add_inferreds_for_item(item.hir_id);
 141
 142                 for variant in enum_def.variants {
 143                     if let hir::VariantData::Tuple(..) = variant.data {
 144                         self.add_inferreds_for_item(variant.data.ctor_hir_id().unwrap());
 145                     }
 146                 }
 147             }
 148
 149             hir::ItemKind::Fn(..) => {
 150                 self.add_inferreds_for_item(item.hir_id);
 151             }
 152
 153             hir::ItemKind::ForeignMod(ref foreign_mod) => {
 154                 for foreign_item in foreign_mod.items {
 155                     if let hir::ForeignItemKind::Fn(..) = foreign_item.kind {
 156                         self.add_inferreds_for_item(foreign_item.hir_id);
 157                     }
 158                 }
 159             }
 160
 161             _ => {}
 162         }
 163     }
 164
 165     fn visit_trait_item(&mut self, trait_item: &hir::TraitItem<'_>) {
 166         if let hir::TraitItemKind::Method(..) = trait_item.kind {
 167             self.add_inferreds_for_item(trait_item.hir_id);
 168         }
 169     }
 170
 171     fn visit_impl_item(&mut self, impl_item: &hir::ImplItem<'_>) {
 172         if let hir::ImplItemKind::Method(..) = impl_item.kind {
 173             self.add_inferreds_for_item(impl_item.hir_id);
 174         }
 175     }
 176 }