4 import option::{none, some};
8 // Context-passing AST walker. Each overridden visit method has full control
9 // over what happens with its node, it can do its own traversal of the node's
10 // children (potentially passing in different contexts to each), call
11 // visit::visit_* to apply the default traversal algorithm (again, it can
12 // override the context), or prevent deeper traversal by doing nothing.
14 // Our typesystem doesn't do circular types, so the visitor record can not
15 // hold functions that take visitors. A vt tag is used to break the cycle.
16 tag vt<E> { mk_vt(visitor<E>); }
19 fk_item_fn(ident, [ty_param]); //< an item declared with fn()
20 fk_method(ident, [ty_param]);
21 fk_res(ident, [ty_param]);
22 fk_anon(proto); //< an anonymous function like fn@(...)
23 fk_fn_block; //< a block {||...}
26 fn name_of_fn(fk: fn_kind) -> ident {
28 fk_item_fn(name, _) | fk_method(name, _) | fk_res(name, _) { name }
29 fk_anon(_) | fk_fn_block. { "anon" }
33 fn tps_of_fn(fk: fn_kind) -> [ty_param] {
35 fk_item_fn(_, tps) | fk_method(_, tps) | fk_res(_, tps) { tps }
36 fk_anon(_) | fk_fn_block. { [] }
41 // takes the components so that one function can be
42 // generic over constr and ty_constr
43 @{visit_mod: fn@(_mod, span, E, vt<E>),
44 visit_view_item: fn@(@view_item, E, vt<E>),
45 visit_native_item: fn@(@native_item, E, vt<E>),
46 visit_item: fn@(@item, E, vt<E>),
47 visit_local: fn@(@local, E, vt<E>),
48 visit_block: fn@(ast::blk, E, vt<E>),
49 visit_stmt: fn@(@stmt, E, vt<E>),
50 visit_arm: fn@(arm, E, vt<E>),
51 visit_pat: fn@(@pat, E, vt<E>),
52 visit_decl: fn@(@decl, E, vt<E>),
53 visit_expr: fn@(@expr, E, vt<E>),
54 visit_ty: fn@(@ty, E, vt<E>),
55 visit_ty_params: fn@([ty_param], E, vt<E>),
56 visit_constr: fn@(@path, span, node_id, E, vt<E>),
57 visit_fn: fn@(fn_kind, fn_decl, blk, span, node_id, E, vt<E>)};
59 fn default_visitor<E>() -> visitor<E> {
60 ret @{visit_mod: bind visit_mod::<E>(_, _, _, _),
61 visit_view_item: bind visit_view_item::<E>(_, _, _),
62 visit_native_item: bind visit_native_item::<E>(_, _, _),
63 visit_item: bind visit_item::<E>(_, _, _),
64 visit_local: bind visit_local::<E>(_, _, _),
65 visit_block: bind visit_block::<E>(_, _, _),
66 visit_stmt: bind visit_stmt::<E>(_, _, _),
67 visit_arm: bind visit_arm::<E>(_, _, _),
68 visit_pat: bind visit_pat::<E>(_, _, _),
69 visit_decl: bind visit_decl::<E>(_, _, _),
70 visit_expr: bind visit_expr::<E>(_, _, _),
71 visit_ty: bind skip_ty::<E>(_, _, _),
72 visit_ty_params: bind visit_ty_params::<E>(_, _, _),
73 visit_constr: bind visit_constr::<E>(_, _, _, _, _),
74 visit_fn: bind visit_fn::<E>(_, _, _, _, _, _, _)};
77 fn visit_crate<E>(c: crate, e: E, v: vt<E>) {
78 v.visit_mod(c.node.module, c.span, e, v);
81 fn visit_crate_directive<E>(cd: @crate_directive, e: E, v: vt<E>) {
83 cdir_src_mod(_, _) { }
84 cdir_dir_mod(_, cdirs, _) {
85 for cdir: @crate_directive in cdirs {
86 visit_crate_directive(cdir, e, v);
89 cdir_view_item(vi) { v.visit_view_item(vi, e, v); }
94 fn visit_mod<E>(m: _mod, _sp: span, e: E, v: vt<E>) {
95 for vi: @view_item in m.view_items { v.visit_view_item(vi, e, v); }
96 for i: @item in m.items { v.visit_item(i, e, v); }
99 fn visit_view_item<E>(_vi: @view_item, _e: E, _v: vt<E>) { }
101 fn visit_local<E>(loc: @local, e: E, v: vt<E>) {
102 v.visit_pat(loc.node.pat, e, v);
103 v.visit_ty(loc.node.ty, e, v);
104 alt loc.node.init { none. { } some(i) { v.visit_expr(i.expr, e, v); } }
107 fn visit_item<E>(i: @item, e: E, v: vt<E>) {
109 item_const(t, ex) { v.visit_ty(t, e, v); v.visit_expr(ex, e, v); }
110 item_fn(decl, tp, body) {
111 v.visit_fn(fk_item_fn(i.ident, tp), decl, body, i.span, i.id, e, v);
113 item_mod(m) { v.visit_mod(m, i.span, e, v); }
114 item_native_mod(nm) {
115 for vi: @view_item in nm.view_items { v.visit_view_item(vi, e, v); }
116 for ni: @native_item in nm.items { v.visit_native_item(ni, e, v); }
118 item_ty(t, tps) { v.visit_ty(t, e, v); v.visit_ty_params(tps, e, v); }
119 item_res(decl, tps, body, dtor_id, _) {
120 v.visit_fn(fk_res(i.ident, tps), decl, body, i.span,
123 item_tag(variants, tps) {
124 v.visit_ty_params(tps, e, v);
125 for vr: variant in variants {
126 for va: variant_arg in vr.node.args { v.visit_ty(va.ty, e, v); }
129 item_obj(ob, tps, _) {
130 v.visit_ty_params(tps, e, v);
131 for f: obj_field in ob.fields { v.visit_ty(f.ty, e, v); }
132 for m: @method in ob.methods {
133 v.visit_fn(fk_method(m.ident, m.tps), m.decl, m.body, m.span,
137 item_impl(tps, ifce, ty, methods) {
138 v.visit_ty_params(tps, e, v);
139 alt ifce { some(ty) { v.visit_ty(ty, e, v); } _ {} }
140 v.visit_ty(ty, e, v);
142 v.visit_fn(fk_method(m.ident, m.tps), m.decl, m.body, m.span,
146 item_iface(tps, methods) {
147 v.visit_ty_params(tps, e, v);
149 for a in m.decl.inputs { v.visit_ty(a.ty, e, v); }
150 v.visit_ty(m.decl.output, e, v);
156 fn skip_ty<E>(_t: @ty, _e: E, _v: vt<E>) {}
158 fn visit_ty<E>(t: @ty, e: E, v: vt<E>) {
160 ty_box(mt) { v.visit_ty(mt.ty, e, v); }
161 ty_uniq(mt) { v.visit_ty(mt.ty, e, v); }
162 ty_vec(mt) { v.visit_ty(mt.ty, e, v); }
163 ty_ptr(mt) { v.visit_ty(mt.ty, e, v); }
165 for f: ty_field in flds { v.visit_ty(f.node.mt.ty, e, v); }
167 ty_tup(ts) { for tt in ts { v.visit_ty(tt, e, v); } }
169 for a in decl.inputs { v.visit_ty(a.ty, e, v); }
170 for c: @constr in decl.constraints {
171 v.visit_constr(c.node.path, c.span, c.node.id, e, v);
173 v.visit_ty(decl.output, e, v);
176 for m: ty_method in tmeths {
177 for a in m.decl.inputs { v.visit_ty(a.ty, e, v); }
178 v.visit_ty(m.decl.output, e, v);
181 ty_path(p, _) { visit_path(p, e, v); }
182 ty_type. {/* no-op */ }
185 for tc: @spanned<constr_general_<@path, node_id>> in cs {
186 v.visit_constr(tc.node.path, tc.span, tc.node.id, e, v);
193 fn visit_constr<E>(_operator: @path, _sp: span, _id: node_id, _e: E,
198 fn visit_path<E>(p: @path, e: E, v: vt<E>) {
199 for tp: @ty in p.node.types { v.visit_ty(tp, e, v); }
202 fn visit_pat<E>(p: @pat, e: E, v: vt<E>) {
204 pat_tag(path, children) {
205 visit_path(path, e, v);
206 for child: @pat in children { v.visit_pat(child, e, v); }
209 for f: field_pat in fields { v.visit_pat(f.pat, e, v); }
211 pat_tup(elts) { for elt in elts { v.visit_pat(elt, e, v); } }
212 pat_box(inner) | pat_uniq(inner) | pat_bind(_, some(inner)) {
213 v.visit_pat(inner, e, v);
219 fn visit_native_item<E>(ni: @native_item, e: E, v: vt<E>) {
221 native_item_fn(fd, tps) {
222 v.visit_ty_params(tps, e, v);
223 visit_fn_decl(fd, e, v);
229 fn visit_ty_params<E>(tps: [ty_param], e: E, v: vt<E>) {
231 for bound in *tp.bounds {
233 bound_iface(t) { v.visit_ty(t, e, v); }
240 fn visit_fn_decl<E>(fd: fn_decl, e: E, v: vt<E>) {
241 for a: arg in fd.inputs { v.visit_ty(a.ty, e, v); }
242 for c: @constr in fd.constraints {
243 v.visit_constr(c.node.path, c.span, c.node.id, e, v);
245 v.visit_ty(fd.output, e, v);
248 fn visit_fn<E>(fk: fn_kind, decl: fn_decl, body: blk, _sp: span,
249 _id: node_id, e: E, v: vt<E>) {
250 visit_fn_decl(decl, e, v);
251 v.visit_ty_params(tps_of_fn(fk), e, v);
252 v.visit_block(body, e, v);
255 fn visit_block<E>(b: ast::blk, e: E, v: vt<E>) {
256 for vi in b.node.view_items { v.visit_view_item(vi, e, v); }
257 for s in b.node.stmts { v.visit_stmt(s, e, v); }
258 visit_expr_opt(b.node.expr, e, v);
261 fn visit_stmt<E>(s: @stmt, e: E, v: vt<E>) {
263 stmt_decl(d, _) { v.visit_decl(d, e, v); }
264 stmt_expr(ex, _) { v.visit_expr(ex, e, v); }
265 stmt_semi(ex, _) { v.visit_expr(ex, e, v); }
269 fn visit_decl<E>(d: @decl, e: E, v: vt<E>) {
272 for (_, loc) in locs { v.visit_local(loc, e, v); }
274 decl_item(it) { v.visit_item(it, e, v); }
278 fn visit_expr_opt<E>(eo: option::t<@expr>, e: E, v: vt<E>) {
279 alt eo { none. { } some(ex) { v.visit_expr(ex, e, v); } }
282 fn visit_exprs<E>(exprs: [@expr], e: E, v: vt<E>) {
283 for ex: @expr in exprs { v.visit_expr(ex, e, v); }
286 fn visit_mac<E>(m: mac, e: E, v: vt<E>) {
288 ast::mac_invoc(pth, arg, body) { visit_expr(arg, e, v); }
289 ast::mac_embed_type(ty) { v.visit_ty(ty, e, v); }
290 ast::mac_embed_block(blk) { v.visit_block(blk, e, v); }
291 ast::mac_ellipsis. { }
295 fn visit_expr<E>(ex: @expr, e: E, v: vt<E>) {
297 expr_vec(es, _) { visit_exprs(es, e, v); }
298 expr_rec(flds, base) {
299 for f: field in flds { v.visit_expr(f.node.expr, e, v); }
300 visit_expr_opt(base, e, v);
302 expr_tup(elts) { for el in elts { v.visit_expr(el, e, v); } }
303 expr_call(callee, args, _) {
304 visit_exprs(args, e, v);
305 v.visit_expr(callee, e, v);
307 expr_bind(callee, args) {
308 v.visit_expr(callee, e, v);
309 for eo: option::t<@expr> in args { visit_expr_opt(eo, e, v); }
311 expr_binary(_, a, b) { v.visit_expr(a, e, v); v.visit_expr(b, e, v); }
312 expr_unary(_, a) { v.visit_expr(a, e, v); }
314 expr_cast(x, t) { v.visit_expr(x, e, v); v.visit_ty(t, e, v); }
316 v.visit_expr(x, e, v);
317 v.visit_block(b, e, v);
318 visit_expr_opt(eo, e, v);
320 expr_if_check(x, b, eo) {
321 v.visit_expr(x, e, v);
322 v.visit_block(b, e, v);
323 visit_expr_opt(eo, e, v);
325 expr_ternary(c, t, el) {
326 v.visit_expr(c, e, v);
327 v.visit_expr(t, e, v);
328 v.visit_expr(el, e, v);
330 expr_while(x, b) { v.visit_expr(x, e, v); v.visit_block(b, e, v); }
331 expr_for(dcl, x, b) {
332 v.visit_local(dcl, e, v);
333 v.visit_expr(x, e, v);
334 v.visit_block(b, e, v);
336 expr_do_while(b, x) { v.visit_block(b, e, v); v.visit_expr(x, e, v); }
338 v.visit_expr(x, e, v);
339 for a: arm in arms { v.visit_arm(a, e, v); }
341 expr_fn(proto, decl, body, _) {
342 v.visit_fn(fk_anon(proto), decl, body, ex.span, ex.id, e, v);
344 expr_fn_block(decl, body) {
345 v.visit_fn(fk_fn_block, decl, body, ex.span, ex.id, e, v);
347 expr_block(b) { v.visit_block(b, e, v); }
348 expr_assign(a, b) { v.visit_expr(b, e, v); v.visit_expr(a, e, v); }
349 expr_copy(a) { v.visit_expr(a, e, v); }
350 expr_move(a, b) { v.visit_expr(b, e, v); v.visit_expr(a, e, v); }
351 expr_swap(a, b) { v.visit_expr(a, e, v); v.visit_expr(b, e, v); }
352 expr_assign_op(_, a, b) {
353 v.visit_expr(b, e, v);
354 v.visit_expr(a, e, v);
356 expr_field(x, _, tys) {
357 v.visit_expr(x, e, v);
358 for tp in tys { v.visit_ty(tp, e, v); }
360 expr_index(a, b) { v.visit_expr(a, e, v); v.visit_expr(b, e, v); }
361 expr_path(p) { visit_path(p, e, v); }
362 expr_fail(eo) { visit_expr_opt(eo, e, v); }
365 expr_ret(eo) { visit_expr_opt(eo, e, v); }
366 expr_be(x) { v.visit_expr(x, e, v); }
368 v.visit_expr(lv, e, v);
369 v.visit_expr(x, e, v);
371 expr_check(_, x) { v.visit_expr(x, e, v); }
372 expr_assert(x) { v.visit_expr(x, e, v); }
373 expr_anon_obj(anon_obj) {
374 alt anon_obj.fields {
377 for f: anon_obj_field in fields {
378 v.visit_ty(f.ty, e, v);
379 v.visit_expr(f.expr, e, v);
383 alt anon_obj.inner_obj {
385 some(ex) { v.visit_expr(ex, e, v); }
387 for m: @method in anon_obj.methods {
388 v.visit_fn(fk_method(m.ident, m.tps), m.decl, m.body, m.span,
392 expr_mac(mac) { visit_mac(mac, e, v); }
396 fn visit_arm<E>(a: arm, e: E, v: vt<E>) {
397 for p: @pat in a.pats { v.visit_pat(p, e, v); }
398 visit_expr_opt(a.guard, e, v);
399 v.visit_block(a.body, e, v);
402 // Simpler, non-context passing interface. Always walks the whole tree, simply
403 // calls the given functions on the nodes.
405 type simple_visitor =
406 // takes the components so that one function can be
407 // generic over constr and ty_constr
408 @{visit_mod: fn@(_mod, span),
409 visit_view_item: fn@(@view_item),
410 visit_native_item: fn@(@native_item),
411 visit_item: fn@(@item),
412 visit_local: fn@(@local),
413 visit_block: fn@(ast::blk),
414 visit_stmt: fn@(@stmt),
416 visit_pat: fn@(@pat),
417 visit_decl: fn@(@decl),
418 visit_expr: fn@(@expr),
420 visit_ty_params: fn@([ty_param]),
421 visit_constr: fn@(@path, span, node_id),
422 visit_fn: fn@(fn_kind, fn_decl, blk, span, node_id)};
424 fn simple_ignore_ty(_t: @ty) {}
426 fn default_simple_visitor() -> simple_visitor {
427 ret @{visit_mod: fn(_m: _mod, _sp: span) { },
428 visit_view_item: fn(_vi: @view_item) { },
429 visit_native_item: fn(_ni: @native_item) { },
430 visit_item: fn(_i: @item) { },
431 visit_local: fn(_l: @local) { },
432 visit_block: fn(_b: ast::blk) { },
433 visit_stmt: fn(_s: @stmt) { },
434 visit_arm: fn(_a: arm) { },
435 visit_pat: fn(_p: @pat) { },
436 visit_decl: fn(_d: @decl) { },
437 visit_expr: fn(_e: @expr) { },
438 visit_ty: simple_ignore_ty,
439 visit_ty_params: fn(_ps: [ty_param]) {},
440 visit_constr: fn(_p: @path, _sp: span, _id: node_id) { },
441 visit_fn: fn(_fk: fn_kind, _d: fn_decl, _b: blk, _sp: span,
446 fn mk_simple_visitor(v: simple_visitor) -> vt<()> {
447 fn v_mod(f: fn@(_mod, span), m: _mod, sp: span, &&e: (), v: vt<()>) {
449 visit_mod(m, sp, e, v);
451 fn v_view_item(f: fn@(@view_item), vi: @view_item, &&e: (), v: vt<()>) {
453 visit_view_item(vi, e, v);
455 fn v_native_item(f: fn@(@native_item), ni: @native_item, &&e: (),
458 visit_native_item(ni, e, v);
460 fn v_item(f: fn@(@item), i: @item, &&e: (), v: vt<()>) {
464 fn v_local(f: fn@(@local), l: @local, &&e: (), v: vt<()>) {
466 visit_local(l, e, v);
468 fn v_block(f: fn@(ast::blk), bl: ast::blk, &&e: (), v: vt<()>) {
470 visit_block(bl, e, v);
472 fn v_stmt(f: fn@(@stmt), st: @stmt, &&e: (), v: vt<()>) {
474 visit_stmt(st, e, v);
476 fn v_arm(f: fn@(arm), a: arm, &&e: (), v: vt<()>) {
480 fn v_pat(f: fn@(@pat), p: @pat, &&e: (), v: vt<()>) {
484 fn v_decl(f: fn@(@decl), d: @decl, &&e: (), v: vt<()>) {
488 fn v_expr(f: fn@(@expr), ex: @expr, &&e: (), v: vt<()>) {
490 visit_expr(ex, e, v);
492 fn v_ty(f: fn@(@ty), ty: @ty, &&e: (), v: vt<()>) {
496 fn v_ty_params(f: fn@([ty_param]), ps: [ty_param], &&e: (), v: vt<()>) {
498 visit_ty_params(ps, e, v);
500 fn v_constr(f: fn@(@path, span, node_id), pt: @path, sp: span,
501 id: node_id, &&e: (), v: vt<()>) {
503 visit_constr(pt, sp, id, e, v);
505 fn v_fn(f: fn@(fn_kind, fn_decl, blk, span, node_id),
506 fk: fn_kind, decl: fn_decl, body: blk, sp: span,
507 id: node_id, &&e: (), v: vt<()>) {
508 f(fk, decl, body, sp, id);
509 visit_fn(fk, decl, body, sp, id, e, v);
511 let visit_ty = if v.visit_ty == simple_ignore_ty {
512 bind skip_ty(_, _, _)
514 bind v_ty(v.visit_ty, _, _, _)
516 ret mk_vt(@{visit_mod: bind v_mod(v.visit_mod, _, _, _, _),
517 visit_view_item: bind v_view_item(v.visit_view_item, _, _, _),
519 bind v_native_item(v.visit_native_item, _, _, _),
520 visit_item: bind v_item(v.visit_item, _, _, _),
521 visit_local: bind v_local(v.visit_local, _, _, _),
522 visit_block: bind v_block(v.visit_block, _, _, _),
523 visit_stmt: bind v_stmt(v.visit_stmt, _, _, _),
524 visit_arm: bind v_arm(v.visit_arm, _, _, _),
525 visit_pat: bind v_pat(v.visit_pat, _, _, _),
526 visit_decl: bind v_decl(v.visit_decl, _, _, _),
527 visit_expr: bind v_expr(v.visit_expr, _, _, _),
529 visit_ty_params: bind v_ty_params(v.visit_ty_params, _, _, _),
530 visit_constr: bind v_constr(v.visit_constr, _, _, _, _, _),
531 visit_fn: bind v_fn(v.visit_fn, _, _, _, _, _, _, _)
538 // indent-tabs-mode: nil
540 // buffer-file-coding-system: utf-8-unix