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