1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
//! Provider for the `implied_outlives_bounds` query.
//! Do not call this query directory. See
//! [`rustc_trait_selection::traits::query::type_op::implied_outlives_bounds`].

use rustc_hir as hir;
use rustc_infer::infer::canonical::{self, Canonical};
use rustc_infer::infer::outlives::components::{push_outlives_components, Component};
use rustc_infer::infer::{InferCtxt, TyCtxtInferExt};
use rustc_infer::traits::query::OutlivesBound;
use rustc_infer::traits::TraitEngineExt as _;
use rustc_middle::ty::query::Providers;
use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitable};
use rustc_span::source_map::DUMMY_SP;
use rustc_trait_selection::infer::InferCtxtBuilderExt;
use rustc_trait_selection::traits::query::{CanonicalTyGoal, Fallible, NoSolution};
use rustc_trait_selection::traits::wf;
use rustc_trait_selection::traits::{TraitEngine, TraitEngineExt};
use smallvec::{smallvec, SmallVec};

pub(crate) fn provide(p: &mut Providers) {
    *p = Providers { implied_outlives_bounds, ..*p };
}

fn implied_outlives_bounds<'tcx>(
    tcx: TyCtxt<'tcx>,
    goal: CanonicalTyGoal<'tcx>,
) -> Result<
    &'tcx Canonical<'tcx, canonical::QueryResponse<'tcx, Vec<OutlivesBound<'tcx>>>>,
    NoSolution,
> {
    tcx.infer_ctxt().enter_canonical_trait_query(&goal, |infcx, _fulfill_cx, key| {
        let (param_env, ty) = key.into_parts();
        compute_implied_outlives_bounds(&infcx, param_env, ty)
    })
}

fn compute_implied_outlives_bounds<'tcx>(
    infcx: &InferCtxt<'_, 'tcx>,
    param_env: ty::ParamEnv<'tcx>,
    ty: Ty<'tcx>,
) -> Fallible<Vec<OutlivesBound<'tcx>>> {
    let tcx = infcx.tcx;

    // Sometimes when we ask what it takes for T: WF, we get back that
    // U: WF is required; in that case, we push U onto this stack and
    // process it next. Because the resulting predicates aren't always
    // guaranteed to be a subset of the original type, so we need to store the
    // WF args we've computed in a set.
    let mut checked_wf_args = rustc_data_structures::fx::FxHashSet::default();
    let mut wf_args = vec![ty.into()];

    let mut implied_bounds = vec![];

    let mut fulfill_cx = <dyn TraitEngine<'tcx>>::new(tcx);

    while let Some(arg) = wf_args.pop() {
        if !checked_wf_args.insert(arg) {
            continue;
        }

        // Compute the obligations for `arg` to be well-formed. If `arg` is
        // an unresolved inference variable, just substituted an empty set
        // -- because the return type here is going to be things we *add*
        // to the environment, it's always ok for this set to be smaller
        // than the ultimate set. (Note: normally there won't be
        // unresolved inference variables here anyway, but there might be
        // during typeck under some circumstances.)
        let obligations = wf::obligations(infcx, param_env, hir::CRATE_HIR_ID, 0, arg, DUMMY_SP)
            .unwrap_or_default();

        // N.B., all of these predicates *ought* to be easily proven
        // true. In fact, their correctness is (mostly) implied by
        // other parts of the program. However, in #42552, we had
        // an annoying scenario where:
        //
        // - Some `T::Foo` gets normalized, resulting in a
        //   variable `_1` and a `T: Trait<Foo=_1>` constraint
        //   (not sure why it couldn't immediately get
        //   solved). This result of `_1` got cached.
        // - These obligations were dropped on the floor here,
        //   rather than being registered.
        // - Then later we would get a request to normalize
        //   `T::Foo` which would result in `_1` being used from
        //   the cache, but hence without the `T: Trait<Foo=_1>`
        //   constraint. As a result, `_1` never gets resolved,
        //   and we get an ICE (in dropck).
        //
        // Therefore, we register any predicates involving
        // inference variables. We restrict ourselves to those
        // involving inference variables both for efficiency and
        // to avoids duplicate errors that otherwise show up.
        fulfill_cx.register_predicate_obligations(
            infcx,
            obligations.iter().filter(|o| o.predicate.has_infer_types_or_consts()).cloned(),
        );

        // From the full set of obligations, just filter down to the
        // region relationships.
        implied_bounds.extend(obligations.into_iter().flat_map(|obligation| {
            assert!(!obligation.has_escaping_bound_vars());
            match obligation.predicate.kind().no_bound_vars() {
                None => vec![],
                Some(pred) => match pred {
                    ty::PredicateKind::Trait(..)
                    | ty::PredicateKind::Subtype(..)
                    | ty::PredicateKind::Coerce(..)
                    | ty::PredicateKind::Projection(..)
                    | ty::PredicateKind::ClosureKind(..)
                    | ty::PredicateKind::ObjectSafe(..)
                    | ty::PredicateKind::ConstEvaluatable(..)
                    | ty::PredicateKind::ConstEquate(..)
                    | ty::PredicateKind::TypeWellFormedFromEnv(..) => vec![],
                    ty::PredicateKind::WellFormed(arg) => {
                        wf_args.push(arg);
                        vec![]
                    }

                    ty::PredicateKind::RegionOutlives(ty::OutlivesPredicate(r_a, r_b)) => {
                        vec![OutlivesBound::RegionSubRegion(r_b, r_a)]
                    }

                    ty::PredicateKind::TypeOutlives(ty::OutlivesPredicate(ty_a, r_b)) => {
                        let ty_a = infcx.resolve_vars_if_possible(ty_a);
                        let mut components = smallvec![];
                        push_outlives_components(tcx, ty_a, &mut components);
                        implied_bounds_from_components(r_b, components)
                    }
                },
            }
        }));
    }

    // Ensure that those obligations that we had to solve
    // get solved *here*.
    match fulfill_cx.select_all_or_error(infcx).as_slice() {
        [] => Ok(implied_bounds),
        _ => Err(NoSolution),
    }
}

/// When we have an implied bound that `T: 'a`, we can further break
/// this down to determine what relationships would have to hold for
/// `T: 'a` to hold. We get to assume that the caller has validated
/// those relationships.
fn implied_bounds_from_components<'tcx>(
    sub_region: ty::Region<'tcx>,
    sup_components: SmallVec<[Component<'tcx>; 4]>,
) -> Vec<OutlivesBound<'tcx>> {
    sup_components
        .into_iter()
        .filter_map(|component| {
            match component {
                Component::Region(r) => Some(OutlivesBound::RegionSubRegion(sub_region, r)),
                Component::Param(p) => Some(OutlivesBound::RegionSubParam(sub_region, p)),
                Component::Projection(p) => Some(OutlivesBound::RegionSubProjection(sub_region, p)),
                Component::EscapingProjection(_) =>
                // If the projection has escaping regions, don't
                // try to infer any implied bounds even for its
                // free components. This is conservative, because
                // the caller will still have to prove that those
                // free components outlive `sub_region`. But the
                // idea is that the WAY that the caller proves
                // that may change in the future and we want to
                // give ourselves room to get smarter here.
                {
                    None
                }
                Component::UnresolvedInferenceVariable(..) => None,
            }
        })
        .collect()
}