src/librustc/metadata/tydecode.rs

   1 // Copyright 2012-2014 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
  12 // Type decoding
  13
  14 // tjc note: Would be great to have a `match check` macro equivalent
  15 // for some of these
  16
  17 #![allow(non_camel_case_types)]
  18
  19 pub use self::DefIdSource::*;
  20
  21 use middle::region;
  22 use middle::subst;
  23 use middle::subst::VecPerParamSpace;
  24 use middle::ty::{self, AsPredicate, Ty};
  25
  26 use std::str;
  27 use syntax::abi;
  28 use syntax::ast;
  29 use syntax::parse::token;
  30
  31 // Compact string representation for Ty values. API TyStr &
  32 // parse_from_str. Extra parameters are for converting to/from def_ids in the
  33 // data buffer. Whatever format you choose should not contain pipe characters.
  34
  35 // Def id conversion: when we encounter def-ids, they have to be translated.
  36 // For example, the crate number must be converted from the crate number used
  37 // in the library we are reading from into the local crate numbers in use
  38 // here.  To perform this translation, the type decoder is supplied with a
  39 // conversion function of type `conv_did`.
  40 //
  41 // Sometimes, particularly when inlining, the correct translation of the
  42 // def-id will depend on where it originated from.  Therefore, the conversion
  43 // function is given an indicator of the source of the def-id.  See
  44 // astencode.rs for more information.
  45 #[derive(Copy, Clone, Debug)]
  46 pub enum DefIdSource {
  47     // Identifies a struct, trait, enum, etc.
  48     NominalType,
  49
  50     // Identifies a type alias (`type X = ...`).
  51     TypeWithId,
  52
  53     // Identifies a region parameter (`fn foo<'X>() { ... }`).
  54     RegionParameter,
  55
  56     // Identifies a closure
  57     ClosureSource
  58 }
  59
  60 // type conv_did = impl FnMut(DefIdSource, ast::DefId) -> ast::DefId;
  61
  62 pub struct PState<'a, 'tcx: 'a> {
  63     data: &'a [u8],
  64     krate: ast::CrateNum,
  65     pos: usize,
  66     tcx: &'a ty::ctxt<'tcx>
  67 }
  68
  69 fn peek(st: &PState) -> char {
  70     st.data[st.pos] as char
  71 }
  72
  73 fn next(st: &mut PState) -> char {
  74     let ch = st.data[st.pos] as char;
  75     st.pos = st.pos + 1;
  76     return ch;
  77 }
  78
  79 fn next_byte(st: &mut PState) -> u8 {
  80     let b = st.data[st.pos];
  81     st.pos = st.pos + 1;
  82     return b;
  83 }
  84
  85 fn scan<R, F, G>(st: &mut PState, mut is_last: F, op: G) -> R where
  86     F: FnMut(char) -> bool,
  87     G: FnOnce(&[u8]) -> R,
  88 {
  89     let start_pos = st.pos;
  90     debug!("scan: '{}' (start)", st.data[st.pos] as char);
  91     while !is_last(st.data[st.pos] as char) {
  92         st.pos += 1;
  93         debug!("scan: '{}'", st.data[st.pos] as char);
  94     }
  95     let end_pos = st.pos;
  96     st.pos += 1;
  97     return op(&st.data[start_pos..end_pos]);
  98 }
  99
 100 pub fn parse_name(st: &mut PState, last: char) -> ast::Name {
 101     fn is_last(b: char, c: char) -> bool { return c == b; }
 102     parse_name_(st, |a| is_last(last, a) )
 103 }
 104
 105 fn parse_name_<F>(st: &mut PState, is_last: F) -> ast::Name where
 106     F: FnMut(char) -> bool,
 107 {
 108     scan(st, is_last, |bytes| {
 109         token::intern(str::from_utf8(bytes).unwrap())
 110     })
 111 }
 112
 113 pub fn parse_state_from_data<'a, 'tcx>(data: &'a [u8], crate_num: ast::CrateNum,
 114                                        pos: usize, tcx: &'a ty::ctxt<'tcx>)
 115                                        -> PState<'a, 'tcx> {
 116     PState {
 117         data: data,
 118         krate: crate_num,
 119         pos: pos,
 120         tcx: tcx
 121     }
 122 }
 123
 124 fn data_log_string(data: &[u8], pos: usize) -> String {
 125     let mut buf = String::new();
 126     buf.push_str("<<");
 127     for i in pos..data.len() {
 128         let c = data[i];
 129         if c > 0x20 && c <= 0x7F {
 130             buf.push(c as char);
 131         } else {
 132             buf.push('.');
 133         }
 134     }
 135     buf.push_str(">>");
 136     buf
 137 }
 138
 139 pub fn parse_ty_closure_data<'tcx, F>(data: &[u8],
 140                                       crate_num: ast::CrateNum,
 141                                       pos: usize,
 142                                       tcx: &ty::ctxt<'tcx>,
 143                                       conv: F)
 144                                       -> ty::ClosureTy<'tcx> where
 145     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 146 {
 147     let mut st = parse_state_from_data(data, crate_num, pos, tcx);
 148     parse_closure_ty(&mut st, conv)
 149 }
 150
 151 pub fn parse_ty_data<'tcx, F>(data: &[u8], crate_num: ast::CrateNum, pos: usize,
 152                               tcx: &ty::ctxt<'tcx>, conv: F) -> Ty<'tcx> where
 153     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 154 {
 155     debug!("parse_ty_data {}", data_log_string(data, pos));
 156     let mut st = parse_state_from_data(data, crate_num, pos, tcx);
 157     parse_ty(&mut st, conv)
 158 }
 159
 160 pub fn parse_region_data<F>(data: &[u8], crate_num: ast::CrateNum, pos: usize, tcx: &ty::ctxt,
 161                             conv: F) -> ty::Region where
 162     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 163 {
 164     debug!("parse_region_data {}", data_log_string(data, pos));
 165     let mut st = parse_state_from_data(data, crate_num, pos, tcx);
 166     parse_region(&mut st, conv)
 167 }
 168
 169 pub fn parse_bare_fn_ty_data<'tcx, F>(data: &[u8], crate_num: ast::CrateNum, pos: usize,
 170                                       tcx: &ty::ctxt<'tcx>, conv: F)
 171                                       -> ty::BareFnTy<'tcx> where
 172     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 173 {
 174     debug!("parse_bare_fn_ty_data {}", data_log_string(data, pos));
 175     let mut st = parse_state_from_data(data, crate_num, pos, tcx);
 176     parse_bare_fn_ty(&mut st, conv)
 177 }
 178
 179 pub fn parse_trait_ref_data<'tcx, F>(data: &[u8], crate_num: ast::CrateNum, pos: usize,
 180                                      tcx: &ty::ctxt<'tcx>, conv: F)
 181                                      -> ty::TraitRef<'tcx> where
 182     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 183 {
 184     debug!("parse_trait_ref_data {}", data_log_string(data, pos));
 185     let mut st = parse_state_from_data(data, crate_num, pos, tcx);
 186     parse_trait_ref(&mut st, conv)
 187 }
 188
 189 pub fn parse_substs_data<'tcx, F>(data: &[u8], crate_num: ast::CrateNum, pos: usize,
 190                                   tcx: &ty::ctxt<'tcx>, conv: F) -> subst::Substs<'tcx> where
 191     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 192 {
 193     debug!("parse_substs_data{}", data_log_string(data, pos));
 194     let mut st = parse_state_from_data(data, crate_num, pos, tcx);
 195     parse_substs(&mut st, conv)
 196 }
 197
 198 pub fn parse_existential_bounds_data<'tcx, F>(data: &[u8], crate_num: ast::CrateNum,
 199                                               pos: usize, tcx: &ty::ctxt<'tcx>, conv: F)
 200                                               -> ty::ExistentialBounds<'tcx> where
 201     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 202 {
 203     let mut st = parse_state_from_data(data, crate_num, pos, tcx);
 204     parse_existential_bounds(&mut st, conv)
 205 }
 206
 207 pub fn parse_builtin_bounds_data<F>(data: &[u8], crate_num: ast::CrateNum,
 208                                     pos: usize, tcx: &ty::ctxt, conv: F)
 209                                     -> ty::BuiltinBounds where
 210     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 211 {
 212     let mut st = parse_state_from_data(data, crate_num, pos, tcx);
 213     parse_builtin_bounds(&mut st, conv)
 214 }
 215
 216 fn parse_size(st: &mut PState) -> Option<usize> {
 217     assert_eq!(next(st), '/');
 218
 219     if peek(st) == '|' {
 220         assert_eq!(next(st), '|');
 221         None
 222     } else {
 223         let n = parse_uint(st);
 224         assert_eq!(next(st), '|');
 225         Some(n)
 226     }
 227 }
 228
 229 fn parse_vec_per_param_space<'a, 'tcx, T, F>(st: &mut PState<'a, 'tcx>,
 230                                              mut f: F)
 231                                              -> VecPerParamSpace<T> where
 232     F: FnMut(&mut PState<'a, 'tcx>) -> T,
 233 {
 234     let mut r = VecPerParamSpace::empty();
 235     for &space in &subst::ParamSpace::all() {
 236         assert_eq!(next(st), '[');
 237         while peek(st) != ']' {
 238             r.push(space, f(st));
 239         }
 240         assert_eq!(next(st), ']');
 241     }
 242     r
 243 }
 244
 245 fn parse_substs<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>,
 246                              mut conv: F) -> subst::Substs<'tcx> where
 247     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 248 {
 249     parse_substs_(st, &mut conv)
 250 }
 251
 252 fn parse_substs_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>,
 253                               conv: &mut F) -> subst::Substs<'tcx> where
 254     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 255 {
 256     let regions =
 257         parse_region_substs_(st, conv);
 258
 259     let types =
 260         parse_vec_per_param_space(st, |st| parse_ty_(st, conv));
 261
 262     subst::Substs { types: types,
 263                     regions: regions }
 264 }
 265
 266 fn parse_region_substs_<F>(st: &mut PState, conv: &mut F) -> subst::RegionSubsts where
 267     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 268 {
 269     match next(st) {
 270         'e' => subst::ErasedRegions,
 271         'n' => {
 272             subst::NonerasedRegions(
 273                 parse_vec_per_param_space(
 274                     st, |st| parse_region_(st, conv)))
 275         }
 276         _ => panic!("parse_bound_region: bad input")
 277     }
 278 }
 279
 280 fn parse_bound_region_<F>(st: &mut PState, conv: &mut F) -> ty::BoundRegion where
 281     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 282 {
 283     match next(st) {
 284         'a' => {
 285             let id = parse_u32(st);
 286             assert_eq!(next(st), '|');
 287             ty::BrAnon(id)
 288         }
 289         '[' => {
 290             let def = parse_def_(st, RegionParameter, conv);
 291             let ident = token::str_to_ident(&parse_str(st, ']'));
 292             ty::BrNamed(def, ident.name)
 293         }
 294         'f' => {
 295             let id = parse_u32(st);
 296             assert_eq!(next(st), '|');
 297             ty::BrFresh(id)
 298         }
 299         'e' => ty::BrEnv,
 300         _ => panic!("parse_bound_region: bad input")
 301     }
 302 }
 303
 304 fn parse_region<F>(st: &mut PState, mut conv: F) -> ty::Region where
 305     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 306 {
 307     parse_region_(st, &mut conv)
 308 }
 309
 310 fn parse_region_<F>(st: &mut PState, conv: &mut F) -> ty::Region where
 311     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 312 {
 313     match next(st) {
 314       'b' => {
 315         assert_eq!(next(st), '[');
 316         let id = ty::DebruijnIndex::new(parse_u32(st));
 317         assert_eq!(next(st), '|');
 318         let br = parse_bound_region_(st, conv);
 319         assert_eq!(next(st), ']');
 320         ty::ReLateBound(id, br)
 321       }
 322       'B' => {
 323         assert_eq!(next(st), '[');
 324         let node_id = parse_uint(st) as ast::NodeId;
 325         assert_eq!(next(st), '|');
 326         let space = parse_param_space(st);
 327         assert_eq!(next(st), '|');
 328         let index = parse_u32(st);
 329         assert_eq!(next(st), '|');
 330         let nm = token::str_to_ident(&parse_str(st, ']'));
 331         ty::ReEarlyBound(ty::EarlyBoundRegion {
 332             param_id: node_id,
 333             space: space,
 334             index: index,
 335             name: nm.name
 336         })
 337       }
 338       'f' => {
 339         assert_eq!(next(st), '[');
 340         let scope = parse_destruction_scope_data(st);
 341         assert_eq!(next(st), '|');
 342         let br = parse_bound_region_(st, conv);
 343         assert_eq!(next(st), ']');
 344         ty::ReFree(ty::FreeRegion { scope: scope,
 345                                     bound_region: br})
 346       }
 347       's' => {
 348         let scope = parse_scope(st);
 349         assert_eq!(next(st), '|');
 350         ty::ReScope(scope)
 351       }
 352       't' => {
 353         ty::ReStatic
 354       }
 355       'e' => {
 356         ty::ReStatic
 357       }
 358       _ => panic!("parse_region: bad input")
 359     }
 360 }
 361
 362 fn parse_scope(st: &mut PState) -> region::CodeExtent {
 363     match next(st) {
 364         'P' => {
 365             assert_eq!(next(st), '[');
 366             let fn_id = parse_uint(st) as ast::NodeId;
 367             assert_eq!(next(st), '|');
 368             let body_id = parse_uint(st) as ast::NodeId;
 369             assert_eq!(next(st), ']');
 370             region::CodeExtent::ParameterScope {
 371                 fn_id: fn_id, body_id: body_id
 372             }
 373         }
 374         'M' => {
 375             let node_id = parse_uint(st) as ast::NodeId;
 376             region::CodeExtent::Misc(node_id)
 377         }
 378         'D' => {
 379             let node_id = parse_uint(st) as ast::NodeId;
 380             region::CodeExtent::DestructionScope(node_id)
 381         }
 382         'B' => {
 383             assert_eq!(next(st), '[');
 384             let node_id = parse_uint(st) as ast::NodeId;
 385             assert_eq!(next(st), '|');
 386             let first_stmt_index = parse_uint(st);
 387             assert_eq!(next(st), ']');
 388             let block_remainder = region::BlockRemainder {
 389                 block: node_id, first_statement_index: first_stmt_index,
 390             };
 391             region::CodeExtent::Remainder(block_remainder)
 392         }
 393         _ => panic!("parse_scope: bad input")
 394     }
 395 }
 396
 397 fn parse_destruction_scope_data(st: &mut PState) -> region::DestructionScopeData {
 398     let node_id = parse_uint(st) as ast::NodeId;
 399     region::DestructionScopeData::new(node_id)
 400 }
 401
 402 fn parse_opt<'a, 'tcx, T, F>(st: &mut PState<'a, 'tcx>, f: F) -> Option<T> where
 403     F: FnOnce(&mut PState<'a, 'tcx>) -> T,
 404 {
 405     match next(st) {
 406       'n' => None,
 407       's' => Some(f(st)),
 408       _ => panic!("parse_opt: bad input")
 409     }
 410 }
 411
 412 fn parse_str(st: &mut PState, term: char) -> String {
 413     let mut result = String::new();
 414     while peek(st) != term {
 415         unsafe {
 416             result.as_mut_vec().push_all(&[next_byte(st)])
 417         }
 418     }
 419     next(st);
 420     result
 421 }
 422
 423 fn parse_trait_ref<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, mut conv: F)
 424                                 -> ty::TraitRef<'tcx> where
 425     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 426 {
 427     parse_trait_ref_(st, &mut conv)
 428 }
 429
 430 fn parse_trait_ref_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, conv: &mut F)
 431                               -> ty::TraitRef<'tcx> where
 432     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 433 {
 434     let def = parse_def_(st, NominalType, conv);
 435     let substs = st.tcx.mk_substs(parse_substs_(st, conv));
 436     ty::TraitRef {def_id: def, substs: substs}
 437 }
 438
 439 fn parse_ty<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, mut conv: F) -> Ty<'tcx> where
 440     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 441 {
 442     parse_ty_(st, &mut conv)
 443 }
 444
 445 fn parse_ty_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, conv: &mut F) -> Ty<'tcx> where
 446     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 447 {
 448     let tcx = st.tcx;
 449     match next(st) {
 450       'b' => return tcx.types.bool,
 451       'i' => { /* eat the s of is */ next(st); return tcx.types.isize },
 452       'u' => { /* eat the s of us */ next(st); return tcx.types.usize },
 453       'M' => {
 454         match next(st) {
 455           'b' => return tcx.types.u8,
 456           'w' => return tcx.types.u16,
 457           'l' => return tcx.types.u32,
 458           'd' => return tcx.types.u64,
 459           'B' => return tcx.types.i8,
 460           'W' => return tcx.types.i16,
 461           'L' => return tcx.types.i32,
 462           'D' => return tcx.types.i64,
 463           'f' => return tcx.types.f32,
 464           'F' => return tcx.types.f64,
 465           _ => panic!("parse_ty: bad numeric type")
 466         }
 467       }
 468       'c' => return tcx.types.char,
 469       't' => {
 470         assert_eq!(next(st), '[');
 471         let def = parse_def_(st, NominalType, conv);
 472         let substs = parse_substs_(st, conv);
 473         assert_eq!(next(st), ']');
 474         return ty::mk_enum(tcx, def, st.tcx.mk_substs(substs));
 475       }
 476       'x' => {
 477         assert_eq!(next(st), '[');
 478         let trait_ref = ty::Binder(parse_trait_ref_(st, conv));
 479         let bounds = parse_existential_bounds_(st, conv);
 480         assert_eq!(next(st), ']');
 481         return ty::mk_trait(tcx, trait_ref, bounds);
 482       }
 483       'p' => {
 484         assert_eq!(next(st), '[');
 485         let index = parse_u32(st);
 486         assert_eq!(next(st), '|');
 487         let space = parse_param_space(st);
 488         assert_eq!(next(st), '|');
 489         let name = token::intern(&parse_str(st, ']'));
 490         return ty::mk_param(tcx, space, index, name);
 491       }
 492       '~' => return ty::mk_uniq(tcx, parse_ty_(st, conv)),
 493       '*' => return ty::mk_ptr(tcx, parse_mt_(st, conv)),
 494       '&' => {
 495         let r = parse_region_(st, conv);
 496         let mt = parse_mt_(st, conv);
 497         return ty::mk_rptr(tcx, tcx.mk_region(r), mt);
 498       }
 499       'V' => {
 500         let t = parse_ty_(st, conv);
 501         let sz = parse_size(st);
 502         return ty::mk_vec(tcx, t, sz);
 503       }
 504       'v' => {
 505         return ty::mk_str(tcx);
 506       }
 507       'T' => {
 508         assert_eq!(next(st), '[');
 509         let mut params = Vec::new();
 510         while peek(st) != ']' { params.push(parse_ty_(st, conv)); }
 511         st.pos = st.pos + 1;
 512         return ty::mk_tup(tcx, params);
 513       }
 514       'F' => {
 515           let def_id = parse_def_(st, NominalType, conv);
 516           return ty::mk_bare_fn(tcx, Some(def_id),
 517                                 tcx.mk_bare_fn(parse_bare_fn_ty_(st, conv)));
 518       }
 519       'G' => {
 520           return ty::mk_bare_fn(tcx, None,
 521                                 tcx.mk_bare_fn(parse_bare_fn_ty_(st, conv)));
 522       }
 523       '#' => {
 524         let pos = parse_hex(st);
 525         assert_eq!(next(st), ':');
 526         let len = parse_hex(st);
 527         assert_eq!(next(st), '#');
 528         let key = ty::creader_cache_key {cnum: st.krate,
 529                                          pos: pos,
 530                                          len: len };
 531
 532         match tcx.rcache.borrow().get(&key).cloned() {
 533           Some(tt) => {
 534             // If there is a closure buried in the type some where, then we
 535             // need to re-convert any def ids (see case 'k', below). That means
 536             // we can't reuse the cached version.
 537             if !ty::type_has_ty_closure(tt) {
 538                 return tt;
 539             }
 540           }
 541           None => {}
 542         }
 543         let mut ps = PState {
 544             pos: pos,
 545             .. *st
 546         };
 547         let tt = parse_ty_(&mut ps, conv);
 548         tcx.rcache.borrow_mut().insert(key, tt);
 549         return tt;
 550       }
 551       '\"' => {
 552         let _ = parse_def_(st, TypeWithId, conv);
 553         let inner = parse_ty_(st, conv);
 554         inner
 555       }
 556       'a' => {
 557           assert_eq!(next(st), '[');
 558           let did = parse_def_(st, NominalType, conv);
 559           let substs = parse_substs_(st, conv);
 560           assert_eq!(next(st), ']');
 561           return ty::mk_struct(st.tcx, did, st.tcx.mk_substs(substs));
 562       }
 563       'k' => {
 564           assert_eq!(next(st), '[');
 565           let did = parse_def_(st, ClosureSource, conv);
 566           let substs = parse_substs_(st, conv);
 567           assert_eq!(next(st), ']');
 568           return ty::mk_closure(st.tcx, did, st.tcx.mk_substs(substs));
 569       }
 570       'P' => {
 571           assert_eq!(next(st), '[');
 572           let trait_ref = parse_trait_ref_(st, conv);
 573           let name = token::intern(&parse_str(st, ']'));
 574           return ty::mk_projection(tcx, trait_ref, name);
 575       }
 576       'e' => {
 577           return tcx.types.err;
 578       }
 579       c => { panic!("unexpected char in type string: {}", c);}
 580     }
 581 }
 582
 583 fn parse_mutability(st: &mut PState) -> ast::Mutability {
 584     match peek(st) {
 585       'm' => { next(st); ast::MutMutable }
 586       _ => { ast::MutImmutable }
 587     }
 588 }
 589
 590 fn parse_mt_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, conv: &mut F) -> ty::mt<'tcx> where
 591     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 592 {
 593     let m = parse_mutability(st);
 594     ty::mt { ty: parse_ty_(st, conv), mutbl: m }
 595 }
 596
 597 fn parse_def_<F>(st: &mut PState, source: DefIdSource, conv: &mut F) -> ast::DefId where
 598     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 599 {
 600     return (*conv)(source, scan(st, |c| { c == '|' }, parse_def_id));
 601 }
 602
 603 fn parse_uint(st: &mut PState) -> usize {
 604     let mut n = 0;
 605     loop {
 606         let cur = peek(st);
 607         if cur < '0' || cur > '9' { return n; }
 608         st.pos = st.pos + 1;
 609         n *= 10;
 610         n += (cur as usize) - ('0' as usize);
 611     };
 612 }
 613
 614 fn parse_u32(st: &mut PState) -> u32 {
 615     let n = parse_uint(st);
 616     let m = n as u32;
 617     assert_eq!(m as usize, n);
 618     m
 619 }
 620
 621 fn parse_param_space(st: &mut PState) -> subst::ParamSpace {
 622     subst::ParamSpace::from_uint(parse_uint(st))
 623 }
 624
 625 fn parse_hex(st: &mut PState) -> usize {
 626     let mut n = 0;
 627     loop {
 628         let cur = peek(st);
 629         if (cur < '0' || cur > '9') && (cur < 'a' || cur > 'f') { return n; }
 630         st.pos = st.pos + 1;
 631         n *= 16;
 632         if '0' <= cur && cur <= '9' {
 633             n += (cur as usize) - ('0' as usize);
 634         } else { n += 10 + (cur as usize) - ('a' as usize); }
 635     };
 636 }
 637
 638 fn parse_unsafety(c: char) -> ast::Unsafety {
 639     match c {
 640         'u' => ast::Unsafety::Unsafe,
 641         'n' => ast::Unsafety::Normal,
 642         _ => panic!("parse_unsafety: bad unsafety {}", c)
 643     }
 644 }
 645
 646 fn parse_abi_set(st: &mut PState) -> abi::Abi {
 647     assert_eq!(next(st), '[');
 648     scan(st, |c| c == ']', |bytes| {
 649         let abi_str = str::from_utf8(bytes).unwrap();
 650         abi::lookup(&abi_str[..]).expect(abi_str)
 651     })
 652 }
 653
 654 fn parse_closure_ty<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>,
 655                                  mut conv: F) -> ty::ClosureTy<'tcx> where
 656     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 657 {
 658     parse_closure_ty_(st, &mut conv)
 659 }
 660
 661 fn parse_closure_ty_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>,
 662                                  conv: &mut F) -> ty::ClosureTy<'tcx> where
 663     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 664 {
 665     let unsafety = parse_unsafety(next(st));
 666     let sig = parse_sig_(st, conv);
 667     let abi = parse_abi_set(st);
 668     ty::ClosureTy {
 669         unsafety: unsafety,
 670         sig: sig,
 671         abi: abi,
 672     }
 673 }
 674
 675 fn parse_bare_fn_ty<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>,
 676                                  mut conv: F) -> ty::BareFnTy<'tcx> where
 677     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 678 {
 679     parse_bare_fn_ty_(st, &mut conv)
 680 }
 681
 682 fn parse_bare_fn_ty_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>,
 683                                  conv: &mut F) -> ty::BareFnTy<'tcx> where
 684     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 685 {
 686     let unsafety = parse_unsafety(next(st));
 687     let abi = parse_abi_set(st);
 688     let sig = parse_sig_(st, conv);
 689     ty::BareFnTy {
 690         unsafety: unsafety,
 691         abi: abi,
 692         sig: sig
 693     }
 694 }
 695
 696 fn parse_sig_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, conv: &mut F) -> ty::PolyFnSig<'tcx> where
 697     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 698 {
 699     assert_eq!(next(st), '[');
 700     let mut inputs = Vec::new();
 701     while peek(st) != ']' {
 702         inputs.push(parse_ty_(st, conv));
 703     }
 704     st.pos += 1; // eat the ']'
 705     let variadic = match next(st) {
 706         'V' => true,
 707         'N' => false,
 708         r => panic!(format!("bad variadic: {}", r)),
 709     };
 710     let output = match peek(st) {
 711         'z' => {
 712           st.pos += 1;
 713           ty::FnDiverging
 714         }
 715         _ => ty::FnConverging(parse_ty_(st, conv))
 716     };
 717     ty::Binder(ty::FnSig {inputs: inputs,
 718                         output: output,
 719                         variadic: variadic})
 720 }
 721
 722 // Rust metadata parsing
 723 pub fn parse_def_id(buf: &[u8]) -> ast::DefId {
 724     let mut colon_idx = 0;
 725     let len = buf.len();
 726     while colon_idx < len && buf[colon_idx] != ':' as u8 { colon_idx += 1; }
 727     if colon_idx == len {
 728         error!("didn't find ':' when parsing def id");
 729         panic!();
 730     }
 731
 732     let crate_part = &buf[0..colon_idx];
 733     let def_part = &buf[colon_idx + 1..len];
 734
 735     let crate_num = match str::from_utf8(crate_part).ok().and_then(|s| {
 736         s.parse::<usize>().ok()
 737     }) {
 738        Some(cn) => cn as ast::CrateNum,
 739        None => panic!("internal error: parse_def_id: crate number expected, found {:?}",
 740                      crate_part)
 741     };
 742     let def_num = match str::from_utf8(def_part).ok().and_then(|s| {
 743         s.parse::<usize>().ok()
 744     }) {
 745        Some(dn) => dn as ast::NodeId,
 746        None => panic!("internal error: parse_def_id: id expected, found {:?}",
 747                      def_part)
 748     };
 749     ast::DefId { krate: crate_num, node: def_num }
 750 }
 751
 752 pub fn parse_predicate_data<'tcx, F>(data: &[u8],
 753                                      start: usize,
 754                                      crate_num: ast::CrateNum,
 755                                      tcx: &ty::ctxt<'tcx>,
 756                                      conv: F)
 757                                      -> ty::Predicate<'tcx> where
 758     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 759 {
 760     let mut st = parse_state_from_data(data, crate_num, start, tcx);
 761     parse_predicate(&mut st, conv)
 762 }
 763
 764 pub fn parse_predicate<'a,'tcx, F>(st: &mut PState<'a, 'tcx>,
 765                                    mut conv: F)
 766                                    -> ty::Predicate<'tcx> where
 767     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 768 {
 769     parse_predicate_(st, &mut conv)
 770 }
 771
 772 fn parse_predicate_<'a,'tcx, F>(st: &mut PState<'a, 'tcx>,
 773                                 conv: &mut F)
 774                                 -> ty::Predicate<'tcx> where
 775     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 776 {
 777     match next(st) {
 778         't' => ty::Binder(parse_trait_ref_(st, conv)).as_predicate(),
 779         'e' => ty::Binder(ty::EquatePredicate(parse_ty_(st, conv),
 780                                               parse_ty_(st, conv))).as_predicate(),
 781         'r' => ty::Binder(ty::OutlivesPredicate(parse_region_(st, conv),
 782                                                 parse_region_(st, conv))).as_predicate(),
 783         'o' => ty::Binder(ty::OutlivesPredicate(parse_ty_(st, conv),
 784                                                 parse_region_(st, conv))).as_predicate(),
 785         'p' => ty::Binder(parse_projection_predicate_(st, conv)).as_predicate(),
 786         c => panic!("Encountered invalid character in metadata: {}", c)
 787     }
 788 }
 789
 790 fn parse_projection_predicate_<'a,'tcx, F>(
 791     st: &mut PState<'a, 'tcx>,
 792     conv: &mut F,
 793 ) -> ty::ProjectionPredicate<'tcx> where
 794     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 795 {
 796     ty::ProjectionPredicate {
 797         projection_ty: ty::ProjectionTy {
 798             trait_ref: parse_trait_ref_(st, conv),
 799             item_name: token::str_to_ident(&parse_str(st, '|')).name,
 800         },
 801         ty: parse_ty_(st, conv),
 802     }
 803 }
 804
 805 pub fn parse_type_param_def_data<'tcx, F>(data: &[u8], start: usize,
 806                                           crate_num: ast::CrateNum, tcx: &ty::ctxt<'tcx>,
 807                                           conv: F) -> ty::TypeParameterDef<'tcx> where
 808     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 809 {
 810     let mut st = parse_state_from_data(data, crate_num, start, tcx);
 811     parse_type_param_def(&mut st, conv)
 812 }
 813
 814 fn parse_type_param_def<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, mut conv: F)
 815                                      -> ty::TypeParameterDef<'tcx> where
 816     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 817 {
 818     parse_type_param_def_(st, &mut conv)
 819 }
 820
 821 fn parse_type_param_def_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, conv: &mut F)
 822                                       -> ty::TypeParameterDef<'tcx> where
 823     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 824 {
 825     let name = parse_name(st, ':');
 826     let def_id = parse_def_(st, NominalType, conv);
 827     let space = parse_param_space(st);
 828     assert_eq!(next(st), '|');
 829     let index = parse_u32(st);
 830     assert_eq!(next(st), '|');
 831     let default = parse_opt(st, |st| parse_ty_(st, conv));
 832     let object_lifetime_default = parse_object_lifetime_default(st, conv);
 833
 834     ty::TypeParameterDef {
 835         name: name,
 836         def_id: def_id,
 837         space: space,
 838         index: index,
 839         default: default,
 840         object_lifetime_default: object_lifetime_default,
 841     }
 842 }
 843
 844 fn parse_object_lifetime_default<'a,'tcx, F>(st: &mut PState<'a,'tcx>,
 845                                              conv: &mut F)
 846                                              -> ty::ObjectLifetimeDefault
 847     where F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 848 {
 849     match next(st) {
 850         'a' => ty::ObjectLifetimeDefault::Ambiguous,
 851         'b' => ty::ObjectLifetimeDefault::BaseDefault,
 852         's' => {
 853             let region = parse_region_(st, conv);
 854             ty::ObjectLifetimeDefault::Specific(region)
 855         }
 856         _ => panic!("parse_object_lifetime_default: bad input")
 857     }
 858 }
 859
 860 fn parse_existential_bounds<'a,'tcx, F>(st: &mut PState<'a,'tcx>,
 861                                         mut conv: F)
 862                                         -> ty::ExistentialBounds<'tcx> where
 863     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 864 {
 865     parse_existential_bounds_(st, &mut conv)
 866 }
 867
 868 fn parse_existential_bounds_<'a,'tcx, F>(st: &mut PState<'a,'tcx>,
 869                                         conv: &mut F)
 870                                         -> ty::ExistentialBounds<'tcx> where
 871     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 872 {
 873     let builtin_bounds = parse_builtin_bounds_(st, conv);
 874     let region_bound = parse_region_(st, conv);
 875     let mut projection_bounds = Vec::new();
 876
 877     loop {
 878         match next(st) {
 879             'P' => {
 880                 projection_bounds.push(
 881                     ty::Binder(parse_projection_predicate_(st, conv)));
 882                 }
 883             '.' => { break; }
 884             c => {
 885                 panic!("parse_bounds: bad bounds ('{}')", c)
 886             }
 887         }
 888     }
 889
 890     let region_bound_will_change = match next(st) {
 891         'y' => true,
 892         'n' => false,
 893         c => panic!("parse_ty: expected y/n not '{}'", c)
 894     };
 895
 896     return ty::ExistentialBounds { region_bound: region_bound,
 897                                    builtin_bounds: builtin_bounds,
 898                                    projection_bounds: projection_bounds,
 899                                    region_bound_will_change: region_bound_will_change };
 900 }
 901
 902 fn parse_builtin_bounds<F>(st: &mut PState, mut _conv: F) -> ty::BuiltinBounds where
 903     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 904 {
 905     parse_builtin_bounds_(st, &mut _conv)
 906 }
 907
 908 fn parse_builtin_bounds_<F>(st: &mut PState, _conv: &mut F) -> ty::BuiltinBounds where
 909     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 910 {
 911     let mut builtin_bounds = ty::BuiltinBounds::empty();
 912
 913     loop {
 914         match next(st) {
 915             'S' => {
 916                 builtin_bounds.insert(ty::BoundSend);
 917             }
 918             'Z' => {
 919                 builtin_bounds.insert(ty::BoundSized);
 920             }
 921             'P' => {
 922                 builtin_bounds.insert(ty::BoundCopy);
 923             }
 924             'T' => {
 925                 builtin_bounds.insert(ty::BoundSync);
 926             }
 927             '.' => {
 928                 return builtin_bounds;
 929             }
 930             c => {
 931                 panic!("parse_bounds: bad builtin bounds ('{}')", c)
 932             }
 933         }
 934     }
 935 }