use crate::bit_set::BitMatrix;
use crate::fx::FxHashMap;
use crate::stable_hasher::{HashStable, StableHasher, StableHasherResult};
use crate::sync::Lock;
use rustc_serialize::{Encodable, Encoder, Decodable, Decoder};
use std::fmt::Debug;
use std::hash::Hash;
use std::mem;
#[derive(Clone, Debug)]
pub struct TransitiveRelation<T: Clone + Debug + Eq + Hash> {
elements: Vec<T>,
map: FxHashMap<T, Index>,
edges: Vec<Edge>,
closure: Lock<Option<BitMatrix<usize, usize>>>,
}
impl<T: Clone + Debug + Eq + Hash> Default for TransitiveRelation<T> {
fn default() -> Self {
TransitiveRelation {
elements: Default::default(),
map: Default::default(),
edges: Default::default(),
closure: Default::default(),
}
}
}
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, RustcEncodable, RustcDecodable, Debug)]
struct Index(usize);
#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Debug)]
struct Edge {
source: Index,
target: Index,
}
impl<T: Clone + Debug + Eq + Hash> TransitiveRelation<T> {
pub fn is_empty(&self) -> bool {
self.edges.is_empty()
}
fn index(&self, a: &T) -> Option<Index> {
self.map.get(a).cloned()
}
fn add_index(&mut self, a: T) -> Index {
let &mut TransitiveRelation {
ref mut elements,
ref mut closure,
ref mut map,
..
} = self;
*map.entry(a.clone())
.or_insert_with(|| {
elements.push(a);
*closure.get_mut() = None;
Index(elements.len() - 1)
})
}
pub fn maybe_map<F, U>(&self, mut f: F) -> Option<TransitiveRelation<U>>
where F: FnMut(&T) -> Option<U>,
U: Clone + Debug + Eq + Hash + Clone,
{
let mut result = TransitiveRelation::default();
for edge in &self.edges {
result.add(f(&self.elements[edge.source.0])?, f(&self.elements[edge.target.0])?);
}
Some(result)
}
pub fn add(&mut self, a: T, b: T) {
let a = self.add_index(a);
let b = self.add_index(b);
let edge = Edge {
source: a,
target: b,
};
if !self.edges.contains(&edge) {
self.edges.push(edge);
*self.closure.get_mut() = None;
}
}
pub fn contains(&self, a: &T, b: &T) -> bool {
match (self.index(a), self.index(b)) {
(Some(a), Some(b)) => self.with_closure(|closure| closure.contains(a.0, b.0)),
(None, _) | (_, None) => false,
}
}
pub fn reachable_from(&self, a: &T) -> Vec<&T> {
match self.index(a) {
Some(a) => self.with_closure(|closure| {
closure.iter(a.0).map(|i| &self.elements[i]).collect()
}),
None => vec![],
}
}
pub fn postdom_upper_bound(&self, a: &T, b: &T) -> Option<&T> {
let mubs = self.minimal_upper_bounds(a, b);
self.mutual_immediate_postdominator(mubs)
}
pub fn mutual_immediate_postdominator<'a>(&'a self, mut mubs: Vec<&'a T>) -> Option<&'a T> {
loop {
match mubs.len() {
0 => return None,
1 => return Some(mubs[0]),
_ => {
let m = mubs.pop().unwrap();
let n = mubs.pop().unwrap();
mubs.extend(self.minimal_upper_bounds(n, m));
}
}
}
}
pub fn minimal_upper_bounds(&self, a: &T, b: &T) -> Vec<&T> {
let (mut a, mut b) = match (self.index(a), self.index(b)) {
(Some(a), Some(b)) => (a, b),
(None, _) | (_, None) => {
return vec![];
}
};
if a > b {
mem::swap(&mut a, &mut b);
}
let lub_indices = self.with_closure(|closure| {
if closure.contains(a.0, b.0) {
return vec![b.0];
}
if closure.contains(b.0, a.0) {
return vec![a.0];
}
let mut candidates = closure.intersect_rows(a.0, b.0);
pare_down(&mut candidates, closure);
candidates.reverse();
pare_down(&mut candidates, closure);
candidates
});
lub_indices.into_iter()
.rev()
.map(|i| &self.elements[i])
.collect()
}
pub fn parents(&self, a: &T) -> Vec<&T> {
let a = match self.index(a) {
Some(a) => a,
None => return vec![]
};
let ancestors = self.with_closure(|closure| {
let mut ancestors = closure.intersect_rows(a.0, a.0);
ancestors.retain(|&e| !closure.contains(e, a.0));
pare_down(&mut ancestors, closure);
ancestors.reverse();
pare_down(&mut ancestors, closure);
ancestors
});
ancestors.into_iter()
.rev()
.map(|i| &self.elements[i])
.collect()
}
pub fn postdom_parent(&self, a: &T) -> Option<&T> {
self.mutual_immediate_postdominator(self.parents(a))
}
fn with_closure<OP, R>(&self, op: OP) -> R
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 {
changed |= matrix.insert(edge.source.0, edge.target.0);
changed |= matrix.union_rows(edge.target.0, edge.source.0);
}
}
matrix
}
}
fn pare_down(candidates: &mut Vec<usize>, closure: &BitMatrix<usize, usize>) {
let mut i = 0;
while i < candidates.len() {
let candidate_i = candidates[i];
i += 1;
let mut j = i;
let mut dead = 0;
while j < candidates.len() {
let candidate_j = candidates[j];
if closure.contains(candidate_i, candidate_j) {
dead += 1;
} else {
candidates[j - dead] = candidate_j;
}
j += 1;
}
candidates.truncate(j - dead);
}
}
impl<T> Encodable for TransitiveRelation<T>
where T: Clone + Encodable + Debug + Eq + Hash + Clone
{
fn encode<E: Encoder>(&self, s: &mut E) -> Result<(), E::Error> {
s.emit_struct("TransitiveRelation", 2, |s| {
s.emit_struct_field("elements", 0, |s| self.elements.encode(s))?;
s.emit_struct_field("edges", 1, |s| self.edges.encode(s))?;
Ok(())
})
}
}
impl<T> Decodable for TransitiveRelation<T>
where T: Clone + Decodable + Debug + Eq + Hash + Clone
{
fn decode<D: Decoder>(d: &mut D) -> Result<Self, D::Error> {
d.read_struct("TransitiveRelation", 2, |d| {
let elements: Vec<T> = d.read_struct_field("elements", 0, |d| Decodable::decode(d))?;
let edges = d.read_struct_field("edges", 1, |d| Decodable::decode(d))?;
let map = elements.iter()
.enumerate()
.map(|(index, elem)| (elem.clone(), Index(index)))
.collect();
Ok(TransitiveRelation { elements, edges, map, closure: Lock::new(None) })
})
}
}
impl<CTX, T> HashStable<CTX> for TransitiveRelation<T>
where T: HashStable<CTX> + Eq + Debug + Clone + Hash
{
fn hash_stable<W: StableHasherResult>(&self,
hcx: &mut CTX,
hasher: &mut StableHasher<W>) {
let TransitiveRelation {
ref elements,
ref edges,
map: _,
closure: _
} = *self;
elements.hash_stable(hcx, hasher);
edges.hash_stable(hcx, hasher);
}
}
impl<CTX> HashStable<CTX> for Edge {
fn hash_stable<W: StableHasherResult>(&self,
hcx: &mut CTX,
hasher: &mut StableHasher<W>) {
let Edge {
ref source,
ref target,
} = *self;
source.hash_stable(hcx, hasher);
target.hash_stable(hcx, hasher);
}
}
impl<CTX> HashStable<CTX> for Index {
fn hash_stable<W: StableHasherResult>(&self,
hcx: &mut CTX,
hasher: &mut StableHasher<W>) {
let Index(idx) = *self;
idx.hash_stable(hcx, hasher);
}
}
#[test]
fn test_one_step() {
let mut relation = TransitiveRelation::default();
relation.add("a", "b");
relation.add("a", "c");
assert!(relation.contains(&"a", &"c"));
assert!(relation.contains(&"a", &"b"));
assert!(!relation.contains(&"b", &"a"));
assert!(!relation.contains(&"a", &"d"));
}
#[test]
fn test_many_steps() {
let mut relation = TransitiveRelation::default();
relation.add("a", "b");
relation.add("a", "c");
relation.add("a", "f");
relation.add("b", "c");
relation.add("b", "d");
relation.add("b", "e");
relation.add("e", "g");
assert!(relation.contains(&"a", &"b"));
assert!(relation.contains(&"a", &"c"));
assert!(relation.contains(&"a", &"d"));
assert!(relation.contains(&"a", &"e"));
assert!(relation.contains(&"a", &"f"));
assert!(relation.contains(&"a", &"g"));
assert!(relation.contains(&"b", &"g"));
assert!(!relation.contains(&"a", &"x"));
assert!(!relation.contains(&"b", &"f"));
}
#[test]
fn mubs_triangle() {
let mut relation = TransitiveRelation::default();
relation.add("a", "tcx");
relation.add("b", "tcx");
assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"tcx"]);
assert_eq!(relation.parents(&"a"), vec![&"tcx"]);
assert_eq!(relation.parents(&"b"), vec![&"tcx"]);
}
#[test]
fn mubs_best_choice1() {
let mut relation = TransitiveRelation::default();
relation.add("0", "1");
relation.add("0", "2");
relation.add("2", "1");
relation.add("3", "1");
relation.add("3", "2");
assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"2"]);
assert_eq!(relation.parents(&"0"), vec![&"2"]);
assert_eq!(relation.parents(&"2"), vec![&"1"]);
assert!(relation.parents(&"1").is_empty());
}
#[test]
fn mubs_best_choice2() {
let mut relation = TransitiveRelation::default();
relation.add("0", "1");
relation.add("0", "2");
relation.add("1", "2");
relation.add("3", "1");
relation.add("3", "2");
assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1"]);
assert_eq!(relation.parents(&"0"), vec![&"1"]);
assert_eq!(relation.parents(&"1"), vec![&"2"]);
assert!(relation.parents(&"2").is_empty());
}
#[test]
fn mubs_no_best_choice() {
let mut relation = TransitiveRelation::default();
relation.add("0", "1");
relation.add("0", "2");
relation.add("3", "1");
relation.add("3", "2");
assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1", &"2"]);
assert_eq!(relation.parents(&"0"), vec![&"1", &"2"]);
assert_eq!(relation.parents(&"3"), vec![&"1", &"2"]);
}
#[test]
fn mubs_best_choice_scc() {
let mut relation = TransitiveRelation::default();
relation.add("0", "1");
relation.add("0", "2");
relation.add("1", "2");
relation.add("2", "1");
relation.add("3", "1");
relation.add("3", "2");
assert_eq!(relation.minimal_upper_bounds(&"0", &"3"), vec![&"1"]);
assert_eq!(relation.parents(&"0"), vec![&"1"]);
}
#[test]
fn pdub_crisscross() {
let mut relation = TransitiveRelation::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");
assert_eq!(relation.minimal_upper_bounds(&"a", &"b"),
vec![&"a1", &"b1"]);
assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
assert_eq!(relation.postdom_parent(&"a"), Some(&"x"));
assert_eq!(relation.postdom_parent(&"b"), Some(&"x"));
}
#[test]
fn pdub_crisscross_more() {
let mut relation = TransitiveRelation::default();
relation.add("a", "a1");
relation.add("a", "b1");
relation.add("b", "a1");
relation.add("b", "b1");
relation.add("a1", "a2");
relation.add("a1", "b2");
relation.add("b1", "a2");
relation.add("b1", "b2");
relation.add("a2", "a3");
relation.add("a3", "x");
relation.add("b2", "x");
assert_eq!(relation.minimal_upper_bounds(&"a", &"b"),
vec![&"a1", &"b1"]);
assert_eq!(relation.minimal_upper_bounds(&"a1", &"b1"),
vec![&"a2", &"b2"]);
assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
assert_eq!(relation.postdom_parent(&"a"), Some(&"x"));
assert_eq!(relation.postdom_parent(&"b"), Some(&"x"));
}
#[test]
fn pdub_lub() {
let mut relation = TransitiveRelation::default();
relation.add("a", "a1");
relation.add("b", "b1");
relation.add("a1", "x");
relation.add("b1", "x");
assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"x"]);
assert_eq!(relation.postdom_upper_bound(&"a", &"b"), Some(&"x"));
assert_eq!(relation.postdom_parent(&"a"), Some(&"a1"));
assert_eq!(relation.postdom_parent(&"b"), Some(&"b1"));
assert_eq!(relation.postdom_parent(&"a1"), Some(&"x"));
assert_eq!(relation.postdom_parent(&"b1"), Some(&"x"));
}
#[test]
fn mubs_intermediate_node_on_one_side_only() {
let mut relation = TransitiveRelation::default();
relation.add("a", "c");
relation.add("c", "d");
relation.add("b", "d");
assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"d"]);
}
#[test]
fn mubs_scc_1() {
let mut relation = TransitiveRelation::default();
relation.add("a", "c");
relation.add("c", "d");
relation.add("d", "c");
relation.add("a", "d");
relation.add("b", "d");
assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
}
#[test]
fn mubs_scc_2() {
let mut relation = TransitiveRelation::default();
relation.add("a", "c");
relation.add("c", "d");
relation.add("d", "c");
relation.add("b", "d");
relation.add("b", "c");
assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
}
#[test]
fn mubs_scc_3() {
let mut relation = TransitiveRelation::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");
assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
}
#[test]
fn mubs_scc_4() {
let mut relation = TransitiveRelation::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");
assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"c"]);
}
#[test]
fn parent() {
let pairs = vec![
(2, 0),
(2, 2),
(0, 0),
(0, 0),
(1, 0),
(1, 1),
(3, 0),
(3, 3),
(4, 0),
(4, 1),
(1, 3),
];
let mut relation = TransitiveRelation::default();
for (a, b) in pairs {
relation.add(a, b);
}
let p = relation.postdom_parent(&3);
assert_eq!(p, Some(&0));
}