src/libsyntax/visit.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 //! Context-passing AST walker. Each overridden visit method has full control
  12 //! over what happens with its node, it can do its own traversal of the node's
  13 //! children (potentially passing in different contexts to each), call
  14 //! `visit::visit_*` to apply the default traversal algorithm (again, it can
  15 //! override the context), or prevent deeper traversal by doing nothing.
  16 //!
  17 //! Note: it is an important invariant that the default visitor walks the body
  18 //! of a function in "execution order" (more concretely, reverse post-order
  19 //! with respect to the CFG implied by the AST), meaning that if AST node A may
  20 //! execute before AST node B, then A is visited first.  The borrow checker in
  21 //! particular relies on this property.
  22 //!
  23 //! Note: walking an AST before macro expansion is probably a bad idea. For
  24 //! instance, a walker looking for item names in a module will miss all of
  25 //! those that are created by the expansion of a macro.
  26
  27 use abi::Abi;
  28 use ast::*;
  29 use ast;
  30 use ast_util;
  31 use codemap::Span;
  32 use parse;
  33 use owned_slice::OwnedSlice;
  34
  35 use std::gc::Gc;
  36
  37 pub enum FnKind<'a> {
  38     /// fn foo() or extern "Abi" fn foo()
  39     FkItemFn(Ident, &'a Generics, FnStyle, Abi),
  40
  41     /// fn foo(&self)
  42     FkMethod(Ident, &'a Generics, &'a Method),
  43
  44     /// |x, y| ...
  45     /// proc(x, y) ...
  46     FkFnBlock,
  47 }
  48
  49 pub fn name_of_fn(fk: &FnKind) -> Ident {
  50     match *fk {
  51         FkItemFn(name, _, _, _) | FkMethod(name, _, _) => name,
  52         FkFnBlock(..) => parse::token::special_idents::invalid
  53     }
  54 }
  55
  56 pub fn generics_of_fn(fk: &FnKind) -> Generics {
  57     match *fk {
  58         FkItemFn(_, generics, _, _) |
  59         FkMethod(_, generics, _) => {
  60             (*generics).clone()
  61         }
  62         FkFnBlock(..) => ast_util::empty_generics(),
  63     }
  64 }
  65
  66 /// Each method of the Visitor trait is a hook to be potentially
  67 /// overridden.  Each method's default implementation recursively visits
  68 /// the substructure of the input via the corresponding `walk` method;
  69 /// e.g. the `visit_mod` method by default calls `visit::walk_mod`.
  70 ///
  71 /// If you want to ensure that your code handles every variant
  72 /// explicitly, you need to override each method.  (And you also need
  73 /// to monitor future changes to `Visitor` in case a new method with a
  74 /// new default implementation gets introduced.)
  75 pub trait Visitor<E: Clone> {
  76
  77     fn visit_ident(&mut self, _sp: Span, _ident: Ident, _e: E) {
  78         /*! Visit the idents */
  79     }
  80     fn visit_mod(&mut self, m: &Mod, _s: Span, _n: NodeId, e: E) { walk_mod(self, m, e) }
  81     fn visit_view_item(&mut self, i: &ViewItem, e: E) { walk_view_item(self, i, e) }
  82     fn visit_foreign_item(&mut self, i: &ForeignItem, e: E) { walk_foreign_item(self, i, e) }
  83     fn visit_item(&mut self, i: &Item, e: E) { walk_item(self, i, e) }
  84     fn visit_local(&mut self, l: &Local, e: E) { walk_local(self, l, e) }
  85     fn visit_block(&mut self, b: &Block, e: E) { walk_block(self, b, e) }
  86     fn visit_stmt(&mut self, s: &Stmt, e: E) { walk_stmt(self, s, e) }
  87     fn visit_arm(&mut self, a: &Arm, e: E) { walk_arm(self, a, e) }
  88     fn visit_pat(&mut self, p: &Pat, e: E) { walk_pat(self, p, e) }
  89     fn visit_decl(&mut self, d: &Decl, e: E) { walk_decl(self, d, e) }
  90     fn visit_expr(&mut self, ex: &Expr, e: E) { walk_expr(self, ex, e) }
  91     fn visit_expr_post(&mut self, _ex: &Expr, _e: E) { }
  92     fn visit_ty(&mut self, t: &Ty, e: E) { walk_ty(self, t, e) }
  93     fn visit_generics(&mut self, g: &Generics, e: E) { walk_generics(self, g, e) }
  94     fn visit_fn(&mut self, fk: &FnKind, fd: &FnDecl, b: &Block, s: Span, _: NodeId, e: E) {
  95         walk_fn(self, fk, fd, b, s, e)
  96     }
  97     fn visit_ty_method(&mut self, t: &TypeMethod, e: E) { walk_ty_method(self, t, e) }
  98     fn visit_trait_item(&mut self, t: &TraitItem, e: E) { walk_trait_item(self, t, e) }
  99     fn visit_struct_def(&mut self, s: &StructDef, _: Ident, _: &Generics, _: NodeId, e: E) {
 100         walk_struct_def(self, s, e)
 101     }
 102     fn visit_struct_field(&mut self, s: &StructField, e: E) { walk_struct_field(self, s, e) }
 103     fn visit_variant(&mut self, v: &Variant, g: &Generics, e: E) { walk_variant(self, v, g, e) }
 104     fn visit_opt_lifetime_ref(&mut self,
 105                               _span: Span,
 106                               opt_lifetime: &Option<Lifetime>,
 107                               env: E) {
 108         /*!
 109          * Visits an optional reference to a lifetime. The `span` is
 110          * the span of some surrounding reference should opt_lifetime
 111          * be None.
 112          */
 113         match *opt_lifetime {
 114             Some(ref l) => self.visit_lifetime_ref(l, env),
 115             None => ()
 116         }
 117     }
 118     fn visit_lifetime_ref(&mut self, _lifetime: &Lifetime, _e: E) {
 119         /*! Visits a reference to a lifetime */
 120     }
 121     fn visit_lifetime_decl(&mut self, _lifetime: &LifetimeDef, _e: E) {
 122         /*! Visits a declaration of a lifetime */
 123     }
 124     fn visit_explicit_self(&mut self, es: &ExplicitSelf, e: E) {
 125         walk_explicit_self(self, es, e)
 126     }
 127     fn visit_mac(&mut self, _macro: &Mac, _e: E) {
 128         fail!("visit_mac disabled by default");
 129         // NB: see note about macros above.
 130         // if you really want a visitor that
 131         // works on macros, use this
 132         // definition in your trait impl:
 133         // visit::walk_mac(self, _macro, _e)
 134     }
 135     fn visit_path(&mut self, path: &Path, _id: ast::NodeId, e: E) {
 136         walk_path(self, path, e)
 137     }
 138     fn visit_attribute(&mut self, _attr: &Attribute, _e: E) {}
 139 }
 140
 141 pub fn walk_inlined_item<E: Clone, V: Visitor<E>>(visitor: &mut V,
 142                                                   item: &ast::InlinedItem,
 143                                                   env: E) {
 144     match *item {
 145         IIItem(i) => visitor.visit_item(&*i, env),
 146         IIForeign(i) => visitor.visit_foreign_item(&*i, env),
 147         IITraitItem(_, iti) => {
 148             match iti {
 149                 ProvidedInlinedTraitItem(m) => {
 150                     walk_method_helper(visitor, &*m, env)
 151                 }
 152                 RequiredInlinedTraitItem(m) => {
 153                     walk_method_helper(visitor, &*m, env)
 154                 }
 155             }
 156         }
 157     }
 158 }
 159
 160
 161 pub fn walk_crate<E: Clone, V: Visitor<E>>(visitor: &mut V, krate: &Crate, env: E) {
 162     visitor.visit_mod(&krate.module, krate.span, CRATE_NODE_ID, env.clone());
 163     for attr in krate.attrs.iter() {
 164         visitor.visit_attribute(attr, env.clone());
 165     }
 166 }
 167
 168 pub fn walk_mod<E: Clone, V: Visitor<E>>(visitor: &mut V, module: &Mod, env: E) {
 169     for view_item in module.view_items.iter() {
 170         visitor.visit_view_item(view_item, env.clone())
 171     }
 172
 173     for item in module.items.iter() {
 174         visitor.visit_item(&**item, env.clone())
 175     }
 176 }
 177
 178 pub fn walk_view_item<E: Clone, V: Visitor<E>>(visitor: &mut V, vi: &ViewItem, env: E) {
 179     match vi.node {
 180         ViewItemExternCrate(name, _, _) => {
 181             visitor.visit_ident(vi.span, name, env.clone())
 182         }
 183         ViewItemUse(ref vp) => {
 184             match vp.node {
 185                 ViewPathSimple(ident, ref path, id) => {
 186                     visitor.visit_ident(vp.span, ident, env.clone());
 187                     visitor.visit_path(path, id, env.clone());
 188                 }
 189                 ViewPathGlob(ref path, id) => {
 190                     visitor.visit_path(path, id, env.clone());
 191                 }
 192                 ViewPathList(ref path, ref list, _) => {
 193                     for id in list.iter() {
 194                         match id.node {
 195                             PathListIdent { name, .. } => {
 196                                 visitor.visit_ident(id.span, name, env.clone());
 197                             }
 198                             PathListMod { .. } => ()
 199                         }
 200                     }
 201                     walk_path(visitor, path, env.clone());
 202                 }
 203             }
 204         }
 205     }
 206     for attr in vi.attrs.iter() {
 207         visitor.visit_attribute(attr, env.clone());
 208     }
 209 }
 210
 211 pub fn walk_local<E: Clone, V: Visitor<E>>(visitor: &mut V, local: &Local, env: E) {
 212     visitor.visit_pat(&*local.pat, env.clone());
 213     visitor.visit_ty(&*local.ty, env.clone());
 214     match local.init {
 215         None => {}
 216         Some(initializer) => visitor.visit_expr(&*initializer, env),
 217     }
 218 }
 219
 220 pub fn walk_explicit_self<E: Clone, V: Visitor<E>>(visitor: &mut V,
 221                                                    explicit_self: &ExplicitSelf,
 222                                                    env: E) {
 223     match explicit_self.node {
 224         SelfStatic | SelfValue(_) => {},
 225         SelfRegion(ref lifetime, _, _) => {
 226             visitor.visit_opt_lifetime_ref(explicit_self.span, lifetime, env)
 227         }
 228         SelfExplicit(ref typ, _) => visitor.visit_ty(&**typ, env.clone()),
 229     }
 230 }
 231
 232 /// Like with walk_method_helper this doesn't correspond to a method
 233 /// in Visitor, and so it gets a _helper suffix.
 234 pub fn walk_trait_ref_helper<E: Clone, V: Visitor<E>>(visitor: &mut V,
 235                                                       trait_ref: &TraitRef,
 236                                                       env: E) {
 237     visitor.visit_path(&trait_ref.path, trait_ref.ref_id, env)
 238 }
 239
 240 pub fn walk_item<E: Clone, V: Visitor<E>>(visitor: &mut V, item: &Item, env: E) {
 241     visitor.visit_ident(item.span, item.ident, env.clone());
 242     match item.node {
 243         ItemStatic(ref typ, _, ref expr) => {
 244             visitor.visit_ty(&**typ, env.clone());
 245             visitor.visit_expr(&**expr, env.clone());
 246         }
 247         ItemFn(declaration, fn_style, abi, ref generics, body) => {
 248             visitor.visit_fn(&FkItemFn(item.ident, generics, fn_style, abi),
 249                              &*declaration,
 250                              &*body,
 251                              item.span,
 252                              item.id,
 253                              env.clone())
 254         }
 255         ItemMod(ref module) => {
 256             visitor.visit_mod(module, item.span, item.id, env.clone())
 257         }
 258         ItemForeignMod(ref foreign_module) => {
 259             for view_item in foreign_module.view_items.iter() {
 260                 visitor.visit_view_item(view_item, env.clone())
 261             }
 262             for foreign_item in foreign_module.items.iter() {
 263                 visitor.visit_foreign_item(&**foreign_item, env.clone())
 264             }
 265         }
 266         ItemTy(ref typ, ref type_parameters) => {
 267             visitor.visit_ty(&**typ, env.clone());
 268             visitor.visit_generics(type_parameters, env.clone())
 269         }
 270         ItemEnum(ref enum_definition, ref type_parameters) => {
 271             visitor.visit_generics(type_parameters, env.clone());
 272             walk_enum_def(visitor, enum_definition, type_parameters, env.clone())
 273         }
 274         ItemImpl(ref type_parameters,
 275                  ref trait_reference,
 276                  typ,
 277                  ref impl_items) => {
 278             visitor.visit_generics(type_parameters, env.clone());
 279             match *trait_reference {
 280                 Some(ref trait_reference) => walk_trait_ref_helper(visitor,
 281                                                                    trait_reference, env.clone()),
 282                 None => ()
 283             }
 284             visitor.visit_ty(&*typ, env.clone());
 285             for impl_item in impl_items.iter() {
 286                 match *impl_item {
 287                     MethodImplItem(method) => {
 288                         walk_method_helper(visitor, &*method, env.clone())
 289                     }
 290                 }
 291             }
 292         }
 293         ItemStruct(ref struct_definition, ref generics) => {
 294             visitor.visit_generics(generics, env.clone());
 295             visitor.visit_struct_def(&**struct_definition,
 296                                      item.ident,
 297                                      generics,
 298                                      item.id,
 299                                      env.clone())
 300         }
 301         ItemTrait(ref generics, _, ref bounds, ref methods) => {
 302             visitor.visit_generics(generics, env.clone());
 303             walk_ty_param_bounds(visitor, bounds, env.clone());
 304             for method in methods.iter() {
 305                 visitor.visit_trait_item(method, env.clone())
 306             }
 307         }
 308         ItemMac(ref macro) => visitor.visit_mac(macro, env.clone()),
 309     }
 310     for attr in item.attrs.iter() {
 311         visitor.visit_attribute(attr, env.clone());
 312     }
 313 }
 314
 315 pub fn walk_enum_def<E: Clone, V:Visitor<E>>(visitor: &mut V,
 316                                              enum_definition: &EnumDef,
 317                                              generics: &Generics,
 318                                              env: E) {
 319     for &variant in enum_definition.variants.iter() {
 320         visitor.visit_variant(&*variant, generics, env.clone());
 321     }
 322 }
 323
 324 pub fn walk_variant<E: Clone, V: Visitor<E>>(visitor: &mut V,
 325                                              variant: &Variant,
 326                                              generics: &Generics,
 327                                              env: E) {
 328     visitor.visit_ident(variant.span, variant.node.name, env.clone());
 329
 330     match variant.node.kind {
 331         TupleVariantKind(ref variant_arguments) => {
 332             for variant_argument in variant_arguments.iter() {
 333                 visitor.visit_ty(&*variant_argument.ty, env.clone())
 334             }
 335         }
 336         StructVariantKind(ref struct_definition) => {
 337             visitor.visit_struct_def(&**struct_definition,
 338                                      variant.node.name,
 339                                      generics,
 340                                      variant.node.id,
 341                                      env.clone())
 342         }
 343     }
 344     match variant.node.disr_expr {
 345         Some(ref expr) => visitor.visit_expr(&**expr, env.clone()),
 346         None => ()
 347     }
 348     for attr in variant.node.attrs.iter() {
 349         visitor.visit_attribute(attr, env.clone());
 350     }
 351 }
 352
 353 pub fn skip_ty<E, V: Visitor<E>>(_: &mut V, _: &Ty, _: E) {
 354     // Empty!
 355 }
 356
 357 pub fn walk_ty<E: Clone, V: Visitor<E>>(visitor: &mut V, typ: &Ty, env: E) {
 358     match typ.node {
 359         TyUniq(ty) | TyVec(ty) | TyBox(ty) | TyParen(ty) => {
 360             visitor.visit_ty(&*ty, env)
 361         }
 362         TyPtr(ref mutable_type) => {
 363             visitor.visit_ty(&*mutable_type.ty, env)
 364         }
 365         TyRptr(ref lifetime, ref mutable_type) => {
 366             visitor.visit_opt_lifetime_ref(typ.span, lifetime, env.clone());
 367             visitor.visit_ty(&*mutable_type.ty, env)
 368         }
 369         TyTup(ref tuple_element_types) => {
 370             for &tuple_element_type in tuple_element_types.iter() {
 371                 visitor.visit_ty(&*tuple_element_type, env.clone())
 372             }
 373         }
 374         TyClosure(ref function_declaration) => {
 375             for argument in function_declaration.decl.inputs.iter() {
 376                 visitor.visit_ty(&*argument.ty, env.clone())
 377             }
 378             visitor.visit_ty(&*function_declaration.decl.output, env.clone());
 379             walk_ty_param_bounds(visitor, &function_declaration.bounds,
 380                                  env.clone());
 381             walk_lifetime_decls(visitor, &function_declaration.lifetimes,
 382                                 env.clone());
 383         }
 384         TyProc(ref function_declaration) => {
 385             for argument in function_declaration.decl.inputs.iter() {
 386                 visitor.visit_ty(&*argument.ty, env.clone())
 387             }
 388             visitor.visit_ty(&*function_declaration.decl.output, env.clone());
 389             walk_ty_param_bounds(visitor, &function_declaration.bounds,
 390                                  env.clone());
 391             walk_lifetime_decls(visitor, &function_declaration.lifetimes,
 392                                 env.clone());
 393         }
 394         TyBareFn(ref function_declaration) => {
 395             for argument in function_declaration.decl.inputs.iter() {
 396                 visitor.visit_ty(&*argument.ty, env.clone())
 397             }
 398             visitor.visit_ty(&*function_declaration.decl.output, env.clone());
 399             walk_lifetime_decls(visitor, &function_declaration.lifetimes,
 400                                 env.clone());
 401         }
 402         TyUnboxedFn(ref function_declaration) => {
 403             for argument in function_declaration.decl.inputs.iter() {
 404                 visitor.visit_ty(&*argument.ty, env.clone())
 405             }
 406             visitor.visit_ty(&*function_declaration.decl.output, env.clone());
 407         }
 408         TyPath(ref path, ref opt_bounds, id) => {
 409             visitor.visit_path(path, id, env.clone());
 410             match *opt_bounds {
 411                 Some(ref bounds) => {
 412                     walk_ty_param_bounds(visitor, bounds, env.clone());
 413                 }
 414                 None => { }
 415             }
 416         }
 417         TyFixedLengthVec(ref ty, ref expression) => {
 418             visitor.visit_ty(&**ty, env.clone());
 419             visitor.visit_expr(&**expression, env)
 420         }
 421         TyTypeof(ref expression) => {
 422             visitor.visit_expr(&**expression, env)
 423         }
 424         TyNil | TyBot | TyInfer => {}
 425     }
 426 }
 427
 428 fn walk_lifetime_decls<E: Clone, V: Visitor<E>>(visitor: &mut V,
 429                                                 lifetimes: &Vec<LifetimeDef>,
 430                                                 env: E) {
 431     for l in lifetimes.iter() {
 432         visitor.visit_lifetime_decl(l, env.clone());
 433     }
 434 }
 435
 436 pub fn walk_path<E: Clone, V: Visitor<E>>(visitor: &mut V, path: &Path, env: E) {
 437     for segment in path.segments.iter() {
 438         visitor.visit_ident(path.span, segment.identifier, env.clone());
 439
 440         for typ in segment.types.iter() {
 441             visitor.visit_ty(&**typ, env.clone());
 442         }
 443         for lifetime in segment.lifetimes.iter() {
 444             visitor.visit_lifetime_ref(lifetime, env.clone());
 445         }
 446     }
 447 }
 448
 449 pub fn walk_pat<E: Clone, V: Visitor<E>>(visitor: &mut V, pattern: &Pat, env: E) {
 450     match pattern.node {
 451         PatEnum(ref path, ref children) => {
 452             visitor.visit_path(path, pattern.id, env.clone());
 453             for children in children.iter() {
 454                 for child in children.iter() {
 455                     visitor.visit_pat(&**child, env.clone())
 456                 }
 457             }
 458         }
 459         PatStruct(ref path, ref fields, _) => {
 460             visitor.visit_path(path, pattern.id, env.clone());
 461             for field in fields.iter() {
 462                 visitor.visit_pat(&*field.pat, env.clone())
 463             }
 464         }
 465         PatTup(ref tuple_elements) => {
 466             for tuple_element in tuple_elements.iter() {
 467                 visitor.visit_pat(&**tuple_element, env.clone())
 468             }
 469         }
 470         PatBox(ref subpattern) |
 471         PatRegion(ref subpattern) => {
 472             visitor.visit_pat(&**subpattern, env)
 473         }
 474         PatIdent(_, ref pth1, ref optional_subpattern) => {
 475             visitor.visit_ident(pth1.span, pth1.node, env.clone());
 476             match *optional_subpattern {
 477                 None => {}
 478                 Some(ref subpattern) => visitor.visit_pat(&**subpattern, env),
 479             }
 480         }
 481         PatLit(ref expression) => visitor.visit_expr(&**expression, env),
 482         PatRange(ref lower_bound, ref upper_bound) => {
 483             visitor.visit_expr(&**lower_bound, env.clone());
 484             visitor.visit_expr(&**upper_bound, env)
 485         }
 486         PatWild(_) => (),
 487         PatVec(ref prepattern, ref slice_pattern, ref postpatterns) => {
 488             for prepattern in prepattern.iter() {
 489                 visitor.visit_pat(&**prepattern, env.clone())
 490             }
 491             for slice_pattern in slice_pattern.iter() {
 492                 visitor.visit_pat(&**slice_pattern, env.clone())
 493             }
 494             for postpattern in postpatterns.iter() {
 495                 visitor.visit_pat(&**postpattern, env.clone())
 496             }
 497         }
 498         PatMac(ref macro) => visitor.visit_mac(macro, env),
 499     }
 500 }
 501
 502 pub fn walk_foreign_item<E: Clone, V: Visitor<E>>(visitor: &mut V,
 503                                                   foreign_item: &ForeignItem,
 504                                                   env: E) {
 505     visitor.visit_ident(foreign_item.span, foreign_item.ident, env.clone());
 506
 507     match foreign_item.node {
 508         ForeignItemFn(ref function_declaration, ref generics) => {
 509             walk_fn_decl(visitor, &**function_declaration, env.clone());
 510             visitor.visit_generics(generics, env.clone())
 511         }
 512         ForeignItemStatic(ref typ, _) => visitor.visit_ty(&**typ, env.clone()),
 513     }
 514
 515     for attr in foreign_item.attrs.iter() {
 516         visitor.visit_attribute(attr, env.clone());
 517     }
 518 }
 519
 520 pub fn walk_ty_param_bounds<E: Clone, V: Visitor<E>>(visitor: &mut V,
 521                                                      bounds: &OwnedSlice<TyParamBound>,
 522                                                      env: E) {
 523     for bound in bounds.iter() {
 524         match *bound {
 525             TraitTyParamBound(ref typ) => {
 526                 walk_trait_ref_helper(visitor, typ, env.clone())
 527             }
 528             UnboxedFnTyParamBound(ref function_declaration) => {
 529                 for argument in function_declaration.decl.inputs.iter() {
 530                     visitor.visit_ty(&*argument.ty, env.clone())
 531                 }
 532                 visitor.visit_ty(&*function_declaration.decl.output,
 533                                  env.clone());
 534             }
 535             RegionTyParamBound(ref lifetime) => {
 536                 visitor.visit_lifetime_ref(lifetime, env.clone());
 537             }
 538         }
 539     }
 540 }
 541
 542 pub fn walk_generics<E: Clone, V: Visitor<E>>(visitor: &mut V,
 543                                               generics: &Generics,
 544                                               env: E) {
 545     for type_parameter in generics.ty_params.iter() {
 546         walk_ty_param_bounds(visitor, &type_parameter.bounds, env.clone());
 547         match type_parameter.default {
 548             Some(ref ty) => visitor.visit_ty(&**ty, env.clone()),
 549             None => {}
 550         }
 551     }
 552     walk_lifetime_decls(visitor, &generics.lifetimes, env.clone());
 553     for predicate in generics.where_clause.predicates.iter() {
 554         visitor.visit_ident(predicate.span, predicate.ident, env.clone());
 555         walk_ty_param_bounds(visitor, &predicate.bounds, env.clone());
 556     }
 557 }
 558
 559 pub fn walk_fn_decl<E: Clone, V: Visitor<E>>(visitor: &mut V,
 560                                              function_declaration: &FnDecl,
 561                                              env: E) {
 562     for argument in function_declaration.inputs.iter() {
 563         visitor.visit_pat(&*argument.pat, env.clone());
 564         visitor.visit_ty(&*argument.ty, env.clone())
 565     }
 566     visitor.visit_ty(&*function_declaration.output, env)
 567 }
 568
 569 // Note: there is no visit_method() method in the visitor, instead override
 570 // visit_fn() and check for FkMethod().  I named this visit_method_helper()
 571 // because it is not a default impl of any method, though I doubt that really
 572 // clarifies anything. - Niko
 573 pub fn walk_method_helper<E: Clone, V: Visitor<E>>(visitor: &mut V,
 574                                                    method: &Method,
 575                                                    env: E) {
 576     match method.node {
 577         MethDecl(ident, ref generics, _, _, _, decl, body, _) => {
 578             visitor.visit_ident(method.span, ident, env.clone());
 579             visitor.visit_fn(&FkMethod(ident, generics, method),
 580                              &*decl,
 581                              &*body,
 582                              method.span,
 583                              method.id,
 584                              env.clone());
 585             for attr in method.attrs.iter() {
 586                 visitor.visit_attribute(attr, env.clone());
 587             }
 588
 589         },
 590         MethMac(ref mac) => visitor.visit_mac(mac, env.clone())
 591     }
 592 }
 593
 594 pub fn walk_fn<E: Clone, V: Visitor<E>>(visitor: &mut V,
 595                                         function_kind: &FnKind,
 596                                         function_declaration: &FnDecl,
 597                                         function_body: &Block,
 598                                         _span: Span,
 599                                         env: E) {
 600     walk_fn_decl(visitor, function_declaration, env.clone());
 601
 602     match *function_kind {
 603         FkItemFn(_, generics, _, _) => {
 604             visitor.visit_generics(generics, env.clone());
 605         }
 606         FkMethod(_, generics, method) => {
 607             visitor.visit_generics(generics, env.clone());
 608             match method.node {
 609                 MethDecl(_, _, _, ref explicit_self, _, _, _, _) =>
 610                     visitor.visit_explicit_self(explicit_self, env.clone()),
 611                 MethMac(ref mac) =>
 612                     visitor.visit_mac(mac, env.clone())
 613             }
 614         }
 615         FkFnBlock(..) => {}
 616     }
 617
 618     visitor.visit_block(function_body, env)
 619 }
 620
 621 pub fn walk_ty_method<E: Clone, V: Visitor<E>>(visitor: &mut V,
 622                                                method_type: &TypeMethod,
 623                                                env: E) {
 624     visitor.visit_ident(method_type.span, method_type.ident, env.clone());
 625     visitor.visit_explicit_self(&method_type.explicit_self, env.clone());
 626     for argument_type in method_type.decl.inputs.iter() {
 627         visitor.visit_ty(&*argument_type.ty, env.clone())
 628     }
 629     visitor.visit_generics(&method_type.generics, env.clone());
 630     visitor.visit_ty(&*method_type.decl.output, env.clone());
 631     for attr in method_type.attrs.iter() {
 632         visitor.visit_attribute(attr, env.clone());
 633     }
 634 }
 635
 636 pub fn walk_trait_item<E: Clone, V: Visitor<E>>(visitor: &mut V,
 637                                                   trait_method: &TraitItem,
 638                                                   env: E) {
 639     match *trait_method {
 640         RequiredMethod(ref method_type) => {
 641             visitor.visit_ty_method(method_type, env)
 642         }
 643         ProvidedMethod(ref method) => walk_method_helper(visitor, &**method, env),
 644     }
 645 }
 646
 647 pub fn walk_struct_def<E: Clone, V: Visitor<E>>(visitor: &mut V,
 648                                                 struct_definition: &StructDef,
 649                                                 env: E) {
 650     match struct_definition.super_struct {
 651         Some(ref t) => visitor.visit_ty(&**t, env.clone()),
 652         None => {},
 653     }
 654     for field in struct_definition.fields.iter() {
 655         visitor.visit_struct_field(field, env.clone())
 656     }
 657 }
 658
 659 pub fn walk_struct_field<E: Clone, V: Visitor<E>>(visitor: &mut V,
 660                                                   struct_field: &StructField,
 661                                                   env: E) {
 662     match struct_field.node.kind {
 663         NamedField(name, _) => {
 664             visitor.visit_ident(struct_field.span, name, env.clone())
 665         }
 666         _ => {}
 667     }
 668
 669     visitor.visit_ty(&*struct_field.node.ty, env.clone());
 670
 671     for attr in struct_field.node.attrs.iter() {
 672         visitor.visit_attribute(attr, env.clone());
 673     }
 674 }
 675
 676 pub fn walk_block<E: Clone, V: Visitor<E>>(visitor: &mut V, block: &Block, env: E) {
 677     for view_item in block.view_items.iter() {
 678         visitor.visit_view_item(view_item, env.clone())
 679     }
 680     for statement in block.stmts.iter() {
 681         visitor.visit_stmt(&**statement, env.clone())
 682     }
 683     walk_expr_opt(visitor, block.expr, env)
 684 }
 685
 686 pub fn walk_stmt<E: Clone, V: Visitor<E>>(visitor: &mut V, statement: &Stmt, env: E) {
 687     match statement.node {
 688         StmtDecl(ref declaration, _) => visitor.visit_decl(&**declaration, env),
 689         StmtExpr(ref expression, _) | StmtSemi(ref expression, _) => {
 690             visitor.visit_expr(&**expression, env)
 691         }
 692         StmtMac(ref macro, _) => visitor.visit_mac(macro, env),
 693     }
 694 }
 695
 696 pub fn walk_decl<E: Clone, V: Visitor<E>>(visitor: &mut V, declaration: &Decl, env: E) {
 697     match declaration.node {
 698         DeclLocal(ref local) => visitor.visit_local(&**local, env),
 699         DeclItem(ref item) => visitor.visit_item(&**item, env),
 700     }
 701 }
 702
 703 pub fn walk_expr_opt<E: Clone, V: Visitor<E>>(visitor: &mut V,
 704                                               optional_expression: Option<Gc<Expr>>,
 705                                               env: E) {
 706     match optional_expression {
 707         None => {}
 708         Some(ref expression) => visitor.visit_expr(&**expression, env),
 709     }
 710 }
 711
 712 pub fn walk_exprs<E: Clone, V: Visitor<E>>(visitor: &mut V,
 713                                            expressions: &[Gc<Expr>],
 714                                            env: E) {
 715     for expression in expressions.iter() {
 716         visitor.visit_expr(&**expression, env.clone())
 717     }
 718 }
 719
 720 pub fn walk_mac<E, V: Visitor<E>>(_: &mut V, _: &Mac, _: E) {
 721     // Empty!
 722 }
 723
 724 pub fn walk_expr<E: Clone, V: Visitor<E>>(visitor: &mut V, expression: &Expr, env: E) {
 725     match expression.node {
 726         ExprBox(ref place, ref subexpression) => {
 727             visitor.visit_expr(&**place, env.clone());
 728             visitor.visit_expr(&**subexpression, env.clone())
 729         }
 730         ExprVec(ref subexpressions) => {
 731             walk_exprs(visitor, subexpressions.as_slice(), env.clone())
 732         }
 733         ExprRepeat(ref element, ref count) => {
 734             visitor.visit_expr(&**element, env.clone());
 735             visitor.visit_expr(&**count, env.clone())
 736         }
 737         ExprStruct(ref path, ref fields, optional_base) => {
 738             visitor.visit_path(path, expression.id, env.clone());
 739             for field in fields.iter() {
 740                 visitor.visit_expr(&*field.expr, env.clone())
 741             }
 742             walk_expr_opt(visitor, optional_base, env.clone())
 743         }
 744         ExprTup(ref subexpressions) => {
 745             for subexpression in subexpressions.iter() {
 746                 visitor.visit_expr(&**subexpression, env.clone())
 747             }
 748         }
 749         ExprCall(ref callee_expression, ref arguments) => {
 750             for argument in arguments.iter() {
 751                 visitor.visit_expr(&**argument, env.clone())
 752             }
 753             visitor.visit_expr(&**callee_expression, env.clone())
 754         }
 755         ExprMethodCall(_, ref types, ref arguments) => {
 756             walk_exprs(visitor, arguments.as_slice(), env.clone());
 757             for typ in types.iter() {
 758                 visitor.visit_ty(&**typ, env.clone())
 759             }
 760         }
 761         ExprBinary(_, ref left_expression, ref right_expression) => {
 762             visitor.visit_expr(&**left_expression, env.clone());
 763             visitor.visit_expr(&**right_expression, env.clone())
 764         }
 765         ExprAddrOf(_, ref subexpression) | ExprUnary(_, ref subexpression) => {
 766             visitor.visit_expr(&**subexpression, env.clone())
 767         }
 768         ExprLit(_) => {}
 769         ExprCast(ref subexpression, ref typ) => {
 770             visitor.visit_expr(&**subexpression, env.clone());
 771             visitor.visit_ty(&**typ, env.clone())
 772         }
 773         ExprIf(ref head_expression, ref if_block, optional_else) => {
 774             visitor.visit_expr(&**head_expression, env.clone());
 775             visitor.visit_block(&**if_block, env.clone());
 776             walk_expr_opt(visitor, optional_else, env.clone())
 777         }
 778         ExprWhile(ref subexpression, ref block, _) => {
 779             visitor.visit_expr(&**subexpression, env.clone());
 780             visitor.visit_block(&**block, env.clone())
 781         }
 782         ExprForLoop(ref pattern, ref subexpression, ref block, _) => {
 783             visitor.visit_pat(&**pattern, env.clone());
 784             visitor.visit_expr(&**subexpression, env.clone());
 785             visitor.visit_block(&**block, env.clone())
 786         }
 787         ExprLoop(ref block, _) => visitor.visit_block(&**block, env.clone()),
 788         ExprMatch(ref subexpression, ref arms) => {
 789             visitor.visit_expr(&**subexpression, env.clone());
 790             for arm in arms.iter() {
 791                 visitor.visit_arm(arm, env.clone())
 792             }
 793         }
 794         ExprFnBlock(_, ref function_declaration, ref body) => {
 795             visitor.visit_fn(&FkFnBlock,
 796                              &**function_declaration,
 797                              &**body,
 798                              expression.span,
 799                              expression.id,
 800                              env.clone())
 801         }
 802         ExprUnboxedFn(_, _, ref function_declaration, ref body) => {
 803             visitor.visit_fn(&FkFnBlock,
 804                              &**function_declaration,
 805                              &**body,
 806                              expression.span,
 807                              expression.id,
 808                              env.clone())
 809         }
 810         ExprProc(ref function_declaration, ref body) => {
 811             visitor.visit_fn(&FkFnBlock,
 812                              &**function_declaration,
 813                              &**body,
 814                              expression.span,
 815                              expression.id,
 816                              env.clone())
 817         }
 818         ExprBlock(ref block) => visitor.visit_block(&**block, env.clone()),
 819         ExprAssign(ref left_hand_expression, ref right_hand_expression) => {
 820             visitor.visit_expr(&**right_hand_expression, env.clone());
 821             visitor.visit_expr(&**left_hand_expression, env.clone())
 822         }
 823         ExprAssignOp(_, ref left_expression, ref right_expression) => {
 824             visitor.visit_expr(&**right_expression, env.clone());
 825             visitor.visit_expr(&**left_expression, env.clone())
 826         }
 827         ExprField(ref subexpression, _, ref types) => {
 828             visitor.visit_expr(&**subexpression, env.clone());
 829             for typ in types.iter() {
 830                 visitor.visit_ty(&**typ, env.clone())
 831             }
 832         }
 833         ExprIndex(ref main_expression, ref index_expression) => {
 834             visitor.visit_expr(&**main_expression, env.clone());
 835             visitor.visit_expr(&**index_expression, env.clone())
 836         }
 837         ExprPath(ref path) => {
 838             visitor.visit_path(path, expression.id, env.clone())
 839         }
 840         ExprBreak(_) | ExprAgain(_) => {}
 841         ExprRet(optional_expression) => {
 842             walk_expr_opt(visitor, optional_expression, env.clone())
 843         }
 844         ExprMac(ref macro) => visitor.visit_mac(macro, env.clone()),
 845         ExprParen(ref subexpression) => {
 846             visitor.visit_expr(&**subexpression, env.clone())
 847         }
 848         ExprInlineAsm(ref ia) => {
 849             for &(_, ref input) in ia.inputs.iter() {
 850                 visitor.visit_expr(&**input, env.clone())
 851             }
 852             for &(_, ref output, _) in ia.outputs.iter() {
 853                 visitor.visit_expr(&**output, env.clone())
 854             }
 855         }
 856     }
 857
 858     visitor.visit_expr_post(expression, env.clone())
 859 }
 860
 861 pub fn walk_arm<E: Clone, V: Visitor<E>>(visitor: &mut V, arm: &Arm, env: E) {
 862     for pattern in arm.pats.iter() {
 863         visitor.visit_pat(&**pattern, env.clone())
 864     }
 865     walk_expr_opt(visitor, arm.guard, env.clone());
 866     visitor.visit_expr(&*arm.body, env.clone());
 867     for attr in arm.attrs.iter() {
 868         visitor.visit_attribute(attr, env.clone());
 869     }
 870 }