##// END OF EJS Templates
strip: make query to get new bookmark target cheaper...
strip: make query to get new bookmark target cheaper The current query to get the new bookmark target for stripped revisions involves multiple walks up the DAG, and is really expensive, taking over 2.5 seconds on a repository with over 400,000 changesets even if just one changeset is being stripped. A slightly simplified version of the current query is max(heads(::<tostrip> - <tostrip>)) We make two observations here. 1. For any set s, max(heads(s)) == max(s). That is because revision numbers define a topological order, so that the element with the highest revision number in s will not have any children in s. 2. For any set s, max(::s - s) == max(parents(s) - s). In other words, the ancestor of s with the highest revision number not in s is a parent of one of the revs in s. Why? Because if it were an ancestor but not a parent of s, it would have a descendant that would be a parent of s. This descendant would have a higher revision number, leading to a contradiction. Combining these two observations, we rewrite the revset query as max(parents(<tostrip>) - <tostrip>) The time complexity is now linear in the number of changesets being stripped. For the above repository, the query now takes 0.1 seconds when one changeset is stripped. This speeds up operations that use repair.strip, like the rebase and strip commands.

File last commit:

r17991:d605a82c default
r18040:fe8caf28 default
Show More
webutil.py
350 lines | 11.0 KiB | text/x-python | PythonLexer
# hgweb/webutil.py - utility library for the web interface.
#
# Copyright 21 May 2005 - (c) 2005 Jake Edge <jake@edge2.net>
# Copyright 2005-2007 Matt Mackall <mpm@selenic.com>
#
# This software may be used and distributed according to the terms of the
# GNU General Public License version 2 or any later version.
import os, copy
from mercurial import match, patch, scmutil, error, ui, util
from mercurial.i18n import _
from mercurial.node import hex, nullid
from common import ErrorResponse
from common import HTTP_NOT_FOUND
import difflib
def up(p):
if p[0] != "/":
p = "/" + p
if p[-1] == "/":
p = p[:-1]
up = os.path.dirname(p)
if up == "/":
return "/"
return up + "/"
def revnavgen(pos, pagelen, limit, nodefunc):
def seq(factor, limit=None):
if limit:
yield limit
if limit >= 20 and limit <= 40:
yield 50
else:
yield 1 * factor
yield 3 * factor
for f in seq(factor * 10):
yield f
navbefore = []
navafter = []
last = 0
for f in seq(1, pagelen):
if f < pagelen or f <= last:
continue
if f > limit:
break
last = f
if pos + f < limit:
navafter.append(("+%d" % f, hex(nodefunc(pos + f).node())))
if pos - f >= 0:
navbefore.insert(0, ("-%d" % f, hex(nodefunc(pos - f).node())))
navafter.append(("tip", "tip"))
try:
navbefore.insert(0, ("(0)", hex(nodefunc('0').node())))
except error.RepoError:
pass
def gen(l):
def f(**map):
for label, node in l:
yield {"label": label, "node": node}
return f
return (dict(before=gen(navbefore), after=gen(navafter)),)
def _siblings(siblings=[], hiderev=None):
siblings = [s for s in siblings if s.node() != nullid]
if len(siblings) == 1 and siblings[0].rev() == hiderev:
return
for s in siblings:
d = {'node': s.hex(), 'rev': s.rev()}
d['user'] = s.user()
d['date'] = s.date()
d['description'] = s.description()
d['branch'] = s.branch()
if util.safehasattr(s, 'path'):
d['file'] = s.path()
yield d
def parents(ctx, hide=None):
return _siblings(ctx.parents(), hide)
def children(ctx, hide=None):
return _siblings(ctx.children(), hide)
def renamelink(fctx):
r = fctx.renamed()
if r:
return [dict(file=r[0], node=hex(r[1]))]
return []
def nodetagsdict(repo, node):
return [{"name": i} for i in repo.nodetags(node)]
def nodebookmarksdict(repo, node):
return [{"name": i} for i in repo.nodebookmarks(node)]
def nodebranchdict(repo, ctx):
branches = []
branch = ctx.branch()
# If this is an empty repo, ctx.node() == nullid,
# ctx.branch() == 'default'.
try:
branchnode = repo.branchtip(branch)
except error.RepoLookupError:
branchnode = None
if branchnode == ctx.node():
branches.append({"name": branch})
return branches
def nodeinbranch(repo, ctx):
branches = []
branch = ctx.branch()
try:
branchnode = repo.branchtip(branch)
except error.RepoLookupError:
branchnode = None
if branch != 'default' and branchnode != ctx.node():
branches.append({"name": branch})
return branches
def nodebranchnodefault(ctx):
branches = []
branch = ctx.branch()
if branch != 'default':
branches.append({"name": branch})
return branches
def showtag(repo, tmpl, t1, node=nullid, **args):
for t in repo.nodetags(node):
yield tmpl(t1, tag=t, **args)
def showbookmark(repo, tmpl, t1, node=nullid, **args):
for t in repo.nodebookmarks(node):
yield tmpl(t1, bookmark=t, **args)
def cleanpath(repo, path):
path = path.lstrip('/')
return scmutil.canonpath(repo.root, '', path)
def changeidctx (repo, changeid):
try:
ctx = repo[changeid]
except error.RepoError:
man = repo.manifest
ctx = repo[man.linkrev(man.rev(man.lookup(changeid)))]
return ctx
def changectx (repo, req):
changeid = "tip"
if 'node' in req.form:
changeid = req.form['node'][0]
ipos=changeid.find(':')
if ipos != -1:
changeid = changeid[(ipos + 1):]
elif 'manifest' in req.form:
changeid = req.form['manifest'][0]
return changeidctx(repo, changeid)
def basechangectx(repo, req):
if 'node' in req.form:
changeid = req.form['node'][0]
ipos=changeid.find(':')
if ipos != -1:
changeid = changeid[:ipos]
return changeidctx(repo, changeid)
return None
def filectx(repo, req):
if 'file' not in req.form:
raise ErrorResponse(HTTP_NOT_FOUND, 'file not given')
path = cleanpath(repo, req.form['file'][0])
if 'node' in req.form:
changeid = req.form['node'][0]
elif 'filenode' in req.form:
changeid = req.form['filenode'][0]
else:
raise ErrorResponse(HTTP_NOT_FOUND, 'node or filenode not given')
try:
fctx = repo[changeid][path]
except error.RepoError:
fctx = repo.filectx(path, fileid=changeid)
return fctx
def listfilediffs(tmpl, files, node, max):
for f in files[:max]:
yield tmpl('filedifflink', node=hex(node), file=f)
if len(files) > max:
yield tmpl('fileellipses')
def diffs(repo, tmpl, ctx, basectx, files, parity, style):
def countgen():
start = 1
while True:
yield start
start += 1
blockcount = countgen()
def prettyprintlines(diff, blockno):
for lineno, l in enumerate(diff.splitlines(True)):
lineno = "%d.%d" % (blockno, lineno + 1)
if l.startswith('+'):
ltype = "difflineplus"
elif l.startswith('-'):
ltype = "difflineminus"
elif l.startswith('@'):
ltype = "difflineat"
else:
ltype = "diffline"
yield tmpl(ltype,
line=l,
lineid="l%s" % lineno,
linenumber="% 8s" % lineno)
if files:
m = match.exact(repo.root, repo.getcwd(), files)
else:
m = match.always(repo.root, repo.getcwd())
diffopts = patch.diffopts(repo.ui, untrusted=True)
if basectx is None:
parents = ctx.parents()
node1 = parents and parents[0].node() or nullid
else:
node1 = basectx.node()
node2 = ctx.node()
block = []
for chunk in patch.diff(repo, node1, node2, m, opts=diffopts):
if chunk.startswith('diff') and block:
blockno = blockcount.next()
yield tmpl('diffblock', parity=parity.next(), blockno=blockno,
lines=prettyprintlines(''.join(block), blockno))
block = []
if chunk.startswith('diff') and style != 'raw':
chunk = ''.join(chunk.splitlines(True)[1:])
block.append(chunk)
blockno = blockcount.next()
yield tmpl('diffblock', parity=parity.next(), blockno=blockno,
lines=prettyprintlines(''.join(block), blockno))
def compare(tmpl, context, leftlines, rightlines):
'''Generator function that provides side-by-side comparison data.'''
def compline(type, leftlineno, leftline, rightlineno, rightline):
lineid = leftlineno and ("l%s" % leftlineno) or ''
lineid += rightlineno and ("r%s" % rightlineno) or ''
return tmpl('comparisonline',
type=type,
lineid=lineid,
leftlinenumber="% 6s" % (leftlineno or ''),
leftline=leftline or '',
rightlinenumber="% 6s" % (rightlineno or ''),
rightline=rightline or '')
def getblock(opcodes):
for type, llo, lhi, rlo, rhi in opcodes:
len1 = lhi - llo
len2 = rhi - rlo
count = min(len1, len2)
for i in xrange(count):
yield compline(type=type,
leftlineno=llo + i + 1,
leftline=leftlines[llo + i],
rightlineno=rlo + i + 1,
rightline=rightlines[rlo + i])
if len1 > len2:
for i in xrange(llo + count, lhi):
yield compline(type=type,
leftlineno=i + 1,
leftline=leftlines[i],
rightlineno=None,
rightline=None)
elif len2 > len1:
for i in xrange(rlo + count, rhi):
yield compline(type=type,
leftlineno=None,
leftline=None,
rightlineno=i + 1,
rightline=rightlines[i])
s = difflib.SequenceMatcher(None, leftlines, rightlines)
if context < 0:
yield tmpl('comparisonblock', lines=getblock(s.get_opcodes()))
else:
for oc in s.get_grouped_opcodes(n=context):
yield tmpl('comparisonblock', lines=getblock(oc))
def diffstatgen(ctx, basectx):
'''Generator function that provides the diffstat data.'''
stats = patch.diffstatdata(util.iterlines(ctx.diff(basectx)))
maxname, maxtotal, addtotal, removetotal, binary = patch.diffstatsum(stats)
while True:
yield stats, maxname, maxtotal, addtotal, removetotal, binary
def diffsummary(statgen):
'''Return a short summary of the diff.'''
stats, maxname, maxtotal, addtotal, removetotal, binary = statgen.next()
return _(' %d files changed, %d insertions(+), %d deletions(-)\n') % (
len(stats), addtotal, removetotal)
def diffstat(tmpl, ctx, statgen, parity):
'''Return a diffstat template for each file in the diff.'''
stats, maxname, maxtotal, addtotal, removetotal, binary = statgen.next()
files = ctx.files()
def pct(i):
if maxtotal == 0:
return 0
return (float(i) / maxtotal) * 100
fileno = 0
for filename, adds, removes, isbinary in stats:
template = filename in files and 'diffstatlink' or 'diffstatnolink'
total = adds + removes
fileno += 1
yield tmpl(template, node=ctx.hex(), file=filename, fileno=fileno,
total=total, addpct=pct(adds), removepct=pct(removes),
parity=parity.next())
class sessionvars(object):
def __init__(self, vars, start='?'):
self.start = start
self.vars = vars
def __getitem__(self, key):
return self.vars[key]
def __setitem__(self, key, value):
self.vars[key] = value
def __copy__(self):
return sessionvars(copy.copy(self.vars), self.start)
def __iter__(self):
separator = self.start
for key, value in self.vars.iteritems():
yield {'name': key, 'value': str(value), 'separator': separator}
separator = '&'
class wsgiui(ui.ui):
# default termwidth breaks under mod_wsgi
def termwidth(self):
return 80