Show More
@@ -8,7 +8,129 b'' | |||
|
8 | 8 | import heapq, util |
|
9 | 9 | from node import nullrev |
|
10 | 10 | |
|
11 |
def ancestor( |
|
|
11 | def ancestors(pfunc, *orignodes): | |
|
12 | """ | |
|
13 | Returns the common ancestors of a and b that are furthest from a | |
|
14 | root (as measured by longest path). | |
|
15 | ||
|
16 | pfunc must return a list of parent vertices for a given vertex. | |
|
17 | """ | |
|
18 | if not isinstance(orignodes, set): | |
|
19 | orignodes = set(orignodes) | |
|
20 | if nullrev in orignodes: | |
|
21 | return set() | |
|
22 | if len(orignodes) <= 1: | |
|
23 | return orignodes | |
|
24 | ||
|
25 | def candidates(nodes): | |
|
26 | allseen = (1 << len(nodes)) - 1 | |
|
27 | seen = [0] * (max(nodes) + 1) | |
|
28 | for i, n in enumerate(nodes): | |
|
29 | seen[n] = 1 << i | |
|
30 | poison = 1 << (i + 1) | |
|
31 | ||
|
32 | gca = set() | |
|
33 | interesting = left = len(nodes) | |
|
34 | nv = len(seen) - 1 | |
|
35 | while nv >= 0 and interesting: | |
|
36 | v = nv | |
|
37 | nv -= 1 | |
|
38 | if not seen[v]: | |
|
39 | continue | |
|
40 | sv = seen[v] | |
|
41 | if sv < poison: | |
|
42 | interesting -= 1 | |
|
43 | if sv == allseen: | |
|
44 | gca.add(v) | |
|
45 | sv |= poison | |
|
46 | if v in nodes: | |
|
47 | left -= 1 | |
|
48 | if left <= 1: | |
|
49 | # history is linear | |
|
50 | return set([v]) | |
|
51 | if sv < poison: | |
|
52 | for p in pfunc(v): | |
|
53 | sp = seen[p] | |
|
54 | if p == nullrev: | |
|
55 | continue | |
|
56 | if sp == 0: | |
|
57 | seen[p] = sv | |
|
58 | interesting += 1 | |
|
59 | elif sp != sv: | |
|
60 | seen[p] |= sv | |
|
61 | else: | |
|
62 | for p in pfunc(v): | |
|
63 | if p == nullrev: | |
|
64 | continue | |
|
65 | sp = seen[p] | |
|
66 | if sp and sp < poison: | |
|
67 | interesting -= 1 | |
|
68 | seen[p] = sv | |
|
69 | return gca | |
|
70 | ||
|
71 | def deepest(nodes): | |
|
72 | interesting = {} | |
|
73 | count = max(nodes) + 1 | |
|
74 | depth = [0] * count | |
|
75 | seen = [0] * count | |
|
76 | mapping = [] | |
|
77 | for (i, n) in enumerate(sorted(nodes)): | |
|
78 | depth[n] = 1 | |
|
79 | b = 1 << i | |
|
80 | seen[n] = b | |
|
81 | interesting[b] = 1 | |
|
82 | mapping.append((b, n)) | |
|
83 | nv = count - 1 | |
|
84 | while nv >= 0 and len(interesting) > 1: | |
|
85 | v = nv | |
|
86 | nv -= 1 | |
|
87 | dv = depth[v] | |
|
88 | if dv == 0: | |
|
89 | continue | |
|
90 | sv = seen[v] | |
|
91 | for p in pfunc(v): | |
|
92 | if p == nullrev: | |
|
93 | continue | |
|
94 | dp = depth[p] | |
|
95 | nsp = sp = seen[p] | |
|
96 | if dp <= dv: | |
|
97 | depth[p] = dv + 1 | |
|
98 | if sp != sv: | |
|
99 | interesting[sv] += 1 | |
|
100 | nsp = seen[p] = sv | |
|
101 | if sp: | |
|
102 | interesting[sp] -= 1 | |
|
103 | if interesting[sp] == 0: | |
|
104 | del interesting[sp] | |
|
105 | elif dv == dp - 1: | |
|
106 | nsp = sp | sv | |
|
107 | if nsp == sp: | |
|
108 | continue | |
|
109 | seen[p] = nsp | |
|
110 | interesting.setdefault(nsp, 0) | |
|
111 | interesting[nsp] += 1 | |
|
112 | interesting[sp] -= 1 | |
|
113 | if interesting[sp] == 0: | |
|
114 | del interesting[sp] | |
|
115 | interesting[sv] -= 1 | |
|
116 | if interesting[sv] == 0: | |
|
117 | del interesting[sv] | |
|
118 | ||
|
119 | if len(interesting) != 1: | |
|
120 | return [] | |
|
121 | ||
|
122 | k = 0 | |
|
123 | for i in interesting: | |
|
124 | k |= i | |
|
125 | return set(n for (i, n) in mapping if k & i) | |
|
126 | ||
|
127 | gca = candidates(orignodes) | |
|
128 | ||
|
129 | if len(gca) <= 1: | |
|
130 | return gca | |
|
131 | return deepest(gca) | |
|
132 | ||
|
133 | def genericancestor(a, b, pfunc): | |
|
12 | 134 | """ |
|
13 | 135 | Returns the common ancestor of a and b that is furthest from a |
|
14 | 136 | root (as measured by longest path) or None if no ancestor is |
@@ -30,7 +152,7 b' def ancestor(a, b, pfunc):' | |||
|
30 | 152 | depth = {} |
|
31 | 153 | while visit: |
|
32 | 154 | vertex = visit[-1] |
|
33 | pl = pfunc(vertex) | |
|
155 | pl = [p for p in pfunc(vertex) if p != nullrev] | |
|
34 | 156 | parentcache[vertex] = pl |
|
35 | 157 | if not pl: |
|
36 | 158 | depth[vertex] = 0 |
@@ -756,7 +756,7 b' class filectx(object):' | |||
|
756 | 756 | return pl |
|
757 | 757 | |
|
758 | 758 | a, b = (self._path, self._filenode), (fc2._path, fc2._filenode) |
|
759 | v = ancestor.ancestor(a, b, parents) | |
|
759 | v = ancestor.genericancestor(a, b, parents) | |
|
760 | 760 | if v: |
|
761 | 761 | f, n = v |
|
762 | 762 | return filectx(self._repo, f, fileid=n, filelog=flcache[f]) |
@@ -1163,6 +1163,366 b' static int index_contains(indexObject *s' | |||
|
1163 | 1163 | } |
|
1164 | 1164 | } |
|
1165 | 1165 | |
|
1166 | static inline void index_get_parents(indexObject *self, int rev, int *ps) | |
|
1167 | { | |
|
1168 | if (rev >= self->length - 1) { | |
|
1169 | PyObject *tuple = PyList_GET_ITEM(self->added, | |
|
1170 | rev - self->length + 1); | |
|
1171 | ps[0] = (int)PyInt_AS_LONG(PyTuple_GET_ITEM(tuple, 5)); | |
|
1172 | ps[1] = (int)PyInt_AS_LONG(PyTuple_GET_ITEM(tuple, 6)); | |
|
1173 | } else { | |
|
1174 | const char *data = index_deref(self, rev); | |
|
1175 | ps[0] = getbe32(data + 24); | |
|
1176 | ps[1] = getbe32(data + 28); | |
|
1177 | } | |
|
1178 | } | |
|
1179 | ||
|
1180 | typedef uint64_t bitmask; | |
|
1181 | ||
|
1182 | /* | |
|
1183 | * Given a disjoint set of revs, return all candidates for the | |
|
1184 | * greatest common ancestor. In revset notation, this is the set | |
|
1185 | * "heads(::a and ::b and ...)" | |
|
1186 | */ | |
|
1187 | static PyObject *find_gca_candidates(indexObject *self, const int *revs, | |
|
1188 | int revcount) | |
|
1189 | { | |
|
1190 | const bitmask allseen = (1ull << revcount) - 1; | |
|
1191 | const bitmask poison = 1ull << revcount; | |
|
1192 | PyObject *gca = PyList_New(0); | |
|
1193 | int i, v, interesting, left; | |
|
1194 | int maxrev = -1; | |
|
1195 | bitmask *seen; | |
|
1196 | ||
|
1197 | for (i = 0; i < revcount; i++) { | |
|
1198 | if (revs[i] > maxrev) | |
|
1199 | maxrev = revs[i]; | |
|
1200 | } | |
|
1201 | ||
|
1202 | seen = calloc(sizeof(*seen), maxrev + 1); | |
|
1203 | if (seen == NULL) | |
|
1204 | return PyErr_NoMemory(); | |
|
1205 | ||
|
1206 | for (i = 0; i < revcount; i++) | |
|
1207 | seen[revs[i]] = 1ull << i; | |
|
1208 | ||
|
1209 | interesting = left = revcount; | |
|
1210 | ||
|
1211 | for (v = maxrev; v >= 0 && interesting; v--) { | |
|
1212 | long sv = seen[v]; | |
|
1213 | int parents[2]; | |
|
1214 | ||
|
1215 | if (!sv) | |
|
1216 | continue; | |
|
1217 | ||
|
1218 | if (sv < poison) { | |
|
1219 | interesting -= 1; | |
|
1220 | if (sv == allseen) { | |
|
1221 | PyObject *obj = PyInt_FromLong(v); | |
|
1222 | if (obj == NULL) | |
|
1223 | goto bail; | |
|
1224 | if (PyList_Append(gca, obj) == -1) { | |
|
1225 | Py_DECREF(obj); | |
|
1226 | goto bail; | |
|
1227 | } | |
|
1228 | sv |= poison; | |
|
1229 | for (i = 0; i < revcount; i++) { | |
|
1230 | if (revs[i] == v) { | |
|
1231 | if (--left <= 1) | |
|
1232 | goto done; | |
|
1233 | break; | |
|
1234 | } | |
|
1235 | } | |
|
1236 | } | |
|
1237 | } | |
|
1238 | index_get_parents(self, v, parents); | |
|
1239 | ||
|
1240 | for (i = 0; i < 2; i++) { | |
|
1241 | int p = parents[i]; | |
|
1242 | if (p == -1) | |
|
1243 | continue; | |
|
1244 | const long sp = seen[p]; | |
|
1245 | if (sv < poison) { | |
|
1246 | if (sp == 0) { | |
|
1247 | seen[p] = sv; | |
|
1248 | interesting++; | |
|
1249 | } | |
|
1250 | else if (sp != sv) | |
|
1251 | seen[p] |= sv; | |
|
1252 | } else { | |
|
1253 | if (sp && sp < poison) | |
|
1254 | interesting--; | |
|
1255 | seen[p] = sv; | |
|
1256 | } | |
|
1257 | } | |
|
1258 | } | |
|
1259 | ||
|
1260 | done: | |
|
1261 | free(seen); | |
|
1262 | return gca; | |
|
1263 | bail: | |
|
1264 | free(seen); | |
|
1265 | Py_XDECREF(gca); | |
|
1266 | return NULL; | |
|
1267 | } | |
|
1268 | ||
|
1269 | /* | |
|
1270 | * Given a disjoint set of revs, return the subset with the longest | |
|
1271 | * path to the root. | |
|
1272 | */ | |
|
1273 | static PyObject *find_deepest(indexObject *self, PyObject *revs) | |
|
1274 | { | |
|
1275 | const Py_ssize_t revcount = PyList_GET_SIZE(revs); | |
|
1276 | static const Py_ssize_t capacity = 24; | |
|
1277 | int *depth, *interesting = NULL; | |
|
1278 | int i, j, v, ninteresting; | |
|
1279 | PyObject *dict = NULL, *keys; | |
|
1280 | long *seen = NULL; | |
|
1281 | int maxrev = -1; | |
|
1282 | long final; | |
|
1283 | ||
|
1284 | if (revcount > capacity) { | |
|
1285 | PyErr_Format(PyExc_OverflowError, | |
|
1286 | "bitset size (%ld) > capacity (%ld)", | |
|
1287 | revcount, capacity); | |
|
1288 | return NULL; | |
|
1289 | } | |
|
1290 | ||
|
1291 | for (i = 0; i < revcount; i++) { | |
|
1292 | int n = (int)PyInt_AsLong(PyList_GET_ITEM(revs, i)); | |
|
1293 | if (n > maxrev) | |
|
1294 | maxrev = n; | |
|
1295 | } | |
|
1296 | ||
|
1297 | depth = calloc(sizeof(*depth), maxrev + 1); | |
|
1298 | if (depth == NULL) | |
|
1299 | return PyErr_NoMemory(); | |
|
1300 | ||
|
1301 | seen = calloc(sizeof(*seen), maxrev + 1); | |
|
1302 | if (seen == NULL) { | |
|
1303 | PyErr_NoMemory(); | |
|
1304 | goto bail; | |
|
1305 | } | |
|
1306 | ||
|
1307 | interesting = calloc(sizeof(*interesting), 2 << revcount); | |
|
1308 | if (interesting == NULL) { | |
|
1309 | PyErr_NoMemory(); | |
|
1310 | goto bail; | |
|
1311 | } | |
|
1312 | ||
|
1313 | for (i = 0; i < revcount; i++) { | |
|
1314 | int n = (int)PyInt_AsLong(PyList_GET_ITEM(revs, i)); | |
|
1315 | long b = 1l << i; | |
|
1316 | depth[n] = 1; | |
|
1317 | seen[n] = b; | |
|
1318 | interesting[b] = 1; | |
|
1319 | } | |
|
1320 | ||
|
1321 | ninteresting = (int)revcount; | |
|
1322 | ||
|
1323 | for (v = maxrev; v >= 0 && ninteresting > 1; v--) { | |
|
1324 | int dv = depth[v]; | |
|
1325 | int parents[2]; | |
|
1326 | long sv; | |
|
1327 | ||
|
1328 | if (dv == 0) | |
|
1329 | continue; | |
|
1330 | ||
|
1331 | sv = seen[v]; | |
|
1332 | index_get_parents(self, v, parents); | |
|
1333 | ||
|
1334 | for (i = 0; i < 2; i++) { | |
|
1335 | int p = parents[i]; | |
|
1336 | long nsp, sp; | |
|
1337 | int dp; | |
|
1338 | ||
|
1339 | if (p == -1) | |
|
1340 | continue; | |
|
1341 | ||
|
1342 | dp = depth[p]; | |
|
1343 | nsp = sp = seen[p]; | |
|
1344 | if (dp <= dv) { | |
|
1345 | depth[p] = dv + 1; | |
|
1346 | if (sp != sv) { | |
|
1347 | interesting[sv] += 1; | |
|
1348 | nsp = seen[p] = sv; | |
|
1349 | if (sp) { | |
|
1350 | interesting[sp] -= 1; | |
|
1351 | if (interesting[sp] == 0) | |
|
1352 | ninteresting -= 1; | |
|
1353 | } | |
|
1354 | } | |
|
1355 | } | |
|
1356 | else if (dv == dp - 1) { | |
|
1357 | nsp = sp | sv; | |
|
1358 | if (nsp == sp) | |
|
1359 | continue; | |
|
1360 | seen[p] = nsp; | |
|
1361 | interesting[nsp] += 1; | |
|
1362 | interesting[sp] -= 1; | |
|
1363 | if (interesting[sp] == 0) | |
|
1364 | ninteresting -= 1; | |
|
1365 | } | |
|
1366 | } | |
|
1367 | interesting[sv] -= 1; | |
|
1368 | if (interesting[sv] == 0) | |
|
1369 | ninteresting -= 1; | |
|
1370 | } | |
|
1371 | ||
|
1372 | final = 0; | |
|
1373 | j = ninteresting; | |
|
1374 | for (i = 0; i < (int)(2 << revcount) && j > 0; i++) { | |
|
1375 | if (interesting[i] == 0) | |
|
1376 | continue; | |
|
1377 | final |= i; | |
|
1378 | j -= 1; | |
|
1379 | } | |
|
1380 | if (final == 0) | |
|
1381 | return PyList_New(0); | |
|
1382 | ||
|
1383 | dict = PyDict_New(); | |
|
1384 | if (dict == NULL) | |
|
1385 | goto bail; | |
|
1386 | ||
|
1387 | j = ninteresting; | |
|
1388 | for (i = 0; i < revcount && j > 0; i++) { | |
|
1389 | PyObject *key; | |
|
1390 | ||
|
1391 | if ((final & (1 << i)) == 0) | |
|
1392 | continue; | |
|
1393 | ||
|
1394 | key = PyList_GET_ITEM(revs, i); | |
|
1395 | Py_INCREF(key); | |
|
1396 | Py_INCREF(Py_None); | |
|
1397 | if (PyDict_SetItem(dict, key, Py_None) == -1) { | |
|
1398 | Py_DECREF(key); | |
|
1399 | Py_DECREF(Py_None); | |
|
1400 | goto bail; | |
|
1401 | } | |
|
1402 | j -= 1; | |
|
1403 | } | |
|
1404 | ||
|
1405 | keys = PyDict_Keys(dict); | |
|
1406 | ||
|
1407 | free(depth); | |
|
1408 | free(seen); | |
|
1409 | free(interesting); | |
|
1410 | Py_DECREF(dict); | |
|
1411 | ||
|
1412 | return keys; | |
|
1413 | bail: | |
|
1414 | free(depth); | |
|
1415 | free(seen); | |
|
1416 | free(interesting); | |
|
1417 | Py_XDECREF(dict); | |
|
1418 | ||
|
1419 | return NULL; | |
|
1420 | } | |
|
1421 | ||
|
1422 | /* | |
|
1423 | * Given a (possibly overlapping) set of revs, return the greatest | |
|
1424 | * common ancestors: those with the longest path to the root. | |
|
1425 | */ | |
|
1426 | static PyObject *index_ancestors(indexObject *self, PyObject *args) | |
|
1427 | { | |
|
1428 | PyObject *ret = NULL, *gca = NULL; | |
|
1429 | Py_ssize_t argcount, i, len; | |
|
1430 | bitmask repeat = 0; | |
|
1431 | int revcount = 0; | |
|
1432 | int *revs; | |
|
1433 | ||
|
1434 | argcount = PySequence_Length(args); | |
|
1435 | revs = malloc(argcount * sizeof(*revs)); | |
|
1436 | if (argcount > 0 && revs == NULL) | |
|
1437 | return PyErr_NoMemory(); | |
|
1438 | len = index_length(self) - 1; | |
|
1439 | ||
|
1440 | for (i = 0; i < argcount; i++) { | |
|
1441 | static const int capacity = 24; | |
|
1442 | PyObject *obj = PySequence_GetItem(args, i); | |
|
1443 | bitmask x; | |
|
1444 | long val; | |
|
1445 | ||
|
1446 | if (!PyInt_Check(obj)) { | |
|
1447 | PyErr_SetString(PyExc_TypeError, | |
|
1448 | "arguments must all be ints"); | |
|
1449 | goto bail; | |
|
1450 | } | |
|
1451 | val = PyInt_AsLong(obj); | |
|
1452 | if (val == -1) { | |
|
1453 | ret = PyList_New(0); | |
|
1454 | goto done; | |
|
1455 | } | |
|
1456 | if (val < 0 || val >= len) { | |
|
1457 | PyErr_SetString(PyExc_IndexError, | |
|
1458 | "index out of range"); | |
|
1459 | goto bail; | |
|
1460 | } | |
|
1461 | /* this cheesy bloom filter lets us avoid some more | |
|
1462 | * expensive duplicate checks in the common set-is-disjoint | |
|
1463 | * case */ | |
|
1464 | x = 1ull << (val & 0x3f); | |
|
1465 | if (repeat & x) { | |
|
1466 | int k; | |
|
1467 | for (k = 0; k < revcount; k++) { | |
|
1468 | if (val == revs[k]) | |
|
1469 | goto duplicate; | |
|
1470 | } | |
|
1471 | } | |
|
1472 | else repeat |= x; | |
|
1473 | if (revcount >= capacity) { | |
|
1474 | PyErr_Format(PyExc_OverflowError, | |
|
1475 | "bitset size (%d) > capacity (%d)", | |
|
1476 | revcount, capacity); | |
|
1477 | goto bail; | |
|
1478 | } | |
|
1479 | revs[revcount++] = (int)val; | |
|
1480 | duplicate:; | |
|
1481 | } | |
|
1482 | ||
|
1483 | if (revcount == 0) { | |
|
1484 | ret = PyList_New(0); | |
|
1485 | goto done; | |
|
1486 | } | |
|
1487 | if (revcount == 1) { | |
|
1488 | PyObject *obj; | |
|
1489 | ret = PyList_New(1); | |
|
1490 | if (ret == NULL) | |
|
1491 | goto bail; | |
|
1492 | obj = PyInt_FromLong(revs[0]); | |
|
1493 | if (obj == NULL) | |
|
1494 | goto bail; | |
|
1495 | PyList_SET_ITEM(ret, 0, obj); | |
|
1496 | goto done; | |
|
1497 | } | |
|
1498 | ||
|
1499 | gca = find_gca_candidates(self, revs, revcount); | |
|
1500 | if (gca == NULL) | |
|
1501 | goto bail; | |
|
1502 | ||
|
1503 | if (PyList_GET_SIZE(gca) <= 1) { | |
|
1504 | ret = gca; | |
|
1505 | Py_INCREF(gca); | |
|
1506 | } | |
|
1507 | else if (PyList_GET_SIZE(gca) == 1) { | |
|
1508 | ret = PyList_GET_ITEM(gca, 0); | |
|
1509 | Py_INCREF(ret); | |
|
1510 | } | |
|
1511 | else ret = find_deepest(self, gca); | |
|
1512 | ||
|
1513 | done: | |
|
1514 | free(revs); | |
|
1515 | Py_XDECREF(gca); | |
|
1516 | ||
|
1517 | return ret; | |
|
1518 | ||
|
1519 | bail: | |
|
1520 | free(revs); | |
|
1521 | Py_XDECREF(gca); | |
|
1522 | Py_XDECREF(ret); | |
|
1523 | return NULL; | |
|
1524 | } | |
|
1525 | ||
|
1166 | 1526 | /* |
|
1167 | 1527 | * Invalidate any trie entries introduced by added revs. |
|
1168 | 1528 | */ |
@@ -1406,6 +1766,8 b' static PyMappingMethods index_mapping_me' | |||
|
1406 | 1766 | }; |
|
1407 | 1767 | |
|
1408 | 1768 | static PyMethodDef index_methods[] = { |
|
1769 | {"ancestors", (PyCFunction)index_ancestors, METH_VARARGS, | |
|
1770 | "return the gca set of the given revs"}, | |
|
1409 | 1771 | {"clearcaches", (PyCFunction)index_clearcaches, METH_NOARGS, |
|
1410 | 1772 | "clear the index caches"}, |
|
1411 | 1773 | {"get", (PyCFunction)index_m_get, METH_VARARGS, |
@@ -705,20 +705,15 b' class revlog(object):' | |||
|
705 | 705 | def ancestor(self, a, b): |
|
706 | 706 | """calculate the least common ancestor of nodes a and b""" |
|
707 | 707 | |
|
708 | # fast path, check if it is a descendant | |
|
709 | 708 | a, b = self.rev(a), self.rev(b) |
|
710 | start, end = sorted((a, b)) | |
|
711 | if self.descendant(start, end): | |
|
712 | return self.node(start) | |
|
713 | ||
|
714 |
|
|
|
715 | return [p for p in self.parentrevs(rev) if p != nullrev] | |
|
716 | ||
|
717 | c = ancestor.ancestor(a, b, parents) | |
|
718 | if c is None: | |
|
719 | return nullid | |
|
720 | ||
|
721 | return self.node(c) | |
|
709 | try: | |
|
710 | ancs = self.index.ancestors(a, b) | |
|
711 | except (AttributeError, OverflowError): | |
|
712 | ancs = ancestor.ancestors(self.parentrevs, a, b) | |
|
713 | if ancs: | |
|
714 | # choose a consistent winner when there's a tie | |
|
715 | return min(map(self.node, ancs)) | |
|
716 | return nullid | |
|
722 | 717 | |
|
723 | 718 | def _match(self, id): |
|
724 | 719 | if isinstance(id, int): |
General Comments 0
You need to be logged in to leave comments.
Login now