18 '''dag interface to a revlog''' |
18 '''dag interface to a revlog''' |
19 |
19 |
20 def __init__(self, revlog): |
20 def __init__(self, revlog): |
21 self._revlog = revlog |
21 self._revlog = revlog |
22 |
22 |
23 def parents(self, ix): |
|
24 rlog = self._revlog |
|
25 idx = rlog.index |
|
26 revdata = idx[ix] |
|
27 prev = revdata[5] |
|
28 if prev != nullrev: |
|
29 prev2 = revdata[6] |
|
30 if prev2 == nullrev: |
|
31 return [prev] |
|
32 return [prev, prev2] |
|
33 prev2 = revdata[6] |
|
34 if prev2 != nullrev: |
|
35 return [prev2] |
|
36 return [] |
|
37 |
|
38 def linearize(self, ixs): |
23 def linearize(self, ixs): |
39 '''linearize and topologically sort a list of revisions |
24 '''linearize and topologically sort a list of revisions |
40 |
25 |
41 The linearization process tries to create long runs of revs where |
26 The linearization process tries to create long runs of revs where |
42 a child rev comes immediately after its first parent. This is done by |
27 a child rev comes immediately after its first parent. This is done by |
43 visiting the heads of the given revs in inverse topological order, |
28 visiting the heads of the given revs in inverse topological order, |
44 and for each visited rev, visiting its second parent, then its first |
29 and for each visited rev, visiting its second parent, then its first |
45 parent, then adding the rev itself to the output list. |
30 parent, then adding the rev itself to the output list. |
46 ''' |
31 ''' |
47 sorted = [] |
32 sorted = [] |
48 visit = list(dagop.headrevs(ixs, self.parents)) |
33 visit = list(dagop.headrevs(ixs, self._revlog.parentrevs)) |
49 visit.sort(reverse=True) |
34 visit.sort(reverse=True) |
50 finished = set() |
35 finished = set() |
51 |
36 |
52 while visit: |
37 while visit: |
53 cur = visit.pop() |
38 cur = visit.pop() |
56 if cur not in finished: |
41 if cur not in finished: |
57 sorted.append(cur) |
42 sorted.append(cur) |
58 finished.add(cur) |
43 finished.add(cur) |
59 else: |
44 else: |
60 visit.append(-cur - 1) |
45 visit.append(-cur - 1) |
61 visit += [p for p in self.parents(cur) |
46 visit += [p for p in self._revlog.parentrevs(cur) |
62 if p in ixs and p not in finished] |
47 if p != nullrev and p in ixs and p not in finished] |
63 assert len(sorted) == len(ixs) |
48 assert len(sorted) == len(ixs) |
64 return sorted |
49 return sorted |