Mercurial > public > mercurial-scm > hg-stable

annotate mercurial/dagutil.py @ 39212:1c3184d7e882

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
dagop: extract headsetofconnecteds() from dagutil The functionality for resolving the set of DAG heads from a subset simply requires a function to resolve parent revisions. Let's establish a function in the dagop module to do this, which seems to be where generic DAG functionality goes these days. Differential Revision: https://phab.mercurial-scm.org/D4327
author Gregory Szorc <gregory.szorc@gmail.com>
date Fri, 17 Aug 2018 19:45:13 +0000
parents 4cf3f54cc8e7
children 8de526995844
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
39212
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39210
diff changeset
13 from . import (
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39210
diff changeset
14 dagop,
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39210
diff changeset
15 )
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39210
diff changeset
16
39210
4cf3f54cc8e7 dagutil: remove unused classes
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39208
diff changeset
17 class revlogdag(object):
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
18 '''dag interface to a revlog'''
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
19
39205
8973fc62bfff dagutil: remove heads() and localsubset from revlogdag.__init__
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39200
diff changeset
20 def __init__(self, revlog):
39210
4cf3f54cc8e7 dagutil: remove unused classes
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39208
diff changeset
21 self._revlog = revlog
14164
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
22
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
23 def parents(self, ix):
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
24 rlog = self._revlog
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
25 idx = rlog.index
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
26 revdata = idx[ix]
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
27 prev = revdata[5]
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
28 if prev != nullrev:
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 [prev]
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
32 return [prev, prev2]
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
33 prev2 = revdata[6]
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
34 if prev2 != nullrev:
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
35 return [prev2]
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
36 return []
cb98fed52495 discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff changeset
37
14364
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
38 def linearize(self, ixs):
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
39 '''linearize and topologically sort a list of revisions
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
40
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
41 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
42 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
43 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
44 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
45 parent, then adding the rev itself to the output list.
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
46 '''
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
47 sorted = []
39212
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents: 39210
diff changeset
48 visit = list(dagop.headrevs(ixs, self.parents))
14364
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
49 visit.sort(reverse=True)
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
50 finished = set()
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 while visit:
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
53 cur = visit.pop()
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
54 if cur < 0:
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
55 cur = -cur - 1
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
56 if cur not in finished:
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
57 sorted.append(cur)
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
58 finished.add(cur)
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
59 else:
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
60 visit.append(-cur - 1)
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
61 visit += [p for p in self.parents(cur)
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
62 if p in ixs and p not in finished]
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
63 assert len(sorted) == len(ixs)
a3b9f1bddab1 revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents: 14206
diff changeset
64 return sorted