src/librustc_typeck/variance/terms.rs

   1 // Copyright 2013 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 // Representing terms
  12 //
  13 // Terms are structured as a straightforward tree. Rather than rely on
  14 // GC, we allocate terms out of a bounded arena (the lifetime of this
  15 // arena is the lifetime 'a that is threaded around).
  16 //
  17 // We assign a unique index to each type/region parameter whose variance
  18 // is to be inferred. We refer to such variables as "inferreds". An
  19 // `InferredIndex` is a newtype'd int representing the index of such
  20 // a variable.
  21
  22 use arena::TypedArena;
  23 use rustc::ty::{self, TyCtxt};
  24 use std::fmt;
  25 use std::rc::Rc;
  26 use syntax::ast;
  27 use rustc::hir;
  28 use rustc::hir::itemlikevisit::ItemLikeVisitor;
  29 use util::nodemap::NodeMap;
  30
  31 use self::VarianceTerm::*;
  32
  33 pub type VarianceTermPtr<'a> = &'a VarianceTerm<'a>;
  34
  35 use dep_graph::DepNode::ItemSignature as VarianceDepNode;
  36
  37 #[derive(Copy, Clone, Debug)]
  38 pub struct InferredIndex(pub usize);
  39
  40 #[derive(Copy, Clone)]
  41 pub enum VarianceTerm<'a> {
  42     ConstantTerm(ty::Variance),
  43     TransformTerm(VarianceTermPtr<'a>, VarianceTermPtr<'a>),
  44     InferredTerm(InferredIndex),
  45 }
  46
  47 impl<'a> fmt::Debug for VarianceTerm<'a> {
  48     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  49         match *self {
  50             ConstantTerm(c1) => write!(f, "{:?}", c1),
  51             TransformTerm(v1, v2) => write!(f, "({:?} \u{00D7} {:?})", v1, v2),
  52             InferredTerm(id) => {
  53                 write!(f, "[{}]", {
  54                     let InferredIndex(i) = id;
  55                     i
  56                 })
  57             }
  58         }
  59     }
  60 }
  61
  62 // The first pass over the crate simply builds up the set of inferreds.
  63
  64 pub struct TermsContext<'a, 'tcx: 'a> {
  65     pub tcx: TyCtxt<'a, 'tcx, 'tcx>,
  66     pub arena: &'a TypedArena<VarianceTerm<'a>>,
  67
  68     pub empty_variances: Rc<Vec<ty::Variance>>,
  69
  70     // For marker types, UnsafeCell, and other lang items where
  71     // variance is hardcoded, records the item-id and the hardcoded
  72     // variance.
  73     pub lang_items: Vec<(ast::NodeId, Vec<ty::Variance>)>,
  74
  75     // Maps from the node id of a type/generic parameter to the
  76     // corresponding inferred index.
  77     pub inferred_map: NodeMap<InferredIndex>,
  78
  79     // Maps from an InferredIndex to the info for that variable.
  80     pub inferred_infos: Vec<InferredInfo<'a>>,
  81 }
  82
  83 pub struct InferredInfo<'a> {
  84     pub item_id: ast::NodeId,
  85     pub index: usize,
  86     pub param_id: ast::NodeId,
  87     pub term: VarianceTermPtr<'a>,
  88
  89     // Initial value to use for this parameter when inferring
  90     // variance. For most parameters, this is Bivariant. But for lang
  91     // items and input type parameters on traits, it is different.
  92     pub initial_variance: ty::Variance,
  93 }
  94
  95 pub fn determine_parameters_to_be_inferred<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
  96                                                      arena: &'a mut TypedArena<VarianceTerm<'a>>)
  97                                                      -> TermsContext<'a, 'tcx> {
  98     let mut terms_cx = TermsContext {
  99         tcx: tcx,
 100         arena: arena,
 101         inferred_map: NodeMap(),
 102         inferred_infos: Vec::new(),
 103
 104         lang_items: lang_items(tcx),
 105
 106         // cache and share the variance struct used for items with
 107         // no type/region parameters
 108         empty_variances: Rc::new(vec![]),
 109     };
 110
 111     // See README.md for a discussion on dep-graph management.
 112     tcx.visit_all_item_likes_in_krate(|def_id| VarianceDepNode(def_id), &mut terms_cx);
 113
 114     terms_cx
 115 }
 116
 117 fn lang_items(tcx: TyCtxt) -> Vec<(ast::NodeId, Vec<ty::Variance>)> {
 118     let all = vec![
 119         (tcx.lang_items.phantom_data(), vec![ty::Covariant]),
 120         (tcx.lang_items.unsafe_cell_type(), vec![ty::Invariant]),
 121
 122         // Deprecated:
 123         (tcx.lang_items.covariant_type(), vec![ty::Covariant]),
 124         (tcx.lang_items.contravariant_type(), vec![ty::Contravariant]),
 125         (tcx.lang_items.invariant_type(), vec![ty::Invariant]),
 126         (tcx.lang_items.covariant_lifetime(), vec![ty::Covariant]),
 127         (tcx.lang_items.contravariant_lifetime(), vec![ty::Contravariant]),
 128         (tcx.lang_items.invariant_lifetime(), vec![ty::Invariant]),
 129
 130         ];
 131
 132     all.into_iter() // iterating over (Option<DefId>, Variance)
 133        .filter(|&(ref d,_)| d.is_some())
 134        .map(|(d, v)| (d.unwrap(), v)) // (DefId, Variance)
 135        .filter_map(|(d, v)| tcx.hir.as_local_node_id(d).map(|n| (n, v))) // (NodeId, Variance)
 136        .collect()
 137 }
 138
 139 impl<'a, 'tcx> TermsContext<'a, 'tcx> {
 140     fn add_inferreds_for_item(&mut self,
 141                               item_id: ast::NodeId,
 142                               generics: &hir::Generics) {
 143         //! Add "inferreds" for the generic parameters declared on this
 144         //! item. This has a lot of annoying parameters because we are
 145         //! trying to drive this from the AST, rather than the
 146         //! ty::Generics, so that we can get span info -- but this
 147         //! means we must accommodate syntactic distinctions.
 148         //!
 149
 150         // NB: In the code below for writing the results back into the
 151         // `CrateVariancesMap`, we rely on the fact that all inferreds
 152         // for a particular item are assigned continuous indices.
 153
 154         for (p, i) in generics.lifetimes.iter().zip(0..) {
 155             let id = p.lifetime.id;
 156             self.add_inferred(item_id, i, id);
 157         }
 158
 159         for (p, i) in generics.ty_params.iter().zip(generics.lifetimes.len()..) {
 160             self.add_inferred(item_id, i, p.id);
 161         }
 162     }
 163
 164     fn add_inferred(&mut self, item_id: ast::NodeId, index: usize, param_id: ast::NodeId) {
 165         let inf_index = InferredIndex(self.inferred_infos.len());
 166         let term = self.arena.alloc(InferredTerm(inf_index));
 167         let initial_variance = self.pick_initial_variance(item_id, index);
 168         self.inferred_infos.push(InferredInfo {
 169             item_id: item_id,
 170             index: index,
 171             param_id: param_id,
 172             term: term,
 173             initial_variance: initial_variance,
 174         });
 175         let newly_added = self.inferred_map.insert(param_id, inf_index).is_none();
 176         assert!(newly_added);
 177
 178         debug!("add_inferred(item_path={}, \
 179                 item_id={}, \
 180                 index={}, \
 181                 param_id={}, \
 182                 inf_index={:?}, \
 183                 initial_variance={:?})",
 184                self.tcx.item_path_str(self.tcx.hir.local_def_id(item_id)),
 185                item_id,
 186                index,
 187                param_id,
 188                inf_index,
 189                initial_variance);
 190     }
 191
 192     fn pick_initial_variance(&self, item_id: ast::NodeId, index: usize) -> ty::Variance {
 193         match self.lang_items.iter().find(|&&(n, _)| n == item_id) {
 194             Some(&(_, ref variances)) => variances[index],
 195             None => ty::Bivariant,
 196         }
 197     }
 198
 199     pub fn num_inferred(&self) -> usize {
 200         self.inferred_infos.len()
 201     }
 202 }
 203
 204 impl<'a, 'tcx, 'v> ItemLikeVisitor<'v> for TermsContext<'a, 'tcx> {
 205     fn visit_item(&mut self, item: &hir::Item) {
 206         debug!("add_inferreds for item {}",
 207                self.tcx.hir.node_to_string(item.id));
 208
 209         match item.node {
 210             hir::ItemEnum(_, ref generics) |
 211             hir::ItemStruct(_, ref generics) |
 212             hir::ItemUnion(_, ref generics) => {
 213                 self.add_inferreds_for_item(item.id, generics);
 214             }
 215
 216             hir::ItemTrait(..) |
 217             hir::ItemExternCrate(_) |
 218             hir::ItemUse(..) |
 219             hir::ItemDefaultImpl(..) |
 220             hir::ItemImpl(..) |
 221             hir::ItemStatic(..) |
 222             hir::ItemConst(..) |
 223             hir::ItemFn(..) |
 224             hir::ItemMod(..) |
 225             hir::ItemForeignMod(..) |
 226             hir::ItemGlobalAsm(..) |
 227             hir::ItemTy(..) => {}
 228         }
 229     }
 230
 231     fn visit_trait_item(&mut self, _trait_item: &hir::TraitItem) {
 232     }
 233
 234     fn visit_impl_item(&mut self, _impl_item: &hir::ImplItem) {
 235     }
 236 }