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.
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.
11 #![allow(non_camel_case_types)]
13 use std::cell::{RefCell, Cell};
14 use std::collections::HashMap;
16 use std::hash::{Hash, Hasher};
17 use std::time::Duration;
21 use syntax::visit::Visitor;
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;
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); }
32 let old = DEPTH.with(|slot| {
40 let dur = Duration::span(|| {
41 rv = Some(f(u.take().unwrap()))
45 println!("{}time: {}.{:03} \t{}", " ".repeat(old),
46 dur.num_seconds(), dur.num_milliseconds() % 1000, what);
47 DEPTH.with(|slot| slot.set(old));
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.
57 debug!("<< (Result = {})", r);
62 _cannot_construct_outside_of_this_module: ()
65 impl Drop for Indenter {
66 fn drop(&mut self) { debug!("<<"); }
69 pub fn indenter() -> Indenter {
71 Indenter { _cannot_construct_outside_of_this_module: () }
74 struct LoopQueryVisitor<'a> {
75 p: |&ast::Expr_|: 'a -> bool,
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);
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)
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 {
98 visit::walk_block(&mut v, b);
102 struct BlockQueryVisitor<'a> {
103 p: |&ast::Expr|: 'a -> bool,
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)
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 {
121 visit::walk_block(&mut v, &*b);
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>,
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`.
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.
143 if source == destination {
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
151 let mut queue = vec!(source);
153 while i < queue.len() {
154 match edges_map.get(&queue[i]) {
156 for target in edges.iter() {
157 if *target == destination {
161 if !queue.iter().any(|x| x == target) {
162 queue.push((*target).clone());
173 /// Memoizes a one-argument closure using the given RefCell containing
174 /// a type implementing MutableMap to serve as a cache.
176 /// In the future the signature of this function is expected to be:
178 /// pub fn memoized<T: Clone, U: Clone, M: MutableMap<T, U>>(
179 /// cache: &RefCell<M>,
181 /// ) -> impl |&: T| -> U {
183 /// but currently it is not possible.
188 /// cache: RefCell<HashMap<uint, uint>>
191 /// fn factorial(ctxt: &Context, n: uint) -> uint {
192 /// memoized(&ctxt.cache, n, |n| match n {
194 /// _ => factorial(ctxt, n - 2) + factorial(ctxt, n - 1)
199 pub fn memoized<T: Clone + Hash<S> + Eq, U: Clone, S, H: Hasher<S>>(
200 cache: &RefCell<HashMap<T, U, H>>,
204 let key = arg.clone();
205 let result = cache.borrow().get(&key).map(|result| result.clone());
207 Some(result) => result,
210 cache.borrow_mut().insert(key, result.clone());