Mercurial > hg
comparison mercurial/obsolete.py @ 33142:4f49810a1011
obsutil: move 'successorssets' to the new modules
We have a new 'obsutil' module now. We move this high level utility there to bring
'obsolete.py' back to a more reasonable size.
author | Pierre-Yves David <pierre-yves.david@octobus.net> |
---|---|
date | Tue, 27 Jun 2017 01:03:01 +0200 |
parents | 31ab1912678a |
children | d09ae850296d |
comparison
equal
deleted
inserted
replaced
33140:f458a6701983 | 33142:4f49810a1011 |
---|---|
74 | 74 |
75 from .i18n import _ | 75 from .i18n import _ |
76 from . import ( | 76 from . import ( |
77 error, | 77 error, |
78 node, | 78 node, |
79 obsutil, | |
79 phases, | 80 phases, |
80 policy, | 81 policy, |
81 util, | 82 util, |
82 ) | 83 ) |
83 | 84 |
1060 succs.update(allsuccessors(repo.obsstore, mutable)) | 1061 succs.update(allsuccessors(repo.obsstore, mutable)) |
1061 known = (n for n in succs if n in nm) | 1062 known = (n for n in succs if n in nm) |
1062 foreground = set(repo.set('%ln::', known)) | 1063 foreground = set(repo.set('%ln::', known)) |
1063 return set(c.node() for c in foreground) | 1064 return set(c.node() for c in foreground) |
1064 | 1065 |
1065 | |
1066 def successorssets(repo, initialnode, cache=None): | 1066 def successorssets(repo, initialnode, cache=None): |
1067 """Return set of all latest successors of initial nodes | 1067 movemsg = 'obsolete.successorssets moved to obsutil.successorssets' |
1068 | 1068 repo.ui.deprecwarn(movemsg, '4.3') |
1069 The successors set of a changeset A are the group of revisions that succeed | 1069 return obsutil.successorssets(repo, initialnode, cache=cache) |
1070 A. It succeeds A as a consistent whole, each revision being only a partial | |
1071 replacement. The successors set contains non-obsolete changesets only. | |
1072 | |
1073 This function returns the full list of successor sets which is why it | |
1074 returns a list of tuples and not just a single tuple. Each tuple is a valid | |
1075 successors set. Note that (A,) may be a valid successors set for changeset A | |
1076 (see below). | |
1077 | |
1078 In most cases, a changeset A will have a single element (e.g. the changeset | |
1079 A is replaced by A') in its successors set. Though, it is also common for a | |
1080 changeset A to have no elements in its successor set (e.g. the changeset | |
1081 has been pruned). Therefore, the returned list of successors sets will be | |
1082 [(A',)] or [], respectively. | |
1083 | |
1084 When a changeset A is split into A' and B', however, it will result in a | |
1085 successors set containing more than a single element, i.e. [(A',B')]. | |
1086 Divergent changesets will result in multiple successors sets, i.e. [(A',), | |
1087 (A'')]. | |
1088 | |
1089 If a changeset A is not obsolete, then it will conceptually have no | |
1090 successors set. To distinguish this from a pruned changeset, the successor | |
1091 set will contain itself only, i.e. [(A,)]. | |
1092 | |
1093 Finally, successors unknown locally are considered to be pruned (obsoleted | |
1094 without any successors). | |
1095 | |
1096 The optional `cache` parameter is a dictionary that may contain precomputed | |
1097 successors sets. It is meant to reuse the computation of a previous call to | |
1098 `successorssets` when multiple calls are made at the same time. The cache | |
1099 dictionary is updated in place. The caller is responsible for its life | |
1100 span. Code that makes multiple calls to `successorssets` *must* use this | |
1101 cache mechanism or suffer terrible performance. | |
1102 """ | |
1103 | |
1104 succmarkers = repo.obsstore.successors | |
1105 | |
1106 # Stack of nodes we search successors sets for | |
1107 toproceed = [initialnode] | |
1108 # set version of above list for fast loop detection | |
1109 # element added to "toproceed" must be added here | |
1110 stackedset = set(toproceed) | |
1111 if cache is None: | |
1112 cache = {} | |
1113 | |
1114 # This while loop is the flattened version of a recursive search for | |
1115 # successors sets | |
1116 # | |
1117 # def successorssets(x): | |
1118 # successors = directsuccessors(x) | |
1119 # ss = [[]] | |
1120 # for succ in directsuccessors(x): | |
1121 # # product as in itertools cartesian product | |
1122 # ss = product(ss, successorssets(succ)) | |
1123 # return ss | |
1124 # | |
1125 # But we can not use plain recursive calls here: | |
1126 # - that would blow the python call stack | |
1127 # - obsolescence markers may have cycles, we need to handle them. | |
1128 # | |
1129 # The `toproceed` list act as our call stack. Every node we search | |
1130 # successors set for are stacked there. | |
1131 # | |
1132 # The `stackedset` is set version of this stack used to check if a node is | |
1133 # already stacked. This check is used to detect cycles and prevent infinite | |
1134 # loop. | |
1135 # | |
1136 # successors set of all nodes are stored in the `cache` dictionary. | |
1137 # | |
1138 # After this while loop ends we use the cache to return the successors sets | |
1139 # for the node requested by the caller. | |
1140 while toproceed: | |
1141 # Every iteration tries to compute the successors sets of the topmost | |
1142 # node of the stack: CURRENT. | |
1143 # | |
1144 # There are four possible outcomes: | |
1145 # | |
1146 # 1) We already know the successors sets of CURRENT: | |
1147 # -> mission accomplished, pop it from the stack. | |
1148 # 2) Node is not obsolete: | |
1149 # -> the node is its own successors sets. Add it to the cache. | |
1150 # 3) We do not know successors set of direct successors of CURRENT: | |
1151 # -> We add those successors to the stack. | |
1152 # 4) We know successors sets of all direct successors of CURRENT: | |
1153 # -> We can compute CURRENT successors set and add it to the | |
1154 # cache. | |
1155 # | |
1156 current = toproceed[-1] | |
1157 if current in cache: | |
1158 # case (1): We already know the successors sets | |
1159 stackedset.remove(toproceed.pop()) | |
1160 elif current not in succmarkers: | |
1161 # case (2): The node is not obsolete. | |
1162 if current in repo: | |
1163 # We have a valid last successors. | |
1164 cache[current] = [(current,)] | |
1165 else: | |
1166 # Final obsolete version is unknown locally. | |
1167 # Do not count that as a valid successors | |
1168 cache[current] = [] | |
1169 else: | |
1170 # cases (3) and (4) | |
1171 # | |
1172 # We proceed in two phases. Phase 1 aims to distinguish case (3) | |
1173 # from case (4): | |
1174 # | |
1175 # For each direct successors of CURRENT, we check whether its | |
1176 # successors sets are known. If they are not, we stack the | |
1177 # unknown node and proceed to the next iteration of the while | |
1178 # loop. (case 3) | |
1179 # | |
1180 # During this step, we may detect obsolescence cycles: a node | |
1181 # with unknown successors sets but already in the call stack. | |
1182 # In such a situation, we arbitrary set the successors sets of | |
1183 # the node to nothing (node pruned) to break the cycle. | |
1184 # | |
1185 # If no break was encountered we proceed to phase 2. | |
1186 # | |
1187 # Phase 2 computes successors sets of CURRENT (case 4); see details | |
1188 # in phase 2 itself. | |
1189 # | |
1190 # Note the two levels of iteration in each phase. | |
1191 # - The first one handles obsolescence markers using CURRENT as | |
1192 # precursor (successors markers of CURRENT). | |
1193 # | |
1194 # Having multiple entry here means divergence. | |
1195 # | |
1196 # - The second one handles successors defined in each marker. | |
1197 # | |
1198 # Having none means pruned node, multiple successors means split, | |
1199 # single successors are standard replacement. | |
1200 # | |
1201 for mark in sorted(succmarkers[current]): | |
1202 for suc in mark[1]: | |
1203 if suc not in cache: | |
1204 if suc in stackedset: | |
1205 # cycle breaking | |
1206 cache[suc] = [] | |
1207 else: | |
1208 # case (3) If we have not computed successors sets | |
1209 # of one of those successors we add it to the | |
1210 # `toproceed` stack and stop all work for this | |
1211 # iteration. | |
1212 toproceed.append(suc) | |
1213 stackedset.add(suc) | |
1214 break | |
1215 else: | |
1216 continue | |
1217 break | |
1218 else: | |
1219 # case (4): we know all successors sets of all direct | |
1220 # successors | |
1221 # | |
1222 # Successors set contributed by each marker depends on the | |
1223 # successors sets of all its "successors" node. | |
1224 # | |
1225 # Each different marker is a divergence in the obsolescence | |
1226 # history. It contributes successors sets distinct from other | |
1227 # markers. | |
1228 # | |
1229 # Within a marker, a successor may have divergent successors | |
1230 # sets. In such a case, the marker will contribute multiple | |
1231 # divergent successors sets. If multiple successors have | |
1232 # divergent successors sets, a Cartesian product is used. | |
1233 # | |
1234 # At the end we post-process successors sets to remove | |
1235 # duplicated entry and successors set that are strict subset of | |
1236 # another one. | |
1237 succssets = [] | |
1238 for mark in sorted(succmarkers[current]): | |
1239 # successors sets contributed by this marker | |
1240 markss = [[]] | |
1241 for suc in mark[1]: | |
1242 # cardinal product with previous successors | |
1243 productresult = [] | |
1244 for prefix in markss: | |
1245 for suffix in cache[suc]: | |
1246 newss = list(prefix) | |
1247 for part in suffix: | |
1248 # do not duplicated entry in successors set | |
1249 # first entry wins. | |
1250 if part not in newss: | |
1251 newss.append(part) | |
1252 productresult.append(newss) | |
1253 markss = productresult | |
1254 succssets.extend(markss) | |
1255 # remove duplicated and subset | |
1256 seen = [] | |
1257 final = [] | |
1258 candidate = sorted(((set(s), s) for s in succssets if s), | |
1259 key=lambda x: len(x[1]), reverse=True) | |
1260 for setversion, listversion in candidate: | |
1261 for seenset in seen: | |
1262 if setversion.issubset(seenset): | |
1263 break | |
1264 else: | |
1265 final.append(listversion) | |
1266 seen.append(setversion) | |
1267 final.reverse() # put small successors set first | |
1268 cache[current] = final | |
1269 return cache[initialnode] | |
1270 | 1070 |
1271 # mapping of 'set-name' -> <function to compute this set> | 1071 # mapping of 'set-name' -> <function to compute this set> |
1272 cachefuncs = {} | 1072 cachefuncs = {} |
1273 def cachefor(name): | 1073 def cachefor(name): |
1274 """Decorator to register a function as computing the cache for a set""" | 1074 """Decorator to register a function as computing the cache for a set""" |
1389 prec = toprocess.pop()[0] | 1189 prec = toprocess.pop()[0] |
1390 if prec in seen: | 1190 if prec in seen: |
1391 continue # emergency cycle hanging prevention | 1191 continue # emergency cycle hanging prevention |
1392 seen.add(prec) | 1192 seen.add(prec) |
1393 if prec not in newermap: | 1193 if prec not in newermap: |
1394 successorssets(repo, prec, newermap) | 1194 obsutil.successorssets(repo, prec, newermap) |
1395 newer = [n for n in newermap[prec] if n] | 1195 newer = [n for n in newermap[prec] if n] |
1396 if len(newer) > 1: | 1196 if len(newer) > 1: |
1397 divergent.add(ctx.rev()) | 1197 divergent.add(ctx.rev()) |
1398 break | 1198 break |
1399 toprocess.update(obsstore.precursors.get(prec, ())) | 1199 toprocess.update(obsstore.precursors.get(prec, ())) |