1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 // This file contains various trait resolution methods used by trans.
12 // They all assume regions can be erased and monomorphic types. It
13 // seems likely that they should eventually be merged into more
16 use dep_graph::{DepGraph, DepNode, DepTrackingMap, DepTrackingMapConfig};
17 use hir::def_id::DefId;
18 use infer::TransNormalize;
19 use std::cell::RefCell;
20 use std::marker::PhantomData;
23 use traits::{FulfillmentContext, Obligation, ObligationCause, Reveal, SelectionContext, Vtable};
24 use ty::{self, Ty, TyCtxt};
25 use ty::subst::{Subst, Substs};
26 use ty::fold::{TypeFoldable, TypeFolder};
27 use util::common::MemoizationMap;
29 impl<'a, 'tcx> TyCtxt<'a, 'tcx, 'tcx> {
30 /// Attempts to resolve an obligation to a vtable.. The result is
31 /// a shallow vtable resolution -- meaning that we do not
32 /// (necessarily) resolve all nested obligations on the impl. Note
33 /// that type check should guarantee to us that all nested
34 /// obligations *could be* resolved if we wanted to.
35 pub fn trans_fulfill_obligation(self,
37 trait_ref: ty::PolyTraitRef<'tcx>)
40 // Remove any references to regions; this helps improve caching.
41 let trait_ref = self.erase_regions(&trait_ref);
43 self.trans_trait_caches.trait_cache.memoize(trait_ref, || {
44 debug!("trans::fulfill_obligation(trait_ref={:?}, def_id={:?})",
45 trait_ref, trait_ref.def_id());
47 // Do the initial selection for the obligation. This yields the
48 // shallow result we are looking for -- that is, what specific impl.
49 self.infer_ctxt((), Reveal::All).enter(|infcx| {
50 let mut selcx = SelectionContext::new(&infcx);
52 let obligation_cause = ObligationCause::misc(span,
54 let obligation = Obligation::new(obligation_cause,
55 trait_ref.to_poly_trait_predicate());
57 let selection = match selcx.select(&obligation) {
58 Ok(Some(selection)) => selection,
60 // Ambiguity can happen when monomorphizing during trans
61 // expands to some humongo type that never occurred
62 // statically -- this humongo type can then overflow,
63 // leading to an ambiguous result. So report this as an
64 // overflow bug, since I believe this is the only case
65 // where ambiguity can result.
66 debug!("Encountered ambiguity selecting `{:?}` during trans, \
67 presuming due to overflow",
69 self.sess.span_fatal(span,
70 "reached the recursion limit during monomorphization \
71 (selection ambiguity)");
74 span_bug!(span, "Encountered error `{:?}` selecting `{:?}` during trans",
79 debug!("fulfill_obligation: selection={:?}", selection);
81 // Currently, we use a fulfillment context to completely resolve
82 // all nested obligations. This is because they can inform the
83 // inference of the impl's type parameters.
84 let mut fulfill_cx = FulfillmentContext::new();
85 let vtable = selection.map(|predicate| {
86 debug!("fulfill_obligation: register_predicate_obligation {:?}", predicate);
87 fulfill_cx.register_predicate_obligation(&infcx, predicate);
89 let vtable = infcx.drain_fulfillment_cx_or_panic(span, &mut fulfill_cx, &vtable);
91 info!("Cache miss: {:?} => {:?}", trait_ref, vtable);
97 /// Monomorphizes a type from the AST by first applying the in-scope
98 /// substitutions and then normalizing any associated types.
99 pub fn trans_apply_param_substs<T>(self,
100 param_substs: &Substs<'tcx>,
103 where T: TransNormalize<'tcx>
105 debug!("apply_param_substs(param_substs={:?}, value={:?})", param_substs, value);
106 let substituted = value.subst(self, param_substs);
107 let substituted = self.erase_regions(&substituted);
108 AssociatedTypeNormalizer::new(self).fold(&substituted)
112 struct AssociatedTypeNormalizer<'a, 'gcx: 'a> {
113 tcx: TyCtxt<'a, 'gcx, 'gcx>,
116 impl<'a, 'gcx> AssociatedTypeNormalizer<'a, 'gcx> {
117 fn new(tcx: TyCtxt<'a, 'gcx, 'gcx>) -> Self {
118 AssociatedTypeNormalizer { tcx }
121 fn fold<T:TypeFoldable<'gcx>>(&mut self, value: &T) -> T {
122 if !value.has_projection_types() {
125 value.fold_with(self)
130 impl<'a, 'gcx> TypeFolder<'gcx, 'gcx> for AssociatedTypeNormalizer<'a, 'gcx> {
131 fn tcx<'c>(&'c self) -> TyCtxt<'c, 'gcx, 'gcx> {
135 fn fold_ty(&mut self, ty: Ty<'gcx>) -> Ty<'gcx> {
136 if !ty.has_projection_types() {
139 self.tcx.trans_trait_caches.project_cache.memoize(ty, || {
140 debug!("AssociatedTypeNormalizer: ty={:?}", ty);
141 self.tcx.normalize_associated_type(&ty)
147 /// Specializes caches used in trans -- in particular, they assume all
148 /// types are fully monomorphized and that free regions can be erased.
149 pub struct TransTraitCaches<'tcx> {
150 trait_cache: RefCell<DepTrackingMap<TraitSelectionCache<'tcx>>>,
151 project_cache: RefCell<DepTrackingMap<ProjectionCache<'tcx>>>,
154 impl<'tcx> TransTraitCaches<'tcx> {
155 pub fn new(graph: DepGraph) -> Self {
157 trait_cache: RefCell::new(DepTrackingMap::new(graph.clone())),
158 project_cache: RefCell::new(DepTrackingMap::new(graph)),
163 // Implement DepTrackingMapConfig for `trait_cache`
164 pub struct TraitSelectionCache<'tcx> {
165 data: PhantomData<&'tcx ()>
168 impl<'tcx> DepTrackingMapConfig for TraitSelectionCache<'tcx> {
169 type Key = ty::PolyTraitRef<'tcx>;
170 type Value = Vtable<'tcx, ()>;
171 fn to_dep_node(key: &ty::PolyTraitRef<'tcx>) -> DepNode<DefId> {
172 key.to_poly_trait_predicate().dep_node()
178 pub struct ProjectionCache<'gcx> {
179 data: PhantomData<&'gcx ()>
182 impl<'gcx> DepTrackingMapConfig for ProjectionCache<'gcx> {
184 type Value = Ty<'gcx>;
185 fn to_dep_node(key: &Self::Key) -> DepNode<DefId> {
186 // Ideally, we'd just put `key` into the dep-node, but we
187 // can't put full types in there. So just collect up all the
188 // def-ids of structs/enums as well as any traits that we
189 // project out of. It doesn't matter so much what we do here,
190 // except that if we are too coarse, we'll create overly
191 // coarse edges between impls and the trans. For example, if
192 // we just used the def-id of things we are projecting out of,
193 // then the key for `<Foo as SomeTrait>::T` and `<Bar as
194 // SomeTrait>::T` would both share a dep-node
195 // (`TraitSelect(SomeTrait)`), and hence the impls for both
196 // `Foo` and `Bar` would be considered inputs. So a change to
197 // `Bar` would affect things that just normalized `Foo`.
198 // Anyway, this heuristic is not ideal, but better than
200 let def_ids: Vec<DefId> =
202 .filter_map(|t| match t.sty {
203 ty::TyAdt(adt_def, _) => Some(adt_def.did),
204 ty::TyProjection(ref proj) => Some(proj.trait_ref.def_id),
209 DepNode::ProjectionCache { def_ids: def_ids }