src/librustc/middle/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::ty;
  14 use middle::ty_fold;
  15 use middle::ty_fold::{TypeFoldable, TypeFolder};
  16 use util::ppaux::Repr;
  17
  18 use std::fmt;
  19 use std::mem;
  20 use std::raw;
  21 use std::slice::{Items, MutItems};
  22 use std::vec::Vec;
  23 use syntax::codemap::{Span, DUMMY_SP};
  24
  25 ///////////////////////////////////////////////////////////////////////////
  26 // HomogeneousTuple3 trait
  27 //
  28 // This could be moved into standard library at some point.
  29
  30 trait HomogeneousTuple3<T> {
  31     fn len(&self) -> uint;
  32     fn as_slice<'a>(&'a self) -> &'a [T];
  33     fn as_mut_slice<'a>(&'a mut self) -> &'a mut [T];
  34     fn iter<'a>(&'a self) -> Items<'a, T>;
  35     fn mut_iter<'a>(&'a mut self) -> MutItems<'a, T>;
  36     fn get<'a>(&'a self, index: uint) -> Option<&'a T>;
  37     fn get_mut<'a>(&'a mut self, index: uint) -> Option<&'a mut T>;
  38 }
  39
  40 impl<T> HomogeneousTuple3<T> for (T, T, T) {
  41     fn len(&self) -> uint {
  42         3
  43     }
  44
  45     fn as_slice<'a>(&'a self) -> &'a [T] {
  46         unsafe {
  47             let ptr: *const T = mem::transmute(self);
  48             let slice = raw::Slice { data: ptr, len: 3 };
  49             mem::transmute(slice)
  50         }
  51     }
  52
  53     fn as_mut_slice<'a>(&'a mut self) -> &'a mut [T] {
  54         unsafe {
  55             let ptr: *const T = mem::transmute(self);
  56             let slice = raw::Slice { data: ptr, len: 3 };
  57             mem::transmute(slice)
  58         }
  59     }
  60
  61     fn iter<'a>(&'a self) -> Items<'a, T> {
  62         let slice: &'a [T] = self.as_slice();
  63         slice.iter()
  64     }
  65
  66     fn mut_iter<'a>(&'a mut self) -> MutItems<'a, T> {
  67         self.as_mut_slice().mut_iter()
  68     }
  69
  70     fn get<'a>(&'a self, index: uint) -> Option<&'a T> {
  71         self.as_slice().get(index)
  72     }
  73
  74     fn get_mut<'a>(&'a mut self, index: uint) -> Option<&'a mut T> {
  75         Some(&mut self.as_mut_slice()[index]) // wrong: fallible
  76     }
  77 }
  78
  79 ///////////////////////////////////////////////////////////////////////////
  80
  81 /**
  82  * A substitution mapping type/region parameters to new values. We
  83  * identify each in-scope parameter by an *index* and a *parameter
  84  * space* (which indices where the parameter is defined; see
  85  * `ParamSpace`).
  86  */
  87 #[deriving(Clone, PartialEq, Eq, Hash, Show)]
  88 pub struct Substs {
  89     pub types: VecPerParamSpace<ty::t>,
  90     pub regions: RegionSubsts,
  91 }
  92
  93 /**
  94  * Represents the values to use when substituting lifetime parameters.
  95  * If the value is `ErasedRegions`, then this subst is occurring during
  96  * trans, and all region parameters will be replaced with `ty::ReStatic`. */
  97 #[deriving(Clone, PartialEq, Eq, Hash, Show)]
  98 pub enum RegionSubsts {
  99     ErasedRegions,
 100     NonerasedRegions(VecPerParamSpace<ty::Region>)
 101 }
 102
 103 impl Substs {
 104     pub fn new(t: VecPerParamSpace<ty::t>,
 105                r: VecPerParamSpace<ty::Region>)
 106                -> Substs
 107     {
 108         Substs { types: t, regions: NonerasedRegions(r) }
 109     }
 110
 111     pub fn new_type(t: Vec<ty::t>,
 112                     r: Vec<ty::Region>)
 113                     -> Substs
 114     {
 115         Substs::new(VecPerParamSpace::new(t, Vec::new(), Vec::new()),
 116                     VecPerParamSpace::new(r, Vec::new(), Vec::new()))
 117     }
 118
 119     pub fn new_trait(t: Vec<ty::t>,
 120                      r: Vec<ty::Region>,
 121                      s: ty::t)
 122                     -> Substs
 123     {
 124         Substs::new(VecPerParamSpace::new(t, vec!(s), Vec::new()),
 125                     VecPerParamSpace::new(r, Vec::new(), Vec::new()))
 126     }
 127
 128     pub fn erased(t: VecPerParamSpace<ty::t>) -> Substs
 129     {
 130         Substs { types: t, regions: ErasedRegions }
 131     }
 132
 133     pub fn empty() -> Substs {
 134         Substs {
 135             types: VecPerParamSpace::empty(),
 136             regions: NonerasedRegions(VecPerParamSpace::empty()),
 137         }
 138     }
 139
 140     pub fn trans_empty() -> Substs {
 141         Substs {
 142             types: VecPerParamSpace::empty(),
 143             regions: ErasedRegions
 144         }
 145     }
 146
 147     pub fn is_noop(&self) -> bool {
 148         let regions_is_noop = match self.regions {
 149             ErasedRegions => false, // may be used to canonicalize
 150             NonerasedRegions(ref regions) => regions.is_empty(),
 151         };
 152
 153         regions_is_noop && self.types.is_empty()
 154     }
 155
 156     pub fn self_ty(&self) -> Option<ty::t> {
 157         self.types.get_self().map(|&t| t)
 158     }
 159
 160     pub fn with_self_ty(&self, self_ty: ty::t) -> Substs {
 161         assert!(self.self_ty().is_none());
 162         let mut s = (*self).clone();
 163         s.types.push(SelfSpace, self_ty);
 164         s
 165     }
 166
 167     pub fn regions<'a>(&'a self) -> &'a VecPerParamSpace<ty::Region> {
 168         /*!
 169          * Since ErasedRegions are only to be used in trans, most of
 170          * the compiler can use this method to easily access the set
 171          * of region substitutions.
 172          */
 173
 174         match self.regions {
 175             ErasedRegions => fail!("Erased regions only expected in trans"),
 176             NonerasedRegions(ref r) => r
 177         }
 178     }
 179
 180     pub fn mut_regions<'a>(&'a mut self) -> &'a mut VecPerParamSpace<ty::Region> {
 181         /*!
 182          * Since ErasedRegions are only to be used in trans, most of
 183          * the compiler can use this method to easily access the set
 184          * of region substitutions.
 185          */
 186
 187         match self.regions {
 188             ErasedRegions => fail!("Erased regions only expected in trans"),
 189             NonerasedRegions(ref mut r) => r
 190         }
 191     }
 192
 193     pub fn with_method_from(self, substs: &Substs) -> Substs {
 194         self.with_method(Vec::from_slice(substs.types.get_slice(FnSpace)),
 195                          Vec::from_slice(substs.regions().get_slice(FnSpace)))
 196     }
 197
 198     pub fn with_method(self,
 199                        m_types: Vec<ty::t>,
 200                        m_regions: Vec<ty::Region>)
 201                        -> Substs
 202     {
 203         let Substs { types, regions } = self;
 204         let types = types.with_vec(FnSpace, m_types);
 205         let regions = regions.map(m_regions,
 206                                   |r, m_regions| r.with_vec(FnSpace, m_regions));
 207         Substs { types: types, regions: regions }
 208     }
 209 }
 210
 211 impl RegionSubsts {
 212     fn map<A>(self,
 213               a: A,
 214               op: |VecPerParamSpace<ty::Region>, A| -> VecPerParamSpace<ty::Region>)
 215               -> RegionSubsts {
 216         match self {
 217             ErasedRegions => ErasedRegions,
 218             NonerasedRegions(r) => NonerasedRegions(op(r, a))
 219         }
 220     }
 221 }
 222
 223 ///////////////////////////////////////////////////////////////////////////
 224 // ParamSpace
 225
 226 #[deriving(PartialOrd, Ord, PartialEq, Eq,
 227            Clone, Hash, Encodable, Decodable, Show)]
 228 pub enum ParamSpace {
 229     TypeSpace, // Type parameters attached to a type definition, trait, or impl
 230     SelfSpace, // Self parameter on a trait
 231     FnSpace,   // Type parameters attached to a method or fn
 232 }
 233
 234 impl ParamSpace {
 235     pub fn all() -> [ParamSpace, ..3] {
 236         [TypeSpace, SelfSpace, FnSpace]
 237     }
 238
 239     pub fn to_uint(self) -> uint {
 240         match self {
 241             TypeSpace => 0,
 242             SelfSpace => 1,
 243             FnSpace => 2,
 244         }
 245     }
 246
 247     pub fn from_uint(u: uint) -> ParamSpace {
 248         match u {
 249             0 => TypeSpace,
 250             1 => SelfSpace,
 251             2 => FnSpace,
 252             _ => fail!("Invalid ParamSpace: {}", u)
 253         }
 254     }
 255 }
 256
 257 /**
 258  * Vector of things sorted by param space. Used to keep
 259  * the set of things declared on the type, self, or method
 260  * distinct.
 261  */
 262 #[deriving(PartialEq, Eq, Clone, Hash, Encodable, Decodable)]
 263 pub struct VecPerParamSpace<T> {
 264     // This was originally represented as a tuple with one Vec<T> for
 265     // each variant of ParamSpace, and that remains the abstraction
 266     // that it provides to its clients.
 267     //
 268     // Here is how the representation corresponds to the abstraction
 269     // i.e. the "abstraction function" AF:
 270     //
 271     // AF(self) = (self.content.slice_to(self.type_limit),
 272     //             self.content.slice(self.type_limit, self.self_limit),
 273     //             self.content.slice_from(self.self_limit))
 274     type_limit: uint,
 275     self_limit: uint,
 276     content: Vec<T>,
 277 }
 278
 279 impl<T:fmt::Show> fmt::Show for VecPerParamSpace<T> {
 280     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
 281         try!(write!(fmt, "VecPerParamSpace {{"));
 282         for space in ParamSpace::all().iter() {
 283             try!(write!(fmt, "{}: {}, ", *space, self.get_slice(*space)));
 284         }
 285         try!(write!(fmt, "}}"));
 286         Ok(())
 287     }
 288 }
 289
 290 impl<T:Clone> VecPerParamSpace<T> {
 291     pub fn push_all(&mut self, space: ParamSpace, values: &[T]) {
 292         // FIXME (#15435): slow; O(n^2); could enhance vec to make it O(n).
 293         for t in values.iter() {
 294             self.push(space, t.clone());
 295         }
 296     }
 297 }
 298
 299 impl<T> VecPerParamSpace<T> {
 300     fn limits(&self, space: ParamSpace) -> (uint, uint) {
 301         match space {
 302             TypeSpace => (0, self.type_limit),
 303             SelfSpace => (self.type_limit, self.self_limit),
 304             FnSpace => (self.self_limit, self.content.len()),
 305         }
 306     }
 307
 308     pub fn empty() -> VecPerParamSpace<T> {
 309         VecPerParamSpace {
 310             type_limit: 0,
 311             self_limit: 0,
 312             content: Vec::new()
 313         }
 314     }
 315
 316     pub fn params_from_type(types: Vec<T>) -> VecPerParamSpace<T> {
 317         VecPerParamSpace::empty().with_vec(TypeSpace, types)
 318     }
 319
 320     /// `t` is the type space.
 321     /// `s` is the self space.
 322     /// `f` is the fn space.
 323     pub fn new(t: Vec<T>, s: Vec<T>, f: Vec<T>) -> VecPerParamSpace<T> {
 324         let type_limit = t.len();
 325         let self_limit = t.len() + s.len();
 326         let mut content = t;
 327         content.push_all_move(s);
 328         content.push_all_move(f);
 329         VecPerParamSpace {
 330             type_limit: type_limit,
 331             self_limit: self_limit,
 332             content: content,
 333         }
 334     }
 335
 336     pub fn sort(t: Vec<T>, space: |&T| -> ParamSpace) -> VecPerParamSpace<T> {
 337         let mut result = VecPerParamSpace::empty();
 338         for t in t.move_iter() {
 339             result.push(space(&t), t);
 340         }
 341         result
 342     }
 343
 344     /// Appends `value` to the vector associated with `space`.
 345     ///
 346     /// Unlike the `push` method in `Vec`, this should not be assumed
 347     /// to be a cheap operation (even when amortized over many calls).
 348     pub fn push(&mut self, space: ParamSpace, value: T) {
 349         let (_, limit) = self.limits(space);
 350         match space {
 351             TypeSpace => { self.type_limit += 1; self.self_limit += 1; }
 352             SelfSpace => { self.self_limit += 1; }
 353             FnSpace   => {}
 354         }
 355         self.content.insert(limit, value);
 356     }
 357
 358     pub fn pop(&mut self, space: ParamSpace) -> Option<T> {
 359         let (start, limit) = self.limits(space);
 360         if start == limit {
 361             None
 362         } else {
 363             match space {
 364                 TypeSpace => { self.type_limit -= 1; self.self_limit -= 1; }
 365                 SelfSpace => { self.self_limit -= 1; }
 366                 FnSpace   => {}
 367             }
 368             self.content.remove(limit - 1)
 369         }
 370     }
 371
 372     pub fn truncate(&mut self, space: ParamSpace, len: uint) {
 373         // FIXME (#15435): slow; O(n^2); could enhance vec to make it O(n).
 374         while self.len(space) > len {
 375             self.pop(space);
 376         }
 377     }
 378
 379     pub fn replace(&mut self, space: ParamSpace, elems: Vec<T>) {
 380         // FIXME (#15435): slow; O(n^2); could enhance vec to make it O(n).
 381         self.truncate(space, 0);
 382         for t in elems.move_iter() {
 383             self.push(space, t);
 384         }
 385     }
 386
 387     pub fn get_self<'a>(&'a self) -> Option<&'a T> {
 388         let v = self.get_slice(SelfSpace);
 389         assert!(v.len() <= 1);
 390         if v.len() == 0 { None } else { Some(&v[0]) }
 391     }
 392
 393     pub fn len(&self, space: ParamSpace) -> uint {
 394         self.get_slice(space).len()
 395     }
 396
 397     pub fn is_empty_in(&self, space: ParamSpace) -> bool {
 398         self.len(space) == 0
 399     }
 400
 401     pub fn get_slice<'a>(&'a self, space: ParamSpace) -> &'a [T] {
 402         let (start, limit) = self.limits(space);
 403         self.content.slice(start, limit)
 404     }
 405
 406     pub fn get_mut_slice<'a>(&'a mut self, space: ParamSpace) -> &'a mut [T] {
 407         let (start, limit) = self.limits(space);
 408         self.content.mut_slice(start, limit)
 409     }
 410
 411     pub fn opt_get<'a>(&'a self,
 412                        space: ParamSpace,
 413                        index: uint)
 414                        -> Option<&'a T> {
 415         let v = self.get_slice(space);
 416         if index < v.len() { Some(&v[index]) } else { None }
 417     }
 418
 419     pub fn get<'a>(&'a self, space: ParamSpace, index: uint) -> &'a T {
 420         &self.get_slice(space)[index]
 421     }
 422
 423     pub fn get_mut<'a>(&'a mut self,
 424                        space: ParamSpace,
 425                        index: uint) -> &'a mut T {
 426         &mut self.get_mut_slice(space)[index]
 427     }
 428
 429     pub fn iter<'a>(&'a self) -> Items<'a,T> {
 430         self.content.iter()
 431     }
 432
 433     pub fn all_vecs(&self, pred: |&[T]| -> bool) -> bool {
 434         let spaces = [TypeSpace, SelfSpace, FnSpace];
 435         spaces.iter().all(|&space| { pred(self.get_slice(space)) })
 436     }
 437
 438     pub fn all(&self, pred: |&T| -> bool) -> bool {
 439         self.iter().all(pred)
 440     }
 441
 442     pub fn any(&self, pred: |&T| -> bool) -> bool {
 443         self.iter().any(pred)
 444     }
 445
 446     pub fn is_empty(&self) -> bool {
 447         self.all_vecs(|v| v.is_empty())
 448     }
 449
 450     pub fn map<U>(&self, pred: |&T| -> U) -> VecPerParamSpace<U> {
 451         // FIXME (#15418): this could avoid allocating the intermediate
 452         // Vec's, but note that the values of type_limit and self_limit
 453         // also need to be kept in sync during construction.
 454         VecPerParamSpace::new(
 455             self.get_slice(TypeSpace).iter().map(|p| pred(p)).collect(),
 456             self.get_slice(SelfSpace).iter().map(|p| pred(p)).collect(),
 457             self.get_slice(FnSpace).iter().map(|p| pred(p)).collect())
 458     }
 459
 460     pub fn map_rev<U>(&self, pred: |&T| -> U) -> VecPerParamSpace<U> {
 461         /*!
 462          * Executes the map but in reverse order. For hacky reasons, we rely
 463          * on this in table.
 464          *
 465          * FIXME(#5527) -- order of eval becomes irrelevant with newer
 466          * trait reform, which features an idempotent algorithm that
 467          * can be run to a fixed point
 468          */
 469
 470         let mut fns: Vec<U> = self.get_slice(FnSpace).iter().rev().map(|p| pred(p)).collect();
 471
 472         // NB: Calling foo.rev().map().rev() causes the calls to map
 473         // to occur in the wrong order. This was somewhat surprising
 474         // to me, though it makes total sense.
 475         fns.reverse();
 476
 477         let mut selfs: Vec<U> = self.get_slice(SelfSpace).iter().rev().map(|p| pred(p)).collect();
 478         selfs.reverse();
 479         let mut tys: Vec<U> = self.get_slice(TypeSpace).iter().rev().map(|p| pred(p)).collect();
 480         tys.reverse();
 481         VecPerParamSpace::new(tys, selfs, fns)
 482     }
 483
 484     pub fn split(self) -> (Vec<T>, Vec<T>, Vec<T>) {
 485         // FIXME (#15418): this does two traversals when in principle
 486         // one would suffice.  i.e. change to use `move_iter`.
 487         let VecPerParamSpace { type_limit, self_limit, content } = self;
 488         let mut i = 0;
 489         let (prefix, fn_vec) = content.partition(|_| {
 490             let on_left = i < self_limit;
 491             i += 1;
 492             on_left
 493         });
 494
 495         let mut i = 0;
 496         let (type_vec, self_vec) = prefix.partition(|_| {
 497             let on_left = i < type_limit;
 498             i += 1;
 499             on_left
 500         });
 501
 502         (type_vec, self_vec, fn_vec)
 503     }
 504
 505     pub fn with_vec(mut self, space: ParamSpace, vec: Vec<T>)
 506                     -> VecPerParamSpace<T>
 507     {
 508         assert!(self.is_empty_in(space));
 509         self.replace(space, vec);
 510         self
 511     }
 512 }
 513
 514 ///////////////////////////////////////////////////////////////////////////
 515 // Public trait `Subst`
 516 //
 517 // Just call `foo.subst(tcx, substs)` to perform a substitution across
 518 // `foo`. Or use `foo.subst_spanned(tcx, substs, Some(span))` when
 519 // there is more information available (for better errors).
 520
 521 pub trait Subst {
 522     fn subst(&self, tcx: &ty::ctxt, substs: &Substs) -> Self {
 523         self.subst_spanned(tcx, substs, None)
 524     }
 525
 526     fn subst_spanned(&self, tcx: &ty::ctxt,
 527                      substs: &Substs,
 528                      span: Option<Span>)
 529                      -> Self;
 530 }
 531
 532 impl<T:TypeFoldable> Subst for T {
 533     fn subst_spanned(&self,
 534                      tcx: &ty::ctxt,
 535                      substs: &Substs,
 536                      span: Option<Span>)
 537                      -> T
 538     {
 539         let mut folder = SubstFolder { tcx: tcx,
 540                                        substs: substs,
 541                                        span: span,
 542                                        root_ty: None,
 543                                        ty_stack_depth: 0 };
 544         (*self).fold_with(&mut folder)
 545     }
 546 }
 547
 548 ///////////////////////////////////////////////////////////////////////////
 549 // The actual substitution engine itself is a type folder.
 550
 551 struct SubstFolder<'a, 'tcx: 'a> {
 552     tcx: &'a ty::ctxt<'tcx>,
 553     substs: &'a Substs,
 554
 555     // The location for which the substitution is performed, if available.
 556     span: Option<Span>,
 557
 558     // The root type that is being substituted, if available.
 559     root_ty: Option<ty::t>,
 560
 561     // Depth of type stack
 562     ty_stack_depth: uint,
 563 }
 564
 565 impl<'a, 'tcx> TypeFolder<'tcx> for SubstFolder<'a, 'tcx> {
 566     fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> { self.tcx }
 567
 568     fn fold_region(&mut self, r: ty::Region) -> ty::Region {
 569         // Note: This routine only handles regions that are bound on
 570         // type declarations and other outer declarations, not those
 571         // bound in *fn types*. Region substitution of the bound
 572         // regions that appear in a function signature is done using
 573         // the specialized routine
 574         // `middle::typeck::check::regionmanip::replace_late_regions_in_fn_sig()`.
 575         match r {
 576             ty::ReEarlyBound(_, space, i, region_name) => {
 577                 match self.substs.regions {
 578                     ErasedRegions => ty::ReStatic,
 579                     NonerasedRegions(ref regions) =>
 580                         match regions.opt_get(space, i) {
 581                             Some(t) => *t,
 582                             None => {
 583                                 let span = self.span.unwrap_or(DUMMY_SP);
 584                                 self.tcx().sess.span_bug(
 585                                     span,
 586                                     format!("Type parameter out of range \
 587                                      when substituting in region {} (root type={}) \
 588                                      (space={}, index={})",
 589                                     region_name.as_str(),
 590                                     self.root_ty.repr(self.tcx()),
 591                                     space, i).as_slice());
 592                             }
 593                         }
 594                 }
 595             }
 596             _ => r
 597         }
 598     }
 599
 600     fn fold_ty(&mut self, t: ty::t) -> ty::t {
 601         if !ty::type_needs_subst(t) {
 602             return t;
 603         }
 604
 605         // track the root type we were asked to substitute
 606         let depth = self.ty_stack_depth;
 607         if depth == 0 {
 608             self.root_ty = Some(t);
 609         }
 610         self.ty_stack_depth += 1;
 611
 612         let t1 = match ty::get(t).sty {
 613             ty::ty_param(p) => {
 614                 check(self, p, t, self.substs.types.opt_get(p.space, p.idx))
 615             }
 616             _ => {
 617                 ty_fold::super_fold_ty(self, t)
 618             }
 619         };
 620
 621         assert_eq!(depth + 1, self.ty_stack_depth);
 622         self.ty_stack_depth -= 1;
 623         if depth == 0 {
 624             self.root_ty = None;
 625         }
 626
 627         return t1;
 628
 629         fn check(this: &SubstFolder,
 630                  p: ty::ParamTy,
 631                  source_ty: ty::t,
 632                  opt_ty: Option<&ty::t>)
 633                  -> ty::t {
 634             match opt_ty {
 635                 Some(t) => *t,
 636                 None => {
 637                     let span = this.span.unwrap_or(DUMMY_SP);
 638                     this.tcx().sess.span_bug(
 639                         span,
 640                         format!("Type parameter `{}` ({}) out of range \
 641                                  when substituting (root type={})",
 642                                 p.repr(this.tcx()),
 643                                 source_ty.repr(this.tcx()),
 644                                 this.root_ty.repr(this.tcx())).as_slice());
 645                 }
 646             }
 647         }
 648     }
 649 }