mercurial-scm/hg-stable: mercurial/graphmod.py annotate

annotate mercurial/graphmod.py @ 23564:f7ce0837eefd

graphmod: add a function for topological iteration This changeset introduces a function to perform topological (one branch after the other) iteration over a set of changesets. This first version has a lot of limitations, but the approach should be flexible enough to allow many improvements in the future. This changeset aims to set the first stone more than providing a complete solution. The algorithm does not need to know the whole set of nodes involved before emitting revision. This makes it a good candidate for usage in place like `hg log` or graphical tools that need a fast first result time.

author	Pierre-Yves David <pierre-yves.david@fb.com>
date	Thu, 04 Sep 2014 18:19:32 +0200
parents	bb1bd9ee323d
children	996c01bfbec4

rev	line source
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	1 # Revision graph generator for Mercurial
0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	2 #
0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	3 # Copyright 2008 Dirkjan Ochtman <dirkjan@ochtman.nl>
0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	4 # Copyright 2007 Joel Rosdahl <joel@rosdahl.net>
0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	5 #
8225 46293a0c7e9f updated license to be explicit about GPL version 2 Martin Geisler <mg@lazybytes.net> parents: 7873 diff changeset	6 # This software may be used and distributed according to the terms of the
10263 25e572394f5c Update license to GPLv2+ Matt Mackall <mpm@selenic.com> parents: 10084 diff changeset	7 # GNU General Public License version 2 or any later version.
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	8
8840 d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	9 """supports walking the history as DAGs suitable for graphical output
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	10
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	11 The most basic format we use is that of::
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	12
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	13 (id, type, data, [parentids])
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	14
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	15 The node and parent ids are arbitrary integers which identify a node in the
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	16 context of the graph returned. Type is a constant specifying the node type.
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	17 Data depends on type.
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	18 """
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	19
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	20 from mercurial.node import nullrev
16132 41fc1e078d68 graphmod: add config cache Matt Mackall <mpm@selenic.com> parents: 16131 diff changeset	21 import util
8840 d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	22
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	23 CHANGESET = 'C'
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	24
23564 f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	25 def groupbranchiter(revs, parentsfunc):
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	26 """yield revision from heads to roots one (topo) branch after the other.
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	27
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	28 This function aims to be used by a graph generator that wishes to minimize
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	29 the amount of parallel branches and their interleaving.
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	30
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	31 Example iteration order:
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	32
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	33 o 4
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	34 \|
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	35 o 1
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	36 \|
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	37 \| o 3
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	38 \| \|
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	39 \| o 2
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	40 \|/
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	41 o 0
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	42
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	43 Currently does not handle non-contiguous <revs> input.
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	44
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	45 Currently consider every changeset under a merge to be on the same branch
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	46 using revision number to sort them.
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	47
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	48 Could be easily extend to give priority to an initial branch."""
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	49 ### Quick summary of the algorithm
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	50 #
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	51 # This function is based around a "retention" principle. We keep revisions
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	52 # in memory until we are ready to emit a whole branch that immediately
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	53 # "merge" into an existing one. This reduce the number of branch "ongoing"
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	54 # at the same time.
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	55 #
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	56 # During iteration revs are split into two groups:
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	57 # A) revision already emitted
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	58 # B) revision in "retention". They are stored as different subgroups.
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	59 #
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	60 # for each REV, we do the follow logic:
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	61 #
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	62 # a) if REV is a parent of (A), we will emit it. But before emitting it,
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	63 # we'll "free" all the revs from subgroup in (B) that were waiting for
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	64 # REV to be available. So we emit all revision of such subgroup before
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	65 # emitting REV
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	66 #
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	67 # b) else, we'll search for a subgroup in (B) awaiting for REV to be
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	68 # available, if such subgroup exist, we add REV to it and the subgroup is
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	69 # now awaiting for REV.parents() to be available.
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	70 #
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	71 # c) finally if no such group existed in (B), we create a new subgroup.
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	72 #
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	73 #
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	74 # To bootstrap the algorithm, we emit the tipmost revision.
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	75
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	76 revs.sort(reverse=True)
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	77
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	78 # Set of parents of revision that have been yield. They can be considered
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	79 # unblocked as the graph generator is already aware of them so there is no
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	80 # need to delay the one that reference them.
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	81 unblocked = set()
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	82
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	83 # list of group waiting to be displayed, each group is defined by:
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	84 #
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	85 # (revs: lists of revs waiting to be displayed,
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	86 # blocked: set of that cannot be displayed before those in 'revs')
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	87 #
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	88 # The second value ('blocked') correspond to parents of any revision in the
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	89 # group ('revs') that is not itself contained in the group. The main idea
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	90 # of this algorithm is to delay as much as possible the emission of any
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	91 # revision. This means waiting for the moment we are about to display
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	92 # theses parents to display the revs in a group.
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	93 #
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	94 # This first implementation is smart until it meet a merge: it will emit
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	95 # revs as soon as any parents is about to be emitted and can grow an
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	96 # arbitrary number of revs in 'blocked'. In practice this mean we properly
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	97 # retains new branches but give up on any special ordering for ancestors of
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	98 # merges. The implementation can be improved to handle this better.
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	99 #
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	100 # The first subgroup is special. It correspond to all the revision that
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	101 # were already emitted. The 'revs' lists is expected to be empty and the
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	102 # 'blocked' set contains the parents revisions of already emitted revision.
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	103 #
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	104 # You could pre-seed the <parents> set of groups[0] to a specific
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	105 # changesets to select what the first emitted branch should be.
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	106 #
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	107 # We do not support revisions will hole yet, but adding such support would
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	108 # be easy. The iteration will have to be done using both input revision and
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	109 # parents (see cl.ancestors function + a few tweaks) but only revisions
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	110 # parts of the initial set should be emitted.
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	111 groups = [([], unblocked)]
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	112 for current in revs:
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	113 # Look for a subgroup blocked, waiting for the current revision.
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	114 matching = [i for i, g in enumerate(groups) if current in g[1]]
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	115
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	116 if matching:
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	117 # The main idea is to gather together all sets that await on the
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	118 # same revision.
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	119 #
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	120 # This merging is done at the time we are about to add this common
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	121 # awaited to the subgroup for simplicity purpose. Such merge could
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	122 # happen sooner when we update the "blocked" set of revision.
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	123 #
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	124 # We also always keep the oldest subgroup first. We can probably
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	125 # improve the behavior by having the longuest set first. That way,
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	126 # graph algorythms could minimise the length of parallele lines
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	127 # their draw. This is currently not done.
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	128 targetidx = matching.pop(0)
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	129 trevs, tparents = groups[targetidx]
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	130 for i in matching:
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	131 gr = groups[i]
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	132 trevs.extend(gr[0])
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	133 tparents \|= gr[1]
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	134 # delete all merged subgroups (but the one we keep)
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	135 # (starting from the last subgroup for performance and sanity reason)
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	136 for i in reversed(matching):
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	137 del groups[i]
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	138 else:
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	139 # This is a new head. We create a new subgroup for it.
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	140 targetidx = len(groups)
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	141 groups.append(([], set([current])))
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	142
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	143 gr = groups[targetidx]
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	144
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	145 # We now adds the current nodes to this subgroups. This is done after
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	146 # the subgroup merging because all elements from a subgroup that relied
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	147 # on this rev must preceed it.
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	148 #
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	149 # we also update the <parents> set to includes the parents on the
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	150 # new nodes.
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	151 gr[0].append(current)
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	152 gr[1].remove(current)
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	153 gr[1].update([p for p in parentsfunc(current) if p > nullrev])
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	154
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	155 # Look for a subgroup to display
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	156 #
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	157 # When unblocked is empty (if clause), We are not waiting over any
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	158 # revision during the first iteration (if no priority was given) or if
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	159 # we outputed a whole disconnected sets of the graph (reached a root).
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	160 # In that case we arbitrarily takes the oldest known subgroup. The
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	161 # heuristique could probably be better.
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	162 #
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	163 # Otherwise (elif clause) this mean we have some emitted revision. if
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	164 # the subgroup awaits on the same revision that the outputed ones, we
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	165 # can safely output it.
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	166 if not unblocked:
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	167 if len(groups) > 1: # display other subset
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	168 targetidx = 1
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	169 gr = groups[1]
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	170 elif not gr[1] & unblocked:
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	171 gr = None
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	172
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	173 if gr is not None:
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	174 # update the set of awaited revisions with the one from the
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	175 # subgroup
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	176 unblocked \|= gr[1]
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	177 # output all revisions in the subgroup
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	178 for r in gr[0]:
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	179 yield r
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	180 # delete the subgroup that you just output
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	181 # unless it is groups[0] in which case you just empty it.
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	182 if targetidx:
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	183 del groups[targetidx]
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	184 else:
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	185 gr[0][:] = []
f7ce0837eefd graphmod: add a function for topological iteration Pierre-Yves David <pierre-yves.david@fb.com> parents: 23006 diff changeset	186
14042 9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	187 def dagwalker(repo, revs):
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	188 """cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	189
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	190 This generator function walks through revisions (which should be ordered
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	191 from bigger to lower). It returns a tuple for each node. The node and parent
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	192 ids are arbitrary integers which identify a node in the context of the graph
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	193 returned.
8836 11ff34956ee7 graphmod/graphlog: move log walks to graphmod Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8835 diff changeset	194 """
14042 9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	195 if not revs:
14087 f3d585c9b042 graphmod: restore generator nature of dagwalker Idan Kamara <idankk86@gmail.com> parents: 14064 diff changeset	196 return
14042 9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	197
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	198 cl = repo.changelog
20762 e87bd3485a07 graphmod: changed code in dagwalker to use lazy implementations Lucas Moscovicz <lmoscovicz@fb.com> parents: 18467 diff changeset	199 lowestrev = revs.min()
14042 9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	200 gpcache = {}
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	201
14087 f3d585c9b042 graphmod: restore generator nature of dagwalker Idan Kamara <idankk86@gmail.com> parents: 14064 diff changeset	202 for rev in revs:
f3d585c9b042 graphmod: restore generator nature of dagwalker Idan Kamara <idankk86@gmail.com> parents: 14064 diff changeset	203 ctx = repo[rev]
14088 e83ced8b6464 graphlog: use a set for inclusion test Patrick Mezard <pmezard@gmail.com> parents: 14087 diff changeset	204 parents = sorted(set([p.rev() for p in ctx.parents()
23006 bb1bd9ee323d dagwalker: drop a useless intermediate variable Pierre-Yves David <pierre-yves.david@fb.com> parents: 22878 diff changeset	205 if p.rev() in revs]))
14042 9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	206 mpars = [p.rev() for p in ctx.parents() if
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	207 p.rev() != nullrev and p.rev() not in parents]
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	208
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	209 for mpar in mpars:
14131 03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors Patrick Mezard <pmezard@gmail.com> parents: 14088 diff changeset	210 gp = gpcache.get(mpar)
14042 9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	211 if gp is None:
14131 03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors Patrick Mezard <pmezard@gmail.com> parents: 14088 diff changeset	212 gp = gpcache[mpar] = grandparent(cl, lowestrev, revs, mpar)
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors Patrick Mezard <pmezard@gmail.com> parents: 14088 diff changeset	213 if not gp:
14087 f3d585c9b042 graphmod: restore generator nature of dagwalker Idan Kamara <idankk86@gmail.com> parents: 14064 diff changeset	214 parents.append(mpar)
14131 03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors Patrick Mezard <pmezard@gmail.com> parents: 14088 diff changeset	215 else:
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors Patrick Mezard <pmezard@gmail.com> parents: 14088 diff changeset	216 parents.extend(g for g in gp if g not in parents)
14042 9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	217
14087 f3d585c9b042 graphmod: restore generator nature of dagwalker Idan Kamara <idankk86@gmail.com> parents: 14064 diff changeset	218 yield (ctx.rev(), CHANGESET, ctx, parents)
8836 11ff34956ee7 graphmod/graphlog: move log walks to graphmod Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8835 diff changeset	219
8837 d8e3a98018cb graphmod/graphlog: extract nodelistwalk Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8836 diff changeset	220 def nodes(repo, nodes):
8840 d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	221 """cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	222
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	223 This generator function walks the given nodes. It only returns parents
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	224 that are in nodes, too.
d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	225 """
8837 d8e3a98018cb graphmod/graphlog: extract nodelistwalk Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8836 diff changeset	226 include = set(nodes)
d8e3a98018cb graphmod/graphlog: extract nodelistwalk Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8836 diff changeset	227 for node in nodes:
d8e3a98018cb graphmod/graphlog: extract nodelistwalk Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8836 diff changeset	228 ctx = repo[node]
12951 101366ad816c graphmod: safer code when a changeset has two identical parents Nicolas Dumazet <nicdumz.commits@gmail.com> parents: 10602 diff changeset	229 parents = set([p.rev() for p in ctx.parents() if p.node() in include])
8840 d9acbe7b0049 graphmod/graphlog: make dag walks carry data as type, payload Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8837 diff changeset	230 yield (ctx.rev(), CHANGESET, ctx, sorted(parents))
8837 d8e3a98018cb graphmod/graphlog: extract nodelistwalk Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8836 diff changeset	231
16129 5e50982c633c graph: in hgrc specify line width for main branch Constantine Linnick <theaspect@gmail.com> parents: 14131 diff changeset	232 def colored(dag, repo):
8842 acd03a6e2426 graphmod/webcommands: use generic DAG walks Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8841 diff changeset	233 """annotates a DAG with colored edge information
acd03a6e2426 graphmod/webcommands: use generic DAG walks Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8841 diff changeset	234
acd03a6e2426 graphmod/webcommands: use generic DAG walks Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8841 diff changeset	235 For each DAG node this function emits tuples::
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	236
8842 acd03a6e2426 graphmod/webcommands: use generic DAG walks Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8841 diff changeset	237 (id, type, data, (col, color), [(col, nextcol, color)])
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	238
8842 acd03a6e2426 graphmod/webcommands: use generic DAG walks Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8841 diff changeset	239 with the following new elements:
acd03a6e2426 graphmod/webcommands: use generic DAG walks Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8841 diff changeset	240
8835 ec5483efc31f graphmod: code cleanup and doc fix Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8225 diff changeset	241 - Tuple (col, color) with column and color index for the current node
8842 acd03a6e2426 graphmod/webcommands: use generic DAG walks Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8841 diff changeset	242 - A list of tuples indicating the edges between the current node and its
acd03a6e2426 graphmod/webcommands: use generic DAG walks Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8841 diff changeset	243 parents.
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	244 """
8841 94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	245 seen = []
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	246 colors = {}
8841 94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	247 newcolor = 1
16129 5e50982c633c graph: in hgrc specify line width for main branch Constantine Linnick <theaspect@gmail.com> parents: 14131 diff changeset	248 config = {}
5e50982c633c graph: in hgrc specify line width for main branch Constantine Linnick <theaspect@gmail.com> parents: 14131 diff changeset	249
5e50982c633c graph: in hgrc specify line width for main branch Constantine Linnick <theaspect@gmail.com> parents: 14131 diff changeset	250 for key, val in repo.ui.configitems('graph'):
16131 6f236c8bdc01 graphmod: rewrite graph config validation Matt Mackall <mpm@selenic.com> parents: 16130 diff changeset	251 if '.' in key:
6f236c8bdc01 graphmod: rewrite graph config validation Matt Mackall <mpm@selenic.com> parents: 16130 diff changeset	252 branch, setting = key.rsplit('.', 1)
6f236c8bdc01 graphmod: rewrite graph config validation Matt Mackall <mpm@selenic.com> parents: 16130 diff changeset	253 # Validation
6f236c8bdc01 graphmod: rewrite graph config validation Matt Mackall <mpm@selenic.com> parents: 16130 diff changeset	254 if setting == "width" and val.isdigit():
16138 6e4de55a41a4 hgweb: refactor graph customization javascript Patrick Mezard <patrick@mezard.eu> parents: 16132 diff changeset	255 config.setdefault(branch, {})[setting] = int(val)
16131 6f236c8bdc01 graphmod: rewrite graph config validation Matt Mackall <mpm@selenic.com> parents: 16130 diff changeset	256 elif setting == "color" and val.isalnum():
6f236c8bdc01 graphmod: rewrite graph config validation Matt Mackall <mpm@selenic.com> parents: 16130 diff changeset	257 config.setdefault(branch, {})[setting] = val
16129 5e50982c633c graph: in hgrc specify line width for main branch Constantine Linnick <theaspect@gmail.com> parents: 14131 diff changeset	258
16132 41fc1e078d68 graphmod: add config cache Matt Mackall <mpm@selenic.com> parents: 16131 diff changeset	259 if config:
16138 6e4de55a41a4 hgweb: refactor graph customization javascript Patrick Mezard <patrick@mezard.eu> parents: 16132 diff changeset	260 getconf = util.lrucachefunc(
6e4de55a41a4 hgweb: refactor graph customization javascript Patrick Mezard <patrick@mezard.eu> parents: 16132 diff changeset	261 lambda rev: config.get(repo[rev].branch(), {}))
16132 41fc1e078d68 graphmod: add config cache Matt Mackall <mpm@selenic.com> parents: 16131 diff changeset	262 else:
16138 6e4de55a41a4 hgweb: refactor graph customization javascript Patrick Mezard <patrick@mezard.eu> parents: 16132 diff changeset	263 getconf = lambda rev: {}
16129 5e50982c633c graph: in hgrc specify line width for main branch Constantine Linnick <theaspect@gmail.com> parents: 14131 diff changeset	264
8842 acd03a6e2426 graphmod/webcommands: use generic DAG walks Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8841 diff changeset	265 for (cur, type, data, parents) in dag:
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	266
8841 94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	267 # Compute seen and next
94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	268 if cur not in seen:
94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	269 seen.append(cur) # new head
94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	270 colors[cur] = newcolor
94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	271 newcolor += 1
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	272
8841 94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	273 col = seen.index(cur)
94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	274 color = colors.pop(cur)
94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	275 next = seen[:]
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	276
8842 acd03a6e2426 graphmod/webcommands: use generic DAG walks Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8841 diff changeset	277 # Add parents to next
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	278 addparents = [p for p in parents if p not in next]
8841 94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	279 next[col:col + 1] = addparents
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	280
0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	281 # Set colors for the parents
0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	282 for i, p in enumerate(addparents):
0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	283 if not i:
0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	284 colors[p] = color
0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	285 else:
8841 94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	286 colors[p] = newcolor
94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	287 newcolor += 1
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	288
0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	289 # Add edges to the graph
0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	290 edges = []
8841 94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	291 for ecol, eid in enumerate(seen):
94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	292 if eid in next:
16138 6e4de55a41a4 hgweb: refactor graph customization javascript Patrick Mezard <patrick@mezard.eu> parents: 16132 diff changeset	293 bconf = getconf(eid)
16129 5e50982c633c graph: in hgrc specify line width for main branch Constantine Linnick <theaspect@gmail.com> parents: 14131 diff changeset	294 edges.append((
5e50982c633c graph: in hgrc specify line width for main branch Constantine Linnick <theaspect@gmail.com> parents: 14131 diff changeset	295 ecol, next.index(eid), colors[eid],
16138 6e4de55a41a4 hgweb: refactor graph customization javascript Patrick Mezard <patrick@mezard.eu> parents: 16132 diff changeset	296 bconf.get('width', -1),
6e4de55a41a4 hgweb: refactor graph customization javascript Patrick Mezard <patrick@mezard.eu> parents: 16132 diff changeset	297 bconf.get('color', '')))
8842 acd03a6e2426 graphmod/webcommands: use generic DAG walks Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8841 diff changeset	298 elif eid == cur:
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	299 for p in parents:
16138 6e4de55a41a4 hgweb: refactor graph customization javascript Patrick Mezard <patrick@mezard.eu> parents: 16132 diff changeset	300 bconf = getconf(p)
16129 5e50982c633c graph: in hgrc specify line width for main branch Constantine Linnick <theaspect@gmail.com> parents: 14131 diff changeset	301 edges.append((
5e50982c633c graph: in hgrc specify line width for main branch Constantine Linnick <theaspect@gmail.com> parents: 14131 diff changeset	302 ecol, next.index(p), color,
16138 6e4de55a41a4 hgweb: refactor graph customization javascript Patrick Mezard <patrick@mezard.eu> parents: 16132 diff changeset	303 bconf.get('width', -1),
6e4de55a41a4 hgweb: refactor graph customization javascript Patrick Mezard <patrick@mezard.eu> parents: 16132 diff changeset	304 bconf.get('color', '')))
6691 0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	305
0dba955c2636 add graph page to hgweb Dirkjan Ochtman <dirkjan@ochtman.nl> parents: diff changeset	306 # Yield and move on
8842 acd03a6e2426 graphmod/webcommands: use generic DAG walks Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8841 diff changeset	307 yield (cur, type, data, (col, color), edges)
8841 94ac080e7af9 graphmod: rename a bunch of vars in graph() Peter Arrenbrecht <peter.arrenbrecht@gmail.com> parents: 8840 diff changeset	308 seen = next
14042 9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	309
9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	310 def grandparent(cl, lowestrev, roots, head):
14131 03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors Patrick Mezard <pmezard@gmail.com> parents: 14088 diff changeset	311 """Return all ancestors of head in roots which revision is
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors Patrick Mezard <pmezard@gmail.com> parents: 14088 diff changeset	312 greater or equal to lowestrev.
14042 9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	313 """
14131 03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors Patrick Mezard <pmezard@gmail.com> parents: 14088 diff changeset	314 pending = set([head])
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors Patrick Mezard <pmezard@gmail.com> parents: 14088 diff changeset	315 seen = set()
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors Patrick Mezard <pmezard@gmail.com> parents: 14088 diff changeset	316 kept = set()
14042 9966c95b8c4f graphmod: use revsets internally Alexander Solovyov <alexander@solovyov.net> parents: 12951 diff changeset	317 llowestrev = max(nullrev, lowestrev)
14131 03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors Patrick Mezard <pmezard@gmail.com> parents: 14088 diff changeset	318 while pending:
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors Patrick Mezard <pmezard@gmail.com> parents: 14088 diff changeset	319 r = pending.pop()
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors Patrick Mezard <pmezard@gmail.com> parents: 14088 diff changeset	320 if r >= llowestrev and r not in seen:
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors Patrick Mezard <pmezard@gmail.com> parents: 14088 diff changeset	321 if r in roots:
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors Patrick Mezard <pmezard@gmail.com> parents: 14088 diff changeset	322 kept.add(r)
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors Patrick Mezard <pmezard@gmail.com> parents: 14088 diff changeset	323 else:
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors Patrick Mezard <pmezard@gmail.com> parents: 14088 diff changeset	324 pending.update([p for p in cl.parentrevs(r)])
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors Patrick Mezard <pmezard@gmail.com> parents: 14088 diff changeset	325 seen.add(r)
03e1c2d35c6a graphmod: correctly emit nodes with more than 2 predecessors Patrick Mezard <pmezard@gmail.com> parents: 14088 diff changeset	326 return sorted(kept)
17179 0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	327
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	328 def asciiedges(type, char, lines, seen, rev, parents):
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	329 """adds edge info to changelog DAG walk suitable for ascii()"""
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	330 if rev not in seen:
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	331 seen.append(rev)
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	332 nodeidx = seen.index(rev)
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	333
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	334 knownparents = []
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	335 newparents = []
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	336 for parent in parents:
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	337 if parent in seen:
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	338 knownparents.append(parent)
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	339 else:
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	340 newparents.append(parent)
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	341
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	342 ncols = len(seen)
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	343 nextseen = seen[:]
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	344 nextseen[nodeidx:nodeidx + 1] = newparents
18467 e441657b372b graphmod: don't try to visit nullrev (issue3772) Bryan O'Sullivan <bryano@fb.com> parents: 17179 diff changeset	345 edges = [(nodeidx, nextseen.index(p)) for p in knownparents if p != nullrev]
17179 0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	346
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	347 while len(newparents) > 2:
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	348 # ascii() only knows how to add or remove a single column between two
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	349 # calls. Nodes with more than two parents break this constraint so we
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	350 # introduce intermediate expansion lines to grow the active node list
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	351 # slowly.
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	352 edges.append((nodeidx, nodeidx))
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	353 edges.append((nodeidx, nodeidx + 1))
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	354 nmorecols = 1
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	355 yield (type, char, lines, (nodeidx, edges, ncols, nmorecols))
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	356 char = '\\'
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	357 lines = []
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	358 nodeidx += 1
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	359 ncols += 1
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	360 edges = []
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	361 del newparents[0]
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	362
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	363 if len(newparents) > 0:
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	364 edges.append((nodeidx, nodeidx))
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	365 if len(newparents) > 1:
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	366 edges.append((nodeidx, nodeidx + 1))
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	367 nmorecols = len(nextseen) - ncols
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	368 seen[:] = nextseen
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	369 yield (type, char, lines, (nodeidx, edges, ncols, nmorecols))
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	370
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	371 def _fixlongrightedges(edges):
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	372 for (i, (start, end)) in enumerate(edges):
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	373 if end > start:
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	374 edges[i] = (start, end + 1)
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	375
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	376 def _getnodelineedgestail(
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	377 node_index, p_node_index, n_columns, n_columns_diff, p_diff, fix_tail):
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	378 if fix_tail and n_columns_diff == p_diff and n_columns_diff != 0:
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	379 # Still going in the same non-vertical direction.
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	380 if n_columns_diff == -1:
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	381 start = max(node_index + 1, p_node_index)
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	382 tail = ["\|", " "] * (start - node_index - 1)
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	383 tail.extend(["/", " "] * (n_columns - start))
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	384 return tail
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	385 else:
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	386 return ["\\", " "] * (n_columns - node_index - 1)
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	387 else:
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	388 return ["\|", " "] * (n_columns - node_index - 1)
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	389
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	390 def _drawedges(edges, nodeline, interline):
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	391 for (start, end) in edges:
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	392 if start == end + 1:
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	393 interline[2 * end + 1] = "/"
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	394 elif start == end - 1:
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	395 interline[2 * start + 1] = "\\"
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	396 elif start == end:
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	397 interline[2 * start] = "\|"
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	398 else:
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	399 if 2 * end >= len(nodeline):
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	400 continue
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	401 nodeline[2 * end] = "+"
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	402 if start > end:
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	403 (start, end) = (end, start)
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	404 for i in range(2 * start + 1, 2 * end):
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	405 if nodeline[i] != "+":
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	406 nodeline[i] = "-"
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	407
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	408 def _getpaddingline(ni, n_columns, edges):
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	409 line = []
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	410 line.extend(["\|", " "] * ni)
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	411 if (ni, ni - 1) in edges or (ni, ni) in edges:
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	412 # (ni, ni - 1) (ni, ni)
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	413 # \| \| \| \| \| \| \| \|
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	414 # +---o \| \| o---+
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	415 # \| \| c \| \| c \| \|
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	416 # \| \|/ / \| \|/ /
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	417 # \| \| \| \| \| \|
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	418 c = "\|"
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	419 else:
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	420 c = " "
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	421 line.extend([c, " "])
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	422 line.extend(["\|", " "] * (n_columns - ni - 1))
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	423 return line
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	424
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	425 def asciistate():
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	426 """returns the initial value for the "state" argument to ascii()"""
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	427 return [0, 0]
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	428
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	429 def ascii(ui, state, type, char, text, coldata):
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	430 """prints an ASCII graph of the DAG
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	431
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	432 takes the following arguments (one call per node in the graph):
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	433
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	434 - ui to write to
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	435 - Somewhere to keep the needed state in (init to asciistate())
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	436 - Column of the current node in the set of ongoing edges.
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	437 - Type indicator of node data, usually 'C' for changesets.
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	438 - Payload: (char, lines):
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	439 - Character to use as node's symbol.
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	440 - List of lines to display as the node's text.
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	441 - Edges; a list of (col, next_col) indicating the edges between
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	442 the current node and its parents.
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	443 - Number of columns (ongoing edges) in the current revision.
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	444 - The difference between the number of columns (ongoing edges)
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	445 in the next revision and the number of columns (ongoing edges)
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	446 in the current revision. That is: -1 means one column removed;
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	447 0 means no columns added or removed; 1 means one column added.
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	448 """
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	449
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	450 idx, edges, ncols, coldiff = coldata
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	451 assert -2 < coldiff < 2
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	452 if coldiff == -1:
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	453 # Transform
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	454 #
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	455 # \| \| \| \| \| \|
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	456 # o \| \| into o---+
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	457 # \|X / \|/ /
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	458 # \| \| \| \|
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	459 _fixlongrightedges(edges)
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	460
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	461 # add_padding_line says whether to rewrite
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	462 #
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	463 # \| \| \| \| \| \| \| \|
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	464 # \| o---+ into \| o---+
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	465 # \| / / \| \| \| # <--- padding line
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	466 # o \| \| \| / /
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	467 # o \| \|
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	468 add_padding_line = (len(text) > 2 and coldiff == -1 and
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	469 [x for (x, y) in edges if x + 1 < y])
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	470
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	471 # fix_nodeline_tail says whether to rewrite
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	472 #
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	473 # \| \| o \| \| \| \| o \| \|
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	474 # \| \| \|/ / \| \| \|/ /
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	475 # \| o \| \| into \| o / / # <--- fixed nodeline tail
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	476 # \| \|/ / \| \|/ /
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	477 # o \| \| o \| \|
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	478 fix_nodeline_tail = len(text) <= 2 and not add_padding_line
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	479
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	480 # nodeline is the line containing the node character (typically o)
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	481 nodeline = ["\|", " "] * idx
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	482 nodeline.extend([char, " "])
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	483
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	484 nodeline.extend(
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	485 _getnodelineedgestail(idx, state[1], ncols, coldiff,
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	486 state[0], fix_nodeline_tail))
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	487
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	488 # shift_interline is the line containing the non-vertical
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	489 # edges between this entry and the next
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	490 shift_interline = ["\|", " "] * idx
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	491 if coldiff == -1:
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	492 n_spaces = 1
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	493 edge_ch = "/"
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	494 elif coldiff == 0:
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	495 n_spaces = 2
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	496 edge_ch = "\|"
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	497 else:
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	498 n_spaces = 3
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	499 edge_ch = "\\"
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	500 shift_interline.extend(n_spaces * [" "])
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	501 shift_interline.extend([edge_ch, " "] * (ncols - idx - 1))
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	502
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	503 # draw edges from the current node to its parents
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	504 _drawedges(edges, nodeline, shift_interline)
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	505
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	506 # lines is the list of all graph lines to print
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	507 lines = [nodeline]
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	508 if add_padding_line:
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	509 lines.append(_getpaddingline(idx, ncols, edges))
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	510 lines.append(shift_interline)
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	511
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	512 # make sure that there are as many graph lines as there are
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	513 # log strings
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	514 while len(text) < len(lines):
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	515 text.append("")
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	516 if len(lines) < len(text):
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	517 extra_interline = ["\|", " "] * (ncols + coldiff)
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	518 while len(lines) < len(text):
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	519 lines.append(extra_interline)
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	520
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	521 # print lines
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	522 indentation_level = max(ncols, ncols + coldiff)
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	523 for (line, logstr) in zip(lines, text):
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	524 ln = "%-s %s" % (2 indentation_level, "".join(line), logstr)
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	525 ui.write(ln.rstrip() + '\n')
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	526
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	527 # ... and start over
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	528 state[0] = coldiff
0849d725e2f9 graphlog: extract ascii drawing code into graphmod Patrick Mezard <patrick@mezard.eu> parents: 16138 diff changeset	529 state[1] = idx

Mercurial > public > mercurial-scm > hg-stable

annotate mercurial/graphmod.py @ 23564:f7ce0837eefd