995 

   996     # branchlookup returns a dict giving a list of branches for

   997     # each head.  A branch is defined as the tag of a node or

   998     # the branch of the node's parents.  If a node has multiple

   999     # branch tags, tags are eliminated if they are visible from other

  1000     # branch tags.

  1001     #

  1002     # So, for this graph:  a->b->c->d->e

  1003     #                       \         /

  1004     #                        aa -----/

  1005     # a has tag 2.6.12

  1006     # d has tag 2.6.13

  1007     # e would have branch tags for 2.6.12 and 2.6.13.  Because the node

  1008     # for 2.6.12 can be reached from the node 2.6.13, that is eliminated

  1009     # from the list.

  1010     #

  1011     # It is possible that more than one head will have the same branch tag.

  1012     # callers need to check the result for multiple heads under the same

  1013     # branch tag if that is a problem for them (ie checkout of a specific

  1014     # branch).

  1015     #

  1016     # passing in a specific branch will limit the depth of the search

  1017     # through the parents.  It won't limit the branches returned in the

  1018     # result though.

  1019     def branchlookup(self, heads=None, branch=None):

  1020         if not heads:

  1021             heads = self.heads()

  1022         headt = [ h for h in heads ]

  1023         chlog = self.changelog

  1024         branches = {}

  1025         merges = []

  1026         seenmerge = {}

  1027 

  1028         # traverse the tree once for each head, recording in the branches

  1029         # dict which tags are visible from this head.  The branches

  1030         # dict also records which tags are visible from each tag

  1031         # while we traverse.

  1032         while headt or merges:

  1033             if merges:

  1034                 n, found = merges.pop()

  1035                 visit = [n]

  1036             else:

  1037                 h = headt.pop()

  1038                 visit = [h]

  1039                 found = [h]

  1040                 seen = {}

  1041             while visit:

  1042                 n = visit.pop()

  1043                 if n in seen:

  1044                     continue

  1045                 pp = chlog.parents(n)

  1046                 tags = self.nodetags(n)

  1047                 if tags:

  1048                     for x in tags:

  1049                         if x == 'tip':

  1050                             continue

  1051                         for f in found:

  1052                             branches.setdefault(f, {})[n] = 1

  1053                         branches.setdefault(n, {})[n] = 1

  1054                         break

  1055                     if n not in found:

  1056                         found.append(n)

  1057                     if branch in tags:

  1058                         continue

  1059                 seen[n] = 1

  1060                 if pp[1] != nullid and n not in seenmerge:

  1061                     merges.append((pp[1], [x for x in found]))

  1062                     seenmerge[n] = 1

  1063                 if pp[0] != nullid:

  1064                     visit.append(pp[0])

  1065         # traverse the branches dict, eliminating branch tags from each

  1066         # head that are visible from another branch tag for that head.

  1067         out = {}

  1068         viscache = {}

  1069         for h in heads:

  1070             def visible(node):

  1071                 if node in viscache:

  1072                     return viscache[node]

  1073                 ret = {}

  1074                 visit = [node]

  1075                 while visit:

  1076                     x = visit.pop()

  1077                     if x in viscache:

  1078                         ret.update(viscache[x])

  1079                     elif x not in ret:

  1080                         ret[x] = 1

  1081                         if x in branches:

  1082                             visit[len(visit):] = branches[x].keys()

  1083                 viscache[node] = ret

  1084                 return ret

  1085             if h not in branches:

  1086                 continue

  1087             # O(n^2), but somewhat limited.  This only searches the

  1088             # tags visible from a specific head, not all the tags in the

  1089             # whole repo.

  1090             for b in branches[h]:

  1091                 vis = False

  1092                 for bb in branches[h].keys():

  1093                     if b != bb:

  1094                         if b in visible(bb):

  1095                             vis = True

  1096                             break

  1097                 if not vis:

  1098                     l = out.setdefault(h, [])

  1099                     l[len(l):] = self.nodetags(b)

  1100         return out