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

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

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

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

  1079     # branch tags.

  1080     #

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

  1082     #                       \         /

  1083     #                        aa -----/

  1084     # a has tag 2.6.12                     

  1085     # d has tag 2.6.13

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

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

  1088     # from the list.

  1089     #

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

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

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

  1093     # branch).

  1094     #

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

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

  1097     # result though.

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

  1099         if not heads:

  1100             heads = self.heads()

  1101         headt = [ h for h in heads ]

  1102         chlog = self.changelog

  1103         branches = {}

  1104         merges = []

  1105         seenmerge = {}

  1106 

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

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

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

  1110         # while we traverse.

  1111         while headt or merges:

  1112             if merges:

  1113                 n, found = merges.pop()

  1114                 visit = [n]

  1115             else:

  1116                 h = headt.pop()

  1117                 visit = [h]

  1118                 found = [h]

  1119                 seen = {}

  1120             while visit:

  1121                 n = visit.pop()

  1122                 if n in seen:

  1123                     continue

  1124                 pp = chlog.parents(n)

  1125                 tags = self.nodetags(n)

  1126                 if tags:

  1127                     for x in tags:

  1128                         if x == 'tip':

  1129                             continue

  1130                         for f in found:

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

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

  1133                         break

  1134                     if n not in found:

  1135                         found.append(n)

  1136                     if branch in tags:

  1137                         continue

  1138                 seen[n] = 1

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

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

  1141                     seenmerge[n] = 1

  1142                 if pp[0] != nullid:

  1143                     visit.append(pp[0])

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

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

  1146         out = {}

  1147         viscache = {}

  1148         for h in heads:

  1149             def visible(node):

  1150                 if node in viscache:

  1151                     return viscache[node]

  1152                 ret = {}

  1153                 visit = [node]

  1154                 while visit:

  1155                     x = visit.pop()

  1156                     if x in viscache:

  1157                         ret.update(viscache[x])

  1158                     elif x not in ret:

  1159                         ret[x] = 1

  1160                         if x in branches:

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

  1162                 viscache[node] = ret

  1163                 return ret

  1164             if h not in branches:

  1165                 continue

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

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

  1168             # whole repo.

  1169             for b in branches[h]:

  1170                 vis = False

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

  1172                     if b != bb:

  1173                         if b in visible(bb):

  1174                             vis = True

  1175                             break

  1176                 if not vis:

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

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

  1179         return out

  1180