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         return ty::mk_closure(tcx, parse_closure_ty_(st, conv));
 511       }
 512       'F' => {
 513           let def_id = parse_def_(st, NominalType, conv);
 514           return ty::mk_bare_fn(tcx, Some(def_id),
 515                                 tcx.mk_bare_fn(parse_bare_fn_ty_(st, conv)));
 516       }
 517       'G' => {
 518           return ty::mk_bare_fn(tcx, None,
 519                                 tcx.mk_bare_fn(parse_bare_fn_ty_(st, conv)));
 520       }
 521       '#' => {
 522         let pos = parse_hex(st);
 523         assert_eq!(next(st), ':');
 524         let len = parse_hex(st);
 525         assert_eq!(next(st), '#');
 526         let key = ty::creader_cache_key {cnum: st.krate,
 527                                          pos: pos,
 528                                          len: len };
 529
 530         match tcx.rcache.borrow().get(&key).cloned() {
 531           Some(tt) => return tt,
 532           None => {}
 533         }
 534         let mut ps = PState {
 535             pos: pos,
 536             .. *st
 537         };
 538         let tt = parse_ty_(&mut ps, conv);
 539         tcx.rcache.borrow_mut().insert(key, tt);
 540         return tt;
 541       }
 542       '\"' => {
 543         let _ = parse_def_(st, TypeWithId, conv);
 544         let inner = parse_ty_(st, conv);
 545         inner
 546       }
 547       'a' => {
 548           assert_eq!(next(st), '[');
 549           let did = parse_def_(st, NominalType, conv);
 550           let substs = parse_substs_(st, conv);
 551           assert_eq!(next(st), ']');
 552           return ty::mk_struct(st.tcx, did, st.tcx.mk_substs(substs));
 553       }
 554       'k' => {
 555           assert_eq!(next(st), '[');
 556           let did = parse_def_(st, UnboxedClosureSource, conv);
 557           let region = parse_region_(st, conv);
 558           let substs = parse_substs_(st, conv);
 559           assert_eq!(next(st), ']');
 560           return ty::mk_unboxed_closure(st.tcx, did,
 561                   st.tcx.mk_region(region), st.tcx.mk_substs(substs));
 562       }
 563       'P' => {
 564           assert_eq!(next(st), '[');
 565           let trait_ref = parse_trait_ref_(st, conv);
 566           let name = token::intern(parse_str(st, ']').as_slice());
 567           return ty::mk_projection(tcx, trait_ref, name);
 568       }
 569       'e' => {
 570           return tcx.types.err;
 571       }
 572       c => { panic!("unexpected char in type string: {}", c);}
 573     }
 574 }
 575
 576 fn parse_mutability(st: &mut PState) -> ast::Mutability {
 577     match peek(st) {
 578       'm' => { next(st); ast::MutMutable }
 579       _ => { ast::MutImmutable }
 580     }
 581 }
 582
 583 fn parse_mt_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, conv: &mut F) -> ty::mt<'tcx> where
 584     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 585 {
 586     let m = parse_mutability(st);
 587     ty::mt { ty: parse_ty_(st, conv), mutbl: m }
 588 }
 589
 590 fn parse_def_<F>(st: &mut PState, source: DefIdSource, conv: &mut F) -> ast::DefId where
 591     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 592 {
 593     return (*conv)(source, scan(st, |c| { c == '|' }, parse_def_id));
 594 }
 595
 596 fn parse_uint(st: &mut PState) -> uint {
 597     let mut n = 0;
 598     loop {
 599         let cur = peek(st);
 600         if cur < '0' || cur > '9' { return n; }
 601         st.pos = st.pos + 1u;
 602         n *= 10;
 603         n += (cur as uint) - ('0' as uint);
 604     };
 605 }
 606
 607 fn parse_u32(st: &mut PState) -> u32 {
 608     let n = parse_uint(st);
 609     let m = n as u32;
 610     assert_eq!(m as uint, n);
 611     m
 612 }
 613
 614 fn parse_param_space(st: &mut PState) -> subst::ParamSpace {
 615     subst::ParamSpace::from_uint(parse_uint(st))
 616 }
 617
 618 fn parse_hex(st: &mut PState) -> uint {
 619     let mut n = 0u;
 620     loop {
 621         let cur = peek(st);
 622         if (cur < '0' || cur > '9') && (cur < 'a' || cur > 'f') { return n; }
 623         st.pos = st.pos + 1u;
 624         n *= 16u;
 625         if '0' <= cur && cur <= '9' {
 626             n += (cur as uint) - ('0' as uint);
 627         } else { n += 10u + (cur as uint) - ('a' as uint); }
 628     };
 629 }
 630
 631 fn parse_unsafety(c: char) -> ast::Unsafety {
 632     match c {
 633         'u' => ast::Unsafety::Unsafe,
 634         'n' => ast::Unsafety::Normal,
 635         _ => panic!("parse_unsafety: bad unsafety {}", c)
 636     }
 637 }
 638
 639 fn parse_abi_set(st: &mut PState) -> abi::Abi {
 640     assert_eq!(next(st), '[');
 641     scan(st, |c| c == ']', |bytes| {
 642         let abi_str = str::from_utf8(bytes).unwrap();
 643         abi::lookup(abi_str[]).expect(abi_str)
 644     })
 645 }
 646
 647 fn parse_onceness(c: char) -> ast::Onceness {
 648     match c {
 649         'o' => ast::Once,
 650         'm' => ast::Many,
 651         _ => panic!("parse_onceness: bad onceness")
 652     }
 653 }
 654
 655 fn parse_closure_ty<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>,
 656                                  mut conv: F) -> ty::ClosureTy<'tcx> where
 657     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 658 {
 659     parse_closure_ty_(st, &mut conv)
 660 }
 661
 662 fn parse_closure_ty_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>,
 663                                  conv: &mut F) -> ty::ClosureTy<'tcx> where
 664     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 665 {
 666     let unsafety = parse_unsafety(next(st));
 667     let onceness = parse_onceness(next(st));
 668     let store = parse_trait_store_(st, conv);
 669     let bounds = parse_existential_bounds_(st, conv);
 670     let sig = parse_sig_(st, conv);
 671     let abi = parse_abi_set(st);
 672     ty::ClosureTy {
 673         unsafety: unsafety,
 674         onceness: onceness,
 675         store: store,
 676         bounds: bounds,
 677         sig: sig,
 678         abi: abi,
 679     }
 680 }
 681
 682 fn parse_bare_fn_ty<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>,
 683                                  mut conv: F) -> ty::BareFnTy<'tcx> where
 684     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 685 {
 686     parse_bare_fn_ty_(st, &mut conv)
 687 }
 688
 689 fn parse_bare_fn_ty_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>,
 690                                  conv: &mut F) -> ty::BareFnTy<'tcx> where
 691     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 692 {
 693     let unsafety = parse_unsafety(next(st));
 694     let abi = parse_abi_set(st);
 695     let sig = parse_sig_(st, conv);
 696     ty::BareFnTy {
 697         unsafety: unsafety,
 698         abi: abi,
 699         sig: sig
 700     }
 701 }
 702
 703 fn parse_sig_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, conv: &mut F) -> ty::PolyFnSig<'tcx> where
 704     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 705 {
 706     assert_eq!(next(st), '[');
 707     let mut inputs = Vec::new();
 708     while peek(st) != ']' {
 709         inputs.push(parse_ty_(st, conv));
 710     }
 711     st.pos += 1u; // eat the ']'
 712     let variadic = match next(st) {
 713         'V' => true,
 714         'N' => false,
 715         r => panic!(format!("bad variadic: {}", r)),
 716     };
 717     let output = match peek(st) {
 718         'z' => {
 719           st.pos += 1u;
 720           ty::FnDiverging
 721         }
 722         _ => ty::FnConverging(parse_ty_(st, conv))
 723     };
 724     ty::Binder(ty::FnSig {inputs: inputs,
 725                         output: output,
 726                         variadic: variadic})
 727 }
 728
 729 // Rust metadata parsing
 730 pub fn parse_def_id(buf: &[u8]) -> ast::DefId {
 731     let mut colon_idx = 0u;
 732     let len = buf.len();
 733     while colon_idx < len && buf[colon_idx] != ':' as u8 { colon_idx += 1u; }
 734     if colon_idx == len {
 735         error!("didn't find ':' when parsing def id");
 736         panic!();
 737     }
 738
 739     let crate_part = buf[0u..colon_idx];
 740     let def_part = buf[colon_idx + 1u..len];
 741
 742     let crate_num = match str::from_utf8(crate_part).ok().and_then(|s| s.parse::<uint>()) {
 743        Some(cn) => cn as ast::CrateNum,
 744        None => panic!("internal error: parse_def_id: crate number expected, found {}",
 745                      crate_part)
 746     };
 747     let def_num = match str::from_utf8(def_part).ok().and_then(|s| s.parse::<uint>()) {
 748        Some(dn) => dn as ast::NodeId,
 749        None => panic!("internal error: parse_def_id: id expected, found {}",
 750                      def_part)
 751     };
 752     ast::DefId { krate: crate_num, node: def_num }
 753 }
 754
 755 pub fn parse_predicate_data<'tcx, F>(data: &[u8],
 756                                      start: uint,
 757                                      crate_num: ast::CrateNum,
 758                                      tcx: &ty::ctxt<'tcx>,
 759                                      conv: F)
 760                                      -> ty::Predicate<'tcx> where
 761     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 762 {
 763     let mut st = parse_state_from_data(data, crate_num, start, tcx);
 764     parse_predicate(&mut st, conv)
 765 }
 766
 767 pub fn parse_predicate<'a,'tcx, F>(st: &mut PState<'a, 'tcx>,
 768                                    mut conv: F)
 769                                    -> ty::Predicate<'tcx> where
 770     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 771 {
 772     parse_predicate_(st, &mut conv)
 773 }
 774
 775 fn parse_predicate_<'a,'tcx, F>(st: &mut PState<'a, 'tcx>,
 776                                 conv: &mut F)
 777                                 -> ty::Predicate<'tcx> where
 778     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 779 {
 780     match next(st) {
 781         't' => ty::Binder(parse_trait_ref_(st, conv)).as_predicate(),
 782         'e' => ty::Binder(ty::EquatePredicate(parse_ty_(st, conv),
 783                                               parse_ty_(st, conv))).as_predicate(),
 784         'r' => ty::Binder(ty::OutlivesPredicate(parse_region_(st, conv),
 785                                                 parse_region_(st, conv))).as_predicate(),
 786         'o' => ty::Binder(ty::OutlivesPredicate(parse_ty_(st, conv),
 787                                                 parse_region_(st, conv))).as_predicate(),
 788         'p' => ty::Binder(parse_projection_predicate_(st, conv)).as_predicate(),
 789         c => panic!("Encountered invalid character in metadata: {}", c)
 790     }
 791 }
 792
 793 fn parse_projection_predicate_<'a,'tcx, F>(
 794     st: &mut PState<'a, 'tcx>,
 795     conv: &mut F,
 796 ) -> ty::ProjectionPredicate<'tcx> where
 797     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 798 {
 799     ty::ProjectionPredicate {
 800         projection_ty: ty::ProjectionTy {
 801             trait_ref: parse_trait_ref_(st, conv),
 802             item_name: token::str_to_ident(parse_str(st, '|').as_slice()).name,
 803         },
 804         ty: parse_ty_(st, conv),
 805     }
 806 }
 807
 808 pub fn parse_type_param_def_data<'tcx, F>(data: &[u8], start: uint,
 809                                           crate_num: ast::CrateNum, tcx: &ty::ctxt<'tcx>,
 810                                           conv: F) -> ty::TypeParameterDef<'tcx> where
 811     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 812 {
 813     let mut st = parse_state_from_data(data, crate_num, start, tcx);
 814     parse_type_param_def(&mut st, conv)
 815 }
 816
 817 fn parse_type_param_def<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, mut conv: F)
 818                                      -> ty::TypeParameterDef<'tcx> where
 819     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 820 {
 821     parse_type_param_def_(st, &mut conv)
 822 }
 823
 824 fn parse_type_param_def_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, conv: &mut F)
 825                                       -> ty::TypeParameterDef<'tcx> where
 826     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 827 {
 828     let name = parse_name(st, ':');
 829     let def_id = parse_def_(st, NominalType, conv);
 830     let space = parse_param_space(st);
 831     assert_eq!(next(st), '|');
 832     let index = parse_u32(st);
 833     assert_eq!(next(st), '|');
 834     let bounds = parse_bounds_(st, conv);
 835     let default = parse_opt(st, |st| parse_ty_(st, conv));
 836
 837     ty::TypeParameterDef {
 838         name: name,
 839         def_id: def_id,
 840         space: space,
 841         index: index,
 842         bounds: bounds,
 843         default: default
 844     }
 845 }
 846
 847 fn parse_existential_bounds<'a,'tcx, F>(st: &mut PState<'a,'tcx>,
 848                                         mut conv: F)
 849                                         -> ty::ExistentialBounds<'tcx> where
 850     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 851 {
 852     parse_existential_bounds_(st, &mut conv)
 853 }
 854
 855 fn parse_existential_bounds_<'a,'tcx, F>(st: &mut PState<'a,'tcx>,
 856                                         conv: &mut F)
 857                                         -> ty::ExistentialBounds<'tcx> where
 858     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 859 {
 860     let ty::ParamBounds { trait_bounds, mut region_bounds, builtin_bounds, projection_bounds } =
 861          parse_bounds_(st, conv);
 862     assert_eq!(region_bounds.len(), 1);
 863     assert_eq!(trait_bounds.len(), 0);
 864     let region_bound = region_bounds.pop().unwrap();
 865     return ty::ExistentialBounds { region_bound: region_bound,
 866                                    builtin_bounds: builtin_bounds,
 867                                    projection_bounds: projection_bounds };
 868 }
 869
 870 fn parse_builtin_bounds<F>(st: &mut PState, mut _conv: F) -> ty::BuiltinBounds where
 871     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 872 {
 873     parse_builtin_bounds_(st, &mut _conv)
 874 }
 875
 876 fn parse_builtin_bounds_<F>(st: &mut PState, _conv: &mut F) -> ty::BuiltinBounds where
 877     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 878 {
 879     let mut builtin_bounds = ty::empty_builtin_bounds();
 880
 881     loop {
 882         match next(st) {
 883             'S' => {
 884                 builtin_bounds.insert(ty::BoundSend);
 885             }
 886             'Z' => {
 887                 builtin_bounds.insert(ty::BoundSized);
 888             }
 889             'P' => {
 890                 builtin_bounds.insert(ty::BoundCopy);
 891             }
 892             'T' => {
 893                 builtin_bounds.insert(ty::BoundSync);
 894             }
 895             '.' => {
 896                 return builtin_bounds;
 897             }
 898             c => {
 899                 panic!("parse_bounds: bad builtin bounds ('{}')", c)
 900             }
 901         }
 902     }
 903 }
 904
 905 fn parse_bounds<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, mut conv: F)
 906                              -> ty::ParamBounds<'tcx> where
 907     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 908 {
 909     parse_bounds_(st, &mut conv)
 910 }
 911
 912 fn parse_bounds_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, conv: &mut F)
 913                               -> ty::ParamBounds<'tcx> where
 914     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 915 {
 916     let builtin_bounds = parse_builtin_bounds_(st, conv);
 917
 918     let mut param_bounds = ty::ParamBounds {
 919         region_bounds: Vec::new(),
 920         builtin_bounds: builtin_bounds,
 921         trait_bounds: Vec::new(),
 922         projection_bounds: Vec::new(),
 923     };
 924     loop {
 925         match next(st) {
 926             'R' => {
 927                 param_bounds.region_bounds.push(
 928                     parse_region_(st, conv));
 929             }
 930             'I' => {
 931                 param_bounds.trait_bounds.push(
 932                     ty::Binder(parse_trait_ref_(st, conv)));
 933             }
 934             'P' => {
 935                 param_bounds.projection_bounds.push(
 936                     ty::Binder(parse_projection_predicate_(st, conv)));
 937             }
 938             '.' => {
 939                 return param_bounds;
 940             }
 941             c => {
 942                 panic!("parse_bounds: bad bounds ('{}')", c)
 943             }
 944         }
 945     }
 946 }