rustc_next_trait_solver/solve/

mod.rs

//! The next-generation trait solver, currently still WIP.
//!
//! As a user of rust, you can use `-Znext-solver` to enable the new trait solver.
//!
//! As a developer of rustc, you shouldn't be using the new trait
//! solver without asking the trait-system-refactor-initiative, but it can
//! be enabled with `InferCtxtBuilder::with_next_trait_solver`. This will
//! ensure that trait solving using that inference context will be routed
//! to the new trait solver.
//!
//! For a high-level overview of how this solver works, check out the relevant
//! section of the rustc-dev-guide.

mod assembly;
mod effect_goals;
mod eval_ctxt;
pub mod inspect;
mod normalizes_to;
mod project_goals;
mod search_graph;
mod trait_goals;

use derive_where::derive_where;
use rustc_type_ir::inherent::*;
use rustc_type_ir::lang_items::SolverTraitLangItem;
pub use rustc_type_ir::solve::*;
use rustc_type_ir::transmute::Condition;
use rustc_type_ir::{self as ty, Const, Interner, Region, TraitClause, TypeVisitableExt, Upcast};
use thin_vec::{ThinVec, thin_vec};
use tracing::instrument;

pub use self::eval_ctxt::{
    EvalCtxt, GenerateProofTree, SolverDelegateEvalExt,
    evaluate_root_goal_for_proof_tree_raw_provider, fast_path,
};
use crate::delegate::SolverDelegate;
use crate::solve::assembly::Candidate;

/// How many fixpoint iterations we should attempt inside of the solver before bailing
/// with overflow.
///
/// We previously used  `cx.recursion_limit().0.checked_ilog2().unwrap_or(0)` for this.
/// However, it feels unlikely that uncreasing the recursion limit by a power of two
/// to get one more iteration is ever useful or desirable. We now instead used a constant
/// here. If there ever ends up some use-cases where a bigger number of fixpoint iterations
/// is required, we can add a new attribute for that or revert this to be dependent on the
/// recursion limit again. However, this feels very unlikely.
const FIXPOINT_STEP_LIMIT: usize = 8;

/// Whether evaluating this goal ended up changing the
/// inference state.
#[derive(PartialEq, Eq, Debug, Hash, Clone, Copy)]
pub enum HasChanged {
    Yes,
    No,
}

// FIXME(trait-system-refactor-initiative#117): we don't detect whether a response
// ended up pulling down any universes.
fn has_no_inference_or_external_constraints<I: Interner>(
    response: ty::Canonical<I, Response<I>>,
) -> bool {
    let ExternalConstraintsData {
        ref region_constraints,
        ref opaque_types,
        ref normalization_nested_goals,
    } = *response.value.external_constraints;
    response.value.is_identity()
        && region_constraints.is_empty()
        && opaque_types.is_empty()
        && normalization_nested_goals.is_empty()
}

fn has_only_region_constraints<I: Interner>(response: ty::Canonical<I, Response<I>>) -> bool {
    let ExternalConstraintsData {
        region_constraints: _,
        ref opaque_types,
        ref normalization_nested_goals,
    } = *response.value.external_constraints;
    response.value.is_identity_modulo_regions()
        && opaque_types.is_empty()
        && normalization_nested_goals.is_empty()
}

/// Whether two canonical responses are exactly equal except for their
/// region constraints.
fn equal_response_modulo_region_constraints<I: Interner>(
    a: &CanonicalResponse<I>,
    b: &CanonicalResponse<I>,
) -> bool {
    let CanonicalResponse {
        max_universe: a_max_universe,
        var_kinds: a_var_kinds,
        value:
            Response {
                var_values: a_var_values,
                certainty: a_certainty,
                external_constraints: a_external_constraints,
            },
    } = a;

    let ExternalConstraintsData { region_constraints: _, opaque_types, normalization_nested_goals } =
        &**a_external_constraints;

    a_max_universe == &b.max_universe
        && a_var_kinds == &b.var_kinds
        && a_var_values == &b.value.var_values
        && a_certainty == &b.value.certainty
        && opaque_types == &b.value.external_constraints.opaque_types
        && normalization_nested_goals == &b.value.external_constraints.normalization_nested_goals
}

impl<'a, D, I> EvalCtxt<'a, D>
where
    D: SolverDelegate<Interner = I>,
    I: Interner,
{
    #[instrument(level = "trace", skip(self))]
    fn compute_type_outlives_goal(
        &mut self,
        goal: Goal<I, ty::OutlivesClause<I, I::Ty>>,
    ) -> QueryResultOrRerunNonErased<I> {
        let ty::OutlivesClause(ty, lt) = goal.predicate;
        let ty = self.normalize(goal.param_env, ty::Unnormalized::new_wip(ty))?;

        // The normalized type can still contain non-rigid higher ranked aliases if their
        // normalization ends up with ambiguity. Or we have non-rigid aliases inside rigid ones.
        // Infer vars may be resolved to types/consts containing non-rigid aliases later.
        // Thus we should stall this goal to avoid registering non-rigid type outlives into
        // the outer infcx.
        if ty.has_non_region_infer() || ty.has_non_rigid_aliases() {
            self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
        } else {
            // We drop region constraints in ambiguous response so there's no need to add them in
            // the ambiguous branch. Also this guarantees we don't have ty vars when destructuring
            // type outlives.
            if self.cx().assumptions_on_binders() {
                use rustc_type_ir::region_constraint::RegionConstraint;

                let constraint = self.destructure_type_outlives(ty, lt);
                self.register_solver_region_constraint(RegionConstraint::new_from_or(constraint));
            } else {
                self.register_ty_outlives(ty, lt);
            }

            self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
        }
    }

    #[instrument(level = "trace", skip(self))]
    fn compute_region_outlives_goal(
        &mut self,
        goal: Goal<I, ty::OutlivesClause<I, Region<I>>>,
    ) -> QueryResultOrRerunNonErased<I> {
        let ty::OutlivesClause(a, b) = goal.predicate;

        if self.cx().assumptions_on_binders() {
            use rustc_type_ir::region_constraint::{LeafRegionConstraint, RegionConstraint};

            let constraint =
                RegionConstraint::new_leaf(LeafRegionConstraint::RegionOutlives(a, b, ()));
            self.register_solver_region_constraint(constraint);
        } else {
            self.register_region_outlives(a, b, VisibleForLeakCheck::Yes);
        }

        self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
    }

    #[instrument(level = "trace", skip(self))]
    fn compute_coerce_goal(
        &mut self,
        goal: Goal<I, ty::CoercePredicate<I>>,
    ) -> QueryResultOrRerunNonErased<I> {
        self.compute_subtype_goal(Goal {
            param_env: goal.param_env,
            predicate: ty::SubtypePredicate {
                a_is_expected: false,
                a: goal.predicate.a,
                b: goal.predicate.b,
            },
        })
    }

    #[instrument(level = "trace", skip(self))]
    fn compute_subtype_goal(
        &mut self,
        goal: Goal<I, ty::SubtypePredicate<I>>,
    ) -> QueryResultOrRerunNonErased<I> {
        match (goal.predicate.a.kind(), goal.predicate.b.kind()) {
            (ty::Infer(ty::TyVar(a_vid)), ty::Infer(ty::TyVar(b_vid))) => {
                self.sub_unify_ty_vids_raw(a_vid, b_vid);
                self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
            }
            _ => {
                self.sub(goal.param_env, goal.predicate.a, goal.predicate.b)?;
                self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
            }
        }
    }

    fn compute_dyn_compatible_goal(
        &mut self,
        trait_def_id: I::TraitId,
    ) -> QueryResultOrRerunNonErased<I> {
        if self.cx().trait_is_dyn_compatible(trait_def_id) {
            self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
        } else {
            Err(NoSolution.into())
        }
    }

    #[instrument(level = "trace", skip(self))]
    fn compute_well_formed_goal(
        &mut self,
        goal: Goal<I, I::Term>,
    ) -> QueryResultOrRerunNonErased<I> {
        match self.well_formed_goals(goal.param_env, goal.predicate) {
            Some(goals) => {
                self.add_goals(GoalSource::Misc, goals)?;
                self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
            }
            None => self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS),
        }
    }

    fn compute_unstable_feature_goal(
        &mut self,
        param_env: <I as Interner>::ParamEnv,
        symbol: <I as Interner>::Symbol,
    ) -> QueryResultOrRerunNonErased<I> {
        if self.may_use_unstable_feature(param_env, symbol)? {
            self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
        } else {
            self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
        }
    }

    #[instrument(level = "trace", skip(self))]
    fn compute_const_evaluatable_goal(
        &mut self,
        Goal { param_env, predicate: ct }: Goal<I, Const<I>>,
    ) -> QueryResultOrRerunNonErased<I> {
        match ct.kind() {
            ty::ConstKind::Alias(ty::IsRigid::Yes, _)
            | ty::ConstKind::Placeholder(_)
            | ty::ConstKind::Value(_)
            | ty::ConstKind::Error(_) => {
                self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
            }

            ty::ConstKind::Infer(_) => {
                self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
            }

            ty::ConstKind::Alias(ty::IsRigid::No, alias_const) => {
                // We never return `NoSolution` here as `evaluate_const` emits an
                // error itself when failing to evaluate, so emitting an additional fulfillment
                // error in that case is unnecessary noise. This may change in the future once
                // evaluation failures are allowed to impact selection, e.g. generic const
                // expressions in impl headers or `where`-clauses.

                // FIXME(generic_const_exprs): Implement handling for generic
                // const expressions here.
                if let Some(_normalized) = self.evaluate_const(param_env, alias_const)? {
                    self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
                } else {
                    self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
                }
            }

            // We can freely ICE here as:
            // - `Param` gets replaced with a placeholder during canonicalization
            // - `Bound` cannot exist as we don't have a binder around the self Type
            // - `Expr` is part of `feature(generic_const_exprs)` and is not implemented yet
            ty::ConstKind::Param(_) | ty::ConstKind::Bound(_, _) | ty::ConstKind::Expr(_) => {
                panic!("unexpected const kind: {:?}", ct)
            }
        }
    }

    #[instrument(level = "trace", skip(self), ret)]
    fn compute_const_arg_has_type_goal(
        &mut self,
        goal: Goal<I, (Const<I>, I::Ty)>,
    ) -> QueryResultOrRerunNonErased<I> {
        let (ct, ty) = goal.predicate;
        let ct = self.structurally_normalize_const(goal.param_env, ct)?;

        let ct_ty = match ct.kind() {
            ty::ConstKind::Infer(_) => {
                return self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS);
            }
            ty::ConstKind::Error(_) => {
                return self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes);
            }
            ty::ConstKind::Alias(ty::IsRigid::Yes, alias_const) => {
                alias_const.type_of(self.cx()).skip_norm_wip()
            }
            ty::ConstKind::Alias(ty::IsRigid::No, _) => unimplemented!(
                "non-rigid unevaluated constant for compute_const_arg_has_type_goal: {ct:?}"
            ),
            ty::ConstKind::Expr(_) => unimplemented!(
                "`feature(generic_const_exprs)` is not supported in the new trait solver"
            ),
            ty::ConstKind::Param(_) => {
                unreachable!("`ConstKind::Param` should have been canonicalized to `Placeholder`")
            }
            ty::ConstKind::Bound(_, _) => panic!("escaping bound vars in {:?}", ct),
            ty::ConstKind::Value(cv) => cv.ty(),
            ty::ConstKind::Placeholder(placeholder) => {
                placeholder.find_const_ty_from_env(goal.param_env)
            }
        };

        self.eq(goal.param_env, ct_ty, ty)?;
        self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
    }
}

#[derive(Debug)]
enum MergeCandidateInfo {
    AlwaysApplicable(usize),
    EqualResponse,
}

impl<D, I> EvalCtxt<'_, D>
where
    D: SolverDelegate<Interner = I>,
    I: Interner,
{
    /// Try to merge multiple possible ways to prove a goal, if that is not possible returns `None`.
    ///
    /// In this case we tend to flounder and return ambiguity by calling `[EvalCtxt::flounder]`.
    #[instrument(level = "trace", skip(self), ret)]
    fn try_merge_candidates(
        &mut self,
        candidates: &[Candidate<I>],
    ) -> Option<(CanonicalResponse<I>, MergeCandidateInfo)> {
        if candidates.is_empty() {
            return None;
        }

        let always_applicable = candidates.iter().enumerate().find(|(_, candidate)| {
            candidate.result.value.certainty == Certainty::Yes
                && has_no_inference_or_external_constraints(candidate.result)
        });

        if let Some((i, candidate)) = always_applicable {
            return Some((candidate.result, MergeCandidateInfo::AlwaysApplicable(i)));
        }

        let one: CanonicalResponse<I> = candidates[0].result;

        if candidates[1..]
            .iter()
            .all(|candidate| equal_response_modulo_region_constraints(&one, &candidate.result))
        {
            let region_constraints = &one.value.external_constraints.region_constraints;
            if candidates[1..].iter().all(|candidate| {
                &candidate.result.value.external_constraints.region_constraints
                    == region_constraints
            }) {
                return Some((one, MergeCandidateInfo::EqualResponse));
            }

            // If candidates differ only in region constraints, their merged region
            // constraints are an `Or` of their respective constraints. If one of them
            // has no region constraints, the `Or` constraint evaluates to `true`.
            //
            // This is a special case of `-Zassumptions-on-binders` and should be
            // replaced eventually.
            if let Some(candidate) = candidates.iter().find(|candidate| {
                candidate.result.value.external_constraints.region_constraints.is_empty()
            }) {
                return Some((candidate.result, MergeCandidateInfo::EqualResponse));
            }
        }

        None
    }

    fn bail_with_ambiguity(&mut self, candidates: &[Candidate<I>]) -> CanonicalResponse<I> {
        debug_assert!(candidates.len() > 1);
        let maybe = candidates.iter().fold(MaybeInfo::AMBIGUOUS, |maybe, candidate| {
            // We pull down the certainty of `Certainty::Yes` to ambiguity when combining
            // these responses, b/c we're combining more than one response and this we
            // don't know which one applies.
            match candidate.result.value.certainty {
                Certainty::Yes => maybe,
                Certainty::Maybe(cand_maybe) => maybe.or(cand_maybe),
            }
        });
        self.make_ambiguous_response_no_constraints(maybe)
    }

    /// If we fail to merge responses we flounder and return overflow or ambiguity.
    #[instrument(level = "trace", skip(self), ret)]
    fn flounder(&mut self, candidates: &[Candidate<I>]) -> QueryResult<I> {
        if candidates.is_empty() {
            return Err(NoSolution);
        } else {
            Ok(self.bail_with_ambiguity(candidates))
        }
    }

    /// Normalize a type for when it is structurally matched on.
    ///
    /// This function is necessary in nearly all cases before matching on a type.
    /// Not doing so is likely to be incomplete and therefore unsound during
    /// coherence.
    #[instrument(level = "trace", skip(self, param_env), ret)]
    fn structurally_normalize_ty(
        &mut self,
        param_env: I::ParamEnv,
        ty: I::Ty,
    ) -> Result<I::Ty, NoSolutionOrRerunNonErased> {
        self.structurally_normalize_term(param_env, ty.into()).map(|term| term.expect_ty())
    }

    /// Normalize a const for when it is structurally matched on, or more likely
    /// when it needs `.try_to_*` called on it (e.g. to turn it into a usize).
    ///
    /// This function is necessary in nearly all cases before matching on a const.
    /// Not doing so is likely to be incomplete and therefore unsound during
    /// coherence.
    #[instrument(level = "trace", skip(self, param_env), ret)]
    fn structurally_normalize_const(
        &mut self,
        param_env: I::ParamEnv,
        ct: Const<I>,
    ) -> Result<Const<I>, NoSolutionOrRerunNonErased> {
        self.structurally_normalize_term(param_env, ct.into()).map(|term| term.expect_const())
    }

    /// Normalize a term for when it is structurally matched on.
    ///
    /// This function is necessary in nearly all cases before matching on a ty/const.
    /// Not doing so is likely to be incomplete and therefore unsound during coherence.
    fn structurally_normalize_term(
        &mut self,
        param_env: I::ParamEnv,
        term: I::Term,
    ) -> Result<I::Term, NoSolutionOrRerunNonErased> {
        if !self.cx().renormalize_rigid_aliases() && !term.is_non_rigid_alias() {
            return Ok(term);
        }

        if let Some(alias) = term.to_alias_term() {
            let normalized_term = self.next_term_infer_of_alias_kind(alias);
            let projection_goal = Goal::new(
                self.cx(),
                param_env,
                ty::ProjectionClause { projection_term: alias, term: normalized_term },
            );
            // We normalize the self type to be able to relate it with
            // types from candidates.
            self.add_goal(GoalSource::Normalization, projection_goal)?;
            self.try_evaluate_added_goals()?;
            Ok(self.deeply_resolve_ignoring_regions(normalized_term))
        } else {
            Ok(term)
        }
    }
}

/// The result of evaluating a goal.
#[derive_where(Debug; I: Interner)]
pub struct GoalEvaluation<I: Interner> {
    /// The goal we've evaluated. This is the input goal, but potentially with its
    /// inference variables resolved. This never applies any inference constraints
    /// from evaluating the goal.
    ///
    /// We rely on this to check whether root goals in HIR typeck had an unresolved
    /// type inference variable in the input. We must not resolve this after evaluating
    /// the goal as even if the inference variable has been resolved by evaluating the
    /// goal itself, this goal may still end up failing due to region uniquification
    /// later on.
    ///
    /// This is used as a minor optimization to avoid re-resolving inference variables
    /// when reevaluating ambiguous goals. E.g. if we've got a goal `?x: Trait` with `?x`
    /// already being constrained to `Vec<?y>`, then the first evaluation resolves it to
    /// `Vec<?y>: Trait`. If this goal is still ambiguous and we later resolve `?y` to `u32`,
    /// then reevaluating this goal now only needs to resolve `?y` while it would otherwise
    /// have to resolve both `?x` and `?y`,
    pub goal: Goal<I, I::Predicate>,
    pub certainty: Certainty,
    pub has_changed: HasChanged,
    /// If the [`Certainty`] was `Maybe`, then keep track of whether the goal has changed
    /// before rerunning it.
    pub stalled_on: Option<GoalStalledOn<I>>,
}

/// Flatten the `Condition` tree into a conjunction of predicates.
#[instrument(level = "debug", skip(interner, predicate))]
pub fn flatten_answer_tree<I: Interner>(
    interner: I,
    predicate: TraitClause<I>,
    cond: Condition<Region<I>, I::Ty>,
) -> ThinVec<I::Predicate> {
    match cond {
        // FIXME(bryangarza): Add separate `IfAny` case, instead of treating as `IfAll`
        // Not possible until the trait solver supports disjunctions of obligations
        Condition::IfAll(conds) | Condition::IfAny(conds) => conds
            .into_iter()
            .flat_map(|cond| flatten_answer_tree(interner, predicate, cond))
            .collect(),
        Condition::Immutable { ty } => {
            let trait_ref = ty::TraitRef::new(
                interner,
                interner.require_trait_lang_item(SolverTraitLangItem::Freeze),
                [I::GenericArg::from(ty)],
            );
            thin_vec![trait_ref.upcast(interner)]
        }
        Condition::Outlives { long, short } => {
            let outlives = ty::OutlivesClause(long, short);
            thin_vec![outlives.upcast(interner)]
        }
        Condition::Transmutable { src, dst } => {
            let transmute_trait = predicate.def_id();
            let assume = predicate.trait_ref.args.const_at(2);
            let trait_ref = ty::TraitRef::new(
                interner,
                transmute_trait,
                [I::GenericArg::from(dst), I::GenericArg::from(src), I::GenericArg::from(assume)],
            );
            thin_vec![trait_ref.upcast(interner)]
        }
    }
}