blob: 0d8620c3614a274ae4f637bbf451a37f8fd4ee7c [file]
//! Canonicalization is used to separate some goal from its context,
//! throwing away unnecessary information in the process.
//!
//! This is necessary to cache goals containing inference variables
//! and placeholders without restricting them to the current `InferCtxt`.
//!
//! Canonicalization is fairly involved, for more details see the relevant
//! section of the [rustc-dev-guide][c].
//!
//! [c]: https://rustc-dev-guide.rust-lang.org/solve/canonicalization.html
use std::iter;
use canonicalizer::Canonicalizer;
use rustc_index::IndexVec;
use rustc_type_ir::inherent::*;
use rustc_type_ir::relate::{
self, Relate, RelateResult, TypeRelation, VarianceDiagInfo, relate_args_invariantly,
};
use rustc_type_ir::{
self as ty, Canonical, CanonicalVarKind, CanonicalVarValues, InferCtxtLike, Interner, Region,
TypeFoldable, TypingMode, TypingModeEqWrapper, eager_resolve_vars,
};
use thin_vec::ThinVec;
use tracing::instrument;
use crate::delegate::SolverDelegate;
use crate::solve::{
CanonicalResponse, Certainty, ExternalConstraintsData, ExternalRegionConstraints, Goal,
NestedNormalizationGoals, QueryInput, Response, VisibleForLeakCheck, inspect,
};
pub mod canonicalizer;
trait ResponseT<I: Interner> {
fn var_values(&self) -> CanonicalVarValues<I>;
}
impl<I: Interner> ResponseT<I> for Response<I> {
fn var_values(&self) -> CanonicalVarValues<I> {
self.var_values
}
}
impl<I: Interner, T> ResponseT<I> for inspect::State<I, T> {
fn var_values(&self) -> CanonicalVarValues<I> {
self.var_values
}
}
/// Canonicalizes the goal remembering the original values
/// for each bound variable.
///
/// This expects `goal` and `opaque_types` to be eager resolved.
pub(super) fn canonicalize_goal<D, I>(
delegate: &D,
goal: Goal<I, I::Predicate>,
opaque_types: &[(ty::OpaqueTypeKey<I>, I::Ty)],
typing_mode: TypingMode<I>,
) -> (ThinVec<I::GenericArg>, I::CanonicalInput)
where
D: SolverDelegate<Interner = I>,
I: Interner,
{
let (orig_values, canonical) = Canonicalizer::canonicalize_input(
delegate,
QueryInput {
goal,
predefined_opaques_in_body: delegate.cx().mk_predefined_opaques_in_body(opaque_types),
},
);
let query_input = delegate.cx().mk_canonical_input(ty::CanonicalQueryInput {
canonical,
typing_mode: TypingModeEqWrapper(typing_mode),
});
(orig_values, query_input)
}
pub(super) fn canonicalize_response<D, I, T>(
delegate: &D,
max_input_universe: ty::UniverseIndex,
value: T,
) -> ty::Canonical<I, T>
where
D: SolverDelegate<Interner = I>,
I: Interner,
T: TypeFoldable<I>,
{
Canonicalizer::canonicalize_response(delegate, max_input_universe, value)
}
/// After calling a canonical query, we apply the constraints returned
/// by the query using this function.
///
/// This happens in three steps:
/// - we instantiate the bound variables of the query response
/// - we unify the `var_values` of the response with the `original_values`
/// - we apply the `external_constraints` returned by the query, returning
/// the `normalization_nested_goals`
pub(super) fn instantiate_and_apply_query_response<D, I>(
delegate: &D,
param_env: I::ParamEnv,
original_values: &[I::GenericArg],
response: CanonicalResponse<I>,
span: I::Span,
) -> (NestedNormalizationGoals<I>, Certainty)
where
D: SolverDelegate<Interner = I>,
I: Interner,
{
let instantiation =
compute_query_response_instantiation_values(delegate, &original_values, &response, span);
let Response { var_values, external_constraints, certainty } =
delegate.instantiate_canonical(response, instantiation);
unify_query_var_values(delegate, param_env, &original_values, var_values, span);
let ExternalConstraintsData { region_constraints, opaque_types, normalization_nested_goals } =
&*external_constraints;
match region_constraints {
ExternalRegionConstraints::Old(r) => register_region_constraints(
delegate,
r.iter().map(|(c, vis)| {
// FIXME: We should revisit and consider removing this after *assumptions on
// binders* is available, like once we had done in the stabilization of
// `-Znext-solver=coherence`(#121848).
// We ignore constraints from the nested goals in leak check. This is to match with
// the old solver's behavior, which has separated evaluation and fulfillment, and
// the former doesn't consider outlives obligations from the later.
(*c, vis.and(VisibleForLeakCheck::No))
}),
span,
),
ExternalRegionConstraints::NextGen(r) => {
delegate.register_solver_region_constraint(r.clone(), span)
}
};
register_new_opaque_types(delegate, opaque_types, span);
(normalization_nested_goals.clone(), certainty)
}
/// This returns the canonical variable values to instantiate the bound variables of
/// the canonical response. This depends on the `original_values` for the
/// bound variables.
fn compute_query_response_instantiation_values<D, I, T>(
delegate: &D,
original_values: &[I::GenericArg],
response: &Canonical<I, T>,
span: I::Span,
) -> CanonicalVarValues<I>
where
D: SolverDelegate<Interner = I>,
I: Interner,
T: ResponseT<I>,
{
// FIXME: Longterm canonical queries should deal with all placeholders
// created inside of the query directly instead of returning them to the
// caller.
let prev_universe = delegate.universe();
let universes_created_in_query = response.max_universe.index();
for _ in 0..universes_created_in_query {
let new_universe = delegate.create_next_universe();
if delegate.cx().assumptions_on_binders() {
// FIXME(-Zassumptions-on-binders): Remove this temporary workaround once
// opaque types no longer escape query responses with query-created placeholders.
// Region constraints involving query-created placeholders were handled inside
// the query. However, the placeholders can still escape in other response
// fields, such as opaque type constraints. To avoid triggering
// assertions, we explicitly insert empty assumptions for the
// recreated universes here.
delegate.insert_placeholder_assumptions(
new_universe,
Some(rustc_type_ir::region_constraint::Assumptions::empty()),
);
}
}
compute_query_response_instantiation_values_in_universe(
delegate,
original_values,
response,
span,
prev_universe,
)
}
fn compute_query_response_instantiation_values_in_universe<D, I, T>(
delegate: &D,
original_values: &[I::GenericArg],
response: &Canonical<I, T>,
span: I::Span,
prev_universe: ty::UniverseIndex,
) -> CanonicalVarValues<I>
where
D: SolverDelegate<Interner = I>,
I: Interner,
T: ResponseT<I>,
{
let var_values = response.value.var_values();
assert_eq!(original_values.len(), var_values.len());
// If the query did not make progress with constraining inference variables,
// we would normally create a new inference variables for bound existential variables
// only then unify this new inference variable with the inference variable from
// the input.
//
// We therefore instantiate the existential variable in the canonical response with the
// inference variable of the input right away, which is more performant.
let mut opt_values = IndexVec::from_elem_n(None, response.var_kinds.len());
for (original_value, result_value) in iter::zip(original_values, var_values.var_values.iter()) {
match result_value.kind() {
ty::GenericArgKind::Type(t) => {
// We disable the instantiation guess for inference variables
// and only use it for placeholders. We need to handle the
// `sub_root` of type inference variables which would make this
// more involved. They are also a lot rarer than region variables.
if let ty::Bound(index_kind, b) = t.kind()
&& !matches!(
response.var_kinds.get(b.var().as_usize()).unwrap(),
CanonicalVarKind::Ty { .. }
)
{
assert!(matches!(index_kind, ty::BoundVarIndexKind::Canonical));
opt_values[b.var()] = Some(*original_value);
}
}
ty::GenericArgKind::Lifetime(r) => {
if let ty::ReBound(index_kind, br) = r.kind() {
assert!(matches!(index_kind, ty::BoundVarIndexKind::Canonical));
opt_values[br.var()] = Some(*original_value);
}
}
ty::GenericArgKind::Const(c) => {
if let ty::ConstKind::Bound(index_kind, bc) = c.kind() {
assert!(matches!(index_kind, ty::BoundVarIndexKind::Canonical));
opt_values[bc.var()] = Some(*original_value);
}
}
}
}
CanonicalVarValues::instantiate(delegate.cx(), response.var_kinds, |var_values, kind| {
if kind.universe() != ty::UniverseIndex::ROOT {
// A variable from inside a binder of the query. While ideally these shouldn't
// exist at all (see the FIXME at the start of this method), we have to deal with
// them for now.
delegate.instantiate_canonical_var(kind, span, &var_values, |idx| {
prev_universe + idx.index()
})
} else if kind.is_existential() {
// As an optimization we sometimes avoid creating a new inference variable here.
//
// All new inference variables we create start out in the current universe of the caller.
// This is conceptually wrong as these inference variables would be able to name
// more placeholders then they should be able to. However the inference variables have
// to "come from somewhere", so by equating them with the original values of the caller
// later on, we pull them down into their correct universe again.
if let Some(v) = opt_values[ty::BoundVar::from_usize(var_values.len())] {
v
} else {
delegate.instantiate_canonical_var(kind, span, &var_values, |_| prev_universe)
}
} else {
// For placeholders which were already part of the input, we simply map this
// universal bound variable back the placeholder of the input.
//
// For `CanonicalVarKind::PlaceholderRegion`, this differs slightly: we
// canonicalize all free regions from the input into placeholders. This is
// unlike types or consts, where only input placeholders remain placeholders
// in the canonical form.
//
// We can still map these back to the original input regions, as we
// just instantiate the canonical variable with its corresponding
// `original_value`.
//
// For more information on why we canonicalize all input regions as
// placeholders, see the comment in `Canonicalizer::fold_region`.
original_values[kind.expect_placeholder_index()]
}
})
}
/// Enforce that `a` is equal to `b`.
///
/// In normal type relating, we don't structurally relate non-rigid aliases
/// as they can be normalized to any type. So we emit projection obligations to
/// defer the checks. E.g. in `infcx.eq` or `infcx.relate`.
/// But when unifying query response with original vars, we want to directly
/// set the original vars to values in response.
///
/// Therefore this type relation is created to **always** structurally relate
/// aliases, or more specifically, structurally eq everything.
struct ResponseRelating<'infcx, Infcx, I: Interner> {
infcx: &'infcx Infcx,
span: I::Span,
}
impl<'infcx, Infcx, I> ResponseRelating<'infcx, Infcx, I>
where
Infcx: InferCtxtLike<Interner = I>,
I: Interner,
{
fn new(infcx: &'infcx Infcx, span: I::Span) -> Self {
ResponseRelating { infcx, span }
}
}
impl<Infcx, I> TypeRelation<I> for ResponseRelating<'_, Infcx, I>
where
Infcx: InferCtxtLike<Interner = I>,
I: Interner,
{
fn cx(&self) -> I {
self.infcx.cx()
}
fn relate_ty_args(
&mut self,
a_ty: I::Ty,
_b_ty: I::Ty,
_def_id: I::DefId,
a_args: I::GenericArgs,
b_args: I::GenericArgs,
_: impl FnOnce(I::GenericArgs) -> I::Ty,
) -> RelateResult<I, I::Ty> {
relate_args_invariantly(self, a_args, b_args)?;
Ok(a_ty)
}
fn relate_with_variance<T: Relate<I>>(
&mut self,
_variance: ty::Variance,
_info: VarianceDiagInfo<I>,
a: T,
b: T,
) -> RelateResult<I, T> {
self.relate(a, b)
}
#[instrument(skip(self), level = "trace")]
fn tys(&mut self, a: I::Ty, b: I::Ty) -> RelateResult<I, I::Ty> {
if a == b {
return Ok(a);
}
let infcx = self.infcx;
let a = infcx.shallow_resolve(a);
let b = infcx.shallow_resolve(b);
match (a.kind(), b.kind()) {
(ty::Infer(ty::TyVar(a_id)), ty::Infer(ty::TyVar(b_id))) => {
infcx.equate_ty_vids_raw(a_id, b_id);
}
(ty::Infer(ty::TyVar(a_vid)), _) => {
infcx.instantiate_ty_var_raw(a_vid, b);
}
(_, ty::Infer(ty::TyVar(b_vid))) => {
infcx.instantiate_ty_var_raw(b_vid, a);
}
(ty::Error(e), _) | (_, ty::Error(e)) => {
infcx.set_tainted_by_errors(e);
return Ok(Ty::new_error(infcx.cx(), e));
}
// FIXME: Share the arms below with `super_combine_tys`.
// We can't use `super_combine_tys` here because we want to support
// values with escaping bound vars so that we can avoid
// instantiating binders when relating them.
//
// Relate integral variables to other types
(ty::Infer(ty::IntVar(a_id)), ty::Infer(ty::IntVar(b_id))) => {
infcx.equate_int_vids_raw(a_id, b_id);
}
(ty::Infer(ty::IntVar(v_id)), ty::Int(v)) => {
infcx.instantiate_int_var_raw(v_id, ty::IntVarValue::IntType(v));
}
(ty::Int(v), ty::Infer(ty::IntVar(v_id))) => {
infcx.instantiate_int_var_raw(v_id, ty::IntVarValue::IntType(v));
}
(ty::Infer(ty::IntVar(v_id)), ty::Uint(v)) => {
infcx.instantiate_int_var_raw(v_id, ty::IntVarValue::UintType(v));
}
(ty::Uint(v), ty::Infer(ty::IntVar(v_id))) => {
infcx.instantiate_int_var_raw(v_id, ty::IntVarValue::UintType(v));
}
// Relate floating-point variables to other types
(ty::Infer(ty::FloatVar(a_id)), ty::Infer(ty::FloatVar(b_id))) => {
infcx.equate_float_vids_raw(a_id, b_id);
}
(ty::Infer(ty::FloatVar(v_id)), ty::Float(v)) => {
infcx.instantiate_float_var_raw(v_id, ty::FloatVarValue::Known(v));
}
(ty::Float(v), ty::Infer(ty::FloatVar(v_id))) => {
infcx.instantiate_float_var_raw(v_id, ty::FloatVarValue::Known(v));
}
(_, ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)))
| (ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)), _) => {
panic!("We do not expect to encounter `Fresh` variables in the new solver")
}
_ => {
relate::structurally_relate_tys(self, a, b)?;
}
}
Ok(a)
}
#[instrument(skip(self), level = "trace")]
fn regions(&mut self, a: Region<I>, b: Region<I>) -> RelateResult<I, Region<I>> {
self.infcx.equate_regions(a, b, VisibleForLeakCheck::Yes, self.span);
Ok(a)
}
#[instrument(skip(self), level = "trace")]
fn consts(&mut self, a: I::Const, b: I::Const) -> RelateResult<I, I::Const> {
if a == b {
return Ok(a);
}
let infcx = self.infcx;
// Proof tree evaluation can unify inference variables in the original
// values without eagerly resolving them.
let a = infcx.shallow_resolve_const(a);
let b = infcx.shallow_resolve_const(b);
match (a.kind(), b.kind()) {
(
ty::ConstKind::Infer(ty::InferConst::Var(a_vid)),
ty::ConstKind::Infer(ty::InferConst::Var(b_vid)),
) => {
infcx.equate_const_vids_raw(a_vid, b_vid);
}
(ty::ConstKind::Infer(ty::InferConst::Var(a_vid)), _) => {
infcx.instantiate_const_var_raw(a_vid, b);
}
(_, ty::ConstKind::Infer(ty::InferConst::Var(b_vid))) => {
infcx.instantiate_const_var_raw(b_vid, a);
}
_ => {
relate::structurally_relate_consts(self, a, b)?;
}
}
Ok(a)
}
fn binders<T>(
&mut self,
a: ty::Binder<I, T>,
b: ty::Binder<I, T>,
) -> RelateResult<I, ty::Binder<I, T>>
where
T: Relate<I>,
{
if a == b {
return Ok(a);
}
debug_assert_eq!(a.bound_vars(), b.bound_vars());
self.relate(a.skip_binder(), b.skip_binder())?;
Ok(a)
}
}
/// Unify the `original_values` with the `var_values` returned by the canonical query..
///
/// This assumes that this unification will always succeed. This is the case when
/// applying a query response right away. However, calling a canonical query, doing any
/// other kind of trait solving, and only then instantiating the result of the query
/// can cause the instantiation to fail. This is not supported and we ICE in this case.
///
/// We always structurally instantiate aliases. Relating aliases needs to be different
/// depending on whether the alias is *rigid* or not. We're only really able to tell
/// whether an alias is rigid by using the trait solver. When instantiating a response
/// from the solver we assume that the solver correctly handled aliases and therefore
/// always relate them structurally here.
#[instrument(level = "trace", skip(delegate))]
fn unify_query_var_values<D, I>(
delegate: &D,
param_env: I::ParamEnv,
original_values: &[I::GenericArg],
var_values: CanonicalVarValues<I>,
span: I::Span,
) where
D: SolverDelegate<Interner = I>,
I: Interner,
{
assert_eq!(original_values.len(), var_values.len());
for (&orig, response) in iter::zip(original_values, var_values.var_values.iter()) {
let mut must_eq = ResponseRelating::new(&**delegate, span);
must_eq.relate(orig, response).unwrap();
}
}
fn register_region_constraints<D, I>(
delegate: &D,
constraints: impl IntoIterator<Item = (ty::RegionConstraint<I>, VisibleForLeakCheck)>,
span: I::Span,
) where
D: SolverDelegate<Interner = I>,
I: Interner,
{
for (constraint, vis) in constraints {
match constraint {
ty::RegionConstraint::Outlives(ty::OutlivesClause(lhs, rhs)) => match lhs.kind() {
ty::GenericArgKind::Lifetime(lhs) => delegate.sub_regions(rhs, lhs, vis, span),
ty::GenericArgKind::Type(lhs) => delegate.register_ty_outlives(lhs, rhs, span),
ty::GenericArgKind::Const(_) => panic!("const outlives: {lhs:?}: {rhs:?}"),
},
ty::RegionConstraint::Eq(ty::RegionEqPredicate(lhs, rhs)) => {
delegate.equate_regions(lhs, rhs, vis, span)
}
}
}
}
fn register_new_opaque_types<D, I>(
delegate: &D,
opaque_types: &[(ty::OpaqueTypeKey<I>, I::Ty)],
span: I::Span,
) where
D: SolverDelegate<Interner = I>,
I: Interner,
{
for &(key, ty) in opaque_types {
let prev = delegate.register_hidden_type_in_storage(key, ty, span);
// We eagerly resolve inference variables when computing the query response.
// This can cause previously distinct opaque type keys to now be structurally equal.
//
// To handle this, we store any duplicate entries in a separate list to check them
// at the end of typeck/borrowck. We could alternatively eagerly equate the hidden
// types here. However, doing so is difficult as it may result in nested goals and
// any errors may make it harder to track the control flow for diagnostics.
if let Some(prev) = prev {
delegate.add_duplicate_opaque_type(key, prev, span);
}
}
}
/// Used by proof trees to be able to recompute intermediate actions while
/// evaluating a goal. The `var_values` not only include the bound variables
/// of the query input, but also contain all unconstrained inference vars
/// created while evaluating this goal.
pub fn make_canonical_state<D, I, T>(
delegate: &D,
var_values: &[I::GenericArg],
max_input_universe: ty::UniverseIndex,
data: T,
) -> inspect::CanonicalState<I, T>
where
D: SolverDelegate<Interner = I>,
I: Interner,
T: TypeFoldable<I>,
{
let var_values = CanonicalVarValues { var_values: delegate.cx().mk_args(var_values) };
let state = inspect::State { var_values, data };
let state = eager_resolve_vars(&**delegate, state);
Canonicalizer::canonicalize_response(delegate, max_input_universe, state)
}
// FIXME: needs to be pub to be accessed by downstream
// `rustc_trait_selection::solve::inspect::analyse`.
pub fn instantiate_canonical_state<D, I, T>(
delegate: &D,
span: I::Span,
param_env: I::ParamEnv,
prev_universe: ty::UniverseIndex,
orig_values: &mut ThinVec<I::GenericArg>,
state: inspect::CanonicalState<I, T>,
) -> T
where
D: SolverDelegate<Interner = I>,
I: Interner,
T: TypeFoldable<I>,
{
// In case any fresh inference variables have been created between `state`
// and the previous instantiation, extend `orig_values` for it.
let max_universe = prev_universe + state.max_universe.index();
while delegate.universe() < max_universe {
delegate.create_next_universe();
}
orig_values.extend(
state.value.var_values.var_values.as_slice()[orig_values.len()..]
.iter()
.map(|&arg| delegate.fresh_var_for_kind(arg, span, max_universe)),
);
let instantiation = compute_query_response_instantiation_values_in_universe(
delegate,
orig_values,
&state,
span,
prev_universe,
);
let inspect::State { var_values, data } = delegate.instantiate_canonical(state, instantiation);
unify_query_var_values(delegate, param_env, orig_values, var_values, span);
data
}
pub fn response_no_constraints_raw<I: Interner>(
cx: I,
max_universe: ty::UniverseIndex,
var_kinds: I::CanonicalVarKinds,
certainty: Certainty,
) -> CanonicalResponse<I> {
ty::Canonical {
max_universe,
var_kinds,
value: Response {
var_values: ty::CanonicalVarValues::make_identity(cx, var_kinds),
// FIXME: maybe we should store the "no response" version in cx, like
// we do for cx.types and stuff.
external_constraints: cx.mk_external_constraints(ExternalConstraintsData::new(cx)),
certainty,
},
}
}