Refactor merge code

Delete old code
Fix calculation of newer nodes on server
Fix branch recursion on client
Fix manifest merge problems
Add more debugging and note messages to merge

mercurial/hg.py

@@ -1,967 +1,825 b''
 # hg.py - repository classes for mercurial
 #
 # Copyright 2005 Matt Mackall <[e-mail]>
 #
 # This software may be used and distributed according to the terms
 # of the GNU General Public License, incorporated herein by reference.
 
 import sys, struct, sha, socket, os, time, base64, re, urllib2
 import urllib
 from mercurial import byterange
 from mercurial.transaction import *
 from mercurial.revlog import *
 from difflib import SequenceMatcher
 
 class filelog(revlog):
     def __init__(self, opener, path):
         s = self.encodepath(path)
         revlog.__init__(self, opener, os.path.join("data", s + "i"),
                         os.path.join("data", s))
 
     def encodepath(self, path):
         s = sha.sha(path).digest()
         s = base64.encodestring(s)[:-3]
         s = re.sub("\+", "%", s)
         s = re.sub("/", "_", s)
         return s
 
     def read(self, node):
         return self.revision(node)
     def add(self, text, transaction, link, p1=None, p2=None):
         return self.addrevision(text, transaction, link, p1, p2)
 
-    def resolvedag(self, old, new, transaction, link):
-        """resolve unmerged heads in our DAG"""
-        if old == new: return None
-        a = self.ancestor(old, new)
-        if old == a: return None
-        return self.merge3(old, new, a, transaction, link)
-
-    def merge3(self, my, other, base, transaction, link):
-        """perform a 3-way merge and append the result"""
-        def temp(prefix, node):
-            (fd, name) = tempfile.mkstemp(prefix)
-            f = os.fdopen(fd, "w")
-            f.write(self.revision(node))
-            f.close()
-            return name
-
-        a = temp("local", my)
-        b = temp("remote", other)
-        c = temp("parent", base)
-
-        cmd = os.environ["HGMERGE"]
-        r = os.system("%s %s %s %s" % (cmd, a, b, c))
-        if r:
-            raise "Merge failed, implement rollback!"
-
-        t = open(a).read()
-        os.unlink(a)
-        os.unlink(b)
-        os.unlink(c)
-        return self.addrevision(t, transaction, link, my, other)
-
-    def merge(self, other, transaction, linkseq, link):
-        """perform a merge and resolve resulting heads"""
-        (o, n) = self.mergedag(other, transaction, linkseq)
-        return self.resolvedag(o, n, transaction, link)
-
     def annotate(self, node):
         revs = []
         while node != nullid:
             revs.append(node)
             node = self.parents(node)[0]
         revs.reverse()
         prev = []
         annotate = []
         for node in revs:
             curr = self.read(node).splitlines(1)
             linkrev = self.linkrev(node)
             sm = SequenceMatcher(None, prev, curr)
             offset = 0
             for o, m, n, s, t in sm.get_opcodes():
                 if o in ('insert','replace'):
                     annotate[m+offset:n+offset] = \
                         [ (linkrev, l) for l in curr[s:t]]
                     if o == 'insert':
                         offset += m-n
                 elif o == 'delete':
                     del annotate[m+offset:n+offset]
                     offset -= m-n
             assert len(annotate) == len(curr)
             prev = curr
         return annotate
 
 class manifest(revlog):
     def __init__(self, opener):
         self.mapcache = None
         self.listcache = None
         self.addlist = None
         revlog.__init__(self, opener, "00manifest.i", "00manifest.d")
 
     def read(self, node):
         if self.mapcache and self.mapcache[0] == node:
             return self.mapcache[1].copy()
         text = self.revision(node)
         map = {}
         self.listcache = (text, text.splitlines(1))
         for l in self.listcache[1]:
             (f, n) = l.split('\0')
             map[f] = bin(n[:40])
         self.mapcache = (node, map)
         return map
 
     def diff(self, a, b):
         # this is sneaky, as we're not actually using a and b
         if self.listcache and len(self.listcache[0]) == len(a):
             return mdiff.diff(self.listcache[1], self.addlist, 1)
         else:
             return mdiff.textdiff(a, b)
 
     def add(self, map, transaction, link, p1=None, p2=None):
         files = map.keys()
         files.sort()
 
         self.addlist = ["%s\000%s\n" % (f, hex(map[f])) for f in files]
         text = "".join(self.addlist)
 
         n = self.addrevision(text, transaction, link, p1, p2)
         self.mapcache = (n, map)
         self.listcache = (text, self.addlist)
 
         return n
 
 class changelog(revlog):
     def __init__(self, opener):
         revlog.__init__(self, opener, "00changelog.i", "00changelog.d")
 
     def extract(self, text):
         if not text:
             return (nullid, "", "0", [], "")
         last = text.index("\n\n")
         desc = text[last + 2:]
         l = text[:last].splitlines()
         manifest = bin(l[0])
         user = l[1]
         date = l[2]
         files = l[3:]
         return (manifest, user, date, files, desc)
 
     def read(self, node):
         return self.extract(self.revision(node))
 
     def add(self, manifest, list, desc, transaction, p1=None, p2=None):
         user = (os.environ.get("HGUSER") or
                 os.environ.get("EMAIL") or
                 os.environ.get("LOGNAME", "unknown") + '@' + socket.getfqdn())
         date = "%d %d" % (time.time(), time.timezone)
         list.sort()
         l = [hex(manifest), user, date] + list + ["", desc]
         text = "\n".join(l)
         return self.addrevision(text, transaction, self.count(), p1, p2)
 
-    def merge3(self, my, other, base):
-        pass
-
 class dircache:
     def __init__(self, opener, ui):
         self.opener = opener
         self.dirty = 0
         self.ui = ui
         self.map = None
     def __del__(self):
         if self.dirty: self.write()
     def __getitem__(self, key):
         try:
             return self.map[key]
         except TypeError:
             self.read()
             return self[key]
         
     def read(self):
         if self.map is not None: return self.map
 
         self.map = {}
         try:
             st = self.opener("dircache").read()
         except: return
 
         pos = 0
         while pos < len(st):
             e = struct.unpack(">llll", st[pos:pos+16])
             l = e[3]
             pos += 16
             f = st[pos:pos + l]
             self.map[f] = e[:3]
             pos += l
         
     def update(self, files):
         if not files: return
         self.read()
         self.dirty = 1
         for f in files:
             try:
                 s = os.stat(f)
                 self.map[f] = (s.st_mode, s.st_size, s.st_mtime)
             except IOError:
                 self.remove(f)
 
     def taint(self, files):
         if not files: return
         self.read()
         self.dirty = 1
         for f in files:
             self.map[f] = (0, -1, 0)
 
     def remove(self, files):
         if not files: return
         self.read()
         self.dirty = 1
         for f in files:
             try:
                 del self.map[f]
             except KeyError:
                 self.ui.warn("Not in dircache: %s\n" % f)
                 pass
 
     def clear(self):
         self.map = {}
         self.dirty = 1
 
     def write(self):
         st = self.opener("dircache", "w")
         for f, e in self.map.items():
             e = struct.pack(">llll", e[0], e[1], e[2], len(f))
             st.write(e + f)
         self.dirty = 0
 
     def copy(self):
         self.read()
         return self.map.copy()
 
 # used to avoid circular references so destructors work
 def opener(base):
     p = base
     def o(path, mode="r"):
         if p[:7] == "http://":
             f = os.path.join(p, urllib.quote(path))
             return httprangereader(f)
 
         f = os.path.join(p, path)
 
         if mode != "r" and os.path.isfile(f):
             s = os.stat(f)
             if s.st_nlink > 1:
                 file(f + ".tmp", "w").write(file(f).read())
                 os.rename(f+".tmp", f)
 
         return file(f, mode)
 
     return o
 
 class localrepository:
     def __init__(self, ui, path=None, create=0):
         self.remote = 0
         if path and path[:7] == "http://":
             self.remote = 1
             self.path = path
         else:
             if not path:
                 p = os.getcwd()
                 while not os.path.isdir(os.path.join(p, ".hg")):
                     p = os.path.dirname(p)
                     if p == "/": raise "No repo found"
                 path = p
             self.path = os.path.join(path, ".hg")
 
         self.root = path
         self.ui = ui
 
         if create:
             os.mkdir(self.path)  
             os.mkdir(self.join("data"))
 
         self.opener = opener(self.path)
         self.manifest = manifest(self.opener)
         self.changelog = changelog(self.opener)
         self.ignorelist = None
         self.tags = None
 
         if not self.remote:
             self.dircache = dircache(self.opener, ui)
             try:
                 self.current = bin(self.opener("current").read())
             except IOError:
                 self.current = None
 
     def setcurrent(self, node):
         self.current = node
         self.opener("current", "w").write(hex(node))
       
     def ignore(self, f):
         if self.ignorelist is None:
             self.ignorelist = []
             try:
                 l = open(os.path.join(self.root, ".hgignore"))
                 for pat in l:
                     if pat != "\n":
                         self.ignorelist.append(re.compile(pat[:-1]))
             except IOError: pass
         for pat in self.ignorelist:
             if pat.search(f): return True
         return False
 
     def lookup(self, key):
         if self.tags is None:
             self.tags = {}
             try:
                 fl = self.file(".hgtags")
                 for l in fl.revision(fl.tip()).splitlines():
                     if l:
                         n, k = l.split(" ")
                         self.tags[k] = bin(n)
             except KeyError: pass
         try:
             return self.tags[key]
         except KeyError:
             return self.changelog.lookup(key)
 
     def join(self, f):
         return os.path.join(self.path, f)
 
     def file(self, f):
         return filelog(self.opener, f)
 
     def transaction(self):
         return transaction(self.opener, self.join("journal"))
 
-    def merge(self, other):
-        tr = self.transaction()
-        changed = {}
-        new = {}
-        seqrev = self.changelog.count()
-        # some magic to allow fiddling in nested scope
-        nextrev = [seqrev]
-
-        # helpers for back-linking file revisions to local changeset
-        # revisions so we can immediately get to changeset from annotate
-        def accumulate(text):
-            # track which files are added in which changeset and the
-            # corresponding _local_ changeset revision
-            files = self.changelog.extract(text)[3]
-            for f in files:
-                changed.setdefault(f, []).append(nextrev[0])
-            nextrev[0] += 1
-
-        def seq(start):
-            while 1:
-                yield start
-                start += 1
-
-        def lseq(l):
-            for r in l:
-                yield r
-
-        # begin the import/merge of changesets
-        self.ui.status("merging new changesets\n")
-        (co, cn) = self.changelog.mergedag(other.changelog, tr,
-                                           seq(seqrev), accumulate)
-        resolverev = self.changelog.count()
-
-        # is there anything to do?
-        if co == cn:
-            tr.close()
-            return
-        
-        # do we need to resolve?
-        simple = (co == self.changelog.ancestor(co, cn))
-
-        # merge all files changed by the changesets,
-        # keeping track of the new tips
-        changelist = changed.keys()
-        changelist.sort()
-        for f in changelist:
-            sys.stdout.write(".")
-            sys.stdout.flush()
-            r = self.file(f)
-            node = r.merge(other.file(f), tr, lseq(changed[f]), resolverev)
-            if node:
-                new[f] = node
-        sys.stdout.write("\n")
-
-        # begin the merge of the manifest
-        self.ui.status("merging manifests\n")
-        (mm, mo) = self.manifest.mergedag(other.manifest, tr, seq(seqrev))
-
-        # For simple merges, we don't need to resolve manifests or changesets
-        if simple:
-            tr.close()
-            return
-
-        ma = self.manifest.ancestor(mm, mo)
-
-        # resolve the manifest to point to all the merged files
-        self.ui.status("resolving manifests\n")
-        omap = self.manifest.read(mo) # other
-        amap = self.manifest.read(ma) # ancestor
-        mmap = self.manifest.read(mm) # mine
-        nmap = {}
-
-        for f, mid in mmap.iteritems():
-            if f in omap:
-                if mid != omap[f]: 
-                    nmap[f] = new.get(f, mid) # use merged version
-                else:
-                    nmap[f] = new.get(f, mid) # they're the same
-                del omap[f]
-            elif f in amap:
-                if mid != amap[f]: 
-                    pass # we should prompt here
-                else:
-                    pass # other deleted it
-            else:
-                nmap[f] = new.get(f, mid) # we created it
-                
-        del mmap
-
-        for f, oid in omap.iteritems():
-            if f in amap:
-                if oid != amap[f]:
-                    pass # this is the nasty case, we should prompt
-                else:
-                    pass # probably safe
-            else:
-                nmap[f] = new.get(f, oid) # remote created it
-
-        del omap
-        del amap
-
-        node = self.manifest.add(nmap, tr, resolverev, mm, mo)
-
-        # Now all files and manifests are merged, we add the changed files
-        # and manifest id to the changelog
-        self.ui.status("committing merge changeset\n")
-        new = new.keys()
-        new.sort()
-        if co == cn: cn = -1
-
-        edittext = "\n"+"".join(["HG: changed %s\n" % f for f in new])
-        edittext = self.ui.edit(edittext)
-        n = self.changelog.add(node, new, edittext, tr, co, cn)
-
-        tr.close()
-
     def commit(self, parent, update = None, text = ""):
         tr = self.transaction()
         
         try:
             remove = [ l[:-1] for l in self.opener("to-remove") ]
             os.unlink(self.join("to-remove"))
 
         except IOError:
             remove = []
 
         if update == None:
             update = self.diffdir(self.root, parent)[0]
 
         # check in files
         new = {}
         linkrev = self.changelog.count()
         for f in update:
             self.ui.note(f + "\n")
             try:
                 t = file(f).read()
             except IOError:
                 remove.append(f)
                 continue
             r = self.file(f)
             new[f] = r.add(t, tr, linkrev)
 
         # update manifest
         mmap = self.manifest.read(self.manifest.tip())
         mmap.update(new)
         for f in remove:
             del mmap[f]
         mnode = self.manifest.add(mmap, tr, linkrev)
 
         # add changeset
         new = new.keys()
         new.sort()
 
         edittext = text + "\n"+"".join(["HG: changed %s\n" % f for f in new])
         edittext += "".join(["HG: removed %s\n" % f for f in remove])
         edittext = self.ui.edit(edittext)
 
         n = self.changelog.add(mnode, new, edittext, tr)
         tr.close()
 
         self.setcurrent(n)
         self.dircache.update(new)
         self.dircache.remove(remove)
 
     def checkdir(self, path):
         d = os.path.dirname(path)
         if not d: return
         if not os.path.isdir(d):
             self.checkdir(d)
             os.mkdir(d)
 
     def checkout(self, node):
         # checkout is really dumb at the moment
         # it ought to basically merge
         change = self.changelog.read(node)
         mmap = self.manifest.read(change[0])
 
         l = mmap.keys()
         l.sort()
         stats = []
         for f in l:
             self.ui.note(f + "\n")
             r = self.file(f)
             t = r.revision(mmap[f])
             try:
                 file(f, "w").write(t)
             except:
                 self.checkdir(f)
                 file(f, "w").write(t)
 
         self.setcurrent(node)
         self.dircache.clear()
         self.dircache.update(l)
 
     def diffdir(self, path, changeset):
         changed = []
         mf = {}
         added = []
 
         if changeset:
             change = self.changelog.read(changeset)
             mf = self.manifest.read(change[0])
 
         if changeset == self.current:
             dc = self.dircache.copy()
         else:
             dc = dict.fromkeys(mf)
 
         def fcmp(fn):
             t1 = file(os.path.join(self.root, fn)).read()
             t2 = self.file(fn).revision(mf[fn])
             return cmp(t1, t2)
 
         for dir, subdirs, files in os.walk(self.root):
             d = dir[len(self.root)+1:]
             if ".hg" in subdirs: subdirs.remove(".hg")
             
             for f in files:
                 fn = os.path.join(d, f)
                 try: s = os.stat(os.path.join(self.root, fn))
                 except: continue
                 if fn in dc:
                     c = dc[fn]
                     del dc[fn]
                     if not c:
                         if fcmp(fn):
                             changed.append(fn)
                     elif c[1] != s.st_size:
                         changed.append(fn)
                     elif c[0] != s.st_mode or c[2] != s.st_mtime:
                         if fcmp(fn):
                             changed.append(fn)
                 else:
                     if self.ignore(fn): continue
                     added.append(fn)
 
         deleted = dc.keys()
         deleted.sort()
 
         return (changed, added, deleted)
 
     def diffrevs(self, node1, node2):
         changed, added = [], []
 
         change = self.changelog.read(node1)
         mf1 = self.manifest.read(change[0])
         change = self.changelog.read(node2)
         mf2 = self.manifest.read(change[0])
 
         for fn in mf2:
             if mf1.has_key(fn):
                 if mf1[fn] != mf2[fn]:
                     changed.append(fn)
                 del mf1[fn]
             else:
                 added.append(fn)
                 
         deleted = mf1.keys()
         deleted.sort()
     
         return (changed, added, deleted)
 
     def add(self, list):
         self.dircache.taint(list)
 
     def remove(self, list):
         dl = self.opener("to-remove", "a")
         for f in list:
             dl.write(f + "\n")
 
     def branches(self, nodes):
         if not nodes: nodes = [self.changelog.tip()]
         b = []
         for n in nodes:
             t = n
             while n:
                 p = self.changelog.parents(n)
                 if p[1] != nullid or p[0] == nullid:
                     b.append((t, n, p[0], p[1]))
                     break
                 n = p[0]
         return b
 
     def between(self, pairs):
         r = []
 
         for top, bottom in pairs:
             n, l, i = top, [], 0
             f = 1
 
             while n != bottom:
                 p = self.changelog.parents(n)[0]
                 if i == f:
                     l.append(n) 
                     f = f * 2
                 n = p
                 i += 1
 
             r.append(l)
 
         return r
 
     def newer(self, nodes):
         m = {}
         nl = []
+        pm = {}
         cl = self.changelog
         t = l = cl.count()
+
+        # find the lowest numbered node
         for n in nodes:
             l = min(l, cl.rev(n))
-            for p in cl.parents(n):
-                m[p] = 1
+            m[n] = 1
 
         for i in xrange(l, t):
             n = cl.node(i)
+            if n in m: # explicitly listed
+                pm[n] = 1
+                nl.append(n)
+                continue
             for p in cl.parents(n):
-                if p in m and n not in m:
-                    m[n] = 1
+                if p in pm: # parent listed
+                    pm[n] = 1
                     nl.append(n)
+                    break
 
         return nl
 
     def getchangegroup(self, remote):
         tip = remote.branches([])[0]
         self.ui.debug("remote tip branch is %s:%s\n" %
                       (short(tip[0]), short(tip[1])))
         m = self.changelog.nodemap
         unknown = [tip]
         search = []
         fetch = []
 
         if tip[0] in m:
             self.ui.note("nothing to do!\n")
             return None
 
         while unknown:
             n = unknown.pop(0)
             if n == nullid: break
             if n[1] and n[1] in m: # do we know the base?
                 self.ui.debug("found incomplete branch %s\n" % short(n[1]))
                 search.append(n) # schedule branch range for scanning
             else:
+                if n[2] in m and n[3] in m:
+                    if n[1] not in fetch:
+                        self.ui.debug("found new changeset %s\n" %
+                                      short(n[1]))
+                        fetch.append(n[1]) # earliest unknown
+                        continue
                 for b in remote.branches([n[2], n[3]]):
-                    if b[0] in m:
-                        if n[1] not in fetch:
-                            self.ui.debug("found new changeset %s\n" %
-                                          short(n[1]))
-                            fetch.append(n[1]) # earliest unknown
-                    else:
+                    if b[0] not in m:
                         unknown.append(b)
   
         while search:
             n = search.pop(0)
             l = remote.between([(n[0], n[1])])[0]
             p = n[0]
             f = 1
             for i in l + [n[1]]:
                 if i in m:
                     if f <= 2:
                         self.ui.debug("found new branch changeset %s\n" %
                                           short(p))
                         fetch.append(p)
                     else:
                         self.ui.debug("narrowed branch search to %s:%s\n"
                                       % (short(p), short(i)))
                         search.append((p, i))
                     break
                 p, f = i, f * 2
 
         for f in fetch:
             if f in m:
                 raise "already have", short(f[:4])
 
-        self.ui.note("merging new changesets starting at " +
+        self.ui.note("adding new changesets starting at " +
                      " ".join([short(f) for f in fetch]) + "\n")
 
         return remote.changegroup(fetch)
     
     def changegroup(self, basenodes):
         nodes = self.newer(basenodes)
 
         # construct the link map
         linkmap = {}
         for n in nodes:
             linkmap[self.changelog.rev(n)] = n
 
         # construct a list of all changed files
         changed = {}
         for n in nodes:
             c = self.changelog.read(n)
             for f in c[3]:
                 changed[f] = 1
         changed = changed.keys()
         changed.sort()
 
         # the changegroup is changesets + manifests + all file revs
         revs = [ self.changelog.rev(n) for n in nodes ]
 
         yield self.changelog.group(linkmap)
         yield self.manifest.group(linkmap)
 
         for f in changed:
             g = self.file(f).group(linkmap)
             if not g: raise "couldn't find change to %s" % f
             l = struct.pack(">l", len(f))
             yield "".join([l, f, g])
 
     def addchangegroup(self, generator):
         class genread:
             def __init__(self, generator):
                 self.g = generator
                 self.buf = ""
             def read(self, l):
                 while l > len(self.buf):
                     try:
                         self.buf += self.g.next()
                     except StopIteration:
                         break
                 d, self.buf = self.buf[:l], self.buf[l:]
                 return d
                 
         if not generator: return
         source = genread(generator)
 
         def getchunk(add = 0):
             d = source.read(4)
             if not d: return ""
             l = struct.unpack(">l", d)[0]
             return source.read(l - 4 + add)
 
         tr = self.transaction()
         simple = True
 
-        self.ui.status("merging changesets\n")
+        self.ui.status("adding changesets\n")
         # pull off the changeset group
+        def report(x):
+            self.ui.debug("add changeset %s\n" % short(x))
+            return self.changelog.count()
+            
         csg = getchunk()
         co = self.changelog.tip()
-        cn = self.changelog.addgroup(csg, lambda x: self.changelog.count(), tr)
+        cn = self.changelog.addgroup(csg, report, tr)
 
-        self.ui.status("merging manifests\n")
+        self.ui.status("adding manifests\n")
         # pull off the manifest group
         mfg = getchunk()
         mm = self.manifest.tip()
         mo = self.manifest.addgroup(mfg, lambda x: self.changelog.rev(x), tr)
 
         # do we need a resolve?
         if self.changelog.ancestor(co, cn) != co:
             simple = False
             resolverev = self.changelog.count()
 
         # process the files
-        self.ui.status("merging files\n")
+        self.ui.status("adding files\n")
         new = {}
         while 1:
             f = getchunk(4)
             if not f: break
             fg = getchunk()
-
+            self.ui.debug("adding %s revisions\n" % f)
             fl = self.file(f)
             o = fl.tip()
             n = fl.addgroup(fg, lambda x: self.changelog.rev(x), tr)
             if not simple:
-                nn = fl.resolvedag(o, n, tr, resolverev)
-                if nn:
-                    self.ui.note("merged %s\n", f)
-                    new[f] = nn
+                if o == n: continue
+                # this file has changed between branches, so it must be
+                # represented in the merge changeset
+                new[f] = self.merge3(fl, f, o, n, tr, resolverev)
 
         # For simple merges, we don't need to resolve manifests or changesets
         if simple:
             self.ui.debug("simple merge, skipping resolve\n")
             tr.close()
             return
 
         # resolve the manifest to point to all the merged files
         self.ui.status("resolving manifests\n")
         ma = self.manifest.ancestor(mm, mo)
         omap = self.manifest.read(mo) # other
         amap = self.manifest.read(ma) # ancestor
         mmap = self.manifest.read(mm) # mine
         self.ui.debug("ancestor %s local %s other %s\n" %
                       (short(ma), short(mm), short(mo)))
         nmap = {}
 
         for f, mid in mmap.iteritems():
             if f in omap:
                 if mid != omap[f]:
                     self.ui.debug("%s versions differ\n" % f)
-                    if f in new: self.ui.note("%s updated in resolve\n" % f)
-                    nmap[f] = new.get(f, mid) # use merged version
+                    if f in new: self.ui.debug("%s updated in resolve\n" % f)
+                    # use merged version or local version
+                    nmap[f] = new.get(f, mid)
                 else:
                     nmap[f] = mid # keep ours
                 del omap[f]
             elif f in amap:
                 if mid != amap[f]:
                     self.ui.debug("local changed %s which other deleted\n" % f)
                     pass # we should prompt here
                 else:
                     self.ui.debug("other deleted %s\n" % f)
                     pass # other deleted it
             else:
                 self.ui.debug("local created %s\n" %f)
                 nmap[f] = mid # we created it
                 
         del mmap
 
         for f, oid in omap.iteritems():
             if f in amap:
                 if oid != amap[f]:
                     self.ui.debug("other changed %s which we deleted\n" % f)
                     pass # this is the nasty case, we should prompt
                 else:
                     pass # probably safe
             else:
                 self.ui.debug("remote created %s\n" % f)
                 nmap[f] = new.get(f, oid) # remote created it
 
         del omap
         del amap
 
         node = self.manifest.add(nmap, tr, resolverev, mm, mo)
 
         # Now all files and manifests are merged, we add the changed files
         # and manifest id to the changelog
         self.ui.status("committing merge changeset\n")
         new = new.keys()
         new.sort()
         if co == cn: cn = -1
 
         edittext = "\nHG: merge resolve\n" + \
                    "".join(["HG: changed %s\n" % f for f in new])
         edittext = self.ui.edit(edittext)
         n = self.changelog.add(node, new, edittext, tr, co, cn)
 
         tr.close()
 
 class remoterepository:
     def __init__(self, ui, path):
         self.url = path.replace("hg://", "http://", 1)
         self.ui = ui
 
     def do_cmd(self, cmd, **args):
         self.ui.debug("sending %s command\n" % cmd)
         q = {"cmd": cmd}
         q.update(args)
         qs = urllib.urlencode(q)
         cu = "%s?%s" % (self.url, qs)
         return urllib.urlopen(cu)
 
     def branches(self, nodes):
         n = " ".join(map(hex, nodes))
         d = self.do_cmd("branches", nodes=n).read()
         br = [ map(bin, b.split(" ")) for b in d.splitlines() ]
         return br
 
     def between(self, pairs):
         n = "\n".join(["-".join(map(hex, p)) for p in pairs])
         d = self.do_cmd("between", pairs=n).read()
         p = [ map(bin, l.split(" ")) for l in d.splitlines() ]
         return p
 
     def changegroup(self, nodes):
         n = " ".join(map(hex, nodes))
         zd = zlib.decompressobj()
         f = self.do_cmd("changegroup", roots=n)
         while 1:
             d = f.read(4096)
             if not d:
                 yield zd.flush()
                 break
             yield zd.decompress(d)
 
 def repository(ui, path=None, create=0):
     if path and path[:5] == "hg://":
         return remoterepository(ui, path)
     else:
         return localrepository(ui, path, create)
 
 class ui:
     def __init__(self, verbose=False, debug=False, quiet=False):
         self.quiet = quiet and not verbose and not debug
         self.verbose = verbose or debug
         self.debugflag = debug
     def write(self, *args):
         for a in args:
             sys.stdout.write(str(a))
     def prompt(self, msg, pat):
         while 1:
             sys.stdout.write(msg)
             r = sys.stdin.readline()[:-1]
             if re.match(pat, r):
                 return r
     def status(self, *msg):
         if not self.quiet: self.write(*msg)
     def warn(self, msg):
         self.write(*msg)
     def note(self, msg):
         if self.verbose: self.write(*msg)
     def debug(self, msg):
         if self.debugflag: self.write(*msg)
     def edit(self, text):
         (fd, name) = tempfile.mkstemp("hg")
         f = os.fdopen(fd, "w")
         f.write(text)
         f.close()
 
         editor = os.environ.get("EDITOR", "vi")
         r = os.system("%s %s" % (editor, name))
         if r:
             raise "Edit failed!"
 
         t = open(name).read()
         t = re.sub("(?m)^HG:.*\n", "", t)
 
         return t
 
     
 class httprangereader:
     def __init__(self, url):
         self.url = url
         self.pos = 0
     def seek(self, pos):
         self.pos = pos
     def read(self, bytes=None):
         opener = urllib2.build_opener(byterange.HTTPRangeHandler())
         urllib2.install_opener(opener)
         req = urllib2.Request(self.url)
         end = ''
         if bytes: end = self.pos + bytes
         req.add_header('Range', 'bytes=%d-%s' % (self.pos, end))
         f = urllib2.urlopen(req)
         return f.read()

mercurial/revlog.py

@@ -1,481 +1,450 b''
 # revlog.py - storage back-end for mercurial
 #
 # This provides efficient delta storage with O(1) retrieve and append
 # and O(changes) merge between branches
 #
 # Copyright 2005 Matt Mackall <[e-mail]>
 #
 # This software may be used and distributed according to the terms
 # of the GNU General Public License, incorporated herein by reference.
 
 import zlib, struct, sha, os, tempfile, binascii
 from mercurial import mdiff
 
 def hex(node): return binascii.hexlify(node)
 def bin(node): return binascii.unhexlify(node)
 def short(node): return hex(node[:4])
 
 def compress(text):
     return zlib.compress(text)
 
 def decompress(bin):
     return zlib.decompress(bin)
 
 def hash(text, p1, p2):
     l = [p1, p2]
     l.sort()
     return sha.sha(l[0] + l[1] + text).digest()
 
 nullid = "\0" * 20
 indexformat = ">4l20s20s20s"
 
 class lazyparser:
     def __init__(self, data):
         self.data = data
         self.s = struct.calcsize(indexformat)
         self.l = len(data)/self.s
         self.index = [None] * self.l
         self.map = {nullid: -1}
 
         if 0:
             n = 0
             i = self.data
             s = struct.calcsize(indexformat)
             for f in xrange(0, len(i), s):
                 # offset, size, base, linkrev, p1, p2, nodeid
                 e = struct.unpack(indexformat, i[f:f + s])
                 self.map[e[6]] = n
                 self.index.append(e)
                 n += 1
 
     def load(self, pos):
         block = pos / 1000
         i = block * 1000
         end = min(self.l, i + 1000)
         while i < end:
             d = self.data[i * self.s: (i + 1) * self.s]
             e = struct.unpack(indexformat, d)
             self.index[i] = e
             self.map[e[6]] = i
             i += 1
         
 class lazyindex:
     def __init__(self, parser):
         self.p = parser
     def __len__(self):
         return len(self.p.index)
     def __getitem__(self, pos):
         i = self.p.index[pos]
         if not i:
             self.p.load(pos)
             return self.p.index[pos]
         return i
     def append(self, e):
         self.p.index.append(e)
         
 class lazymap:
     def __init__(self, parser):
         self.p = parser
     def load(self, key):
         n = self.p.data.find(key)
         if n < 0: raise KeyError("node " + hex(key))
         pos = n / self.p.s
         self.p.load(pos)
     def __contains__(self, key):
         try:
             self[key]
             return True
         except KeyError:
             return False
     def __getitem__(self, key):
         try:
             return self.p.map[key]
         except KeyError:
             try:
                 self.load(key)
                 return self.p.map[key]
             except KeyError:
                 raise KeyError("node " + hex(key))
     def __setitem__(self, key, val):
         self.p.map[key] = val
 
 class revlog:
     def __init__(self, opener, indexfile, datafile):
         self.indexfile = indexfile
         self.datafile = datafile
         self.opener = opener
         self.cache = None
         # read the whole index for now, handle on-demand later
         try:
             i = self.opener(self.indexfile).read()
         except IOError:
             i = ""
         parser = lazyparser(i)
         self.index = lazyindex(parser)
         self.nodemap = lazymap(parser)
 
     def tip(self): return self.node(len(self.index) - 1)
     def count(self): return len(self.index)
     def node(self, rev): return (rev < 0) and nullid or self.index[rev][6]
     def rev(self, node): return self.nodemap[node]
     def linkrev(self, node): return self.index[self.nodemap[node]][3]
     def parents(self, node):
         if node == nullid: return (nullid, nullid)
         return self.index[self.nodemap[node]][4:6]
 
     def start(self, rev): return self.index[rev][0]
     def length(self, rev): return self.index[rev][1]
     def end(self, rev): return self.start(rev) + self.length(rev)
     def base(self, rev): return self.index[rev][2]
 
     def lookup(self, id):
         try:
             rev = int(id)
             return self.node(rev)
         except ValueError:
             c = []
             for n in self.nodemap:
                 if id in hex(n):
                     c.append(n)
             if len(c) > 1: raise KeyError("Ambiguous identifier")
             if len(c) < 1: raise KeyError("No match found")
             return c[0]
                 
         return None
 
-    def revisions(self, list):
-        # this can be optimized to do spans, etc
-        # be stupid for now
-        for node in list:
-            yield self.revision(node)
-
     def diff(self, a, b):
         return mdiff.textdiff(a, b)
 
     def patches(self, t, pl):
         return mdiff.patches(t, pl)
 
     def revision(self, node):
         if node == nullid: return ""
         if self.cache and self.cache[0] == node: return self.cache[2]
 
         text = None
         rev = self.rev(node)
         base = self.base(rev)
         start = self.start(base)
         end = self.end(rev)
 
         if self.cache and self.cache[1] >= base and self.cache[1] < rev:
             base = self.cache[1]
             start = self.start(base + 1)
             text = self.cache[2]
             last = 0
 
         f = self.opener(self.datafile)
         f.seek(start)
         data = f.read(end - start)
 
         if not text:
             last = self.length(base)
             text = decompress(data[:last])
 
         bins = []
         for r in xrange(base + 1, rev + 1):
             s = self.length(r)
             bins.append(decompress(data[last:last + s]))
             last = last + s
 
         text = mdiff.patches(text, bins)
 
         (p1, p2) = self.parents(node)
         if node != hash(text, p1, p2):
             raise "integrity check failed on %s:%d" % (self.datafile, rev)
 
         self.cache = (node, rev, text)
         return text  
 
     def addrevision(self, text, transaction, link, p1=None, p2=None):
         if text is None: text = ""
         if p1 is None: p1 = self.tip()
         if p2 is None: p2 = nullid
 
         node = hash(text, p1, p2)
 
         n = self.count()
         t = n - 1
 
         if n:
             base = self.base(t)
             start = self.start(base)
             end = self.end(t)
             prev = self.revision(self.tip())
             data = compress(self.diff(prev, text))
             dist = end - start + len(data)
 
         # full versions are inserted when the needed deltas
         # become comparable to the uncompressed text
         if not n or dist > len(text) * 2:
             data = compress(text)
             base = n
         else:
             base = self.base(t)
 
         offset = 0
         if t >= 0:
             offset = self.end(t)
 
         e = (offset, len(data), base, link, p1, p2, node)
         
         self.index.append(e)
         self.nodemap[node] = n
         entry = struct.pack(indexformat, *e)
 
         transaction.add(self.datafile, e[0])
         self.opener(self.datafile, "a").write(data)
         transaction.add(self.indexfile, n * len(entry))
         self.opener(self.indexfile, "a").write(entry)
 
         self.cache = (node, n, text)
         return node
 
     def ancestor(self, a, b):
         def expand(list, map):
             a = []
             while list:
                 n = list.pop(0)
                 map[n] = 1
                 yield n
                 for p in self.parents(n):
                     if p != nullid and p not in map:
                         list.append(p)
             yield nullid
 
         amap = {}
         bmap = {}
         ag = expand([a], amap)
         bg = expand([b], bmap)
         adone = bdone = 0
 
         while not adone or not bdone:
             if not adone:
                 an = ag.next()
                 if an == nullid:
                     adone = 1
                 elif an in bmap:
                     return an
             if not bdone:
                 bn = bg.next()
                 if bn == nullid:
                     bdone = 1
                 elif bn in amap:
                     return bn
 
         return nullid
 
-    def mergedag(self, other, transaction, linkseq, accumulate = None):
-        """combine the nodes from other's DAG into ours"""
-        old = self.tip()
-        i = self.count()
-        l = []
-
-        # merge the other revision log into our DAG
-        for r in range(other.count()):
-            id = other.node(r)
-            if id not in self.nodemap:
-                (xn, yn) = other.parents(id)
-                l.append((id, xn, yn))
-                self.nodemap[id] = i
-                i += 1
-
-        # merge node date for new nodes
-        r = other.revisions([e[0] for e in l])
-        for e in l:
-            t = r.next()
-            if accumulate: accumulate(t)
-            self.addrevision(t, transaction, linkseq.next(), e[1], e[2])
-
-        # return the unmerged heads for later resolving
-        return (old, self.tip())
-
     def group(self, linkmap):
         # given a list of changeset revs, return a set of deltas and
-        # metadata corresponding to nodes the first delta is
+        # metadata corresponding to nodes. the first delta is
         # parent(nodes[0]) -> nodes[0] the receiver is guaranteed to
         # have this parent as it has all history before these
         # changesets. parent is parent[0]
 
         revs = []
         needed = {}
 
         # find file nodes/revs that match changeset revs
         for i in xrange(0, self.count()):
             if self.index[i][3] in linkmap:
                 revs.append(i)
                 needed[i] = 1
 
         # if we don't have any revisions touched by these changesets, bail
         if not revs: return struct.pack(">l", 0)
 
         # add the parent of the first rev
         p = self.parents(self.node(revs[0]))[0]
         revs.insert(0, self.rev(p))
 
         # for each delta that isn't contiguous in the log, we need to
         # reconstruct the base, reconstruct the result, and then
         # calculate the delta. We also need to do this where we've
         # stored a full version and not a delta
         for i in xrange(0, len(revs) - 1):
             a, b = revs[i], revs[i + 1]
             if a + 1 != b or self.base(b) == b:
                 for j in xrange(self.base(a), a + 1):
                     needed[j] = 1
                 for j in xrange(self.base(b), b + 1):
                     needed[j] = 1
 
         # calculate spans to retrieve from datafile
         needed = needed.keys()
         needed.sort()
         spans = []
         for n in needed:
             if n < 0: continue
             o = self.start(n)
             l = self.length(n)
             spans.append((o, l, [(n, l)]))
 
         # merge spans
         merge = [spans.pop(0)]
         while spans:
             e = spans.pop(0)
             f = merge[-1]
             if e[0] == f[0] + f[1]:
                 merge[-1] = (f[0], f[1] + e[1], f[2] + e[2])
             else:
                 merge.append(e)
 
         # read spans in, divide up chunks
         chunks = {}
         for span in merge:
             # we reopen the file for each span to make http happy for now
             f = self.opener(self.datafile)
             f.seek(span[0])
             data = f.read(span[1])
 
             # divide up the span
             pos = 0
             for r, l in span[2]:
                 chunks[r] = data[pos: pos + l]
                 pos += l
 
         # helper to reconstruct intermediate versions
         def construct(text, base, rev):
             bins = [decompress(chunks[r]) for r in xrange(base + 1, rev + 1)]
             return mdiff.patches(text, bins)
 
         # build deltas
         deltas = []
         for d in xrange(0, len(revs) - 1):
             a, b = revs[d], revs[d + 1]
             n = self.node(b)
             
             if a + 1 != b or self.base(b) == b:
                 if a >= 0:
                     base = self.base(a)
                     ta = decompress(chunks[self.base(a)])
                     ta = construct(ta, base, a)
                 else:
                     ta = ""
                     
                 base = self.base(b)
                 if a > base:
                     base = a
                     tb = ta
                 else:
                     tb = decompress(chunks[self.base(b)])
                 tb = construct(tb, base, b)
                 d = self.diff(ta, tb)
             else:
                 d = decompress(chunks[b])
 
             p = self.parents(n)
             meta = n + p[0] + p[1] + linkmap[self.linkrev(n)]
             l = struct.pack(">l", len(meta) + len(d) + 4)
             deltas.append(l + meta + d)
 
         l = struct.pack(">l", sum(map(len, deltas)) + 4)
         deltas.insert(0, l)
         return "".join(deltas)
         
     def addgroup(self, data, linkmapper, transaction):
         # given a set of deltas, add them to the revision log. the
         # first delta is against its parent, which should be in our
         # log, the rest are against the previous delta.
 
         if not data: return self.tip()
 
         # retrieve the parent revision of the delta chain
         chain = data[24:44]
         if not chain in self.nodemap:
             raise "unknown base %s" % short(chain[:4])
 
         # track the base of the current delta log
         r = self.count()
         t = r - 1
         
         base = prev = -1
         start = end = 0
         if r:
             start = self.start(self.base(t))
             end = self.end(t)
             measure = self.length(self.base(t))
             base = self.base(t)
             prev = self.tip()
 
         transaction.add(self.datafile, end)
         transaction.add(self.indexfile, r * struct.calcsize(indexformat))
         dfh = self.opener(self.datafile, "a")
         ifh = self.opener(self.indexfile, "a")
 
         # loop through our set of deltas
         pos = 0
         while pos < len(data):
             l, node, p1, p2, cs = struct.unpack(">l20s20s20s20s",
                                                 data[pos:pos+84])
+            link = linkmapper(cs)
             if node in self.nodemap:
                 raise "already have %s" % hex(node[:4])
-            link = linkmapper(cs)
             delta = data[pos + 84:pos + l]
             pos += l
 
             # full versions are inserted when the needed deltas become
             # comparable to the uncompressed text or when the previous
             # version is not the one we have a delta against. We use
             # the size of the previous full rev as a proxy for the
             # current size.
 
             if chain == prev:
                 cdelta = compress(delta)
 
             if chain != prev or (end - start + len(cdelta)) > measure * 2:
                 # flush our writes here so we can read it in revision
                 dfh.flush()
                 ifh.flush()
                 text = self.revision(chain)
                 text = self.patches(text, [delta])
                 chk = self.addrevision(text, transaction, link, p1, p2)
                 if chk != node:
                     raise "consistency error adding group"
                 measure = len(text)
             else:
                 e = (end, len(cdelta), self.base(t), link, p1, p2, node)
                 self.index.append(e)
                 self.nodemap[node] = r
                 dfh.write(cdelta)
                 ifh.write(struct.pack(indexformat, *e))
 
             t, r, chain, prev = r, r + 1, node, node
             start = self.start(self.base(t))
             end = self.end(t)
 
         dfh.close()
         ifh.close()
         return node