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 codegen.
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::{DepKind, DepTrackingMapConfig};
17 use std::marker::PhantomData;
18 use syntax_pos::DUMMY_SP;
21 use traits::{FulfillmentContext, Obligation, ObligationCause, SelectionContext,
23 use ty::{self, Ty, TyCtxt};
24 use ty::subst::{Subst, Substs};
25 use ty::fold::TypeFoldable;
27 /// Attempts to resolve an obligation to a vtable.. The result is
28 /// a shallow vtable resolution -- meaning that we do not
29 /// (necessarily) resolve all nested obligations on the impl. Note
30 /// that type check should guarantee to us that all nested
31 /// obligations *could be* resolved if we wanted to.
32 /// Assumes that this is run after the entire crate has been successfully type-checked.
33 pub fn codegen_fulfill_obligation<'a, 'tcx>(ty: TyCtxt<'a, 'tcx, 'tcx>,
34 (param_env, trait_ref):
35 (ty::ParamEnv<'tcx>, ty::PolyTraitRef<'tcx>))
38 // Remove any references to regions; this helps improve caching.
39 let trait_ref = ty.erase_regions(&trait_ref);
41 debug!("codegen_fulfill_obligation(trait_ref={:?}, def_id={:?})",
42 (param_env, trait_ref), trait_ref.def_id());
44 // Do the initial selection for the obligation. This yields the
45 // shallow result we are looking for -- that is, what specific impl.
46 ty.infer_ctxt().enter(|infcx| {
47 let mut selcx = SelectionContext::new(&infcx);
49 let obligation_cause = ObligationCause::dummy();
50 let obligation = Obligation::new(obligation_cause,
52 trait_ref.to_poly_trait_predicate());
54 let selection = match selcx.select(&obligation) {
55 Ok(Some(selection)) => selection,
57 // Ambiguity can happen when monomorphizing during trans
58 // expands to some humongo type that never occurred
59 // statically -- this humongo type can then overflow,
60 // leading to an ambiguous result. So report this as an
61 // overflow bug, since I believe this is the only case
62 // where ambiguity can result.
63 bug!("Encountered ambiguity selecting `{:?}` during codegen, \
64 presuming due to overflow",
68 bug!("Encountered error `{:?}` selecting `{:?}` during codegen", e, trait_ref)
72 debug!("fulfill_obligation: selection={:?}", selection);
74 // Currently, we use a fulfillment context to completely resolve
75 // all nested obligations. This is because they can inform the
76 // inference of the impl's type parameters.
77 let mut fulfill_cx = FulfillmentContext::new();
78 let vtable = selection.map(|predicate| {
79 debug!("fulfill_obligation: register_predicate_obligation {:?}", predicate);
80 fulfill_cx.register_predicate_obligation(&infcx, predicate);
82 let vtable = infcx.drain_fulfillment_cx_or_panic(DUMMY_SP, &mut fulfill_cx, &vtable);
84 info!("Cache miss: {:?} => {:?}", trait_ref, vtable);
89 impl<'a, 'tcx> TyCtxt<'a, 'tcx, 'tcx> {
90 /// Monomorphizes a type from the AST by first applying the
91 /// in-scope substitutions and then normalizing any associated
93 pub fn subst_and_normalize_erasing_regions<T>(
95 param_substs: &Substs<'tcx>,
96 param_env: ty::ParamEnv<'tcx>,
100 T: TypeFoldable<'tcx>,
103 "subst_and_normalize_erasing_regions(\
111 let substituted = value.subst(self, param_substs);
112 self.normalize_erasing_regions(param_env, substituted)
116 // Implement DepTrackingMapConfig for `trait_cache`
117 pub struct TraitSelectionCache<'tcx> {
118 data: PhantomData<&'tcx ()>
121 impl<'tcx> DepTrackingMapConfig for TraitSelectionCache<'tcx> {
122 type Key = (ty::ParamEnv<'tcx>, ty::PolyTraitRef<'tcx>);
123 type Value = Vtable<'tcx, ()>;
124 fn to_dep_kind() -> DepKind {
131 pub struct ProjectionCache<'gcx> {
132 data: PhantomData<&'gcx ()>
135 impl<'gcx> DepTrackingMapConfig for ProjectionCache<'gcx> {
137 type Value = Ty<'gcx>;
138 fn to_dep_kind() -> DepKind {
143 impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
144 /// Finishes processes any obligations that remain in the
145 /// fulfillment context, and then returns the result with all type
146 /// variables removed and regions erased. Because this is intended
147 /// for use after type-check has completed, if any errors occur,
148 /// it will panic. It is used during normalization and other cases
149 /// where processing the obligations in `fulfill_cx` may cause
150 /// type inference variables that appear in `result` to be
151 /// unified, and hence we need to process those obligations to get
152 /// the complete picture of the type.
153 fn drain_fulfillment_cx_or_panic<T>(&self,
155 fulfill_cx: &mut FulfillmentContext<'tcx>,
158 where T: TypeFoldable<'tcx> + ty::Lift<'gcx>
160 debug!("drain_fulfillment_cx_or_panic()");
162 // In principle, we only need to do this so long as `result`
163 // contains unbound type parameters. It could be a slight
164 // optimization to stop iterating early.
165 if let Err(errors) = fulfill_cx.select_all_or_error(self) {
166 span_bug!(span, "Encountered errors `{:?}` resolving bounds after type-checking",
170 let result = self.resolve_type_vars_if_possible(result);
171 let result = self.tcx.erase_regions(&result);
173 self.tcx.lift_to_global(&result).unwrap_or_else(||
174 span_bug!(span, "Uninferred types/regions in `{:?}`", result)