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