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
;
15 use std
::collections
::hash_state
::HashState
;
16 use std
::ffi
::CString
;
19 use std
::iter
::repeat
;
21 use std
::time
::Duration
;
25 use syntax
::visit
::Visitor
;
27 // The name of the associated type for `Fn` return types
28 pub const FN_OUTPUT_NAME
: &'
static str = "Output";
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
;
35 pub fn time
<T
, U
, F
>(do_it
: bool
, what
: &str, u
: U
, f
: F
) -> T
where
38 thread_local
!(static DEPTH
: Cell
<usize> = Cell
::new(0));
39 if !do_it { return f(u); }
41 let old
= DEPTH
.with(|slot
| {
51 Duration
::span(move || {
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 println
!("{}time: {:.3} \t{}", repeat(" ").take(old
).collect
::<String
>(),
65 DEPTH
.with(|slot
| slot
.set(old
));
70 pub fn indent
<R
, F
>(op
: F
) -> R
where
74 // Use in conjunction with the log post-processor like `src/etc/indenter`
75 // to make debug output more readable.
78 debug
!("<< (Result = {:?})", r
);
83 _cannot_construct_outside_of_this_module
: ()
86 impl Drop
for Indenter
{
87 fn drop(&mut self) { debug!("<<"); }
90 pub fn indenter() -> Indenter
{
92 Indenter { _cannot_construct_outside_of_this_module: () }
95 struct LoopQueryVisitor
<P
> where P
: FnMut(&ast
::Expr_
) -> bool
{
100 impl<'v
, P
> Visitor
<'v
> for LoopQueryVisitor
<P
> where P
: FnMut(&ast
::Expr_
) -> bool
{
101 fn visit_expr(&mut self, e
: &ast
::Expr
) {
102 self.flag
|= (self.p
)(&e
.node
);
104 // Skip inner loops, since a break in the inner loop isn't a
105 // break inside the outer loop
106 ast
::ExprLoop(..) | ast
::ExprWhile(..) => {}
107 _
=> visit
::walk_expr(self, e
)
112 // Takes a predicate p, returns true iff p is true for any subexpressions
113 // of b -- skipping any inner loops (loop, while, loop_body)
114 pub fn loop_query
<P
>(b
: &ast
::Block
, p
: P
) -> bool
where P
: FnMut(&ast
::Expr_
) -> bool
{
115 let mut v
= LoopQueryVisitor
{
119 visit
::walk_block(&mut v
, b
);
123 struct BlockQueryVisitor
<P
> where P
: FnMut(&ast
::Expr
) -> bool
{
128 impl<'v
, P
> Visitor
<'v
> for BlockQueryVisitor
<P
> where P
: FnMut(&ast
::Expr
) -> bool
{
129 fn visit_expr(&mut self, e
: &ast
::Expr
) {
130 self.flag
|= (self.p
)(e
);
131 visit
::walk_expr(self, e
)
135 // Takes a predicate p, returns true iff p is true for any subexpressions
136 // of b -- skipping any inner loops (loop, while, loop_body)
137 pub fn block_query
<P
>(b
: &ast
::Block
, p
: P
) -> bool
where P
: FnMut(&ast
::Expr
) -> bool
{
138 let mut v
= BlockQueryVisitor
{
142 visit
::walk_block(&mut v
, &*b
);
146 /// K: Eq + Hash<S>, V, S, H: Hasher<S>
148 /// Determines whether there exists a path from `source` to `destination`. The
149 /// graph is defined by the `edges_map`, which maps from a node `S` to a list of
150 /// its adjacent nodes `T`.
152 /// Efficiency note: This is implemented in an inefficient way because it is
153 /// typically invoked on very small graphs. If the graphs become larger, a more
154 /// efficient graph representation and algorithm would probably be advised.
155 pub fn can_reach
<T
, S
>(edges_map
: &HashMap
<T
, Vec
<T
>, S
>, source
: T
,
156 destination
: T
) -> bool
157 where S
: HashState
, T
: Hash
+ Eq
+ Clone
,
159 if source
== destination
{
163 // Do a little breadth-first-search here. The `queue` list
164 // doubles as a way to detect if we've seen a particular FR
165 // before. Note that we expect this graph to be an *extremely
167 let mut queue
= vec
!(source
);
169 while i
< queue
.len() {
170 match edges_map
.get(&queue
[i
]) {
172 for target
in edges
{
173 if *target
== destination
{
177 if !queue
.iter().any(|x
| x
== target
) {
178 queue
.push((*target
).clone());
189 /// Memoizes a one-argument closure using the given RefCell containing
190 /// a type implementing MutableMap to serve as a cache.
192 /// In the future the signature of this function is expected to be:
194 /// pub fn memoized<T: Clone, U: Clone, M: MutableMap<T, U>>(
195 /// cache: &RefCell<M>,
197 /// ) -> impl |T| -> U {
199 /// but currently it is not possible.
204 /// cache: RefCell<HashMap<usize, usize>>
207 /// fn factorial(ctxt: &Context, n: usize) -> usize {
208 /// memoized(&ctxt.cache, n, |n| match n {
210 /// _ => factorial(ctxt, n - 2) + factorial(ctxt, n - 1)
215 pub fn memoized
<T
, U
, S
, F
>(cache
: &RefCell
<HashMap
<T
, U
, S
>>, arg
: T
, f
: F
) -> U
216 where T
: Clone
+ Hash
+ Eq
,
221 let key
= arg
.clone();
222 let result
= cache
.borrow().get(&key
).cloned();
224 Some(result
) => result
,
227 cache
.borrow_mut().insert(key
, result
.clone());
234 pub fn path2cstr(p
: &Path
) -> CString
{
235 use std
::os
::unix
::prelude
::*;
237 let p
: &OsStr
= p
.as_ref();
238 CString
::new(p
.as_bytes()).unwrap()
241 pub fn path2cstr(p
: &Path
) -> CString
{
242 CString
::new(p
.to_str().unwrap()).unwrap()