##// END OF EJS Templates
dagutil: use a listcomp instead of a map()...
Augie Fackler -
r34729:09397d0d default
parent child Browse files
Show More
@@ -1,286 +1,286 b''
1 # dagutil.py - dag utilities for mercurial
1 # dagutil.py - dag utilities for mercurial
2 #
2 #
3 # Copyright 2010 Benoit Boissinot <bboissin@gmail.com>
3 # Copyright 2010 Benoit Boissinot <bboissin@gmail.com>
4 # and Peter Arrenbrecht <peter@arrenbrecht.ch>
4 # and Peter Arrenbrecht <peter@arrenbrecht.ch>
5 #
5 #
6 # This software may be used and distributed according to the terms of the
6 # This software may be used and distributed according to the terms of the
7 # GNU General Public License version 2 or any later version.
7 # GNU General Public License version 2 or any later version.
8
8
9 from __future__ import absolute_import
9 from __future__ import absolute_import
10
10
11 from .i18n import _
11 from .i18n import _
12 from .node import nullrev
12 from .node import nullrev
13
13
14 class basedag(object):
14 class basedag(object):
15 '''generic interface for DAGs
15 '''generic interface for DAGs
16
16
17 terms:
17 terms:
18 "ix" (short for index) identifies a nodes internally,
18 "ix" (short for index) identifies a nodes internally,
19 "id" identifies one externally.
19 "id" identifies one externally.
20
20
21 All params are ixs unless explicitly suffixed otherwise.
21 All params are ixs unless explicitly suffixed otherwise.
22 Pluralized params are lists or sets.
22 Pluralized params are lists or sets.
23 '''
23 '''
24
24
25 def __init__(self):
25 def __init__(self):
26 self._inverse = None
26 self._inverse = None
27
27
28 def nodeset(self):
28 def nodeset(self):
29 '''set of all node ixs'''
29 '''set of all node ixs'''
30 raise NotImplementedError
30 raise NotImplementedError
31
31
32 def heads(self):
32 def heads(self):
33 '''list of head ixs'''
33 '''list of head ixs'''
34 raise NotImplementedError
34 raise NotImplementedError
35
35
36 def parents(self, ix):
36 def parents(self, ix):
37 '''list of parents ixs of ix'''
37 '''list of parents ixs of ix'''
38 raise NotImplementedError
38 raise NotImplementedError
39
39
40 def inverse(self):
40 def inverse(self):
41 '''inverse DAG, where parents becomes children, etc.'''
41 '''inverse DAG, where parents becomes children, etc.'''
42 raise NotImplementedError
42 raise NotImplementedError
43
43
44 def ancestorset(self, starts, stops=None):
44 def ancestorset(self, starts, stops=None):
45 '''
45 '''
46 set of all ancestors of starts (incl), but stop walk at stops (excl)
46 set of all ancestors of starts (incl), but stop walk at stops (excl)
47 '''
47 '''
48 raise NotImplementedError
48 raise NotImplementedError
49
49
50 def descendantset(self, starts, stops=None):
50 def descendantset(self, starts, stops=None):
51 '''
51 '''
52 set of all descendants of starts (incl), but stop walk at stops (excl)
52 set of all descendants of starts (incl), but stop walk at stops (excl)
53 '''
53 '''
54 return self.inverse().ancestorset(starts, stops)
54 return self.inverse().ancestorset(starts, stops)
55
55
56 def headsetofconnecteds(self, ixs):
56 def headsetofconnecteds(self, ixs):
57 '''
57 '''
58 subset of connected list of ixs so that no node has a descendant in it
58 subset of connected list of ixs so that no node has a descendant in it
59
59
60 By "connected list" we mean that if an ancestor and a descendant are in
60 By "connected list" we mean that if an ancestor and a descendant are in
61 the list, then so is at least one path connecting them.
61 the list, then so is at least one path connecting them.
62 '''
62 '''
63 raise NotImplementedError
63 raise NotImplementedError
64
64
65 def externalize(self, ix):
65 def externalize(self, ix):
66 '''return a node id'''
66 '''return a node id'''
67 return self._externalize(ix)
67 return self._externalize(ix)
68
68
69 def externalizeall(self, ixs):
69 def externalizeall(self, ixs):
70 '''return a list of (or set if given a set) of node ids'''
70 '''return a list of (or set if given a set) of node ids'''
71 ids = self._externalizeall(ixs)
71 ids = self._externalizeall(ixs)
72 if isinstance(ixs, set):
72 if isinstance(ixs, set):
73 return set(ids)
73 return set(ids)
74 return list(ids)
74 return list(ids)
75
75
76 def internalize(self, id):
76 def internalize(self, id):
77 '''return a node ix'''
77 '''return a node ix'''
78 return self._internalize(id)
78 return self._internalize(id)
79
79
80 def internalizeall(self, ids, filterunknown=False):
80 def internalizeall(self, ids, filterunknown=False):
81 '''return a list of (or set if given a set) of node ixs'''
81 '''return a list of (or set if given a set) of node ixs'''
82 ixs = self._internalizeall(ids, filterunknown)
82 ixs = self._internalizeall(ids, filterunknown)
83 if isinstance(ids, set):
83 if isinstance(ids, set):
84 return set(ixs)
84 return set(ixs)
85 return list(ixs)
85 return list(ixs)
86
86
87
87
88 class genericdag(basedag):
88 class genericdag(basedag):
89 '''generic implementations for DAGs'''
89 '''generic implementations for DAGs'''
90
90
91 def ancestorset(self, starts, stops=None):
91 def ancestorset(self, starts, stops=None):
92 if stops:
92 if stops:
93 stops = set(stops)
93 stops = set(stops)
94 else:
94 else:
95 stops = set()
95 stops = set()
96 seen = set()
96 seen = set()
97 pending = list(starts)
97 pending = list(starts)
98 while pending:
98 while pending:
99 n = pending.pop()
99 n = pending.pop()
100 if n not in seen and n not in stops:
100 if n not in seen and n not in stops:
101 seen.add(n)
101 seen.add(n)
102 pending.extend(self.parents(n))
102 pending.extend(self.parents(n))
103 return seen
103 return seen
104
104
105 def headsetofconnecteds(self, ixs):
105 def headsetofconnecteds(self, ixs):
106 hds = set(ixs)
106 hds = set(ixs)
107 if not hds:
107 if not hds:
108 return hds
108 return hds
109 for n in ixs:
109 for n in ixs:
110 for p in self.parents(n):
110 for p in self.parents(n):
111 hds.discard(p)
111 hds.discard(p)
112 assert hds
112 assert hds
113 return hds
113 return hds
114
114
115
115
116 class revlogbaseddag(basedag):
116 class revlogbaseddag(basedag):
117 '''generic dag interface to a revlog'''
117 '''generic dag interface to a revlog'''
118
118
119 def __init__(self, revlog, nodeset):
119 def __init__(self, revlog, nodeset):
120 basedag.__init__(self)
120 basedag.__init__(self)
121 self._revlog = revlog
121 self._revlog = revlog
122 self._heads = None
122 self._heads = None
123 self._nodeset = nodeset
123 self._nodeset = nodeset
124
124
125 def nodeset(self):
125 def nodeset(self):
126 return self._nodeset
126 return self._nodeset
127
127
128 def heads(self):
128 def heads(self):
129 if self._heads is None:
129 if self._heads is None:
130 self._heads = self._getheads()
130 self._heads = self._getheads()
131 return self._heads
131 return self._heads
132
132
133 def _externalize(self, ix):
133 def _externalize(self, ix):
134 return self._revlog.index[ix][7]
134 return self._revlog.index[ix][7]
135 def _externalizeall(self, ixs):
135 def _externalizeall(self, ixs):
136 idx = self._revlog.index
136 idx = self._revlog.index
137 return [idx[i][7] for i in ixs]
137 return [idx[i][7] for i in ixs]
138
138
139 def _internalize(self, id):
139 def _internalize(self, id):
140 ix = self._revlog.rev(id)
140 ix = self._revlog.rev(id)
141 if ix == nullrev:
141 if ix == nullrev:
142 raise LookupError(id, self._revlog.indexfile, _('nullid'))
142 raise LookupError(id, self._revlog.indexfile, _('nullid'))
143 return ix
143 return ix
144 def _internalizeall(self, ids, filterunknown):
144 def _internalizeall(self, ids, filterunknown):
145 rl = self._revlog
145 rl = self._revlog
146 if filterunknown:
146 if filterunknown:
147 return [r for r in map(rl.nodemap.get, ids)
147 return [r for r in map(rl.nodemap.get, ids)
148 if (r is not None
148 if (r is not None
149 and r != nullrev
149 and r != nullrev
150 and r not in rl.filteredrevs)]
150 and r not in rl.filteredrevs)]
151 return map(self._internalize, ids)
151 return [self._internalize(i) for i in ids]
152
152
153
153
154 class revlogdag(revlogbaseddag):
154 class revlogdag(revlogbaseddag):
155 '''dag interface to a revlog'''
155 '''dag interface to a revlog'''
156
156
157 def __init__(self, revlog):
157 def __init__(self, revlog):
158 revlogbaseddag.__init__(self, revlog, set(revlog))
158 revlogbaseddag.__init__(self, revlog, set(revlog))
159
159
160 def _getheads(self):
160 def _getheads(self):
161 return [r for r in self._revlog.headrevs() if r != nullrev]
161 return [r for r in self._revlog.headrevs() if r != nullrev]
162
162
163 def parents(self, ix):
163 def parents(self, ix):
164 rlog = self._revlog
164 rlog = self._revlog
165 idx = rlog.index
165 idx = rlog.index
166 revdata = idx[ix]
166 revdata = idx[ix]
167 prev = revdata[5]
167 prev = revdata[5]
168 if prev != nullrev:
168 if prev != nullrev:
169 prev2 = revdata[6]
169 prev2 = revdata[6]
170 if prev2 == nullrev:
170 if prev2 == nullrev:
171 return [prev]
171 return [prev]
172 return [prev, prev2]
172 return [prev, prev2]
173 prev2 = revdata[6]
173 prev2 = revdata[6]
174 if prev2 != nullrev:
174 if prev2 != nullrev:
175 return [prev2]
175 return [prev2]
176 return []
176 return []
177
177
178 def inverse(self):
178 def inverse(self):
179 if self._inverse is None:
179 if self._inverse is None:
180 self._inverse = inverserevlogdag(self)
180 self._inverse = inverserevlogdag(self)
181 return self._inverse
181 return self._inverse
182
182
183 def ancestorset(self, starts, stops=None):
183 def ancestorset(self, starts, stops=None):
184 rlog = self._revlog
184 rlog = self._revlog
185 idx = rlog.index
185 idx = rlog.index
186 if stops:
186 if stops:
187 stops = set(stops)
187 stops = set(stops)
188 else:
188 else:
189 stops = set()
189 stops = set()
190 seen = set()
190 seen = set()
191 pending = list(starts)
191 pending = list(starts)
192 while pending:
192 while pending:
193 rev = pending.pop()
193 rev = pending.pop()
194 if rev not in seen and rev not in stops:
194 if rev not in seen and rev not in stops:
195 seen.add(rev)
195 seen.add(rev)
196 revdata = idx[rev]
196 revdata = idx[rev]
197 for i in [5, 6]:
197 for i in [5, 6]:
198 prev = revdata[i]
198 prev = revdata[i]
199 if prev != nullrev:
199 if prev != nullrev:
200 pending.append(prev)
200 pending.append(prev)
201 return seen
201 return seen
202
202
203 def headsetofconnecteds(self, ixs):
203 def headsetofconnecteds(self, ixs):
204 if not ixs:
204 if not ixs:
205 return set()
205 return set()
206 rlog = self._revlog
206 rlog = self._revlog
207 idx = rlog.index
207 idx = rlog.index
208 headrevs = set(ixs)
208 headrevs = set(ixs)
209 for rev in ixs:
209 for rev in ixs:
210 revdata = idx[rev]
210 revdata = idx[rev]
211 for i in [5, 6]:
211 for i in [5, 6]:
212 prev = revdata[i]
212 prev = revdata[i]
213 if prev != nullrev:
213 if prev != nullrev:
214 headrevs.discard(prev)
214 headrevs.discard(prev)
215 assert headrevs
215 assert headrevs
216 return headrevs
216 return headrevs
217
217
218 def linearize(self, ixs):
218 def linearize(self, ixs):
219 '''linearize and topologically sort a list of revisions
219 '''linearize and topologically sort a list of revisions
220
220
221 The linearization process tries to create long runs of revs where
221 The linearization process tries to create long runs of revs where
222 a child rev comes immediately after its first parent. This is done by
222 a child rev comes immediately after its first parent. This is done by
223 visiting the heads of the given revs in inverse topological order,
223 visiting the heads of the given revs in inverse topological order,
224 and for each visited rev, visiting its second parent, then its first
224 and for each visited rev, visiting its second parent, then its first
225 parent, then adding the rev itself to the output list.
225 parent, then adding the rev itself to the output list.
226 '''
226 '''
227 sorted = []
227 sorted = []
228 visit = list(self.headsetofconnecteds(ixs))
228 visit = list(self.headsetofconnecteds(ixs))
229 visit.sort(reverse=True)
229 visit.sort(reverse=True)
230 finished = set()
230 finished = set()
231
231
232 while visit:
232 while visit:
233 cur = visit.pop()
233 cur = visit.pop()
234 if cur < 0:
234 if cur < 0:
235 cur = -cur - 1
235 cur = -cur - 1
236 if cur not in finished:
236 if cur not in finished:
237 sorted.append(cur)
237 sorted.append(cur)
238 finished.add(cur)
238 finished.add(cur)
239 else:
239 else:
240 visit.append(-cur - 1)
240 visit.append(-cur - 1)
241 visit += [p for p in self.parents(cur)
241 visit += [p for p in self.parents(cur)
242 if p in ixs and p not in finished]
242 if p in ixs and p not in finished]
243 assert len(sorted) == len(ixs)
243 assert len(sorted) == len(ixs)
244 return sorted
244 return sorted
245
245
246
246
247 class inverserevlogdag(revlogbaseddag, genericdag):
247 class inverserevlogdag(revlogbaseddag, genericdag):
248 '''inverse of an existing revlog dag; see revlogdag.inverse()'''
248 '''inverse of an existing revlog dag; see revlogdag.inverse()'''
249
249
250 def __init__(self, orig):
250 def __init__(self, orig):
251 revlogbaseddag.__init__(self, orig._revlog, orig._nodeset)
251 revlogbaseddag.__init__(self, orig._revlog, orig._nodeset)
252 self._orig = orig
252 self._orig = orig
253 self._children = {}
253 self._children = {}
254 self._roots = []
254 self._roots = []
255 self._walkfrom = len(self._revlog) - 1
255 self._walkfrom = len(self._revlog) - 1
256
256
257 def _walkto(self, walkto):
257 def _walkto(self, walkto):
258 rev = self._walkfrom
258 rev = self._walkfrom
259 cs = self._children
259 cs = self._children
260 roots = self._roots
260 roots = self._roots
261 idx = self._revlog.index
261 idx = self._revlog.index
262 while rev >= walkto:
262 while rev >= walkto:
263 data = idx[rev]
263 data = idx[rev]
264 isroot = True
264 isroot = True
265 for prev in [data[5], data[6]]: # parent revs
265 for prev in [data[5], data[6]]: # parent revs
266 if prev != nullrev:
266 if prev != nullrev:
267 cs.setdefault(prev, []).append(rev)
267 cs.setdefault(prev, []).append(rev)
268 isroot = False
268 isroot = False
269 if isroot:
269 if isroot:
270 roots.append(rev)
270 roots.append(rev)
271 rev -= 1
271 rev -= 1
272 self._walkfrom = rev
272 self._walkfrom = rev
273
273
274 def _getheads(self):
274 def _getheads(self):
275 self._walkto(nullrev)
275 self._walkto(nullrev)
276 return self._roots
276 return self._roots
277
277
278 def parents(self, ix):
278 def parents(self, ix):
279 if ix is None:
279 if ix is None:
280 return []
280 return []
281 if ix <= self._walkfrom:
281 if ix <= self._walkfrom:
282 self._walkto(ix)
282 self._walkto(ix)
283 return self._children.get(ix, [])
283 return self._children.get(ix, [])
284
284
285 def inverse(self):
285 def inverse(self):
286 return self._orig
286 return self._orig
General Comments 0
You need to be logged in to leave comments. Login now