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, Canonicalized,
  20     OriginalQueryValues,
  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, BoundTy, BoundTyIndex, Lift, List, Ty, TyCtxt, TypeFlags};
  27
  28 use rustc_data_structures::fx::FxHashMap;
  29 use rustc_data_structures::indexed_vec::Idx;
  30 use smallvec::SmallVec;
  31
  32 impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
  33     /// Canonicalizes a query value `V`. When we canonicalize a query,
  34     /// we not only canonicalize unbound inference variables, but we
  35     /// *also* replace all free regions whatsoever. So for example a
  36     /// query like `T: Trait<'static>` would be canonicalized to
  37     ///
  38     /// ```text
  39     /// T: Trait<'?0>
  40     /// ```
  41     ///
  42     /// with a mapping M that maps `'?0` to `'static`.
  43     ///
  44     /// To get a good understanding of what is happening here, check
  45     /// out the [chapter in the rustc guide][c].
  46     ///
  47     /// [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html#canonicalizing-the-query
  48     pub fn canonicalize_query<V>(
  49         &self,
  50         value: &V,
  51         query_state: &mut OriginalQueryValues<'tcx>,
  52     ) -> Canonicalized<'gcx, V>
  53     where
  54         V: TypeFoldable<'tcx> + Lift<'gcx>,
  55     {
  56         self.tcx
  57             .sess
  58             .perf_stats
  59             .queries_canonicalized
  60             .fetch_add(1, Ordering::Relaxed);
  61
  62         Canonicalizer::canonicalize(
  63             value,
  64             Some(self),
  65             self.tcx,
  66             &CanonicalizeAllFreeRegions,
  67             query_state,
  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>(&self, value: &V) -> Canonicalized<'gcx, V>
  97     where
  98         V: TypeFoldable<'tcx> + Lift<'gcx>,
  99     {
 100         let mut query_state = OriginalQueryValues::default();
 101         Canonicalizer::canonicalize(
 102             value,
 103             Some(self),
 104             self.tcx,
 105             &CanonicalizeQueryResponse,
 106             &mut query_state,
 107         )
 108     }
 109
 110     pub fn canonicalize_user_type_annotation<V>(&self, value: &V) -> Canonicalized<'gcx, V>
 111     where
 112         V: TypeFoldable<'tcx> + Lift<'gcx>,
 113     {
 114         let mut query_state = OriginalQueryValues::default();
 115         Canonicalizer::canonicalize(
 116             value,
 117             Some(self),
 118             self.tcx,
 119             &CanonicalizeUserTypeAnnotation,
 120             &mut query_state,
 121         )
 122     }
 123
 124     /// A hacky variant of `canonicalize_query` that does not
 125     /// canonicalize `'static`.  Unfortunately, the existing leak
 126     /// check treaks `'static` differently in some cases (see also
 127     /// #33684), so if we are performing an operation that may need to
 128     /// prove "leak-check" related things, we leave `'static`
 129     /// alone.
 130     ///
 131     /// FIXME(#48536) -- once we have universes, we can remove this and just use
 132     /// `canonicalize_query`.
 133     pub fn canonicalize_hr_query_hack<V>(
 134         &self,
 135         value: &V,
 136         query_state: &mut OriginalQueryValues<'tcx>,
 137     ) -> Canonicalized<'gcx, V>
 138     where
 139         V: TypeFoldable<'tcx> + Lift<'gcx>,
 140     {
 141         self.tcx
 142             .sess
 143             .perf_stats
 144             .queries_canonicalized
 145             .fetch_add(1, Ordering::Relaxed);
 146
 147         Canonicalizer::canonicalize(
 148             value,
 149             Some(self),
 150             self.tcx,
 151             &CanonicalizeFreeRegionsOtherThanStatic,
 152             query_state,
 153         )
 154     }
 155 }
 156
 157 /// Controls how we canonicalize "free regions" that are not inference
 158 /// variables. This depends on what we are canonicalizing *for* --
 159 /// e.g., if we are canonicalizing to create a query, we want to
 160 /// replace those with inference variables, since we want to make a
 161 /// maximally general query. But if we are canonicalizing a *query
 162 /// response*, then we don't typically replace free regions, as they
 163 /// must have been introduced from other parts of the system.
 164 trait CanonicalizeRegionMode {
 165     fn canonicalize_free_region(
 166         &self,
 167         canonicalizer: &mut Canonicalizer<'_, '_, 'tcx>,
 168         r: ty::Region<'tcx>,
 169     ) -> ty::Region<'tcx>;
 170
 171     fn any(&self) -> bool;
 172 }
 173
 174 struct CanonicalizeQueryResponse;
 175
 176 impl CanonicalizeRegionMode for CanonicalizeQueryResponse {
 177     fn canonicalize_free_region(
 178         &self,
 179         canonicalizer: &mut Canonicalizer<'_, '_, 'tcx>,
 180         r: ty::Region<'tcx>,
 181     ) -> ty::Region<'tcx> {
 182         match r {
 183             ty::ReFree(_) | ty::ReEmpty | ty::ReErased | ty::ReStatic | ty::ReEarlyBound(..) => r,
 184             ty::RePlaceholder(placeholder) => canonicalizer.canonical_var_for_region(
 185                 CanonicalVarInfo {
 186                     kind: CanonicalVarKind::PlaceholderRegion(*placeholder),
 187                 },
 188                 r,
 189             ),
 190             ty::ReVar(vid) => {
 191                 let universe = canonicalizer.region_var_universe(*vid);
 192                 canonicalizer.canonical_var_for_region(
 193                     CanonicalVarInfo {
 194                         kind: CanonicalVarKind::Region(universe),
 195                     },
 196                     r,
 197                 )
 198             }
 199             _ => {
 200                 // Other than `'static` or `'empty`, the query
 201                 // response should be executing in a fully
 202                 // canonicalized environment, so there shouldn't be
 203                 // any other region names it can come up.
 204                 bug!("unexpected region in query response: `{:?}`", r)
 205             }
 206         }
 207     }
 208
 209     fn any(&self) -> bool {
 210         false
 211     }
 212 }
 213
 214 struct CanonicalizeUserTypeAnnotation;
 215
 216 impl CanonicalizeRegionMode for CanonicalizeUserTypeAnnotation {
 217     fn canonicalize_free_region(
 218         &self,
 219         canonicalizer: &mut Canonicalizer<'_, '_, 'tcx>,
 220         r: ty::Region<'tcx>,
 221     ) -> ty::Region<'tcx> {
 222         match r {
 223             ty::ReEarlyBound(_) | ty::ReFree(_) | ty::ReErased | ty::ReEmpty | ty::ReStatic => r,
 224             ty::ReVar(_) => canonicalizer.canonical_var_for_region_in_root_universe(r),
 225             _ => {
 226                 // We only expect region names that the user can type.
 227                 bug!("unexpected region in query response: `{:?}`", r)
 228             }
 229         }
 230     }
 231
 232     fn any(&self) -> bool {
 233         false
 234     }
 235 }
 236
 237 struct CanonicalizeAllFreeRegions;
 238
 239 impl CanonicalizeRegionMode for CanonicalizeAllFreeRegions {
 240     fn canonicalize_free_region(
 241         &self,
 242         canonicalizer: &mut Canonicalizer<'_, '_, 'tcx>,
 243         r: ty::Region<'tcx>,
 244     ) -> ty::Region<'tcx> {
 245         canonicalizer.canonical_var_for_region_in_root_universe(r)
 246     }
 247
 248     fn any(&self) -> bool {
 249         true
 250     }
 251 }
 252
 253 struct CanonicalizeFreeRegionsOtherThanStatic;
 254
 255 impl CanonicalizeRegionMode for CanonicalizeFreeRegionsOtherThanStatic {
 256     fn canonicalize_free_region(
 257         &self,
 258         canonicalizer: &mut Canonicalizer<'_, '_, 'tcx>,
 259         r: ty::Region<'tcx>,
 260     ) -> ty::Region<'tcx> {
 261         if let ty::ReStatic = r {
 262             r
 263         } else {
 264             canonicalizer.canonical_var_for_region_in_root_universe(r)
 265         }
 266     }
 267
 268     fn any(&self) -> bool {
 269         true
 270     }
 271 }
 272
 273 struct Canonicalizer<'cx, 'gcx: 'tcx, 'tcx: 'cx> {
 274     infcx: Option<&'cx InferCtxt<'cx, 'gcx, 'tcx>>,
 275     tcx: TyCtxt<'cx, 'gcx, 'tcx>,
 276     variables: SmallVec<[CanonicalVarInfo; 8]>,
 277     query_state: &'cx mut OriginalQueryValues<'tcx>,
 278     // Note that indices is only used once `var_values` is big enough to be
 279     // heap-allocated.
 280     indices: FxHashMap<Kind<'tcx>, BoundTyIndex>,
 281     canonicalize_region_mode: &'cx dyn CanonicalizeRegionMode,
 282     needs_canonical_flags: TypeFlags,
 283 }
 284
 285 impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for Canonicalizer<'cx, 'gcx, 'tcx> {
 286     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> {
 287         self.tcx
 288     }
 289
 290     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 291         match *r {
 292             ty::ReLateBound(..) => {
 293                 // leave bound regions alone
 294                 r
 295             }
 296
 297             ty::ReVar(vid) => {
 298                 let r = self.infcx
 299                     .unwrap()
 300                     .borrow_region_constraints()
 301                     .opportunistic_resolve_var(self.tcx, vid);
 302                 debug!(
 303                     "canonical: region var found with vid {:?}, \
 304                      opportunistically resolved to {:?}",
 305                     vid, r
 306                 );
 307                 self.canonicalize_region_mode
 308                     .canonicalize_free_region(self, r)
 309             }
 310
 311             ty::ReStatic
 312             | ty::ReEarlyBound(..)
 313             | ty::ReFree(_)
 314             | ty::ReScope(_)
 315             | ty::RePlaceholder(..)
 316             | ty::ReEmpty
 317             | ty::ReErased => self.canonicalize_region_mode
 318                 .canonicalize_free_region(self, r),
 319
 320             ty::ReClosureBound(..) | ty::ReCanonical(_) => {
 321                 bug!("canonical region encountered during canonicalization")
 322             }
 323         }
 324     }
 325
 326     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 327         match t.sty {
 328             ty::Infer(ty::TyVar(_)) => self.canonicalize_ty_var(CanonicalTyVarKind::General, t),
 329
 330             ty::Infer(ty::IntVar(_)) => self.canonicalize_ty_var(CanonicalTyVarKind::Int, t),
 331
 332             ty::Infer(ty::FloatVar(_)) => self.canonicalize_ty_var(CanonicalTyVarKind::Float, t),
 333
 334             ty::Infer(ty::FreshTy(_))
 335             | ty::Infer(ty::FreshIntTy(_))
 336             | ty::Infer(ty::FreshFloatTy(_)) => {
 337                 bug!("encountered a fresh type during canonicalization")
 338             }
 339
 340             ty::Bound(_) => {
 341                 bug!("encountered a bound type during canonicalization")
 342             }
 343
 344             ty::Closure(..)
 345             | ty::Generator(..)
 346             | ty::GeneratorWitness(..)
 347             | ty::Bool
 348             | ty::Char
 349             | ty::Int(..)
 350             | ty::Uint(..)
 351             | ty::Float(..)
 352             | ty::Adt(..)
 353             | ty::Str
 354             | ty::Error
 355             | ty::Array(..)
 356             | ty::Slice(..)
 357             | ty::RawPtr(..)
 358             | ty::Ref(..)
 359             | ty::FnDef(..)
 360             | ty::FnPtr(_)
 361             | ty::Dynamic(..)
 362             | ty::Never
 363             | ty::Tuple(..)
 364             | ty::Projection(..)
 365             | ty::UnnormalizedProjection(..)
 366             | ty::Foreign(..)
 367             | ty::Param(..)
 368             | ty::Opaque(..) => {
 369                 if t.flags.intersects(self.needs_canonical_flags) {
 370                     t.super_fold_with(self)
 371                 } else {
 372                     t
 373                 }
 374             }
 375         }
 376     }
 377 }
 378
 379 impl<'cx, 'gcx, 'tcx> Canonicalizer<'cx, 'gcx, 'tcx> {
 380     /// The main `canonicalize` method, shared impl of
 381     /// `canonicalize_query` and `canonicalize_response`.
 382     fn canonicalize<V>(
 383         value: &V,
 384         infcx: Option<&InferCtxt<'_, 'gcx, 'tcx>>,
 385         tcx: TyCtxt<'_, 'gcx, 'tcx>,
 386         canonicalize_region_mode: &dyn CanonicalizeRegionMode,
 387         query_state: &mut OriginalQueryValues<'tcx>,
 388     ) -> Canonicalized<'gcx, V>
 389     where
 390         V: TypeFoldable<'tcx> + Lift<'gcx>,
 391     {
 392         debug_assert!(
 393             !value.has_type_flags(TypeFlags::HAS_CANONICAL_VARS),
 394             "canonicalizing a canonical value: {:?}",
 395             value,
 396         );
 397
 398         let needs_canonical_flags = if canonicalize_region_mode.any() {
 399             TypeFlags::HAS_FREE_REGIONS | TypeFlags::KEEP_IN_LOCAL_TCX
 400         } else {
 401             TypeFlags::KEEP_IN_LOCAL_TCX
 402         };
 403
 404         let gcx = tcx.global_tcx();
 405
 406         // Fast path: nothing that needs to be canonicalized.
 407         if !value.has_type_flags(needs_canonical_flags) {
 408             let out_value = gcx.lift(value).unwrap();
 409             let canon_value = Canonical {
 410                 max_universe: ty::UniverseIndex::ROOT,
 411                 variables: List::empty(),
 412                 value: out_value,
 413             };
 414             return canon_value;
 415         }
 416
 417         let mut canonicalizer = Canonicalizer {
 418             infcx,
 419             tcx,
 420             canonicalize_region_mode,
 421             needs_canonical_flags,
 422             variables: SmallVec::new(),
 423             query_state,
 424             indices: FxHashMap::default(),
 425         };
 426         let out_value = value.fold_with(&mut canonicalizer);
 427
 428         // Once we have canonicalized `out_value`, it should not
 429         // contain anything that ties it to this inference context
 430         // anymore, so it should live in the global arena.
 431         let out_value = gcx.lift(&out_value).unwrap_or_else(|| {
 432             bug!(
 433                 "failed to lift `{:?}`, canonicalized from `{:?}`",
 434                 out_value,
 435                 value
 436             )
 437         });
 438
 439         let canonical_variables = tcx.intern_canonical_var_infos(&canonicalizer.variables);
 440
 441         let max_universe = canonical_variables
 442             .iter()
 443             .map(|cvar| cvar.universe())
 444             .max()
 445             .unwrap_or(ty::UniverseIndex::ROOT);
 446
 447         Canonical {
 448             max_universe,
 449             variables: canonical_variables,
 450             value: out_value,
 451         }
 452     }
 453
 454     /// Creates a canonical variable replacing `kind` from the input,
 455     /// or returns an existing variable if `kind` has already been
 456     /// seen. `kind` is expected to be an unbound variable (or
 457     /// potentially a free region).
 458     fn canonical_var(&mut self, info: CanonicalVarInfo, kind: Kind<'tcx>) -> BoundTyIndex {
 459         let Canonicalizer {
 460             variables,
 461             query_state,
 462             indices,
 463             ..
 464         } = self;
 465
 466         let var_values = &mut query_state.var_values;
 467
 468         // This code is hot. `variables` and `var_values` are usually small
 469         // (fewer than 8 elements ~95% of the time). They are SmallVec's to
 470         // avoid allocations in those cases. We also don't use `indices` to
 471         // determine if a kind has been seen before until the limit of 8 has
 472         // been exceeded, to also avoid allocations for `indices`.
 473         let var = if !var_values.spilled() {
 474             // `var_values` is stack-allocated. `indices` isn't used yet. Do a
 475             // direct linear search of `var_values`.
 476             if let Some(idx) = var_values.iter().position(|&k| k == kind) {
 477                 // `kind` is already present in `var_values`.
 478                 BoundTyIndex::new(idx)
 479             } else {
 480                 // `kind` isn't present in `var_values`. Append it. Likewise
 481                 // for `info` and `variables`.
 482                 variables.push(info);
 483                 var_values.push(kind);
 484                 assert_eq!(variables.len(), var_values.len());
 485
 486                 // If `var_values` has become big enough to be heap-allocated,
 487                 // fill up `indices` to facilitate subsequent lookups.
 488                 if var_values.spilled() {
 489                     assert!(indices.is_empty());
 490                     *indices = var_values
 491                         .iter()
 492                         .enumerate()
 493                         .map(|(i, &kind)| (kind, BoundTyIndex::new(i)))
 494                         .collect();
 495                 }
 496                 // The cv is the index of the appended element.
 497                 BoundTyIndex::new(var_values.len() - 1)
 498             }
 499         } else {
 500             // `var_values` is large. Do a hashmap search via `indices`.
 501             *indices.entry(kind).or_insert_with(|| {
 502                 variables.push(info);
 503                 var_values.push(kind);
 504                 assert_eq!(variables.len(), var_values.len());
 505                 BoundTyIndex::new(variables.len() - 1)
 506             })
 507         };
 508
 509         var
 510     }
 511
 512     /// Shorthand helper that creates a canonical region variable for
 513     /// `r` (always in the root universe). The reason that we always
 514     /// put these variables into the root universe is because this
 515     /// method is used during **query construction:** in that case, we
 516     /// are taking all the regions and just putting them into the most
 517     /// generic context we can. This may generate solutions that don't
 518     /// fit (e.g., that equate some region variable with a placeholder
 519     /// it can't name) on the caller side, but that's ok, the caller
 520     /// can figure that out. In the meantime, it maximizes our
 521     /// caching.
 522     ///
 523     /// (This works because unification never fails -- and hence trait
 524     /// selection is never affected -- due to a universe mismatch.)
 525     fn canonical_var_for_region_in_root_universe(
 526         &mut self,
 527         r: ty::Region<'tcx>,
 528     ) -> ty::Region<'tcx> {
 529         self.canonical_var_for_region(
 530             CanonicalVarInfo {
 531                 kind: CanonicalVarKind::Region(ty::UniverseIndex::ROOT),
 532             },
 533             r,
 534         )
 535     }
 536
 537     /// Returns the universe in which `vid` is defined.
 538     fn region_var_universe(&self, vid: ty::RegionVid) -> ty::UniverseIndex {
 539         self.infcx
 540             .unwrap()
 541             .borrow_region_constraints()
 542             .var_universe(vid)
 543     }
 544
 545     /// Create a canonical variable (with the given `info`)
 546     /// representing the region `r`; return a region referencing it.
 547     fn canonical_var_for_region(
 548         &mut self,
 549         info: CanonicalVarInfo,
 550         r: ty::Region<'tcx>,
 551     ) -> ty::Region<'tcx> {
 552         let var = self.canonical_var(info, r.into());
 553         self.tcx().mk_region(ty::ReCanonical(var))
 554     }
 555
 556     /// Given a type variable `ty_var` of the given kind, first check
 557     /// if `ty_var` is bound to anything; if so, canonicalize
 558     /// *that*. Otherwise, create a new canonical variable for
 559     /// `ty_var`.
 560     fn canonicalize_ty_var(&mut self, ty_kind: CanonicalTyVarKind, ty_var: Ty<'tcx>) -> Ty<'tcx> {
 561         let infcx = self.infcx.expect("encountered ty-var without infcx");
 562         let bound_to = infcx.shallow_resolve(ty_var);
 563         if bound_to != ty_var {
 564             self.fold_ty(bound_to)
 565         } else {
 566             let info = CanonicalVarInfo {
 567                 kind: CanonicalVarKind::Ty(ty_kind),
 568             };
 569             let var = self.canonical_var(info, ty_var.into());
 570             self.tcx().mk_ty(ty::Bound(BoundTy::new(ty::INNERMOST, var)))
 571         }
 572     }
 573 }