/b-gtk/fix-viz

# -*- coding: UTF-8 -*-

"""Directed graph production.

This module contains the code to produce an ordered directed graph of a

bzr branch, such as we display in the tree view at the top of the bzrk

window.

"""

__copyright__ = "Copyright © 2005 Canonical Ltd."

__author__    = "Scott James Remnant <scott@ubuntu.com>"

def linegraph(branch, start, maxnum):

    """Produce a directed graph of a bzr branch.

    Returns a list of tuples of (revision, node, lines, parents, children).

    Node is a tuple of (column, colour) with column being a zero-indexed

    column number of the graph that this revision represents and colour

    being a zero-indexed colour (which doesn't specify any actual colour

    in particular) to draw the node in.

    Lines is a list of tuples which represent lines you should draw away

    from the revision, if you also need to draw lines into the revision

    you should use the lines list from the previous iteration.  Each

    typle in the list is in the form (start, end, colour) with start and

    end being zero-indexed column numbers and colour as in node.

    It's up to you how to actually draw the nodes and lines (straight,

    curved, kinked, etc.) and to pick the actual colours for each index.

    """

    def getdirectparent(childrevid, childindex, childsparents):

        """Return the revision id of the direct parent

        The direct parent is the first parent with the same committer"""

        childrevision = revisions[childindex]

        directparent = directparentcache[childindex]

        if directparent is None:

            for parentrevid in childsparents:

                if parentrevid in revindex:

                    parentindex = revindex[parentrevid]

                    parentrevision = revisions[parentindex]

                    if childrevision.committer == parentrevision.committer:

                        # This may be a direct parent, but first check that

                        # for this parent, there are no other children, who are

                        # before us in the children list, for which this parent

                        # is also the direct parent.

                        # pc in all the below var name stands for parents child

                        first = True

                        for pcrevid in revisionchildren[parentindex]:

                            if pcrevid == childrevid:

                                break

                            pcindex = revindex[pcrevid]

                            pcdirectparent = getdirectparent(pcrevid,

                                                    pcindex,

                                                    revisionchildren[pcindex])

                            if pcdirectparent==parentrevid:

                                first = False

                                break

                        if first:

                            directparent = parentrevid

                            break

            #no parents have the same commiter

            if directparent is None:

                directparent = ""

            directparentcache[childindex] = directparent

        return directparent

    def find_column_from_branchlineid(branchlineid):

        for index, column in enumerate(columns):

            if column is not None and column["branchlineid"] == branchlineid:

                return (index, column)

        return (None, None)

    def has_no_nodes_between (column, startindex, endindex):

        for nodeindex in column["nodeindexes"]:

            if nodeindex > startindex and nodeindex < endindex:

                return False

        return True

    def append_line (column , startindex, endindex):

        column["lines"].append((startindex,endindex))

        if endindex > column["maxindex"] :

            column["maxindex"] = endindex

    def append_column (column, minindex):

        columnindex = None

        for (i, c) in enumerate(columns):

            if c is None or (c["branchlineid"] == "finished" \

                             and c["maxindex"] <= minindex):

                columnindex = i

                columns[columnindex] = column

                break

        if columnindex is None:

            columnindex = len(columns)

            columns.append(column)

        return columnindex

    revids = []

    revindex = {}

    for (index, revid) in enumerate(reversed( \

            branch.repository.get_ancestry(start))):

        if revid is not None:

            revids.append(revid)

            revindex[revid] = index

        if maxnum is not None and index > maxnum:

            break

    mainline = branch.revision_history()

    revisions = branch.repository.get_revisions(revids)

    revisionparents = branch.repository.get_graph().get_parents(revids)    

    directparentcache = [None for revision in revisions]

    # This will hold what we plan to put in each column.

    # The position of the item in this list indicates the column, and it

    # it may change if we need to make space for other things.

    # Each typle in the list is in the form:

    # (branchlineid, nodeindexes, lines, maxindex)

    # A item may be None to indicate that there is nothing in the column

    columns = []

    linegraph = []

    lastbranchlineid = 0

    branchlineids = []

    revisionchildren = [[] for revision in revisions]

    notdrawnlines = []

    for (index, revision) in enumerate(revisions):

        parents = [parent for parent in revisionparents[index] \

                   if parent!="null:"]

        for parentrevid in parents:

            if parentrevid in revindex:

                revisionchildren[revindex[parentrevid]]\

                    .append(revision.revision_id)

        children = revisionchildren[index]

        #We use childrevid, childindex, childbranchlineid often, so cache it

        children_ext = []

        for childrevid in children:

            childindex = revindex[childrevid]

            children_ext.append((childrevid,

                                 childindex,

                                 branchlineids[childindex]))

        linegraph.append([revision, None,

                          [], parents, children])

        branchlineid = None

        if revision.revision_id in mainline:

            branchlineid = 0

        else:

            #Try and see if we are the same branchline as one of our children

            #If we are, use the same branchlineid

            for (childrevid, childindex, childbranchlineid) in children_ext: 

                childsparents = revisionparents[childindex]

                if len(children) == 1 and len(childsparents) == 1: 

                    # one-one relationship between parent and child

                    branchlineid = childbranchlineid

                    break

                #Is the current revision the direct parent of the child?

                if childbranchlineid != 0 and revision.revision_id == \

                        getdirectparent(childrevid, childindex, childsparents):

                    branchlineid = childbranchlineid

                    break

        if branchlineid is None:

            branchlineid = lastbranchlineid = lastbranchlineid + 1

        branchlineids.append(branchlineid)

        (columnindex, column) = find_column_from_branchlineid(branchlineid)

        if columnindex is None:

            for (childrevid, childindex, childbranchlineid) in children_ext:

                (i, c) = find_column_from_branchlineid(childbranchlineid)

                if c is not None and c["maxindex"] <= index:

                    (columnindex, column) = (i, c)

                    break

        if columnindex is None:

            minindex = index

            for childrevid in children:

                childindex = revindex[childrevid]

                if childindex<minindex:

                    minindex = childindex

            column = {"branchlineid": branchlineid,

                      "nodeindexes": [index],

                      "lines": [],

                      "maxindex": index}

            columnindex = append_column(column, minindex)

        else:

            column["branchlineid"] = branchlineid

            column["nodeindexes"].append(index)

        opentillparent = getdirectparent(revision.revision_id, index, parents)

        if opentillparent == "":

            if len(parents)>0:

                opentillparent = parents[0]

            else:

                opentillparent = None

        if opentillparent is not None and opentillparent in revindex:

            parentindex = revindex[opentillparent]

            if parentindex > column["maxindex"]:

                column["maxindex"] = parentindex

        for (childrevid, childindex, childbranchlineid) in children_ext: 

            (childcolumnindex, childcolumn) = \

                find_column_from_branchlineid(childbranchlineid)

            if index-childindex == 1 or childcolumnindex is None:

                append_line(column,childindex,index)

            elif childcolumnindex >= columnindex and \

                    has_no_nodes_between(childcolumn, childindex, index):

                append_line(childcolumn,childindex,index)

            elif childcolumnindex > columnindex and \

                    has_no_nodes_between(column, childindex, index):

                append_line(column,childindex,index)

            elif childcolumnindex < columnindex and \

                    has_no_nodes_between(column, childindex, index):

                append_line(column,childindex,index)

            elif childcolumnindex < columnindex and \

                    has_no_nodes_between(childcolumn, childindex, index):

                append_line(childcolumn,childindex,index)

            else:

                append_column({"branchlineid": "line",

                                "nodeindexes": [],

                                "lines": [(childindex,index)],

                                "maxindex": index}, childindex)

        for (columnindex, column) in enumerate(columns):

            if column is not None and column["maxindex"] <= index \

                    and column["branchlineid"] != "finished":

                for nodeindex in column["nodeindexes"]:

                    linegraph[nodeindex][1] = (columnindex,

                                               branchlineids[nodeindex])

                for (childindex, parentindex) in column["lines"]:

                    notdrawnlines.append((columnindex, childindex, parentindex))

                column["branchlineid"] = "finished"

                column["nodeindexes"] = []

                column["lines"] = []

        for (lineindex,(columnindex, childindex, parentindex))\

                in enumerate(notdrawnlines):

            childnode = linegraph[childindex][1]

            parentnode = linegraph[parentindex][1]

            if childnode is not None and parentnode is not None:

                notdrawnlines[lineindex] = None

                if parentindex>childindex+1:

                    #out from the child to line

                    linegraph[childindex][2].append(

                        (childnode[0],    #the column of the child

                         columnindex,     #the column of the line

                         parentnode[1]))

                    #down the line

                    for linepartindex in range(childindex+1, parentindex-1):

                        linegraph[linepartindex][2].append(

                            (columnindex, #the column of the line

                             columnindex, #the column of the line

                             parentnode[1]))

                    #in to the parent

                    linegraph[parentindex-1][2].append(

                        (columnindex,     #the column of the line

                         parentnode[0],   #the column of the parent

                         parentnode[1]))

                else:

                    #child to parent

                    linegraph[childindex][2].append(

                        (childnode[0],    #the column of the child

                         parentnode[0],   #the column of the parent

                         parentnode[1]))

        notdrawnlines = [line for line in notdrawnlines if line is not None]

    return (linegraph, revindex, revisions)

def same_branch(a, b):

    """Return whether we think revisions a and b are on the same branch."""

    if len(a.parent_ids) == 1:

        # Defacto same branch if only parent

        return True

    elif a.committer == b.committer:

        # Same committer so may as well be

        return True

    else:

        return False