diff options
Diffstat (limited to 'compiler/rustc_middle/src/traits/solve.rs')
| -rw-r--r-- | compiler/rustc_middle/src/traits/solve.rs | 218 |
1 files changed, 10 insertions, 208 deletions
diff --git a/compiler/rustc_middle/src/traits/solve.rs b/compiler/rustc_middle/src/traits/solve.rs index 3ad6b68d129..c8c16ec1e2c 100644 --- a/compiler/rustc_middle/src/traits/solve.rs +++ b/compiler/rustc_middle/src/traits/solve.rs @@ -1,122 +1,24 @@ use rustc_ast_ir::try_visit; use rustc_data_structures::intern::Interned; use rustc_macros::{HashStable, TypeFoldable, TypeVisitable}; -use rustc_span::def_id::DefId; +use rustc_next_trait_solver as ir; +pub use rustc_next_trait_solver::solve::*; -use crate::infer::canonical::{CanonicalVarValues, QueryRegionConstraints}; -use crate::traits::query::NoSolution; -use crate::traits::Canonical; +use crate::infer::canonical::QueryRegionConstraints; use crate::ty::{ - self, FallibleTypeFolder, ToPredicate, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeVisitable, - TypeVisitor, + self, FallibleTypeFolder, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeVisitable, TypeVisitor, }; -use super::BuiltinImplSource; - mod cache; -pub mod inspect; pub use cache::{CacheData, EvaluationCache}; -/// 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, HashStable, 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, HashStable, 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, HashStable, 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 do not 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(a), Certainty::Maybe(b)) => Certainty::Maybe(a.unify_with(b)), - } - } - - pub const fn overflow(suggest_increasing_limit: bool) -> Certainty { - Certainty::Maybe(MaybeCause::Overflow { suggest_increasing_limit }) - } -} - -/// Why we failed to evaluate a goal. -#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, HashStable, 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 { suggest_increasing_limit: bool }, -} - -impl MaybeCause { - fn unify_with(self, other: MaybeCause) -> MaybeCause { - match (self, other) { - (MaybeCause::Ambiguity, MaybeCause::Ambiguity) => MaybeCause::Ambiguity, - (MaybeCause::Ambiguity, MaybeCause::Overflow { .. }) => other, - (MaybeCause::Overflow { .. }, MaybeCause::Ambiguity) => self, - ( - MaybeCause::Overflow { suggest_increasing_limit: a }, - MaybeCause::Overflow { suggest_increasing_limit: b }, - ) => MaybeCause::Overflow { suggest_increasing_limit: a || b }, - } - } -} - -#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, HashStable, TypeFoldable, TypeVisitable)] -pub struct QueryInput<'tcx, T> { - pub goal: Goal<'tcx, T>, - pub predefined_opaques_in_body: PredefinedOpaques<'tcx>, -} +pub type Goal<'tcx, P> = ir::solve::Goal<TyCtxt<'tcx>, P>; +pub type QueryInput<'tcx, P> = ir::solve::QueryInput<TyCtxt<'tcx>, P>; +pub type QueryResult<'tcx> = ir::solve::QueryResult<TyCtxt<'tcx>>; +pub type CandidateSource<'tcx> = ir::solve::CandidateSource<TyCtxt<'tcx>>; +pub type CanonicalInput<'tcx, P = ty::Predicate<'tcx>> = ir::solve::CanonicalInput<TyCtxt<'tcx>, P>; +pub type CanonicalResponse<'tcx> = ir::solve::CanonicalResponse<TyCtxt<'tcx>>; /// Additional constraints returned on success. #[derive(Debug, PartialEq, Eq, Clone, Hash, HashStable, Default)] @@ -135,18 +37,6 @@ impl<'tcx> std::ops::Deref for PredefinedOpaques<'tcx> { } } -pub type CanonicalInput<'tcx, T = ty::Predicate<'tcx>> = Canonical<'tcx, QueryInput<'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, HashStable)] pub struct ExternalConstraints<'tcx>(pub(crate) Interned<'tcx, ExternalConstraintsData<'tcx>>); @@ -253,91 +143,3 @@ impl<'tcx> TypeVisitable<TyCtxt<'tcx>> for PredefinedOpaques<'tcx> { self.opaque_types.visit_with(visitor) } } - -/// Why a specific goal has to be proven. -/// -/// This is necessary as we treat nested goals different depending on -/// their source. -#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, HashStable, TypeVisitable, TypeFoldable)] -pub enum GoalSource { - Misc, - /// We're proving a where-bound of an impl. - /// - /// FIXME(-Znext-solver=coinductive): Explain how and why this - /// changes whether cycles are coinductive. - /// - /// This also impacts whether we erase constraints on overflow. - /// Erasing constraints is generally very useful for perf and also - /// results in better error messages by avoiding spurious errors. - /// We do not erase overflow constraints in `normalizes-to` goals unless - /// they are from an impl where-clause. This is necessary due to - /// backwards compatability, cc trait-system-refactor-initiatitive#70. - ImplWhereBound, - /// Instantiating a higher-ranked goal and re-proving it. - InstantiateHigherRanked, -} - -/// Possible ways the given goal can be proven. -#[derive(Debug, Clone, Copy, PartialEq, Eq)] -pub enum CandidateSource { - /// A user written impl. - /// - /// ## Examples - /// - /// ```rust - /// fn main() { - /// let x: Vec<u32> = Vec::new(); - /// // This uses the impl from the standard library to prove `Vec<T>: Clone`. - /// let y = x.clone(); - /// } - /// ``` - Impl(DefId), - /// A builtin impl generated by the compiler. When adding a new special - /// trait, try to use actual impls whenever possible. Builtin impls should - /// only be used in cases where the impl cannot be manually be written. - /// - /// Notable examples are auto traits, `Sized`, and `DiscriminantKind`. - /// For a list of all traits with builtin impls, check out the - /// `EvalCtxt::assemble_builtin_impl_candidates` method. - BuiltinImpl(BuiltinImplSource), - /// An assumption from the environment. - /// - /// More precisely we've used the `n-th` assumption in the `param_env`. - /// - /// ## Examples - /// - /// ```rust - /// fn is_clone<T: Clone>(x: T) -> (T, T) { - /// // This uses the assumption `T: Clone` from the `where`-bounds - /// // to prove `T: Clone`. - /// (x.clone(), x) - /// } - /// ``` - ParamEnv(usize), - /// If the self type is an alias type, e.g. an opaque type or a projection, - /// we know the bounds on that alias to hold even without knowing its concrete - /// underlying type. - /// - /// More precisely this candidate is using the `n-th` bound in the `item_bounds` of - /// the self type. - /// - /// ## Examples - /// - /// ```rust - /// trait Trait { - /// type Assoc: Clone; - /// } - /// - /// fn foo<T: Trait>(x: <T as Trait>::Assoc) { - /// // We prove `<T as Trait>::Assoc` by looking at the bounds on `Assoc` in - /// // in the trait definition. - /// let _y = x.clone(); - /// } - /// ``` - AliasBound, - /// A candidate that is registered only during coherence to represent some - /// yet-unknown impl that could be produced downstream without violating orphan - /// rules. - // FIXME: Merge this with the forced ambiguity candidates, so those don't use `Misc`. - CoherenceUnknowable, -} |