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