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