diff options
Diffstat (limited to 'src/librustc_data_structures')
| -rw-r--r-- | src/librustc_data_structures/blake2b.rs | 2 | ||||
| -rw-r--r-- | src/librustc_data_structures/control_flow_graph/dominators/mod.rs | 79 | ||||
| -rw-r--r-- | src/librustc_data_structures/control_flow_graph/iterate/mod.rs | 16 | ||||
| -rw-r--r-- | src/librustc_data_structures/control_flow_graph/iterate/test.rs | 20 | ||||
| -rw-r--r-- | src/librustc_data_structures/control_flow_graph/mod.rs | 3 | ||||
| -rw-r--r-- | src/librustc_data_structures/control_flow_graph/reachable/mod.rs | 62 | ||||
| -rw-r--r-- | src/librustc_data_structures/control_flow_graph/reachable/test.rs | 50 | ||||
| -rw-r--r-- | src/librustc_data_structures/control_flow_graph/transpose.rs | 64 | ||||
| -rw-r--r-- | src/librustc_data_structures/fmt_wrap.rs | 31 | ||||
| -rw-r--r-- | src/librustc_data_structures/fx.rs | 6 | ||||
| -rw-r--r-- | src/librustc_data_structures/graph/mod.rs | 109 | ||||
| -rw-r--r-- | src/librustc_data_structures/graph/tests.rs | 81 | ||||
| -rw-r--r-- | src/librustc_data_structures/ivar.rs | 71 | ||||
| -rw-r--r-- | src/librustc_data_structures/lib.rs | 4 | ||||
| -rw-r--r-- | src/librustc_data_structures/obligation_forest/mod.rs | 48 | ||||
| -rw-r--r-- | src/librustc_data_structures/unify/mod.rs | 3 |
16 files changed, 6 insertions, 643 deletions
diff --git a/src/librustc_data_structures/blake2b.rs b/src/librustc_data_structures/blake2b.rs index 5adeef1ab3a..6b8bf8df0d3 100644 --- a/src/librustc_data_structures/blake2b.rs +++ b/src/librustc_data_structures/blake2b.rs @@ -24,7 +24,7 @@ use std::mem; use std::slice; #[repr(C)] -pub struct Blake2bCtx { +struct Blake2bCtx { b: [u8; 128], h: [u64; 8], t: [u64; 2], diff --git a/src/librustc_data_structures/control_flow_graph/dominators/mod.rs b/src/librustc_data_structures/control_flow_graph/dominators/mod.rs index 65dd336fdbd..90670517f59 100644 --- a/src/librustc_data_structures/control_flow_graph/dominators/mod.rs +++ b/src/librustc_data_structures/control_flow_graph/dominators/mod.rs @@ -134,56 +134,10 @@ impl<Node: Idx> Dominators<Node> { self.dominators(node).any(|n| n == dom) } - pub fn mutual_dominator_node(&self, node1: Node, node2: Node) -> Node { - assert!(self.is_reachable(node1), - "node {:?} is not reachable", - node1); - assert!(self.is_reachable(node2), - "node {:?} is not reachable", - node2); - intersect::<Node>(&self.post_order_rank, - &self.immediate_dominators, - node1, - node2) - } - - pub fn mutual_dominator<I>(&self, iter: I) -> Option<Node> - where I: IntoIterator<Item = Node> - { - let mut iter = iter.into_iter(); - iter.next() - .map(|dom| iter.fold(dom, |dom, node| self.mutual_dominator_node(dom, node))) - } - - pub fn all_immediate_dominators(&self) -> &IndexVec<Node, Option<Node>> { + #[cfg(test)] + fn all_immediate_dominators(&self) -> &IndexVec<Node, Option<Node>> { &self.immediate_dominators } - - pub fn dominator_tree(&self) -> DominatorTree<Node> { - let elem: Vec<Node> = Vec::new(); - let mut children: IndexVec<Node, Vec<Node>> = - IndexVec::from_elem_n(elem, self.immediate_dominators.len()); - let mut root = None; - for (index, immed_dom) in self.immediate_dominators.iter().enumerate() { - let node = Node::new(index); - match *immed_dom { - None => { - // node not reachable - } - Some(immed_dom) => { - if node == immed_dom { - root = Some(node); - } else { - children[immed_dom].push(node); - } - } - } - } - DominatorTree { - root: root.unwrap(), - children, - } - } } pub struct Iter<'dom, Node: Idx + 'dom> { @@ -215,38 +169,9 @@ pub struct DominatorTree<N: Idx> { } impl<Node: Idx> DominatorTree<Node> { - pub fn root(&self) -> Node { - self.root - } - pub fn children(&self, node: Node) -> &[Node] { &self.children[node] } - - pub fn iter_children_of(&self, node: Node) -> IterChildrenOf<Node> { - IterChildrenOf { - tree: self, - stack: vec![node], - } - } -} - -pub struct IterChildrenOf<'iter, Node: Idx + 'iter> { - tree: &'iter DominatorTree<Node>, - stack: Vec<Node>, -} - -impl<'iter, Node: Idx> Iterator for IterChildrenOf<'iter, Node> { - type Item = Node; - - fn next(&mut self) -> Option<Node> { - if let Some(node) = self.stack.pop() { - self.stack.extend(self.tree.children(node)); - Some(node) - } else { - None - } - } } impl<Node: Idx> fmt::Debug for DominatorTree<Node> { diff --git a/src/librustc_data_structures/control_flow_graph/iterate/mod.rs b/src/librustc_data_structures/control_flow_graph/iterate/mod.rs index 11b557cbcad..2d70b406342 100644 --- a/src/librustc_data_structures/control_flow_graph/iterate/mod.rs +++ b/src/librustc_data_structures/control_flow_graph/iterate/mod.rs @@ -47,22 +47,6 @@ fn post_order_walk<G: ControlFlowGraph>(graph: &G, result.push(node); } -pub fn pre_order_walk<G: ControlFlowGraph>(graph: &G, - node: G::Node, - result: &mut Vec<G::Node>, - visited: &mut IndexVec<G::Node, bool>) { - if visited[node] { - return; - } - visited[node] = true; - - result.push(node); - - for successor in graph.successors(node) { - pre_order_walk(graph, successor, result, visited); - } -} - pub fn reverse_post_order<G: ControlFlowGraph>(graph: &G, start_node: G::Node) -> Vec<G::Node> { let mut vec = post_order_from(graph, start_node); vec.reverse(); diff --git a/src/librustc_data_structures/control_flow_graph/iterate/test.rs b/src/librustc_data_structures/control_flow_graph/iterate/test.rs index dca45602f17..100881ddfdd 100644 --- a/src/librustc_data_structures/control_flow_graph/iterate/test.rs +++ b/src/librustc_data_structures/control_flow_graph/iterate/test.rs @@ -9,7 +9,6 @@ // except according to those terms. use super::super::test::TestGraph; -use super::super::transpose::TransposedGraph; use super::*; @@ -20,22 +19,3 @@ fn diamond_post_order() { let result = post_order_from(&graph, 0); assert_eq!(result, vec![3, 1, 2, 0]); } - - -#[test] -fn rev_post_order_inner_loop() { - // 0 -> 1 -> 2 -> 3 -> 5 - // ^ ^ v | - // | 6 <- 4 | - // +-----------------+ - let graph = TestGraph::new(0, - &[(0, 1), (1, 2), (2, 3), (3, 5), (3, 1), (2, 4), (4, 6), (6, 2)]); - - let rev_graph = TransposedGraph::new(&graph); - - let result = post_order_from_to(&rev_graph, 6, Some(2)); - assert_eq!(result, vec![4, 6]); - - let result = post_order_from_to(&rev_graph, 3, Some(1)); - assert_eq!(result, vec![4, 6, 2, 3]); -} diff --git a/src/librustc_data_structures/control_flow_graph/mod.rs b/src/librustc_data_structures/control_flow_graph/mod.rs index eb6839df627..7bf776675c6 100644 --- a/src/librustc_data_structures/control_flow_graph/mod.rs +++ b/src/librustc_data_structures/control_flow_graph/mod.rs @@ -9,13 +9,10 @@ // except according to those terms. use super::indexed_vec::Idx; -pub use std::slice::Iter; pub mod dominators; pub mod iterate; -pub mod reachable; mod reference; -pub mod transpose; #[cfg(test)] mod test; diff --git a/src/librustc_data_structures/control_flow_graph/reachable/mod.rs b/src/librustc_data_structures/control_flow_graph/reachable/mod.rs deleted file mode 100644 index 24210ebb95d..00000000000 --- a/src/librustc_data_structures/control_flow_graph/reachable/mod.rs +++ /dev/null @@ -1,62 +0,0 @@ -// Copyright 2016 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. - -//! Compute reachability using a simple dataflow propagation. -//! Store end-result in a big NxN bit matrix. - -use super::ControlFlowGraph; -use super::super::bitvec::BitVector; -use super::iterate::reverse_post_order; -use super::super::indexed_vec::{IndexVec, Idx}; - -#[cfg(test)] -mod test; - -pub fn reachable<G: ControlFlowGraph>(graph: &G) -> Reachability<G::Node> { - let reverse_post_order = reverse_post_order(graph, graph.start_node()); - reachable_given_rpo(graph, &reverse_post_order) -} - -pub fn reachable_given_rpo<G: ControlFlowGraph>(graph: &G, - reverse_post_order: &[G::Node]) - -> Reachability<G::Node> { - let mut reachability = Reachability::new(graph); - let mut changed = true; - while changed { - changed = false; - for &node in reverse_post_order.iter().rev() { - // every node can reach itself - changed |= reachability.bits[node].insert(node.index()); - - // and every pred can reach everything node can reach - for pred in graph.predecessors(node) { - let nodes_bits = reachability.bits[node].clone(); - changed |= reachability.bits[pred].insert_all(&nodes_bits); - } - } - } - reachability -} - -pub struct Reachability<Node: Idx> { - bits: IndexVec<Node, BitVector>, -} - -impl<Node: Idx> Reachability<Node> { - fn new<G: ControlFlowGraph>(graph: &G) -> Self { - let num_nodes = graph.num_nodes(); - Reachability { bits: IndexVec::from_elem_n(BitVector::new(num_nodes), num_nodes) } - } - - pub fn can_reach(&self, source: Node, target: Node) -> bool { - let bit: usize = target.index(); - self.bits[source].contains(bit) - } -} diff --git a/src/librustc_data_structures/control_flow_graph/reachable/test.rs b/src/librustc_data_structures/control_flow_graph/reachable/test.rs deleted file mode 100644 index ef45deeaafc..00000000000 --- a/src/librustc_data_structures/control_flow_graph/reachable/test.rs +++ /dev/null @@ -1,50 +0,0 @@ -// Copyright 2016 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 super::super::test::TestGraph; - -use super::*; - -#[test] -fn test1() { - // 0 -> 1 -> 2 -> 3 - // ^ v - // 6 <- 4 -> 5 - let graph = TestGraph::new(0, &[(0, 1), (1, 2), (2, 3), (2, 4), (4, 5), (4, 6), (6, 1)]); - let reachable = reachable(&graph); - assert!((0..6).all(|i| reachable.can_reach(0, i))); - assert!((1..6).all(|i| reachable.can_reach(1, i))); - assert!((1..6).all(|i| reachable.can_reach(2, i))); - assert!((1..6).all(|i| reachable.can_reach(4, i))); - assert!((1..6).all(|i| reachable.can_reach(6, i))); - assert!(reachable.can_reach(3, 3)); - assert!(!reachable.can_reach(3, 5)); - assert!(!reachable.can_reach(5, 3)); -} - -/// use bigger indices to cross between words in the bit set -#[test] -fn test2() { - // 30 -> 31 -> 32 -> 33 - // ^ v - // 36 <- 34 -> 35 - let graph = TestGraph::new(30, - &[(30, 31), (31, 32), (32, 33), (32, 34), (34, 35), (34, 36), - (36, 31)]); - let reachable = reachable(&graph); - assert!((30..36).all(|i| reachable.can_reach(30, i))); - assert!((31..36).all(|i| reachable.can_reach(31, i))); - assert!((31..36).all(|i| reachable.can_reach(32, i))); - assert!((31..36).all(|i| reachable.can_reach(34, i))); - assert!((31..36).all(|i| reachable.can_reach(36, i))); - assert!(reachable.can_reach(33, 33)); - assert!(!reachable.can_reach(33, 35)); - assert!(!reachable.can_reach(35, 33)); -} diff --git a/src/librustc_data_structures/control_flow_graph/transpose.rs b/src/librustc_data_structures/control_flow_graph/transpose.rs deleted file mode 100644 index 163d65c089c..00000000000 --- a/src/librustc_data_structures/control_flow_graph/transpose.rs +++ /dev/null @@ -1,64 +0,0 @@ -// Copyright 2016 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 super::*; - -pub struct TransposedGraph<G: ControlFlowGraph> { - base_graph: G, - start_node: G::Node, -} - -impl<G: ControlFlowGraph> TransposedGraph<G> { - pub fn new(base_graph: G) -> Self { - let start_node = base_graph.start_node(); - Self::with_start(base_graph, start_node) - } - - pub fn with_start(base_graph: G, start_node: G::Node) -> Self { - TransposedGraph { - base_graph, - start_node, - } - } -} - -impl<G: ControlFlowGraph> ControlFlowGraph for TransposedGraph<G> { - type Node = G::Node; - - fn num_nodes(&self) -> usize { - self.base_graph.num_nodes() - } - - fn start_node(&self) -> Self::Node { - self.start_node - } - - fn predecessors<'graph>(&'graph self, - node: Self::Node) - -> <Self as GraphPredecessors<'graph>>::Iter { - self.base_graph.successors(node) - } - - fn successors<'graph>(&'graph self, - node: Self::Node) - -> <Self as GraphSuccessors<'graph>>::Iter { - self.base_graph.predecessors(node) - } -} - -impl<'graph, G: ControlFlowGraph> GraphPredecessors<'graph> for TransposedGraph<G> { - type Item = G::Node; - type Iter = <G as GraphSuccessors<'graph>>::Iter; -} - -impl<'graph, G: ControlFlowGraph> GraphSuccessors<'graph> for TransposedGraph<G> { - type Item = G::Node; - type Iter = <G as GraphPredecessors<'graph>>::Iter; -} diff --git a/src/librustc_data_structures/fmt_wrap.rs b/src/librustc_data_structures/fmt_wrap.rs deleted file mode 100644 index 50fd1d802b7..00000000000 --- a/src/librustc_data_structures/fmt_wrap.rs +++ /dev/null @@ -1,31 +0,0 @@ -// Copyright 2016 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::fmt; - -// Provide some more formatting options for some data types (at the moment -// that's just `{:x}` for slices of u8). - -pub struct FmtWrap<T>(pub T); - -impl<'a> fmt::LowerHex for FmtWrap<&'a [u8]> { - fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result { - for byte in self.0.iter() { - try!(write!(formatter, "{:02x}", byte)); - } - Ok(()) - } -} - -#[test] -fn test_lower_hex() { - let bytes: &[u8] = &[0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef]; - assert_eq!("0123456789abcdef", &format!("{:x}", FmtWrap(bytes))); -} diff --git a/src/librustc_data_structures/fx.rs b/src/librustc_data_structures/fx.rs index 00dfc1617a8..5bf25437763 100644 --- a/src/librustc_data_structures/fx.rs +++ b/src/librustc_data_structures/fx.rs @@ -107,9 +107,3 @@ impl Hasher for FxHasher { self.hash as u64 } } - -pub fn hash<T: Hash>(v: &T) -> u64 { - let mut state = FxHasher::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 eb8342530ab..a5f83ce05f5 100644 --- a/src/librustc_data_structures/graph/mod.rs +++ b/src/librustc_data_structures/graph/mod.rs @@ -106,13 +106,6 @@ impl NodeIndex { } } -impl EdgeIndex { - /// Returns unique id (unique with respect to the graph holding associated edge). - pub fn edge_id(&self) -> usize { - self.0 - } -} - impl<N: Debug, E: Debug> Graph<N, E> { pub fn new() -> Graph<N, E> { Graph { @@ -201,34 +194,10 @@ impl<N: Debug, E: Debug> Graph<N, E> { return idx; } - pub fn mut_edge_data(&mut self, idx: EdgeIndex) -> &mut E { - &mut self.edges[idx.0].data - } - - pub fn edge_data(&self, idx: EdgeIndex) -> &E { - &self.edges[idx.0].data - } - pub fn edge(&self, idx: EdgeIndex) -> &Edge<E> { &self.edges[idx.0] } - pub fn first_adjacent(&self, node: NodeIndex, dir: Direction) -> EdgeIndex { - //! Accesses the index of the first edge adjacent to `node`. - //! This is useful if you wish to modify the graph while walking - //! the linked list of edges. - - self.nodes[node.0].first_edge[dir.repr] - } - - pub fn next_adjacent(&self, edge: EdgeIndex, dir: Direction) -> EdgeIndex { - //! Accesses the next edge in a given direction. - //! This is useful if you wish to modify the graph while walking - //! the linked list of edges. - - self.edges[edge.0].next_edge[dir.repr] - } - // # Iterating over nodes, edges pub fn enumerated_nodes(&self) -> EnumeratedNodes<N> { @@ -282,25 +251,6 @@ impl<N: Debug, E: Debug> Graph<N, E> { self.incoming_edges(target).sources() } - /// A common use for graphs in our compiler is to perform - /// fixed-point iteration. In this case, each edge represents a - /// constraint, and the nodes themselves are associated with - /// variables or other bitsets. This method facilitates such a - /// computation. - pub fn iterate_until_fixed_point<'a, F>(&'a self, mut op: F) - where F: FnMut(usize, EdgeIndex, &'a Edge<E>) -> bool - { - let mut iteration = 0; - let mut changed = true; - while changed { - changed = false; - iteration += 1; - for (edge_index, edge) in self.enumerated_edges() { - changed |= op(iteration, edge_index, edge); - } - } - } - pub fn depth_traverse<'a>(&'a self, start: NodeIndex, direction: Direction) @@ -343,35 +293,6 @@ impl<N: Debug, E: Debug> Graph<N, E> { 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 - // can't use that, because depth traversal doesn't show - // the starting node a second time. - let mut visited = BitVector::new(self.len_nodes()); - let mut stack = vec![starting_node_index]; - - while let Some(current_node_index) = stack.pop() { - visited.insert(current_node_index.0); - - // Directionality doesn't change the answer, - // so just use outgoing edges. - for (_, edge) in self.outgoing_edges(current_node_index) { - let target_node_index = edge.target(); - - if target_node_index == starting_node_index { - return true; - } - - if !visited.contains(target_node_index.0) { - stack.push(target_node_index); - } - } - } - - false - } } // # Iterators @@ -479,16 +400,6 @@ pub struct DepthFirstTraversal<'g, N, E> } impl<'g, N: Debug, E: Debug> DepthFirstTraversal<'g, N, E> { - pub fn new(graph: &'g Graph<N, E>, direction: Direction) -> Self { - let visited = BitVector::new(graph.len_nodes()); - DepthFirstTraversal { - graph, - stack: vec![], - visited, - direction, - } - } - pub fn with_start_node(graph: &'g Graph<N, E>, start_node: NodeIndex, direction: Direction) @@ -503,13 +414,6 @@ impl<'g, N: Debug, E: Debug> DepthFirstTraversal<'g, N, E> { } } - pub fn reset(&mut self, start_node: NodeIndex) { - self.stack.truncate(0); - self.stack.push(start_node); - self.visited.clear(); - self.visited.insert(start_node.node_id()); - } - fn visit(&mut self, node: NodeIndex) { if self.visited.insert(node.node_id()) { self.stack.push(node); @@ -532,19 +436,6 @@ impl<'g, N: Debug, E: Debug> Iterator for DepthFirstTraversal<'g, N, E> { } } -pub fn each_edge_index<F>(max_edge_index: EdgeIndex, mut f: F) - where F: FnMut(EdgeIndex) -> bool -{ - let mut i = 0; - let n = max_edge_index.0; - while i < n { - if !f(EdgeIndex(i)) { - return; - } - i += 1; - } -} - impl<E> Edge<E> { pub fn source(&self) -> NodeIndex { self.source diff --git a/src/librustc_data_structures/graph/tests.rs b/src/librustc_data_structures/graph/tests.rs index b6a0d4cff5a..007704357af 100644 --- a/src/librustc_data_structures/graph/tests.rs +++ b/src/librustc_data_structures/graph/tests.rs @@ -43,29 +43,6 @@ fn create_graph() -> TestGraph { return graph; } -fn create_graph_with_cycle() -> TestGraph { - let mut graph = Graph::new(); - - // Create a graph with a cycle. - // - // A --> B <-- + - // | | - // v | - // C --> D - - let a = graph.add_node("A"); - let b = graph.add_node("B"); - let c = graph.add_node("C"); - let d = graph.add_node("D"); - - graph.add_edge(a, b, "AB"); - graph.add_edge(b, c, "BC"); - graph.add_edge(c, d, "CD"); - graph.add_edge(d, b, "DB"); - - return graph; -} - #[test] fn each_node() { let graph = create_graph(); @@ -82,7 +59,6 @@ fn each_edge() { let graph = create_graph(); let expected = ["AB", "BC", "BD", "DE", "EC", "FB"]; graph.each_edge(|idx, edge| { - assert_eq!(&expected[idx.0], graph.edge_data(idx)); assert_eq!(expected[idx.0], edge.data); true }); @@ -97,7 +73,6 @@ fn test_adjacent_edges<N: PartialEq + Debug, E: PartialEq + Debug>(graph: &Graph let mut counter = 0; for (edge_index, edge) in graph.incoming_edges(start_index) { - assert!(graph.edge_data(edge_index) == &edge.data); assert!(counter < expected_incoming.len()); debug!("counter={:?} expected={:?} edge_index={:?} edge={:?}", counter, @@ -117,7 +92,6 @@ fn test_adjacent_edges<N: PartialEq + Debug, E: PartialEq + Debug>(graph: &Graph let mut counter = 0; for (edge_index, edge) in graph.outgoing_edges(start_index) { - assert!(graph.edge_data(edge_index) == &edge.data); assert!(counter < expected_outgoing.len()); debug!("counter={:?} expected={:?} edge_index={:?} edge={:?}", counter, @@ -163,58 +137,3 @@ fn each_adjacent_from_d() { let graph = create_graph(); test_adjacent_edges(&graph, NodeIndex(3), "D", &[("BD", "B")], &[("DE", "E")]); } - -#[test] -fn is_node_cyclic_a() { - let graph = create_graph_with_cycle(); - assert!(!graph.is_node_cyclic(NodeIndex(0))); -} - -#[test] -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/ivar.rs b/src/librustc_data_structures/ivar.rs deleted file mode 100644 index de44509ef2f..00000000000 --- a/src/librustc_data_structures/ivar.rs +++ /dev/null @@ -1,71 +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::fmt; -use std::cell::Cell; - -/// A write-once variable. When constructed, it is empty, and -/// can only be set once. -/// -/// Ivars ensure that data that can only be initialized once. A full -/// implementation is used for concurrency and blocks on a read of an -/// unfulfilled value. This implementation is more minimal and panics -/// if you attempt to read the value before it has been set. It is also -/// not `Sync`, but may be extended in the future to be usable as a true -/// concurrency type. -/// -/// The `T: Copy` bound is not strictly needed, but it is required by -/// Cell (so removing it would require using UnsafeCell), and it -/// suffices for the current purposes. -#[derive(PartialEq)] -pub struct Ivar<T: Copy> { - data: Cell<Option<T>>, -} - -impl<T: Copy> Ivar<T> { - pub fn new() -> Ivar<T> { - Ivar { data: Cell::new(None) } - } - - pub fn get(&self) -> Option<T> { - self.data.get() - } - - pub fn fulfill(&self, value: T) { - assert!(self.data.get().is_none(), "Value already set!"); - self.data.set(Some(value)); - } - - pub fn is_fulfilled(&self) -> bool { - self.data.get().is_some() - } - - pub fn unwrap(&self) -> T { - self.get().unwrap() - } -} - -impl<T: Copy + fmt::Debug> fmt::Debug for Ivar<T> { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - match self.get() { - Some(val) => write!(f, "Ivar({:?})", val), - None => f.write_str("Ivar(<unfulfilled>)"), - } - } -} - -impl<T: Copy> Clone for Ivar<T> { - fn clone(&self) -> Ivar<T> { - match self.get() { - Some(val) => Ivar { data: Cell::new(Some(val)) }, - None => Ivar::new(), - } - } -} diff --git a/src/librustc_data_structures/lib.rs b/src/librustc_data_structures/lib.rs index 3cb3e088364..54eed6dc92a 100644 --- a/src/librustc_data_structures/lib.rs +++ b/src/librustc_data_structures/lib.rs @@ -52,11 +52,9 @@ pub mod accumulate_vec; pub mod small_vec; pub mod base_n; pub mod bitslice; -pub mod blake2b; pub mod bitvec; -pub mod fmt_wrap; +pub mod blake2b; pub mod graph; -pub mod ivar; pub mod indexed_set; pub mod indexed_vec; pub mod obligation_forest; diff --git a/src/librustc_data_structures/obligation_forest/mod.rs b/src/librustc_data_structures/obligation_forest/mod.rs index 5a5bc67b592..02cae52166a 100644 --- a/src/librustc_data_structures/obligation_forest/mod.rs +++ b/src/librustc_data_structures/obligation_forest/mod.rs @@ -57,11 +57,6 @@ pub trait ObligationProcessor { where I: Clone + Iterator<Item=&'c Self::Obligation>; } -struct SnapshotData { - node_len: usize, - cache_list_len: usize, -} - pub struct ObligationForest<O: ForestObligation> { /// The list of obligations. In between calls to /// `process_obligations`, this list only contains nodes in the @@ -83,14 +78,9 @@ pub struct ObligationForest<O: ForestObligation> { /// A list of the obligations added in snapshots, to allow /// for their removal. cache_list: Vec<O::Predicate>, - snapshots: Vec<SnapshotData>, scratch: Option<Vec<usize>>, } -pub struct Snapshot { - len: usize, -} - #[derive(Debug)] struct Node<O> { obligation: O, @@ -166,7 +156,6 @@ impl<O: ForestObligation> ObligationForest<O> { pub fn new() -> ObligationForest<O> { ObligationForest { nodes: vec![], - snapshots: vec![], done_cache: FxHashSet(), waiting_cache: FxHashMap(), cache_list: vec![], @@ -180,39 +169,6 @@ impl<O: ForestObligation> ObligationForest<O> { self.nodes.len() } - pub fn start_snapshot(&mut self) -> Snapshot { - self.snapshots.push(SnapshotData { - node_len: self.nodes.len(), - cache_list_len: self.cache_list.len() - }); - Snapshot { len: self.snapshots.len() } - } - - pub fn commit_snapshot(&mut self, snapshot: Snapshot) { - assert_eq!(snapshot.len, self.snapshots.len()); - let info = self.snapshots.pop().unwrap(); - assert!(self.nodes.len() >= info.node_len); - assert!(self.cache_list.len() >= info.cache_list_len); - } - - pub fn rollback_snapshot(&mut self, snapshot: Snapshot) { - // Check that we are obeying stack discipline. - assert_eq!(snapshot.len, self.snapshots.len()); - let info = self.snapshots.pop().unwrap(); - - for entry in &self.cache_list[info.cache_list_len..] { - self.done_cache.remove(entry); - self.waiting_cache.remove(entry); - } - - self.nodes.truncate(info.node_len); - self.cache_list.truncate(info.cache_list_len); - } - - pub fn in_snapshot(&self) -> bool { - !self.snapshots.is_empty() - } - /// Registers an obligation /// /// This CAN be done in a snapshot @@ -262,7 +218,6 @@ impl<O: ForestObligation> ObligationForest<O> { /// /// This cannot be done during a snapshot. pub fn to_errors<E: Clone>(&mut self, error: E) -> Vec<Error<O, E>> { - assert!(!self.in_snapshot()); let mut errors = vec![]; for index in 0..self.nodes.len() { if let NodeState::Pending = self.nodes[index].state.get() { @@ -297,7 +252,6 @@ impl<O: ForestObligation> ObligationForest<O> { where P: ObligationProcessor<Obligation=O> { debug!("process_obligations(len={})", self.nodes.len()); - assert!(!self.in_snapshot()); // cannot unroll this action let mut errors = vec![]; let mut stalled = true; @@ -528,8 +482,6 @@ impl<O: ForestObligation> ObligationForest<O> { /// on these nodes may be present. This is done by e.g. `process_cycles`. #[inline(never)] fn compress(&mut self) -> Vec<O> { - assert!(!self.in_snapshot()); // didn't write code to unroll this action - let nodes_len = self.nodes.len(); let mut node_rewrites: Vec<_> = self.scratch.take().unwrap(); node_rewrites.extend(0..nodes_len); diff --git a/src/librustc_data_structures/unify/mod.rs b/src/librustc_data_structures/unify/mod.rs index c9c50e1acb6..7853bf9478a 100644 --- a/src/librustc_data_structures/unify/mod.rs +++ b/src/librustc_data_structures/unify/mod.rs @@ -275,7 +275,8 @@ impl<'tcx, K: UnifyKey> UnificationTable<K> self.get(id).value } - pub fn unioned(&mut self, a_id: K, b_id: K) -> bool { + #[cfg(test)] + fn unioned(&mut self, a_id: K, b_id: K) -> bool { self.find(a_id) == self.find(b_id) } } |