DXR is a code search and navigation tool aimed at making sense of large projects. It supports full-text and regex searches as well as structural queries.

Git (4fb54ed484)

VCS Links

Line Code
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
//! 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::{InferCtxt, TyCtxtInferExt};
use rustc_infer::traits::TraitEngineExt as _;
use rustc_middle::ty::outlives::Component;
use rustc_middle::ty::query::Providers;
use rustc_middle::ty::{self, Ty, TyCtxt, TypeFoldable};
use rustc_span::source_map::DUMMY_SP;
use rustc_trait_selection::infer::InferCtxtBuilderExt;
use rustc_trait_selection::traits::query::outlives_bounds::OutlivesBound;
use rustc_trait_selection::traits::query::{CanonicalTyGoal, Fallible, NoSolution};
use rustc_trait_selection::traits::wf;
use rustc_trait_selection::traits::FulfillmentContext;
use rustc_trait_selection::traits::TraitEngine;
use smallvec::{smallvec, SmallVec};

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. Currently (at least) these resulting
    // predicates are always guaranteed to be a subset of the original
    // type, so we need not fear non-termination.
    let mut wf_args = vec![ty.into()];

    let mut implied_bounds = vec![];

    let mut fulfill_cx = FulfillmentContext::new();

    while let Some(arg) = wf_args.pop() {
        // 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, arg, DUMMY_SP).unwrap_or(vec![]);

        // 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() {
                ty::PredicateKind::Trait(..)
                | ty::PredicateKind::Subtype(..)
                | ty::PredicateKind::Projection(..)
                | ty::PredicateKind::ClosureKind(..)
                | ty::PredicateKind::ObjectSafe(..)
                | ty::PredicateKind::ConstEvaluatable(..)
                | ty::PredicateKind::ConstEquate(..) => vec![],

                &ty::PredicateKind::WellFormed(arg) => {
                    wf_args.push(arg);
                    vec![]
                }

                ty::PredicateKind::RegionOutlives(ref data) => match data.no_bound_vars() {
                    None => vec![],
                    Some(ty::OutlivesPredicate(r_a, r_b)) => {
                        vec![OutlivesBound::RegionSubRegion(r_b, r_a)]
                    }
                },

                ty::PredicateKind::TypeOutlives(ref data) => match data.no_bound_vars() {
                    None => vec![],
                    Some(ty::OutlivesPredicate(ty_a, r_b)) => {
                        let ty_a = infcx.resolve_vars_if_possible(&ty_a);
                        let mut components = smallvec![];
                        tcx.push_outlives_components(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) {
        Ok(()) => Ok(implied_bounds),
        Err(_) => 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(
    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()
}