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 dep_graph::DepTrackingMapConfig;
  24 use rustc::ty::{self, TyCtxt};
  25 use rustc::ty::maps::ItemVariances;
  26 use std::fmt;
  27 use std::rc::Rc;
  28 use syntax::ast;
  29 use rustc::hir;
  30 use rustc::hir::intravisit::Visitor;
  31 use util::nodemap::NodeMap;
  32
  33 use self::VarianceTerm::*;
  34
  35 pub type VarianceTermPtr<'a> = &'a VarianceTerm<'a>;
  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) => write!(f, "[{}]", { let InferredIndex(i) = id; i })
  53         }
  54     }
  55 }
  56
  57 // The first pass over the crate simply builds up the set of inferreds.
  58
  59 pub struct TermsContext<'a, 'tcx: 'a> {
  60     pub tcx: TyCtxt<'a, 'tcx, 'tcx>,
  61     pub arena: &'a TypedArena<VarianceTerm<'a>>,
  62
  63     pub empty_variances: Rc<Vec<ty::Variance>>,
  64
  65     // For marker types, UnsafeCell, and other lang items where
  66     // variance is hardcoded, records the item-id and the hardcoded
  67     // variance.
  68     pub lang_items: Vec<(ast::NodeId, Vec<ty::Variance>)>,
  69
  70     // Maps from the node id of a type/generic parameter to the
  71     // corresponding inferred index.
  72     pub inferred_map: NodeMap<InferredIndex>,
  73
  74     // Maps from an InferredIndex to the info for that variable.
  75     pub inferred_infos: Vec<InferredInfo<'a>> ,
  76 }
  77
  78 pub struct InferredInfo<'a> {
  79     pub item_id: ast::NodeId,
  80     pub index: usize,
  81     pub param_id: ast::NodeId,
  82     pub term: VarianceTermPtr<'a>,
  83
  84     // Initial value to use for this parameter when inferring
  85     // variance. For most parameters, this is Bivariant. But for lang
  86     // items and input type parameters on traits, it is different.
  87     pub initial_variance: ty::Variance,
  88 }
  89
  90 pub fn determine_parameters_to_be_inferred<'a, 'tcx>(
  91     tcx: TyCtxt<'a, 'tcx, 'tcx>,
  92     arena: &'a mut TypedArena<VarianceTerm<'a>>)
  93     -> TermsContext<'a, 'tcx>
  94 {
  95     let mut terms_cx = TermsContext {
  96         tcx: tcx,
  97         arena: arena,
  98         inferred_map: NodeMap(),
  99         inferred_infos: Vec::new(),
 100
 101         lang_items: lang_items(tcx),
 102
 103         // cache and share the variance struct used for items with
 104         // no type/region parameters
 105         empty_variances: Rc::new(vec![])
 106     };
 107
 108     // See README.md for a discussion on dep-graph management.
 109     tcx.visit_all_items_in_krate(|def_id| ItemVariances::to_dep_node(&def_id),
 110                                  &mut terms_cx);
 111
 112     terms_cx
 113 }
 114
 115 fn lang_items(tcx: TyCtxt) -> Vec<(ast::NodeId,Vec<ty::Variance>)> {
 116     let all = vec![
 117         (tcx.lang_items.phantom_data(), vec![ty::Covariant]),
 118         (tcx.lang_items.unsafe_cell_type(), vec![ty::Invariant]),
 119
 120         // Deprecated:
 121         (tcx.lang_items.covariant_type(), vec![ty::Covariant]),
 122         (tcx.lang_items.contravariant_type(), vec![ty::Contravariant]),
 123         (tcx.lang_items.invariant_type(), vec![ty::Invariant]),
 124         (tcx.lang_items.covariant_lifetime(), vec![ty::Covariant]),
 125         (tcx.lang_items.contravariant_lifetime(), vec![ty::Contravariant]),
 126         (tcx.lang_items.invariant_lifetime(), vec![ty::Invariant]),
 127
 128         ];
 129
 130     all.into_iter() // iterating over (Option<DefId>, Variance)
 131        .filter(|&(ref d,_)| d.is_some())
 132        .map(|(d, v)| (d.unwrap(), v)) // (DefId, Variance)
 133        .filter_map(|(d, v)| tcx.map.as_local_node_id(d).map(|n| (n, v))) // (NodeId, Variance)
 134        .collect()
 135 }
 136
 137 impl<'a, 'tcx> TermsContext<'a, 'tcx> {
 138     fn add_inferreds_for_item(&mut self,
 139                               item_id: ast::NodeId,
 140                               has_self: bool,
 141                               generics: &hir::Generics)
 142     {
 143         /*!
 144          * Add "inferreds" for the generic parameters declared on this
 145          * item. This has a lot of annoying parameters because we are
 146          * trying to drive this from the AST, rather than the
 147          * ty::Generics, so that we can get span info -- but this
 148          * means we must accommodate syntactic distinctions.
 149          */
 150
 151         // NB: In the code below for writing the results back into the
 152         // tcx, we rely on the fact that all inferreds for a particular
 153         // item are assigned continuous indices.
 154
 155         let inferreds_on_entry = self.num_inferred();
 156
 157         if has_self {
 158             self.add_inferred(item_id, 0, item_id);
 159         }
 160
 161         for (i, p) in generics.lifetimes.iter().enumerate() {
 162             let id = p.lifetime.id;
 163             let i = has_self as usize + i;
 164             self.add_inferred(item_id, i, id);
 165         }
 166
 167         for (i, p) in generics.ty_params.iter().enumerate() {
 168             let i = has_self as usize + generics.lifetimes.len() + i;
 169             self.add_inferred(item_id, i, p.id);
 170         }
 171
 172         // If this item has no type or lifetime parameters,
 173         // then there are no variances to infer, so just
 174         // insert an empty entry into the variance map.
 175         // Arguably we could just leave the map empty in this
 176         // case but it seems cleaner to be able to distinguish
 177         // "invalid item id" from "item id with no
 178         // parameters".
 179         if self.num_inferred() == inferreds_on_entry {
 180             let item_def_id = self.tcx.map.local_def_id(item_id);
 181             let newly_added =
 182                 self.tcx.item_variance_map.borrow_mut().insert(
 183                     item_def_id,
 184                     self.empty_variances.clone()).is_none();
 185             assert!(newly_added);
 186         }
 187     }
 188
 189     fn add_inferred(&mut self,
 190                     item_id: ast::NodeId,
 191                     index: usize,
 192                     param_id: ast::NodeId) {
 193         let inf_index = InferredIndex(self.inferred_infos.len());
 194         let term = self.arena.alloc(InferredTerm(inf_index));
 195         let initial_variance = self.pick_initial_variance(item_id, index);
 196         self.inferred_infos.push(InferredInfo { item_id: item_id,
 197                                                 index: index,
 198                                                 param_id: param_id,
 199                                                 term: term,
 200                                                 initial_variance: initial_variance });
 201         let newly_added = self.inferred_map.insert(param_id, inf_index).is_none();
 202         assert!(newly_added);
 203
 204         debug!("add_inferred(item_path={}, \
 205                 item_id={}, \
 206                 index={}, \
 207                 param_id={}, \
 208                 inf_index={:?}, \
 209                 initial_variance={:?})",
 210                self.tcx.item_path_str(self.tcx.map.local_def_id(item_id)),
 211                item_id, index, param_id, inf_index,
 212                initial_variance);
 213     }
 214
 215     fn pick_initial_variance(&self,
 216                              item_id: ast::NodeId,
 217                              index: usize)
 218                              -> ty::Variance
 219     {
 220         match self.lang_items.iter().find(|&&(n, _)| n == item_id) {
 221             Some(&(_, ref variances)) => variances[index],
 222             None => ty::Bivariant
 223         }
 224     }
 225
 226     pub fn num_inferred(&self) -> usize {
 227         self.inferred_infos.len()
 228     }
 229 }
 230
 231 impl<'a, 'tcx, 'v> Visitor<'v> for TermsContext<'a, 'tcx> {
 232     fn visit_item(&mut self, item: &hir::Item) {
 233         debug!("add_inferreds for item {}", self.tcx.map.node_to_string(item.id));
 234
 235         match item.node {
 236             hir::ItemEnum(_, ref generics) |
 237             hir::ItemStruct(_, ref generics) => {
 238                 self.add_inferreds_for_item(item.id, false, generics);
 239             }
 240             hir::ItemTrait(_, ref generics, _, _) => {
 241                 // Note: all inputs for traits are ultimately
 242                 // constrained to be invariant. See `visit_item` in
 243                 // the impl for `ConstraintContext` in `constraints.rs`.
 244                 self.add_inferreds_for_item(item.id, true, generics);
 245             }
 246
 247             hir::ItemExternCrate(_) |
 248             hir::ItemUse(_) |
 249             hir::ItemDefaultImpl(..) |
 250             hir::ItemImpl(..) |
 251             hir::ItemStatic(..) |
 252             hir::ItemConst(..) |
 253             hir::ItemFn(..) |
 254             hir::ItemMod(..) |
 255             hir::ItemForeignMod(..) |
 256             hir::ItemTy(..) => {
 257             }
 258         }
 259     }
 260 }
 261