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