src/librustc/infer/canonical/substitute.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 code to substitute new values into a
  12 //! `Canonical<'tcx, T>`.
  13 //!
  14 //! For an overview of what canonicaliation is and how it fits into
  15 //! rustc, check out the [chapter in the rustc guide][c].
  16 //!
  17 //! [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html
  18
  19 use infer::canonical::{Canonical, CanonicalVarValues};
  20 use ty::fold::{TypeFoldable, TypeFolder};
  21 use ty::subst::UnpackedKind;
  22 use ty::{self, Ty, TyCtxt};
  23
  24 impl<'tcx, V> Canonical<'tcx, V> {
  25     /// Instantiate the wrapped value, replacing each canonical value
  26     /// with the value given in `var_values`.
  27     pub fn substitute(&self, tcx: TyCtxt<'_, '_, 'tcx>, var_values: &CanonicalVarValues<'tcx>) -> V
  28     where
  29         V: TypeFoldable<'tcx>,
  30     {
  31         self.substitute_projected(tcx, var_values, |value| value)
  32     }
  33
  34     /// Allows one to apply a substitute to some subset of
  35     /// `self.value`. Invoke `projection_fn` with `self.value` to get
  36     /// a value V that is expressed in terms of the same canonical
  37     /// variables bound in `self` (usually this extracts from subset
  38     /// of `self`). Apply the substitution `var_values` to this value
  39     /// V, replacing each of the canonical variables.
  40     pub fn substitute_projected<T>(
  41         &self,
  42         tcx: TyCtxt<'_, '_, 'tcx>,
  43         var_values: &CanonicalVarValues<'tcx>,
  44         projection_fn: impl FnOnce(&V) -> &T,
  45     ) -> T
  46     where
  47         T: TypeFoldable<'tcx>,
  48     {
  49         assert_eq!(self.variables.len(), var_values.len());
  50         let value = projection_fn(&self.value);
  51         substitute_value(tcx, var_values, value)
  52     }
  53 }
  54
  55 /// Substitute the values from `var_values` into `value`. `var_values`
  56 /// must be values for the set of canonical variables that appear in
  57 /// `value`.
  58 pub(super) fn substitute_value<'a, 'tcx, T>(
  59     tcx: TyCtxt<'_, '_, 'tcx>,
  60     var_values: &CanonicalVarValues<'tcx>,
  61     value: &'a T,
  62 ) -> T
  63 where
  64     T: TypeFoldable<'tcx>,
  65 {
  66     if var_values.var_values.is_empty() {
  67         value.clone()
  68     } else if !value.has_escaping_bound_vars() {
  69         // There are no bound vars to substitute.
  70         value.clone()
  71     } else {
  72         value.fold_with(&mut CanonicalVarValuesSubst {
  73             tcx,
  74             var_values,
  75             binder_index: ty::INNERMOST,
  76         })
  77     }
  78 }
  79
  80 struct CanonicalVarValuesSubst<'cx, 'gcx: 'tcx, 'tcx: 'cx> {
  81     tcx: TyCtxt<'cx, 'gcx, 'tcx>,
  82     var_values: &'cx CanonicalVarValues<'tcx>,
  83     binder_index: ty::DebruijnIndex,
  84 }
  85
  86 impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for CanonicalVarValuesSubst<'cx, 'gcx, 'tcx> {
  87     fn tcx(&self) -> TyCtxt<'_, 'gcx, 'tcx> {
  88         self.tcx
  89     }
  90
  91     fn fold_binder<T>(&mut self, t: &ty::Binder<T>) -> ty::Binder<T>
  92         where T: TypeFoldable<'tcx>
  93     {
  94         self.binder_index.shift_in(1);
  95         let t = t.super_fold_with(self);
  96         self.binder_index.shift_out(1);
  97         t
  98     }
  99
 100     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 101         match t.sty {
 102             ty::Bound(b) => {
 103                 if b.index == self.binder_index {
 104                     match self.var_values.var_values[b.var].unpack() {
 105                         UnpackedKind::Type(ty) => ty::fold::shift_vars(
 106                             self.tcx,
 107                             &ty,
 108                             self.binder_index.index() as u32
 109                         ),
 110                         r => bug!("{:?} is a type but value is {:?}", b, r),
 111                     }
 112                 } else {
 113                     t
 114                 }
 115             }
 116             _ => {
 117                 if !t.has_vars_bound_at_or_above(self.binder_index) {
 118                     // Nothing more to substitute.
 119                     t
 120                 } else {
 121                     t.super_fold_with(self)
 122                 }
 123             }
 124         }
 125     }
 126
 127     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 128         match r {
 129             ty::RegionKind::ReLateBound(index, br) => {
 130                 if *index == self.binder_index {
 131                     match self.var_values.var_values[br.as_bound_var()].unpack() {
 132                         UnpackedKind::Lifetime(l) => ty::fold::shift_region(
 133                             self.tcx,
 134                             l,
 135                             self.binder_index.index() as u32,
 136                         ),
 137                         r => bug!("{:?} is a region but value is {:?}", br, r),
 138                     }
 139                 } else {
 140                     r
 141                 }
 142             }
 143             _ => r.super_fold_with(self),
 144         }
 145     }
 146 }