1.1 --- a/hggtk/logview/revgraph.py Mon Aug 31 09:50:47 2009 +0200
1.2 +++ b/hggtk/logview/revgraph.py Mon Aug 31 09:50:48 2009 +0200
1.3 @@ -145,6 +145,189 @@
1.4 curr_rev -= 1
1.5
1.6
1.7 +class BranchGrapher:
1.8 + """Incremental branch grapher
1.9 +
1.10 + This generator function produces a graph that uses loose ends to keep
1.11 + focus on branches. All revisions in the range are shown, but not all edges.
1.12 + The function identifies branches and may use loose ends if an edge links
1.13 + two branches.
1.14 + """
1.15 +
1.16 + def __init__(self, repo, start_rev, stop_rev):
1.17 + assert start_rev >= stop_rev
1.18 + self.repo = repo
1.19 +
1.20 + #
1.21 + # Iterator content
1.22 + # Variables that keep track of the iterator
1.23 + #
1.24 +
1.25 + # The current revision to process
1.26 + self.curr_rev = start_rev
1.27 +
1.28 + # Process all revs from start_rev to and including stop_rev
1.29 + self.stop_rev = stop_rev
1.30 +
1.31 + # List current branches. For each branch the next rev is listed
1.32 + # The order of branches determine their columns
1.33 + self.curr_branches = [start_rev]
1.34 +
1.35 + # For each branch, tell the next version that will show up
1.36 + self.next_in_branch = {}
1.37 +
1.38 + #
1.39 + # Graph variables
1.40 + # These hold information related to the graph. Most are computed lazily.
1.41 + #
1.42 +
1.43 + # Map rev to next rev in branch = first parent of rev.
1.44 + # The parent of last rev in a branch is undefined,
1.45 + # even if the revsion has a parent rev.
1.46 + self.parent_of = {}
1.47 +
1.48 + # Map rev to newest rev in branch. This identifies the branch that the rev
1.49 + # is part of
1.50 + self.branch4rev = {}
1.51 +
1.52 + # Last revision in branch
1.53 + self.branch_tail = {}
1.54 +
1.55 + # Map branch-id (head-rev of branch) to color
1.56 + self.color4branch = {}
1.57 +
1.58 + # Next colour used. for branches
1.59 + self.nextcolor = 0
1.60 +
1.61 + def _get_parents(self, rev):
1.62 + return [x for x in self.repo.changelog.parentrevs(rev) if x != nullrev]
1.63 +
1.64 + def _covered_rev(self, rev):
1.65 + """True if rev is inside the revision range for the iterator"""
1.66 + return self.stop_rev <= rev
1.67 +
1.68 + def _new_branch(self, branch_head):
1.69 + """Mark all unknown revisions in range that are direct ancestors
1.70 + of branch_head as part of the same branch. Stops when stop_rev
1.71 + is passed or a known revision is found"""
1.72 + assert self._covered_rev(branch_head)
1.73 + assert not branch_head in self.branch4rev
1.74 + self.color4branch[branch_head] = self.nextcolor
1.75 + self.nextcolor += 1
1.76 + self.next_in_branch[branch_head] = branch_head
1.77 + rev = branch_head
1.78 + while not rev in self.branch4rev:
1.79 + # TODO consider lazy evaluation here
1.80 + if not self._covered_rev(rev):
1.81 + # rev is outside visible range, so we don't know tail location
1.82 + self.branch_tail[branch_head] = 0 # Prev revs wasn't tail
1.83 + return
1.84 + self.branch4rev[rev] = branch_head
1.85 + self.branch_tail[branch_head] = rev
1.86 + parents = self._get_parents(rev)
1.87 + if not parents:
1.88 + # All revisions have been exhausted (rev = 0)
1.89 + self.parent_of[rev] = None
1.90 + return
1.91 + self.parent_of[rev] = parents[0]
1.92 + rev = parents[0]
1.93 +
1.94 + def _get_rev_branch(self, rev):
1.95 + """Find revision branch or create a new branch"""
1.96 + branch = self.branch4rev.get(rev)
1.97 + if branch is None:
1.98 + branch = rev
1.99 + self._new_branch(branch)
1.100 + assert rev in self.branch4rev
1.101 + assert branch in self.branch_tail
1.102 + return branch
1.103 +
1.104 + def _compute_next_branches(self):
1.105 + """Compute next row of branches"""
1.106 + next_branches = self.curr_branches[:]
1.107 + # Find branch used by current revision
1.108 + curr_branch = self._get_rev_branch(self.curr_rev)
1.109 + self.next_in_branch[curr_branch] = self.parent_of[self.curr_rev]
1.110 + branch_index = self.curr_branches.index(curr_branch)
1.111 + # Insert branches if parents point to new branches
1.112 + new_parents = 0
1.113 + for parent in self._get_parents(self.curr_rev):
1.114 + branch = self._get_rev_branch(parent)
1.115 + if not branch in next_branches:
1.116 + new_parents += 1
1.117 + next_branches.insert(branch_index + new_parents, branch)
1.118 + # Delete branch if last revision
1.119 + if self.curr_rev == self.branch_tail[curr_branch]:
1.120 + del next_branches[branch_index]
1.121 + # Return result
1.122 + return next_branches
1.123 +
1.124 + def _rev_color(self, rev):
1.125 + """Map a revision to a color"""
1.126 + return self.color4branch[self.branch4rev[rev]]
1.127 +
1.128 + def _compute_lines(self, parents, next_branches):
1.129 + # Compute lines (from CUR to NEXT branch row)
1.130 + lines = []
1.131 + curr_rev_branch = self.branch4rev[self.curr_rev]
1.132 + for curr_column, branch in enumerate(self.curr_branches):
1.133 + if branch == curr_rev_branch:
1.134 + # Add lines from current branch to parents
1.135 + for par_rev in parents:
1.136 + par_branch = self._get_rev_branch(par_rev)
1.137 + color = self.color4branch[par_branch]
1.138 + next_column = next_branches.index(par_branch)
1.139 + line_type = type_PLAIN
1.140 + if par_rev != self.next_in_branch.get(par_branch):
1.141 + line_type = type_LOOSE_LOW
1.142 + lines.append( (curr_column, next_column, color, line_type) )
1.143 + else:
1.144 + # Continue unrelated branch
1.145 + color = self.color4branch[branch]
1.146 + next_column = next_branches.index(branch)
1.147 + lines.append( (curr_column, next_column, color, type_PLAIN) )
1.148 + return lines
1.149 +
1.150 + def more(self):
1.151 + return self.curr_rev >= self.stop_rev
1.152 +
1.153 + def next(self):
1.154 + """Perform one iteration of the branch grapher"""
1.155 +
1.156 + # Compute revision (on CUR branch row)
1.157 + rev = self.curr_rev
1.158 + rev_branch = self._get_rev_branch(rev)
1.159 + if rev_branch not in self.curr_branches:
1.160 + # New head
1.161 + self.curr_branches.append(rev_branch)
1.162 +
1.163 + # Compute parents (indicates the branches on NEXT branch row that curr_rev links to)
1.164 + parents = self._get_parents(rev)
1.165 + # BUG: __get_parents is not defined - why?
1.166 +
1.167 + # Compute lines (from CUR to NEXT branch row)
1.168 + next_branches = self._compute_next_branches()
1.169 + lines = self._compute_lines(parents, next_branches)
1.170 +
1.171 + # Compute node info (for CUR branch row)
1.172 + rev_column = self.curr_branches.index(rev_branch)
1.173 + rev_color = self.color4branch[rev_branch]
1.174 + node = (rev_column, rev_color)
1.175 +
1.176 + # Next loop
1.177 + self.curr_branches = next_branches
1.178 + self.curr_rev -= 1
1.179 +
1.180 + # Return result
1.181 + # TODO: Refactor parents field away - it is apparently not used anywhere
1.182 + return (rev, node, lines, parents)
1.183 +
1.184 +def branch_grapher(repo, start_rev, stop_rev):
1.185 + grapher = BranchGrapher(repo, start_rev, stop_rev)
1.186 + while grapher.more():
1.187 + yield grapher.next()
1.188 +
1.189 +
1.190 def filelog_grapher(repo, path):
1.191 '''
1.192 Graph the ancestry of a single file (log). Deletions show