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