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: Default::default(),
  85         inferred_terms: vec![],
  86
  87         lang_items: lang_items(tcx),
  88     };
  89
  90     // See the following for a discussion on dep-graph management.
  91     //
  92     // - https://rust-lang.github.io/rustc-guide/query.html
  93     // - https://rust-lang.github.io/rustc-guide/variance.html
  94     tcx.hir().krate().visit_all_item_likes(&mut terms_cx);
  95
  96     terms_cx
  97 }
  98
  99 fn lang_items(tcx: TyCtxt) -> Vec<(ast::NodeId, Vec<ty::Variance>)> {
 100     let lang_items = tcx.lang_items();
 101     let all = vec![
 102         (lang_items.phantom_data(), vec![ty::Covariant]),
 103         (lang_items.unsafe_cell_type(), vec![ty::Invariant]),
 104         ];
 105
 106     all.into_iter() // iterating over (Option<DefId>, Variance)
 107        .filter(|&(ref d,_)| d.is_some())
 108        .map(|(d, v)| (d.unwrap(), v)) // (DefId, Variance)
 109        .filter_map(|(d, v)| tcx.hir().as_local_node_id(d).map(|n| (n, v))) // (NodeId, Variance)
 110        .collect()
 111 }
 112
 113 impl<'a, 'tcx> TermsContext<'a, 'tcx> {
 114     fn add_inferreds_for_item(&mut self, id: ast::NodeId) {
 115         let tcx = self.tcx;
 116         let def_id = tcx.hir().local_def_id(id);
 117         let count = tcx.generics_of(def_id).count();
 118
 119         if count == 0 {
 120             return;
 121         }
 122
 123         // Record the start of this item's inferreds.
 124         let start = self.inferred_terms.len();
 125         let newly_added = self.inferred_starts.insert(id, InferredIndex(start)).is_none();
 126         assert!(newly_added);
 127
 128         // N.B., in the code below for writing the results back into the
 129         // `CrateVariancesMap`, we rely on the fact that all inferreds
 130         // for a particular item are assigned continuous indices.
 131
 132         let arena = self.arena;
 133         self.inferred_terms.extend((start..start+count).map(|i| {
 134             &*arena.alloc(InferredTerm(InferredIndex(i)))
 135         }));
 136     }
 137 }
 138
 139 impl<'a, 'tcx, 'v> ItemLikeVisitor<'v> for TermsContext<'a, 'tcx> {
 140     fn visit_item(&mut self, item: &hir::Item) {
 141         debug!("add_inferreds for item {}",
 142                self.tcx.hir().node_to_string(item.id));
 143
 144         match item.node {
 145             hir::ItemKind::Struct(ref struct_def, _) |
 146             hir::ItemKind::Union(ref struct_def, _) => {
 147                 self.add_inferreds_for_item(item.id);
 148
 149                 if let hir::VariantData::Tuple(..) = *struct_def {
 150                     self.add_inferreds_for_item(struct_def.id());
 151                 }
 152             }
 153
 154             hir::ItemKind::Enum(ref enum_def, _) => {
 155                 self.add_inferreds_for_item(item.id);
 156
 157                 for variant in &enum_def.variants {
 158                     if let hir::VariantData::Tuple(..) = variant.node.data {
 159                         self.add_inferreds_for_item(variant.node.data.id());
 160                     }
 161                 }
 162             }
 163
 164             hir::ItemKind::Fn(..) => {
 165                 self.add_inferreds_for_item(item.id);
 166             }
 167
 168             hir::ItemKind::ForeignMod(ref foreign_mod) => {
 169                 for foreign_item in &foreign_mod.items {
 170                     if let hir::ForeignItemKind::Fn(..) = foreign_item.node {
 171                         self.add_inferreds_for_item(foreign_item.id);
 172                     }
 173                 }
 174             }
 175
 176             _ => {}
 177         }
 178     }
 179
 180     fn visit_trait_item(&mut self, trait_item: &hir::TraitItem) {
 181         if let hir::TraitItemKind::Method(..) = trait_item.node {
 182             self.add_inferreds_for_item(trait_item.id);
 183         }
 184     }
 185
 186     fn visit_impl_item(&mut self, impl_item: &hir::ImplItem) {
 187         if let hir::ImplItemKind::Method(..) = impl_item.node {
 188             self.add_inferreds_for_item(impl_item.id);
 189         }
 190     }
 191 }