1 // Type substitutions. 2 3 use crate::mir; 4 use crate::ty::codec::{TyDecoder, TyEncoder}; 5 use crate::ty::fold::{TypeFoldable, TypeFolder, TypeVisitor}; 6 use crate::ty::sty::{ClosureSubsts, GeneratorSubsts, InlineConstSubsts}; 7 use crate::ty::{self, Lift, List, ParamConst, Ty, TyCtxt}; 8 9 use rustc_hir::def_id::DefId; 10 use rustc_macros::HashStable; 11 use rustc_serialize::{self, Decodable, Encodable}; 12 use rustc_span::{Span, DUMMY_SP}; 13 use smallvec::SmallVec; 14 15 use core::intrinsics; 16 use std::cmp::Ordering; 17 use std::fmt; 18 use std::marker::PhantomData; 19 use std::mem; 20 use std::num::NonZeroUsize; 21 use std::ops::ControlFlow; 22 23 /// An entity in the Rust type system, which can be one of 24 /// several kinds (types, lifetimes, and consts). 25 /// To reduce memory usage, a `GenericArg` is an interned pointer, 26 /// with the lowest 2 bits being reserved for a tag to 27 /// indicate the type (`Ty`, `Region`, or `Const`) it points to. 28 #[derive(Copy, Clone, PartialEq, Eq, Hash)] 29 pub struct GenericArg<'tcx> { 30 ptr: NonZeroUsize, 31 marker: PhantomData<(Ty<'tcx>, ty::Region<'tcx>, &'tcx ty::Const<'tcx>)>, 32 } 33 34 const TAG_MASK: usize = 0b11; 35 const TYPE_TAG: usize = 0b00; 36 const REGION_TAG: usize = 0b01; 37 const CONST_TAG: usize = 0b10; 38 39 #[derive(Debug, TyEncodable, TyDecodable, PartialEq, Eq, PartialOrd, Ord, HashStable)] 40 pub enum GenericArgKind<'tcx> { 41 Lifetime(ty::Region<'tcx>), 42 Type(Ty<'tcx>), 43 Const(&'tcx ty::Const<'tcx>), 44 } 45 46 impl<'tcx> GenericArgKind<'tcx> { pack(self) -> GenericArg<'tcx>47 fn pack(self) -> GenericArg<'tcx> { 48 let (tag, ptr) = match self { 49 GenericArgKind::Lifetime(lt) => { 50 // Ensure we can use the tag bits. 51 assert_eq!(mem::align_of_val(lt) & TAG_MASK, 0); 52 (REGION_TAG, lt as *const _ as usize) 53 } 54 GenericArgKind::Type(ty) => { 55 // Ensure we can use the tag bits. 56 assert_eq!(mem::align_of_val(ty) & TAG_MASK, 0); 57 (TYPE_TAG, ty as *const _ as usize) 58 } 59 GenericArgKind::Const(ct) => { 60 // Ensure we can use the tag bits. 61 assert_eq!(mem::align_of_val(ct) & TAG_MASK, 0); 62 (CONST_TAG, ct as *const _ as usize) 63 } 64 }; 65 66 GenericArg { ptr: unsafe { NonZeroUsize::new_unchecked(ptr | tag) }, marker: PhantomData } 67 } 68 } 69 70 impl fmt::Debug for GenericArg<'tcx> { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result71 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 72 match self.unpack() { 73 GenericArgKind::Lifetime(lt) => lt.fmt(f), 74 GenericArgKind::Type(ty) => ty.fmt(f), 75 GenericArgKind::Const(ct) => ct.fmt(f), 76 } 77 } 78 } 79 80 impl<'tcx> Ord for GenericArg<'tcx> { cmp(&self, other: &GenericArg<'_>) -> Ordering81 fn cmp(&self, other: &GenericArg<'_>) -> Ordering { 82 self.unpack().cmp(&other.unpack()) 83 } 84 } 85 86 impl<'tcx> PartialOrd for GenericArg<'tcx> { partial_cmp(&self, other: &GenericArg<'_>) -> Option<Ordering>87 fn partial_cmp(&self, other: &GenericArg<'_>) -> Option<Ordering> { 88 Some(self.cmp(&other)) 89 } 90 } 91 92 impl<'tcx> From<ty::Region<'tcx>> for GenericArg<'tcx> { from(r: ty::Region<'tcx>) -> GenericArg<'tcx>93 fn from(r: ty::Region<'tcx>) -> GenericArg<'tcx> { 94 GenericArgKind::Lifetime(r).pack() 95 } 96 } 97 98 impl<'tcx> From<Ty<'tcx>> for GenericArg<'tcx> { from(ty: Ty<'tcx>) -> GenericArg<'tcx>99 fn from(ty: Ty<'tcx>) -> GenericArg<'tcx> { 100 GenericArgKind::Type(ty).pack() 101 } 102 } 103 104 impl<'tcx> From<&'tcx ty::Const<'tcx>> for GenericArg<'tcx> { from(c: &'tcx ty::Const<'tcx>) -> GenericArg<'tcx>105 fn from(c: &'tcx ty::Const<'tcx>) -> GenericArg<'tcx> { 106 GenericArgKind::Const(c).pack() 107 } 108 } 109 110 impl<'tcx> GenericArg<'tcx> { 111 #[inline] unpack(self) -> GenericArgKind<'tcx>112 pub fn unpack(self) -> GenericArgKind<'tcx> { 113 let ptr = self.ptr.get(); 114 unsafe { 115 match ptr & TAG_MASK { 116 REGION_TAG => GenericArgKind::Lifetime(&*((ptr & !TAG_MASK) as *const _)), 117 TYPE_TAG => GenericArgKind::Type(&*((ptr & !TAG_MASK) as *const _)), 118 CONST_TAG => GenericArgKind::Const(&*((ptr & !TAG_MASK) as *const _)), 119 _ => intrinsics::unreachable(), 120 } 121 } 122 } 123 124 /// Unpack the `GenericArg` as a type when it is known certainly to be a type. 125 /// This is true in cases where `Substs` is used in places where the kinds are known 126 /// to be limited (e.g. in tuples, where the only parameters are type parameters). expect_ty(self) -> Ty<'tcx>127 pub fn expect_ty(self) -> Ty<'tcx> { 128 match self.unpack() { 129 GenericArgKind::Type(ty) => ty, 130 _ => bug!("expected a type, but found another kind"), 131 } 132 } 133 134 /// Unpack the `GenericArg` as a const when it is known certainly to be a const. expect_const(self) -> &'tcx ty::Const<'tcx>135 pub fn expect_const(self) -> &'tcx ty::Const<'tcx> { 136 match self.unpack() { 137 GenericArgKind::Const(c) => c, 138 _ => bug!("expected a const, but found another kind"), 139 } 140 } 141 } 142 143 impl<'a, 'tcx> Lift<'tcx> for GenericArg<'a> { 144 type Lifted = GenericArg<'tcx>; 145 lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted>146 fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> { 147 match self.unpack() { 148 GenericArgKind::Lifetime(lt) => tcx.lift(lt).map(|lt| lt.into()), 149 GenericArgKind::Type(ty) => tcx.lift(ty).map(|ty| ty.into()), 150 GenericArgKind::Const(ct) => tcx.lift(ct).map(|ct| ct.into()), 151 } 152 } 153 } 154 155 impl<'tcx> TypeFoldable<'tcx> for GenericArg<'tcx> { super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self156 fn super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self { 157 match self.unpack() { 158 GenericArgKind::Lifetime(lt) => lt.fold_with(folder).into(), 159 GenericArgKind::Type(ty) => ty.fold_with(folder).into(), 160 GenericArgKind::Const(ct) => ct.fold_with(folder).into(), 161 } 162 } 163 super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy>164 fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> { 165 match self.unpack() { 166 GenericArgKind::Lifetime(lt) => lt.visit_with(visitor), 167 GenericArgKind::Type(ty) => ty.visit_with(visitor), 168 GenericArgKind::Const(ct) => ct.visit_with(visitor), 169 } 170 } 171 } 172 173 impl<'tcx, E: TyEncoder<'tcx>> Encodable<E> for GenericArg<'tcx> { encode(&self, e: &mut E) -> Result<(), E::Error>174 fn encode(&self, e: &mut E) -> Result<(), E::Error> { 175 self.unpack().encode(e) 176 } 177 } 178 179 impl<'tcx, D: TyDecoder<'tcx>> Decodable<D> for GenericArg<'tcx> { decode(d: &mut D) -> Result<GenericArg<'tcx>, D::Error>180 fn decode(d: &mut D) -> Result<GenericArg<'tcx>, D::Error> { 181 Ok(GenericArgKind::decode(d)?.pack()) 182 } 183 } 184 185 /// A substitution mapping generic parameters to new values. 186 pub type InternalSubsts<'tcx> = List<GenericArg<'tcx>>; 187 188 pub type SubstsRef<'tcx> = &'tcx InternalSubsts<'tcx>; 189 190 impl<'a, 'tcx> InternalSubsts<'tcx> { 191 /// Interpret these substitutions as the substitutions of a closure type. 192 /// Closure substitutions have a particular structure controlled by the 193 /// compiler that encodes information like the signature and closure kind; 194 /// see `ty::ClosureSubsts` struct for more comments. as_closure(&'a self) -> ClosureSubsts<'a>195 pub fn as_closure(&'a self) -> ClosureSubsts<'a> { 196 ClosureSubsts { substs: self } 197 } 198 199 /// Interpret these substitutions as the substitutions of a generator type. 200 /// Generator substitutions have a particular structure controlled by the 201 /// compiler that encodes information like the signature and generator kind; 202 /// see `ty::GeneratorSubsts` struct for more comments. as_generator(&'tcx self) -> GeneratorSubsts<'tcx>203 pub fn as_generator(&'tcx self) -> GeneratorSubsts<'tcx> { 204 GeneratorSubsts { substs: self } 205 } 206 207 /// Interpret these substitutions as the substitutions of an inline const. 208 /// Inline const substitutions have a particular structure controlled by the 209 /// compiler that encodes information like the inferred type; 210 /// see `ty::InlineConstSubsts` struct for more comments. as_inline_const(&'tcx self) -> InlineConstSubsts<'tcx>211 pub fn as_inline_const(&'tcx self) -> InlineConstSubsts<'tcx> { 212 InlineConstSubsts { substs: self } 213 } 214 215 /// Creates an `InternalSubsts` that maps each generic parameter to itself. identity_for_item(tcx: TyCtxt<'tcx>, def_id: DefId) -> SubstsRef<'tcx>216 pub fn identity_for_item(tcx: TyCtxt<'tcx>, def_id: DefId) -> SubstsRef<'tcx> { 217 Self::for_item(tcx, def_id, |param, _| tcx.mk_param_from_def(param)) 218 } 219 220 /// Creates an `InternalSubsts` for generic parameter definitions, 221 /// by calling closures to obtain each kind. 222 /// The closures get to observe the `InternalSubsts` as they're 223 /// being built, which can be used to correctly 224 /// substitute defaults of generic parameters. for_item<F>(tcx: TyCtxt<'tcx>, def_id: DefId, mut mk_kind: F) -> SubstsRef<'tcx> where F: FnMut(&ty::GenericParamDef, &[GenericArg<'tcx>]) -> GenericArg<'tcx>,225 pub fn for_item<F>(tcx: TyCtxt<'tcx>, def_id: DefId, mut mk_kind: F) -> SubstsRef<'tcx> 226 where 227 F: FnMut(&ty::GenericParamDef, &[GenericArg<'tcx>]) -> GenericArg<'tcx>, 228 { 229 let defs = tcx.generics_of(def_id); 230 let count = defs.count(); 231 let mut substs = SmallVec::with_capacity(count); 232 Self::fill_item(&mut substs, tcx, defs, &mut mk_kind); 233 tcx.intern_substs(&substs) 234 } 235 extend_to<F>(&self, tcx: TyCtxt<'tcx>, def_id: DefId, mut mk_kind: F) -> SubstsRef<'tcx> where F: FnMut(&ty::GenericParamDef, &[GenericArg<'tcx>]) -> GenericArg<'tcx>,236 pub fn extend_to<F>(&self, tcx: TyCtxt<'tcx>, def_id: DefId, mut mk_kind: F) -> SubstsRef<'tcx> 237 where 238 F: FnMut(&ty::GenericParamDef, &[GenericArg<'tcx>]) -> GenericArg<'tcx>, 239 { 240 Self::for_item(tcx, def_id, |param, substs| { 241 self.get(param.index as usize).cloned().unwrap_or_else(|| mk_kind(param, substs)) 242 }) 243 } 244 fill_item<F>( substs: &mut SmallVec<[GenericArg<'tcx>; 8]>, tcx: TyCtxt<'tcx>, defs: &ty::Generics, mk_kind: &mut F, ) where F: FnMut(&ty::GenericParamDef, &[GenericArg<'tcx>]) -> GenericArg<'tcx>,245 pub fn fill_item<F>( 246 substs: &mut SmallVec<[GenericArg<'tcx>; 8]>, 247 tcx: TyCtxt<'tcx>, 248 defs: &ty::Generics, 249 mk_kind: &mut F, 250 ) where 251 F: FnMut(&ty::GenericParamDef, &[GenericArg<'tcx>]) -> GenericArg<'tcx>, 252 { 253 if let Some(def_id) = defs.parent { 254 let parent_defs = tcx.generics_of(def_id); 255 Self::fill_item(substs, tcx, parent_defs, mk_kind); 256 } 257 Self::fill_single(substs, defs, mk_kind) 258 } 259 fill_single<F>( substs: &mut SmallVec<[GenericArg<'tcx>; 8]>, defs: &ty::Generics, mk_kind: &mut F, ) where F: FnMut(&ty::GenericParamDef, &[GenericArg<'tcx>]) -> GenericArg<'tcx>,260 pub fn fill_single<F>( 261 substs: &mut SmallVec<[GenericArg<'tcx>; 8]>, 262 defs: &ty::Generics, 263 mk_kind: &mut F, 264 ) where 265 F: FnMut(&ty::GenericParamDef, &[GenericArg<'tcx>]) -> GenericArg<'tcx>, 266 { 267 substs.reserve(defs.params.len()); 268 for param in &defs.params { 269 let kind = mk_kind(param, substs); 270 assert_eq!(param.index as usize, substs.len()); 271 substs.push(kind); 272 } 273 } 274 is_noop(&self) -> bool275 pub fn is_noop(&self) -> bool { 276 self.is_empty() 277 } 278 279 #[inline] types(&'a self) -> impl DoubleEndedIterator<Item = Ty<'tcx>> + 'a280 pub fn types(&'a self) -> impl DoubleEndedIterator<Item = Ty<'tcx>> + 'a { 281 self.iter() 282 .filter_map(|k| if let GenericArgKind::Type(ty) = k.unpack() { Some(ty) } else { None }) 283 } 284 285 #[inline] regions(&'a self) -> impl DoubleEndedIterator<Item = ty::Region<'tcx>> + 'a286 pub fn regions(&'a self) -> impl DoubleEndedIterator<Item = ty::Region<'tcx>> + 'a { 287 self.iter().filter_map(|k| { 288 if let GenericArgKind::Lifetime(lt) = k.unpack() { Some(lt) } else { None } 289 }) 290 } 291 292 #[inline] consts(&'a self) -> impl DoubleEndedIterator<Item = &'tcx ty::Const<'tcx>> + 'a293 pub fn consts(&'a self) -> impl DoubleEndedIterator<Item = &'tcx ty::Const<'tcx>> + 'a { 294 self.iter().filter_map(|k| { 295 if let GenericArgKind::Const(ct) = k.unpack() { Some(ct) } else { None } 296 }) 297 } 298 299 #[inline] non_erasable_generics( &'a self, ) -> impl DoubleEndedIterator<Item = GenericArgKind<'tcx>> + 'a300 pub fn non_erasable_generics( 301 &'a self, 302 ) -> impl DoubleEndedIterator<Item = GenericArgKind<'tcx>> + 'a { 303 self.iter().filter_map(|k| match k.unpack() { 304 GenericArgKind::Lifetime(_) => None, 305 generic => Some(generic), 306 }) 307 } 308 309 #[inline] type_at(&self, i: usize) -> Ty<'tcx>310 pub fn type_at(&self, i: usize) -> Ty<'tcx> { 311 if let GenericArgKind::Type(ty) = self[i].unpack() { 312 ty 313 } else { 314 bug!("expected type for param #{} in {:?}", i, self); 315 } 316 } 317 318 #[inline] region_at(&self, i: usize) -> ty::Region<'tcx>319 pub fn region_at(&self, i: usize) -> ty::Region<'tcx> { 320 if let GenericArgKind::Lifetime(lt) = self[i].unpack() { 321 lt 322 } else { 323 bug!("expected region for param #{} in {:?}", i, self); 324 } 325 } 326 327 #[inline] const_at(&self, i: usize) -> &'tcx ty::Const<'tcx>328 pub fn const_at(&self, i: usize) -> &'tcx ty::Const<'tcx> { 329 if let GenericArgKind::Const(ct) = self[i].unpack() { 330 ct 331 } else { 332 bug!("expected const for param #{} in {:?}", i, self); 333 } 334 } 335 336 #[inline] type_for_def(&self, def: &ty::GenericParamDef) -> GenericArg<'tcx>337 pub fn type_for_def(&self, def: &ty::GenericParamDef) -> GenericArg<'tcx> { 338 self.type_at(def.index as usize).into() 339 } 340 341 /// Transform from substitutions for a child of `source_ancestor` 342 /// (e.g., a trait or impl) to substitutions for the same child 343 /// in a different item, with `target_substs` as the base for 344 /// the target impl/trait, with the source child-specific 345 /// parameters (e.g., method parameters) on top of that base. 346 /// 347 /// For example given: 348 /// 349 /// ```no_run 350 /// trait X<S> { fn f<T>(); } 351 /// impl<U> X<U> for U { fn f<V>() {} } 352 /// ``` 353 /// 354 /// * If `self` is `[Self, S, T]`: the identity substs of `f` in the trait. 355 /// * If `source_ancestor` is the def_id of the trait. 356 /// * If `target_substs` is `[U]`, the substs for the impl. 357 /// * Then we will return `[U, T]`, the subst for `f` in the impl that 358 /// are needed for it to match the trait. rebase_onto( &self, tcx: TyCtxt<'tcx>, source_ancestor: DefId, target_substs: SubstsRef<'tcx>, ) -> SubstsRef<'tcx>359 pub fn rebase_onto( 360 &self, 361 tcx: TyCtxt<'tcx>, 362 source_ancestor: DefId, 363 target_substs: SubstsRef<'tcx>, 364 ) -> SubstsRef<'tcx> { 365 let defs = tcx.generics_of(source_ancestor); 366 tcx.mk_substs(target_substs.iter().chain(self.iter().skip(defs.params.len()))) 367 } 368 truncate_to(&self, tcx: TyCtxt<'tcx>, generics: &ty::Generics) -> SubstsRef<'tcx>369 pub fn truncate_to(&self, tcx: TyCtxt<'tcx>, generics: &ty::Generics) -> SubstsRef<'tcx> { 370 tcx.mk_substs(self.iter().take(generics.count())) 371 } 372 } 373 374 impl<'tcx> TypeFoldable<'tcx> for SubstsRef<'tcx> { super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self375 fn super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self { 376 // This code is hot enough that it's worth specializing for the most 377 // common length lists, to avoid the overhead of `SmallVec` creation. 378 // The match arms are in order of frequency. The 1, 2, and 0 cases are 379 // typically hit in 90--99.99% of cases. When folding doesn't change 380 // the substs, it's faster to reuse the existing substs rather than 381 // calling `intern_substs`. 382 match self.len() { 383 1 => { 384 let param0 = self[0].fold_with(folder); 385 if param0 == self[0] { self } else { folder.tcx().intern_substs(&[param0]) } 386 } 387 2 => { 388 let param0 = self[0].fold_with(folder); 389 let param1 = self[1].fold_with(folder); 390 if param0 == self[0] && param1 == self[1] { 391 self 392 } else { 393 folder.tcx().intern_substs(&[param0, param1]) 394 } 395 } 396 0 => self, 397 _ => { 398 let params: SmallVec<[_; 8]> = self.iter().map(|k| k.fold_with(folder)).collect(); 399 if params[..] == self[..] { self } else { folder.tcx().intern_substs(¶ms) } 400 } 401 } 402 } 403 super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy>404 fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> { 405 self.iter().try_for_each(|t| t.visit_with(visitor)) 406 } 407 } 408 409 /////////////////////////////////////////////////////////////////////////// 410 // Public trait `Subst` 411 // 412 // Just call `foo.subst(tcx, substs)` to perform a substitution across 413 // `foo`. Or use `foo.subst_spanned(tcx, substs, Some(span))` when 414 // there is more information available (for better errors). 415 416 pub trait Subst<'tcx>: Sized { subst(self, tcx: TyCtxt<'tcx>, substs: &[GenericArg<'tcx>]) -> Self417 fn subst(self, tcx: TyCtxt<'tcx>, substs: &[GenericArg<'tcx>]) -> Self { 418 self.subst_spanned(tcx, substs, None) 419 } 420 subst_spanned( self, tcx: TyCtxt<'tcx>, substs: &[GenericArg<'tcx>], span: Option<Span>, ) -> Self421 fn subst_spanned( 422 self, 423 tcx: TyCtxt<'tcx>, 424 substs: &[GenericArg<'tcx>], 425 span: Option<Span>, 426 ) -> Self; 427 } 428 429 impl<'tcx, T: TypeFoldable<'tcx>> Subst<'tcx> for T { subst_spanned( self, tcx: TyCtxt<'tcx>, substs: &[GenericArg<'tcx>], span: Option<Span>, ) -> T430 fn subst_spanned( 431 self, 432 tcx: TyCtxt<'tcx>, 433 substs: &[GenericArg<'tcx>], 434 span: Option<Span>, 435 ) -> T { 436 let mut folder = SubstFolder { tcx, substs, span, binders_passed: 0 }; 437 self.fold_with(&mut folder) 438 } 439 } 440 441 /////////////////////////////////////////////////////////////////////////// 442 // The actual substitution engine itself is a type folder. 443 444 struct SubstFolder<'a, 'tcx> { 445 tcx: TyCtxt<'tcx>, 446 substs: &'a [GenericArg<'tcx>], 447 448 /// The location for which the substitution is performed, if available. 449 span: Option<Span>, 450 451 /// Number of region binders we have passed through while doing the substitution 452 binders_passed: u32, 453 } 454 455 impl<'a, 'tcx> TypeFolder<'tcx> for SubstFolder<'a, 'tcx> { tcx<'b>(&'b self) -> TyCtxt<'tcx>456 fn tcx<'b>(&'b self) -> TyCtxt<'tcx> { 457 self.tcx 458 } 459 fold_binder<T: TypeFoldable<'tcx>>( &mut self, t: ty::Binder<'tcx, T>, ) -> ty::Binder<'tcx, T>460 fn fold_binder<T: TypeFoldable<'tcx>>( 461 &mut self, 462 t: ty::Binder<'tcx, T>, 463 ) -> ty::Binder<'tcx, T> { 464 self.binders_passed += 1; 465 let t = t.super_fold_with(self); 466 self.binders_passed -= 1; 467 t 468 } 469 fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx>470 fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { 471 // Note: This routine only handles regions that are bound on 472 // type declarations and other outer declarations, not those 473 // bound in *fn types*. Region substitution of the bound 474 // regions that appear in a function signature is done using 475 // the specialized routine `ty::replace_late_regions()`. 476 match *r { 477 ty::ReEarlyBound(data) => { 478 let rk = self.substs.get(data.index as usize).map(|k| k.unpack()); 479 match rk { 480 Some(GenericArgKind::Lifetime(lt)) => self.shift_region_through_binders(lt), 481 _ => { 482 let span = self.span.unwrap_or(DUMMY_SP); 483 let msg = format!( 484 "Region parameter out of range \ 485 when substituting in region {} (index={})", 486 data.name, data.index 487 ); 488 span_bug!(span, "{}", msg); 489 } 490 } 491 } 492 _ => r, 493 } 494 } 495 fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx>496 fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { 497 if !t.potentially_needs_subst() { 498 return t; 499 } 500 501 match *t.kind() { 502 ty::Param(p) => self.ty_for_param(p, t), 503 _ => t.super_fold_with(self), 504 } 505 } 506 fold_const(&mut self, c: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx>507 fn fold_const(&mut self, c: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> { 508 if let ty::ConstKind::Param(p) = c.val { 509 self.const_for_param(p, c) 510 } else { 511 c.super_fold_with(self) 512 } 513 } 514 515 #[inline] fold_mir_const(&mut self, c: mir::ConstantKind<'tcx>) -> mir::ConstantKind<'tcx>516 fn fold_mir_const(&mut self, c: mir::ConstantKind<'tcx>) -> mir::ConstantKind<'tcx> { 517 c.super_fold_with(self) 518 } 519 } 520 521 impl<'a, 'tcx> SubstFolder<'a, 'tcx> { ty_for_param(&self, p: ty::ParamTy, source_ty: Ty<'tcx>) -> Ty<'tcx>522 fn ty_for_param(&self, p: ty::ParamTy, source_ty: Ty<'tcx>) -> Ty<'tcx> { 523 // Look up the type in the substitutions. It really should be in there. 524 let opt_ty = self.substs.get(p.index as usize).map(|k| k.unpack()); 525 let ty = match opt_ty { 526 Some(GenericArgKind::Type(ty)) => ty, 527 Some(kind) => { 528 let span = self.span.unwrap_or(DUMMY_SP); 529 span_bug!( 530 span, 531 "expected type for `{:?}` ({:?}/{}) but found {:?} \ 532 when substituting, substs={:?}", 533 p, 534 source_ty, 535 p.index, 536 kind, 537 self.substs, 538 ); 539 } 540 None => { 541 let span = self.span.unwrap_or(DUMMY_SP); 542 span_bug!( 543 span, 544 "type parameter `{:?}` ({:?}/{}) out of range \ 545 when substituting, substs={:?}", 546 p, 547 source_ty, 548 p.index, 549 self.substs, 550 ); 551 } 552 }; 553 554 self.shift_vars_through_binders(ty) 555 } 556 const_for_param( &self, p: ParamConst, source_ct: &'tcx ty::Const<'tcx>, ) -> &'tcx ty::Const<'tcx>557 fn const_for_param( 558 &self, 559 p: ParamConst, 560 source_ct: &'tcx ty::Const<'tcx>, 561 ) -> &'tcx ty::Const<'tcx> { 562 // Look up the const in the substitutions. It really should be in there. 563 let opt_ct = self.substs.get(p.index as usize).map(|k| k.unpack()); 564 let ct = match opt_ct { 565 Some(GenericArgKind::Const(ct)) => ct, 566 Some(kind) => { 567 let span = self.span.unwrap_or(DUMMY_SP); 568 span_bug!( 569 span, 570 "expected const for `{:?}` ({:?}/{}) but found {:?} \ 571 when substituting substs={:?}", 572 p, 573 source_ct, 574 p.index, 575 kind, 576 self.substs, 577 ); 578 } 579 None => { 580 let span = self.span.unwrap_or(DUMMY_SP); 581 span_bug!( 582 span, 583 "const parameter `{:?}` ({:?}/{}) out of range \ 584 when substituting substs={:?}", 585 p, 586 source_ct, 587 p.index, 588 self.substs, 589 ); 590 } 591 }; 592 593 self.shift_vars_through_binders(ct) 594 } 595 596 /// It is sometimes necessary to adjust the De Bruijn indices during substitution. This occurs 597 /// when we are substituting a type with escaping bound vars into a context where we have 598 /// passed through binders. That's quite a mouthful. Let's see an example: 599 /// 600 /// ``` 601 /// type Func<A> = fn(A); 602 /// type MetaFunc = for<'a> fn(Func<&'a i32>) 603 /// ``` 604 /// 605 /// The type `MetaFunc`, when fully expanded, will be 606 /// 607 /// for<'a> fn(fn(&'a i32)) 608 /// ^~ ^~ ^~~ 609 /// | | | 610 /// | | DebruijnIndex of 2 611 /// Binders 612 /// 613 /// Here the `'a` lifetime is bound in the outer function, but appears as an argument of the 614 /// inner one. Therefore, that appearance will have a DebruijnIndex of 2, because we must skip 615 /// over the inner binder (remember that we count De Bruijn indices from 1). However, in the 616 /// definition of `MetaFunc`, the binder is not visible, so the type `&'a i32` will have a 617 /// De Bruijn index of 1. It's only during the substitution that we can see we must increase the 618 /// depth by 1 to account for the binder that we passed through. 619 /// 620 /// As a second example, consider this twist: 621 /// 622 /// ``` 623 /// type FuncTuple<A> = (A,fn(A)); 624 /// type MetaFuncTuple = for<'a> fn(FuncTuple<&'a i32>) 625 /// ``` 626 /// 627 /// Here the final type will be: 628 /// 629 /// for<'a> fn((&'a i32, fn(&'a i32))) 630 /// ^~~ ^~~ 631 /// | | 632 /// DebruijnIndex of 1 | 633 /// DebruijnIndex of 2 634 /// 635 /// As indicated in the diagram, here the same type `&'a i32` is substituted once, but in the 636 /// first case we do not increase the De Bruijn index and in the second case we do. The reason 637 /// is that only in the second case have we passed through a fn binder. shift_vars_through_binders<T: TypeFoldable<'tcx>>(&self, val: T) -> T638 fn shift_vars_through_binders<T: TypeFoldable<'tcx>>(&self, val: T) -> T { 639 debug!( 640 "shift_vars(val={:?}, binders_passed={:?}, has_escaping_bound_vars={:?})", 641 val, 642 self.binders_passed, 643 val.has_escaping_bound_vars() 644 ); 645 646 if self.binders_passed == 0 || !val.has_escaping_bound_vars() { 647 return val; 648 } 649 650 let result = ty::fold::shift_vars(self.tcx(), val, self.binders_passed); 651 debug!("shift_vars: shifted result = {:?}", result); 652 653 result 654 } 655 shift_region_through_binders(&self, region: ty::Region<'tcx>) -> ty::Region<'tcx>656 fn shift_region_through_binders(&self, region: ty::Region<'tcx>) -> ty::Region<'tcx> { 657 if self.binders_passed == 0 || !region.has_escaping_bound_vars() { 658 return region; 659 } 660 ty::fold::shift_region(self.tcx, region, self.binders_passed) 661 } 662 } 663 664 /// Stores the user-given substs to reach some fully qualified path 665 /// (e.g., `<T>::Item` or `<T as Trait>::Item`). 666 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TyEncodable, TyDecodable)] 667 #[derive(HashStable, TypeFoldable, Lift)] 668 pub struct UserSubsts<'tcx> { 669 /// The substitutions for the item as given by the user. 670 pub substs: SubstsRef<'tcx>, 671 672 /// The self type, in the case of a `<T>::Item` path (when applied 673 /// to an inherent impl). See `UserSelfTy` below. 674 pub user_self_ty: Option<UserSelfTy<'tcx>>, 675 } 676 677 /// Specifies the user-given self type. In the case of a path that 678 /// refers to a member in an inherent impl, this self type is 679 /// sometimes needed to constrain the type parameters on the impl. For 680 /// example, in this code: 681 /// 682 /// ``` 683 /// struct Foo<T> { } 684 /// impl<A> Foo<A> { fn method() { } } 685 /// ``` 686 /// 687 /// when you then have a path like `<Foo<&'static u32>>::method`, 688 /// this struct would carry the `DefId` of the impl along with the 689 /// self type `Foo<u32>`. Then we can instantiate the parameters of 690 /// the impl (with the substs from `UserSubsts`) and apply those to 691 /// the self type, giving `Foo<?A>`. Finally, we unify that with 692 /// the self type here, which contains `?A` to be `&'static u32` 693 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TyEncodable, TyDecodable)] 694 #[derive(HashStable, TypeFoldable, Lift)] 695 pub struct UserSelfTy<'tcx> { 696 pub impl_def_id: DefId, 697 pub self_ty: Ty<'tcx>, 698 } 699