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_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().iter() {
 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_scope(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         _ => panic!("parse_scope: bad input")
 381     }
 382 }
 383
 384 fn parse_opt<'a, 'tcx, T, F>(st: &mut PState<'a, 'tcx>, f: F) -> Option<T> where
 385     F: FnOnce(&mut PState<'a, 'tcx>) -> T,
 386 {
 387     match next(st) {
 388       'n' => None,
 389       's' => Some(f(st)),
 390       _ => panic!("parse_opt: bad input")
 391     }
 392 }
 393
 394 fn parse_str(st: &mut PState, term: char) -> String {
 395     let mut result = String::new();
 396     while peek(st) != term {
 397         unsafe {
 398             result.as_mut_vec().push_all(&[next_byte(st)])
 399         }
 400     }
 401     next(st);
 402     result
 403 }
 404
 405 fn parse_trait_ref<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, mut conv: F)
 406                                 -> Rc<ty::TraitRef<'tcx>> where
 407     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 408 {
 409     parse_trait_ref_(st, &mut conv)
 410 }
 411
 412 fn parse_trait_ref_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, conv: &mut F)
 413                               -> Rc<ty::TraitRef<'tcx>> where
 414     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 415 {
 416     let def = parse_def_(st, NominalType, conv);
 417     let substs = st.tcx.mk_substs(parse_substs_(st, conv));
 418     Rc::new(ty::TraitRef {def_id: def, substs: substs})
 419 }
 420
 421 fn parse_ty<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, mut conv: F) -> Ty<'tcx> where
 422     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 423 {
 424     parse_ty_(st, &mut conv)
 425 }
 426
 427 fn parse_ty_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, conv: &mut F) -> Ty<'tcx> where
 428     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 429 {
 430     let tcx = st.tcx;
 431     match next(st) {
 432       'b' => return tcx.types.bool,
 433       'i' => { /* eat the s of is */ next(st); return tcx.types.int },
 434       'u' => { /* eat the s of us */ next(st); return tcx.types.uint },
 435       'M' => {
 436         match next(st) {
 437           'b' => return tcx.types.u8,
 438           'w' => return tcx.types.u16,
 439           'l' => return tcx.types.u32,
 440           'd' => return tcx.types.u64,
 441           'B' => return tcx.types.i8,
 442           'W' => return tcx.types.i16,
 443           'L' => return tcx.types.i32,
 444           'D' => return tcx.types.i64,
 445           'f' => return tcx.types.f32,
 446           'F' => return tcx.types.f64,
 447           _ => panic!("parse_ty: bad numeric type")
 448         }
 449       }
 450       'c' => return tcx.types.char,
 451       't' => {
 452         assert_eq!(next(st), '[');
 453         let def = parse_def_(st, NominalType, conv);
 454         let substs = parse_substs_(st, conv);
 455         assert_eq!(next(st), ']');
 456         return ty::mk_enum(tcx, def, st.tcx.mk_substs(substs));
 457       }
 458       'x' => {
 459         assert_eq!(next(st), '[');
 460         let trait_ref = ty::Binder(parse_trait_ref_(st, conv));
 461         let bounds = parse_existential_bounds_(st, conv);
 462         assert_eq!(next(st), ']');
 463         return ty::mk_trait(tcx, trait_ref, bounds);
 464       }
 465       'p' => {
 466         assert_eq!(next(st), '[');
 467         let index = parse_u32(st);
 468         assert_eq!(next(st), '|');
 469         let space = parse_param_space(st);
 470         assert_eq!(next(st), '|');
 471         let name = token::intern(&parse_str(st, ']')[]);
 472         return ty::mk_param(tcx, space, index, name);
 473       }
 474       '~' => return ty::mk_uniq(tcx, parse_ty_(st, conv)),
 475       '*' => return ty::mk_ptr(tcx, parse_mt_(st, conv)),
 476       '&' => {
 477         let r = parse_region_(st, conv);
 478         let mt = parse_mt_(st, conv);
 479         return ty::mk_rptr(tcx, tcx.mk_region(r), mt);
 480       }
 481       'V' => {
 482         let t = parse_ty_(st, conv);
 483         let sz = parse_size(st);
 484         return ty::mk_vec(tcx, t, sz);
 485       }
 486       'v' => {
 487         return ty::mk_str(tcx);
 488       }
 489       'T' => {
 490         assert_eq!(next(st), '[');
 491         let mut params = Vec::new();
 492         while peek(st) != ']' { params.push(parse_ty_(st, conv)); }
 493         st.pos = st.pos + 1u;
 494         return ty::mk_tup(tcx, params);
 495       }
 496       'F' => {
 497           let def_id = parse_def_(st, NominalType, conv);
 498           return ty::mk_bare_fn(tcx, Some(def_id),
 499                                 tcx.mk_bare_fn(parse_bare_fn_ty_(st, conv)));
 500       }
 501       'G' => {
 502           return ty::mk_bare_fn(tcx, None,
 503                                 tcx.mk_bare_fn(parse_bare_fn_ty_(st, conv)));
 504       }
 505       '#' => {
 506         let pos = parse_hex(st);
 507         assert_eq!(next(st), ':');
 508         let len = parse_hex(st);
 509         assert_eq!(next(st), '#');
 510         let key = ty::creader_cache_key {cnum: st.krate,
 511                                          pos: pos,
 512                                          len: len };
 513
 514         match tcx.rcache.borrow().get(&key).cloned() {
 515           Some(tt) => return tt,
 516           None => {}
 517         }
 518         let mut ps = PState {
 519             pos: pos,
 520             .. *st
 521         };
 522         let tt = parse_ty_(&mut ps, conv);
 523         tcx.rcache.borrow_mut().insert(key, tt);
 524         return tt;
 525       }
 526       '\"' => {
 527         let _ = parse_def_(st, TypeWithId, conv);
 528         let inner = parse_ty_(st, conv);
 529         inner
 530       }
 531       'a' => {
 532           assert_eq!(next(st), '[');
 533           let did = parse_def_(st, NominalType, conv);
 534           let substs = parse_substs_(st, conv);
 535           assert_eq!(next(st), ']');
 536           return ty::mk_struct(st.tcx, did, st.tcx.mk_substs(substs));
 537       }
 538       'k' => {
 539           assert_eq!(next(st), '[');
 540           let did = parse_def_(st, UnboxedClosureSource, conv);
 541           let region = parse_region_(st, conv);
 542           let substs = parse_substs_(st, conv);
 543           assert_eq!(next(st), ']');
 544           return ty::mk_unboxed_closure(st.tcx, did,
 545                   st.tcx.mk_region(region), st.tcx.mk_substs(substs));
 546       }
 547       'P' => {
 548           assert_eq!(next(st), '[');
 549           let trait_ref = parse_trait_ref_(st, conv);
 550           let name = token::intern(parse_str(st, ']').as_slice());
 551           return ty::mk_projection(tcx, trait_ref, name);
 552       }
 553       'e' => {
 554           return tcx.types.err;
 555       }
 556       c => { panic!("unexpected char in type string: {}", c);}
 557     }
 558 }
 559
 560 fn parse_mutability(st: &mut PState) -> ast::Mutability {
 561     match peek(st) {
 562       'm' => { next(st); ast::MutMutable }
 563       _ => { ast::MutImmutable }
 564     }
 565 }
 566
 567 fn parse_mt_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, conv: &mut F) -> ty::mt<'tcx> where
 568     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 569 {
 570     let m = parse_mutability(st);
 571     ty::mt { ty: parse_ty_(st, conv), mutbl: m }
 572 }
 573
 574 fn parse_def_<F>(st: &mut PState, source: DefIdSource, conv: &mut F) -> ast::DefId where
 575     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 576 {
 577     return (*conv)(source, scan(st, |c| { c == '|' }, parse_def_id));
 578 }
 579
 580 fn parse_uint(st: &mut PState) -> uint {
 581     let mut n = 0;
 582     loop {
 583         let cur = peek(st);
 584         if cur < '0' || cur > '9' { return n; }
 585         st.pos = st.pos + 1u;
 586         n *= 10;
 587         n += (cur as uint) - ('0' as uint);
 588     };
 589 }
 590
 591 fn parse_u32(st: &mut PState) -> u32 {
 592     let n = parse_uint(st);
 593     let m = n as u32;
 594     assert_eq!(m as uint, n);
 595     m
 596 }
 597
 598 fn parse_param_space(st: &mut PState) -> subst::ParamSpace {
 599     subst::ParamSpace::from_uint(parse_uint(st))
 600 }
 601
 602 fn parse_hex(st: &mut PState) -> uint {
 603     let mut n = 0u;
 604     loop {
 605         let cur = peek(st);
 606         if (cur < '0' || cur > '9') && (cur < 'a' || cur > 'f') { return n; }
 607         st.pos = st.pos + 1u;
 608         n *= 16u;
 609         if '0' <= cur && cur <= '9' {
 610             n += (cur as uint) - ('0' as uint);
 611         } else { n += 10u + (cur as uint) - ('a' as uint); }
 612     };
 613 }
 614
 615 fn parse_unsafety(c: char) -> ast::Unsafety {
 616     match c {
 617         'u' => ast::Unsafety::Unsafe,
 618         'n' => ast::Unsafety::Normal,
 619         _ => panic!("parse_unsafety: bad unsafety {}", c)
 620     }
 621 }
 622
 623 fn parse_abi_set(st: &mut PState) -> abi::Abi {
 624     assert_eq!(next(st), '[');
 625     scan(st, |c| c == ']', |bytes| {
 626         let abi_str = str::from_utf8(bytes).unwrap();
 627         abi::lookup(&abi_str[]).expect(abi_str)
 628     })
 629 }
 630
 631 fn parse_closure_ty<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>,
 632                                  mut conv: F) -> ty::ClosureTy<'tcx> where
 633     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 634 {
 635     parse_closure_ty_(st, &mut conv)
 636 }
 637
 638 fn parse_closure_ty_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>,
 639                                  conv: &mut F) -> ty::ClosureTy<'tcx> where
 640     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 641 {
 642     let unsafety = parse_unsafety(next(st));
 643     let sig = parse_sig_(st, conv);
 644     let abi = parse_abi_set(st);
 645     ty::ClosureTy {
 646         unsafety: unsafety,
 647         sig: sig,
 648         abi: abi,
 649     }
 650 }
 651
 652 fn parse_bare_fn_ty<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>,
 653                                  mut conv: F) -> ty::BareFnTy<'tcx> where
 654     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 655 {
 656     parse_bare_fn_ty_(st, &mut conv)
 657 }
 658
 659 fn parse_bare_fn_ty_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>,
 660                                  conv: &mut F) -> ty::BareFnTy<'tcx> where
 661     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 662 {
 663     let unsafety = parse_unsafety(next(st));
 664     let abi = parse_abi_set(st);
 665     let sig = parse_sig_(st, conv);
 666     ty::BareFnTy {
 667         unsafety: unsafety,
 668         abi: abi,
 669         sig: sig
 670     }
 671 }
 672
 673 fn parse_sig_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, conv: &mut F) -> ty::PolyFnSig<'tcx> where
 674     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 675 {
 676     assert_eq!(next(st), '[');
 677     let mut inputs = Vec::new();
 678     while peek(st) != ']' {
 679         inputs.push(parse_ty_(st, conv));
 680     }
 681     st.pos += 1u; // eat the ']'
 682     let variadic = match next(st) {
 683         'V' => true,
 684         'N' => false,
 685         r => panic!(format!("bad variadic: {}", r)),
 686     };
 687     let output = match peek(st) {
 688         'z' => {
 689           st.pos += 1u;
 690           ty::FnDiverging
 691         }
 692         _ => ty::FnConverging(parse_ty_(st, conv))
 693     };
 694     ty::Binder(ty::FnSig {inputs: inputs,
 695                         output: output,
 696                         variadic: variadic})
 697 }
 698
 699 // Rust metadata parsing
 700 pub fn parse_def_id(buf: &[u8]) -> ast::DefId {
 701     let mut colon_idx = 0u;
 702     let len = buf.len();
 703     while colon_idx < len && buf[colon_idx] != ':' as u8 { colon_idx += 1u; }
 704     if colon_idx == len {
 705         error!("didn't find ':' when parsing def id");
 706         panic!();
 707     }
 708
 709     let crate_part = &buf[0u..colon_idx];
 710     let def_part = &buf[colon_idx + 1u..len];
 711
 712     let crate_num = match str::from_utf8(crate_part).ok().and_then(|s| s.parse::<uint>()) {
 713        Some(cn) => cn as ast::CrateNum,
 714        None => panic!("internal error: parse_def_id: crate number expected, found {:?}",
 715                      crate_part)
 716     };
 717     let def_num = match str::from_utf8(def_part).ok().and_then(|s| s.parse::<uint>()) {
 718        Some(dn) => dn as ast::NodeId,
 719        None => panic!("internal error: parse_def_id: id expected, found {:?}",
 720                      def_part)
 721     };
 722     ast::DefId { krate: crate_num, node: def_num }
 723 }
 724
 725 pub fn parse_predicate_data<'tcx, F>(data: &[u8],
 726                                      start: uint,
 727                                      crate_num: ast::CrateNum,
 728                                      tcx: &ty::ctxt<'tcx>,
 729                                      conv: F)
 730                                      -> ty::Predicate<'tcx> where
 731     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 732 {
 733     let mut st = parse_state_from_data(data, crate_num, start, tcx);
 734     parse_predicate(&mut st, conv)
 735 }
 736
 737 pub fn parse_predicate<'a,'tcx, F>(st: &mut PState<'a, 'tcx>,
 738                                    mut conv: F)
 739                                    -> ty::Predicate<'tcx> where
 740     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 741 {
 742     parse_predicate_(st, &mut conv)
 743 }
 744
 745 fn parse_predicate_<'a,'tcx, F>(st: &mut PState<'a, 'tcx>,
 746                                 conv: &mut F)
 747                                 -> ty::Predicate<'tcx> where
 748     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 749 {
 750     match next(st) {
 751         't' => ty::Binder(parse_trait_ref_(st, conv)).as_predicate(),
 752         'e' => ty::Binder(ty::EquatePredicate(parse_ty_(st, conv),
 753                                               parse_ty_(st, conv))).as_predicate(),
 754         'r' => ty::Binder(ty::OutlivesPredicate(parse_region_(st, conv),
 755                                                 parse_region_(st, conv))).as_predicate(),
 756         'o' => ty::Binder(ty::OutlivesPredicate(parse_ty_(st, conv),
 757                                                 parse_region_(st, conv))).as_predicate(),
 758         'p' => ty::Binder(parse_projection_predicate_(st, conv)).as_predicate(),
 759         c => panic!("Encountered invalid character in metadata: {}", c)
 760     }
 761 }
 762
 763 fn parse_projection_predicate_<'a,'tcx, F>(
 764     st: &mut PState<'a, 'tcx>,
 765     conv: &mut F,
 766 ) -> ty::ProjectionPredicate<'tcx> where
 767     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 768 {
 769     ty::ProjectionPredicate {
 770         projection_ty: ty::ProjectionTy {
 771             trait_ref: parse_trait_ref_(st, conv),
 772             item_name: token::str_to_ident(parse_str(st, '|').as_slice()).name,
 773         },
 774         ty: parse_ty_(st, conv),
 775     }
 776 }
 777
 778 pub fn parse_type_param_def_data<'tcx, F>(data: &[u8], start: uint,
 779                                           crate_num: ast::CrateNum, tcx: &ty::ctxt<'tcx>,
 780                                           conv: F) -> ty::TypeParameterDef<'tcx> where
 781     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 782 {
 783     let mut st = parse_state_from_data(data, crate_num, start, tcx);
 784     parse_type_param_def(&mut st, conv)
 785 }
 786
 787 fn parse_type_param_def<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, mut conv: F)
 788                                      -> ty::TypeParameterDef<'tcx> where
 789     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 790 {
 791     parse_type_param_def_(st, &mut conv)
 792 }
 793
 794 fn parse_type_param_def_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, conv: &mut F)
 795                                       -> ty::TypeParameterDef<'tcx> where
 796     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 797 {
 798     let name = parse_name(st, ':');
 799     let def_id = parse_def_(st, NominalType, conv);
 800     let space = parse_param_space(st);
 801     assert_eq!(next(st), '|');
 802     let index = parse_u32(st);
 803     assert_eq!(next(st), '|');
 804     let bounds = parse_bounds_(st, conv);
 805     let default = parse_opt(st, |st| parse_ty_(st, conv));
 806
 807     ty::TypeParameterDef {
 808         name: name,
 809         def_id: def_id,
 810         space: space,
 811         index: index,
 812         bounds: bounds,
 813         default: default
 814     }
 815 }
 816
 817 fn parse_existential_bounds<'a,'tcx, F>(st: &mut PState<'a,'tcx>,
 818                                         mut conv: F)
 819                                         -> ty::ExistentialBounds<'tcx> where
 820     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 821 {
 822     parse_existential_bounds_(st, &mut conv)
 823 }
 824
 825 fn parse_existential_bounds_<'a,'tcx, F>(st: &mut PState<'a,'tcx>,
 826                                         conv: &mut F)
 827                                         -> ty::ExistentialBounds<'tcx> where
 828     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 829 {
 830     let ty::ParamBounds { trait_bounds, mut region_bounds, builtin_bounds, projection_bounds } =
 831          parse_bounds_(st, conv);
 832     assert_eq!(region_bounds.len(), 1);
 833     assert_eq!(trait_bounds.len(), 0);
 834     let region_bound = region_bounds.pop().unwrap();
 835     return ty::ExistentialBounds { region_bound: region_bound,
 836                                    builtin_bounds: builtin_bounds,
 837                                    projection_bounds: projection_bounds };
 838 }
 839
 840 fn parse_builtin_bounds<F>(st: &mut PState, mut _conv: F) -> ty::BuiltinBounds where
 841     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 842 {
 843     parse_builtin_bounds_(st, &mut _conv)
 844 }
 845
 846 fn parse_builtin_bounds_<F>(st: &mut PState, _conv: &mut F) -> ty::BuiltinBounds where
 847     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 848 {
 849     let mut builtin_bounds = ty::empty_builtin_bounds();
 850
 851     loop {
 852         match next(st) {
 853             'S' => {
 854                 builtin_bounds.insert(ty::BoundSend);
 855             }
 856             'Z' => {
 857                 builtin_bounds.insert(ty::BoundSized);
 858             }
 859             'P' => {
 860                 builtin_bounds.insert(ty::BoundCopy);
 861             }
 862             'T' => {
 863                 builtin_bounds.insert(ty::BoundSync);
 864             }
 865             '.' => {
 866                 return builtin_bounds;
 867             }
 868             c => {
 869                 panic!("parse_bounds: bad builtin bounds ('{}')", c)
 870             }
 871         }
 872     }
 873 }
 874
 875 fn parse_bounds<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, mut conv: F)
 876                              -> ty::ParamBounds<'tcx> where
 877     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 878 {
 879     parse_bounds_(st, &mut conv)
 880 }
 881
 882 fn parse_bounds_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, conv: &mut F)
 883                               -> ty::ParamBounds<'tcx> where
 884     F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
 885 {
 886     let builtin_bounds = parse_builtin_bounds_(st, conv);
 887
 888     let mut param_bounds = ty::ParamBounds {
 889         region_bounds: Vec::new(),
 890         builtin_bounds: builtin_bounds,
 891         trait_bounds: Vec::new(),
 892         projection_bounds: Vec::new(),
 893     };
 894     loop {
 895         match next(st) {
 896             'R' => {
 897                 param_bounds.region_bounds.push(
 898                     parse_region_(st, conv));
 899             }
 900             'I' => {
 901                 param_bounds.trait_bounds.push(
 902                     ty::Binder(parse_trait_ref_(st, conv)));
 903             }
 904             'P' => {
 905                 param_bounds.projection_bounds.push(
 906                     ty::Binder(parse_projection_predicate_(st, conv)));
 907             }
 908             '.' => {
 909                 return param_bounds;
 910             }
 911             c => {
 912                 panic!("parse_bounds: bad bounds ('{}')", c)
 913             }
 914         }
 915     }
 916 }