Merge remote-tracking branch 'origin/master' into gen

5 files changed, 81 insertions, 67 deletions

diff --git a/src/librustc_data_structures/bitslice.rs b/src/librustc_data_structures/bitslice.rs
index ba53578e579..f74af6ee163 100644
--- a/src/librustc_data_structures/bitslice.rs
+++ b/src/librustc_data_structures/bitslice.rs
@@ -134,9 +134,11 @@ pub trait BitwiseOperator {
 
 pub struct Union;
 impl BitwiseOperator for Union {
+    #[inline]
     fn join(&self, a: usize, b: usize) -> usize { a | b }
 }
 pub struct Subtract;
 impl BitwiseOperator for Subtract {
+    #[inline]
     fn join(&self, a: usize, b: usize) -> usize { a & !b }
 }
diff --git a/src/librustc_data_structures/fnv.rs b/src/librustc_data_structures/fnv.rs
deleted file mode 100644
index 5bd57236e7c..00000000000
--- a/src/librustc_data_structures/fnv.rs
+++ /dev/null
@@ -1,66 +0,0 @@
-// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-use std::collections::{HashMap, HashSet};
-use std::default::Default;
-use std::hash::{Hasher, Hash, BuildHasherDefault};
-
-pub type FnvHashMap<K, V> = HashMap<K, V, BuildHasherDefault<FnvHasher>>;
-pub type FnvHashSet<V> = HashSet<V, BuildHasherDefault<FnvHasher>>;
-
-#[allow(non_snake_case)]
-pub fn FnvHashMap<K: Hash + Eq, V>() -> FnvHashMap<K, V> {
-    HashMap::default()
-}
-
-#[allow(non_snake_case)]
-pub fn FnvHashSet<V: Hash + Eq>() -> FnvHashSet<V> {
-    HashSet::default()
-}
-
-/// A speedy hash algorithm for node ids and def ids. The hashmap in
-/// liballoc by default uses SipHash which isn't quite as speedy as we
-/// want. In the compiler we're not really worried about DOS attempts, so we
-/// just default to a non-cryptographic hash.
-///
-/// This uses FNV hashing, as described here:
-/// http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
-pub struct FnvHasher(u64);
-
-impl Default for FnvHasher {
-    /// Creates a `FnvHasher`, with a 64-bit hex initial value.
-    #[inline]
-    fn default() -> FnvHasher {
-        FnvHasher(0xcbf29ce484222325)
-    }
-}
-
-impl Hasher for FnvHasher {
-    #[inline]
-    fn write(&mut self, bytes: &[u8]) {
-        let FnvHasher(mut hash) = *self;
-        for byte in bytes {
-            hash = hash ^ (*byte as u64);
-            hash = hash.wrapping_mul(0x100000001b3);
-        }
-        *self = FnvHasher(hash);
-    }
-
-    #[inline]
-    fn finish(&self) -> u64 {
-        self.0
-    }
-}
-
-pub fn hash<T: Hash>(v: &T) -> u64 {
-    let mut state = FnvHasher::default();
-    v.hash(&mut state);
-    state.finish()
-}
diff --git a/src/librustc_data_structures/graph/mod.rs b/src/librustc_data_structures/graph/mod.rs
index f94ed6b7209..f562ae0e3b8 100644
--- a/src/librustc_data_structures/graph/mod.rs
+++ b/src/librustc_data_structures/graph/mod.rs
@@ -308,6 +308,42 @@ impl<N: Debug, E: Debug> Graph<N, E> {
         DepthFirstTraversal::with_start_node(self, start, direction)
     }
 
+    pub fn nodes_in_postorder<'a>(&'a self,
+                                  direction: Direction,
+                                  entry_node: NodeIndex)
+                                  -> Vec<NodeIndex>
+    {
+        let mut visited = BitVector::new(self.len_nodes());
+        let mut stack = vec![];
+        let mut result = Vec::with_capacity(self.len_nodes());
+        let mut push_node = |stack: &mut Vec<_>, node: NodeIndex| {
+            if visited.insert(node.0) {
+                stack.push((node, self.adjacent_edges(node, direction)));
+            }
+        };
+
+        for node in Some(entry_node).into_iter()
+            .chain(self.enumerated_nodes().map(|(node, _)| node))
+        {
+            push_node(&mut stack, node);
+            while let Some((node, mut iter)) = stack.pop() {
+                if let Some((_, child)) = iter.next() {
+                    let target = child.source_or_target(direction);
+                    // the current node needs more processing, so
+                    // add it back to the stack
+                    stack.push((node, iter));
+                    // and then push the new node
+                    push_node(&mut stack, target);
+                } else {
+                    result.push(node);
+                }
+            }
+        }
+
+        assert_eq!(result.len(), self.len_nodes());
+        result
+    }
+
     /// Whether or not a node can be reached from itself.
     pub fn is_node_cyclic(&self, starting_node_index: NodeIndex) -> bool {
         // This is similar to depth traversal below, but we
diff --git a/src/librustc_data_structures/graph/tests.rs b/src/librustc_data_structures/graph/tests.rs
index bdefc39a61a..b6a0d4cff5a 100644
--- a/src/librustc_data_structures/graph/tests.rs
+++ b/src/librustc_data_structures/graph/tests.rs
@@ -175,3 +175,46 @@ fn is_node_cyclic_b() {
     let graph = create_graph_with_cycle();
     assert!(graph.is_node_cyclic(NodeIndex(1)));
 }
+
+#[test]
+fn nodes_in_postorder() {
+    let expected = vec![
+        ("A", vec!["C", "E", "D", "B", "A", "F"]),
+        ("B", vec!["C", "E", "D", "B", "A", "F"]),
+        ("C", vec!["C", "E", "D", "B", "A", "F"]),
+        ("D", vec!["C", "E", "D", "B", "A", "F"]),
+        ("E", vec!["C", "E", "D", "B", "A", "F"]),
+        ("F", vec!["C", "E", "D", "B", "F", "A"])
+    ];
+
+    let graph = create_graph();
+
+    for ((idx, node), &(node_name, ref expected))
+        in graph.enumerated_nodes().zip(&expected)
+    {
+        assert_eq!(node.data, node_name);
+        assert_eq!(expected,
+                   &graph.nodes_in_postorder(OUTGOING, idx)
+                   .into_iter().map(|idx| *graph.node_data(idx))
+                   .collect::<Vec<&str>>());
+    }
+
+    let expected = vec![
+        ("A", vec!["D", "C", "B", "A"]),
+        ("B", vec!["D", "C", "B", "A"]),
+        ("C", vec!["B", "D", "C", "A"]),
+        ("D", vec!["C", "B", "D", "A"]),
+    ];
+
+    let graph = create_graph_with_cycle();
+
+    for ((idx, node), &(node_name, ref expected))
+        in graph.enumerated_nodes().zip(&expected)
+    {
+        assert_eq!(node.data, node_name);
+        assert_eq!(expected,
+                   &graph.nodes_in_postorder(OUTGOING, idx)
+                   .into_iter().map(|idx| *graph.node_data(idx))
+                   .collect::<Vec<&str>>());
+    }
+}
diff --git a/src/librustc_data_structures/lib.rs b/src/librustc_data_structures/lib.rs
index bb27d479a41..3cb3e088364 100644
--- a/src/librustc_data_structures/lib.rs
+++ b/src/librustc_data_structures/lib.rs
@@ -65,7 +65,6 @@ pub mod snapshot_vec;
 pub mod stable_hasher;
 pub mod transitive_relation;
 pub mod unify;
-pub mod fnv;
 pub mod fx;
 pub mod tuple_slice;
 pub mod veccell;