From 631cd5845e8de329d0e227aaa707d7ea228b8f8f Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:20:29 +0200 Subject: Merging upstream version 1.70.0+dfsg1. Signed-off-by: Daniel Baumann --- compiler/rustc_middle/src/traits/solve.rs | 107 +++++++++++++++++++++++++++++- 1 file changed, 104 insertions(+), 3 deletions(-) (limited to 'compiler/rustc_middle/src/traits/solve.rs') diff --git a/compiler/rustc_middle/src/traits/solve.rs b/compiler/rustc_middle/src/traits/solve.rs index bd43867a3..fef2be133 100644 --- a/compiler/rustc_middle/src/traits/solve.rs +++ b/compiler/rustc_middle/src/traits/solve.rs @@ -1,12 +1,113 @@ use std::ops::ControlFlow; use rustc_data_structures::intern::Interned; +use rustc_query_system::cache::Cache; -use crate::infer::canonical::QueryRegionConstraints; +use crate::infer::canonical::{CanonicalVarValues, QueryRegionConstraints}; +use crate::traits::query::NoSolution; +use crate::traits::Canonical; use crate::ty::{ - FallibleTypeFolder, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeVisitable, TypeVisitor, + self, FallibleTypeFolder, ToPredicate, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeVisitable, + TypeVisitor, }; +pub type EvaluationCache<'tcx> = Cache, QueryResult<'tcx>>; + +/// A goal is a statement, i.e. `predicate`, we want to prove +/// given some assumptions, i.e. `param_env`. +/// +/// Most of the time the `param_env` contains the `where`-bounds of the function +/// we're currently typechecking while the `predicate` is some trait bound. +#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)] +pub struct Goal<'tcx, P> { + pub predicate: P, + pub param_env: ty::ParamEnv<'tcx>, +} + +impl<'tcx, P> Goal<'tcx, P> { + pub fn new( + tcx: TyCtxt<'tcx>, + param_env: ty::ParamEnv<'tcx>, + predicate: impl ToPredicate<'tcx, P>, + ) -> Goal<'tcx, P> { + Goal { param_env, predicate: predicate.to_predicate(tcx) } + } + + /// Updates the goal to one with a different `predicate` but the same `param_env`. + pub fn with(self, tcx: TyCtxt<'tcx>, predicate: impl ToPredicate<'tcx, Q>) -> Goal<'tcx, Q> { + Goal { param_env: self.param_env, predicate: predicate.to_predicate(tcx) } + } +} + +#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)] +pub struct Response<'tcx> { + pub certainty: Certainty, + pub var_values: CanonicalVarValues<'tcx>, + /// Additional constraints returned by this query. + pub external_constraints: ExternalConstraints<'tcx>, +} + +#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)] +pub enum Certainty { + Yes, + Maybe(MaybeCause), +} + +impl Certainty { + pub const AMBIGUOUS: Certainty = Certainty::Maybe(MaybeCause::Ambiguity); + + /// Use this function to merge the certainty of multiple nested subgoals. + /// + /// Given an impl like `impl Baz for T {}`, we have 2 nested + /// subgoals whenever we use the impl as a candidate: `T: Foo` and `T: Bar`. + /// If evaluating `T: Foo` results in ambiguity and `T: Bar` results in + /// success, we merge these two responses. This results in ambiguity. + /// + /// If we unify ambiguity with overflow, we return overflow. This doesn't matter + /// inside of the solver as we distinguish ambiguity from overflow. It does + /// however matter for diagnostics. If `T: Foo` resulted in overflow and `T: Bar` + /// in ambiguity without changing the inference state, we still want to tell the + /// user that `T: Baz` results in overflow. + pub fn unify_with(self, other: Certainty) -> Certainty { + match (self, other) { + (Certainty::Yes, Certainty::Yes) => Certainty::Yes, + (Certainty::Yes, Certainty::Maybe(_)) => other, + (Certainty::Maybe(_), Certainty::Yes) => self, + (Certainty::Maybe(MaybeCause::Ambiguity), Certainty::Maybe(MaybeCause::Ambiguity)) => { + Certainty::Maybe(MaybeCause::Ambiguity) + } + (Certainty::Maybe(MaybeCause::Ambiguity), Certainty::Maybe(MaybeCause::Overflow)) + | (Certainty::Maybe(MaybeCause::Overflow), Certainty::Maybe(MaybeCause::Ambiguity)) + | (Certainty::Maybe(MaybeCause::Overflow), Certainty::Maybe(MaybeCause::Overflow)) => { + Certainty::Maybe(MaybeCause::Overflow) + } + } + } +} + +/// Why we failed to evaluate a goal. +#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)] +pub enum MaybeCause { + /// We failed due to ambiguity. This ambiguity can either + /// be a true ambiguity, i.e. there are multiple different answers, + /// or we hit a case where we just don't bother, e.g. `?x: Trait` goals. + Ambiguity, + /// We gave up due to an overflow, most often by hitting the recursion limit. + Overflow, +} + +pub type CanonicalGoal<'tcx, T = ty::Predicate<'tcx>> = Canonical<'tcx, Goal<'tcx, T>>; + +pub type CanonicalResponse<'tcx> = Canonical<'tcx, Response<'tcx>>; + +/// The result of evaluating a canonical query. +/// +/// FIXME: We use a different type than the existing canonical queries. This is because +/// we need to add a `Certainty` for `overflow` and may want to restructure this code without +/// having to worry about changes to currently used code. Once we've made progress on this +/// solver, merge the two responses again. +pub type QueryResult<'tcx> = Result, NoSolution>; + #[derive(Debug, PartialEq, Eq, Copy, Clone, Hash)] pub struct ExternalConstraints<'tcx>(pub(crate) Interned<'tcx, ExternalConstraintsData<'tcx>>); @@ -14,7 +115,7 @@ impl<'tcx> std::ops::Deref for ExternalConstraints<'tcx> { type Target = ExternalConstraintsData<'tcx>; fn deref(&self) -> &Self::Target { - &*self.0 + &self.0 } } -- cgit v1.2.3