src/librustc/infer/canonical/canonicalizer.rs

   1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! This module contains the "canonicalizer" itself.
  12 //!
  13 //! For an overview of what canonicaliation is and how it fits into
  14 //! rustc, check out the [chapter in the rustc guide][c].
  15 //!
  16 //! [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html
  17
  18 use infer::canonical::{
  19     Canonical, CanonicalTyVarKind, CanonicalVarInfo, CanonicalVarKind, CanonicalVarValues,
  20     Canonicalized,
  21 };
  22 use infer::InferCtxt;
  23 use std::sync::atomic::Ordering;
  24 use ty::fold::{TypeFoldable, TypeFolder};
  25 use ty::subst::Kind;
  26 use ty::{self, CanonicalVar, Lift, Slice, Ty, TyCtxt, TypeFlags};
  27
  28 use rustc_data_structures::fx::FxHashMap;
  29 use rustc_data_structures::indexed_vec::IndexVec;
  30
  31 impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
  32     /// Canonicalizes a query value `V`. When we canonicalize a query,
  33     /// we not only canonicalize unbound inference variables, but we
  34     /// *also* replace all free regions whatsoever. So for example a
  35     /// query like `T: Trait<'static>` would be canonicalized to
  36     ///
  37     /// ```text
  38     /// T: Trait<'?0>
  39     /// ```
  40     ///
  41     /// with a mapping M that maps `'?0` to `'static`.
  42     ///
  43     /// To get a good understanding of what is happening here, check
  44     /// out the [chapter in the rustc guide][c].
  45     ///
  46     /// [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html#canonicalizing-the-query
  47     pub fn canonicalize_query<V>(
  48         &self,
  49         value: &V,
  50     ) -> (Canonicalized<'gcx, V>, CanonicalVarValues<'tcx>)
  51     where
  52         V: TypeFoldable<'tcx> + Lift<'gcx>,
  53     {
  54         self.tcx
  55             .sess
  56             .perf_stats
  57             .queries_canonicalized
  58             .fetch_add(1, Ordering::Relaxed);
  59
  60         Canonicalizer::canonicalize(
  61             value,
  62             Some(self),
  63             self.tcx,
  64             CanonicalizeRegionMode {
  65                 static_region: true,
  66                 other_free_regions: true,
  67             },
  68         )
  69     }
  70
  71     /// Canonicalizes a query *response* `V`. When we canonicalize a
  72     /// query response, we only canonicalize unbound inference
  73     /// variables, and we leave other free regions alone. So,
  74     /// continuing with the example from `canonicalize_query`, if
  75     /// there was an input query `T: Trait<'static>`, it would have
  76     /// been canonicalized to
  77     ///
  78     /// ```text
  79     /// T: Trait<'?0>
  80     /// ```
  81     ///
  82     /// with a mapping M that maps `'?0` to `'static`. But if we found that there
  83     /// exists only one possible impl of `Trait`, and it looks like
  84     ///
  85     ///     impl<T> Trait<'static> for T { .. }
  86     ///
  87     /// then we would prepare a query result R that (among other
  88     /// things) includes a mapping to `'?0 := 'static`. When
  89     /// canonicalizing this query result R, we would leave this
  90     /// reference to `'static` alone.
  91     ///
  92     /// To get a good understanding of what is happening here, check
  93     /// out the [chapter in the rustc guide][c].
  94     ///
  95     /// [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html#canonicalizing-the-query-result
  96     pub fn canonicalize_response<V>(
  97         &self,
  98         value: &V,
  99     ) -> (Canonicalized<'gcx, V>, CanonicalVarValues<'tcx>)
 100     where
 101         V: TypeFoldable<'tcx> + Lift<'gcx>,
 102     {
 103         Canonicalizer::canonicalize(
 104             value,
 105             Some(self),
 106             self.tcx,
 107             CanonicalizeRegionMode {
 108                 static_region: false,
 109                 other_free_regions: false,
 110             },
 111         )
 112     }
 113
 114     /// A hacky variant of `canonicalize_query` that does not
 115     /// canonicalize `'static`.  Unfortunately, the existing leak
 116     /// check treaks `'static` differently in some cases (see also
 117     /// #33684), so if we are performing an operation that may need to
 118     /// prove "leak-check" related things, we leave `'static`
 119     /// alone.
 120     ///
 121     /// FIXME(#48536) -- once we have universes, we can remove this and just use
 122     /// `canonicalize_query`.
 123     pub fn canonicalize_hr_query_hack<V>(
 124         &self,
 125         value: &V,
 126     ) -> (Canonicalized<'gcx, V>, CanonicalVarValues<'tcx>)
 127     where
 128         V: TypeFoldable<'tcx> + Lift<'gcx>,
 129     {
 130         self.tcx
 131             .sess
 132             .perf_stats
 133             .queries_canonicalized
 134             .fetch_add(1, Ordering::Relaxed);
 135
 136         Canonicalizer::canonicalize(
 137             value,
 138             Some(self),
 139             self.tcx,
 140             CanonicalizeRegionMode {
 141                 static_region: false,
 142                 other_free_regions: true,
 143             },
 144         )
 145     }
 146 }
 147
 148 /// If this flag is true, then all free regions will be replaced with
 149 /// a canonical var. This is used to make queries as generic as
 150 /// possible. For example, the query `F: Foo<'static>` would be
 151 /// canonicalized to `F: Foo<'0>`.
 152 struct CanonicalizeRegionMode {
 153     static_region: bool,
 154     other_free_regions: bool,
 155 }
 156
 157 impl CanonicalizeRegionMode {
 158     fn any(&self) -> bool {
 159         self.static_region || self.other_free_regions
 160     }
 161 }
 162
 163 struct Canonicalizer<'cx, 'gcx: 'tcx, 'tcx: 'cx> {
 164     infcx: Option<&'cx InferCtxt<'cx, 'gcx, 'tcx>>,
 165     tcx: TyCtxt<'cx, 'gcx, 'tcx>,
 166     variables: IndexVec<CanonicalVar, CanonicalVarInfo>,
 167     indices: FxHashMap<Kind<'tcx>, CanonicalVar>,
 168     var_values: IndexVec<CanonicalVar, Kind<'tcx>>,
 169     canonicalize_region_mode: CanonicalizeRegionMode,
 170     needs_canonical_flags: TypeFlags,
 171 }
 172
 173 impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for Canonicalizer<'cx, 'gcx, 'tcx> {
 174     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> {
 175         self.tcx
 176     }
 177
 178     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 179         match *r {
 180             ty::ReLateBound(..) => {
 181                 // leave bound regions alone
 182                 r
 183             }
 184
 185             ty::ReVar(vid) => {
 186                 let r = self
 187                     .infcx
 188                     .unwrap()
 189                     .borrow_region_constraints()
 190                     .opportunistic_resolve_var(self.tcx, vid);
 191                 let info = CanonicalVarInfo {
 192                     kind: CanonicalVarKind::Region,
 193                 };
 194                 debug!(
 195                     "canonical: region var found with vid {:?}, \
 196                      opportunistically resolved to {:?}",
 197                     vid, r
 198                 );
 199                 let cvar = self.canonical_var(info, r.into());
 200                 self.tcx().mk_region(ty::ReCanonical(cvar))
 201             }
 202
 203             ty::ReStatic => {
 204                 if self.canonicalize_region_mode.static_region {
 205                     let info = CanonicalVarInfo {
 206                         kind: CanonicalVarKind::Region,
 207                     };
 208                     let cvar = self.canonical_var(info, r.into());
 209                     self.tcx().mk_region(ty::ReCanonical(cvar))
 210                 } else {
 211                     r
 212                 }
 213             }
 214
 215             ty::ReEarlyBound(..)
 216             | ty::ReFree(_)
 217             | ty::ReScope(_)
 218             | ty::ReSkolemized(..)
 219             | ty::ReEmpty
 220             | ty::ReErased => {
 221                 if self.canonicalize_region_mode.other_free_regions {
 222                     let info = CanonicalVarInfo {
 223                         kind: CanonicalVarKind::Region,
 224                     };
 225                     let cvar = self.canonical_var(info, r.into());
 226                     self.tcx().mk_region(ty::ReCanonical(cvar))
 227                 } else {
 228                     r
 229                 }
 230             }
 231
 232             ty::ReClosureBound(..) | ty::ReCanonical(_) => {
 233                 bug!("canonical region encountered during canonicalization")
 234             }
 235         }
 236     }
 237
 238     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 239         match t.sty {
 240             ty::TyInfer(ty::TyVar(_)) => self.canonicalize_ty_var(CanonicalTyVarKind::General, t),
 241
 242             ty::TyInfer(ty::IntVar(_)) => self.canonicalize_ty_var(CanonicalTyVarKind::Int, t),
 243
 244             ty::TyInfer(ty::FloatVar(_)) => self.canonicalize_ty_var(CanonicalTyVarKind::Float, t),
 245
 246             ty::TyInfer(ty::FreshTy(_))
 247             | ty::TyInfer(ty::FreshIntTy(_))
 248             | ty::TyInfer(ty::FreshFloatTy(_)) => {
 249                 bug!("encountered a fresh type during canonicalization")
 250             }
 251
 252             ty::TyInfer(ty::CanonicalTy(_)) => {
 253                 bug!("encountered a canonical type during canonicalization")
 254             }
 255
 256             ty::TyClosure(..)
 257             | ty::TyGenerator(..)
 258             | ty::TyGeneratorWitness(..)
 259             | ty::TyBool
 260             | ty::TyChar
 261             | ty::TyInt(..)
 262             | ty::TyUint(..)
 263             | ty::TyFloat(..)
 264             | ty::TyAdt(..)
 265             | ty::TyStr
 266             | ty::TyError
 267             | ty::TyArray(..)
 268             | ty::TySlice(..)
 269             | ty::TyRawPtr(..)
 270             | ty::TyRef(..)
 271             | ty::TyFnDef(..)
 272             | ty::TyFnPtr(_)
 273             | ty::TyDynamic(..)
 274             | ty::TyNever
 275             | ty::TyTuple(..)
 276             | ty::TyProjection(..)
 277             | ty::TyForeign(..)
 278             | ty::TyParam(..)
 279             | ty::TyAnon(..) => {
 280                 if t.flags.intersects(self.needs_canonical_flags) {
 281                     t.super_fold_with(self)
 282                 } else {
 283                     t
 284                 }
 285             }
 286         }
 287     }
 288 }
 289
 290 impl<'cx, 'gcx, 'tcx> Canonicalizer<'cx, 'gcx, 'tcx> {
 291     /// The main `canonicalize` method, shared impl of
 292     /// `canonicalize_query` and `canonicalize_response`.
 293     fn canonicalize<V>(
 294         value: &V,
 295         infcx: Option<&'cx InferCtxt<'cx, 'gcx, 'tcx>>,
 296         tcx: TyCtxt<'cx, 'gcx, 'tcx>,
 297         canonicalize_region_mode: CanonicalizeRegionMode,
 298     ) -> (Canonicalized<'gcx, V>, CanonicalVarValues<'tcx>)
 299     where
 300         V: TypeFoldable<'tcx> + Lift<'gcx>,
 301     {
 302         debug_assert!(
 303             !value.has_type_flags(TypeFlags::HAS_CANONICAL_VARS),
 304             "canonicalizing a canonical value: {:?}",
 305             value,
 306         );
 307
 308         let needs_canonical_flags = if canonicalize_region_mode.any() {
 309             TypeFlags::HAS_FREE_REGIONS | TypeFlags::KEEP_IN_LOCAL_TCX
 310         } else {
 311             TypeFlags::KEEP_IN_LOCAL_TCX
 312         };
 313
 314         let gcx = tcx.global_tcx();
 315
 316         // Fast path: nothing that needs to be canonicalized.
 317         if !value.has_type_flags(needs_canonical_flags) {
 318             let out_value = gcx.lift(value).unwrap();
 319             let canon_value = Canonical {
 320                 variables: Slice::empty(),
 321                 value: out_value,
 322             };
 323             let values = CanonicalVarValues {
 324                 var_values: IndexVec::default(),
 325             };
 326             return (canon_value, values);
 327         }
 328
 329         let mut canonicalizer = Canonicalizer {
 330             infcx,
 331             tcx,
 332             canonicalize_region_mode,
 333             needs_canonical_flags,
 334             variables: IndexVec::default(),
 335             indices: FxHashMap::default(),
 336             var_values: IndexVec::default(),
 337         };
 338         let out_value = value.fold_with(&mut canonicalizer);
 339
 340         // Once we have canonicalized `out_value`, it should not
 341         // contain anything that ties it to this inference context
 342         // anymore, so it should live in the global arena.
 343         let out_value = gcx.lift(&out_value).unwrap_or_else(|| {
 344             bug!(
 345                 "failed to lift `{:?}`, canonicalized from `{:?}`",
 346                 out_value,
 347                 value
 348             )
 349         });
 350
 351         let canonical_variables = tcx.intern_canonical_var_infos(&canonicalizer.variables.raw);
 352
 353         let canonical_value = Canonical {
 354             variables: canonical_variables,
 355             value: out_value,
 356         };
 357         let canonical_var_values = CanonicalVarValues {
 358             var_values: canonicalizer.var_values,
 359         };
 360         (canonical_value, canonical_var_values)
 361     }
 362
 363     /// Creates a canonical variable replacing `kind` from the input,
 364     /// or returns an existing variable if `kind` has already been
 365     /// seen. `kind` is expected to be an unbound variable (or
 366     /// potentially a free region).
 367     fn canonical_var(&mut self, info: CanonicalVarInfo, kind: Kind<'tcx>) -> CanonicalVar {
 368         let Canonicalizer {
 369             indices,
 370             variables,
 371             var_values,
 372             ..
 373         } = self;
 374
 375         indices
 376             .entry(kind)
 377             .or_insert_with(|| {
 378                 let cvar1 = variables.push(info);
 379                 let cvar2 = var_values.push(kind);
 380                 assert_eq!(cvar1, cvar2);
 381                 cvar1
 382             })
 383             .clone()
 384     }
 385
 386     /// Given a type variable `ty_var` of the given kind, first check
 387     /// if `ty_var` is bound to anything; if so, canonicalize
 388     /// *that*. Otherwise, create a new canonical variable for
 389     /// `ty_var`.
 390     fn canonicalize_ty_var(&mut self, ty_kind: CanonicalTyVarKind, ty_var: Ty<'tcx>) -> Ty<'tcx> {
 391         let infcx = self.infcx.expect("encountered ty-var without infcx");
 392         let bound_to = infcx.shallow_resolve(ty_var);
 393         if bound_to != ty_var {
 394             self.fold_ty(bound_to)
 395         } else {
 396             let info = CanonicalVarInfo {
 397                 kind: CanonicalVarKind::Ty(ty_kind),
 398             };
 399             let cvar = self.canonical_var(info, ty_var.into());
 400             self.tcx().mk_infer(ty::InferTy::CanonicalTy(cvar))
 401         }
 402     }
 403 }