use rustc_hir::def_id::DefId;
use rustc_infer::infer::canonical::{Canonical, CanonicalVarValues};
use rustc_infer::traits::query::NoSolution;
use rustc_middle::infer::canonical::CanonicalVarInfos;
use rustc_middle::traits::solve::{
CanonicalResponse, Certainty, ExternalConstraintsData, Goal, IsNormalizesToHack, QueryResult,
Response,
};
use rustc_middle::ty::{self, Ty, TyCtxt, UniverseIndex};
use rustc_middle::ty::{
CoercePredicate, RegionOutlivesPredicate, SubtypePredicate, TypeOutlivesPredicate,
};
mod alias_relate;
mod assembly;
mod canonicalize;
mod eval_ctxt;
mod fulfill;
mod inherent_projection;
pub mod inspect;
mod normalize;
mod opaques;
mod project_goals;
mod search_graph;
mod trait_goals;
mod weak_types;
pub use eval_ctxt::{
EvalCtxt, GenerateProofTree, InferCtxtEvalExt, InferCtxtSelectExt, UseGlobalCache,
};
pub use fulfill::FulfillmentCtxt;
pub(crate) use normalize::{deeply_normalize, deeply_normalize_with_skipped_universes};
#[derive(Debug, Clone, Copy)]
enum SolverMode {
Normal,
Coherence,
}
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
enum GoalEvaluationKind {
Root,
Nested { is_normalizes_to_hack: IsNormalizesToHack },
}
trait CanonicalResponseExt {
fn has_no_inference_or_external_constraints(&self) -> bool;
fn has_only_region_constraints(&self) -> bool;
}
impl<'tcx> CanonicalResponseExt for Canonical<'tcx, Response<'tcx>> {
fn has_no_inference_or_external_constraints(&self) -> bool {
self.value.external_constraints.region_constraints.is_empty()
&& self.value.var_values.is_identity()
&& self.value.external_constraints.opaque_types.is_empty()
}
fn has_only_region_constraints(&self) -> bool {
self.value.var_values.is_identity_modulo_regions()
&& self.value.external_constraints.opaque_types.is_empty()
}
}
impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
#[instrument(level = "debug", skip(self))]
fn compute_type_outlives_goal(
&mut self,
goal: Goal<'tcx, TypeOutlivesPredicate<'tcx>>,
) -> QueryResult<'tcx> {
let ty::OutlivesPredicate(ty, lt) = goal.predicate;
self.register_ty_outlives(ty, lt);
self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
}
#[instrument(level = "debug", skip(self))]
fn compute_region_outlives_goal(
&mut self,
goal: Goal<'tcx, RegionOutlivesPredicate<'tcx>>,
) -> QueryResult<'tcx> {
let ty::OutlivesPredicate(a, b) = goal.predicate;
self.register_region_outlives(a, b);
self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
}
#[instrument(level = "debug", skip(self))]
fn compute_coerce_goal(
&mut self,
goal: Goal<'tcx, CoercePredicate<'tcx>>,
) -> QueryResult<'tcx> {
self.compute_subtype_goal(Goal {
param_env: goal.param_env,
predicate: SubtypePredicate {
a_is_expected: false,
a: goal.predicate.a,
b: goal.predicate.b,
},
})
}
#[instrument(level = "debug", skip(self))]
fn compute_subtype_goal(
&mut self,
goal: Goal<'tcx, SubtypePredicate<'tcx>>,
) -> QueryResult<'tcx> {
if goal.predicate.a.is_ty_var() && goal.predicate.b.is_ty_var() {
self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
} else {
self.sub(goal.param_env, goal.predicate.a, goal.predicate.b)?;
self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
}
}
#[instrument(level = "debug", skip(self))]
fn compute_closure_kind_goal(
&mut self,
goal: Goal<'tcx, (DefId, ty::GenericArgsRef<'tcx>, ty::ClosureKind)>,
) -> QueryResult<'tcx> {
let (_, args, expected_kind) = goal.predicate;
let found_kind = args.as_closure().kind_ty().to_opt_closure_kind();
let Some(found_kind) = found_kind else {
return self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS);
};
if found_kind.extends(expected_kind) {
self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
} else {
Err(NoSolution)
}
}
#[instrument(level = "debug", skip(self))]
fn compute_object_safe_goal(&mut self, trait_def_id: DefId) -> QueryResult<'tcx> {
if self.tcx().check_is_object_safe(trait_def_id) {
self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
} else {
Err(NoSolution)
}
}
#[instrument(level = "debug", skip(self))]
fn compute_well_formed_goal(
&mut self,
goal: Goal<'tcx, ty::GenericArg<'tcx>>,
) -> QueryResult<'tcx> {
match self.well_formed_goals(goal.param_env, goal.predicate) {
Some(goals) => {
self.add_goals(goals);
self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
}
None => self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS),
}
}
#[instrument(level = "debug", skip(self))]
fn compute_const_evaluatable_goal(
&mut self,
Goal { param_env, predicate: ct }: Goal<'tcx, ty::Const<'tcx>>,
) -> QueryResult<'tcx> {
match ct.kind() {
ty::ConstKind::Unevaluated(uv) => {
if let Some(_normalized) = self.try_const_eval_resolve(param_env, uv, ct.ty()) {
self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
} else {
self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
}
}
ty::ConstKind::Infer(_) => {
self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
}
ty::ConstKind::Placeholder(_) | ty::ConstKind::Value(_) | ty::ConstKind::Error(_) => {
self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
}
ty::ConstKind::Param(_) | ty::ConstKind::Bound(_, _) | ty::ConstKind::Expr(_) => {
bug!("unexpect const kind: {:?}", ct)
}
}
}
#[instrument(level = "debug", skip(self), ret)]
fn compute_const_arg_has_type_goal(
&mut self,
goal: Goal<'tcx, (ty::Const<'tcx>, Ty<'tcx>)>,
) -> QueryResult<'tcx> {
let (ct, ty) = goal.predicate;
self.eq(goal.param_env, ct.ty(), ty)?;
self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
}
}
impl<'tcx> EvalCtxt<'_, 'tcx> {
#[instrument(level = "debug", skip(self))]
fn set_normalizes_to_hack_goal(&mut self, goal: Goal<'tcx, ty::ProjectionPredicate<'tcx>>) {
assert!(
self.nested_goals.normalizes_to_hack_goal.is_none(),
"attempted to set the projection eq hack goal when one already exists"
);
self.nested_goals.normalizes_to_hack_goal = Some(goal);
}
#[instrument(level = "debug", skip(self))]
fn add_goal(&mut self, goal: Goal<'tcx, ty::Predicate<'tcx>>) {
inspect::ProofTreeBuilder::add_goal(self, goal);
self.nested_goals.goals.push(goal);
}
#[instrument(level = "debug", skip(self, goals))]
fn add_goals(&mut self, goals: impl IntoIterator<Item = Goal<'tcx, ty::Predicate<'tcx>>>) {
for goal in goals {
self.add_goal(goal);
}
}
#[instrument(level = "debug", skip(self), ret)]
fn try_merge_responses(
&mut self,
responses: &[CanonicalResponse<'tcx>],
) -> Option<CanonicalResponse<'tcx>> {
if responses.is_empty() {
return None;
}
let one = responses[0];
if responses[1..].iter().all(|&resp| resp == one) {
return Some(one);
}
responses
.iter()
.find(|response| {
response.value.certainty == Certainty::Yes
&& response.has_no_inference_or_external_constraints()
})
.copied()
}
#[instrument(level = "debug", skip(self), ret)]
fn flounder(&mut self, responses: &[CanonicalResponse<'tcx>]) -> QueryResult<'tcx> {
if responses.is_empty() {
return Err(NoSolution);
}
let Certainty::Maybe(maybe_cause) =
responses.iter().fold(Certainty::AMBIGUOUS, |certainty, response| {
certainty.unify_with(response.value.certainty)
})
else {
bug!("expected flounder response to be ambiguous")
};
Ok(self.make_ambiguous_response_no_constraints(maybe_cause))
}
fn try_normalize_ty(
&mut self,
param_env: ty::ParamEnv<'tcx>,
mut ty: Ty<'tcx>,
) -> Result<Option<Ty<'tcx>>, NoSolution> {
for _ in 0..self.local_overflow_limit() {
let ty::Alias(_, projection_ty) = *ty.kind() else {
return Ok(Some(ty));
};
let normalized_ty = self.next_ty_infer();
let normalizes_to_goal = Goal::new(
self.tcx(),
param_env,
ty::ProjectionPredicate { projection_ty, term: normalized_ty.into() },
);
self.add_goal(normalizes_to_goal);
self.try_evaluate_added_goals()?;
ty = self.resolve_vars_if_possible(normalized_ty);
}
Ok(None)
}
}
fn response_no_constraints_raw<'tcx>(
tcx: TyCtxt<'tcx>,
max_universe: UniverseIndex,
variables: CanonicalVarInfos<'tcx>,
certainty: Certainty,
) -> CanonicalResponse<'tcx> {
Canonical {
max_universe,
variables,
value: Response {
var_values: CanonicalVarValues::make_identity(tcx, variables),
external_constraints: tcx.mk_external_constraints(ExternalConstraintsData::default()),
certainty,
},
}
}