Mercurial > kallithea
changeset 4340:d1aba9ab3bc1
graph: clean-up of variable naming
author | Mads Kiilerich <madski@unity3d.com> |
---|---|
date | Tue, 10 Dec 2013 19:30:37 +0100 |
parents | 58fe03c0aad1 |
children | ab89f7ce2c0b |
files | kallithea/lib/graphmod.py |
diffstat | 1 files changed, 47 insertions(+), 49 deletions(-) [+] |
line wrap: on
line diff
--- a/kallithea/lib/graphmod.py Tue Dec 10 19:30:37 2013 +0100 +++ b/kallithea/lib/graphmod.py Tue Dec 10 19:30:37 2013 +0100 @@ -19,25 +19,25 @@ nullrev = -1 - -def grandparent(parentrev_func, lowestrev, roots, head): +def _first_known_ancestors(parentrev_func, minrev, knownrevs, head): """ - Return all ancestors of head in roots which revision is - greater or equal to lowestrev. + Walk DAG defined by parentrev_func. + Return most immediate ancestors of head that are in knownrevs. + minrev is lower bound on knownrevs. """ pending = set([head]) seen = set() - kept = set() - llowestrev = max(nullrev, lowestrev) + ancestors = set() + minrev = max(nullrev, minrev) while pending: r = pending.pop() - if r >= llowestrev and r not in seen: - if r in roots: - kept.add(r) + if r >= minrev and r not in seen: + if r in knownrevs: + ancestors.add(r) else: - pending.update([p for p in parentrev_func(r)]) + pending.update(parentrev_func(r)) seen.add(r) - return sorted(kept) + return sorted(ancestors) def graph_data(repo, revs): """Return a DAG with colored edge information for revs @@ -60,32 +60,30 @@ return if repo.alias == 'hg': - cl = repo._repo.changelog.parentrevs + parentrev_func = repo._repo.changelog.parentrevs elif repo.alias == 'git': - def cl(rev): + def parentrev_func(rev): return [x.revision for x in repo[rev].parents] - lowestrev = min(revs) - gpcache = {} - + minrev = min(revs) knownrevs = set(revs) + acache = {} for rev in revs: ctx = repo[rev] - parents = sorted(set([p.revision for p in ctx.parents - if p.revision in knownrevs])) - mpars = [p.revision for p in ctx.parents if - p.revision != nullrev and p.revision not in parents] + parents = [p.revision for p in ctx.parents] + dagparents = sorted(set(parents) & knownrevs) + mpars = sorted(set(parents) - knownrevs - set([nullrev])) + # Calculate indirect parents + for p in mpars: + ancestors = acache.get(p) + if ancestors is None: + ancestors = acache[p] = _first_known_ancestors(parentrev_func, minrev, revs, p) + if ancestors: # some indirect known ancestors found - use them and ignore unknown ancestors + dagparents.extend(g for g in ancestors if g not in dagparents) + else: # no known ancestors - use the real but unknown parent + dagparents.append(p) - for mpar in mpars: - gp = gpcache.get(mpar) - if gp is None: - gp = gpcache[mpar] = grandparent(cl, lowestrev, revs, mpar) - if not gp: - parents.append(mpar) - else: - parents.extend(g for g in gp if g not in parents) - - yield (ctx.revision, parents) + yield (ctx.revision, dagparents) def _colored(dag): @@ -101,27 +99,27 @@ - A list of tuples indicating the edges between the current node and its parents. """ - seen = [] + row = [] colors = {} newcolor = 1 - for (cur, parents) in dag: + for (rev, dagparents) in dag: - # Compute seen and next - if cur not in seen: - seen.append(cur) # new head - colors[cur] = newcolor + # Compute row and nextrow + if rev not in row: + row.append(rev) # new head + colors[rev] = newcolor newcolor += 1 - col = seen.index(cur) - color = colors.pop(cur) - next = seen[:] + nextrow = row[:] - # Add parents to next - addparents = [p for p in parents if p not in next] - next[col:col + 1] = addparents + # Add unknown parents to nextrow + addparents = [p for p in dagparents if p not in nextrow] + col = nextrow.index(rev) + nextrow[col:col + 1] = addparents # Set colors for the parents + color = colors.pop(rev) for i, p in enumerate(addparents): if not i: colors[p] = color @@ -131,13 +129,13 @@ # 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 == cur: - for p in parents: - edges.append((ecol, next.index(p), colors[p] if len(parents) > 1 else color)) + for ecol, ep in enumerate(row): + if ep in nextrow: + edges.append((ecol, nextrow.index(ep), colors[ep])) + elif ep == rev: + for p in dagparents: + edges.append((ecol, nextrow.index(p), colors[p] if len(dagparents) > 1 else color)) # Yield and move on yield ((col, color), edges) - seen = next + row = nextrow