Show More
graphmod.py
142 lines
| 4.4 KiB
| text/x-python
|
PythonLexer
r1 | # -*- coding: utf-8 -*- | |||
r2487 | # Copyright (C) 2010-2018 RhodeCode GmbH | |||
r1 | # | |||
# This program is free software: you can redistribute it and/or modify | ||||
# it under the terms of the GNU Affero General Public License, version 3 | ||||
# (only), as published by the Free Software Foundation. | ||||
# | ||||
# This program is distributed in the hope that it will be useful, | ||||
# but WITHOUT ANY WARRANTY; without even the implied warranty of | ||||
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | ||||
# GNU General Public License for more details. | ||||
# | ||||
# You should have received a copy of the GNU Affero General Public License | ||||
# along with this program. If not, see <http://www.gnu.org/licenses/>. | ||||
# | ||||
# This program is dual-licensed. If you wish to learn more about the | ||||
# RhodeCode Enterprise Edition, including its added features, Support services, | ||||
# and proprietary license terms, please see https://rhodecode.com/licenses/ | ||||
""" | ||||
Modified mercurial DAG graph functions that re-uses VCS structure | ||||
r1379 | It allows to have a shared codebase for DAG generation for hg, git, svn repos | |||
r1 | """ | |||
nullrev = -1 | ||||
def grandparent(parent_idx_func, lowest_idx, roots, head): | ||||
""" | ||||
Return all ancestors of head in roots which commit is | ||||
greater or equal to lowest_idx. | ||||
""" | ||||
pending = set([head]) | ||||
seen = set() | ||||
kept = set() | ||||
llowestrev = max(nullrev, lowest_idx) | ||||
while pending: | ||||
r = pending.pop() | ||||
if r >= llowestrev and r not in seen: | ||||
if r in roots: | ||||
kept.add(r) | ||||
else: | ||||
pending.update(parent_idx_func(r)) | ||||
seen.add(r) | ||||
return sorted(kept) | ||||
def _dagwalker(repo, commits): | ||||
if not commits: | ||||
return | ||||
r1379 | def get_parent_indexes(idx): | |||
return [commit.idx for commit in repo[idx].parents] | ||||
r1 | ||||
r1379 | indexes = [commit['idx'] for commit in commits] | |||
r1 | lowest_idx = min(indexes) | |||
known_indexes = set(indexes) | ||||
r1379 | grandparnet_cache = {} | |||
r1 | for commit in commits: | |||
r1379 | parents = sorted(set([p['idx'] for p in commit['parents'] | |||
if p['idx'] in known_indexes])) | ||||
mpars = [p['idx'] for p in commit['parents'] if | ||||
p['idx'] != nullrev and p['idx'] not in parents] | ||||
r1 | for mpar in mpars: | |||
r1379 | gp = grandparnet_cache.get(mpar) | |||
r1 | if gp is None: | |||
r1379 | gp = grandparnet_cache[mpar] = grandparent( | |||
r1 | get_parent_indexes, lowest_idx, indexes, mpar) | |||
if not gp: | ||||
parents.append(mpar) | ||||
else: | ||||
parents.extend(g for g in gp if g not in parents) | ||||
r1379 | yield (commit['raw_id'], commit['idx'], parents, commit['branch']) | |||
r1 | ||||
def _colored(dag): | ||||
"""annotates a DAG with colored edge information | ||||
For each DAG node this function emits tuples:: | ||||
((col, color), [(col, nextcol, color)]) | ||||
with the following new elements: | ||||
- Tuple (col, color) with column and color index for the current node | ||||
- A list of tuples indicating the edges between the current node and its | ||||
parents. | ||||
""" | ||||
seen = [] | ||||
colors = {} | ||||
newcolor = 1 | ||||
r1379 | for commit_id, commit_idx, parents, branch in dag: | |||
r1 | ||||
# Compute seen and next_ | ||||
if commit_idx not in seen: | ||||
seen.append(commit_idx) # new head | ||||
colors[commit_idx] = newcolor | ||||
newcolor += 1 | ||||
col = seen.index(commit_idx) | ||||
color = colors.pop(commit_idx) | ||||
next_ = seen[:] | ||||
# Add parents to next_ | ||||
addparents = [p for p in parents if p not in next_] | ||||
next_[col:col + 1] = addparents | ||||
# Set colors for the parents | ||||
for i, p in enumerate(addparents): | ||||
if i == 0: | ||||
colors[p] = color | ||||
else: | ||||
colors[p] = newcolor | ||||
newcolor += 1 | ||||
# Add edges to the graph | ||||
edges = [] | ||||
for ecol, eid in enumerate(seen): | ||||
if eid in next_: | ||||
edges.append((ecol, next_.index(eid), colors[eid])) | ||||
elif eid == commit_idx: | ||||
total_parents = len(parents) | ||||
edges.extend([ | ||||
(ecol, next_.index(p), | ||||
_get_edge_color(p, total_parents, color, colors)) | ||||
for p in parents]) | ||||
# Yield and move on | ||||
r1379 | yield (commit_id, (col, color), edges, branch) | |||
r1 | seen = next_ | |||
def _get_edge_color(parent, total_parents, color, colors): | ||||
if total_parents <= 1: | ||||
return color | ||||
return colors.get(parent, color) | ||||