diff options
author | Russell Belfer <rb@github.com> | 2012-10-30 20:40:50 +0400 |
---|---|---|
committer | Russell Belfer <rb@github.com> | 2012-10-30 20:40:50 +0400 |
commit | db106d01f093b3e61170e3738d6651a2866cb76e (patch) | |
tree | 0028e57a8490841e60f7b84ce2a3abe0634d54c3 /src/diff_tform.c | |
parent | b4f5bb074721823cc016b66a9984abe2c271cb1f (diff) |
Move rename detection into new file
This improves the naming for the rename related functionality
moving it to be called `git_diff_find_similar()` and renaming
all the associated constants, etc. to make more sense.
I also moved the new code (plus the existing `git_diff_merge`)
into a new file `diff_tform.c` where I can put new functions
related to manipulating git diff lists.
This also updates the implementation significantly from the
last revision fixing some ordering issues (where break-rewrite
needs to be handled prior to copy and rename detection) and
improving config option handling.
Diffstat (limited to 'src/diff_tform.c')
-rw-r--r-- | src/diff_tform.c | 466 |
1 files changed, 466 insertions, 0 deletions
diff --git a/src/diff_tform.c b/src/diff_tform.c new file mode 100644 index 000000000..987d4b8e6 --- /dev/null +++ b/src/diff_tform.c @@ -0,0 +1,466 @@ +/* + * Copyright (C) 2012 the libgit2 contributors + * + * This file is part of libgit2, distributed under the GNU GPL v2 with + * a Linking Exception. For full terms see the included COPYING file. + */ +#include "common.h" +#include "diff.h" +#include "git2/config.h" + +static git_diff_delta *diff_delta__dup( + const git_diff_delta *d, git_pool *pool) +{ + git_diff_delta *delta = git__malloc(sizeof(git_diff_delta)); + if (!delta) + return NULL; + + memcpy(delta, d, sizeof(git_diff_delta)); + + delta->old_file.path = git_pool_strdup(pool, d->old_file.path); + if (delta->old_file.path == NULL) + goto fail; + + if (d->new_file.path != d->old_file.path) { + delta->new_file.path = git_pool_strdup(pool, d->new_file.path); + if (delta->new_file.path == NULL) + goto fail; + } else { + delta->new_file.path = delta->old_file.path; + } + + return delta; + +fail: + git__free(delta); + return NULL; +} + +static git_diff_delta *diff_delta__merge_like_cgit( + const git_diff_delta *a, const git_diff_delta *b, git_pool *pool) +{ + git_diff_delta *dup; + + /* Emulate C git for merging two diffs (a la 'git diff <sha>'). + * + * When C git does a diff between the work dir and a tree, it actually + * diffs with the index but uses the workdir contents. This emulates + * those choices so we can emulate the type of diff. + * + * We have three file descriptions here, let's call them: + * f1 = a->old_file + * f2 = a->new_file AND b->old_file + * f3 = b->new_file + */ + + /* if f2 == f3 or f2 is deleted, then just dup the 'a' diff */ + if (b->status == GIT_DELTA_UNMODIFIED || a->status == GIT_DELTA_DELETED) + return diff_delta__dup(a, pool); + + /* otherwise, base this diff on the 'b' diff */ + if ((dup = diff_delta__dup(b, pool)) == NULL) + return NULL; + + /* If 'a' status is uninteresting, then we're done */ + if (a->status == GIT_DELTA_UNMODIFIED) + return dup; + + assert(a->status != GIT_DELTA_UNMODIFIED); + assert(b->status != GIT_DELTA_UNMODIFIED); + + /* A cgit exception is that the diff of a file that is only in the + * index (i.e. not in HEAD nor workdir) is given as empty. + */ + if (dup->status == GIT_DELTA_DELETED) { + if (a->status == GIT_DELTA_ADDED) + dup->status = GIT_DELTA_UNMODIFIED; + /* else don't overwrite DELETE status */ + } else { + dup->status = a->status; + } + + git_oid_cpy(&dup->old_file.oid, &a->old_file.oid); + dup->old_file.mode = a->old_file.mode; + dup->old_file.size = a->old_file.size; + dup->old_file.flags = a->old_file.flags; + + return dup; +} + +int git_diff_merge( + git_diff_list *onto, + const git_diff_list *from) +{ + int error = 0; + git_pool onto_pool; + git_vector onto_new; + git_diff_delta *delta; + bool ignore_case = false; + unsigned int i, j; + + assert(onto && from); + + if (!from->deltas.length) + return 0; + + if (git_vector_init( + &onto_new, onto->deltas.length, git_diff_delta__cmp) < 0 || + git_pool_init(&onto_pool, 1, 0) < 0) + return -1; + + if ((onto->opts.flags & GIT_DIFF_DELTAS_ARE_ICASE) != 0 || + (from->opts.flags & GIT_DIFF_DELTAS_ARE_ICASE) != 0) + { + ignore_case = true; + + /* This function currently only supports merging diff lists that + * are sorted identically. */ + assert((onto->opts.flags & GIT_DIFF_DELTAS_ARE_ICASE) != 0 && + (from->opts.flags & GIT_DIFF_DELTAS_ARE_ICASE) != 0); + } + + for (i = 0, j = 0; i < onto->deltas.length || j < from->deltas.length; ) { + git_diff_delta *o = GIT_VECTOR_GET(&onto->deltas, i); + const git_diff_delta *f = GIT_VECTOR_GET(&from->deltas, j); + int cmp = !f ? -1 : !o ? 1 : STRCMP_CASESELECT(ignore_case, o->old_file.path, f->old_file.path); + + if (cmp < 0) { + delta = diff_delta__dup(o, &onto_pool); + i++; + } else if (cmp > 0) { + delta = diff_delta__dup(f, &onto_pool); + j++; + } else { + delta = diff_delta__merge_like_cgit(o, f, &onto_pool); + i++; + j++; + } + + /* the ignore rules for the target may not match the source + * or the result of a merged delta could be skippable... + */ + if (git_diff_delta__should_skip(&onto->opts, delta)) { + git__free(delta); + continue; + } + + if ((error = !delta ? -1 : git_vector_insert(&onto_new, delta)) < 0) + break; + } + + if (!error) { + git_vector_swap(&onto->deltas, &onto_new); + git_pool_swap(&onto->pool, &onto_pool); + onto->new_src = from->new_src; + + /* prefix strings also come from old pool, so recreate those.*/ + onto->opts.old_prefix = + git_pool_strdup_safe(&onto->pool, onto->opts.old_prefix); + onto->opts.new_prefix = + git_pool_strdup_safe(&onto->pool, onto->opts.new_prefix); + } + + git_vector_foreach(&onto_new, i, delta) + git__free(delta); + git_vector_free(&onto_new); + git_pool_clear(&onto_pool); + + return error; +} + +#define DEFAULT_THRESHOLD 50 +#define DEFAULT_BREAK_REWRITE_THRESHOLD 60 +#define DEFAULT_TARGET_LIMIT 200 + +static int normalize_find_opts( + git_diff_list *diff, + git_diff_find_options *opts, + git_diff_find_options *given) +{ + git_config *cfg = NULL; + const char *val; + + if (diff->repo != NULL && + git_repository_config__weakptr(&cfg, diff->repo) < 0) + return -1; + + if (given != NULL) + memcpy(opts, given, sizeof(*opts)); + else { + memset(opts, 0, sizeof(*opts)); + + opts->flags = GIT_DIFF_FIND_RENAMES; + + if (git_config_get_string(&val, cfg, "diff.renames") < 0) + giterr_clear(); + else if (val && + (!strcasecmp(val, "copies") || !strcasecmp(val, "copy"))) + opts->flags = GIT_DIFF_FIND_RENAMES | GIT_DIFF_FIND_COPIES; + } + + /* some flags imply others */ + + if (opts->flags & GIT_DIFF_FIND_RENAMES_FROM_REWRITES) + opts->flags |= GIT_DIFF_FIND_RENAMES; + + if (opts->flags & GIT_DIFF_FIND_COPIES_FROM_UNMODIFIED) + opts->flags |= GIT_DIFF_FIND_COPIES; + +#define USE_DEFAULT(X) ((X) == 0 || (X) > 100) + + if (USE_DEFAULT(opts->rename_threshold)) + opts->rename_threshold = DEFAULT_THRESHOLD; + + if (USE_DEFAULT(opts->rename_from_rewrite_threshold)) + opts->rename_from_rewrite_threshold = DEFAULT_THRESHOLD; + + if (USE_DEFAULT(opts->copy_threshold)) + opts->copy_threshold = DEFAULT_THRESHOLD; + + if (USE_DEFAULT(opts->break_rewrite_threshold)) + opts->break_rewrite_threshold = DEFAULT_BREAK_REWRITE_THRESHOLD; + +#undef USE_DEFAULT + + if (!opts->target_limit) { + int32_t limit = 0; + + opts->target_limit = DEFAULT_TARGET_LIMIT; + + if (git_config_get_int32(&limit, cfg, "diff.renameLimit") < 0) + giterr_clear(); + else if (limit > 0) + opts->target_limit = limit; + } + + return 0; +} + +static int apply_splits_and_deletes(git_diff_list *diff, size_t expected_size) +{ + git_vector onto = GIT_VECTOR_INIT; + size_t i; + git_diff_delta *delta; + + if (git_vector_init(&onto, expected_size, git_diff_delta__cmp) < 0) + return -1; + + /* build new delta list without TO_DELETE and splitting TO_SPLIT */ + git_vector_foreach(&diff->deltas, i, delta) { + if (delta->status == GIT_DELTA__TO_DELETE) { + git__free(delta); + continue; + } + + if (delta->status == GIT_DELTA__TO_SPLIT) { + git_diff_delta *deleted = diff_delta__dup(delta, &diff->pool); + if (!deleted) + return -1; + + deleted->status = GIT_DELTA_DELETED; + memset(&deleted->new_file, 0, sizeof(deleted->new_file)); + deleted->new_file.path = deleted->old_file.path; + deleted->new_file.flags |= GIT_DIFF_FILE_VALID_OID; + + git_vector_insert(&onto, deleted); + + delta->status = GIT_DELTA_ADDED; + memset(&delta->old_file, 0, sizeof(delta->old_file)); + delta->old_file.path = delta->new_file.path; + delta->old_file.flags |= GIT_DIFF_FILE_VALID_OID; + } + + git_vector_insert(&onto, delta); + } + + /* swap new delta list into place */ + git_vector_sort(&onto); + git_vector_swap(&diff->deltas, &onto); + git_vector_free(&onto); + + return 0; +} + +static unsigned int calc_similarity( + void *cache, git_diff_file *old_file, git_diff_file *new_file) +{ + GIT_UNUSED(cache); + + if (git_oid_cmp(&old_file->oid, &new_file->oid) == 0) + return 100; + + /* TODO: insert actual similarity algo here */ + + return 0; +} + +#define FLAG_SET(opts,flag_name) ((opts.flags & flag_name) != 0) + +int git_diff_find_similar( + git_diff_list *diff, + git_diff_find_options *given_opts) +{ + unsigned int i, j, similarity; + git_diff_delta *from, *to; + git_diff_find_options opts; + unsigned int tried_targets, num_changes = 0; + git_vector matches = GIT_VECTOR_INIT; + + if (normalize_find_opts(diff, &opts, given_opts) < 0) + return -1; + + /* first do splits if requested */ + + if (FLAG_SET(opts, GIT_DIFF_FIND_AND_BREAK_REWRITES)) { + git_vector_foreach(&diff->deltas, i, from) { + if (from->status != GIT_DELTA_MODIFIED) + continue; + + /* Right now, this doesn't work right because the similarity + * algorithm isn't actually implemented... + */ + similarity = 100; + /* calc_similarity(NULL, &from->old_file, from->new_file); */ + + if (similarity < opts.break_rewrite_threshold) { + from->status = GIT_DELTA__TO_SPLIT; + num_changes++; + } + } + + /* apply splits as needed */ + if (num_changes > 0 && + apply_splits_and_deletes( + diff, diff->deltas.length + num_changes) < 0) + return -1; + } + + /* next find the most similar delta for each rename / copy candidate */ + + if (git_vector_init(&matches, diff->deltas.length, git_diff_delta__cmp) < 0) + return -1; + + git_vector_foreach(&diff->deltas, i, from) { + tried_targets = 0; + + git_vector_foreach(&diff->deltas, j, to) { + if (i == j) + continue; + + switch (to->status) { + case GIT_DELTA_ADDED: + case GIT_DELTA_UNTRACKED: + case GIT_DELTA_RENAMED: + case GIT_DELTA_COPIED: + break; + default: + /* only the above status values should be checked */ + continue; + } + + /* skip all but DELETED files unless copy detection is on */ + if (from->status != GIT_DELTA_DELETED && + !FLAG_SET(opts, GIT_DIFF_FIND_COPIES)) + continue; + + /* don't check UNMODIFIED files as source unless given option */ + if (from->status == GIT_DELTA_UNMODIFIED && + !FLAG_SET(opts, GIT_DIFF_FIND_COPIES_FROM_UNMODIFIED)) + continue; + + /* cap on maximum files we'll examine */ + if (++tried_targets > opts.target_limit) + break; + + /* calculate similarity and see if this pair beats the + * similarity score of the current best pair. + */ + similarity = calc_similarity(NULL, &from->old_file, &to->new_file); + + if (to->similarity < similarity) { + to->similarity = similarity; + if (git_vector_set(NULL, &matches, j, from) < 0) + return -1; + } + } + } + + /* next rewrite the diffs with renames / copies */ + + num_changes = 0; + + git_vector_foreach(&diff->deltas, j, to) { + from = GIT_VECTOR_GET(&matches, j); + if (!from) { + assert(to->similarity == 0); + continue; + } + + /* three possible outcomes here: + * 1. old DELETED and if over rename threshold, + * new becomes RENAMED and old goes away + * 2. old was MODIFIED but FIND_RENAMES_FROM_REWRITES is on and + * old is more similar to new than it is to itself, in which + * case, new becomes RENAMED and old becomed ADDED + * 3. otherwise if over copy threshold, new becomes COPIED + */ + + if (from->status == GIT_DELTA_DELETED) { + if (to->similarity < opts.rename_threshold) { + to->similarity = 0; + continue; + } + + to->status = GIT_DELTA_RENAMED; + memcpy(&to->old_file, &from->old_file, sizeof(to->old_file)); + + from->status = GIT_DELTA__TO_DELETE; + num_changes++; + + continue; + } + + if (from->status == GIT_DELTA_MODIFIED && + FLAG_SET(opts, GIT_DIFF_FIND_RENAMES_FROM_REWRITES) && + to->similarity > opts.rename_threshold) + { + similarity = 100; + /* calc_similarity(NULL, &from->old_file, from->new_file); */ + + if (similarity < opts.rename_from_rewrite_threshold) { + to->status = GIT_DELTA_RENAMED; + memcpy(&to->old_file, &from->old_file, sizeof(to->old_file)); + + from->status = GIT_DELTA_ADDED; + memset(&from->old_file, 0, sizeof(from->old_file)); + from->old_file.path = to->old_file.path; + from->old_file.flags |= GIT_DIFF_FILE_VALID_OID; + + continue; + } + } + + if (to->similarity < opts.copy_threshold) { + to->similarity = 0; + continue; + } + + /* convert "to" to a COPIED record */ + to->status = GIT_DELTA_COPIED; + memcpy(&to->old_file, &from->old_file, sizeof(to->old_file)); + } + + git_vector_free(&matches); + + if (num_changes > 0) { + assert(num_changes < diff->deltas.length); + + if (apply_splits_and_deletes( + diff, diff->deltas.length - num_changes) < 0) + return -1; + } + + return 0; +} + +#undef FLAG_SET |