-// 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 bit_set::BitMatrix;
-use fx::FxHashMap;
-use sync::Lock;
+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 stable_hasher::{HashStable, StableHasher, StableHasherResult};
use std::fmt::Debug;
use std::hash::Hash;
use std::mem;
closure: Lock<Option<BitMatrix<usize, usize>>>,
}
+// HACK(eddyb) manual impl avoids `Default` bound on `T`.
+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);
target: Index,
}
-impl<T: Clone + Debug + Eq + Hash> Default for TransitiveRelation<T> {
- fn default() -> TransitiveRelation<T> {
- TransitiveRelation {
- elements: vec![],
- map: FxHashMap::default(),
- edges: vec![],
- closure: Lock::new(None),
- }
- }
-}
-
impl<T: Clone + Debug + Eq + Hash> TransitiveRelation<T> {
pub fn is_empty(&self) -> bool {
self.edges.is_empty()
}
/// Applies the (partial) function to each edge and returns a new
- /// relation. If `f` returns `None` for any end-point, returns
+ /// relation. If `f` returns `None` for any end-point, returns
/// `None`.
pub fn maybe_map<F, U>(&self, mut f: F) -> Option<TransitiveRelation<U>>
where F: FnMut(&T) -> Option<U>,
}
}
- /// Check whether `a < target` (transitively)
+ /// Checks 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)),
/// Thinking of `x R y` as an edge `x -> y` in a graph, this
/// returns all things reachable from `a`.
///
- /// Really this probably ought to be `impl Iterator<Item=&T>`, but
+ /// Really this probably ought to be `impl Iterator<Item = &T>`, but
/// I'm too lazy to make that work, and -- given the caching
/// strategy -- it'd be a touch tricky anyhow.
pub fn reachable_from(&self, a: &T) -> Vec<&T> {
/// the query is `postdom_upper_bound(a, b)`:
///
/// ```text
- /// // returns Some(x), which is also LUB
+ /// // 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
+ /// // Returns `Some(x)`, which is not LUB (there is none)
+ /// // diagonal edges run left-to-right.
/// a -> a1 -> x
/// \/ ^
/// /\ |
/// b -> b1 ---+
///
- /// // returns None
+ /// // Returns `None`.
/// a -> a1
/// b -> b1
/// ```
///
/// The intuition is that this moves "one step up" through a lattice
/// (where the relation is encoding the `<=` relation for the lattice).
- /// So e.g. if the relation is `->` and we have
+ /// So e.g., if the relation is `->` and we have
///
/// ```
/// a -> b -> d -> f