# # # patch "ChangeLog" # from [a90102fbf7b5d7be6c5d553f362389c465267832] # to [2f53a621e78d70464a48722c586ac3abd6efa4b5] # # patch "README" # from [46ffe1ce5080c9fd0081574ae8a8da30c3df65dc] # to [5fa5a33cef3770ba09a216acc1659490712ba505] # # patch "viewmtn.py" # from [26b1e351f925173805bccc4b59c24f3d40cde0c6] # to [2ab7af7898c05351d6121d756037736fed7116b5] # ============================================================ --- ChangeLog a90102fbf7b5d7be6c5d553f362389c465267832 +++ ChangeLog 2f53a621e78d70464a48722c586ac3abd6efa4b5 @@ -1,3 +1,15 @@ +2007-03-29 Grahame Bowland + + * rewrite BranchChanges.get_last_changes, much more + efficient algorithm suggested by Matthias Radestock. + Use python's heapq class to get an efficient, sorted + list of revisions of interest. + * to my horror, discover that README has totally out + of date, incorrect installation instructions. Delete + and replace with something useful. This explains the + emails I've been getting asking for help setting + up mod_python and wrapper.py.. + 2006-10-26 Grahame Bowland * release 0.06 ============================================================ --- README 46ffe1ce5080c9fd0081574ae8a8da30c3df65dc +++ README 5fa5a33cef3770ba09a216acc1659490712ba505 @@ -1,48 +1,13 @@ - ViewMTN ------- A web interface to monotone. See "LICENSE" for distribution terms. ViewMTN is Copyright 2005 Grahame Bowland. -The minimum version of monotone required is: 0.24 +The minimum version of monotone required is: 0.32 -For the graphs to work you'll need dotty installed - it is a -part of GraphViz. - http://www.research.att.com/sw/tools/graphviz/ +See "INSTALL" for installation information. -ViewMTN requires mod_python. - http://www.modpython.org/ - -When installing be sure to copy config.py.example to config.py, and -then edit config.py (paying attention to the comments!) - -Common issues -------------- - -If you are getting a 404 error for "getfile.py", make sure that you have -updated ".htacess" to include the following line. - PythonHandler wrapper -"wrapper.py" contains several Python functions which are called -for various pages that do not need to go through mod_python's PSP -framework. The above line causes all page requests to go through -wrapper.py, which decides which function (or PSP file) should be called -to handle the request. - -(Note: recent versions of ViewMTN will not work at all if you are missing - the line above.) - -MacOS ------ - -I run ViewMTN on MacOS by using mod_python and apache2 compiled from source -using Darwin Ports: - http://darwinports.opendarwin.org/ -You should be able to install graphviz from Darwin Ports as well. - -The graphs seem to look terrible with the default fault from config.py.example; -I set the font to "Monaco" instead and it looks pretty good. - Bugs, suggestions, feedback --------------------------- @@ -50,13 +15,7 @@ Grahame Bowland PO BOX 3105, Broadway, Nedlands WA 6009 Australia -In particular, please look at the TODO file. If you're interested in -fixing any of the issues listed (or just adding extra TODO entries) -please go ahead - perhaps let me know so I can keep track and let you -know if the item is already done but not committed. - As monotone is a distributed version control system, feel free to grab a copy of viewmtn, commit to your local DB, etc. If you want to send me your commits, email me (or catch me in #monotone) and we'll work something out. - ============================================================ --- viewmtn.py 26b1e351f925173805bccc4b59c24f3d40cde0c6 +++ viewmtn.py 2ab7af7898c05351d6121d756037736fed7116b5 @@ -7,6 +7,7 @@ import json import sys import web import json +import heapq import struct import string import rfc822 @@ -351,12 +352,25 @@ class BranchChanges: class BranchChanges: def get_last_changes(self, branch, heads, from_change, to_change): - revs = set(heads) - if len(revs) == 0: - raise Exception("get_last_changes() unable to find somewhere to start - probably a non-existent branch?") - new_to_parent = set() - to_parent = revs.copy() - count = to_change + # revised algorithm in colaboration with Matthias Radestock + # + # use a heapq to keep a list of interesting revisions + # pop from the heapq; get the most recent interesting revision + # insert the parents of this revision into the heap + # .. repeat until len(heap) >= to_count + class ComparisonRev: + def __init__(self, revision): + self.revision = revision + self.certs = map (None, ops.certs(self.revision)) + self.date = None + for cert in self.certs: + if cert[4] == 'name' and cert[5] == 'date': + self.date = common.parse_timecert(cert[7]) + def __cmp__(self, other): + # irritating edge-case, heapq compares us to empty string if + # there's only one thing in the list + if not other: return 1 + return cmp(self.date, other.date) def on_our_branch(r): rv = False @@ -365,34 +379,30 @@ class BranchChanges: if cert[7] == branch.name: rv = True return rv - - while len(revs) < count: - new_to_parent = set() + + if not heads: + raise Exception("get_last_changes() unable to find somewhere to start - probably a non-existent branch?") + + result = [] + revq = [] + to_parent = map (lambda r: ComparisonRev(r), heads) + while len(result) < to_change: for rev in to_parent: - # we must be cautious; we only want to look at parents on our branch! - parents = filter(None, ops.parents(rev)) + parents = filter(None, ops.parents(rev.revision)) for parent_rev in parents: if parent_rev == None or not on_our_branch(parent_rev): continue - new_to_parent.add(parent_rev) - if len(new_to_parent) == 0: - # out of revisions... - break - to_parent = new_to_parent - for rev in new_to_parent: - revs.add(rev) -# toposort seems pretty darn slow; let's avoid this one.. -# revs = map(None, ops.toposort(revs))[:count] - certs_for_revs = [] - for rev in revs: - certs_for_revs.append((rev, map(None, ops.certs(rev)))) - def cd(certs): - for cert in certs: - if cert[4] == 'name' and cert[5] == 'date': - return common.parse_timecert(cert[7]) - return None - certs_for_revs.sort(lambda b, a: cmp(cd(a[1]), cd(b[1]))) - return certs_for_revs[from_change:to_change], list(new_to_parent) + heapq.heappush(revq, ComparisonRev(parent_rev)) + if len(revq) == 0: + break + # follow the newest edge + next_rev = heapq.heappop(revq) + to_parent = [ next_rev ] + result.append(next_rev) + + rv = map (lambda x: (x.revision, x.certs), result[from_change:to_change]), revq + print >> sys.stderr, revq + return rv def GET(self, branch, from_change, to_change, template_name): def for_template(revs):