Mercurial > hg-stable
changeset 3142:aabc5ef7d159
merge with crew
| author | Benoit Boissinot <benoit.boissinot@ens-lyon.org> |
|---|---|
| date | Fri, 22 Sep 2006 08:48:56 +0200 |
| parents | e21337e06952 (current diff) 1fd1cdcc4200 (diff) |
| children | db25f7b80fdb |
| files | |
| diffstat | 5 files changed, 156 insertions(+), 83 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/mercurial/ancestor.py Fri Sep 22 08:48:56 2006 +0200 @@ -0,0 +1,83 @@ +# ancestor.py - generic DAG ancestor algorithm for mercurial +# +# Copyright 2006 Matt Mackall <mpm@selenic.com> +# +# This software may be used and distributed according to the terms +# of the GNU General Public License, incorporated herein by reference. + +import heapq + +def ancestor(a, b, pfunc): + """ + return the least common ancestor of nodes a and b or None if there + is no such ancestor. + + pfunc must return a list of parent vertices + """ + + if a == b: + return a + + # find depth from root of all ancestors + visit = [a, b] + depth = {} + while visit: + vertex = visit[-1] + pl = pfunc(vertex) + if not pl: + depth[vertex] = 0 + visit.pop() + else: + for p in pl: + if p == a or p == b: # did we find a or b as a parent? + return p # we're done + if p not in depth: + visit.append(p) + if visit[-1] == vertex: + depth[vertex] = min([depth[p] for p in pl]) - 1 + visit.pop() + + # traverse ancestors in order of decreasing distance from root + def ancestors(vertex): + h = [(depth[vertex], vertex)] + seen = {} + while h: + d, n = heapq.heappop(h) + if n not in seen: + seen[n] = 1 + yield (d, n) + for p in pfunc(n): + heapq.heappush(h, (depth[p], p)) + + def generations(vertex): + sg, s = None, {} + for g,v in ancestors(vertex): + if g != sg: + if sg: + yield sg, s + sg, s = g, {v:1} + else: + s[v] = 1 + yield sg, s + + x = generations(a) + y = generations(b) + gx = x.next() + gy = y.next() + + # increment each ancestor list until it is closer to root than + # the other, or they match + try: + while 1: + if gx[0] == gy[0]: + for v in gx[1]: + if v in gy[1]: + return v + gy = y.next() + gx = x.next() + elif gx[0] > gy[0]: + gy = y.next() + else: + gx = x.next() + except StopIteration: + return None
--- a/mercurial/context.py Tue Sep 19 10:22:30 2006 -0700 +++ b/mercurial/context.py Fri Sep 22 08:48:56 2006 +0200 @@ -5,6 +5,10 @@ # This software may be used and distributed according to the terms # of the GNU General Public License, incorporated herein by reference. +from node import * +from demandload import demandload +demandload(globals(), "ancestor") + class changectx(object): """A changecontext object makes access to data related to a particular changeset convenient.""" @@ -42,7 +46,7 @@ def node(self): return self._node def user(self): return self.changeset()[1] def date(self): return self.changeset()[2] - def changedfiles(self): return self.changeset()[3] + def files(self): return self.changeset()[3] def description(self): return self.changeset()[4] def parents(self): @@ -74,10 +78,17 @@ for f in m: yield self.filectx(f, fileid=mf[f]) + def ancestor(self, c2): + """ + return the ancestor context of self and c2 + """ + n = self._repo.changelog.ancestor(self._node, c2._node) + return changectx(self._repo, n) + class filectx(object): """A filecontext object makes access to data related to a particular filerevision convenient.""" - def __init__(self, repo, path, changeid=None, fileid=None): + def __init__(self, repo, path, changeid=None, fileid=None, filelog=None): """changeid can be a changeset revision, node, or tag. fileid can be a file revision or node.""" self._repo = repo @@ -85,15 +96,18 @@ assert changeid or fileid + if filelog: + self._filelog = filelog + else: + self._filelog = self._repo.file(self._path) + if not fileid: # if given a changeset id, go ahead and look up the file self._changeid = changeid self._changectx = self.changectx() - self._filelog = self._repo.file(self._path) self._filenode = self._changectx.filenode(self._path) else: - # else be lazy - self._filelog = self._repo.file(self._path) + # else delay changectx creation self._filenode = self._filelog.lookup(fileid) self._changeid = self._filelog.linkrev(self._filenode) self._filerev = self._filelog.rev(self._filenode) @@ -118,18 +132,55 @@ def manifest(self): return self.changectx().manifest() def data(self): return self._filelog.read(self._filenode) - def metadata(self): return self._filelog.readmeta(self._filenode) def renamed(self): return self._filelog.renamed(self._filenode) + def path(self): return self._path def parents(self): - # need to fix for renames - p = self._filelog.parents(self._filenode) - return [ filectx(self._repo, self._path, fileid=x) for x in p ] + p = self._path + fl = self._filelog + pl = [ (p, n, fl) for n in self._filelog.parents(self._filenode) ] + + r = self.renamed() + if r: + pl[0] = (r[0], r[1], None) + + return [ filectx(self._repo, p, fileid=n, filelog=l) + for p,n,l in pl if n != nullid ] def children(self): # hard for renames c = self._filelog.children(self._filenode) - return [ filectx(self._repo, self._path, fileid=x) for x in c ] + return [ filectx(self._repo, self._path, fileid=x, + filelog=self._filelog) for x in c ] def annotate(self): return self._filelog.annotate(self._filenode) + + def ancestor(self, fc2): + """ + find the common ancestor file context, if any, of self, and fc2 + """ + + acache = {} + flcache = {self._path:self._filelog, fc2._path:fc2._filelog} + def parents(vertex): + if vertex in acache: + return acache[vertex] + f, n = vertex + if f not in flcache: + flcache[f] = self._repo.file(f) + fl = flcache[f] + pl = [ (f,p) for p in fl.parents(n) if p != nullid ] + re = fl.renamed(n) + if re: + pl.append(re) + acache[vertex]=pl + return pl + + a, b = (self._path, self._filenode), (fc2._path, fc2._filenode) + v = ancestor.ancestor(a, b, parents) + if v: + f,n = v + return filectx(self._repo, f, fileid=n, filelog=flcache[f]) + + return None
--- a/mercurial/filelog.py Tue Sep 19 10:22:30 2006 -0700 +++ b/mercurial/filelog.py Fri Sep 22 08:48:56 2006 +0200 @@ -37,7 +37,7 @@ s = t.index('\1\n', 2) return t[s+2:] - def readmeta(self, node): + def _readmeta(self, node): t = self.revision(node) if not t.startswith('\1\n'): return {} @@ -60,7 +60,7 @@ def renamed(self, node): if self.parents(node)[0] != nullid: return False - m = self.readmeta(node) + m = self._readmeta(node) if m and m.has_key("copy"): return (m["copy"], bin(m["copyrev"])) return False
--- a/mercurial/mpatch.c Tue Sep 19 10:22:30 2006 -0700 +++ b/mercurial/mpatch.c Fri Sep 22 08:48:56 2006 +0200 @@ -62,6 +62,9 @@ { struct flist *a = NULL; + if (size < 1) + size = 1; + a = (struct flist *)malloc(sizeof(struct flist)); if (a) { a->base = (struct frag *)malloc(sizeof(struct frag) * size);
--- a/mercurial/revlog.py Tue Sep 19 10:22:30 2006 -0700 +++ b/mercurial/revlog.py Fri Sep 22 08:48:56 2006 +0200 @@ -13,7 +13,7 @@ from node import * from i18n import gettext as _ from demandload import demandload -demandload(globals(), "binascii changegroup errno heapq mdiff os") +demandload(globals(), "binascii changegroup errno ancestor mdiff os") demandload(globals(), "sha struct util zlib") # revlog version strings @@ -1016,78 +1016,14 @@ def ancestor(self, a, b): """calculate the least common ancestor of nodes a and b""" - # start with some short cuts for the linear cases - if a == b: - return a - ra = self.rev(a) - rb = self.rev(b) - if ra < rb: - last = b - first = a - else: - last = a - first = b - - # reachable won't include stop in the list, so we have to use a parent - reachable = self.reachable(last, stop=self.parents(first)[0]) - if first in reachable: - return first - - # calculate the distance of every node from root - dist = {nullid: 0} - for i in xrange(self.count()): - n = self.node(i) - p1, p2 = self.parents(n) - dist[n] = max(dist[p1], dist[p2]) + 1 + def parents(rev): + return [p for p in self.parentrevs(rev) if p != -1] - # traverse ancestors in order of decreasing distance from root - def ancestors(node): - # we store negative distances because heap returns smallest member - h = [(-dist[node], node)] - seen = {} - while h: - d, n = heapq.heappop(h) - if n not in seen: - seen[n] = 1 - yield (-d, n) - for p in self.parents(n): - heapq.heappush(h, (-dist[p], p)) - - def generations(node): - sg, s = None, {} - for g,n in ancestors(node): - if g != sg: - if sg: - yield sg, s - sg, s = g, {n:1} - else: - s[n] = 1 - yield sg, s + c = ancestor.ancestor(self.rev(a), self.rev(b), parents) + if c is None: + return nullid - x = generations(a) - y = generations(b) - gx = x.next() - gy = y.next() - - # increment each ancestor list until it is closer to root than - # the other, or they match - while 1: - #print "ancestor gen %s %s" % (gx[0], gy[0]) - if gx[0] == gy[0]: - # find the intersection - i = [ n for n in gx[1] if n in gy[1] ] - if i: - return i[0] - else: - #print "next" - gy = y.next() - gx = x.next() - elif gx[0] < gy[0]: - #print "next y" - gy = y.next() - else: - #print "next x" - gx = x.next() + return self.node(c) def group(self, nodelist, lookup, infocollect=None): """calculate a delta group