Merging upstream version 1.70.0+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

2 files changed, 135 insertions, 10 deletions

diff --git a/compiler/rustc_middle/src/traits/mod.rs b/compiler/rustc_middle/src/traits/mod.rs
index 6231dd9b6..91f07389f 100644
--- a/compiler/rustc_middle/src/traits/mod.rs
+++ b/compiler/rustc_middle/src/traits/mod.rs
@@ -305,8 +305,6 @@ pub enum ObligationCauseCode<'tcx> {
     SizedReturnType,
     /// Yield type must be `Sized`.
     SizedYieldType,
-    /// Box expression result type must be `Sized`.
-    SizedBoxType,
     /// Inline asm operand type must be `Sized`.
     InlineAsmSized,
     /// `[expr; N]` requires `type_of(expr): Copy`.
@@ -699,9 +697,9 @@ impl<'tcx, N> ImplSource<'tcx, N> {
     }
 
     pub fn borrow_nested_obligations(&self) -> &[N] {
-        match &self {
-            ImplSource::UserDefined(i) => &i.nested[..],
-            ImplSource::Param(n, _) => &n,
+        match self {
+            ImplSource::UserDefined(i) => &i.nested,
+            ImplSource::Param(n, _) => n,
             ImplSource::Builtin(i) => &i.nested,
             ImplSource::AutoImpl(d) => &d.nested,
             ImplSource::Closure(c) => &c.nested,
@@ -715,6 +713,23 @@ impl<'tcx, N> ImplSource<'tcx, N> {
         }
     }
 
+    pub fn borrow_nested_obligations_mut(&mut self) -> &mut [N] {
+        match self {
+            ImplSource::UserDefined(i) => &mut i.nested,
+            ImplSource::Param(n, _) => n,
+            ImplSource::Builtin(i) => &mut i.nested,
+            ImplSource::AutoImpl(d) => &mut d.nested,
+            ImplSource::Closure(c) => &mut c.nested,
+            ImplSource::Generator(c) => &mut c.nested,
+            ImplSource::Future(c) => &mut c.nested,
+            ImplSource::Object(d) => &mut d.nested,
+            ImplSource::FnPointer(d) => &mut d.nested,
+            ImplSource::TraitAlias(d) => &mut d.nested,
+            ImplSource::TraitUpcasting(d) => &mut d.nested,
+            ImplSource::ConstDestruct(i) => &mut i.nested,
+        }
+    }
+
     pub fn map<M, F>(self, f: F) -> ImplSource<'tcx, M>
     where
         F: FnMut(N) -> M,
@@ -899,6 +914,9 @@ pub enum ObjectSafetyViolation {
     /// (e.g., `trait Foo : Bar<Self>`).
     SupertraitSelf(SmallVec<[Span; 1]>),
 
+    // Supertrait has a non-lifetime `for<T>` binder.
+    SupertraitNonLifetimeBinder(SmallVec<[Span; 1]>),
+
     /// Method has something illegal.
     Method(Symbol, MethodViolationCode, Span),
 
@@ -921,6 +939,9 @@ impl ObjectSafetyViolation {
                         .into()
                 }
             }
+            ObjectSafetyViolation::SupertraitNonLifetimeBinder(_) => {
+                "where clause cannot reference non-lifetime `for<...>` variables".into()
+            }
             ObjectSafetyViolation::Method(name, MethodViolationCode::StaticMethod(_), _) => {
                 format!("associated function `{}` has no `self` parameter", name).into()
             }
@@ -971,7 +992,9 @@ impl ObjectSafetyViolation {
 
     pub fn solution(&self, err: &mut Diagnostic) {
         match self {
-            ObjectSafetyViolation::SizedSelf(_) | ObjectSafetyViolation::SupertraitSelf(_) => {}
+            ObjectSafetyViolation::SizedSelf(_)
+            | ObjectSafetyViolation::SupertraitSelf(_)
+            | ObjectSafetyViolation::SupertraitNonLifetimeBinder(..) => {}
             ObjectSafetyViolation::Method(
                 name,
                 MethodViolationCode::StaticMethod(Some((add_self_sugg, make_sized_sugg))),
@@ -1025,7 +1048,8 @@ impl ObjectSafetyViolation {
         // diagnostics use a `note` instead of a `span_label`.
         match self {
             ObjectSafetyViolation::SupertraitSelf(spans)
-            | ObjectSafetyViolation::SizedSelf(spans) => spans.clone(),
+            | ObjectSafetyViolation::SizedSelf(spans)
+            | ObjectSafetyViolation::SupertraitNonLifetimeBinder(spans) => spans.clone(),
             ObjectSafetyViolation::AssocConst(_, span)
             | ObjectSafetyViolation::GAT(_, span)
             | ObjectSafetyViolation::Method(_, _, span)
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<CanonicalGoal<'tcx>, 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<Q>(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<T: Foo + Bar> 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<CanonicalResponse<'tcx>, 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
     }
 }