-use rustc_index::bit_set::BitMatrix;
use crate::fx::FxHashMap;
use crate::stable_hasher::{HashStable, StableHasher};
use crate::sync::Lock;
-use rustc_serialize::{Encodable, Encoder, Decodable, Decoder};
+use rustc_index::bit_set::BitMatrix;
+use rustc_serialize::{Decodable, Decoder, Encodable, Encoder};
use std::fmt::Debug;
use std::hash::Hash;
use std::mem;
self.edges.is_empty()
}
- pub fn elements(&self) -> impl Iterator<Item=&T> {
+ pub fn elements(&self) -> impl Iterator<Item = &T> {
self.elements.iter()
}
}
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);
-
- // if we changed the dimensions, clear the cache
- *closure.get_mut() = None;
-
- Index(elements.len() - 1)
- })
+ let &mut TransitiveRelation { ref mut elements, ref mut closure, ref mut map, .. } = self;
+
+ *map.entry(a.clone()).or_insert_with(|| {
+ elements.push(a);
+
+ // if we changed the dimensions, clear the cache
+ *closure.get_mut() = None;
+
+ Index(elements.len() - 1)
+ })
}
/// 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>>
- where F: FnMut(&T) -> Option<U>,
- U: Clone + Debug + Eq + Hash + Clone,
+ where
+ F: FnMut(&T) -> Option<U>,
+ U: Clone + Debug + Eq + Hash + Clone,
{
let mut result = TransitiveRelation::default();
for edge in &self.edges {
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,
- };
+ let edge = Edge { source: a, target: b };
if !self.edges.contains(&edge) {
self.edges.push(edge);
/// strategy -- it'd be a touch tricky anyhow.
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()
- }),
+ Some(a) => {
+ self.with_closure(|closure| closure.iter(a.0).map(|i| &self.elements[i]).collect())
+ }
None => vec![],
}
}
candidates
});
- lub_indices.into_iter()
- .rev() // (4)
- .map(|i| &self.elements[i])
- .collect()
+ lub_indices
+ .into_iter()
+ .rev() // (4)
+ .map(|i| &self.elements[i])
+ .collect()
}
/// Given an element A, returns the maximal set {B} of elements B
pub fn parents(&self, a: &T) -> Vec<&T> {
let a = match self.index(a) {
Some(a) => a,
- None => return vec![]
+ None => return vec![],
};
// Steal the algorithm for `minimal_upper_bounds` above, but
ancestors
});
- ancestors.into_iter()
- .rev() // (4)
- .map(|i| &self.elements[i])
- .collect()
+ ancestors
+ .into_iter()
+ .rev() // (4)
+ .map(|i| &self.elements[i])
+ .collect()
}
/// A "best" parent in some sense. See `parents` and
}
fn with_closure<OP, R>(&self, op: OP) -> R
- where OP: FnOnce(&BitMatrix<usize, usize>) -> R
+ where
+ OP: FnOnce(&BitMatrix<usize, usize>) -> R,
{
let mut closure_cell = self.closure.borrow_mut();
let mut closure = closure_cell.take();
}
fn compute_closure(&self) -> BitMatrix<usize, usize> {
- let mut matrix = BitMatrix::new(self.elements.len(),
- self.elements.len());
+ let mut matrix = BitMatrix::new(self.elements.len(), self.elements.len());
let mut changed = true;
while changed {
changed = false;
/// Lists all the base edges in the graph: the initial _non-transitive_ set of element
/// relations, which will be later used as the basis for the transitive closure computation.
- pub fn base_edges(&self) -> impl Iterator<Item=(&T, &T)> {
+ pub fn base_edges(&self) -> impl Iterator<Item = (&T, &T)> {
self.edges
.iter()
.map(move |edge| (&self.elements[edge.source.0], &self.elements[edge.target.0]))
}
impl<T> Encodable for TransitiveRelation<T>
- where T: Clone + Encodable + Debug + Eq + Hash + Clone
+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| {
}
impl<T> Decodable for TransitiveRelation<T>
- where T: Clone + Decodable + Debug + Eq + Hash + Clone
+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();
+ 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
+where
+ T: HashStable<CTX> + Eq + Debug + Clone + Hash,
{
fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
// We are assuming here that the relation graph has been built in a
// "map" is just a copy of elements vec
map: _,
// "closure" is just a copy of the data above
- closure: _
+ closure: _,
} = *self;
elements.hash_stable(hcx, hasher);
impl<CTX> HashStable<CTX> for Edge {
fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
- let Edge {
- ref source,
- ref target,
- } = *self;
+ let Edge { ref source, ref target } = *self;
source.hash_stable(hcx, hasher);
target.hash_stable(hcx, hasher);
projects / rust.git / blobdiff