transitive_relation.rs

// 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 bitvec::BitMatrix;
use std::cell::RefCell;
use std::fmt::Debug;
use std::mem;

#[derive(Clone)]
pub struct TransitiveRelation<T:Debug+PartialEq> {
    // List of elements. This is used to map from a T to a usize.  We
    // expect domain to be small so just use a linear list versus a
    // hashmap or something.
    elements: Vec<T>,

    // List of base edges in the graph. Require to compute transitive
    // closure.
    edges: Vec<Edge>,

    // This is a cached transitive closure derived from the edges.
    // Currently, we build it lazilly and just throw out any existing
    // copy whenever a new edge is added. (The RefCell 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: RefCell<Option<BitMatrix>>
}

#[derive(Clone, PartialEq, PartialOrd)]
struct Index(usize);

#[derive(Clone, PartialEq)]
struct Edge {
    source: Index,
    target: Index,
}

impl<T:Debug+PartialEq> TransitiveRelation<T> {
    pub fn new() -> TransitiveRelation<T> {
        TransitiveRelation { elements: vec![],
                             edges: vec![],
                             closure: RefCell::new(None) }
    }

    fn index(&self, a: &T) -> Option<Index> {
        self.elements.iter().position(|e| *e == *a).map(Index)
    }

    fn add_index(&mut self, a: T) -> Index {
        match self.index(&a) {
            Some(i) => i,
            None => {
                self.elements.push(a);

                // if we changed the dimensions, clear the cache
                *self.closure.borrow_mut() = None;

                Index(self.elements.len() - 1)
            }
        }
    }

    /// Indicate that `a < b` (where `<` is this relation)
    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);

            // added an edge, clear the cache
            *self.closure.borrow_mut() = None;
        }
    }

    /// Check whether `a < target` (transitively)
    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,
        }
    }

    /// Picks what I am referring to as the "best" upper-bound for `a`
    /// and `b`. This is usually the least upper bound, but in cases where
    /// there is no single least upper bound, it is the "mutual immediate postdominator",
    /// if you imagine a graph where `a < b` means `a -> b`.
    ///
    /// This function is needed because region inference currently
    /// requires that we produce a single "UB", and there is no best
    /// choice for the LUB. Rather than pick arbitrarily, I pick a
    /// less good, but predictable choice. This should help ensure
    /// that region inference yields predictable results (though it
    /// itself is not fully sufficient).
    ///
    /// Examples are probably clearer than any prose I could write
    /// (there are corresponding tests below, btw). In each case,
    /// the query is `best_upper_bound(a, b)`:
    ///
    /// ```
    /// // returns Some(x), which is also LUB
    /// a -> a1 -> x
    ///            ^
    ///            |
    /// b -> b1 ---+
    ///
    /// // returns Some(x), which is not LUB (there is none)
    /// // diagonal edges run left-to-right
    /// a -> a1 -> x
    ///   \/       ^
    ///   /\       |
    /// b -> b1 ---+
    ///
    /// // returns None
    /// a -> a1
    /// b -> b1
    /// ```
    pub fn best_upper_bound(&self, a: &T, b: &T) -> Option<&T> {
        let mut mubs = self.minimal_upper_bounds(a, b);
        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));
                }
            }
        }
    }

    /// Returns the set of bounds `X` such that:
    ///
    /// - `a < X` and `b < X`
    /// - there is no `Y != X` such that `a < Y` and `Y < X`
    ///   - except for the case where `X < a` (i.e., a strongly connected
    ///     component in the graph). In that case, the smallest
    ///     representative of the SCC is returned (as determined by the
    ///     internal indices).
    ///
    /// Note that this set can, in principle, have any size.
    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![]; }
        };

        // in some cases, there are some arbitrary choices to be made;
        // it doesn't really matter what we pick, as long as we pick
        // the same thing consistently when queried, so ensure that
        // (a, b) are in a consistent relative order
        if a > b {
            mem::swap(&mut a, &mut b);
        }

        let lub_indices = self.with_closure(|closure| {
            // Easy case is when either a < b or b < a:
            if closure.contains(a.0, b.0) {
                return vec![b.0];
            }
            if closure.contains(b.0, a.0) {
                return vec![a.0];
            }

            // Otherwise, the tricky part is that there may be some c
            // where a < c and b < c. In fact, there may be many such
            // values. So here is what we do:
            //
            // 1. Find the vector `[X | a < X && b < X]` of all values
            //    `X` where `a < X` and `b < X`.  In terms of the
            //    graph, this means all values reachable from both `a`
            //    and `b`. Note that this vector is also a set, but we
            //    use the term vector because the order matters
            //    to the steps below.
            //    - This vector contains upper bounds, but they are
            //      not minimal upper bounds. So you may have e.g.
            //      `[x, y, tcx, z]` where `x < tcx` and `y < tcx` and
            //      `z < x` and `z < y`:
            //
            //           z --+---> x ----+----> tcx
            //               |           |
            //               |           |
            //               +---> y ----+
            //
            //      In this case, we really want to return just `[z]`.
            //      The following steps below achieve this by gradually
            //      reducing the list.
            // 2. Pare down the vector using `pare_down`. This will
            //    remove elements from the vector that can be reached
            //    by an earlier element.
            //    - In the example above, this would convert `[x, y,
            //      tcx, z]` to `[x, y, z]`. Note that `x` and `y` are
            //      still in the vector; this is because while `z < x`
            //      (and `z < y`) holds, `z` comes after them in the
            //      vector.
            // 3. Reverse the vector and repeat the pare down process.
            //    - In the example above, we would reverse to
            //      `[z, y, x]` and then pare down to `[z]`.
            // 4. Reverse once more just so that we yield a vector in
            //    increasing order of index. Maybe this is silly.
            //
            // I believe this algorithm yields a minimal set. The
            // argument is that, after step 2, we know that no element
            // can reach its successors (in the vector, not the graph).
            // After step 3, we know that no element can reach any of
            // its predecesssors (because of step 2) nor successors
            // (because we just called `pare_down`)

            let mut candidates = closure.intersection(a.0, b.0); // (1)
            pare_down(&mut candidates, closure); // (2)
            candidates.reverse(); // (3a)
            pare_down(&mut candidates, closure); // (3b)
            candidates.reverse(); // (4)
            candidates
        });

        lub_indices.into_iter()
                   .map(|i| &self.elements[i])
                   .collect()
    }

    fn with_closure<OP,R>(&self, op: OP) -> R
        where OP: FnOnce(&BitMatrix) -> 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 {
        let mut matrix = BitMatrix::new(self.elements.len());
        let mut changed = true;
        while changed {
            changed = false;
            for edge in self.edges.iter() {
                // add an edge from S -> T
                changed |= matrix.add(edge.source.0, edge.target.0);

                // add all outgoing edges from T into S
                changed |= matrix.merge(edge.target.0, edge.source.0);
            }
        }
        matrix
    }
}

/// Pare down is used as a step in the LUB computation. It edits the
/// candidates array in place by removing any element j for which
/// there exists an earlier element i<j such that i -> j. That is,
/// after you run `pare_down`, you know that for all elements that
/// remain in candidates, they cannot reach any of the elements that
/// come after them.
///
/// Examples follow. Assume that a -> b -> c and x -> y -> z.
///
/// - Input: `[a, b, x]`. Output: `[a, x]`.
/// - Input: `[b, a, x]`. Output: `[b, a, x]`.
/// - Input: `[a, x, b, y]`. Output: `[a, x]`.
fn pare_down(candidates: &mut Vec<usize>, closure: &BitMatrix) {
    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) {
                // If `i` can reach `j`, then we can remove `j`. So just
                // mark it as dead and move on; subsequent indices will be
                // shifted into its place.
                dead += 1;
            } else {
                candidates[j - dead] = candidate_j;
            }
            j += 1;
        }
        candidates.truncate(j - dead);
    }
}

#[test]
fn test_one_step() {
    let mut relation = TransitiveRelation::new();
    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::new();
    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_triange() {
    let mut relation = TransitiveRelation::new();
    relation.add("a", "tcx");
    relation.add("b", "tcx");
    assert_eq!(relation.minimal_upper_bounds(&"a", &"b"), vec![&"tcx"]);
}

#[test]
fn mubs_best_choice1() {
    // 0 -> 1 <- 3
    // |    ^    |
    // |    |    |
    // +--> 2 <--+
    //
    // mubs(0,3) = [1]

    // This tests a particular state in the algorithm, in which we
    // need the second pare down call to get the right result (after
    // intersection, we have [1, 2], but 2 -> 1).

    let mut relation = TransitiveRelation::new();
    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"]);
}

#[test]
fn mubs_best_choice2() {
    // 0 -> 1 <- 3
    // |    |    |
    // |    v    |
    // +--> 2 <--+
    //
    // mubs(0,3) = [2]

    // Like the precedecing test, but in this case intersection is [2,
    // 1], and hence we rely on the first pare down call.

    let mut relation = TransitiveRelation::new();
    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"]);
}

#[test]
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::new();
    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"]);
}

#[test]
fn mubs_best_choice_scc() {
    let mut relation = TransitiveRelation::new();
    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"]);
}

#[test]
fn bub_crisscross() {
    // diagonal edges run left-to-right
    // a -> a1 -> x
    //   \/       ^
    //   /\       |
    // b -> b1 ---+

    let mut relation = TransitiveRelation::new();
    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.best_upper_bound(&"a", &"b"), Some(&"x"));
}

#[test]
fn bub_crisscross_more() {
    // diagonal edges run left-to-right
    // a -> a1 -> a2 -> a3 -> x
    //   \/    \/             ^
    //   /\    /\             |
    // b -> b1 -> b2 ---------+

    let mut relation = TransitiveRelation::new();
    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.best_upper_bound(&"a", &"b"), Some(&"x"));
}

#[test]
fn bub_lub() {
    // a -> a1 -> x
    //            ^
    //            |
    // b -> b1 ---+

    let mut relation = TransitiveRelation::new();
    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.best_upper_bound(&"a", &"b"), Some(&"x"));
}

#[test]
fn mubs_intermediate_node_on_one_side_only() {
    // a -> c -> d
    //           ^
    //           |
    //           b

    // "digraph { a -> c -> d; b -> d; }",
    let mut relation = TransitiveRelation::new();
    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() {
    // +-------------+
    // |    +----+   |
    // |    v    |   |
    // a -> c -> d <-+
    //           ^
    //           |
    //           b

    // "digraph { a -> c -> d; d -> c; a -> d; b -> d; }",
    let mut relation = TransitiveRelation::new();
    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() {
    //      +----+
    //      v    |
    // a -> c -> d
    //      ^    ^
    //      |    |
    //      +--- b

    // "digraph { a -> c -> d; d -> c; b -> d; b -> c; }",
    let mut relation = TransitiveRelation::new();
    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() {
    //      +---------+
    //      v         |
    // a -> c -> d -> e
    //           ^    ^
    //           |    |
    //           b ---+

    // "digraph { a -> c -> d -> e -> c; b -> d; b -> e; }",
    let mut relation = TransitiveRelation::new();
    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() {
    //      +---------+
    //      v         |
    // a -> c -> d -> e
    // |         ^    ^
    // +---------+    |
    //                |
    //           b ---+

    // "digraph { a -> c -> d -> e -> c; a -> d; b -> e; }"
    let mut relation = TransitiveRelation::new();
    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"]);
}