Mercurial > public > mercurial-scm > hg-stable

annotate mercurial/obsutil.py @ 33151:0a370b93cca2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
obsutil: move 'allsuccessors' to the new modules We have a new 'obsutil' module now. We move the high level utility there to bring 'obsolete.py' back to a more reasonable size.
author Pierre-Yves David <pierre-yves.david@octobus.net>
date Tue, 27 Jun 2017 01:36:20 +0200
parents d0e5bf12f314
children 7017567ebdf2
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
32897
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
1 # obsutil.py - utility functions for obsolescence
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
2 #
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
3 # Copyright 2017 Boris Feld <boris.feld@octobus.net>
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
4 #
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
5 # This software may be used and distributed according to the terms of the
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
6 # GNU General Public License version 2 or any later version.
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
7
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
8 from __future__ import absolute_import
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
9
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
10 def closestpredecessors(repo, nodeid):
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
11 """yield the list of next predecessors pointing on visible changectx nodes
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
12
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
13 This function respect the repoview filtering, filtered revision will be
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
14 considered missing.
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
15 """
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
16
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
17 precursors = repo.obsstore.precursors
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
18 stack = [nodeid]
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
19 seen = set(stack)
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
20
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
21 while stack:
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
22 current = stack.pop()
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
23 currentpreccs = precursors.get(current, ())
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
24
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
25 for prec in currentpreccs:
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
26 precnodeid = prec[0]
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
27
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
28 # Basic cycle protection
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
29 if precnodeid in seen:
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
30 continue
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
31 seen.add(precnodeid)
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
32
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
33 if precnodeid in repo:
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
34 yield precnodeid
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
35 else:
1858fc2327ef template: add predecessors template
Boris Feld <boris.feld@octobus.net>
parents:
diff changeset
36 stack.append(precnodeid)
33148
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
37
33150
d0e5bf12f314 obsutil: move 'allprecursors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33149
diff changeset
38 def allprecursors(obsstore, nodes, ignoreflags=0):
d0e5bf12f314 obsutil: move 'allprecursors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33149
diff changeset
39 """Yield node for every precursors of <nodes>.
d0e5bf12f314 obsutil: move 'allprecursors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33149
diff changeset
40
d0e5bf12f314 obsutil: move 'allprecursors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33149
diff changeset
41 Some precursors may be unknown locally.
d0e5bf12f314 obsutil: move 'allprecursors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33149
diff changeset
42
d0e5bf12f314 obsutil: move 'allprecursors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33149
diff changeset
43 This is a linear yield unsuited to detecting folded changesets. It includes
d0e5bf12f314 obsutil: move 'allprecursors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33149
diff changeset
44 initial nodes too."""
d0e5bf12f314 obsutil: move 'allprecursors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33149
diff changeset
45
d0e5bf12f314 obsutil: move 'allprecursors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33149
diff changeset
46 remaining = set(nodes)
d0e5bf12f314 obsutil: move 'allprecursors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33149
diff changeset
47 seen = set(remaining)
d0e5bf12f314 obsutil: move 'allprecursors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33149
diff changeset
48 while remaining:
d0e5bf12f314 obsutil: move 'allprecursors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33149
diff changeset
49 current = remaining.pop()
d0e5bf12f314 obsutil: move 'allprecursors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33149
diff changeset
50 yield current
d0e5bf12f314 obsutil: move 'allprecursors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33149
diff changeset
51 for mark in obsstore.precursors.get(current, ()):
d0e5bf12f314 obsutil: move 'allprecursors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33149
diff changeset
52 # ignore marker flagged with specified flag
d0e5bf12f314 obsutil: move 'allprecursors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33149
diff changeset
53 if mark[2] & ignoreflags:
d0e5bf12f314 obsutil: move 'allprecursors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33149
diff changeset
54 continue
d0e5bf12f314 obsutil: move 'allprecursors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33149
diff changeset
55 suc = mark[0]
d0e5bf12f314 obsutil: move 'allprecursors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33149
diff changeset
56 if suc not in seen:
d0e5bf12f314 obsutil: move 'allprecursors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33149
diff changeset
57 seen.add(suc)
d0e5bf12f314 obsutil: move 'allprecursors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33149
diff changeset
58 remaining.add(suc)
d0e5bf12f314 obsutil: move 'allprecursors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33149
diff changeset
59
33151
0a370b93cca2 obsutil: move 'allsuccessors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33150
diff changeset
60 def allsuccessors(obsstore, nodes, ignoreflags=0):
0a370b93cca2 obsutil: move 'allsuccessors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33150
diff changeset
61 """Yield node for every successor of <nodes>.
0a370b93cca2 obsutil: move 'allsuccessors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33150
diff changeset
62
0a370b93cca2 obsutil: move 'allsuccessors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33150
diff changeset
63 Some successors may be unknown locally.
0a370b93cca2 obsutil: move 'allsuccessors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33150
diff changeset
64
0a370b93cca2 obsutil: move 'allsuccessors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33150
diff changeset
65 This is a linear yield unsuited to detecting split changesets. It includes
0a370b93cca2 obsutil: move 'allsuccessors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33150
diff changeset
66 initial nodes too."""
0a370b93cca2 obsutil: move 'allsuccessors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33150
diff changeset
67 remaining = set(nodes)
0a370b93cca2 obsutil: move 'allsuccessors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33150
diff changeset
68 seen = set(remaining)
0a370b93cca2 obsutil: move 'allsuccessors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33150
diff changeset
69 while remaining:
0a370b93cca2 obsutil: move 'allsuccessors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33150
diff changeset
70 current = remaining.pop()
0a370b93cca2 obsutil: move 'allsuccessors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33150
diff changeset
71 yield current
0a370b93cca2 obsutil: move 'allsuccessors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33150
diff changeset
72 for mark in obsstore.successors.get(current, ()):
0a370b93cca2 obsutil: move 'allsuccessors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33150
diff changeset
73 # ignore marker flagged with specified flag
0a370b93cca2 obsutil: move 'allsuccessors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33150
diff changeset
74 if mark[2] & ignoreflags:
0a370b93cca2 obsutil: move 'allsuccessors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33150
diff changeset
75 continue
0a370b93cca2 obsutil: move 'allsuccessors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33150
diff changeset
76 for suc in mark[1]:
0a370b93cca2 obsutil: move 'allsuccessors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33150
diff changeset
77 if suc not in seen:
0a370b93cca2 obsutil: move 'allsuccessors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33150
diff changeset
78 seen.add(suc)
0a370b93cca2 obsutil: move 'allsuccessors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33150
diff changeset
79 remaining.add(suc)
0a370b93cca2 obsutil: move 'allsuccessors' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33150
diff changeset
80
33149
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
81 def _filterprunes(markers):
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
82 """return a set with no prune markers"""
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
83 return set(m for m in markers if m[1])
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
84
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
85 def exclusivemarkers(repo, nodes):
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
86 """set of markers relevant to "nodes" but no other locally-known nodes
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
87
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
88 This function compute the set of markers "exclusive" to a locally-known
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
89 node. This means we walk the markers starting from <nodes> until we reach a
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
90 locally-known precursors outside of <nodes>. Element of <nodes> with
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
91 locally-known successors outside of <nodes> are ignored (since their
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
92 precursors markers are also relevant to these successors).
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
93
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
94 For example:
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
95
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
96 # (A0 rewritten as A1)
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
97 #
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
98 # A0 <-1- A1 # Marker "1" is exclusive to A1
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
99
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
100 or
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
101
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
102 # (A0 rewritten as AX; AX rewritten as A1; AX is unkown locally)
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
103 #
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
104 # <-1- A0 <-2- AX <-3- A1 # Marker "2,3" are exclusive to A1
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
105
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
106 or
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
107
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
108 # (A0 has unknown precursors, A0 rewritten as A1 and A2 (divergence))
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
109 #
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
110 # <-2- A1 # Marker "2" is exclusive to A0,A1
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
111 # /
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
112 # <-1- A0
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
113 # \
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
114 # <-3- A2 # Marker "3" is exclusive to A0,A2
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
115 #
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
116 # in addition:
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
117 #
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
118 # Markers "2,3" are exclusive to A1,A2
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
119 # Markers "1,2,3" are exclusive to A0,A1,A2
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
120
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
121 See test/test-obsolete-bundle-strip.t for more examples.
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
122
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
123 An example usage is strip. When stripping a changeset, we also want to
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
124 strip the markers exclusive to this changeset. Otherwise we would have
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
125 "dangling"" obsolescence markers from its precursors: Obsolescence markers
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
126 marking a node as obsolete without any successors available locally.
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
127
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
128 As for relevant markers, the prune markers for children will be followed.
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
129 Of course, they will only be followed if the pruned children is
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
130 locally-known. Since the prune markers are relevant to the pruned node.
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
131 However, while prune markers are considered relevant to the parent of the
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
132 pruned changesets, prune markers for locally-known changeset (with no
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
133 successors) are considered exclusive to the pruned nodes. This allows
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
134 to strip the prune markers (with the rest of the exclusive chain) alongside
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
135 the pruned changesets.
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
136 """
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
137 # running on a filtered repository would be dangerous as markers could be
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
138 # reported as exclusive when they are relevant for other filtered nodes.
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
139 unfi = repo.unfiltered()
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
140
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
141 # shortcut to various useful item
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
142 nm = unfi.changelog.nodemap
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
143 precursorsmarkers = unfi.obsstore.precursors
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
144 successormarkers = unfi.obsstore.successors
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
145 childrenmarkers = unfi.obsstore.children
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
146
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
147 # exclusive markers (return of the function)
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
148 exclmarkers = set()
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
149 # we need fast membership testing
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
150 nodes = set(nodes)
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
151 # looking for head in the obshistory
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
152 #
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
153 # XXX we are ignoring all issues in regard with cycle for now.
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
154 stack = [n for n in nodes if not _filterprunes(successormarkers.get(n, ()))]
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
155 stack.sort()
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
156 # nodes already stacked
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
157 seennodes = set(stack)
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
158 while stack:
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
159 current = stack.pop()
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
160 # fetch precursors markers
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
161 markers = list(precursorsmarkers.get(current, ()))
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
162 # extend the list with prune markers
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
163 for mark in successormarkers.get(current, ()):
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
164 if not mark[1]:
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
165 markers.append(mark)
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
166 # and markers from children (looking for prune)
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
167 for mark in childrenmarkers.get(current, ()):
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
168 if not mark[1]:
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
169 markers.append(mark)
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
170 # traverse the markers
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
171 for mark in markers:
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
172 if mark in exclmarkers:
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
173 # markers already selected
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
174 continue
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
175
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
176 # If the markers is about the current node, select it
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
177 #
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
178 # (this delay the addition of markers from children)
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
179 if mark[1] or mark[0] == current:
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
180 exclmarkers.add(mark)
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
181
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
182 # should we keep traversing through the precursors?
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
183 prec = mark[0]
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
184
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
185 # nodes in the stack or already processed
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
186 if prec in seennodes:
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
187 continue
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
188
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
189 # is this a locally known node ?
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
190 known = prec in nm
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
191 # if locally-known and not in the <nodes> set the traversal
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
192 # stop here.
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
193 if known and prec not in nodes:
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
194 continue
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
195
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
196 # do not keep going if there are unselected markers pointing to this
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
197 # nodes. If we end up traversing these unselected markers later the
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
198 # node will be taken care of at that point.
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
199 precmarkers = _filterprunes(successormarkers.get(prec))
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
200 if precmarkers.issubset(exclmarkers):
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
201 seennodes.add(prec)
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
202 stack.append(prec)
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
203
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
204 return exclmarkers
d09ae850296d obsutil: move 'exclusivemarkers' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 33148
diff changeset
205
33148
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
206 def successorssets(repo, initialnode, cache=None):
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
207 """Return set of all latest successors of initial nodes
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
208
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
209 The successors set of a changeset A are the group of revisions that succeed
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
210 A. It succeeds A as a consistent whole, each revision being only a partial
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
211 replacement. The successors set contains non-obsolete changesets only.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
212
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
213 This function returns the full list of successor sets which is why it
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
214 returns a list of tuples and not just a single tuple. Each tuple is a valid
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
215 successors set. Note that (A,) may be a valid successors set for changeset A
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
216 (see below).
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
217
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
218 In most cases, a changeset A will have a single element (e.g. the changeset
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
219 A is replaced by A') in its successors set. Though, it is also common for a
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
220 changeset A to have no elements in its successor set (e.g. the changeset
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
221 has been pruned). Therefore, the returned list of successors sets will be
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
222 [(A',)] or [], respectively.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
223
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
224 When a changeset A is split into A' and B', however, it will result in a
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
225 successors set containing more than a single element, i.e. [(A',B')].
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
226 Divergent changesets will result in multiple successors sets, i.e. [(A',),
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
227 (A'')].
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
228
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
229 If a changeset A is not obsolete, then it will conceptually have no
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
230 successors set. To distinguish this from a pruned changeset, the successor
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
231 set will contain itself only, i.e. [(A,)].
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
232
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
233 Finally, successors unknown locally are considered to be pruned (obsoleted
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
234 without any successors).
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
235
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
236 The optional `cache` parameter is a dictionary that may contain precomputed
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
237 successors sets. It is meant to reuse the computation of a previous call to
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
238 `successorssets` when multiple calls are made at the same time. The cache
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
239 dictionary is updated in place. The caller is responsible for its life
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
240 span. Code that makes multiple calls to `successorssets` *must* use this
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
241 cache mechanism or suffer terrible performance.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
242 """
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
243
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
244 succmarkers = repo.obsstore.successors
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
245
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
246 # Stack of nodes we search successors sets for
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
247 toproceed = [initialnode]
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
248 # set version of above list for fast loop detection
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
249 # element added to "toproceed" must be added here
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
250 stackedset = set(toproceed)
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
251 if cache is None:
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
252 cache = {}
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
253
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
254 # This while loop is the flattened version of a recursive search for
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
255 # successors sets
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
256 #
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
257 # def successorssets(x):
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
258 # successors = directsuccessors(x)
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
259 # ss = [[]]
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
260 # for succ in directsuccessors(x):
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
261 # # product as in itertools cartesian product
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
262 # ss = product(ss, successorssets(succ))
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
263 # return ss
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
264 #
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
265 # But we can not use plain recursive calls here:
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
266 # - that would blow the python call stack
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
267 # - obsolescence markers may have cycles, we need to handle them.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
268 #
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
269 # The `toproceed` list act as our call stack. Every node we search
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
270 # successors set for are stacked there.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
271 #
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
272 # The `stackedset` is set version of this stack used to check if a node is
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
273 # already stacked. This check is used to detect cycles and prevent infinite
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
274 # loop.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
275 #
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
276 # successors set of all nodes are stored in the `cache` dictionary.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
277 #
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
278 # After this while loop ends we use the cache to return the successors sets
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
279 # for the node requested by the caller.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
280 while toproceed:
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
281 # Every iteration tries to compute the successors sets of the topmost
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
282 # node of the stack: CURRENT.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
283 #
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
284 # There are four possible outcomes:
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
285 #
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
286 # 1) We already know the successors sets of CURRENT:
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
287 # -> mission accomplished, pop it from the stack.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
288 # 2) Node is not obsolete:
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
289 # -> the node is its own successors sets. Add it to the cache.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
290 # 3) We do not know successors set of direct successors of CURRENT:
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
291 # -> We add those successors to the stack.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
292 # 4) We know successors sets of all direct successors of CURRENT:
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
293 # -> We can compute CURRENT successors set and add it to the
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
294 # cache.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
295 #
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
296 current = toproceed[-1]
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
297 if current in cache:
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
298 # case (1): We already know the successors sets
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
299 stackedset.remove(toproceed.pop())
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
300 elif current not in succmarkers:
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
301 # case (2): The node is not obsolete.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
302 if current in repo:
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
303 # We have a valid last successors.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
304 cache[current] = [(current,)]
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
305 else:
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
306 # Final obsolete version is unknown locally.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
307 # Do not count that as a valid successors
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
308 cache[current] = []
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
309 else:
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
310 # cases (3) and (4)
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
311 #
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
312 # We proceed in two phases. Phase 1 aims to distinguish case (3)
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
313 # from case (4):
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
314 #
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
315 # For each direct successors of CURRENT, we check whether its
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
316 # successors sets are known. If they are not, we stack the
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
317 # unknown node and proceed to the next iteration of the while
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
318 # loop. (case 3)
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
319 #
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
320 # During this step, we may detect obsolescence cycles: a node
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
321 # with unknown successors sets but already in the call stack.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
322 # In such a situation, we arbitrary set the successors sets of
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
323 # the node to nothing (node pruned) to break the cycle.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
324 #
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
325 # If no break was encountered we proceed to phase 2.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
326 #
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
327 # Phase 2 computes successors sets of CURRENT (case 4); see details
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
328 # in phase 2 itself.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
329 #
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
330 # Note the two levels of iteration in each phase.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
331 # - The first one handles obsolescence markers using CURRENT as
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
332 # precursor (successors markers of CURRENT).
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
333 #
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
334 # Having multiple entry here means divergence.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
335 #
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
336 # - The second one handles successors defined in each marker.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
337 #
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
338 # Having none means pruned node, multiple successors means split,
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
339 # single successors are standard replacement.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
340 #
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
341 for mark in sorted(succmarkers[current]):
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
342 for suc in mark[1]:
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
343 if suc not in cache:
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
344 if suc in stackedset:
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
345 # cycle breaking
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
346 cache[suc] = []
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
347 else:
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
348 # case (3) If we have not computed successors sets
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
349 # of one of those successors we add it to the
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
350 # `toproceed` stack and stop all work for this
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
351 # iteration.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
352 toproceed.append(suc)
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
353 stackedset.add(suc)
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
354 break
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
355 else:
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
356 continue
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
357 break
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
358 else:
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
359 # case (4): we know all successors sets of all direct
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
360 # successors
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
361 #
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
362 # Successors set contributed by each marker depends on the
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
363 # successors sets of all its "successors" node.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
364 #
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
365 # Each different marker is a divergence in the obsolescence
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
366 # history. It contributes successors sets distinct from other
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
367 # markers.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
368 #
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
369 # Within a marker, a successor may have divergent successors
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
370 # sets. In such a case, the marker will contribute multiple
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
371 # divergent successors sets. If multiple successors have
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
372 # divergent successors sets, a Cartesian product is used.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
373 #
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
374 # At the end we post-process successors sets to remove
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
375 # duplicated entry and successors set that are strict subset of
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
376 # another one.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
377 succssets = []
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
378 for mark in sorted(succmarkers[current]):
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
379 # successors sets contributed by this marker
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
380 markss = [[]]
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
381 for suc in mark[1]:
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
382 # cardinal product with previous successors
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
383 productresult = []
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
384 for prefix in markss:
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
385 for suffix in cache[suc]:
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
386 newss = list(prefix)
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
387 for part in suffix:
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
388 # do not duplicated entry in successors set
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
389 # first entry wins.
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
390 if part not in newss:
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
391 newss.append(part)
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
392 productresult.append(newss)
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
393 markss = productresult
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
394 succssets.extend(markss)
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
395 # remove duplicated and subset
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
396 seen = []
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
397 final = []
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
398 candidate = sorted(((set(s), s) for s in succssets if s),
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
399 key=lambda x: len(x[1]), reverse=True)
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
400 for setversion, listversion in candidate:
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
401 for seenset in seen:
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
402 if setversion.issubset(seenset):
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
403 break
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
404 else:
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
405 final.append(listversion)
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
406 seen.append(setversion)
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
407 final.reverse() # put small successors set first
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
408 cache[current] = final
4f49810a1011 obsutil: move 'successorssets' to the new modules
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 32897
diff changeset
409 return cache[initialnode]