src/librustc/metadata/tydecode.rs

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