# HG changeset patch
# User Pierre-Yves David <pierre-yves.david@octobus.net>
# Date 1647889611 -3600
# Node ID 3f6ddb1c193b6714533c57c12f8a8ef45d8d6f13
# Parent  5a24bb7f4ed742c6d84cf6c694b73c97b14e2d50
subsetmaker: rework the antichain generation to be usable

Before this, antichain computation can run for 10s of hours without completion in
sight. We use a more direct approach in the computation to keep the computation
in complexity in check. With good result.

We can now have a full antichain computation on mozilla-try in about one
minute. Which is usable.

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

diff -r 5a24bb7f4ed7 -r 3f6ddb1c193b contrib/perf-utils/subsetmaker.py
--- a/contrib/perf-utils/subsetmaker.py	Sun Mar 13 16:24:01 2022 +0100
+++ b/contrib/perf-utils/subsetmaker.py	Mon Mar 21 20:06:51 2022 +0100
@@ -159,16 +159,44 @@
     else:
         assert False
 
-    selected = set()
+    cl = repo.changelog
 
-    baseset = revset.getset(repo, smartset.fullreposet(repo), x)
-    undecided = baseset
+    # We already have cheap access to the parent mapping.
+    # However, we need to build a mapping of the children mapping
+    parents = repo.changelog._uncheckedparentrevs
+    children_map = collections.defaultdict(list)
+    for r in cl:
+        p1, p2 = parents(r)
+        if p1 >= 0:
+            children_map[p1].append(r)
+        if p2 >= 0:
+            children_map[p2].append(r)
+    children = children_map.__getitem__
+
+    selected = set()
+    undecided = SortedSet(cl)
 
     while undecided:
-        pick = rand.choice(list(undecided))
+        # while there is "undecided content", we pick a random changeset X
+        # and we remove anything in `::X + X::` from undecided content
+        pick = rand.choice(undecided)
         selected.add(pick)
-        undecided = repo.revs(
-            '%ld and not (::%ld or %ld::head())', baseset, selected, selected
-        )
+        undecided.remove(pick)
+
+        ancestors = set(p for p in parents(pick) if p in undecided)
+        descendants = set(c for c in children(pick) if c in undecided)
+
+        while ancestors:
+            current = ancestors.pop()
+            undecided.remove(current)
+            for p in parents(current):
+                if p in undecided:
+                    ancestors.add(p)
+        while descendants:
+            current = descendants.pop()
+            undecided.remove(current)
+            for p in children(current):
+                if p in undecided:
+                    ancestors.add(p)
 
     return smartset.baseset(selected) & subset