--- a/mercurial/bdiff.c Thu Oct 04 14:26:34 2007 +0200
+++ b/mercurial/bdiff.c Thu Oct 04 19:47:22 2007 -0500
@@ -12,6 +12,7 @@
#include <Python.h>
#include <stdlib.h>
#include <string.h>
+#include <limits.h>
#if defined __hpux || defined __SUNPRO_C || defined _AIX
# define inline
@@ -58,21 +59,17 @@
struct hunk *base, *head;
};
-static inline uint32_t rol32(uint32_t word, unsigned int shift)
-{
- return (word << shift) | (word >> (32 - shift));
-}
-
int splitlines(const char *a, int len, struct line **lr)
{
- int g, h, i;
+ int h, i;
const char *p, *b = a;
+ const char * const plast = a + len - 1;
struct line *l;
/* count the lines */
i = 1; /* extra line for sentinel */
for (p = a; p < a + len; p++)
- if (*p == '\n' || p == a + len - 1)
+ if (*p == '\n' || p == plast)
i++;
*lr = l = (struct line *)malloc(sizeof(struct line) * i);
@@ -82,24 +79,17 @@
/* build the line array and calculate hashes */
h = 0;
for (p = a; p < a + len; p++) {
- /*
- * a simple hash from GNU diff, with better collision
- * resistance from hashpjw. this slows down common
- * case by 10%, but speeds up worst case by 100x.
- */
- h = *p + rol32(h, 7);
- if ((g = h & 0xf0000000)) {
- h ^= g >> 24;
- h ^= g;
- }
- if (*p == '\n' || p == a + len - 1) {
+ /* Leonid Yuriev's hash */
+ h = (h * 1664525) + *p + 1013904223;
+
+ if (*p == '\n' || p == plast) {
+ l->h = h;
+ h = 0;
l->len = p - b + 1;
- l->h = h * l->len;
l->l = b;
- l->n = -1;
+ l->n = INT_MAX;
l++;
b = p + 1;
- h = 0;
}
}
@@ -117,27 +107,34 @@
static int equatelines(struct line *a, int an, struct line *b, int bn)
{
int i, j, buckets = 1, t;
+ int scale = 32;
struct pos *h;
/* build a hash table of the next highest power of 2 */
while (buckets < bn + 1)
buckets *= 2;
- h = (struct pos *)malloc(buckets * sizeof(struct pos));
- buckets = buckets - 1;
+ /* try to allocate a large hash table to avoid collisions */
+ do {
+ scale /= 2;
+ h = (struct pos *)malloc(scale * buckets * sizeof(struct pos));
+ } while (!h && scale != 1);
+
if (!h)
return 0;
+ buckets = buckets * scale - 1;
+
/* clear the hash table */
for (i = 0; i <= buckets; i++) {
- h[i].pos = -1;
+ h[i].pos = INT_MAX;
h[i].len = 0;
}
/* add lines to the hash table chains */
for (i = bn - 1; i >= 0; i--) {
/* find the equivalence class */
- for (j = b[i].h & buckets; h[j].pos != -1;
+ for (j = b[i].h & buckets; h[j].pos != INT_MAX;
j = (j + 1) & buckets)
if (!cmp(b + i, b + h[j].pos))
break;
@@ -155,7 +152,7 @@
/* match items in a to their equivalence class in b */
for (i = 0; i < an; i++) {
/* find the equivalence class */
- for (j = a[i].h & buckets; h[j].pos != -1;
+ for (j = a[i].h & buckets; h[j].pos != INT_MAX;
j = (j + 1) & buckets)
if (!cmp(a + i, b + h[j].pos))
break;
@@ -164,7 +161,7 @@
if (h[j].len <= t)
a[i].n = h[j].pos; /* point to head of match list */
else
- a[i].n = -1; /* too popular */
+ a[i].n = INT_MAX; /* too popular */
}
/* discard hash tables */
@@ -179,11 +176,11 @@
for (i = a1; i < a2; i++) {
/* skip things before the current block */
- for (j = a[i].n; j != -1 && j < b1; j = b[j].n)
+ for (j = a[i].n; j < b1; j = b[j].n)
;
/* loop through all lines match a[i] in b */
- for (; j != -1 && j < b2; j = b[j].n) {
+ for (; j < b2; j = b[j].n) {
/* does this extend an earlier match? */
if (i > a1 && j > b1 && pos[j - 1].pos == i - 1)
k = pos[j - 1].len + 1;
@@ -216,6 +213,7 @@
*omi = mi - mb;
*omj = mj - mb;
+
return mk + mb;
}
--- a/mercurial/changegroup.py Thu Oct 04 14:26:34 2007 +0200
+++ b/mercurial/changegroup.py Thu Oct 04 19:47:22 2007 -0500
@@ -33,10 +33,9 @@
break
yield c
-def genchunk(data):
- """build a changegroup chunk"""
- header = struct.pack(">l", len(data)+ 4)
- return "%s%s" % (header, data)
+def chunkheader(length):
+ """build a changegroup chunk header"""
+ return struct.pack(">l", length + 4)
def closechunk():
return struct.pack(">l", 0)
@@ -86,7 +85,12 @@
empty = True
for chunk in chunkiter(cg):
empty = False
- fh.write(z.compress(genchunk(chunk)))
+ fh.write(z.compress(chunkheader(len(chunk))))
+ pos = 0
+ while pos < len(chunk):
+ next = pos + 2**20
+ fh.write(z.compress(chunk[pos:next]))
+ pos = next
fh.write(z.compress(closechunk()))
fh.write(z.flush())
cleanup = None
--- a/mercurial/localrepo.py Thu Oct 04 14:26:34 2007 +0200
+++ b/mercurial/localrepo.py Thu Oct 04 19:47:22 2007 -0500
@@ -1720,7 +1720,8 @@
# If any filenodes are left, generate the group for them,
# otherwise don't bother.
if len(msng_filenode_lst) > 0:
- yield changegroup.genchunk(fname)
+ yield changegroup.chunkheader(len(fname))
+ yield fname
# Sort the filenodes by their revision #
msng_filenode_lst.sort(cmp_by_rev_func(filerevlog))
# Create a group generator and only pass in a changenode
@@ -1796,7 +1797,8 @@
nodeiter = gennodelst(filerevlog)
nodeiter = list(nodeiter)
if nodeiter:
- yield changegroup.genchunk(fname)
+ yield changegroup.chunkheader(len(fname))
+ yield fname
lookup = lookuprevlink_func(filerevlog)
for chnk in filerevlog.group(nodeiter, lookup):
yield chnk
--- a/mercurial/mdiff.py Thu Oct 04 14:26:34 2007 +0200
+++ b/mercurial/mdiff.py Thu Oct 04 19:47:22 2007 -0500
@@ -245,6 +245,9 @@
def get_matching_blocks(a, b):
return [(d[0], d[2], d[1] - d[0]) for d in bdiff.blocks(a, b)]
+def trivialdiffheader(length):
+ return struct.pack(">lll", 0, 0, length)
+
patches = mpatch.patches
patchedsize = mpatch.patchedsize
textdiff = bdiff.bdiff
--- a/mercurial/merge.py Thu Oct 04 14:26:34 2007 +0200
+++ b/mercurial/merge.py Thu Oct 04 19:47:22 2007 -0500
@@ -188,9 +188,18 @@
if not m1 or not m2 or not ma:
return {}, {}
+ repo.ui.debug(_(" searching for copies back to rev %d\n") % limit)
+
u1 = nonoverlap(m1, m2, ma)
u2 = nonoverlap(m2, m1, ma)
+ if u1:
+ repo.ui.debug(_(" unmatched files in local:\n %s\n")
+ % "\n ".join(u1))
+ if u2:
+ repo.ui.debug(_(" unmatched files in other:\n %s\n")
+ % "\n ".join(u2))
+
for f in u1:
checkcopies(ctx(f, m1[f]), m2, ma)
@@ -204,9 +213,19 @@
fo.remove(f)
d2[f] = (of, fo)
+ if fullcopy:
+ repo.ui.debug(_(" all copies found (* = to merge, ! = divergent):\n"))
+ for f in fullcopy:
+ note = ""
+ if f in copy: note += "*"
+ if f in diverge: note += "!"
+ repo.ui.debug(_(" %s -> %s %s\n") % (f, fullcopy[f], note))
+
if not fullcopy or not repo.ui.configbool("merge", "followdirs", True):
return copy, diverge
+ repo.ui.debug(_(" checking for directory renames\n"))
+
# generate a directory move map
d1, d2 = dirs(m1), dirs(m2)
invalid = {}
@@ -241,6 +260,9 @@
if not dirmove:
return copy, diverge
+ for d in dirmove:
+ repo.ui.debug(_(" dir %s -> %s\n") % (d, dirmove[d]))
+
# check unaccounted nonoverlapping files against directory moves
for f in u1 + u2:
if f not in fullcopy:
@@ -248,6 +270,7 @@
if f.startswith(d):
# new file added in a directory that was moved, move it
copy[f] = dirmove[d] + f[len(d):]
+ repo.ui.debug(_(" file %s -> %s\n") % (f, copy[f]))
break
return copy, diverge
--- a/mercurial/revlog.py Thu Oct 04 14:26:34 2007 +0200
+++ b/mercurial/revlog.py Thu Oct 04 19:47:22 2007 -0500
@@ -1087,10 +1087,16 @@
if infocollect is not None:
infocollect(nb)
- d = self.revdiff(a, b)
p = self.parents(nb)
meta = nb + p[0] + p[1] + lookup(nb)
- yield changegroup.genchunk("%s%s" % (meta, d))
+ if a == -1:
+ d = self.revision(nb)
+ meta += mdiff.trivialdiffheader(len(d))
+ else:
+ d = self.revdiff(a, b)
+ yield changegroup.chunkheader(len(meta) + len(d))
+ yield meta
+ yield d
yield changegroup.closechunk()
--- a/tests/test-copy-move-merge.out Thu Oct 04 14:26:34 2007 +0200
+++ b/tests/test-copy-move-merge.out Thu Oct 04 19:47:22 2007 -0500
@@ -2,6 +2,14 @@
resolving manifests
overwrite None partial False
ancestor 583c7b748052 local fb3948d97f07+ remote 40da226db0f0
+ searching for copies back to rev 1
+ unmatched files in other:
+ b
+ c
+ all copies found (* = to merge, ! = divergent):
+ c -> a *
+ b -> a *
+ checking for directory renames
a: remote moved to c -> m
a: remote moved to b -> m
copying a to b
--- a/tests/test-double-merge.out Thu Oct 04 14:26:34 2007 +0200
+++ b/tests/test-double-merge.out Thu Oct 04 19:47:22 2007 -0500
@@ -1,6 +1,12 @@
resolving manifests
overwrite None partial False
ancestor 310fd17130da local 2092631ce82b+ remote 7731dad1c2b9
+ searching for copies back to rev 1
+ unmatched files in other:
+ bar
+ all copies found (* = to merge, ! = divergent):
+ bar -> foo *
+ checking for directory renames
foo: versions differ -> m
foo: remote copied to bar -> m
copying foo to bar
--- a/tests/test-issue522.out Thu Oct 04 14:26:34 2007 +0200
+++ b/tests/test-issue522.out Thu Oct 04 19:47:22 2007 -0500
@@ -4,6 +4,9 @@
resolving manifests
overwrite None partial False
ancestor bbd179dfa0a7 local 71766447bdbb+ remote 4d9e78aaceee
+ searching for copies back to rev 1
+ unmatched files in local:
+ bar
foo: remote is newer -> g
getting foo
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
--- a/tests/test-issue672.out Thu Oct 04 14:26:34 2007 +0200
+++ b/tests/test-issue672.out Thu Oct 04 19:47:22 2007 -0500
@@ -4,6 +4,12 @@
resolving manifests
overwrite None partial False
ancestor 81f4b099af3d local c64f439569a9+ remote 2f8037f47a5c
+ searching for copies back to rev 1
+ unmatched files in other:
+ 1a
+ all copies found (* = to merge, ! = divergent):
+ 1a -> 1
+ checking for directory renames
1: other deleted -> r
1a: remote created -> g
removing 1
@@ -15,6 +21,12 @@
resolving manifests
overwrite None partial False
ancestor c64f439569a9 local ac7575e3c052+ remote 746e9549ea96
+ searching for copies back to rev 1
+ unmatched files in local:
+ 1a
+ all copies found (* = to merge, ! = divergent):
+ 1a -> 1 *
+ checking for directory renames
1a: local moved to 1 -> m
merging 1a and 1
my 1a@ac7575e3c052+ other 1@746e9549ea96 ancestor 1@81f4b099af3d
@@ -24,6 +36,12 @@
resolving manifests
overwrite None partial False
ancestor c64f439569a9 local 746e9549ea96+ remote ac7575e3c052
+ searching for copies back to rev 1
+ unmatched files in other:
+ 1a
+ all copies found (* = to merge, ! = divergent):
+ 1a -> 1 *
+ checking for directory renames
1: remote moved to 1a -> m
copying 1 to 1a
merging 1 and 1a
--- a/tests/test-merge-commit.out Thu Oct 04 14:26:34 2007 +0200
+++ b/tests/test-merge-commit.out Thu Oct 04 19:47:22 2007 -0500
@@ -23,6 +23,7 @@
resolving manifests
overwrite None partial False
ancestor 0a3ab4856510 local 2d2f9a22c82b+ remote 7d3b554bfdf1
+ searching for copies back to rev 1
bar: versions differ -> m
merging bar
my bar@2d2f9a22c82b+ other bar@7d3b554bfdf1 ancestor bar@0a3ab4856510
@@ -68,6 +69,7 @@
resolving manifests
overwrite None partial False
ancestor 0a3ab4856510 local 2d2f9a22c82b+ remote 96ab80c60897
+ searching for copies back to rev 1
bar: versions differ -> m
merging bar
my bar@2d2f9a22c82b+ other bar@96ab80c60897 ancestor bar@0a3ab4856510
--- a/tests/test-merge7.out Thu Oct 04 14:26:34 2007 +0200
+++ b/tests/test-merge7.out Thu Oct 04 19:47:22 2007 -0500
@@ -24,6 +24,7 @@
resolving manifests
overwrite None partial False
ancestor faaea63e63a9 local 451c744aabcc+ remote a070d41e8360
+ searching for copies back to rev 1
test.txt: versions differ -> m
merging test.txt
my test.txt@451c744aabcc+ other test.txt@a070d41e8360 ancestor test.txt@faaea63e63a9
--- a/tests/test-rename-dir-merge.out Thu Oct 04 14:26:34 2007 +0200
+++ b/tests/test-rename-dir-merge.out Thu Oct 04 19:47:22 2007 -0500
@@ -9,6 +9,18 @@
resolving manifests
overwrite None partial False
ancestor f9b20c0d4c51 local ce36d17b18fb+ remote 55119e611c80
+ searching for copies back to rev 1
+ unmatched files in local:
+ a/c
+ unmatched files in other:
+ b/a
+ b/b
+ all copies found (* = to merge, ! = divergent):
+ b/a -> a/a
+ b/b -> a/b
+ checking for directory renames
+ dir a/ -> b/
+ file a/c -> b/c
a/c: remote renamed directory to b/c -> d
a/b: other deleted -> r
a/a: other deleted -> r
@@ -34,6 +46,18 @@
resolving manifests
overwrite None partial False
ancestor f9b20c0d4c51 local 55119e611c80+ remote ce36d17b18fb
+ searching for copies back to rev 1
+ unmatched files in local:
+ b/a
+ b/b
+ unmatched files in other:
+ a/c
+ all copies found (* = to merge, ! = divergent):
+ b/a -> a/a
+ b/b -> a/b
+ checking for directory renames
+ dir a/ -> b/
+ file a/c -> b/c
None: local renamed directory to b/c -> d
getting a/c to b/c
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
--- a/tests/test-rename-merge1.out Thu Oct 04 14:26:34 2007 +0200
+++ b/tests/test-rename-merge1.out Thu Oct 04 19:47:22 2007 -0500
@@ -4,6 +4,17 @@
resolving manifests
overwrite None partial False
ancestor af1939970a1c local f26ec4fc3fa3+ remote 8e765a822af2
+ searching for copies back to rev 1
+ unmatched files in local:
+ c2
+ unmatched files in other:
+ b
+ b2
+ all copies found (* = to merge, ! = divergent):
+ c2 -> a2
+ b -> a *
+ b2 -> a2
+ checking for directory renames
a2: divergent renames -> dr
a: remote moved to b -> m
b2: remote created -> g
--- a/tests/test-up-local-change.out Thu Oct 04 14:26:34 2007 +0200
+++ b/tests/test-up-local-change.out Thu Oct 04 19:47:22 2007 -0500
@@ -17,6 +17,9 @@
resolving manifests
overwrite False partial False
ancestor 33aaa84a386b local 33aaa84a386b+ remote 802f095af299
+ searching for copies back to rev 1
+ unmatched files in other:
+ b
a: versions differ -> m
b: remote created -> g
merging a
@@ -50,6 +53,9 @@
resolving manifests
overwrite False partial False
ancestor 33aaa84a386b local 33aaa84a386b+ remote 802f095af299
+ searching for copies back to rev 1
+ unmatched files in other:
+ b
a: versions differ -> m
b: remote created -> g
merging a
@@ -100,6 +106,7 @@
resolving manifests
overwrite False partial False
ancestor 33aaa84a386b local 802f095af299+ remote 030602aee63d
+ searching for copies back to rev 1
a: versions differ -> m
b: versions differ -> m
merging a