|
1 # dagutil.py - dag utilities for mercurial |
|
2 # |
|
3 # Copyright 2010 Benoit Boissinot <bboissin@gmail.com> |
|
4 # and Peter Arrenbrecht <peter@arrenbrecht.ch> |
|
5 # |
|
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. |
|
8 |
|
9 from node import nullrev |
|
10 |
|
11 |
|
12 class basedag(object): |
|
13 '''generic interface for DAGs |
|
14 |
|
15 terms: |
|
16 "ix" (short for index) identifies a nodes internally, |
|
17 "id" identifies one externally. |
|
18 |
|
19 All params are ixs unless explicitly suffixed otherwise. |
|
20 Pluralized params are lists or sets. |
|
21 ''' |
|
22 |
|
23 def __init__(self): |
|
24 self._inverse = None |
|
25 |
|
26 def nodeset(self): |
|
27 '''set of all node idxs''' |
|
28 raise NotImplementedError() |
|
29 |
|
30 def heads(self): |
|
31 '''list of head ixs''' |
|
32 raise NotImplementedError() |
|
33 |
|
34 def parents(self, ix): |
|
35 '''list of parents ixs of ix''' |
|
36 raise NotImplementedError() |
|
37 |
|
38 def inverse(self): |
|
39 '''inverse DAG, where parents becomes children, etc.''' |
|
40 raise NotImplementedError() |
|
41 |
|
42 def ancestorset(self, starts, stops=None): |
|
43 '''set of all ancestors of starts (incl), but stop walk at stops (excl)''' |
|
44 raise NotImplementedError() |
|
45 |
|
46 def descendantset(self, starts, stops=None): |
|
47 '''set of all descendants of starts (incl), but stop walk at stops (excl)''' |
|
48 return self.inverse().ancestorset(starts, stops) |
|
49 |
|
50 def headsetofconnecteds(self, ixs): |
|
51 '''subset of connected list of ixs so that no node has a descendant in it |
|
52 |
|
53 By "connected list" we mean that if an ancestor and a descendant are in |
|
54 the list, then so is at least one path connecting them.''' |
|
55 raise NotImplementedError() |
|
56 |
|
57 def externalize(self, ix): |
|
58 '''return a list of (or set if given a set) of node ids''' |
|
59 return self._externalize(ix) |
|
60 |
|
61 def externalizeall(self, ixs): |
|
62 '''return a list of (or set if given a set) of node ids''' |
|
63 ids = self._externalizeall(ixs) |
|
64 if isinstance(ixs, set): |
|
65 return set(ids) |
|
66 return list(ids) |
|
67 |
|
68 def internalize(self, id): |
|
69 '''return a list of (or set if given a set) of node ixs''' |
|
70 return self._internalize(id) |
|
71 |
|
72 def internalizeall(self, ids, filterunknown=False): |
|
73 '''return a list of (or set if given a set) of node ids''' |
|
74 ixs = self._internalizeall(ids, filterunknown) |
|
75 if isinstance(ids, set): |
|
76 return set(ixs) |
|
77 return list(ixs) |
|
78 |
|
79 |
|
80 class genericdag(basedag): |
|
81 '''generic implementations for DAGs''' |
|
82 |
|
83 def ancestorset(self, starts, stops=None): |
|
84 stops = stops and set(stops) or set() |
|
85 seen = set() |
|
86 pending = list(starts) |
|
87 while pending: |
|
88 n = pending.pop() |
|
89 if n not in seen and n not in stops: |
|
90 seen.add(n) |
|
91 pending.extend(self.parents(n)) |
|
92 return seen |
|
93 |
|
94 def headsetofconnecteds(self, ixs): |
|
95 hds = set(ixs) |
|
96 if not hds: |
|
97 return hds |
|
98 for n in ixs: |
|
99 for p in self.parents(n): |
|
100 hds.discard(p) |
|
101 assert hds |
|
102 return hds |
|
103 |
|
104 |
|
105 class revlogbaseddag(basedag): |
|
106 '''generic dag interface to a revlog''' |
|
107 |
|
108 def __init__(self, revlog, nodeset): |
|
109 basedag.__init__(self) |
|
110 self._revlog = revlog |
|
111 self._heads = None |
|
112 self._nodeset = nodeset |
|
113 |
|
114 def nodeset(self): |
|
115 return self._nodeset |
|
116 |
|
117 def heads(self): |
|
118 if self._heads is None: |
|
119 self._heads = self._getheads() |
|
120 return self._heads |
|
121 |
|
122 def _externalize(self, ix): |
|
123 return self._revlog.index[ix][7] |
|
124 def _externalizeall(self, ixs): |
|
125 idx = self._revlog.index |
|
126 return [idx[i][7] for i in ixs] |
|
127 |
|
128 def _internalize(self, id): |
|
129 ix = self._revlog.rev(id) |
|
130 if ix == nullrev: |
|
131 raise LookupError(id, self._revlog.indexfile, _('nullid')) |
|
132 return ix |
|
133 def _internalizeall(self, ids, filterunknown): |
|
134 rl = self._revlog |
|
135 if filterunknown: |
|
136 return [r for r in map(rl.nodemap.get, ids) |
|
137 if r is not None and r != nullrev] |
|
138 return map(self._internalize, ids) |
|
139 |
|
140 |
|
141 class revlogdag(revlogbaseddag): |
|
142 '''dag interface to a revlog''' |
|
143 |
|
144 def __init__(self, revlog): |
|
145 revlogbaseddag.__init__(self, revlog, set(xrange(len(revlog)))) |
|
146 |
|
147 def _getheads(self): |
|
148 return [r for r in self._revlog.headrevs() if r != nullrev] |
|
149 |
|
150 def parents(self, ix): |
|
151 rlog = self._revlog |
|
152 idx = rlog.index |
|
153 revdata = idx[ix] |
|
154 prev = revdata[5] |
|
155 if prev != nullrev: |
|
156 prev2 = revdata[6] |
|
157 if prev2 == nullrev: |
|
158 return [prev] |
|
159 return [prev, prev2] |
|
160 prev2 = revdata[6] |
|
161 if prev2 != nullrev: |
|
162 return [prev2] |
|
163 return [] |
|
164 |
|
165 def inverse(self): |
|
166 if self._inverse is None: |
|
167 self._inverse = inverserevlogdag(self) |
|
168 return self._inverse |
|
169 |
|
170 def ancestorset(self, starts, stops=None): |
|
171 rlog = self._revlog |
|
172 idx = rlog.index |
|
173 stops = stops and set(stops) or set() |
|
174 seen = set() |
|
175 pending = list(starts) |
|
176 while pending: |
|
177 rev = pending.pop() |
|
178 if rev not in seen and rev not in stops: |
|
179 seen.add(rev) |
|
180 revdata = idx[rev] |
|
181 for i in [5, 6]: |
|
182 prev = revdata[i] |
|
183 if prev != nullrev: |
|
184 pending.append(prev) |
|
185 return seen |
|
186 |
|
187 def headsetofconnecteds(self, ixs): |
|
188 if not ixs: |
|
189 return set() |
|
190 rlog = self._revlog |
|
191 idx = rlog.index |
|
192 headrevs = set(ixs) |
|
193 for rev in ixs: |
|
194 revdata = idx[rev] |
|
195 for i in [5, 6]: |
|
196 prev = revdata[i] |
|
197 if prev != nullrev: |
|
198 headrevs.discard(prev) |
|
199 assert headrevs |
|
200 return headrevs |
|
201 |
|
202 |
|
203 class inverserevlogdag(revlogbaseddag, genericdag): |
|
204 '''inverse of an existing revlog dag; see revlogdag.inverse()''' |
|
205 |
|
206 def __init__(self, orig): |
|
207 revlogbaseddag.__init__(self, orig._revlog, orig._nodeset) |
|
208 self._orig = orig |
|
209 self._children = {} |
|
210 self._roots = [] |
|
211 self._walkfrom = len(self._revlog) - 1 |
|
212 |
|
213 def _walkto(self, walkto): |
|
214 rev = self._walkfrom |
|
215 cs = self._children |
|
216 roots = self._roots |
|
217 idx = self._revlog.index |
|
218 while rev >= walkto: |
|
219 data = idx[rev] |
|
220 isroot = True |
|
221 for prev in [data[5], data[6]]: # parent revs |
|
222 if prev != nullrev: |
|
223 cs.setdefault(prev, []).append(rev) |
|
224 isroot = False |
|
225 if isroot: |
|
226 roots.append(rev) |
|
227 rev -= 1 |
|
228 self._walkfrom = rev - 1 |
|
229 |
|
230 def _getheads(self): |
|
231 self._walkto(nullrev) |
|
232 return self._roots |
|
233 |
|
234 def parents(self, ix): |
|
235 if ix is None: |
|
236 return [] |
|
237 if ix <= self._walkfrom: |
|
238 self._walkto(ix) |
|
239 return self._children.get(ix, []) |
|
240 |
|
241 def inverse(self): |
|
242 return self._orig |