root/hodgestar/PythonCode/SvnDots/svndots.py

#!/usr/bin/env python

import re
import optparse
import datetime
import math
import random
import os
import logging

class Rev(object):
    """Revision object."""

    def __init__(self, revid, date):
        self.revid = revid
        self.date = date
        self.contributions = {}
        self.comments = {}

    def __str__(self):
        return "r%s: %s" % (self.revid, self.date)

    def add_contribution(self, user, path):
        if user in self.contributions:
            self.contributions[user].add(path)
        else:
            self.contributions[user] = set([path])

    def add_comment(self, user, comment):
        if user in self.comments:
            self.comments[user].add(comment)
        else:
            self.comments[user] = set([comment])


class SvnLogParser(object):

    START_RE = re.compile(r"^----+$")

    DATE_FORMAT = '%Y-%m-%d %H:%M:%S'

    def _start_state(self, line, state):
        """Process start line, return new state."""
        if self.START_RE.match(line):
            return self._first_line_state
        return self._start_state

    def _first_line_state(self, line, state):
        """Process first line, move to paths."""
        revid, user, date, lines = [part.strip() for part in line.split('|')]
        revid = int(revid[1:])
        date = datetime.datetime.strptime(" ".join(date.split()[:2]), self.DATE_FORMAT)
        lines = int(lines.split()[0])

        state['rev'] = Rev(revid, date)
        state['user'] = user
        state['lines_remaining'] = lines

        return self._path_state

    def _path_state(self, line, state):
        if line == "Changed paths:":
            return self._path_state
        elif not line.strip():
            return self._comment_state
        else:
            change, filename = line.split()[:2]
            state['rev'].add_contribution(state['user'], filename)
            return self._path_state

    def _comment_state(self, line, state):
        state.setdefault('comment', '')
        state['comment'] += line
        state['lines_remaining'] -= 1
        if state['lines_remaining'] > 0:
            return self._comment_state
        else:
            state['rev'].add_comment(state['user'], state['comment'])
            state['done'] = True
            return self._start_state

    def parse(self, logfile):
        """Parse svn log -v file."""
        # Example log entry:
        #
        # ------------------------------------------------------------------------
        # r371 | jerith | 2009-09-12 18:01:06 +0200 (Sat, 12 Sep 2009) | 1 line
        # Changed paths:
        #    M /gamelib/animal.py
        # 
        # Foxes are more averse to armed chickens and less averse to indoor chickens.

        state = {}
        state_func = self._start_state

        for line in logfile:
            state_func = state_func(line, state)
            if 'done' in state:
                yield state['rev']
                state.clear()


class Vector(object):
    """Really simple class representing a row of card table data."""

    METRICS = {}

    def __init__(self, aData):
        self._aData = aData

    # We do want to access _aData on other Vectors.
    # pylint: disable-msg=W0212

    def euclidian_distance(self, oVec2):
        """Euclidean distance between two vectors."""
        assert len(self._aData) == len(oVec2._aData)
        fSum = sum(((x-y)**2 for (x, y) in zip(self._aData, oVec2._aData)))
        return math.sqrt(fSum)

    METRICS['Euclidean Distance'] = euclidian_distance

    def sutekh_distance(self, oVec2):
        """Like Euclidean distance, but -1 is distance 0.25 to anything
           (including 0 and -1) and 0 is distance 4.0 from anything other
           than 0.
           """
        assert len(self._aData) == len(oVec2._aData)
        fSum = sum((
            ((x == -1 or y == -1) and 0.25) or
            (((x == 0) ^ (y == 0) and 4.0)) or
            (x-y)**2 for (x, y) in zip(self._aData, oVec2._aData)
        ))
        return math.sqrt(fSum)

    METRICS['Sutekh Distance'] = sutekh_distance

    # Other possibile metrics:
    #  'City Block Distance',
    #  'Correlation',
    #  'Absolute Value of the Correlation',
    #  'Uncentered Correlation',
    #  'Absolute Value of the Uncentered Correlation',
    #  "Spearman's Rank Correlation"
    #  "Kendall's Tau"

    def __add__(self, oOther):
        """Sum this vector with another."""
        if oOther == 0:
            return self
        assert len(self._aData) == len(oOther._aData)
        return Vector([ x+y for (x, y) in zip(self._aData, oOther._aData)])

    def __radd__(self, oOther):
        """Sum this vector with another."""
        if oOther == 0:
            return self
        assert len(self._aData) == len(oOther._aData)
        return Vector([ x+y for (x, y) in zip(self._aData, oOther._aData)])

    def __mul__(self, fScale):
        """Multiply this vector by a scalar."""
        fScale = float(fScale)
        return Vector([x*fScale for x in self._aData])

    def __rmul__(self, fScale):
        """Multiply this vector by a scalar."""
        fScale = float(fScale)
        return Vector([x*fScale for x in self._aData])

    def __len__(self):
        """Length of this vector."""
        return len(self._aData)

    def __str__(self):
        """String representation of this vector."""
        return str(self._aData)

    def __iter__(self):
        """Iterator."""
        return iter(self._aData)


def k_means_plus_plus(aCards, iNumClust, fDist):
    """Find a set of initial centers using the k-means++ algorithm.

       See http://www.stanford.edu/~darthur/kMeansPlusPlus.pdf.
       """
    aMeans = [ random.choice(aCards) ]

    while len(aMeans) < iNumClust:
        aDists = []
        for oVec in aCards:
            fMinD = min((fDist(oVec, oMean) for oMean in aMeans))**2
            aDists.append(fMinD)

        fSumSq = sum(aDists)
        fPick = random.uniform(0, fSumSq)

        for iCard, fMinD in enumerate(aDists):
            fPick -= fMinD
            if fPick <= 0:
                break

        # iCard is defined because k_means doesn't call
        # this unless aCards is non-empty
        # pylint: disable-msg=W0631

        if iCard == len(aCards):
            # guard against slight possibility of being very close
            # to end of fSumSq.
            iCard -= 1

        aMeans.append(aCards[iCard])

    return aMeans

def k_means(aCards, iNumClust, iIterations, fDist):
    """Perform k-means clustering on a list of cards using Lloyd's
       algorithm."""
    if (not aCards) or (not aCards[0]):
        # empty card set or zero-length vectors
        return [], []

    aMeans = k_means_plus_plus(aCards, iNumClust, fDist)
    iCards = len(aCards)

    # just do a fixed number of interations (no complex stopping condition)
    for _iIter in range(iIterations):
        # empty clusters
        aClusters = []
        for iClust in xrange(iNumClust):
            aClusters.append([])

        # calculate membership in clusters
        for iCard in xrange(iCards):
            oVec = aCards[iCard]
            iVmin = min(xrange(iNumClust),
                key=lambda iV: fDist(oVec, aMeans[iV]))
            aClusters[iVmin].append(iCard)

        # recompute the centroids
        for iClust in xrange(iNumClust):
            if aClusters[iClust]:
                aMeans[iClust] = (1.0 / len(aClusters[iClust])) * sum(
                    (aCards[x] for x in aClusters[iClust])
                )

    return aMeans, aClusters


def plotrevs(users, paths, data, is_date=False, linestyle="o-"):
    """Plot a list of revision objects"""
    import matplotlib.pyplot as plt
    import pylab

    common = len(os.path.commonprefix(paths))
    paths = [p[common:] for p in paths]
    for user, points in data.items():
        data[user] = [(d[0], d[1][common:]) for d in points]

    pathdict = dict(zip(paths, range(len(paths))))
    userdict = dict(zip(users, range(len(users))))
    usercolor = dict(zip(users, ['r', 'g', 'b', 'c', 'm', 'y']))

    if is_date:
        plotter = plt.plot_date
        xgetter = lambda r: r.date
    else:
        plotter = plt.plot
        xgetter = lambda r: r.revid

    for user in users:
        points = data[user]
        x = [xgetter(p[0]) for p in points]
        y = [pathdict[p[1]]+0.1*userdict[user]-0.2 for p in points]
        plotter(x, y,
            usercolor[user] + '-',
            alpha=0.25,
            linewidth=1.0,
        )
        plotter(x, y,
            usercolor[user] + linestyle,
            label=user,
            markersize=8.0,
            linewidth=1.0,
            picker=4.0,
        )

    plt.yticks([y for y in range(len(paths))], paths)
    plt.grid(color='grey', linestyle='-', alpha=0.25, ydata=[y for y in range(0,len(paths)+1,2)], linewidth=24.0)
    plt.ylabel('File')
    plt.xlabel(is_date and 'Date' or 'Revision')
    plt.ylim(-0.5,len(paths)-0.5)
    plt.legend(loc=0)

    fig = plt.figure(1)
    xmin, xmax = plt.xlim()
    ymin, ymax = plt.ylim()
    ann = plt.annotate("default", (xmin + (xmax-xmin)*0.05, ymin + (ymax-ymin)*0.05),
        backgroundcolor="yellow",
        bbox=dict(boxstyle="round", fc="0.8"),
        visible=False,
    )
    #ann.set_animated(True)
    current_rev = [-1]

    def onpick(event):
        line = event.artist
        ind = event.ind[0]
        x, y = line.get_xdata()[ind], line.get_ydata()[ind]
        user = line.get_label()
        rev = data[user][ind][0]
        comment = list(rev.comments[user])[0]
        text = "%s [%s]: %s" % (user, rev.revid, comment)
        text = text[:150]

        if ann.get_visible() and current_rev[0] == rev.revid:
            # print "II:", rev.revid
            ann.set_visible(False)
            current_rev[0] = -1
        else:
            # print "VV:", rev.revid
            ann.set_text(text)
            ann.set_visible(True)
            current_rev[0] = rev.revid

        pylab.draw()

    cid = fig.canvas.mpl_connect('pick_event', onpick)

    plt.show()

def minimize_rev_separation(revs, paths):
    """Attempt to minimize the maximum distance between paths in
       a revision.
       """
    import numpy

    pathindex = dict(zip(paths, range(len(paths))))
    revindex = []
    userindex = {}
    for rev in revs:
        for r_user, r_paths in rev.contributions.items():
            idxs = [pathindex[r] for r in r_paths if r in pathindex]
            if idxs:
                revindex.append(idxs)
                userindex.setdefault(r_user,[])
                userindex[r_user].extend(idxs)
    userindex = userindex.values()

    allindex = userindex

    def func(x):
        tot = 0.0
        for idxs in allindex:
            places = x.take(idxs)
            tot += sum((places[1:] - places[:-1])**2)
        return tot

    x0 = numpy.array(range(len(paths)), dtype=float)
    best_tot = func(x0)
    path_min = x0.copy()
    logging.info("Initial objective function value: %s", best_tot)
    for i in range(1000):
        random.shuffle(x0)
        tot = func(x0)
        if tot < best_tot:
            best_tot = tot
            path_min = x0.copy()
    logging.info("Final objective function value:", best_tot)

    path_pairs = zip(paths, path_min)
    path_pairs.sort(key=lambda p: p[1])
    return [p[0] for p in path_pairs]

def main(args):

    parser = optparse.OptionParser(version="%prog 0.1")
    parser.add_option("-d", "--bydate", dest="bydate",
                      action="store_true",
                      help="plot by date rather than revision id.")
    parser.add_option("-l", "--linestyle", dest="linestyle",
                      default="o-",
                      help="matplotlib line format")
    parser.add_option("-s", "--seed", dest="seed",
                      type="int",
                      default=42,
                      help="set random module seed.")
    parser.add_option("-f", "--filter", dest="filter",
                      default=r".*\.py$",
                      help="regular expression filter for file names")

    (options, args) = parser.parse_args()

    random.seed(options.seed)

    if len(args) < 1:
        print parser.get_usage()
        return 1

    logfile = args[0]

    parser = SvnLogParser()

    revs = list(parser.parse(file(logfile)))
    revs.sort(key=lambda rev: rev.date)

    users, paths = set(), set()
    data = {}
    path_vecs = {}

    path_revs = {}

    path_re = re.compile(options.filter)

    for i, rev in enumerate(revs):
        for r_user, r_paths in rev.contributions.iteritems():
            r_paths = [p for p in r_paths if path_re.match(p)]
            users.add(r_user)
            paths.update(r_paths)

            data.setdefault(r_user, [])
            data[r_user].extend((rev, p) for p in r_paths)

            for r_path in r_paths:
                path_revs.setdefault(r_path, [])
                path_revs[r_path].append(i)

#            for r_path in r_paths:
#                path_vecs.setdefault(r_path, {})
#                path_vecs[r_path].setdefault(r_user, 0.0)
#                path_vecs[r_path][r_user] += 1.0

    users = sorted(users)

    # paths = sorted(paths, key=lambda p: (len(path_revs[p]), max(path_revs[p])))
    # ordered_paths = paths

    ordered_paths = minimize_rev_separation(revs, paths)

#    path_vecs = path_vecs.items()
#    path_names = [pv[0] for pv in path_vecs]
#    path_dicts = [pv[1] for pv in path_vecs]
#    path_vectors = [Vector([u in d and d[u] or 0.0 for u in users]) for d in path_dicts]
#    path_vectors = [v*(1.0/sum(v)) for v in path_vectors]
#
#    means, clusters = k_means(path_vectors, len(users)+2, 100, Vector.euclidian_distance)
#
#    clusters.sort(key=lambda c: len(c))
#
#    ordered_paths = []
#    print "Clusters:"
#    for cluster in clusters:
#        print "\t", [path_names[i] for i in cluster]
#        ordered_paths.extend(path_names[i] for i in cluster)

    plotrevs(users, ordered_paths, data, options.bydate, options.linestyle)


if __name__ == "__main__":
    import sys
    sys.exit(main(sys.argv))