--- a/mercurial/discovery.py	Mon May 02 19:21:30 2011 +0200
+++ b/mercurial/discovery.py	Mon May 02 19:21:30 2011 +0200
@@ -7,7 +7,7 @@
 
 from node import nullid, short
 from i18n import _
-import util, error
+import util, error, setdiscovery, treediscovery
 
 def findcommonincoming(repo, remote, heads=None, force=False):
     """Return a tuple (common, anyincoming, heads) used to identify the common
@@ -20,145 +20,28 @@
       changegroupsubset. No code except for pull should be relying on this fact
       any longer.
     "heads" is either the supplied heads, or else the remote's heads.
+
+    If you pass heads and they are all known locally, the reponse lists justs
+    these heads in "common" and in "heads".
     """
 
-    m = repo.changelog.nodemap
-    search = []
-    fetch = set()
-    seen = set()
-    seenbranch = set()
-    base = set()
-
-    if not heads:
-        heads = remote.heads()
-
-    if repo.changelog.tip() == nullid:
-        base.add(nullid)
-        if heads != [nullid]:
-            return [nullid], [nullid], list(heads)
-        return [nullid], [], []
-
-    # assume we're closer to the tip than the root
-    # and start by examining the heads
-    repo.ui.status(_("searching for changes\n"))
-
-    if remote.capable('getbundle'):
-        myheads = repo.heads()
-        known = remote.known(myheads)
-        if util.all(known):
-            hasincoming = set(heads).difference(set(myheads)) and True
-            return myheads, hasincoming, heads
-
-    unknown = []
-    for h in heads:
-        if h not in m:
-            unknown.append(h)
-        else:
-            base.add(h)
-
-    heads = unknown
-    if not unknown:
-        return list(base), [], []
-
-    req = set(unknown)
-    reqcnt = 0
-
-    # search through remote branches
-    # a 'branch' here is a linear segment of history, with four parts:
-    # head, root, first parent, second parent
-    # (a branch always has two parents (or none) by definition)
-    unknown = remote.branches(unknown)
-    while unknown:
-        r = []
-        while unknown:
-            n = unknown.pop(0)
-            if n[0] in seen:
-                continue
+    if not remote.capable('getbundle'):
+        return treediscovery.findcommonincoming(repo, remote, heads, force)
 
-            repo.ui.debug("examining %s:%s\n"
-                          % (short(n[0]), short(n[1])))
-            if n[0] == nullid: # found the end of the branch
-                pass
-            elif n in seenbranch:
-                repo.ui.debug("branch already found\n")
-                continue
-            elif n[1] and n[1] in m: # do we know the base?
-                repo.ui.debug("found incomplete branch %s:%s\n"
-                              % (short(n[0]), short(n[1])))
-                search.append(n[0:2]) # schedule branch range for scanning
-                seenbranch.add(n)
-            else:
-                if n[1] not in seen and n[1] not in fetch:
-                    if n[2] in m and n[3] in m:
-                        repo.ui.debug("found new changeset %s\n" %
-                                      short(n[1]))
-                        fetch.add(n[1]) # earliest unknown
-                    for p in n[2:4]:
-                        if p in m:
-                            base.add(p) # latest known
-
-                for p in n[2:4]:
-                    if p not in req and p not in m:
-                        r.append(p)
-                        req.add(p)
-            seen.add(n[0])
-
-        if r:
-            reqcnt += 1
-            repo.ui.progress(_('searching'), reqcnt, unit=_('queries'))
-            repo.ui.debug("request %d: %s\n" %
-                        (reqcnt, " ".join(map(short, r))))
-            for p in xrange(0, len(r), 10):
-                for b in remote.branches(r[p:p + 10]):
-                    repo.ui.debug("received %s:%s\n" %
-                                  (short(b[0]), short(b[1])))
-                    unknown.append(b)
+    if heads:
+        allknown = True
+        nm = repo.changelog.nodemap
+        for h in heads:
+            if nm.get(h) is None:
+                allknown = False
+                break
+        if allknown:
+            return (heads, False, heads)
 
-    # do binary search on the branches we found
-    while search:
-        newsearch = []
-        reqcnt += 1
-        repo.ui.progress(_('searching'), reqcnt, unit=_('queries'))
-        for n, l in zip(search, remote.between(search)):
-            l.append(n[1])
-            p = n[0]
-            f = 1
-            for i in l:
-                repo.ui.debug("narrowing %d:%d %s\n" % (f, len(l), short(i)))
-                if i in m:
-                    if f <= 2:
-                        repo.ui.debug("found new branch changeset %s\n" %
-                                          short(p))
-                        fetch.add(p)
-                        base.add(i)
-                    else:
-                        repo.ui.debug("narrowed branch search to %s:%s\n"
-                                      % (short(p), short(i)))
-                        newsearch.append((p, i))
-                    break
-                p, f = i, f * 2
-            search = newsearch
-
-    # sanity check our fetch list
-    for f in fetch:
-        if f in m:
-            raise error.RepoError(_("already have changeset ")
-                                  + short(f[:4]))
-
-    base = list(base)
-    if base == [nullid]:
-        if force:
-            repo.ui.warn(_("warning: repository is unrelated\n"))
-        else:
-            raise util.Abort(_("repository is unrelated"))
-
-    repo.ui.debug("found new changesets starting at " +
-                 " ".join([short(f) for f in fetch]) + "\n")
-
-    repo.ui.progress(_('searching'), None)
-    repo.ui.debug("%d total queries\n" % reqcnt)
-
-    return base, list(fetch), heads
+    res = setdiscovery.findcommonheads(repo.ui, repo, remote,
+                                       abortwhenunrelated=not force)
+    common, anyinc, srvheads = res
+    return (list(common), anyinc, heads or list(srvheads))
 
 def prepush(repo, remote, force, revs, newbranch):
     '''Analyze the local and remote repositories and determine which
@@ -174,9 +57,7 @@
     changegroup is a readable file-like object whose read() returns
     successive changegroup chunks ready to be sent over the wire and
     remoteheads is the list of remote heads.'''
-    remoteheads = remote.heads()
-    common, inc, _rheads = findcommonincoming(repo, remote, heads=remoteheads,
-                                              force=force)
+    common, inc, remoteheads = findcommonincoming(repo, remote, force=force)
 
     cl = repo.changelog
     outg = cl.findmissing(common, revs)