diff options
| -rw-r--r-- | Makefile | 4 | ||||
| -rw-r--r-- | count-delta.c | 72 | ||||
| -rw-r--r-- | count-delta.h | 10 | ||||
| -rw-r--r-- | diff.c | 2 | ||||
| -rw-r--r-- | diffcore-break.c | 46 | ||||
| -rw-r--r-- | diffcore-delta.c | 227 | ||||
| -rw-r--r-- | diffcore-rename.c | 27 | ||||
| -rw-r--r-- | diffcore.h | 7 | ||||
| -rwxr-xr-x | git-fetch.sh | 10 | ||||
| -rwxr-xr-x | git-fmt-merge-msg.perl | 8 | ||||
| -rwxr-xr-x | git-parse-remote.sh | 8 | ||||
| -rw-r--r-- | revision.c | 12 |
12 files changed, 276 insertions, 157 deletions
@@ -190,7 +190,7 @@ PYMODULES = \ LIB_FILE=libgit.a LIB_H = \ - blob.h cache.h commit.h count-delta.h csum-file.h delta.h \ + blob.h cache.h commit.h csum-file.h delta.h \ diff.h object.h pack.h pkt-line.h quote.h refs.h \ run-command.h strbuf.h tag.h tree.h git-compat-util.h revision.h @@ -200,7 +200,7 @@ DIFF_OBJS = \ diffcore-delta.o LIB_OBJS = \ - blob.o commit.o connect.o count-delta.o csum-file.o \ + blob.o commit.o connect.o csum-file.o \ date.o diff-delta.o entry.o exec_cmd.o ident.o index.o \ object.o pack-check.o patch-delta.o path.o pkt-line.o \ quote.o read-cache.o refs.o run-command.o \ diff --git a/count-delta.c b/count-delta.c deleted file mode 100644 index 058a2aadb1..0000000000 --- a/count-delta.c +++ /dev/null @@ -1,72 +0,0 @@ -/* - * Copyright (C) 2005 Junio C Hamano - * The delta-parsing part is almost straight copy of patch-delta.c - * which is (C) 2005 Nicolas Pitre <nico@cam.org>. - */ -#include <stdlib.h> -#include <string.h> -#include <limits.h> -#include "delta.h" -#include "count-delta.h" - -/* - * NOTE. We do not _interpret_ delta fully. As an approximation, we - * just count the number of bytes that are copied from the source, and - * the number of literal data bytes that are inserted. - * - * Number of bytes that are _not_ copied from the source is deletion, - * and number of inserted literal bytes are addition, so sum of them - * is the extent of damage. - */ -int count_delta(void *delta_buf, unsigned long delta_size, - unsigned long *src_copied, unsigned long *literal_added) -{ - unsigned long copied_from_source, added_literal; - const unsigned char *data, *top; - unsigned char cmd; - unsigned long src_size, dst_size, out; - - if (delta_size < DELTA_SIZE_MIN) - return -1; - - data = delta_buf; - top = delta_buf + delta_size; - - src_size = get_delta_hdr_size(&data); - dst_size = get_delta_hdr_size(&data); - - added_literal = copied_from_source = out = 0; - while (data < top) { - cmd = *data++; - if (cmd & 0x80) { - unsigned long cp_off = 0, cp_size = 0; - if (cmd & 0x01) cp_off = *data++; - if (cmd & 0x02) cp_off |= (*data++ << 8); - if (cmd & 0x04) cp_off |= (*data++ << 16); - if (cmd & 0x08) cp_off |= (*data++ << 24); - if (cmd & 0x10) cp_size = *data++; - if (cmd & 0x20) cp_size |= (*data++ << 8); - if (cmd & 0x40) cp_size |= (*data++ << 16); - if (cp_size == 0) cp_size = 0x10000; - - copied_from_source += cp_size; - out += cp_size; - } else { - /* write literal into dst */ - added_literal += cmd; - out += cmd; - data += cmd; - } - } - - /* sanity check */ - if (data != top || out != dst_size) - return -1; - - /* delete size is what was _not_ copied from source. - * edit size is that and literal additions. - */ - *src_copied = copied_from_source; - *literal_added = added_literal; - return 0; -} diff --git a/count-delta.h b/count-delta.h deleted file mode 100644 index 7359629827..0000000000 --- a/count-delta.h +++ /dev/null @@ -1,10 +0,0 @@ -/* - * Copyright (C) 2005 Junio C Hamano - */ -#ifndef COUNT_DELTA_H -#define COUNT_DELTA_H - -int count_delta(void *, unsigned long, - unsigned long *src_copied, unsigned long *literal_added); - -#endif @@ -463,6 +463,8 @@ void diff_free_filespec_data(struct diff_filespec *s) munmap(s->data, s->size); s->should_free = s->should_munmap = 0; s->data = NULL; + free(s->cnt_data); + s->cnt_data = NULL; } static void prep_temp_blob(struct diff_tempfile *temp, diff --git a/diffcore-break.c b/diffcore-break.c index 0fc2b860be..ed0e14c6d8 100644 --- a/diffcore-break.c +++ b/diffcore-break.c @@ -45,8 +45,8 @@ static int should_break(struct diff_filespec *src, * The value we return is 1 if we want the pair to be broken, * or 0 if we do not. */ - unsigned long delta_size, base_size, src_copied, literal_added; - int to_break = 0; + unsigned long delta_size, base_size, src_copied, literal_added, + src_removed; *merge_score_p = 0; /* assume no deletion --- "do not break" * is the default. @@ -68,37 +68,45 @@ static int should_break(struct diff_filespec *src, if (diffcore_count_changes(src->data, src->size, dst->data, dst->size, + NULL, NULL, 0, &src_copied, &literal_added)) return 0; + /* sanity */ + if (src->size < src_copied) + src_copied = src->size; + if (dst->size < literal_added + src_copied) { + if (src_copied < dst->size) + literal_added = dst->size - src_copied; + else + literal_added = 0; + } + src_removed = src->size - src_copied; + /* Compute merge-score, which is "how much is removed * from the source material". The clean-up stage will * merge the surviving pair together if the score is * less than the minimum, after rename/copy runs. */ - if (src->size <= src_copied) - ; /* all copied, nothing removed */ - else { - delta_size = src->size - src_copied; - *merge_score_p = delta_size * MAX_SCORE / src->size; - } - + *merge_score_p = src_removed * MAX_SCORE / src->size; + /* Extent of damage, which counts both inserts and * deletes. */ - if (src->size + literal_added <= src_copied) - delta_size = 0; /* avoid wrapping around */ - else - delta_size = (src->size - src_copied) + literal_added; - - /* We break if the edit exceeds the minimum. - * i.e. (break_score / MAX_SCORE < delta_size / base_size) + delta_size = src_removed + literal_added; + if (delta_size * MAX_SCORE / base_size < break_score) + return 0; + + /* If you removed a lot without adding new material, that is + * not really a rewrite. */ - if (break_score * base_size < delta_size * MAX_SCORE) - to_break = 1; + if ((src->size * break_score < src_removed * MAX_SCORE) && + (literal_added * 20 < src_removed) && + (literal_added * 20 < src_copied)) + return 0; - return to_break; + return 1; } void diffcore_break(int break_score) diff --git a/diffcore-delta.c b/diffcore-delta.c index 1e6a6911ec..ceb35c3276 100644 --- a/diffcore-delta.c +++ b/diffcore-delta.c @@ -1,43 +1,212 @@ #include "cache.h" #include "diff.h" #include "diffcore.h" -#include "delta.h" -#include "count-delta.h" - -static int diffcore_count_changes_1(void *src, unsigned long src_size, - void *dst, unsigned long dst_size, - unsigned long delta_limit, - unsigned long *src_copied, - unsigned long *literal_added) + +/* + * 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). + * + * 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. + * + * 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 */ +#define INITIAL_HASH_SIZE 9 + +/* We leave more room in smaller hash but do not let it + * grow to have unused hole too much. + */ +#define INITIAL_FREE(sz_log2) ((1<<(sz_log2))*(sz_log2-3)/(sz_log2)) + +/* A prime rather carefully chosen between 2^16..2^17, so that + * HASHBASE < INITIAL_FREE(17). We want to keep the maximum hashtable + * size under the current 2<<17 maximum, which can hold this many + * different values before overflowing to hashtable of size 2<<18. + */ +#define HASHBASE 107927 + +struct spanhash { + unsigned long hashval; + unsigned long cnt; +}; +struct spanhash_top { + int alloc_log2; + int free; + struct spanhash data[FLEX_ARRAY]; +}; + +static struct spanhash *spanhash_find(struct spanhash_top *top, + unsigned long hashval) { - void *delta; - unsigned long delta_size; - - delta = diff_delta(src, src_size, - dst, dst_size, - &delta_size, delta_limit); - if (!delta) - /* If delta_limit is exceeded, we have too much differences */ - return -1; - - /* Estimate the edit size by interpreting delta. */ - if (count_delta(delta, delta_size, src_copied, literal_added)) { - free(delta); - return -1; + int sz = 1 << top->alloc_log2; + int bucket = hashval & (sz - 1); + while (1) { + struct spanhash *h = &(top->data[bucket++]); + if (!h->cnt) + return NULL; + if (h->hashval == hashval) + return h; + if (sz <= bucket) + bucket = 0; } - free(delta); - return 0; +} + +static struct spanhash_top *spanhash_rehash(struct spanhash_top *orig) +{ + struct spanhash_top *new; + int i; + int osz = 1 << orig->alloc_log2; + int sz = osz << 1; + + new = xmalloc(sizeof(*orig) + sizeof(struct spanhash) * sz); + new->alloc_log2 = orig->alloc_log2 + 1; + new->free = INITIAL_FREE(new->alloc_log2); + memset(new->data, 0, sizeof(struct spanhash) * sz); + for (i = 0; i < osz; i++) { + struct spanhash *o = &(orig->data[i]); + int bucket; + if (!o->cnt) + continue; + bucket = o->hashval & (sz - 1); + while (1) { + struct spanhash *h = &(new->data[bucket++]); + if (!h->cnt) { + h->hashval = o->hashval; + h->cnt = o->cnt; + new->free--; + break; + } + if (sz <= bucket) + bucket = 0; + } + } + free(orig); + return new; +} + +static struct spanhash_top *add_spanhash(struct spanhash_top *top, + unsigned long hashval, int cnt) +{ + int bucket, lim; + struct spanhash *h; + + lim = (1 << top->alloc_log2); + bucket = hashval & (lim - 1); + while (1) { + h = &(top->data[bucket++]); + if (!h->cnt) { + h->hashval = hashval; + h->cnt = cnt; + top->free--; + if (top->free < 0) + return spanhash_rehash(top); + return top; + } + if (h->hashval == hashval) { + h->cnt += cnt; + return top; + } + if (lim <= bucket) + bucket = 0; + } +} + +static struct spanhash_top *hash_chars(unsigned char *buf, unsigned long sz) +{ + int i, n; + unsigned long accum1, accum2, hashval; + struct spanhash_top *hash; + + i = INITIAL_HASH_SIZE; + hash = xmalloc(sizeof(*hash) + sizeof(struct spanhash) * (1<<i)); + hash->alloc_log2 = i; + hash->free = INITIAL_FREE(i); + memset(hash->data, 0, sizeof(struct spanhash) * (1<<i)); + + n = 0; + accum1 = accum2 = 0; + while (sz) { + unsigned long c = *buf++; + sz--; + accum1 = (accum1 << 7) | (accum2 >> 25); + accum2 = (accum2 << 7) | (accum1 >> 25); + accum1 += c; + if (++n < 64 && c != '\n') + continue; + hashval = (accum1 + accum2 * 0x61) % HASHBASE; + hash = add_spanhash(hash, hashval, n); + n = 0; + accum1 = accum2 = 0; + } + return hash; } int diffcore_count_changes(void *src, unsigned long src_size, void *dst, unsigned long dst_size, + void **src_count_p, + void **dst_count_p, unsigned long delta_limit, unsigned long *src_copied, unsigned long *literal_added) { - return diffcore_count_changes_1(src, src_size, - dst, dst_size, - delta_limit, - src_copied, - literal_added); + int i, ssz; + struct spanhash_top *src_count, *dst_count; + unsigned long sc, la; + + src_count = dst_count = NULL; + if (src_count_p) + src_count = *src_count_p; + if (!src_count) { + src_count = hash_chars(src, src_size); + 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); + if (dst_count_p) + *dst_count_p = dst_count; + } + sc = la = 0; + + ssz = 1 << src_count->alloc_log2; + for (i = 0; i < ssz; i++) { + struct spanhash *s = &(src_count->data[i]); + struct spanhash *d; + unsigned dst_cnt, src_cnt; + if (!s->cnt) + continue; + src_cnt = s->cnt; + d = spanhash_find(dst_count, s->hashval); + dst_cnt = d ? d->cnt : 0; + if (src_cnt < dst_cnt) { + la += dst_cnt - src_cnt; + sc += src_cnt; + } + else + sc += dst_cnt; + } + + if (!src_count_p) + free(src_count); + if (!dst_count_p) + free(dst_count); + *src_copied = sc; + *literal_added = la; + return 0; } diff --git a/diffcore-rename.c b/diffcore-rename.c index 55cf1c37f3..e992698720 100644 --- a/diffcore-rename.c +++ b/diffcore-rename.c @@ -133,7 +133,7 @@ static int estimate_similarity(struct diff_filespec *src, * match than anything else; the destination does not even * call into this function in that case. */ - unsigned long delta_size, base_size, src_copied, literal_added; + unsigned long max_size, delta_size, base_size, src_copied, literal_added; unsigned long delta_limit; int score; @@ -144,9 +144,9 @@ static int estimate_similarity(struct diff_filespec *src, if (!S_ISREG(src->mode) || !S_ISREG(dst->mode)) return 0; - delta_size = ((src->size < dst->size) ? - (dst->size - src->size) : (src->size - dst->size)); + max_size = ((src->size > dst->size) ? src->size : dst->size); base_size = ((src->size < dst->size) ? src->size : dst->size); + delta_size = max_size - base_size; /* We would not consider edits that change the file size so * drastically. delta_size must be smaller than @@ -166,23 +166,18 @@ static int estimate_similarity(struct diff_filespec *src, delta_limit = base_size * (MAX_SCORE-minimum_score) / MAX_SCORE; if (diffcore_count_changes(src->data, src->size, dst->data, dst->size, + &src->cnt_data, &dst->cnt_data, delta_limit, &src_copied, &literal_added)) return 0; - /* Extent of damage */ - if (src->size + literal_added < src_copied) - delta_size = 0; - else - delta_size = (src->size - src_copied) + literal_added; - - /* - * Now we will give some score to it. 100% edit gets 0 points - * and 0% edit gets MAX_SCORE points. + /* How similar are they? + * what percentage of material in dst are from source? */ - score = MAX_SCORE - (MAX_SCORE * delta_size / base_size); - if (score < 0) return 0; - if (MAX_SCORE < score) return MAX_SCORE; + if (!dst->size) + score = 0; /* should not happen */ + else + score = src_copied * MAX_SCORE / max_size; return score; } @@ -310,6 +305,8 @@ void diffcore_rename(struct diff_options *options) m->score = estimate_similarity(one, two, minimum_score); } + /* We do not need the text anymore */ + diff_free_filespec_data(two); dst_cnt++; } /* cost matrix sorted by most to least similar pair */ diff --git a/diffcore.h b/diffcore.h index dba4f17658..73c7842cc7 100644 --- a/diffcore.h +++ b/diffcore.h @@ -17,8 +17,8 @@ */ #define MAX_SCORE 60000.0 #define DEFAULT_RENAME_SCORE 30000 /* rename/copy similarity minimum (50%) */ -#define DEFAULT_BREAK_SCORE 30000 /* minimum for break to happen (50%)*/ -#define DEFAULT_MERGE_SCORE 48000 /* maximum for break-merge to happen (80%)*/ +#define DEFAULT_BREAK_SCORE 30000 /* minimum for break to happen (50%) */ +#define DEFAULT_MERGE_SCORE 36000 /* maximum for break-merge to happen 60%) */ #define MINIMUM_BREAK_SIZE 400 /* do not break a file smaller than this */ @@ -26,6 +26,7 @@ struct diff_filespec { unsigned char sha1[20]; char *path; void *data; + void *cnt_data; unsigned long size; int xfrm_flags; /* for use by the xfrm */ unsigned short mode; /* file mode */ @@ -103,6 +104,8 @@ void diff_debug_queue(const char *, struct diff_queue_struct *); extern int diffcore_count_changes(void *src, unsigned long src_size, void *dst, unsigned long dst_size, + void **src_count_p, + void **dst_count_p, unsigned long delta_limit, unsigned long *src_copied, unsigned long *literal_added); diff --git a/git-fetch.sh b/git-fetch.sh index 0346d4a45c..c0eb96752e 100755 --- a/git-fetch.sh +++ b/git-fetch.sh @@ -94,6 +94,9 @@ append_fetch_head () { # remote-nick is the URL given on the command line (or a shorthand) # remote-name is the $GIT_DIR relative refs/ path we computed # for this refspec. + + # the $note_ variable will be fed to git-fmt-merge-msg for further + # processing. case "$remote_name_" in HEAD) note_= ;; @@ -103,6 +106,9 @@ append_fetch_head () { refs/tags/*) note_="$(expr "$remote_name_" : 'refs/tags/\(.*\)')" note_="tag '$note_' of " ;; + refs/remotes/*) + note_="$(expr "$remote_name_" : 'refs/remotes/\(.*\)')" + note_="remote branch '$note_' of " ;; *) note_="$remote_name of " ;; esac @@ -147,10 +153,10 @@ fast_forward_local () { else echo >&2 "* $1: storing $3" fi - git-update-ref "$1" "$2" + git-update-ref "$1" "$2" ;; - refs/heads/*) + refs/heads/* | refs/remotes/*) # $1 is the ref being updated. # $2 is the new value for the ref. local=$(git-rev-parse --verify "$1^0" 2>/dev/null) diff --git a/git-fmt-merge-msg.perl b/git-fmt-merge-msg.perl index afe80e6321..5986e5414a 100755 --- a/git-fmt-merge-msg.perl +++ b/git-fmt-merge-msg.perl @@ -75,6 +75,7 @@ while (<>) { $src{$src} = { BRANCH => [], TAG => [], + R_BRANCH => [], GENERIC => [], # &1 == has HEAD. # &2 == has others. @@ -91,6 +92,11 @@ while (<>) { push @{$src{$src}{TAG}}, $1; $src{$src}{HEAD_STATUS} |= 2; } + elsif (/^remote branch (.*)$/) { + $origin = $1; + push @{$src{$src}{R_BRANCH}}, $1; + $src{$src}{HEAD_STATUS} |= 2; + } elsif (/^HEAD$/) { $origin = $src; $src{$src}{HEAD_STATUS} |= 1; @@ -123,6 +129,8 @@ for my $src (@src) { } push @this, andjoin("branch ", "branches ", $src{$src}{BRANCH}); + push @this, andjoin("remote branch ", "remote branches ", + $src{$src}{R_BRANCH}); push @this, andjoin("tag ", "tags ", $src{$src}{TAG}); push @this, andjoin("commit ", "commits ", diff --git a/git-parse-remote.sh b/git-parse-remote.sh index 5f158c613f..63f22818e6 100755 --- a/git-parse-remote.sh +++ b/git-parse-remote.sh @@ -86,14 +86,14 @@ canon_refs_list_for_fetch () { local=$(expr "$ref" : '[^:]*:\(.*\)') case "$remote" in '') remote=HEAD ;; - refs/heads/* | refs/tags/*) ;; - heads/* | tags/* ) remote="refs/$remote" ;; + refs/heads/* | refs/tags/* | refs/remotes/*) ;; + heads/* | tags/* | remotes/* ) remote="refs/$remote" ;; *) remote="refs/heads/$remote" ;; esac case "$local" in '') local= ;; - refs/heads/* | refs/tags/*) ;; - heads/* | tags/* ) local="refs/$local" ;; + refs/heads/* | refs/tags/* | refs/remotes/*) ;; + heads/* | tags/* | remotes/* ) local="refs/$local" ;; *) local="refs/heads/$local" ;; esac diff --git a/revision.c b/revision.c index 01386ed6d4..12cd0529a5 100644 --- a/revision.c +++ b/revision.c @@ -313,8 +313,16 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit) case REV_TREE_NEW: if (revs->remove_empty_trees && rev_same_tree_as_empty(p->tree)) { - *pp = parent->next; - continue; + /* We are adding all the specified + * paths from this parent, so the + * history beyond this parent is not + * interesting. Remove its parents + * (they are grandparents for us). + * IOW, we pretend this parent is a + * "root" commit. + */ + parse_commit(p); + p->parents = NULL; } /* fallthrough */ case REV_TREE_DIFFERENT: |