src/librustc/ty/subst.rs

   1 // Copyright 2012 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 // Type substitutions.
  12
  13 use hir::def_id::DefId;
  14 use ty::{self, Lift, Slice, Ty, TyCtxt};
  15 use ty::fold::{TypeFoldable, TypeFolder, TypeVisitor};
  16
  17 use serialize::{self, Encodable, Encoder, Decodable, Decoder};
  18 use syntax_pos::{Span, DUMMY_SP};
  19 use rustc_data_structures::accumulate_vec::AccumulateVec;
  20 use rustc_data_structures::array_vec::ArrayVec;
  21
  22 use core::intrinsics;
  23 use std::cmp::Ordering;
  24 use std::fmt;
  25 use std::marker::PhantomData;
  26 use std::mem;
  27 use std::num::NonZeroUsize;
  28
  29 /// An entity in the Rust typesystem, which can be one of
  30 /// several kinds (only types and lifetimes for now).
  31 /// To reduce memory usage, a `Kind` is a interned pointer,
  32 /// with the lowest 2 bits being reserved for a tag to
  33 /// indicate the type (`Ty` or `Region`) it points to.
  34 #[derive(Copy, Clone, PartialEq, Eq, Hash)]
  35 pub struct Kind<'tcx> {
  36     ptr: NonZeroUsize,
  37     marker: PhantomData<(Ty<'tcx>, ty::Region<'tcx>)>
  38 }
  39
  40 const TAG_MASK: usize = 0b11;
  41 const TYPE_TAG: usize = 0b00;
  42 const REGION_TAG: usize = 0b01;
  43
  44 #[derive(Debug, RustcEncodable, RustcDecodable)]
  45 pub enum UnpackedKind<'tcx> {
  46     Lifetime(ty::Region<'tcx>),
  47     Type(Ty<'tcx>),
  48 }
  49
  50 impl<'tcx> UnpackedKind<'tcx> {
  51     fn pack(self) -> Kind<'tcx> {
  52         let (tag, ptr) = match self {
  53             UnpackedKind::Lifetime(lt) => {
  54                 // Ensure we can use the tag bits.
  55                 assert_eq!(mem::align_of_val(lt) & TAG_MASK, 0);
  56                 (REGION_TAG, lt as *const _ as usize)
  57             }
  58             UnpackedKind::Type(ty) => {
  59                 // Ensure we can use the tag bits.
  60                 assert_eq!(mem::align_of_val(ty) & TAG_MASK, 0);
  61                 (TYPE_TAG, ty as *const _ as usize)
  62             }
  63         };
  64
  65         Kind {
  66             ptr: unsafe {
  67                 NonZeroUsize::new_unchecked(ptr | tag)
  68             },
  69             marker: PhantomData
  70         }
  71     }
  72 }
  73
  74 impl<'tcx> Ord for Kind<'tcx> {
  75     fn cmp(&self, other: &Kind) -> Ordering {
  76         match (self.unpack(), other.unpack()) {
  77             (UnpackedKind::Type(_), UnpackedKind::Lifetime(_)) => Ordering::Greater,
  78
  79             (UnpackedKind::Type(ty1), UnpackedKind::Type(ty2)) => {
  80                 ty1.sty.cmp(&ty2.sty)
  81             }
  82
  83             (UnpackedKind::Lifetime(reg1), UnpackedKind::Lifetime(reg2)) => reg1.cmp(reg2),
  84
  85             (UnpackedKind::Lifetime(_), UnpackedKind::Type(_))  => Ordering::Less,
  86         }
  87     }
  88 }
  89
  90 impl<'tcx> PartialOrd for Kind<'tcx> {
  91     fn partial_cmp(&self, other: &Kind) -> Option<Ordering> {
  92         Some(self.cmp(&other))
  93     }
  94 }
  95
  96 impl<'tcx> From<ty::Region<'tcx>> for Kind<'tcx> {
  97     fn from(r: ty::Region<'tcx>) -> Kind<'tcx> {
  98         UnpackedKind::Lifetime(r).pack()
  99     }
 100 }
 101
 102 impl<'tcx> From<Ty<'tcx>> for Kind<'tcx> {
 103     fn from(ty: Ty<'tcx>) -> Kind<'tcx> {
 104         UnpackedKind::Type(ty).pack()
 105     }
 106 }
 107
 108 impl<'tcx> Kind<'tcx> {
 109     #[inline]
 110     pub fn unpack(self) -> UnpackedKind<'tcx> {
 111         let ptr = self.ptr.get();
 112         unsafe {
 113             match ptr & TAG_MASK {
 114                 REGION_TAG => UnpackedKind::Lifetime(&*((ptr & !TAG_MASK) as *const _)),
 115                 TYPE_TAG => UnpackedKind::Type(&*((ptr & !TAG_MASK) as *const _)),
 116                 _ => intrinsics::unreachable()
 117             }
 118         }
 119     }
 120 }
 121
 122 impl<'tcx> fmt::Debug for Kind<'tcx> {
 123     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 124         match self.unpack() {
 125             UnpackedKind::Lifetime(lt) => write!(f, "{:?}", lt),
 126             UnpackedKind::Type(ty) => write!(f, "{:?}", ty),
 127         }
 128     }
 129 }
 130
 131 impl<'tcx> fmt::Display for Kind<'tcx> {
 132     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 133         match self.unpack() {
 134             UnpackedKind::Lifetime(lt) => write!(f, "{}", lt),
 135             UnpackedKind::Type(ty) => write!(f, "{}", ty),
 136         }
 137     }
 138 }
 139
 140 impl<'a, 'tcx> Lift<'tcx> for Kind<'a> {
 141     type Lifted = Kind<'tcx>;
 142
 143     fn lift_to_tcx<'cx, 'gcx>(&self, tcx: TyCtxt<'cx, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 144         match self.unpack() {
 145             UnpackedKind::Lifetime(a) => a.lift_to_tcx(tcx).map(|a| a.into()),
 146             UnpackedKind::Type(a) => a.lift_to_tcx(tcx).map(|a| a.into()),
 147         }
 148     }
 149 }
 150
 151 impl<'tcx> TypeFoldable<'tcx> for Kind<'tcx> {
 152     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 153         match self.unpack() {
 154             UnpackedKind::Lifetime(lt) => lt.fold_with(folder).into(),
 155             UnpackedKind::Type(ty) => ty.fold_with(folder).into(),
 156         }
 157     }
 158
 159     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 160         match self.unpack() {
 161             UnpackedKind::Lifetime(lt) => lt.visit_with(visitor),
 162             UnpackedKind::Type(ty) => ty.visit_with(visitor),
 163         }
 164     }
 165 }
 166
 167 impl<'tcx> Encodable for Kind<'tcx> {
 168     fn encode<E: Encoder>(&self, e: &mut E) -> Result<(), E::Error> {
 169         self.unpack().encode(e)
 170     }
 171 }
 172
 173 impl<'tcx> Decodable for Kind<'tcx> {
 174     fn decode<D: Decoder>(d: &mut D) -> Result<Kind<'tcx>, D::Error> {
 175         Ok(UnpackedKind::decode(d)?.pack())
 176     }
 177 }
 178
 179 /// A substitution mapping generic parameters to new values.
 180 pub type Substs<'tcx> = Slice<Kind<'tcx>>;
 181
 182 impl<'a, 'gcx, 'tcx> Substs<'tcx> {
 183     /// Creates a Substs that maps each generic parameter to itself.
 184     pub fn identity_for_item(tcx: TyCtxt<'a, 'gcx, 'tcx>, def_id: DefId)
 185                              -> &'tcx Substs<'tcx> {
 186         Substs::for_item(tcx, def_id, |param, _| {
 187             tcx.mk_param_from_def(param)
 188         })
 189     }
 190
 191     /// Creates a Substs for generic parameter definitions,
 192     /// by calling closures to obtain each kind.
 193     /// The closures get to observe the Substs as they're
 194     /// being built, which can be used to correctly
 195     /// substitute defaults of generic parameters.
 196     pub fn for_item<F>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
 197                        def_id: DefId,
 198                        mut mk_kind: F)
 199                        -> &'tcx Substs<'tcx>
 200     where F: FnMut(&ty::GenericParamDef, &[Kind<'tcx>]) -> Kind<'tcx>
 201     {
 202         let defs = tcx.generics_of(def_id);
 203         let count = defs.count();
 204         let mut substs = if count <= 8 {
 205             AccumulateVec::Array(ArrayVec::new())
 206         } else {
 207             AccumulateVec::Heap(Vec::with_capacity(count))
 208         };
 209         Substs::fill_item(&mut substs, tcx, defs, &mut mk_kind);
 210         tcx.intern_substs(&substs)
 211     }
 212
 213     pub fn extend_to<F>(&self,
 214                         tcx: TyCtxt<'a, 'gcx, 'tcx>,
 215                         def_id: DefId,
 216                         mut mk_kind: F)
 217                         -> &'tcx Substs<'tcx>
 218     where F: FnMut(&ty::GenericParamDef, &[Kind<'tcx>]) -> Kind<'tcx>
 219     {
 220         Substs::for_item(tcx, def_id, |param, substs| {
 221             match self.get(param.index as usize) {
 222                 Some(&kind) => kind,
 223                 None => mk_kind(param, substs),
 224             }
 225         })
 226     }
 227
 228     fn fill_item<F>(substs: &mut AccumulateVec<[Kind<'tcx>; 8]>,
 229                     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 230                     defs: &ty::Generics,
 231                     mk_kind: &mut F)
 232     where F: FnMut(&ty::GenericParamDef, &[Kind<'tcx>]) -> Kind<'tcx>
 233     {
 234         if let Some(def_id) = defs.parent {
 235             let parent_defs = tcx.generics_of(def_id);
 236             Substs::fill_item(substs, tcx, parent_defs, mk_kind);
 237         }
 238         Substs::fill_single(substs, defs, mk_kind)
 239     }
 240
 241     fn fill_single<F>(substs: &mut AccumulateVec<[Kind<'tcx>; 8]>,
 242                       defs: &ty::Generics,
 243                       mk_kind: &mut F)
 244     where F: FnMut(&ty::GenericParamDef, &[Kind<'tcx>]) -> Kind<'tcx>
 245     {
 246         for param in &defs.params {
 247             let kind = mk_kind(param, substs);
 248             assert_eq!(param.index as usize, substs.len());
 249             match *substs {
 250                 AccumulateVec::Array(ref mut arr) => arr.push(kind),
 251                 AccumulateVec::Heap(ref mut vec) => vec.push(kind),
 252             }
 253         }
 254     }
 255
 256     pub fn is_noop(&self) -> bool {
 257         self.is_empty()
 258     }
 259
 260     #[inline]
 261     pub fn types(&'a self) -> impl DoubleEndedIterator<Item=Ty<'tcx>> + 'a {
 262         self.iter().filter_map(|k| {
 263             if let UnpackedKind::Type(ty) = k.unpack() {
 264                 Some(ty)
 265             } else {
 266                 None
 267             }
 268         })
 269     }
 270
 271     #[inline]
 272     pub fn regions(&'a self) -> impl DoubleEndedIterator<Item=ty::Region<'tcx>> + 'a {
 273         self.iter().filter_map(|k| {
 274             if let UnpackedKind::Lifetime(lt) = k.unpack() {
 275                 Some(lt)
 276             } else {
 277                 None
 278             }
 279         })
 280     }
 281
 282     #[inline]
 283     pub fn type_at(&self, i: usize) -> Ty<'tcx> {
 284         if let UnpackedKind::Type(ty) = self[i].unpack() {
 285             ty
 286         } else {
 287             bug!("expected type for param #{} in {:?}", i, self);
 288         }
 289     }
 290
 291     #[inline]
 292     pub fn region_at(&self, i: usize) -> ty::Region<'tcx> {
 293         if let UnpackedKind::Lifetime(lt) = self[i].unpack() {
 294             lt
 295         } else {
 296             bug!("expected region for param #{} in {:?}", i, self);
 297         }
 298     }
 299
 300     #[inline]
 301     pub fn type_for_def(&self, def: &ty::GenericParamDef) -> Kind<'tcx> {
 302         self.type_at(def.index as usize).into()
 303     }
 304
 305     /// Transform from substitutions for a child of `source_ancestor`
 306     /// (e.g. a trait or impl) to substitutions for the same child
 307     /// in a different item, with `target_substs` as the base for
 308     /// the target impl/trait, with the source child-specific
 309     /// parameters (e.g. method parameters) on top of that base.
 310     pub fn rebase_onto(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>,
 311                        source_ancestor: DefId,
 312                        target_substs: &Substs<'tcx>)
 313                        -> &'tcx Substs<'tcx> {
 314         let defs = tcx.generics_of(source_ancestor);
 315         tcx.mk_substs(target_substs.iter().chain(&self[defs.params.len()..]).cloned())
 316     }
 317
 318     pub fn truncate_to(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>, generics: &ty::Generics)
 319                        -> &'tcx Substs<'tcx> {
 320         tcx.mk_substs(self.iter().take(generics.count()).cloned())
 321     }
 322 }
 323
 324 impl<'tcx> TypeFoldable<'tcx> for &'tcx Substs<'tcx> {
 325     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 326         let params: AccumulateVec<[_; 8]> = self.iter().map(|k| k.fold_with(folder)).collect();
 327
 328         // If folding doesn't change the substs, it's faster to avoid
 329         // calling `mk_substs` and instead reuse the existing substs.
 330         if params[..] == self[..] {
 331             self
 332         } else {
 333             folder.tcx().intern_substs(&params)
 334         }
 335     }
 336
 337     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 338         self.iter().any(|t| t.visit_with(visitor))
 339     }
 340 }
 341
 342 impl<'tcx> serialize::UseSpecializedDecodable for &'tcx Substs<'tcx> {}
 343
 344 ///////////////////////////////////////////////////////////////////////////
 345 // Public trait `Subst`
 346 //
 347 // Just call `foo.subst(tcx, substs)` to perform a substitution across
 348 // `foo`. Or use `foo.subst_spanned(tcx, substs, Some(span))` when
 349 // there is more information available (for better errors).
 350
 351 pub trait Subst<'tcx> : Sized {
 352     fn subst<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>,
 353                       substs: &[Kind<'tcx>]) -> Self {
 354         self.subst_spanned(tcx, substs, None)
 355     }
 356
 357     fn subst_spanned<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>,
 358                                substs: &[Kind<'tcx>],
 359                                span: Option<Span>)
 360                                -> Self;
 361 }
 362
 363 impl<'tcx, T:TypeFoldable<'tcx>> Subst<'tcx> for T {
 364     fn subst_spanned<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>,
 365                                substs: &[Kind<'tcx>],
 366                                span: Option<Span>)
 367                                -> T
 368     {
 369         let mut folder = SubstFolder { tcx,
 370                                        substs,
 371                                        span,
 372                                        root_ty: None,
 373                                        ty_stack_depth: 0,
 374                                        region_binders_passed: 0 };
 375         (*self).fold_with(&mut folder)
 376     }
 377 }
 378
 379 ///////////////////////////////////////////////////////////////////////////
 380 // The actual substitution engine itself is a type folder.
 381
 382 struct SubstFolder<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
 383     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 384     substs: &'a [Kind<'tcx>],
 385
 386     // The location for which the substitution is performed, if available.
 387     span: Option<Span>,
 388
 389     // The root type that is being substituted, if available.
 390     root_ty: Option<Ty<'tcx>>,
 391
 392     // Depth of type stack
 393     ty_stack_depth: usize,
 394
 395     // Number of region binders we have passed through while doing the substitution
 396     region_binders_passed: u32,
 397 }
 398
 399 impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for SubstFolder<'a, 'gcx, 'tcx> {
 400     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> { self.tcx }
 401
 402     fn fold_binder<T: TypeFoldable<'tcx>>(&mut self, t: &ty::Binder<T>) -> ty::Binder<T> {
 403         self.region_binders_passed += 1;
 404         let t = t.super_fold_with(self);
 405         self.region_binders_passed -= 1;
 406         t
 407     }
 408
 409     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 410         // Note: This routine only handles regions that are bound on
 411         // type declarations and other outer declarations, not those
 412         // bound in *fn types*. Region substitution of the bound
 413         // regions that appear in a function signature is done using
 414         // the specialized routine `ty::replace_late_regions()`.
 415         match *r {
 416             ty::ReEarlyBound(data) => {
 417                 let r = self.substs.get(data.index as usize).map(|k| k.unpack());
 418                 match r {
 419                     Some(UnpackedKind::Lifetime(lt)) => {
 420                         self.shift_region_through_binders(lt)
 421                     }
 422                     _ => {
 423                         let span = self.span.unwrap_or(DUMMY_SP);
 424                         span_bug!(
 425                             span,
 426                             "Region parameter out of range \
 427                              when substituting in region {} (root type={:?}) \
 428                              (index={})",
 429                             data.name,
 430                             self.root_ty,
 431                             data.index);
 432                     }
 433                 }
 434             }
 435             _ => r
 436         }
 437     }
 438
 439     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 440         if !t.needs_subst() {
 441             return t;
 442         }
 443
 444         // track the root type we were asked to substitute
 445         let depth = self.ty_stack_depth;
 446         if depth == 0 {
 447             self.root_ty = Some(t);
 448         }
 449         self.ty_stack_depth += 1;
 450
 451         let t1 = match t.sty {
 452             ty::TyParam(p) => {
 453                 self.ty_for_param(p, t)
 454             }
 455             _ => {
 456                 t.super_fold_with(self)
 457             }
 458         };
 459
 460         assert_eq!(depth + 1, self.ty_stack_depth);
 461         self.ty_stack_depth -= 1;
 462         if depth == 0 {
 463             self.root_ty = None;
 464         }
 465
 466         return t1;
 467     }
 468 }
 469
 470 impl<'a, 'gcx, 'tcx> SubstFolder<'a, 'gcx, 'tcx> {
 471     fn ty_for_param(&self, p: ty::ParamTy, source_ty: Ty<'tcx>) -> Ty<'tcx> {
 472         // Look up the type in the substitutions. It really should be in there.
 473         let opt_ty = self.substs.get(p.idx as usize).map(|k| k.unpack());
 474         let ty = match opt_ty {
 475             Some(UnpackedKind::Type(ty)) => ty,
 476             _ => {
 477                 let span = self.span.unwrap_or(DUMMY_SP);
 478                 span_bug!(
 479                     span,
 480                     "Type parameter `{:?}` ({:?}/{}) out of range \
 481                          when substituting (root type={:?}) substs={:?}",
 482                     p,
 483                     source_ty,
 484                     p.idx,
 485                     self.root_ty,
 486                     self.substs);
 487             }
 488         };
 489
 490         self.shift_regions_through_binders(ty)
 491     }
 492
 493     /// It is sometimes necessary to adjust the debruijn indices during substitution. This occurs
 494     /// when we are substituting a type with escaping regions into a context where we have passed
 495     /// through region binders. That's quite a mouthful. Let's see an example:
 496     ///
 497     /// ```
 498     /// type Func<A> = fn(A);
 499     /// type MetaFunc = for<'a> fn(Func<&'a int>)
 500     /// ```
 501     ///
 502     /// The type `MetaFunc`, when fully expanded, will be
 503     ///
 504     ///     for<'a> fn(fn(&'a int))
 505     ///             ^~ ^~ ^~~
 506     ///             |  |  |
 507     ///             |  |  DebruijnIndex of 2
 508     ///             Binders
 509     ///
 510     /// Here the `'a` lifetime is bound in the outer function, but appears as an argument of the
 511     /// inner one. Therefore, that appearance will have a DebruijnIndex of 2, because we must skip
 512     /// over the inner binder (remember that we count Debruijn indices from 1). However, in the
 513     /// definition of `MetaFunc`, the binder is not visible, so the type `&'a int` will have a
 514     /// debruijn index of 1. It's only during the substitution that we can see we must increase the
 515     /// depth by 1 to account for the binder that we passed through.
 516     ///
 517     /// As a second example, consider this twist:
 518     ///
 519     /// ```
 520     /// type FuncTuple<A> = (A,fn(A));
 521     /// type MetaFuncTuple = for<'a> fn(FuncTuple<&'a int>)
 522     /// ```
 523     ///
 524     /// Here the final type will be:
 525     ///
 526     ///     for<'a> fn((&'a int, fn(&'a int)))
 527     ///                 ^~~         ^~~
 528     ///                 |           |
 529     ///          DebruijnIndex of 1 |
 530     ///                      DebruijnIndex of 2
 531     ///
 532     /// As indicated in the diagram, here the same type `&'a int` is substituted once, but in the
 533     /// first case we do not increase the Debruijn index and in the second case we do. The reason
 534     /// is that only in the second case have we passed through a fn binder.
 535     fn shift_regions_through_binders(&self, ty: Ty<'tcx>) -> Ty<'tcx> {
 536         debug!("shift_regions(ty={:?}, region_binders_passed={:?}, has_escaping_regions={:?})",
 537                ty, self.region_binders_passed, ty.has_escaping_regions());
 538
 539         if self.region_binders_passed == 0 || !ty.has_escaping_regions() {
 540             return ty;
 541         }
 542
 543         let result = ty::fold::shift_regions(self.tcx(), self.region_binders_passed, &ty);
 544         debug!("shift_regions: shifted result = {:?}", result);
 545
 546         result
 547     }
 548
 549     fn shift_region_through_binders(&self, region: ty::Region<'tcx>) -> ty::Region<'tcx> {
 550         if self.region_binders_passed == 0 || !region.has_escaping_regions() {
 551             return region;
 552         }
 553         self.tcx().mk_region(ty::fold::shift_region(*region, self.region_binders_passed))
 554     }
 555 }