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