1 // Copyright 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 use infer
::{RegionObligation, InferCtxt, InferOk}
;
12 use ty
::{self, Ty, TypeFoldable, ToPolyTraitRef, ToPredicate}
;
13 use ty
::error
::ExpectedFound
;
14 use rustc_data_structures
::obligation_forest
::{ObligationForest, Error}
;
15 use rustc_data_structures
::obligation_forest
::{ForestObligation, ObligationProcessor}
;
16 use std
::marker
::PhantomData
;
17 use hir
::def_id
::DefId
;
19 use super::CodeAmbiguity
;
20 use super::CodeProjectionError
;
21 use super::CodeSelectionError
;
22 use super::{FulfillmentError, FulfillmentErrorCode}
;
23 use super::{ObligationCause, PredicateObligation, Obligation}
;
25 use super::select
::SelectionContext
;
26 use super::{Unimplemented, ConstEvalFailure}
;
28 impl<'tcx
> ForestObligation
for PendingPredicateObligation
<'tcx
> {
29 type Predicate
= ty
::Predicate
<'tcx
>;
31 fn as_predicate(&self) -> &Self::Predicate { &self.obligation.predicate }
34 /// The fulfillment context is used to drive trait resolution. It
35 /// consists of a list of obligations that must be (eventually)
36 /// satisfied. The job is to track which are satisfied, which yielded
37 /// errors, and which are still pending. At any point, users can call
38 /// `select_where_possible`, and the fulfillment context will try to do
39 /// selection, retaining only those obligations that remain
40 /// ambiguous. This may be helpful in pushing type inference
41 /// along. Once all type inference constraints have been generated, the
42 /// method `select_all_or_error` can be used to report any remaining
43 /// ambiguous cases as errors.
45 pub struct FulfillmentContext
<'tcx
> {
46 // A list of all obligations that have been registered with this
47 // fulfillment context.
48 predicates
: ObligationForest
<PendingPredicateObligation
<'tcx
>>,
51 #[derive(Clone, Debug)]
52 pub struct PendingPredicateObligation
<'tcx
> {
53 pub obligation
: PredicateObligation
<'tcx
>,
54 pub stalled_on
: Vec
<Ty
<'tcx
>>,
57 impl<'a
, 'gcx
, 'tcx
> FulfillmentContext
<'tcx
> {
58 /// Creates a new fulfillment context.
59 pub fn new() -> FulfillmentContext
<'tcx
> {
61 predicates
: ObligationForest
::new(),
65 /// "Normalize" a projection type `<SomeType as SomeTrait>::X` by
66 /// creating a fresh type variable `$0` as well as a projection
67 /// predicate `<SomeType as SomeTrait>::X == $0`. When the
68 /// inference engine runs, it will attempt to find an impl of
69 /// `SomeTrait` or a where clause that lets us unify `$0` with
70 /// something concrete. If this fails, we'll unify `$0` with
71 /// `projection_ty` again.
72 pub fn normalize_projection_type(&mut self,
73 infcx
: &InferCtxt
<'a
, 'gcx
, 'tcx
>,
74 param_env
: ty
::ParamEnv
<'tcx
>,
75 projection_ty
: ty
::ProjectionTy
<'tcx
>,
76 cause
: ObligationCause
<'tcx
>)
79 debug
!("normalize_projection_type(projection_ty={:?})",
82 assert
!(!projection_ty
.has_escaping_regions());
84 // FIXME(#20304) -- cache
86 let mut selcx
= SelectionContext
::new(infcx
);
87 let normalized
= project
::normalize_projection_type(&mut selcx
,
93 for obligation
in normalized
.obligations
{
94 self.register_predicate_obligation(infcx
, obligation
);
97 debug
!("normalize_projection_type: result={:?}", normalized
.value
);
102 /// Requires that `ty` must implement the trait with `def_id` in
103 /// the given environment. This trait must not have any type
104 /// parameters (except for `Self`).
105 pub fn register_bound(&mut self,
106 infcx
: &InferCtxt
<'a
, 'gcx
, 'tcx
>,
107 param_env
: ty
::ParamEnv
<'tcx
>,
110 cause
: ObligationCause
<'tcx
>)
112 let trait_ref
= ty
::TraitRef
{
114 substs
: infcx
.tcx
.mk_substs_trait(ty
, &[]),
116 self.register_predicate_obligation(infcx
, Obligation
{
120 predicate
: trait_ref
.to_predicate()
124 pub fn register_predicate_obligation(&mut self,
125 infcx
: &InferCtxt
<'a
, 'gcx
, 'tcx
>,
126 obligation
: PredicateObligation
<'tcx
>)
128 // this helps to reduce duplicate errors, as well as making
129 // debug output much nicer to read and so on.
130 let obligation
= infcx
.resolve_type_vars_if_possible(&obligation
);
132 debug
!("register_predicate_obligation(obligation={:?})", obligation
);
134 assert
!(!infcx
.is_in_snapshot());
136 self.predicates
.register_obligation(PendingPredicateObligation
{
142 pub fn register_predicate_obligations
<I
>(&mut self,
143 infcx
: &InferCtxt
<'a
, 'gcx
, 'tcx
>,
145 where I
: IntoIterator
<Item
= PredicateObligation
<'tcx
>>
147 for obligation
in obligations
{
148 self.register_predicate_obligation(infcx
, obligation
);
152 pub fn select_all_or_error(&mut self,
153 infcx
: &InferCtxt
<'a
, 'gcx
, 'tcx
>)
154 -> Result
<(),Vec
<FulfillmentError
<'tcx
>>>
156 self.select_where_possible(infcx
)?
;
159 self.predicates
.to_errors(CodeAmbiguity
)
161 .map(|e
| to_fulfillment_error(e
))
163 if errors
.is_empty() {
170 pub fn select_where_possible(&mut self,
171 infcx
: &InferCtxt
<'a
, 'gcx
, 'tcx
>)
172 -> Result
<(),Vec
<FulfillmentError
<'tcx
>>>
174 let mut selcx
= SelectionContext
::new(infcx
);
175 self.select(&mut selcx
)
178 pub fn pending_obligations(&self) -> Vec
<PendingPredicateObligation
<'tcx
>> {
179 self.predicates
.pending_obligations()
182 /// Attempts to select obligations using `selcx`. If `only_new_obligations` is true, then it
183 /// only attempts to select obligations that haven't been seen before.
184 fn select(&mut self, selcx
: &mut SelectionContext
<'a
, 'gcx
, 'tcx
>)
185 -> Result
<(),Vec
<FulfillmentError
<'tcx
>>> {
186 debug
!("select(obligation-forest-size={})", self.predicates
.len());
188 let mut errors
= Vec
::new();
191 debug
!("select: starting another iteration");
193 // Process pending obligations.
194 let outcome
= self.predicates
.process_obligations(&mut FulfillProcessor { selcx }
);
195 debug
!("select: outcome={:?}", outcome
);
197 // FIXME: if we kept the original cache key, we could mark projection
198 // obligations as complete for the projection cache here.
201 outcome
.errors
.into_iter()
202 .map(|e
| to_fulfillment_error(e
)));
204 // If nothing new was added, no need to keep looping.
210 debug
!("select({} predicates remaining, {} errors) done",
211 self.predicates
.len(), errors
.len());
213 if errors
.is_empty() {
221 struct FulfillProcessor
<'a
, 'b
: 'a
, 'gcx
: 'tcx
, 'tcx
: 'b
> {
222 selcx
: &'a
mut SelectionContext
<'b
, 'gcx
, 'tcx
>,
225 impl<'a
, 'b
, 'gcx
, 'tcx
> ObligationProcessor
for FulfillProcessor
<'a
, 'b
, 'gcx
, 'tcx
> {
226 type Obligation
= PendingPredicateObligation
<'tcx
>;
227 type Error
= FulfillmentErrorCode
<'tcx
>;
229 fn process_obligation(&mut self,
230 obligation
: &mut Self::Obligation
)
231 -> Result
<Option
<Vec
<Self::Obligation
>>, Self::Error
>
233 process_predicate(self.selcx
, obligation
)
234 .map(|os
| os
.map(|os
| os
.into_iter().map(|o
| PendingPredicateObligation
{
240 fn process_backedge
<'c
, I
>(&mut self, cycle
: I
,
241 _marker
: PhantomData
<&'c PendingPredicateObligation
<'tcx
>>)
242 where I
: Clone
+ Iterator
<Item
=&'c PendingPredicateObligation
<'tcx
>>,
244 if self.selcx
.coinductive_match(cycle
.clone().map(|s
| s
.obligation
.predicate
)) {
245 debug
!("process_child_obligations: coinductive match");
247 let cycle
: Vec
<_
> = cycle
.map(|c
| c
.obligation
.clone()).collect();
248 self.selcx
.infcx().report_overflow_error_cycle(&cycle
);
253 /// Return the set of type variables contained in a trait ref
254 fn trait_ref_type_vars
<'a
, 'gcx
, 'tcx
>(selcx
: &mut SelectionContext
<'a
, 'gcx
, 'tcx
>,
255 t
: ty
::PolyTraitRef
<'tcx
>) -> Vec
<Ty
<'tcx
>>
257 t
.skip_binder() // ok b/c this check doesn't care about regions
259 .map(|t
| selcx
.infcx().resolve_type_vars_if_possible(&t
))
260 .filter(|t
| t
.has_infer_types())
261 .flat_map(|t
| t
.walk())
262 .filter(|t
| match t
.sty { ty::TyInfer(_) => true, _ => false }
)
266 /// Processes a predicate obligation and returns either:
267 /// - `Ok(Some(v))` if the predicate is true, presuming that `v` are also true
268 /// - `Ok(None)` if we don't have enough info to be sure
269 /// - `Err` if the predicate does not hold
270 fn process_predicate
<'a
, 'gcx
, 'tcx
>(
271 selcx
: &mut SelectionContext
<'a
, 'gcx
, 'tcx
>,
272 pending_obligation
: &mut PendingPredicateObligation
<'tcx
>)
273 -> Result
<Option
<Vec
<PredicateObligation
<'tcx
>>>,
274 FulfillmentErrorCode
<'tcx
>>
276 // if we were stalled on some unresolved variables, first check
277 // whether any of them have been resolved; if not, don't bother
278 // doing more work yet
279 if !pending_obligation
.stalled_on
.is_empty() {
280 if pending_obligation
.stalled_on
.iter().all(|&ty
| {
281 let resolved_ty
= selcx
.infcx().shallow_resolve(&ty
);
282 resolved_ty
== ty
// nothing changed here
284 debug
!("process_predicate: pending obligation {:?} still stalled on {:?}",
285 selcx
.infcx().resolve_type_vars_if_possible(&pending_obligation
.obligation
),
286 pending_obligation
.stalled_on
);
289 pending_obligation
.stalled_on
= vec
![];
292 let obligation
= &mut pending_obligation
.obligation
;
294 if obligation
.predicate
.has_infer_types() {
295 obligation
.predicate
= selcx
.infcx().resolve_type_vars_if_possible(&obligation
.predicate
);
298 match obligation
.predicate
{
299 ty
::Predicate
::Trait(ref data
) => {
300 let trait_obligation
= obligation
.with(data
.clone());
302 if data
.is_global() {
303 // no type variables present, can use evaluation for better caching.
304 // FIXME: consider caching errors too.
306 // make defaulted unit go through the slow path for better warnings,
307 // please remove this when the warnings are removed.
308 !trait_obligation
.predicate
.skip_binder().self_ty().is_defaulted_unit() &&
309 selcx
.evaluate_obligation_conservatively(&obligation
) {
310 debug
!("selecting trait `{:?}` at depth {} evaluated to holds",
311 data
, obligation
.recursion_depth
);
312 return Ok(Some(vec
![]))
316 match selcx
.select(&trait_obligation
) {
317 Ok(Some(vtable
)) => {
318 debug
!("selecting trait `{:?}` at depth {} yielded Ok(Some)",
319 data
, obligation
.recursion_depth
);
320 Ok(Some(vtable
.nested_obligations()))
323 debug
!("selecting trait `{:?}` at depth {} yielded Ok(None)",
324 data
, obligation
.recursion_depth
);
326 // This is a bit subtle: for the most part, the
327 // only reason we can fail to make progress on
328 // trait selection is because we don't have enough
329 // information about the types in the trait. One
330 // exception is that we sometimes haven't decided
331 // what kind of closure a closure is. *But*, in
332 // that case, it turns out, the type of the
333 // closure will also change, because the closure
334 // also includes references to its upvars as part
335 // of its type, and those types are resolved at
338 // FIXME(#32286) logic seems false if no upvars
339 pending_obligation
.stalled_on
=
340 trait_ref_type_vars(selcx
, data
.to_poly_trait_ref());
342 debug
!("process_predicate: pending obligation {:?} now stalled on {:?}",
343 selcx
.infcx().resolve_type_vars_if_possible(obligation
),
344 pending_obligation
.stalled_on
);
348 Err(selection_err
) => {
349 info
!("selecting trait `{:?}` at depth {} yielded Err",
350 data
, obligation
.recursion_depth
);
352 Err(CodeSelectionError(selection_err
))
357 ty
::Predicate
::Equate(ref binder
) => {
358 match selcx
.infcx().equality_predicate(&obligation
.cause
,
359 obligation
.param_env
,
361 Ok(InferOk { obligations, value: () }
) => {
362 Ok(Some(obligations
))
364 Err(_
) => Err(CodeSelectionError(Unimplemented
)),
368 ty
::Predicate
::RegionOutlives(ref binder
) => {
369 match selcx
.infcx().region_outlives_predicate(&obligation
.cause
, binder
) {
370 Ok(()) => Ok(Some(Vec
::new())),
371 Err(_
) => Err(CodeSelectionError(Unimplemented
)),
375 ty
::Predicate
::TypeOutlives(ref binder
) => {
376 // Check if there are higher-ranked regions.
377 match selcx
.tcx().no_late_bound_regions(binder
) {
378 // If there are, inspect the underlying type further.
380 // Convert from `Binder<OutlivesPredicate<Ty, Region>>` to `Binder<Ty>`.
381 let binder
= binder
.map_bound_ref(|pred
| pred
.0);
383 // Check if the type has any bound regions.
384 match selcx
.tcx().no_late_bound_regions(&binder
) {
385 // If so, this obligation is an error (for now). Eventually we should be
386 // able to support additional cases here, like `for<'a> &'a str: 'a`.
388 Err(CodeSelectionError(Unimplemented
))
390 // Otherwise, we have something of the form
391 // `for<'a> T: 'a where 'a not in T`, which we can treat as `T: 'static`.
393 let r_static
= selcx
.tcx().types
.re_static
;
394 selcx
.infcx().register_region_obligation(
395 obligation
.cause
.body_id
,
398 sub_region
: r_static
,
399 cause
: obligation
.cause
.clone(),
405 // If there aren't, register the obligation.
406 Some(ty
::OutlivesPredicate(t_a
, r_b
)) => {
407 selcx
.infcx().register_region_obligation(
408 obligation
.cause
.body_id
,
412 cause
: obligation
.cause
.clone()
419 ty
::Predicate
::Projection(ref data
) => {
420 let project_obligation
= obligation
.with(data
.clone());
421 match project
::poly_project_and_unify_type(selcx
, &project_obligation
) {
423 let tcx
= selcx
.tcx();
424 pending_obligation
.stalled_on
=
425 trait_ref_type_vars(selcx
, data
.to_poly_trait_ref(tcx
));
429 Err(e
) => Err(CodeProjectionError(e
))
433 ty
::Predicate
::ObjectSafe(trait_def_id
) => {
434 if !selcx
.tcx().is_object_safe(trait_def_id
) {
435 Err(CodeSelectionError(Unimplemented
))
441 ty
::Predicate
::ClosureKind(closure_def_id
, kind
) => {
442 match selcx
.infcx().closure_kind(closure_def_id
) {
443 Some(closure_kind
) => {
444 if closure_kind
.extends(kind
) {
447 Err(CodeSelectionError(Unimplemented
))
456 ty
::Predicate
::WellFormed(ty
) => {
457 match ty
::wf
::obligations(selcx
.infcx(),
458 obligation
.param_env
,
459 obligation
.cause
.body_id
,
460 ty
, obligation
.cause
.span
) {
462 pending_obligation
.stalled_on
= vec
![ty
];
469 ty
::Predicate
::Subtype(ref subtype
) => {
470 match selcx
.infcx().subtype_predicate(&obligation
.cause
,
471 obligation
.param_env
,
474 // none means that both are unresolved
475 pending_obligation
.stalled_on
= vec
![subtype
.skip_binder().a
,
476 subtype
.skip_binder().b
];
480 Ok(Some(ok
.obligations
))
483 let expected_found
= ExpectedFound
::new(subtype
.skip_binder().a_is_expected
,
484 subtype
.skip_binder().a
,
485 subtype
.skip_binder().b
);
486 Err(FulfillmentErrorCode
::CodeSubtypeError(expected_found
, err
))
491 ty
::Predicate
::ConstEvaluatable(def_id
, substs
) => {
492 match selcx
.tcx().lift_to_global(&obligation
.param_env
) {
497 match selcx
.tcx().lift_to_global(&substs
) {
499 pending_obligation
.stalled_on
= substs
.types().collect();
503 match selcx
.tcx().at(obligation
.cause
.span
)
504 .const_eval(param_env
.and((def_id
, substs
))) {
505 Ok(_
) => Ok(Some(vec
![])),
506 Err(e
) => Err(CodeSelectionError(ConstEvalFailure(e
)))
516 fn to_fulfillment_error
<'tcx
>(
517 error
: Error
<PendingPredicateObligation
<'tcx
>, FulfillmentErrorCode
<'tcx
>>)
518 -> FulfillmentError
<'tcx
>
520 let obligation
= error
.backtrace
.into_iter().next().unwrap().obligation
;
521 FulfillmentError
::new(obligation
, error
.error
)