# HG changeset patch
# User Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
# Date 1308085080 -7200
# Node ID f03c82d1f50acbc368a7b1b9bb16a9e1cd169b59
# Parent  e7c9fdbbb9020424dcb0f26367a9b9c19b035a39
setdiscovery: batch heads and known(ownheads)

This means that we now discover both subset conditions (local<remote and
remote<local) in a single roundtrip without ever constructing an actual
sample (which takes a bit of client CPU).

diff -r e7c9fdbbb902 -r f03c82d1f50a mercurial/setdiscovery.py
--- a/mercurial/setdiscovery.py	Tue Jun 14 22:56:20 2011 +0200
+++ b/mercurial/setdiscovery.py	Tue Jun 14 22:58:00 2011 +0200
@@ -91,15 +91,27 @@
     roundtrips = 0
     cl = local.changelog
     dag = dagutil.revlogdag(cl)
-    nodes = dag.nodeset()
 
-    # early exit if we know all the specified server heads already
+    # early exit if we know all the specified remote heads already
     ui.debug("query 1; heads\n")
     roundtrips += 1
-    srvheadhashes = remote.heads()
-
-    ## TODO We might want to request an additional random sample of the server's
-    ## nodes batched with the heads query here.
+    ownheads = dag.heads()
+    sample = ownheads
+    if remote.local():
+        # stopgap until we have a proper localpeer that supports batch()
+        srvheadhashes = remote.heads()
+        yesno = remote.known(dag.externalizeall(sample))
+    elif remote.capable('batch'):
+        batch = remote.batch()
+        srvheadhashesref = batch.heads()
+        yesnoref = batch.known(dag.externalizeall(sample))
+        batch.submit()
+        srvheadhashes = srvheadhashesref.value
+        yesno = yesnoref.value
+    else:
+        # compatibitity with pre-batch, but post-known remotes during 1.9 devel
+        srvheadhashes = remote.heads()
+        sample = []
 
     if cl.tip() == nullid:
         if srvheadhashes != [nullid]:
@@ -115,46 +127,48 @@
         ui.note("all remote heads known locally\n")
         return (srvheadhashes, False, srvheadhashes,)
 
+    if sample and util.all(yesno):
+        ui.note("all local heads known remotely\n")
+        ownheadhashes = dag.externalizeall(ownheads)
+        return (ownheadhashes, True, srvheadhashes,)
+
     # full blown discovery
-    undecided = nodes # own nodes where I don't know if the server knows them
+    undecided = dag.nodeset() # own nodes where I don't know if remote knows them
     common = set() # own nodes I know we both know
-    missing = set() # own nodes I know the server lacks
+    missing = set() # own nodes I know remote lacks
 
-    # treat remote heads as a first implicit sample response
+    # treat remote heads (and maybe own heads) as a first implicit sample response
     common.update(dag.ancestorset(srvheads))
     undecided.difference_update(common)
-    # use cheapish initial sample
-    if common:
-        ui.debug("taking initial sample\n")
-        sample = _takefullsample(dag, undecided, size=fullsamplesize)
-    else:
-        ui.debug("taking quick initial sample\n")
-        sample = _takequicksample(dag, nodes, size=initialsamplesize,
-                                  initial=True)
+
+    full = False
+    while undecided:
 
-    roundtrips += 1
-    ui.progress(_('searching'), roundtrips, unit=_('queries'))
-    ui.debug("query %i; still undecided: %i, sample size is: %i\n"
-             % (roundtrips, len(undecided), len(sample)))
-    # indices between sample and externalized version must match
-    sample = list(sample)
-    yesno = remote.known(dag.externalizeall(sample))
+        if sample:
+            commoninsample = set(n for i, n in enumerate(sample) if yesno[i])
+            common.update(dag.ancestorset(commoninsample, common))
 
-    while undecided:
-        commoninsample = set(n for i, n in enumerate(sample) if yesno[i])
-        common.update(dag.ancestorset(commoninsample, common))
+            missinginsample = [n for i, n in enumerate(sample) if not yesno[i]]
+            missing.update(dag.descendantset(missinginsample, missing))
 
-        missinginsample = [n for i, n in enumerate(sample) if not yesno[i]]
-        missing.update(dag.descendantset(missinginsample, missing))
-
-        undecided.difference_update(missing)
-        undecided.difference_update(common)
+            undecided.difference_update(missing)
+            undecided.difference_update(common)
 
         if not undecided:
             break
 
-        ui.note("sampling from both directions\n")
-        sample = _takefullsample(dag, undecided, size=fullsamplesize)
+        if full:
+            ui.note("sampling from both directions\n")
+            sample = _takefullsample(dag, undecided, size=fullsamplesize)
+        elif common:
+            # use cheapish initial sample
+            ui.debug("taking initial sample\n")
+            sample = _takefullsample(dag, undecided, size=fullsamplesize)
+        else:
+            # use even cheaper initial sample
+            ui.debug("taking quick initial sample\n")
+            sample = _takequicksample(dag, undecided, size=initialsamplesize,
+                                      initial=True)
 
         roundtrips += 1
         ui.progress(_('searching'), roundtrips, unit=_('queries'))
@@ -163,6 +177,7 @@
         # indices between sample and externalized version must match
         sample = list(sample)
         yesno = remote.known(dag.externalizeall(sample))
+        full = True
 
     result = dag.headsetofconnecteds(common)
     ui.progress(_('searching'), None)
diff -r e7c9fdbbb902 -r f03c82d1f50a tests/test-http-proxy.t
--- a/tests/test-http-proxy.t	Tue Jun 14 22:56:20 2011 +0200
+++ b/tests/test-http-proxy.t	Tue Jun 14 22:58:00 2011 +0200
@@ -102,19 +102,19 @@
   * - - [*] "GET http://localhost:$HGPORT/?cmd=stream_out HTTP/1.1" - - (glob)
   * - - [*] "GET http://localhost:$HGPORT/?cmd=listkeys HTTP/1.1" - - x-hgarg-1:namespace=bookmarks (glob)
   * - - [*] "GET http://localhost:$HGPORT/?cmd=capabilities HTTP/1.1" - - (glob)
-  * - - [*] "GET http://localhost:$HGPORT/?cmd=heads HTTP/1.1" - - (glob)
+  * - - [*] "GET http://localhost:$HGPORT/?cmd=batch HTTP/1.1" - - x-hgarg-1:cmds=heads+%3Bknown+nodes%3D (glob)
   * - - [*] "GET http://localhost:$HGPORT/?cmd=getbundle HTTP/1.1" - - x-hgarg-1:common=0000000000000000000000000000000000000000&heads=83180e7845de420a1bb46896fd5fe05294f8d629 (glob)
   * - - [*] "GET http://localhost:$HGPORT/?cmd=listkeys HTTP/1.1" - - x-hgarg-1:namespace=bookmarks (glob)
   * - - [*] "GET http://localhost:$HGPORT/?cmd=capabilities HTTP/1.1" - - (glob)
-  * - - [*] "GET http://localhost:$HGPORT/?cmd=heads HTTP/1.1" - - (glob)
+  * - - [*] "GET http://localhost:$HGPORT/?cmd=batch HTTP/1.1" - - x-hgarg-1:cmds=heads+%3Bknown+nodes%3D (glob)
   * - - [*] "GET http://localhost:$HGPORT/?cmd=getbundle HTTP/1.1" - - x-hgarg-1:common=0000000000000000000000000000000000000000&heads=83180e7845de420a1bb46896fd5fe05294f8d629 (glob)
   * - - [*] "GET http://localhost:$HGPORT/?cmd=listkeys HTTP/1.1" - - x-hgarg-1:namespace=bookmarks (glob)
   * - - [*] "GET http://localhost:$HGPORT/?cmd=capabilities HTTP/1.1" - - (glob)
-  * - - [*] "GET http://localhost:$HGPORT/?cmd=heads HTTP/1.1" - - (glob)
+  * - - [*] "GET http://localhost:$HGPORT/?cmd=batch HTTP/1.1" - - x-hgarg-1:cmds=heads+%3Bknown+nodes%3D (glob)
   * - - [*] "GET http://localhost:$HGPORT/?cmd=getbundle HTTP/1.1" - - x-hgarg-1:common=0000000000000000000000000000000000000000&heads=83180e7845de420a1bb46896fd5fe05294f8d629 (glob)
   * - - [*] "GET http://localhost:$HGPORT/?cmd=listkeys HTTP/1.1" - - x-hgarg-1:namespace=bookmarks (glob)
   * - - [*] "GET http://localhost:$HGPORT/?cmd=capabilities HTTP/1.1" - - (glob)
-  * - - [*] "GET http://localhost:$HGPORT/?cmd=heads HTTP/1.1" - - (glob)
+  * - - [*] "GET http://localhost:$HGPORT/?cmd=batch HTTP/1.1" - - x-hgarg-1:cmds=heads+%3Bknown+nodes%3D (glob)
   * - - [*] "GET http://localhost:$HGPORT/?cmd=getbundle HTTP/1.1" - - x-hgarg-1:common=0000000000000000000000000000000000000000&heads=83180e7845de420a1bb46896fd5fe05294f8d629 (glob)
   * - - [*] "GET http://localhost:$HGPORT/?cmd=listkeys HTTP/1.1" - - x-hgarg-1:namespace=bookmarks (glob)
 
diff -r e7c9fdbbb902 -r f03c82d1f50a tests/test-push-warn.t
--- a/tests/test-push-warn.t	Tue Jun 14 22:56:20 2011 +0200
+++ b/tests/test-push-warn.t	Tue Jun 14 22:58:00 2011 +0200
@@ -35,7 +35,7 @@
   searching for changes
   taking quick initial sample
   searching: 2 queries
-  query 2; still undecided: 2, sample size is: 2
+  query 2; still undecided: 1, sample size is: 1
   2 total queries
   new remote heads on branch 'default'
   new remote head 1e108cc5548c
diff -r e7c9fdbbb902 -r f03c82d1f50a tests/test-schemes.t
--- a/tests/test-schemes.t	Tue Jun 14 22:56:20 2011 +0200
+++ b/tests/test-schemes.t	Tue Jun 14 22:58:00 2011 +0200
@@ -28,7 +28,7 @@
   sending capabilities command
   comparing with parts://localhost/
   query 1; heads
-  sending heads command
+  sending batch command
   searching for changes
   all remote heads known locally
   no changes found
diff -r e7c9fdbbb902 -r f03c82d1f50a tests/test-setdiscovery.t
--- a/tests/test-setdiscovery.t	Tue Jun 14 22:56:20 2011 +0200
+++ b/tests/test-setdiscovery.t	Tue Jun 14 22:58:00 2011 +0200
@@ -44,10 +44,7 @@
   comparing with b
   query 1; heads
   searching for changes
-  taking initial sample
-  searching: 2 queries
-  query 2; still undecided: 4, sample size is: 4
-  2 total queries
+  all local heads known remotely
   common heads: b5714e113bc0 01241442b3c2
   local is subset
   
@@ -83,9 +80,9 @@
   comparing with b
   query 1; heads
   searching for changes
-  taking quick initial sample
+  taking initial sample
   searching: 2 queries
-  query 2; still undecided: 35, sample size is: 35
+  query 2; still undecided: 29, sample size is: 29
   2 total queries
   common heads: bebd167eb94d
   
@@ -101,7 +98,7 @@
   searching for changes
   taking initial sample
   searching: 2 queries
-  query 2; still undecided: 3, sample size is: 3
+  query 2; still undecided: 2, sample size is: 2
   2 total queries
   common heads: bebd167eb94d
 
@@ -122,9 +119,9 @@
   comparing with b
   query 1; heads
   searching for changes
-  taking quick initial sample
+  taking initial sample
   searching: 2 queries
-  query 2; still undecided: 34, sample size is: 34
+  query 2; still undecided: 29, sample size is: 29
   2 total queries
   common heads: 2dc09a01254d
   
@@ -140,7 +137,7 @@
   searching for changes
   taking initial sample
   searching: 2 queries
-  query 2; still undecided: 30, sample size is: 30
+  query 2; still undecided: 29, sample size is: 29
   2 total queries
   common heads: 2dc09a01254d
 
@@ -163,7 +160,7 @@
   searching for changes
   taking quick initial sample
   searching: 2 queries
-  query 2; still undecided: 32, sample size is: 32
+  query 2; still undecided: 31, sample size is: 31
   2 total queries
   common heads: 66f7d451a68b
   
@@ -179,7 +176,7 @@
   searching for changes
   taking quick initial sample
   searching: 2 queries
-  query 2; still undecided: 32, sample size is: 32
+  query 2; still undecided: 31, sample size is: 31
   2 total queries
   common heads: 66f7d451a68b
 
@@ -202,7 +199,7 @@
   searching for changes
   taking quick initial sample
   searching: 2 queries
-  query 2; still undecided: 52, sample size is: 52
+  query 2; still undecided: 51, sample size is: 51
   2 total queries
   common heads: 66f7d451a68b
   
@@ -218,7 +215,7 @@
   searching for changes
   taking quick initial sample
   searching: 2 queries
-  query 2; still undecided: 32, sample size is: 32
+  query 2; still undecided: 31, sample size is: 31
   2 total queries
   common heads: 66f7d451a68b
 
@@ -241,7 +238,7 @@
   searching for changes
   taking quick initial sample
   searching: 2 queries
-  query 2; still undecided: 1050, sample size is: 11
+  query 2; still undecided: 1049, sample size is: 11
   sampling from both directions
   searching: 3 queries
   query 3; still undecided: 31, sample size is: 31
@@ -260,7 +257,7 @@
   searching for changes
   taking quick initial sample
   searching: 2 queries
-  query 2; still undecided: 1030, sample size is: 11
+  query 2; still undecided: 1029, sample size is: 11
   sampling from both directions
   searching: 3 queries
   query 3; still undecided: 16, sample size is: 16