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, Debug)]
  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 a closure
  61     ClosureSource
  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 + 1;
  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 + 1;
  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 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_vec_per_param_space<'a, 'tcx, T, F>(st: &mut PState<'a, 'tcx>,
 247                                              mut f: F)
 248                                              -> VecPerParamSpace<T> where
 249     F: FnMut(&mut PState<'a, 'tcx>) -> T,
 250 {
 251     let mut r = VecPerParamSpace::empty();
 252     for &space in &subst::ParamSpace::all() {
 253         assert_eq!(next(st), '[');
 254         while peek(st) != ']' {
 255             r.push(space, f(st));
 256         }
 257         assert_eq!(next(st), ']');
 258     }
 259     r
 260 }
 261
 262 fn parse_substs<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>,
 263                              mut conv: F) -> subst::Substs<'tcx> where
 264     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 265 {
 266     parse_substs_(st, &mut conv)
 267 }
 268
 269 fn parse_substs_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>,
 270                               conv: &mut F) -> subst::Substs<'tcx> where
 271     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 272 {
 273     let regions =
 274         parse_region_substs_(st, conv);
 275
 276     let types =
 277         parse_vec_per_param_space(st, |st| parse_ty_(st, conv));
 278
 279     subst::Substs { types: types,
 280                     regions: regions }
 281 }
 282
 283 fn parse_region_substs_<F>(st: &mut PState, conv: &mut F) -> subst::RegionSubsts where
 284     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 285 {
 286     match next(st) {
 287         'e' => subst::ErasedRegions,
 288         'n' => {
 289             subst::NonerasedRegions(
 290                 parse_vec_per_param_space(
 291                     st, |st| parse_region_(st, conv)))
 292         }
 293         _ => panic!("parse_bound_region: bad input")
 294     }
 295 }
 296
 297 fn parse_bound_region_<F>(st: &mut PState, conv: &mut F) -> ty::BoundRegion where
 298     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 299 {
 300     match next(st) {
 301         'a' => {
 302             let id = parse_u32(st);
 303             assert_eq!(next(st), '|');
 304             ty::BrAnon(id)
 305         }
 306         '[' => {
 307             let def = parse_def_(st, RegionParameter, conv);
 308             let ident = token::str_to_ident(&parse_str(st, ']')[]);
 309             ty::BrNamed(def, ident.name)
 310         }
 311         'f' => {
 312             let id = parse_u32(st);
 313             assert_eq!(next(st), '|');
 314             ty::BrFresh(id)
 315         }
 316         'e' => ty::BrEnv,
 317         _ => panic!("parse_bound_region: bad input")
 318     }
 319 }
 320
 321 fn parse_region<F>(st: &mut PState, mut conv: F) -> ty::Region where
 322     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 323 {
 324     parse_region_(st, &mut conv)
 325 }
 326
 327 fn parse_region_<F>(st: &mut PState, conv: &mut F) -> ty::Region where
 328     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 329 {
 330     match next(st) {
 331       'b' => {
 332         assert_eq!(next(st), '[');
 333         let id = ty::DebruijnIndex::new(parse_u32(st));
 334         assert_eq!(next(st), '|');
 335         let br = parse_bound_region_(st, conv);
 336         assert_eq!(next(st), ']');
 337         ty::ReLateBound(id, br)
 338       }
 339       'B' => {
 340         assert_eq!(next(st), '[');
 341         let node_id = parse_uint(st) as ast::NodeId;
 342         assert_eq!(next(st), '|');
 343         let space = parse_param_space(st);
 344         assert_eq!(next(st), '|');
 345         let index = parse_u32(st);
 346         assert_eq!(next(st), '|');
 347         let nm = token::str_to_ident(&parse_str(st, ']')[]);
 348         ty::ReEarlyBound(node_id, space, index, nm.name)
 349       }
 350       'f' => {
 351         assert_eq!(next(st), '[');
 352         let scope = parse_destruction_scope_data(st);
 353         assert_eq!(next(st), '|');
 354         let br = parse_bound_region_(st, conv);
 355         assert_eq!(next(st), ']');
 356         ty::ReFree(ty::FreeRegion { scope: scope,
 357                                     bound_region: br})
 358       }
 359       's' => {
 360         let scope = parse_scope(st);
 361         assert_eq!(next(st), '|');
 362         ty::ReScope(scope)
 363       }
 364       't' => {
 365         ty::ReStatic
 366       }
 367       'e' => {
 368         ty::ReStatic
 369       }
 370       _ => panic!("parse_region: bad input")
 371     }
 372 }
 373
 374 fn parse_scope(st: &mut PState) -> region::CodeExtent {
 375     match next(st) {
 376         'M' => {
 377             let node_id = parse_uint(st) as ast::NodeId;
 378             region::CodeExtent::Misc(node_id)
 379         }
 380         'D' => {
 381             let node_id = parse_uint(st) as ast::NodeId;
 382             region::CodeExtent::DestructionScope(node_id)
 383         }
 384         'B' => {
 385             let node_id = parse_uint(st) as ast::NodeId;
 386             let first_stmt_index = parse_uint(st);
 387             let block_remainder = region::BlockRemainder {
 388                 block: node_id, first_statement_index: first_stmt_index,
 389             };
 390             region::CodeExtent::Remainder(block_remainder)
 391         }
 392         _ => panic!("parse_scope: bad input")
 393     }
 394 }
 395
 396 fn parse_destruction_scope_data(st: &mut PState) -> region::DestructionScopeData {
 397     let node_id = parse_uint(st) as ast::NodeId;
 398     region::DestructionScopeData::new(node_id)
 399 }
 400
 401 fn parse_opt<'a, 'tcx, T, F>(st: &mut PState<'a, 'tcx>, f: F) -> Option<T> where
 402     F: FnOnce(&mut PState<'a, 'tcx>) -> T,
 403 {
 404     match next(st) {
 405       'n' => None,
 406       's' => Some(f(st)),
 407       _ => panic!("parse_opt: bad input")
 408     }
 409 }
 410
 411 fn parse_str(st: &mut PState, term: char) -> String {
 412     let mut result = String::new();
 413     while peek(st) != term {
 414         unsafe {
 415             result.as_mut_vec().push_all(&[next_byte(st)])
 416         }
 417     }
 418     next(st);
 419     result
 420 }
 421
 422 fn parse_trait_ref<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, mut conv: F)
 423                                 -> Rc<ty::TraitRef<'tcx>> where
 424     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 425 {
 426     parse_trait_ref_(st, &mut conv)
 427 }
 428
 429 fn parse_trait_ref_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, conv: &mut F)
 430                               -> Rc<ty::TraitRef<'tcx>> where
 431     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 432 {
 433     let def = parse_def_(st, NominalType, conv);
 434     let substs = st.tcx.mk_substs(parse_substs_(st, conv));
 435     Rc::new(ty::TraitRef {def_id: def, substs: substs})
 436 }
 437
 438 fn parse_ty<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, mut conv: F) -> Ty<'tcx> where
 439     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 440 {
 441     parse_ty_(st, &mut conv)
 442 }
 443
 444 fn parse_ty_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, conv: &mut F) -> Ty<'tcx> where
 445     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 446 {
 447     let tcx = st.tcx;
 448     match next(st) {
 449       'b' => return tcx.types.bool,
 450       'i' => { /* eat the s of is */ next(st); return tcx.types.int },
 451       'u' => { /* eat the s of us */ next(st); return tcx.types.uint },
 452       'M' => {
 453         match next(st) {
 454           'b' => return tcx.types.u8,
 455           'w' => return tcx.types.u16,
 456           'l' => return tcx.types.u32,
 457           'd' => return tcx.types.u64,
 458           'B' => return tcx.types.i8,
 459           'W' => return tcx.types.i16,
 460           'L' => return tcx.types.i32,
 461           'D' => return tcx.types.i64,
 462           'f' => return tcx.types.f32,
 463           'F' => return tcx.types.f64,
 464           _ => panic!("parse_ty: bad numeric type")
 465         }
 466       }
 467       'c' => return tcx.types.char,
 468       't' => {
 469         assert_eq!(next(st), '[');
 470         let def = parse_def_(st, NominalType, conv);
 471         let substs = parse_substs_(st, conv);
 472         assert_eq!(next(st), ']');
 473         return ty::mk_enum(tcx, def, st.tcx.mk_substs(substs));
 474       }
 475       'x' => {
 476         assert_eq!(next(st), '[');
 477         let trait_ref = ty::Binder(parse_trait_ref_(st, conv));
 478         let bounds = parse_existential_bounds_(st, conv);
 479         assert_eq!(next(st), ']');
 480         return ty::mk_trait(tcx, trait_ref, bounds);
 481       }
 482       'p' => {
 483         assert_eq!(next(st), '[');
 484         let index = parse_u32(st);
 485         assert_eq!(next(st), '|');
 486         let space = parse_param_space(st);
 487         assert_eq!(next(st), '|');
 488         let name = token::intern(&parse_str(st, ']')[]);
 489         return ty::mk_param(tcx, space, index, name);
 490       }
 491       '~' => return ty::mk_uniq(tcx, parse_ty_(st, conv)),
 492       '*' => return ty::mk_ptr(tcx, parse_mt_(st, conv)),
 493       '&' => {
 494         let r = parse_region_(st, conv);
 495         let mt = parse_mt_(st, conv);
 496         return ty::mk_rptr(tcx, tcx.mk_region(r), mt);
 497       }
 498       'V' => {
 499         let t = parse_ty_(st, conv);
 500         let sz = parse_size(st);
 501         return ty::mk_vec(tcx, t, sz);
 502       }
 503       'v' => {
 504         return ty::mk_str(tcx);
 505       }
 506       'T' => {
 507         assert_eq!(next(st), '[');
 508         let mut params = Vec::new();
 509         while peek(st) != ']' { params.push(parse_ty_(st, conv)); }
 510         st.pos = st.pos + 1;
 511         return ty::mk_tup(tcx, params);
 512       }
 513       'F' => {
 514           let def_id = parse_def_(st, NominalType, conv);
 515           return ty::mk_bare_fn(tcx, Some(def_id),
 516                                 tcx.mk_bare_fn(parse_bare_fn_ty_(st, conv)));
 517       }
 518       'G' => {
 519           return ty::mk_bare_fn(tcx, None,
 520                                 tcx.mk_bare_fn(parse_bare_fn_ty_(st, conv)));
 521       }
 522       '#' => {
 523         let pos = parse_hex(st);
 524         assert_eq!(next(st), ':');
 525         let len = parse_hex(st);
 526         assert_eq!(next(st), '#');
 527         let key = ty::creader_cache_key {cnum: st.krate,
 528                                          pos: pos,
 529                                          len: len };
 530
 531         match tcx.rcache.borrow().get(&key).cloned() {
 532           Some(tt) => return tt,
 533           None => {}
 534         }
 535         let mut ps = PState {
 536             pos: pos,
 537             .. *st
 538         };
 539         let tt = parse_ty_(&mut ps, conv);
 540         tcx.rcache.borrow_mut().insert(key, tt);
 541         return tt;
 542       }
 543       '\"' => {
 544         let _ = parse_def_(st, TypeWithId, conv);
 545         let inner = parse_ty_(st, conv);
 546         inner
 547       }
 548       'a' => {
 549           assert_eq!(next(st), '[');
 550           let did = parse_def_(st, NominalType, conv);
 551           let substs = parse_substs_(st, conv);
 552           assert_eq!(next(st), ']');
 553           return ty::mk_struct(st.tcx, did, st.tcx.mk_substs(substs));
 554       }
 555       'k' => {
 556           assert_eq!(next(st), '[');
 557           let did = parse_def_(st, ClosureSource, conv);
 558           let region = parse_region_(st, conv);
 559           let substs = parse_substs_(st, conv);
 560           assert_eq!(next(st), ']');
 561           return ty::mk_closure(st.tcx, did,
 562                   st.tcx.mk_region(region), st.tcx.mk_substs(substs));
 563       }
 564       'P' => {
 565           assert_eq!(next(st), '[');
 566           let trait_ref = parse_trait_ref_(st, conv);
 567           let name = token::intern(&parse_str(st, ']'));
 568           return ty::mk_projection(tcx, trait_ref, name);
 569       }
 570       'e' => {
 571           return tcx.types.err;
 572       }
 573       c => { panic!("unexpected char in type string: {}", c);}
 574     }
 575 }
 576
 577 fn parse_mutability(st: &mut PState) -> ast::Mutability {
 578     match peek(st) {
 579       'm' => { next(st); ast::MutMutable }
 580       _ => { ast::MutImmutable }
 581     }
 582 }
 583
 584 fn parse_mt_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, conv: &mut F) -> ty::mt<'tcx> where
 585     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 586 {
 587     let m = parse_mutability(st);
 588     ty::mt { ty: parse_ty_(st, conv), mutbl: m }
 589 }
 590
 591 fn parse_def_<F>(st: &mut PState, source: DefIdSource, conv: &mut F) -> ast::DefId where
 592     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 593 {
 594     return (*conv)(source, scan(st, |c| { c == '|' }, parse_def_id));
 595 }
 596
 597 fn parse_uint(st: &mut PState) -> uint {
 598     let mut n = 0;
 599     loop {
 600         let cur = peek(st);
 601         if cur < '0' || cur > '9' { return n; }
 602         st.pos = st.pos + 1;
 603         n *= 10;
 604         n += (cur as uint) - ('0' as uint);
 605     };
 606 }
 607
 608 fn parse_u32(st: &mut PState) -> u32 {
 609     let n = parse_uint(st);
 610     let m = n as u32;
 611     assert_eq!(m as uint, n);
 612     m
 613 }
 614
 615 fn parse_param_space(st: &mut PState) -> subst::ParamSpace {
 616     subst::ParamSpace::from_uint(parse_uint(st))
 617 }
 618
 619 fn parse_hex(st: &mut PState) -> uint {
 620     let mut n = 0;
 621     loop {
 622         let cur = peek(st);
 623         if (cur < '0' || cur > '9') && (cur < 'a' || cur > 'f') { return n; }
 624         st.pos = st.pos + 1;
 625         n *= 16;
 626         if '0' <= cur && cur <= '9' {
 627             n += (cur as uint) - ('0' as uint);
 628         } else { n += 10 + (cur as uint) - ('a' as uint); }
 629     };
 630 }
 631
 632 fn parse_unsafety(c: char) -> ast::Unsafety {
 633     match c {
 634         'u' => ast::Unsafety::Unsafe,
 635         'n' => ast::Unsafety::Normal,
 636         _ => panic!("parse_unsafety: bad unsafety {}", c)
 637     }
 638 }
 639
 640 fn parse_abi_set(st: &mut PState) -> abi::Abi {
 641     assert_eq!(next(st), '[');
 642     scan(st, |c| c == ']', |bytes| {
 643         let abi_str = str::from_utf8(bytes).unwrap();
 644         abi::lookup(&abi_str[..]).expect(abi_str)
 645     })
 646 }
 647
 648 fn parse_closure_ty<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>,
 649                                  mut conv: F) -> ty::ClosureTy<'tcx> where
 650     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 651 {
 652     parse_closure_ty_(st, &mut conv)
 653 }
 654
 655 fn parse_closure_ty_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>,
 656                                  conv: &mut F) -> ty::ClosureTy<'tcx> where
 657     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 658 {
 659     let unsafety = parse_unsafety(next(st));
 660     let sig = parse_sig_(st, conv);
 661     let abi = parse_abi_set(st);
 662     ty::ClosureTy {
 663         unsafety: unsafety,
 664         sig: sig,
 665         abi: abi,
 666     }
 667 }
 668
 669 fn parse_bare_fn_ty<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>,
 670                                  mut conv: F) -> ty::BareFnTy<'tcx> where
 671     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 672 {
 673     parse_bare_fn_ty_(st, &mut conv)
 674 }
 675
 676 fn parse_bare_fn_ty_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>,
 677                                  conv: &mut F) -> ty::BareFnTy<'tcx> where
 678     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 679 {
 680     let unsafety = parse_unsafety(next(st));
 681     let abi = parse_abi_set(st);
 682     let sig = parse_sig_(st, conv);
 683     ty::BareFnTy {
 684         unsafety: unsafety,
 685         abi: abi,
 686         sig: sig
 687     }
 688 }
 689
 690 fn parse_sig_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, conv: &mut F) -> ty::PolyFnSig<'tcx> where
 691     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 692 {
 693     assert_eq!(next(st), '[');
 694     let mut inputs = Vec::new();
 695     while peek(st) != ']' {
 696         inputs.push(parse_ty_(st, conv));
 697     }
 698     st.pos += 1; // eat the ']'
 699     let variadic = match next(st) {
 700         'V' => true,
 701         'N' => false,
 702         r => panic!(format!("bad variadic: {}", r)),
 703     };
 704     let output = match peek(st) {
 705         'z' => {
 706           st.pos += 1;
 707           ty::FnDiverging
 708         }
 709         _ => ty::FnConverging(parse_ty_(st, conv))
 710     };
 711     ty::Binder(ty::FnSig {inputs: inputs,
 712                         output: output,
 713                         variadic: variadic})
 714 }
 715
 716 // Rust metadata parsing
 717 pub fn parse_def_id(buf: &[u8]) -> ast::DefId {
 718     let mut colon_idx = 0;
 719     let len = buf.len();
 720     while colon_idx < len && buf[colon_idx] != ':' as u8 { colon_idx += 1; }
 721     if colon_idx == len {
 722         error!("didn't find ':' when parsing def id");
 723         panic!();
 724     }
 725
 726     let crate_part = &buf[0..colon_idx];
 727     let def_part = &buf[colon_idx + 1..len];
 728
 729     let crate_num = match str::from_utf8(crate_part).ok().and_then(|s| {
 730         s.parse::<uint>().ok()
 731     }) {
 732        Some(cn) => cn as ast::CrateNum,
 733        None => panic!("internal error: parse_def_id: crate number expected, found {:?}",
 734                      crate_part)
 735     };
 736     let def_num = match str::from_utf8(def_part).ok().and_then(|s| {
 737         s.parse::<uint>().ok()
 738     }) {
 739        Some(dn) => dn as ast::NodeId,
 740        None => panic!("internal error: parse_def_id: id expected, found {:?}",
 741                      def_part)
 742     };
 743     ast::DefId { krate: crate_num, node: def_num }
 744 }
 745
 746 pub fn parse_predicate_data<'tcx, F>(data: &[u8],
 747                                      start: uint,
 748                                      crate_num: ast::CrateNum,
 749                                      tcx: &ty::ctxt<'tcx>,
 750                                      conv: F)
 751                                      -> ty::Predicate<'tcx> where
 752     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 753 {
 754     let mut st = parse_state_from_data(data, crate_num, start, tcx);
 755     parse_predicate(&mut st, conv)
 756 }
 757
 758 pub fn parse_predicate<'a,'tcx, F>(st: &mut PState<'a, 'tcx>,
 759                                    mut conv: F)
 760                                    -> ty::Predicate<'tcx> where
 761     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 762 {
 763     parse_predicate_(st, &mut conv)
 764 }
 765
 766 fn parse_predicate_<'a,'tcx, F>(st: &mut PState<'a, 'tcx>,
 767                                 conv: &mut F)
 768                                 -> ty::Predicate<'tcx> where
 769     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 770 {
 771     match next(st) {
 772         't' => ty::Binder(parse_trait_ref_(st, conv)).as_predicate(),
 773         'e' => ty::Binder(ty::EquatePredicate(parse_ty_(st, conv),
 774                                               parse_ty_(st, conv))).as_predicate(),
 775         'r' => ty::Binder(ty::OutlivesPredicate(parse_region_(st, conv),
 776                                                 parse_region_(st, conv))).as_predicate(),
 777         'o' => ty::Binder(ty::OutlivesPredicate(parse_ty_(st, conv),
 778                                                 parse_region_(st, conv))).as_predicate(),
 779         'p' => ty::Binder(parse_projection_predicate_(st, conv)).as_predicate(),
 780         c => panic!("Encountered invalid character in metadata: {}", c)
 781     }
 782 }
 783
 784 fn parse_projection_predicate_<'a,'tcx, F>(
 785     st: &mut PState<'a, 'tcx>,
 786     conv: &mut F,
 787 ) -> ty::ProjectionPredicate<'tcx> where
 788     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 789 {
 790     ty::ProjectionPredicate {
 791         projection_ty: ty::ProjectionTy {
 792             trait_ref: parse_trait_ref_(st, conv),
 793             item_name: token::str_to_ident(&parse_str(st, '|')).name,
 794         },
 795         ty: parse_ty_(st, conv),
 796     }
 797 }
 798
 799 pub fn parse_type_param_def_data<'tcx, F>(data: &[u8], start: uint,
 800                                           crate_num: ast::CrateNum, tcx: &ty::ctxt<'tcx>,
 801                                           conv: F) -> ty::TypeParameterDef<'tcx> where
 802     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 803 {
 804     let mut st = parse_state_from_data(data, crate_num, start, tcx);
 805     parse_type_param_def(&mut st, conv)
 806 }
 807
 808 fn parse_type_param_def<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, mut conv: F)
 809                                      -> ty::TypeParameterDef<'tcx> where
 810     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 811 {
 812     parse_type_param_def_(st, &mut conv)
 813 }
 814
 815 fn parse_type_param_def_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, conv: &mut F)
 816                                       -> ty::TypeParameterDef<'tcx> where
 817     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 818 {
 819     let name = parse_name(st, ':');
 820     let def_id = parse_def_(st, NominalType, conv);
 821     let space = parse_param_space(st);
 822     assert_eq!(next(st), '|');
 823     let index = parse_u32(st);
 824     assert_eq!(next(st), '|');
 825     let bounds = parse_bounds_(st, conv);
 826     let default = parse_opt(st, |st| parse_ty_(st, conv));
 827     let object_lifetime_default = parse_object_lifetime_default(st, conv);
 828
 829     ty::TypeParameterDef {
 830         name: name,
 831         def_id: def_id,
 832         space: space,
 833         index: index,
 834         bounds: bounds,
 835         default: default,
 836         object_lifetime_default: object_lifetime_default,
 837     }
 838 }
 839
 840 fn parse_object_lifetime_default<'a,'tcx, F>(st: &mut PState<'a,'tcx>,
 841                                              conv: &mut F)
 842                                              -> Option<ty::ObjectLifetimeDefault>
 843     where F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 844 {
 845     match next(st) {
 846         'n' => None,
 847         'a' => Some(ty::ObjectLifetimeDefault::Ambiguous),
 848         's' => {
 849             let region = parse_region_(st, conv);
 850             Some(ty::ObjectLifetimeDefault::Specific(region))
 851         }
 852         _ => panic!("parse_object_lifetime_default: bad input")
 853     }
 854 }
 855
 856 fn parse_existential_bounds<'a,'tcx, F>(st: &mut PState<'a,'tcx>,
 857                                         mut conv: F)
 858                                         -> ty::ExistentialBounds<'tcx> where
 859     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 860 {
 861     parse_existential_bounds_(st, &mut conv)
 862 }
 863
 864 fn parse_existential_bounds_<'a,'tcx, F>(st: &mut PState<'a,'tcx>,
 865                                         conv: &mut F)
 866                                         -> ty::ExistentialBounds<'tcx> where
 867     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 868 {
 869     let ty::ParamBounds { trait_bounds, mut region_bounds, builtin_bounds, projection_bounds } =
 870          parse_bounds_(st, conv);
 871     assert_eq!(region_bounds.len(), 1);
 872     assert_eq!(trait_bounds.len(), 0);
 873     let region_bound = region_bounds.pop().unwrap();
 874     return ty::ExistentialBounds { region_bound: region_bound,
 875                                    builtin_bounds: builtin_bounds,
 876                                    projection_bounds: projection_bounds };
 877 }
 878
 879 fn parse_builtin_bounds<F>(st: &mut PState, mut _conv: F) -> ty::BuiltinBounds where
 880     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 881 {
 882     parse_builtin_bounds_(st, &mut _conv)
 883 }
 884
 885 fn parse_builtin_bounds_<F>(st: &mut PState, _conv: &mut F) -> ty::BuiltinBounds where
 886     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 887 {
 888     let mut builtin_bounds = ty::empty_builtin_bounds();
 889
 890     loop {
 891         match next(st) {
 892             'S' => {
 893                 builtin_bounds.insert(ty::BoundSend);
 894             }
 895             'Z' => {
 896                 builtin_bounds.insert(ty::BoundSized);
 897             }
 898             'P' => {
 899                 builtin_bounds.insert(ty::BoundCopy);
 900             }
 901             'T' => {
 902                 builtin_bounds.insert(ty::BoundSync);
 903             }
 904             '.' => {
 905                 return builtin_bounds;
 906             }
 907             c => {
 908                 panic!("parse_bounds: bad builtin bounds ('{}')", c)
 909             }
 910         }
 911     }
 912 }
 913
 914 fn parse_bounds<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, mut conv: F)
 915                              -> ty::ParamBounds<'tcx> where
 916     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 917 {
 918     parse_bounds_(st, &mut conv)
 919 }
 920
 921 fn parse_bounds_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, conv: &mut F)
 922                               -> ty::ParamBounds<'tcx> where
 923     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 924 {
 925     let builtin_bounds = parse_builtin_bounds_(st, conv);
 926
 927     let mut param_bounds = ty::ParamBounds {
 928         region_bounds: Vec::new(),
 929         builtin_bounds: builtin_bounds,
 930         trait_bounds: Vec::new(),
 931         projection_bounds: Vec::new(),
 932     };
 933     loop {
 934         match next(st) {
 935             'R' => {
 936                 param_bounds.region_bounds.push(
 937                     parse_region_(st, conv));
 938             }
 939             'I' => {
 940                 param_bounds.trait_bounds.push(
 941                     ty::Binder(parse_trait_ref_(st, conv)));
 942             }
 943             'P' => {
 944                 param_bounds.projection_bounds.push(
 945                     ty::Binder(parse_projection_predicate_(st, conv)));
 946             }
 947             '.' => {
 948                 return param_bounds;
 949             }
 950             c => {
 951                 panic!("parse_bounds: bad bounds ('{}')", c)
 952             }
 953         }
 954     }
 955 }