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::TypeFolder;
  16 use util::ppaux::Repr;
  17
  18 use std::rc::Rc;
  19 use syntax::codemap::Span;
  20 use syntax::owned_slice::OwnedSlice;
  21
  22 ///////////////////////////////////////////////////////////////////////////
  23 // Public trait `Subst`
  24 //
  25 // Just call `foo.subst(tcx, substs)` to perform a substitution across
  26 // `foo`.
  27 // Or use `foo.subst_spanned(tcx, substs, Some(span))` when there is more
  28 // information available (for better errors).
  29
  30 pub trait Subst {
  31     fn subst(&self, tcx: &ty::ctxt, substs: &ty::substs) -> Self {
  32         self.subst_spanned(tcx, substs, None)
  33     }
  34     fn subst_spanned(&self, tcx: &ty::ctxt,
  35                      substs: &ty::substs,
  36                      span: Option<Span>) -> Self;
  37 }
  38
  39 ///////////////////////////////////////////////////////////////////////////
  40 // Substitution over types
  41 //
  42 // Because this is so common, we make a special optimization to avoid
  43 // doing anything if `substs` is a no-op.  I tried to generalize these
  44 // to all subst methods but ran into trouble due to the limitations of
  45 // our current method/trait matching algorithm. - Niko
  46
  47 impl Subst for ty::t {
  48     fn subst_spanned(&self, tcx: &ty::ctxt,
  49                      substs: &ty::substs,
  50                      span: Option<Span>) -> ty::t {
  51         if ty::substs_is_noop(substs) && !ty::type_has_params(*self) {
  52             *self
  53         } else {
  54             let mut folder = SubstFolder {
  55                 tcx: tcx,
  56                 substs: substs,
  57                 span: span,
  58                 root_ty: Some(*self)
  59             };
  60             folder.fold_ty(*self)
  61         }
  62     }
  63 }
  64
  65 struct SubstFolder<'a> {
  66     tcx: &'a ty::ctxt,
  67     substs: &'a ty::substs,
  68
  69     // The location for which the substitution is performed, if available.
  70     span: Option<Span>,
  71
  72     // The root type that is being substituted, if available.
  73     root_ty: Option<ty::t>
  74 }
  75
  76 impl<'a> TypeFolder for SubstFolder<'a> {
  77     fn tcx<'a>(&'a self) -> &'a ty::ctxt { self.tcx }
  78
  79     fn fold_region(&mut self, r: ty::Region) -> ty::Region {
  80         r.subst(self.tcx, self.substs)
  81     }
  82
  83     fn fold_ty(&mut self, t: ty::t) -> ty::t {
  84         if !ty::type_needs_subst(t) {
  85             return t;
  86         }
  87
  88         match ty::get(t).sty {
  89             ty::ty_param(p) => {
  90                 if p.idx < self.substs.tps.len() {
  91                     *self.substs.tps.get(p.idx)
  92                 } else {
  93                     let root_msg = match self.root_ty {
  94                         Some(root) => format!(" in the substitution of `{}`",
  95                                               root.repr(self.tcx)),
  96                         None => ~""
  97                     };
  98                     let m = format!("can't use type parameters from outer \
  99                                     function{}; try using a local type \
 100                                     parameter instead", root_msg);
 101                     match self.span {
 102                         Some(span) => self.tcx.sess.span_err(span, m),
 103                         None => self.tcx.sess.err(m)
 104                     }
 105                     ty::mk_err()
 106                 }
 107             }
 108             ty::ty_self(_) => {
 109                 match self.substs.self_ty {
 110                     Some(ty) => ty,
 111                     None => {
 112                         let root_msg = match self.root_ty {
 113                             Some(root) => format!(" in the substitution of `{}`",
 114                                                   root.repr(self.tcx)),
 115                             None => ~""
 116                         };
 117                         let m = format!("missing `Self` type param{}", root_msg);
 118                         match self.span {
 119                             Some(span) => self.tcx.sess.span_err(span, m),
 120                             None => self.tcx.sess.err(m)
 121                         }
 122                         ty::mk_err()
 123                     }
 124                 }
 125             }
 126             _ => ty_fold::super_fold_ty(self, t)
 127         }
 128     }
 129 }
 130
 131 ///////////////////////////////////////////////////////////////////////////
 132 // Other types
 133
 134 impl<T:Subst> Subst for Vec<T> {
 135     fn subst_spanned(&self, tcx: &ty::ctxt,
 136                      substs: &ty::substs,
 137                      span: Option<Span>) -> Vec<T> {
 138         self.iter().map(|t| t.subst_spanned(tcx, substs, span)).collect()
 139     }
 140 }
 141 impl<T:Subst> Subst for Rc<T> {
 142     fn subst_spanned(&self, tcx: &ty::ctxt,
 143                      substs: &ty::substs,
 144                      span: Option<Span>) -> Rc<T> {
 145         Rc::new((**self).subst_spanned(tcx, substs, span))
 146     }
 147 }
 148
 149 impl<T:Subst> Subst for OwnedSlice<T> {
 150     fn subst_spanned(&self, tcx: &ty::ctxt,
 151                      substs: &ty::substs,
 152                      span: Option<Span>) -> OwnedSlice<T> {
 153         self.map(|t| t.subst_spanned(tcx, substs, span))
 154     }
 155 }
 156
 157 impl<T:Subst + 'static> Subst for @T {
 158     fn subst_spanned(&self, tcx: &ty::ctxt,
 159                      substs: &ty::substs,
 160                      span: Option<Span>) -> @T {
 161         match self {
 162             t => @(**t).subst_spanned(tcx, substs, span)
 163         }
 164     }
 165 }
 166
 167 impl<T:Subst> Subst for Option<T> {
 168     fn subst_spanned(&self, tcx: &ty::ctxt,
 169                      substs: &ty::substs,
 170                      span: Option<Span>) -> Option<T> {
 171         self.as_ref().map(|t| t.subst_spanned(tcx, substs, span))
 172     }
 173 }
 174
 175 impl Subst for ty::TraitRef {
 176     fn subst_spanned(&self, tcx: &ty::ctxt,
 177                      substs: &ty::substs,
 178                      span: Option<Span>) -> ty::TraitRef {
 179         ty::TraitRef {
 180             def_id: self.def_id,
 181             substs: self.substs.subst_spanned(tcx, substs, span)
 182         }
 183     }
 184 }
 185
 186 impl Subst for ty::substs {
 187     fn subst_spanned(&self, tcx: &ty::ctxt,
 188                      substs: &ty::substs,
 189                      span: Option<Span>) -> ty::substs {
 190         ty::substs {
 191             regions: self.regions.subst_spanned(tcx, substs, span),
 192             self_ty: self.self_ty.map(|typ| typ.subst_spanned(tcx, substs, span)),
 193             tps: self.tps.iter().map(|typ| typ.subst_spanned(tcx, substs, span)).collect()
 194         }
 195     }
 196 }
 197
 198 impl Subst for ty::RegionSubsts {
 199     fn subst_spanned(&self, tcx: &ty::ctxt,
 200                      substs: &ty::substs,
 201                      span: Option<Span>) -> ty::RegionSubsts {
 202         match *self {
 203             ty::ErasedRegions => {
 204                 ty::ErasedRegions
 205             }
 206             ty::NonerasedRegions(ref regions) => {
 207                 ty::NonerasedRegions(regions.subst_spanned(tcx, substs, span))
 208             }
 209         }
 210     }
 211 }
 212
 213 impl Subst for ty::BareFnTy {
 214     fn subst_spanned(&self, tcx: &ty::ctxt,
 215                      substs: &ty::substs,
 216                      span: Option<Span>) -> ty::BareFnTy {
 217         let mut folder = SubstFolder {
 218             tcx: tcx,
 219             substs: substs,
 220             span: span,
 221             root_ty: None
 222         };
 223         folder.fold_bare_fn_ty(self)
 224     }
 225 }
 226
 227 impl Subst for ty::ParamBounds {
 228     fn subst_spanned(&self, tcx: &ty::ctxt,
 229                      substs: &ty::substs,
 230                      span: Option<Span>) -> ty::ParamBounds {
 231         ty::ParamBounds {
 232             builtin_bounds: self.builtin_bounds,
 233             trait_bounds: self.trait_bounds.subst_spanned(tcx, substs, span)
 234         }
 235     }
 236 }
 237
 238 impl Subst for ty::TypeParameterDef {
 239     fn subst_spanned(&self, tcx: &ty::ctxt,
 240                      substs: &ty::substs,
 241                      span: Option<Span>) -> ty::TypeParameterDef {
 242         ty::TypeParameterDef {
 243             ident: self.ident,
 244             def_id: self.def_id,
 245             bounds: self.bounds.subst_spanned(tcx, substs, span),
 246             default: self.default.map(|x| x.subst_spanned(tcx, substs, span))
 247         }
 248     }
 249 }
 250
 251 impl Subst for ty::Generics {
 252     fn subst_spanned(&self, tcx: &ty::ctxt,
 253                      substs: &ty::substs,
 254                      span: Option<Span>) -> ty::Generics {
 255         ty::Generics {
 256             type_param_defs: self.type_param_defs.subst_spanned(tcx, substs, span),
 257             region_param_defs: self.region_param_defs.subst_spanned(tcx, substs, span),
 258         }
 259     }
 260 }
 261
 262 impl Subst for ty::RegionParameterDef {
 263     fn subst_spanned(&self, _: &ty::ctxt,
 264                      _: &ty::substs,
 265                      _: Option<Span>) -> ty::RegionParameterDef {
 266         *self
 267     }
 268 }
 269
 270 impl Subst for ty::Region {
 271     fn subst_spanned(&self, _tcx: &ty::ctxt,
 272                      substs: &ty::substs,
 273                      _: Option<Span>) -> ty::Region {
 274         // Note: This routine only handles regions that are bound on
 275         // type declarationss and other outer declarations, not those
 276         // bound in *fn types*. Region substitution of the bound
 277         // regions that appear in a function signature is done using
 278         // the specialized routine
 279         // `middle::typeck::check::regionmanip::replace_late_regions_in_fn_sig()`.
 280         match self {
 281             &ty::ReEarlyBound(_, i, _) => {
 282                 match substs.regions {
 283                     ty::ErasedRegions => ty::ReStatic,
 284                     ty::NonerasedRegions(ref regions) => *regions.get(i),
 285                 }
 286             }
 287             _ => *self
 288         }
 289     }
 290 }
 291
 292 impl Subst for ty::ty_param_bounds_and_ty {
 293     fn subst_spanned(&self, tcx: &ty::ctxt,
 294                      substs: &ty::substs,
 295                      span: Option<Span>) -> ty::ty_param_bounds_and_ty {
 296         ty::ty_param_bounds_and_ty {
 297             generics: self.generics.subst_spanned(tcx, substs, span),
 298             ty: self.ty.subst_spanned(tcx, substs, span)
 299         }
 300     }
 301 }