rust: translation of missingancestors

This is as direct as possible a translation of the ancestor.missingancestors
Python class in pure Rust. The goal for this changeset is to make it easy
to compare with the Python version.

We also add to Python tests the cases that helped us develop and debug
this implementation.

Some possible optimizations are marked along the way as TODO comments

Differential Revision: https://phab.mercurial-scm.org/D5416

rust/hg-core/src/ancestors.rs

@@ -1,255 +1,645 b''
 // ancestors.rs
 //
 // Copyright 2018 Georges Racinet <[e-mail]>
 //
 // This software may be used and distributed according to the terms of the
 // GNU General Public License version 2 or any later version.
 
 //! Rust versions of generic DAG ancestors algorithms for Mercurial
 
 use super::{Graph, GraphError, Revision, NULL_REVISION};
+use std::cmp::max;
 use std::collections::{BinaryHeap, HashSet};
 
 /// Iterator over the ancestors of a given list of revisions
 /// This is a generic type, defined and implemented for any Graph, so that
 /// it's easy to
 ///
 /// - unit test in pure Rust
 /// - bind to main Mercurial code, potentially in several ways and have these
 ///   bindings evolve over time
 pub struct AncestorsIterator<G: Graph> {
     graph: G,
     visit: BinaryHeap<Revision>,
     seen: HashSet<Revision>,
     stoprev: Revision,
 }
 
+pub struct MissingAncestors<G: Graph> {
+    graph: G,
+    bases: HashSet<Revision>,
+}
+
 impl<G: Graph> AncestorsIterator<G> {
     /// Constructor.
     ///
     /// if `inclusive` is true, then the init revisions are emitted in
     /// particular, otherwise iteration starts from their parents.
     pub fn new<I>(
         graph: G,
         initrevs: I,
         stoprev: Revision,
         inclusive: bool,
     ) -> Result<Self, GraphError>
     where
         I: IntoIterator<Item = Revision>,
     {
         let filtered_initrevs = initrevs.into_iter().filter(|&r| r >= stoprev);
         if inclusive {
             let visit: BinaryHeap<Revision> = filtered_initrevs.collect();
             let seen = visit.iter().map(|&x| x).collect();
             return Ok(AncestorsIterator {
                 visit: visit,
                 seen: seen,
                 stoprev: stoprev,
                 graph: graph,
             });
         }
         let mut this = AncestorsIterator {
             visit: BinaryHeap::new(),
             seen: HashSet::new(),
             stoprev: stoprev,
             graph: graph,
         };
         this.seen.insert(NULL_REVISION);
         for rev in filtered_initrevs {
             for parent in this.graph.parents(rev)?.iter().cloned() {
                 this.conditionally_push_rev(parent);
             }
         }
         Ok(this)
     }
 
     #[inline]
     fn conditionally_push_rev(&mut self, rev: Revision) {
         if self.stoprev <= rev && !self.seen.contains(&rev) {
             self.seen.insert(rev);
             self.visit.push(rev);
         }
     }
 
     /// Consumes partially the iterator to tell if the given target
     /// revision
     /// is in the ancestors it emits.
     /// This is meant for iterators actually dedicated to that kind of
     /// purpose
     pub fn contains(&mut self, target: Revision) -> Result<bool, GraphError> {
         if self.seen.contains(&target) && target != NULL_REVISION {
             return Ok(true);
         }
         for item in self {
             let rev = item?;
             if rev == target {
                 return Ok(true);
             }
             if rev < target {
                 return Ok(false);
             }
         }
         Ok(false)
     }
 }
 
 /// Main implementation.
 ///
 /// The algorithm is the same as in `_lazyancestorsiter()` from `ancestors.py`
 /// with a few non crucial differences:
 ///
 /// - there's no filtering of invalid parent revisions. Actually, it should be
 ///   consistent and more efficient to filter them from the end caller.
 /// - we don't have the optimization for adjacent revisions (i.e., the case
 ///   where `p1 == rev - 1`), because it amounts to update the first element of
 ///   the heap without sifting, which Rust's BinaryHeap doesn't let us do.
 /// - we save a few pushes by comparing with `stoprev` before pushing
 impl<G: Graph> Iterator for AncestorsIterator<G> {
     type Item = Result<Revision, GraphError>;
 
     fn next(&mut self) -> Option<Self::Item> {
         let current = match self.visit.peek() {
             None => {
                 return None;
             }
             Some(c) => *c,
         };
         let [p1, p2] = match self.graph.parents(current) {
             Ok(ps) => ps,
             Err(e) => return Some(Err(e)),
         };
         if p1 < self.stoprev || self.seen.contains(&p1) {
             self.visit.pop();
         } else {
             *(self.visit.peek_mut().unwrap()) = p1;
             self.seen.insert(p1);
         };
 
         self.conditionally_push_rev(p2);
         Some(Ok(current))
     }
 }
 
+impl<G: Graph> MissingAncestors<G> {
+    pub fn new(graph: G, bases: impl IntoIterator<Item = Revision>) -> Self {
+        let mut bases: HashSet<Revision> = bases.into_iter().collect();
+        if bases.is_empty() {
+            bases.insert(NULL_REVISION);
+        }
+        MissingAncestors { graph, bases }
+    }
+
+    pub fn has_bases(&self) -> bool {
+        self.bases.iter().any(|&b| b != NULL_REVISION)
+    }
+
+    /// Return a reference to current bases.
+    ///
+    /// This is useful in unit tests, but also setdiscovery.py does
+    /// read the bases attribute of a ancestor.missingancestors instance.
+    pub fn get_bases<'a>(&'a self) -> &'a HashSet<Revision> {
+        &self.bases
+    }
+
+    pub fn add_bases(
+        &mut self,
+        new_bases: impl IntoIterator<Item = Revision>,
+    ) {
+        self.bases.extend(new_bases);
+    }
+
+    /// Remove all ancestors of self.bases from the revs set (in place)
+    pub fn remove_ancestors_from(
+        &mut self,
+        revs: &mut HashSet<Revision>,
+    ) -> Result<(), GraphError> {
+        revs.retain(|r| !self.bases.contains(r));
+        // the null revision is always an ancestor
+        revs.remove(&NULL_REVISION);
+        if revs.is_empty() {
+            return Ok(());
+        }
+        // anything in revs > start is definitely not an ancestor of bases
+        // revs <= start need to be investigated
+        // TODO optim: if a missingancestors is to be used several times,
+        // we shouldn't need to iterate each time on bases
+        let start = match self.bases.iter().cloned().max() {
+            Some(m) => m,
+            None => {
+                // bases is empty (shouldn't happen, but let's be safe)
+                return Ok(());
+            }
+        };
+        // whatever happens, we'll keep at least keepcount of them
+        // knowing this gives us a earlier stop condition than
+        // going all the way to the root
+        let keepcount = revs.iter().filter(|r| **r > start).count();
+
+        let mut curr = start;
+        while curr != NULL_REVISION && revs.len() > keepcount {
+            if self.bases.contains(&curr) {
+                revs.remove(&curr);
+                self.add_parents(curr)?;
+            }
+            curr -= 1;
+        }
+        Ok(())
+    }
+
+    /// Add rev's parents to self.bases
+    #[inline]
+    fn add_parents(&mut self, rev: Revision) -> Result<(), GraphError> {
+        // No need to bother the set with inserting NULL_REVISION over and
+        // over
+        for p in self.graph.parents(rev)?.iter().cloned() {
+            if p != NULL_REVISION {
+                self.bases.insert(p);
+            }
+        }
+        Ok(())
+    }
+
+    /// Return all the ancestors of revs that are not ancestors of self.bases
+    ///
+    /// This may include elements from revs.
+    ///
+    /// Equivalent to the revset (::revs - ::self.bases). Revs are returned in
+    /// revision number order, which is a topological order.
+    pub fn missing_ancestors(
+        &mut self,
+        revs: impl IntoIterator<Item = Revision>,
+    ) -> Result<Vec<Revision>, GraphError> {
+        // just for convenience and comparison with Python version
+        let bases_visit = &mut self.bases;
+        let mut revs: HashSet<Revision> = revs
+            .into_iter()
+            .filter(|r| !bases_visit.contains(r))
+            .collect();
+        let revs_visit = &mut revs;
+        let mut both_visit: HashSet<Revision> =
+            revs_visit.intersection(&bases_visit).cloned().collect();
+        if revs_visit.is_empty() {
+            return Ok(Vec::new());
+        }
+
+        let max_bases =
+            bases_visit.iter().cloned().max().unwrap_or(NULL_REVISION);
+        let max_revs =
+            revs_visit.iter().cloned().max().unwrap_or(NULL_REVISION);
+        let start = max(max_bases, max_revs);
+
+        // TODO heuristics for with_capacity()?
+        let mut missing: Vec<Revision> = Vec::new();
+        for curr in (0..=start).map(|i| start - i) {
+            if revs_visit.is_empty() {
+                break;
+            }
+            if both_visit.contains(&curr) {
+                // curr's parents might have made it into revs_visit through
+                // another path
+                // TODO optim: Rust's HashSet.remove returns a boolean telling
+                // if it happened. This will spare us one set lookup
+                both_visit.remove(&curr);
+                for p in self.graph.parents(curr)?.iter().cloned() {
+                    if p == NULL_REVISION {
+                        continue;
+                    }
+                    revs_visit.remove(&p);
+                    bases_visit.insert(p);
+                    both_visit.insert(p);
+                }
+                continue;
+            }
+            // in Rust, one can't just use mutable variables assignation
+            // to be more straightforward. Instead of Python's
+            // thisvisit and othervisit, we'll differentiate with a boolean
+            let this_visit_is_revs = {
+                if revs_visit.remove(&curr) {
+                    missing.push(curr);
+                    true
+                } else if bases_visit.contains(&curr) {
+                    false
+                } else {
+                    // not an ancestor of revs or bases: ignore
+                    continue;
+                }
+            };
+
+            for p in self.graph.parents(curr)?.iter().cloned() {
+                if p == NULL_REVISION {
+                    continue;
+                }
+                let in_other_visit = if this_visit_is_revs {
+                    bases_visit.contains(&p)
+                } else {
+                    revs_visit.contains(&p)
+                };
+                if in_other_visit || both_visit.contains(&p) {
+                    // p is implicitely in this_visit.
+                    // This means p is or should be in bothvisit
+                    // TODO optim: hence if bothvisit, we look up twice
+                    revs_visit.remove(&p);
+                    bases_visit.insert(p);
+                    both_visit.insert(p);
+                } else {
+                    // visit later
+                    if this_visit_is_revs {
+                        revs_visit.insert(p);
+                    } else {
+                        bases_visit.insert(p);
+                    }
+                }
+            }
+        }
+        missing.reverse();
+        Ok(missing)
+    }
+}
+
 #[cfg(test)]
 mod tests {
 
     use super::*;
+    use std::iter::FromIterator;
 
     #[derive(Clone, Debug)]
     struct Stub;
 
     /// This is the same as the dict from test-ancestors.py
     impl Graph for Stub {
         fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> {
             match rev {
                 0 => Ok([-1, -1]),
                 1 => Ok([0, -1]),
                 2 => Ok([1, -1]),
                 3 => Ok([1, -1]),
                 4 => Ok([2, -1]),
                 5 => Ok([4, -1]),
                 6 => Ok([4, -1]),
                 7 => Ok([4, -1]),
                 8 => Ok([-1, -1]),
                 9 => Ok([6, 7]),
                 10 => Ok([5, -1]),
                 11 => Ok([3, 7]),
                 12 => Ok([9, -1]),
                 13 => Ok([8, -1]),
                 r => Err(GraphError::ParentOutOfRange(r)),
             }
         }
     }
 
     fn list_ancestors<G: Graph>(
         graph: G,
         initrevs: Vec<Revision>,
         stoprev: Revision,
         inclusive: bool,
     ) -> Vec<Revision> {
         AncestorsIterator::new(graph, initrevs, stoprev, inclusive)
             .unwrap()
             .map(|res| res.unwrap())
             .collect()
     }
 
     #[test]
     /// Same tests as test-ancestor.py, without membership
     /// (see also test-ancestor.py.out)
     fn test_list_ancestor() {
         assert_eq!(list_ancestors(Stub, vec![], 0, false), vec![]);
         assert_eq!(
             list_ancestors(Stub, vec![11, 13], 0, false),
             vec![8, 7, 4, 3, 2, 1, 0]
         );
         assert_eq!(list_ancestors(Stub, vec![1, 3], 0, false), vec![1, 0]);
         assert_eq!(
             list_ancestors(Stub, vec![11, 13], 0, true),
             vec![13, 11, 8, 7, 4, 3, 2, 1, 0]
         );
         assert_eq!(list_ancestors(Stub, vec![11, 13], 6, false), vec![8, 7]);
         assert_eq!(
             list_ancestors(Stub, vec![11, 13], 6, true),
             vec![13, 11, 8, 7]
         );
         assert_eq!(list_ancestors(Stub, vec![11, 13], 11, true), vec![13, 11]);
         assert_eq!(list_ancestors(Stub, vec![11, 13], 12, true), vec![13]);
         assert_eq!(
             list_ancestors(Stub, vec![10, 1], 0, true),
             vec![10, 5, 4, 2, 1, 0]
         );
     }
 
     #[test]
     /// Corner case that's not directly in test-ancestors.py, but
     /// that happens quite often, as demonstrated by running the whole
     /// suite.
     /// For instance, run tests/test-obsolete-checkheads.t
     fn test_nullrev_input() {
         let mut iter =
             AncestorsIterator::new(Stub, vec![-1], 0, false).unwrap();
         assert_eq!(iter.next(), None)
     }
 
     #[test]
     fn test_contains() {
         let mut lazy =
             AncestorsIterator::new(Stub, vec![10, 1], 0, true).unwrap();
         assert!(lazy.contains(1).unwrap());
         assert!(!lazy.contains(3).unwrap());
 
         let mut lazy =
             AncestorsIterator::new(Stub, vec![0], 0, false).unwrap();
         assert!(!lazy.contains(NULL_REVISION).unwrap());
     }
 
     /// A corrupted Graph, supporting error handling tests
     struct Corrupted;
 
     impl Graph for Corrupted {
         fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> {
             match rev {
                 1 => Ok([0, -1]),
                 r => Err(GraphError::ParentOutOfRange(r)),
             }
         }
     }
 
     #[test]
     fn test_initrev_out_of_range() {
         // inclusive=false looks up initrev's parents right away
         match AncestorsIterator::new(Stub, vec![25], 0, false) {
             Ok(_) => panic!("Should have been ParentOutOfRange"),
             Err(e) => assert_eq!(e, GraphError::ParentOutOfRange(25)),
         }
     }
 
     #[test]
     fn test_next_out_of_range() {
         // inclusive=false looks up initrev's parents right away
         let mut iter =
             AncestorsIterator::new(Corrupted, vec![1], 0, false).unwrap();
         assert_eq!(iter.next(), Some(Err(GraphError::ParentOutOfRange(0))));
     }
+
+    #[test]
+    /// Test constructor, add/get bases
+    fn test_missing_bases() {
+        let mut missing_ancestors =
+            MissingAncestors::new(Stub, [5, 3, 1, 3].iter().cloned());
+        let mut as_vec: Vec<Revision> =
+            missing_ancestors.get_bases().iter().cloned().collect();
+        as_vec.sort();
+        assert_eq!(as_vec, [1, 3, 5]);
+
+        missing_ancestors.add_bases([3, 7, 8].iter().cloned());
+        as_vec = missing_ancestors.get_bases().iter().cloned().collect();
+        as_vec.sort();
+        assert_eq!(as_vec, [1, 3, 5, 7, 8]);
+    }
+
+    fn assert_missing_remove(
+        bases: &[Revision],
+        revs: &[Revision],
+        expected: &[Revision],
+    ) {
+        let mut missing_ancestors =
+            MissingAncestors::new(Stub, bases.iter().cloned());
+        let mut revset: HashSet<Revision> = revs.iter().cloned().collect();
+        missing_ancestors
+            .remove_ancestors_from(&mut revset)
+            .unwrap();
+        let mut as_vec: Vec<Revision> = revset.into_iter().collect();
+        as_vec.sort();
+        assert_eq!(as_vec.as_slice(), expected);
+    }
+
+    #[test]
+    fn test_missing_remove() {
+        assert_missing_remove(
+            &[1, 2, 3, 4, 7],
+            Vec::from_iter(1..10).as_slice(),
+            &[5, 6, 8, 9],
+        );
+        assert_missing_remove(&[10], &[11, 12, 13, 14], &[11, 12, 13, 14]);
+        assert_missing_remove(&[7], &[1, 2, 3, 4, 5], &[3, 5]);
+    }
+
+    fn assert_missing_ancestors(
+        bases: &[Revision],
+        revs: &[Revision],
+        expected: &[Revision],
+    ) {
+        let mut missing_ancestors =
+            MissingAncestors::new(Stub, bases.iter().cloned());
+        let missing = missing_ancestors
+            .missing_ancestors(revs.iter().cloned())
+            .unwrap();
+        assert_eq!(missing.as_slice(), expected);
+    }
+
+    #[test]
+    fn test_missing_ancestors() {
+        // examples taken from test-ancestors.py by having it run
+        // on the same graph (both naive and fast Python algs)
+        assert_missing_ancestors(&[10], &[11], &[3, 7, 11]);
+        assert_missing_ancestors(&[11], &[10], &[5, 10]);
+        assert_missing_ancestors(&[7], &[9, 11], &[3, 6, 9, 11]);
+    }
+
+    // A Graph represented by a vector whose indices are revisions
+    // and values are parents of the revisions
+    type VecGraph = Vec<[Revision; 2]>;
+
+    impl Graph for VecGraph {
+        fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> {
+            Ok(self[rev as usize])
+        }
+    }
+
+    /// An interesting case found by a random generator similar to
+    /// the one in test-ancestor.py. An early version of Rust MissingAncestors
+    /// failed this, yet none of the integration tests of the whole suite
+    /// catched it.
+    #[test]
+    fn test_remove_ancestors_from_case1() {
+        let graph: VecGraph = vec![
+            [NULL_REVISION, NULL_REVISION],
+            [0, NULL_REVISION],
+            [1, 0],
+            [2, 1],
+            [3, NULL_REVISION],
+            [4, NULL_REVISION],
+            [5, 1],
+            [2, NULL_REVISION],
+            [7, NULL_REVISION],
+            [8, NULL_REVISION],
+            [9, NULL_REVISION],
+            [10, 1],
+            [3, NULL_REVISION],
+            [12, NULL_REVISION],
+            [13, NULL_REVISION],
+            [14, NULL_REVISION],
+            [4, NULL_REVISION],
+            [16, NULL_REVISION],
+            [17, NULL_REVISION],
+            [18, NULL_REVISION],
+            [19, 11],
+            [20, NULL_REVISION],
+            [21, NULL_REVISION],
+            [22, NULL_REVISION],
+            [23, NULL_REVISION],
+            [2, NULL_REVISION],
+            [3, NULL_REVISION],
+            [26, 24],
+            [27, NULL_REVISION],
+            [28, NULL_REVISION],
+            [12, NULL_REVISION],
+            [1, NULL_REVISION],
+            [1, 9],
+            [32, NULL_REVISION],
+            [33, NULL_REVISION],
+            [34, 31],
+            [35, NULL_REVISION],
+            [36, 26],
+            [37, NULL_REVISION],
+            [38, NULL_REVISION],
+            [39, NULL_REVISION],
+            [40, NULL_REVISION],
+            [41, NULL_REVISION],
+            [42, 26],
+            [0, NULL_REVISION],
+            [44, NULL_REVISION],
+            [45, 4],
+            [40, NULL_REVISION],
+            [47, NULL_REVISION],
+            [36, 0],
+            [49, NULL_REVISION],
+            [NULL_REVISION, NULL_REVISION],
+            [51, NULL_REVISION],
+            [52, NULL_REVISION],
+            [53, NULL_REVISION],
+            [14, NULL_REVISION],
+            [55, NULL_REVISION],
+            [15, NULL_REVISION],
+            [23, NULL_REVISION],
+            [58, NULL_REVISION],
+            [59, NULL_REVISION],
+            [2, NULL_REVISION],
+            [61, 59],
+            [62, NULL_REVISION],
+            [63, NULL_REVISION],
+            [NULL_REVISION, NULL_REVISION],
+            [65, NULL_REVISION],
+            [66, NULL_REVISION],
+            [67, NULL_REVISION],
+            [68, NULL_REVISION],
+            [37, 28],
+            [69, 25],
+            [71, NULL_REVISION],
+            [72, NULL_REVISION],
+            [50, 2],
+            [74, NULL_REVISION],
+            [12, NULL_REVISION],
+            [18, NULL_REVISION],
+            [77, NULL_REVISION],
+            [78, NULL_REVISION],
+            [79, NULL_REVISION],
+            [43, 33],
+            [81, NULL_REVISION],
+            [82, NULL_REVISION],
+            [83, NULL_REVISION],
+            [84, 45],
+            [85, NULL_REVISION],
+            [86, NULL_REVISION],
+            [NULL_REVISION, NULL_REVISION],
+            [88, NULL_REVISION],
+            [NULL_REVISION, NULL_REVISION],
+            [76, 83],
+            [44, NULL_REVISION],
+            [92, NULL_REVISION],
+            [93, NULL_REVISION],
+            [9, NULL_REVISION],
+            [95, 67],
+            [96, NULL_REVISION],
+            [97, NULL_REVISION],
+            [NULL_REVISION, NULL_REVISION],
+        ];
+        let problem_rev = 28 as Revision;
+        let problem_base = 70 as Revision;
+        // making the problem obvious: problem_rev is a parent of problem_base
+        assert_eq!(graph.parents(problem_base).unwrap()[1], problem_rev);
+
+        let mut missing_ancestors: MissingAncestors<VecGraph> =
+            MissingAncestors::new(
+                graph,
+                [60, 26, 70, 3, 96, 19, 98, 49, 97, 47, 1, 6]
+                    .iter()
+                    .cloned(),
+            );
+        assert!(missing_ancestors.bases.contains(&problem_base));
+
+        let mut revs: HashSet<Revision> =
+            [4, 12, 41, 28, 68, 38, 1, 30, 56, 44]
+                .iter()
+                .cloned()
+                .collect();
+        missing_ancestors.remove_ancestors_from(&mut revs).unwrap();
+        assert!(!revs.contains(&problem_rev));
+    }
+
 }

rust/hg-core/src/lib.rs

@@ -1,24 +1,27 b''
 // Copyright 2018 Georges Racinet <[e-mail]>
 //
 // This software may be used and distributed according to the terms of the
 // GNU General Public License version 2 or any later version.
 mod ancestors;
-pub use ancestors::AncestorsIterator;
+pub use ancestors::{AncestorsIterator, MissingAncestors};
 
 /// Mercurial revision numbers
 ///
 /// As noted in revlog.c, revision numbers are actually encoded in
 /// 4 bytes, and are liberally converted to ints, whence the i32
 pub type Revision = i32;
 
 pub const NULL_REVISION: Revision = -1;
 
 /// The simplest expression of what we need of Mercurial DAGs.
 pub trait Graph {
+    /// Return the two parents of the given `Revision`.
+    ///
+    /// Each of the parents can be independently `NULL_REVISION`
     fn parents(&self, Revision) -> Result<[Revision; 2], GraphError>;
 }
 
 #[derive(Clone, Debug, PartialEq)]
 pub enum GraphError {
     ParentOutOfRange(Revision),
 }

tests/test-ancestor.py

@@ -1,284 +1,343 b''
 from __future__ import absolute_import, print_function
 
 import binascii
 import getopt
 import math
 import os
 import random
 import sys
 import time
 
 from mercurial.node import nullrev
 from mercurial import (
     ancestor,
     debugcommands,
     hg,
     pycompat,
     ui as uimod,
     util,
 )
 
 if pycompat.ispy3:
     long = int
     xrange = range
 
 def buildgraph(rng, nodes=100, rootprob=0.05, mergeprob=0.2, prevprob=0.7):
     '''nodes: total number of nodes in the graph
     rootprob: probability that a new node (not 0) will be a root
     mergeprob: probability that, excluding a root a node will be a merge
     prevprob: probability that p1 will be the previous node
 
     return value is a graph represented as an adjacency list.
     '''
     graph = [None] * nodes
     for i in xrange(nodes):
         if i == 0 or rng.random() < rootprob:
             graph[i] = [nullrev]
         elif i == 1:
             graph[i] = [0]
         elif rng.random() < mergeprob:
             if i == 2 or rng.random() < prevprob:
                 # p1 is prev
                 p1 = i - 1
             else:
                 p1 = rng.randrange(i - 1)
             p2 = rng.choice(list(range(0, p1)) + list(range(p1 + 1, i)))
             graph[i] = [p1, p2]
         elif rng.random() < prevprob:
             graph[i] = [i - 1]
         else:
             graph[i] = [rng.randrange(i - 1)]
 
     return graph
 
 def buildancestorsets(graph):
     ancs = [None] * len(graph)
     for i in xrange(len(graph)):
         ancs[i] = {i}
         if graph[i] == [nullrev]:
             continue
         for p in graph[i]:
             ancs[i].update(ancs[p])
     return ancs
 
 class naiveincrementalmissingancestors(object):
     def __init__(self, ancs, bases):
         self.ancs = ancs
         self.bases = set(bases)
     def addbases(self, newbases):
         self.bases.update(newbases)
     def removeancestorsfrom(self, revs):
         for base in self.bases:
             if base != nullrev:
                 revs.difference_update(self.ancs[base])
         revs.discard(nullrev)
     def missingancestors(self, revs):
         res = set()
         for rev in revs:
             if rev != nullrev:
                 res.update(self.ancs[rev])
         for base in self.bases:
             if base != nullrev:
                 res.difference_update(self.ancs[base])
         return sorted(res)
 
 def test_missingancestors(seed, rng):
     # empirically observed to take around 1 second
     graphcount = 100
     testcount = 10
     inccount = 10
     nerrs = [0]
     # the default mu and sigma give us a nice distribution of mostly
     # single-digit counts (including 0) with some higher ones
     def lognormrandom(mu, sigma):
         return int(math.floor(rng.lognormvariate(mu, sigma)))
 
     def samplerevs(nodes, mu=1.1, sigma=0.8):
         count = min(lognormrandom(mu, sigma), len(nodes))
         return rng.sample(nodes, count)
 
     def err(seed, graph, bases, seq, output, expected):
         if nerrs[0] == 0:
             print('seed:', hex(seed)[:-1], file=sys.stderr)
         if gerrs[0] == 0:
             print('graph:', graph, file=sys.stderr)
         print('* bases:', bases, file=sys.stderr)
         print('* seq: ', seq, file=sys.stderr)
         print('*  output:  ', output, file=sys.stderr)
         print('*  expected:', expected, file=sys.stderr)
         nerrs[0] += 1
         gerrs[0] += 1
 
     for g in xrange(graphcount):
         graph = buildgraph(rng)
         ancs = buildancestorsets(graph)
         gerrs = [0]
         for _ in xrange(testcount):
             # start from nullrev to include it as a possibility
             graphnodes = range(nullrev, len(graph))
             bases = samplerevs(graphnodes)
 
             # fast algorithm
             inc = ancestor.incrementalmissingancestors(graph.__getitem__, bases)
             # reference slow algorithm
             naiveinc = naiveincrementalmissingancestors(ancs, bases)
             seq = []
             revs = []
             for _ in xrange(inccount):
                 if rng.random() < 0.2:
                     newbases = samplerevs(graphnodes)
                     seq.append(('addbases', newbases))
                     inc.addbases(newbases)
                     naiveinc.addbases(newbases)
                 if rng.random() < 0.4:
                     # larger set so that there are more revs to remove from
                     revs = samplerevs(graphnodes, mu=1.5)
                     seq.append(('removeancestorsfrom', revs))
                     hrevs = set(revs)
                     rrevs = set(revs)
                     inc.removeancestorsfrom(hrevs)
                     naiveinc.removeancestorsfrom(rrevs)
                     if hrevs != rrevs:
                         err(seed, graph, bases, seq, sorted(hrevs),
                             sorted(rrevs))
                 else:
                     revs = samplerevs(graphnodes)
                     seq.append(('missingancestors', revs))
                     h = inc.missingancestors(revs)
                     r = naiveinc.missingancestors(revs)
                     if h != r:
                         err(seed, graph, bases, seq, h, r)
 
 # graph is a dict of child->parent adjacency lists for this graph:
 # o  13
 # |
 # | o  12
 # | |
 # | | o    11
 # | | |\
 # | | | | o  10
 # | | | | |
 # | o---+ |  9
 # | | | | |
 # o | | | |  8
 #  / / / /
 # | | o |  7
 # | | | |
 # o---+ |  6
 #  / / /
 # | | o  5
 # | |/
 # | o  4
 # | |
 # o |  3
 # | |
 # | o  2
 # |/
 # o  1
 # |
 # o  0
 
 graph = {0: [-1, -1], 1: [0, -1], 2: [1, -1], 3: [1, -1], 4: [2, -1],
          5: [4, -1], 6: [4, -1], 7: [4, -1], 8: [-1, -1], 9: [6, 7],
          10: [5, -1], 11: [3, 7], 12: [9, -1], 13: [8, -1]}
 
+def test_missingancestors_explicit():
+    """A few explicit cases, easier to check for catching errors in refactors.
+
+    The bigger graph at the end has been produced by the random generator
+    above, and we have some evidence that the other tests don't cover it.
+    """
+    for i, (bases, revs) in enumerate((({1, 2, 3, 4, 7}, set(xrange(10))),
+                                       ({10}, set({11, 12, 13, 14})),
+                                       ({7}, set({1, 2, 3, 4, 5})),
+                                       )):
+        print("%% removeancestorsfrom(), example %d" % (i + 1))
+        missanc = ancestor.incrementalmissingancestors(graph.get, bases)
+        missanc.removeancestorsfrom(revs)
+        print("remaining (sorted): %s" % sorted(list(revs)))
+
+    for i, (bases, revs) in enumerate((({10}, {11}),
+                                       ({11}, {10}),
+                                       ({7}, {9, 11}),
+                                       )):
+        print("%% missingancestors(), example %d" % (i + 1))
+        missanc = ancestor.incrementalmissingancestors(graph.get, bases)
+        print("return %s" % missanc.missingancestors(revs))
+
+    print("% removeancestorsfrom(), bigger graph")
+    vecgraph = [
+        [-1, -1], [0, -1], [1, 0], [2, 1], [3, -1], [4, -1], [5, 1],
+        [2, -1], [7, -1], [8, -1], [9, -1], [10, 1], [3, -1], [12, -1],
+        [13, -1], [14, -1], [4, -1], [16, -1], [17, -1], [18, -1],
+        [19, 11], [20, -1], [21, -1], [22, -1], [23, -1], [2, -1],
+        [3, -1], [26, 24], [27, -1], [28, -1], [12, -1], [1, -1], [1, 9],
+        [32, -1], [33, -1], [34, 31], [35, -1], [36, 26], [37, -1],
+        [38, -1], [39, -1], [40, -1], [41, -1], [42, 26], [0, -1],
+        [44, -1], [45, 4], [40, -1], [47, -1], [36, 0], [49, -1],
+        [-1, -1], [51, -1], [52, -1], [53, -1], [14, -1],
+        [55, -1], [15, -1], [23, -1], [58, -1], [59, -1], [2, -1],
+        [61, 59], [62, -1], [63, -1], [-1, -1], [65, -1],
+        [66, -1], [67, -1], [68, -1], [37, 28], [69, 25],
+        [71, -1], [72, -1], [50, 2], [74, -1], [12, -1],
+        [18, -1], [77, -1], [78, -1], [79, -1], [43, 33],
+        [81, -1], [82, -1], [83, -1], [84, 45], [85, -1],
+        [86, -1], [-1, -1], [88, -1], [-1, -1], [76, 83], [44, -1],
+        [92, -1], [93, -1], [9, -1], [95, 67], [96, -1], [97, -1],
+        [-1, -1]]
+    problem_rev = 28
+    problem_base = 70
+    # problem_rev is a parent of problem_base, but a faulty implementation
+    # could forget to remove it.
+    bases = {60, 26, 70, 3, 96, 19, 98, 49, 97, 47, 1, 6}
+    if problem_rev not in vecgraph[problem_base] or problem_base not in bases:
+        print("Conditions have changed")
+    missanc = ancestor.incrementalmissingancestors(vecgraph.__getitem__, bases)
+    revs = {4, 12, 41, 28, 68, 38, 1, 30, 56, 44}
+    missanc.removeancestorsfrom(revs)
+    if 28 in revs:
+        print("Failed!")
+    else:
+        print("Ok")
+
 def genlazyancestors(revs, stoprev=0, inclusive=False):
     print(("%% lazy ancestor set for %s, stoprev = %s, inclusive = %s" %
            (revs, stoprev, inclusive)))
     return ancestor.lazyancestors(graph.get, revs, stoprev=stoprev,
                                   inclusive=inclusive)
 
 def printlazyancestors(s, l):
     print('membership: %r' % [n for n in l if n in s])
     print('iteration:  %r' % list(s))
 
 def test_lazyancestors():
     # Empty revs
     s = genlazyancestors([])
     printlazyancestors(s, [3, 0, -1])
 
     # Standard example
     s = genlazyancestors([11, 13])
     printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0])
 
     # Standard with ancestry in the initial set (1 is ancestor of 3)
     s = genlazyancestors([1, 3])
     printlazyancestors(s, [1, -1, 0])
 
     # Including revs
     s = genlazyancestors([11, 13], inclusive=True)
     printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0])
 
     # Test with stoprev
     s = genlazyancestors([11, 13], stoprev=6)
     printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0])
     s = genlazyancestors([11, 13], stoprev=6, inclusive=True)
     printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0])
 
     # Test with stoprev >= min(initrevs)
     s = genlazyancestors([11, 13], stoprev=11, inclusive=True)
     printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0])
     s = genlazyancestors([11, 13], stoprev=12, inclusive=True)
     printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0])
 
     # Contiguous chains: 5->4, 2->1 (where 1 is in seen set), 1->0
     s = genlazyancestors([10, 1], inclusive=True)
     printlazyancestors(s, [2, 10, 4, 5, -1, 0, 1])
 
 # The C gca algorithm requires a real repo. These are textual descriptions of
 # DAGs that have been known to be problematic, and, optionally, known pairs
 # of revisions and their expected ancestor list.
 dagtests = [
     (b'+2*2*2/*3/2', {}),
     (b'+3*3/*2*2/*4*4/*4/2*4/2*2', {}),
     (b'+2*2*/2*4*/4*/3*2/4', {(6, 7): [3, 5]}),
 ]
 def test_gca():
     u = uimod.ui.load()
     for i, (dag, tests) in enumerate(dagtests):
         repo = hg.repository(u, b'gca%d' % i, create=1)
         cl = repo.changelog
         if not util.safehasattr(cl.index, 'ancestors'):
             # C version not available
             return
 
         debugcommands.debugbuilddag(u, repo, dag)
         # Compare the results of the Python and C versions. This does not
         # include choosing a winner when more than one gca exists -- we make
         # sure both return exactly the same set of gcas.
         # Also compare against expected results, if available.
         for a in cl:
             for b in cl:
                 cgcas = sorted(cl.index.ancestors(a, b))
                 pygcas = sorted(ancestor.ancestors(cl.parentrevs, a, b))
                 expected = None
                 if (a, b) in tests:
                     expected = tests[(a, b)]
                 if cgcas != pygcas or (expected and cgcas != expected):
                     print("test_gca: for dag %s, gcas for %d, %d:"
                           % (dag, a, b))
                     print("  C returned:      %s" % cgcas)
                     print("  Python returned: %s" % pygcas)
                     if expected:
                         print("  expected:        %s" % expected)
 
 def main():
     seed = None
     opts, args = getopt.getopt(sys.argv[1:], 's:', ['seed='])
     for o, a in opts:
         if o in ('-s', '--seed'):
             seed = long(a, base=0) # accepts base 10 or 16 strings
 
     if seed is None:
         try:
             seed = long(binascii.hexlify(os.urandom(16)), 16)
         except AttributeError:
             seed = long(time.time() * 1000)
 
     rng = random.Random(seed)
+    test_missingancestors_explicit()
     test_missingancestors(seed, rng)
     test_lazyancestors()
     test_gca()
 
 if __name__ == '__main__':
     main()

tests/test-ancestor.py.out

@@ -1,27 +1,41 b''
+% removeancestorsfrom(), example 1
+remaining (sorted): [5, 6, 8, 9]
+% removeancestorsfrom(), example 2
+remaining (sorted): [11, 12, 13, 14]
+% removeancestorsfrom(), example 3
+remaining (sorted): [3, 5]
+% missingancestors(), example 1
+return [3, 7, 11]
+% missingancestors(), example 2
+return [5, 10]
+% missingancestors(), example 3
+return [3, 6, 9, 11]
+% removeancestorsfrom(), bigger graph
+Ok
 % lazy ancestor set for [], stoprev = 0, inclusive = False
 membership: []
 iteration:  []
 % lazy ancestor set for [11, 13], stoprev = 0, inclusive = False
 membership: [7, 8, 3, 4, 1, 0]
 iteration:  [8, 7, 4, 3, 2, 1, 0]
 % lazy ancestor set for [1, 3], stoprev = 0, inclusive = False
 membership: [1, 0]
 iteration:  [1, 0]
 % lazy ancestor set for [11, 13], stoprev = 0, inclusive = True
 membership: [11, 13, 7, 8, 3, 4, 1, 0]
 iteration:  [13, 11, 8, 7, 4, 3, 2, 1, 0]
 % lazy ancestor set for [11, 13], stoprev = 6, inclusive = False
 membership: [7, 8]
 iteration:  [8, 7]
 % lazy ancestor set for [11, 13], stoprev = 6, inclusive = True
 membership: [11, 13, 7, 8]
 iteration:  [13, 11, 8, 7]
 % lazy ancestor set for [11, 13], stoprev = 11, inclusive = True
 membership: [11, 13]
 iteration:  [13, 11]
 % lazy ancestor set for [11, 13], stoprev = 12, inclusive = True
 membership: [13]
 iteration:  [13]
 % lazy ancestor set for [10, 1], stoprev = 0, inclusive = True
 membership: [2, 10, 4, 5, 0, 1]
 iteration:  [10, 5, 4, 2, 1, 0]