summaryrefslogtreecommitdiffstats
path: root/compiler/rustc_trait_selection/src/solve/canonical
diff options
context:
space:
mode:
Diffstat (limited to 'compiler/rustc_trait_selection/src/solve/canonical')
-rw-r--r--compiler/rustc_trait_selection/src/solve/canonical/canonicalize.rs390
-rw-r--r--compiler/rustc_trait_selection/src/solve/canonical/mod.rs240
2 files changed, 630 insertions, 0 deletions
diff --git a/compiler/rustc_trait_selection/src/solve/canonical/canonicalize.rs b/compiler/rustc_trait_selection/src/solve/canonical/canonicalize.rs
new file mode 100644
index 000000000..c048d4a2a
--- /dev/null
+++ b/compiler/rustc_trait_selection/src/solve/canonical/canonicalize.rs
@@ -0,0 +1,390 @@
+use std::cmp::Ordering;
+
+use crate::infer::InferCtxt;
+use rustc_middle::infer::canonical::Canonical;
+use rustc_middle::infer::canonical::CanonicalTyVarKind;
+use rustc_middle::infer::canonical::CanonicalVarInfo;
+use rustc_middle::infer::canonical::CanonicalVarInfos;
+use rustc_middle::infer::canonical::CanonicalVarKind;
+use rustc_middle::ty::BoundRegionKind::BrAnon;
+use rustc_middle::ty::BoundTyKind;
+use rustc_middle::ty::TyCtxt;
+use rustc_middle::ty::TypeVisitableExt;
+use rustc_middle::ty::{self, Ty};
+use rustc_middle::ty::{TypeFoldable, TypeFolder, TypeSuperFoldable};
+
+/// Whether we're canonicalizing a query input or the query reponse.
+///
+/// When canonicalizing an input we're in the context of the caller
+/// while canonicalizing the response happens in the context of the
+/// query.
+#[derive(Debug, Clone, Copy)]
+pub enum CanonicalizeMode {
+ Input,
+ /// FIXME: We currently return region constraints refering to
+ /// placeholders and inference variables from a binder instantiated
+ /// inside of the query.
+ ///
+ /// In the long term we should eagerly deal with these constraints
+ /// inside of the query and only propagate constraints which are
+ /// actually nameable by the caller.
+ Response {
+ /// The highest universe nameable by the caller.
+ ///
+ /// All variables in a universe nameable by the caller get mapped
+ /// to the root universe in the response and then mapped back to
+ /// their correct universe when applying the query response in the
+ /// context of the caller.
+ ///
+ /// This doesn't work for universes created inside of the query so
+ /// we do remember their universe in the response.
+ max_input_universe: ty::UniverseIndex,
+ },
+}
+
+pub struct Canonicalizer<'a, 'tcx> {
+ infcx: &'a InferCtxt<'tcx>,
+ canonicalize_mode: CanonicalizeMode,
+
+ variables: &'a mut Vec<ty::GenericArg<'tcx>>,
+ primitive_var_infos: Vec<CanonicalVarInfo<'tcx>>,
+ binder_index: ty::DebruijnIndex,
+}
+
+impl<'a, 'tcx> Canonicalizer<'a, 'tcx> {
+ #[instrument(level = "debug", skip(infcx), ret)]
+ pub fn canonicalize<T: TypeFoldable<TyCtxt<'tcx>>>(
+ infcx: &'a InferCtxt<'tcx>,
+ canonicalize_mode: CanonicalizeMode,
+ variables: &'a mut Vec<ty::GenericArg<'tcx>>,
+ value: T,
+ ) -> Canonical<'tcx, T> {
+ let mut canonicalizer = Canonicalizer {
+ infcx,
+ canonicalize_mode,
+
+ variables,
+ primitive_var_infos: Vec::new(),
+ binder_index: ty::INNERMOST,
+ };
+
+ let value = value.fold_with(&mut canonicalizer);
+ assert!(!value.needs_infer());
+ assert!(!value.has_placeholders());
+
+ let (max_universe, variables) = canonicalizer.finalize();
+
+ Canonical { max_universe, variables, value }
+ }
+
+ fn finalize(self) -> (ty::UniverseIndex, CanonicalVarInfos<'tcx>) {
+ let mut var_infos = self.primitive_var_infos;
+ // See the rustc-dev-guide section about how we deal with universes
+ // during canonicalization in the new solver.
+ match self.canonicalize_mode {
+ // We try to deduplicate as many query calls as possible and hide
+ // all information which should not matter for the solver.
+ //
+ // For this we compress universes as much as possible.
+ CanonicalizeMode::Input => {}
+ // When canonicalizing a response we map a universes already entered
+ // by the caller to the root universe and only return useful universe
+ // information for placeholders and inference variables created inside
+ // of the query.
+ CanonicalizeMode::Response { max_input_universe } => {
+ for var in var_infos.iter_mut() {
+ let uv = var.universe();
+ let new_uv = ty::UniverseIndex::from(
+ uv.index().saturating_sub(max_input_universe.index()),
+ );
+ *var = var.with_updated_universe(new_uv);
+ }
+ let max_universe = var_infos
+ .iter()
+ .map(|info| info.universe())
+ .max()
+ .unwrap_or(ty::UniverseIndex::ROOT);
+
+ let var_infos = self.infcx.tcx.mk_canonical_var_infos(&var_infos);
+ return (max_universe, var_infos);
+ }
+ }
+
+ // Given a `var_infos` with existentials `En` and universals `Un` in
+ // universes `n`, this algorithm compresses them in place so that:
+ //
+ // - the new universe indices are as small as possible
+ // - we only create a new universe if we would otherwise put a placeholder in
+ // the same compressed universe as an existential which cannot name it
+ //
+ // Let's walk through an example:
+ // - var_infos: [E0, U1, E5, U2, E2, E6, U6], curr_compressed_uv: 0, next_orig_uv: 0
+ // - var_infos: [E0, U1, E5, U2, E2, E6, U6], curr_compressed_uv: 0, next_orig_uv: 1
+ // - var_infos: [E0, U1, E5, U2, E2, E6, U6], curr_compressed_uv: 1, next_orig_uv: 2
+ // - var_infos: [E0, U1, E5, U1, E1, E6, U6], curr_compressed_uv: 1, next_orig_uv: 5
+ // - var_infos: [E0, U1, E1, U1, E1, E6, U6], curr_compressed_uv: 1, next_orig_uv: 6
+ // - var_infos: [E0, U1, E1, U1, E1, E2, U2], curr_compressed_uv: 2, next_orig_uv: -
+ //
+ // This algorithm runs in `O(n²)` where `n` is the number of different universe
+ // indices in the input. This should be fine as `n` is expected to be small.
+ let mut curr_compressed_uv = ty::UniverseIndex::ROOT;
+ let mut existential_in_new_uv = false;
+ let mut next_orig_uv = Some(ty::UniverseIndex::ROOT);
+ while let Some(orig_uv) = next_orig_uv.take() {
+ let mut update_uv = |var: &mut CanonicalVarInfo<'tcx>, orig_uv, is_existential| {
+ let uv = var.universe();
+ match uv.cmp(&orig_uv) {
+ Ordering::Less => (), // Already updated
+ Ordering::Equal => {
+ if is_existential {
+ existential_in_new_uv = true;
+ } else if existential_in_new_uv {
+ // `var` is a placeholder from a universe which is not nameable
+ // by an existential which we already put into the compressed
+ // universe `curr_compressed_uv`. We therefore have to create a
+ // new universe for `var`.
+ curr_compressed_uv = curr_compressed_uv.next_universe();
+ existential_in_new_uv = false;
+ }
+
+ *var = var.with_updated_universe(curr_compressed_uv);
+ }
+ Ordering::Greater => {
+ // We can ignore this variable in this iteration. We only look at
+ // universes which actually occur in the input for performance.
+ //
+ // For this we set `next_orig_uv` to the next smallest, not yet compressed,
+ // universe of the input.
+ if next_orig_uv.map_or(true, |curr_next_uv| uv.cannot_name(curr_next_uv)) {
+ next_orig_uv = Some(uv);
+ }
+ }
+ }
+ };
+
+ // For each universe which occurs in the input, we first iterate over all
+ // placeholders and then over all inference variables.
+ //
+ // Whenever we compress the universe of a placeholder, no existential with
+ // an already compressed universe can name that placeholder.
+ for is_existential in [false, true] {
+ for var in var_infos.iter_mut() {
+ // We simply put all regions from the input into the highest
+ // compressed universe, so we only deal with them at the end.
+ if !var.is_region() {
+ if is_existential == var.is_existential() {
+ update_uv(var, orig_uv, is_existential)
+ }
+ }
+ }
+ }
+ }
+
+ for var in var_infos.iter_mut() {
+ if var.is_region() {
+ assert!(var.is_existential());
+ *var = var.with_updated_universe(curr_compressed_uv);
+ }
+ }
+
+ let var_infos = self.infcx.tcx.mk_canonical_var_infos(&var_infos);
+ (curr_compressed_uv, var_infos)
+ }
+}
+
+impl<'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'_, 'tcx> {
+ fn interner(&self) -> TyCtxt<'tcx> {
+ self.infcx.tcx
+ }
+
+ fn fold_binder<T>(&mut self, t: ty::Binder<'tcx, T>) -> ty::Binder<'tcx, T>
+ where
+ T: TypeFoldable<TyCtxt<'tcx>>,
+ {
+ self.binder_index.shift_in(1);
+ let t = t.super_fold_with(self);
+ self.binder_index.shift_out(1);
+ t
+ }
+
+ fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
+ let r = self.infcx.shallow_resolve(r);
+ let kind = match *r {
+ ty::ReLateBound(..) => return r,
+
+ ty::ReStatic => match self.canonicalize_mode {
+ CanonicalizeMode::Input => CanonicalVarKind::Region(ty::UniverseIndex::ROOT),
+ CanonicalizeMode::Response { .. } => return r,
+ },
+
+ ty::ReErased | ty::ReFree(_) | ty::ReEarlyBound(_) => match self.canonicalize_mode {
+ CanonicalizeMode::Input => CanonicalVarKind::Region(ty::UniverseIndex::ROOT),
+ CanonicalizeMode::Response { .. } => bug!("unexpected region in response: {r:?}"),
+ },
+
+ ty::RePlaceholder(placeholder) => match self.canonicalize_mode {
+ // We canonicalize placeholder regions as existentials in query inputs.
+ CanonicalizeMode::Input => CanonicalVarKind::Region(ty::UniverseIndex::ROOT),
+ CanonicalizeMode::Response { max_input_universe } => {
+ // If we have a placeholder region inside of a query, it must be from
+ // a new universe.
+ if max_input_universe.can_name(placeholder.universe) {
+ bug!("new placeholder in universe {max_input_universe:?}: {r:?}");
+ }
+ CanonicalVarKind::PlaceholderRegion(placeholder)
+ }
+ },
+
+ ty::ReVar(_) => match self.canonicalize_mode {
+ CanonicalizeMode::Input => CanonicalVarKind::Region(ty::UniverseIndex::ROOT),
+ CanonicalizeMode::Response { .. } => {
+ CanonicalVarKind::Region(self.infcx.universe_of_region(r))
+ }
+ },
+
+ ty::ReError(_) => return r,
+ };
+
+ let existing_bound_var = match self.canonicalize_mode {
+ CanonicalizeMode::Input => None,
+ CanonicalizeMode::Response { .. } => {
+ self.variables.iter().position(|&v| v == r.into()).map(ty::BoundVar::from)
+ }
+ };
+ let var = existing_bound_var.unwrap_or_else(|| {
+ let var = ty::BoundVar::from(self.variables.len());
+ self.variables.push(r.into());
+ self.primitive_var_infos.push(CanonicalVarInfo { kind });
+ var
+ });
+ let br = ty::BoundRegion { var, kind: BrAnon(var.as_u32(), None) };
+ self.interner().mk_re_late_bound(self.binder_index, br)
+ }
+
+ fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
+ let kind = match *t.kind() {
+ ty::Infer(ty::TyVar(vid)) => match self.infcx.probe_ty_var(vid) {
+ Ok(t) => return self.fold_ty(t),
+ Err(ui) => CanonicalVarKind::Ty(CanonicalTyVarKind::General(ui)),
+ },
+ ty::Infer(ty::IntVar(_)) => {
+ let nt = self.infcx.shallow_resolve(t);
+ if nt != t {
+ return self.fold_ty(nt);
+ } else {
+ CanonicalVarKind::Ty(CanonicalTyVarKind::Int)
+ }
+ }
+ ty::Infer(ty::FloatVar(_)) => {
+ let nt = self.infcx.shallow_resolve(t);
+ if nt != t {
+ return self.fold_ty(nt);
+ } else {
+ CanonicalVarKind::Ty(CanonicalTyVarKind::Int)
+ }
+ }
+ ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => {
+ bug!("fresh var during canonicalization: {t:?}")
+ }
+ ty::Placeholder(placeholder) => match self.canonicalize_mode {
+ CanonicalizeMode::Input => CanonicalVarKind::PlaceholderTy(ty::Placeholder {
+ universe: placeholder.universe,
+ name: BoundTyKind::Anon(self.variables.len() as u32),
+ }),
+ CanonicalizeMode::Response { .. } => CanonicalVarKind::PlaceholderTy(placeholder),
+ },
+ ty::Param(_) => match self.canonicalize_mode {
+ CanonicalizeMode::Input => CanonicalVarKind::PlaceholderTy(ty::Placeholder {
+ universe: ty::UniverseIndex::ROOT,
+ name: ty::BoundTyKind::Anon(self.variables.len() as u32),
+ }),
+ CanonicalizeMode::Response { .. } => bug!("param ty in response: {t:?}"),
+ },
+ ty::Bool
+ | ty::Char
+ | ty::Int(_)
+ | ty::Uint(_)
+ | ty::Float(_)
+ | ty::Adt(_, _)
+ | ty::Foreign(_)
+ | ty::Str
+ | ty::Array(_, _)
+ | ty::Slice(_)
+ | ty::RawPtr(_)
+ | ty::Ref(_, _, _)
+ | ty::FnDef(_, _)
+ | ty::FnPtr(_)
+ | ty::Dynamic(_, _, _)
+ | ty::Closure(_, _)
+ | ty::Generator(_, _, _)
+ | ty::GeneratorWitness(_)
+ | ty::GeneratorWitnessMIR(..)
+ | ty::Never
+ | ty::Tuple(_)
+ | ty::Alias(_, _)
+ | ty::Bound(_, _)
+ | ty::Error(_) => return t.super_fold_with(self),
+ };
+
+ let var = ty::BoundVar::from(
+ self.variables.iter().position(|&v| v == t.into()).unwrap_or_else(|| {
+ let var = self.variables.len();
+ self.variables.push(t.into());
+ self.primitive_var_infos.push(CanonicalVarInfo { kind });
+ var
+ }),
+ );
+ let bt = ty::BoundTy { var, kind: BoundTyKind::Anon(var.index() as u32) };
+ self.interner().mk_bound(self.binder_index, bt)
+ }
+
+ fn fold_const(&mut self, c: ty::Const<'tcx>) -> ty::Const<'tcx> {
+ let kind = match c.kind() {
+ ty::ConstKind::Infer(ty::InferConst::Var(vid)) => match self.infcx.probe_const_var(vid)
+ {
+ Ok(c) => return self.fold_const(c),
+ Err(universe) => CanonicalVarKind::Const(universe, c.ty()),
+ },
+ ty::ConstKind::Infer(ty::InferConst::Fresh(_)) => {
+ bug!("fresh var during canonicalization: {c:?}")
+ }
+ ty::ConstKind::Placeholder(placeholder) => match self.canonicalize_mode {
+ CanonicalizeMode::Input => CanonicalVarKind::PlaceholderConst(
+ ty::Placeholder {
+ universe: placeholder.universe,
+ name: ty::BoundVar::from(self.variables.len()),
+ },
+ c.ty(),
+ ),
+ CanonicalizeMode::Response { .. } => {
+ CanonicalVarKind::PlaceholderConst(placeholder, c.ty())
+ }
+ },
+ ty::ConstKind::Param(_) => match self.canonicalize_mode {
+ CanonicalizeMode::Input => CanonicalVarKind::PlaceholderConst(
+ ty::Placeholder {
+ universe: ty::UniverseIndex::ROOT,
+ name: ty::BoundVar::from(self.variables.len()),
+ },
+ c.ty(),
+ ),
+ CanonicalizeMode::Response { .. } => bug!("param ty in response: {c:?}"),
+ },
+ ty::ConstKind::Bound(_, _)
+ | ty::ConstKind::Unevaluated(_)
+ | ty::ConstKind::Value(_)
+ | ty::ConstKind::Error(_)
+ | ty::ConstKind::Expr(_) => return c.super_fold_with(self),
+ };
+
+ let var = ty::BoundVar::from(
+ self.variables.iter().position(|&v| v == c.into()).unwrap_or_else(|| {
+ let var = self.variables.len();
+ self.variables.push(c.into());
+ self.primitive_var_infos.push(CanonicalVarInfo { kind });
+ var
+ }),
+ );
+ self.interner().mk_const(ty::ConstKind::Bound(self.binder_index, var), c.ty())
+ }
+}
diff --git a/compiler/rustc_trait_selection/src/solve/canonical/mod.rs b/compiler/rustc_trait_selection/src/solve/canonical/mod.rs
new file mode 100644
index 000000000..8c3be8da1
--- /dev/null
+++ b/compiler/rustc_trait_selection/src/solve/canonical/mod.rs
@@ -0,0 +1,240 @@
+/// 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 self::canonicalize::{CanonicalizeMode, Canonicalizer};
+use super::{CanonicalGoal, Certainty, EvalCtxt, Goal};
+use super::{CanonicalResponse, ExternalConstraints, QueryResult, Response};
+use rustc_infer::infer::canonical::query_response::make_query_region_constraints;
+use rustc_infer::infer::canonical::CanonicalVarValues;
+use rustc_infer::infer::canonical::{CanonicalExt, QueryRegionConstraints};
+use rustc_infer::traits::query::NoSolution;
+use rustc_infer::traits::solve::ExternalConstraintsData;
+use rustc_infer::traits::ObligationCause;
+use rustc_middle::ty::{self, GenericArgKind};
+use rustc_span::DUMMY_SP;
+use std::iter;
+use std::ops::Deref;
+
+mod canonicalize;
+
+impl<'tcx> EvalCtxt<'_, 'tcx> {
+ /// Canonicalizes the goal remembering the original values
+ /// for each bound variable.
+ pub(super) fn canonicalize_goal(
+ &self,
+ goal: Goal<'tcx, ty::Predicate<'tcx>>,
+ ) -> (Vec<ty::GenericArg<'tcx>>, CanonicalGoal<'tcx>) {
+ let mut orig_values = Default::default();
+ let canonical_goal = Canonicalizer::canonicalize(
+ self.infcx,
+ CanonicalizeMode::Input,
+ &mut orig_values,
+ goal,
+ );
+ (orig_values, canonical_goal)
+ }
+
+ /// To return the constraints of a canonical query to the caller, we canonicalize:
+ ///
+ /// - `var_values`: a map from bound variables in the canonical goal to
+ /// the values inferred while solving the instantiated goal.
+ /// - `external_constraints`: additional constraints which aren't expressable
+ /// using simple unification of inference variables.
+ #[instrument(level = "debug", skip(self))]
+ pub(super) fn make_canonical_response(&self, certainty: Certainty) -> QueryResult<'tcx> {
+ let external_constraints = self.compute_external_query_constraints()?;
+
+ let response = Response { var_values: self.var_values, external_constraints, certainty };
+ let canonical = Canonicalizer::canonicalize(
+ self.infcx,
+ CanonicalizeMode::Response { max_input_universe: self.max_input_universe },
+ &mut Default::default(),
+ response,
+ );
+ Ok(canonical)
+ }
+
+ #[instrument(level = "debug", skip(self), ret)]
+ fn compute_external_query_constraints(&self) -> Result<ExternalConstraints<'tcx>, NoSolution> {
+ // Cannot use `take_registered_region_obligations` as we may compute the response
+ // inside of a `probe` whenever we have multiple choices inside of the solver.
+ let region_obligations = self.infcx.inner.borrow().region_obligations().to_owned();
+ let region_constraints = self.infcx.with_region_constraints(|region_constraints| {
+ make_query_region_constraints(
+ self.tcx(),
+ region_obligations
+ .iter()
+ .map(|r_o| (r_o.sup_type, r_o.sub_region, r_o.origin.to_constraint_category())),
+ region_constraints,
+ )
+ });
+ let opaque_types = self.infcx.clone_opaque_types_for_query_response();
+ Ok(self
+ .tcx()
+ .mk_external_constraints(ExternalConstraintsData { region_constraints, opaque_types }))
+ }
+
+ /// 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
+ pub(super) fn instantiate_and_apply_query_response(
+ &mut self,
+ param_env: ty::ParamEnv<'tcx>,
+ original_values: Vec<ty::GenericArg<'tcx>>,
+ response: CanonicalResponse<'tcx>,
+ ) -> Result<Certainty, NoSolution> {
+ let substitution = self.compute_query_response_substitution(&original_values, &response);
+
+ let Response { var_values, external_constraints, certainty } =
+ response.substitute(self.tcx(), &substitution);
+
+ self.unify_query_var_values(param_env, &original_values, var_values)?;
+
+ // FIXME: implement external constraints.
+ let ExternalConstraintsData { region_constraints, opaque_types: _ } =
+ external_constraints.deref();
+ self.register_region_constraints(region_constraints);
+
+ Ok(certainty)
+ }
+
+ /// This returns the substitutions to instantiate the bound variables of
+ /// the canonical reponse. This depends on the `original_values` for the
+ /// bound variables.
+ fn compute_query_response_substitution(
+ &self,
+ original_values: &[ty::GenericArg<'tcx>],
+ response: &CanonicalResponse<'tcx>,
+ ) -> CanonicalVarValues<'tcx> {
+ // 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 = self.infcx.universe();
+ let universes_created_in_query = response.max_universe.index() + 1;
+ for _ in 0..universes_created_in_query {
+ self.infcx.create_next_universe();
+ }
+
+ 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 = vec![None; response.variables.len()];
+ for (original_value, result_value) in iter::zip(original_values, var_values.var_values) {
+ match result_value.unpack() {
+ GenericArgKind::Type(t) => {
+ if let &ty::Bound(debruijn, b) = t.kind() {
+ assert_eq!(debruijn, ty::INNERMOST);
+ opt_values[b.var.index()] = Some(*original_value);
+ }
+ }
+ GenericArgKind::Lifetime(r) => {
+ if let ty::ReLateBound(debruijn, br) = *r {
+ assert_eq!(debruijn, ty::INNERMOST);
+ opt_values[br.var.index()] = Some(*original_value);
+ }
+ }
+ GenericArgKind::Const(c) => {
+ if let ty::ConstKind::Bound(debrujin, b) = c.kind() {
+ assert_eq!(debrujin, ty::INNERMOST);
+ opt_values[b.index()] = Some(*original_value);
+ }
+ }
+ }
+ }
+
+ let var_values = self.tcx().mk_substs_from_iter(response.variables.iter().enumerate().map(
+ |(index, info)| {
+ if info.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.
+ self.infcx.instantiate_canonical_var(DUMMY_SP, info, |idx| {
+ ty::UniverseIndex::from(prev_universe.index() + idx.index())
+ })
+ } else if info.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 conceptionally 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[index] {
+ v
+ } else {
+ self.infcx.instantiate_canonical_var(DUMMY_SP, info, |_| 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.
+ original_values[info.expect_anon_placeholder() as usize]
+ }
+ },
+ ));
+
+ CanonicalVarValues { var_values }
+ }
+
+ #[instrument(level = "debug", skip(self, param_env), ret)]
+ fn unify_query_var_values(
+ &self,
+ param_env: ty::ParamEnv<'tcx>,
+ original_values: &[ty::GenericArg<'tcx>],
+ var_values: CanonicalVarValues<'tcx>,
+ ) -> Result<(), NoSolution> {
+ assert_eq!(original_values.len(), var_values.len());
+ for (&orig, response) in iter::zip(original_values, var_values.var_values) {
+ // This can fail due to the occurs check, see
+ // `tests/ui/typeck/lazy-norm/equating-projection-cyclically.rs` for an example
+ // where that can happen.
+ //
+ // FIXME: To deal with #105787 I also expect us to emit nested obligations here at
+ // some point. We can figure out how to deal with this once we actually have
+ // an ICE.
+ let nested_goals = self.eq(param_env, orig, response)?;
+ assert!(nested_goals.is_empty(), "{nested_goals:?}");
+ }
+
+ Ok(())
+ }
+
+ fn register_region_constraints(&mut self, region_constraints: &QueryRegionConstraints<'tcx>) {
+ for &(ty::OutlivesPredicate(lhs, rhs), _) in &region_constraints.outlives {
+ match lhs.unpack() {
+ GenericArgKind::Lifetime(lhs) => self.infcx.region_outlives_predicate(
+ &ObligationCause::dummy(),
+ ty::Binder::dummy(ty::OutlivesPredicate(lhs, rhs)),
+ ),
+ GenericArgKind::Type(lhs) => self.infcx.register_region_obligation_with_cause(
+ lhs,
+ rhs,
+ &ObligationCause::dummy(),
+ ),
+ GenericArgKind::Const(_) => bug!("const outlives: {lhs:?}: {rhs:?}"),
+ }
+ }
+
+ for member_constraint in &region_constraints.member_constraints {
+ // FIXME: Deal with member constraints :<
+ let _ = member_constraint;
+ }
+ }
+}