src/librustc_trans/trans/monomorphize.rs

   1 // Copyright 2012-2014 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 use back::link::exported_name;
  12 use session;
  13 use llvm::ValueRef;
  14 use llvm;
  15 use middle::infer;
  16 use middle::subst;
  17 use middle::subst::{Subst, Substs};
  18 use middle::traits;
  19 use middle::ty_fold::{TypeFolder, TypeFoldable};
  20 use trans::base::{set_llvm_fn_attrs, set_inline_hint};
  21 use trans::base::{trans_enum_variant, push_ctxt, get_item_val};
  22 use trans::base::{trans_fn, decl_internal_rust_fn};
  23 use trans::base;
  24 use trans::common::*;
  25 use trans::foreign;
  26 use middle::ty::{self, HasProjectionTypes, Ty};
  27 use util::ppaux::Repr;
  28
  29 use syntax::abi;
  30 use syntax::ast;
  31 use syntax::ast_map;
  32 use syntax::ast_util::{local_def, PostExpansionMethod};
  33 use syntax::attr;
  34 use syntax::codemap::DUMMY_SP;
  35 use std::hash::{Hasher, Hash, SipHasher};
  36
  37 pub fn monomorphic_fn<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
  38                                 fn_id: ast::DefId,
  39                                 psubsts: &'tcx subst::Substs<'tcx>,
  40                                 ref_id: Option<ast::NodeId>)
  41     -> (ValueRef, Ty<'tcx>, bool) {
  42     debug!("monomorphic_fn(\
  43             fn_id={}, \
  44             real_substs={}, \
  45             ref_id={:?})",
  46            fn_id.repr(ccx.tcx()),
  47            psubsts.repr(ccx.tcx()),
  48            ref_id);
  49
  50     assert!(psubsts.types.all(|t| {
  51         !ty::type_needs_infer(*t) && !ty::type_has_params(*t)
  52     }));
  53
  54     let _icx = push_ctxt("monomorphic_fn");
  55
  56     let hash_id = MonoId {
  57         def: fn_id,
  58         params: &psubsts.types
  59     };
  60
  61     let item_ty = ty::lookup_item_type(ccx.tcx(), fn_id).ty;
  62     let mono_ty = item_ty.subst(ccx.tcx(), psubsts);
  63
  64     match ccx.monomorphized().borrow().get(&hash_id) {
  65         Some(&val) => {
  66             debug!("leaving monomorphic fn {}",
  67             ty::item_path_str(ccx.tcx(), fn_id));
  68             return (val, mono_ty, false);
  69         }
  70         None => ()
  71     }
  72
  73     debug!("monomorphic_fn(\
  74             fn_id={}, \
  75             psubsts={}, \
  76             hash_id={:?})",
  77            fn_id.repr(ccx.tcx()),
  78            psubsts.repr(ccx.tcx()),
  79            hash_id);
  80
  81
  82     let map_node = session::expect(
  83         ccx.sess(),
  84         ccx.tcx().map.find(fn_id.node),
  85         || {
  86             format!("while monomorphizing {:?}, couldn't find it in \
  87                      the item map (may have attempted to monomorphize \
  88                      an item defined in a different crate?)",
  89                     fn_id)
  90         });
  91
  92     if let ast_map::NodeForeignItem(_) = map_node {
  93         if ccx.tcx().map.get_foreign_abi(fn_id.node) != abi::RustIntrinsic {
  94             // Foreign externs don't have to be monomorphized.
  95             return (get_item_val(ccx, fn_id.node), mono_ty, true);
  96         }
  97     }
  98
  99     debug!("monomorphic_fn about to subst into {}", item_ty.repr(ccx.tcx()));
 100
 101     debug!("mono_ty = {} (post-substitution)", mono_ty.repr(ccx.tcx()));
 102
 103     let mono_ty = normalize_associated_type(ccx.tcx(), &mono_ty);
 104     debug!("mono_ty = {} (post-normalization)", mono_ty.repr(ccx.tcx()));
 105
 106     ccx.stats().n_monos.set(ccx.stats().n_monos.get() + 1);
 107
 108     let depth;
 109     {
 110         let mut monomorphizing = ccx.monomorphizing().borrow_mut();
 111         depth = match monomorphizing.get(&fn_id) {
 112             Some(&d) => d, None => 0
 113         };
 114
 115         // Random cut-off -- code that needs to instantiate the same function
 116         // recursively more than thirty times can probably safely be assumed
 117         // to be causing an infinite expansion.
 118         if depth > ccx.sess().recursion_limit.get() {
 119             ccx.sess().span_fatal(ccx.tcx().map.span(fn_id.node),
 120                 "reached the recursion limit during monomorphization");
 121         }
 122
 123         monomorphizing.insert(fn_id, depth + 1);
 124     }
 125
 126     let hash;
 127     let s = {
 128         let mut state = SipHasher::new();
 129         hash_id.hash(&mut state);
 130         mono_ty.hash(&mut state);
 131
 132         hash = format!("h{}", state.finish());
 133         ccx.tcx().map.with_path(fn_id.node, |path| {
 134             exported_name(path, &hash[..])
 135         })
 136     };
 137
 138     debug!("monomorphize_fn mangled to {}", s);
 139
 140     // This shouldn't need to option dance.
 141     let mut hash_id = Some(hash_id);
 142     let mut mk_lldecl = |abi: abi::Abi| {
 143         let lldecl = if abi != abi::Rust {
 144             foreign::decl_rust_fn_with_foreign_abi(ccx, mono_ty, &s[..])
 145         } else {
 146             decl_internal_rust_fn(ccx, mono_ty, &s[..])
 147         };
 148
 149         ccx.monomorphized().borrow_mut().insert(hash_id.take().unwrap(), lldecl);
 150         lldecl
 151     };
 152     let setup_lldecl = |lldecl, attrs: &[ast::Attribute]| {
 153         base::update_linkage(ccx, lldecl, None, base::OriginalTranslation);
 154         set_llvm_fn_attrs(ccx, attrs, lldecl);
 155
 156         let is_first = !ccx.available_monomorphizations().borrow().contains(&s);
 157         if is_first {
 158             ccx.available_monomorphizations().borrow_mut().insert(s.clone());
 159         }
 160
 161         let trans_everywhere = attr::requests_inline(attrs);
 162         if trans_everywhere && !is_first {
 163             llvm::SetLinkage(lldecl, llvm::AvailableExternallyLinkage);
 164         }
 165
 166         // If `true`, then `lldecl` should be given a function body.
 167         // Otherwise, it should be left as a declaration of an external
 168         // function, with no definition in the current compilation unit.
 169         trans_everywhere || is_first
 170     };
 171
 172     let lldecl = match map_node {
 173         ast_map::NodeItem(i) => {
 174             match *i {
 175               ast::Item {
 176                   node: ast::ItemFn(ref decl, _, abi, _, ref body),
 177                   ..
 178               } => {
 179                   let d = mk_lldecl(abi);
 180                   let needs_body = setup_lldecl(d, &i.attrs[]);
 181                   if needs_body {
 182                       if abi != abi::Rust {
 183                           foreign::trans_rust_fn_with_foreign_abi(
 184                               ccx, &**decl, &**body, &[], d, psubsts, fn_id.node,
 185                               Some(&hash[..]));
 186                       } else {
 187                           trans_fn(ccx, &**decl, &**body, d, psubsts, fn_id.node, &[]);
 188                       }
 189                   }
 190
 191                   d
 192               }
 193               _ => {
 194                 ccx.sess().bug("Can't monomorphize this kind of item")
 195               }
 196             }
 197         }
 198         ast_map::NodeVariant(v) => {
 199             let parent = ccx.tcx().map.get_parent(fn_id.node);
 200             let tvs = ty::enum_variants(ccx.tcx(), local_def(parent));
 201             let this_tv = tvs.iter().find(|tv| { tv.id.node == fn_id.node}).unwrap();
 202             let d = mk_lldecl(abi::Rust);
 203             set_inline_hint(d);
 204             match v.node.kind {
 205                 ast::TupleVariantKind(ref args) => {
 206                     trans_enum_variant(ccx,
 207                                        parent,
 208                                        &*v,
 209                                        &args[..],
 210                                        this_tv.disr_val,
 211                                        psubsts,
 212                                        d);
 213                 }
 214                 ast::StructVariantKind(_) =>
 215                     ccx.sess().bug("can't monomorphize struct variants"),
 216             }
 217             d
 218         }
 219         ast_map::NodeImplItem(ii) => {
 220             match *ii {
 221                 ast::MethodImplItem(ref mth) => {
 222                     let d = mk_lldecl(abi::Rust);
 223                     let needs_body = setup_lldecl(d, &mth.attrs[]);
 224                     if needs_body {
 225                         trans_fn(ccx,
 226                                  mth.pe_fn_decl(),
 227                                  mth.pe_body(),
 228                                  d,
 229                                  psubsts,
 230                                  mth.id,
 231                                  &[]);
 232                     }
 233                     d
 234                 }
 235                 ast::TypeImplItem(_) => {
 236                     ccx.sess().bug("can't monomorphize an associated type")
 237                 }
 238             }
 239         }
 240         ast_map::NodeTraitItem(method) => {
 241             match *method {
 242                 ast::ProvidedMethod(ref mth) => {
 243                     let d = mk_lldecl(abi::Rust);
 244                     let needs_body = setup_lldecl(d, &mth.attrs[]);
 245                     if needs_body {
 246                         trans_fn(ccx, mth.pe_fn_decl(), mth.pe_body(), d,
 247                                  psubsts, mth.id, &[]);
 248                     }
 249                     d
 250                 }
 251                 _ => {
 252                     ccx.sess().bug(&format!("can't monomorphize a {:?}",
 253                                            map_node)[])
 254                 }
 255             }
 256         }
 257         ast_map::NodeStructCtor(struct_def) => {
 258             let d = mk_lldecl(abi::Rust);
 259             set_inline_hint(d);
 260             base::trans_tuple_struct(ccx,
 261                                      &struct_def.fields[],
 262                                      struct_def.ctor_id.expect("ast-mapped tuple struct \
 263                                                                 didn't have a ctor id"),
 264                                      psubsts,
 265                                      d);
 266             d
 267         }
 268
 269         // Ugh -- but this ensures any new variants won't be forgotten
 270         ast_map::NodeForeignItem(..) |
 271         ast_map::NodeLifetime(..) |
 272         ast_map::NodeExpr(..) |
 273         ast_map::NodeStmt(..) |
 274         ast_map::NodeArg(..) |
 275         ast_map::NodeBlock(..) |
 276         ast_map::NodePat(..) |
 277         ast_map::NodeLocal(..) => {
 278             ccx.sess().bug(&format!("can't monomorphize a {:?}",
 279                                    map_node)[])
 280         }
 281     };
 282
 283     ccx.monomorphizing().borrow_mut().insert(fn_id, depth);
 284
 285     debug!("leaving monomorphic fn {}", ty::item_path_str(ccx.tcx(), fn_id));
 286     (lldecl, mono_ty, true)
 287 }
 288
 289 #[derive(PartialEq, Eq, Hash, Debug)]
 290 pub struct MonoId<'tcx> {
 291     pub def: ast::DefId,
 292     pub params: &'tcx subst::VecPerParamSpace<Ty<'tcx>>
 293 }
 294
 295 /// Monomorphizes a type from the AST by first applying the in-scope
 296 /// substitutions and then normalizing any associated types.
 297 pub fn apply_param_substs<'tcx,T>(tcx: &ty::ctxt<'tcx>,
 298                                   param_substs: &Substs<'tcx>,
 299                                   value: &T)
 300                                   -> T
 301     where T : TypeFoldable<'tcx> + Repr<'tcx> + HasProjectionTypes + Clone
 302 {
 303     let substituted = value.subst(tcx, param_substs);
 304     normalize_associated_type(tcx, &substituted)
 305 }
 306
 307 /// Removes associated types, if any. Since this during
 308 /// monomorphization, we know that only concrete types are involved,
 309 /// and hence we can be sure that all associated types will be
 310 /// completely normalized away.
 311 pub fn normalize_associated_type<'tcx,T>(tcx: &ty::ctxt<'tcx>, value: &T) -> T
 312     where T : TypeFoldable<'tcx> + Repr<'tcx> + HasProjectionTypes + Clone
 313 {
 314     debug!("normalize_associated_type(t={})", value.repr(tcx));
 315
 316     let value = erase_regions(tcx, value);
 317
 318     if !value.has_projection_types() {
 319         return value;
 320     }
 321
 322     // FIXME(#20304) -- cache
 323
 324     let infcx = infer::new_infer_ctxt(tcx);
 325     let typer = NormalizingClosureTyper::new(tcx);
 326     let mut selcx = traits::SelectionContext::new(&infcx, &typer);
 327     let cause = traits::ObligationCause::dummy();
 328     let traits::Normalized { value: result, obligations } =
 329         traits::normalize(&mut selcx, cause, &value);
 330
 331     debug!("normalize_associated_type: result={} obligations={}",
 332            result.repr(tcx),
 333            obligations.repr(tcx));
 334
 335     let mut fulfill_cx = traits::FulfillmentContext::new();
 336     for obligation in obligations {
 337         fulfill_cx.register_predicate_obligation(&infcx, obligation);
 338     }
 339     let result = drain_fulfillment_cx(DUMMY_SP, &infcx, &mut fulfill_cx, &result);
 340
 341     result
 342 }