~abentley/bzrtools/bzrtools.dev

# Copyright (C) 2005, 2008 Aaron Bentley

# <aaron@aaronbentley.com>

#

#    This program is free software; you can redistribute it and/or modify

#    it under the terms of the GNU General Public License as published by

#    the Free Software Foundation; either version 2 of the License, or

#    (at your option) any later version.

#

#    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 General Public License

#    along with this program; if not, write to the Free Software

#    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

import time

from bzrlib.branch import Branch

from bzrlib.errors import BzrCommandError, NoSuchRevision

from bzrlib.revision import NULL_REVISION

from bzrtools import short_committer

from dotgraph import (

    dot_output,

    DOT_OUTPUT_TYPES,

    Edge,

    invoke_dot,

    invoke_dot_aa,

    invoke_dot_html,

    Node,

    NoDot,

    NoRsvg,

    RSVG_OUTPUT_TYPES,

    )

def max_distance(node, ancestors, distances, root_descendants):

    """Calculate the max distance to an ancestor.

    Return None if not all possible ancestors have known distances"""

    best = None

    if node in distances:

        best = distances[node]

    for ancestor in ancestors[node]:

        # skip ancestors we will never traverse:

        if root_descendants is not None and ancestor not in root_descendants:

            continue

        # An ancestor which is not listed in ancestors will never be in

        # distances, so we pretend it never existed.

        if ancestor not in ancestors:

            continue

        if ancestor not in distances:

            return None

        if best is None or distances[ancestor]+1 > best:

            best = distances[ancestor] + 1

    return best

def node_distances(graph, ancestors, start, root_descendants=None):

    """Produce a list of nodes, sorted by distance from a start node.

    This is an algorithm devised by Aaron Bentley, because applying Dijkstra

    backwards seemed too complicated.

    For each node, we walk its descendants.  If all the descendant's ancestors

    have a max-distance-to-start, (excluding ones that can never reach start),

    we calculate their max-distance-to-start, and schedule their descendants.

    So when a node's last parent acquires a distance, it will acquire a

    distance on the next iteration.

    Once we know the max distances for all nodes, we can return a list sorted

    by distance, farthest first.

    """

    distances = {start: 0}

    lines = set([start])

    while len(lines) > 0:

        new_lines = set()

        for line in lines:

            line_descendants = graph[line]

            for descendant in line_descendants:

                distance = max_distance(descendant, ancestors, distances,

                                        root_descendants)

                if distance is None:

                    continue

                distances[descendant] = distance

                new_lines.add(descendant)

        lines = new_lines

    return distances

def nodes_by_distance(distances):

    """Return a list of nodes sorted by distance"""

    def by_distance(n):

        return distances[n],n

    node_list = distances.keys()

    node_list.sort(key=by_distance, reverse=True)

    return node_list

def select_farthest(distances, common):

    """Return the farthest common node, or None if no node qualifies."""

    node_list = nodes_by_distance(distances)

    for node in node_list:

        if node in common:

            return node

mail_map = {'aaron.bentley@utoronto.ca'     : 'Aaron Bentley',

            'abentley@panoramicfeedback.com': 'Aaron Bentley',

            'abentley@lappy'                : 'Aaron Bentley',

            'john@arbash-meinel.com'        : 'John Arbash Meinel',

            'mbp@sourcefrog.net'            : 'Martin Pool',

            'robertc@robertcollins.net'     : 'Robert Collins',

            }

committer_alias = {'abentley': 'Aaron Bentley'}

def can_skip(rev_id, descendants, ancestors):

    if rev_id not in descendants:

        return False

    elif rev_id not in ancestors:

        return False

    elif len(ancestors[rev_id]) != 1:

        return False

    elif len(descendants[list(ancestors[rev_id])[0]]) != 1:

        return False

    elif len(descendants[rev_id]) != 1:

        return False

    else:

        return True

def compact_ancestors(descendants, ancestors, exceptions=()):

    new_ancestors={}

    skip = set()

    for me, my_parents in ancestors.iteritems():

        if me in skip:

            continue

        new_ancestors[me] = {}

        for parent in my_parents:

            new_parent = parent

            distance = 0

            while can_skip(new_parent, descendants, ancestors):

                if new_parent in exceptions:

                    break

                skip.add(new_parent)

                if new_parent in new_ancestors:

                    del new_ancestors[new_parent]

                new_parent = list(ancestors[new_parent])[0]

                distance += 1

            new_ancestors[me][new_parent] = distance

    return new_ancestors

def get_rev_info(rev_id, source):

    """Return the committer, message, nick and date of a revision."""

    committer = None

    message = None

    date = None

    nick = None

    if rev_id == 'null:':

        return None, 'Null Revision', None, None

    try:

        rev = source.get_revision(rev_id)

    except NoSuchRevision:

        try:

            committer = '-'.join(rev_id.split('-')[:-2]).strip(' ')

            if committer == '':

                return None, None, None, None

        except ValueError:

            return None, None, None, None

    else:

        committer = short_committer(rev.committer)

        if rev.message is not None:

            message = rev.message.split('\n')[0]

        gmtime = time.gmtime(rev.timestamp + (rev.timezone or 0))

        date = time.strftime('%Y/%m/%d', gmtime)

        nick = rev.properties.get('branch-nick')

    if '@' in committer:

        try:

            committer = mail_map[committer]

        except KeyError:

            pass

    try:

        committer = committer_alias[committer]

    except KeyError:

        pass

    return committer, message, nick, date

class Grapher(object):

    def __init__(self, branch, other_branch=None):

        object.__init__(self)

        self.branch = branch

        self.other_branch = other_branch

        if other_branch is not None:

            other_repo = other_branch.repository

            revision_b = self.other_branch.last_revision()

        else:

            other_repo = None

            revision_b = None

        self.graph = self.branch.repository.get_graph(other_repo)

        revision_a = self.branch.last_revision()

        self.scan_graph(revision_a, revision_b)

        self.n_history = branch.revision_history()

        self.n_revnos = branch.get_revision_id_to_revno_map()

        self.distances = node_distances(self.descendants, self.ancestors,

                                        self.root)

        if other_branch is not None:

            self.base = select_farthest(self.distances, self.common)

            self.m_history = other_branch.revision_history()

            self.m_revnos = other_branch.get_revision_id_to_revno_map()

            self.new_base = self.graph.find_unique_lca(revision_a,

                                                       revision_b)

            self.lcas = self.graph.find_lca(revision_a, revision_b)

        else:

            self.base = None

            self.new_base = None

            self.lcas = set()

            self.m_history = []

            self.m_revnos = {}

    def scan_graph(self, revision_a, revision_b):

        a_ancestors = dict(self.graph.iter_ancestry([revision_a]))

        self.ancestors = a_ancestors

        self.root = NULL_REVISION

        if revision_b is not None:

            b_ancestors = dict(self.graph.iter_ancestry([revision_b]))

            self.common = set(a_ancestors.keys())

            self.common.intersection_update(b_ancestors)

            self.ancestors.update(b_ancestors)

        else:

            self.common = []

            revision_b = None

        self.descendants = {}

        ghosts = set()

        for revision, parents in self.ancestors.iteritems():

            self.descendants.setdefault(revision, [])

            if parents is None:

                ghosts.add(revision)

                parents = [NULL_REVISION]

            for parent in parents:

                self.descendants.setdefault(parent, []).append(revision)

        for ghost in ghosts:

            self.ancestors[ghost] = [NULL_REVISION]

    @staticmethod

    def _get_revno_str(prefix, revno_map, revision_id):

        try:

            revno = revno_map[revision_id]

        except KeyError:

            return None

        return '%s%s' % (prefix, '.'.join(str(n) for n in revno))

    def dot_node(self, node, num):

        try:

            n_rev = self.n_history.index(node) + 1

        except ValueError:

            n_rev = None

        try:

            m_rev = self.m_history.index(node) + 1

        except ValueError:

            m_rev = None

        if (n_rev, m_rev) == (None, None):

            name = self._get_revno_str('r', self.n_revnos, node)

            if name is None:

                name = self._get_revno_str('R', self.m_revnos, node)

            if name is None:

                name = node[-5:]

            cluster = None

        elif n_rev == m_rev:

            name = "rR%d" % n_rev

        else:

            namelist = []

            for prefix, revno in (('r', n_rev), ('R', m_rev)):

                if revno is not None:

                    namelist.append("%s%d" % (prefix, revno))

            name = ' '.join(namelist)

        if None not in (n_rev, m_rev):

            cluster = "common_history"

            color = "#ff9900"

        elif (None, None) == (n_rev, m_rev):

            cluster = None

            if node in self.common:

                color = "#6699ff"

            else:

                color = "white"

        elif n_rev is not None:

            cluster = "my_history"

            color = "#ffff00"

        else:

            assert m_rev is not None

            cluster = "other_history"

            color = "#ff0000"

        if node in self.lcas:

            color = "#9933cc"

        if node == self.base:

            color = "#669933"

            if node == self.new_base:

                color = "#33ff33"

        if node == self.new_base:

            color = '#33cc99'

        label = [name]

        committer, message, nick, date = get_rev_info(node,

                                                      self.branch.repository)

        if committer is not None:

            label.append(committer)

        if nick is not None:

            label.append(nick)

        if date is not None:

            label.append(date)

        if node in self.distances:

            rank = self.distances[node]

            label.append('d%d' % self.distances[node])

        else:

            rank = None

        d_node = Node("n%d" % num, color=color, label="\\n".join(label),

                    rev_id=node, cluster=cluster, message=message,

                    date=date)

        d_node.rank = rank

        if node not in self.ancestors:

            d_node.node_style.append('dotted')

        return d_node

    def get_relations(self, collapse=False, max_distance=None):

        dot_nodes = {}

        node_relations = []

        num = 0

        if collapse:

            exceptions = self.lcas.union([self.base, self.new_base])

            visible_ancestors = compact_ancestors(self.descendants,

                                                  self.ancestors,

                                                  exceptions)

        else:

            visible_ancestors = {}

            for revision, parents in self.ancestors.iteritems():

                visible_ancestors[revision] = dict((p, 0) for p in parents)

        if max_distance is not None:

            min_distance = max(self.distances.values()) - max_distance

            visible_ancestors = dict((n, p) for n, p in

                                     visible_ancestors.iteritems() if

                                     self.distances[n] >= min_distance)

        for node, parents in visible_ancestors.iteritems():

            if node not in dot_nodes:

                dot_nodes[node] = self.dot_node(node, num)

                num += 1

            for parent, skipped in parents.iteritems():

                if parent not in dot_nodes:

                    dot_nodes[parent] = self.dot_node(parent, num)

                    num += 1

                edge = Edge(dot_nodes[parent], dot_nodes[node])

                if skipped != 0:

                    edge.label = "%d" % skipped

                node_relations.append(edge)

        return node_relations

def write_ancestry_file(branch, filename, collapse=True, antialias=True,

                        merge_branch=None, ranking="forced", max_distance=None):

    b = Branch.open_containing(branch)[0]

    if merge_branch is not None:

        m = Branch.open_containing(merge_branch)[0]

    else:

        m = None

    b.lock_write()

    try:

        if m is not None:

            m.lock_read()

        try:

            grapher = Grapher(b, m)

            relations = grapher.get_relations(collapse, max_distance)

        finally:

            if m is not None:

                m.unlock()

    finally:

        b.unlock()

    ext = filename.split('.')[-1]

    output = dot_output(relations, ranking)

    done = False

    if ext not in RSVG_OUTPUT_TYPES:

        antialias = False

    if antialias:

        output = list(output)

        try:

            invoke_dot_aa(output, filename, ext)

            done = True

        except NoDot, e:

            raise BzrCommandError("Can't find 'dot'.  Please ensure Graphviz"\

                " is installed correctly.")

        except NoRsvg, e:

            print "Not antialiasing because rsvg (from librsvg-bin) is not"\

                " installed."

            antialias = False

    if ext in DOT_OUTPUT_TYPES and not antialias and not done:

        try:

            invoke_dot(output, filename, ext)

            done = True

        except NoDot, e:

            raise BzrCommandError("Can't find 'dot'.  Please ensure Graphviz"\

                " is installed correctly.")

    elif ext == 'dot' and not done:

        my_file = file(filename, 'wb')

        for fragment in output:

            my_file.write(fragment.encode('utf-8'))

    elif ext == 'html':

        try:

            invoke_dot_html(output, filename)

        except NoDot, e:

            raise BzrCommandError("Can't find 'dot'.  Please ensure Graphviz"\

                " is installed correctly.")

    elif not done:

        print "Unknown file extension: %s" % ext