diff options
Diffstat (limited to 'compiler/rustc_data_structures/src')
| -rw-r--r-- | compiler/rustc_data_structures/src/transitive_relation.rs | 121 | ||||
| -rw-r--r-- | compiler/rustc_data_structures/src/transitive_relation/tests.rs | 48 |
2 files changed, 99 insertions, 70 deletions
diff --git a/compiler/rustc_data_structures/src/transitive_relation.rs b/compiler/rustc_data_structures/src/transitive_relation.rs index 0ff64969b07..f016c391fe7 100644 --- a/compiler/rustc_data_structures/src/transitive_relation.rs +++ b/compiler/rustc_data_structures/src/transitive_relation.rs @@ -1,45 +1,57 @@ +use crate::frozen::Frozen; use crate::fx::FxIndexSet; -use crate::sync::Lock; use rustc_index::bit_set::BitMatrix; use std::fmt::Debug; use std::hash::Hash; use std::mem; +use std::ops::Deref; #[cfg(test)] mod tests; #[derive(Clone, Debug)] -pub struct TransitiveRelation<T> { +pub struct TransitiveRelationBuilder<T> { // List of elements. This is used to map from a T to a usize. elements: FxIndexSet<T>, // List of base edges in the graph. Require to compute transitive // closure. edges: Vec<Edge>, +} + +#[derive(Debug)] +pub struct TransitiveRelation<T> { + // Frozen transitive relation elements and edges. + builder: Frozen<TransitiveRelationBuilder<T>>, - // This is a cached transitive closure derived from the edges. - // Currently, we build it lazily and just throw out any existing - // copy whenever a new edge is added. (The Lock is to permit - // the lazy computation.) This is kind of silly, except for the - // fact its size is tied to `self.elements.len()`, so I wanted to - // wait before building it up to avoid reallocating as new edges - // are added with new elements. Perhaps better would be to ask the - // user for a batch of edges to minimize this effect, but I - // already wrote the code this way. :P -nmatsakis - closure: Lock<Option<BitMatrix<usize, usize>>>, + // Cached transitive closure derived from the edges. + closure: Frozen<BitMatrix<usize, usize>>, } -// HACK(eddyb) manual impl avoids `Default` bound on `T`. -impl<T: Eq + Hash> Default for TransitiveRelation<T> { - fn default() -> Self { +impl<T> Deref for TransitiveRelation<T> { + type Target = Frozen<TransitiveRelationBuilder<T>>; + + fn deref(&self) -> &Self::Target { + &self.builder + } +} + +impl<T: Clone> Clone for TransitiveRelation<T> { + fn clone(&self) -> Self { TransitiveRelation { - elements: Default::default(), - edges: Default::default(), - closure: Default::default(), + builder: Frozen::freeze(self.builder.deref().clone()), + closure: Frozen::freeze(self.closure.deref().clone()), } } } +// HACK(eddyb) manual impl avoids `Default` bound on `T`. +impl<T: Eq + Hash> Default for TransitiveRelationBuilder<T> { + fn default() -> Self { + TransitiveRelationBuilder { elements: Default::default(), edges: Default::default() } + } +} + #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Debug)] struct Index(usize); @@ -49,7 +61,7 @@ struct Edge { target: Index, } -impl<T: Eq + Hash + Copy> TransitiveRelation<T> { +impl<T: Eq + Hash + Copy> TransitiveRelationBuilder<T> { pub fn is_empty(&self) -> bool { self.edges.is_empty() } @@ -63,23 +75,19 @@ impl<T: Eq + Hash + Copy> TransitiveRelation<T> { } fn add_index(&mut self, a: T) -> Index { - let (index, added) = self.elements.insert_full(a); - if added { - // if we changed the dimensions, clear the cache - *self.closure.get_mut() = None; - } + let (index, _added) = self.elements.insert_full(a); Index(index) } /// Applies the (partial) function to each edge and returns a new - /// relation. If `f` returns `None` for any end-point, returns - /// `None`. - pub fn maybe_map<F, U>(&self, mut f: F) -> Option<TransitiveRelation<U>> + /// relation builder. If `f` returns `None` for any end-point, + /// returns `None`. + pub fn maybe_map<F, U>(&self, mut f: F) -> Option<TransitiveRelationBuilder<U>> where F: FnMut(T) -> Option<U>, U: Clone + Debug + Eq + Hash + Copy, { - let mut result = TransitiveRelation::default(); + let mut result = TransitiveRelationBuilder::default(); for edge in &self.edges { result.add(f(self.elements[edge.source.0])?, f(self.elements[edge.target.0])?); } @@ -93,10 +101,38 @@ impl<T: Eq + Hash + Copy> TransitiveRelation<T> { let edge = Edge { source: a, target: b }; if !self.edges.contains(&edge) { self.edges.push(edge); + } + } + + /// Compute the transitive closure derived from the edges, and converted to + /// the final result. After this, all elements will be immutable to maintain + /// the correctness of the result. + pub fn freeze(self) -> TransitiveRelation<T> { + let mut matrix = BitMatrix::new(self.elements.len(), self.elements.len()); + let mut changed = true; + while changed { + changed = false; + for edge in &self.edges { + // add an edge from S -> T + changed |= matrix.insert(edge.source.0, edge.target.0); - // added an edge, clear the cache - *self.closure.get_mut() = None; + // add all outgoing edges from T into S + changed |= matrix.union_rows(edge.target.0, edge.source.0); + } } + TransitiveRelation { builder: Frozen::freeze(self), closure: Frozen::freeze(matrix) } + } +} + +impl<T: Eq + Hash + Copy> TransitiveRelation<T> { + /// Applies the (partial) function to each edge and returns a new + /// relation including transitive closures. + pub fn maybe_map<F, U>(&self, f: F) -> Option<TransitiveRelation<U>> + where + F: FnMut(T) -> Option<U>, + U: Clone + Debug + Eq + Hash + Copy, + { + Some(self.builder.maybe_map(f)?.freeze()) } /// Checks whether `a < target` (transitively) @@ -322,30 +358,7 @@ impl<T: Eq + Hash + Copy> TransitiveRelation<T> { where OP: FnOnce(&BitMatrix<usize, usize>) -> R, { - let mut closure_cell = self.closure.borrow_mut(); - let mut closure = closure_cell.take(); - if closure.is_none() { - closure = Some(self.compute_closure()); - } - let result = op(closure.as_ref().unwrap()); - *closure_cell = closure; - result - } - - fn compute_closure(&self) -> BitMatrix<usize, usize> { - let mut matrix = BitMatrix::new(self.elements.len(), self.elements.len()); - let mut changed = true; - while changed { - changed = false; - for edge in &self.edges { - // add an edge from S -> T - changed |= matrix.insert(edge.source.0, edge.target.0); - - // add all outgoing edges from T into S - changed |= matrix.union_rows(edge.target.0, edge.source.0); - } - } - matrix + op(&self.closure) } /// Lists all the base edges in the graph: the initial _non-transitive_ set of element diff --git a/compiler/rustc_data_structures/src/transitive_relation/tests.rs b/compiler/rustc_data_structures/src/transitive_relation/tests.rs index e1f4c7ee073..e756c546e41 100644 --- a/compiler/rustc_data_structures/src/transitive_relation/tests.rs +++ b/compiler/rustc_data_structures/src/transitive_relation/tests.rs @@ -10,9 +10,10 @@ impl<T: Eq + Hash + Copy> TransitiveRelation<T> { #[test] fn test_one_step() { - let mut relation = TransitiveRelation::default(); + let mut relation = TransitiveRelationBuilder::default(); relation.add("a", "b"); relation.add("a", "c"); + let relation = relation.freeze(); assert!(relation.contains("a", "c")); assert!(relation.contains("a", "b")); assert!(!relation.contains("b", "a")); @@ -21,7 +22,7 @@ fn test_one_step() { #[test] fn test_many_steps() { - let mut relation = TransitiveRelation::default(); + let mut relation = TransitiveRelationBuilder::default(); relation.add("a", "b"); relation.add("a", "c"); relation.add("a", "f"); @@ -31,6 +32,7 @@ fn test_many_steps() { relation.add("b", "e"); relation.add("e", "g"); + let relation = relation.freeze(); assert!(relation.contains("a", "b")); assert!(relation.contains("a", "c")); @@ -51,9 +53,10 @@ fn mubs_triangle() { // ^ // | // b - let mut relation = TransitiveRelation::default(); + let mut relation = TransitiveRelationBuilder::default(); relation.add("a", "tcx"); relation.add("b", "tcx"); + let relation = relation.freeze(); assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["tcx"]); assert_eq!(relation.parents("a"), vec!["tcx"]); assert_eq!(relation.parents("b"), vec!["tcx"]); @@ -72,7 +75,7 @@ fn mubs_best_choice1() { // need the second pare down call to get the right result (after // intersection, we have [1, 2], but 2 -> 1). - let mut relation = TransitiveRelation::default(); + let mut relation = TransitiveRelationBuilder::default(); relation.add("0", "1"); relation.add("0", "2"); @@ -80,6 +83,7 @@ fn mubs_best_choice1() { relation.add("3", "1"); relation.add("3", "2"); + let relation = relation.freeze(); assert_eq!(relation.minimal_upper_bounds("0", "3"), vec!["2"]); assert_eq!(relation.parents("0"), vec!["2"]); @@ -99,7 +103,7 @@ fn mubs_best_choice2() { // Like the preceding test, but in this case intersection is [2, // 1], and hence we rely on the first pare down call. - let mut relation = TransitiveRelation::default(); + let mut relation = TransitiveRelationBuilder::default(); relation.add("0", "1"); relation.add("0", "2"); @@ -107,6 +111,7 @@ fn mubs_best_choice2() { relation.add("3", "1"); relation.add("3", "2"); + let relation = relation.freeze(); assert_eq!(relation.minimal_upper_bounds("0", "3"), vec!["1"]); assert_eq!(relation.parents("0"), vec!["1"]); @@ -118,12 +123,13 @@ fn mubs_best_choice2() { fn mubs_no_best_choice() { // in this case, the intersection yields [1, 2], and the "pare // down" calls find nothing to remove. - let mut relation = TransitiveRelation::default(); + let mut relation = TransitiveRelationBuilder::default(); relation.add("0", "1"); relation.add("0", "2"); relation.add("3", "1"); relation.add("3", "2"); + let relation = relation.freeze(); assert_eq!(relation.minimal_upper_bounds("0", "3"), vec!["1", "2"]); assert_eq!(relation.parents("0"), vec!["1", "2"]); @@ -135,7 +141,7 @@ fn mubs_best_choice_scc() { // in this case, 1 and 2 form a cycle; we pick arbitrarily (but // consistently). - let mut relation = TransitiveRelation::default(); + let mut relation = TransitiveRelationBuilder::default(); relation.add("0", "1"); relation.add("0", "2"); @@ -144,6 +150,7 @@ fn mubs_best_choice_scc() { relation.add("3", "1"); relation.add("3", "2"); + let relation = relation.freeze(); assert_eq!(relation.minimal_upper_bounds("0", "3"), vec!["1"]); assert_eq!(relation.parents("0"), vec!["1"]); @@ -157,13 +164,14 @@ fn pdub_crisscross() { // /\ | // b -> b1 ---+ - let mut relation = TransitiveRelation::default(); + let mut relation = TransitiveRelationBuilder::default(); relation.add("a", "a1"); relation.add("a", "b1"); relation.add("b", "a1"); relation.add("b", "b1"); relation.add("a1", "x"); relation.add("b1", "x"); + let relation = relation.freeze(); assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["a1", "b1"]); assert_eq!(relation.postdom_upper_bound("a", "b"), Some("x")); @@ -179,7 +187,7 @@ fn pdub_crisscross_more() { // /\ /\ | // b -> b1 -> b2 ---------+ - let mut relation = TransitiveRelation::default(); + let mut relation = TransitiveRelationBuilder::default(); relation.add("a", "a1"); relation.add("a", "b1"); relation.add("b", "a1"); @@ -194,6 +202,7 @@ fn pdub_crisscross_more() { relation.add("a3", "x"); relation.add("b2", "x"); + let relation = relation.freeze(); assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["a1", "b1"]); assert_eq!(relation.minimal_upper_bounds("a1", "b1"), vec!["a2", "b2"]); @@ -210,11 +219,12 @@ fn pdub_lub() { // | // b -> b1 ---+ - let mut relation = TransitiveRelation::default(); + let mut relation = TransitiveRelationBuilder::default(); relation.add("a", "a1"); relation.add("b", "b1"); relation.add("a1", "x"); relation.add("b1", "x"); + let relation = relation.freeze(); assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["x"]); assert_eq!(relation.postdom_upper_bound("a", "b"), Some("x")); @@ -233,10 +243,11 @@ fn mubs_intermediate_node_on_one_side_only() { // b // "digraph { a -> c -> d; b -> d; }", - let mut relation = TransitiveRelation::default(); + let mut relation = TransitiveRelationBuilder::default(); relation.add("a", "c"); relation.add("c", "d"); relation.add("b", "d"); + let relation = relation.freeze(); assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["d"]); } @@ -252,12 +263,13 @@ fn mubs_scc_1() { // b // "digraph { a -> c -> d; d -> c; a -> d; b -> d; }", - let mut relation = TransitiveRelation::default(); + let mut relation = TransitiveRelationBuilder::default(); relation.add("a", "c"); relation.add("c", "d"); relation.add("d", "c"); relation.add("a", "d"); relation.add("b", "d"); + let relation = relation.freeze(); assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["c"]); } @@ -272,12 +284,13 @@ fn mubs_scc_2() { // +--- b // "digraph { a -> c -> d; d -> c; b -> d; b -> c; }", - let mut relation = TransitiveRelation::default(); + let mut relation = TransitiveRelationBuilder::default(); relation.add("a", "c"); relation.add("c", "d"); relation.add("d", "c"); relation.add("b", "d"); relation.add("b", "c"); + let relation = relation.freeze(); assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["c"]); } @@ -292,13 +305,14 @@ fn mubs_scc_3() { // b ---+ // "digraph { a -> c -> d -> e -> c; b -> d; b -> e; }", - let mut relation = TransitiveRelation::default(); + let mut relation = TransitiveRelationBuilder::default(); relation.add("a", "c"); relation.add("c", "d"); relation.add("d", "e"); relation.add("e", "c"); relation.add("b", "d"); relation.add("b", "e"); + let relation = relation.freeze(); assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["c"]); } @@ -314,13 +328,14 @@ fn mubs_scc_4() { // b ---+ // "digraph { a -> c -> d -> e -> c; a -> d; b -> e; }" - let mut relation = TransitiveRelation::default(); + let mut relation = TransitiveRelationBuilder::default(); relation.add("a", "c"); relation.add("c", "d"); relation.add("d", "e"); relation.add("e", "c"); relation.add("a", "d"); relation.add("b", "e"); + let relation = relation.freeze(); assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["c"]); } @@ -352,10 +367,11 @@ fn parent() { (1, /*->*/ 3), ]; - let mut relation = TransitiveRelation::default(); + let mut relation = TransitiveRelationBuilder::default(); for (a, b) in pairs { relation.add(a, b); } + let relation = relation.freeze(); let p = relation.postdom_parent(3); assert_eq!(p, Some(0)); |