diff options
Diffstat (limited to 'compiler/rustc_infer/src/infer/canonical')
| -rw-r--r-- | compiler/rustc_infer/src/infer/canonical/canonicalizer.rs | 791 | ||||
| -rw-r--r-- | compiler/rustc_infer/src/infer/canonical/mod.rs | 159 | ||||
| -rw-r--r-- | compiler/rustc_infer/src/infer/canonical/query_response.rs | 741 | ||||
| -rw-r--r-- | compiler/rustc_infer/src/infer/canonical/substitute.rs | 91 |
4 files changed, 1782 insertions, 0 deletions
diff --git a/compiler/rustc_infer/src/infer/canonical/canonicalizer.rs b/compiler/rustc_infer/src/infer/canonical/canonicalizer.rs new file mode 100644 index 000000000..ca7862c9d --- /dev/null +++ b/compiler/rustc_infer/src/infer/canonical/canonicalizer.rs @@ -0,0 +1,791 @@ +//! This module contains the "canonicalizer" itself. +//! +//! For an overview of what canonicalization is and how it fits into +//! rustc, check out the [chapter in the rustc dev guide][c]. +//! +//! [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html + +use crate::infer::canonical::{ + Canonical, CanonicalTyVarKind, CanonicalVarInfo, CanonicalVarKind, Canonicalized, + OriginalQueryValues, +}; +use crate::infer::InferCtxt; +use rustc_middle::ty::flags::FlagComputation; +use rustc_middle::ty::fold::{TypeFoldable, TypeFolder, TypeSuperFoldable}; +use rustc_middle::ty::subst::GenericArg; +use rustc_middle::ty::{self, BoundVar, InferConst, List, Ty, TyCtxt, TypeFlags}; +use std::sync::atomic::Ordering; + +use rustc_data_structures::fx::FxHashMap; +use rustc_index::vec::Idx; +use smallvec::SmallVec; + +impl<'cx, 'tcx> InferCtxt<'cx, 'tcx> { + /// Canonicalizes a query value `V`. When we canonicalize a query, + /// we not only canonicalize unbound inference variables, but we + /// *also* replace all free regions whatsoever. So for example a + /// query like `T: Trait<'static>` would be canonicalized to + /// + /// ```text + /// T: Trait<'?0> + /// ``` + /// + /// with a mapping M that maps `'?0` to `'static`. + /// + /// To get a good understanding of what is happening here, check + /// out the [chapter in the rustc dev guide][c]. + /// + /// [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html#canonicalizing-the-query + pub fn canonicalize_query<V>( + &self, + value: V, + query_state: &mut OriginalQueryValues<'tcx>, + ) -> Canonicalized<'tcx, V> + where + V: TypeFoldable<'tcx>, + { + self.tcx.sess.perf_stats.queries_canonicalized.fetch_add(1, Ordering::Relaxed); + + Canonicalizer::canonicalize(value, self, self.tcx, &CanonicalizeAllFreeRegions, query_state) + } + + /// Like [Self::canonicalize_query], but preserves distinct universes. For + /// example, canonicalizing `&'?0: Trait<'?1>`, where `'?0` is in `U1` and + /// `'?1` is in `U3` would be canonicalized to have ?0` in `U1` and `'?1` + /// in `U2`. + /// + /// This is used for Chalk integration. + pub fn canonicalize_query_preserving_universes<V>( + &self, + value: V, + query_state: &mut OriginalQueryValues<'tcx>, + ) -> Canonicalized<'tcx, V> + where + V: TypeFoldable<'tcx>, + { + self.tcx.sess.perf_stats.queries_canonicalized.fetch_add(1, Ordering::Relaxed); + + Canonicalizer::canonicalize( + value, + self, + self.tcx, + &CanonicalizeAllFreeRegionsPreservingUniverses, + query_state, + ) + } + + /// Canonicalizes a query *response* `V`. When we canonicalize a + /// query response, we only canonicalize unbound inference + /// variables, and we leave other free regions alone. So, + /// continuing with the example from `canonicalize_query`, if + /// there was an input query `T: Trait<'static>`, it would have + /// been canonicalized to + /// + /// ```text + /// T: Trait<'?0> + /// ``` + /// + /// with a mapping M that maps `'?0` to `'static`. But if we found that there + /// exists only one possible impl of `Trait`, and it looks like + /// ```ignore (illustrative) + /// impl<T> Trait<'static> for T { .. } + /// ``` + /// then we would prepare a query result R that (among other + /// things) includes a mapping to `'?0 := 'static`. When + /// canonicalizing this query result R, we would leave this + /// reference to `'static` alone. + /// + /// To get a good understanding of what is happening here, check + /// out the [chapter in the rustc dev guide][c]. + /// + /// [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html#canonicalizing-the-query-result + pub fn canonicalize_response<V>(&self, value: V) -> Canonicalized<'tcx, V> + where + V: TypeFoldable<'tcx>, + { + let mut query_state = OriginalQueryValues::default(); + Canonicalizer::canonicalize( + value, + self, + self.tcx, + &CanonicalizeQueryResponse, + &mut query_state, + ) + } + + pub fn canonicalize_user_type_annotation<V>(&self, value: V) -> Canonicalized<'tcx, V> + where + V: TypeFoldable<'tcx>, + { + let mut query_state = OriginalQueryValues::default(); + Canonicalizer::canonicalize( + value, + self, + self.tcx, + &CanonicalizeUserTypeAnnotation, + &mut query_state, + ) + } + + /// A variant of `canonicalize_query` that does not + /// canonicalize `'static`. This is useful when + /// the query implementation can perform more efficient + /// handling of `'static` regions (e.g. trait evaluation). + pub fn canonicalize_query_keep_static<V>( + &self, + value: V, + query_state: &mut OriginalQueryValues<'tcx>, + ) -> Canonicalized<'tcx, V> + where + V: TypeFoldable<'tcx>, + { + self.tcx.sess.perf_stats.queries_canonicalized.fetch_add(1, Ordering::Relaxed); + + Canonicalizer::canonicalize( + value, + self, + self.tcx, + &CanonicalizeFreeRegionsOtherThanStatic, + query_state, + ) + } +} + +/// Controls how we canonicalize "free regions" that are not inference +/// variables. This depends on what we are canonicalizing *for* -- +/// e.g., if we are canonicalizing to create a query, we want to +/// replace those with inference variables, since we want to make a +/// maximally general query. But if we are canonicalizing a *query +/// response*, then we don't typically replace free regions, as they +/// must have been introduced from other parts of the system. +trait CanonicalizeMode { + fn canonicalize_free_region<'tcx>( + &self, + canonicalizer: &mut Canonicalizer<'_, 'tcx>, + r: ty::Region<'tcx>, + ) -> ty::Region<'tcx>; + + fn any(&self) -> bool; + + // Do we preserve universe of variables. + fn preserve_universes(&self) -> bool; +} + +struct CanonicalizeQueryResponse; + +impl CanonicalizeMode for CanonicalizeQueryResponse { + fn canonicalize_free_region<'tcx>( + &self, + canonicalizer: &mut Canonicalizer<'_, 'tcx>, + r: ty::Region<'tcx>, + ) -> ty::Region<'tcx> { + match *r { + ty::ReFree(_) + | ty::ReErased + | ty::ReStatic + | ty::ReEmpty(ty::UniverseIndex::ROOT) + | ty::ReEarlyBound(..) => r, + + ty::RePlaceholder(placeholder) => canonicalizer.canonical_var_for_region( + CanonicalVarInfo { kind: CanonicalVarKind::PlaceholderRegion(placeholder) }, + r, + ), + + ty::ReVar(vid) => { + let universe = canonicalizer.region_var_universe(vid); + canonicalizer.canonical_var_for_region( + CanonicalVarInfo { kind: CanonicalVarKind::Region(universe) }, + r, + ) + } + + ty::ReEmpty(ui) => { + bug!("canonicalizing 'empty in universe {:?}", ui) // FIXME + } + + _ => { + // Other than `'static` or `'empty`, the query + // response should be executing in a fully + // canonicalized environment, so there shouldn't be + // any other region names it can come up. + // + // rust-lang/rust#57464: `impl Trait` can leak local + // scopes (in manner violating typeck). Therefore, use + // `delay_span_bug` to allow type error over an ICE. + ty::tls::with(|tcx| { + tcx.sess.delay_span_bug( + rustc_span::DUMMY_SP, + &format!("unexpected region in query response: `{:?}`", r), + ); + }); + r + } + } + } + + fn any(&self) -> bool { + false + } + + fn preserve_universes(&self) -> bool { + true + } +} + +struct CanonicalizeUserTypeAnnotation; + +impl CanonicalizeMode for CanonicalizeUserTypeAnnotation { + fn canonicalize_free_region<'tcx>( + &self, + canonicalizer: &mut Canonicalizer<'_, 'tcx>, + r: ty::Region<'tcx>, + ) -> ty::Region<'tcx> { + match *r { + ty::ReEarlyBound(_) | ty::ReFree(_) | ty::ReErased | ty::ReStatic => r, + ty::ReVar(_) => canonicalizer.canonical_var_for_region_in_root_universe(r), + _ => { + // We only expect region names that the user can type. + bug!("unexpected region in query response: `{:?}`", r) + } + } + } + + fn any(&self) -> bool { + false + } + + fn preserve_universes(&self) -> bool { + false + } +} + +struct CanonicalizeAllFreeRegions; + +impl CanonicalizeMode for CanonicalizeAllFreeRegions { + fn canonicalize_free_region<'tcx>( + &self, + canonicalizer: &mut Canonicalizer<'_, 'tcx>, + r: ty::Region<'tcx>, + ) -> ty::Region<'tcx> { + canonicalizer.canonical_var_for_region_in_root_universe(r) + } + + fn any(&self) -> bool { + true + } + + fn preserve_universes(&self) -> bool { + false + } +} + +struct CanonicalizeAllFreeRegionsPreservingUniverses; + +impl CanonicalizeMode for CanonicalizeAllFreeRegionsPreservingUniverses { + fn canonicalize_free_region<'tcx>( + &self, + canonicalizer: &mut Canonicalizer<'_, 'tcx>, + r: ty::Region<'tcx>, + ) -> ty::Region<'tcx> { + let universe = canonicalizer.infcx.universe_of_region(r); + canonicalizer.canonical_var_for_region( + CanonicalVarInfo { kind: CanonicalVarKind::Region(universe) }, + r, + ) + } + + fn any(&self) -> bool { + true + } + + fn preserve_universes(&self) -> bool { + true + } +} + +struct CanonicalizeFreeRegionsOtherThanStatic; + +impl CanonicalizeMode for CanonicalizeFreeRegionsOtherThanStatic { + fn canonicalize_free_region<'tcx>( + &self, + canonicalizer: &mut Canonicalizer<'_, 'tcx>, + r: ty::Region<'tcx>, + ) -> ty::Region<'tcx> { + if r.is_static() { r } else { canonicalizer.canonical_var_for_region_in_root_universe(r) } + } + + fn any(&self) -> bool { + true + } + + fn preserve_universes(&self) -> bool { + false + } +} + +struct Canonicalizer<'cx, 'tcx> { + infcx: &'cx InferCtxt<'cx, 'tcx>, + tcx: TyCtxt<'tcx>, + variables: SmallVec<[CanonicalVarInfo<'tcx>; 8]>, + query_state: &'cx mut OriginalQueryValues<'tcx>, + // Note that indices is only used once `var_values` is big enough to be + // heap-allocated. + indices: FxHashMap<GenericArg<'tcx>, BoundVar>, + canonicalize_mode: &'cx dyn CanonicalizeMode, + needs_canonical_flags: TypeFlags, + + binder_index: ty::DebruijnIndex, +} + +impl<'cx, 'tcx> TypeFolder<'tcx> for Canonicalizer<'cx, 'tcx> { + fn tcx<'b>(&'b self) -> TyCtxt<'tcx> { + self.tcx + } + + fn fold_binder<T>(&mut self, t: ty::Binder<'tcx, T>) -> ty::Binder<'tcx, T> + where + T: TypeFoldable<'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> { + match *r { + ty::ReLateBound(index, ..) => { + if index >= self.binder_index { + bug!("escaping late-bound region during canonicalization"); + } else { + r + } + } + + ty::ReVar(vid) => { + let resolved_vid = self + .infcx + .inner + .borrow_mut() + .unwrap_region_constraints() + .opportunistic_resolve_var(vid); + debug!( + "canonical: region var found with vid {:?}, \ + opportunistically resolved to {:?}", + vid, r + ); + let r = self.tcx.reuse_or_mk_region(r, ty::ReVar(resolved_vid)); + self.canonicalize_mode.canonicalize_free_region(self, r) + } + + ty::ReStatic + | ty::ReEarlyBound(..) + | ty::ReFree(_) + | ty::ReEmpty(_) + | ty::RePlaceholder(..) + | ty::ReErased => self.canonicalize_mode.canonicalize_free_region(self, r), + } + } + + fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { + match *t.kind() { + ty::Infer(ty::TyVar(vid)) => { + debug!("canonical: type var found with vid {:?}", vid); + match self.infcx.probe_ty_var(vid) { + // `t` could be a float / int variable; canonicalize that instead. + Ok(t) => { + debug!("(resolved to {:?})", t); + self.fold_ty(t) + } + + // `TyVar(vid)` is unresolved, track its universe index in the canonicalized + // result. + Err(mut ui) => { + if !self.canonicalize_mode.preserve_universes() { + // FIXME: perf problem described in #55921. + ui = ty::UniverseIndex::ROOT; + } + self.canonicalize_ty_var( + CanonicalVarInfo { + kind: CanonicalVarKind::Ty(CanonicalTyVarKind::General(ui)), + }, + t, + ) + } + } + } + + ty::Infer(ty::IntVar(_)) => self.canonicalize_ty_var( + CanonicalVarInfo { kind: CanonicalVarKind::Ty(CanonicalTyVarKind::Int) }, + t, + ), + + ty::Infer(ty::FloatVar(_)) => self.canonicalize_ty_var( + CanonicalVarInfo { kind: CanonicalVarKind::Ty(CanonicalTyVarKind::Float) }, + t, + ), + + ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => { + bug!("encountered a fresh type during canonicalization") + } + + ty::Placeholder(placeholder) => self.canonicalize_ty_var( + CanonicalVarInfo { kind: CanonicalVarKind::PlaceholderTy(placeholder) }, + t, + ), + + ty::Bound(debruijn, _) => { + if debruijn >= self.binder_index { + bug!("escaping bound type during canonicalization") + } else { + t + } + } + + ty::Closure(..) + | ty::Generator(..) + | ty::GeneratorWitness(..) + | ty::Bool + | ty::Char + | ty::Int(..) + | ty::Uint(..) + | ty::Float(..) + | ty::Adt(..) + | ty::Str + | ty::Error(_) + | ty::Array(..) + | ty::Slice(..) + | ty::RawPtr(..) + | ty::Ref(..) + | ty::FnDef(..) + | ty::FnPtr(_) + | ty::Dynamic(..) + | ty::Never + | ty::Tuple(..) + | ty::Projection(..) + | ty::Foreign(..) + | ty::Param(..) + | ty::Opaque(..) => { + if t.flags().intersects(self.needs_canonical_flags) { + t.super_fold_with(self) + } else { + t + } + } + } + } + + fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> { + match ct.kind() { + ty::ConstKind::Infer(InferConst::Var(vid)) => { + debug!("canonical: const var found with vid {:?}", vid); + match self.infcx.probe_const_var(vid) { + Ok(c) => { + debug!("(resolved to {:?})", c); + return self.fold_const(c); + } + + // `ConstVar(vid)` is unresolved, track its universe index in the + // canonicalized result + Err(mut ui) => { + if !self.canonicalize_mode.preserve_universes() { + // FIXME: perf problem described in #55921. + ui = ty::UniverseIndex::ROOT; + } + return self.canonicalize_const_var( + CanonicalVarInfo { kind: CanonicalVarKind::Const(ui, ct.ty()) }, + ct, + ); + } + } + } + ty::ConstKind::Infer(InferConst::Fresh(_)) => { + bug!("encountered a fresh const during canonicalization") + } + ty::ConstKind::Bound(debruijn, _) => { + if debruijn >= self.binder_index { + bug!("escaping bound type during canonicalization") + } else { + return ct; + } + } + ty::ConstKind::Placeholder(placeholder) => { + return self.canonicalize_const_var( + CanonicalVarInfo { + kind: CanonicalVarKind::PlaceholderConst(placeholder, ct.ty()), + }, + ct, + ); + } + _ => {} + } + + let flags = FlagComputation::for_const(ct); + if flags.intersects(self.needs_canonical_flags) { ct.super_fold_with(self) } else { ct } + } +} + +impl<'cx, 'tcx> Canonicalizer<'cx, 'tcx> { + /// The main `canonicalize` method, shared impl of + /// `canonicalize_query` and `canonicalize_response`. + fn canonicalize<V>( + value: V, + infcx: &InferCtxt<'_, 'tcx>, + tcx: TyCtxt<'tcx>, + canonicalize_region_mode: &dyn CanonicalizeMode, + query_state: &mut OriginalQueryValues<'tcx>, + ) -> Canonicalized<'tcx, V> + where + V: TypeFoldable<'tcx>, + { + let needs_canonical_flags = if canonicalize_region_mode.any() { + TypeFlags::NEEDS_INFER | + TypeFlags::HAS_FREE_REGIONS | // `HAS_RE_PLACEHOLDER` implies `HAS_FREE_REGIONS` + TypeFlags::HAS_TY_PLACEHOLDER | + TypeFlags::HAS_CT_PLACEHOLDER + } else { + TypeFlags::NEEDS_INFER + | TypeFlags::HAS_RE_PLACEHOLDER + | TypeFlags::HAS_TY_PLACEHOLDER + | TypeFlags::HAS_CT_PLACEHOLDER + }; + + // Fast path: nothing that needs to be canonicalized. + if !value.has_type_flags(needs_canonical_flags) { + let canon_value = Canonical { + max_universe: ty::UniverseIndex::ROOT, + variables: List::empty(), + value, + }; + return canon_value; + } + + let mut canonicalizer = Canonicalizer { + infcx, + tcx, + canonicalize_mode: canonicalize_region_mode, + needs_canonical_flags, + variables: SmallVec::new(), + query_state, + indices: FxHashMap::default(), + binder_index: ty::INNERMOST, + }; + let out_value = value.fold_with(&mut canonicalizer); + + // Once we have canonicalized `out_value`, it should not + // contain anything that ties it to this inference context + // anymore. + debug_assert!(!out_value.needs_infer() && !out_value.has_placeholders()); + + let canonical_variables = + tcx.intern_canonical_var_infos(&canonicalizer.universe_canonicalized_variables()); + + let max_universe = canonical_variables + .iter() + .map(|cvar| cvar.universe()) + .max() + .unwrap_or(ty::UniverseIndex::ROOT); + + Canonical { max_universe, variables: canonical_variables, value: out_value } + } + + /// Creates a canonical variable replacing `kind` from the input, + /// or returns an existing variable if `kind` has already been + /// seen. `kind` is expected to be an unbound variable (or + /// potentially a free region). + fn canonical_var(&mut self, info: CanonicalVarInfo<'tcx>, kind: GenericArg<'tcx>) -> BoundVar { + let Canonicalizer { variables, query_state, indices, .. } = self; + + let var_values = &mut query_state.var_values; + + let universe = info.universe(); + if universe != ty::UniverseIndex::ROOT { + assert!(self.canonicalize_mode.preserve_universes()); + + // Insert universe into the universe map. To preserve the order of the + // universes in the value being canonicalized, we don't update the + // universe in `info` until we have finished canonicalizing. + match query_state.universe_map.binary_search(&universe) { + Err(idx) => query_state.universe_map.insert(idx, universe), + Ok(_) => {} + } + } + + // This code is hot. `variables` and `var_values` are usually small + // (fewer than 8 elements ~95% of the time). They are SmallVec's to + // avoid allocations in those cases. We also don't use `indices` to + // determine if a kind has been seen before until the limit of 8 has + // been exceeded, to also avoid allocations for `indices`. + if !var_values.spilled() { + // `var_values` is stack-allocated. `indices` isn't used yet. Do a + // direct linear search of `var_values`. + if let Some(idx) = var_values.iter().position(|&k| k == kind) { + // `kind` is already present in `var_values`. + BoundVar::new(idx) + } else { + // `kind` isn't present in `var_values`. Append it. Likewise + // for `info` and `variables`. + variables.push(info); + var_values.push(kind); + assert_eq!(variables.len(), var_values.len()); + + // If `var_values` has become big enough to be heap-allocated, + // fill up `indices` to facilitate subsequent lookups. + if var_values.spilled() { + assert!(indices.is_empty()); + *indices = var_values + .iter() + .enumerate() + .map(|(i, &kind)| (kind, BoundVar::new(i))) + .collect(); + } + // The cv is the index of the appended element. + BoundVar::new(var_values.len() - 1) + } + } else { + // `var_values` is large. Do a hashmap search via `indices`. + *indices.entry(kind).or_insert_with(|| { + variables.push(info); + var_values.push(kind); + assert_eq!(variables.len(), var_values.len()); + BoundVar::new(variables.len() - 1) + }) + } + } + + /// Replaces the universe indexes used in `var_values` with their index in + /// `query_state.universe_map`. This minimizes the maximum universe used in + /// the canonicalized value. + fn universe_canonicalized_variables(self) -> SmallVec<[CanonicalVarInfo<'tcx>; 8]> { + if self.query_state.universe_map.len() == 1 { + return self.variables; + } + + let reverse_universe_map: FxHashMap<ty::UniverseIndex, ty::UniverseIndex> = self + .query_state + .universe_map + .iter() + .enumerate() + .map(|(idx, universe)| (*universe, ty::UniverseIndex::from_usize(idx))) + .collect(); + + self.variables + .iter() + .map(|v| CanonicalVarInfo { + kind: match v.kind { + CanonicalVarKind::Ty(CanonicalTyVarKind::Int | CanonicalTyVarKind::Float) => { + return *v; + } + CanonicalVarKind::Ty(CanonicalTyVarKind::General(u)) => { + CanonicalVarKind::Ty(CanonicalTyVarKind::General(reverse_universe_map[&u])) + } + CanonicalVarKind::Region(u) => { + CanonicalVarKind::Region(reverse_universe_map[&u]) + } + CanonicalVarKind::Const(u, t) => { + CanonicalVarKind::Const(reverse_universe_map[&u], t) + } + CanonicalVarKind::PlaceholderTy(placeholder) => { + CanonicalVarKind::PlaceholderTy(ty::Placeholder { + universe: reverse_universe_map[&placeholder.universe], + ..placeholder + }) + } + CanonicalVarKind::PlaceholderRegion(placeholder) => { + CanonicalVarKind::PlaceholderRegion(ty::Placeholder { + universe: reverse_universe_map[&placeholder.universe], + ..placeholder + }) + } + CanonicalVarKind::PlaceholderConst(placeholder, t) => { + CanonicalVarKind::PlaceholderConst( + ty::Placeholder { + universe: reverse_universe_map[&placeholder.universe], + ..placeholder + }, + t, + ) + } + }, + }) + .collect() + } + + /// Shorthand helper that creates a canonical region variable for + /// `r` (always in the root universe). The reason that we always + /// put these variables into the root universe is because this + /// method is used during **query construction:** in that case, we + /// are taking all the regions and just putting them into the most + /// generic context we can. This may generate solutions that don't + /// fit (e.g., that equate some region variable with a placeholder + /// it can't name) on the caller side, but that's ok, the caller + /// can figure that out. In the meantime, it maximizes our + /// caching. + /// + /// (This works because unification never fails -- and hence trait + /// selection is never affected -- due to a universe mismatch.) + fn canonical_var_for_region_in_root_universe( + &mut self, + r: ty::Region<'tcx>, + ) -> ty::Region<'tcx> { + self.canonical_var_for_region( + CanonicalVarInfo { kind: CanonicalVarKind::Region(ty::UniverseIndex::ROOT) }, + r, + ) + } + + /// Returns the universe in which `vid` is defined. + fn region_var_universe(&self, vid: ty::RegionVid) -> ty::UniverseIndex { + self.infcx.inner.borrow_mut().unwrap_region_constraints().var_universe(vid) + } + + /// Creates a canonical variable (with the given `info`) + /// representing the region `r`; return a region referencing it. + fn canonical_var_for_region( + &mut self, + info: CanonicalVarInfo<'tcx>, + r: ty::Region<'tcx>, + ) -> ty::Region<'tcx> { + let var = self.canonical_var(info, r.into()); + let br = ty::BoundRegion { var, kind: ty::BrAnon(var.as_u32()) }; + let region = ty::ReLateBound(self.binder_index, br); + self.tcx().mk_region(region) + } + + /// Given a type variable `ty_var` of the given kind, first check + /// if `ty_var` is bound to anything; if so, canonicalize + /// *that*. Otherwise, create a new canonical variable for + /// `ty_var`. + fn canonicalize_ty_var(&mut self, info: CanonicalVarInfo<'tcx>, ty_var: Ty<'tcx>) -> Ty<'tcx> { + let infcx = self.infcx; + let bound_to = infcx.shallow_resolve(ty_var); + if bound_to != ty_var { + self.fold_ty(bound_to) + } else { + let var = self.canonical_var(info, ty_var.into()); + self.tcx().mk_ty(ty::Bound(self.binder_index, var.into())) + } + } + + /// Given a type variable `const_var` of the given kind, first check + /// if `const_var` is bound to anything; if so, canonicalize + /// *that*. Otherwise, create a new canonical variable for + /// `const_var`. + fn canonicalize_const_var( + &mut self, + info: CanonicalVarInfo<'tcx>, + const_var: ty::Const<'tcx>, + ) -> ty::Const<'tcx> { + let infcx = self.infcx; + let bound_to = infcx.shallow_resolve(const_var); + if bound_to != const_var { + self.fold_const(bound_to) + } else { + let var = self.canonical_var(info, const_var.into()); + self.tcx().mk_const(ty::ConstS { + kind: ty::ConstKind::Bound(self.binder_index, var), + ty: self.fold_ty(const_var.ty()), + }) + } + } +} diff --git a/compiler/rustc_infer/src/infer/canonical/mod.rs b/compiler/rustc_infer/src/infer/canonical/mod.rs new file mode 100644 index 000000000..a9294a85e --- /dev/null +++ b/compiler/rustc_infer/src/infer/canonical/mod.rs @@ -0,0 +1,159 @@ +//! **Canonicalization** is the key to constructing a query in the +//! middle of type inference. Ordinarily, it is not possible to store +//! types from type inference in query keys, because they contain +//! references to inference variables whose lifetimes are too short +//! and so forth. Canonicalizing a value T1 using `canonicalize_query` +//! produces two things: +//! +//! - a value T2 where each unbound inference variable has been +//! replaced with a **canonical variable**; +//! - a map M (of type `CanonicalVarValues`) from those canonical +//! variables back to the original. +//! +//! We can then do queries using T2. These will give back constraints +//! on the canonical variables which can be translated, using the map +//! M, into constraints in our source context. This process of +//! translating the results back is done by the +//! `instantiate_query_result` method. +//! +//! For a more detailed look at what is happening here, check +//! out the [chapter in the rustc dev guide][c]. +//! +//! [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html + +use crate::infer::{ConstVariableOrigin, ConstVariableOriginKind}; +use crate::infer::{InferCtxt, RegionVariableOrigin, TypeVariableOrigin, TypeVariableOriginKind}; +use rustc_index::vec::IndexVec; +use rustc_middle::ty::fold::TypeFoldable; +use rustc_middle::ty::subst::GenericArg; +use rustc_middle::ty::{self, BoundVar, List}; +use rustc_span::source_map::Span; + +pub use rustc_middle::infer::canonical::*; +use substitute::CanonicalExt; + +mod canonicalizer; +pub mod query_response; +mod substitute; + +impl<'cx, 'tcx> InferCtxt<'cx, 'tcx> { + /// Creates a substitution S for the canonical value with fresh + /// inference variables and applies it to the canonical value. + /// Returns both the instantiated result *and* the substitution S. + /// + /// This is only meant to be invoked as part of constructing an + /// inference context at the start of a query (see + /// `InferCtxtBuilder::enter_with_canonical`). It basically + /// brings the canonical value "into scope" within your new infcx. + /// + /// At the end of processing, the substitution S (once + /// canonicalized) then represents the values that you computed + /// for each of the canonical inputs to your query. + pub fn instantiate_canonical_with_fresh_inference_vars<T>( + &self, + span: Span, + canonical: &Canonical<'tcx, T>, + ) -> (T, CanonicalVarValues<'tcx>) + where + T: TypeFoldable<'tcx>, + { + // For each universe that is referred to in the incoming + // query, create a universe in our local inference context. In + // practice, as of this writing, all queries have no universes + // in them, so this code has no effect, but it is looking + // forward to the day when we *do* want to carry universes + // through into queries. + let universes: IndexVec<ty::UniverseIndex, _> = std::iter::once(ty::UniverseIndex::ROOT) + .chain((0..canonical.max_universe.as_u32()).map(|_| self.create_next_universe())) + .collect(); + + let canonical_inference_vars = + self.instantiate_canonical_vars(span, canonical.variables, |ui| universes[ui]); + let result = canonical.substitute(self.tcx, &canonical_inference_vars); + (result, canonical_inference_vars) + } + + /// Given the "infos" about the canonical variables from some + /// canonical, creates fresh variables with the same + /// characteristics (see `instantiate_canonical_var` for + /// details). You can then use `substitute` to instantiate the + /// canonical variable with these inference variables. + fn instantiate_canonical_vars( + &self, + span: Span, + variables: &List<CanonicalVarInfo<'tcx>>, + universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex, + ) -> CanonicalVarValues<'tcx> { + let var_values: IndexVec<BoundVar, GenericArg<'tcx>> = variables + .iter() + .map(|info| self.instantiate_canonical_var(span, info, &universe_map)) + .collect(); + + CanonicalVarValues { var_values } + } + + /// Given the "info" about a canonical variable, creates a fresh + /// variable for it. If this is an existentially quantified + /// variable, then you'll get a new inference variable; if it is a + /// universally quantified variable, you get a placeholder. + fn instantiate_canonical_var( + &self, + span: Span, + cv_info: CanonicalVarInfo<'tcx>, + universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex, + ) -> GenericArg<'tcx> { + match cv_info.kind { + CanonicalVarKind::Ty(ty_kind) => { + let ty = match ty_kind { + CanonicalTyVarKind::General(ui) => self.next_ty_var_in_universe( + TypeVariableOrigin { kind: TypeVariableOriginKind::MiscVariable, span }, + universe_map(ui), + ), + + CanonicalTyVarKind::Int => self.next_int_var(), + + CanonicalTyVarKind::Float => self.next_float_var(), + }; + ty.into() + } + + CanonicalVarKind::PlaceholderTy(ty::PlaceholderType { universe, name }) => { + let universe_mapped = universe_map(universe); + let placeholder_mapped = ty::PlaceholderType { universe: universe_mapped, name }; + self.tcx.mk_ty(ty::Placeholder(placeholder_mapped)).into() + } + + CanonicalVarKind::Region(ui) => self + .next_region_var_in_universe( + RegionVariableOrigin::MiscVariable(span), + universe_map(ui), + ) + .into(), + + CanonicalVarKind::PlaceholderRegion(ty::PlaceholderRegion { universe, name }) => { + let universe_mapped = universe_map(universe); + let placeholder_mapped = ty::PlaceholderRegion { universe: universe_mapped, name }; + self.tcx.mk_region(ty::RePlaceholder(placeholder_mapped)).into() + } + + CanonicalVarKind::Const(ui, ty) => self + .next_const_var_in_universe( + ty, + ConstVariableOrigin { kind: ConstVariableOriginKind::MiscVariable, span }, + universe_map(ui), + ) + .into(), + + CanonicalVarKind::PlaceholderConst(ty::PlaceholderConst { universe, name }, ty) => { + let universe_mapped = universe_map(universe); + let placeholder_mapped = ty::PlaceholderConst { universe: universe_mapped, name }; + self.tcx + .mk_const(ty::ConstS { + kind: ty::ConstKind::Placeholder(placeholder_mapped), + ty, + }) + .into() + } + } + } +} diff --git a/compiler/rustc_infer/src/infer/canonical/query_response.rs b/compiler/rustc_infer/src/infer/canonical/query_response.rs new file mode 100644 index 000000000..8dc20544f --- /dev/null +++ b/compiler/rustc_infer/src/infer/canonical/query_response.rs @@ -0,0 +1,741 @@ +//! This module contains the code to instantiate a "query result", and +//! in particular to extract out the resulting region obligations and +//! encode them therein. +//! +//! For an overview of what canonicalization is and how it fits into +//! rustc, check out the [chapter in the rustc dev guide][c]. +//! +//! [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html + +use crate::infer::canonical::substitute::{substitute_value, CanonicalExt}; +use crate::infer::canonical::{ + Canonical, CanonicalVarValues, CanonicalizedQueryResponse, Certainty, OriginalQueryValues, + QueryOutlivesConstraint, QueryRegionConstraints, QueryResponse, +}; +use crate::infer::nll_relate::{NormalizationStrategy, TypeRelating, TypeRelatingDelegate}; +use crate::infer::region_constraints::{Constraint, RegionConstraintData}; +use crate::infer::{InferCtxt, InferOk, InferResult, NllRegionVariableOrigin}; +use crate::traits::query::{Fallible, NoSolution}; +use crate::traits::TraitEngine; +use crate::traits::{Obligation, ObligationCause, PredicateObligation}; +use rustc_data_structures::captures::Captures; +use rustc_index::vec::Idx; +use rustc_index::vec::IndexVec; +use rustc_middle::arena::ArenaAllocatable; +use rustc_middle::ty::error::TypeError; +use rustc_middle::ty::fold::TypeFoldable; +use rustc_middle::ty::relate::TypeRelation; +use rustc_middle::ty::subst::{GenericArg, GenericArgKind}; +use rustc_middle::ty::{self, BoundVar, Const, ToPredicate, Ty, TyCtxt}; +use rustc_span::Span; +use std::fmt::Debug; +use std::iter; + +impl<'cx, 'tcx> InferCtxt<'cx, 'tcx> { + /// This method is meant to be invoked as the final step of a canonical query + /// implementation. It is given: + /// + /// - the instantiated variables `inference_vars` created from the query key + /// - the result `answer` of the query + /// - a fulfillment context `fulfill_cx` that may contain various obligations which + /// have yet to be proven. + /// + /// Given this, the function will process the obligations pending + /// in `fulfill_cx`: + /// + /// - If all the obligations can be proven successfully, it will + /// package up any resulting region obligations (extracted from + /// `infcx`) along with the fully resolved value `answer` into a + /// query result (which is then itself canonicalized). + /// - If some obligations can be neither proven nor disproven, then + /// the same thing happens, but the resulting query is marked as ambiguous. + /// - Finally, if any of the obligations result in a hard error, + /// then `Err(NoSolution)` is returned. + #[instrument(skip(self, inference_vars, answer, fulfill_cx), level = "trace")] + pub fn make_canonicalized_query_response<T>( + &self, + inference_vars: CanonicalVarValues<'tcx>, + answer: T, + fulfill_cx: &mut dyn TraitEngine<'tcx>, + ) -> Fallible<CanonicalizedQueryResponse<'tcx, T>> + where + T: Debug + TypeFoldable<'tcx>, + Canonical<'tcx, QueryResponse<'tcx, T>>: ArenaAllocatable<'tcx>, + { + let query_response = self.make_query_response(inference_vars, answer, fulfill_cx)?; + let canonical_result = self.canonicalize_response(query_response); + + debug!("canonical_result = {:#?}", canonical_result); + + Ok(self.tcx.arena.alloc(canonical_result)) + } + + /// A version of `make_canonicalized_query_response` that does + /// not pack in obligations, for contexts that want to drop + /// pending obligations instead of treating them as an ambiguity (e.g. + /// typeck "probing" contexts). + /// + /// If you DO want to keep track of pending obligations (which + /// include all region obligations, so this includes all cases + /// that care about regions) with this function, you have to + /// do it yourself, by e.g., having them be a part of the answer. + pub fn make_query_response_ignoring_pending_obligations<T>( + &self, + inference_vars: CanonicalVarValues<'tcx>, + answer: T, + ) -> Canonical<'tcx, QueryResponse<'tcx, T>> + where + T: Debug + TypeFoldable<'tcx>, + { + self.canonicalize_response(QueryResponse { + var_values: inference_vars, + region_constraints: QueryRegionConstraints::default(), + certainty: Certainty::Proven, // Ambiguities are OK! + opaque_types: vec![], + value: answer, + }) + } + + /// Helper for `make_canonicalized_query_response` that does + /// everything up until the final canonicalization. + #[instrument(skip(self, fulfill_cx), level = "debug")] + fn make_query_response<T>( + &self, + inference_vars: CanonicalVarValues<'tcx>, + answer: T, + fulfill_cx: &mut dyn TraitEngine<'tcx>, + ) -> Result<QueryResponse<'tcx, T>, NoSolution> + where + T: Debug + TypeFoldable<'tcx>, + { + let tcx = self.tcx; + + // Select everything, returning errors. + let true_errors = fulfill_cx.select_where_possible(self); + debug!("true_errors = {:#?}", true_errors); + + if !true_errors.is_empty() { + // FIXME -- we don't indicate *why* we failed to solve + debug!("make_query_response: true_errors={:#?}", true_errors); + return Err(NoSolution); + } + + // Anything left unselected *now* must be an ambiguity. + let ambig_errors = fulfill_cx.select_all_or_error(self); + debug!("ambig_errors = {:#?}", ambig_errors); + + let region_obligations = self.take_registered_region_obligations(); + let region_constraints = self.with_region_constraints(|region_constraints| { + make_query_region_constraints( + tcx, + region_obligations.iter().map(|r_o| (r_o.sup_type, r_o.sub_region)), + region_constraints, + ) + }); + + let certainty = + if ambig_errors.is_empty() { Certainty::Proven } else { Certainty::Ambiguous }; + + let opaque_types = self.take_opaque_types_for_query_response(); + + Ok(QueryResponse { + var_values: inference_vars, + region_constraints, + certainty, + value: answer, + opaque_types, + }) + } + + fn take_opaque_types_for_query_response(&self) -> Vec<(Ty<'tcx>, Ty<'tcx>)> { + self.inner + .borrow_mut() + .opaque_type_storage + .take_opaque_types() + .into_iter() + .map(|(k, v)| (self.tcx.mk_opaque(k.def_id.to_def_id(), k.substs), v.hidden_type.ty)) + .collect() + } + + /// Given the (canonicalized) result to a canonical query, + /// instantiates the result so it can be used, plugging in the + /// values from the canonical query. (Note that the result may + /// have been ambiguous; you should check the certainty level of + /// the query before applying this function.) + /// + /// To get a good understanding of what is happening here, check + /// out the [chapter in the rustc dev guide][c]. + /// + /// [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html#processing-the-canonicalized-query-result + pub fn instantiate_query_response_and_region_obligations<R>( + &self, + cause: &ObligationCause<'tcx>, + param_env: ty::ParamEnv<'tcx>, + original_values: &OriginalQueryValues<'tcx>, + query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>, + ) -> InferResult<'tcx, R> + where + R: Debug + TypeFoldable<'tcx>, + { + let InferOk { value: result_subst, mut obligations } = + self.query_response_substitution(cause, param_env, original_values, query_response)?; + + obligations.extend(self.query_outlives_constraints_into_obligations( + cause, + param_env, + &query_response.value.region_constraints.outlives, + &result_subst, + )); + + let user_result: R = + query_response.substitute_projected(self.tcx, &result_subst, |q_r| q_r.value.clone()); + + Ok(InferOk { value: user_result, obligations }) + } + + /// An alternative to + /// `instantiate_query_response_and_region_obligations` that is more + /// efficient for NLL. NLL is a bit more advanced in the + /// "transition to chalk" than the rest of the compiler. During + /// the NLL type check, all of the "processing" of types and + /// things happens in queries -- the NLL checker itself is only + /// interested in the region obligations (`'a: 'b` or `T: 'b`) + /// that come out of these queries, which it wants to convert into + /// MIR-based constraints and solve. Therefore, it is most + /// convenient for the NLL Type Checker to **directly consume** + /// the `QueryOutlivesConstraint` values that arise from doing a + /// query. This is contrast to other parts of the compiler, which + /// would prefer for those `QueryOutlivesConstraint` to be converted + /// into the older infcx-style constraints (e.g., calls to + /// `sub_regions` or `register_region_obligation`). + /// + /// Therefore, `instantiate_nll_query_response_and_region_obligations` performs the same + /// basic operations as `instantiate_query_response_and_region_obligations` but + /// it returns its result differently: + /// + /// - It creates a substitution `S` that maps from the original + /// query variables to the values computed in the query + /// result. If any errors arise, they are propagated back as an + /// `Err` result. + /// - In the case of a successful substitution, we will append + /// `QueryOutlivesConstraint` values onto the + /// `output_query_region_constraints` vector for the solver to + /// use (if an error arises, some values may also be pushed, but + /// they should be ignored). + /// - It **can happen** (though it rarely does currently) that + /// equating types and things will give rise to subobligations + /// that must be processed. In this case, those subobligations + /// are propagated back in the return value. + /// - Finally, the query result (of type `R`) is propagated back, + /// after applying the substitution `S`. + pub fn instantiate_nll_query_response_and_region_obligations<R>( + &self, + cause: &ObligationCause<'tcx>, + param_env: ty::ParamEnv<'tcx>, + original_values: &OriginalQueryValues<'tcx>, + query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>, + output_query_region_constraints: &mut QueryRegionConstraints<'tcx>, + ) -> InferResult<'tcx, R> + where + R: Debug + TypeFoldable<'tcx>, + { + let InferOk { value: result_subst, mut obligations } = self + .query_response_substitution_guess(cause, param_env, original_values, query_response)?; + + // Compute `QueryOutlivesConstraint` values that unify each of + // the original values `v_o` that was canonicalized into a + // variable... + + for (index, original_value) in original_values.var_values.iter().enumerate() { + // ...with the value `v_r` of that variable from the query. + let result_value = query_response.substitute_projected(self.tcx, &result_subst, |v| { + v.var_values[BoundVar::new(index)] + }); + match (original_value.unpack(), result_value.unpack()) { + (GenericArgKind::Lifetime(re1), GenericArgKind::Lifetime(re2)) + if re1.is_erased() && re2.is_erased() => + { + // No action needed. + } + + (GenericArgKind::Lifetime(v_o), GenericArgKind::Lifetime(v_r)) => { + // To make `v_o = v_r`, we emit `v_o: v_r` and `v_r: v_o`. + if v_o != v_r { + output_query_region_constraints + .outlives + .push(ty::Binder::dummy(ty::OutlivesPredicate(v_o.into(), v_r))); + output_query_region_constraints + .outlives + .push(ty::Binder::dummy(ty::OutlivesPredicate(v_r.into(), v_o))); + } + } + + (GenericArgKind::Type(v1), GenericArgKind::Type(v2)) => { + TypeRelating::new( + self, + QueryTypeRelatingDelegate { + infcx: self, + param_env, + cause, + obligations: &mut obligations, + }, + ty::Variance::Invariant, + ) + .relate(v1, v2)?; + } + + (GenericArgKind::Const(v1), GenericArgKind::Const(v2)) => { + TypeRelating::new( + self, + QueryTypeRelatingDelegate { + infcx: self, + param_env, + cause, + obligations: &mut obligations, + }, + ty::Variance::Invariant, + ) + .relate(v1, v2)?; + } + + _ => { + bug!("kind mismatch, cannot unify {:?} and {:?}", original_value, result_value); + } + } + } + + // ...also include the other query region constraints from the query. + output_query_region_constraints.outlives.extend( + query_response.value.region_constraints.outlives.iter().filter_map(|&r_c| { + let r_c = substitute_value(self.tcx, &result_subst, r_c); + + // Screen out `'a: 'a` cases -- we skip the binder here but + // only compare the inner values to one another, so they are still at + // consistent binding levels. + let ty::OutlivesPredicate(k1, r2) = r_c.skip_binder(); + if k1 != r2.into() { Some(r_c) } else { None } + }), + ); + + // ...also include the query member constraints. + output_query_region_constraints.member_constraints.extend( + query_response + .value + .region_constraints + .member_constraints + .iter() + .map(|p_c| substitute_value(self.tcx, &result_subst, p_c.clone())), + ); + + let user_result: R = + query_response.substitute_projected(self.tcx, &result_subst, |q_r| q_r.value.clone()); + + Ok(InferOk { value: user_result, obligations }) + } + + /// Given the original values and the (canonicalized) result from + /// computing a query, returns a substitution that can be applied + /// to the query result to convert the result back into the + /// original namespace. + /// + /// The substitution also comes accompanied with subobligations + /// that arose from unification; these might occur if (for + /// example) we are doing lazy normalization and the value + /// assigned to a type variable is unified with an unnormalized + /// projection. + fn query_response_substitution<R>( + &self, + cause: &ObligationCause<'tcx>, + param_env: ty::ParamEnv<'tcx>, + original_values: &OriginalQueryValues<'tcx>, + query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>, + ) -> InferResult<'tcx, CanonicalVarValues<'tcx>> + where + R: Debug + TypeFoldable<'tcx>, + { + debug!( + "query_response_substitution(original_values={:#?}, query_response={:#?})", + original_values, query_response, + ); + + let mut value = self.query_response_substitution_guess( + cause, + param_env, + original_values, + query_response, + )?; + + value.obligations.extend( + self.unify_query_response_substitution_guess( + cause, + param_env, + original_values, + &value.value, + query_response, + )? + .into_obligations(), + ); + + Ok(value) + } + + /// Given the original values and the (canonicalized) result from + /// computing a query, returns a **guess** at a substitution that + /// can be applied to the query result to convert the result back + /// into the original namespace. This is called a **guess** + /// because it uses a quick heuristic to find the values for each + /// canonical variable; if that quick heuristic fails, then we + /// will instantiate fresh inference variables for each canonical + /// variable instead. Therefore, the result of this method must be + /// properly unified + fn query_response_substitution_guess<R>( + &self, + cause: &ObligationCause<'tcx>, + param_env: ty::ParamEnv<'tcx>, + original_values: &OriginalQueryValues<'tcx>, + query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>, + ) -> InferResult<'tcx, CanonicalVarValues<'tcx>> + where + R: Debug + TypeFoldable<'tcx>, + { + debug!( + "query_response_substitution_guess(original_values={:#?}, query_response={:#?})", + original_values, query_response, + ); + + // For each new universe created in the query result that did + // not appear in the original query, create a local + // superuniverse. + let mut universe_map = original_values.universe_map.clone(); + let num_universes_in_query = original_values.universe_map.len(); + let num_universes_in_response = query_response.max_universe.as_usize() + 1; + for _ in num_universes_in_query..num_universes_in_response { + universe_map.push(self.create_next_universe()); + } + assert!(!universe_map.is_empty()); // always have the root universe + assert_eq!(universe_map[ty::UniverseIndex::ROOT.as_usize()], ty::UniverseIndex::ROOT); + + // Every canonical query result includes values for each of + // the inputs to the query. Therefore, we begin by unifying + // these values with the original inputs that were + // canonicalized. + let result_values = &query_response.value.var_values; + assert_eq!(original_values.var_values.len(), result_values.len()); + + // Quickly try to find initial values for the canonical + // variables in the result in terms of the query. We do this + // by iterating down the values that the query gave to each of + // the canonical inputs. If we find that one of those values + // is directly equal to one of the canonical variables in the + // result, then we can type the corresponding value from the + // input. See the example above. + let mut opt_values: IndexVec<BoundVar, Option<GenericArg<'tcx>>> = + IndexVec::from_elem_n(None, query_response.variables.len()); + + // In terms of our example above, we are iterating over pairs like: + // [(?A, Vec<?0>), ('static, '?1), (?B, ?0)] + for (original_value, result_value) in iter::zip(&original_values.var_values, result_values) + { + match result_value.unpack() { + GenericArgKind::Type(result_value) => { + // e.g., here `result_value` might be `?0` in the example above... + if let ty::Bound(debruijn, b) = *result_value.kind() { + // ...in which case we would set `canonical_vars[0]` to `Some(?U)`. + + // We only allow a `ty::INNERMOST` index in substitutions. + assert_eq!(debruijn, ty::INNERMOST); + opt_values[b.var] = Some(*original_value); + } + } + GenericArgKind::Lifetime(result_value) => { + // e.g., here `result_value` might be `'?1` in the example above... + if let ty::ReLateBound(debruijn, br) = *result_value { + // ... in which case we would set `canonical_vars[0]` to `Some('static)`. + + // We only allow a `ty::INNERMOST` index in substitutions. + assert_eq!(debruijn, ty::INNERMOST); + opt_values[br.var] = Some(*original_value); + } + } + GenericArgKind::Const(result_value) => { + if let ty::ConstKind::Bound(debrujin, b) = result_value.kind() { + // ...in which case we would set `canonical_vars[0]` to `Some(const X)`. + + // We only allow a `ty::INNERMOST` index in substitutions. + assert_eq!(debrujin, ty::INNERMOST); + opt_values[b] = Some(*original_value); + } + } + } + } + + // Create a result substitution: if we found a value for a + // given variable in the loop above, use that. Otherwise, use + // a fresh inference variable. + let result_subst = CanonicalVarValues { + var_values: query_response + .variables + .iter() + .enumerate() + .map(|(index, info)| { + if info.is_existential() { + match opt_values[BoundVar::new(index)] { + Some(k) => k, + None => self.instantiate_canonical_var(cause.span, info, |u| { + universe_map[u.as_usize()] + }), + } + } else { + self.instantiate_canonical_var(cause.span, info, |u| { + universe_map[u.as_usize()] + }) + } + }) + .collect(), + }; + + let mut obligations = vec![]; + + // Carry all newly resolved opaque types to the caller's scope + for &(a, b) in &query_response.value.opaque_types { + let a = substitute_value(self.tcx, &result_subst, a); + let b = substitute_value(self.tcx, &result_subst, b); + obligations.extend(self.handle_opaque_type(a, b, true, cause, param_env)?.obligations); + } + + Ok(InferOk { value: result_subst, obligations }) + } + + /// Given a "guess" at the values for the canonical variables in + /// the input, try to unify with the *actual* values found in the + /// query result. Often, but not always, this is a no-op, because + /// we already found the mapping in the "guessing" step. + /// + /// See also: `query_response_substitution_guess` + fn unify_query_response_substitution_guess<R>( + &self, + cause: &ObligationCause<'tcx>, + param_env: ty::ParamEnv<'tcx>, + original_values: &OriginalQueryValues<'tcx>, + result_subst: &CanonicalVarValues<'tcx>, + query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>, + ) -> InferResult<'tcx, ()> + where + R: Debug + TypeFoldable<'tcx>, + { + // A closure that yields the result value for the given + // canonical variable; this is taken from + // `query_response.var_values` after applying the substitution + // `result_subst`. + let substituted_query_response = |index: BoundVar| -> GenericArg<'tcx> { + query_response.substitute_projected(self.tcx, &result_subst, |v| v.var_values[index]) + }; + + // Unify the original value for each variable with the value + // taken from `query_response` (after applying `result_subst`). + self.unify_canonical_vars(cause, param_env, original_values, substituted_query_response) + } + + /// Converts the region constraints resulting from a query into an + /// iterator of obligations. + fn query_outlives_constraints_into_obligations<'a>( + &'a self, + cause: &'a ObligationCause<'tcx>, + param_env: ty::ParamEnv<'tcx>, + unsubstituted_region_constraints: &'a [QueryOutlivesConstraint<'tcx>], + result_subst: &'a CanonicalVarValues<'tcx>, + ) -> impl Iterator<Item = PredicateObligation<'tcx>> + 'a + Captures<'tcx> { + unsubstituted_region_constraints.iter().map(move |&constraint| { + let predicate = substitute_value(self.tcx, result_subst, constraint); + self.query_outlives_constraint_to_obligation(predicate, cause.clone(), param_env) + }) + } + + pub fn query_outlives_constraint_to_obligation( + &self, + predicate: QueryOutlivesConstraint<'tcx>, + cause: ObligationCause<'tcx>, + param_env: ty::ParamEnv<'tcx>, + ) -> Obligation<'tcx, ty::Predicate<'tcx>> { + let ty::OutlivesPredicate(k1, r2) = predicate.skip_binder(); + + let atom = match k1.unpack() { + GenericArgKind::Lifetime(r1) => { + ty::PredicateKind::RegionOutlives(ty::OutlivesPredicate(r1, r2)) + } + GenericArgKind::Type(t1) => { + ty::PredicateKind::TypeOutlives(ty::OutlivesPredicate(t1, r2)) + } + GenericArgKind::Const(..) => { + // Consts cannot outlive one another, so we don't expect to + // encounter this branch. + span_bug!(cause.span, "unexpected const outlives {:?}", predicate); + } + }; + let predicate = predicate.rebind(atom).to_predicate(self.tcx); + + Obligation::new(cause, param_env, predicate) + } + + /// Given two sets of values for the same set of canonical variables, unify them. + /// The second set is produced lazily by supplying indices from the first set. + fn unify_canonical_vars( + &self, + cause: &ObligationCause<'tcx>, + param_env: ty::ParamEnv<'tcx>, + variables1: &OriginalQueryValues<'tcx>, + variables2: impl Fn(BoundVar) -> GenericArg<'tcx>, + ) -> InferResult<'tcx, ()> { + self.commit_if_ok(|_| { + let mut obligations = vec![]; + for (index, value1) in variables1.var_values.iter().enumerate() { + let value2 = variables2(BoundVar::new(index)); + + match (value1.unpack(), value2.unpack()) { + (GenericArgKind::Type(v1), GenericArgKind::Type(v2)) => { + obligations + .extend(self.at(cause, param_env).eq(v1, v2)?.into_obligations()); + } + (GenericArgKind::Lifetime(re1), GenericArgKind::Lifetime(re2)) + if re1.is_erased() && re2.is_erased() => + { + // no action needed + } + (GenericArgKind::Lifetime(v1), GenericArgKind::Lifetime(v2)) => { + obligations + .extend(self.at(cause, param_env).eq(v1, v2)?.into_obligations()); + } + (GenericArgKind::Const(v1), GenericArgKind::Const(v2)) => { + let ok = self.at(cause, param_env).eq(v1, v2)?; + obligations.extend(ok.into_obligations()); + } + _ => { + bug!("kind mismatch, cannot unify {:?} and {:?}", value1, value2,); + } + } + } + Ok(InferOk { value: (), obligations }) + }) + } +} + +/// Given the region obligations and constraints scraped from the infcx, +/// creates query region constraints. +pub fn make_query_region_constraints<'tcx>( + tcx: TyCtxt<'tcx>, + outlives_obligations: impl Iterator<Item = (Ty<'tcx>, ty::Region<'tcx>)>, + region_constraints: &RegionConstraintData<'tcx>, +) -> QueryRegionConstraints<'tcx> { + let RegionConstraintData { constraints, verifys, givens, member_constraints } = + region_constraints; + + assert!(verifys.is_empty()); + assert!(givens.is_empty()); + + let outlives: Vec<_> = constraints + .iter() + .map(|(k, _)| match *k { + // Swap regions because we are going from sub (<=) to outlives + // (>=). + Constraint::VarSubVar(v1, v2) => ty::OutlivesPredicate( + tcx.mk_region(ty::ReVar(v2)).into(), + tcx.mk_region(ty::ReVar(v1)), + ), + Constraint::VarSubReg(v1, r2) => { + ty::OutlivesPredicate(r2.into(), tcx.mk_region(ty::ReVar(v1))) + } + Constraint::RegSubVar(r1, v2) => { + ty::OutlivesPredicate(tcx.mk_region(ty::ReVar(v2)).into(), r1) + } + Constraint::RegSubReg(r1, r2) => ty::OutlivesPredicate(r2.into(), r1), + }) + .map(ty::Binder::dummy) // no bound vars in the code above + .chain( + outlives_obligations + .map(|(ty, r)| ty::OutlivesPredicate(ty.into(), r)) + .map(ty::Binder::dummy), // no bound vars in the code above + ) + .collect(); + + QueryRegionConstraints { outlives, member_constraints: member_constraints.clone() } +} + +struct QueryTypeRelatingDelegate<'a, 'tcx> { + infcx: &'a InferCtxt<'a, 'tcx>, + obligations: &'a mut Vec<PredicateObligation<'tcx>>, + param_env: ty::ParamEnv<'tcx>, + cause: &'a ObligationCause<'tcx>, +} + +impl<'tcx> TypeRelatingDelegate<'tcx> for QueryTypeRelatingDelegate<'_, 'tcx> { + fn span(&self) -> Span { + self.cause.span + } + + fn param_env(&self) -> ty::ParamEnv<'tcx> { + self.param_env + } + + fn create_next_universe(&mut self) -> ty::UniverseIndex { + self.infcx.create_next_universe() + } + + fn next_existential_region_var(&mut self, from_forall: bool) -> ty::Region<'tcx> { + let origin = NllRegionVariableOrigin::Existential { from_forall }; + self.infcx.next_nll_region_var(origin) + } + + fn next_placeholder_region(&mut self, placeholder: ty::PlaceholderRegion) -> ty::Region<'tcx> { + self.infcx.tcx.mk_region(ty::RePlaceholder(placeholder)) + } + + fn generalize_existential(&mut self, universe: ty::UniverseIndex) -> ty::Region<'tcx> { + self.infcx.next_nll_region_var_in_universe( + NllRegionVariableOrigin::Existential { from_forall: false }, + universe, + ) + } + + fn push_outlives( + &mut self, + sup: ty::Region<'tcx>, + sub: ty::Region<'tcx>, + _info: ty::VarianceDiagInfo<'tcx>, + ) { + self.obligations.push(Obligation { + cause: self.cause.clone(), + param_env: self.param_env, + predicate: ty::Binder::dummy(ty::PredicateKind::RegionOutlives(ty::OutlivesPredicate( + sup, sub, + ))) + .to_predicate(self.infcx.tcx), + recursion_depth: 0, + }); + } + + fn const_equate(&mut self, _a: Const<'tcx>, _b: Const<'tcx>) { + span_bug!(self.cause.span(), "generic_const_exprs: unreachable `const_equate`"); + } + + fn normalization() -> NormalizationStrategy { + NormalizationStrategy::Eager + } + + fn forbid_inference_vars() -> bool { + true + } + + fn register_opaque_type( + &mut self, + a: Ty<'tcx>, + b: Ty<'tcx>, + a_is_expected: bool, + ) -> Result<(), TypeError<'tcx>> { + self.obligations.extend( + self.infcx + .handle_opaque_type(a, b, a_is_expected, &self.cause, self.param_env)? + .obligations, + ); + Ok(()) + } +} diff --git a/compiler/rustc_infer/src/infer/canonical/substitute.rs b/compiler/rustc_infer/src/infer/canonical/substitute.rs new file mode 100644 index 000000000..34b611342 --- /dev/null +++ b/compiler/rustc_infer/src/infer/canonical/substitute.rs @@ -0,0 +1,91 @@ +//! This module contains code to substitute new values into a +//! `Canonical<'tcx, T>`. +//! +//! For an overview of what canonicalization is and how it fits into +//! rustc, check out the [chapter in the rustc dev guide][c]. +//! +//! [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html + +use crate::infer::canonical::{Canonical, CanonicalVarValues}; +use rustc_middle::ty::fold::{FnMutDelegate, TypeFoldable}; +use rustc_middle::ty::subst::GenericArgKind; +use rustc_middle::ty::{self, TyCtxt}; + +pub(super) trait CanonicalExt<'tcx, V> { + /// Instantiate the wrapped value, replacing each canonical value + /// with the value given in `var_values`. + fn substitute(&self, tcx: TyCtxt<'tcx>, var_values: &CanonicalVarValues<'tcx>) -> V + where + V: TypeFoldable<'tcx>; + + /// Allows one to apply a substitute to some subset of + /// `self.value`. Invoke `projection_fn` with `self.value` to get + /// a value V that is expressed in terms of the same canonical + /// variables bound in `self` (usually this extracts from subset + /// of `self`). Apply the substitution `var_values` to this value + /// V, replacing each of the canonical variables. + fn substitute_projected<T>( + &self, + tcx: TyCtxt<'tcx>, + var_values: &CanonicalVarValues<'tcx>, + projection_fn: impl FnOnce(&V) -> T, + ) -> T + where + T: TypeFoldable<'tcx>; +} + +impl<'tcx, V> CanonicalExt<'tcx, V> for Canonical<'tcx, V> { + fn substitute(&self, tcx: TyCtxt<'tcx>, var_values: &CanonicalVarValues<'tcx>) -> V + where + V: TypeFoldable<'tcx>, + { + self.substitute_projected(tcx, var_values, |value| value.clone()) + } + + fn substitute_projected<T>( + &self, + tcx: TyCtxt<'tcx>, + var_values: &CanonicalVarValues<'tcx>, + projection_fn: impl FnOnce(&V) -> T, + ) -> T + where + T: TypeFoldable<'tcx>, + { + assert_eq!(self.variables.len(), var_values.len()); + let value = projection_fn(&self.value); + substitute_value(tcx, var_values, value) + } +} + +/// Substitute the values from `var_values` into `value`. `var_values` +/// must be values for the set of canonical variables that appear in +/// `value`. +pub(super) fn substitute_value<'tcx, T>( + tcx: TyCtxt<'tcx>, + var_values: &CanonicalVarValues<'tcx>, + value: T, +) -> T +where + T: TypeFoldable<'tcx>, +{ + if var_values.var_values.is_empty() { + value + } else { + let delegate = FnMutDelegate { + regions: |br: ty::BoundRegion| match var_values.var_values[br.var].unpack() { + GenericArgKind::Lifetime(l) => l, + r => bug!("{:?} is a region but value is {:?}", br, r), + }, + types: |bound_ty: ty::BoundTy| match var_values.var_values[bound_ty.var].unpack() { + GenericArgKind::Type(ty) => ty, + r => bug!("{:?} is a type but value is {:?}", bound_ty, r), + }, + consts: |bound_ct: ty::BoundVar, _| match var_values.var_values[bound_ct].unpack() { + GenericArgKind::Const(ct) => ct, + c => bug!("{:?} is a const but value is {:?}", bound_ct, c), + }, + }; + + tcx.replace_escaping_bound_vars_uncached(value, delegate) + } +} |