From 1376c5a617be5c25655d0d7cb63e3beaa5a6e026 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:20:39 +0200 Subject: Merging upstream version 1.70.0+dfsg1. Signed-off-by: Daniel Baumann --- compiler/rustc_middle/src/traits/mod.rs | 38 +++++++++-- compiler/rustc_middle/src/traits/solve.rs | 107 +++++++++++++++++++++++++++++- 2 files changed, 135 insertions(+), 10 deletions(-) (limited to 'compiler/rustc_middle/src/traits') 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(self, f: F) -> ImplSource<'tcx, M> where F: FnMut(N) -> M, @@ -899,6 +914,9 @@ pub enum ObjectSafetyViolation { /// (e.g., `trait Foo : Bar`). SupertraitSelf(SmallVec<[Span; 1]>), + // Supertrait has a non-lifetime `for` 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, 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