From 906523efea60f4d58d6ce58bc61589d4ff3d7b4e Mon Sep 17 00:00:00 2001 From: bjorn3 Date: Thu, 19 Oct 2017 11:01:31 +0200 Subject: Move collector to rustc_trans_utils --- src/Cargo.lock | 1 + src/librustc_trans/back/symbol_names.rs | 2 +- src/librustc_trans/base.rs | 30 +- src/librustc_trans/collector.rs | 1061 ----------------------------- src/librustc_trans/common.rs | 17 - src/librustc_trans/lib.rs | 5 +- src/librustc_trans/monomorphize.rs | 136 ---- src/librustc_trans/partitioning.rs | 2 +- src/librustc_trans/trans_item.rs | 417 +----------- src/librustc_trans_utils/Cargo.toml | 1 + src/librustc_trans_utils/collector.rs | 1062 ++++++++++++++++++++++++++++++ src/librustc_trans_utils/common.rs | 78 +++ src/librustc_trans_utils/lib.rs | 5 + src/librustc_trans_utils/monomorphize.rs | 136 ++++ src/librustc_trans_utils/trans_item.rs | 464 +++++++++++++ 15 files changed, 1761 insertions(+), 1656 deletions(-) delete mode 100644 src/librustc_trans/collector.rs delete mode 100644 src/librustc_trans/monomorphize.rs create mode 100644 src/librustc_trans_utils/collector.rs create mode 100644 src/librustc_trans_utils/common.rs create mode 100644 src/librustc_trans_utils/monomorphize.rs create mode 100644 src/librustc_trans_utils/trans_item.rs diff --git a/src/Cargo.lock b/src/Cargo.lock index 328ce353e2a..0989c430df0 100644 --- a/src/Cargo.lock +++ b/src/Cargo.lock @@ -1787,6 +1787,7 @@ dependencies = [ "owning_ref 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)", "rustc 0.0.0", "rustc_back 0.0.0", + "rustc_data_structures 0.0.0", "syntax 0.0.0", "syntax_pos 0.0.0", ] diff --git a/src/librustc_trans/back/symbol_names.rs b/src/librustc_trans/back/symbol_names.rs index 66a27f1c4a9..0ebfe4daad1 100644 --- a/src/librustc_trans/back/symbol_names.rs +++ b/src/librustc_trans/back/symbol_names.rs @@ -98,7 +98,7 @@ //! DefPaths which are much more robust in the face of changes to the code base. use monomorphize::Instance; -use trans_item::{TransItemExt, InstantiationMode}; +use trans_item::{BaseTransItemExt, InstantiationMode}; use rustc::middle::weak_lang_items; use rustc::middle::trans::TransItem; diff --git a/src/librustc_trans/base.rs b/src/librustc_trans/base.rs index 6b53b5b6411..5a3adde8d1d 100644 --- a/src/librustc_trans/base.rs +++ b/src/librustc_trans/base.rs @@ -70,7 +70,7 @@ use monomorphize::{self, Instance}; use partitioning::{self, PartitioningStrategy, CodegenUnit, CodegenUnitExt}; use symbol_names_test; use time_graph; -use trans_item::{TransItem, TransItemExt, DefPathBasedNames}; +use trans_item::{TransItem, BaseTransItemExt, TransItemExt, DefPathBasedNames}; use type_::Type; use type_of; use value::Value; @@ -93,6 +93,7 @@ use syntax::ast; use mir::lvalue::Alignment; pub use rustc_trans_utils::{find_exported_symbols, check_for_rustc_errors_attr}; +pub use rustc_trans_utils::trans_item::linkage_by_name; pub struct StatRecorder<'a, 'tcx: 'a> { ccx: &'a CrateContext<'a, 'tcx>, @@ -618,33 +619,6 @@ pub fn trans_instance<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>, instance: Instance mir::trans_mir(ccx, lldecl, &mir, instance, sig); } -pub fn linkage_by_name(name: &str) -> Option { - use rustc::middle::trans::Linkage::*; - - // Use the names from src/llvm/docs/LangRef.rst here. Most types are only - // applicable to variable declarations and may not really make sense for - // Rust code in the first place but whitelist them anyway and trust that - // the user knows what s/he's doing. Who knows, unanticipated use cases - // may pop up in the future. - // - // ghost, dllimport, dllexport and linkonce_odr_autohide are not supported - // and don't have to be, LLVM treats them as no-ops. - match name { - "appending" => Some(Appending), - "available_externally" => Some(AvailableExternally), - "common" => Some(Common), - "extern_weak" => Some(ExternalWeak), - "external" => Some(External), - "internal" => Some(Internal), - "linkonce" => Some(LinkOnceAny), - "linkonce_odr" => Some(LinkOnceODR), - "private" => Some(Private), - "weak" => Some(WeakAny), - "weak_odr" => Some(WeakODR), - _ => None, - } -} - pub fn set_link_section(ccx: &CrateContext, llval: ValueRef, attrs: &[ast::Attribute]) { diff --git a/src/librustc_trans/collector.rs b/src/librustc_trans/collector.rs deleted file mode 100644 index 33a2e96ee66..00000000000 --- a/src/librustc_trans/collector.rs +++ /dev/null @@ -1,1061 +0,0 @@ -// Copyright 2014 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 or the MIT license -// , at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -//! Translation Item Collection -//! =========================== -//! -//! This module is responsible for discovering all items that will contribute to -//! to code generation of the crate. The important part here is that it not only -//! needs to find syntax-level items (functions, structs, etc) but also all -//! their monomorphized instantiations. Every non-generic, non-const function -//! maps to one LLVM artifact. Every generic function can produce -//! from zero to N artifacts, depending on the sets of type arguments it -//! is instantiated with. -//! This also applies to generic items from other crates: A generic definition -//! in crate X might produce monomorphizations that are compiled into crate Y. -//! We also have to collect these here. -//! -//! The following kinds of "translation items" are handled here: -//! -//! - Functions -//! - Methods -//! - Closures -//! - Statics -//! - Drop glue -//! -//! The following things also result in LLVM artifacts, but are not collected -//! here, since we instantiate them locally on demand when needed in a given -//! codegen unit: -//! -//! - Constants -//! - Vtables -//! - Object Shims -//! -//! -//! General Algorithm -//! ----------------- -//! Let's define some terms first: -//! -//! - A "translation item" is something that results in a function or global in -//! the LLVM IR of a codegen unit. Translation items do not stand on their -//! own, they can reference other translation items. For example, if function -//! `foo()` calls function `bar()` then the translation item for `foo()` -//! references the translation item for function `bar()`. In general, the -//! definition for translation item A referencing a translation item B is that -//! the LLVM artifact produced for A references the LLVM artifact produced -//! for B. -//! -//! - Translation items and the references between them form a directed graph, -//! where the translation items are the nodes and references form the edges. -//! Let's call this graph the "translation item graph". -//! -//! - The translation item graph for a program contains all translation items -//! that are needed in order to produce the complete LLVM IR of the program. -//! -//! The purpose of the algorithm implemented in this module is to build the -//! translation item graph for the current crate. It runs in two phases: -//! -//! 1. Discover the roots of the graph by traversing the HIR of the crate. -//! 2. Starting from the roots, find neighboring nodes by inspecting the MIR -//! representation of the item corresponding to a given node, until no more -//! new nodes are found. -//! -//! ### Discovering roots -//! -//! The roots of the translation item graph correspond to the non-generic -//! syntactic items in the source code. We find them by walking the HIR of the -//! crate, and whenever we hit upon a function, method, or static item, we -//! create a translation item consisting of the items DefId and, since we only -//! consider non-generic items, an empty type-substitution set. -//! -//! ### Finding neighbor nodes -//! Given a translation item node, we can discover neighbors by inspecting its -//! MIR. We walk the MIR and any time we hit upon something that signifies a -//! reference to another translation item, we have found a neighbor. Since the -//! translation item we are currently at is always monomorphic, we also know the -//! concrete type arguments of its neighbors, and so all neighbors again will be -//! monomorphic. The specific forms a reference to a neighboring node can take -//! in MIR are quite diverse. Here is an overview: -//! -//! #### Calling Functions/Methods -//! The most obvious form of one translation item referencing another is a -//! function or method call (represented by a CALL terminator in MIR). But -//! calls are not the only thing that might introduce a reference between two -//! function translation items, and as we will see below, they are just a -//! specialized of the form described next, and consequently will don't get any -//! special treatment in the algorithm. -//! -//! #### Taking a reference to a function or method -//! A function does not need to actually be called in order to be a neighbor of -//! another function. It suffices to just take a reference in order to introduce -//! an edge. Consider the following example: -//! -//! ```rust -//! fn print_val(x: T) { -//! println!("{}", x); -//! } -//! -//! fn call_fn(f: &Fn(i32), x: i32) { -//! f(x); -//! } -//! -//! fn main() { -//! let print_i32 = print_val::; -//! call_fn(&print_i32, 0); -//! } -//! ``` -//! The MIR of none of these functions will contain an explicit call to -//! `print_val::`. Nonetheless, in order to translate this program, we need -//! an instance of this function. Thus, whenever we encounter a function or -//! method in operand position, we treat it as a neighbor of the current -//! translation item. Calls are just a special case of that. -//! -//! #### Closures -//! In a way, closures are a simple case. Since every closure object needs to be -//! constructed somewhere, we can reliably discover them by observing -//! `RValue::Aggregate` expressions with `AggregateKind::Closure`. This is also -//! true for closures inlined from other crates. -//! -//! #### Drop glue -//! Drop glue translation items are introduced by MIR drop-statements. The -//! generated translation item will again have drop-glue item neighbors if the -//! type to be dropped contains nested values that also need to be dropped. It -//! might also have a function item neighbor for the explicit `Drop::drop` -//! implementation of its type. -//! -//! #### Unsizing Casts -//! A subtle way of introducing neighbor edges is by casting to a trait object. -//! Since the resulting fat-pointer contains a reference to a vtable, we need to -//! instantiate all object-save methods of the trait, as we need to store -//! pointers to these functions even if they never get called anywhere. This can -//! be seen as a special case of taking a function reference. -//! -//! #### Boxes -//! Since `Box` expression have special compiler support, no explicit calls to -//! `exchange_malloc()` and `exchange_free()` may show up in MIR, even if the -//! compiler will generate them. We have to observe `Rvalue::Box` expressions -//! and Box-typed drop-statements for that purpose. -//! -//! -//! Interaction with Cross-Crate Inlining -//! ------------------------------------- -//! The binary of a crate will not only contain machine code for the items -//! defined in the source code of that crate. It will also contain monomorphic -//! instantiations of any extern generic functions and of functions marked with -//! #[inline]. -//! The collection algorithm handles this more or less transparently. If it is -//! about to create a translation item for something with an external `DefId`, -//! it will take a look if the MIR for that item is available, and if so just -//! proceed normally. If the MIR is not available, it assumes that the item is -//! just linked to and no node is created; which is exactly what we want, since -//! no machine code should be generated in the current crate for such an item. -//! -//! Eager and Lazy Collection Mode -//! ------------------------------ -//! Translation item collection can be performed in one of two modes: -//! -//! - Lazy mode means that items will only be instantiated when actually -//! referenced. The goal is to produce the least amount of machine code -//! possible. -//! -//! - Eager mode is meant to be used in conjunction with incremental compilation -//! where a stable set of translation items is more important than a minimal -//! one. Thus, eager mode will instantiate drop-glue for every drop-able type -//! in the crate, even of no drop call for that type exists (yet). It will -//! also instantiate default implementations of trait methods, something that -//! otherwise is only done on demand. -//! -//! -//! Open Issues -//! ----------- -//! Some things are not yet fully implemented in the current version of this -//! module. -//! -//! ### Initializers of Constants and Statics -//! Since no MIR is constructed yet for initializer expressions of constants and -//! statics we cannot inspect these properly. -//! -//! ### Const Fns -//! Ideally, no translation item should be generated for const fns unless there -//! is a call to them that cannot be evaluated at compile time. At the moment -//! this is not implemented however: a translation item will be produced -//! regardless of whether it is actually needed or not. - -use rustc::hir; -use rustc::hir::itemlikevisit::ItemLikeVisitor; - -use rustc::hir::map as hir_map; -use rustc::hir::def_id::DefId; -use rustc::middle::const_val::ConstVal; -use rustc::middle::lang_items::{ExchangeMallocFnLangItem}; -use rustc::traits; -use rustc::ty::subst::Substs; -use rustc::ty::{self, TypeFoldable, Ty, TyCtxt}; -use rustc::ty::adjustment::CustomCoerceUnsized; -use rustc::mir::{self, Location}; -use rustc::mir::visit::Visitor as MirVisitor; - -use common::{def_ty, instance_ty, type_is_sized}; -use monomorphize::{self, Instance}; -use rustc::util::nodemap::{FxHashSet, FxHashMap, DefIdMap}; - -use trans_item::{TransItem, TransItemExt, DefPathBasedNames, InstantiationMode}; - -use rustc_data_structures::bitvec::BitVector; - -#[derive(PartialEq, Eq, Hash, Clone, Copy, Debug)] -pub enum TransItemCollectionMode { - Eager, - Lazy -} - -/// Maps every translation item to all translation items it references in its -/// body. -pub struct InliningMap<'tcx> { - // Maps a source translation item to the range of translation items - // accessed by it. - // The two numbers in the tuple are the start (inclusive) and - // end index (exclusive) within the `targets` vecs. - index: FxHashMap, (usize, usize)>, - targets: Vec>, - - // Contains one bit per translation item in the `targets` field. That bit - // is true if that translation item needs to be inlined into every CGU. - inlines: BitVector, -} - -impl<'tcx> InliningMap<'tcx> { - - fn new() -> InliningMap<'tcx> { - InliningMap { - index: FxHashMap(), - targets: Vec::new(), - inlines: BitVector::new(1024), - } - } - - fn record_accesses(&mut self, - source: TransItem<'tcx>, - new_targets: I) - where I: Iterator, bool)> + ExactSizeIterator - { - assert!(!self.index.contains_key(&source)); - - let start_index = self.targets.len(); - let new_items_count = new_targets.len(); - let new_items_count_total = new_items_count + self.targets.len(); - - self.targets.reserve(new_items_count); - self.inlines.grow(new_items_count_total); - - for (i, (target, inline)) in new_targets.enumerate() { - self.targets.push(target); - if inline { - self.inlines.insert(i + start_index); - } - } - - let end_index = self.targets.len(); - self.index.insert(source, (start_index, end_index)); - } - - // Internally iterate over all items referenced by `source` which will be - // made available for inlining. - pub fn with_inlining_candidates(&self, source: TransItem<'tcx>, mut f: F) - where F: FnMut(TransItem<'tcx>) - { - if let Some(&(start_index, end_index)) = self.index.get(&source) { - for (i, candidate) in self.targets[start_index .. end_index] - .iter() - .enumerate() { - if self.inlines.contains(start_index + i) { - f(*candidate); - } - } - } - } - - // Internally iterate over all items and the things each accesses. - pub fn iter_accesses(&self, mut f: F) - where F: FnMut(TransItem<'tcx>, &[TransItem<'tcx>]) - { - for (&accessor, &(start_index, end_index)) in &self.index { - f(accessor, &self.targets[start_index .. end_index]) - } - } -} - -pub fn collect_crate_translation_items<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, - mode: TransItemCollectionMode) - -> (FxHashSet>, - InliningMap<'tcx>) { - let roots = collect_roots(tcx, mode); - - debug!("Building translation item graph, beginning at roots"); - let mut visited = FxHashSet(); - let mut recursion_depths = DefIdMap(); - let mut inlining_map = InliningMap::new(); - - for root in roots { - collect_items_rec(tcx, - root, - &mut visited, - &mut recursion_depths, - &mut inlining_map); - } - - (visited, inlining_map) -} - -// Find all non-generic items by walking the HIR. These items serve as roots to -// start monomorphizing from. -fn collect_roots<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, - mode: TransItemCollectionMode) - -> Vec> { - debug!("Collecting roots"); - let mut roots = Vec::new(); - - { - let mut visitor = RootCollector { - tcx, - mode, - output: &mut roots, - }; - - tcx.hir.krate().visit_all_item_likes(&mut visitor); - } - - // We can only translate items that are instantiable - items all of - // whose predicates hold. Luckily, items that aren't instantiable - // can't actually be used, so we can just skip translating them. - roots.retain(|root| root.is_instantiable(tcx)); - - roots -} - -// Collect all monomorphized translation items reachable from `starting_point` -fn collect_items_rec<'a, 'tcx: 'a>(tcx: TyCtxt<'a, 'tcx, 'tcx>, - starting_point: TransItem<'tcx>, - visited: &mut FxHashSet>, - recursion_depths: &mut DefIdMap, - inlining_map: &mut InliningMap<'tcx>) { - if !visited.insert(starting_point.clone()) { - // We've been here already, no need to search again. - return; - } - debug!("BEGIN collect_items_rec({})", starting_point.to_string(tcx)); - - let mut neighbors = Vec::new(); - let recursion_depth_reset; - - match starting_point { - TransItem::Static(node_id) => { - let def_id = tcx.hir.local_def_id(node_id); - let instance = Instance::mono(tcx, def_id); - - // Sanity check whether this ended up being collected accidentally - debug_assert!(should_trans_locally(tcx, &instance)); - - let ty = instance_ty(tcx, &instance); - visit_drop_use(tcx, ty, true, &mut neighbors); - - recursion_depth_reset = None; - - collect_neighbours(tcx, instance, true, &mut neighbors); - } - TransItem::Fn(instance) => { - // Sanity check whether this ended up being collected accidentally - debug_assert!(should_trans_locally(tcx, &instance)); - - // Keep track of the monomorphization recursion depth - recursion_depth_reset = Some(check_recursion_limit(tcx, - instance, - recursion_depths)); - check_type_length_limit(tcx, instance); - - collect_neighbours(tcx, instance, false, &mut neighbors); - } - TransItem::GlobalAsm(..) => { - recursion_depth_reset = None; - } - } - - record_accesses(tcx, starting_point, &neighbors[..], inlining_map); - - for neighbour in neighbors { - collect_items_rec(tcx, neighbour, visited, recursion_depths, inlining_map); - } - - if let Some((def_id, depth)) = recursion_depth_reset { - recursion_depths.insert(def_id, depth); - } - - debug!("END collect_items_rec({})", starting_point.to_string(tcx)); -} - -fn record_accesses<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, - caller: TransItem<'tcx>, - callees: &[TransItem<'tcx>], - inlining_map: &mut InliningMap<'tcx>) { - let is_inlining_candidate = |trans_item: &TransItem<'tcx>| { - trans_item.instantiation_mode(tcx) == InstantiationMode::LocalCopy - }; - - let accesses = callees.into_iter() - .map(|trans_item| { - (*trans_item, is_inlining_candidate(trans_item)) - }); - - inlining_map.record_accesses(caller, accesses); -} - -fn check_recursion_limit<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, - instance: Instance<'tcx>, - recursion_depths: &mut DefIdMap) - -> (DefId, usize) { - let def_id = instance.def_id(); - let recursion_depth = recursion_depths.get(&def_id).cloned().unwrap_or(0); - debug!(" => recursion depth={}", recursion_depth); - - let recursion_depth = if Some(def_id) == tcx.lang_items().drop_in_place_fn() { - // HACK: drop_in_place creates tight monomorphization loops. Give - // it more margin. - recursion_depth / 4 - } else { - recursion_depth - }; - - // Code that needs to instantiate the same function recursively - // more than the recursion limit is assumed to be causing an - // infinite expansion. - if recursion_depth > tcx.sess.recursion_limit.get() { - let error = format!("reached the recursion limit while instantiating `{}`", - instance); - if let Some(node_id) = tcx.hir.as_local_node_id(def_id) { - tcx.sess.span_fatal(tcx.hir.span(node_id), &error); - } else { - tcx.sess.fatal(&error); - } - } - - recursion_depths.insert(def_id, recursion_depth + 1); - - (def_id, recursion_depth) -} - -fn check_type_length_limit<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, - instance: Instance<'tcx>) -{ - let type_length = instance.substs.types().flat_map(|ty| ty.walk()).count(); - debug!(" => type length={}", type_length); - - // Rust code can easily create exponentially-long types using only a - // polynomial recursion depth. Even with the default recursion - // depth, you can easily get cases that take >2^60 steps to run, - // which means that rustc basically hangs. - // - // Bail out in these cases to avoid that bad user experience. - let type_length_limit = tcx.sess.type_length_limit.get(); - if type_length > type_length_limit { - // The instance name is already known to be too long for rustc. Use - // `{:.64}` to avoid blasting the user's terminal with thousands of - // lines of type-name. - let instance_name = instance.to_string(); - let msg = format!("reached the type-length limit while instantiating `{:.64}...`", - instance_name); - let mut diag = if let Some(node_id) = tcx.hir.as_local_node_id(instance.def_id()) { - tcx.sess.struct_span_fatal(tcx.hir.span(node_id), &msg) - } else { - tcx.sess.struct_fatal(&msg) - }; - - diag.note(&format!( - "consider adding a `#![type_length_limit=\"{}\"]` attribute to your crate", - type_length_limit*2)); - diag.emit(); - tcx.sess.abort_if_errors(); - } -} - -struct MirNeighborCollector<'a, 'tcx: 'a> { - tcx: TyCtxt<'a, 'tcx, 'tcx>, - mir: &'a mir::Mir<'tcx>, - output: &'a mut Vec>, - param_substs: &'tcx Substs<'tcx>, - const_context: bool, -} - -impl<'a, 'tcx> MirVisitor<'tcx> for MirNeighborCollector<'a, 'tcx> { - - fn visit_rvalue(&mut self, rvalue: &mir::Rvalue<'tcx>, location: Location) { - debug!("visiting rvalue {:?}", *rvalue); - - match *rvalue { - // When doing an cast from a regular pointer to a fat pointer, we - // have to instantiate all methods of the trait being cast to, so we - // can build the appropriate vtable. - mir::Rvalue::Cast(mir::CastKind::Unsize, ref operand, target_ty) => { - let target_ty = self.tcx.trans_apply_param_substs(self.param_substs, - &target_ty); - let source_ty = operand.ty(self.mir, self.tcx); - let source_ty = self.tcx.trans_apply_param_substs(self.param_substs, - &source_ty); - let (source_ty, target_ty) = find_vtable_types_for_unsizing(self.tcx, - source_ty, - target_ty); - // This could also be a different Unsize instruction, like - // from a fixed sized array to a slice. But we are only - // interested in things that produce a vtable. - if target_ty.is_trait() && !source_ty.is_trait() { - create_trans_items_for_vtable_methods(self.tcx, - target_ty, - source_ty, - self.output); - } - } - mir::Rvalue::Cast(mir::CastKind::ReifyFnPointer, ref operand, _) => { - let fn_ty = operand.ty(self.mir, self.tcx); - let fn_ty = self.tcx.trans_apply_param_substs(self.param_substs, - &fn_ty); - visit_fn_use(self.tcx, fn_ty, false, &mut self.output); - } - mir::Rvalue::Cast(mir::CastKind::ClosureFnPointer, ref operand, _) => { - let source_ty = operand.ty(self.mir, self.tcx); - let source_ty = self.tcx.trans_apply_param_substs(self.param_substs, - &source_ty); - match source_ty.sty { - ty::TyClosure(def_id, substs) => { - let instance = monomorphize::resolve_closure( - self.tcx, def_id, substs, ty::ClosureKind::FnOnce); - self.output.push(create_fn_trans_item(instance)); - } - _ => bug!(), - } - } - mir::Rvalue::NullaryOp(mir::NullOp::Box, _) => { - let tcx = self.tcx; - let exchange_malloc_fn_def_id = tcx - .lang_items() - .require(ExchangeMallocFnLangItem) - .unwrap_or_else(|e| tcx.sess.fatal(&e)); - let instance = Instance::mono(tcx, exchange_malloc_fn_def_id); - if should_trans_locally(tcx, &instance) { - self.output.push(create_fn_trans_item(instance)); - } - } - _ => { /* not interesting */ } - } - - self.super_rvalue(rvalue, location); - } - - fn visit_const(&mut self, constant: &&'tcx ty::Const<'tcx>, location: Location) { - debug!("visiting const {:?} @ {:?}", *constant, location); - - if let ConstVal::Unevaluated(def_id, substs) = constant.val { - let substs = self.tcx.trans_apply_param_substs(self.param_substs, - &substs); - let instance = ty::Instance::resolve(self.tcx, - ty::ParamEnv::empty(traits::Reveal::All), - def_id, - substs).unwrap(); - collect_neighbours(self.tcx, instance, true, self.output); - } - - self.super_const(constant); - } - - fn visit_terminator_kind(&mut self, - block: mir::BasicBlock, - kind: &mir::TerminatorKind<'tcx>, - location: Location) { - debug!("visiting terminator {:?} @ {:?}", kind, location); - - let tcx = self.tcx; - match *kind { - mir::TerminatorKind::Call { ref func, .. } => { - let callee_ty = func.ty(self.mir, tcx); - let callee_ty = tcx.trans_apply_param_substs(self.param_substs, &callee_ty); - - let constness = match (self.const_context, &callee_ty.sty) { - (true, &ty::TyFnDef(def_id, substs)) if self.tcx.is_const_fn(def_id) => { - let instance = - ty::Instance::resolve(self.tcx, - ty::ParamEnv::empty(traits::Reveal::All), - def_id, - substs).unwrap(); - Some(instance) - } - _ => None - }; - - if let Some(const_fn_instance) = constness { - // If this is a const fn, called from a const context, we - // have to visit its body in order to find any fn reifications - // it might contain. - collect_neighbours(self.tcx, - const_fn_instance, - true, - self.output); - } else { - visit_fn_use(self.tcx, callee_ty, true, &mut self.output); - } - } - mir::TerminatorKind::Drop { ref location, .. } | - mir::TerminatorKind::DropAndReplace { ref location, .. } => { - let ty = location.ty(self.mir, self.tcx) - .to_ty(self.tcx); - let ty = tcx.trans_apply_param_substs(self.param_substs, &ty); - visit_drop_use(self.tcx, ty, true, self.output); - } - mir::TerminatorKind::Goto { .. } | - mir::TerminatorKind::SwitchInt { .. } | - mir::TerminatorKind::Resume | - mir::TerminatorKind::Return | - mir::TerminatorKind::Unreachable | - mir::TerminatorKind::Assert { .. } => {} - mir::TerminatorKind::GeneratorDrop | - mir::TerminatorKind::Yield { .. } => bug!(), - } - - self.super_terminator_kind(block, kind, location); - } - - fn visit_static(&mut self, - static_: &mir::Static<'tcx>, - context: mir::visit::LvalueContext<'tcx>, - location: Location) { - debug!("visiting static {:?} @ {:?}", static_.def_id, location); - - let tcx = self.tcx; - let instance = Instance::mono(tcx, static_.def_id); - if should_trans_locally(tcx, &instance) { - let node_id = tcx.hir.as_local_node_id(static_.def_id).unwrap(); - self.output.push(TransItem::Static(node_id)); - } - - self.super_static(static_, context, location); - } -} - -fn visit_drop_use<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, - ty: Ty<'tcx>, - is_direct_call: bool, - output: &mut Vec>) -{ - let instance = monomorphize::resolve_drop_in_place(tcx, ty); - visit_instance_use(tcx, instance, is_direct_call, output); -} - -fn visit_fn_use<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, - ty: Ty<'tcx>, - is_direct_call: bool, - output: &mut Vec>) -{ - if let ty::TyFnDef(def_id, substs) = ty.sty { - let instance = ty::Instance::resolve(tcx, - ty::ParamEnv::empty(traits::Reveal::All), - def_id, - substs).unwrap(); - visit_instance_use(tcx, instance, is_direct_call, output); - } -} - -fn visit_instance_use<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, - instance: ty::Instance<'tcx>, - is_direct_call: bool, - output: &mut Vec>) -{ - debug!("visit_item_use({:?}, is_direct_call={:?})", instance, is_direct_call); - if !should_trans_locally(tcx, &instance) { - return - } - - match instance.def { - ty::InstanceDef::Intrinsic(def_id) => { - if !is_direct_call { - bug!("intrinsic {:?} being reified", def_id); - } - } - ty::InstanceDef::Virtual(..) | - ty::InstanceDef::DropGlue(_, None) => { - // don't need to emit shim if we are calling directly. - if !is_direct_call { - output.push(create_fn_trans_item(instance)); - } - } - ty::InstanceDef::DropGlue(_, Some(_)) => { - output.push(create_fn_trans_item(instance)); - } - ty::InstanceDef::ClosureOnceShim { .. } | - ty::InstanceDef::Item(..) | - ty::InstanceDef::FnPtrShim(..) | - ty::InstanceDef::CloneShim(..) => { - output.push(create_fn_trans_item(instance)); - } - } -} - -// Returns true if we should translate an instance in the local crate. -// Returns false if we can just link to the upstream crate and therefore don't -// need a translation item. -fn should_trans_locally<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, instance: &Instance<'tcx>) - -> bool { - let def_id = match instance.def { - ty::InstanceDef::Item(def_id) => def_id, - ty::InstanceDef::ClosureOnceShim { .. } | - ty::InstanceDef::Virtual(..) | - ty::InstanceDef::FnPtrShim(..) | - ty::InstanceDef::DropGlue(..) | - ty::InstanceDef::Intrinsic(_) | - ty::InstanceDef::CloneShim(..) => return true - }; - match tcx.hir.get_if_local(def_id) { - Some(hir_map::NodeForeignItem(..)) => { - false // foreign items are linked against, not translated. - } - Some(_) => true, - None => { - if tcx.is_exported_symbol(def_id) || - tcx.is_foreign_item(def_id) - { - // We can link to the item in question, no instance needed - // in this crate - false - } else { - if !tcx.is_mir_available(def_id) { - bug!("Cannot create local trans-item for {:?}", def_id) - } - true - } - } - } -} - -/// For given pair of source and target type that occur in an unsizing coercion, -/// this function finds the pair of types that determines the vtable linking -/// them. -/// -/// For example, the source type might be `&SomeStruct` and the target type\ -/// might be `&SomeTrait` in a cast like: -/// -/// let src: &SomeStruct = ...; -/// let target = src as &SomeTrait; -/// -/// Then the output of this function would be (SomeStruct, SomeTrait) since for -/// constructing the `target` fat-pointer we need the vtable for that pair. -/// -/// Things can get more complicated though because there's also the case where -/// the unsized type occurs as a field: -/// -/// ```rust -/// struct ComplexStruct { -/// a: u32, -/// b: f64, -/// c: T -/// } -/// ``` -/// -/// In this case, if `T` is sized, `&ComplexStruct` is a thin pointer. If `T` -/// is unsized, `&SomeStruct` is a fat pointer, and the vtable it points to is -/// for the pair of `T` (which is a trait) and the concrete type that `T` was -/// originally coerced from: -/// -/// let src: &ComplexStruct = ...; -/// let target = src as &ComplexStruct; -/// -/// Again, we want this `find_vtable_types_for_unsizing()` to provide the pair -/// `(SomeStruct, SomeTrait)`. -/// -/// Finally, there is also the case of custom unsizing coercions, e.g. for -/// smart pointers such as `Rc` and `Arc`. -fn find_vtable_types_for_unsizing<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, - source_ty: Ty<'tcx>, - target_ty: Ty<'tcx>) - -> (Ty<'tcx>, Ty<'tcx>) { - let ptr_vtable = |inner_source: Ty<'tcx>, inner_target: Ty<'tcx>| { - if !type_is_sized(tcx, inner_source) { - (inner_source, inner_target) - } else { - tcx.struct_lockstep_tails(inner_source, inner_target) - } - }; - match (&source_ty.sty, &target_ty.sty) { - (&ty::TyRef(_, ty::TypeAndMut { ty: a, .. }), - &ty::TyRef(_, ty::TypeAndMut { ty: b, .. })) | - (&ty::TyRef(_, ty::TypeAndMut { ty: a, .. }), - &ty::TyRawPtr(ty::TypeAndMut { ty: b, .. })) | - (&ty::TyRawPtr(ty::TypeAndMut { ty: a, .. }), - &ty::TyRawPtr(ty::TypeAndMut { ty: b, .. })) => { - ptr_vtable(a, b) - } - (&ty::TyAdt(def_a, _), &ty::TyAdt(def_b, _)) if def_a.is_box() && def_b.is_box() => { - ptr_vtable(source_ty.boxed_ty(), target_ty.boxed_ty()) - } - - (&ty::TyAdt(source_adt_def, source_substs), - &ty::TyAdt(target_adt_def, target_substs)) => { - assert_eq!(source_adt_def, target_adt_def); - - let kind = - monomorphize::custom_coerce_unsize_info(tcx, source_ty, target_ty); - - let coerce_index = match kind { - CustomCoerceUnsized::Struct(i) => i - }; - - let source_fields = &source_adt_def.struct_variant().fields; - let target_fields = &target_adt_def.struct_variant().fields; - - assert!(coerce_index < source_fields.len() && - source_fields.len() == target_fields.len()); - - find_vtable_types_for_unsizing(tcx, - source_fields[coerce_index].ty(tcx, - source_substs), - target_fields[coerce_index].ty(tcx, - target_substs)) - } - _ => bug!("find_vtable_types_for_unsizing: invalid coercion {:?} -> {:?}", - source_ty, - target_ty) - } -} - -fn create_fn_trans_item<'a, 'tcx>(instance: Instance<'tcx>) -> TransItem<'tcx> { - debug!("create_fn_trans_item(instance={})", instance); - TransItem::Fn(instance) -} - -/// Creates a `TransItem` for each method that is referenced by the vtable for -/// the given trait/impl pair. -fn create_trans_items_for_vtable_methods<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, - trait_ty: Ty<'tcx>, - impl_ty: Ty<'tcx>, - output: &mut Vec>) { - assert!(!trait_ty.needs_subst() && !trait_ty.has_escaping_regions() && - !impl_ty.needs_subst() && !impl_ty.has_escaping_regions()); - - if let ty::TyDynamic(ref trait_ty, ..) = trait_ty.sty { - if let Some(principal) = trait_ty.principal() { - let poly_trait_ref = principal.with_self_ty(tcx, impl_ty); - assert!(!poly_trait_ref.has_escaping_regions()); - - // Walk all methods of the trait, including those of its supertraits - let methods = tcx.vtable_methods(poly_trait_ref); - let methods = methods.iter().cloned().filter_map(|method| method) - .map(|(def_id, substs)| ty::Instance::resolve( - tcx, - ty::ParamEnv::empty(traits::Reveal::All), - def_id, - substs).unwrap()) - .filter(|&instance| should_trans_locally(tcx, &instance)) - .map(|instance| create_fn_trans_item(instance)); - output.extend(methods); - } - // Also add the destructor - visit_drop_use(tcx, impl_ty, false, output); - } -} - -//=----------------------------------------------------------------------------- -// Root Collection -//=----------------------------------------------------------------------------- - -struct RootCollector<'b, 'a: 'b, 'tcx: 'a + 'b> { - tcx: TyCtxt<'a, 'tcx, 'tcx>, - mode: TransItemCollectionMode, - output: &'b mut Vec>, -} - -impl<'b, 'a, 'v> ItemLikeVisitor<'v> for RootCollector<'b, 'a, 'v> { - fn visit_item(&mut self, item: &'v hir::Item) { - match item.node { - hir::ItemExternCrate(..) | - hir::ItemUse(..) | - hir::ItemForeignMod(..) | - hir::ItemTy(..) | - hir::ItemDefaultImpl(..) | - hir::ItemTrait(..) | - hir::ItemMod(..) => { - // Nothing to do, just keep recursing... - } - - hir::ItemImpl(..) => { - if self.mode == TransItemCollectionMode::Eager { - create_trans_items_for_default_impls(self.tcx, - item, - self.output); - } - } - - hir::ItemEnum(_, ref generics) | - hir::ItemStruct(_, ref generics) | - hir::ItemUnion(_, ref generics) => { - if !generics.is_parameterized() { - if self.mode == TransItemCollectionMode::Eager { - let def_id = self.tcx.hir.local_def_id(item.id); - debug!("RootCollector: ADT drop-glue for {}", - def_id_to_string(self.tcx, def_id)); - - let ty = def_ty(self.tcx, def_id, Substs::empty()); - visit_drop_use(self.tcx, ty, true, self.output); - } - } - } - hir::ItemGlobalAsm(..) => { - debug!("RootCollector: ItemGlobalAsm({})", - def_id_to_string(self.tcx, - self.tcx.hir.local_def_id(item.id))); - self.output.push(TransItem::GlobalAsm(item.id)); - } - hir::ItemStatic(..) => { - debug!("RootCollector: ItemStatic({})", - def_id_to_string(self.tcx, - self.tcx.hir.local_def_id(item.id))); - self.output.push(TransItem::Static(item.id)); - } - hir::ItemConst(..) => { - // const items only generate translation items if they are - // actually used somewhere. Just declaring them is insufficient. - } - hir::ItemFn(..) => { - let tcx = self.tcx; - let def_id = tcx.hir.local_def_id(item.id); - - if (self.mode == TransItemCollectionMode::Eager || - !tcx.is_const_fn(def_id) || tcx.is_exported_symbol(def_id)) && - !item_has_type_parameters(tcx, def_id) { - - debug!("RootCollector: ItemFn({})", - def_id_to_string(tcx, def_id)); - - let instance = Instance::mono(tcx, def_id); - self.output.push(TransItem::Fn(instance)); - } - } - } - } - - fn visit_trait_item(&mut self, _: &'v hir::TraitItem) { - // Even if there's a default body with no explicit generics, - // it's still generic over some `Self: Trait`, so not a root. - } - - fn visit_impl_item(&mut self, ii: &'v hir::ImplItem) { - match ii.node { - hir::ImplItemKind::Method(hir::MethodSig { .. }, _) => { - let tcx = self.tcx; - let def_id = tcx.hir.local_def_id(ii.id); - - if (self.mode == TransItemCollectionMode::Eager || - !tcx.is_const_fn(def_id) || - tcx.is_exported_symbol(def_id)) && - !item_has_type_parameters(tcx, def_id) { - debug!("RootCollector: MethodImplItem({})", - def_id_to_string(tcx, def_id)); - - let instance = Instance::mono(tcx, def_id); - self.output.push(TransItem::Fn(instance)); - } - } - _ => { /* Nothing to do here */ } - } - } -} - -fn item_has_type_parameters<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId) -> bool { - let generics = tcx.generics_of(def_id); - generics.parent_types as usize + generics.types.len() > 0 -} - -fn create_trans_items_for_default_impls<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, - item: &'tcx hir::Item, - output: &mut Vec>) { - match item.node { - hir::ItemImpl(_, - _, - _, - ref generics, - .., - ref impl_item_refs) => { - if generics.is_type_parameterized() { - return - } - - let impl_def_id = tcx.hir.local_def_id(item.id); - - debug!("create_trans_items_for_default_impls(item={})", - def_id_to_string(tcx, impl_def_id)); - - if let Some(trait_ref) = tcx.impl_trait_ref(impl_def_id) { - let callee_substs = tcx.erase_regions(&trait_ref.substs); - let overridden_methods: FxHashSet<_> = - impl_item_refs.iter() - .map(|iiref| iiref.name) - .collect(); - for method in tcx.provided_trait_methods(trait_ref.def_id) { - if overridden_methods.contains(&method.name) { - continue; - } - - if !tcx.generics_of(method.def_id).types.is_empty() { - continue; - } - - let instance = ty::Instance::resolve(tcx, - ty::ParamEnv::empty(traits::Reveal::All), - method.def_id, - callee_substs).unwrap(); - - let trans_item = create_fn_trans_item(instance); - if trans_item.is_instantiable(tcx) && should_trans_locally(tcx, &instance) { - output.push(trans_item); - } - } - } - } - _ => { - bug!() - } - } -} - -/// Scan the MIR in order to find function calls, closures, and drop-glue -fn collect_neighbours<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, - instance: Instance<'tcx>, - const_context: bool, - output: &mut Vec>) -{ - let mir = tcx.instance_mir(instance.def); - - let mut visitor = MirNeighborCollector { - tcx, - mir: &mir, - output, - param_substs: instance.substs, - const_context, - }; - - visitor.visit_mir(&mir); - for promoted in &mir.promoted { - visitor.mir = promoted; - visitor.visit_mir(promoted); - } -} - -fn def_id_to_string<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, - def_id: DefId) - -> String { - let mut output = String::new(); - let printer = DefPathBasedNames::new(tcx, false, false); - printer.push_def_path(def_id, &mut output); - output -} diff --git a/src/librustc_trans/common.rs b/src/librustc_trans/common.rs index 52607904f73..e3856cabcf9 100644 --- a/src/librustc_trans/common.rs +++ b/src/librustc_trans/common.rs @@ -36,7 +36,6 @@ use libc::{c_uint, c_char}; use std::iter; use syntax::abi::Abi; -use syntax::attr; use syntax::symbol::InternedString; use syntax_pos::{Span, DUMMY_SP}; @@ -552,22 +551,6 @@ pub fn ty_fn_sig<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>, } } -pub fn requests_inline<'a, 'tcx>( - tcx: TyCtxt<'a, 'tcx, 'tcx>, - instance: &ty::Instance<'tcx> -) -> bool { - if is_inline_instance(tcx, instance) { - return true - } - if let ty::InstanceDef::DropGlue(..) = instance.def { - // Drop glue wants to be instantiated at every translation - // unit, but without an #[inline] hint. We should make this - // available to normal end-users. - return true - } - attr::requests_inline(&instance.def.attrs(tcx)[..]) -} - pub fn is_inline_instance<'a, 'tcx>( tcx: TyCtxt<'a, 'tcx, 'tcx>, instance: &ty::Instance<'tcx> diff --git a/src/librustc_trans/lib.rs b/src/librustc_trans/lib.rs index 2b1c62c7f1c..88ec3a65d35 100644 --- a/src/librustc_trans/lib.rs +++ b/src/librustc_trans/lib.rs @@ -83,6 +83,9 @@ use rustc::ty::maps::Providers; use rustc::ty::{self, TyCtxt}; use rustc::util::nodemap::{FxHashSet, FxHashMap}; +use rustc_trans_utils::collector; +use rustc_trans_utils::monomorphize; + mod diagnostics; pub mod back { @@ -124,7 +127,6 @@ mod cabi_x86; mod cabi_x86_64; mod cabi_x86_win64; mod callee; -mod collector; mod common; mod consts; mod context; @@ -137,7 +139,6 @@ mod machine; mod metadata; mod meth; mod mir; -mod monomorphize; mod partitioning; mod symbol_names_test; mod time_graph; diff --git a/src/librustc_trans/monomorphize.rs b/src/librustc_trans/monomorphize.rs deleted file mode 100644 index 471be439a8f..00000000000 --- a/src/librustc_trans/monomorphize.rs +++ /dev/null @@ -1,136 +0,0 @@ -// Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 or the MIT license -// , at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -use rustc::hir::def_id::DefId; -use rustc::middle::lang_items::DropInPlaceFnLangItem; -use rustc::traits; -use rustc::ty::adjustment::CustomCoerceUnsized; -use rustc::ty::subst::{Kind, Subst, Substs}; -use rustc::ty::{self, Ty, TyCtxt}; - -pub use rustc::ty::Instance; - -fn fn_once_adapter_instance<'a, 'tcx>( - tcx: TyCtxt<'a, 'tcx, 'tcx>, - closure_did: DefId, - substs: ty::ClosureSubsts<'tcx>, - ) -> Instance<'tcx> { - debug!("fn_once_adapter_shim({:?}, {:?})", - closure_did, - substs); - let fn_once = tcx.lang_items().fn_once_trait().unwrap(); - let call_once = tcx.associated_items(fn_once) - .find(|it| it.kind == ty::AssociatedKind::Method) - .unwrap().def_id; - let def = ty::InstanceDef::ClosureOnceShim { call_once }; - - let self_ty = tcx.mk_closure_from_closure_substs( - closure_did, substs); - - let sig = tcx.fn_sig(closure_did).subst(tcx, substs.substs); - let sig = tcx.erase_late_bound_regions_and_normalize(&sig); - assert_eq!(sig.inputs().len(), 1); - let substs = tcx.mk_substs([ - Kind::from(self_ty), - Kind::from(sig.inputs()[0]), - ].iter().cloned()); - - debug!("fn_once_adapter_shim: self_ty={:?} sig={:?}", self_ty, sig); - Instance { def, substs } -} - -fn needs_fn_once_adapter_shim(actual_closure_kind: ty::ClosureKind, - trait_closure_kind: ty::ClosureKind) - -> Result -{ - match (actual_closure_kind, trait_closure_kind) { - (ty::ClosureKind::Fn, ty::ClosureKind::Fn) | - (ty::ClosureKind::FnMut, ty::ClosureKind::FnMut) | - (ty::ClosureKind::FnOnce, ty::ClosureKind::FnOnce) => { - // No adapter needed. - Ok(false) - } - (ty::ClosureKind::Fn, ty::ClosureKind::FnMut) => { - // The closure fn `llfn` is a `fn(&self, ...)`. We want a - // `fn(&mut self, ...)`. In fact, at trans time, these are - // basically the same thing, so we can just return llfn. - Ok(false) - } - (ty::ClosureKind::Fn, ty::ClosureKind::FnOnce) | - (ty::ClosureKind::FnMut, ty::ClosureKind::FnOnce) => { - // The closure fn `llfn` is a `fn(&self, ...)` or `fn(&mut - // self, ...)`. We want a `fn(self, ...)`. We can produce - // this by doing something like: - // - // fn call_once(self, ...) { call_mut(&self, ...) } - // fn call_once(mut self, ...) { call_mut(&mut self, ...) } - // - // These are both the same at trans time. - Ok(true) - } - _ => Err(()), - } -} - -pub fn resolve_closure<'a, 'tcx> ( - tcx: TyCtxt<'a, 'tcx, 'tcx>, - def_id: DefId, - substs: ty::ClosureSubsts<'tcx>, - requested_kind: ty::ClosureKind) - -> Instance<'tcx> -{ - let actual_kind = tcx.closure_kind(def_id); - - match needs_fn_once_adapter_shim(actual_kind, requested_kind) { - Ok(true) => fn_once_adapter_instance(tcx, def_id, substs), - _ => Instance::new(def_id, substs.substs) - } -} - -pub fn resolve_drop_in_place<'a, 'tcx>( - tcx: TyCtxt<'a, 'tcx, 'tcx>, - ty: Ty<'tcx>) - -> ty::Instance<'tcx> -{ - let def_id = tcx.require_lang_item(DropInPlaceFnLangItem); - let substs = tcx.intern_substs(&[Kind::from(ty)]); - Instance::resolve(tcx, ty::ParamEnv::empty(traits::Reveal::All), def_id, substs).unwrap() -} - -pub fn custom_coerce_unsize_info<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, - source_ty: Ty<'tcx>, - target_ty: Ty<'tcx>) - -> CustomCoerceUnsized { - let def_id = tcx.lang_items().coerce_unsized_trait().unwrap(); - - let trait_ref = ty::Binder(ty::TraitRef { - def_id: def_id, - substs: tcx.mk_substs_trait(source_ty, &[target_ty]) - }); - - match tcx.trans_fulfill_obligation( (ty::ParamEnv::empty(traits::Reveal::All), trait_ref)) { - traits::VtableImpl(traits::VtableImplData { impl_def_id, .. }) => { - tcx.coerce_unsized_info(impl_def_id).custom_kind.unwrap() - } - vtable => { - bug!("invalid CoerceUnsized vtable: {:?}", vtable); - } - } -} - -/// Returns the normalized type of a struct field -pub fn field_ty<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, - param_substs: &Substs<'tcx>, - f: &'tcx ty::FieldDef) - -> Ty<'tcx> -{ - tcx.normalize_associated_type(&f.ty(tcx, param_substs)) -} - diff --git a/src/librustc_trans/partitioning.rs b/src/librustc_trans/partitioning.rs index 386806e4c9c..6980ba8a525 100644 --- a/src/librustc_trans/partitioning.rs +++ b/src/librustc_trans/partitioning.rs @@ -114,7 +114,7 @@ use rustc::util::nodemap::{FxHashMap, FxHashSet}; use std::collections::hash_map::Entry; use syntax::ast::NodeId; use syntax::symbol::{Symbol, InternedString}; -use trans_item::{TransItem, TransItemExt, InstantiationMode}; +use trans_item::{TransItem, BaseTransItemExt, TransItemExt, InstantiationMode}; pub use rustc::middle::trans::CodegenUnit; diff --git a/src/librustc_trans/trans_item.rs b/src/librustc_trans/trans_item.rs index 060f02ee23e..db1af8cdefb 100644 --- a/src/librustc_trans/trans_item.rs +++ b/src/librustc_trans/trans_item.rs @@ -24,50 +24,21 @@ use declare; use llvm; use monomorphize::Instance; use rustc::hir; -use rustc::hir::def_id::DefId; use rustc::middle::trans::{Linkage, Visibility}; -use rustc::session::config::OptLevel; -use rustc::traits; -use rustc::ty::{self, Ty, TyCtxt, TypeFoldable}; -use rustc::ty::subst::{Subst, Substs}; +use rustc::ty::{self, TyCtxt, TypeFoldable}; use syntax::ast; -use syntax::attr::{self, InlineAttr}; +use syntax::attr; use syntax_pos::Span; use syntax_pos::symbol::Symbol; use type_of; -use std::fmt::{self, Write}; -use std::iter; +use std::fmt; pub use rustc::middle::trans::TransItem; -/// Describes how a translation item will be instantiated in object files. -#[derive(PartialEq, Eq, Clone, Copy, Debug, Hash)] -pub enum InstantiationMode { - /// There will be exactly one instance of the given TransItem. It will have - /// external linkage so that it can be linked to from other codegen units. - GloballyShared { - /// In some compilation scenarios we may decide to take functions that - /// are typically `LocalCopy` and instead move them to `GloballyShared` - /// to avoid translating them a bunch of times. In this situation, - /// however, our local copy may conflict with other crates also - /// inlining the same function. - /// - /// This flag indicates that this situation is occuring, and informs - /// symbol name calculation that some extra mangling is needed to - /// avoid conflicts. Note that this may eventually go away entirely if - /// ThinLTO enables us to *always* have a globally shared instance of a - /// function within one crate's compilation. - may_conflict: bool, - }, - - /// Each codegen unit containing a reference to the given TransItem will - /// have its own private copy of the function (with internal linkage). - LocalCopy, -} - -pub trait TransItemExt<'a, 'tcx>: fmt::Debug { - fn as_trans_item(&self) -> &TransItem<'tcx>; +pub use rustc_trans_utils::trans_item::*; +pub use rustc_trans_utils::trans_item::TransItemExt as BaseTransItemExt; +pub trait TransItemExt<'a, 'tcx>: fmt::Debug + BaseTransItemExt<'a, 'tcx> { fn define(&self, ccx: &CrateContext<'a, 'tcx>) { debug!("BEGIN IMPLEMENTING '{} ({})' in cgu {}", self.to_string(ccx.tcx()), @@ -165,53 +136,6 @@ pub trait TransItemExt<'a, 'tcx>: fmt::Debug { }.map(|node_id| tcx.hir.span(node_id)) } - fn instantiation_mode(&self, - tcx: TyCtxt<'a, 'tcx, 'tcx>) - -> InstantiationMode { - let inline_in_all_cgus = - tcx.sess.opts.debugging_opts.inline_in_all_cgus.unwrap_or_else(|| { - tcx.sess.opts.optimize != OptLevel::No - }); - - match *self.as_trans_item() { - TransItem::Fn(ref instance) => { - // If this function isn't inlined or otherwise has explicit - // linkage, then we'll be creating a globally shared version. - if self.explicit_linkage(tcx).is_some() || - !common::requests_inline(tcx, instance) - { - return InstantiationMode::GloballyShared { may_conflict: false } - } - - // At this point we don't have explicit linkage and we're an - // inlined function. If we're inlining into all CGUs then we'll - // be creating a local copy per CGU - if inline_in_all_cgus { - return InstantiationMode::LocalCopy - } - - // Finally, if this is `#[inline(always)]` we're sure to respect - // that with an inline copy per CGU, but otherwise we'll be - // creating one copy of this `#[inline]` function which may - // conflict with upstream crates as it could be an exported - // symbol. - let attrs = instance.def.attrs(tcx); - match attr::find_inline_attr(Some(tcx.sess.diagnostic()), &attrs) { - InlineAttr::Always => InstantiationMode::LocalCopy, - _ => { - InstantiationMode::GloballyShared { may_conflict: true } - } - } - } - TransItem::Static(..) => { - InstantiationMode::GloballyShared { may_conflict: false } - } - TransItem::GlobalAsm(..) => { - InstantiationMode::GloballyShared { may_conflict: false } - } - } - } - fn is_generic_fn(&self) -> bool { match *self.as_trans_item() { TransItem::Fn(ref instance) => { @@ -222,97 +146,6 @@ pub trait TransItemExt<'a, 'tcx>: fmt::Debug { } } - fn explicit_linkage(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Option { - let def_id = match *self.as_trans_item() { - TransItem::Fn(ref instance) => instance.def_id(), - TransItem::Static(node_id) => tcx.hir.local_def_id(node_id), - TransItem::GlobalAsm(..) => return None, - }; - - let attributes = tcx.get_attrs(def_id); - if let Some(name) = attr::first_attr_value_str_by_name(&attributes, "linkage") { - if let Some(linkage) = base::linkage_by_name(&name.as_str()) { - Some(linkage) - } else { - let span = tcx.hir.span_if_local(def_id); - if let Some(span) = span { - tcx.sess.span_fatal(span, "invalid linkage specified") - } else { - tcx.sess.fatal(&format!("invalid linkage specified: {}", name)) - } - } - } else { - None - } - } - - /// Returns whether this instance is instantiable - whether it has no unsatisfied - /// predicates. - /// - /// In order to translate an item, all of its predicates must hold, because - /// otherwise the item does not make sense. Type-checking ensures that - /// the predicates of every item that is *used by* a valid item *do* - /// hold, so we can rely on that. - /// - /// However, we translate collector roots (reachable items) and functions - /// in vtables when they are seen, even if they are not used, and so they - /// might not be instantiable. For example, a programmer can define this - /// public function: - /// - /// pub fn foo<'a>(s: &'a mut ()) where &'a mut (): Clone { - /// <&mut () as Clone>::clone(&s); - /// } - /// - /// That function can't be translated, because the method `<&mut () as Clone>::clone` - /// does not exist. Luckily for us, that function can't ever be used, - /// because that would require for `&'a mut (): Clone` to hold, so we - /// can just not emit any code, or even a linker reference for it. - /// - /// Similarly, if a vtable method has such a signature, and therefore can't - /// be used, we can just not emit it and have a placeholder (a null pointer, - /// which will never be accessed) in its place. - fn is_instantiable(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> bool { - debug!("is_instantiable({:?})", self); - let (def_id, substs) = match *self.as_trans_item() { - TransItem::Fn(ref instance) => (instance.def_id(), instance.substs), - TransItem::Static(node_id) => (tcx.hir.local_def_id(node_id), Substs::empty()), - // global asm never has predicates - TransItem::GlobalAsm(..) => return true - }; - - let predicates = tcx.predicates_of(def_id).predicates.subst(tcx, substs); - traits::normalize_and_test_predicates(tcx, predicates) - } - - fn to_string(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> String { - let hir_map = &tcx.hir; - - return match *self.as_trans_item() { - TransItem::Fn(instance) => { - to_string_internal(tcx, "fn ", instance) - }, - TransItem::Static(node_id) => { - let def_id = hir_map.local_def_id(node_id); - let instance = Instance::new(def_id, tcx.intern_substs(&[])); - to_string_internal(tcx, "static ", instance) - }, - TransItem::GlobalAsm(..) => { - "global_asm".to_string() - } - }; - - fn to_string_internal<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, - prefix: &str, - instance: Instance<'tcx>) - -> String { - let mut result = String::with_capacity(32); - result.push_str(prefix); - let printer = DefPathBasedNames::new(tcx, false, false); - printer.push_instance_as_string(instance, &mut result); - result - } - } - fn to_raw_string(&self) -> String { match *self.as_trans_item() { TransItem::Fn(instance) => { @@ -330,11 +163,7 @@ pub trait TransItemExt<'a, 'tcx>: fmt::Debug { } } -impl<'a, 'tcx> TransItemExt<'a, 'tcx> for TransItem<'tcx> { - fn as_trans_item(&self) -> &TransItem<'tcx> { - self - } -} +impl<'a, 'tcx> TransItemExt<'a, 'tcx> for TransItem<'tcx> {} fn predefine_static<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>, node_id: ast::NodeId, @@ -402,235 +231,3 @@ fn predefine_fn<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>, ccx.instances().borrow_mut().insert(instance, lldecl); } -//=----------------------------------------------------------------------------- -// TransItem String Keys -//=----------------------------------------------------------------------------- - -// The code below allows for producing a unique string key for a trans item. -// These keys are used by the handwritten auto-tests, so they need to be -// predictable and human-readable. -// -// Note: A lot of this could looks very similar to what's already in the -// ppaux module. It would be good to refactor things so we only have one -// parameterizable implementation for printing types. - -/// Same as `unique_type_name()` but with the result pushed onto the given -/// `output` parameter. -pub struct DefPathBasedNames<'a, 'tcx: 'a> { - tcx: TyCtxt<'a, 'tcx, 'tcx>, - omit_disambiguators: bool, - omit_local_crate_name: bool, -} - -impl<'a, 'tcx> DefPathBasedNames<'a, 'tcx> { - pub fn new(tcx: TyCtxt<'a, 'tcx, 'tcx>, - omit_disambiguators: bool, - omit_local_crate_name: bool) - -> Self { - DefPathBasedNames { - tcx, - omit_disambiguators, - omit_local_crate_name, - } - } - - pub fn push_type_name(&self, t: Ty<'tcx>, output: &mut String) { - match t.sty { - ty::TyBool => output.push_str("bool"), - ty::TyChar => output.push_str("char"), - ty::TyStr => output.push_str("str"), - ty::TyNever => output.push_str("!"), - ty::TyInt(ast::IntTy::Is) => output.push_str("isize"), - ty::TyInt(ast::IntTy::I8) => output.push_str("i8"), - ty::TyInt(ast::IntTy::I16) => output.push_str("i16"), - ty::TyInt(ast::IntTy::I32) => output.push_str("i32"), - ty::TyInt(ast::IntTy::I64) => output.push_str("i64"), - ty::TyInt(ast::IntTy::I128) => output.push_str("i128"), - ty::TyUint(ast::UintTy::Us) => output.push_str("usize"), - ty::TyUint(ast::UintTy::U8) => output.push_str("u8"), - ty::TyUint(ast::UintTy::U16) => output.push_str("u16"), - ty::TyUint(ast::UintTy::U32) => output.push_str("u32"), - ty::TyUint(ast::UintTy::U64) => output.push_str("u64"), - ty::TyUint(ast::UintTy::U128) => output.push_str("u128"), - ty::TyFloat(ast::FloatTy::F32) => output.push_str("f32"), - ty::TyFloat(ast::FloatTy::F64) => output.push_str("f64"), - ty::TyAdt(adt_def, substs) => { - self.push_def_path(adt_def.did, output); - self.push_type_params(substs, iter::empty(), output); - }, - ty::TyTuple(component_types, _) => { - output.push('('); - for &component_type in component_types { - self.push_type_name(component_type, output); - output.push_str(", "); - } - if !component_types.is_empty() { - output.pop(); - output.pop(); - } - output.push(')'); - }, - ty::TyRawPtr(ty::TypeAndMut { ty: inner_type, mutbl } ) => { - output.push('*'); - match mutbl { - hir::MutImmutable => output.push_str("const "), - hir::MutMutable => output.push_str("mut "), - } - - self.push_type_name(inner_type, output); - }, - ty::TyRef(_, ty::TypeAndMut { ty: inner_type, mutbl }) => { - output.push('&'); - if mutbl == hir::MutMutable { - output.push_str("mut "); - } - - self.push_type_name(inner_type, output); - }, - ty::TyArray(inner_type, len) => { - output.push('['); - self.push_type_name(inner_type, output); - write!(output, "; {}", - len.val.to_const_int().unwrap().to_u64().unwrap()).unwrap(); - output.push(']'); - }, - ty::TySlice(inner_type) => { - output.push('['); - self.push_type_name(inner_type, output); - output.push(']'); - }, - ty::TyDynamic(ref trait_data, ..) => { - if let Some(principal) = trait_data.principal() { - self.push_def_path(principal.def_id(), output); - self.push_type_params(principal.skip_binder().substs, - trait_data.projection_bounds(), - output); - } - }, - ty::TyFnDef(..) | - ty::TyFnPtr(_) => { - let sig = t.fn_sig(self.tcx); - if sig.unsafety() == hir::Unsafety::Unsafe { - output.push_str("unsafe "); - } - - let abi = sig.abi(); - if abi != ::abi::Abi::Rust { - output.push_str("extern \""); - output.push_str(abi.name()); - output.push_str("\" "); - } - - output.push_str("fn("); - - let sig = self.tcx.erase_late_bound_regions_and_normalize(&sig); - - if !sig.inputs().is_empty() { - for ¶meter_type in sig.inputs() { - self.push_type_name(parameter_type, output); - output.push_str(", "); - } - output.pop(); - output.pop(); - } - - if sig.variadic { - if !sig.inputs().is_empty() { - output.push_str(", ..."); - } else { - output.push_str("..."); - } - } - - output.push(')'); - - if !sig.output().is_nil() { - output.push_str(" -> "); - self.push_type_name(sig.output(), output); - } - }, - ty::TyGenerator(def_id, ref closure_substs, _) | - ty::TyClosure(def_id, ref closure_substs) => { - self.push_def_path(def_id, output); - let generics = self.tcx.generics_of(self.tcx.closure_base_def_id(def_id)); - let substs = closure_substs.substs.truncate_to(self.tcx, generics); - self.push_type_params(substs, iter::empty(), output); - } - ty::TyError | - ty::TyInfer(_) | - ty::TyProjection(..) | - ty::TyParam(_) | - ty::TyAnon(..) => { - bug!("DefPathBasedNames: Trying to create type name for \ - unexpected type: {:?}", t); - } - } - } - - pub fn push_def_path(&self, - def_id: DefId, - output: &mut String) { - let def_path = self.tcx.def_path(def_id); - - // some_crate:: - if !(self.omit_local_crate_name && def_id.is_local()) { - output.push_str(&self.tcx.crate_name(def_path.krate).as_str()); - output.push_str("::"); - } - - // foo::bar::ItemName:: - for part in self.tcx.def_path(def_id).data { - if self.omit_disambiguators { - write!(output, "{}::", part.data.as_interned_str()).unwrap(); - } else { - write!(output, "{}[{}]::", - part.data.as_interned_str(), - part.disambiguator).unwrap(); - } - } - - // remove final "::" - output.pop(); - output.pop(); - } - - fn push_type_params(&self, - substs: &Substs<'tcx>, - projections: I, - output: &mut String) - where I: Iterator> - { - let mut projections = projections.peekable(); - if substs.types().next().is_none() && projections.peek().is_none() { - return; - } - - output.push('<'); - - for type_parameter in substs.types() { - self.push_type_name(type_parameter, output); - output.push_str(", "); - } - - for projection in projections { - let projection = projection.skip_binder(); - let name = &self.tcx.associated_item(projection.item_def_id).name.as_str(); - output.push_str(name); - output.push_str("="); - self.push_type_name(projection.ty, output); - output.push_str(", "); - } - - output.pop(); - output.pop(); - - output.push('>'); - } - - pub fn push_instance_as_string(&self, - instance: Instance<'tcx>, - output: &mut String) { - self.push_def_path(instance.def_id(), output); - self.push_type_params(instance.substs, iter::empty(), output); - } -} diff --git a/src/librustc_trans_utils/Cargo.toml b/src/librustc_trans_utils/Cargo.toml index bedbea00688..7d9d7cea933 100644 --- a/src/librustc_trans_utils/Cargo.toml +++ b/src/librustc_trans_utils/Cargo.toml @@ -19,3 +19,4 @@ syntax = { path = "../libsyntax" } syntax_pos = { path = "../libsyntax_pos" } rustc = { path = "../librustc" } rustc_back = { path = "../librustc_back" } +rustc_data_structures = { path = "../librustc_data_structures" } diff --git a/src/librustc_trans_utils/collector.rs b/src/librustc_trans_utils/collector.rs new file mode 100644 index 00000000000..c87d86262ef --- /dev/null +++ b/src/librustc_trans_utils/collector.rs @@ -0,0 +1,1062 @@ +// Copyright 2014 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 or the MIT license +// , at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! Translation Item Collection +//! =========================== +//! +//! This module is responsible for discovering all items that will contribute to +//! to code generation of the crate. The important part here is that it not only +//! needs to find syntax-level items (functions, structs, etc) but also all +//! their monomorphized instantiations. Every non-generic, non-const function +//! maps to one LLVM artifact. Every generic function can produce +//! from zero to N artifacts, depending on the sets of type arguments it +//! is instantiated with. +//! This also applies to generic items from other crates: A generic definition +//! in crate X might produce monomorphizations that are compiled into crate Y. +//! We also have to collect these here. +//! +//! The following kinds of "translation items" are handled here: +//! +//! - Functions +//! - Methods +//! - Closures +//! - Statics +//! - Drop glue +//! +//! The following things also result in LLVM artifacts, but are not collected +//! here, since we instantiate them locally on demand when needed in a given +//! codegen unit: +//! +//! - Constants +//! - Vtables +//! - Object Shims +//! +//! +//! General Algorithm +//! ----------------- +//! Let's define some terms first: +//! +//! - A "translation item" is something that results in a function or global in +//! the LLVM IR of a codegen unit. Translation items do not stand on their +//! own, they can reference other translation items. For example, if function +//! `foo()` calls function `bar()` then the translation item for `foo()` +//! references the translation item for function `bar()`. In general, the +//! definition for translation item A referencing a translation item B is that +//! the LLVM artifact produced for A references the LLVM artifact produced +//! for B. +//! +//! - Translation items and the references between them form a directed graph, +//! where the translation items are the nodes and references form the edges. +//! Let's call this graph the "translation item graph". +//! +//! - The translation item graph for a program contains all translation items +//! that are needed in order to produce the complete LLVM IR of the program. +//! +//! The purpose of the algorithm implemented in this module is to build the +//! translation item graph for the current crate. It runs in two phases: +//! +//! 1. Discover the roots of the graph by traversing the HIR of the crate. +//! 2. Starting from the roots, find neighboring nodes by inspecting the MIR +//! representation of the item corresponding to a given node, until no more +//! new nodes are found. +//! +//! ### Discovering roots +//! +//! The roots of the translation item graph correspond to the non-generic +//! syntactic items in the source code. We find them by walking the HIR of the +//! crate, and whenever we hit upon a function, method, or static item, we +//! create a translation item consisting of the items DefId and, since we only +//! consider non-generic items, an empty type-substitution set. +//! +//! ### Finding neighbor nodes +//! Given a translation item node, we can discover neighbors by inspecting its +//! MIR. We walk the MIR and any time we hit upon something that signifies a +//! reference to another translation item, we have found a neighbor. Since the +//! translation item we are currently at is always monomorphic, we also know the +//! concrete type arguments of its neighbors, and so all neighbors again will be +//! monomorphic. The specific forms a reference to a neighboring node can take +//! in MIR are quite diverse. Here is an overview: +//! +//! #### Calling Functions/Methods +//! The most obvious form of one translation item referencing another is a +//! function or method call (represented by a CALL terminator in MIR). But +//! calls are not the only thing that might introduce a reference between two +//! function translation items, and as we will see below, they are just a +//! specialized of the form described next, and consequently will don't get any +//! special treatment in the algorithm. +//! +//! #### Taking a reference to a function or method +//! A function does not need to actually be called in order to be a neighbor of +//! another function. It suffices to just take a reference in order to introduce +//! an edge. Consider the following example: +//! +//! ```rust +//! fn print_val(x: T) { +//! println!("{}", x); +//! } +//! +//! fn call_fn(f: &Fn(i32), x: i32) { +//! f(x); +//! } +//! +//! fn main() { +//! let print_i32 = print_val::; +//! call_fn(&print_i32, 0); +//! } +//! ``` +//! The MIR of none of these functions will contain an explicit call to +//! `print_val::`. Nonetheless, in order to translate this program, we need +//! an instance of this function. Thus, whenever we encounter a function or +//! method in operand position, we treat it as a neighbor of the current +//! translation item. Calls are just a special case of that. +//! +//! #### Closures +//! In a way, closures are a simple case. Since every closure object needs to be +//! constructed somewhere, we can reliably discover them by observing +//! `RValue::Aggregate` expressions with `AggregateKind::Closure`. This is also +//! true for closures inlined from other crates. +//! +//! #### Drop glue +//! Drop glue translation items are introduced by MIR drop-statements. The +//! generated translation item will again have drop-glue item neighbors if the +//! type to be dropped contains nested values that also need to be dropped. It +//! might also have a function item neighbor for the explicit `Drop::drop` +//! implementation of its type. +//! +//! #### Unsizing Casts +//! A subtle way of introducing neighbor edges is by casting to a trait object. +//! Since the resulting fat-pointer contains a reference to a vtable, we need to +//! instantiate all object-save methods of the trait, as we need to store +//! pointers to these functions even if they never get called anywhere. This can +//! be seen as a special case of taking a function reference. +//! +//! #### Boxes +//! Since `Box` expression have special compiler support, no explicit calls to +//! `exchange_malloc()` and `exchange_free()` may show up in MIR, even if the +//! compiler will generate them. We have to observe `Rvalue::Box` expressions +//! and Box-typed drop-statements for that purpose. +//! +//! +//! Interaction with Cross-Crate Inlining +//! ------------------------------------- +//! The binary of a crate will not only contain machine code for the items +//! defined in the source code of that crate. It will also contain monomorphic +//! instantiations of any extern generic functions and of functions marked with +//! #[inline]. +//! The collection algorithm handles this more or less transparently. If it is +//! about to create a translation item for something with an external `DefId`, +//! it will take a look if the MIR for that item is available, and if so just +//! proceed normally. If the MIR is not available, it assumes that the item is +//! just linked to and no node is created; which is exactly what we want, since +//! no machine code should be generated in the current crate for such an item. +//! +//! Eager and Lazy Collection Mode +//! ------------------------------ +//! Translation item collection can be performed in one of two modes: +//! +//! - Lazy mode means that items will only be instantiated when actually +//! referenced. The goal is to produce the least amount of machine code +//! possible. +//! +//! - Eager mode is meant to be used in conjunction with incremental compilation +//! where a stable set of translation items is more important than a minimal +//! one. Thus, eager mode will instantiate drop-glue for every drop-able type +//! in the crate, even of no drop call for that type exists (yet). It will +//! also instantiate default implementations of trait methods, something that +//! otherwise is only done on demand. +//! +//! +//! Open Issues +//! ----------- +//! Some things are not yet fully implemented in the current version of this +//! module. +//! +//! ### Initializers of Constants and Statics +//! Since no MIR is constructed yet for initializer expressions of constants and +//! statics we cannot inspect these properly. +//! +//! ### Const Fns +//! Ideally, no translation item should be generated for const fns unless there +//! is a call to them that cannot be evaluated at compile time. At the moment +//! this is not implemented however: a translation item will be produced +//! regardless of whether it is actually needed or not. + +use rustc::hir; +use rustc::hir::itemlikevisit::ItemLikeVisitor; + +use rustc::hir::map as hir_map; +use rustc::hir::def_id::DefId; +use rustc::middle::const_val::ConstVal; +use rustc::middle::lang_items::{ExchangeMallocFnLangItem}; +use rustc::middle::trans::TransItem; +use rustc::traits; +use rustc::ty::subst::Substs; +use rustc::ty::{self, TypeFoldable, Ty, TyCtxt}; +use rustc::ty::adjustment::CustomCoerceUnsized; +use rustc::mir::{self, Location}; +use rustc::mir::visit::Visitor as MirVisitor; + +use common::{def_ty, instance_ty, type_is_sized}; +use monomorphize::{self, Instance}; +use rustc::util::nodemap::{FxHashSet, FxHashMap, DefIdMap}; + +use trans_item::{TransItemExt, DefPathBasedNames, InstantiationMode}; + +use rustc_data_structures::bitvec::BitVector; + +#[derive(PartialEq, Eq, Hash, Clone, Copy, Debug)] +pub enum TransItemCollectionMode { + Eager, + Lazy +} + +/// Maps every translation item to all translation items it references in its +/// body. +pub struct InliningMap<'tcx> { + // Maps a source translation item to the range of translation items + // accessed by it. + // The two numbers in the tuple are the start (inclusive) and + // end index (exclusive) within the `targets` vecs. + index: FxHashMap, (usize, usize)>, + targets: Vec>, + + // Contains one bit per translation item in the `targets` field. That bit + // is true if that translation item needs to be inlined into every CGU. + inlines: BitVector, +} + +impl<'tcx> InliningMap<'tcx> { + + fn new() -> InliningMap<'tcx> { + InliningMap { + index: FxHashMap(), + targets: Vec::new(), + inlines: BitVector::new(1024), + } + } + + fn record_accesses(&mut self, + source: TransItem<'tcx>, + new_targets: I) + where I: Iterator, bool)> + ExactSizeIterator + { + assert!(!self.index.contains_key(&source)); + + let start_index = self.targets.len(); + let new_items_count = new_targets.len(); + let new_items_count_total = new_items_count + self.targets.len(); + + self.targets.reserve(new_items_count); + self.inlines.grow(new_items_count_total); + + for (i, (target, inline)) in new_targets.enumerate() { + self.targets.push(target); + if inline { + self.inlines.insert(i + start_index); + } + } + + let end_index = self.targets.len(); + self.index.insert(source, (start_index, end_index)); + } + + // Internally iterate over all items referenced by `source` which will be + // made available for inlining. + pub fn with_inlining_candidates(&self, source: TransItem<'tcx>, mut f: F) + where F: FnMut(TransItem<'tcx>) + { + if let Some(&(start_index, end_index)) = self.index.get(&source) { + for (i, candidate) in self.targets[start_index .. end_index] + .iter() + .enumerate() { + if self.inlines.contains(start_index + i) { + f(*candidate); + } + } + } + } + + // Internally iterate over all items and the things each accesses. + pub fn iter_accesses(&self, mut f: F) + where F: FnMut(TransItem<'tcx>, &[TransItem<'tcx>]) + { + for (&accessor, &(start_index, end_index)) in &self.index { + f(accessor, &self.targets[start_index .. end_index]) + } + } +} + +pub fn collect_crate_translation_items<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + mode: TransItemCollectionMode) + -> (FxHashSet>, + InliningMap<'tcx>) { + let roots = collect_roots(tcx, mode); + + debug!("Building translation item graph, beginning at roots"); + let mut visited = FxHashSet(); + let mut recursion_depths = DefIdMap(); + let mut inlining_map = InliningMap::new(); + + for root in roots { + collect_items_rec(tcx, + root, + &mut visited, + &mut recursion_depths, + &mut inlining_map); + } + + (visited, inlining_map) +} + +// Find all non-generic items by walking the HIR. These items serve as roots to +// start monomorphizing from. +fn collect_roots<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + mode: TransItemCollectionMode) + -> Vec> { + debug!("Collecting roots"); + let mut roots = Vec::new(); + + { + let mut visitor = RootCollector { + tcx, + mode, + output: &mut roots, + }; + + tcx.hir.krate().visit_all_item_likes(&mut visitor); + } + + // We can only translate items that are instantiable - items all of + // whose predicates hold. Luckily, items that aren't instantiable + // can't actually be used, so we can just skip translating them. + roots.retain(|root| root.is_instantiable(tcx)); + + roots +} + +// Collect all monomorphized translation items reachable from `starting_point` +fn collect_items_rec<'a, 'tcx: 'a>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + starting_point: TransItem<'tcx>, + visited: &mut FxHashSet>, + recursion_depths: &mut DefIdMap, + inlining_map: &mut InliningMap<'tcx>) { + if !visited.insert(starting_point.clone()) { + // We've been here already, no need to search again. + return; + } + debug!("BEGIN collect_items_rec({})", starting_point.to_string(tcx)); + + let mut neighbors = Vec::new(); + let recursion_depth_reset; + + match starting_point { + TransItem::Static(node_id) => { + let def_id = tcx.hir.local_def_id(node_id); + let instance = Instance::mono(tcx, def_id); + + // Sanity check whether this ended up being collected accidentally + debug_assert!(should_trans_locally(tcx, &instance)); + + let ty = instance_ty(tcx, &instance); + visit_drop_use(tcx, ty, true, &mut neighbors); + + recursion_depth_reset = None; + + collect_neighbours(tcx, instance, true, &mut neighbors); + } + TransItem::Fn(instance) => { + // Sanity check whether this ended up being collected accidentally + debug_assert!(should_trans_locally(tcx, &instance)); + + // Keep track of the monomorphization recursion depth + recursion_depth_reset = Some(check_recursion_limit(tcx, + instance, + recursion_depths)); + check_type_length_limit(tcx, instance); + + collect_neighbours(tcx, instance, false, &mut neighbors); + } + TransItem::GlobalAsm(..) => { + recursion_depth_reset = None; + } + } + + record_accesses(tcx, starting_point, &neighbors[..], inlining_map); + + for neighbour in neighbors { + collect_items_rec(tcx, neighbour, visited, recursion_depths, inlining_map); + } + + if let Some((def_id, depth)) = recursion_depth_reset { + recursion_depths.insert(def_id, depth); + } + + debug!("END collect_items_rec({})", starting_point.to_string(tcx)); +} + +fn record_accesses<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + caller: TransItem<'tcx>, + callees: &[TransItem<'tcx>], + inlining_map: &mut InliningMap<'tcx>) { + let is_inlining_candidate = |trans_item: &TransItem<'tcx>| { + trans_item.instantiation_mode(tcx) == InstantiationMode::LocalCopy + }; + + let accesses = callees.into_iter() + .map(|trans_item| { + (*trans_item, is_inlining_candidate(trans_item)) + }); + + inlining_map.record_accesses(caller, accesses); +} + +fn check_recursion_limit<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + instance: Instance<'tcx>, + recursion_depths: &mut DefIdMap) + -> (DefId, usize) { + let def_id = instance.def_id(); + let recursion_depth = recursion_depths.get(&def_id).cloned().unwrap_or(0); + debug!(" => recursion depth={}", recursion_depth); + + let recursion_depth = if Some(def_id) == tcx.lang_items().drop_in_place_fn() { + // HACK: drop_in_place creates tight monomorphization loops. Give + // it more margin. + recursion_depth / 4 + } else { + recursion_depth + }; + + // Code that needs to instantiate the same function recursively + // more than the recursion limit is assumed to be causing an + // infinite expansion. + if recursion_depth > tcx.sess.recursion_limit.get() { + let error = format!("reached the recursion limit while instantiating `{}`", + instance); + if let Some(node_id) = tcx.hir.as_local_node_id(def_id) { + tcx.sess.span_fatal(tcx.hir.span(node_id), &error); + } else { + tcx.sess.fatal(&error); + } + } + + recursion_depths.insert(def_id, recursion_depth + 1); + + (def_id, recursion_depth) +} + +fn check_type_length_limit<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + instance: Instance<'tcx>) +{ + let type_length = instance.substs.types().flat_map(|ty| ty.walk()).count(); + debug!(" => type length={}", type_length); + + // Rust code can easily create exponentially-long types using only a + // polynomial recursion depth. Even with the default recursion + // depth, you can easily get cases that take >2^60 steps to run, + // which means that rustc basically hangs. + // + // Bail out in these cases to avoid that bad user experience. + let type_length_limit = tcx.sess.type_length_limit.get(); + if type_length > type_length_limit { + // The instance name is already known to be too long for rustc. Use + // `{:.64}` to avoid blasting the user's terminal with thousands of + // lines of type-name. + let instance_name = instance.to_string(); + let msg = format!("reached the type-length limit while instantiating `{:.64}...`", + instance_name); + let mut diag = if let Some(node_id) = tcx.hir.as_local_node_id(instance.def_id()) { + tcx.sess.struct_span_fatal(tcx.hir.span(node_id), &msg) + } else { + tcx.sess.struct_fatal(&msg) + }; + + diag.note(&format!( + "consider adding a `#![type_length_limit=\"{}\"]` attribute to your crate", + type_length_limit*2)); + diag.emit(); + tcx.sess.abort_if_errors(); + } +} + +struct MirNeighborCollector<'a, 'tcx: 'a> { + tcx: TyCtxt<'a, 'tcx, 'tcx>, + mir: &'a mir::Mir<'tcx>, + output: &'a mut Vec>, + param_substs: &'tcx Substs<'tcx>, + const_context: bool, +} + +impl<'a, 'tcx> MirVisitor<'tcx> for MirNeighborCollector<'a, 'tcx> { + + fn visit_rvalue(&mut self, rvalue: &mir::Rvalue<'tcx>, location: Location) { + debug!("visiting rvalue {:?}", *rvalue); + + match *rvalue { + // When doing an cast from a regular pointer to a fat pointer, we + // have to instantiate all methods of the trait being cast to, so we + // can build the appropriate vtable. + mir::Rvalue::Cast(mir::CastKind::Unsize, ref operand, target_ty) => { + let target_ty = self.tcx.trans_apply_param_substs(self.param_substs, + &target_ty); + let source_ty = operand.ty(self.mir, self.tcx); + let source_ty = self.tcx.trans_apply_param_substs(self.param_substs, + &source_ty); + let (source_ty, target_ty) = find_vtable_types_for_unsizing(self.tcx, + source_ty, + target_ty); + // This could also be a different Unsize instruction, like + // from a fixed sized array to a slice. But we are only + // interested in things that produce a vtable. + if target_ty.is_trait() && !source_ty.is_trait() { + create_trans_items_for_vtable_methods(self.tcx, + target_ty, + source_ty, + self.output); + } + } + mir::Rvalue::Cast(mir::CastKind::ReifyFnPointer, ref operand, _) => { + let fn_ty = operand.ty(self.mir, self.tcx); + let fn_ty = self.tcx.trans_apply_param_substs(self.param_substs, + &fn_ty); + visit_fn_use(self.tcx, fn_ty, false, &mut self.output); + } + mir::Rvalue::Cast(mir::CastKind::ClosureFnPointer, ref operand, _) => { + let source_ty = operand.ty(self.mir, self.tcx); + let source_ty = self.tcx.trans_apply_param_substs(self.param_substs, + &source_ty); + match source_ty.sty { + ty::TyClosure(def_id, substs) => { + let instance = monomorphize::resolve_closure( + self.tcx, def_id, substs, ty::ClosureKind::FnOnce); + self.output.push(create_fn_trans_item(instance)); + } + _ => bug!(), + } + } + mir::Rvalue::NullaryOp(mir::NullOp::Box, _) => { + let tcx = self.tcx; + let exchange_malloc_fn_def_id = tcx + .lang_items() + .require(ExchangeMallocFnLangItem) + .unwrap_or_else(|e| tcx.sess.fatal(&e)); + let instance = Instance::mono(tcx, exchange_malloc_fn_def_id); + if should_trans_locally(tcx, &instance) { + self.output.push(create_fn_trans_item(instance)); + } + } + _ => { /* not interesting */ } + } + + self.super_rvalue(rvalue, location); + } + + fn visit_const(&mut self, constant: &&'tcx ty::Const<'tcx>, location: Location) { + debug!("visiting const {:?} @ {:?}", *constant, location); + + if let ConstVal::Unevaluated(def_id, substs) = constant.val { + let substs = self.tcx.trans_apply_param_substs(self.param_substs, + &substs); + let instance = ty::Instance::resolve(self.tcx, + ty::ParamEnv::empty(traits::Reveal::All), + def_id, + substs).unwrap(); + collect_neighbours(self.tcx, instance, true, self.output); + } + + self.super_const(constant); + } + + fn visit_terminator_kind(&mut self, + block: mir::BasicBlock, + kind: &mir::TerminatorKind<'tcx>, + location: Location) { + debug!("visiting terminator {:?} @ {:?}", kind, location); + + let tcx = self.tcx; + match *kind { + mir::TerminatorKind::Call { ref func, .. } => { + let callee_ty = func.ty(self.mir, tcx); + let callee_ty = tcx.trans_apply_param_substs(self.param_substs, &callee_ty); + + let constness = match (self.const_context, &callee_ty.sty) { + (true, &ty::TyFnDef(def_id, substs)) if self.tcx.is_const_fn(def_id) => { + let instance = + ty::Instance::resolve(self.tcx, + ty::ParamEnv::empty(traits::Reveal::All), + def_id, + substs).unwrap(); + Some(instance) + } + _ => None + }; + + if let Some(const_fn_instance) = constness { + // If this is a const fn, called from a const context, we + // have to visit its body in order to find any fn reifications + // it might contain. + collect_neighbours(self.tcx, + const_fn_instance, + true, + self.output); + } else { + visit_fn_use(self.tcx, callee_ty, true, &mut self.output); + } + } + mir::TerminatorKind::Drop { ref location, .. } | + mir::TerminatorKind::DropAndReplace { ref location, .. } => { + let ty = location.ty(self.mir, self.tcx) + .to_ty(self.tcx); + let ty = tcx.trans_apply_param_substs(self.param_substs, &ty); + visit_drop_use(self.tcx, ty, true, self.output); + } + mir::TerminatorKind::Goto { .. } | + mir::TerminatorKind::SwitchInt { .. } | + mir::TerminatorKind::Resume | + mir::TerminatorKind::Return | + mir::TerminatorKind::Unreachable | + mir::TerminatorKind::Assert { .. } => {} + mir::TerminatorKind::GeneratorDrop | + mir::TerminatorKind::Yield { .. } => bug!(), + } + + self.super_terminator_kind(block, kind, location); + } + + fn visit_static(&mut self, + static_: &mir::Static<'tcx>, + context: mir::visit::LvalueContext<'tcx>, + location: Location) { + debug!("visiting static {:?} @ {:?}", static_.def_id, location); + + let tcx = self.tcx; + let instance = Instance::mono(tcx, static_.def_id); + if should_trans_locally(tcx, &instance) { + let node_id = tcx.hir.as_local_node_id(static_.def_id).unwrap(); + self.output.push(TransItem::Static(node_id)); + } + + self.super_static(static_, context, location); + } +} + +fn visit_drop_use<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + ty: Ty<'tcx>, + is_direct_call: bool, + output: &mut Vec>) +{ + let instance = monomorphize::resolve_drop_in_place(tcx, ty); + visit_instance_use(tcx, instance, is_direct_call, output); +} + +fn visit_fn_use<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + ty: Ty<'tcx>, + is_direct_call: bool, + output: &mut Vec>) +{ + if let ty::TyFnDef(def_id, substs) = ty.sty { + let instance = ty::Instance::resolve(tcx, + ty::ParamEnv::empty(traits::Reveal::All), + def_id, + substs).unwrap(); + visit_instance_use(tcx, instance, is_direct_call, output); + } +} + +fn visit_instance_use<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + instance: ty::Instance<'tcx>, + is_direct_call: bool, + output: &mut Vec>) +{ + debug!("visit_item_use({:?}, is_direct_call={:?})", instance, is_direct_call); + if !should_trans_locally(tcx, &instance) { + return + } + + match instance.def { + ty::InstanceDef::Intrinsic(def_id) => { + if !is_direct_call { + bug!("intrinsic {:?} being reified", def_id); + } + } + ty::InstanceDef::Virtual(..) | + ty::InstanceDef::DropGlue(_, None) => { + // don't need to emit shim if we are calling directly. + if !is_direct_call { + output.push(create_fn_trans_item(instance)); + } + } + ty::InstanceDef::DropGlue(_, Some(_)) => { + output.push(create_fn_trans_item(instance)); + } + ty::InstanceDef::ClosureOnceShim { .. } | + ty::InstanceDef::Item(..) | + ty::InstanceDef::FnPtrShim(..) | + ty::InstanceDef::CloneShim(..) => { + output.push(create_fn_trans_item(instance)); + } + } +} + +// Returns true if we should translate an instance in the local crate. +// Returns false if we can just link to the upstream crate and therefore don't +// need a translation item. +fn should_trans_locally<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, instance: &Instance<'tcx>) + -> bool { + let def_id = match instance.def { + ty::InstanceDef::Item(def_id) => def_id, + ty::InstanceDef::ClosureOnceShim { .. } | + ty::InstanceDef::Virtual(..) | + ty::InstanceDef::FnPtrShim(..) | + ty::InstanceDef::DropGlue(..) | + ty::InstanceDef::Intrinsic(_) | + ty::InstanceDef::CloneShim(..) => return true + }; + match tcx.hir.get_if_local(def_id) { + Some(hir_map::NodeForeignItem(..)) => { + false // foreign items are linked against, not translated. + } + Some(_) => true, + None => { + if tcx.is_exported_symbol(def_id) || + tcx.is_foreign_item(def_id) + { + // We can link to the item in question, no instance needed + // in this crate + false + } else { + if !tcx.is_mir_available(def_id) { + bug!("Cannot create local trans-item for {:?}", def_id) + } + true + } + } + } +} + +/// For given pair of source and target type that occur in an unsizing coercion, +/// this function finds the pair of types that determines the vtable linking +/// them. +/// +/// For example, the source type might be `&SomeStruct` and the target type\ +/// might be `&SomeTrait` in a cast like: +/// +/// let src: &SomeStruct = ...; +/// let target = src as &SomeTrait; +/// +/// Then the output of this function would be (SomeStruct, SomeTrait) since for +/// constructing the `target` fat-pointer we need the vtable for that pair. +/// +/// Things can get more complicated though because there's also the case where +/// the unsized type occurs as a field: +/// +/// ```rust +/// struct ComplexStruct { +/// a: u32, +/// b: f64, +/// c: T +/// } +/// ``` +/// +/// In this case, if `T` is sized, `&ComplexStruct` is a thin pointer. If `T` +/// is unsized, `&SomeStruct` is a fat pointer, and the vtable it points to is +/// for the pair of `T` (which is a trait) and the concrete type that `T` was +/// originally coerced from: +/// +/// let src: &ComplexStruct = ...; +/// let target = src as &ComplexStruct; +/// +/// Again, we want this `find_vtable_types_for_unsizing()` to provide the pair +/// `(SomeStruct, SomeTrait)`. +/// +/// Finally, there is also the case of custom unsizing coercions, e.g. for +/// smart pointers such as `Rc` and `Arc`. +fn find_vtable_types_for_unsizing<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + source_ty: Ty<'tcx>, + target_ty: Ty<'tcx>) + -> (Ty<'tcx>, Ty<'tcx>) { + let ptr_vtable = |inner_source: Ty<'tcx>, inner_target: Ty<'tcx>| { + if !type_is_sized(tcx, inner_source) { + (inner_source, inner_target) + } else { + tcx.struct_lockstep_tails(inner_source, inner_target) + } + }; + match (&source_ty.sty, &target_ty.sty) { + (&ty::TyRef(_, ty::TypeAndMut { ty: a, .. }), + &ty::TyRef(_, ty::TypeAndMut { ty: b, .. })) | + (&ty::TyRef(_, ty::TypeAndMut { ty: a, .. }), + &ty::TyRawPtr(ty::TypeAndMut { ty: b, .. })) | + (&ty::TyRawPtr(ty::TypeAndMut { ty: a, .. }), + &ty::TyRawPtr(ty::TypeAndMut { ty: b, .. })) => { + ptr_vtable(a, b) + } + (&ty::TyAdt(def_a, _), &ty::TyAdt(def_b, _)) if def_a.is_box() && def_b.is_box() => { + ptr_vtable(source_ty.boxed_ty(), target_ty.boxed_ty()) + } + + (&ty::TyAdt(source_adt_def, source_substs), + &ty::TyAdt(target_adt_def, target_substs)) => { + assert_eq!(source_adt_def, target_adt_def); + + let kind = + monomorphize::custom_coerce_unsize_info(tcx, source_ty, target_ty); + + let coerce_index = match kind { + CustomCoerceUnsized::Struct(i) => i + }; + + let source_fields = &source_adt_def.struct_variant().fields; + let target_fields = &target_adt_def.struct_variant().fields; + + assert!(coerce_index < source_fields.len() && + source_fields.len() == target_fields.len()); + + find_vtable_types_for_unsizing(tcx, + source_fields[coerce_index].ty(tcx, + source_substs), + target_fields[coerce_index].ty(tcx, + target_substs)) + } + _ => bug!("find_vtable_types_for_unsizing: invalid coercion {:?} -> {:?}", + source_ty, + target_ty) + } +} + +fn create_fn_trans_item<'a, 'tcx>(instance: Instance<'tcx>) -> TransItem<'tcx> { + debug!("create_fn_trans_item(instance={})", instance); + TransItem::Fn(instance) +} + +/// Creates a `TransItem` for each method that is referenced by the vtable for +/// the given trait/impl pair. +fn create_trans_items_for_vtable_methods<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + trait_ty: Ty<'tcx>, + impl_ty: Ty<'tcx>, + output: &mut Vec>) { + assert!(!trait_ty.needs_subst() && !trait_ty.has_escaping_regions() && + !impl_ty.needs_subst() && !impl_ty.has_escaping_regions()); + + if let ty::TyDynamic(ref trait_ty, ..) = trait_ty.sty { + if let Some(principal) = trait_ty.principal() { + let poly_trait_ref = principal.with_self_ty(tcx, impl_ty); + assert!(!poly_trait_ref.has_escaping_regions()); + + // Walk all methods of the trait, including those of its supertraits + let methods = tcx.vtable_methods(poly_trait_ref); + let methods = methods.iter().cloned().filter_map(|method| method) + .map(|(def_id, substs)| ty::Instance::resolve( + tcx, + ty::ParamEnv::empty(traits::Reveal::All), + def_id, + substs).unwrap()) + .filter(|&instance| should_trans_locally(tcx, &instance)) + .map(|instance| create_fn_trans_item(instance)); + output.extend(methods); + } + // Also add the destructor + visit_drop_use(tcx, impl_ty, false, output); + } +} + +//=----------------------------------------------------------------------------- +// Root Collection +//=----------------------------------------------------------------------------- + +struct RootCollector<'b, 'a: 'b, 'tcx: 'a + 'b> { + tcx: TyCtxt<'a, 'tcx, 'tcx>, + mode: TransItemCollectionMode, + output: &'b mut Vec>, +} + +impl<'b, 'a, 'v> ItemLikeVisitor<'v> for RootCollector<'b, 'a, 'v> { + fn visit_item(&mut self, item: &'v hir::Item) { + match item.node { + hir::ItemExternCrate(..) | + hir::ItemUse(..) | + hir::ItemForeignMod(..) | + hir::ItemTy(..) | + hir::ItemDefaultImpl(..) | + hir::ItemTrait(..) | + hir::ItemMod(..) => { + // Nothing to do, just keep recursing... + } + + hir::ItemImpl(..) => { + if self.mode == TransItemCollectionMode::Eager { + create_trans_items_for_default_impls(self.tcx, + item, + self.output); + } + } + + hir::ItemEnum(_, ref generics) | + hir::ItemStruct(_, ref generics) | + hir::ItemUnion(_, ref generics) => { + if !generics.is_parameterized() { + if self.mode == TransItemCollectionMode::Eager { + let def_id = self.tcx.hir.local_def_id(item.id); + debug!("RootCollector: ADT drop-glue for {}", + def_id_to_string(self.tcx, def_id)); + + let ty = def_ty(self.tcx, def_id, Substs::empty()); + visit_drop_use(self.tcx, ty, true, self.output); + } + } + } + hir::ItemGlobalAsm(..) => { + debug!("RootCollector: ItemGlobalAsm({})", + def_id_to_string(self.tcx, + self.tcx.hir.local_def_id(item.id))); + self.output.push(TransItem::GlobalAsm(item.id)); + } + hir::ItemStatic(..) => { + debug!("RootCollector: ItemStatic({})", + def_id_to_string(self.tcx, + self.tcx.hir.local_def_id(item.id))); + self.output.push(TransItem::Static(item.id)); + } + hir::ItemConst(..) => { + // const items only generate translation items if they are + // actually used somewhere. Just declaring them is insufficient. + } + hir::ItemFn(..) => { + let tcx = self.tcx; + let def_id = tcx.hir.local_def_id(item.id); + + if (self.mode == TransItemCollectionMode::Eager || + !tcx.is_const_fn(def_id) || tcx.is_exported_symbol(def_id)) && + !item_has_type_parameters(tcx, def_id) { + + debug!("RootCollector: ItemFn({})", + def_id_to_string(tcx, def_id)); + + let instance = Instance::mono(tcx, def_id); + self.output.push(TransItem::Fn(instance)); + } + } + } + } + + fn visit_trait_item(&mut self, _: &'v hir::TraitItem) { + // Even if there's a default body with no explicit generics, + // it's still generic over some `Self: Trait`, so not a root. + } + + fn visit_impl_item(&mut self, ii: &'v hir::ImplItem) { + match ii.node { + hir::ImplItemKind::Method(hir::MethodSig { .. }, _) => { + let tcx = self.tcx; + let def_id = tcx.hir.local_def_id(ii.id); + + if (self.mode == TransItemCollectionMode::Eager || + !tcx.is_const_fn(def_id) || + tcx.is_exported_symbol(def_id)) && + !item_has_type_parameters(tcx, def_id) { + debug!("RootCollector: MethodImplItem({})", + def_id_to_string(tcx, def_id)); + + let instance = Instance::mono(tcx, def_id); + self.output.push(TransItem::Fn(instance)); + } + } + _ => { /* Nothing to do here */ } + } + } +} + +fn item_has_type_parameters<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId) -> bool { + let generics = tcx.generics_of(def_id); + generics.parent_types as usize + generics.types.len() > 0 +} + +fn create_trans_items_for_default_impls<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + item: &'tcx hir::Item, + output: &mut Vec>) { + match item.node { + hir::ItemImpl(_, + _, + _, + ref generics, + .., + ref impl_item_refs) => { + if generics.is_type_parameterized() { + return + } + + let impl_def_id = tcx.hir.local_def_id(item.id); + + debug!("create_trans_items_for_default_impls(item={})", + def_id_to_string(tcx, impl_def_id)); + + if let Some(trait_ref) = tcx.impl_trait_ref(impl_def_id) { + let callee_substs = tcx.erase_regions(&trait_ref.substs); + let overridden_methods: FxHashSet<_> = + impl_item_refs.iter() + .map(|iiref| iiref.name) + .collect(); + for method in tcx.provided_trait_methods(trait_ref.def_id) { + if overridden_methods.contains(&method.name) { + continue; + } + + if !tcx.generics_of(method.def_id).types.is_empty() { + continue; + } + + let instance = ty::Instance::resolve(tcx, + ty::ParamEnv::empty(traits::Reveal::All), + method.def_id, + callee_substs).unwrap(); + + let trans_item = create_fn_trans_item(instance); + if trans_item.is_instantiable(tcx) && should_trans_locally(tcx, &instance) { + output.push(trans_item); + } + } + } + } + _ => { + bug!() + } + } +} + +/// Scan the MIR in order to find function calls, closures, and drop-glue +fn collect_neighbours<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + instance: Instance<'tcx>, + const_context: bool, + output: &mut Vec>) +{ + let mir = tcx.instance_mir(instance.def); + + let mut visitor = MirNeighborCollector { + tcx, + mir: &mir, + output, + param_substs: instance.substs, + const_context, + }; + + visitor.visit_mir(&mir); + for promoted in &mir.promoted { + visitor.mir = promoted; + visitor.visit_mir(promoted); + } +} + +fn def_id_to_string<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + def_id: DefId) + -> String { + let mut output = String::new(); + let printer = DefPathBasedNames::new(tcx, false, false); + printer.push_def_path(def_id, &mut output); + output +} diff --git a/src/librustc_trans_utils/common.rs b/src/librustc_trans_utils/common.rs new file mode 100644 index 00000000000..634e37220e2 --- /dev/null +++ b/src/librustc_trans_utils/common.rs @@ -0,0 +1,78 @@ +// Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 or the MIT license +// , at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +#![allow(non_camel_case_types, non_snake_case)] + +//! Code that is useful in various trans modules. + +use rustc::hir::def_id::DefId; +use rustc::hir::map::DefPathData; +use rustc::traits; +use rustc::ty::{self, Ty, TyCtxt}; +use rustc::ty::subst::Substs; + +use syntax::attr; +use syntax_pos::DUMMY_SP; + +pub fn type_is_sized<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, ty: Ty<'tcx>) -> bool { + ty.is_sized(tcx, ty::ParamEnv::empty(traits::Reveal::All), DUMMY_SP) +} + +pub fn requests_inline<'a, 'tcx>( + tcx: TyCtxt<'a, 'tcx, 'tcx>, + instance: &ty::Instance<'tcx> +) -> bool { + if is_inline_instance(tcx, instance) { + return true + } + if let ty::InstanceDef::DropGlue(..) = instance.def { + // Drop glue wants to be instantiated at every translation + // unit, but without an #[inline] hint. We should make this + // available to normal end-users. + return true + } + attr::requests_inline(&instance.def.attrs(tcx)[..]) +} + +pub fn is_inline_instance<'a, 'tcx>( + tcx: TyCtxt<'a, 'tcx, 'tcx>, + instance: &ty::Instance<'tcx> +) -> bool { + let def_id = match instance.def { + ty::InstanceDef::Item(def_id) => def_id, + ty::InstanceDef::DropGlue(_, Some(_)) => return false, + _ => return true + }; + match tcx.def_key(def_id).disambiguated_data.data { + DefPathData::StructCtor | + DefPathData::EnumVariant(..) | + DefPathData::ClosureExpr => true, + _ => false + } +} + +/// Given a DefId and some Substs, produces the monomorphic item type. +pub fn def_ty<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + def_id: DefId, + substs: &'tcx Substs<'tcx>) + -> Ty<'tcx> +{ + let ty = tcx.type_of(def_id); + tcx.trans_apply_param_substs(substs, &ty) +} + +/// Return the substituted type of an instance. +pub fn instance_ty<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + instance: &ty::Instance<'tcx>) + -> Ty<'tcx> +{ + let ty = instance.def.def_ty(tcx); + tcx.trans_apply_param_substs(instance.substs, &ty) +} diff --git a/src/librustc_trans_utils/lib.rs b/src/librustc_trans_utils/lib.rs index 6873befd2bf..bc8f8d5a6da 100644 --- a/src/librustc_trans_utils/lib.rs +++ b/src/librustc_trans_utils/lib.rs @@ -38,6 +38,7 @@ extern crate log; #[macro_use] extern crate rustc; extern crate rustc_back; +extern crate rustc_data_structures; extern crate syntax; extern crate syntax_pos; @@ -49,7 +50,11 @@ use rustc::util::nodemap::NodeSet; use syntax::attr; +mod common; pub mod link; +pub mod collector; +pub mod trans_item; +pub mod monomorphize; pub mod trans_crate; /// check for the #[rustc_error] annotation, which forces an diff --git a/src/librustc_trans_utils/monomorphize.rs b/src/librustc_trans_utils/monomorphize.rs new file mode 100644 index 00000000000..471be439a8f --- /dev/null +++ b/src/librustc_trans_utils/monomorphize.rs @@ -0,0 +1,136 @@ +// Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 or the MIT license +// , at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use rustc::hir::def_id::DefId; +use rustc::middle::lang_items::DropInPlaceFnLangItem; +use rustc::traits; +use rustc::ty::adjustment::CustomCoerceUnsized; +use rustc::ty::subst::{Kind, Subst, Substs}; +use rustc::ty::{self, Ty, TyCtxt}; + +pub use rustc::ty::Instance; + +fn fn_once_adapter_instance<'a, 'tcx>( + tcx: TyCtxt<'a, 'tcx, 'tcx>, + closure_did: DefId, + substs: ty::ClosureSubsts<'tcx>, + ) -> Instance<'tcx> { + debug!("fn_once_adapter_shim({:?}, {:?})", + closure_did, + substs); + let fn_once = tcx.lang_items().fn_once_trait().unwrap(); + let call_once = tcx.associated_items(fn_once) + .find(|it| it.kind == ty::AssociatedKind::Method) + .unwrap().def_id; + let def = ty::InstanceDef::ClosureOnceShim { call_once }; + + let self_ty = tcx.mk_closure_from_closure_substs( + closure_did, substs); + + let sig = tcx.fn_sig(closure_did).subst(tcx, substs.substs); + let sig = tcx.erase_late_bound_regions_and_normalize(&sig); + assert_eq!(sig.inputs().len(), 1); + let substs = tcx.mk_substs([ + Kind::from(self_ty), + Kind::from(sig.inputs()[0]), + ].iter().cloned()); + + debug!("fn_once_adapter_shim: self_ty={:?} sig={:?}", self_ty, sig); + Instance { def, substs } +} + +fn needs_fn_once_adapter_shim(actual_closure_kind: ty::ClosureKind, + trait_closure_kind: ty::ClosureKind) + -> Result +{ + match (actual_closure_kind, trait_closure_kind) { + (ty::ClosureKind::Fn, ty::ClosureKind::Fn) | + (ty::ClosureKind::FnMut, ty::ClosureKind::FnMut) | + (ty::ClosureKind::FnOnce, ty::ClosureKind::FnOnce) => { + // No adapter needed. + Ok(false) + } + (ty::ClosureKind::Fn, ty::ClosureKind::FnMut) => { + // The closure fn `llfn` is a `fn(&self, ...)`. We want a + // `fn(&mut self, ...)`. In fact, at trans time, these are + // basically the same thing, so we can just return llfn. + Ok(false) + } + (ty::ClosureKind::Fn, ty::ClosureKind::FnOnce) | + (ty::ClosureKind::FnMut, ty::ClosureKind::FnOnce) => { + // The closure fn `llfn` is a `fn(&self, ...)` or `fn(&mut + // self, ...)`. We want a `fn(self, ...)`. We can produce + // this by doing something like: + // + // fn call_once(self, ...) { call_mut(&self, ...) } + // fn call_once(mut self, ...) { call_mut(&mut self, ...) } + // + // These are both the same at trans time. + Ok(true) + } + _ => Err(()), + } +} + +pub fn resolve_closure<'a, 'tcx> ( + tcx: TyCtxt<'a, 'tcx, 'tcx>, + def_id: DefId, + substs: ty::ClosureSubsts<'tcx>, + requested_kind: ty::ClosureKind) + -> Instance<'tcx> +{ + let actual_kind = tcx.closure_kind(def_id); + + match needs_fn_once_adapter_shim(actual_kind, requested_kind) { + Ok(true) => fn_once_adapter_instance(tcx, def_id, substs), + _ => Instance::new(def_id, substs.substs) + } +} + +pub fn resolve_drop_in_place<'a, 'tcx>( + tcx: TyCtxt<'a, 'tcx, 'tcx>, + ty: Ty<'tcx>) + -> ty::Instance<'tcx> +{ + let def_id = tcx.require_lang_item(DropInPlaceFnLangItem); + let substs = tcx.intern_substs(&[Kind::from(ty)]); + Instance::resolve(tcx, ty::ParamEnv::empty(traits::Reveal::All), def_id, substs).unwrap() +} + +pub fn custom_coerce_unsize_info<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + source_ty: Ty<'tcx>, + target_ty: Ty<'tcx>) + -> CustomCoerceUnsized { + let def_id = tcx.lang_items().coerce_unsized_trait().unwrap(); + + let trait_ref = ty::Binder(ty::TraitRef { + def_id: def_id, + substs: tcx.mk_substs_trait(source_ty, &[target_ty]) + }); + + match tcx.trans_fulfill_obligation( (ty::ParamEnv::empty(traits::Reveal::All), trait_ref)) { + traits::VtableImpl(traits::VtableImplData { impl_def_id, .. }) => { + tcx.coerce_unsized_info(impl_def_id).custom_kind.unwrap() + } + vtable => { + bug!("invalid CoerceUnsized vtable: {:?}", vtable); + } + } +} + +/// Returns the normalized type of a struct field +pub fn field_ty<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + param_substs: &Substs<'tcx>, + f: &'tcx ty::FieldDef) + -> Ty<'tcx> +{ + tcx.normalize_associated_type(&f.ty(tcx, param_substs)) +} + diff --git a/src/librustc_trans_utils/trans_item.rs b/src/librustc_trans_utils/trans_item.rs new file mode 100644 index 00000000000..0ada39d7d27 --- /dev/null +++ b/src/librustc_trans_utils/trans_item.rs @@ -0,0 +1,464 @@ +// Copyright 2016 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 or the MIT license +// , at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! Walks the crate looking for items/impl-items/trait-items that have +//! either a `rustc_symbol_name` or `rustc_item_path` attribute and +//! generates an error giving, respectively, the symbol name or +//! item-path. This is used for unit testing the code that generates +//! paths etc in all kinds of annoying scenarios. + +use common; +use monomorphize::Instance; +use rustc::hir; +use rustc::hir::def_id::DefId; +use rustc::middle::trans::Linkage; +use rustc::session::config::OptLevel; +use rustc::traits; +use rustc::ty::{self, Ty, TyCtxt}; +use rustc::ty::subst::{Subst, Substs}; +use syntax::ast; +use syntax::attr::{self, InlineAttr}; +use std::fmt::{self, Write}; +use std::iter; + +pub use rustc::middle::trans::TransItem; + +pub fn linkage_by_name(name: &str) -> Option { + use rustc::middle::trans::Linkage::*; + + // Use the names from src/llvm/docs/LangRef.rst here. Most types are only + // applicable to variable declarations and may not really make sense for + // Rust code in the first place but whitelist them anyway and trust that + // the user knows what s/he's doing. Who knows, unanticipated use cases + // may pop up in the future. + // + // ghost, dllimport, dllexport and linkonce_odr_autohide are not supported + // and don't have to be, LLVM treats them as no-ops. + match name { + "appending" => Some(Appending), + "available_externally" => Some(AvailableExternally), + "common" => Some(Common), + "extern_weak" => Some(ExternalWeak), + "external" => Some(External), + "internal" => Some(Internal), + "linkonce" => Some(LinkOnceAny), + "linkonce_odr" => Some(LinkOnceODR), + "private" => Some(Private), + "weak" => Some(WeakAny), + "weak_odr" => Some(WeakODR), + _ => None, + } +} + +/// Describes how a translation item will be instantiated in object files. +#[derive(PartialEq, Eq, Clone, Copy, Debug, Hash)] +pub enum InstantiationMode { + /// There will be exactly one instance of the given TransItem. It will have + /// external linkage so that it can be linked to from other codegen units. + GloballyShared { + /// In some compilation scenarios we may decide to take functions that + /// are typically `LocalCopy` and instead move them to `GloballyShared` + /// to avoid translating them a bunch of times. In this situation, + /// however, our local copy may conflict with other crates also + /// inlining the same function. + /// + /// This flag indicates that this situation is occuring, and informs + /// symbol name calculation that some extra mangling is needed to + /// avoid conflicts. Note that this may eventually go away entirely if + /// ThinLTO enables us to *always* have a globally shared instance of a + /// function within one crate's compilation. + may_conflict: bool, + }, + + /// Each codegen unit containing a reference to the given TransItem will + /// have its own private copy of the function (with internal linkage). + LocalCopy, +} + +pub trait TransItemExt<'a, 'tcx>: fmt::Debug { + fn as_trans_item(&self) -> &TransItem<'tcx>; + + fn instantiation_mode(&self, + tcx: TyCtxt<'a, 'tcx, 'tcx>) + -> InstantiationMode { + let inline_in_all_cgus = + tcx.sess.opts.debugging_opts.inline_in_all_cgus.unwrap_or_else(|| { + tcx.sess.opts.optimize != OptLevel::No + }); + + match *self.as_trans_item() { + TransItem::Fn(ref instance) => { + // If this function isn't inlined or otherwise has explicit + // linkage, then we'll be creating a globally shared version. + if self.explicit_linkage(tcx).is_some() || + !common::requests_inline(tcx, instance) + { + return InstantiationMode::GloballyShared { may_conflict: false } + } + + // At this point we don't have explicit linkage and we're an + // inlined function. If we're inlining into all CGUs then we'll + // be creating a local copy per CGU + if inline_in_all_cgus { + return InstantiationMode::LocalCopy + } + + // Finally, if this is `#[inline(always)]` we're sure to respect + // that with an inline copy per CGU, but otherwise we'll be + // creating one copy of this `#[inline]` function which may + // conflict with upstream crates as it could be an exported + // symbol. + let attrs = instance.def.attrs(tcx); + match attr::find_inline_attr(Some(tcx.sess.diagnostic()), &attrs) { + InlineAttr::Always => InstantiationMode::LocalCopy, + _ => { + InstantiationMode::GloballyShared { may_conflict: true } + } + } + } + TransItem::Static(..) => { + InstantiationMode::GloballyShared { may_conflict: false } + } + TransItem::GlobalAsm(..) => { + InstantiationMode::GloballyShared { may_conflict: false } + } + } + } + + fn explicit_linkage(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Option { + let def_id = match *self.as_trans_item() { + TransItem::Fn(ref instance) => instance.def_id(), + TransItem::Static(node_id) => tcx.hir.local_def_id(node_id), + TransItem::GlobalAsm(..) => return None, + }; + + let attributes = tcx.get_attrs(def_id); + if let Some(name) = attr::first_attr_value_str_by_name(&attributes, "linkage") { + if let Some(linkage) = linkage_by_name(&name.as_str()) { + Some(linkage) + } else { + let span = tcx.hir.span_if_local(def_id); + if let Some(span) = span { + tcx.sess.span_fatal(span, "invalid linkage specified") + } else { + tcx.sess.fatal(&format!("invalid linkage specified: {}", name)) + } + } + } else { + None + } + } + + /// Returns whether this instance is instantiable - whether it has no unsatisfied + /// predicates. + /// + /// In order to translate an item, all of its predicates must hold, because + /// otherwise the item does not make sense. Type-checking ensures that + /// the predicates of every item that is *used by* a valid item *do* + /// hold, so we can rely on that. + /// + /// However, we translate collector roots (reachable items) and functions + /// in vtables when they are seen, even if they are not used, and so they + /// might not be instantiable. For example, a programmer can define this + /// public function: + /// + /// pub fn foo<'a>(s: &'a mut ()) where &'a mut (): Clone { + /// <&mut () as Clone>::clone(&s); + /// } + /// + /// That function can't be translated, because the method `<&mut () as Clone>::clone` + /// does not exist. Luckily for us, that function can't ever be used, + /// because that would require for `&'a mut (): Clone` to hold, so we + /// can just not emit any code, or even a linker reference for it. + /// + /// Similarly, if a vtable method has such a signature, and therefore can't + /// be used, we can just not emit it and have a placeholder (a null pointer, + /// which will never be accessed) in its place. + fn is_instantiable(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> bool { + debug!("is_instantiable({:?})", self); + let (def_id, substs) = match *self.as_trans_item() { + TransItem::Fn(ref instance) => (instance.def_id(), instance.substs), + TransItem::Static(node_id) => (tcx.hir.local_def_id(node_id), Substs::empty()), + // global asm never has predicates + TransItem::GlobalAsm(..) => return true + }; + + let predicates = tcx.predicates_of(def_id).predicates.subst(tcx, substs); + traits::normalize_and_test_predicates(tcx, predicates) + } + + fn to_string(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> String { + let hir_map = &tcx.hir; + + return match *self.as_trans_item() { + TransItem::Fn(instance) => { + to_string_internal(tcx, "fn ", instance) + }, + TransItem::Static(node_id) => { + let def_id = hir_map.local_def_id(node_id); + let instance = Instance::new(def_id, tcx.intern_substs(&[])); + to_string_internal(tcx, "static ", instance) + }, + TransItem::GlobalAsm(..) => { + "global_asm".to_string() + } + }; + + fn to_string_internal<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + prefix: &str, + instance: Instance<'tcx>) + -> String { + let mut result = String::with_capacity(32); + result.push_str(prefix); + let printer = DefPathBasedNames::new(tcx, false, false); + printer.push_instance_as_string(instance, &mut result); + result + } + } +} + +impl<'a, 'tcx> TransItemExt<'a, 'tcx> for TransItem<'tcx> { + fn as_trans_item(&self) -> &TransItem<'tcx> { + self + } +} + +//=----------------------------------------------------------------------------- +// TransItem String Keys +//=----------------------------------------------------------------------------- + +// The code below allows for producing a unique string key for a trans item. +// These keys are used by the handwritten auto-tests, so they need to be +// predictable and human-readable. +// +// Note: A lot of this could looks very similar to what's already in the +// ppaux module. It would be good to refactor things so we only have one +// parameterizable implementation for printing types. + +/// Same as `unique_type_name()` but with the result pushed onto the given +/// `output` parameter. +pub struct DefPathBasedNames<'a, 'tcx: 'a> { + tcx: TyCtxt<'a, 'tcx, 'tcx>, + omit_disambiguators: bool, + omit_local_crate_name: bool, +} + +impl<'a, 'tcx> DefPathBasedNames<'a, 'tcx> { + pub fn new(tcx: TyCtxt<'a, 'tcx, 'tcx>, + omit_disambiguators: bool, + omit_local_crate_name: bool) + -> Self { + DefPathBasedNames { + tcx, + omit_disambiguators, + omit_local_crate_name, + } + } + + pub fn push_type_name(&self, t: Ty<'tcx>, output: &mut String) { + match t.sty { + ty::TyBool => output.push_str("bool"), + ty::TyChar => output.push_str("char"), + ty::TyStr => output.push_str("str"), + ty::TyNever => output.push_str("!"), + ty::TyInt(ast::IntTy::Is) => output.push_str("isize"), + ty::TyInt(ast::IntTy::I8) => output.push_str("i8"), + ty::TyInt(ast::IntTy::I16) => output.push_str("i16"), + ty::TyInt(ast::IntTy::I32) => output.push_str("i32"), + ty::TyInt(ast::IntTy::I64) => output.push_str("i64"), + ty::TyInt(ast::IntTy::I128) => output.push_str("i128"), + ty::TyUint(ast::UintTy::Us) => output.push_str("usize"), + ty::TyUint(ast::UintTy::U8) => output.push_str("u8"), + ty::TyUint(ast::UintTy::U16) => output.push_str("u16"), + ty::TyUint(ast::UintTy::U32) => output.push_str("u32"), + ty::TyUint(ast::UintTy::U64) => output.push_str("u64"), + ty::TyUint(ast::UintTy::U128) => output.push_str("u128"), + ty::TyFloat(ast::FloatTy::F32) => output.push_str("f32"), + ty::TyFloat(ast::FloatTy::F64) => output.push_str("f64"), + ty::TyAdt(adt_def, substs) => { + self.push_def_path(adt_def.did, output); + self.push_type_params(substs, iter::empty(), output); + }, + ty::TyTuple(component_types, _) => { + output.push('('); + for &component_type in component_types { + self.push_type_name(component_type, output); + output.push_str(", "); + } + if !component_types.is_empty() { + output.pop(); + output.pop(); + } + output.push(')'); + }, + ty::TyRawPtr(ty::TypeAndMut { ty: inner_type, mutbl } ) => { + output.push('*'); + match mutbl { + hir::MutImmutable => output.push_str("const "), + hir::MutMutable => output.push_str("mut "), + } + + self.push_type_name(inner_type, output); + }, + ty::TyRef(_, ty::TypeAndMut { ty: inner_type, mutbl }) => { + output.push('&'); + if mutbl == hir::MutMutable { + output.push_str("mut "); + } + + self.push_type_name(inner_type, output); + }, + ty::TyArray(inner_type, len) => { + output.push('['); + self.push_type_name(inner_type, output); + write!(output, "; {}", + len.val.to_const_int().unwrap().to_u64().unwrap()).unwrap(); + output.push(']'); + }, + ty::TySlice(inner_type) => { + output.push('['); + self.push_type_name(inner_type, output); + output.push(']'); + }, + ty::TyDynamic(ref trait_data, ..) => { + if let Some(principal) = trait_data.principal() { + self.push_def_path(principal.def_id(), output); + self.push_type_params(principal.skip_binder().substs, + trait_data.projection_bounds(), + output); + } + }, + ty::TyFnDef(..) | + ty::TyFnPtr(_) => { + let sig = t.fn_sig(self.tcx); + if sig.unsafety() == hir::Unsafety::Unsafe { + output.push_str("unsafe "); + } + + let abi = sig.abi(); + if abi != ::syntax::abi::Abi::Rust { + output.push_str("extern \""); + output.push_str(abi.name()); + output.push_str("\" "); + } + + output.push_str("fn("); + + let sig = self.tcx.erase_late_bound_regions_and_normalize(&sig); + + if !sig.inputs().is_empty() { + for ¶meter_type in sig.inputs() { + self.push_type_name(parameter_type, output); + output.push_str(", "); + } + output.pop(); + output.pop(); + } + + if sig.variadic { + if !sig.inputs().is_empty() { + output.push_str(", ..."); + } else { + output.push_str("..."); + } + } + + output.push(')'); + + if !sig.output().is_nil() { + output.push_str(" -> "); + self.push_type_name(sig.output(), output); + } + }, + ty::TyGenerator(def_id, ref closure_substs, _) | + ty::TyClosure(def_id, ref closure_substs) => { + self.push_def_path(def_id, output); + let generics = self.tcx.generics_of(self.tcx.closure_base_def_id(def_id)); + let substs = closure_substs.substs.truncate_to(self.tcx, generics); + self.push_type_params(substs, iter::empty(), output); + } + ty::TyError | + ty::TyInfer(_) | + ty::TyProjection(..) | + ty::TyParam(_) | + ty::TyAnon(..) => { + bug!("DefPathBasedNames: Trying to create type name for \ + unexpected type: {:?}", t); + } + } + } + + pub fn push_def_path(&self, + def_id: DefId, + output: &mut String) { + let def_path = self.tcx.def_path(def_id); + + // some_crate:: + if !(self.omit_local_crate_name && def_id.is_local()) { + output.push_str(&self.tcx.crate_name(def_path.krate).as_str()); + output.push_str("::"); + } + + // foo::bar::ItemName:: + for part in self.tcx.def_path(def_id).data { + if self.omit_disambiguators { + write!(output, "{}::", part.data.as_interned_str()).unwrap(); + } else { + write!(output, "{}[{}]::", + part.data.as_interned_str(), + part.disambiguator).unwrap(); + } + } + + // remove final "::" + output.pop(); + output.pop(); + } + + fn push_type_params(&self, + substs: &Substs<'tcx>, + projections: I, + output: &mut String) + where I: Iterator> + { + let mut projections = projections.peekable(); + if substs.types().next().is_none() && projections.peek().is_none() { + return; + } + + output.push('<'); + + for type_parameter in substs.types() { + self.push_type_name(type_parameter, output); + output.push_str(", "); + } + + for projection in projections { + let projection = projection.skip_binder(); + let name = &self.tcx.associated_item(projection.item_def_id).name.as_str(); + output.push_str(name); + output.push_str("="); + self.push_type_name(projection.ty, output); + output.push_str(", "); + } + + output.pop(); + output.pop(); + + output.push('>'); + } + + pub fn push_instance_as_string(&self, + instance: Instance<'tcx>, + output: &mut String) { + self.push_def_path(instance.def_id(), output); + self.push_type_params(instance.substs, iter::empty(), output); + } +} -- cgit 1.4.1-3-g733a5