diff options
| -rw-r--r-- | Makefile | 5 | ||||
| -rw-r--r-- | diff.c | 55 | ||||
| -rw-r--r-- | diffcore-rename.c | 344 | ||||
| -rw-r--r-- | diffcore.h | 4 | ||||
| -rw-r--r-- | hash.c | 110 | ||||
| -rw-r--r-- | hash.h | 43 |
6 files changed, 395 insertions, 166 deletions
@@ -289,7 +289,7 @@ LIB_H = \ run-command.h strbuf.h tag.h tree.h git-compat-util.h revision.h \ tree-walk.h log-tree.h dir.h path-list.h unpack-trees.h builtin.h \ utf8.h reflog-walk.h patch-ids.h attr.h decorate.h progress.h \ - mailmap.h remote.h transport.h + mailmap.h remote.h transport.h diffcore.h hash.h DIFF_OBJS = \ diff.o diff-lib.o diffcore-break.o diffcore-order.o \ @@ -299,7 +299,7 @@ DIFF_OBJS = \ LIB_OBJS = \ blob.o commit.o connect.o csum-file.o cache-tree.o base85.o \ date.o diff-delta.o entry.o exec_cmd.o ident.o \ - interpolate.o \ + interpolate.o hash.o \ lockfile.o \ patch-ids.o \ object.o pack-check.o pack-write.o patch-delta.o path.o pkt-line.o \ @@ -916,7 +916,6 @@ git-http-push$X: revision.o http.o http-push.o $(GITLIBS) $(LIB_OBJS) $(BUILTIN_OBJS): $(LIB_H) $(patsubst git-%$X,%.o,$(PROGRAMS)): $(LIB_H) $(wildcard */*.h) -$(DIFF_OBJS): diffcore.h $(LIB_FILE): $(LIB_OBJS) $(QUIET_AR)$(RM) $@ && $(AR) rcs $@ $(LIB_OBJS) @@ -1440,9 +1440,18 @@ struct diff_filespec *alloc_filespec(const char *path) memset(spec, 0, sizeof(*spec)); spec->path = (char *)(spec + 1); memcpy(spec->path, path, namelen+1); + spec->count = 1; return spec; } +void free_filespec(struct diff_filespec *spec) +{ + if (!--spec->count) { + diff_free_filespec_data(spec); + free(spec); + } +} + void fill_filespec(struct diff_filespec *spec, const unsigned char *sha1, unsigned short mode) { @@ -2435,10 +2444,8 @@ struct diff_filepair *diff_queue(struct diff_queue_struct *queue, void diff_free_filepair(struct diff_filepair *p) { - diff_free_filespec_data(p->one); - diff_free_filespec_data(p->two); - free(p->one); - free(p->two); + free_filespec(p->one); + free_filespec(p->two); free(p); } @@ -2590,9 +2597,9 @@ void diff_debug_filepair(const struct diff_filepair *p, int i) { diff_debug_filespec(p->one, i, "one"); diff_debug_filespec(p->two, i, "two"); - fprintf(stderr, "score %d, status %c stays %d broken %d\n", + fprintf(stderr, "score %d, status %c rename_used %d broken %d\n", p->score, p->status ? p->status : '?', - p->source_stays, p->broken_pair); + p->one->rename_used, p->broken_pair); } void diff_debug_queue(const char *msg, struct diff_queue_struct *q) @@ -2610,8 +2617,8 @@ void diff_debug_queue(const char *msg, struct diff_queue_struct *q) static void diff_resolve_rename_copy(void) { - int i, j; - struct diff_filepair *p, *pp; + int i; + struct diff_filepair *p; struct diff_queue_struct *q = &diff_queued_diff; diff_debug_queue("resolve-rename-copy", q); @@ -2633,27 +2640,21 @@ static void diff_resolve_rename_copy(void) * either in-place edit or rename/copy edit. */ else if (DIFF_PAIR_RENAME(p)) { - if (p->source_stays) { - p->status = DIFF_STATUS_COPIED; - continue; - } - /* See if there is some other filepair that - * copies from the same source as us. If so - * we are a copy. Otherwise we are either a - * copy if the path stays, or a rename if it - * does not, but we already handled "stays" case. + /* + * A rename might have re-connected a broken + * pair up, causing the pathnames to be the + * same again. If so, that's not a rename at + * all, just a modification.. + * + * Otherwise, see if this source was used for + * multiple renames, in which case we decrement + * the count, and call it a copy. */ - for (j = i + 1; j < q->nr; j++) { - pp = q->queue[j]; - if (strcmp(pp->one->path, p->one->path)) - continue; /* not us */ - if (!DIFF_PAIR_RENAME(pp)) - continue; /* not a rename/copy */ - /* pp is a rename/copy from the same source */ + if (!strcmp(p->one->path, p->two->path)) + p->status = DIFF_STATUS_MODIFIED; + else if (--p->one->rename_used > 0) p->status = DIFF_STATUS_COPIED; - break; - } - if (!p->status) + else p->status = DIFF_STATUS_RENAMED; } else if (hashcmp(p->one->sha1, p->two->sha1) || diff --git a/diffcore-rename.c b/diffcore-rename.c index 142e5376dd..f9ebea5640 100644 --- a/diffcore-rename.c +++ b/diffcore-rename.c @@ -4,6 +4,7 @@ #include "cache.h" #include "diff.h" #include "diffcore.h" +#include "hash.h" /* Table of rename/copy destinations */ @@ -55,12 +56,10 @@ static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two, static struct diff_rename_src { struct diff_filespec *one; unsigned short score; /* to remember the break score */ - unsigned src_path_left : 1; } *rename_src; static int rename_src_nr, rename_src_alloc; static struct diff_rename_src *register_rename_src(struct diff_filespec *one, - int src_path_left, unsigned short score) { int first, last; @@ -92,33 +91,9 @@ static struct diff_rename_src *register_rename_src(struct diff_filespec *one, (rename_src_nr - first - 1) * sizeof(*rename_src)); rename_src[first].one = one; rename_src[first].score = score; - rename_src[first].src_path_left = src_path_left; return &(rename_src[first]); } -static int is_exact_match(struct diff_filespec *src, - struct diff_filespec *dst, - int contents_too) -{ - if (src->sha1_valid && dst->sha1_valid && - !hashcmp(src->sha1, dst->sha1)) - return 1; - if (!contents_too) - return 0; - if (diff_populate_filespec(src, 1) || diff_populate_filespec(dst, 1)) - return 0; - if (src->size != dst->size) - return 0; - if (src->sha1_valid && dst->sha1_valid) - return !hashcmp(src->sha1, dst->sha1); - if (diff_populate_filespec(src, 0) || diff_populate_filespec(dst, 0)) - return 0; - if (src->size == dst->size && - !memcmp(src->data, dst->data, src->size)) - return 1; - return 0; -} - static int basename_same(struct diff_filespec *src, struct diff_filespec *dst) { int src_len = strlen(src->path), dst_len = strlen(dst->path); @@ -169,6 +144,20 @@ static int estimate_similarity(struct diff_filespec *src, if (!S_ISREG(src->mode) || !S_ISREG(dst->mode)) return 0; + /* + * Need to check that source and destination sizes are + * filled in before comparing them. + * + * If we already have "cnt_data" filled in, we know it's + * all good (avoid checking the size for zero, as that + * is a possible size - we really should have a flag to + * say whether the size is valid or not!) + */ + if (!src->cnt_data && diff_populate_filespec(src, 0)) + return 0; + if (!dst->cnt_data && diff_populate_filespec(dst, 0)) + return 0; + 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; @@ -184,11 +173,6 @@ static int estimate_similarity(struct diff_filespec *src, if (base_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE) return 0; - if ((!src->cnt_data && diff_populate_filespec(src, 0)) - || (!dst->cnt_data && diff_populate_filespec(dst, 0))) - return 0; /* error but caught downstream */ - - delta_limit = (unsigned long) (base_size * (MAX_SCORE-minimum_score) / MAX_SCORE); if (diffcore_count_changes(src, dst, @@ -209,27 +193,25 @@ static int estimate_similarity(struct diff_filespec *src, static void record_rename_pair(int dst_index, int src_index, int score) { - struct diff_filespec *one, *two, *src, *dst; + struct diff_filespec *src, *dst; struct diff_filepair *dp; if (rename_dst[dst_index].pair) die("internal error: dst already matched."); src = rename_src[src_index].one; - one = alloc_filespec(src->path); - fill_filespec(one, src->sha1, src->mode); + src->rename_used++; + src->count++; dst = rename_dst[dst_index].two; - two = alloc_filespec(dst->path); - fill_filespec(two, dst->sha1, dst->mode); + dst->count++; - dp = diff_queue(NULL, one, two); + dp = diff_queue(NULL, src, dst); dp->renamed_pair = 1; if (!strcmp(src->path, dst->path)) dp->score = rename_src[src_index].score; else dp->score = score; - dp->source_stays = rename_src[src_index].src_path_left; rename_dst[dst_index].pair = dp; } @@ -247,19 +229,155 @@ static int score_compare(const void *a_, const void *b_) return b->score - a->score; } -static int compute_stays(struct diff_queue_struct *q, - struct diff_filespec *one) +struct file_similarity { + int src_dst, index; + struct diff_filespec *filespec; + struct file_similarity *next; +}; + +static int find_identical_files(struct file_similarity *src, + struct file_similarity *dst) { - int i; - for (i = 0; i < q->nr; i++) { - struct diff_filepair *p = q->queue[i]; - if (strcmp(one->path, p->two->path)) - continue; - if (DIFF_PAIR_RENAME(p)) { - return 0; /* something else is renamed into this */ + int renames = 0; + + /* + * Walk over all the destinations ... + */ + do { + struct diff_filespec *one = dst->filespec; + struct file_similarity *p, *best; + int i = 100; + + /* + * .. to find the best source match + */ + best = NULL; + for (p = src; p; p = p->next) { + struct diff_filespec *two = p->filespec; + + /* False hash collission? */ + if (hashcmp(one->sha1, two->sha1)) + continue; + /* Non-regular files? If so, the modes must match! */ + if (!S_ISREG(one->mode) || !S_ISREG(two->mode)) { + if (one->mode != two->mode) + continue; + } + best = p; + if (basename_same(one, two)) + break; + + /* Too many identical alternatives? Pick one */ + if (!--i) + break; + } + if (best) { + record_rename_pair(dst->index, best->index, MAX_SCORE); + renames++; } + } while ((dst = dst->next) != NULL); + return renames; +} + +static void free_similarity_list(struct file_similarity *p) +{ + while (p) { + struct file_similarity *entry = p; + p = p->next; + free(entry); } - return 1; +} + +static int find_same_files(void *ptr) +{ + int ret; + struct file_similarity *p = ptr; + struct file_similarity *src = NULL, *dst = NULL; + + /* Split the hash list up into sources and destinations */ + do { + struct file_similarity *entry = p; + p = p->next; + if (entry->src_dst < 0) { + entry->next = src; + src = entry; + } else { + entry->next = dst; + dst = entry; + } + } while (p); + + /* + * If we have both sources *and* destinations, see if + * we can match them up + */ + ret = (src && dst) ? find_identical_files(src, dst) : 0; + + /* Free the hashes and return the number of renames found */ + free_similarity_list(src); + free_similarity_list(dst); + return ret; +} + +static unsigned int hash_filespec(struct diff_filespec *filespec) +{ + unsigned int hash; + if (!filespec->sha1_valid) { + if (diff_populate_filespec(filespec, 0)) + return 0; + hash_sha1_file(filespec->data, filespec->size, "blob", filespec->sha1); + } + memcpy(&hash, filespec->sha1, sizeof(hash)); + return hash; +} + +static void insert_file_table(struct hash_table *table, int src_dst, int index, struct diff_filespec *filespec) +{ + void **pos; + unsigned int hash; + struct file_similarity *entry = xmalloc(sizeof(*entry)); + + entry->src_dst = src_dst; + entry->index = index; + entry->filespec = filespec; + entry->next = NULL; + + hash = hash_filespec(filespec); + pos = insert_hash(hash, entry, table); + + /* We already had an entry there? */ + if (pos) { + entry->next = *pos; + *pos = entry; + } +} + +/* + * Find exact renames first. + * + * The first round matches up the up-to-date entries, + * and then during the second round we try to match + * cache-dirty entries as well. + */ +static int find_exact_renames(void) +{ + int i; + struct hash_table file_table; + + init_hash(&file_table); + for (i = 0; i < rename_src_nr; i++) + insert_file_table(&file_table, -1, i, rename_src[i].one); + + for (i = 0; i < rename_dst_nr; i++) + insert_file_table(&file_table, 1, i, rename_dst[i].two); + + /* Find the renames */ + i = for_each_hash(&file_table, find_same_files); + + /* .. and free the hash data structure */ + free_hash(&file_table); + + return i; } void diffcore_rename(struct diff_options *options) @@ -270,12 +388,11 @@ void diffcore_rename(struct diff_options *options) struct diff_queue_struct *q = &diff_queued_diff; struct diff_queue_struct outq; struct diff_score *mx; - int i, j, rename_count, contents_too; + int i, j, rename_count; int num_create, num_src, dst_cnt; if (!minimum_score) minimum_score = DEFAULT_RENAME_SCORE; - rename_count = 0; for (i = 0; i < q->nr; i++) { struct diff_filepair *p = q->queue[i]; @@ -289,81 +406,66 @@ void diffcore_rename(struct diff_options *options) locate_rename_dst(p->two, 1); } else if (!DIFF_FILE_VALID(p->two)) { - /* If the source is a broken "delete", and + /* + * If the source is a broken "delete", and * they did not really want to get broken, * that means the source actually stays. + * So we increment the "rename_used" score + * by one, to indicate ourselves as a user + */ + if (p->broken_pair && !p->score) + p->one->rename_used++; + register_rename_src(p->one, p->score); + } + else if (detect_rename == DIFF_DETECT_COPY) { + /* + * Increment the "rename_used" score by + * one, to indicate ourselves as a user. */ - int stays = (p->broken_pair && !p->score); - register_rename_src(p->one, stays, p->score); + p->one->rename_used++; + register_rename_src(p->one, p->score); } - else if (detect_rename == DIFF_DETECT_COPY) - register_rename_src(p->one, 1, p->score); } if (rename_dst_nr == 0 || rename_src_nr == 0) goto cleanup; /* nothing to do */ /* + * We really want to cull the candidates list early + * with cheap tests in order to avoid doing deltas. + */ + rename_count = find_exact_renames(); + + /* Did we only want exact renames? */ + if (minimum_score == MAX_SCORE) + goto cleanup; + + /* + * Calculate how many renames are left (but all the source + * files still remain as options for rename/copies!) + */ + num_create = (rename_dst_nr - rename_count); + num_src = rename_src_nr; + + /* All done? */ + if (!num_create) + goto cleanup; + + /* * This basically does a test for the rename matrix not * growing larger than a "rename_limit" square matrix, ie: * - * rename_dst_nr * rename_src_nr > rename_limit * rename_limit + * num_create * num_src > rename_limit * rename_limit * * but handles the potential overflow case specially (and we * assume at least 32-bit integers) */ if (rename_limit <= 0 || rename_limit > 32767) rename_limit = 32767; - if (rename_dst_nr > rename_limit && rename_src_nr > rename_limit) + if (num_create > rename_limit && num_src > rename_limit) goto cleanup; - if (rename_dst_nr * rename_src_nr > rename_limit * rename_limit) + if (num_create * num_src > rename_limit * rename_limit) goto cleanup; - /* We really want to cull the candidates list early - * with cheap tests in order to avoid doing deltas. - * The first round matches up the up-to-date entries, - * and then during the second round we try to match - * cache-dirty entries as well. - */ - for (contents_too = 0; contents_too < 2; contents_too++) { - for (i = 0; i < rename_dst_nr; i++) { - struct diff_filespec *two = rename_dst[i].two; - if (rename_dst[i].pair) - continue; /* dealt with an earlier round */ - for (j = 0; j < rename_src_nr; j++) { - int k; - struct diff_filespec *one = rename_src[j].one; - if (!is_exact_match(one, two, contents_too)) - continue; - - /* see if there is a basename match, too */ - for (k = j; k < rename_src_nr; k++) { - one = rename_src[k].one; - if (basename_same(one, two) && - is_exact_match(one, two, - contents_too)) { - j = k; - break; - } - } - - record_rename_pair(i, j, (int)MAX_SCORE); - rename_count++; - break; /* we are done with this entry */ - } - } - } - - /* Have we run out the created file pool? If so we can avoid - * doing the delta matrix altogether. - */ - if (rename_count == rename_dst_nr) - goto cleanup; - - if (minimum_score == MAX_SCORE) - goto cleanup; - - num_create = (rename_dst_nr - rename_count); - num_src = rename_src_nr; mx = xmalloc(sizeof(*mx) * num_create * num_src); for (dst_cnt = i = 0; i < rename_dst_nr; i++) { int base = dst_cnt * num_src; @@ -452,16 +554,7 @@ void diffcore_rename(struct diff_options *options) pair_to_free = p; } else { - for (j = 0; j < rename_dst_nr; j++) { - if (!rename_dst[j].pair) - continue; - if (strcmp(rename_dst[j].pair-> - one->path, - p->one->path)) - continue; - break; - } - if (j < rename_dst_nr) + if (p->one->rename_used) /* this path remains */ pair_to_free = p; } @@ -487,27 +580,8 @@ void diffcore_rename(struct diff_options *options) *q = outq; diff_debug_queue("done collapsing", q); - /* We need to see which rename source really stays here; - * earlier we only checked if the path is left in the result, - * but even if a path remains in the result, if that is coming - * from copying something else on top of it, then the original - * source is lost and does not stay. - */ - for (i = 0; i < q->nr; i++) { - struct diff_filepair *p = q->queue[i]; - if (DIFF_PAIR_RENAME(p) && p->source_stays) { - /* If one appears as the target of a rename-copy, - * then mark p->source_stays = 0; otherwise - * leave it as is. - */ - p->source_stays = compute_stays(q, p->one); - } - } - - for (i = 0; i < rename_dst_nr; i++) { - diff_free_filespec_data(rename_dst[i].two); - free(rename_dst[i].two); - } + for (i = 0; i < rename_dst_nr; i++) + free_filespec(rename_dst[i].two); free(rename_dst); rename_dst = NULL; diff --git a/diffcore.h b/diffcore.h index eb618b1ec0..cc96c20734 100644 --- a/diffcore.h +++ b/diffcore.h @@ -29,7 +29,9 @@ struct diff_filespec { void *cnt_data; const char *funcname_pattern_ident; unsigned long size; + int count; /* Reference count */ int xfrm_flags; /* for use by the xfrm */ + int rename_used; /* Count of rename users */ unsigned short mode; /* file mode */ unsigned sha1_valid : 1; /* if true, use sha1 and trust mode; * if false, use the name and read from @@ -43,6 +45,7 @@ struct diff_filespec { }; extern struct diff_filespec *alloc_filespec(const char *); +extern void free_filespec(struct diff_filespec *); extern void fill_filespec(struct diff_filespec *, const unsigned char *, unsigned short); @@ -56,7 +59,6 @@ struct diff_filepair { struct diff_filespec *two; unsigned short int score; char status; /* M C R N D U (see Documentation/diff-format.txt) */ - unsigned source_stays : 1; /* all of R/C are copies */ unsigned broken_pair : 1; unsigned renamed_pair : 1; unsigned is_unmerged : 1; diff --git a/hash.c b/hash.c new file mode 100644 index 0000000000..7b492d4fc0 --- /dev/null +++ b/hash.c @@ -0,0 +1,110 @@ +/* + * Some generic hashing helpers. + */ +#include "cache.h" +#include "hash.h" + +/* + * Look up a hash entry in the hash table. Return the pointer to + * the existing entry, or the empty slot if none existed. The caller + * can then look at the (*ptr) to see whether it existed or not. + */ +static struct hash_table_entry *lookup_hash_entry(unsigned int hash, struct hash_table *table) +{ + unsigned int size = table->size, nr = hash % size; + struct hash_table_entry *array = table->array; + + while (array[nr].ptr) { + if (array[nr].hash == hash) + break; + nr++; + if (nr >= size) + nr = 0; + } + return array + nr; +} + + +/* + * Insert a new hash entry pointer into the table. + * + * If that hash entry already existed, return the pointer to + * the existing entry (and the caller can create a list of the + * pointers or do anything else). If it didn't exist, return + * NULL (and the caller knows the pointer has been inserted). + */ +static void **insert_hash_entry(unsigned int hash, void *ptr, struct hash_table *table) +{ + struct hash_table_entry *entry = lookup_hash_entry(hash, table); + + if (!entry->ptr) { + entry->ptr = ptr; + entry->hash = hash; + table->nr++; + return NULL; + } + return &entry->ptr; +} + +static void grow_hash_table(struct hash_table *table) +{ + unsigned int i; + unsigned int old_size = table->size, new_size; + struct hash_table_entry *old_array = table->array, *new_array; + + new_size = alloc_nr(old_size); + new_array = xcalloc(sizeof(struct hash_table_entry), new_size); + table->size = new_size; + table->array = new_array; + table->nr = 0; + for (i = 0; i < old_size; i++) { + unsigned int hash = old_array[i].hash; + void *ptr = old_array[i].ptr; + if (ptr) + insert_hash_entry(hash, ptr, table); + } + free(old_array); +} + +void *lookup_hash(unsigned int hash, struct hash_table *table) +{ + if (!table->array) + return NULL; + return &lookup_hash_entry(hash, table)->ptr; +} + +void **insert_hash(unsigned int hash, void *ptr, struct hash_table *table) +{ + unsigned int nr = table->nr; + if (nr >= table->size/2) + grow_hash_table(table); + return insert_hash_entry(hash, ptr, table); +} + +int for_each_hash(struct hash_table *table, int (*fn)(void *)) +{ + int sum = 0; + unsigned int i; + unsigned int size = table->size; + struct hash_table_entry *array = table->array; + + for (i = 0; i < size; i++) { + void *ptr = array->ptr; + array++; + if (ptr) { + int val = fn(ptr); + if (val < 0) + return val; + sum += val; + } + } + return sum; +} + +void free_hash(struct hash_table *table) +{ + free(table->array); + table->array = NULL; + table->size = 0; + table->nr = 0; +} diff --git a/hash.h b/hash.h new file mode 100644 index 0000000000..a8b0fbb5b5 --- /dev/null +++ b/hash.h @@ -0,0 +1,43 @@ +#ifndef HASH_H +#define HASH_H + +/* + * These are some simple generic hash table helper functions. + * Not necessarily suitable for all users, but good for things + * where you want to just keep track of a list of things, and + * have a good hash to use on them. + * + * It keeps the hash table at roughly 50-75% free, so the memory + * cost of the hash table itself is roughly + * + * 3 * 2*sizeof(void *) * nr_of_objects + * + * bytes. + * + * FIXME: on 64-bit architectures, we waste memory. It would be + * good to have just 32-bit pointers, requiring a special allocator + * for hashed entries or something. + */ +struct hash_table_entry { + unsigned int hash; + void *ptr; +}; + +struct hash_table { + unsigned int size, nr; + struct hash_table_entry *array; +}; + +extern void *lookup_hash(unsigned int hash, struct hash_table *table); +extern void **insert_hash(unsigned int hash, void *ptr, struct hash_table *table); +extern int for_each_hash(struct hash_table *table, int (*fn)(void *)); +extern void free_hash(struct hash_table *table); + +static inline void init_hash(struct hash_table *table) +{ + table->size = 0; + table->nr = 0; + table->array = NULL; +} + +#endif |