Mercurial > public > mercurial-scm > hg-stable

annotate mercurial/dagutil.py @ 39210:4cf3f54cc8e7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
dagutil: remove unused classes We only directly use revlogdag in changegroup code. We don't need all this abstraction. So remove various classes and levels of inheritance. Differential Revision: https://phab.mercurial-scm.org/D4325
author Gregory Szorc <gregory.szorc@gmail.com>
date Fri, 17 Aug 2018 19:24:36 +0000
parents bbb855c412c6
children 1c3184d7e882
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
1 # dagutil.py - dag utilities for mercurial
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
2 #
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
3 # Copyright 2010 Benoit Boissinot <bboissin@gmail.com>
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
4 # and Peter Arrenbrecht <peter@arrenbrecht.ch>
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
5 #
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
6 # This software may be used and distributed according to the terms of the
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
7 # GNU General Public License version 2 or any later version.
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
8
25942
015ded095933 dagutil: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 24306
diff changeset
9 from __future__ import absolute_import
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
10
25942
015ded095933 dagutil: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 24306
diff changeset
11 from .node import nullrev
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
12
39210
4cf3f54cc8e7 dagutil: remove unused classes
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39208
diff changeset
13 class revlogdag(object):
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
14 '''dag interface to a revlog'''
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
15
39205
8973fc62bfff dagutil: remove heads() and localsubset from revlogdag.__init__
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39200
diff changeset
16 def __init__(self, revlog):
39210
4cf3f54cc8e7 dagutil: remove unused classes
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39208
diff changeset
17 self._revlog = revlog
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
18
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
19 def parents(self, ix):
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
20 rlog = self._revlog
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
21 idx = rlog.index
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
22 revdata = idx[ix]
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
23 prev = revdata[5]
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
24 if prev != nullrev:
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
25 prev2 = revdata[6]
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
26 if prev2 == nullrev:
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
27 return [prev]
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
28 return [prev, prev2]
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
29 prev2 = revdata[6]
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
30 if prev2 != nullrev:
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
31 return [prev2]
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
32 return []
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
33
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
34 def headsetofconnecteds(self, ixs):
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
35 if not ixs:
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
36 return set()
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
37 rlog = self._revlog
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
38 idx = rlog.index
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
39 headrevs = set(ixs)
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
40 for rev in ixs:
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
41 revdata = idx[rev]
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
42 for i in [5, 6]:
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
43 prev = revdata[i]
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
44 if prev != nullrev:
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
45 headrevs.discard(prev)
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
46 assert headrevs
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
47 return headrevs
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
48
14364
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
49 def linearize(self, ixs):
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
50 '''linearize and topologically sort a list of revisions
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
51
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
52 The linearization process tries to create long runs of revs where
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
53 a child rev comes immediately after its first parent. This is done by
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
54 visiting the heads of the given revs in inverse topological order,
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
55 and for each visited rev, visiting its second parent, then its first
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
56 parent, then adding the rev itself to the output list.
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
57 '''
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
58 sorted = []
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
59 visit = list(self.headsetofconnecteds(ixs))
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
60 visit.sort(reverse=True)
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
61 finished = set()
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
62
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
63 while visit:
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
64 cur = visit.pop()
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
65 if cur < 0:
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
66 cur = -cur - 1
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
67 if cur not in finished:
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
68 sorted.append(cur)
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
69 finished.add(cur)
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
70 else:
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
71 visit.append(-cur - 1)
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
72 visit += [p for p in self.parents(cur)
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
73 if p in ixs and p not in finished]
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
74 assert len(sorted) == len(ixs)
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
75 return sorted