diff -r 5ff1fc726848 -r c6bca38c1cbf eggs/mercurial-1.7.3-py2.6-linux-x86_64.egg/mercurial/discovery.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/eggs/mercurial-1.7.3-py2.6-linux-x86_64.egg/mercurial/discovery.py	Sat Jan 08 11:20:57 2011 +0530
@@ -0,0 +1,308 @@
+# discovery.py - protocol changeset discovery functions
+#
+# Copyright 2010 Matt Mackall <mpm@selenic.com>
+#
+# This software may be used and distributed according to the terms of the
+# GNU General Public License version 2 or any later version.
+
+from node import nullid, short
+from i18n import _
+import util, error
+
+def findcommonincoming(repo, remote, heads=None, force=False):
+    """Return a tuple (common, missing roots, heads) used to identify
+    missing nodes from remote.
+
+    If a list of heads is specified, return only nodes which are heads
+    or ancestors of these 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"))
+
+    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
+
+            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)
+
+    # 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
+
+def findoutgoing(repo, remote, base=None, remoteheads=None, force=False):
+    """Return list of nodes that are roots of subsets not in remote
+
+    If base dict is specified, assume that these nodes and their parents
+    exist on the remote side.
+    If remotehead is specified, assume it is the list of the heads from
+    the remote repository.
+    """
+    if base is None:
+        base = findcommonincoming(repo, remote, heads=remoteheads,
+                                  force=force)[0]
+    else:
+        base = list(base)
+
+    repo.ui.debug("common changesets up to "
+                  + " ".join(map(short, base)) + "\n")
+
+    remain = set(repo.changelog.nodemap)
+
+    # prune everything remote has from the tree
+    remain.remove(nullid)
+    remove = base
+    while remove:
+        n = remove.pop(0)
+        if n in remain:
+            remain.remove(n)
+            for p in repo.changelog.parents(n):
+                remove.append(p)
+
+    # find every node whose parents have been pruned
+    subset = []
+    # find every remote head that will get new children
+    for n in remain:
+        p1, p2 = repo.changelog.parents(n)
+        if p1 not in remain and p2 not in remain:
+            subset.append(n)
+
+    return subset
+
+def prepush(repo, remote, force, revs, newbranch):
+    '''Analyze the local and remote repositories and determine which
+    changesets need to be pushed to the remote. Return value depends
+    on circumstances:
+
+    If we are not going to push anything, return a tuple (None,
+    outgoing) where outgoing is 0 if there are no outgoing
+    changesets and 1 if there are, but we refuse to push them
+    (e.g. would create new remote heads).
+
+    Otherwise, return a tuple (changegroup, remoteheads), where
+    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)
+
+    cl = repo.changelog
+    update = findoutgoing(repo, remote, common, remoteheads)
+    outg, bases, heads = cl.nodesbetween(update, revs)
+
+    if not bases:
+        repo.ui.status(_("no changes found\n"))
+        return None, 1
+
+    if not force and remoteheads != [nullid]:
+        if remote.capable('branchmap'):
+            # Check for each named branch if we're creating new remote heads.
+            # To be a remote head after push, node must be either:
+            # - unknown locally
+            # - a local outgoing head descended from update
+            # - a remote head that's known locally and not
+            #   ancestral to an outgoing head
+            #
+            # New named branches cannot be created without --force.
+
+            # 1. Create set of branches involved in the push.
+            branches = set(repo[n].branch() for n in outg)
+
+            # 2. Check for new branches on the remote.
+            remotemap = remote.branchmap()
+            newbranches = branches - set(remotemap)
+            if newbranches and not newbranch: # new branch requires --new-branch
+                branchnames = ', '.join(sorted(newbranches))
+                raise util.Abort(_("push creates new remote branches: %s!")
+                                   % branchnames,
+                                 hint=_("use 'hg push --new-branch' to create"
+                                        " new remote branches"))
+            branches.difference_update(newbranches)
+
+            # 3. Construct the initial oldmap and newmap dicts.
+            # They contain information about the remote heads before and
+            # after the push, respectively.
+            # Heads not found locally are not included in either dict,
+            # since they won't be affected by the push.
+            # unsynced contains all branches with incoming changesets.
+            oldmap = {}
+            newmap = {}
+            unsynced = set()
+            for branch in branches:
+                remotebrheads = remotemap[branch]
+                prunedbrheads = [h for h in remotebrheads if h in cl.nodemap]
+                oldmap[branch] = prunedbrheads
+                newmap[branch] = list(prunedbrheads)
+                if len(remotebrheads) > len(prunedbrheads):
+                    unsynced.add(branch)
+
+            # 4. Update newmap with outgoing changes.
+            # This will possibly add new heads and remove existing ones.
+            ctxgen = (repo[n] for n in outg)
+            repo._updatebranchcache(newmap, ctxgen)
+
+        else:
+            # 1-4b. old servers: Check for new topological heads.
+            # Construct {old,new}map with branch = None (topological branch).
+            # (code based on _updatebranchcache)
+            oldheads = set(h for h in remoteheads if h in cl.nodemap)
+            newheads = oldheads.union(outg)
+            if len(newheads) > 1:
+                for latest in reversed(outg):
+                    if latest not in newheads:
+                        continue
+                    minhrev = min(cl.rev(h) for h in newheads)
+                    reachable = cl.reachable(latest, cl.node(minhrev))
+                    reachable.remove(latest)
+                    newheads.difference_update(reachable)
+            branches = set([None])
+            newmap = {None: newheads}
+            oldmap = {None: oldheads}
+            unsynced = inc and branches or set()
+
+        # 5. Check for new heads.
+        # If there are more heads after the push than before, a suitable
+        # warning, depending on unsynced status, is displayed.
+        for branch in branches:
+            if len(newmap[branch]) > len(oldmap[branch]):
+                if branch:
+                    msg = _("push creates new remote heads "
+                            "on branch '%s'!") % branch
+                else:
+                    msg = _("push creates new remote heads!")
+
+                if branch in unsynced:
+                    hint = _("you should pull and merge or use push -f to force")
+                else:
+                    hint = _("did you forget to merge? use push -f to force")
+                raise util.Abort(msg, hint=hint)
+
+        # 6. Check for unsynced changes on involved branches.
+        if unsynced:
+            repo.ui.warn(_("note: unsynced remote changes!\n"))
+
+    if revs is None:
+        # use the fast path, no race possible on push
+        nodes = repo.changelog.findmissing(common)
+        cg = repo._changegroup(nodes, 'push')
+    else:
+        cg = repo.changegroupsubset(update, revs, 'push')
+    return cg, remoteheads