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