Add searching for named branches

named branching is when you identify a head by a tag on an earlier revision.
This patch adds repo.branchlookup for searching through the tree to
find branch tags for heads.

hg update -b tag is added to checkout based on branch tags
hg heads -b is added to print the tag associated with each head

mercurial/commands.py

@@ -194,7 +194,7 def dodiff(fp, ui, repo, files=None, nod
         tn = None
         fp.write(mdiff.unidiff(to, date1, tn, date2, f, r))
 
-def show_changeset(ui, repo, rev=0, changenode=None, filelog=None):
+def show_changeset(ui, repo, rev=0, changenode=None, filelog=None, brinfo=None):
     """show a single changeset or file revision"""
     changelog = repo.changelog
     if filelog:
@@ -236,6 +236,10 def show_changeset(ui, repo, rev=0, chan
     if filelog:
         ui.debug("file rev:    %d:%s\n" % (filerev, hg.hex(filenode)))
 
+    if brinfo and changenode in brinfo:
+        br = brinfo[changenode]
+        ui.write("branch:      %s\n" % " ".join(br))
+
     ui.debug("manifest:    %d:%s\n" % (repo.manifest.rev(changes[0]),
                                       hg.hex(changes[0])))
     ui.status("user:        %s\n" % changes[1])
@@ -675,10 +679,14 def forget(ui, repo, *pats, **opts):
             if rel not in q: ui.status('forgetting ', rel, '\n')
     repo.forget(forget)
 
-def heads(ui, repo):
+def heads(ui, repo, **opts):
     """show current repository heads"""
+    heads = repo.changelog.heads()
+    br = None
+    if opts['branches']:
+        br = repo.branchlookup(heads)
     for n in repo.changelog.heads():
-        show_changeset(ui, repo, changenode=n)
+        show_changeset(ui, repo, changenode=n, brinfo=br)
 
 def identify(ui, repo):
     """print information about the working copy"""
@@ -1150,7 +1158,7 def undo(ui, repo):
     """
     repo.undo()
 
-def update(ui, repo, node=None, merge=False, clean=False):
+def update(ui, repo, node=None, merge=False, clean=False, branch=None):
     '''update or merge working directory
 
     If there are no outstanding changes in the working directory and
@@ -1163,6 +1171,24 def update(ui, repo, node=None, merge=Fa
     commit and a commit must be performed before any further updates
     are allowed.
     '''
+    if branch:
+        br = repo.branchlookup(branch=branch)
+        found = []
+        for x in br:
+            if branch in br[x]:
+                found.append(x)
+        if len(found) > 1:
+            ui.warn("Found multiple heads for %s\n" % branch)
+            for x in found:
+                show_changeset(ui, repo, changenode=x, brinfo=br)
+            return 1
+        if len(found) == 1:
+            node = found[0]
+            ui.warn("Using head %s for branch %s\n" % (hg.short(node), branch))
+        else:
+            ui.warn("branch %s not found\n" % (branch))
+            return 1
+    else:
     node = node and repo.lookup(node) or repo.changelog.tip()
     return repo.update(node, allow=merge, force=clean)
 
@@ -1236,7 +1262,7 table = {
          [('I', 'include', [], 'include path in search'),
           ('X', 'exclude', [], 'exclude path from search')],
          "hg forget FILE..."),
-    "heads": (heads, [], 'hg heads'),
+    "heads": (heads, [('b', 'branches', None, 'find branch info')], 'hg heads'),
     "help": (help_, [], 'hg help [COMMAND]'),
     "identify|id": (identify, [], 'hg identify'),
     "import|patch":
@@ -1320,7 +1346,8 table = {
     "undo": (undo, [], 'hg undo'),
     "^update|up|checkout|co":
         (update,
-         [('m', 'merge', None, 'allow merging of conflicts'),
+         [('b', 'branch', "", 'checkout the head of a specific branch'),
+          ('m', 'merge', None, 'allow merging of conflicts'),
           ('C', 'clean', None, 'overwrite locally modified files')],
          'hg update [-m] [-C] [REV]'),
     "verify": (verify, [], 'hg verify'),

mercurial/hg.py

@@ -1072,6 +1072,112 class localrepository:
     def heads(self):
         return self.changelog.heads()
 
+    # branchlookup returns a dict giving a list of branches for
+    # each head.  A branch is defined as the tag of a node or
+    # the branch of the node's parents.  If a node has multiple
+    # branch tags, tags are eliminated if they are visible from other
+    # branch tags.
+    #
+    # So, for this graph:  a->b->c->d->e
+    #                       \         /
+    #                        aa -----/
+    # a has tag 2.6.12                     
+    # d has tag 2.6.13
+    # e would have branch tags for 2.6.12 and 2.6.13.  Because the node
+    # for 2.6.12 can be reached from the node 2.6.13, that is eliminated
+    # from the list.
+    #
+    # It is possible that more than one head will have the same branch tag.
+    # callers need to check the result for multiple heads under the same
+    # branch tag if that is a problem for them (ie checkout of a specific
+    # branch).
+    #
+    # passing in a specific branch will limit the depth of the search
+    # through the parents.  It won't limit the branches returned in the
+    # result though.
+    def branchlookup(self, heads=None, branch=None):
+        if not heads:
+            heads = self.heads()
+        headt = [ h for h in heads ]
+        chlog = self.changelog
+        branches = {}
+        merges = []
+        seenmerge = {}
+
+        # traverse the tree once for each head, recording in the branches
+        # dict which tags are visible from this head.  The branches
+        # dict also records which tags are visible from each tag
+        # while we traverse.
+        while headt or merges:
+            if merges:
+                n, found = merges.pop()
+                visit = [n]
+            else:
+                h = headt.pop()
+                visit = [h]
+                found = [h]
+                seen = {}
+            while visit:
+                n = visit.pop()
+                if n in seen:
+                    continue
+                pp = chlog.parents(n)
+                tags = self.nodetags(n)
+                if tags:
+                    for x in tags:
+                        if x == 'tip':
+                            continue
+                        for f in found:
+                            branches.setdefault(f, {})[n] = 1
+                        branches.setdefault(n, {})[n] = 1
+                        break
+                    if n not in found:
+                        found.append(n)
+                    if branch in tags:
+                        continue
+                seen[n] = 1
+                if pp[1] != nullid and n not in seenmerge:
+                    merges.append((pp[1], [x for x in found]))
+                    seenmerge[n] = 1
+                if pp[0] != nullid:
+                    visit.append(pp[0])
+        # traverse the branches dict, eliminating branch tags from each
+        # head that are visible from another branch tag for that head.
+        out = {}
+        viscache = {}
+        for h in heads:
+            def visible(node):
+                if node in viscache:
+                    return viscache[node]
+                ret = {}
+                visit = [node]
+                while visit:
+                    x = visit.pop()
+                    if x in viscache:
+                        ret.update(viscache[x])
+                    elif x not in ret:
+                        ret[x] = 1
+                        if x in branches:
+                            visit[len(visit):] = branches[x].keys()
+                viscache[node] = ret
+                return ret
+            if h not in branches:
+                continue
+            # O(n^2), but somewhat limited.  This only searches the
+            # tags visible from a specific head, not all the tags in the
+            # whole repo.
+            for b in branches[h]:
+                vis = False
+                for bb in branches[h].keys():
+                    if b != bb:
+                        if b in visible(bb):
+                            vis = True
+                            break
+                if not vis:
+                    l = out.setdefault(h, [])
+                    l[len(l):] = self.nodetags(b)
+        return out
+
     def branches(self, nodes):
         if not nodes: nodes = [self.changelog.tip()]
         b = []