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

rustc_next_trait_solver/solve/eval_ctxt/
solver_region_constraints.rs
