src/comp/middle/freevars.rs

   1 // A pass that annotates for each loops and functions with the free
   2 // variables that they contain.
   3
   4 import syntax::print::pprust::path_to_str;
   5 import int;
   6 import std::map::*;
   7 import option::*;
   8 import syntax::{ast, ast_util, visit};
   9 import middle::resolve;
  10 import syntax::codemap::span;
  11
  12 export annotate_freevars;
  13 export freevar_map;
  14 export freevar_info;
  15 export get_freevars;
  16 export has_freevars;
  17
  18 // A vector of defs representing the free variables referred to in a function.
  19 // (The def_upvar will already have been stripped).
  20 type freevar_entry = {
  21     def: ast::def, //< The variable being accessed free.
  22     span: span     //< First span where it is accessed (there can be multiple)
  23 };
  24 type freevar_info = @[@freevar_entry];
  25 type freevar_map = hashmap<ast::node_id, freevar_info>;
  26
  27 // Searches through part of the AST for all references to locals or
  28 // upvars in this frame and returns the list of definition IDs thus found.
  29 // Since we want to be able to collect upvars in some arbitrary piece
  30 // of the AST, we take a walker function that we invoke with a visitor
  31 // in order to start the search.
  32 fn collect_freevars(def_map: resolve::def_map, blk: ast::blk)
  33     -> freevar_info {
  34     let seen = new_int_hash();
  35     let refs = @mutable [];
  36
  37     fn ignore_item(_i: @ast::item, &&_depth: int, _v: visit::vt<int>) { }
  38
  39     let walk_expr =
  40         fn@ (expr: @ast::expr, &&depth: int, v: visit::vt<int>) {
  41             alt expr.node {
  42               ast::expr_fn(proto, decl, _, captures) {
  43                 if proto != ast::proto_bare {
  44                     visit::visit_expr(expr, depth + 1, v);
  45                 }
  46               }
  47               ast::expr_fn_block(_, _) {
  48                 visit::visit_expr(expr, depth + 1, v);
  49               }
  50               ast::expr_path(path) {
  51                   let i = 0;
  52                   alt def_map.find(expr.id) {
  53                     none. { fail ("Not found: " + path_to_str(path)) }
  54                     some(df) {
  55                       let def = df;
  56                       while i < depth {
  57                         alt copy def {
  58                           ast::def_upvar(_, inner, _) { def = *inner; }
  59                           _ { break; }
  60                         }
  61                         i += 1;
  62                       }
  63                       if i == depth { // Made it to end of loop
  64                         let dnum = ast_util::def_id_of_def(def).node;
  65                         if !seen.contains_key(dnum) {
  66                            *refs += [@{def:def, span:expr.span}];
  67                            seen.insert(dnum, ());
  68                         }
  69                       }
  70                     }
  71                   }
  72               }
  73               _ { visit::visit_expr(expr, depth, v); }
  74             }
  75         };
  76
  77     let v = visit::mk_vt(@{visit_item: ignore_item, visit_expr: walk_expr
  78                            with *visit::default_visitor()});
  79     v.visit_block(blk, 1, v);
  80     ret @*refs;
  81 }
  82
  83 // Build a map from every function and for-each body to a set of the
  84 // freevars contained in it. The implementation is not particularly
  85 // efficient as it fully recomputes the free variables at every
  86 // node of interest rather than building up the free variables in
  87 // one pass. This could be improved upon if it turns out to matter.
  88 fn annotate_freevars(def_map: resolve::def_map, crate: @ast::crate) ->
  89    freevar_map {
  90     let freevars = new_int_hash();
  91
  92     let walk_fn = fn@ (_fk: visit::fn_kind, _decl: ast::fn_decl,
  93                           blk: ast::blk, _sp: span, nid: ast::node_id) {
  94         let vars = collect_freevars(def_map, blk);
  95         freevars.insert(nid, vars);
  96     };
  97
  98     let visitor =
  99         visit::mk_simple_visitor(@{visit_fn: walk_fn
 100                                    with *visit::default_simple_visitor()});
 101     visit::visit_crate(*crate, (), visitor);
 102
 103     ret freevars;
 104 }
 105
 106 fn get_freevars(tcx: ty::ctxt, fid: ast::node_id) -> freevar_info {
 107     alt tcx.freevars.find(fid) {
 108       none. { fail "get_freevars: " + int::str(fid) + " has no freevars"; }
 109       some(d) { ret d; }
 110     }
 111 }
 112 fn has_freevars(tcx: ty::ctxt, fid: ast::node_id) -> bool {
 113     ret vec::len(*get_freevars(tcx, fid)) != 0u;
 114 }
 115
 116 // Local Variables:
 117 // mode: rust
 118 // fill-column: 78;
 119 // indent-tabs-mode: nil
 120 // c-basic-offset: 4
 121 // buffer-file-coding-system: utf-8-unix
 122 // End: