diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-17 12:02:58 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-17 12:02:58 +0000 |
commit | 698f8c2f01ea549d77d7dc3338a12e04c11057b9 (patch) | |
tree | 173a775858bd501c378080a10dca74132f05bc50 /compiler/rustc_middle/src/infer | |
parent | Initial commit. (diff) | |
download | rustc-698f8c2f01ea549d77d7dc3338a12e04c11057b9.tar.xz rustc-698f8c2f01ea549d77d7dc3338a12e04c11057b9.zip |
Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'compiler/rustc_middle/src/infer')
-rw-r--r-- | compiler/rustc_middle/src/infer/canonical.rs | 363 | ||||
-rw-r--r-- | compiler/rustc_middle/src/infer/mod.rs | 32 | ||||
-rw-r--r-- | compiler/rustc_middle/src/infer/unify_key.rs | 162 |
3 files changed, 557 insertions, 0 deletions
diff --git a/compiler/rustc_middle/src/infer/canonical.rs b/compiler/rustc_middle/src/infer/canonical.rs new file mode 100644 index 000000000..200de9079 --- /dev/null +++ b/compiler/rustc_middle/src/infer/canonical.rs @@ -0,0 +1,363 @@ +//! **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::MemberConstraint; +use crate::ty::subst::GenericArg; +use crate::ty::{self, BoundVar, List, Region, Ty, TyCtxt}; +use rustc_index::vec::IndexVec; +use rustc_macros::HashStable; +use smallvec::SmallVec; +use std::iter; +use std::ops::Index; + +/// A "canonicalized" type `V` is one where all free inference +/// variables have been rewritten to "canonical vars". These are +/// numbered starting from 0 in order of first appearance. +#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TyDecodable, TyEncodable)] +#[derive(HashStable, TypeFoldable, TypeVisitable, Lift)] +pub struct Canonical<'tcx, V> { + pub max_universe: ty::UniverseIndex, + pub variables: CanonicalVarInfos<'tcx>, + pub value: V, +} + +pub type CanonicalVarInfos<'tcx> = &'tcx List<CanonicalVarInfo<'tcx>>; + +/// A set of values corresponding to the canonical variables from some +/// `Canonical`. You can give these values to +/// `canonical_value.substitute` to substitute them into the canonical +/// value at the right places. +/// +/// When you canonicalize a value `V`, you get back one of these +/// vectors with the original values that were replaced by canonical +/// variables. You will need to supply it later to instantiate the +/// canonicalized query response. +#[derive(Clone, Debug, PartialEq, Eq, Hash, TyDecodable, TyEncodable)] +#[derive(HashStable, TypeFoldable, TypeVisitable, Lift)] +pub struct CanonicalVarValues<'tcx> { + pub var_values: IndexVec<BoundVar, GenericArg<'tcx>>, +} + +/// When we canonicalize a value to form a query, we wind up replacing +/// various parts of it with canonical variables. This struct stores +/// those replaced bits to remember for when we process the query +/// result. +#[derive(Clone, Debug)] +pub struct OriginalQueryValues<'tcx> { + /// Map from the universes that appear in the query to the universes in the + /// caller context. For all queries except `evaluate_goal` (used by Chalk), + /// we only ever put ROOT values into the query, so this map is very + /// simple. + pub universe_map: SmallVec<[ty::UniverseIndex; 4]>, + + /// This is equivalent to `CanonicalVarValues`, but using a + /// `SmallVec` yields a significant performance win. + pub var_values: SmallVec<[GenericArg<'tcx>; 8]>, +} + +impl<'tcx> Default for OriginalQueryValues<'tcx> { + fn default() -> Self { + let mut universe_map = SmallVec::default(); + universe_map.push(ty::UniverseIndex::ROOT); + + Self { universe_map, var_values: SmallVec::default() } + } +} + +/// Information about a canonical variable that is included with the +/// canonical value. This is sufficient information for code to create +/// a copy of the canonical value in some other inference context, +/// with fresh inference variables replacing the canonical values. +#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TyDecodable, TyEncodable, HashStable)] +pub struct CanonicalVarInfo<'tcx> { + pub kind: CanonicalVarKind<'tcx>, +} + +impl<'tcx> CanonicalVarInfo<'tcx> { + pub fn universe(&self) -> ty::UniverseIndex { + self.kind.universe() + } + + pub fn is_existential(&self) -> bool { + match self.kind { + CanonicalVarKind::Ty(_) => true, + CanonicalVarKind::PlaceholderTy(_) => false, + CanonicalVarKind::Region(_) => true, + CanonicalVarKind::PlaceholderRegion(..) => false, + CanonicalVarKind::Const(..) => true, + CanonicalVarKind::PlaceholderConst(_, _) => false, + } + } +} + +/// Describes the "kind" of the canonical variable. This is a "kind" +/// in the type-theory sense of the term -- i.e., a "meta" type system +/// that analyzes type-like values. +#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TyDecodable, TyEncodable, HashStable)] +pub enum CanonicalVarKind<'tcx> { + /// Some kind of type inference variable. + Ty(CanonicalTyVarKind), + + /// A "placeholder" that represents "any type". + PlaceholderTy(ty::PlaceholderType), + + /// Region variable `'?R`. + Region(ty::UniverseIndex), + + /// A "placeholder" that represents "any region". Created when you + /// are solving a goal like `for<'a> T: Foo<'a>` to represent the + /// bound region `'a`. + PlaceholderRegion(ty::PlaceholderRegion), + + /// Some kind of const inference variable. + Const(ty::UniverseIndex, Ty<'tcx>), + + /// A "placeholder" that represents "any const". + PlaceholderConst(ty::PlaceholderConst<'tcx>, Ty<'tcx>), +} + +impl<'tcx> CanonicalVarKind<'tcx> { + pub fn universe(self) -> ty::UniverseIndex { + match self { + CanonicalVarKind::Ty(kind) => match kind { + CanonicalTyVarKind::General(ui) => ui, + CanonicalTyVarKind::Float | CanonicalTyVarKind::Int => ty::UniverseIndex::ROOT, + }, + + CanonicalVarKind::PlaceholderTy(placeholder) => placeholder.universe, + CanonicalVarKind::Region(ui) => ui, + CanonicalVarKind::PlaceholderRegion(placeholder) => placeholder.universe, + CanonicalVarKind::Const(ui, _) => ui, + CanonicalVarKind::PlaceholderConst(placeholder, _) => placeholder.universe, + } + } +} + +/// Rust actually has more than one category of type variables; +/// notably, the type variables we create for literals (e.g., 22 or +/// 22.) can only be instantiated with integral/float types (e.g., +/// usize or f32). In order to faithfully reproduce a type, we need to +/// know what set of types a given type variable can be unified with. +#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TyDecodable, TyEncodable, HashStable)] +pub enum CanonicalTyVarKind { + /// General type variable `?T` that can be unified with arbitrary types. + General(ty::UniverseIndex), + + /// Integral type variable `?I` (that can only be unified with integral types). + Int, + + /// Floating-point type variable `?F` (that can only be unified with float types). + Float, +} + +/// After we execute a query with a canonicalized key, we get back a +/// `Canonical<QueryResponse<..>>`. You can use +/// `instantiate_query_result` to access the data in this result. +#[derive(Clone, Debug, HashStable, TypeFoldable, TypeVisitable, Lift)] +pub struct QueryResponse<'tcx, R> { + pub var_values: CanonicalVarValues<'tcx>, + pub region_constraints: QueryRegionConstraints<'tcx>, + pub certainty: Certainty, + /// List of opaque types which we tried to compare to another type. + /// Inside the query we don't know yet whether the opaque type actually + /// should get its hidden type inferred. So we bubble the opaque type + /// and the type it was compared against upwards and let the query caller + /// handle it. + pub opaque_types: Vec<(Ty<'tcx>, Ty<'tcx>)>, + pub value: R, +} + +#[derive(Clone, Debug, Default, HashStable, TypeFoldable, TypeVisitable, Lift)] +pub struct QueryRegionConstraints<'tcx> { + pub outlives: Vec<QueryOutlivesConstraint<'tcx>>, + pub member_constraints: Vec<MemberConstraint<'tcx>>, +} + +impl QueryRegionConstraints<'_> { + /// Represents an empty (trivially true) set of region + /// constraints. + pub fn is_empty(&self) -> bool { + self.outlives.is_empty() && self.member_constraints.is_empty() + } +} + +pub type Canonicalized<'tcx, V> = Canonical<'tcx, V>; + +pub type CanonicalizedQueryResponse<'tcx, T> = &'tcx Canonical<'tcx, QueryResponse<'tcx, T>>; + +/// Indicates whether or not we were able to prove the query to be +/// true. +#[derive(Copy, Clone, Debug, HashStable)] +pub enum Certainty { + /// The query is known to be true, presuming that you apply the + /// given `var_values` and the region-constraints are satisfied. + Proven, + + /// The query is not known to be true, but also not known to be + /// false. The `var_values` represent *either* values that must + /// hold in order for the query to be true, or helpful tips that + /// *might* make it true. Currently rustc's trait solver cannot + /// distinguish the two (e.g., due to our preference for where + /// clauses over impls). + /// + /// After some unification and things have been done, it makes + /// sense to try and prove again -- of course, at that point, the + /// canonical form will be different, making this a distinct + /// query. + Ambiguous, +} + +impl Certainty { + pub fn is_proven(&self) -> bool { + match self { + Certainty::Proven => true, + Certainty::Ambiguous => false, + } + } +} + +impl<'tcx, R> QueryResponse<'tcx, R> { + pub fn is_proven(&self) -> bool { + self.certainty.is_proven() + } +} + +impl<'tcx, R> Canonical<'tcx, QueryResponse<'tcx, R>> { + pub fn is_proven(&self) -> bool { + self.value.is_proven() + } + + pub fn is_ambiguous(&self) -> bool { + !self.is_proven() + } +} + +impl<'tcx, R> Canonical<'tcx, ty::ParamEnvAnd<'tcx, R>> { + #[inline] + pub fn without_const(mut self) -> Self { + self.value = self.value.without_const(); + self + } +} + +impl<'tcx, V> Canonical<'tcx, V> { + /// Allows you to map the `value` of a canonical while keeping the + /// same set of bound variables. + /// + /// **WARNING:** This function is very easy to mis-use, hence the + /// name! In particular, the new value `W` must use all **the + /// same type/region variables** in **precisely the same order** + /// as the original! (The ordering is defined by the + /// `TypeFoldable` implementation of the type in question.) + /// + /// An example of a **correct** use of this: + /// + /// ```rust,ignore (not real code) + /// let a: Canonical<'_, T> = ...; + /// let b: Canonical<'_, (T,)> = a.unchecked_map(|v| (v, )); + /// ``` + /// + /// An example of an **incorrect** use of this: + /// + /// ```rust,ignore (not real code) + /// let a: Canonical<'tcx, T> = ...; + /// let ty: Ty<'tcx> = ...; + /// let b: Canonical<'tcx, (T, Ty<'tcx>)> = a.unchecked_map(|v| (v, ty)); + /// ``` + pub fn unchecked_map<W>(self, map_op: impl FnOnce(V) -> W) -> Canonical<'tcx, W> { + let Canonical { max_universe, variables, value } = self; + Canonical { max_universe, variables, value: map_op(value) } + } +} + +pub type QueryOutlivesConstraint<'tcx> = + ty::Binder<'tcx, ty::OutlivesPredicate<GenericArg<'tcx>, Region<'tcx>>>; + +TrivialTypeTraversalAndLiftImpls! { + for <'tcx> { + crate::infer::canonical::Certainty, + crate::infer::canonical::CanonicalVarInfo<'tcx>, + crate::infer::canonical::CanonicalVarKind<'tcx>, + } +} + +TrivialTypeTraversalImpls! { + for <'tcx> { + crate::infer::canonical::CanonicalVarInfos<'tcx>, + } +} + +impl<'tcx> CanonicalVarValues<'tcx> { + #[inline] + pub fn len(&self) -> usize { + self.var_values.len() + } + + /// Makes an identity substitution from this one: each bound var + /// is matched to the same bound var, preserving the original kinds. + /// For example, if we have: + /// `self.var_values == [Type(u32), Lifetime('a), Type(u64)]` + /// we'll return a substitution `subst` with: + /// `subst.var_values == [Type(^0), Lifetime(^1), Type(^2)]`. + pub fn make_identity(&self, tcx: TyCtxt<'tcx>) -> Self { + use crate::ty::subst::GenericArgKind; + + CanonicalVarValues { + var_values: iter::zip(&self.var_values, 0..) + .map(|(kind, i)| match kind.unpack() { + GenericArgKind::Type(..) => { + tcx.mk_ty(ty::Bound(ty::INNERMOST, ty::BoundVar::from_u32(i).into())).into() + } + GenericArgKind::Lifetime(..) => { + let br = + ty::BoundRegion { var: ty::BoundVar::from_u32(i), kind: ty::BrAnon(i) }; + tcx.mk_region(ty::ReLateBound(ty::INNERMOST, br)).into() + } + GenericArgKind::Const(ct) => tcx + .mk_const(ty::ConstS { + ty: ct.ty(), + kind: ty::ConstKind::Bound(ty::INNERMOST, ty::BoundVar::from_u32(i)), + }) + .into(), + }) + .collect(), + } + } +} + +impl<'a, 'tcx> IntoIterator for &'a CanonicalVarValues<'tcx> { + type Item = GenericArg<'tcx>; + type IntoIter = ::std::iter::Cloned<::std::slice::Iter<'a, GenericArg<'tcx>>>; + + fn into_iter(self) -> Self::IntoIter { + self.var_values.iter().cloned() + } +} + +impl<'tcx> Index<BoundVar> for CanonicalVarValues<'tcx> { + type Output = GenericArg<'tcx>; + + fn index(&self, value: BoundVar) -> &GenericArg<'tcx> { + &self.var_values[value] + } +} diff --git a/compiler/rustc_middle/src/infer/mod.rs b/compiler/rustc_middle/src/infer/mod.rs new file mode 100644 index 000000000..38868c210 --- /dev/null +++ b/compiler/rustc_middle/src/infer/mod.rs @@ -0,0 +1,32 @@ +pub mod canonical; +pub mod unify_key; + +use crate::ty::Region; +use crate::ty::{OpaqueTypeKey, Ty}; +use rustc_data_structures::sync::Lrc; +use rustc_span::Span; + +/// Requires that `region` must be equal to one of the regions in `choice_regions`. +/// We often denote this using the syntax: +/// +/// ```text +/// R0 member of [O1..On] +/// ``` +#[derive(Debug, Clone, HashStable, TypeFoldable, TypeVisitable, Lift)] +pub struct MemberConstraint<'tcx> { + /// The `DefId` and substs of the opaque type causing this constraint. + /// Used for error reporting. + pub key: OpaqueTypeKey<'tcx>, + + /// The span where the hidden type was instantiated. + pub definition_span: Span, + + /// The hidden type in which `member_region` appears: used for error reporting. + pub hidden_ty: Ty<'tcx>, + + /// The region `R0`. + pub member_region: Region<'tcx>, + + /// The options `O1..On`. + pub choice_regions: Lrc<Vec<Region<'tcx>>>, +} diff --git a/compiler/rustc_middle/src/infer/unify_key.rs b/compiler/rustc_middle/src/infer/unify_key.rs new file mode 100644 index 000000000..f2627885d --- /dev/null +++ b/compiler/rustc_middle/src/infer/unify_key.rs @@ -0,0 +1,162 @@ +use crate::ty::{self, Ty, TyCtxt}; +use rustc_data_structures::unify::{NoError, UnifyKey, UnifyValue}; +use rustc_span::def_id::DefId; +use rustc_span::symbol::Symbol; +use rustc_span::Span; +use std::cmp; +use std::marker::PhantomData; + +pub trait ToType { + fn to_type<'tcx>(&self, tcx: TyCtxt<'tcx>) -> Ty<'tcx>; +} + +#[derive(PartialEq, Copy, Clone, Debug)] +pub struct UnifiedRegion<'tcx>(pub Option<ty::Region<'tcx>>); + +#[derive(PartialEq, Copy, Clone, Debug)] +pub struct RegionVidKey<'tcx> { + pub vid: ty::RegionVid, + pub phantom: PhantomData<UnifiedRegion<'tcx>>, +} + +impl<'tcx> From<ty::RegionVid> for RegionVidKey<'tcx> { + fn from(vid: ty::RegionVid) -> Self { + RegionVidKey { vid, phantom: PhantomData } + } +} + +impl<'tcx> UnifyKey for RegionVidKey<'tcx> { + type Value = UnifiedRegion<'tcx>; + #[inline] + fn index(&self) -> u32 { + self.vid.as_u32() + } + #[inline] + fn from_index(i: u32) -> Self { + RegionVidKey::from(ty::RegionVid::from_u32(i)) + } + fn tag() -> &'static str { + "RegionVidKey" + } +} + +impl<'tcx> UnifyValue for UnifiedRegion<'tcx> { + type Error = NoError; + + fn unify_values(value1: &Self, value2: &Self) -> Result<Self, NoError> { + Ok(match (value1.0, value2.0) { + // Here we can just pick one value, because the full constraints graph + // will be handled later. Ideally, we might want a `MultipleValues` + // variant or something. For now though, this is fine. + (Some(_), Some(_)) => *value1, + + (Some(_), _) => *value1, + (_, Some(_)) => *value2, + + (None, None) => *value1, + }) + } +} + +impl ToType for ty::IntVarValue { + fn to_type<'tcx>(&self, tcx: TyCtxt<'tcx>) -> Ty<'tcx> { + match *self { + ty::IntType(i) => tcx.mk_mach_int(i), + ty::UintType(i) => tcx.mk_mach_uint(i), + } + } +} + +impl ToType for ty::FloatVarValue { + fn to_type<'tcx>(&self, tcx: TyCtxt<'tcx>) -> Ty<'tcx> { + tcx.mk_mach_float(self.0) + } +} + +// Generic consts. + +#[derive(Copy, Clone, Debug)] +pub struct ConstVariableOrigin { + pub kind: ConstVariableOriginKind, + pub span: Span, +} + +/// Reasons to create a const inference variable +#[derive(Copy, Clone, Debug)] +pub enum ConstVariableOriginKind { + MiscVariable, + ConstInference, + ConstParameterDefinition(Symbol, DefId), + SubstitutionPlaceholder, +} + +#[derive(Copy, Clone, Debug)] +pub enum ConstVariableValue<'tcx> { + Known { value: ty::Const<'tcx> }, + Unknown { universe: ty::UniverseIndex }, +} + +impl<'tcx> ConstVariableValue<'tcx> { + /// If this value is known, returns the const it is known to be. + /// Otherwise, `None`. + pub fn known(&self) -> Option<ty::Const<'tcx>> { + match *self { + ConstVariableValue::Unknown { .. } => None, + ConstVariableValue::Known { value } => Some(value), + } + } +} + +#[derive(Copy, Clone, Debug)] +pub struct ConstVarValue<'tcx> { + pub origin: ConstVariableOrigin, + pub val: ConstVariableValue<'tcx>, +} + +impl<'tcx> UnifyKey for ty::ConstVid<'tcx> { + type Value = ConstVarValue<'tcx>; + #[inline] + fn index(&self) -> u32 { + self.index + } + #[inline] + fn from_index(i: u32) -> Self { + ty::ConstVid { index: i, phantom: PhantomData } + } + fn tag() -> &'static str { + "ConstVid" + } +} + +impl<'tcx> UnifyValue for ConstVarValue<'tcx> { + type Error = (ty::Const<'tcx>, ty::Const<'tcx>); + + fn unify_values(&value1: &Self, &value2: &Self) -> Result<Self, Self::Error> { + Ok(match (value1.val, value2.val) { + (ConstVariableValue::Known { .. }, ConstVariableValue::Known { .. }) => { + bug!("equating two const variables, both of which have known values") + } + + // If one side is known, prefer that one. + (ConstVariableValue::Known { .. }, ConstVariableValue::Unknown { .. }) => value1, + (ConstVariableValue::Unknown { .. }, ConstVariableValue::Known { .. }) => value2, + + // If both sides are *unknown*, it hardly matters, does it? + ( + ConstVariableValue::Unknown { universe: universe1 }, + ConstVariableValue::Unknown { universe: universe2 }, + ) => { + // If we unify two unbound variables, ?T and ?U, then whatever + // value they wind up taking (which must be the same value) must + // be nameable by both universes. Therefore, the resulting + // universe is the minimum of the two universes, because that is + // the one which contains the fewest names in scope. + let universe = cmp::min(universe1, universe2); + ConstVarValue { + val: ConstVariableValue::Unknown { universe }, + origin: value1.origin, + } + } + }) + } +} |