src/libsyntax/ast_util.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 use ast::*;
  12 use ast;
  13 use ast_util;
  14 use codemap;
  15 use codemap::Span;
  16 use owned_slice::OwnedSlice;
  17 use parse::token;
  18 use print::pprust;
  19 use ptr::P;
  20 use visit::Visitor;
  21 use visit;
  22
  23 use std::cmp;
  24 use std::u32;
  25
  26 pub fn path_name_i(idents: &[Ident]) -> String {
  27     // FIXME: Bad copies (#2543 -- same for everything else that says "bad")
  28     idents.iter().map(|i| {
  29         token::get_ident(*i).to_string()
  30     }).collect::<Vec<String>>().connect("::")
  31 }
  32
  33 pub fn local_def(id: NodeId) -> DefId {
  34     ast::DefId { krate: LOCAL_CRATE, node: id }
  35 }
  36
  37 pub fn is_local(did: ast::DefId) -> bool { did.krate == LOCAL_CRATE }
  38
  39 pub fn stmt_id(s: &Stmt) -> NodeId {
  40     match s.node {
  41       StmtDecl(_, id) => id,
  42       StmtExpr(_, id) => id,
  43       StmtSemi(_, id) => id,
  44       StmtMac(..) => panic!("attempted to analyze unexpanded stmt")
  45     }
  46 }
  47
  48 pub fn binop_to_string(op: BinOp_) -> &'static str {
  49     match op {
  50         BiAdd => "+",
  51         BiSub => "-",
  52         BiMul => "*",
  53         BiDiv => "/",
  54         BiRem => "%",
  55         BiAnd => "&&",
  56         BiOr => "||",
  57         BiBitXor => "^",
  58         BiBitAnd => "&",
  59         BiBitOr => "|",
  60         BiShl => "<<",
  61         BiShr => ">>",
  62         BiEq => "==",
  63         BiLt => "<",
  64         BiLe => "<=",
  65         BiNe => "!=",
  66         BiGe => ">=",
  67         BiGt => ">"
  68     }
  69 }
  70
  71 pub fn lazy_binop(b: BinOp_) -> bool {
  72     match b {
  73       BiAnd => true,
  74       BiOr => true,
  75       _ => false
  76     }
  77 }
  78
  79 pub fn is_shift_binop(b: BinOp_) -> bool {
  80     match b {
  81       BiShl => true,
  82       BiShr => true,
  83       _ => false
  84     }
  85 }
  86
  87 pub fn is_comparison_binop(b: BinOp_) -> bool {
  88     match b {
  89         BiEq | BiLt | BiLe | BiNe | BiGt | BiGe =>
  90             true,
  91         BiAnd | BiOr | BiAdd | BiSub | BiMul | BiDiv | BiRem |
  92         BiBitXor | BiBitAnd | BiBitOr | BiShl | BiShr =>
  93             false,
  94     }
  95 }
  96
  97 /// Returns `true` if the binary operator takes its arguments by value
  98 pub fn is_by_value_binop(b: BinOp_) -> bool {
  99     !is_comparison_binop(b)
 100 }
 101
 102 /// Returns `true` if the unary operator takes its argument by value
 103 pub fn is_by_value_unop(u: UnOp) -> bool {
 104     match u {
 105         UnNeg | UnNot => true,
 106         _ => false,
 107     }
 108 }
 109
 110 pub fn unop_to_string(op: UnOp) -> &'static str {
 111     match op {
 112       UnUniq => "box() ",
 113       UnDeref => "*",
 114       UnNot => "!",
 115       UnNeg => "-",
 116     }
 117 }
 118
 119 pub fn is_path(e: P<Expr>) -> bool {
 120     match e.node { ExprPath(..) => true, _ => false }
 121 }
 122
 123 /// Get a string representation of a signed int type, with its value.
 124 /// We want to avoid "45int" and "-3int" in favor of "45" and "-3"
 125 pub fn int_ty_to_string(t: IntTy, val: Option<i64>) -> String {
 126     let s = match t {
 127         TyIs => "isize",
 128         TyI8 => "i8",
 129         TyI16 => "i16",
 130         TyI32 => "i32",
 131         TyI64 => "i64"
 132     };
 133
 134     match val {
 135         // cast to a u64 so we can correctly print INT64_MIN. All integral types
 136         // are parsed as u64, so we wouldn't want to print an extra negative
 137         // sign.
 138         Some(n) => format!("{}{}", n as u64, s),
 139         None => s.to_string()
 140     }
 141 }
 142
 143 pub fn int_ty_max(t: IntTy) -> u64 {
 144     match t {
 145         TyI8 => 0x80,
 146         TyI16 => 0x8000,
 147         TyIs | TyI32 => 0x80000000, // actually ni about TyIs
 148         TyI64 => 0x8000000000000000
 149     }
 150 }
 151
 152 /// Get a string representation of an unsigned int type, with its value.
 153 /// We want to avoid "42u" in favor of "42us". "42uint" is right out.
 154 pub fn uint_ty_to_string(t: UintTy, val: Option<u64>) -> String {
 155     let s = match t {
 156         TyUs => "usize",
 157         TyU8 => "u8",
 158         TyU16 => "u16",
 159         TyU32 => "u32",
 160         TyU64 => "u64"
 161     };
 162
 163     match val {
 164         Some(n) => format!("{}{}", n, s),
 165         None => s.to_string()
 166     }
 167 }
 168
 169 pub fn uint_ty_max(t: UintTy) -> u64 {
 170     match t {
 171         TyU8 => 0xff,
 172         TyU16 => 0xffff,
 173         TyUs | TyU32 => 0xffffffff, // actually ni about TyUs
 174         TyU64 => 0xffffffffffffffff
 175     }
 176 }
 177
 178 pub fn float_ty_to_string(t: FloatTy) -> String {
 179     match t {
 180         TyF32 => "f32".to_string(),
 181         TyF64 => "f64".to_string(),
 182     }
 183 }
 184
 185 // convert a span and an identifier to the corresponding
 186 // 1-segment path
 187 pub fn ident_to_path(s: Span, identifier: Ident) -> Path {
 188     ast::Path {
 189         span: s,
 190         global: false,
 191         segments: vec!(
 192             ast::PathSegment {
 193                 identifier: identifier,
 194                 parameters: ast::AngleBracketedParameters(ast::AngleBracketedParameterData {
 195                     lifetimes: Vec::new(),
 196                     types: OwnedSlice::empty(),
 197                     bindings: OwnedSlice::empty(),
 198                 })
 199             }
 200         ),
 201     }
 202 }
 203
 204 // If path is a single segment ident path, return that ident. Otherwise, return
 205 // None.
 206 pub fn path_to_ident(path: &Path) -> Option<Ident> {
 207     if path.segments.len() != 1 {
 208         return None;
 209     }
 210
 211     let segment = &path.segments[0];
 212     if !segment.parameters.is_empty() {
 213         return None;
 214     }
 215
 216     Some(segment.identifier)
 217 }
 218
 219 pub fn ident_to_pat(id: NodeId, s: Span, i: Ident) -> P<Pat> {
 220     P(Pat {
 221         id: id,
 222         node: PatIdent(BindByValue(MutImmutable), codemap::Spanned{span:s, node:i}, None),
 223         span: s
 224     })
 225 }
 226
 227 pub fn name_to_dummy_lifetime(name: Name) -> Lifetime {
 228     Lifetime { id: DUMMY_NODE_ID,
 229                span: codemap::DUMMY_SP,
 230                name: name }
 231 }
 232
 233 /// Generate a "pretty" name for an `impl` from its type and trait.
 234 /// This is designed so that symbols of `impl`'d methods give some
 235 /// hint of where they came from, (previously they would all just be
 236 /// listed as `__extensions__::method_name::hash`, with no indication
 237 /// of the type).
 238 pub fn impl_pretty_name(trait_ref: &Option<TraitRef>, ty: Option<&Ty>) -> Ident {
 239     let mut pretty = match ty {
 240         Some(t) => pprust::ty_to_string(t),
 241         None => String::from("..")
 242     };
 243
 244     match *trait_ref {
 245         Some(ref trait_ref) => {
 246             pretty.push('.');
 247             pretty.push_str(&pprust::path_to_string(&trait_ref.path));
 248         }
 249         None => {}
 250     }
 251     token::gensym_ident(&pretty[..])
 252 }
 253
 254 pub fn struct_field_visibility(field: ast::StructField) -> Visibility {
 255     match field.node.kind {
 256         ast::NamedField(_, v) | ast::UnnamedField(v) => v
 257     }
 258 }
 259
 260 /// Maps a binary operator to its precedence
 261 pub fn operator_prec(op: ast::BinOp_) -> usize {
 262   match op {
 263       // 'as' sits here with 12
 264       BiMul | BiDiv | BiRem     => 11,
 265       BiAdd | BiSub             => 10,
 266       BiShl | BiShr             =>  9,
 267       BiBitAnd                  =>  8,
 268       BiBitXor                  =>  7,
 269       BiBitOr                   =>  6,
 270       BiLt | BiLe | BiGe | BiGt | BiEq | BiNe => 3,
 271       BiAnd                     =>  2,
 272       BiOr                      =>  1
 273   }
 274 }
 275
 276 /// Precedence of the `as` operator, which is a binary operator
 277 /// not appearing in the prior table.
 278 pub const AS_PREC: usize = 12;
 279
 280 pub fn empty_generics() -> Generics {
 281     Generics {
 282         lifetimes: Vec::new(),
 283         ty_params: OwnedSlice::empty(),
 284         where_clause: WhereClause {
 285             id: DUMMY_NODE_ID,
 286             predicates: Vec::new(),
 287         }
 288     }
 289 }
 290
 291 // ______________________________________________________________________
 292 // Enumerating the IDs which appear in an AST
 293
 294 #[derive(Copy, Clone, RustcEncodable, RustcDecodable, Debug)]
 295 pub struct IdRange {
 296     pub min: NodeId,
 297     pub max: NodeId,
 298 }
 299
 300 impl IdRange {
 301     pub fn max() -> IdRange {
 302         IdRange {
 303             min: u32::MAX,
 304             max: u32::MIN,
 305         }
 306     }
 307
 308     pub fn empty(&self) -> bool {
 309         self.min >= self.max
 310     }
 311
 312     pub fn add(&mut self, id: NodeId) {
 313         self.min = cmp::min(self.min, id);
 314         self.max = cmp::max(self.max, id + 1);
 315     }
 316 }
 317
 318 pub trait IdVisitingOperation {
 319     fn visit_id(&mut self, node_id: NodeId);
 320 }
 321
 322 /// A visitor that applies its operation to all of the node IDs
 323 /// in a visitable thing.
 324
 325 pub struct IdVisitor<'a, O:'a> {
 326     pub operation: &'a mut O,
 327     pub pass_through_items: bool,
 328     pub visited_outermost: bool,
 329 }
 330
 331 impl<'a, O: IdVisitingOperation> IdVisitor<'a, O> {
 332     fn visit_generics_helper(&mut self, generics: &Generics) {
 333         for type_parameter in &*generics.ty_params {
 334             self.operation.visit_id(type_parameter.id)
 335         }
 336         for lifetime in &generics.lifetimes {
 337             self.operation.visit_id(lifetime.lifetime.id)
 338         }
 339     }
 340 }
 341
 342 impl<'a, 'v, O: IdVisitingOperation> Visitor<'v> for IdVisitor<'a, O> {
 343     fn visit_mod(&mut self,
 344                  module: &Mod,
 345                  _: Span,
 346                  node_id: NodeId) {
 347         self.operation.visit_id(node_id);
 348         visit::walk_mod(self, module)
 349     }
 350
 351     fn visit_foreign_item(&mut self, foreign_item: &ForeignItem) {
 352         self.operation.visit_id(foreign_item.id);
 353         visit::walk_foreign_item(self, foreign_item)
 354     }
 355
 356     fn visit_item(&mut self, item: &Item) {
 357         if !self.pass_through_items {
 358             if self.visited_outermost {
 359                 return
 360             } else {
 361                 self.visited_outermost = true
 362             }
 363         }
 364
 365         self.operation.visit_id(item.id);
 366         match item.node {
 367             ItemUse(ref view_path) => {
 368                 match view_path.node {
 369                     ViewPathSimple(_, _) |
 370                     ViewPathGlob(_) => {}
 371                     ViewPathList(_, ref paths) => {
 372                         for path in paths {
 373                             self.operation.visit_id(path.node.id())
 374                         }
 375                     }
 376                 }
 377             }
 378             ItemEnum(ref enum_definition, _) => {
 379                 for variant in &enum_definition.variants {
 380                     self.operation.visit_id(variant.node.id)
 381                 }
 382             }
 383             _ => {}
 384         }
 385
 386         visit::walk_item(self, item);
 387
 388         self.visited_outermost = false
 389     }
 390
 391     fn visit_local(&mut self, local: &Local) {
 392         self.operation.visit_id(local.id);
 393         visit::walk_local(self, local)
 394     }
 395
 396     fn visit_block(&mut self, block: &Block) {
 397         self.operation.visit_id(block.id);
 398         visit::walk_block(self, block)
 399     }
 400
 401     fn visit_stmt(&mut self, statement: &Stmt) {
 402         self.operation.visit_id(ast_util::stmt_id(statement));
 403         visit::walk_stmt(self, statement)
 404     }
 405
 406     fn visit_pat(&mut self, pattern: &Pat) {
 407         self.operation.visit_id(pattern.id);
 408         visit::walk_pat(self, pattern)
 409     }
 410
 411     fn visit_expr(&mut self, expression: &Expr) {
 412         self.operation.visit_id(expression.id);
 413         visit::walk_expr(self, expression)
 414     }
 415
 416     fn visit_ty(&mut self, typ: &Ty) {
 417         self.operation.visit_id(typ.id);
 418         visit::walk_ty(self, typ)
 419     }
 420
 421     fn visit_generics(&mut self, generics: &Generics) {
 422         self.visit_generics_helper(generics);
 423         visit::walk_generics(self, generics)
 424     }
 425
 426     fn visit_fn(&mut self,
 427                 function_kind: visit::FnKind<'v>,
 428                 function_declaration: &'v FnDecl,
 429                 block: &'v Block,
 430                 span: Span,
 431                 node_id: NodeId) {
 432         if !self.pass_through_items {
 433             match function_kind {
 434                 visit::FkMethod(..) if self.visited_outermost => return,
 435                 visit::FkMethod(..) => self.visited_outermost = true,
 436                 _ => {}
 437             }
 438         }
 439
 440         self.operation.visit_id(node_id);
 441
 442         match function_kind {
 443             visit::FkItemFn(_, generics, _, _, _) => {
 444                 self.visit_generics_helper(generics)
 445             }
 446             visit::FkMethod(_, sig, _) => {
 447                 self.visit_generics_helper(&sig.generics)
 448             }
 449             visit::FkFnBlock => {}
 450         }
 451
 452         for argument in &function_declaration.inputs {
 453             self.operation.visit_id(argument.id)
 454         }
 455
 456         visit::walk_fn(self,
 457                        function_kind,
 458                        function_declaration,
 459                        block,
 460                        span);
 461
 462         if !self.pass_through_items {
 463             if let visit::FkMethod(..) = function_kind {
 464                 self.visited_outermost = false;
 465             }
 466         }
 467     }
 468
 469     fn visit_struct_field(&mut self, struct_field: &StructField) {
 470         self.operation.visit_id(struct_field.node.id);
 471         visit::walk_struct_field(self, struct_field)
 472     }
 473
 474     fn visit_struct_def(&mut self,
 475                         struct_def: &StructDef,
 476                         _: ast::Ident,
 477                         _: &ast::Generics,
 478                         id: NodeId) {
 479         self.operation.visit_id(id);
 480         struct_def.ctor_id.map(|ctor_id| self.operation.visit_id(ctor_id));
 481         visit::walk_struct_def(self, struct_def);
 482     }
 483
 484     fn visit_trait_item(&mut self, ti: &ast::TraitItem) {
 485         self.operation.visit_id(ti.id);
 486         visit::walk_trait_item(self, ti);
 487     }
 488
 489     fn visit_impl_item(&mut self, ii: &ast::ImplItem) {
 490         self.operation.visit_id(ii.id);
 491         visit::walk_impl_item(self, ii);
 492     }
 493
 494     fn visit_lifetime_ref(&mut self, lifetime: &Lifetime) {
 495         self.operation.visit_id(lifetime.id);
 496     }
 497
 498     fn visit_lifetime_def(&mut self, def: &LifetimeDef) {
 499         self.visit_lifetime_ref(&def.lifetime);
 500     }
 501
 502     fn visit_trait_ref(&mut self, trait_ref: &TraitRef) {
 503         self.operation.visit_id(trait_ref.ref_id);
 504         visit::walk_trait_ref(self, trait_ref);
 505     }
 506 }
 507
 508 pub fn visit_ids_for_inlined_item<O: IdVisitingOperation>(item: &InlinedItem,
 509                                                           operation: &mut O) {
 510     let mut id_visitor = IdVisitor {
 511         operation: operation,
 512         pass_through_items: true,
 513         visited_outermost: false,
 514     };
 515
 516     visit::walk_inlined_item(&mut id_visitor, item);
 517 }
 518
 519 struct IdRangeComputingVisitor {
 520     result: IdRange,
 521 }
 522
 523 impl IdVisitingOperation for IdRangeComputingVisitor {
 524     fn visit_id(&mut self, id: NodeId) {
 525         self.result.add(id);
 526     }
 527 }
 528
 529 pub fn compute_id_range_for_inlined_item(item: &InlinedItem) -> IdRange {
 530     let mut visitor = IdRangeComputingVisitor {
 531         result: IdRange::max()
 532     };
 533     visit_ids_for_inlined_item(item, &mut visitor);
 534     visitor.result
 535 }
 536
 537 /// Computes the id range for a single fn body, ignoring nested items.
 538 pub fn compute_id_range_for_fn_body(fk: visit::FnKind,
 539                                     decl: &FnDecl,
 540                                     body: &Block,
 541                                     sp: Span,
 542                                     id: NodeId)
 543                                     -> IdRange
 544 {
 545     let mut visitor = IdRangeComputingVisitor {
 546         result: IdRange::max()
 547     };
 548     let mut id_visitor = IdVisitor {
 549         operation: &mut visitor,
 550         pass_through_items: false,
 551         visited_outermost: false,
 552     };
 553     id_visitor.visit_fn(fk, decl, body, sp, id);
 554     id_visitor.operation.result
 555 }
 556
 557 pub fn walk_pat<F>(pat: &Pat, mut it: F) -> bool where F: FnMut(&Pat) -> bool {
 558     // FIXME(#19596) this is a workaround, but there should be a better way
 559     fn walk_pat_<G>(pat: &Pat, it: &mut G) -> bool where G: FnMut(&Pat) -> bool {
 560         if !(*it)(pat) {
 561             return false;
 562         }
 563
 564         match pat.node {
 565             PatIdent(_, _, Some(ref p)) => walk_pat_(&**p, it),
 566             PatStruct(_, ref fields, _) => {
 567                 fields.iter().all(|field| walk_pat_(&*field.node.pat, it))
 568             }
 569             PatEnum(_, Some(ref s)) | PatTup(ref s) => {
 570                 s.iter().all(|p| walk_pat_(&**p, it))
 571             }
 572             PatBox(ref s) | PatRegion(ref s, _) => {
 573                 walk_pat_(&**s, it)
 574             }
 575             PatVec(ref before, ref slice, ref after) => {
 576                 before.iter().all(|p| walk_pat_(&**p, it)) &&
 577                 slice.iter().all(|p| walk_pat_(&**p, it)) &&
 578                 after.iter().all(|p| walk_pat_(&**p, it))
 579             }
 580             PatMac(_) => panic!("attempted to analyze unexpanded pattern"),
 581             PatWild(_) | PatLit(_) | PatRange(_, _) | PatIdent(_, _, _) |
 582             PatEnum(_, _) | PatQPath(_, _) => {
 583                 true
 584             }
 585         }
 586     }
 587
 588     walk_pat_(pat, &mut it)
 589 }
 590
 591 /// Returns true if the given struct def is tuple-like; i.e. that its fields
 592 /// are unnamed.
 593 pub fn struct_def_is_tuple_like(struct_def: &ast::StructDef) -> bool {
 594     struct_def.ctor_id.is_some()
 595 }
 596
 597 /// Returns true if the given pattern consists solely of an identifier
 598 /// and false otherwise.
 599 pub fn pat_is_ident(pat: P<ast::Pat>) -> bool {
 600     match pat.node {
 601         ast::PatIdent(..) => true,
 602         _ => false,
 603     }
 604 }
 605
 606 // are two paths equal when compared unhygienically?
 607 // since I'm using this to replace ==, it seems appropriate
 608 // to compare the span, global, etc. fields as well.
 609 pub fn path_name_eq(a : &ast::Path, b : &ast::Path) -> bool {
 610     (a.span == b.span)
 611     && (a.global == b.global)
 612     && (segments_name_eq(&a.segments[..], &b.segments[..]))
 613 }
 614
 615 // are two arrays of segments equal when compared unhygienically?
 616 pub fn segments_name_eq(a : &[ast::PathSegment], b : &[ast::PathSegment]) -> bool {
 617     a.len() == b.len() &&
 618     a.iter().zip(b.iter()).all(|(s, t)| {
 619         s.identifier.name == t.identifier.name &&
 620         // FIXME #7743: ident -> name problems in lifetime comparison?
 621         // can types contain idents?
 622         s.parameters == t.parameters
 623     })
 624 }
 625
 626 /// Returns true if this literal is a string and false otherwise.
 627 pub fn lit_is_str(lit: &Lit) -> bool {
 628     match lit.node {
 629         LitStr(..) => true,
 630         _ => false,
 631     }
 632 }
 633
 634 #[cfg(test)]
 635 mod tests {
 636     use ast::*;
 637     use super::*;
 638
 639     fn ident_to_segment(id : &Ident) -> PathSegment {
 640         PathSegment {identifier: id.clone(),
 641                      parameters: PathParameters::none()}
 642     }
 643
 644     #[test] fn idents_name_eq_test() {
 645         assert!(segments_name_eq(
 646             &[Ident{name:Name(3),ctxt:4}, Ident{name:Name(78),ctxt:82}]
 647                 .iter().map(ident_to_segment).collect::<Vec<PathSegment>>(),
 648             &[Ident{name:Name(3),ctxt:104}, Ident{name:Name(78),ctxt:182}]
 649                 .iter().map(ident_to_segment).collect::<Vec<PathSegment>>()));
 650         assert!(!segments_name_eq(
 651             &[Ident{name:Name(3),ctxt:4}, Ident{name:Name(78),ctxt:82}]
 652                 .iter().map(ident_to_segment).collect::<Vec<PathSegment>>(),
 653             &[Ident{name:Name(3),ctxt:104}, Ident{name:Name(77),ctxt:182}]
 654                 .iter().map(ident_to_segment).collect::<Vec<PathSegment>>()));
 655     }
 656 }