src/librustc/util/common.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 #![allow(non_camel_case_types)]
  12
  13 use std::cell::{RefCell, Cell};
  14 use std::collections::HashMap;
  15 use std::fmt::Show;
  16 use std::hash::{Hash, Hasher};
  17 use std::iter::repeat;
  18 use std::time::Duration;
  19
  20 use syntax::ast;
  21 use syntax::visit;
  22 use syntax::visit::Visitor;
  23
  24 // Useful type to use with `Result<>` indicate that an error has already
  25 // been reported to the user, so no need to continue checking.
  26 #[deriving(Clone, Copy, Show)]
  27 pub struct ErrorReported;
  28
  29 pub fn time<T, U, F>(do_it: bool, what: &str, u: U, f: F) -> T where
  30     F: FnOnce(U) -> T,
  31 {
  32     thread_local!(static DEPTH: Cell<uint> = Cell::new(0));
  33     if !do_it { return f(u); }
  34
  35     let old = DEPTH.with(|slot| {
  36         let r = slot.get();
  37         slot.set(r + 1);
  38         r
  39     });
  40
  41     let mut u = Some(u);
  42     let mut rv = None;
  43     let dur = {
  44         let ref mut rvp = rv;
  45
  46         Duration::span(move || {
  47             *rvp = Some(f(u.take().unwrap()))
  48         })
  49     };
  50     let rv = rv.unwrap();
  51
  52     println!("{}time: {}.{:03} \t{}", repeat("  ").take(old).collect::<String>(),
  53              dur.num_seconds(), dur.num_milliseconds() % 1000, what);
  54     DEPTH.with(|slot| slot.set(old));
  55
  56     rv
  57 }
  58
  59 pub fn indent<R, F>(op: F) -> R where
  60     R: Show,
  61     F: FnOnce() -> R,
  62 {
  63     // Use in conjunction with the log post-processor like `src/etc/indenter`
  64     // to make debug output more readable.
  65     debug!(">>");
  66     let r = op();
  67     debug!("<< (Result = {})", r);
  68     r
  69 }
  70
  71 pub struct Indenter {
  72     _cannot_construct_outside_of_this_module: ()
  73 }
  74
  75 impl Drop for Indenter {
  76     fn drop(&mut self) { debug!("<<"); }
  77 }
  78
  79 pub fn indenter() -> Indenter {
  80     debug!(">>");
  81     Indenter { _cannot_construct_outside_of_this_module: () }
  82 }
  83
  84 struct LoopQueryVisitor<P> where P: FnMut(&ast::Expr_) -> bool {
  85     p: P,
  86     flag: bool,
  87 }
  88
  89 impl<'v, P> Visitor<'v> for LoopQueryVisitor<P> where P: FnMut(&ast::Expr_) -> bool {
  90     fn visit_expr(&mut self, e: &ast::Expr) {
  91         self.flag |= (self.p)(&e.node);
  92         match e.node {
  93           // Skip inner loops, since a break in the inner loop isn't a
  94           // break inside the outer loop
  95           ast::ExprLoop(..) | ast::ExprWhile(..) | ast::ExprForLoop(..) => {}
  96           _ => visit::walk_expr(self, e)
  97         }
  98     }
  99 }
 100
 101 // Takes a predicate p, returns true iff p is true for any subexpressions
 102 // of b -- skipping any inner loops (loop, while, loop_body)
 103 pub fn loop_query<P>(b: &ast::Block, p: P) -> bool where P: FnMut(&ast::Expr_) -> bool {
 104     let mut v = LoopQueryVisitor {
 105         p: p,
 106         flag: false,
 107     };
 108     visit::walk_block(&mut v, b);
 109     return v.flag;
 110 }
 111
 112 struct BlockQueryVisitor<P> where P: FnMut(&ast::Expr) -> bool {
 113     p: P,
 114     flag: bool,
 115 }
 116
 117 impl<'v, P> Visitor<'v> for BlockQueryVisitor<P> where P: FnMut(&ast::Expr) -> bool {
 118     fn visit_expr(&mut self, e: &ast::Expr) {
 119         self.flag |= (self.p)(e);
 120         visit::walk_expr(self, e)
 121     }
 122 }
 123
 124 // Takes a predicate p, returns true iff p is true for any subexpressions
 125 // of b -- skipping any inner loops (loop, while, loop_body)
 126 pub fn block_query<P>(b: &ast::Block, p: P) -> bool where P: FnMut(&ast::Expr) -> bool {
 127     let mut v = BlockQueryVisitor {
 128         p: p,
 129         flag: false,
 130     };
 131     visit::walk_block(&mut v, &*b);
 132     return v.flag;
 133 }
 134
 135 /// K: Eq + Hash<S>, V, S, H: Hasher<S>
 136 ///
 137 /// Determines whether there exists a path from `source` to `destination`.  The graph is defined by
 138 /// the `edges_map`, which maps from a node `S` to a list of its adjacent nodes `T`.
 139 ///
 140 /// Efficiency note: This is implemented in an inefficient way because it is typically invoked on
 141 /// very small graphs. If the graphs become larger, a more efficient graph representation and
 142 /// algorithm would probably be advised.
 143 pub fn can_reach<S,H:Hasher<S>,T:Eq+Clone+Hash<S>>(
 144     edges_map: &HashMap<T,Vec<T>,H>,
 145     source: T,
 146     destination: T)
 147     -> bool
 148 {
 149     if source == destination {
 150         return true;
 151     }
 152
 153     // Do a little breadth-first-search here.  The `queue` list
 154     // doubles as a way to detect if we've seen a particular FR
 155     // before.  Note that we expect this graph to be an *extremely
 156     // shallow* tree.
 157     let mut queue = vec!(source);
 158     let mut i = 0;
 159     while i < queue.len() {
 160         match edges_map.get(&queue[i]) {
 161             Some(edges) => {
 162                 for target in edges.iter() {
 163                     if *target == destination {
 164                         return true;
 165                     }
 166
 167                     if !queue.iter().any(|x| x == target) {
 168                         queue.push((*target).clone());
 169                     }
 170                 }
 171             }
 172             None => {}
 173         }
 174         i += 1;
 175     }
 176     return false;
 177 }
 178
 179 /// Memoizes a one-argument closure using the given RefCell containing
 180 /// a type implementing MutableMap to serve as a cache.
 181 ///
 182 /// In the future the signature of this function is expected to be:
 183 /// ```
 184 /// pub fn memoized<T: Clone, U: Clone, M: MutableMap<T, U>>(
 185 ///    cache: &RefCell<M>,
 186 ///    f: &|&: T| -> U
 187 /// ) -> impl |&: T| -> U {
 188 /// ```
 189 /// but currently it is not possible.
 190 ///
 191 /// # Example
 192 /// ```
 193 /// struct Context {
 194 ///    cache: RefCell<HashMap<uint, uint>>
 195 /// }
 196 ///
 197 /// fn factorial(ctxt: &Context, n: uint) -> uint {
 198 ///     memoized(&ctxt.cache, n, |n| match n {
 199 ///         0 | 1 => n,
 200 ///         _ => factorial(ctxt, n - 2) + factorial(ctxt, n - 1)
 201 ///     })
 202 /// }
 203 /// ```
 204 #[inline(always)]
 205 pub fn memoized<T, U, S, H, F>(cache: &RefCell<HashMap<T, U, H>>, arg: T, f: F) -> U where
 206     T: Clone + Hash<S> + Eq,
 207     U: Clone,
 208     H: Hasher<S>,
 209     F: FnOnce(T) -> U,
 210 {
 211     let key = arg.clone();
 212     let result = cache.borrow().get(&key).map(|result| result.clone());
 213     match result {
 214         Some(result) => result,
 215         None => {
 216             let result = f(arg);
 217             cache.borrow_mut().insert(key, result.clone());
 218             result
 219         }
 220     }
 221 }