# HG changeset patch
# User Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
# Date 1314300314 -7200
# Node ID c20688b7c06129f6fa23d53b7c927f9e79b5b313
# Parent  0fc95f5cea57cb48e55ff7167f273b555275df81
setdiscovery: fix hang when #heads>200 (issue2971)

When setting up the next sample, we always add all of the heads, regardless
of the desired max sample size. But if the number of heads exceeds this
size, then we don't add any more nodes from the still undecided set.
(This is debatable per se, and I'll investigate it, but it's how we designed
it at the moment.)

The bug was that we always added the overall heads, not the heads of the
remaining undecided set. Thus, if #heads>200 (desired sample size), we
did not make progress any longer.

diff -r 0fc95f5cea57 -r c20688b7c061 mercurial/setdiscovery.py
--- a/mercurial/setdiscovery.py	Tue Aug 30 14:18:58 2011 +0200
+++ b/mercurial/setdiscovery.py	Thu Aug 25 21:25:14 2011 +0200
@@ -41,7 +41,7 @@
 def _setupsample(dag, nodes, size):
     if len(nodes) <= size:
         return set(nodes), None, 0
-    always = set(dag.heads())
+    always = dag.headsetofconnecteds(nodes)
     desiredlen = size - len(always)
     if desiredlen <= 0:
         # This could be bad if there are very many heads, all unknown to the
diff -r 0fc95f5cea57 -r c20688b7c061 tests/test-setdiscovery.t
--- a/tests/test-setdiscovery.t	Tue Aug 30 14:18:58 2011 +0200
+++ b/tests/test-setdiscovery.t	Thu Aug 25 21:25:14 2011 +0200
@@ -265,4 +265,62 @@
   common heads: 7ead0cba2838
 
 
+One with >200 heads, which used to use up all of the sample:
 
+  $ hg init manyheads
+  $ cd manyheads
+  $ echo "+300:r @a" >dagdesc
+  $ echo "*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3 *r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3" >>dagdesc # 20 heads
+  $ echo "*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3 *r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3" >>dagdesc # 20 heads
+  $ echo "*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3 *r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3" >>dagdesc # 20 heads
+  $ echo "*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3 *r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3" >>dagdesc # 20 heads
+  $ echo "*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3 *r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3" >>dagdesc # 20 heads
+  $ echo "*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3 *r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3" >>dagdesc # 20 heads
+  $ echo "*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3 *r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3" >>dagdesc # 20 heads
+  $ echo "*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3 *r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3" >>dagdesc # 20 heads
+  $ echo "*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3 *r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3" >>dagdesc # 20 heads
+  $ echo "*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3 *r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3" >>dagdesc # 20 heads
+  $ echo "*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3 *r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3" >>dagdesc # 20 heads
+  $ echo "*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3 *r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3" >>dagdesc # 20 heads
+  $ echo "*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3 *r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3" >>dagdesc # 20 heads
+  $ echo "@b *r+3" >>dagdesc # one more head
+  $ hg debugbuilddag <dagdesc
+  reading DAG from stdin
+
+  $ hg heads -t --template . | wc -c
+  261
+
+  $ hg clone -b a . a
+  adding changesets
+  adding manifests
+  adding file changes
+  added 1340 changesets with 0 changes to 0 files (+259 heads)
+  updating to branch a
+  0 files updated, 0 files merged, 0 files removed, 0 files unresolved
+  $ hg clone -b b . b
+  adding changesets
+  adding manifests
+  adding file changes
+  added 304 changesets with 0 changes to 0 files
+  updating to branch b
+  0 files updated, 0 files merged, 0 files removed, 0 files unresolved
+
+  $ hg -R a debugdiscovery b --debug --verbose
+  comparing with b
+  query 1; heads
+  searching for changes
+  taking quick initial sample
+  searching: 2 queries
+  query 2; still undecided: 1080, sample size is: 260
+  sampling from both directions
+  searching: 3 queries
+  query 3; still undecided: 820, sample size is: 260
+  sampling from both directions
+  searching: 4 queries
+  query 4; still undecided: 560, sample size is: 260
+  sampling from both directions
+  searching: 5 queries
+  query 5; still undecided: 300, sample size is: 200
+  5 total queries
+  common heads: 3ee37d65064a
+