From: Junio C Hamano Date: Sun, 16 Apr 2006 07:52:55 +0000 (-0700) Subject: Merge branch 'lt/logopt' into next X-Git-Tag: v1.4.1-rc1~216 X-Git-Url: https://git.lorimer.id.au/gitweb.git/diff_plain/43f934aa9078b6a82cc43c7d4efc9a048b7fed60?hp=ba1d45051e050cbcf68ccccacea86a4b6ecde731 Merge branch 'lt/logopt' into next * lt/logopt: Tentative built-in "git show" Built-in git-whatchanged. rev-list option parser fix. Split init_revisions() out of setup_revisions() --- diff --git a/.gitignore b/.gitignore index b5959d6311..145f8555ad 100644 --- a/.gitignore +++ b/.gitignore @@ -123,6 +123,7 @@ git-write-tree git-core-*/?* test-date test-delta +test-gsimm common-cmds.h *.tar.gz *.dsc diff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt index 447e522a7b..c183dc9da0 100644 --- a/Documentation/diff-options.txt +++ b/Documentation/diff-options.txt @@ -10,6 +10,9 @@ --stat:: Generate a diffstat instead of a patch. +--patch-with-stat:: + Generate patch and prepend its diffstat. + -z:: \0 line termination on output diff --git a/GIT-VERSION-GEN b/GIT-VERSION-GEN index 656f55542c..e88fe5ae7c 100755 --- a/GIT-VERSION-GEN +++ b/GIT-VERSION-GEN @@ -1,7 +1,7 @@ #!/bin/sh GVF=GIT-VERSION-FILE -DEF_VER=v1.3-rc3.GIT +DEF_VER=v1.3-rc4.GIT # First try git-describe, then see if there is a version file # (included in release tarballs), then default diff --git a/Makefile b/Makefile index 1130af4f38..69ca05b2f9 100644 --- a/Makefile +++ b/Makefile @@ -606,6 +606,9 @@ test-date$X: test-date.c date.o ctype.o test-delta$X: test-delta.c diff-delta.o patch-delta.o $(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) $^ -lz +test-gsimm$X: test-gsimm.c gsimm.o rabinpoly.o + $(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) $^ + check: for i in *.c; do sparse $(ALL_CFLAGS) $(SPARSE_FLAGS) $$i || exit; done @@ -654,6 +657,7 @@ clean: rm -f *.o mozilla-sha1/*.o arm/*.o ppc/*.o compat/*.o xdiff/*.o \ $(LIB_FILE) $(XDIFF_LIB) rm -f $(ALL_PROGRAMS) git$X + rm -f test-date$X test-delta$X test-gsimm$X rm -f *.spec *.pyc *.pyo */*.pyc */*.pyo common-cmds.h TAGS tags rm -rf $(GIT_TARNAME) rm -f $(GIT_TARNAME).tar.gz git-core_$(GIT_VERSION)-*.tar.gz diff --git a/diff.c b/diff.c index f1b672d2dc..b54bbfa627 100644 --- a/diff.c +++ b/diff.c @@ -202,6 +202,8 @@ struct diffstat_t { int alloc; struct diffstat_file { char *name; + unsigned is_unmerged:1; + unsigned is_binary:1; unsigned int added, deleted; } **files; }; @@ -245,11 +247,11 @@ static void show_stats(struct diffstat_t* data) if (data->nr == 0) return; - printf("---\n"); - for (i = 0; i < data->nr; i++) { struct diffstat_file *file = data->files[i]; + if (file->is_binary || file->is_unmerged) + continue; if (max_change < file->added + file->deleted) max_change = file->added + file->deleted; len = strlen(file->name); @@ -294,11 +296,15 @@ static void show_stats(struct diffstat_t* data) if (max + len > 70) max = 70 - len; - if (added < 0) { - /* binary file */ + if (data->files[i]->is_binary) { printf(" %s%-*s | Bin\n", prefix, len, name); goto free_diffstat_file; - } else if (added + deleted == 0) { + } + else if (data->files[i]->is_unmerged) { + printf(" %s%-*s | Unmerged\n", prefix, len, name); + goto free_diffstat_file; + } + else if (added + deleted == 0) { total_files--; goto free_diffstat_file; } @@ -426,11 +432,16 @@ static void builtin_diffstat(const char *name_a, const char *name_b, data = diffstat_add(diffstat, name_a ? name_a : name_b); + if (!one || !two) { + data->is_unmerged = 1; + return; + } + if (fill_mmfile(&mf1, one) < 0 || fill_mmfile(&mf2, two) < 0) die("unable to read files to diff"); if (mmfile_is_binary(&mf1) || mmfile_is_binary(&mf2)) - data->added = -1; + data->is_binary = 1; else { /* Crazy xdl interfaces.. */ xpparam_t xpp; @@ -1049,6 +1060,10 @@ int diff_opt_parse(struct diff_options *options, const char **av, int ac) } else if (!strcmp(arg, "--stat")) options->output_format = DIFF_FORMAT_DIFFSTAT; + else if (!strcmp(arg, "--patch-with-stat")) { + options->output_format = DIFF_FORMAT_PATCH; + options->with_stat = 1; + } else if (!strcmp(arg, "-z")) options->line_termination = 0; else if (!strncmp(arg, "-l", 2)) @@ -1518,7 +1533,7 @@ void diff_flush(struct diff_options *options) int diff_output_format = options->output_format; struct diffstat_t *diffstat = NULL; - if (diff_output_format == DIFF_FORMAT_DIFFSTAT) { + if (diff_output_format == DIFF_FORMAT_DIFFSTAT || options->with_stat) { diffstat = xcalloc(sizeof (struct diffstat_t), 1); diffstat->xm.consume = diffstat_consume; } @@ -1530,6 +1545,17 @@ void diff_flush(struct diff_options *options) } putchar(options->line_termination); } + if (options->with_stat) { + for (i = 0; i < q->nr; i++) { + struct diff_filepair *p = q->queue[i]; + flush_one_pair(p, DIFF_FORMAT_DIFFSTAT, options, + diffstat); + } + show_stats(diffstat); + free(diffstat); + diffstat = NULL; + putchar(options->line_termination); + } for (i = 0; i < q->nr; i++) { struct diff_filepair *p = q->queue[i]; flush_one_pair(p, diff_output_format, options, diffstat); diff --git a/diff.h b/diff.h index 2f8aff2cd4..f783baef14 100644 --- a/diff.h +++ b/diff.h @@ -25,6 +25,7 @@ struct diff_options { const char *pickaxe; unsigned recursive:1, with_raw:1, + with_stat:1, tree_in_recursive:1, full_index:1; int break_opt; @@ -120,6 +121,8 @@ extern void diffcore_std_no_resolve(struct diff_options *); " --patch-with-raw\n" \ " output both a patch and the diff-raw format.\n" \ " --stat show diffstat instead of patch.\n" \ +" --patch-with-stat\n" \ +" output a patch and prepend its diffstat.\n" \ " --name-only show only names of changed files.\n" \ " --name-status show names and status of changed files.\n" \ " --full-index show full object name on index lines.\n" \ diff --git a/git.c b/git.c index 9e29ade2b4..239b26adfd 100644 --- a/git.c +++ b/git.c @@ -330,8 +330,10 @@ static int cmd_log_wc(int argc, const char **argv, char **envp, pretty_print_commit(rev->commit_format, commit, ~0, buf, LOGSIZE, rev->abbrev); printf("%s\n", buf); - if (rev->diff) + if (rev->diff) { + printf("--\n"); log_tree_commit(rev, commit); + } shown = 1; free(commit->buffer); commit->buffer = NULL; @@ -398,6 +400,12 @@ static void handle_internal_command(int argc, const char **argv, char **envp) }; int i; + /* Turn "git cmd --help" into "git help cmd" */ + if (argc > 1 && !strcmp(argv[1], "--help")) { + argv[1] = argv[0]; + argv[0] = cmd = "help"; + } + for (i = 0; i < ARRAY_SIZE(commands); i++) { struct cmd_struct *p = commands+i; if (strcmp(p->cmd, cmd)) diff --git a/gsimm.c b/gsimm.c new file mode 100644 index 0000000000..7024bf8f58 --- /dev/null +++ b/gsimm.c @@ -0,0 +1,94 @@ +#include "rabinpoly.h" +#include "gsimm.h" + +/* Has to be power of two. Since the Rabin hash only has 63 + usable bits, the number of hashes is limited to 32. + Lower powers of two could be used for speeding up processing + of very large files. */ +#define NUM_HASHES_PER_CHAR 32 + +/* Size of cache used to eliminate duplicate substrings. + Make small enough to comfortably fit in L1 cache. */ +#define DUP_CACHE_SIZE 256 + +/* For the final counting, do not count each bit individually, but + group them. Must be power of two, at most NUM_HASHES_PER_CHAR. + However, larger sizes result in higher cache usage. Use 8 bits + per group for efficient processing of large files on fast machines + with decent caches, or 4 bits for faster processing of small files + and for machines with small caches. */ +#define GROUP_BITS 4 +#define GROUP_COUNTERS (1< 0); + md[j] = ch; + } + bzero (freq, sizeof(freq[0]) * MD_BITS); +} + +void gb_simm_process(u_char *data, unsigned len, u_char *md) +{ size_t j = 0; + u_int32_t ofs; + u_int32_t dup_cache[DUP_CACHE_SIZE]; + u_int32_t count [MD_BITS * (GROUP_COUNTERS/GROUP_BITS)]; + int freq[MD_BITS]; + + bzero (freq, sizeof(freq[0]) * MD_BITS); + bzero (dup_cache, DUP_CACHE_SIZE * sizeof (u_int32_t)); + bzero (count, (MD_BITS * (GROUP_COUNTERS/GROUP_BITS) * sizeof (u_int32_t))); + + /* Ignore incomplete substrings */ + while (j < len && j < RABIN_WINDOW_SIZE) rabin_slide8 (data[j++]); + + while (j < len) + { u_int64_t hash; + u_int32_t ofs, sum; + u_char idx; + int k; + + hash = rabin_slide8 (data[j++]); + + /* In order to update a much larger frequency table + with only 32 bits of checksum, randomly select a + part of the table to update. The selection should + only depend on the content of the represented data, + and be independent of the bits used for the update. + + Instead of updating 32 individual counters, process + the checksum in MD_BITS / GROUP_BITS groups of + GROUP_BITS bits, and count the frequency of each bit pattern. + */ + + idx = (hash >> 32); + sum = (u_int32_t) hash; + ofs = idx % (MD_BITS / NUM_HASHES_PER_CHAR) * NUM_HASHES_PER_CHAR; + idx %= DUP_CACHE_SIZE; + if (dup_cache[idx] != sum) + { dup_cache[idx] = sum; + for (k = 0; k < NUM_HASHES_PER_CHAR / GROUP_BITS; k++) + { count[ofs * GROUP_COUNTERS / GROUP_BITS + (sum % GROUP_COUNTERS)]++; + ofs += GROUP_BITS; + sum >>= GROUP_BITS; + } } } + + /* Distribute the occurrences of each bit group over the frequency table. */ + for (ofs = 0; ofs < MD_BITS; ofs += GROUP_BITS) + { int j; + for (j = 0; j < GROUP_COUNTERS; j++) + { int k; + for (k = 0; k < GROUP_BITS; k++) + { freq[ofs + k] += ((1<> 7) + 7: (n >> 5) + 5: + n & 0x0c? (n >> 3) + 3: n - ((n + 1) >> 2); +} + +static inline unsigned fls16(unsigned n) +{ + return n & 0xff00? fls8(n >> 8) + 8: fls8(n); +} + +static inline unsigned fls32(unsigned n) +{ + return n & 0xffff0000? fls16(n >> 16) + 16: fls16(n); +} + +static inline unsigned fls64(unsigned long long n) /* should be u64 */ +{ + return n & 0xffffffff00000000ULL? fls32(n >> 32) + 32: fls32(n); +} + + +static u_int64_t polymod (u_int64_t nh, u_int64_t nl, u_int64_t d); +static void polymult (u_int64_t *php, u_int64_t *plp, + u_int64_t x, u_int64_t y); +static u_int64_t polymmult (u_int64_t x, u_int64_t y, u_int64_t d); + +static u_int64_t poly = 0xb15e234bd3792f63ull; // Actual polynomial +static u_int64_t T[256]; // Lookup table for mod +static int shift; + +u_int64_t append8 (u_int64_t p, u_char m) +{ return ((p << 8) | m) ^ T[p >> shift]; +} + +static u_int64_t +polymod (u_int64_t nh, u_int64_t nl, u_int64_t d) +{ int i, k; + assert (d); + k = fls64 (d) - 1; + d <<= 63 - k; + + if (nh) { + if (nh & MSB64) + nh ^= d; + for (i = 62; i >= 0; i--) + if (nh & 1ULL << i) { + nh ^= d >> (63 - i); + nl ^= d << (i + 1); + } + } + for (i = 63; i >= k; i--) + if (nl & 1ULL << i) + nl ^= d >> (63 - i); + return nl; +} + +static void +polymult (u_int64_t *php, u_int64_t *plp, u_int64_t x, u_int64_t y) +{ int i; + u_int64_t ph = 0, pl = 0; + if (x & 1) + pl = y; + for (i = 1; i < 64; i++) + if (x & (1ULL << i)) { + ph ^= y >> (64 - i); + pl ^= y << i; + } + if (php) + *php = ph; + if (plp) + *plp = pl; +} + +static u_int64_t +polymmult (u_int64_t x, u_int64_t y, u_int64_t d) +{ + u_int64_t h, l; + polymult (&h, &l, x, y); + return polymod (h, l, d); +} + +static int size = RABIN_WINDOW_SIZE; +static u_int64_t fingerprint = 0; +static int bufpos = -1; +static u_int64_t U[256]; +static u_char buf[RABIN_WINDOW_SIZE]; + +void rabin_init () +{ u_int64_t sizeshift = 1; + u_int64_t T1; + int xshift; + int i, j; + assert (poly >= 0x100); + xshift = fls64 (poly) - 1; + shift = xshift - 8; + T1 = polymod (0, 1ULL << xshift, poly); + for (j = 0; j < 256; j++) + T[j] = polymmult (j, T1, poly) | ((u_int64_t) j << xshift); + + for (i = 1; i < size; i++) + sizeshift = append8 (sizeshift, 0); + for (i = 0; i < 256; i++) + U[i] = polymmult (i, sizeshift, poly); + bzero (buf, sizeof (buf)); +} + +void +rabin_reset () +{ rabin_init(); + fingerprint = 0; + bzero (buf, sizeof (buf)); +} + +u_int64_t +rabin_slide8 (u_char m) +{ u_char om; + if (++bufpos >= size) bufpos = 0; + + om = buf[bufpos]; + buf[bufpos] = m; + fingerprint = append8 (fingerprint ^ U[om], m); + + return fingerprint; +} + diff --git a/rabinpoly.h b/rabinpoly.h new file mode 100644 index 0000000000..a19a097459 --- /dev/null +++ b/rabinpoly.h @@ -0,0 +1,31 @@ +/* + * + * Copyright (C) 2000 David Mazieres (dm@uun.org) + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License as + * published by the Free Software Foundation; either version 2, or (at + * your option) any later version. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 + * USA + * + * Translated to C and simplified by Geert Bosch (bosch@gnat.com) + */ + +#include +#include +#include + +#ifndef RABIN_WINDOW_SIZE +#define RABIN_WINDOW_SIZE 48 +#endif +void rabin_reset(); +u_int64_t rabin_slide8(u_char c); diff --git a/rev-list.c b/rev-list.c index 000f27a8fe..33741ebbc4 100644 --- a/rev-list.c +++ b/rev-list.c @@ -337,6 +337,8 @@ int main(int argc, const char **argv) save_commit_buffer = revs.verbose_header; track_object_refs = 0; + if (bisect_list) + revs.limited = 1; prepare_revision_walk(&revs); if (revs.tree_objects) diff --git a/test-gsimm.c b/test-gsimm.c new file mode 100644 index 0000000000..bd28b7da28 --- /dev/null +++ b/test-gsimm.c @@ -0,0 +1,209 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "rabinpoly.h" +#include "gsimm.h" + +#define MIN(x,y) ((y)<(x) ? (y) : (x)) +#define MAX(x,y) ((y)>(x) ? (y) : (x)) + +/* The RABIN_WINDOW_SIZE is the size of fingerprint window used by + Rabin algorithm. This is not a modifiable parameter. + + The first RABIN_WINDOW_SIZE - 1 bytes are skipped, in order to ensure + fingerprints are good hashes. This does somewhat reduce the + influence of the first few bytes in the file (they're part of + fewer windows, like the last few bytes), but that actually isn't + so bad as files often start with fixed content that may bias comparisons. +*/ + +typedef struct fileinfo +{ char *name; + size_t length; + u_char md[MD_LENGTH]; + int match; +} File; + +int flag_verbose = 0; +int flag_debug = 0; +char *flag_relative = 0; + +char cmd[12] = " ..."; +char md_strbuf[MD_LENGTH * 2 + 1]; +u_char relative_md [MD_LENGTH]; + +File *file; +int file_count; +size_t file_bytes; + +char hex[17] = "0123456789abcdef"; + +void usage() +{ fprintf (stderr, "usage: %s [-dhvw] [-r fingerprint] file ...\n", cmd); + fprintf (stderr, " -d\tdebug output, repeate for more verbosity\n"); + fprintf (stderr, " -h\tshow this usage information\n"); + fprintf (stderr, " -r\tshow distance relative to fingerprint " + "(%u hex digits)\n", MD_LENGTH * 2); + fprintf (stderr, " -v\tverbose output, repeat for even more verbosity\n"); + fprintf (stderr, " -w\tenable warnings for suspect statistics\n"); + exit (1); +} + +int dist (u_char *l, u_char *r) +{ int j, k; + int d = 0; + + for (j = 0; j < MD_LENGTH; j++) + { u_char ch = l[j] ^ r[j]; + + for (k = 0; k < 8; k++) d += ((ch & (1< 0); + } + + return d; +} + +char *md_to_str(u_char *md) +{ int j; + + for (j = 0; j < MD_LENGTH; j++) + { u_char ch = md[j]; + + md_strbuf[j*2] = hex[ch >> 4]; + md_strbuf[j*2+1] = hex[ch & 0xF]; + } + + md_strbuf[j*2] = 0; + return md_strbuf; +} + +void process_file (char *name) +{ int fd; + struct stat fs; + u_char *data; + File *fi = file+file_count;; + + fd = open (name, O_RDONLY, 0); + if (fd < 0) + { perror (name); + exit (2); + } + + if (fstat (fd, &fs)) + { perror (name); + exit (2); + } + + if (fs.st_size >= MIN_FILE_SIZE + && fs.st_size <= MAX_FILE_SIZE) + { fi->length = fs.st_size; + fi->name = name; + + data = (u_char *) mmap (0, fs.st_size, PROT_READ, MAP_PRIVATE, fd, 0); + + if (data == (u_char *) -1) + { perror (name); + exit (2); + } + + gb_simm_process (data, fs.st_size, fi->md); + if (flag_relative) + { int d = dist (fi->md, relative_md); + double sim = 1.0 - MIN (1.0, (double) (d) / (MD_LENGTH * 4 - 1)); + fprintf (stdout, "%s %llu %u %s %u %3.1f\n", + md_to_str (fi->md), (long long unsigned) 0, + (unsigned) fs.st_size, name, + d, 100.0 * sim); + } + else + { + fprintf (stdout, "%s %llu %u %s\n", + md_to_str (fi->md), (long long unsigned) 0, + (unsigned) fs.st_size, name); + } + munmap (data, fs.st_size); + file_bytes += fs.st_size; + file_count++; + } else if (flag_verbose) + { fprintf (stdout, "skipping %s (size %llu)\n", name, (long long unsigned) fs.st_size); } + + close (fd); +} + +u_char *str_to_md(char *str, u_char *md) +{ int j; + + if (!md || !str) return 0; + + bzero (md, MD_LENGTH); + + for (j = 0; j < MD_LENGTH * 2; j++) + { char ch = str[j]; + + if (ch >= '0' && ch <= '9') + { md [j/2] = (md [j/2] << 4) + (ch - '0'); + } + else + { ch |= 32; + + if (ch < 'a' || ch > 'f') break; + md [j/2] = (md[j/2] << 4) + (ch - 'a' + 10); + } } + + return (j != MD_LENGTH * 2 || str[j] != 0) ? 0 : md; +} + +int main (int argc, char *argv[]) +{ int ch, j; + + strncpy (cmd, basename (argv[0]), 8); + + while ((ch = getopt(argc, argv, "dhr:vw")) != -1) + { switch (ch) + { case 'd': flag_debug++; + break; + case 'r': if (!optarg) + { fprintf (stderr, "%s: missing argument for -r\n", cmd); + return 1; + } + if (str_to_md (optarg, relative_md)) flag_relative = optarg; + else + { fprintf (stderr, "%s: not a valid fingerprint\n", optarg); + return 1; + } + break; + case 'v': flag_verbose++; + break; + case 'w': break; + default : usage(); + return (ch != 'h'); + } } + + argc -= optind; + argv += optind; + + if (argc == 0) usage(); + + rabin_reset (); + if (flag_verbose && flag_relative) + { fprintf (stdout, "distances are relative to %s\n", flag_relative); + } + + file = (File *) calloc (argc, sizeof (File)); + + for (j = 0; j < argc; j++) process_file (argv[j]); + + if (flag_verbose) + { fprintf (stdout, "%li bytes in %i files\n", (long) file_bytes, file_count); + } + + return 0; +} diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c index 641362d056..b95ade2c1b 100644 --- a/xdiff/xdiffi.c +++ b/xdiff/xdiffi.c @@ -45,6 +45,8 @@ static long xdl_split(unsigned long const *ha1, long off1, long lim1, long *kvdf, long *kvdb, int need_min, xdpsplit_t *spl, xdalgoenv_t *xenv); static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, long chg2); +static int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo); + @@ -395,6 +397,110 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, } +static int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo) { + long ix, ixo, ixs, ixref, grpsiz, nrec = xdf->nrec; + char *rchg = xdf->rchg, *rchgo = xdfo->rchg; + xrecord_t **recs = xdf->recs; + + /* + * This is the same of what GNU diff does. Move back and forward + * change groups for a consistent and pretty diff output. This also + * helps in finding joineable change groups and reduce the diff size. + */ + for (ix = ixo = 0;;) { + /* + * Find the first changed line in the to-be-compacted file. + * We need to keep track of both indexes, so if we find a + * changed lines group on the other file, while scanning the + * to-be-compacted file, we need to skip it properly. Note + * that loops that are testing for changed lines on rchg* do + * not need index bounding since the array is prepared with + * a zero at position -1 and N. + */ + for (; ix < nrec && !rchg[ix]; ix++) + while (rchgo[ixo++]); + if (ix == nrec) + break; + + /* + * Record the start of a changed-group in the to-be-compacted file + * and find the end of it, on both to-be-compacted and other file + * indexes (ix and ixo). + */ + ixs = ix; + for (ix++; rchg[ix]; ix++); + for (; rchgo[ixo]; ixo++); + + do { + grpsiz = ix - ixs; + + /* + * If the line before the current change group, is equal to + * the last line of the current change group, shift backward + * the group. + */ + while (ixs > 0 && recs[ixs - 1]->ha == recs[ix - 1]->ha && + XDL_RECMATCH(recs[ixs - 1], recs[ix - 1])) { + rchg[--ixs] = 1; + rchg[--ix] = 0; + + /* + * This change might have joined two change groups, + * so we try to take this scenario in account by moving + * the start index accordingly (and so the other-file + * end-of-group index). + */ + for (; rchg[ixs - 1]; ixs--); + while (rchgo[--ixo]); + } + + /* + * Record the end-of-group position in case we are matched + * with a group of changes in the other file (that is, the + * change record before the enf-of-group index in the other + * file is set). + */ + ixref = rchgo[ixo - 1] ? ix: nrec; + + /* + * If the first line of the current change group, is equal to + * the line next of the current change group, shift forward + * the group. + */ + while (ix < nrec && recs[ixs]->ha == recs[ix]->ha && + XDL_RECMATCH(recs[ixs], recs[ix])) { + rchg[ixs++] = 0; + rchg[ix++] = 1; + + /* + * This change might have joined two change groups, + * so we try to take this scenario in account by moving + * the start index accordingly (and so the other-file + * end-of-group index). Keep tracking the reference + * index in case we are shifting together with a + * corresponding group of changes in the other file. + */ + for (; rchg[ix]; ix++); + while (rchgo[++ixo]) + ixref = ix; + } + } while (grpsiz != ix - ixs); + + /* + * Try to move back the possibly merged group of changes, to match + * the recorded postion in the other file. + */ + while (ixref < ix) { + rchg[--ixs] = 1; + rchg[--ix] = 0; + while (rchgo[--ixo]); + } + } + + return 0; +} + + int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) { xdchange_t *cscr = NULL, *xch; char *rchg1 = xe->xdf1.rchg, *rchg2 = xe->xdf2.rchg; @@ -440,13 +546,13 @@ int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, return -1; } - - if (xdl_build_script(&xe, &xscr) < 0) { + if (xdl_change_compact(&xe.xdf1, &xe.xdf2) < 0 || + xdl_change_compact(&xe.xdf2, &xe.xdf1) < 0 || + xdl_build_script(&xe, &xscr) < 0) { xdl_free_env(&xe); return -1; } - if (xscr) { if (xdl_emit_diff(&xe, xscr, ecb, xecfg) < 0) { @@ -454,10 +560,8 @@ int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, xdl_free_env(&xe); return -1; } - xdl_free_script(xscr); } - xdl_free_env(&xe); return 0; diff --git a/xdiff/xmacros.h b/xdiff/xmacros.h index 4c2fde80c1..78f02603b8 100644 --- a/xdiff/xmacros.h +++ b/xdiff/xmacros.h @@ -33,6 +33,7 @@ #define XDL_ISDIGIT(c) ((c) >= '0' && (c) <= '9') #define XDL_HASHLONG(v, b) (((unsigned long)(v) * GR_PRIME) >> ((CHAR_BIT * sizeof(unsigned long)) - (b))) #define XDL_PTRFREE(p) do { if (p) { xdl_free(p); (p) = NULL; } } while (0) +#define XDL_RECMATCH(r1, r2) ((r1)->size == (r2)->size && memcmp((r1)->ptr, (r2)->ptr, (r1)->size) == 0) #define XDL_LE32_PUT(p, v) \ do { \ unsigned char *__p = (unsigned char *) (p); \