Merge branch 'jc/diffcore'
authorJunio C Hamano <gitster@pobox.com>
Mon, 2 Jul 2007 08:45:12 +0000 (01:45 -0700)
committerJunio C Hamano <gitster@pobox.com>
Mon, 2 Jul 2007 08:45:12 +0000 (01:45 -0700)
* jc/diffcore:
diffcore-delta.c: Ignore CR in CRLF for text files
diffcore-delta.c: update the comment on the algorithm.
diffcore_filespec: add is_binary
diffcore_count_changes: pass diffcore_filespec

diff.c
diffcore-break.c
diffcore-delta.c
diffcore-rename.c
diffcore.h
t/t0022-crlf-rename.sh [new file with mode: 0755]
diff --git a/diff.c b/diff.c
index e0edb98846753f39cab9e377c9ac4af2d7fdbf35..93eca79c1762e697d57ccd8c49b2f7994f722c89 100644 (file)
--- a/diff.c
+++ b/diff.c
@@ -3005,6 +3005,22 @@ void diffcore_std(struct diff_options *options)
 {
        if (options->quiet)
                return;
+
+       /*
+        * break/rename count similarity differently depending on
+        * the binary-ness.
+        */
+       if ((options->break_opt != -1) || (options->detect_rename)) {
+               struct diff_queue_struct *q = &diff_queued_diff;
+               int i;
+
+               for (i = 0; i < q->nr; i++) {
+                       struct diff_filepair *p = q->queue[i];
+                       p->one->is_binary = file_is_binary(p->one);
+                       p->two->is_binary = file_is_binary(p->two);
+               }
+       }
+
        if (options->break_opt != -1)
                diffcore_break(options->break_opt);
        if (options->detect_rename)
index 9c19b8cab778362b9d369135e743fb232a7cd295..ae8a7d03e2d103739897ac37fe1f9966956b9ec8 100644 (file)
@@ -66,8 +66,7 @@ static int should_break(struct diff_filespec *src,
        if (base_size < MINIMUM_BREAK_SIZE)
                return 0; /* we do not break too small filepair */
 
-       if (diffcore_count_changes(src->data, src->size,
-                                  dst->data, dst->size,
+       if (diffcore_count_changes(src, dst,
                                   NULL, NULL,
                                   0,
                                   &src_copied, &literal_added))
index 7338a40c5964ae6ddfb855465249fc1a2fa5a2a3..a038b166c5aa095ffdf31c2fb0e3263ed13cf8b1 100644 (file)
@@ -5,23 +5,20 @@
 /*
  * Idea here is very simple.
  *
- * We have total of (sz-N+1) N-byte overlapping sequences in buf whose
- * size is sz.  If the same N-byte sequence appears in both source and
- * destination, we say the byte that starts that sequence is shared
- * between them (i.e. copied from source to destination).
+ * Almost all data we are interested in are text, but sometimes we have
+ * to deal with binary data.  So we cut them into chunks delimited by
+ * LF byte, or 64-byte sequence, whichever comes first, and hash them.
  *
- * For each possible N-byte sequence, if the source buffer has more
- * instances of it than the destination buffer, that means the
- * difference are the number of bytes not copied from source to
- * destination.  If the counts are the same, everything was copied
- * from source to destination.  If the destination has more,
- * everything was copied, and destination added more.
+ * For those chunks, if the source buffer has more instances of it
+ * than the destination buffer, that means the difference are the
+ * number of bytes not copied from source to destination.  If the
+ * counts are the same, everything was copied from source to
+ * destination.  If the destination has more, everything was copied,
+ * and destination added more.
  *
  * We are doing an approximation so we do not really have to waste
  * memory by actually storing the sequence.  We just hash them into
  * somewhere around 2^16 hashbuckets and count the occurrences.
- *
- * The length of the sequence is arbitrarily set to 8 for now.
  */
 
 /* Wild guess at the initial hash size */
@@ -125,11 +122,14 @@ static struct spanhash_top *add_spanhash(struct spanhash_top *top,
        }
 }
 
-static struct spanhash_top *hash_chars(unsigned char *buf, unsigned int sz)
+static struct spanhash_top *hash_chars(struct diff_filespec *one)
 {
        int i, n;
        unsigned int accum1, accum2, hashval;
        struct spanhash_top *hash;
+       unsigned char *buf = one->data;
+       unsigned int sz = one->size;
+       int is_text = !one->is_binary;
 
        i = INITIAL_HASH_SIZE;
        hash = xmalloc(sizeof(*hash) + sizeof(struct spanhash) * (1<<i));
@@ -143,6 +143,11 @@ static struct spanhash_top *hash_chars(unsigned char *buf, unsigned int sz)
                unsigned int c = *buf++;
                unsigned int old_1 = accum1;
                sz--;
+
+               /* Ignore CR in CRLF sequence if text */
+               if (is_text && c == '\r' && sz && *buf == '\n')
+                       continue;
+
                accum1 = (accum1 << 7) ^ (accum2 >> 25);
                accum2 = (accum2 << 7) ^ (old_1 >> 25);
                accum1 += c;
@@ -156,8 +161,8 @@ static struct spanhash_top *hash_chars(unsigned char *buf, unsigned int sz)
        return hash;
 }
 
-int diffcore_count_changes(void *src, unsigned long src_size,
-                          void *dst, unsigned long dst_size,
+int diffcore_count_changes(struct diff_filespec *src,
+                          struct diff_filespec *dst,
                           void **src_count_p,
                           void **dst_count_p,
                           unsigned long delta_limit,
@@ -172,14 +177,14 @@ int diffcore_count_changes(void *src, unsigned long src_size,
        if (src_count_p)
                src_count = *src_count_p;
        if (!src_count) {
-               src_count = hash_chars(src, src_size);
+               src_count = hash_chars(src);
                if (src_count_p)
                        *src_count_p = src_count;
        }
        if (dst_count_p)
                dst_count = *dst_count_p;
        if (!dst_count) {
-               dst_count = hash_chars(dst, dst_size);
+               dst_count = hash_chars(dst);
                if (dst_count_p)
                        *dst_count_p = dst_count;
        }
index e0a89f3796890d0d23bb80b3fd6e3cac2ae1b752..6bde4396f212833cc1d411e723d5215c086e7c2d 100644 (file)
@@ -190,8 +190,7 @@ static int estimate_similarity(struct diff_filespec *src,
 
        delta_limit = (unsigned long)
                (base_size * (MAX_SCORE-minimum_score) / MAX_SCORE);
-       if (diffcore_count_changes(src->data, src->size,
-                                  dst->data, dst->size,
+       if (diffcore_count_changes(src, dst,
                                   &src->cnt_data, &dst->cnt_data,
                                   delta_limit,
                                   &src_copied, &literal_added))
index 7b9294eab2c1cb9f7cb03307c90203344d97e3f6..0c8abb5b94dc07769e5cd2603988dad6e6869bb7 100644 (file)
@@ -37,6 +37,7 @@ struct diff_filespec {
 #define DIFF_FILE_VALID(spec) (((spec)->mode) != 0)
        unsigned should_free : 1; /* data should be free()'ed */
        unsigned should_munmap : 1; /* data should be munmap()'ed */
+       unsigned is_binary : 1; /* data should be considered "binary" */
 };
 
 extern struct diff_filespec *alloc_filespec(const char *);
@@ -103,8 +104,8 @@ void diff_debug_queue(const char *, struct diff_queue_struct *);
 #define diff_debug_queue(a,b) do {} while(0)
 #endif
 
-extern int diffcore_count_changes(void *src, unsigned long src_size,
-                                 void *dst, unsigned long dst_size,
+extern int diffcore_count_changes(struct diff_filespec *src,
+                                 struct diff_filespec *dst,
                                  void **src_count_p,
                                  void **dst_count_p,
                                  unsigned long delta_limit,
diff --git a/t/t0022-crlf-rename.sh b/t/t0022-crlf-rename.sh
new file mode 100755 (executable)
index 0000000..430a1d1
--- /dev/null
@@ -0,0 +1,33 @@
+#!/bin/sh
+
+test_description='ignore CR in CRLF sequence while computing similiarity'
+
+. ./test-lib.sh
+
+test_expect_success setup '
+
+       cat ../t0022-crlf-rename.sh >sample &&
+       git add sample &&
+
+       test_tick &&
+       git commit -m Initial &&
+
+       sed -e "s/\$/\r/" ../t0022-crlf-rename.sh >elpmas &&
+       git add elpmas &&
+       rm -f sample &&
+
+       test_tick &&
+       git commit -a -m Second
+
+'
+
+test_expect_success 'diff -M' '
+
+       git diff-tree -M -r --name-status HEAD^ HEAD |
+       sed -e "s/R[0-9]*/RNUM/" >actual &&
+       echo "RNUM      sample  elpmas" >expect &&
+       diff -u expect actual
+
+'
+
+test_done