1 // Copyright 2018 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 //! Provider for the `implied_outlives_bounds` query.
12 //! Do not call this query directory. See [`rustc::traits::query::implied_outlives_bounds`].
14 use rustc::infer::InferCtxt;
15 use rustc::infer::canonical::{self, Canonical};
16 use rustc::traits::{TraitEngine, TraitEngineExt};
17 use rustc::traits::query::outlives_bounds::OutlivesBound;
18 use rustc::traits::query::{CanonicalTyGoal, Fallible, NoSolution};
19 use rustc::ty::{self, Ty, TyCtxt, TypeFoldable};
20 use rustc::ty::outlives::Component;
21 use rustc::ty::query::Providers;
23 use syntax::ast::DUMMY_NODE_ID;
24 use syntax::source_map::DUMMY_SP;
25 use rustc::traits::FulfillmentContext;
27 use rustc_data_structures::sync::Lrc;
29 crate fn provide(p: &mut Providers) {
31 implied_outlives_bounds,
36 fn implied_outlives_bounds<'tcx>(
37 tcx: TyCtxt<'_, 'tcx, 'tcx>,
38 goal: CanonicalTyGoal<'tcx>,
40 Lrc<Canonical<'tcx, canonical::QueryResponse<'tcx, Vec<OutlivesBound<'tcx>>>>>,
44 .enter_canonical_trait_query(&goal, |infcx, _fulfill_cx, key| {
45 let (param_env, ty) = key.into_parts();
46 compute_implied_outlives_bounds(&infcx, param_env, ty)
50 fn compute_implied_outlives_bounds<'tcx>(
51 infcx: &InferCtxt<'_, '_, 'tcx>,
52 param_env: ty::ParamEnv<'tcx>,
54 ) -> Fallible<Vec<OutlivesBound<'tcx>>> {
57 // Sometimes when we ask what it takes for T: WF, we get back that
58 // U: WF is required; in that case, we push U onto this stack and
59 // process it next. Currently (at least) these resulting
60 // predicates are always guaranteed to be a subset of the original
61 // type, so we need not fear non-termination.
62 let mut wf_types = vec![ty];
64 let mut implied_bounds = vec![];
66 let mut fulfill_cx = FulfillmentContext::new();
68 while let Some(ty) = wf_types.pop() {
69 // Compute the obligations for `ty` to be well-formed. If `ty` is
70 // an unresolved inference variable, just substituted an empty set
71 // -- because the return type here is going to be things we *add*
72 // to the environment, it's always ok for this set to be smaller
73 // than the ultimate set. (Note: normally there won't be
74 // unresolved inference variables here anyway, but there might be
75 // during typeck under some circumstances.)
77 wf::obligations(infcx, param_env, DUMMY_NODE_ID, ty, DUMMY_SP).unwrap_or(vec![]);
79 // NB: All of these predicates *ought* to be easily proven
80 // true. In fact, their correctness is (mostly) implied by
81 // other parts of the program. However, in #42552, we had
82 // an annoying scenario where:
84 // - Some `T::Foo` gets normalized, resulting in a
85 // variable `_1` and a `T: Trait<Foo=_1>` constraint
86 // (not sure why it couldn't immediately get
87 // solved). This result of `_1` got cached.
88 // - These obligations were dropped on the floor here,
89 // rather than being registered.
90 // - Then later we would get a request to normalize
91 // `T::Foo` which would result in `_1` being used from
92 // the cache, but hence without the `T: Trait<Foo=_1>`
93 // constraint. As a result, `_1` never gets resolved,
94 // and we get an ICE (in dropck).
96 // Therefore, we register any predicates involving
97 // inference variables. We restrict ourselves to those
98 // involving inference variables both for efficiency and
99 // to avoids duplicate errors that otherwise show up.
100 fulfill_cx.register_predicate_obligations(
104 .filter(|o| o.predicate.has_infer_types())
108 // From the full set of obligations, just filter down to the
109 // region relationships.
110 implied_bounds.extend(obligations.into_iter().flat_map(|obligation| {
111 assert!(!obligation.has_escaping_bound_vars());
112 match obligation.predicate {
113 ty::Predicate::Trait(..) |
114 ty::Predicate::Subtype(..) |
115 ty::Predicate::Projection(..) |
116 ty::Predicate::ClosureKind(..) |
117 ty::Predicate::ObjectSafe(..) |
118 ty::Predicate::ConstEvaluatable(..) => vec![],
120 ty::Predicate::WellFormed(subty) => {
121 wf_types.push(subty);
125 ty::Predicate::RegionOutlives(ref data) => match data.no_bound_vars() {
127 Some(ty::OutlivesPredicate(r_a, r_b)) => {
128 vec![OutlivesBound::RegionSubRegion(r_b, r_a)]
132 ty::Predicate::TypeOutlives(ref data) => match data.no_bound_vars() {
134 Some(ty::OutlivesPredicate(ty_a, r_b)) => {
135 let ty_a = infcx.resolve_type_vars_if_possible(&ty_a);
136 let components = tcx.outlives_components(ty_a);
137 implied_bounds_from_components(r_b, components)
144 // Ensure that those obligations that we had to solve
145 // get solved *here*.
146 match fulfill_cx.select_all_or_error(infcx) {
147 Ok(()) => Ok(implied_bounds),
148 Err(_) => Err(NoSolution),
152 /// When we have an implied bound that `T: 'a`, we can further break
153 /// this down to determine what relationships would have to hold for
154 /// `T: 'a` to hold. We get to assume that the caller has validated
155 /// those relationships.
156 fn implied_bounds_from_components(
157 sub_region: ty::Region<'tcx>,
158 sup_components: Vec<Component<'tcx>>,
159 ) -> Vec<OutlivesBound<'tcx>> {
162 .filter_map(|component| {
164 Component::Region(r) =>
165 Some(OutlivesBound::RegionSubRegion(sub_region, r)),
166 Component::Param(p) =>
167 Some(OutlivesBound::RegionSubParam(sub_region, p)),
168 Component::Projection(p) =>
169 Some(OutlivesBound::RegionSubProjection(sub_region, p)),
170 Component::EscapingProjection(_) =>
171 // If the projection has escaping regions, don't
172 // try to infer any implied bounds even for its
173 // free components. This is conservative, because
174 // the caller will still have to prove that those
175 // free components outlive `sub_region`. But the
176 // idea is that the WAY that the caller proves
177 // that may change in the future and we want to
178 // give ourselves room to get smarter here.
180 Component::UnresolvedInferenceVariable(..) =>