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