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