src/librustc/metadata/tydecode.rs

   1 // Copyright 2012 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
  18 use middle::ty;
  19
  20 use std::str;
  21 use std::uint;
  22 use syntax::abi::AbiSet;
  23 use syntax::abi;
  24 use syntax::ast;
  25 use syntax::ast::*;
  26 use syntax::codemap::dummy_sp;
  27 use syntax::opt_vec;
  28
  29 // Compact string representation for ty::t values. API ty_str &
  30 // parse_from_str. Extra parameters are for converting to/from def_ids in the
  31 // data buffer. Whatever format you choose should not contain pipe characters.
  32
  33 // Def id conversion: when we encounter def-ids, they have to be translated.
  34 // For example, the crate number must be converted from the crate number used
  35 // in the library we are reading from into the local crate numbers in use
  36 // here.  To perform this translation, the type decoder is supplied with a
  37 // conversion function of type `conv_did`.
  38 //
  39 // Sometimes, particularly when inlining, the correct translation of the
  40 // def-id will depend on where it originated from.  Therefore, the conversion
  41 // function is given an indicator of the source of the def-id.  See
  42 // astencode.rs for more information.
  43 pub enum DefIdSource {
  44     // Identifies a struct, trait, enum, etc.
  45     NominalType,
  46
  47     // Identifies a type alias (`type X = ...`).
  48     TypeWithId,
  49
  50     // Identifies a type parameter (`fn foo<X>() { ... }`).
  51     TypeParameter
  52 }
  53 type conv_did<'self> =
  54     &'self fn(source: DefIdSource, ast::DefId) -> ast::DefId;
  55
  56 pub struct PState<'self> {
  57     data: &'self [u8],
  58     crate: int,
  59     pos: uint,
  60     tcx: ty::ctxt
  61 }
  62
  63 fn peek(st: &PState) -> char {
  64     st.data[st.pos] as char
  65 }
  66
  67 fn next(st: &mut PState) -> char {
  68     let ch = st.data[st.pos] as char;
  69     st.pos = st.pos + 1u;
  70     return ch;
  71 }
  72
  73 fn next_byte(st: &mut PState) -> u8 {
  74     let b = st.data[st.pos];
  75     st.pos = st.pos + 1u;
  76     return b;
  77 }
  78
  79 fn scan<R>(st: &mut PState, is_last: &fn(char) -> bool,
  80            op: &fn(&[u8]) -> R) -> R
  81 {
  82     let start_pos = st.pos;
  83     debug!("scan: '{}' (start)", st.data[st.pos] as char);
  84     while !is_last(st.data[st.pos] as char) {
  85         st.pos += 1;
  86         debug!("scan: '{}'", st.data[st.pos] as char);
  87     }
  88     let end_pos = st.pos;
  89     st.pos += 1;
  90     return op(st.data.slice(start_pos, end_pos));
  91 }
  92
  93 pub fn parse_ident(st: &mut PState, last: char) -> ast::Ident {
  94     fn is_last(b: char, c: char) -> bool { return c == b; }
  95     return parse_ident_(st, |a| is_last(last, a) );
  96 }
  97
  98 fn parse_ident_(st: &mut PState, is_last: &fn(char) -> bool) -> ast::Ident {
  99     let rslt = scan(st, is_last, str::from_utf8);
 100     return st.tcx.sess.ident_of(rslt);
 101 }
 102
 103 pub fn parse_state_from_data<'a>(data: &'a [u8], crate_num: int,
 104                              pos: uint, tcx: ty::ctxt) -> PState<'a> {
 105     PState {
 106         data: data,
 107         crate: crate_num,
 108         pos: pos,
 109         tcx: tcx
 110     }
 111 }
 112
 113 pub fn parse_ty_data(data: &[u8], crate_num: int, pos: uint, tcx: ty::ctxt,
 114                      conv: conv_did) -> ty::t {
 115     let mut st = parse_state_from_data(data, crate_num, pos, tcx);
 116     parse_ty(&mut st, conv)
 117 }
 118
 119 pub fn parse_bare_fn_ty_data(data: &[u8], crate_num: int, pos: uint, tcx: ty::ctxt,
 120                              conv: conv_did) -> ty::BareFnTy {
 121     let mut st = parse_state_from_data(data, crate_num, pos, tcx);
 122     parse_bare_fn_ty(&mut st, conv)
 123 }
 124
 125 pub fn parse_trait_ref_data(data: &[u8], crate_num: int, pos: uint, tcx: ty::ctxt,
 126                             conv: conv_did) -> ty::TraitRef {
 127     let mut st = parse_state_from_data(data, crate_num, pos, tcx);
 128     parse_trait_ref(&mut st, conv)
 129 }
 130
 131 fn parse_path(st: &mut PState) -> @ast::Path {
 132     let mut idents: ~[ast::Ident] = ~[];
 133     fn is_last(c: char) -> bool { return c == '(' || c == ':'; }
 134     idents.push(parse_ident_(st, is_last));
 135     loop {
 136         match peek(st) {
 137           ':' => { next(st); next(st); }
 138           c => {
 139             if c == '(' {
 140                 return @ast::Path {
 141                     span: dummy_sp(),
 142                     global: false,
 143                     segments: idents.move_iter().map(|identifier| {
 144                         ast::PathSegment {
 145                             identifier: identifier,
 146                             lifetime: None,
 147                             types: opt_vec::Empty,
 148                         }
 149                     }).collect()
 150                 };
 151             } else {
 152                 idents.push(parse_ident_(st, is_last));
 153             }
 154           }
 155         }
 156     };
 157 }
 158
 159 fn parse_sigil(st: &mut PState) -> ast::Sigil {
 160     match next(st) {
 161         '@' => ast::ManagedSigil,
 162         '~' => ast::OwnedSigil,
 163         '&' => ast::BorrowedSigil,
 164         c => st.tcx.sess.bug(format!("parse_sigil(): bad input '{}'", c))
 165     }
 166 }
 167
 168 fn parse_vstore(st: &mut PState) -> ty::vstore {
 169     assert_eq!(next(st), '/');
 170
 171     let c = peek(st);
 172     if '0' <= c && c <= '9' {
 173         let n = parse_uint(st);
 174         assert_eq!(next(st), '|');
 175         return ty::vstore_fixed(n);
 176     }
 177
 178     match next(st) {
 179       '~' => ty::vstore_uniq,
 180       '@' => ty::vstore_box,
 181       '&' => ty::vstore_slice(parse_region(st)),
 182       c => st.tcx.sess.bug(format!("parse_vstore(): bad input '{}'", c))
 183     }
 184 }
 185
 186 fn parse_trait_store(st: &mut PState) -> ty::TraitStore {
 187     match next(st) {
 188         '~' => ty::UniqTraitStore,
 189         '@' => ty::BoxTraitStore,
 190         '&' => ty::RegionTraitStore(parse_region(st)),
 191         c => st.tcx.sess.bug(format!("parse_trait_store(): bad input '{}'", c))
 192     }
 193 }
 194
 195 fn parse_substs(st: &mut PState, conv: conv_did) -> ty::substs {
 196     let regions = parse_region_substs(st);
 197
 198     let self_ty = parse_opt(st, |st| parse_ty(st, |x,y| conv(x,y)) );
 199
 200     assert_eq!(next(st), '[');
 201     let mut params: ~[ty::t] = ~[];
 202     while peek(st) != ']' { params.push(parse_ty(st, |x,y| conv(x,y))); }
 203     st.pos = st.pos + 1u;
 204
 205     return ty::substs {
 206         regions: regions,
 207         self_ty: self_ty,
 208         tps: params
 209     };
 210 }
 211
 212 fn parse_region_substs(st: &mut PState) -> ty::RegionSubsts {
 213     match next(st) {
 214         'e' => ty::ErasedRegions,
 215         'n' => {
 216             let mut regions = opt_vec::Empty;
 217             while peek(st) != '.' {
 218                 let r = parse_region(st);
 219                 regions.push(r);
 220             }
 221             assert_eq!(next(st), '.');
 222             ty::NonerasedRegions(regions)
 223         }
 224         _ => fail!("parse_bound_region: bad input")
 225     }
 226 }
 227
 228 fn parse_bound_region(st: &mut PState) -> ty::bound_region {
 229     match next(st) {
 230       's' => ty::br_self,
 231       'a' => {
 232         let id = parse_uint(st);
 233         assert_eq!(next(st), '|');
 234         ty::br_anon(id)
 235       }
 236       '[' => ty::br_named(st.tcx.sess.ident_of(parse_str(st, ']'))),
 237       'c' => {
 238         let id = parse_uint(st) as int;
 239         assert_eq!(next(st), '|');
 240         ty::br_cap_avoid(id, @parse_bound_region(st))
 241       },
 242       _ => fail!("parse_bound_region: bad input")
 243     }
 244 }
 245
 246 fn parse_region(st: &mut PState) -> ty::Region {
 247     match next(st) {
 248       'b' => {
 249         ty::re_bound(parse_bound_region(st))
 250       }
 251       'f' => {
 252         assert_eq!(next(st), '[');
 253         let id = parse_uint(st) as int;
 254         assert_eq!(next(st), '|');
 255         let br = parse_bound_region(st);
 256         assert_eq!(next(st), ']');
 257         ty::re_free(ty::FreeRegion {scope_id: id,
 258                                     bound_region: br})
 259       }
 260       's' => {
 261         let id = parse_uint(st) as int;
 262         assert_eq!(next(st), '|');
 263         ty::re_scope(id)
 264       }
 265       't' => {
 266         ty::re_static
 267       }
 268       'e' => {
 269         ty::re_static
 270       }
 271       _ => fail!("parse_region: bad input")
 272     }
 273 }
 274
 275 fn parse_opt<T>(st: &mut PState, f: &fn(&mut PState) -> T) -> Option<T> {
 276     match next(st) {
 277       'n' => None,
 278       's' => Some(f(st)),
 279       _ => fail!("parse_opt: bad input")
 280     }
 281 }
 282
 283 fn parse_str(st: &mut PState, term: char) -> ~str {
 284     let mut result = ~"";
 285     while peek(st) != term {
 286         unsafe {
 287             str::raw::push_byte(&mut result, next_byte(st));
 288         }
 289     }
 290     next(st);
 291     return result;
 292 }
 293
 294 fn parse_trait_ref(st: &mut PState, conv: conv_did) -> ty::TraitRef {
 295     let def = parse_def(st, NominalType, |x,y| conv(x,y));
 296     let substs = parse_substs(st, |x,y| conv(x,y));
 297     ty::TraitRef {def_id: def, substs: substs}
 298 }
 299
 300 fn parse_ty(st: &mut PState, conv: conv_did) -> ty::t {
 301     match next(st) {
 302       'n' => return ty::mk_nil(),
 303       'z' => return ty::mk_bot(),
 304       'b' => return ty::mk_bool(),
 305       'i' => return ty::mk_int(),
 306       'u' => return ty::mk_uint(),
 307       'M' => {
 308         match next(st) {
 309           'b' => return ty::mk_mach_uint(ast::ty_u8),
 310           'w' => return ty::mk_mach_uint(ast::ty_u16),
 311           'l' => return ty::mk_mach_uint(ast::ty_u32),
 312           'd' => return ty::mk_mach_uint(ast::ty_u64),
 313           'B' => return ty::mk_mach_int(ast::ty_i8),
 314           'W' => return ty::mk_mach_int(ast::ty_i16),
 315           'L' => return ty::mk_mach_int(ast::ty_i32),
 316           'D' => return ty::mk_mach_int(ast::ty_i64),
 317           'f' => return ty::mk_mach_float(ast::ty_f32),
 318           'F' => return ty::mk_mach_float(ast::ty_f64),
 319           _ => fail!("parse_ty: bad numeric type")
 320         }
 321       }
 322       'c' => return ty::mk_char(),
 323       't' => {
 324         assert_eq!(next(st), '[');
 325         let def = parse_def(st, NominalType, |x,y| conv(x,y));
 326         let substs = parse_substs(st, |x,y| conv(x,y));
 327         assert_eq!(next(st), ']');
 328         return ty::mk_enum(st.tcx, def, substs);
 329       }
 330       'x' => {
 331         assert_eq!(next(st), '[');
 332         let def = parse_def(st, NominalType, |x,y| conv(x,y));
 333         let substs = parse_substs(st, |x,y| conv(x,y));
 334         let store = parse_trait_store(st);
 335         let mt = parse_mutability(st);
 336         let bounds = parse_bounds(st, |x,y| conv(x,y));
 337         assert_eq!(next(st), ']');
 338         return ty::mk_trait(st.tcx, def, substs, store, mt, bounds.builtin_bounds);
 339       }
 340       'p' => {
 341         let did = parse_def(st, TypeParameter, conv);
 342         debug!("parsed ty_param: did={:?}", did);
 343         return ty::mk_param(st.tcx, parse_uint(st), did);
 344       }
 345       's' => {
 346         let did = parse_def(st, TypeParameter, conv);
 347         return ty::mk_self(st.tcx, did);
 348       }
 349       '@' => return ty::mk_box(st.tcx, parse_mt(st, conv)),
 350       '~' => return ty::mk_uniq(st.tcx, parse_mt(st, conv)),
 351       '*' => return ty::mk_ptr(st.tcx, parse_mt(st, conv)),
 352       '&' => {
 353         let r = parse_region(st);
 354         let mt = parse_mt(st, conv);
 355         return ty::mk_rptr(st.tcx, r, mt);
 356       }
 357       'U' => return ty::mk_unboxed_vec(st.tcx, parse_mt(st, conv)),
 358       'V' => {
 359         let mt = parse_mt(st, conv);
 360         let v = parse_vstore(st);
 361         return ty::mk_evec(st.tcx, mt, v);
 362       }
 363       'v' => {
 364         let v = parse_vstore(st);
 365         return ty::mk_estr(st.tcx, v);
 366       }
 367       'T' => {
 368         assert_eq!(next(st), '[');
 369         let mut params = ~[];
 370         while peek(st) != ']' { params.push(parse_ty(st, |x,y| conv(x,y))); }
 371         st.pos = st.pos + 1u;
 372         return ty::mk_tup(st.tcx, params);
 373       }
 374       'f' => {
 375         return ty::mk_closure(st.tcx, parse_closure_ty(st, conv));
 376       }
 377       'F' => {
 378         return ty::mk_bare_fn(st.tcx, parse_bare_fn_ty(st, conv));
 379       }
 380       'Y' => return ty::mk_type(st.tcx),
 381       'C' => {
 382         let sigil = parse_sigil(st);
 383         return ty::mk_opaque_closure_ptr(st.tcx, sigil);
 384       }
 385       '#' => {
 386         let pos = parse_hex(st);
 387         assert_eq!(next(st), ':');
 388         let len = parse_hex(st);
 389         assert_eq!(next(st), '#');
 390         let key = ty::creader_cache_key {cnum: st.crate,
 391                                          pos: pos,
 392                                          len: len };
 393         match st.tcx.rcache.find(&key) {
 394           Some(&tt) => return tt,
 395           None => {
 396             let mut ps = PState {
 397                 pos: pos,
 398                 .. *st
 399             };
 400             let tt = parse_ty(&mut ps, conv);
 401             st.tcx.rcache.insert(key, tt);
 402             return tt;
 403           }
 404         }
 405       }
 406       '"' => {
 407         let _ = parse_def(st, TypeWithId, |x,y| conv(x,y));
 408         let inner = parse_ty(st, |x,y| conv(x,y));
 409         inner
 410       }
 411       'B' => ty::mk_opaque_box(st.tcx),
 412       'a' => {
 413           assert_eq!(next(st), '[');
 414           let did = parse_def(st, NominalType, |x,y| conv(x,y));
 415           let substs = parse_substs(st, |x,y| conv(x,y));
 416           assert_eq!(next(st), ']');
 417           return ty::mk_struct(st.tcx, did, substs);
 418       }
 419       c => { error!("unexpected char in type string: {}", c); fail!();}
 420     }
 421 }
 422
 423 fn parse_mutability(st: &mut PState) -> ast::Mutability {
 424     match peek(st) {
 425       'm' => { next(st); ast::MutMutable }
 426       _ => { ast::MutImmutable }
 427     }
 428 }
 429
 430 fn parse_mt(st: &mut PState, conv: conv_did) -> ty::mt {
 431     let m = parse_mutability(st);
 432     ty::mt { ty: parse_ty(st, conv), mutbl: m }
 433 }
 434
 435 fn parse_def(st: &mut PState, source: DefIdSource,
 436              conv: conv_did) -> ast::DefId {
 437     return conv(source, scan(st, |c| { c == '|' }, parse_def_id));
 438 }
 439
 440 fn parse_uint(st: &mut PState) -> uint {
 441     let mut n = 0;
 442     loop {
 443         let cur = peek(st);
 444         if cur < '0' || cur > '9' { return n; }
 445         st.pos = st.pos + 1u;
 446         n *= 10;
 447         n += (cur as uint) - ('0' as uint);
 448     };
 449 }
 450
 451 fn parse_hex(st: &mut PState) -> uint {
 452     let mut n = 0u;
 453     loop {
 454         let cur = peek(st);
 455         if (cur < '0' || cur > '9') && (cur < 'a' || cur > 'f') { return n; }
 456         st.pos = st.pos + 1u;
 457         n *= 16u;
 458         if '0' <= cur && cur <= '9' {
 459             n += (cur as uint) - ('0' as uint);
 460         } else { n += 10u + (cur as uint) - ('a' as uint); }
 461     };
 462 }
 463
 464 fn parse_purity(c: char) -> purity {
 465     match c {
 466       'u' => unsafe_fn,
 467       'i' => impure_fn,
 468       'c' => extern_fn,
 469       _ => fail!("parse_purity: bad purity {}", c)
 470     }
 471 }
 472
 473 fn parse_abi_set(st: &mut PState) -> AbiSet {
 474     assert_eq!(next(st), '[');
 475     let mut abis = AbiSet::empty();
 476     while peek(st) != ']' {
 477         // FIXME(#5422) str API should not force this copy
 478         let abi_str = scan(st, |c| c == ',', str::from_utf8);
 479         let abi = abi::lookup(abi_str).expect(abi_str);
 480         abis.add(abi);
 481     }
 482     assert_eq!(next(st), ']');
 483     return abis;
 484 }
 485
 486 fn parse_onceness(c: char) -> ast::Onceness {
 487     match c {
 488         'o' => ast::Once,
 489         'm' => ast::Many,
 490         _ => fail!("parse_onceness: bad onceness")
 491     }
 492 }
 493
 494 fn parse_closure_ty(st: &mut PState, conv: conv_did) -> ty::ClosureTy {
 495     let sigil = parse_sigil(st);
 496     let purity = parse_purity(next(st));
 497     let onceness = parse_onceness(next(st));
 498     let region = parse_region(st);
 499     let bounds = parse_bounds(st, |x,y| conv(x,y));
 500     let sig = parse_sig(st, |x,y| conv(x,y));
 501     ty::ClosureTy {
 502         purity: purity,
 503         sigil: sigil,
 504         onceness: onceness,
 505         region: region,
 506         bounds: bounds.builtin_bounds,
 507         sig: sig
 508     }
 509 }
 510
 511 fn parse_bare_fn_ty(st: &mut PState, conv: conv_did) -> ty::BareFnTy {
 512     let purity = parse_purity(next(st));
 513     let abi = parse_abi_set(st);
 514     let sig = parse_sig(st, conv);
 515     ty::BareFnTy {
 516         purity: purity,
 517         abis: abi,
 518         sig: sig
 519     }
 520 }
 521
 522 fn parse_sig(st: &mut PState, conv: conv_did) -> ty::FnSig {
 523     assert_eq!(next(st), '[');
 524     let mut inputs = ~[];
 525     while peek(st) != ']' {
 526         inputs.push(parse_ty(st, |x,y| conv(x,y)));
 527     }
 528     st.pos += 1u; // eat the ']'
 529     let variadic = if peek(st) == 'A' {
 530         st.pos += 1; // eat the 'A'
 531         true
 532     } else { false };
 533     let ret_ty = parse_ty(st, conv);
 534     ty::FnSig {
 535         bound_lifetime_names: opt_vec::Empty, // FIXME(#4846)
 536         inputs: inputs,
 537         output: ret_ty,
 538         variadic: variadic
 539     }
 540 }
 541
 542 // Rust metadata parsing
 543 pub fn parse_def_id(buf: &[u8]) -> ast::DefId {
 544     let mut colon_idx = 0u;
 545     let len = buf.len();
 546     while colon_idx < len && buf[colon_idx] != ':' as u8 { colon_idx += 1u; }
 547     if colon_idx == len {
 548         error!("didn't find ':' when parsing def id");
 549         fail!();
 550     }
 551
 552     let crate_part = buf.slice(0u, colon_idx);
 553     let def_part = buf.slice(colon_idx + 1u, len);
 554
 555     let crate_num = match uint::parse_bytes(crate_part, 10u) {
 556        Some(cn) => cn as int,
 557        None => fail!("internal error: parse_def_id: crate number expected, but found {:?}",
 558                      crate_part)
 559     };
 560     let def_num = match uint::parse_bytes(def_part, 10u) {
 561        Some(dn) => dn as int,
 562        None => fail!("internal error: parse_def_id: id expected, but found {:?}",
 563                      def_part)
 564     };
 565     ast::DefId { crate: crate_num, node: def_num }
 566 }
 567
 568 pub fn parse_type_param_def_data(data: &[u8], start: uint,
 569                                  crate_num: int, tcx: ty::ctxt,
 570                                  conv: conv_did) -> ty::TypeParameterDef
 571 {
 572     let mut st = parse_state_from_data(data, crate_num, start, tcx);
 573     parse_type_param_def(&mut st, conv)
 574 }
 575
 576 fn parse_type_param_def(st: &mut PState, conv: conv_did) -> ty::TypeParameterDef {
 577     ty::TypeParameterDef {ident: parse_ident(st, ':'),
 578                           def_id: parse_def(st, NominalType, |x,y| conv(x,y)),
 579                           bounds: @parse_bounds(st, |x,y| conv(x,y))}
 580 }
 581
 582 fn parse_bounds(st: &mut PState, conv: conv_did) -> ty::ParamBounds {
 583     let mut param_bounds = ty::ParamBounds {
 584         builtin_bounds: ty::EmptyBuiltinBounds(),
 585         trait_bounds: ~[]
 586     };
 587     loop {
 588         match next(st) {
 589             'S' => {
 590                 param_bounds.builtin_bounds.add(ty::BoundSend);
 591             }
 592             'K' => {
 593                 param_bounds.builtin_bounds.add(ty::BoundFreeze);
 594             }
 595             'O' => {
 596                 param_bounds.builtin_bounds.add(ty::BoundStatic);
 597             }
 598             'Z' => {
 599                 param_bounds.builtin_bounds.add(ty::BoundSized);
 600             }
 601             'I' => {
 602                 param_bounds.trait_bounds.push(@parse_trait_ref(st, |x,y| conv(x,y)));
 603             }
 604             '.' => {
 605                 return param_bounds;
 606             }
 607             _ => {
 608                 fail!("parse_bounds: bad bounds")
 609             }
 610         }
 611     }
 612 }