rustc_next_trait_solver/solve/eval_ctxt/
solver_region_constraints.rs

1//! Logic for `-Zassumptions-on-binders` stuff
2
3#[cfg(feature = "nightly")]
4use rustc_data_structures::transitive_relation::TransitiveRelationBuilder;
5use rustc_type_ir::ClauseKind::*;
6use rustc_type_ir::inherent::*;
7use rustc_type_ir::outlives::{Component, push_outlives_components};
8#[cfg(not(feature = "nightly"))]
9use rustc_type_ir::region_constraint::TransitiveRelationBuilder;
10use rustc_type_ir::region_constraint::{
11    Assumptions, RegionConstraint, eagerly_handle_placeholders_in_universe,
12    evaluate_solver_constraint,
13};
14use rustc_type_ir::{
15    AliasTy, Binder, ClauseKind, InferCtxtLike, Interner, OutlivesClause, Region, TypeVisitable,
16    TypeVisitableExt, TypeVisitor, UniverseIndex, max_universe,
17};
18use tracing::{debug, instrument};
19
20use crate::delegate::SolverDelegate;
21use crate::solve::{Certainty, EvalCtxt, Goal, NoSolution};
22
23/// Logic for `-Zassumptions-on-binders` stuff
24impl<'a, D, I> EvalCtxt<'a, D>
25where
26    D: SolverDelegate<Interner = I>,
27    I: Interner,
28{
29    /// Computes the assumptions associated with a binder for use in eagerly handling placeholders when
30    /// exiting the binder. Though, right now we do not actually handle placeholders when exiting binders,
31    /// instead we handle placeholders when computing the final response for the goal being computed.
32    x;#[instrument(level = "debug", skip(self), ret)]
33    pub(super) fn region_assumptions_for_placeholders_in_universe(
34        &mut self,
35        t: impl TypeVisitable<I>,
36        u: UniverseIndex,
37        param_env: I::ParamEnv,
38    ) -> Option<Assumptions<I>> {
39        assert!(self.cx().assumptions_on_binders());
40
41        struct RawAssumptions<'a, 'b, D: SolverDelegate<Interner = I>, I: Interner> {
42            ecx: &'a mut EvalCtxt<'b, D, I>,
43            param_env: I::ParamEnv,
44            out: Vec<Goal<I, I::Predicate>>,
45        }
46
47        impl<D, I> TypeVisitor<I> for RawAssumptions<'_, '_, D, I>
48        where
49            I: Interner,
50            D: SolverDelegate<Interner = I>,
51        {
52            type Result = ();
53
54            fn visit_ty(&mut self, t: I::Ty) {
55                self.out.extend(
56                    self.ecx
57                        .well_formed_goals(self.param_env, t.into())
58                        .unwrap_or(vec![Goal::new(
59                            self.ecx.cx(),
60                            self.param_env,
61                            ClauseKind::WellFormed(t.into()),
62                        )])
63                        .into_iter(),
64                );
65            }
66
67            fn visit_const(&mut self, c: I::Const) {
68                self.out.extend(
69                    self.ecx
70                        .well_formed_goals(self.param_env, c.into())
71                        .unwrap_or(vec![Goal::new(
72                            self.ecx.cx(),
73                            self.param_env,
74                            ClauseKind::WellFormed(c.into()),
75                        )])
76                        .into_iter(),
77                );
78            }
79        }
80
81        let mut reqs_builder = RawAssumptions { ecx: self, param_env, out: vec![] };
82        t.visit_with(&mut reqs_builder);
83        let reqs = reqs_builder.out;
84
85        let mut region_outlives_builder = TransitiveRelationBuilder::default();
86        let mut type_outlives = vec![];
87
88        // If there are inference variables in type outlives then we may not be able
89        // to elaborate to the full set of implied bounds right now. To avoid incorrectly
90        // NoSolution'ing when lifting constraints to a lower universe due to no usable
91        // assumptions, we just bail here.
92        //
93        // This is somewhat imprecise as if both the infer var and the outlived region are
94        // in a lower universe than the binder we're computing assumptions for then it doesn't
95        // really matter as we wouldn't use those outlives as assumptions anyway.
96        if reqs.iter().any(|goal| {
97            // We don't care about region infers as they can't be further destructured
98            goal.predicate.has_non_region_infer()
99        }) {
100            return None;
101        }
102
103        // FIXME(-Zassumptions-on-binders): we need to normalize here/somewhere
104        // as we assume the type outlives assumptions only have rigid types :>
105        let clauses = rustc_type_ir::elaborate::elaborate(
106            self.cx(),
107            reqs.into_iter().filter_map(|goal| goal.predicate.as_clause()),
108        );
109
110        clauses.filter(move |clause| max_universe(&**self.delegate, *clause) == u).for_each(
111            |clause| match clause.kind().skip_binder() {
112                RegionOutlives(OutlivesClause(r1, r2)) => {
113                    assert!(clause.kind().no_bound_vars().is_some());
114                    region_outlives_builder.add(r1, r2);
115                }
116                TypeOutlives(p) => {
117                    type_outlives.push(clause.kind().map_bound(|_| p));
118                }
119                _ => (),
120            },
121        );
122
123        Some(Assumptions::new(type_outlives, region_outlives_builder.freeze()))
124    }
125
126    x;#[instrument(level = "debug", skip(self), ret)]
127    pub(super) fn eagerly_handle_placeholders(&mut self) -> Result<Certainty, NoSolution> {
128        let constraint = self.delegate.get_solver_region_constraint();
129
130        let smallest_universe = self.max_input_universe.index();
131        let largest_universe = self.delegate.universe().index();
132        debug!(?smallest_universe, largest_universe);
133
134        let constraint = ((smallest_universe + 1)..=largest_universe)
135            .map(|u| UniverseIndex::from_usize(u))
136            .rev()
137            .fold(constraint, |constraint, u| {
138                eagerly_handle_placeholders_in_universe(&**self.delegate, constraint, u)
139            });
140        let constraint = evaluate_solver_constraint(&constraint.canonical_form());
141
142        self.delegate.overwrite_solver_region_constraint(constraint.clone(), self.origin_span);
143
144        if constraint.is_false() {
145            Err(NoSolution)
146        } else if constraint.is_ambig() {
147            Ok(Certainty::AMBIGUOUS)
148        } else {
149            Ok(Certainty::Yes)
150        }
151    }
152
153    /// Convert a type outlives constraint into a set of region outlives constraints and
154    /// type outlives constraints between the "components" of the type. E.g. `Foo<T, 'a>: 'b`
155    /// will be turned into `T: 'b, 'a: 'b`
156    x;#[instrument(level = "debug", skip(self), ret)]
157    pub(in crate::solve) fn destructure_type_outlives(
158        &mut self,
159        ty: I::Ty,
160        r: Region<I>,
161    ) -> RegionConstraint<I> {
162        let mut components = Default::default();
163        push_outlives_components(self.cx(), ty, &mut components);
164        self.destructure_components(&components, r)
165    }
166
167    fn destructure_components(
168        &mut self,
169        components: &[Component<I>],
170        r: Region<I>,
171    ) -> RegionConstraint<I> {
172        RegionConstraint::And(
173            components.into_iter().map(|c| self.destructure_component(c, r)).collect(),
174        )
175    }
176
177    fn destructure_component(&mut self, c: &Component<I>, r: Region<I>) -> RegionConstraint<I> {
178        use Component::*;
179        match c {
180            Region(c_r) => RegionConstraint::RegionOutlives(*c_r, r, ()),
181            Placeholder(p) => {
182                RegionConstraint::PlaceholderTyOutlives(Ty::new_placeholder(self.cx(), *p), r, ())
183            }
184            // The alias is either rigid or ambiguous in which case we'll return with ambiguity.
185            Alias(_, alias) => self.destructure_alias_outlives(*alias, r),
186            UnresolvedInferenceVariable(_) => RegionConstraint::Ambiguity(()),
187            Param(_) => {
    ::core::panicking::panic_fmt(format_args!("Params should have been canonicalized to placeholders"));
}panic!("Params should have been canonicalized to placeholders"),
188            EscapingAlias(components) => self.destructure_components(components, r),
189        }
190    }
191
192    /// Convert an alias outlives constraint into an OR constraint of any number of three
193    /// separate classes of candidates:
194    /// 1. component outlives. we turn `Alias<T, 'a>: 'b` into `T: 'b, 'a: 'b`.
195    /// 2. item bounds. we turn `Alias<T, 'a>: 'b` into `'c: 'b` if `Alias` is
196    ///     defined as `type Alias<T, 'a>: 'c`
197    /// 3. env assumptions. we defer handling `Alias<T, 'a>: 'b` via where clauses until
198    ///     when exiting the current binder. See [`RegionConstraint::AliasTyOutlivesViaEnv`].
199    x;#[instrument(level = "debug", skip(self), ret)]
200    fn destructure_alias_outlives(
201        &mut self,
202        alias: AliasTy<I>,
203        r: Region<I>,
204    ) -> RegionConstraint<I> {
205        let item_bounds =
206            rustc_type_ir::outlives::declared_bounds_from_definition(self.cx(), alias)
207                .map(|bound| RegionConstraint::RegionOutlives(bound, r, ()));
208        let item_bound_outlives = RegionConstraint::Or(item_bounds.collect());
209
210        let where_clause_outlives =
211            RegionConstraint::AliasTyOutlivesViaEnv(Binder::dummy((alias, r)), ());
212
213        let mut components = Default::default();
214        rustc_type_ir::outlives::compute_alias_components_recursive(
215            self.cx(),
216            alias,
217            &mut components,
218        );
219        let components_outlives = self.destructure_components(&components, r);
220
221        RegionConstraint::Or(Box::new([
222            item_bound_outlives,
223            where_clause_outlives,
224            components_outlives,
225        ]))
226    }
227}
rustc_next_trait_solver/solve/eval_ctxt/solver_region_constraints.rs

rustc_next_trait_solver/solve/eval_ctxt/
solver_region_constraints.rs
