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 rv = None;
  48     let dur = {
  49         let ref mut rvp = rv;
  50
  51         Duration::span(move || {
  52             *rvp = Some(f(u))
  53         })
  54     };
  55     let rv = rv.unwrap();
  56
  57     // Hack up our own formatting for the duration to make it easier for scripts
  58     // to parse (always use the same number of decimal places and the same unit).
  59     const NANOS_PER_SEC: f64 = 1_000_000_000.0;
  60     let secs = dur.secs() as f64;
  61     let secs = secs + dur.extra_nanos() as f64 / NANOS_PER_SEC;
  62
  63     let mem_string = match get_resident() {
  64         Some(n) => {
  65             let mb = n as f64 / 1_000_000.0;
  66             format!("; rss: {}MB", mb.round() as usize)
  67         }
  68         None => "".to_owned(),
  69     };
  70     println!("{}time: {:.3}{}\t{}", repeat("  ").take(old).collect::<String>(),
  71              secs, mem_string, what);
  72
  73     DEPTH.with(|slot| slot.set(old));
  74
  75     rv
  76 }
  77
  78 // Memory reporting
  79 fn get_resident() -> Option<usize> {
  80     if cfg!(unix) {
  81         get_proc_self_statm_field(1)
  82     } else {
  83         None
  84     }
  85 }
  86
  87 // Like std::macros::try!, but for Option<>.
  88 macro_rules! option_try(
  89     ($e:expr) => (match $e { Some(e) => e, None => return None })
  90 );
  91
  92 fn get_proc_self_statm_field(field: usize) -> Option<usize> {
  93     use std::fs::File;
  94     use std::io::Read;
  95
  96     assert!(cfg!(unix));
  97
  98     let mut f = option_try!(File::open("/proc/self/statm").ok());
  99     let mut contents = String::new();
 100     option_try!(f.read_to_string(&mut contents).ok());
 101     let s = option_try!(contents.split_whitespace().nth(field));
 102     let npages = option_try!(s.parse::<usize>().ok());
 103     Some(npages * ::std::env::page_size())
 104 }
 105
 106 pub fn indent<R, F>(op: F) -> R where
 107     R: Debug,
 108     F: FnOnce() -> R,
 109 {
 110     // Use in conjunction with the log post-processor like `src/etc/indenter`
 111     // to make debug output more readable.
 112     debug!(">>");
 113     let r = op();
 114     debug!("<< (Result = {:?})", r);
 115     r
 116 }
 117
 118 pub struct Indenter {
 119     _cannot_construct_outside_of_this_module: ()
 120 }
 121
 122 impl Drop for Indenter {
 123     fn drop(&mut self) { debug!("<<"); }
 124 }
 125
 126 pub fn indenter() -> Indenter {
 127     debug!(">>");
 128     Indenter { _cannot_construct_outside_of_this_module: () }
 129 }
 130
 131 struct LoopQueryVisitor<P> where P: FnMut(&ast::Expr_) -> bool {
 132     p: P,
 133     flag: bool,
 134 }
 135
 136 impl<'v, P> Visitor<'v> for LoopQueryVisitor<P> where P: FnMut(&ast::Expr_) -> bool {
 137     fn visit_expr(&mut self, e: &ast::Expr) {
 138         self.flag |= (self.p)(&e.node);
 139         match e.node {
 140           // Skip inner loops, since a break in the inner loop isn't a
 141           // break inside the outer loop
 142           ast::ExprLoop(..) | ast::ExprWhile(..) => {}
 143           _ => visit::walk_expr(self, e)
 144         }
 145     }
 146 }
 147
 148 // Takes a predicate p, returns true iff p is true for any subexpressions
 149 // of b -- skipping any inner loops (loop, while, loop_body)
 150 pub fn loop_query<P>(b: &ast::Block, p: P) -> bool where P: FnMut(&ast::Expr_) -> bool {
 151     let mut v = LoopQueryVisitor {
 152         p: p,
 153         flag: false,
 154     };
 155     visit::walk_block(&mut v, b);
 156     return v.flag;
 157 }
 158
 159 struct BlockQueryVisitor<P> where P: FnMut(&ast::Expr) -> bool {
 160     p: P,
 161     flag: bool,
 162 }
 163
 164 impl<'v, P> Visitor<'v> for BlockQueryVisitor<P> where P: FnMut(&ast::Expr) -> bool {
 165     fn visit_expr(&mut self, e: &ast::Expr) {
 166         self.flag |= (self.p)(e);
 167         visit::walk_expr(self, e)
 168     }
 169 }
 170
 171 // Takes a predicate p, returns true iff p is true for any subexpressions
 172 // of b -- skipping any inner loops (loop, while, loop_body)
 173 pub fn block_query<P>(b: &ast::Block, p: P) -> bool where P: FnMut(&ast::Expr) -> bool {
 174     let mut v = BlockQueryVisitor {
 175         p: p,
 176         flag: false,
 177     };
 178     visit::walk_block(&mut v, &*b);
 179     return v.flag;
 180 }
 181
 182 /// K: Eq + Hash<S>, V, S, H: Hasher<S>
 183 ///
 184 /// Determines whether there exists a path from `source` to `destination`.  The
 185 /// graph is defined by the `edges_map`, which maps from a node `S` to a list of
 186 /// its adjacent nodes `T`.
 187 ///
 188 /// Efficiency note: This is implemented in an inefficient way because it is
 189 /// typically invoked on very small graphs. If the graphs become larger, a more
 190 /// efficient graph representation and algorithm would probably be advised.
 191 pub fn can_reach<T, S>(edges_map: &HashMap<T, Vec<T>, S>, source: T,
 192                        destination: T) -> bool
 193     where S: HashState, T: Hash + Eq + Clone,
 194 {
 195     if source == destination {
 196         return true;
 197     }
 198
 199     // Do a little breadth-first-search here.  The `queue` list
 200     // doubles as a way to detect if we've seen a particular FR
 201     // before.  Note that we expect this graph to be an *extremely
 202     // shallow* tree.
 203     let mut queue = vec!(source);
 204     let mut i = 0;
 205     while i < queue.len() {
 206         match edges_map.get(&queue[i]) {
 207             Some(edges) => {
 208                 for target in edges {
 209                     if *target == destination {
 210                         return true;
 211                     }
 212
 213                     if !queue.iter().any(|x| x == target) {
 214                         queue.push((*target).clone());
 215                     }
 216                 }
 217             }
 218             None => {}
 219         }
 220         i += 1;
 221     }
 222     return false;
 223 }
 224
 225 /// Memoizes a one-argument closure using the given RefCell containing
 226 /// a type implementing MutableMap to serve as a cache.
 227 ///
 228 /// In the future the signature of this function is expected to be:
 229 /// ```
 230 /// pub fn memoized<T: Clone, U: Clone, M: MutableMap<T, U>>(
 231 ///    cache: &RefCell<M>,
 232 ///    f: &|T| -> U
 233 /// ) -> impl |T| -> U {
 234 /// ```
 235 /// but currently it is not possible.
 236 ///
 237 /// # Examples
 238 /// ```
 239 /// struct Context {
 240 ///    cache: RefCell<HashMap<usize, usize>>
 241 /// }
 242 ///
 243 /// fn factorial(ctxt: &Context, n: usize) -> usize {
 244 ///     memoized(&ctxt.cache, n, |n| match n {
 245 ///         0 | 1 => n,
 246 ///         _ => factorial(ctxt, n - 2) + factorial(ctxt, n - 1)
 247 ///     })
 248 /// }
 249 /// ```
 250 #[inline(always)]
 251 pub fn memoized<T, U, S, F>(cache: &RefCell<HashMap<T, U, S>>, arg: T, f: F) -> U
 252     where T: Clone + Hash + Eq,
 253           U: Clone,
 254           S: HashState,
 255           F: FnOnce(T) -> U,
 256 {
 257     let key = arg.clone();
 258     let result = cache.borrow().get(&key).cloned();
 259     match result {
 260         Some(result) => result,
 261         None => {
 262             let result = f(arg);
 263             cache.borrow_mut().insert(key, result.clone());
 264             result
 265         }
 266     }
 267 }
 268
 269 #[cfg(unix)]
 270 pub fn path2cstr(p: &Path) -> CString {
 271     use std::os::unix::prelude::*;
 272     use std::ffi::OsStr;
 273     let p: &OsStr = p.as_ref();
 274     CString::new(p.as_bytes()).unwrap()
 275 }
 276 #[cfg(windows)]
 277 pub fn path2cstr(p: &Path) -> CString {
 278     CString::new(p.to_str().unwrap()).unwrap()
 279 }