|
|
// dagops.rs
|
|
|
//
|
|
|
// Copyright 2019 Georges Racinet <georges.racinet@octobus.net>
|
|
|
//
|
|
|
// This software may be used and distributed according to the terms of the
|
|
|
// GNU General Public License version 2 or any later version.
|
|
|
|
|
|
//! Miscellaneous DAG operations
|
|
|
//!
|
|
|
//! # Terminology
|
|
|
//! - By *relative heads* of a collection of revision numbers (`Revision`), we
|
|
|
//! mean those revisions that have no children among the collection.
|
|
|
//! - Similarly *relative roots* of a collection of `Revision`, we mean those
|
|
|
//! whose parents, if any, don't belong to the collection.
|
|
|
use bitvec::slice::BitSlice;
|
|
|
|
|
|
use super::{Graph, GraphError, Revision, NULL_REVISION};
|
|
|
use crate::{ancestors::AncestorsIterator, BaseRevision};
|
|
|
use std::collections::{BTreeSet, HashSet};
|
|
|
|
|
|
fn remove_parents<S: std::hash::BuildHasher>(
|
|
|
graph: &impl Graph,
|
|
|
rev: Revision,
|
|
|
set: &mut HashSet<Revision, S>,
|
|
|
) -> Result<(), GraphError> {
|
|
|
for parent in graph.parents(rev)?.iter() {
|
|
|
if *parent != NULL_REVISION {
|
|
|
set.remove(parent);
|
|
|
}
|
|
|
}
|
|
|
Ok(())
|
|
|
}
|
|
|
|
|
|
/// Relative heads out of some revisions, passed as an iterator.
|
|
|
///
|
|
|
/// These heads are defined as those revisions that have no children
|
|
|
/// among those emitted by the iterator.
|
|
|
///
|
|
|
/// # Performance notes
|
|
|
/// Internally, this clones the iterator, and builds a `HashSet` out of it.
|
|
|
///
|
|
|
/// This function takes an `Iterator` instead of `impl IntoIterator` to
|
|
|
/// guarantee that cloning the iterator doesn't result in cloning the full
|
|
|
/// construct it comes from.
|
|
|
pub fn heads<'a>(
|
|
|
graph: &impl Graph,
|
|
|
iter_revs: impl Clone + Iterator<Item = &'a Revision>,
|
|
|
) -> Result<HashSet<Revision>, GraphError> {
|
|
|
let mut heads: HashSet<Revision> = iter_revs.clone().cloned().collect();
|
|
|
heads.remove(&NULL_REVISION);
|
|
|
for rev in iter_revs {
|
|
|
if *rev != NULL_REVISION {
|
|
|
remove_parents(graph, *rev, &mut heads)?;
|
|
|
}
|
|
|
}
|
|
|
Ok(heads)
|
|
|
}
|
|
|
|
|
|
/// Retain in `revs` only its relative heads.
|
|
|
///
|
|
|
/// This is an in-place operation, so that control of the incoming
|
|
|
/// set is left to the caller.
|
|
|
/// - a direct Python binding would probably need to build its own `HashSet`
|
|
|
/// from an incoming iterable, even if its sole purpose is to extract the
|
|
|
/// heads.
|
|
|
/// - a Rust caller can decide whether cloning beforehand is appropriate
|
|
|
///
|
|
|
/// # Performance notes
|
|
|
/// Internally, this function will store a full copy of `revs` in a `Vec`.
|
|
|
pub fn retain_heads<S: std::hash::BuildHasher>(
|
|
|
graph: &impl Graph,
|
|
|
revs: &mut HashSet<Revision, S>,
|
|
|
) -> Result<(), GraphError> {
|
|
|
revs.remove(&NULL_REVISION);
|
|
|
// we need to construct an iterable copy of revs to avoid itering while
|
|
|
// mutating
|
|
|
let as_vec: Vec<Revision> = revs.iter().cloned().collect();
|
|
|
for rev in as_vec {
|
|
|
if rev != NULL_REVISION {
|
|
|
remove_parents(graph, rev, revs)?;
|
|
|
}
|
|
|
}
|
|
|
Ok(())
|
|
|
}
|
|
|
|
|
|
/// Optimized version of `retain_heads` that expects an zeroed bitvec of the
|
|
|
/// size of the graph, to act as a faster but less space-efficient `HashSet`.
|
|
|
///
|
|
|
/// # Panics
|
|
|
///
|
|
|
/// Can panic if `not_heads` is shorten than the length of graph.
|
|
|
pub fn retain_heads_fast(
|
|
|
graph: &impl Graph,
|
|
|
not_heads: &mut BitSlice,
|
|
|
filtered_revs: &HashSet<Revision>,
|
|
|
) -> Result<(), GraphError> {
|
|
|
for idx in (0..not_heads.len()).rev() {
|
|
|
let rev = Revision(idx as BaseRevision);
|
|
|
if !not_heads[idx] && filtered_revs.contains(&rev) {
|
|
|
not_heads.get_mut(idx).unwrap().commit(true);
|
|
|
continue;
|
|
|
}
|
|
|
for parent in graph.parents(rev)?.iter() {
|
|
|
if *parent != NULL_REVISION {
|
|
|
not_heads.get_mut(parent.0 as usize).unwrap().commit(true);
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
Ok(())
|
|
|
}
|
|
|
|
|
|
/// Roots of `revs`, passed as a `HashSet`
|
|
|
///
|
|
|
/// They are returned in arbitrary order
|
|
|
pub fn roots<G: Graph, S: std::hash::BuildHasher>(
|
|
|
graph: &G,
|
|
|
revs: &HashSet<Revision, S>,
|
|
|
) -> Result<Vec<Revision>, GraphError> {
|
|
|
let mut roots: Vec<Revision> = Vec::new();
|
|
|
for rev in revs {
|
|
|
if graph
|
|
|
.parents(*rev)?
|
|
|
.iter()
|
|
|
.filter(|p| **p != NULL_REVISION)
|
|
|
.all(|p| !revs.contains(p))
|
|
|
{
|
|
|
roots.push(*rev);
|
|
|
}
|
|
|
}
|
|
|
Ok(roots)
|
|
|
}
|
|
|
|
|
|
/// Compute the topological range between two collections of revisions
|
|
|
///
|
|
|
/// This is equivalent to the revset `<roots>::<heads>`.
|
|
|
///
|
|
|
/// Currently, the given `Graph` has to implement `Clone`, which means
|
|
|
/// actually cloning just a reference-counted Python pointer if
|
|
|
/// it's passed over through `rust-cpython`. This is due to the internal
|
|
|
/// use of `AncestorsIterator`
|
|
|
///
|
|
|
/// # Algorithmic details
|
|
|
///
|
|
|
/// This is a two-pass swipe inspired from what `reachableroots2` from
|
|
|
/// `mercurial.cext.parsers` does to obtain the same results.
|
|
|
///
|
|
|
/// - first, we climb up the DAG from `heads` in topological order, keeping
|
|
|
/// them in the vector `heads_ancestors` vector, and adding any element of
|
|
|
/// `roots` we find among them to the resulting range.
|
|
|
/// - Then, we iterate on that recorded vector so that a revision is always
|
|
|
/// emitted after its parents and add all revisions whose parents are already
|
|
|
/// in the range to the results.
|
|
|
///
|
|
|
/// # Performance notes
|
|
|
///
|
|
|
/// The main difference with the C implementation is that
|
|
|
/// the latter uses a flat array with bit flags, instead of complex structures
|
|
|
/// like `HashSet`, making it faster in most scenarios. In theory, it's
|
|
|
/// possible that the present implementation could be more memory efficient
|
|
|
/// for very large repositories with many branches.
|
|
|
pub fn range(
|
|
|
graph: &(impl Graph + Clone),
|
|
|
roots: impl IntoIterator<Item = Revision>,
|
|
|
heads: impl IntoIterator<Item = Revision>,
|
|
|
) -> Result<BTreeSet<Revision>, GraphError> {
|
|
|
let mut range = BTreeSet::new();
|
|
|
let roots: HashSet<Revision> = roots.into_iter().collect();
|
|
|
let min_root: Revision = match roots.iter().cloned().min() {
|
|
|
None => {
|
|
|
return Ok(range);
|
|
|
}
|
|
|
Some(r) => r,
|
|
|
};
|
|
|
|
|
|
// Internally, AncestorsIterator currently maintains a `HashSet`
|
|
|
// of all seen revision, which is also what we record, albeit in an ordered
|
|
|
// way. There's room for improvement on this duplication.
|
|
|
let ait = AncestorsIterator::new(graph.clone(), heads, min_root, true)?;
|
|
|
let mut heads_ancestors: Vec<Revision> = Vec::new();
|
|
|
for revres in ait {
|
|
|
let rev = revres?;
|
|
|
if roots.contains(&rev) {
|
|
|
range.insert(rev);
|
|
|
}
|
|
|
heads_ancestors.push(rev);
|
|
|
}
|
|
|
|
|
|
for rev in heads_ancestors.into_iter().rev() {
|
|
|
for parent in graph.parents(rev)?.iter() {
|
|
|
if *parent != NULL_REVISION && range.contains(parent) {
|
|
|
range.insert(rev);
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
Ok(range)
|
|
|
}
|
|
|
|
|
|
#[cfg(test)]
|
|
|
mod tests {
|
|
|
|
|
|
use super::*;
|
|
|
use crate::{testing::SampleGraph, BaseRevision};
|
|
|
|
|
|
/// Apply `retain_heads()` to the given slice and return as a sorted `Vec`
|
|
|
fn retain_heads_sorted(
|
|
|
graph: &impl Graph,
|
|
|
revs: &[BaseRevision],
|
|
|
) -> Result<Vec<Revision>, GraphError> {
|
|
|
let mut revs: HashSet<Revision> =
|
|
|
revs.iter().cloned().map(Revision).collect();
|
|
|
retain_heads(graph, &mut revs)?;
|
|
|
let mut as_vec: Vec<Revision> = revs.iter().cloned().collect();
|
|
|
as_vec.sort_unstable();
|
|
|
Ok(as_vec)
|
|
|
}
|
|
|
|
|
|
#[test]
|
|
|
fn test_retain_heads() -> Result<(), GraphError> {
|
|
|
assert_eq!(retain_heads_sorted(&SampleGraph, &[4, 5, 6])?, vec![5, 6]);
|
|
|
assert_eq!(
|
|
|
retain_heads_sorted(&SampleGraph, &[4, 1, 6, 12, 0])?,
|
|
|
vec![1, 6, 12]
|
|
|
);
|
|
|
assert_eq!(
|
|
|
retain_heads_sorted(&SampleGraph, &[1, 2, 3, 4, 5, 6, 7, 8, 9])?,
|
|
|
vec![3, 5, 8, 9]
|
|
|
);
|
|
|
Ok(())
|
|
|
}
|
|
|
|
|
|
/// Apply `heads()` to the given slice and return as a sorted `Vec`
|
|
|
fn heads_sorted(
|
|
|
graph: &impl Graph,
|
|
|
revs: &[BaseRevision],
|
|
|
) -> Result<Vec<Revision>, GraphError> {
|
|
|
let iter_revs: Vec<_> = revs.iter().cloned().map(Revision).collect();
|
|
|
let heads = heads(graph, iter_revs.iter())?;
|
|
|
let mut as_vec: Vec<Revision> = heads.iter().cloned().collect();
|
|
|
as_vec.sort_unstable();
|
|
|
Ok(as_vec)
|
|
|
}
|
|
|
|
|
|
#[test]
|
|
|
fn test_heads() -> Result<(), GraphError> {
|
|
|
assert_eq!(heads_sorted(&SampleGraph, &[4, 5, 6])?, vec![5, 6]);
|
|
|
assert_eq!(
|
|
|
heads_sorted(&SampleGraph, &[4, 1, 6, 12, 0])?,
|
|
|
vec![1, 6, 12]
|
|
|
);
|
|
|
assert_eq!(
|
|
|
heads_sorted(&SampleGraph, &[1, 2, 3, 4, 5, 6, 7, 8, 9])?,
|
|
|
vec![3, 5, 8, 9]
|
|
|
);
|
|
|
Ok(())
|
|
|
}
|
|
|
|
|
|
/// Apply `roots()` and sort the result for easier comparison
|
|
|
fn roots_sorted(
|
|
|
graph: &impl Graph,
|
|
|
revs: &[BaseRevision],
|
|
|
) -> Result<Vec<Revision>, GraphError> {
|
|
|
let set: HashSet<_> = revs.iter().cloned().map(Revision).collect();
|
|
|
let mut as_vec = roots(graph, &set)?;
|
|
|
as_vec.sort_unstable();
|
|
|
Ok(as_vec)
|
|
|
}
|
|
|
|
|
|
#[test]
|
|
|
fn test_roots() -> Result<(), GraphError> {
|
|
|
assert_eq!(roots_sorted(&SampleGraph, &[4, 5, 6])?, vec![4]);
|
|
|
assert_eq!(
|
|
|
roots_sorted(&SampleGraph, &[4, 1, 6, 12, 0])?,
|
|
|
vec![0, 4, 12]
|
|
|
);
|
|
|
assert_eq!(
|
|
|
roots_sorted(&SampleGraph, &[1, 2, 3, 4, 5, 6, 7, 8, 9])?,
|
|
|
vec![1, 8]
|
|
|
);
|
|
|
Ok(())
|
|
|
}
|
|
|
|
|
|
/// Apply `range()` and convert the result into a Vec for easier comparison
|
|
|
fn range_vec(
|
|
|
graph: impl Graph + Clone,
|
|
|
roots: &[BaseRevision],
|
|
|
heads: &[BaseRevision],
|
|
|
) -> Result<Vec<Revision>, GraphError> {
|
|
|
range(
|
|
|
&graph,
|
|
|
roots.iter().cloned().map(Revision),
|
|
|
heads.iter().cloned().map(Revision),
|
|
|
)
|
|
|
.map(|bs| bs.into_iter().collect())
|
|
|
}
|
|
|
|
|
|
#[test]
|
|
|
fn test_range() -> Result<(), GraphError> {
|
|
|
assert_eq!(range_vec(SampleGraph, &[0], &[4])?, vec![0, 1, 2, 4]);
|
|
|
assert_eq!(
|
|
|
range_vec(SampleGraph, &[0], &[8])?,
|
|
|
Vec::<Revision>::new()
|
|
|
);
|
|
|
assert_eq!(
|
|
|
range_vec(SampleGraph, &[5, 6], &[10, 11, 13])?,
|
|
|
vec![5, 10]
|
|
|
);
|
|
|
assert_eq!(
|
|
|
range_vec(SampleGraph, &[5, 6], &[10, 12])?,
|
|
|
vec![5, 6, 9, 10, 12]
|
|
|
);
|
|
|
Ok(())
|
|
|
}
|
|
|
}
|
|
|
|
