compiler/rustc_middle/src/infer/canonical.rs

   1 //! **Canonicalization** is the key to constructing a query in the
   2 //! middle of type inference. Ordinarily, it is not possible to store
   3 //! types from type inference in query keys, because they contain
   4 //! references to inference variables whose lifetimes are too short
   5 //! and so forth. Canonicalizing a value T1 using `canonicalize_query`
   6 //! produces two things:
   7 //!
   8 //! - a value T2 where each unbound inference variable has been
   9 //!   replaced with a **canonical variable**;
  10 //! - a map M (of type `CanonicalVarValues`) from those canonical
  11 //!   variables back to the original.
  12 //!
  13 //! We can then do queries using T2. These will give back constraints
  14 //! on the canonical variables which can be translated, using the map
  15 //! M, into constraints in our source context. This process of
  16 //! translating the results back is done by the
  17 //! `instantiate_query_result` method.
  18 //!
  19 //! For a more detailed look at what is happening here, check
  20 //! out the [chapter in the rustc dev guide][c].
  21 //!
  22 //! [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html
  23
  24 use rustc_data_structures::fx::FxHashMap;
  25 use rustc_data_structures::sync::Lock;
  26 use rustc_macros::HashStable;
  27 use rustc_type_ir::Canonical as IrCanonical;
  28 use rustc_type_ir::CanonicalVarInfo as IrCanonicalVarInfo;
  29 pub use rustc_type_ir::{CanonicalTyVarKind, CanonicalVarKind};
  30 use smallvec::SmallVec;
  31 use std::collections::hash_map::Entry;
  32 use std::ops::Index;
  33
  34 use crate::infer::MemberConstraint;
  35 use crate::mir::ConstraintCategory;
  36 use crate::ty::GenericArg;
  37 use crate::ty::{self, BoundVar, List, Region, Ty, TyCtxt, TypeFlags, TypeVisitableExt};
  38
  39 pub type Canonical<'tcx, V> = IrCanonical<TyCtxt<'tcx>, V>;
  40
  41 pub type CanonicalVarInfo<'tcx> = IrCanonicalVarInfo<TyCtxt<'tcx>>;
  42
  43 pub type CanonicalVarInfos<'tcx> = &'tcx List<CanonicalVarInfo<'tcx>>;
  44
  45 impl<'tcx> ty::TypeFoldable<TyCtxt<'tcx>> for CanonicalVarInfos<'tcx> {
  46     fn try_fold_with<F: ty::FallibleTypeFolder<TyCtxt<'tcx>>>(
  47         self,
  48         folder: &mut F,
  49     ) -> Result<Self, F::Error> {
  50         ty::util::fold_list(self, folder, |tcx, v| tcx.mk_canonical_var_infos(v))
  51     }
  52 }
  53
  54 /// A set of values corresponding to the canonical variables from some
  55 /// `Canonical`. You can give these values to
  56 /// `canonical_value.substitute` to substitute them into the canonical
  57 /// value at the right places.
  58 ///
  59 /// When you canonicalize a value `V`, you get back one of these
  60 /// vectors with the original values that were replaced by canonical
  61 /// variables. You will need to supply it later to instantiate the
  62 /// canonicalized query response.
  63 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TyDecodable, TyEncodable)]
  64 #[derive(HashStable, TypeFoldable, TypeVisitable)]
  65 pub struct CanonicalVarValues<'tcx> {
  66     pub var_values: ty::GenericArgsRef<'tcx>,
  67 }
  68
  69 impl CanonicalVarValues<'_> {
  70     pub fn is_identity(&self) -> bool {
  71         self.var_values.iter().enumerate().all(|(bv, arg)| match arg.unpack() {
  72             ty::GenericArgKind::Lifetime(r) => {
  73                 matches!(*r, ty::ReBound(ty::INNERMOST, br) if br.var.as_usize() == bv)
  74             }
  75             ty::GenericArgKind::Type(ty) => {
  76                 matches!(*ty.kind(), ty::Bound(ty::INNERMOST, bt) if bt.var.as_usize() == bv)
  77             }
  78             ty::GenericArgKind::Const(ct) => {
  79                 matches!(ct.kind(), ty::ConstKind::Bound(ty::INNERMOST, bc) if bc.as_usize() == bv)
  80             }
  81         })
  82     }
  83
  84     pub fn is_identity_modulo_regions(&self) -> bool {
  85         let mut var = ty::BoundVar::from_u32(0);
  86         for arg in self.var_values {
  87             match arg.unpack() {
  88                 ty::GenericArgKind::Lifetime(r) => {
  89                     if let ty::ReBound(ty::INNERMOST, br) = *r
  90                         && var == br.var
  91                     {
  92                         var = var + 1;
  93                     } else {
  94                         // It's ok if this region var isn't unique
  95                     }
  96                 }
  97                 ty::GenericArgKind::Type(ty) => {
  98                     if let ty::Bound(ty::INNERMOST, bt) = *ty.kind()
  99                         && var == bt.var
 100                     {
 101                         var = var + 1;
 102                     } else {
 103                         return false;
 104                     }
 105                 }
 106                 ty::GenericArgKind::Const(ct) => {
 107                     if let ty::ConstKind::Bound(ty::INNERMOST, bc) = ct.kind()
 108                         && var == bc
 109                     {
 110                         var = var + 1;
 111                     } else {
 112                         return false;
 113                     }
 114                 }
 115             }
 116         }
 117
 118         true
 119     }
 120 }
 121
 122 /// When we canonicalize a value to form a query, we wind up replacing
 123 /// various parts of it with canonical variables. This struct stores
 124 /// those replaced bits to remember for when we process the query
 125 /// result.
 126 #[derive(Clone, Debug)]
 127 pub struct OriginalQueryValues<'tcx> {
 128     /// Map from the universes that appear in the query to the universes in the
 129     /// caller context. For all queries except `evaluate_goal` (used by Chalk),
 130     /// we only ever put ROOT values into the query, so this map is very
 131     /// simple.
 132     pub universe_map: SmallVec<[ty::UniverseIndex; 4]>,
 133
 134     /// This is equivalent to `CanonicalVarValues`, but using a
 135     /// `SmallVec` yields a significant performance win.
 136     pub var_values: SmallVec<[GenericArg<'tcx>; 8]>,
 137 }
 138
 139 impl<'tcx> Default for OriginalQueryValues<'tcx> {
 140     fn default() -> Self {
 141         let mut universe_map = SmallVec::default();
 142         universe_map.push(ty::UniverseIndex::ROOT);
 143
 144         Self { universe_map, var_values: SmallVec::default() }
 145     }
 146 }
 147
 148 /// After we execute a query with a canonicalized key, we get back a
 149 /// `Canonical<QueryResponse<..>>`. You can use
 150 /// `instantiate_query_result` to access the data in this result.
 151 #[derive(Clone, Debug, HashStable, TypeFoldable, TypeVisitable)]
 152 pub struct QueryResponse<'tcx, R> {
 153     pub var_values: CanonicalVarValues<'tcx>,
 154     pub region_constraints: QueryRegionConstraints<'tcx>,
 155     pub certainty: Certainty,
 156     /// List of opaque types which we tried to compare to another type.
 157     /// Inside the query we don't know yet whether the opaque type actually
 158     /// should get its hidden type inferred. So we bubble the opaque type
 159     /// and the type it was compared against upwards and let the query caller
 160     /// handle it.
 161     pub opaque_types: Vec<(ty::OpaqueTypeKey<'tcx>, Ty<'tcx>)>,
 162     pub value: R,
 163 }
 164
 165 #[derive(Clone, Debug, Default, PartialEq, Eq, Hash)]
 166 #[derive(HashStable, TypeFoldable, TypeVisitable)]
 167 pub struct QueryRegionConstraints<'tcx> {
 168     pub outlives: Vec<QueryOutlivesConstraint<'tcx>>,
 169     pub member_constraints: Vec<MemberConstraint<'tcx>>,
 170 }
 171
 172 impl QueryRegionConstraints<'_> {
 173     /// Represents an empty (trivially true) set of region
 174     /// constraints.
 175     pub fn is_empty(&self) -> bool {
 176         self.outlives.is_empty() && self.member_constraints.is_empty()
 177     }
 178 }
 179
 180 pub type CanonicalQueryResponse<'tcx, T> = &'tcx Canonical<'tcx, QueryResponse<'tcx, T>>;
 181
 182 /// Indicates whether or not we were able to prove the query to be
 183 /// true.
 184 #[derive(Copy, Clone, Debug, HashStable)]
 185 pub enum Certainty {
 186     /// The query is known to be true, presuming that you apply the
 187     /// given `var_values` and the region-constraints are satisfied.
 188     Proven,
 189
 190     /// The query is not known to be true, but also not known to be
 191     /// false. The `var_values` represent *either* values that must
 192     /// hold in order for the query to be true, or helpful tips that
 193     /// *might* make it true. Currently rustc's trait solver cannot
 194     /// distinguish the two (e.g., due to our preference for where
 195     /// clauses over impls).
 196     ///
 197     /// After some unification and things have been done, it makes
 198     /// sense to try and prove again -- of course, at that point, the
 199     /// canonical form will be different, making this a distinct
 200     /// query.
 201     Ambiguous,
 202 }
 203
 204 impl Certainty {
 205     pub fn is_proven(&self) -> bool {
 206         match self {
 207             Certainty::Proven => true,
 208             Certainty::Ambiguous => false,
 209         }
 210     }
 211 }
 212
 213 impl<'tcx, R> QueryResponse<'tcx, R> {
 214     pub fn is_proven(&self) -> bool {
 215         self.certainty.is_proven()
 216     }
 217 }
 218
 219 pub type QueryOutlivesConstraint<'tcx> =
 220     (ty::OutlivesPredicate<GenericArg<'tcx>, Region<'tcx>>, ConstraintCategory<'tcx>);
 221
 222 TrivialTypeTraversalImpls! {
 223     crate::infer::canonical::Certainty,
 224 }
 225
 226 impl<'tcx> CanonicalVarValues<'tcx> {
 227     // Given a list of canonical variables, construct a set of values which are
 228     // the identity response.
 229     pub fn make_identity(
 230         tcx: TyCtxt<'tcx>,
 231         infos: CanonicalVarInfos<'tcx>,
 232     ) -> CanonicalVarValues<'tcx> {
 233         CanonicalVarValues {
 234             var_values: tcx.mk_args_from_iter(infos.iter().enumerate().map(
 235                 |(i, info)| -> ty::GenericArg<'tcx> {
 236                     match info.kind {
 237                         CanonicalVarKind::Ty(_) | CanonicalVarKind::PlaceholderTy(_) => {
 238                             Ty::new_bound(tcx, ty::INNERMOST, ty::BoundVar::from_usize(i).into())
 239                                 .into()
 240                         }
 241                         CanonicalVarKind::Region(_) | CanonicalVarKind::PlaceholderRegion(_) => {
 242                             let br = ty::BoundRegion {
 243                                 var: ty::BoundVar::from_usize(i),
 244                                 kind: ty::BrAnon,
 245                             };
 246                             ty::Region::new_bound(tcx, ty::INNERMOST, br).into()
 247                         }
 248                         CanonicalVarKind::Effect => ty::Const::new_bound(
 249                             tcx,
 250                             ty::INNERMOST,
 251                             ty::BoundVar::from_usize(i),
 252                             tcx.types.bool,
 253                         )
 254                         .into(),
 255                         CanonicalVarKind::Const(_, ty)
 256                         | CanonicalVarKind::PlaceholderConst(_, ty) => ty::Const::new_bound(
 257                             tcx,
 258                             ty::INNERMOST,
 259                             ty::BoundVar::from_usize(i),
 260                             ty,
 261                         )
 262                         .into(),
 263                     }
 264                 },
 265             )),
 266         }
 267     }
 268
 269     /// Creates dummy var values which should not be used in a
 270     /// canonical response.
 271     pub fn dummy() -> CanonicalVarValues<'tcx> {
 272         CanonicalVarValues { var_values: ty::List::empty() }
 273     }
 274
 275     #[inline]
 276     pub fn len(&self) -> usize {
 277         self.var_values.len()
 278     }
 279 }
 280
 281 impl<'a, 'tcx> IntoIterator for &'a CanonicalVarValues<'tcx> {
 282     type Item = GenericArg<'tcx>;
 283     type IntoIter = ::std::iter::Copied<::std::slice::Iter<'a, GenericArg<'tcx>>>;
 284
 285     fn into_iter(self) -> Self::IntoIter {
 286         self.var_values.iter()
 287     }
 288 }
 289
 290 impl<'tcx> Index<BoundVar> for CanonicalVarValues<'tcx> {
 291     type Output = GenericArg<'tcx>;
 292
 293     fn index(&self, value: BoundVar) -> &GenericArg<'tcx> {
 294         &self.var_values[value.as_usize()]
 295     }
 296 }
 297
 298 #[derive(Default)]
 299 pub struct CanonicalParamEnvCache<'tcx> {
 300     map: Lock<
 301         FxHashMap<
 302             ty::ParamEnv<'tcx>,
 303             (Canonical<'tcx, ty::ParamEnv<'tcx>>, &'tcx [GenericArg<'tcx>]),
 304         >,
 305     >,
 306 }
 307
 308 impl<'tcx> CanonicalParamEnvCache<'tcx> {
 309     /// Gets the cached canonical form of `key` or executes
 310     /// `canonicalize_op` and caches the result if not present.
 311     ///
 312     /// `canonicalize_op` is intentionally not allowed to be a closure to
 313     /// statically prevent it from capturing `InferCtxt` and resolving
 314     /// inference variables, which invalidates the cache.
 315     pub fn get_or_insert(
 316         &self,
 317         tcx: TyCtxt<'tcx>,
 318         key: ty::ParamEnv<'tcx>,
 319         state: &mut OriginalQueryValues<'tcx>,
 320         canonicalize_op: fn(
 321             TyCtxt<'tcx>,
 322             ty::ParamEnv<'tcx>,
 323             &mut OriginalQueryValues<'tcx>,
 324         ) -> Canonical<'tcx, ty::ParamEnv<'tcx>>,
 325     ) -> Canonical<'tcx, ty::ParamEnv<'tcx>> {
 326         if !key.has_type_flags(
 327             TypeFlags::HAS_INFER | TypeFlags::HAS_PLACEHOLDER | TypeFlags::HAS_FREE_REGIONS,
 328         ) {
 329             return Canonical {
 330                 max_universe: ty::UniverseIndex::ROOT,
 331                 variables: List::empty(),
 332                 value: key,
 333             };
 334         }
 335
 336         assert_eq!(state.var_values.len(), 0);
 337         assert_eq!(state.universe_map.len(), 1);
 338         debug_assert_eq!(&*state.universe_map, &[ty::UniverseIndex::ROOT]);
 339
 340         match self.map.borrow().entry(key) {
 341             Entry::Occupied(e) => {
 342                 let (canonical, var_values) = e.get();
 343                 state.var_values.extend_from_slice(var_values);
 344                 *canonical
 345             }
 346             Entry::Vacant(e) => {
 347                 let canonical = canonicalize_op(tcx, key, state);
 348                 let OriginalQueryValues { var_values, universe_map } = state;
 349                 assert_eq!(universe_map.len(), 1);
 350                 e.insert((canonical, tcx.arena.alloc_slice(var_values)));
 351                 canonical
 352             }
 353         }
 354     }
 355 }