equal
deleted
inserted
replaced
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 .node import nullrev |
11 from .node import nullrev |
|
12 |
|
13 from . import ( |
|
14 dagop, |
|
15 ) |
12 |
16 |
13 class revlogdag(object): |
17 class revlogdag(object): |
14 '''dag interface to a revlog''' |
18 '''dag interface to a revlog''' |
15 |
19 |
16 def __init__(self, revlog): |
20 def __init__(self, revlog): |
29 prev2 = revdata[6] |
33 prev2 = revdata[6] |
30 if prev2 != nullrev: |
34 if prev2 != nullrev: |
31 return [prev2] |
35 return [prev2] |
32 return [] |
36 return [] |
33 |
37 |
34 def headsetofconnecteds(self, ixs): |
|
35 if not ixs: |
|
36 return set() |
|
37 rlog = self._revlog |
|
38 idx = rlog.index |
|
39 headrevs = set(ixs) |
|
40 for rev in ixs: |
|
41 revdata = idx[rev] |
|
42 for i in [5, 6]: |
|
43 prev = revdata[i] |
|
44 if prev != nullrev: |
|
45 headrevs.discard(prev) |
|
46 assert headrevs |
|
47 return headrevs |
|
48 |
|
49 def linearize(self, ixs): |
38 def linearize(self, ixs): |
50 '''linearize and topologically sort a list of revisions |
39 '''linearize and topologically sort a list of revisions |
51 |
40 |
52 The linearization process tries to create long runs of revs where |
41 The linearization process tries to create long runs of revs where |
53 a child rev comes immediately after its first parent. This is done by |
42 a child rev comes immediately after its first parent. This is done by |
54 visiting the heads of the given revs in inverse topological order, |
43 visiting the heads of the given revs in inverse topological order, |
55 and for each visited rev, visiting its second parent, then its first |
44 and for each visited rev, visiting its second parent, then its first |
56 parent, then adding the rev itself to the output list. |
45 parent, then adding the rev itself to the output list. |
57 ''' |
46 ''' |
58 sorted = [] |
47 sorted = [] |
59 visit = list(self.headsetofconnecteds(ixs)) |
48 visit = list(dagop.headrevs(ixs, self.parents)) |
60 visit.sort(reverse=True) |
49 visit.sort(reverse=True) |
61 finished = set() |
50 finished = set() |
62 |
51 |
63 while visit: |
52 while visit: |
64 cur = visit.pop() |
53 cur = visit.pop() |