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