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::iter::repeat;
18 use std::time::Duration;
19 use std::collections::hash_state::HashState;
23 use syntax::visit::Visitor;
25 // The name of the associated type for `Fn` return types
26 pub const FN_OUTPUT_NAME: &'static str = "Output";
28 // Useful type to use with `Result<>` indicate that an error has already
29 // been reported to the user, so no need to continue checking.
30 #[derive(Clone, Copy, Debug)]
31 pub struct ErrorReported;
33 pub fn time<T, U, F>(do_it: bool, what: &str, u: U, f: F) -> T where
36 thread_local!(static DEPTH: Cell<uint> = Cell::new(0));
37 if !do_it { return f(u); }
39 let old = DEPTH.with(|slot| {
50 Duration::span(move || {
51 *rvp = Some(f(u.take().unwrap()))
56 println!("{}time: {}.{:03} \t{}", repeat(" ").take(old).collect::<String>(),
57 dur.num_seconds(), dur.num_milliseconds() % 1000, what);
58 DEPTH.with(|slot| slot.set(old));
63 pub fn indent<R, F>(op: F) -> R where
67 // Use in conjunction with the log post-processor like `src/etc/indenter`
68 // to make debug output more readable.
71 debug!("<< (Result = {:?})", r);
76 _cannot_construct_outside_of_this_module: ()
79 impl Drop for Indenter {
80 fn drop(&mut self) { debug!("<<"); }
83 pub fn indenter() -> Indenter {
85 Indenter { _cannot_construct_outside_of_this_module: () }
88 struct LoopQueryVisitor<P> where P: FnMut(&ast::Expr_) -> bool {
93 impl<'v, P> Visitor<'v> for LoopQueryVisitor<P> where P: FnMut(&ast::Expr_) -> bool {
94 fn visit_expr(&mut self, e: &ast::Expr) {
95 self.flag |= (self.p)(&e.node);
97 // Skip inner loops, since a break in the inner loop isn't a
98 // break inside the outer loop
99 ast::ExprLoop(..) | ast::ExprWhile(..) => {}
100 _ => visit::walk_expr(self, e)
105 // Takes a predicate p, returns true iff p is true for any subexpressions
106 // of b -- skipping any inner loops (loop, while, loop_body)
107 pub fn loop_query<P>(b: &ast::Block, p: P) -> bool where P: FnMut(&ast::Expr_) -> bool {
108 let mut v = LoopQueryVisitor {
112 visit::walk_block(&mut v, b);
116 struct BlockQueryVisitor<P> where P: FnMut(&ast::Expr) -> bool {
121 impl<'v, P> Visitor<'v> for BlockQueryVisitor<P> where P: FnMut(&ast::Expr) -> bool {
122 fn visit_expr(&mut self, e: &ast::Expr) {
123 self.flag |= (self.p)(e);
124 visit::walk_expr(self, e)
128 // Takes a predicate p, returns true iff p is true for any subexpressions
129 // of b -- skipping any inner loops (loop, while, loop_body)
130 pub fn block_query<P>(b: &ast::Block, p: P) -> bool where P: FnMut(&ast::Expr) -> bool {
131 let mut v = BlockQueryVisitor {
135 visit::walk_block(&mut v, &*b);
139 /// K: Eq + Hash<S>, V, S, H: Hasher<S>
141 /// Determines whether there exists a path from `source` to `destination`. The graph is defined by
142 /// the `edges_map`, which maps from a node `S` to a list of its adjacent nodes `T`.
144 /// Efficiency note: This is implemented in an inefficient way because it is typically invoked on
145 /// very small graphs. If the graphs become larger, a more efficient graph representation and
146 /// algorithm would probably be advised.
147 pub fn can_reach<T, S>(edges_map: &HashMap<T, Vec<T>, S>, source: T,
148 destination: T) -> bool
150 <S as HashState>::Hasher: Hasher<Output=u64>,
151 T: Hash< <S as HashState>::Hasher> + Eq + Clone,
153 if source == destination {
157 // Do a little breadth-first-search here. The `queue` list
158 // doubles as a way to detect if we've seen a particular FR
159 // before. Note that we expect this graph to be an *extremely
161 let mut queue = vec!(source);
163 while i < queue.len() {
164 match edges_map.get(&queue[i]) {
166 for target in edges {
167 if *target == destination {
171 if !queue.iter().any(|x| x == target) {
172 queue.push((*target).clone());
183 /// Memoizes a one-argument closure using the given RefCell containing
184 /// a type implementing MutableMap to serve as a cache.
186 /// In the future the signature of this function is expected to be:
188 /// pub fn memoized<T: Clone, U: Clone, M: MutableMap<T, U>>(
189 /// cache: &RefCell<M>,
191 /// ) -> impl |T| -> U {
193 /// but currently it is not possible.
198 /// cache: RefCell<HashMap<uint, uint>>
201 /// fn factorial(ctxt: &Context, n: uint) -> uint {
202 /// memoized(&ctxt.cache, n, |n| match n {
204 /// _ => factorial(ctxt, n - 2) + factorial(ctxt, n - 1)
209 pub fn memoized<T, U, S, F>(cache: &RefCell<HashMap<T, U, S>>, arg: T, f: F) -> U
210 where T: Clone + Hash<<S as HashState>::Hasher> + Eq,
213 <S as HashState>::Hasher: Hasher<Output=u64>,
216 let key = arg.clone();
217 let result = cache.borrow().get(&key).map(|result| result.clone());
219 Some(result) => result,
222 cache.borrow_mut().insert(key, result.clone());