src/libsyntax/ast.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 // The Rust abstract syntax tree.
  12
  13 pub use self::TyParamBound::*;
  14 pub use self::UnsafeSource::*;
  15 pub use self::ViewPath_::*;
  16 pub use self::PathParameters::*;
  17
  18 use attr::ThinAttributes;
  19 use codemap::{mk_sp, respan, Span, Spanned, DUMMY_SP, ExpnId};
  20 use abi::Abi;
  21 use errors;
  22 use ext::base;
  23 use ext::tt::macro_parser;
  24 use parse::token::{self, keywords, InternedString};
  25 use parse::lexer;
  26 use parse::lexer::comments::{doc_comment_style, strip_doc_comment_decoration};
  27 use print::pprust;
  28 use ptr::P;
  29
  30 use std::fmt;
  31 use std::rc::Rc;
  32 use std::borrow::Cow;
  33 use std::hash::{Hash, Hasher};
  34 use serialize::{Encodable, Decodable, Encoder, Decoder};
  35
  36 /// A name is a part of an identifier, representing a string or gensym. It's
  37 /// the result of interning.
  38 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
  39 pub struct Name(pub u32);
  40
  41 /// A SyntaxContext represents a chain of macro-expandings
  42 /// and renamings. Each macro expansion corresponds to
  43 /// a fresh u32. This u32 is a reference to a table stored
  44 /// in thread-local storage.
  45 /// The special value EMPTY_CTXT is used to indicate an empty
  46 /// syntax context.
  47 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, RustcEncodable, RustcDecodable)]
  48 pub struct SyntaxContext(pub u32);
  49
  50 /// An identifier contains a Name (index into the interner
  51 /// table) and a SyntaxContext to track renaming and
  52 /// macro expansion per Flatt et al., "Macros That Work Together"
  53 #[derive(Clone, Copy, Eq)]
  54 pub struct Ident {
  55     pub name: Name,
  56     pub ctxt: SyntaxContext
  57 }
  58
  59 impl Name {
  60     pub fn as_str(self) -> token::InternedString {
  61         token::InternedString::new_from_name(self)
  62     }
  63
  64     pub fn unhygienize(self) -> Name {
  65         token::intern(&self.as_str())
  66     }
  67 }
  68
  69 impl fmt::Debug for Name {
  70     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  71         write!(f, "{}({})", self, self.0)
  72     }
  73 }
  74
  75 impl fmt::Display for Name {
  76     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  77         fmt::Display::fmt(&self.as_str(), f)
  78     }
  79 }
  80
  81 impl Encodable for Name {
  82     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
  83         s.emit_str(&self.as_str())
  84     }
  85 }
  86
  87 impl Decodable for Name {
  88     fn decode<D: Decoder>(d: &mut D) -> Result<Name, D::Error> {
  89         Ok(token::intern(&d.read_str()?[..]))
  90     }
  91 }
  92
  93 pub const EMPTY_CTXT : SyntaxContext = SyntaxContext(0);
  94
  95 impl Ident {
  96     pub fn new(name: Name, ctxt: SyntaxContext) -> Ident {
  97         Ident {name: name, ctxt: ctxt}
  98     }
  99     pub const fn with_empty_ctxt(name: Name) -> Ident {
 100         Ident {name: name, ctxt: EMPTY_CTXT}
 101     }
 102 }
 103
 104 impl PartialEq for Ident {
 105     fn eq(&self, other: &Ident) -> bool {
 106         if self.ctxt != other.ctxt {
 107             // There's no one true way to compare Idents. They can be compared
 108             // non-hygienically `id1.name == id2.name`, hygienically
 109             // `mtwt::resolve(id1) == mtwt::resolve(id2)`, or even member-wise
 110             // `(id1.name, id1.ctxt) == (id2.name, id2.ctxt)` depending on the situation.
 111             // Ideally, PartialEq should not be implemented for Ident at all, but that
 112             // would be too impractical, because many larger structures (Token, in particular)
 113             // including Idents as their parts derive PartialEq and use it for non-hygienic
 114             // comparisons. That's why PartialEq is implemented and defaults to non-hygienic
 115             // comparison. Hash is implemented too and is consistent with PartialEq, i.e. only
 116             // the name of Ident is hashed. Still try to avoid comparing idents in your code
 117             // (especially as keys in hash maps), use one of the three methods listed above
 118             // explicitly.
 119             //
 120             // If you see this panic, then some idents from different contexts were compared
 121             // non-hygienically. It's likely a bug. Use one of the three comparison methods
 122             // listed above explicitly.
 123
 124             panic!("idents with different contexts are compared with operator `==`: \
 125                 {:?}, {:?}.", self, other);
 126         }
 127
 128         self.name == other.name
 129     }
 130 }
 131
 132 impl Hash for Ident {
 133     fn hash<H: Hasher>(&self, state: &mut H) {
 134         self.name.hash(state)
 135     }
 136 }
 137
 138 impl fmt::Debug for Ident {
 139     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 140         write!(f, "{}#{}", self.name, self.ctxt.0)
 141     }
 142 }
 143
 144 impl fmt::Display for Ident {
 145     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 146         fmt::Display::fmt(&self.name, f)
 147     }
 148 }
 149
 150 impl Encodable for Ident {
 151     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
 152         self.name.encode(s)
 153     }
 154 }
 155
 156 impl Decodable for Ident {
 157     fn decode<D: Decoder>(d: &mut D) -> Result<Ident, D::Error> {
 158         Ok(Ident::with_empty_ctxt(Name::decode(d)?))
 159     }
 160 }
 161
 162 /// A mark represents a unique id associated with a macro expansion
 163 pub type Mrk = u32;
 164
 165 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Copy)]
 166 pub struct Lifetime {
 167     pub id: NodeId,
 168     pub span: Span,
 169     pub name: Name
 170 }
 171
 172 impl fmt::Debug for Lifetime {
 173     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 174         write!(f, "lifetime({}: {})", self.id, pprust::lifetime_to_string(self))
 175     }
 176 }
 177
 178 /// A lifetime definition, eg `'a: 'b+'c+'d`
 179 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 180 pub struct LifetimeDef {
 181     pub lifetime: Lifetime,
 182     pub bounds: Vec<Lifetime>
 183 }
 184
 185 /// A "Path" is essentially Rust's notion of a name; for instance:
 186 /// std::cmp::PartialEq  .  It's represented as a sequence of identifiers,
 187 /// along with a bunch of supporting information.
 188 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash)]
 189 pub struct Path {
 190     pub span: Span,
 191     /// A `::foo` path, is relative to the crate root rather than current
 192     /// module (like paths in an import).
 193     pub global: bool,
 194     /// The segments in the path: the things separated by `::`.
 195     pub segments: Vec<PathSegment>,
 196 }
 197
 198 impl fmt::Debug for Path {
 199     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 200         write!(f, "path({})", pprust::path_to_string(self))
 201     }
 202 }
 203
 204 impl fmt::Display for Path {
 205     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 206         write!(f, "{}", pprust::path_to_string(self))
 207     }
 208 }
 209
 210 impl Path {
 211     // convert a span and an identifier to the corresponding
 212     // 1-segment path
 213     pub fn from_ident(s: Span, identifier: Ident) -> Path {
 214         Path {
 215             span: s,
 216             global: false,
 217             segments: vec!(
 218                 PathSegment {
 219                     identifier: identifier,
 220                     parameters: PathParameters::none()
 221                 }
 222             ),
 223         }
 224     }
 225 }
 226
 227 /// A segment of a path: an identifier, an optional lifetime, and a set of
 228 /// types.
 229 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 230 pub struct PathSegment {
 231     /// The identifier portion of this path segment.
 232     pub identifier: Ident,
 233
 234     /// Type/lifetime parameters attached to this path. They come in
 235     /// two flavors: `Path<A,B,C>` and `Path(A,B) -> C`. Note that
 236     /// this is more than just simple syntactic sugar; the use of
 237     /// parens affects the region binding rules, so we preserve the
 238     /// distinction.
 239     pub parameters: PathParameters,
 240 }
 241
 242 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 243 pub enum PathParameters {
 244     /// The `<'a, A,B,C>` in `foo::bar::baz::<'a, A,B,C>`
 245     AngleBracketed(AngleBracketedParameterData),
 246     /// The `(A,B)` and `C` in `Foo(A,B) -> C`
 247     Parenthesized(ParenthesizedParameterData),
 248 }
 249
 250 impl PathParameters {
 251     pub fn none() -> PathParameters {
 252         PathParameters::AngleBracketed(AngleBracketedParameterData {
 253             lifetimes: Vec::new(),
 254             types: P::new(),
 255             bindings: P::new(),
 256         })
 257     }
 258
 259     pub fn is_empty(&self) -> bool {
 260         match *self {
 261             PathParameters::AngleBracketed(ref data) => data.is_empty(),
 262
 263             // Even if the user supplied no types, something like
 264             // `X()` is equivalent to `X<(),()>`.
 265             PathParameters::Parenthesized(..) => false,
 266         }
 267     }
 268
 269     pub fn has_lifetimes(&self) -> bool {
 270         match *self {
 271             PathParameters::AngleBracketed(ref data) => !data.lifetimes.is_empty(),
 272             PathParameters::Parenthesized(_) => false,
 273         }
 274     }
 275
 276     pub fn has_types(&self) -> bool {
 277         match *self {
 278             PathParameters::AngleBracketed(ref data) => !data.types.is_empty(),
 279             PathParameters::Parenthesized(..) => true,
 280         }
 281     }
 282
 283     /// Returns the types that the user wrote. Note that these do not necessarily map to the type
 284     /// parameters in the parenthesized case.
 285     pub fn types(&self) -> Vec<&P<Ty>> {
 286         match *self {
 287             PathParameters::AngleBracketed(ref data) => {
 288                 data.types.iter().collect()
 289             }
 290             PathParameters::Parenthesized(ref data) => {
 291                 data.inputs.iter()
 292                     .chain(data.output.iter())
 293                     .collect()
 294             }
 295         }
 296     }
 297
 298     pub fn lifetimes(&self) -> Vec<&Lifetime> {
 299         match *self {
 300             PathParameters::AngleBracketed(ref data) => {
 301                 data.lifetimes.iter().collect()
 302             }
 303             PathParameters::Parenthesized(_) => {
 304                 Vec::new()
 305             }
 306         }
 307     }
 308
 309     pub fn bindings(&self) -> Vec<&TypeBinding> {
 310         match *self {
 311             PathParameters::AngleBracketed(ref data) => {
 312                 data.bindings.iter().collect()
 313             }
 314             PathParameters::Parenthesized(_) => {
 315                 Vec::new()
 316             }
 317         }
 318     }
 319 }
 320
 321 /// A path like `Foo<'a, T>`
 322 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 323 pub struct AngleBracketedParameterData {
 324     /// The lifetime parameters for this path segment.
 325     pub lifetimes: Vec<Lifetime>,
 326     /// The type parameters for this path segment, if present.
 327     pub types: P<[P<Ty>]>,
 328     /// Bindings (equality constraints) on associated types, if present.
 329     /// e.g., `Foo<A=Bar>`.
 330     pub bindings: P<[TypeBinding]>,
 331 }
 332
 333 impl AngleBracketedParameterData {
 334     fn is_empty(&self) -> bool {
 335         self.lifetimes.is_empty() && self.types.is_empty() && self.bindings.is_empty()
 336     }
 337 }
 338
 339 /// A path like `Foo(A,B) -> C`
 340 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 341 pub struct ParenthesizedParameterData {
 342     /// Overall span
 343     pub span: Span,
 344
 345     /// `(A,B)`
 346     pub inputs: Vec<P<Ty>>,
 347
 348     /// `C`
 349     pub output: Option<P<Ty>>,
 350 }
 351
 352 pub type CrateNum = u32;
 353
 354 pub type NodeId = u32;
 355
 356 /// Node id used to represent the root of the crate.
 357 pub const CRATE_NODE_ID: NodeId = 0;
 358
 359 /// When parsing and doing expansions, we initially give all AST nodes this AST
 360 /// node value. Then later, in the renumber pass, we renumber them to have
 361 /// small, positive ids.
 362 pub const DUMMY_NODE_ID: NodeId = !0;
 363
 364 pub trait NodeIdAssigner {
 365     fn next_node_id(&self) -> NodeId;
 366     fn peek_node_id(&self) -> NodeId;
 367
 368     fn diagnostic(&self) -> &errors::Handler {
 369         panic!("this ID assigner cannot emit diagnostics")
 370     }
 371 }
 372
 373 /// The AST represents all type param bounds as types.
 374 /// typeck::collect::compute_bounds matches these against
 375 /// the "special" built-in traits (see middle::lang_items) and
 376 /// detects Copy, Send and Sync.
 377 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 378 pub enum TyParamBound {
 379     TraitTyParamBound(PolyTraitRef, TraitBoundModifier),
 380     RegionTyParamBound(Lifetime)
 381 }
 382
 383 /// A modifier on a bound, currently this is only used for `?Sized`, where the
 384 /// modifier is `Maybe`. Negative bounds should also be handled here.
 385 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 386 pub enum TraitBoundModifier {
 387     None,
 388     Maybe,
 389 }
 390
 391 pub type TyParamBounds = P<[TyParamBound]>;
 392
 393 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 394 pub struct TyParam {
 395     pub ident: Ident,
 396     pub id: NodeId,
 397     pub bounds: TyParamBounds,
 398     pub default: Option<P<Ty>>,
 399     pub span: Span
 400 }
 401
 402 /// Represents lifetimes and type parameters attached to a declaration
 403 /// of a function, enum, trait, etc.
 404 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 405 pub struct Generics {
 406     pub lifetimes: Vec<LifetimeDef>,
 407     pub ty_params: P<[TyParam]>,
 408     pub where_clause: WhereClause,
 409 }
 410
 411 impl Generics {
 412     pub fn is_lt_parameterized(&self) -> bool {
 413         !self.lifetimes.is_empty()
 414     }
 415     pub fn is_type_parameterized(&self) -> bool {
 416         !self.ty_params.is_empty()
 417     }
 418     pub fn is_parameterized(&self) -> bool {
 419         self.is_lt_parameterized() || self.is_type_parameterized()
 420     }
 421 }
 422
 423 impl Default for Generics {
 424     fn default() ->  Generics {
 425         Generics {
 426             lifetimes: Vec::new(),
 427             ty_params: P::new(),
 428             where_clause: WhereClause {
 429                 id: DUMMY_NODE_ID,
 430                 predicates: Vec::new(),
 431             }
 432         }
 433     }
 434 }
 435
 436 /// A `where` clause in a definition
 437 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 438 pub struct WhereClause {
 439     pub id: NodeId,
 440     pub predicates: Vec<WherePredicate>,
 441 }
 442
 443 /// A single predicate in a `where` clause
 444 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 445 pub enum WherePredicate {
 446     /// A type binding, e.g. `for<'c> Foo: Send+Clone+'c`
 447     BoundPredicate(WhereBoundPredicate),
 448     /// A lifetime predicate, e.g. `'a: 'b+'c`
 449     RegionPredicate(WhereRegionPredicate),
 450     /// An equality predicate (unsupported)
 451     EqPredicate(WhereEqPredicate),
 452 }
 453
 454 /// A type bound, e.g. `for<'c> Foo: Send+Clone+'c`
 455 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 456 pub struct WhereBoundPredicate {
 457     pub span: Span,
 458     /// Any lifetimes from a `for` binding
 459     pub bound_lifetimes: Vec<LifetimeDef>,
 460     /// The type being bounded
 461     pub bounded_ty: P<Ty>,
 462     /// Trait and lifetime bounds (`Clone+Send+'static`)
 463     pub bounds: TyParamBounds,
 464 }
 465
 466 /// A lifetime predicate, e.g. `'a: 'b+'c`
 467 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 468 pub struct WhereRegionPredicate {
 469     pub span: Span,
 470     pub lifetime: Lifetime,
 471     pub bounds: Vec<Lifetime>,
 472 }
 473
 474 /// An equality predicate (unsupported), e.g. `T=int`
 475 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 476 pub struct WhereEqPredicate {
 477     pub id: NodeId,
 478     pub span: Span,
 479     pub path: Path,
 480     pub ty: P<Ty>,
 481 }
 482
 483 /// The set of MetaItems that define the compilation environment of the crate,
 484 /// used to drive conditional compilation
 485 pub type CrateConfig = Vec<P<MetaItem>>;
 486
 487 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 488 pub struct Crate {
 489     pub module: Mod,
 490     pub attrs: Vec<Attribute>,
 491     pub config: CrateConfig,
 492     pub span: Span,
 493     pub exported_macros: Vec<MacroDef>,
 494 }
 495
 496 pub type MetaItem = Spanned<MetaItemKind>;
 497
 498 #[derive(Clone, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 499 pub enum MetaItemKind {
 500     Word(InternedString),
 501     List(InternedString, Vec<P<MetaItem>>),
 502     NameValue(InternedString, Lit),
 503 }
 504
 505 // can't be derived because the MetaItemKind::List requires an unordered comparison
 506 impl PartialEq for MetaItemKind {
 507     fn eq(&self, other: &MetaItemKind) -> bool {
 508         use self::MetaItemKind::*;
 509         match *self {
 510             Word(ref ns) => match *other {
 511                 Word(ref no) => (*ns) == (*no),
 512                 _ => false
 513             },
 514             NameValue(ref ns, ref vs) => match *other {
 515                 NameValue(ref no, ref vo) => {
 516                     (*ns) == (*no) && vs.node == vo.node
 517                 }
 518                 _ => false
 519             },
 520             List(ref ns, ref miss) => match *other {
 521                 List(ref no, ref miso) => {
 522                     ns == no &&
 523                         miss.iter().all(|mi| miso.iter().any(|x| x.node == mi.node))
 524                 }
 525                 _ => false
 526             }
 527         }
 528     }
 529 }
 530
 531 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 532 pub struct Block {
 533     /// Statements in a block
 534     pub stmts: Vec<Stmt>,
 535     /// An expression at the end of the block
 536     /// without a semicolon, if any
 537     pub expr: Option<P<Expr>>,
 538     pub id: NodeId,
 539     /// Distinguishes between `unsafe { ... }` and `{ ... }`
 540     pub rules: BlockCheckMode,
 541     pub span: Span,
 542 }
 543
 544 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash)]
 545 pub struct Pat {
 546     pub id: NodeId,
 547     pub node: PatKind,
 548     pub span: Span,
 549 }
 550
 551 impl fmt::Debug for Pat {
 552     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 553         write!(f, "pat({}: {})", self.id, pprust::pat_to_string(self))
 554     }
 555 }
 556
 557 impl Pat {
 558     pub fn walk<F>(&self, it: &mut F) -> bool
 559         where F: FnMut(&Pat) -> bool
 560     {
 561         if !it(self) {
 562             return false;
 563         }
 564
 565         match self.node {
 566             PatKind::Ident(_, _, Some(ref p)) => p.walk(it),
 567             PatKind::Struct(_, ref fields, _) => {
 568                 fields.iter().all(|field| field.node.pat.walk(it))
 569             }
 570             PatKind::TupleStruct(_, Some(ref s)) | PatKind::Tup(ref s) => {
 571                 s.iter().all(|p| p.walk(it))
 572             }
 573             PatKind::Box(ref s) | PatKind::Ref(ref s, _) => {
 574                 s.walk(it)
 575             }
 576             PatKind::Vec(ref before, ref slice, ref after) => {
 577                 before.iter().all(|p| p.walk(it)) &&
 578                 slice.iter().all(|p| p.walk(it)) &&
 579                 after.iter().all(|p| p.walk(it))
 580             }
 581             PatKind::Wild |
 582             PatKind::Lit(_) |
 583             PatKind::Range(_, _) |
 584             PatKind::Ident(_, _, _) |
 585             PatKind::TupleStruct(..) |
 586             PatKind::Path(..) |
 587             PatKind::QPath(_, _) |
 588             PatKind::Mac(_) => {
 589                 true
 590             }
 591         }
 592     }
 593 }
 594
 595 /// A single field in a struct pattern
 596 ///
 597 /// Patterns like the fields of Foo `{ x, ref y, ref mut z }`
 598 /// are treated the same as` x: x, y: ref y, z: ref mut z`,
 599 /// except is_shorthand is true
 600 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 601 pub struct FieldPat {
 602     /// The identifier for the field
 603     pub ident: Ident,
 604     /// The pattern the field is destructured to
 605     pub pat: P<Pat>,
 606     pub is_shorthand: bool,
 607 }
 608
 609 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
 610 pub enum BindingMode {
 611     ByRef(Mutability),
 612     ByValue(Mutability),
 613 }
 614
 615 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 616 pub enum PatKind {
 617     /// Represents a wildcard pattern (`_`)
 618     Wild,
 619
 620     /// A `PatKind::Ident` may either be a new bound variable,
 621     /// or a unit struct/variant pattern, or a const pattern (in the last two cases
 622     /// the third field must be `None`).
 623     ///
 624     /// In the unit or const pattern case, the parser can't determine
 625     /// which it is. The resolver determines this, and
 626     /// records this pattern's `NodeId` in an auxiliary
 627     /// set (of "PatIdents that refer to unit patterns or constants").
 628     Ident(BindingMode, SpannedIdent, Option<P<Pat>>),
 629
 630     /// A struct or struct variant pattern, e.g. `Variant {x, y, ..}`.
 631     /// The `bool` is `true` in the presence of a `..`.
 632     Struct(Path, Vec<Spanned<FieldPat>>, bool),
 633
 634     /// A tuple struct/variant pattern `Variant(x, y, z)`.
 635     /// "None" means a `Variant(..)` pattern where we don't bind the fields to names.
 636     TupleStruct(Path, Option<Vec<P<Pat>>>),
 637
 638     /// A path pattern.
 639     /// Such pattern can be resolved to a unit struct/variant or a constant.
 640     Path(Path),
 641
 642     /// An associated const named using the qualified path `<T>::CONST` or
 643     /// `<T as Trait>::CONST`. Associated consts from inherent impls can be
 644     /// referred to as simply `T::CONST`, in which case they will end up as
 645     /// PatKind::Path, and the resolver will have to sort that out.
 646     QPath(QSelf, Path),
 647
 648     /// A tuple pattern `(a, b)`
 649     Tup(Vec<P<Pat>>),
 650     /// A `box` pattern
 651     Box(P<Pat>),
 652     /// A reference pattern, e.g. `&mut (a, b)`
 653     Ref(P<Pat>, Mutability),
 654     /// A literal
 655     Lit(P<Expr>),
 656     /// A range pattern, e.g. `1...2`
 657     Range(P<Expr>, P<Expr>),
 658     /// `[a, b, ..i, y, z]` is represented as:
 659     ///     `PatKind::Vec(box [a, b], Some(i), box [y, z])`
 660     Vec(Vec<P<Pat>>, Option<P<Pat>>, Vec<P<Pat>>),
 661     /// A macro pattern; pre-expansion
 662     Mac(Mac),
 663 }
 664
 665 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
 666 pub enum Mutability {
 667     Mutable,
 668     Immutable,
 669 }
 670
 671 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
 672 pub enum BinOpKind {
 673     /// The `+` operator (addition)
 674     Add,
 675     /// The `-` operator (subtraction)
 676     Sub,
 677     /// The `*` operator (multiplication)
 678     Mul,
 679     /// The `/` operator (division)
 680     Div,
 681     /// The `%` operator (modulus)
 682     Rem,
 683     /// The `&&` operator (logical and)
 684     And,
 685     /// The `||` operator (logical or)
 686     Or,
 687     /// The `^` operator (bitwise xor)
 688     BitXor,
 689     /// The `&` operator (bitwise and)
 690     BitAnd,
 691     /// The `|` operator (bitwise or)
 692     BitOr,
 693     /// The `<<` operator (shift left)
 694     Shl,
 695     /// The `>>` operator (shift right)
 696     Shr,
 697     /// The `==` operator (equality)
 698     Eq,
 699     /// The `<` operator (less than)
 700     Lt,
 701     /// The `<=` operator (less than or equal to)
 702     Le,
 703     /// The `!=` operator (not equal to)
 704     Ne,
 705     /// The `>=` operator (greater than or equal to)
 706     Ge,
 707     /// The `>` operator (greater than)
 708     Gt,
 709 }
 710
 711 impl BinOpKind {
 712     pub fn to_string(&self) -> &'static str {
 713         use self::BinOpKind::*;
 714         match *self {
 715             Add => "+",
 716             Sub => "-",
 717             Mul => "*",
 718             Div => "/",
 719             Rem => "%",
 720             And => "&&",
 721             Or => "||",
 722             BitXor => "^",
 723             BitAnd => "&",
 724             BitOr => "|",
 725             Shl => "<<",
 726             Shr => ">>",
 727             Eq => "==",
 728             Lt => "<",
 729             Le => "<=",
 730             Ne => "!=",
 731             Ge => ">=",
 732             Gt => ">",
 733         }
 734     }
 735     pub fn lazy(&self) -> bool {
 736         match *self {
 737             BinOpKind::And | BinOpKind::Or => true,
 738             _ => false
 739         }
 740     }
 741
 742     pub fn is_shift(&self) -> bool {
 743         match *self {
 744             BinOpKind::Shl | BinOpKind::Shr => true,
 745             _ => false
 746         }
 747     }
 748     pub fn is_comparison(&self) -> bool {
 749         use self::BinOpKind::*;
 750         match *self {
 751             Eq | Lt | Le | Ne | Gt | Ge =>
 752             true,
 753             And | Or | Add | Sub | Mul | Div | Rem |
 754             BitXor | BitAnd | BitOr | Shl | Shr =>
 755             false,
 756         }
 757     }
 758     /// Returns `true` if the binary operator takes its arguments by value
 759     pub fn is_by_value(&self) -> bool {
 760         !self.is_comparison()
 761     }
 762 }
 763
 764 pub type BinOp = Spanned<BinOpKind>;
 765
 766 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
 767 pub enum UnOp {
 768     /// The `*` operator for dereferencing
 769     Deref,
 770     /// The `!` operator for logical inversion
 771     Not,
 772     /// The `-` operator for negation
 773     Neg,
 774 }
 775
 776 impl UnOp {
 777     /// Returns `true` if the unary operator takes its argument by value
 778     pub fn is_by_value(u: UnOp) -> bool {
 779         match u {
 780             UnOp::Neg | UnOp::Not => true,
 781             _ => false,
 782         }
 783     }
 784
 785     pub fn to_string(op: UnOp) -> &'static str {
 786         match op {
 787             UnOp::Deref => "*",
 788             UnOp::Not => "!",
 789             UnOp::Neg => "-",
 790         }
 791     }
 792 }
 793
 794 /// A statement
 795 pub type Stmt = Spanned<StmtKind>;
 796
 797 impl fmt::Debug for Stmt {
 798     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 799         write!(f, "stmt({}: {})",
 800                self.node.id()
 801                    .map_or(Cow::Borrowed("<macro>"),|id|Cow::Owned(id.to_string())),
 802                pprust::stmt_to_string(self))
 803     }
 804 }
 805
 806
 807 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash)]
 808 pub enum StmtKind {
 809     /// Could be an item or a local (let) binding:
 810     Decl(P<Decl>, NodeId),
 811
 812     /// Expr without trailing semi-colon (must have unit type):
 813     Expr(P<Expr>, NodeId),
 814
 815     /// Expr with trailing semi-colon (may have any type):
 816     Semi(P<Expr>, NodeId),
 817
 818     Mac(P<Mac>, MacStmtStyle, ThinAttributes),
 819 }
 820
 821 impl StmtKind {
 822     pub fn id(&self) -> Option<NodeId> {
 823         match *self {
 824             StmtKind::Decl(_, id) => Some(id),
 825             StmtKind::Expr(_, id) => Some(id),
 826             StmtKind::Semi(_, id) => Some(id),
 827             StmtKind::Mac(..) => None,
 828         }
 829     }
 830
 831     pub fn attrs(&self) -> &[Attribute] {
 832         match *self {
 833             StmtKind::Decl(ref d, _) => d.attrs(),
 834             StmtKind::Expr(ref e, _) |
 835             StmtKind::Semi(ref e, _) => e.attrs(),
 836             StmtKind::Mac(_, _, Some(ref b)) => b,
 837             StmtKind::Mac(_, _, None) => &[],
 838         }
 839     }
 840 }
 841
 842 #[derive(Clone, Copy, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 843 pub enum MacStmtStyle {
 844     /// The macro statement had a trailing semicolon, e.g. `foo! { ... };`
 845     /// `foo!(...);`, `foo![...];`
 846     Semicolon,
 847     /// The macro statement had braces; e.g. foo! { ... }
 848     Braces,
 849     /// The macro statement had parentheses or brackets and no semicolon; e.g.
 850     /// `foo!(...)`. All of these will end up being converted into macro
 851     /// expressions.
 852     NoBraces,
 853 }
 854
 855 // FIXME (pending discussion of #1697, #2178...): local should really be
 856 // a refinement on pat.
 857 /// Local represents a `let` statement, e.g., `let <pat>:<ty> = <expr>;`
 858 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 859 pub struct Local {
 860     pub pat: P<Pat>,
 861     pub ty: Option<P<Ty>>,
 862     /// Initializer expression to set the value, if any
 863     pub init: Option<P<Expr>>,
 864     pub id: NodeId,
 865     pub span: Span,
 866     pub attrs: ThinAttributes,
 867 }
 868
 869 impl Local {
 870     pub fn attrs(&self) -> &[Attribute] {
 871         match self.attrs {
 872             Some(ref b) => b,
 873             None => &[],
 874         }
 875     }
 876 }
 877
 878 pub type Decl = Spanned<DeclKind>;
 879
 880 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 881 pub enum DeclKind {
 882     /// A local (let) binding:
 883     Local(P<Local>),
 884     /// An item binding:
 885     Item(P<Item>),
 886 }
 887
 888 impl Decl {
 889     pub fn attrs(&self) -> &[Attribute] {
 890         match self.node {
 891             DeclKind::Local(ref l) => l.attrs(),
 892             DeclKind::Item(ref i) => i.attrs(),
 893         }
 894     }
 895 }
 896
 897 /// represents one arm of a 'match'
 898 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 899 pub struct Arm {
 900     pub attrs: Vec<Attribute>,
 901     pub pats: Vec<P<Pat>>,
 902     pub guard: Option<P<Expr>>,
 903     pub body: P<Expr>,
 904 }
 905
 906 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 907 pub struct Field {
 908     pub ident: SpannedIdent,
 909     pub expr: P<Expr>,
 910     pub span: Span,
 911 }
 912
 913 pub type SpannedIdent = Spanned<Ident>;
 914
 915 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
 916 pub enum BlockCheckMode {
 917     Default,
 918     Unsafe(UnsafeSource),
 919 }
 920
 921 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
 922 pub enum UnsafeSource {
 923     CompilerGenerated,
 924     UserProvided,
 925 }
 926
 927 /// An expression
 928 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash,)]
 929 pub struct Expr {
 930     pub id: NodeId,
 931     pub node: ExprKind,
 932     pub span: Span,
 933     pub attrs: ThinAttributes
 934 }
 935
 936 impl Expr {
 937     pub fn attrs(&self) -> &[Attribute] {
 938         match self.attrs {
 939             Some(ref b) => b,
 940             None => &[],
 941         }
 942     }
 943 }
 944
 945 impl fmt::Debug for Expr {
 946     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 947         write!(f, "expr({}: {})", self.id, pprust::expr_to_string(self))
 948     }
 949 }
 950
 951 /// Limit types of a range (inclusive or exclusive)
 952 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 953 pub enum RangeLimits {
 954     /// Inclusive at the beginning, exclusive at the end
 955     HalfOpen,
 956     /// Inclusive at the beginning and end
 957     Closed,
 958 }
 959
 960 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 961 pub enum ExprKind {
 962     /// A `box x` expression.
 963     Box(P<Expr>),
 964     /// First expr is the place; second expr is the value.
 965     InPlace(P<Expr>, P<Expr>),
 966     /// An array (`[a, b, c, d]`)
 967     Vec(Vec<P<Expr>>),
 968     /// A function call
 969     ///
 970     /// The first field resolves to the function itself,
 971     /// and the second field is the list of arguments
 972     Call(P<Expr>, Vec<P<Expr>>),
 973     /// A method call (`x.foo::<Bar, Baz>(a, b, c, d)`)
 974     ///
 975     /// The `SpannedIdent` is the identifier for the method name.
 976     /// The vector of `Ty`s are the ascripted type parameters for the method
 977     /// (within the angle brackets).
 978     ///
 979     /// The first element of the vector of `Expr`s is the expression that evaluates
 980     /// to the object on which the method is being called on (the receiver),
 981     /// and the remaining elements are the rest of the arguments.
 982     ///
 983     /// Thus, `x.foo::<Bar, Baz>(a, b, c, d)` is represented as
 984     /// `ExprKind::MethodCall(foo, [Bar, Baz], [x, a, b, c, d])`.
 985     MethodCall(SpannedIdent, Vec<P<Ty>>, Vec<P<Expr>>),
 986     /// A tuple (`(a, b, c ,d)`)
 987     Tup(Vec<P<Expr>>),
 988     /// A binary operation (For example: `a + b`, `a * b`)
 989     Binary(BinOp, P<Expr>, P<Expr>),
 990     /// A unary operation (For example: `!x`, `*x`)
 991     Unary(UnOp, P<Expr>),
 992     /// A literal (For example: `1`, `"foo"`)
 993     Lit(P<Lit>),
 994     /// A cast (`foo as f64`)
 995     Cast(P<Expr>, P<Ty>),
 996     Type(P<Expr>, P<Ty>),
 997     /// An `if` block, with an optional else block
 998     ///
 999     /// `if expr { block } else { expr }`
1000     If(P<Expr>, P<Block>, Option<P<Expr>>),
1001     /// An `if let` expression with an optional else block
1002     ///
1003     /// `if let pat = expr { block } else { expr }`
1004     ///
1005     /// This is desugared to a `match` expression.
1006     IfLet(P<Pat>, P<Expr>, P<Block>, Option<P<Expr>>),
1007     /// A while loop, with an optional label
1008     ///
1009     /// `'label: while expr { block }`
1010     While(P<Expr>, P<Block>, Option<Ident>),
1011     /// A while-let loop, with an optional label
1012     ///
1013     /// `'label: while let pat = expr { block }`
1014     ///
1015     /// This is desugared to a combination of `loop` and `match` expressions.
1016     WhileLet(P<Pat>, P<Expr>, P<Block>, Option<Ident>),
1017     /// A for loop, with an optional label
1018     ///
1019     /// `'label: for pat in expr { block }`
1020     ///
1021     /// This is desugared to a combination of `loop` and `match` expressions.
1022     ForLoop(P<Pat>, P<Expr>, P<Block>, Option<Ident>),
1023     /// Conditionless loop (can be exited with break, continue, or return)
1024     ///
1025     /// `'label: loop { block }`
1026     Loop(P<Block>, Option<Ident>),
1027     /// A `match` block.
1028     Match(P<Expr>, Vec<Arm>),
1029     /// A closure (for example, `move |a, b, c| {a + b + c}`)
1030     ///
1031     /// The final span is the span of the argument block `|...|`
1032     Closure(CaptureBy, P<FnDecl>, P<Block>, Span),
1033     /// A block (`{ ... }`)
1034     Block(P<Block>),
1035
1036     /// An assignment (`a = foo()`)
1037     Assign(P<Expr>, P<Expr>),
1038     /// An assignment with an operator
1039     ///
1040     /// For example, `a += 1`.
1041     AssignOp(BinOp, P<Expr>, P<Expr>),
1042     /// Access of a named struct field (`obj.foo`)
1043     Field(P<Expr>, SpannedIdent),
1044     /// Access of an unnamed field of a struct or tuple-struct
1045     ///
1046     /// For example, `foo.0`.
1047     TupField(P<Expr>, Spanned<usize>),
1048     /// An indexing operation (`foo[2]`)
1049     Index(P<Expr>, P<Expr>),
1050     /// A range (`1..2`, `1..`, `..2`, `1...2`, `1...`, `...2`)
1051     Range(Option<P<Expr>>, Option<P<Expr>>, RangeLimits),
1052
1053     /// Variable reference, possibly containing `::` and/or type
1054     /// parameters, e.g. foo::bar::<baz>.
1055     ///
1056     /// Optionally "qualified",
1057     /// e.g. `<Vec<T> as SomeTrait>::SomeType`.
1058     Path(Option<QSelf>, Path),
1059
1060     /// A referencing operation (`&a` or `&mut a`)
1061     AddrOf(Mutability, P<Expr>),
1062     /// A `break`, with an optional label to break
1063     Break(Option<SpannedIdent>),
1064     /// A `continue`, with an optional label
1065     Again(Option<SpannedIdent>),
1066     /// A `return`, with an optional value to be returned
1067     Ret(Option<P<Expr>>),
1068
1069     /// Output of the `asm!()` macro
1070     InlineAsm(InlineAsm),
1071
1072     /// A macro invocation; pre-expansion
1073     Mac(Mac),
1074
1075     /// A struct literal expression.
1076     ///
1077     /// For example, `Foo {x: 1, y: 2}`, or
1078     /// `Foo {x: 1, .. base}`, where `base` is the `Option<Expr>`.
1079     Struct(Path, Vec<Field>, Option<P<Expr>>),
1080
1081     /// An array literal constructed from one repeated element.
1082     ///
1083     /// For example, `[1; 5]`. The first expression is the element
1084     /// to be repeated; the second is the number of times to repeat it.
1085     Repeat(P<Expr>, P<Expr>),
1086
1087     /// No-op: used solely so we can pretty-print faithfully
1088     Paren(P<Expr>),
1089
1090     /// `expr?`
1091     Try(P<Expr>),
1092 }
1093
1094 /// The explicit Self type in a "qualified path". The actual
1095 /// path, including the trait and the associated item, is stored
1096 /// separately. `position` represents the index of the associated
1097 /// item qualified with this Self type.
1098 ///
1099 /// ```ignore
1100 /// <Vec<T> as a::b::Trait>::AssociatedItem
1101 ///  ^~~~~     ~~~~~~~~~~~~~~^
1102 ///  ty        position = 3
1103 ///
1104 /// <Vec<T>>::AssociatedItem
1105 ///  ^~~~~    ^
1106 ///  ty       position = 0
1107 /// ```
1108 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1109 pub struct QSelf {
1110     pub ty: P<Ty>,
1111     pub position: usize
1112 }
1113
1114 /// A capture clause
1115 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
1116 pub enum CaptureBy {
1117     Value,
1118     Ref,
1119 }
1120
1121 /// A delimited sequence of token trees
1122 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1123 pub struct Delimited {
1124     /// The type of delimiter
1125     pub delim: token::DelimToken,
1126     /// The span covering the opening delimiter
1127     pub open_span: Span,
1128     /// The delimited sequence of token trees
1129     pub tts: Vec<TokenTree>,
1130     /// The span covering the closing delimiter
1131     pub close_span: Span,
1132 }
1133
1134 impl Delimited {
1135     /// Returns the opening delimiter as a token.
1136     pub fn open_token(&self) -> token::Token {
1137         token::OpenDelim(self.delim)
1138     }
1139
1140     /// Returns the closing delimiter as a token.
1141     pub fn close_token(&self) -> token::Token {
1142         token::CloseDelim(self.delim)
1143     }
1144
1145     /// Returns the opening delimiter as a token tree.
1146     pub fn open_tt(&self) -> TokenTree {
1147         TokenTree::Token(self.open_span, self.open_token())
1148     }
1149
1150     /// Returns the closing delimiter as a token tree.
1151     pub fn close_tt(&self) -> TokenTree {
1152         TokenTree::Token(self.close_span, self.close_token())
1153     }
1154 }
1155
1156 /// A sequence of token trees
1157 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1158 pub struct SequenceRepetition {
1159     /// The sequence of token trees
1160     pub tts: Vec<TokenTree>,
1161     /// The optional separator
1162     pub separator: Option<token::Token>,
1163     /// Whether the sequence can be repeated zero (*), or one or more times (+)
1164     pub op: KleeneOp,
1165     /// The number of `MatchNt`s that appear in the sequence (and subsequences)
1166     pub num_captures: usize,
1167 }
1168
1169 /// A Kleene-style [repetition operator](http://en.wikipedia.org/wiki/Kleene_star)
1170 /// for token sequences.
1171 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
1172 pub enum KleeneOp {
1173     ZeroOrMore,
1174     OneOrMore,
1175 }
1176
1177 /// When the main rust parser encounters a syntax-extension invocation, it
1178 /// parses the arguments to the invocation as a token-tree. This is a very
1179 /// loose structure, such that all sorts of different AST-fragments can
1180 /// be passed to syntax extensions using a uniform type.
1181 ///
1182 /// If the syntax extension is an MBE macro, it will attempt to match its
1183 /// LHS token tree against the provided token tree, and if it finds a
1184 /// match, will transcribe the RHS token tree, splicing in any captured
1185 /// macro_parser::matched_nonterminals into the `SubstNt`s it finds.
1186 ///
1187 /// The RHS of an MBE macro is the only place `SubstNt`s are substituted.
1188 /// Nothing special happens to misnamed or misplaced `SubstNt`s.
1189 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1190 pub enum TokenTree {
1191     /// A single token
1192     Token(Span, token::Token),
1193     /// A delimited sequence of token trees
1194     Delimited(Span, Rc<Delimited>),
1195
1196     // This only makes sense in MBE macros.
1197
1198     /// A kleene-style repetition sequence with a span
1199     // FIXME(eddyb) #12938 Use DST.
1200     Sequence(Span, Rc<SequenceRepetition>),
1201 }
1202
1203 impl TokenTree {
1204     pub fn len(&self) -> usize {
1205         match *self {
1206             TokenTree::Token(_, token::DocComment(name)) => {
1207                 match doc_comment_style(&name.as_str()) {
1208                     AttrStyle::Outer => 2,
1209                     AttrStyle::Inner => 3
1210                 }
1211             }
1212             TokenTree::Token(_, token::SpecialVarNt(..)) => 2,
1213             TokenTree::Token(_, token::MatchNt(..)) => 3,
1214             TokenTree::Delimited(_, ref delimed) => {
1215                 delimed.tts.len() + 2
1216             }
1217             TokenTree::Sequence(_, ref seq) => {
1218                 seq.tts.len()
1219             }
1220             TokenTree::Token(..) => 0
1221         }
1222     }
1223
1224     pub fn get_tt(&self, index: usize) -> TokenTree {
1225         match (self, index) {
1226             (&TokenTree::Token(sp, token::DocComment(_)), 0) => {
1227                 TokenTree::Token(sp, token::Pound)
1228             }
1229             (&TokenTree::Token(sp, token::DocComment(name)), 1)
1230             if doc_comment_style(&name.as_str()) == AttrStyle::Inner => {
1231                 TokenTree::Token(sp, token::Not)
1232             }
1233             (&TokenTree::Token(sp, token::DocComment(name)), _) => {
1234                 let stripped = strip_doc_comment_decoration(&name.as_str());
1235
1236                 // Searches for the occurrences of `"#*` and returns the minimum number of `#`s
1237                 // required to wrap the text.
1238                 let num_of_hashes = stripped.chars().scan(0, |cnt, x| {
1239                     *cnt = if x == '"' {
1240                         1
1241                     } else if *cnt != 0 && x == '#' {
1242                         *cnt + 1
1243                     } else {
1244                         0
1245                     };
1246                     Some(*cnt)
1247                 }).max().unwrap_or(0);
1248
1249                 TokenTree::Delimited(sp, Rc::new(Delimited {
1250                     delim: token::Bracket,
1251                     open_span: sp,
1252                     tts: vec![TokenTree::Token(sp, token::Ident(token::str_to_ident("doc"))),
1253                               TokenTree::Token(sp, token::Eq),
1254                               TokenTree::Token(sp, token::Literal(
1255                                   token::StrRaw(token::intern(&stripped), num_of_hashes), None))],
1256                     close_span: sp,
1257                 }))
1258             }
1259             (&TokenTree::Delimited(_, ref delimed), _) => {
1260                 if index == 0 {
1261                     return delimed.open_tt();
1262                 }
1263                 if index == delimed.tts.len() + 1 {
1264                     return delimed.close_tt();
1265                 }
1266                 delimed.tts[index - 1].clone()
1267             }
1268             (&TokenTree::Token(sp, token::SpecialVarNt(var)), _) => {
1269                 let v = [TokenTree::Token(sp, token::Dollar),
1270                          TokenTree::Token(sp, token::Ident(token::str_to_ident(var.as_str())))];
1271                 v[index].clone()
1272             }
1273             (&TokenTree::Token(sp, token::MatchNt(name, kind)), _) => {
1274                 let v = [TokenTree::Token(sp, token::SubstNt(name)),
1275                          TokenTree::Token(sp, token::Colon),
1276                          TokenTree::Token(sp, token::Ident(kind))];
1277                 v[index].clone()
1278             }
1279             (&TokenTree::Sequence(_, ref seq), _) => {
1280                 seq.tts[index].clone()
1281             }
1282             _ => panic!("Cannot expand a token tree")
1283         }
1284     }
1285
1286     /// Returns the `Span` corresponding to this token tree.
1287     pub fn get_span(&self) -> Span {
1288         match *self {
1289             TokenTree::Token(span, _)     => span,
1290             TokenTree::Delimited(span, _) => span,
1291             TokenTree::Sequence(span, _)  => span,
1292         }
1293     }
1294
1295     /// Use this token tree as a matcher to parse given tts.
1296     pub fn parse(cx: &base::ExtCtxt, mtch: &[TokenTree], tts: &[TokenTree])
1297                  -> macro_parser::NamedParseResult {
1298         // `None` is because we're not interpolating
1299         let arg_rdr = lexer::new_tt_reader_with_doc_flag(&cx.parse_sess().span_diagnostic,
1300                                                          None,
1301                                                          None,
1302                                                          tts.iter().cloned().collect(),
1303                                                          true);
1304         macro_parser::parse(cx.parse_sess(), cx.cfg(), arg_rdr, mtch)
1305     }
1306 }
1307
1308 pub type Mac = Spanned<Mac_>;
1309
1310 /// Represents a macro invocation. The Path indicates which macro
1311 /// is being invoked, and the vector of token-trees contains the source
1312 /// of the macro invocation.
1313 ///
1314 /// NB: the additional ident for a macro_rules-style macro is actually
1315 /// stored in the enclosing item. Oog.
1316 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1317 pub struct Mac_ {
1318     pub path: Path,
1319     pub tts: Vec<TokenTree>,
1320     pub ctxt: SyntaxContext,
1321 }
1322
1323 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
1324 pub enum StrStyle {
1325     /// A regular string, like `"foo"`
1326     Cooked,
1327     /// A raw string, like `r##"foo"##`
1328     ///
1329     /// The uint is the number of `#` symbols used
1330     Raw(usize)
1331 }
1332
1333 /// A literal
1334 pub type Lit = Spanned<LitKind>;
1335
1336 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
1337 pub enum LitIntType {
1338     Signed(IntTy),
1339     Unsigned(UintTy),
1340     Unsuffixed,
1341 }
1342
1343 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1344 pub enum LitKind {
1345     /// A string literal (`"foo"`)
1346     Str(InternedString, StrStyle),
1347     /// A byte string (`b"foo"`)
1348     ByteStr(Rc<Vec<u8>>),
1349     /// A byte char (`b'f'`)
1350     Byte(u8),
1351     /// A character literal (`'a'`)
1352     Char(char),
1353     /// An integer literal (`1`)
1354     Int(u64, LitIntType),
1355     /// A float literal (`1f64` or `1E10f64`)
1356     Float(InternedString, FloatTy),
1357     /// A float literal without a suffix (`1.0 or 1.0E10`)
1358     FloatUnsuffixed(InternedString),
1359     /// A boolean literal
1360     Bool(bool),
1361 }
1362
1363 impl LitKind {
1364     /// Returns true if this literal is a string and false otherwise.
1365     pub fn is_str(&self) -> bool {
1366         match *self {
1367             LitKind::Str(..) => true,
1368             _ => false,
1369         }
1370     }
1371 }
1372
1373 // NB: If you change this, you'll probably want to change the corresponding
1374 // type structure in middle/ty.rs as well.
1375 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1376 pub struct MutTy {
1377     pub ty: P<Ty>,
1378     pub mutbl: Mutability,
1379 }
1380
1381 /// Represents a method's signature in a trait declaration,
1382 /// or in an implementation.
1383 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1384 pub struct MethodSig {
1385     pub unsafety: Unsafety,
1386     pub constness: Constness,
1387     pub abi: Abi,
1388     pub decl: P<FnDecl>,
1389     pub generics: Generics,
1390     pub explicit_self: ExplicitSelf,
1391 }
1392
1393 /// Represents an item declaration within a trait declaration,
1394 /// possibly including a default implementation. A trait item is
1395 /// either required (meaning it doesn't have an implementation, just a
1396 /// signature) or provided (meaning it has a default implementation).
1397 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1398 pub struct TraitItem {
1399     pub id: NodeId,
1400     pub ident: Ident,
1401     pub attrs: Vec<Attribute>,
1402     pub node: TraitItemKind,
1403     pub span: Span,
1404 }
1405
1406 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1407 pub enum TraitItemKind {
1408     Const(P<Ty>, Option<P<Expr>>),
1409     Method(MethodSig, Option<P<Block>>),
1410     Type(TyParamBounds, Option<P<Ty>>),
1411 }
1412
1413 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1414 pub struct ImplItem {
1415     pub id: NodeId,
1416     pub ident: Ident,
1417     pub vis: Visibility,
1418     pub defaultness: Defaultness,
1419     pub attrs: Vec<Attribute>,
1420     pub node: ImplItemKind,
1421     pub span: Span,
1422 }
1423
1424 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1425 pub enum ImplItemKind {
1426     Const(P<Ty>, P<Expr>),
1427     Method(MethodSig, P<Block>),
1428     Type(P<Ty>),
1429     Macro(Mac),
1430 }
1431
1432 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Copy)]
1433 pub enum IntTy {
1434     Is,
1435     I8,
1436     I16,
1437     I32,
1438     I64,
1439 }
1440
1441 impl fmt::Debug for IntTy {
1442     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1443         fmt::Display::fmt(self, f)
1444     }
1445 }
1446
1447 impl fmt::Display for IntTy {
1448     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1449         write!(f, "{}", self.ty_to_string())
1450     }
1451 }
1452
1453 impl IntTy {
1454     pub fn ty_to_string(&self) -> &'static str {
1455         match *self {
1456             IntTy::Is => "isize",
1457             IntTy::I8 => "i8",
1458             IntTy::I16 => "i16",
1459             IntTy::I32 => "i32",
1460             IntTy::I64 => "i64"
1461         }
1462     }
1463
1464     pub fn val_to_string(&self, val: i64) -> String {
1465         // cast to a u64 so we can correctly print INT64_MIN. All integral types
1466         // are parsed as u64, so we wouldn't want to print an extra negative
1467         // sign.
1468         format!("{}{}", val as u64, self.ty_to_string())
1469     }
1470
1471     pub fn ty_max(&self) -> u64 {
1472         match *self {
1473             IntTy::I8 => 0x80,
1474             IntTy::I16 => 0x8000,
1475             IntTy::Is | IntTy::I32 => 0x80000000, // FIXME: actually ni about Is
1476             IntTy::I64 => 0x8000000000000000
1477         }
1478     }
1479
1480     pub fn bit_width(&self) -> Option<usize> {
1481         Some(match *self {
1482             IntTy::Is => return None,
1483             IntTy::I8 => 8,
1484             IntTy::I16 => 16,
1485             IntTy::I32 => 32,
1486             IntTy::I64 => 64,
1487         })
1488     }
1489 }
1490
1491 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Copy)]
1492 pub enum UintTy {
1493     Us,
1494     U8,
1495     U16,
1496     U32,
1497     U64,
1498 }
1499
1500 impl UintTy {
1501     pub fn ty_to_string(&self) -> &'static str {
1502         match *self {
1503             UintTy::Us => "usize",
1504             UintTy::U8 => "u8",
1505             UintTy::U16 => "u16",
1506             UintTy::U32 => "u32",
1507             UintTy::U64 => "u64"
1508         }
1509     }
1510
1511     pub fn val_to_string(&self, val: u64) -> String {
1512         format!("{}{}", val, self.ty_to_string())
1513     }
1514
1515     pub fn ty_max(&self) -> u64 {
1516         match *self {
1517             UintTy::U8 => 0xff,
1518             UintTy::U16 => 0xffff,
1519             UintTy::Us | UintTy::U32 => 0xffffffff, // FIXME: actually ni about Us
1520             UintTy::U64 => 0xffffffffffffffff
1521         }
1522     }
1523
1524     pub fn bit_width(&self) -> Option<usize> {
1525         Some(match *self {
1526             UintTy::Us => return None,
1527             UintTy::U8 => 8,
1528             UintTy::U16 => 16,
1529             UintTy::U32 => 32,
1530             UintTy::U64 => 64,
1531         })
1532     }
1533 }
1534
1535 impl fmt::Debug for UintTy {
1536     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1537         fmt::Display::fmt(self, f)
1538     }
1539 }
1540
1541 impl fmt::Display for UintTy {
1542     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1543         write!(f, "{}", self.ty_to_string())
1544     }
1545 }
1546
1547 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Copy)]
1548 pub enum FloatTy {
1549     F32,
1550     F64,
1551 }
1552
1553 impl fmt::Debug for FloatTy {
1554     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1555         fmt::Display::fmt(self, f)
1556     }
1557 }
1558
1559 impl fmt::Display for FloatTy {
1560     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1561         write!(f, "{}", self.ty_to_string())
1562     }
1563 }
1564
1565 impl FloatTy {
1566     pub fn ty_to_string(&self) -> &'static str {
1567         match *self {
1568             FloatTy::F32 => "f32",
1569             FloatTy::F64 => "f64",
1570         }
1571     }
1572
1573     pub fn bit_width(&self) -> usize {
1574         match *self {
1575             FloatTy::F32 => 32,
1576             FloatTy::F64 => 64,
1577         }
1578     }
1579 }
1580
1581 // Bind a type to an associated type: `A=Foo`.
1582 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1583 pub struct TypeBinding {
1584     pub id: NodeId,
1585     pub ident: Ident,
1586     pub ty: P<Ty>,
1587     pub span: Span,
1588 }
1589
1590 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash)]
1591 pub struct Ty {
1592     pub id: NodeId,
1593     pub node: TyKind,
1594     pub span: Span,
1595 }
1596
1597 impl fmt::Debug for Ty {
1598     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1599         write!(f, "type({})", pprust::ty_to_string(self))
1600     }
1601 }
1602
1603 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1604 pub struct BareFnTy {
1605     pub unsafety: Unsafety,
1606     pub abi: Abi,
1607     pub lifetimes: Vec<LifetimeDef>,
1608     pub decl: P<FnDecl>
1609 }
1610
1611 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1612 /// The different kinds of types recognized by the compiler
1613 pub enum TyKind {
1614     Vec(P<Ty>),
1615     /// A fixed length array (`[T; n]`)
1616     FixedLengthVec(P<Ty>, P<Expr>),
1617     /// A raw pointer (`*const T` or `*mut T`)
1618     Ptr(MutTy),
1619     /// A reference (`&'a T` or `&'a mut T`)
1620     Rptr(Option<Lifetime>, MutTy),
1621     /// A bare function (e.g. `fn(usize) -> bool`)
1622     BareFn(P<BareFnTy>),
1623     /// A tuple (`(A, B, C, D,...)`)
1624     Tup(Vec<P<Ty>> ),
1625     /// A path (`module::module::...::Type`), optionally
1626     /// "qualified", e.g. `<Vec<T> as SomeTrait>::SomeType`.
1627     ///
1628     /// Type parameters are stored in the Path itself
1629     Path(Option<QSelf>, Path),
1630     /// Something like `A+B`. Note that `B` must always be a path.
1631     ObjectSum(P<Ty>, TyParamBounds),
1632     /// A type like `for<'a> Foo<&'a Bar>`
1633     PolyTraitRef(TyParamBounds),
1634     /// No-op; kept solely so that we can pretty-print faithfully
1635     Paren(P<Ty>),
1636     /// Unused for now
1637     Typeof(P<Expr>),
1638     /// TyKind::Infer means the type should be inferred instead of it having been
1639     /// specified. This can appear anywhere in a type.
1640     Infer,
1641     // A macro in the type position.
1642     Mac(Mac),
1643 }
1644
1645 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
1646 pub enum AsmDialect {
1647     Att,
1648     Intel,
1649 }
1650
1651 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1652 pub struct InlineAsmOutput {
1653     pub constraint: InternedString,
1654     pub expr: P<Expr>,
1655     pub is_rw: bool,
1656     pub is_indirect: bool,
1657 }
1658
1659 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1660 pub struct InlineAsm {
1661     pub asm: InternedString,
1662     pub asm_str_style: StrStyle,
1663     pub outputs: Vec<InlineAsmOutput>,
1664     pub inputs: Vec<(InternedString, P<Expr>)>,
1665     pub clobbers: Vec<InternedString>,
1666     pub volatile: bool,
1667     pub alignstack: bool,
1668     pub dialect: AsmDialect,
1669     pub expn_id: ExpnId,
1670 }
1671
1672 /// represents an argument in a function header
1673 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1674 pub struct Arg {
1675     pub ty: P<Ty>,
1676     pub pat: P<Pat>,
1677     pub id: NodeId,
1678 }
1679
1680 /// Represents the kind of 'self' associated with a method.
1681 /// String representation of `Ident` here is always "self", but hygiene contexts may differ.
1682 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1683 pub enum SelfKind {
1684     /// No self
1685     Static,
1686     /// `self`, `mut self`
1687     Value(Ident),
1688     /// `&'lt self`, `&'lt mut self`
1689     Region(Option<Lifetime>, Mutability, Ident),
1690     /// `self: TYPE`, `mut self: TYPE`
1691     Explicit(P<Ty>, Ident),
1692 }
1693
1694 pub type ExplicitSelf = Spanned<SelfKind>;
1695
1696 impl Arg {
1697     #[unstable(feature = "rustc_private", issue = "27812")]
1698     #[rustc_deprecated(since = "1.10.0", reason = "use `from_self` instead")]
1699     pub fn new_self(span: Span, mutability: Mutability, self_ident: Ident) -> Arg {
1700         let path = Spanned{span:span,node:self_ident};
1701         Arg {
1702             // HACK(eddyb) fake type for the self argument.
1703             ty: P(Ty {
1704                 id: DUMMY_NODE_ID,
1705                 node: TyKind::Infer,
1706                 span: DUMMY_SP,
1707             }),
1708             pat: P(Pat {
1709                 id: DUMMY_NODE_ID,
1710                 node: PatKind::Ident(BindingMode::ByValue(mutability), path, None),
1711                 span: span
1712             }),
1713             id: DUMMY_NODE_ID
1714         }
1715     }
1716
1717     pub fn to_self(&self) -> Option<ExplicitSelf> {
1718         if let PatKind::Ident(_, ident, _) = self.pat.node {
1719             if ident.node.name == keywords::SelfValue.name() {
1720                 return match self.ty.node {
1721                     TyKind::Infer => Some(respan(self.pat.span, SelfKind::Value(ident.node))),
1722                     TyKind::Rptr(lt, MutTy{ref ty, mutbl}) if ty.node == TyKind::Infer => {
1723                         Some(respan(self.pat.span, SelfKind::Region(lt, mutbl, ident.node)))
1724                     }
1725                     _ => Some(respan(mk_sp(self.pat.span.lo, self.ty.span.hi),
1726                                      SelfKind::Explicit(self.ty.clone(), ident.node))),
1727                 }
1728             }
1729         }
1730         None
1731     }
1732
1733     pub fn from_self(eself: ExplicitSelf, ident_sp: Span, mutbl: Mutability) -> Arg {
1734         let pat = |ident, span| P(Pat {
1735             id: DUMMY_NODE_ID,
1736             node: PatKind::Ident(BindingMode::ByValue(mutbl), respan(ident_sp, ident), None),
1737             span: span,
1738         });
1739         let infer_ty = P(Ty {
1740             id: DUMMY_NODE_ID,
1741             node: TyKind::Infer,
1742             span: DUMMY_SP,
1743         });
1744         let arg = |ident, ty, span| Arg {
1745             pat: pat(ident, span),
1746             ty: ty,
1747             id: DUMMY_NODE_ID,
1748         };
1749         match eself.node {
1750             SelfKind::Static => panic!("bug: `Arg::from_self` is called \
1751                                         with `SelfKind::Static` argument"),
1752             SelfKind::Explicit(ty, ident) => arg(ident, ty, mk_sp(eself.span.lo, ident_sp.hi)),
1753             SelfKind::Value(ident) => arg(ident, infer_ty, eself.span),
1754             SelfKind::Region(lt, mutbl, ident) => arg(ident, P(Ty {
1755                 id: DUMMY_NODE_ID,
1756                 node: TyKind::Rptr(lt, MutTy { ty: infer_ty, mutbl: mutbl }),
1757                 span: DUMMY_SP,
1758             }), eself.span),
1759         }
1760     }
1761 }
1762
1763 /// Represents the header (not the body) of a function declaration
1764 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1765 pub struct FnDecl {
1766     pub inputs: Vec<Arg>,
1767     pub output: FunctionRetTy,
1768     pub variadic: bool
1769 }
1770
1771 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1772 pub enum Unsafety {
1773     Unsafe,
1774     Normal,
1775 }
1776
1777 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1778 pub enum Constness {
1779     Const,
1780     NotConst,
1781 }
1782
1783 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1784 pub enum Defaultness {
1785     Default,
1786     Final,
1787 }
1788
1789 impl fmt::Display for Unsafety {
1790     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1791         fmt::Display::fmt(match *self {
1792             Unsafety::Normal => "normal",
1793             Unsafety::Unsafe => "unsafe",
1794         }, f)
1795     }
1796 }
1797
1798 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash)]
1799 pub enum ImplPolarity {
1800     /// `impl Trait for Type`
1801     Positive,
1802     /// `impl !Trait for Type`
1803     Negative,
1804 }
1805
1806 impl fmt::Debug for ImplPolarity {
1807     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1808         match *self {
1809             ImplPolarity::Positive => "positive".fmt(f),
1810             ImplPolarity::Negative => "negative".fmt(f),
1811         }
1812     }
1813 }
1814
1815
1816 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1817 pub enum FunctionRetTy {
1818     /// Functions with return type `!`that always
1819     /// raise an error or exit (i.e. never return to the caller)
1820     None(Span),
1821     /// Return type is not specified.
1822     ///
1823     /// Functions default to `()` and
1824     /// closures default to inference. Span points to where return
1825     /// type would be inserted.
1826     Default(Span),
1827     /// Everything else
1828     Ty(P<Ty>),
1829 }
1830
1831 impl FunctionRetTy {
1832     pub fn span(&self) -> Span {
1833         match *self {
1834             FunctionRetTy::None(span) => span,
1835             FunctionRetTy::Default(span) => span,
1836             FunctionRetTy::Ty(ref ty) => ty.span,
1837         }
1838     }
1839 }
1840
1841 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1842 pub struct Mod {
1843     /// A span from the first token past `{` to the last token until `}`.
1844     /// For `mod foo;`, the inner span ranges from the first token
1845     /// to the last token in the external file.
1846     pub inner: Span,
1847     pub items: Vec<P<Item>>,
1848 }
1849
1850 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1851 pub struct ForeignMod {
1852     pub abi: Abi,
1853     pub items: Vec<ForeignItem>,
1854 }
1855
1856 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1857 pub struct EnumDef {
1858     pub variants: Vec<Variant>,
1859 }
1860
1861 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1862 pub struct Variant_ {
1863     pub name: Ident,
1864     pub attrs: Vec<Attribute>,
1865     pub data: VariantData,
1866     /// Explicit discriminant, eg `Foo = 1`
1867     pub disr_expr: Option<P<Expr>>,
1868 }
1869
1870 pub type Variant = Spanned<Variant_>;
1871
1872 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
1873 pub enum PathListItemKind {
1874     Ident {
1875         name: Ident,
1876         /// renamed in list, eg `use foo::{bar as baz};`
1877         rename: Option<Ident>,
1878         id: NodeId
1879     },
1880     Mod {
1881         /// renamed in list, eg `use foo::{self as baz};`
1882         rename: Option<Ident>,
1883         id: NodeId
1884     }
1885 }
1886
1887 impl PathListItemKind {
1888     pub fn id(&self) -> NodeId {
1889         match *self {
1890             PathListItemKind::Ident { id, .. } | PathListItemKind::Mod { id, .. } => id
1891         }
1892     }
1893
1894     pub fn name(&self) -> Option<Ident> {
1895         match *self {
1896             PathListItemKind::Ident { name, .. } => Some(name),
1897             PathListItemKind::Mod { .. } => None,
1898         }
1899     }
1900
1901     pub fn rename(&self) -> Option<Ident> {
1902         match *self {
1903             PathListItemKind::Ident { rename, .. } | PathListItemKind::Mod { rename, .. } => rename
1904         }
1905     }
1906 }
1907
1908 pub type PathListItem = Spanned<PathListItemKind>;
1909
1910 pub type ViewPath = Spanned<ViewPath_>;
1911
1912 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1913 pub enum ViewPath_ {
1914
1915     /// `foo::bar::baz as quux`
1916     ///
1917     /// or just
1918     ///
1919     /// `foo::bar::baz` (with `as baz` implicitly on the right)
1920     ViewPathSimple(Ident, Path),
1921
1922     /// `foo::bar::*`
1923     ViewPathGlob(Path),
1924
1925     /// `foo::bar::{a,b,c}`
1926     ViewPathList(Path, Vec<PathListItem>)
1927 }
1928
1929 /// Meta-data associated with an item
1930 pub type Attribute = Spanned<Attribute_>;
1931
1932 /// Distinguishes between Attributes that decorate items and Attributes that
1933 /// are contained as statements within items. These two cases need to be
1934 /// distinguished for pretty-printing.
1935 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
1936 pub enum AttrStyle {
1937     Outer,
1938     Inner,
1939 }
1940
1941 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
1942 pub struct AttrId(pub usize);
1943
1944 /// Doc-comments are promoted to attributes that have is_sugared_doc = true
1945 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1946 pub struct Attribute_ {
1947     pub id: AttrId,
1948     pub style: AttrStyle,
1949     pub value: P<MetaItem>,
1950     pub is_sugared_doc: bool,
1951 }
1952
1953 /// TraitRef's appear in impls.
1954 ///
1955 /// resolve maps each TraitRef's ref_id to its defining trait; that's all
1956 /// that the ref_id is for. The impl_id maps to the "self type" of this impl.
1957 /// If this impl is an ItemKind::Impl, the impl_id is redundant (it could be the
1958 /// same as the impl's node id).
1959 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1960 pub struct TraitRef {
1961     pub path: Path,
1962     pub ref_id: NodeId,
1963 }
1964
1965 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1966 pub struct PolyTraitRef {
1967     /// The `'a` in `<'a> Foo<&'a T>`
1968     pub bound_lifetimes: Vec<LifetimeDef>,
1969
1970     /// The `Foo<&'a T>` in `<'a> Foo<&'a T>`
1971     pub trait_ref: TraitRef,
1972
1973     pub span: Span,
1974 }
1975
1976 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1977 pub enum Visibility {
1978     Public,
1979     Crate(Span),
1980     Restricted { path: P<Path>, id: NodeId },
1981     Inherited,
1982 }
1983
1984 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1985 pub struct StructField {
1986     pub span: Span,
1987     pub ident: Option<Ident>,
1988     pub vis: Visibility,
1989     pub id: NodeId,
1990     pub ty: P<Ty>,
1991     pub attrs: Vec<Attribute>,
1992 }
1993
1994 /// Fields and Ids of enum variants and structs
1995 ///
1996 /// For enum variants: `NodeId` represents both an Id of the variant itself (relevant for all
1997 /// variant kinds) and an Id of the variant's constructor (not relevant for `Struct`-variants).
1998 /// One shared Id can be successfully used for these two purposes.
1999 /// Id of the whole enum lives in `Item`.
2000 ///
2001 /// For structs: `NodeId` represents an Id of the structure's constructor, so it is not actually
2002 /// used for `Struct`-structs (but still presents). Structures don't have an analogue of "Id of
2003 /// the variant itself" from enum variants.
2004 /// Id of the whole struct lives in `Item`.
2005 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
2006 pub enum VariantData {
2007     Struct(Vec<StructField>, NodeId),
2008     Tuple(Vec<StructField>, NodeId),
2009     Unit(NodeId),
2010 }
2011
2012 impl VariantData {
2013     pub fn fields(&self) -> &[StructField] {
2014         match *self {
2015             VariantData::Struct(ref fields, _) | VariantData::Tuple(ref fields, _) => fields,
2016             _ => &[],
2017         }
2018     }
2019     pub fn id(&self) -> NodeId {
2020         match *self {
2021             VariantData::Struct(_, id) | VariantData::Tuple(_, id) | VariantData::Unit(id) => id
2022         }
2023     }
2024     pub fn is_struct(&self) -> bool {
2025         if let VariantData::Struct(..) = *self { true } else { false }
2026     }
2027     pub fn is_tuple(&self) -> bool {
2028         if let VariantData::Tuple(..) = *self { true } else { false }
2029     }
2030     pub fn is_unit(&self) -> bool {
2031         if let VariantData::Unit(..) = *self { true } else { false }
2032     }
2033 }
2034
2035 /*
2036   FIXME (#3300): Should allow items to be anonymous. Right now
2037   we just use dummy names for anon items.
2038  */
2039 /// An item
2040 ///
2041 /// The name might be a dummy name in case of anonymous items
2042 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
2043 pub struct Item {
2044     pub ident: Ident,
2045     pub attrs: Vec<Attribute>,
2046     pub id: NodeId,
2047     pub node: ItemKind,
2048     pub vis: Visibility,
2049     pub span: Span,
2050 }
2051
2052 impl Item {
2053     pub fn attrs(&self) -> &[Attribute] {
2054         &self.attrs
2055     }
2056 }
2057
2058 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
2059 pub enum ItemKind {
2060     /// An`extern crate` item, with optional original crate name,
2061     ///
2062     /// e.g. `extern crate foo` or `extern crate foo_bar as foo`
2063     ExternCrate(Option<Name>),
2064     /// A `use` or `pub use` item
2065     Use(P<ViewPath>),
2066
2067     /// A `static` item
2068     Static(P<Ty>, Mutability, P<Expr>),
2069     /// A `const` item
2070     Const(P<Ty>, P<Expr>),
2071     /// A function declaration
2072     Fn(P<FnDecl>, Unsafety, Constness, Abi, Generics, P<Block>),
2073     /// A module
2074     Mod(Mod),
2075     /// An external module
2076     ForeignMod(ForeignMod),
2077     /// A type alias, e.g. `type Foo = Bar<u8>`
2078     Ty(P<Ty>, Generics),
2079     /// An enum definition, e.g. `enum Foo<A, B> {C<A>, D<B>}`
2080     Enum(EnumDef, Generics),
2081     /// A struct definition, e.g. `struct Foo<A> {x: A}`
2082     Struct(VariantData, Generics),
2083     /// Represents a Trait Declaration
2084     Trait(Unsafety, Generics, TyParamBounds, Vec<TraitItem>),
2085
2086     // Default trait implementations
2087     ///
2088     // `impl Trait for .. {}`
2089     DefaultImpl(Unsafety, TraitRef),
2090     /// An implementation, eg `impl<A> Trait for Foo { .. }`
2091     Impl(Unsafety,
2092              ImplPolarity,
2093              Generics,
2094              Option<TraitRef>, // (optional) trait this impl implements
2095              P<Ty>, // self
2096              Vec<ImplItem>),
2097     /// A macro invocation (which includes macro definition)
2098     Mac(Mac),
2099 }
2100
2101 impl ItemKind {
2102     pub fn descriptive_variant(&self) -> &str {
2103         match *self {
2104             ItemKind::ExternCrate(..) => "extern crate",
2105             ItemKind::Use(..) => "use",
2106             ItemKind::Static(..) => "static item",
2107             ItemKind::Const(..) => "constant item",
2108             ItemKind::Fn(..) => "function",
2109             ItemKind::Mod(..) => "module",
2110             ItemKind::ForeignMod(..) => "foreign module",
2111             ItemKind::Ty(..) => "type alias",
2112             ItemKind::Enum(..) => "enum",
2113             ItemKind::Struct(..) => "struct",
2114             ItemKind::Trait(..) => "trait",
2115             ItemKind::Mac(..) |
2116             ItemKind::Impl(..) |
2117             ItemKind::DefaultImpl(..) => "item"
2118         }
2119     }
2120 }
2121
2122 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
2123 pub struct ForeignItem {
2124     pub ident: Ident,
2125     pub attrs: Vec<Attribute>,
2126     pub node: ForeignItemKind,
2127     pub id: NodeId,
2128     pub span: Span,
2129     pub vis: Visibility,
2130 }
2131
2132 /// An item within an `extern` block
2133 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
2134 pub enum ForeignItemKind {
2135     /// A foreign function
2136     Fn(P<FnDecl>, Generics),
2137     /// A foreign static item (`static ext: u8`), with optional mutability
2138     /// (the boolean is true when mutable)
2139     Static(P<Ty>, bool),
2140 }
2141
2142 impl ForeignItemKind {
2143     pub fn descriptive_variant(&self) -> &str {
2144         match *self {
2145             ForeignItemKind::Fn(..) => "foreign function",
2146             ForeignItemKind::Static(..) => "foreign static item"
2147         }
2148     }
2149 }
2150
2151 /// A macro definition, in this crate or imported from another.
2152 ///
2153 /// Not parsed directly, but created on macro import or `macro_rules!` expansion.
2154 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
2155 pub struct MacroDef {
2156     pub ident: Ident,
2157     pub attrs: Vec<Attribute>,
2158     pub id: NodeId,
2159     pub span: Span,
2160     pub imported_from: Option<Ident>,
2161     pub export: bool,
2162     pub use_locally: bool,
2163     pub allow_internal_unstable: bool,
2164     pub body: Vec<TokenTree>,
2165 }
2166
2167 #[cfg(test)]
2168 mod tests {
2169     use serialize;
2170     use super::*;
2171
2172     // are ASTs encodable?
2173     #[test]
2174     fn check_asts_encodable() {
2175         fn assert_encodable<T: serialize::Encodable>() {}
2176         assert_encodable::<Crate>();
2177     }
2178 }