src/librustc/infer/canonical/mod.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 //! **Canonicalization** is the key to constructing a query in the
  12 //! middle of type inference. Ordinarily, it is not possible to store
  13 //! types from type inference in query keys, because they contain
  14 //! references to inference variables whose lifetimes are too short
  15 //! and so forth. Canonicalizing a value T1 using `canonicalize_query`
  16 //! produces two things:
  17 //!
  18 //! - a value T2 where each unbound inference variable has been
  19 //!   replaced with a **canonical variable**;
  20 //! - a map M (of type `CanonicalVarValues`) from those canonical
  21 //!   variables back to the original.
  22 //!
  23 //! We can then do queries using T2. These will give back constraints
  24 //! on the canonical variables which can be translated, using the map
  25 //! M, into constraints in our source context. This process of
  26 //! translating the results back is done by the
  27 //! `instantiate_query_result` method.
  28 //!
  29 //! For a more detailed look at what is happening here, check
  30 //! out the [chapter in the rustc guide][c].
  31 //!
  32 //! [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html
  33
  34 use infer::{InferCtxt, RegionVariableOrigin, TypeVariableOrigin};
  35 use rustc_data_structures::indexed_vec::IndexVec;
  36 use rustc_data_structures::sync::Lrc;
  37 use serialize::UseSpecializedDecodable;
  38 use smallvec::SmallVec;
  39 use std::ops::Index;
  40 use syntax::source_map::Span;
  41 use ty::fold::TypeFoldable;
  42 use ty::subst::Kind;
  43 use ty::{self, BoundVar, Lift, List, Region, TyCtxt};
  44
  45 mod canonicalizer;
  46
  47 pub mod query_response;
  48
  49 mod substitute;
  50
  51 /// A "canonicalized" type `V` is one where all free inference
  52 /// variables have been rewritten to "canonical vars". These are
  53 /// numbered starting from 0 in order of first appearance.
  54 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)]
  55 pub struct Canonical<'gcx, V> {
  56     pub max_universe: ty::UniverseIndex,
  57     pub variables: CanonicalVarInfos<'gcx>,
  58     pub value: V,
  59 }
  60
  61 pub type CanonicalVarInfos<'gcx> = &'gcx List<CanonicalVarInfo>;
  62
  63 impl<'gcx> UseSpecializedDecodable for CanonicalVarInfos<'gcx> {}
  64
  65 /// A set of values corresponding to the canonical variables from some
  66 /// `Canonical`. You can give these values to
  67 /// `canonical_value.substitute` to substitute them into the canonical
  68 /// value at the right places.
  69 ///
  70 /// When you canonicalize a value `V`, you get back one of these
  71 /// vectors with the original values that were replaced by canonical
  72 /// variables. You will need to supply it later to instantiate the
  73 /// canonicalized query response.
  74 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)]
  75 pub struct CanonicalVarValues<'tcx> {
  76     pub var_values: IndexVec<BoundVar, Kind<'tcx>>,
  77 }
  78
  79 /// When we canonicalize a value to form a query, we wind up replacing
  80 /// various parts of it with canonical variables. This struct stores
  81 /// those replaced bits to remember for when we process the query
  82 /// result.
  83 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)]
  84 pub struct OriginalQueryValues<'tcx> {
  85     /// Map from the universes that appear in the query to the
  86     /// universes in the caller context. For the time being, we only
  87     /// ever put ROOT values into the query, so this map is very
  88     /// simple.
  89     pub universe_map: SmallVec<[ty::UniverseIndex; 4]>,
  90
  91     /// This is equivalent to `CanonicalVarValues`, but using a
  92     /// `SmallVec` yields a significant performance win.
  93     pub var_values: SmallVec<[Kind<'tcx>; 8]>,
  94 }
  95
  96 impl Default for OriginalQueryValues<'tcx> {
  97     fn default() -> Self {
  98         let mut universe_map = SmallVec::default();
  99         universe_map.push(ty::UniverseIndex::ROOT);
 100
 101         Self {
 102             universe_map,
 103             var_values: SmallVec::default(),
 104         }
 105     }
 106 }
 107
 108 /// Information about a canonical variable that is included with the
 109 /// canonical value. This is sufficient information for code to create
 110 /// a copy of the canonical value in some other inference context,
 111 /// with fresh inference variables replacing the canonical values.
 112 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)]
 113 pub struct CanonicalVarInfo {
 114     pub kind: CanonicalVarKind,
 115 }
 116
 117 impl CanonicalVarInfo {
 118     pub fn universe(&self) -> ty::UniverseIndex {
 119         self.kind.universe()
 120     }
 121
 122     pub fn is_existential(&self) -> bool {
 123         match self.kind {
 124             CanonicalVarKind::Ty(_) => true,
 125             CanonicalVarKind::Region(_) => true,
 126             CanonicalVarKind::PlaceholderRegion(..) => false,
 127         }
 128     }
 129 }
 130
 131 /// Describes the "kind" of the canonical variable. This is a "kind"
 132 /// in the type-theory sense of the term -- i.e., a "meta" type system
 133 /// that analyzes type-like values.
 134 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)]
 135 pub enum CanonicalVarKind {
 136     /// Some kind of type inference variable.
 137     Ty(CanonicalTyVarKind),
 138
 139     /// Region variable `'?R`.
 140     Region(ty::UniverseIndex),
 141
 142     /// A "placeholder" that represents "any region". Created when you
 143     /// are solving a goal like `for<'a> T: Foo<'a>` to represent the
 144     /// bound region `'a`.
 145     PlaceholderRegion(ty::PlaceholderRegion),
 146 }
 147
 148 impl CanonicalVarKind {
 149     pub fn universe(self) -> ty::UniverseIndex {
 150         match self {
 151             // At present, we don't support higher-ranked
 152             // quantification over types, so all type variables are in
 153             // the root universe.
 154             CanonicalVarKind::Ty(_) => ty::UniverseIndex::ROOT,
 155
 156             // Region variables can be created in sub-universes.
 157             CanonicalVarKind::Region(ui) => ui,
 158             CanonicalVarKind::PlaceholderRegion(placeholder) => placeholder.universe,
 159         }
 160     }
 161 }
 162
 163 /// Rust actually has more than one category of type variables;
 164 /// notably, the type variables we create for literals (e.g., 22 or
 165 /// 22.) can only be instantiated with integral/float types (e.g.,
 166 /// usize or f32). In order to faithfully reproduce a type, we need to
 167 /// know what set of types a given type variable can be unified with.
 168 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)]
 169 pub enum CanonicalTyVarKind {
 170     /// General type variable `?T` that can be unified with arbitrary types.
 171     General,
 172
 173     /// Integral type variable `?I` (that can only be unified with integral types).
 174     Int,
 175
 176     /// Floating-point type variable `?F` (that can only be unified with float types).
 177     Float,
 178 }
 179
 180 /// After we execute a query with a canonicalized key, we get back a
 181 /// `Canonical<QueryResponse<..>>`. You can use
 182 /// `instantiate_query_result` to access the data in this result.
 183 #[derive(Clone, Debug)]
 184 pub struct QueryResponse<'tcx, R> {
 185     pub var_values: CanonicalVarValues<'tcx>,
 186     pub region_constraints: Vec<QueryRegionConstraint<'tcx>>,
 187     pub certainty: Certainty,
 188     pub value: R,
 189 }
 190
 191 pub type Canonicalized<'gcx, V> = Canonical<'gcx, <V as Lift<'gcx>>::Lifted>;
 192
 193 pub type CanonicalizedQueryResponse<'gcx, T> =
 194     Lrc<Canonical<'gcx, QueryResponse<'gcx, <T as Lift<'gcx>>::Lifted>>>;
 195
 196 /// Indicates whether or not we were able to prove the query to be
 197 /// true.
 198 #[derive(Copy, Clone, Debug)]
 199 pub enum Certainty {
 200     /// The query is known to be true, presuming that you apply the
 201     /// given `var_values` and the region-constraints are satisfied.
 202     Proven,
 203
 204     /// The query is not known to be true, but also not known to be
 205     /// false. The `var_values` represent *either* values that must
 206     /// hold in order for the query to be true, or helpful tips that
 207     /// *might* make it true. Currently rustc's trait solver cannot
 208     /// distinguish the two (e.g., due to our preference for where
 209     /// clauses over impls).
 210     ///
 211     /// After some unifiations and things have been done, it makes
 212     /// sense to try and prove again -- of course, at that point, the
 213     /// canonical form will be different, making this a distinct
 214     /// query.
 215     Ambiguous,
 216 }
 217
 218 impl Certainty {
 219     pub fn is_proven(&self) -> bool {
 220         match self {
 221             Certainty::Proven => true,
 222             Certainty::Ambiguous => false,
 223         }
 224     }
 225
 226     pub fn is_ambiguous(&self) -> bool {
 227         !self.is_proven()
 228     }
 229 }
 230
 231 impl<'tcx, R> QueryResponse<'tcx, R> {
 232     pub fn is_proven(&self) -> bool {
 233         self.certainty.is_proven()
 234     }
 235
 236     pub fn is_ambiguous(&self) -> bool {
 237         !self.is_proven()
 238     }
 239 }
 240
 241 impl<'tcx, R> Canonical<'tcx, QueryResponse<'tcx, R>> {
 242     pub fn is_proven(&self) -> bool {
 243         self.value.is_proven()
 244     }
 245
 246     pub fn is_ambiguous(&self) -> bool {
 247         !self.is_proven()
 248     }
 249 }
 250
 251 impl<'gcx, V> Canonical<'gcx, V> {
 252     /// Allows you to map the `value` of a canonical while keeping the
 253     /// same set of bound variables.
 254     ///
 255     /// **WARNING:** This function is very easy to mis-use, hence the
 256     /// name!  In particular, the new value `W` must use all **the
 257     /// same type/region variables** in **precisely the same order**
 258     /// as the original! (The ordering is defined by the
 259     /// `TypeFoldable` implementation of the type in question.)
 260     ///
 261     /// An example of a **correct** use of this:
 262     ///
 263     /// ```rust,ignore (not real code)
 264     /// let a: Canonical<'_, T> = ...;
 265     /// let b: Canonical<'_, (T,)> = a.unchecked_map(|v| (v, ));
 266     /// ```
 267     ///
 268     /// An example of an **incorrect** use of this:
 269     ///
 270     /// ```rust,ignore (not real code)
 271     /// let a: Canonical<'tcx, T> = ...;
 272     /// let ty: Ty<'tcx> = ...;
 273     /// let b: Canonical<'tcx, (T, Ty<'tcx>)> = a.unchecked_map(|v| (v, ty));
 274     /// ```
 275     pub fn unchecked_map<W>(self, map_op: impl FnOnce(V) -> W) -> Canonical<'gcx, W> {
 276         let Canonical {
 277             max_universe,
 278             variables,
 279             value,
 280         } = self;
 281         Canonical {
 282             max_universe,
 283             variables,
 284             value: map_op(value),
 285         }
 286     }
 287 }
 288
 289 pub type QueryRegionConstraint<'tcx> = ty::Binder<ty::OutlivesPredicate<Kind<'tcx>, Region<'tcx>>>;
 290
 291 impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
 292     /// Creates a substitution S for the canonical value with fresh
 293     /// inference variables and applies it to the canonical value.
 294     /// Returns both the instantiated result *and* the substitution S.
 295     ///
 296     /// This is only meant to be invoked as part of constructing an
 297     /// inference context at the start of a query (see
 298     /// `InferCtxtBuilder::enter_with_canonical`).  It basically
 299     /// brings the canonical value "into scope" within your new infcx.
 300     ///
 301     /// At the end of processing, the substitution S (once
 302     /// canonicalized) then represents the values that you computed
 303     /// for each of the canonical inputs to your query.
 304
 305     pub fn instantiate_canonical_with_fresh_inference_vars<T>(
 306         &self,
 307         span: Span,
 308         canonical: &Canonical<'tcx, T>,
 309     ) -> (T, CanonicalVarValues<'tcx>)
 310     where
 311         T: TypeFoldable<'tcx>,
 312     {
 313         // For each universe that is referred to in the incoming
 314         // query, create a universe in our local inference context. In
 315         // practice, as of this writing, all queries have no universes
 316         // in them, so this code has no effect, but it is looking
 317         // forward to the day when we *do* want to carry universes
 318         // through into queries.
 319         let universes: IndexVec<ty::UniverseIndex, _> = std::iter::once(ty::UniverseIndex::ROOT)
 320             .chain((0..canonical.max_universe.as_u32()).map(|_| self.create_next_universe()))
 321             .collect();
 322
 323         let canonical_inference_vars =
 324             self.instantiate_canonical_vars(span, canonical.variables, |ui| universes[ui]);
 325         let result = canonical.substitute(self.tcx, &canonical_inference_vars);
 326         (result, canonical_inference_vars)
 327     }
 328
 329     /// Given the "infos" about the canonical variables from some
 330     /// canonical, creates fresh variables with the same
 331     /// characteristics (see `instantiate_canonical_var` for
 332     /// details). You can then use `substitute` to instantiate the
 333     /// canonical variable with these inference variables.
 334     fn instantiate_canonical_vars(
 335         &self,
 336         span: Span,
 337         variables: &List<CanonicalVarInfo>,
 338         universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex,
 339     ) -> CanonicalVarValues<'tcx> {
 340         let var_values: IndexVec<BoundVar, Kind<'tcx>> = variables
 341             .iter()
 342             .map(|info| self.instantiate_canonical_var(span, *info, &universe_map))
 343             .collect();
 344
 345         CanonicalVarValues { var_values }
 346     }
 347
 348     /// Given the "info" about a canonical variable, creates a fresh
 349     /// variable for it. If this is an existentially quantified
 350     /// variable, then you'll get a new inference variable; if it is a
 351     /// universally quantified variable, you get a placeholder.
 352     fn instantiate_canonical_var(
 353         &self,
 354         span: Span,
 355         cv_info: CanonicalVarInfo,
 356         universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex,
 357     ) -> Kind<'tcx> {
 358         match cv_info.kind {
 359             CanonicalVarKind::Ty(ty_kind) => {
 360                 let ty = match ty_kind {
 361                     CanonicalTyVarKind::General => {
 362                         self.next_ty_var(TypeVariableOrigin::MiscVariable(span))
 363                     }
 364
 365                     CanonicalTyVarKind::Int => self.tcx.mk_int_var(self.next_int_var_id()),
 366
 367                     CanonicalTyVarKind::Float => self.tcx.mk_float_var(self.next_float_var_id()),
 368                 };
 369                 ty.into()
 370             }
 371
 372             CanonicalVarKind::Region(ui) => self.next_region_var_in_universe(
 373                 RegionVariableOrigin::MiscVariable(span),
 374                 universe_map(ui),
 375             ).into(),
 376
 377             CanonicalVarKind::PlaceholderRegion(ty::PlaceholderRegion { universe, name }) => {
 378                 let universe_mapped = universe_map(universe);
 379                 let placeholder_mapped = ty::PlaceholderRegion {
 380                     universe: universe_mapped,
 381                     name,
 382                 };
 383                 self.tcx
 384                     .mk_region(ty::RePlaceholder(placeholder_mapped))
 385                     .into()
 386             }
 387         }
 388     }
 389 }
 390
 391 CloneTypeFoldableAndLiftImpls! {
 392     ::infer::canonical::Certainty,
 393     ::infer::canonical::CanonicalVarInfo,
 394     ::infer::canonical::CanonicalVarKind,
 395 }
 396
 397 CloneTypeFoldableImpls! {
 398     for <'tcx> {
 399         ::infer::canonical::CanonicalVarInfos<'tcx>,
 400     }
 401 }
 402
 403 BraceStructTypeFoldableImpl! {
 404     impl<'tcx, C> TypeFoldable<'tcx> for Canonical<'tcx, C> {
 405         max_universe,
 406         variables,
 407         value,
 408     } where C: TypeFoldable<'tcx>
 409 }
 410
 411 BraceStructLiftImpl! {
 412     impl<'a, 'tcx, T> Lift<'tcx> for Canonical<'a, T> {
 413         type Lifted = Canonical<'tcx, T::Lifted>;
 414         max_universe, variables, value
 415     } where T: Lift<'tcx>
 416 }
 417
 418 impl<'tcx> CanonicalVarValues<'tcx> {
 419     fn len(&self) -> usize {
 420         self.var_values.len()
 421     }
 422 }
 423
 424 impl<'a, 'tcx> IntoIterator for &'a CanonicalVarValues<'tcx> {
 425     type Item = Kind<'tcx>;
 426     type IntoIter = ::std::iter::Cloned<::std::slice::Iter<'a, Kind<'tcx>>>;
 427
 428     fn into_iter(self) -> Self::IntoIter {
 429         self.var_values.iter().cloned()
 430     }
 431 }
 432
 433 BraceStructLiftImpl! {
 434     impl<'a, 'tcx> Lift<'tcx> for CanonicalVarValues<'a> {
 435         type Lifted = CanonicalVarValues<'tcx>;
 436         var_values,
 437     }
 438 }
 439
 440 BraceStructTypeFoldableImpl! {
 441     impl<'tcx> TypeFoldable<'tcx> for CanonicalVarValues<'tcx> {
 442         var_values,
 443     }
 444 }
 445
 446 BraceStructTypeFoldableImpl! {
 447     impl<'tcx, R> TypeFoldable<'tcx> for QueryResponse<'tcx, R> {
 448         var_values, region_constraints, certainty, value
 449     } where R: TypeFoldable<'tcx>,
 450 }
 451
 452 BraceStructLiftImpl! {
 453     impl<'a, 'tcx, R> Lift<'tcx> for QueryResponse<'a, R> {
 454         type Lifted = QueryResponse<'tcx, R::Lifted>;
 455         var_values, region_constraints, certainty, value
 456     } where R: Lift<'tcx>
 457 }
 458
 459 impl<'tcx> Index<BoundVar> for CanonicalVarValues<'tcx> {
 460     type Output = Kind<'tcx>;
 461
 462     fn index(&self, value: BoundVar) -> &Kind<'tcx> {
 463         &self.var_values[value]
 464     }
 465 }