author | Pierre-Yves David <pierre-yves.david@octobus.net> |
Thu, 21 Dec 2017 00:34:31 +0100 | |
changeset 3338 | 3f049353d733 |
parent 3337 | 94788616fbeb |
child 3340 | fd90e73bf79a |
permissions | -rw-r--r-- |
3243
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
1 |
# Code dedicated to the computation of stable sorting |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
2 |
# |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
3 |
# These stable sorting are used stable ranges |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
4 |
# |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
5 |
# Copyright 2017 Pierre-Yves David <pierre-yves.david@ens-lyon.org> |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
6 |
# |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
7 |
# This software may be used and distributed according to the terms of the |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
8 |
# GNU General Public License version 2 or any later version. |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
9 |
|
3337
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
10 |
import array |
3243
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
11 |
import collections |
3337
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
12 |
import struct |
3338
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
13 |
import weakref |
3243
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
14 |
|
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
15 |
from mercurial import ( |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
16 |
commands, |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
17 |
cmdutil, |
3338
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
18 |
localrepo, |
3246
543708c3f754
stablesort: add a 'method' argument to the debugstablesort command
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3245
diff
changeset
|
19 |
error, |
3243
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
20 |
node as nodemod, |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
21 |
scmutil, |
3338
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
22 |
util, |
3243
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
23 |
) |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
24 |
|
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
25 |
from mercurial.i18n import _ |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
26 |
|
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
27 |
from . import ( |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
28 |
depthcache, |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
29 |
exthelper, |
3311
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
30 |
utility, |
3337
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
31 |
genericcaches, |
3243
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
32 |
) |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
33 |
|
3311
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
34 |
filterparents = utility.filterparents |
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
35 |
|
3243
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
36 |
eh = exthelper.exthelper() |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
37 |
eh.merge(depthcache.eh) |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
38 |
|
3254
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
39 |
def _mergepoint_tie_breaker(repo): |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
40 |
"""the key use to tie break merge parent |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
41 |
|
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
42 |
Exists as a function to help playing with different approaches. |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
43 |
|
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
44 |
Possible other factor are: |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
45 |
* depth of node, |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
46 |
* number of exclusive merges, |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
47 |
* number of jump points. |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
48 |
* <insert-your-idea> |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
49 |
""" |
3322
20b6dae466a7
stablesort: use 'depth' in mergepoint tie breaker
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3321
diff
changeset
|
50 |
node = repo.changelog.node |
20b6dae466a7
stablesort: use 'depth' in mergepoint tie breaker
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3321
diff
changeset
|
51 |
depth = repo.depthcache.get |
20b6dae466a7
stablesort: use 'depth' in mergepoint tie breaker
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3321
diff
changeset
|
52 |
|
20b6dae466a7
stablesort: use 'depth' in mergepoint tie breaker
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3321
diff
changeset
|
53 |
def key(rev): |
20b6dae466a7
stablesort: use 'depth' in mergepoint tie breaker
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3321
diff
changeset
|
54 |
return (-depth(rev), node(rev)) |
20b6dae466a7
stablesort: use 'depth' in mergepoint tie breaker
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3321
diff
changeset
|
55 |
return key |
3254
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
56 |
|
3243
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
57 |
@eh.command( |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
58 |
'debugstablesort', |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
59 |
[ |
3246
543708c3f754
stablesort: add a 'method' argument to the debugstablesort command
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3245
diff
changeset
|
60 |
('r', 'rev', [], 'heads to start from'), |
3255
bb3f8c8c1232
stablesort: introduce a mergepoint based method focused on head
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3254
diff
changeset
|
61 |
('', 'method', 'branchpoint', "method used for sorting, one of: " |
bb3f8c8c1232
stablesort: introduce a mergepoint based method focused on head
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3254
diff
changeset
|
62 |
"branchpoint, basic-mergepoint and basic-headstart"), |
3256
c82a2632327e
stablesort: add a --limit argument
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3255
diff
changeset
|
63 |
('l', 'limit', '', 'number of revision display (default to all)') |
3243
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
64 |
] + commands.formatteropts, |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
65 |
_('')) |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
66 |
def debugstablesort(ui, repo, **opts): |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
67 |
"""display the ::REVS set topologically sorted in a stable way |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
68 |
""" |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
69 |
revs = scmutil.revrange(repo, opts['rev']) |
3246
543708c3f754
stablesort: add a 'method' argument to the debugstablesort command
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3245
diff
changeset
|
70 |
|
543708c3f754
stablesort: add a 'method' argument to the debugstablesort command
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3245
diff
changeset
|
71 |
method = opts['method'] |
543708c3f754
stablesort: add a 'method' argument to the debugstablesort command
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3245
diff
changeset
|
72 |
sorting = _methodmap.get(method) |
543708c3f754
stablesort: add a 'method' argument to the debugstablesort command
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3245
diff
changeset
|
73 |
if sorting is None: |
543708c3f754
stablesort: add a 'method' argument to the debugstablesort command
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3245
diff
changeset
|
74 |
valid_method = ', '.join(sorted(_methodmap)) |
543708c3f754
stablesort: add a 'method' argument to the debugstablesort command
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3245
diff
changeset
|
75 |
raise error.Abort('unknown sorting method: "%s"' % method, |
543708c3f754
stablesort: add a 'method' argument to the debugstablesort command
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3245
diff
changeset
|
76 |
hint='pick one of: %s' % valid_method) |
543708c3f754
stablesort: add a 'method' argument to the debugstablesort command
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3245
diff
changeset
|
77 |
|
3243
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
78 |
displayer = cmdutil.show_changeset(ui, repo, opts, buffered=True) |
3256
c82a2632327e
stablesort: add a --limit argument
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3255
diff
changeset
|
79 |
kwargs = {} |
c82a2632327e
stablesort: add a --limit argument
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3255
diff
changeset
|
80 |
if opts['limit']: |
c82a2632327e
stablesort: add a --limit argument
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3255
diff
changeset
|
81 |
kwargs['limit'] = int(opts['limit']) |
c82a2632327e
stablesort: add a --limit argument
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3255
diff
changeset
|
82 |
for r in sorting(repo, revs, **kwargs): |
3243
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
83 |
ctx = repo[r] |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
84 |
displayer.show(ctx) |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
85 |
displayer.flush(ctx) |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
86 |
displayer.close() |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
87 |
|
3245
63d58f7db120
stablesort: rename function to stablesort_branchpoint
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3243
diff
changeset
|
88 |
def stablesort_branchpoint(repo, revs, mergecallback=None): |
3243
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
89 |
"""return '::revs' topologically sorted in "stable" order |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
90 |
|
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
91 |
This is a depth first traversal starting from 'nullrev', using node as a |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
92 |
tie breaker. |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
93 |
""" |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
94 |
# Various notes: |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
95 |
# |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
96 |
# * Bitbucket is used dates as tie breaker, that might be a good idea. |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
97 |
# |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
98 |
# * It seemds we can traverse in the same order from (one) head to bottom, |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
99 |
# if we the following record data for each merge: |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
100 |
# |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
101 |
# - highest (stablesort-wise) common ancestors, |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
102 |
# - order of parents (tablesort-wise) |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
103 |
cl = repo.changelog |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
104 |
parents = cl.parentrevs |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
105 |
nullrev = nodemod.nullrev |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
106 |
n = cl.node |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
107 |
# step 1: We need a parents -> children mapping for 2 reasons. |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
108 |
# |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
109 |
# * we build the order from nullrev to tip |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
110 |
# |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
111 |
# * we need to detect branching |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
112 |
children = collections.defaultdict(list) |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
113 |
for r in cl.ancestors(revs, inclusive=True): |
3311
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
114 |
ps = filterparents(parents(r)) |
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
115 |
if not ps: |
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
116 |
children[nullrev].append(r) |
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
117 |
for p in ps: |
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
118 |
children[p].append(r) |
3243
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
119 |
# step two: walk back up |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
120 |
# * pick lowest node in case of branching |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
121 |
# * stack disregarded part of the branching |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
122 |
# * process merge when both parents are yielded |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
123 |
|
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
124 |
# track what changeset has been |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
125 |
seen = [0] * (max(revs) + 2) |
3311
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
126 |
seen[nullrev] = True # nullrev is known |
3243
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
127 |
# starts from repository roots |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
128 |
# reuse the list form the mapping as we won't need it again anyway |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
129 |
stack = children[nullrev] |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
130 |
if not stack: |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
131 |
return [] |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
132 |
if 1 < len(stack): |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
133 |
stack.sort(key=n, reverse=True) |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
134 |
|
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
135 |
# list of rev, maybe we should yield, but since we built a children mapping we are 'O(N)' already |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
136 |
result = [] |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
137 |
|
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
138 |
current = stack.pop() |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
139 |
while current is not None or stack: |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
140 |
if current is None: |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
141 |
# previous iteration reached a merge or an unready merge, |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
142 |
current = stack.pop() |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
143 |
if seen[current]: |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
144 |
current = None |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
145 |
continue |
3311
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
146 |
ps = filterparents(parents(current)) |
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
147 |
if not all(seen[p] for p in ps): |
3243
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
148 |
# we can't iterate on this merge yet because other child is not |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
149 |
# yielded yet (and we are topo sorting) we can discard it for now |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
150 |
# because it will be reached from the other child. |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
151 |
current = None |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
152 |
continue |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
153 |
assert not seen[current] |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
154 |
seen[current] = True |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
155 |
result.append(current) # could be yield, cf earlier comment |
3311
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
156 |
if mergecallback is not None and 2 <= len(ps): |
3243
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
157 |
mergecallback(result, current) |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
158 |
cs = children[current] |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
159 |
if not cs: |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
160 |
current = None |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
161 |
elif 1 == len(cs): |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
162 |
current = cs[0] |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
163 |
else: |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
164 |
cs.sort(key=n, reverse=True) |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
165 |
current = cs.pop() # proceed on smallest |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
166 |
stack.extend(cs) # stack the rest for later |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
167 |
assert len(result) == len(set(result)) |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
168 |
return result |
3246
543708c3f754
stablesort: add a 'method' argument to the debugstablesort command
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3245
diff
changeset
|
169 |
|
3254
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
170 |
def stablesort_mergepoint_multirevs(repo, revs): |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
171 |
"""return '::revs' topologically sorted in "stable" order |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
172 |
|
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
173 |
This is a depth first traversal starting from 'revs' (toward root), using node as a |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
174 |
tie breaker. |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
175 |
""" |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
176 |
cl = repo.changelog |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
177 |
tiebreaker = _mergepoint_tie_breaker(repo) |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
178 |
if not revs: |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
179 |
return [] |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
180 |
elif len(revs) == 1: |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
181 |
heads = list(revs) |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
182 |
else: |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
183 |
# keeps heads only |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
184 |
heads = sorted(repo.revs('heads(%ld::%ld)', revs, revs), key=tiebreaker) |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
185 |
|
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
186 |
results = [] |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
187 |
while heads: |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
188 |
h = heads.pop() |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
189 |
if revs: |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
190 |
bound = cl.findmissingrevs(common=heads, heads=[h]) |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
191 |
else: |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
192 |
bound = cl.ancestors([h], inclusive=True) |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
193 |
results.append(stablesort_mergepoint_bounded(repo, h, bound)) |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
194 |
if len(results) == 1: |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
195 |
return results[0] |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
196 |
finalresults = [] |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
197 |
for r in results[::-1]: |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
198 |
finalresults.extend(r) |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
199 |
return finalresults |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
200 |
|
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
201 |
def stablesort_mergepoint_bounded(repo, head, revs): |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
202 |
"""return 'revs' topologically sorted in "stable" order. |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
203 |
|
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
204 |
The 'revs' set MUST have 'head' as its one and unique head. |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
205 |
""" |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
206 |
# Various notes: |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
207 |
# |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
208 |
# * Bitbucket is using dates as tie breaker, that might be a good idea. |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
209 |
cl = repo.changelog |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
210 |
parents = cl.parentrevs |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
211 |
nullrev = nodemod.nullrev |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
212 |
tiebreaker = _mergepoint_tie_breaker(repo) |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
213 |
# step 1: We need a parents -> children mapping to detect dependencies |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
214 |
children = collections.defaultdict(set) |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
215 |
parentmap = {} |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
216 |
for r in revs: |
3311
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
217 |
ps = filterparents(parents(r)) |
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
218 |
if 2 <= len(ps): |
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
219 |
ps = tuple(sorted(ps, key=tiebreaker)) |
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
220 |
parentmap[r] = ps |
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
221 |
for p in ps: |
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
222 |
children[p].add(r) |
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
223 |
if not ps: |
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
224 |
children[nullrev].add(r) |
3254
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
225 |
# step two: walk again, |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
226 |
stack = [head] |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
227 |
resultset = set() |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
228 |
result = [] |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
229 |
|
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
230 |
def add(current): |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
231 |
resultset.add(current) |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
232 |
result.append(current) |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
233 |
|
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
234 |
while stack: |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
235 |
current = stack.pop() |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
236 |
add(current) |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
237 |
parents = parentmap[current] |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
238 |
for p in parents: |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
239 |
if 1 < len(children[p]) and not children[p].issubset(resultset): |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
240 |
# we need other children to be yield first |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
241 |
continue |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
242 |
if p in revs: |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
243 |
stack.append(p) |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
244 |
|
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
245 |
result.reverse() |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
246 |
assert len(result) == len(resultset) |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
247 |
return result |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
248 |
|
3256
c82a2632327e
stablesort: add a --limit argument
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3255
diff
changeset
|
249 |
def stablesort_mergepoint_head_basic(repo, revs, limit=None): |
3255
bb3f8c8c1232
stablesort: introduce a mergepoint based method focused on head
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3254
diff
changeset
|
250 |
heads = repo.revs('heads(%ld)', revs) |
bb3f8c8c1232
stablesort: introduce a mergepoint based method focused on head
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3254
diff
changeset
|
251 |
if not heads: |
bb3f8c8c1232
stablesort: introduce a mergepoint based method focused on head
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3254
diff
changeset
|
252 |
return [] |
bb3f8c8c1232
stablesort: introduce a mergepoint based method focused on head
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3254
diff
changeset
|
253 |
elif 2 < len(heads): |
bb3f8c8c1232
stablesort: introduce a mergepoint based method focused on head
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3254
diff
changeset
|
254 |
raise error.Abort('cannot use head based merging, %d heads found' |
bb3f8c8c1232
stablesort: introduce a mergepoint based method focused on head
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3254
diff
changeset
|
255 |
% len(heads)) |
bb3f8c8c1232
stablesort: introduce a mergepoint based method focused on head
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3254
diff
changeset
|
256 |
head = heads.first() |
3256
c82a2632327e
stablesort: add a --limit argument
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3255
diff
changeset
|
257 |
revs = stablesort_mergepoint_bounded(repo, head, repo.revs('::%d', head)) |
c82a2632327e
stablesort: add a --limit argument
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3255
diff
changeset
|
258 |
if limit is None: |
c82a2632327e
stablesort: add a --limit argument
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3255
diff
changeset
|
259 |
return revs |
c82a2632327e
stablesort: add a --limit argument
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3255
diff
changeset
|
260 |
return revs[-limit:] |
3255
bb3f8c8c1232
stablesort: introduce a mergepoint based method focused on head
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3254
diff
changeset
|
261 |
|
3262
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
262 |
def stablesort_mergepoint_head_debug(repo, revs, limit=None): |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
263 |
heads = repo.revs('heads(%ld)', revs) |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
264 |
if not heads: |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
265 |
return [] |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
266 |
elif 2 < len(heads): |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
267 |
raise error.Abort('cannot use head based merging, %d heads found' |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
268 |
% len(heads)) |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
269 |
head = heads.first() |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
270 |
revs = stablesort_mergepoint_head(repo, head) |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
271 |
if limit is None: |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
272 |
return revs |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
273 |
return revs[-limit:] |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
274 |
|
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
275 |
def stablesort_mergepoint_head(repo, head): |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
276 |
"""return '::rev' topologically sorted in "stable" order |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
277 |
|
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
278 |
This is a depth first traversal starting from 'rev' (toward root), using node as a |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
279 |
tie breaker. |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
280 |
""" |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
281 |
cl = repo.changelog |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
282 |
parents = cl.parentrevs |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
283 |
tiebreaker = _mergepoint_tie_breaker(repo) |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
284 |
|
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
285 |
top = [head] |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
286 |
mid = [] |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
287 |
bottom = [] |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
288 |
|
3311
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
289 |
ps = filterparents(parents(head)) |
3262
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
290 |
while len(ps) == 1: |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
291 |
top.append(ps[0]) |
3311
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
292 |
ps = filterparents(parents(ps[0])) |
3262
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
293 |
top.reverse() |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
294 |
if len(ps) == 2: |
3313
efceae0bfa35
stablesort: avoid attempting to sort a tuple
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3311
diff
changeset
|
295 |
ps = sorted(ps, key=tiebreaker) |
3262
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
296 |
|
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
297 |
# get the part from the highest parent. This is the part that changes |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
298 |
mid_revs = repo.revs('only(%d, %d)', ps[1], ps[0]) |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
299 |
if mid_revs: |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
300 |
mid = stablesort_mergepoint_bounded(repo, ps[1], mid_revs) |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
301 |
|
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
302 |
# And follow up with part othe parent we can inherit from |
3314
110202a00de2
stablesort: fix head start computation
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3313
diff
changeset
|
303 |
bottom = stablesort_mergepoint_head(repo, ps[0]) |
3262
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
304 |
|
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
305 |
return bottom + mid + top |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
306 |
|
3263
07678f7a4481
stablesort: introduce a cache object
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3262
diff
changeset
|
307 |
def stablesort_mergepoint_head_cached(repo, revs, limit=None): |
07678f7a4481
stablesort: introduce a cache object
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3262
diff
changeset
|
308 |
heads = repo.revs('heads(%ld)', revs) |
07678f7a4481
stablesort: introduce a cache object
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3262
diff
changeset
|
309 |
if not heads: |
07678f7a4481
stablesort: introduce a cache object
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3262
diff
changeset
|
310 |
return [] |
07678f7a4481
stablesort: introduce a cache object
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3262
diff
changeset
|
311 |
elif 2 < len(heads): |
07678f7a4481
stablesort: introduce a cache object
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3262
diff
changeset
|
312 |
raise error.Abort('cannot use head based merging, %d heads found' |
07678f7a4481
stablesort: introduce a cache object
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3262
diff
changeset
|
313 |
% len(heads)) |
07678f7a4481
stablesort: introduce a cache object
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3262
diff
changeset
|
314 |
head = heads.first() |
07678f7a4481
stablesort: introduce a cache object
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3262
diff
changeset
|
315 |
cache = stablesortcache() |
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
316 |
first = list(cache.get(repo, head, limit=limit)) |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
317 |
second = list(cache.get(repo, head, limit=limit)) |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
318 |
if first != second: |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
319 |
repo.ui.warn('stablesort-cache: initial run different from re-run:\n' |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
320 |
' %s\n' |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
321 |
' %s\n' % (first, second)) |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
322 |
return second |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
323 |
|
3263
07678f7a4481
stablesort: introduce a cache object
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3262
diff
changeset
|
324 |
class stablesortcache(object): |
07678f7a4481
stablesort: introduce a cache object
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3262
diff
changeset
|
325 |
|
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
326 |
def __init__(self): |
3325
83d2a2f3dc8f
stablesort: use a regular dict for jumps
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3323
diff
changeset
|
327 |
self._jumps = {} |
3337
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
328 |
super(stablesortcache, self).__init__() |
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
329 |
|
3263
07678f7a4481
stablesort: introduce a cache object
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3262
diff
changeset
|
330 |
def get(self, repo, rev, limit=None): |
3265
70b5bc95efbe
stablesort: extract a '_revsfrom' method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3263
diff
changeset
|
331 |
result = [] |
3300
2d49773a378b
stablesort: make the iteration from head available to all
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3267
diff
changeset
|
332 |
for r in self.walkfrom(repo, rev): |
3265
70b5bc95efbe
stablesort: extract a '_revsfrom' method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3263
diff
changeset
|
333 |
result.append(r) |
70b5bc95efbe
stablesort: extract a '_revsfrom' method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3263
diff
changeset
|
334 |
if limit is not None and limit <= len(result): |
70b5bc95efbe
stablesort: extract a '_revsfrom' method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3263
diff
changeset
|
335 |
break |
70b5bc95efbe
stablesort: extract a '_revsfrom' method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3263
diff
changeset
|
336 |
result.reverse() |
70b5bc95efbe
stablesort: extract a '_revsfrom' method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3263
diff
changeset
|
337 |
return result |
70b5bc95efbe
stablesort: extract a '_revsfrom' method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3263
diff
changeset
|
338 |
|
3323
4a84947010a1
stablesort: expose the jumps sequence to other code
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3322
diff
changeset
|
339 |
def getjumps(self, repo, rev): |
3334
db8feb404792
stablesort: abstract all cache access
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3329
diff
changeset
|
340 |
if not self._hasjumpsdata(rev): |
3326
8ebd31af1452
stablesort: warm jump cache more efficiently
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3325
diff
changeset
|
341 |
parents = repo.changelog.parentrevs(rev) |
8ebd31af1452
stablesort: warm jump cache more efficiently
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3325
diff
changeset
|
342 |
if parents[1] == nodemod.nullrev: |
3334
db8feb404792
stablesort: abstract all cache access
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3329
diff
changeset
|
343 |
self._setjumps(rev, None) |
3326
8ebd31af1452
stablesort: warm jump cache more efficiently
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3325
diff
changeset
|
344 |
else: |
8ebd31af1452
stablesort: warm jump cache more efficiently
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3325
diff
changeset
|
345 |
# merge ! warn the cache |
8ebd31af1452
stablesort: warm jump cache more efficiently
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3325
diff
changeset
|
346 |
tiebreaker = _mergepoint_tie_breaker(repo) |
8ebd31af1452
stablesort: warm jump cache more efficiently
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3325
diff
changeset
|
347 |
minparent = sorted(parents, key=tiebreaker)[0] |
8ebd31af1452
stablesort: warm jump cache more efficiently
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3325
diff
changeset
|
348 |
for r in self.walkfrom(repo, rev): |
8ebd31af1452
stablesort: warm jump cache more efficiently
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3325
diff
changeset
|
349 |
if r == minparent: |
8ebd31af1452
stablesort: warm jump cache more efficiently
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3325
diff
changeset
|
350 |
break |
3334
db8feb404792
stablesort: abstract all cache access
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3329
diff
changeset
|
351 |
return self._getjumps(rev) |
db8feb404792
stablesort: abstract all cache access
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3329
diff
changeset
|
352 |
|
db8feb404792
stablesort: abstract all cache access
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3329
diff
changeset
|
353 |
def _hasjumpsdata(self, rev): |
db8feb404792
stablesort: abstract all cache access
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3329
diff
changeset
|
354 |
return rev in self._jumps |
db8feb404792
stablesort: abstract all cache access
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3329
diff
changeset
|
355 |
|
db8feb404792
stablesort: abstract all cache access
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3329
diff
changeset
|
356 |
def _getjumps(self, rev): |
db8feb404792
stablesort: abstract all cache access
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3329
diff
changeset
|
357 |
return self._jumps.get(rev) |
db8feb404792
stablesort: abstract all cache access
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3329
diff
changeset
|
358 |
|
db8feb404792
stablesort: abstract all cache access
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3329
diff
changeset
|
359 |
def _setjumps(self, rev, jumps): |
db8feb404792
stablesort: abstract all cache access
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3329
diff
changeset
|
360 |
self._jumps[rev] = jumps |
3323
4a84947010a1
stablesort: expose the jumps sequence to other code
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3322
diff
changeset
|
361 |
|
3300
2d49773a378b
stablesort: make the iteration from head available to all
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3267
diff
changeset
|
362 |
def walkfrom(self, repo, head): |
3267
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
363 |
tiebreaker = _mergepoint_tie_breaker(repo) |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
364 |
cl = repo.changelog |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
365 |
parentsfunc = cl.parentrevs |
3266
bc173e7f3b6f
stablesort: simplify processing of non-merge changesets
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3265
diff
changeset
|
366 |
|
bc173e7f3b6f
stablesort: simplify processing of non-merge changesets
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3265
diff
changeset
|
367 |
def parents(rev): |
3311
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
368 |
return filterparents(parentsfunc(rev)) |
3266
bc173e7f3b6f
stablesort: simplify processing of non-merge changesets
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3265
diff
changeset
|
369 |
|
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
370 |
def oneparent(rev): |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
371 |
ps = parents(rev) |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
372 |
if not ps: |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
373 |
return None |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
374 |
if len(ps) == 1: |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
375 |
return ps[0] |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
376 |
return max(ps, key=tiebreaker) |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
377 |
|
3266
bc173e7f3b6f
stablesort: simplify processing of non-merge changesets
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3265
diff
changeset
|
378 |
current = head |
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
379 |
previous_current_1 = object() |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
380 |
previous_current_2 = object() |
3267
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
381 |
|
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
382 |
while current is not None: |
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
383 |
previous_current_2 = previous_current_1 |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
384 |
previous_current_1 = current |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
385 |
assert previous_current_1 is not previous_current_2 |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
386 |
|
3334
db8feb404792
stablesort: abstract all cache access
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3329
diff
changeset
|
387 |
jumps = self._getjumps(current) |
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
388 |
if jumps is not None: |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
389 |
# we have enough cached information to directly iterate over |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
390 |
# the exclusive size. |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
391 |
for j in jumps: |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
392 |
jump_point = j[0] |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
393 |
jump_dest = j[1] |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
394 |
if current == jump_point: |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
395 |
yield current |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
396 |
else: |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
397 |
while current != jump_point: |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
398 |
yield current |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
399 |
current = oneparent(current) |
3321
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
400 |
assert current is not None |
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
401 |
yield current |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
402 |
current = jump_dest |
3336
c42158efb64e
stablesort: realign a misaligned continue
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3335
diff
changeset
|
403 |
continue |
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
404 |
|
3266
bc173e7f3b6f
stablesort: simplify processing of non-merge changesets
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3265
diff
changeset
|
405 |
yield current |
3267
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
406 |
|
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
407 |
ps = parents(current) |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
408 |
if not ps: |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
409 |
current = None # break |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
410 |
if len(ps) == 1: |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
411 |
current = ps[0] |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
412 |
elif len(ps) == 2: |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
413 |
lower_parent, higher_parent = sorted(ps, key=tiebreaker) |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
414 |
|
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
415 |
rev = current |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
416 |
jumps = [] |
3319
bacb44f4f33e
stablesort: pass a jump recording function instead of a list
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3318
diff
changeset
|
417 |
|
3329
c056f125e17d
stablesort: record previous segment size in the jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3328
diff
changeset
|
418 |
def recordjump(source, destination, size): |
c056f125e17d
stablesort: record previous segment size in the jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3328
diff
changeset
|
419 |
jump = (source, destination, size) |
3319
bacb44f4f33e
stablesort: pass a jump recording function instead of a list
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3318
diff
changeset
|
420 |
jumps.append(jump) |
3317
a950e6cc5e9e
stablesort: clarify subcall to the exclusive side
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3315
diff
changeset
|
421 |
process = self._process_exclusive_side |
a950e6cc5e9e
stablesort: clarify subcall to the exclusive side
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3315
diff
changeset
|
422 |
for rev in process(lower_parent, higher_parent, cl, parents, |
3319
bacb44f4f33e
stablesort: pass a jump recording function instead of a list
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3318
diff
changeset
|
423 |
tiebreaker, recordjump): |
3267
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
424 |
yield rev |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
425 |
|
3328
ff262ae59541
stablesort: move jump recording inside the exclusive function
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3326
diff
changeset
|
426 |
if rev == current: |
3329
c056f125e17d
stablesort: record previous segment size in the jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3328
diff
changeset
|
427 |
recordjump(rev, lower_parent, 1) |
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
428 |
|
3334
db8feb404792
stablesort: abstract all cache access
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3329
diff
changeset
|
429 |
self._setjumps(current, jumps) |
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
430 |
|
3267
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
431 |
current = lower_parent |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
432 |
|
3317
a950e6cc5e9e
stablesort: clarify subcall to the exclusive side
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3315
diff
changeset
|
433 |
def _process_exclusive_side(self, lower, higher, cl, parents, tiebreaker, |
3319
bacb44f4f33e
stablesort: pass a jump recording function instead of a list
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3318
diff
changeset
|
434 |
recordjump): |
3267
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
435 |
|
3317
a950e6cc5e9e
stablesort: clarify subcall to the exclusive side
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3315
diff
changeset
|
436 |
exclusive = cl.findmissingrevs(common=[lower], heads=[higher]) |
3267
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
437 |
|
3321
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
438 |
def popready(stack): |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
439 |
"""pop the top most ready item in the list""" |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
440 |
for idx in xrange(len(stack) - 1, -1, -1): |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
441 |
if children[stack[idx]].issubset(seen): |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
442 |
return stack.pop(idx) |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
443 |
return None |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
444 |
|
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
445 |
hardstack = [] |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
446 |
previous = None |
3267
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
447 |
seen = set() |
3321
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
448 |
current = higher |
3267
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
449 |
children = collections.defaultdict(set) |
3321
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
450 |
bound = set(exclusive) |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
451 |
if exclusive: |
3267
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
452 |
for r in exclusive: |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
453 |
for p in parents(r): |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
454 |
children[p].add(r) |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
455 |
|
3321
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
456 |
hardstack.append(higher) |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
457 |
nextjump = False |
3329
c056f125e17d
stablesort: record previous segment size in the jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3328
diff
changeset
|
458 |
size = 1 # take the merge point into account |
3321
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
459 |
while hardstack: |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
460 |
current = popready(hardstack) |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
461 |
if current in seen: |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
462 |
continue |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
463 |
softstack = [] |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
464 |
while current in bound and current not in seen: |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
465 |
if nextjump: |
3329
c056f125e17d
stablesort: record previous segment size in the jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3328
diff
changeset
|
466 |
recordjump(previous, current, size) |
3321
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
467 |
nextjump = False |
3329
c056f125e17d
stablesort: record previous segment size in the jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3328
diff
changeset
|
468 |
size = 0 |
3321
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
469 |
yield current |
3329
c056f125e17d
stablesort: record previous segment size in the jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3328
diff
changeset
|
470 |
size += 1 |
3321
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
471 |
previous = current |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
472 |
seen.add(current) |
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
473 |
|
3321
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
474 |
all_parents = parents(current) |
3266
bc173e7f3b6f
stablesort: simplify processing of non-merge changesets
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3265
diff
changeset
|
475 |
|
3321
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
476 |
# search or next parent to walk through |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
477 |
fallback, next = None, None |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
478 |
if 1 == len(all_parents): |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
479 |
next = all_parents[0] |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
480 |
elif 2 <= len(all_parents): |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
481 |
fallback, next = sorted(all_parents, key=tiebreaker) |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
482 |
|
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
483 |
# filter parent not ready (children not emitted) |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
484 |
while next is not None and not children[next].issubset(seen): |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
485 |
nextjump = True |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
486 |
next = fallback |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
487 |
fallback = None |
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
488 |
|
3321
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
489 |
# stack management |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
490 |
if next is None: |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
491 |
next = popready(softstack) |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
492 |
if next is not None: |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
493 |
nextjump = True |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
494 |
elif fallback is not None: |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
495 |
softstack.append(fallback) |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
496 |
|
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
497 |
# get ready for next iteration |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
498 |
current = next |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
499 |
|
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
500 |
# any in processed head has to go in the hard stack |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
501 |
nextjump = True |
14024940f369
stablesort: rework jump gathering
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3320
diff
changeset
|
502 |
hardstack.extend(softstack) |
3329
c056f125e17d
stablesort: record previous segment size in the jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3328
diff
changeset
|
503 |
|
3328
ff262ae59541
stablesort: move jump recording inside the exclusive function
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3326
diff
changeset
|
504 |
if previous is not None: |
3329
c056f125e17d
stablesort: record previous segment size in the jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3328
diff
changeset
|
505 |
recordjump(previous, lower, size) |
3263
07678f7a4481
stablesort: introduce a cache object
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3262
diff
changeset
|
506 |
|
3337
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
507 |
def stablesort_mergepoint_head_ondisk(repo, revs, limit=None): |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
508 |
heads = repo.revs('heads(%ld)', revs) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
509 |
if not heads: |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
510 |
return [] |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
511 |
elif 2 < len(heads): |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
512 |
raise error.Abort('cannot use head based merging, %d heads found' |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
513 |
% len(heads)) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
514 |
head = heads.first() |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
515 |
unfi = repo.unfiltered() |
3338
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
516 |
cache = unfi.stablesort |
3337
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
517 |
cache.save(unfi) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
518 |
return cache.get(repo, head, limit=limit) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
519 |
|
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
520 |
S_INDEXSIZE = struct.Struct('>I') |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
521 |
|
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
522 |
class ondiskstablesortcache(stablesortcache, genericcaches.changelogsourcebase): |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
523 |
|
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
524 |
_filepath = 'evoext-stablesortcache-00' |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
525 |
_cachename = 'evo-ext-stablesort' |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
526 |
|
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
527 |
def __init__(self): |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
528 |
super(ondiskstablesortcache, self).__init__() |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
529 |
self._index = array.array('l') |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
530 |
self._data = array.array('l') |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
531 |
del self._jumps |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
532 |
|
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
533 |
def getjumps(self, repo, rev): |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
534 |
if len(self._index) < rev: |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
535 |
msg = 'stablesortcache must be warmed before use (%d < %d)' |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
536 |
msg %= (len(self._index), rev) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
537 |
raise error.ProgrammingError(msg) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
538 |
return self._getjumps(rev) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
539 |
|
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
540 |
def _getjumps(self, rev): |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
541 |
# very first revision |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
542 |
if rev == 0: |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
543 |
return None |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
544 |
# no data yet |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
545 |
if len(self._index) <= rev: |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
546 |
return None |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
547 |
index = self._index |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
548 |
# non merge revision |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
549 |
if index[rev] == index[rev - 1]: |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
550 |
return None |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
551 |
data = self._data |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
552 |
# merge revision |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
553 |
|
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
554 |
def jumps(): |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
555 |
for idx in xrange(index[rev - 1], index[rev]): |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
556 |
i = idx * 3 |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
557 |
yield tuple(data[i:i + 3]) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
558 |
return jumps() |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
559 |
|
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
560 |
def _setjumps(self, rev, jumps): |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
561 |
assert len(self._index) == rev, (len(self._index), rev) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
562 |
if rev == 0: |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
563 |
self._index.append(0) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
564 |
return |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
565 |
end = self._index[rev - 1] |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
566 |
if jumps is None: |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
567 |
self._index.append(end) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
568 |
return |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
569 |
assert len(self._data) == end * 3, (len(self._data), end) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
570 |
for j in jumps: |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
571 |
self._data.append(j[0]) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
572 |
self._data.append(j[1]) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
573 |
self._data.append(j[2]) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
574 |
end += 1 |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
575 |
self._index.append(end) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
576 |
|
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
577 |
def _updatefrom(self, repo, data): |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
578 |
repo = repo.unfiltered() |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
579 |
|
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
580 |
total = len(data) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
581 |
|
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
582 |
def progress(pos, rev): |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
583 |
repo.ui.progress('updating stablesort cache', |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
584 |
pos, 'rev %s' % rev, unit='revision', total=total) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
585 |
|
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
586 |
progress(0, '') |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
587 |
for idx, rev in enumerate(data): |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
588 |
parents = repo.changelog.parentrevs(rev) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
589 |
if parents[1] == nodemod.nullrev: |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
590 |
self._setjumps(rev, None) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
591 |
else: |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
592 |
# merge! warn the cache |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
593 |
tiebreaker = _mergepoint_tie_breaker(repo) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
594 |
minparent = sorted(parents, key=tiebreaker)[0] |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
595 |
for r in self.walkfrom(repo, rev): |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
596 |
if r == minparent: |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
597 |
break |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
598 |
if not (idx % 1000): # progress as a too high performance impact |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
599 |
progress(idx, rev) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
600 |
progress(None, '') |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
601 |
|
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
602 |
def clear(self, reset=False): |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
603 |
super(ondiskstablesortcache, self).clear() |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
604 |
self._index = array.array('l') |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
605 |
self._data = array.array('l') |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
606 |
|
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
607 |
def load(self, repo): |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
608 |
"""load data from disk |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
609 |
|
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
610 |
(crude version, read everything all the time) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
611 |
""" |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
612 |
assert repo.filtername is None |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
613 |
|
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
614 |
data = repo.cachevfs.tryread(self._filepath) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
615 |
self._index = array.array('l') |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
616 |
self._data = array.array('l') |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
617 |
if not data: |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
618 |
self._cachekey = self.emptykey |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
619 |
else: |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
620 |
headerdata = data[:self._cachekeysize] |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
621 |
self._cachekey = self._deserializecachekey(headerdata) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
622 |
offset = self._cachekeysize |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
623 |
indexsizedata = data[offset:offset + S_INDEXSIZE.size] |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
624 |
indexsize = S_INDEXSIZE.unpack(indexsizedata)[0] |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
625 |
offset += S_INDEXSIZE.size |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
626 |
self._index.fromstring(data[offset:offset + indexsize]) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
627 |
offset += indexsize |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
628 |
self._data.fromstring(data[offset:]) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
629 |
self._ondiskkey = self._cachekey |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
630 |
pass |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
631 |
|
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
632 |
def save(self, repo): |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
633 |
"""save the data to disk |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
634 |
|
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
635 |
(crude version, rewrite everything all the time) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
636 |
""" |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
637 |
if self._cachekey is None or self._cachekey == self._ondiskkey: |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
638 |
return |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
639 |
cachefile = repo.cachevfs(self._filepath, 'w', atomictemp=True) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
640 |
|
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
641 |
# data to write |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
642 |
headerdata = self._serializecachekey() |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
643 |
indexdata = self._index.tostring() |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
644 |
data = self._data.tostring() |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
645 |
indexsize = S_INDEXSIZE.pack(len(indexdata)) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
646 |
|
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
647 |
# writing |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
648 |
cachefile.write(headerdata) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
649 |
cachefile.write(indexsize) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
650 |
cachefile.write(indexdata) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
651 |
cachefile.write(data) |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
652 |
cachefile.close() |
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
653 |
|
3338
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
654 |
@eh.reposetup |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
655 |
def setupcache(ui, repo): |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
656 |
|
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
657 |
class stablesortrepo(repo.__class__): |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
658 |
|
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
659 |
@localrepo.unfilteredpropertycache |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
660 |
def stablesort(self): |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
661 |
cache = ondiskstablesortcache() |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
662 |
cache.update(self) |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
663 |
return cache |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
664 |
|
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
665 |
@localrepo.unfilteredmethod |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
666 |
def destroyed(self): |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
667 |
if 'stablesort' in vars(self): |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
668 |
self.stablesort.clear() |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
669 |
super(stablesortrepo, self).destroyed() |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
670 |
|
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
671 |
if util.safehasattr(repo, 'updatecaches'): |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
672 |
@localrepo.unfilteredmethod |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
673 |
def updatecaches(self, tr=None): |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
674 |
if (repo.ui.configbool('experimental', 'obshashrange', |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
675 |
False) |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
676 |
and repo.ui.configbool('experimental', |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
677 |
'obshashrange.warm-cache', |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
678 |
True)): |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
679 |
self.stablesort.update(repo) |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
680 |
self.stablesort.save(repo) |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
681 |
super(stablesortrepo, self).updatecaches(tr) |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
682 |
|
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
683 |
else: |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
684 |
def transaction(self, *args, **kwargs): |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
685 |
tr = super(stablesortrepo, self).transaction(*args, **kwargs) |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
686 |
reporef = weakref.ref(self) |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
687 |
|
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
688 |
def _warmcache(tr): |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
689 |
repo = reporef() |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
690 |
if repo is None: |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
691 |
return |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
692 |
repo = repo.unfiltered() |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
693 |
|
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
694 |
if (repo.ui.configbool('experimental', 'obshashrange', |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
695 |
False) |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
696 |
and repo.ui.configbool('experimental', |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
697 |
'obshashrange.warm-cache', |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
698 |
True)): |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
699 |
tr.addpostclose('warmcache-02stablesort', _warmcache) |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
700 |
return tr |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
701 |
|
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
702 |
repo.__class__ = stablesortrepo |
3f049353d733
stablesort: expose the cache through the repository
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3337
diff
changeset
|
703 |
|
3246
543708c3f754
stablesort: add a 'method' argument to the debugstablesort command
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3245
diff
changeset
|
704 |
_methodmap = { |
543708c3f754
stablesort: add a 'method' argument to the debugstablesort command
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3245
diff
changeset
|
705 |
'branchpoint': stablesort_branchpoint, |
3254
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
706 |
'basic-mergepoint': stablesort_mergepoint_multirevs, |
3255
bb3f8c8c1232
stablesort: introduce a mergepoint based method focused on head
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3254
diff
changeset
|
707 |
'basic-headstart': stablesort_mergepoint_head_basic, |
3262
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
708 |
'headstart': stablesort_mergepoint_head_debug, |
3263
07678f7a4481
stablesort: introduce a cache object
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3262
diff
changeset
|
709 |
'headcached': stablesort_mergepoint_head_cached, |
3337
94788616fbeb
stablesort: implement an ondisk cache
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3336
diff
changeset
|
710 |
'headondisk': stablesort_mergepoint_head_ondisk, |
3246
543708c3f754
stablesort: add a 'method' argument to the debugstablesort command
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3245
diff
changeset
|
711 |
} |