--- a/mercurial/hg.py Sun Aug 14 12:23:36 2005 -0800
+++ b/mercurial/hg.py Sun Aug 14 12:23:45 2005 -0800
@@ -1072,6 +1072,112 @@
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 = []