author | Pierre-Yves David <pierre-yves.david@octobus.net> |
Wed, 20 Dec 2017 12:36:45 +0100 | |
changeset 3320 | 360a543930c6 |
parent 3319 | bacb44f4f33e |
child 3321 | 14024940f369 |
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 |
|
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
10 |
import collections |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
11 |
|
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
12 |
from mercurial import ( |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
13 |
commands, |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
14 |
cmdutil, |
3246
543708c3f754
stablesort: add a 'method' argument to the debugstablesort command
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3245
diff
changeset
|
15 |
error, |
3243
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
16 |
node as nodemod, |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
17 |
scmutil, |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
18 |
) |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
19 |
|
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
20 |
from mercurial.i18n import _ |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
21 |
|
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
22 |
from . import ( |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
23 |
depthcache, |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
24 |
exthelper, |
3311
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
25 |
utility, |
3243
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 |
|
3311
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
28 |
filterparents = utility.filterparents |
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
29 |
|
3243
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
30 |
eh = exthelper.exthelper() |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
31 |
eh.merge(depthcache.eh) |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
32 |
|
3254
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
33 |
def _mergepoint_tie_breaker(repo): |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
34 |
"""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
|
35 |
|
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
36 |
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
|
37 |
|
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
38 |
Possible other factor are: |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
39 |
* depth of node, |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
40 |
* number of exclusive merges, |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
41 |
* number of jump points. |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
42 |
* <insert-your-idea> |
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 |
return repo.changelog.node |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
45 |
|
3243
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
46 |
@eh.command( |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
47 |
'debugstablesort', |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
48 |
[ |
3246
543708c3f754
stablesort: add a 'method' argument to the debugstablesort command
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3245
diff
changeset
|
49 |
('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
|
50 |
('', '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
|
51 |
"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
|
52 |
('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
|
53 |
] + commands.formatteropts, |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
54 |
_('')) |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
55 |
def debugstablesort(ui, repo, **opts): |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
56 |
"""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
|
57 |
""" |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
58 |
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
|
59 |
|
543708c3f754
stablesort: add a 'method' argument to the debugstablesort command
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3245
diff
changeset
|
60 |
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
|
61 |
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
|
62 |
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
|
63 |
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
|
64 |
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
|
65 |
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
|
66 |
|
3243
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
67 |
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
|
68 |
kwargs = {} |
c82a2632327e
stablesort: add a --limit argument
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3255
diff
changeset
|
69 |
if opts['limit']: |
c82a2632327e
stablesort: add a --limit argument
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3255
diff
changeset
|
70 |
kwargs['limit'] = int(opts['limit']) |
c82a2632327e
stablesort: add a --limit argument
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3255
diff
changeset
|
71 |
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
|
72 |
ctx = repo[r] |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
73 |
displayer.show(ctx) |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
74 |
displayer.flush(ctx) |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
75 |
displayer.close() |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
76 |
|
3245
63d58f7db120
stablesort: rename function to stablesort_branchpoint
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3243
diff
changeset
|
77 |
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
|
78 |
"""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
|
79 |
|
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
80 |
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
|
81 |
tie breaker. |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
82 |
""" |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
83 |
# Various notes: |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
84 |
# |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
85 |
# * 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
|
86 |
# |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
87 |
# * 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
|
88 |
# 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
|
89 |
# |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
90 |
# - highest (stablesort-wise) common ancestors, |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
91 |
# - order of parents (tablesort-wise) |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
92 |
cl = repo.changelog |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
93 |
parents = cl.parentrevs |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
94 |
nullrev = nodemod.nullrev |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
95 |
n = cl.node |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
96 |
# 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
|
97 |
# |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
98 |
# * 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
|
99 |
# |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
100 |
# * we need to detect branching |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
101 |
children = collections.defaultdict(list) |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
102 |
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
|
103 |
ps = filterparents(parents(r)) |
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
104 |
if not ps: |
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
105 |
children[nullrev].append(r) |
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
106 |
for p in ps: |
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
107 |
children[p].append(r) |
3243
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
108 |
# step two: walk back up |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
109 |
# * 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
|
110 |
# * stack disregarded part of the branching |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
111 |
# * 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
|
112 |
|
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
113 |
# track what changeset has been |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
114 |
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
|
115 |
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
|
116 |
# starts from repository roots |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
117 |
# 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
|
118 |
stack = children[nullrev] |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
119 |
if not stack: |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
120 |
return [] |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
121 |
if 1 < len(stack): |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
122 |
stack.sort(key=n, reverse=True) |
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 |
# 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
|
125 |
result = [] |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
126 |
|
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
127 |
current = stack.pop() |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
128 |
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
|
129 |
if current is None: |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
130 |
# 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
|
131 |
current = stack.pop() |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
132 |
if seen[current]: |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
133 |
current = None |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
134 |
continue |
3311
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
135 |
ps = filterparents(parents(current)) |
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
136 |
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
|
137 |
# 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
|
138 |
# 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
|
139 |
# 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
|
140 |
current = None |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
141 |
continue |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
142 |
assert not seen[current] |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
143 |
seen[current] = True |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
144 |
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
|
145 |
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
|
146 |
mergecallback(result, current) |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
147 |
cs = children[current] |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
148 |
if not cs: |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
149 |
current = None |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
150 |
elif 1 == len(cs): |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
151 |
current = cs[0] |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
152 |
else: |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
153 |
cs.sort(key=n, reverse=True) |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
154 |
current = cs.pop() # proceed on smallest |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
155 |
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
|
156 |
assert len(result) == len(set(result)) |
556316fe4b4f
stablesort: extract in its own module
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff
changeset
|
157 |
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
|
158 |
|
3254
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
159 |
def stablesort_mergepoint_multirevs(repo, revs): |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
160 |
"""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
|
161 |
|
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
162 |
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
|
163 |
tie breaker. |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
164 |
""" |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
165 |
cl = repo.changelog |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
166 |
tiebreaker = _mergepoint_tie_breaker(repo) |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
167 |
if not revs: |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
168 |
return [] |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
169 |
elif len(revs) == 1: |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
170 |
heads = list(revs) |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
171 |
else: |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
172 |
# keeps heads only |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
173 |
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
|
174 |
|
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
175 |
results = [] |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
176 |
while heads: |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
177 |
h = heads.pop() |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
178 |
if revs: |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
179 |
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
|
180 |
else: |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
181 |
bound = cl.ancestors([h], inclusive=True) |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
182 |
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
|
183 |
if len(results) == 1: |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
184 |
return results[0] |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
185 |
finalresults = [] |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
186 |
for r in results[::-1]: |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
187 |
finalresults.extend(r) |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
188 |
return finalresults |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
189 |
|
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
190 |
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
|
191 |
"""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
|
192 |
|
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
193 |
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
|
194 |
""" |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
195 |
# Various notes: |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
196 |
# |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
197 |
# * 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
|
198 |
cl = repo.changelog |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
199 |
parents = cl.parentrevs |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
200 |
nullrev = nodemod.nullrev |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
201 |
tiebreaker = _mergepoint_tie_breaker(repo) |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
202 |
# 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
|
203 |
children = collections.defaultdict(set) |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
204 |
parentmap = {} |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
205 |
for r in revs: |
3311
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
206 |
ps = filterparents(parents(r)) |
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
207 |
if 2 <= len(ps): |
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
208 |
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
|
209 |
parentmap[r] = ps |
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
210 |
for p in ps: |
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
211 |
children[p].add(r) |
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
212 |
if not ps: |
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
213 |
children[nullrev].add(r) |
3254
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
214 |
# step two: walk again, |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
215 |
stack = [head] |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
216 |
resultset = set() |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
217 |
result = [] |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
218 |
|
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
219 |
def add(current): |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
220 |
resultset.add(current) |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
221 |
result.append(current) |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
222 |
|
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
223 |
while stack: |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
224 |
current = stack.pop() |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
225 |
add(current) |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
226 |
parents = parentmap[current] |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
227 |
for p in parents: |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
228 |
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
|
229 |
# 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
|
230 |
continue |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
231 |
if p in revs: |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
232 |
stack.append(p) |
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 |
result.reverse() |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
235 |
assert len(result) == len(resultset) |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
236 |
return result |
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
237 |
|
3256
c82a2632327e
stablesort: add a --limit argument
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3255
diff
changeset
|
238 |
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
|
239 |
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
|
240 |
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
|
241 |
return [] |
bb3f8c8c1232
stablesort: introduce a mergepoint based method focused on head
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3254
diff
changeset
|
242 |
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
|
243 |
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
|
244 |
% len(heads)) |
bb3f8c8c1232
stablesort: introduce a mergepoint based method focused on head
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3254
diff
changeset
|
245 |
head = heads.first() |
3256
c82a2632327e
stablesort: add a --limit argument
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3255
diff
changeset
|
246 |
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
|
247 |
if limit is None: |
c82a2632327e
stablesort: add a --limit argument
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3255
diff
changeset
|
248 |
return revs |
c82a2632327e
stablesort: add a --limit argument
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3255
diff
changeset
|
249 |
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
|
250 |
|
3262
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
251 |
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
|
252 |
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
|
253 |
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
|
254 |
return [] |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
255 |
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
|
256 |
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
|
257 |
% len(heads)) |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
258 |
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
|
259 |
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
|
260 |
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
|
261 |
return revs |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
262 |
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
|
263 |
|
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
264 |
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
|
265 |
"""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
|
266 |
|
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
267 |
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
|
268 |
tie breaker. |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
269 |
""" |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
270 |
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
|
271 |
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
|
272 |
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
|
273 |
|
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
274 |
top = [head] |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
275 |
mid = [] |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
276 |
bottom = [] |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
277 |
|
3311
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
278 |
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
|
279 |
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
|
280 |
top.append(ps[0]) |
3311
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
281 |
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
|
282 |
top.reverse() |
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
283 |
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
|
284 |
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
|
285 |
|
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
286 |
# 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
|
287 |
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
|
288 |
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
|
289 |
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
|
290 |
|
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
291 |
# 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
|
292 |
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
|
293 |
|
774f69d74ec2
stablesort: start implementing more advanced version of headstart sorting
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3256
diff
changeset
|
294 |
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
|
295 |
|
3263
07678f7a4481
stablesort: introduce a cache object
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3262
diff
changeset
|
296 |
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
|
297 |
heads = repo.revs('heads(%ld)', revs) |
07678f7a4481
stablesort: introduce a cache object
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3262
diff
changeset
|
298 |
if not heads: |
07678f7a4481
stablesort: introduce a cache object
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3262
diff
changeset
|
299 |
return [] |
07678f7a4481
stablesort: introduce a cache object
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3262
diff
changeset
|
300 |
elif 2 < len(heads): |
07678f7a4481
stablesort: introduce a cache object
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3262
diff
changeset
|
301 |
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
|
302 |
% len(heads)) |
07678f7a4481
stablesort: introduce a cache object
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3262
diff
changeset
|
303 |
head = heads.first() |
07678f7a4481
stablesort: introduce a cache object
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3262
diff
changeset
|
304 |
cache = stablesortcache() |
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
305 |
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
|
306 |
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
|
307 |
if first != second: |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
308 |
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
|
309 |
' %s\n' |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
310 |
' %s\n' % (first, second)) |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
311 |
return second |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
312 |
|
3263
07678f7a4481
stablesort: introduce a cache object
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3262
diff
changeset
|
313 |
class stablesortcache(object): |
07678f7a4481
stablesort: introduce a cache object
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3262
diff
changeset
|
314 |
|
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
315 |
def __init__(self): |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
316 |
self._jumps = collections.defaultdict(lambda: None) |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
317 |
|
3263
07678f7a4481
stablesort: introduce a cache object
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3262
diff
changeset
|
318 |
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
|
319 |
result = [] |
3300
2d49773a378b
stablesort: make the iteration from head available to all
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3267
diff
changeset
|
320 |
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
|
321 |
result.append(r) |
70b5bc95efbe
stablesort: extract a '_revsfrom' method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3263
diff
changeset
|
322 |
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
|
323 |
break |
70b5bc95efbe
stablesort: extract a '_revsfrom' method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3263
diff
changeset
|
324 |
result.reverse() |
70b5bc95efbe
stablesort: extract a '_revsfrom' method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3263
diff
changeset
|
325 |
return result |
70b5bc95efbe
stablesort: extract a '_revsfrom' method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3263
diff
changeset
|
326 |
|
3300
2d49773a378b
stablesort: make the iteration from head available to all
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3267
diff
changeset
|
327 |
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
|
328 |
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
|
329 |
cl = repo.changelog |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
330 |
parentsfunc = cl.parentrevs |
3266
bc173e7f3b6f
stablesort: simplify processing of non-merge changesets
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3265
diff
changeset
|
331 |
|
bc173e7f3b6f
stablesort: simplify processing of non-merge changesets
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3265
diff
changeset
|
332 |
def parents(rev): |
3311
df399e00c10b
stablesort: use the filtered parents utility
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3300
diff
changeset
|
333 |
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
|
334 |
|
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
335 |
def oneparent(rev): |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
336 |
ps = parents(rev) |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
337 |
if not ps: |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
338 |
return None |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
339 |
if len(ps) == 1: |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
340 |
return ps[0] |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
341 |
return max(ps, key=tiebreaker) |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
342 |
|
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
343 |
def walkfrom(start, stop, oneparent): |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
344 |
current = oneparent(start) |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
345 |
while current is not None: |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
346 |
yield current |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
347 |
current = oneparent(start) |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
348 |
|
3266
bc173e7f3b6f
stablesort: simplify processing of non-merge changesets
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3265
diff
changeset
|
349 |
current = head |
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
350 |
previous_current_1 = object() |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
351 |
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
|
352 |
|
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
353 |
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
|
354 |
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
|
355 |
previous_current_1 = current |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
356 |
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
|
357 |
|
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
358 |
jumps = self._jumps[current] |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
359 |
if jumps is not None: |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
360 |
# 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
|
361 |
# the exclusive size. |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
362 |
for j in jumps: |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
363 |
jump_point = j[0] |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
364 |
jump_dest = j[1] |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
365 |
if current == jump_point: |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
366 |
yield current |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
367 |
else: |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
368 |
while current != jump_point: |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
369 |
yield current |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
370 |
current = oneparent(current) |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
371 |
yield current |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
372 |
current = jump_dest |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
373 |
continue |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
374 |
|
3266
bc173e7f3b6f
stablesort: simplify processing of non-merge changesets
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3265
diff
changeset
|
375 |
yield current |
3267
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
376 |
|
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
377 |
ps = parents(current) |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
378 |
if not ps: |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
379 |
current = None # break |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
380 |
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
|
381 |
current = ps[0] |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
382 |
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
|
383 |
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
|
384 |
|
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
385 |
rev = current |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
386 |
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
|
387 |
|
3320
360a543930c6
stablesort: stop recording jump type
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3319
diff
changeset
|
388 |
def recordjump(source, destination): |
360a543930c6
stablesort: stop recording jump type
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3319
diff
changeset
|
389 |
jump = (source, destination) |
3319
bacb44f4f33e
stablesort: pass a jump recording function instead of a list
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3318
diff
changeset
|
390 |
jumps.append(jump) |
3317
a950e6cc5e9e
stablesort: clarify subcall to the exclusive side
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3315
diff
changeset
|
391 |
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
|
392 |
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
|
393 |
tiebreaker, recordjump): |
3267
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
394 |
yield rev |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
395 |
|
3320
360a543930c6
stablesort: stop recording jump type
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3319
diff
changeset
|
396 |
recordjump(rev, lower_parent) |
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
397 |
|
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
398 |
self._jumps[current] = jumps |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
399 |
|
3267
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
400 |
current = lower_parent |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
401 |
|
3317
a950e6cc5e9e
stablesort: clarify subcall to the exclusive side
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3315
diff
changeset
|
402 |
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
|
403 |
recordjump): |
3267
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
404 |
|
3317
a950e6cc5e9e
stablesort: clarify subcall to the exclusive side
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3315
diff
changeset
|
405 |
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
|
406 |
|
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
407 |
stack = [] |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
408 |
seen = set() |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
409 |
children = collections.defaultdict(set) |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
410 |
if not exclusive: |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
411 |
current = None |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
412 |
else: |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
413 |
current = higher |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
414 |
bound = set(exclusive) |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
415 |
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
|
416 |
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
|
417 |
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
|
418 |
|
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
419 |
previous_current = None |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
420 |
while current is not None: |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
421 |
assert current is not previous_current |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
422 |
yield current |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
423 |
seen.add(current) |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
424 |
previous_current = current |
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
425 |
|
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
426 |
all_parents = parents(current) |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
427 |
|
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
428 |
max_parents = None |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
429 |
if 1 == len(all_parents): |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
430 |
max_parents = all_parents[0] |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
431 |
if 2 <= len(all_parents): |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
432 |
max_parents = max(all_parents, key=tiebreaker) |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
433 |
|
3320
360a543930c6
stablesort: stop recording jump type
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3319
diff
changeset
|
434 |
jump = False |
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
435 |
|
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
436 |
ready_parents = [p for p in all_parents |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
437 |
if children[p].issubset(seen)] |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
438 |
|
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
439 |
okay_parents = [p for p in ready_parents if p in bound] |
3266
bc173e7f3b6f
stablesort: simplify processing of non-merge changesets
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3265
diff
changeset
|
440 |
|
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
441 |
if (len(all_parents) != len(ready_parents) |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
442 |
and max_parents not in ready_parents): |
3320
360a543930c6
stablesort: stop recording jump type
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3319
diff
changeset
|
443 |
jump = True |
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
444 |
elif (len(ready_parents) != len(okay_parents) |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
445 |
and max_parents not in okay_parents): |
3320
360a543930c6
stablesort: stop recording jump type
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3319
diff
changeset
|
446 |
jump = True |
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
447 |
elif not all_parents: |
3320
360a543930c6
stablesort: stop recording jump type
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3319
diff
changeset
|
448 |
jump = True |
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
449 |
|
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
450 |
if not okay_parents: |
3320
360a543930c6
stablesort: stop recording jump type
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3319
diff
changeset
|
451 |
if jump is None: |
360a543930c6
stablesort: stop recording jump type
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3319
diff
changeset
|
452 |
jump = True |
3267
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
453 |
if stack: |
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
454 |
next = stack.pop() |
3267
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
455 |
else: |
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
456 |
next = None |
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
457 |
elif len(okay_parents) == 1: |
3318
058120e9d32f
stablesort: minor indent fix
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3317
diff
changeset
|
458 |
next = okay_parents[0] |
3267
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
459 |
else: |
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
460 |
lower_parent, higher_parent = sorted(ready_parents, key=tiebreaker) |
3267
f9206b009f48
stablesort: write a flat version of the algorithm
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3266
diff
changeset
|
461 |
stack.append(lower_parent) |
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
462 |
next = higher_parent |
3320
360a543930c6
stablesort: stop recording jump type
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3319
diff
changeset
|
463 |
if jump is not None and next is not None: |
360a543930c6
stablesort: stop recording jump type
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3319
diff
changeset
|
464 |
recordjump(current, next) |
3315
c153441cdc0e
stablesort: record, cache and reuse jump
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3314
diff
changeset
|
465 |
current = next |
3263
07678f7a4481
stablesort: introduce a cache object
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3262
diff
changeset
|
466 |
|
3246
543708c3f754
stablesort: add a 'method' argument to the debugstablesort command
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3245
diff
changeset
|
467 |
_methodmap = { |
543708c3f754
stablesort: add a 'method' argument to the debugstablesort command
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3245
diff
changeset
|
468 |
'branchpoint': stablesort_branchpoint, |
3254
00e20077bccf
stablesort: introduce a "mergepoint" method
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3246
diff
changeset
|
469 |
'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
|
470 |
'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
|
471 |
'headstart': stablesort_mergepoint_head_debug, |
3263
07678f7a4481
stablesort: introduce a cache object
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3262
diff
changeset
|
472 |
'headcached': stablesort_mergepoint_head_cached, |
3246
543708c3f754
stablesort: add a 'method' argument to the debugstablesort command
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
3245
diff
changeset
|
473 |
} |