Blame src/diff_tform.c

Packit Service 20376f
/*
Packit Service 20376f
 * Copyright (C) the libgit2 contributors. All rights reserved.
Packit Service 20376f
 *
Packit Service 20376f
 * This file is part of libgit2, distributed under the GNU GPL v2 with
Packit Service 20376f
 * a Linking Exception. For full terms see the included COPYING file.
Packit Service 20376f
 */
Packit Service 20376f
#include "common.h"
Packit Service 20376f
Packit Service 20376f
#include "git2/config.h"
Packit Service 20376f
#include "git2/blob.h"
Packit Service 20376f
#include "git2/sys/hashsig.h"
Packit Service 20376f
Packit Service 20376f
#include "diff.h"
Packit Service 20376f
#include "diff_generate.h"
Packit Service 20376f
#include "path.h"
Packit Service 20376f
#include "fileops.h"
Packit Service 20376f
#include "config.h"
Packit Service 20376f
Packit Service 20376f
git_diff_delta *git_diff__delta_dup(
Packit Service 20376f
	const git_diff_delta *d, git_pool *pool)
Packit Service 20376f
{
Packit Service 20376f
	git_diff_delta *delta = git__malloc(sizeof(git_diff_delta));
Packit Service 20376f
	if (!delta)
Packit Service 20376f
		return NULL;
Packit Service 20376f
Packit Service 20376f
	memcpy(delta, d, sizeof(git_diff_delta));
Packit Service 20376f
	GIT_DIFF_FLAG__CLEAR_INTERNAL(delta->flags);
Packit Service 20376f
Packit Service 20376f
	if (d->old_file.path != NULL) {
Packit Service 20376f
		delta->old_file.path = git_pool_strdup(pool, d->old_file.path);
Packit Service 20376f
		if (delta->old_file.path == NULL)
Packit Service 20376f
			goto fail;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	if (d->new_file.path != d->old_file.path && d->new_file.path != NULL) {
Packit Service 20376f
		delta->new_file.path = git_pool_strdup(pool, d->new_file.path);
Packit Service 20376f
		if (delta->new_file.path == NULL)
Packit Service 20376f
			goto fail;
Packit Service 20376f
	} else {
Packit Service 20376f
		delta->new_file.path = delta->old_file.path;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	return delta;
Packit Service 20376f
Packit Service 20376f
fail:
Packit Service 20376f
	git__free(delta);
Packit Service 20376f
	return NULL;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
git_diff_delta *git_diff__merge_like_cgit(
Packit Service 20376f
	const git_diff_delta *a,
Packit Service 20376f
	const git_diff_delta *b,
Packit Service 20376f
	git_pool *pool)
Packit Service 20376f
{
Packit Service 20376f
	git_diff_delta *dup;
Packit Service 20376f
Packit Service 20376f
	/* Emulate C git for merging two diffs (a la 'git diff <sha>').
Packit Service 20376f
	 *
Packit Service 20376f
	 * When C git does a diff between the work dir and a tree, it actually
Packit Service 20376f
	 * diffs with the index but uses the workdir contents.  This emulates
Packit Service 20376f
	 * those choices so we can emulate the type of diff.
Packit Service 20376f
	 *
Packit Service 20376f
	 * We have three file descriptions here, let's call them:
Packit Service 20376f
	 *  f1 = a->old_file
Packit Service 20376f
	 *  f2 = a->new_file AND b->old_file
Packit Service 20376f
	 *  f3 = b->new_file
Packit Service 20376f
	 */
Packit Service 20376f
Packit Service 20376f
	/* If one of the diffs is a conflict, just dup it */
Packit Service 20376f
	if (b->status == GIT_DELTA_CONFLICTED)
Packit Service 20376f
		return git_diff__delta_dup(b, pool);
Packit Service 20376f
	if (a->status == GIT_DELTA_CONFLICTED)
Packit Service 20376f
		return git_diff__delta_dup(a, pool);
Packit Service 20376f
Packit Service 20376f
	/* if f2 == f3 or f2 is deleted, then just dup the 'a' diff */
Packit Service 20376f
	if (b->status == GIT_DELTA_UNMODIFIED || a->status == GIT_DELTA_DELETED)
Packit Service 20376f
		return git_diff__delta_dup(a, pool);
Packit Service 20376f
Packit Service 20376f
	/* otherwise, base this diff on the 'b' diff */
Packit Service 20376f
	if ((dup = git_diff__delta_dup(b, pool)) == NULL)
Packit Service 20376f
		return NULL;
Packit Service 20376f
Packit Service 20376f
	/* If 'a' status is uninteresting, then we're done */
Packit Service 20376f
	if (a->status == GIT_DELTA_UNMODIFIED ||
Packit Service 20376f
		a->status == GIT_DELTA_UNTRACKED ||
Packit Service 20376f
		a->status == GIT_DELTA_UNREADABLE)
Packit Service 20376f
		return dup;
Packit Service 20376f
Packit Service 20376f
	assert(b->status != GIT_DELTA_UNMODIFIED);
Packit Service 20376f
Packit Service 20376f
	/* A cgit exception is that the diff of a file that is only in the
Packit Service 20376f
	 * index (i.e. not in HEAD nor workdir) is given as empty.
Packit Service 20376f
	 */
Packit Service 20376f
	if (dup->status == GIT_DELTA_DELETED) {
Packit Service 20376f
		if (a->status == GIT_DELTA_ADDED) {
Packit Service 20376f
			dup->status = GIT_DELTA_UNMODIFIED;
Packit Service 20376f
			dup->nfiles = 2;
Packit Service 20376f
		}
Packit Service 20376f
		/* else don't overwrite DELETE status */
Packit Service 20376f
	} else {
Packit Service 20376f
		dup->status = a->status;
Packit Service 20376f
		dup->nfiles = a->nfiles;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	git_oid_cpy(&dup->old_file.id, &a->old_file.id);
Packit Service 20376f
	dup->old_file.mode  = a->old_file.mode;
Packit Service 20376f
	dup->old_file.size  = a->old_file.size;
Packit Service 20376f
	dup->old_file.flags = a->old_file.flags;
Packit Service 20376f
Packit Service 20376f
	return dup;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
int git_diff__merge(
Packit Service 20376f
	git_diff *onto, const git_diff *from, git_diff__merge_cb cb)
Packit Service 20376f
{
Packit Service 20376f
	int error = 0;
Packit Service 20376f
	git_pool onto_pool;
Packit Service 20376f
	git_vector onto_new;
Packit Service 20376f
	git_diff_delta *delta;
Packit Service 20376f
	bool ignore_case, reversed;
Packit Service 20376f
	unsigned int i, j;
Packit Service 20376f
Packit Service 20376f
	assert(onto && from);
Packit Service 20376f
Packit Service 20376f
	if (!from->deltas.length)
Packit Service 20376f
		return 0;
Packit Service 20376f
Packit Service 20376f
	ignore_case = ((onto->opts.flags & GIT_DIFF_IGNORE_CASE) != 0);
Packit Service 20376f
	reversed    = ((onto->opts.flags & GIT_DIFF_REVERSE) != 0);
Packit Service 20376f
Packit Service 20376f
	if (ignore_case != ((from->opts.flags & GIT_DIFF_IGNORE_CASE) != 0) ||
Packit Service 20376f
		reversed    != ((from->opts.flags & GIT_DIFF_REVERSE) != 0)) {
Packit Service 20376f
		giterr_set(GITERR_INVALID,
Packit Service 20376f
			"attempt to merge diffs created with conflicting options");
Packit Service 20376f
		return -1;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	if (git_vector_init(&onto_new, onto->deltas.length, git_diff_delta__cmp) < 0)
Packit Service 20376f
		return -1;
Packit Service 20376f
Packit Service 20376f
	git_pool_init(&onto_pool, 1);
Packit Service 20376f
Packit Service 20376f
	for (i = 0, j = 0; i < onto->deltas.length || j < from->deltas.length; ) {
Packit Service 20376f
		git_diff_delta *o = GIT_VECTOR_GET(&onto->deltas, i);
Packit Service 20376f
		const git_diff_delta *f = GIT_VECTOR_GET(&from->deltas, j);
Packit Service 20376f
		int cmp = !f ? -1 : !o ? 1 :
Packit Service 20376f
			STRCMP_CASESELECT(ignore_case, o->old_file.path, f->old_file.path);
Packit Service 20376f
Packit Service 20376f
		if (cmp < 0) {
Packit Service 20376f
			delta = git_diff__delta_dup(o, &onto_pool);
Packit Service 20376f
			i++;
Packit Service 20376f
		} else if (cmp > 0) {
Packit Service 20376f
			delta = git_diff__delta_dup(f, &onto_pool);
Packit Service 20376f
			j++;
Packit Service 20376f
		} else {
Packit Service 20376f
			const git_diff_delta *left = reversed ? f : o;
Packit Service 20376f
			const git_diff_delta *right = reversed ? o : f;
Packit Service 20376f
Packit Service 20376f
			delta = cb(left, right, &onto_pool);
Packit Service 20376f
			i++;
Packit Service 20376f
			j++;
Packit Service 20376f
		}
Packit Service 20376f
Packit Service 20376f
		/* the ignore rules for the target may not match the source
Packit Service 20376f
		 * or the result of a merged delta could be skippable...
Packit Service 20376f
		 */
Packit Service 20376f
		if (delta && git_diff_delta__should_skip(&onto->opts, delta)) {
Packit Service 20376f
			git__free(delta);
Packit Service 20376f
			continue;
Packit Service 20376f
		}
Packit Service 20376f
Packit Service 20376f
		if ((error = !delta ? -1 : git_vector_insert(&onto_new, delta)) < 0)
Packit Service 20376f
			break;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	if (!error) {
Packit Service 20376f
		git_vector_swap(&onto->deltas, &onto_new);
Packit Service 20376f
		git_pool_swap(&onto->pool, &onto_pool);
Packit Service 20376f
Packit Service 20376f
		if ((onto->opts.flags & GIT_DIFF_REVERSE) != 0)
Packit Service 20376f
			onto->old_src = from->old_src;
Packit Service 20376f
		else
Packit Service 20376f
			onto->new_src = from->new_src;
Packit Service 20376f
Packit Service 20376f
		/* prefix strings also come from old pool, so recreate those.*/
Packit Service 20376f
		onto->opts.old_prefix =
Packit Service 20376f
			git_pool_strdup_safe(&onto->pool, onto->opts.old_prefix);
Packit Service 20376f
		onto->opts.new_prefix =
Packit Service 20376f
			git_pool_strdup_safe(&onto->pool, onto->opts.new_prefix);
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	git_vector_free_deep(&onto_new);
Packit Service 20376f
	git_pool_clear(&onto_pool);
Packit Service 20376f
Packit Service 20376f
	return error;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
int git_diff_merge(git_diff *onto, const git_diff *from)
Packit Service 20376f
{
Packit Service 20376f
	return git_diff__merge(onto, from, git_diff__merge_like_cgit);
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
int git_diff_find_similar__hashsig_for_file(
Packit Service 20376f
	void **out, const git_diff_file *f, const char *path, void *p)
Packit Service 20376f
{
Packit Service 20376f
	git_hashsig_option_t opt = (git_hashsig_option_t)(intptr_t)p;
Packit Service 20376f
Packit Service 20376f
	GIT_UNUSED(f);
Packit Service 20376f
	return git_hashsig_create_fromfile((git_hashsig **)out, path, opt);
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
int git_diff_find_similar__hashsig_for_buf(
Packit Service 20376f
	void **out, const git_diff_file *f, const char *buf, size_t len, void *p)
Packit Service 20376f
{
Packit Service 20376f
	git_hashsig_option_t opt = (git_hashsig_option_t)(intptr_t)p;
Packit Service 20376f
Packit Service 20376f
	GIT_UNUSED(f);
Packit Service 20376f
	return git_hashsig_create((git_hashsig **)out, buf, len, opt);
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
void git_diff_find_similar__hashsig_free(void *sig, void *payload)
Packit Service 20376f
{
Packit Service 20376f
	GIT_UNUSED(payload);
Packit Service 20376f
	git_hashsig_free(sig);
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
int git_diff_find_similar__calc_similarity(
Packit Service 20376f
	int *score, void *siga, void *sigb, void *payload)
Packit Service 20376f
{
Packit Service 20376f
	int error;
Packit Service 20376f
Packit Service 20376f
	GIT_UNUSED(payload);
Packit Service 20376f
	error = git_hashsig_compare(siga, sigb);
Packit Service 20376f
	if (error < 0)
Packit Service 20376f
		return error;
Packit Service 20376f
Packit Service 20376f
	*score = error;
Packit Service 20376f
	return 0;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
#define DEFAULT_THRESHOLD 50
Packit Service 20376f
#define DEFAULT_BREAK_REWRITE_THRESHOLD 60
Packit Service 20376f
#define DEFAULT_RENAME_LIMIT 200
Packit Service 20376f
Packit Service 20376f
static int normalize_find_opts(
Packit Service 20376f
	git_diff *diff,
Packit Service 20376f
	git_diff_find_options *opts,
Packit Service 20376f
	const git_diff_find_options *given)
Packit Service 20376f
{
Packit Service 20376f
	git_config *cfg = NULL;
Packit Service 20376f
	git_hashsig_option_t hashsig_opts;
Packit Service 20376f
Packit Service 20376f
	GITERR_CHECK_VERSION(given, GIT_DIFF_FIND_OPTIONS_VERSION, "git_diff_find_options");
Packit Service 20376f
Packit Service 20376f
	if (diff->repo != NULL &&
Packit Service 20376f
		git_repository_config__weakptr(&cfg, diff->repo) < 0)
Packit Service 20376f
		return -1;
Packit Service 20376f
Packit Service 20376f
	if (given)
Packit Service 20376f
		memcpy(opts, given, sizeof(*opts));
Packit Service 20376f
Packit Service 20376f
	if (!given ||
Packit Service 20376f
		 (given->flags & GIT_DIFF_FIND_ALL) == GIT_DIFF_FIND_BY_CONFIG)
Packit Service 20376f
	{
Packit Service 20376f
		if (cfg) {
Packit Service 20376f
			char *rule =
Packit Service 20376f
				git_config__get_string_force(cfg, "diff.renames", "true");
Packit Service 20376f
			int boolval;
Packit Service 20376f
Packit Service 20376f
			if (!git__parse_bool(&boolval, rule) && !boolval)
Packit Service 20376f
				/* don't set FIND_RENAMES if bool value is false */;
Packit Service 20376f
			else if (!strcasecmp(rule, "copies") || !strcasecmp(rule, "copy"))
Packit Service 20376f
				opts->flags |= GIT_DIFF_FIND_RENAMES | GIT_DIFF_FIND_COPIES;
Packit Service 20376f
			else
Packit Service 20376f
				opts->flags |= GIT_DIFF_FIND_RENAMES;
Packit Service 20376f
Packit Service 20376f
			git__free(rule);
Packit Service 20376f
		} else {
Packit Service 20376f
			/* set default flag */
Packit Service 20376f
			opts->flags |= GIT_DIFF_FIND_RENAMES;
Packit Service 20376f
		}
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	/* some flags imply others */
Packit Service 20376f
Packit Service 20376f
	if (opts->flags & GIT_DIFF_FIND_EXACT_MATCH_ONLY) {
Packit Service 20376f
		/* if we are only looking for exact matches, then don't turn
Packit Service 20376f
		 * MODIFIED items into ADD/DELETE pairs because it's too picky
Packit Service 20376f
		 */
Packit Service 20376f
		opts->flags &= ~(GIT_DIFF_FIND_REWRITES | GIT_DIFF_BREAK_REWRITES);
Packit Service 20376f
Packit Service 20376f
		/* similarly, don't look for self-rewrites to split */
Packit Service 20376f
		opts->flags &= ~GIT_DIFF_FIND_RENAMES_FROM_REWRITES;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	if (opts->flags & GIT_DIFF_FIND_RENAMES_FROM_REWRITES)
Packit Service 20376f
		opts->flags |= GIT_DIFF_FIND_RENAMES;
Packit Service 20376f
Packit Service 20376f
	if (opts->flags & GIT_DIFF_FIND_COPIES_FROM_UNMODIFIED)
Packit Service 20376f
		opts->flags |= GIT_DIFF_FIND_COPIES;
Packit Service 20376f
Packit Service 20376f
	if (opts->flags & GIT_DIFF_BREAK_REWRITES)
Packit Service 20376f
		opts->flags |= GIT_DIFF_FIND_REWRITES;
Packit Service 20376f
Packit Service 20376f
#define USE_DEFAULT(X) ((X) == 0 || (X) > 100)
Packit Service 20376f
Packit Service 20376f
	if (USE_DEFAULT(opts->rename_threshold))
Packit Service 20376f
		opts->rename_threshold = DEFAULT_THRESHOLD;
Packit Service 20376f
Packit Service 20376f
	if (USE_DEFAULT(opts->rename_from_rewrite_threshold))
Packit Service 20376f
		opts->rename_from_rewrite_threshold = DEFAULT_THRESHOLD;
Packit Service 20376f
Packit Service 20376f
	if (USE_DEFAULT(opts->copy_threshold))
Packit Service 20376f
		opts->copy_threshold = DEFAULT_THRESHOLD;
Packit Service 20376f
Packit Service 20376f
	if (USE_DEFAULT(opts->break_rewrite_threshold))
Packit Service 20376f
		opts->break_rewrite_threshold = DEFAULT_BREAK_REWRITE_THRESHOLD;
Packit Service 20376f
Packit Service 20376f
#undef USE_DEFAULT
Packit Service 20376f
Packit Service 20376f
	if (!opts->rename_limit) {
Packit Service 20376f
		if (cfg) {
Packit Service 20376f
			opts->rename_limit = git_config__get_int_force(
Packit Service 20376f
				cfg, "diff.renamelimit", DEFAULT_RENAME_LIMIT);
Packit Service 20376f
		}
Packit Service 20376f
Packit Service 20376f
		if (opts->rename_limit <= 0)
Packit Service 20376f
			opts->rename_limit = DEFAULT_RENAME_LIMIT;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	/* assign the internal metric with whitespace flag as payload */
Packit Service 20376f
	if (!opts->metric) {
Packit Service 20376f
		opts->metric = git__malloc(sizeof(git_diff_similarity_metric));
Packit Service 20376f
		GITERR_CHECK_ALLOC(opts->metric);
Packit Service 20376f
Packit Service 20376f
		opts->metric->file_signature = git_diff_find_similar__hashsig_for_file;
Packit Service 20376f
		opts->metric->buffer_signature = git_diff_find_similar__hashsig_for_buf;
Packit Service 20376f
		opts->metric->free_signature = git_diff_find_similar__hashsig_free;
Packit Service 20376f
		opts->metric->similarity = git_diff_find_similar__calc_similarity;
Packit Service 20376f
Packit Service 20376f
		if (opts->flags & GIT_DIFF_FIND_IGNORE_WHITESPACE)
Packit Service 20376f
			hashsig_opts = GIT_HASHSIG_IGNORE_WHITESPACE;
Packit Service 20376f
		else if (opts->flags & GIT_DIFF_FIND_DONT_IGNORE_WHITESPACE)
Packit Service 20376f
			hashsig_opts = GIT_HASHSIG_NORMAL;
Packit Service 20376f
		else
Packit Service 20376f
			hashsig_opts = GIT_HASHSIG_SMART_WHITESPACE;
Packit Service 20376f
		hashsig_opts |= GIT_HASHSIG_ALLOW_SMALL_FILES;
Packit Service 20376f
		opts->metric->payload = (void *)hashsig_opts;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	return 0;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static int insert_delete_side_of_split(
Packit Service 20376f
	git_diff *diff, git_vector *onto, const git_diff_delta *delta)
Packit Service 20376f
{
Packit Service 20376f
	/* make new record for DELETED side of split */
Packit Service 20376f
	git_diff_delta *deleted = git_diff__delta_dup(delta, &diff->pool);
Packit Service 20376f
	GITERR_CHECK_ALLOC(deleted);
Packit Service 20376f
Packit Service 20376f
	deleted->status = GIT_DELTA_DELETED;
Packit Service 20376f
	deleted->nfiles = 1;
Packit Service 20376f
	memset(&deleted->new_file, 0, sizeof(deleted->new_file));
Packit Service 20376f
	deleted->new_file.path = deleted->old_file.path;
Packit Service 20376f
	deleted->new_file.flags |= GIT_DIFF_FLAG_VALID_ID;
Packit Service 20376f
Packit Service 20376f
	return git_vector_insert(onto, deleted);
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static int apply_splits_and_deletes(
Packit Service 20376f
	git_diff *diff, size_t expected_size, bool actually_split)
Packit Service 20376f
{
Packit Service 20376f
	git_vector onto = GIT_VECTOR_INIT;
Packit Service 20376f
	size_t i;
Packit Service 20376f
	git_diff_delta *delta;
Packit Service 20376f
Packit Service 20376f
	if (git_vector_init(&onto, expected_size, git_diff_delta__cmp) < 0)
Packit Service 20376f
		return -1;
Packit Service 20376f
Packit Service 20376f
	/* build new delta list without TO_DELETE and splitting TO_SPLIT */
Packit Service 20376f
	git_vector_foreach(&diff->deltas, i, delta) {
Packit Service 20376f
		if ((delta->flags & GIT_DIFF_FLAG__TO_DELETE) != 0)
Packit Service 20376f
			continue;
Packit Service 20376f
Packit Service 20376f
		if ((delta->flags & GIT_DIFF_FLAG__TO_SPLIT) != 0 && actually_split) {
Packit Service 20376f
			delta->similarity = 0;
Packit Service 20376f
Packit Service 20376f
			if (insert_delete_side_of_split(diff, &onto, delta) < 0)
Packit Service 20376f
				goto on_error;
Packit Service 20376f
Packit Service 20376f
			if (diff->new_src == GIT_ITERATOR_TYPE_WORKDIR)
Packit Service 20376f
				delta->status = GIT_DELTA_UNTRACKED;
Packit Service 20376f
			else
Packit Service 20376f
				delta->status = GIT_DELTA_ADDED;
Packit Service 20376f
			delta->nfiles = 1;
Packit Service 20376f
			memset(&delta->old_file, 0, sizeof(delta->old_file));
Packit Service 20376f
			delta->old_file.path = delta->new_file.path;
Packit Service 20376f
			delta->old_file.flags |= GIT_DIFF_FLAG_VALID_ID;
Packit Service 20376f
		}
Packit Service 20376f
Packit Service 20376f
		/* clean up delta before inserting into new list */
Packit Service 20376f
		GIT_DIFF_FLAG__CLEAR_INTERNAL(delta->flags);
Packit Service 20376f
Packit Service 20376f
		if (delta->status != GIT_DELTA_COPIED &&
Packit Service 20376f
			delta->status != GIT_DELTA_RENAMED &&
Packit Service 20376f
			(delta->status != GIT_DELTA_MODIFIED || actually_split))
Packit Service 20376f
			delta->similarity = 0;
Packit Service 20376f
Packit Service 20376f
		/* insert into new list */
Packit Service 20376f
		if (git_vector_insert(&onto, delta) < 0)
Packit Service 20376f
			goto on_error;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	/* cannot return an error past this point */
Packit Service 20376f
Packit Service 20376f
	/* free deltas from old list that didn't make it to the new one */
Packit Service 20376f
	git_vector_foreach(&diff->deltas, i, delta) {
Packit Service 20376f
		if ((delta->flags & GIT_DIFF_FLAG__TO_DELETE) != 0)
Packit Service 20376f
			git__free(delta);
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	/* swap new delta list into place */
Packit Service 20376f
	git_vector_swap(&diff->deltas, &onto);
Packit Service 20376f
	git_vector_free(&onto);
Packit Service 20376f
	git_vector_sort(&diff->deltas);
Packit Service 20376f
Packit Service 20376f
	return 0;
Packit Service 20376f
Packit Service 20376f
on_error:
Packit Service 20376f
	git_vector_free_deep(&onto);
Packit Service 20376f
Packit Service 20376f
	return -1;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
GIT_INLINE(git_diff_file *) similarity_get_file(git_diff *diff, size_t idx)
Packit Service 20376f
{
Packit Service 20376f
	git_diff_delta *delta = git_vector_get(&diff->deltas, idx / 2);
Packit Service 20376f
	return (idx & 1) ? &delta->new_file : &delta->old_file;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
typedef struct {
Packit Service 20376f
	size_t idx;
Packit Service 20376f
	git_iterator_type_t src;
Packit Service 20376f
	git_repository *repo;
Packit Service 20376f
	git_diff_file *file;
Packit Service 20376f
	git_buf data;
Packit Service 20376f
	git_odb_object *odb_obj;
Packit Service 20376f
	git_blob *blob;
Packit Service 20376f
} similarity_info;
Packit Service 20376f
Packit Service 20376f
static int similarity_init(
Packit Service 20376f
	similarity_info *info, git_diff *diff, size_t file_idx)
Packit Service 20376f
{
Packit Service 20376f
	info->idx  = file_idx;
Packit Service 20376f
	info->src  = (file_idx & 1) ? diff->new_src : diff->old_src;
Packit Service 20376f
	info->repo = diff->repo;
Packit Service 20376f
	info->file = similarity_get_file(diff, file_idx);
Packit Service 20376f
	info->odb_obj = NULL;
Packit Service 20376f
	info->blob = NULL;
Packit Service 20376f
	git_buf_init(&info->data, 0);
Packit Service 20376f
Packit Service 20376f
	if (info->file->size > 0 || info->src == GIT_ITERATOR_TYPE_WORKDIR)
Packit Service 20376f
		return 0;
Packit Service 20376f
Packit Service 20376f
	return git_diff_file__resolve_zero_size(
Packit Service 20376f
		info->file, &info->odb_obj, info->repo);
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static int similarity_sig(
Packit Service 20376f
	similarity_info *info,
Packit Service 20376f
	const git_diff_find_options *opts,
Packit Service 20376f
	void **cache)
Packit Service 20376f
{
Packit Service 20376f
	int error = 0;
Packit Service 20376f
	git_diff_file *file = info->file;
Packit Service 20376f
Packit Service 20376f
	if (info->src == GIT_ITERATOR_TYPE_WORKDIR) {
Packit Service 20376f
		if ((error = git_buf_joinpath(
Packit Service 20376f
			&info->data, git_repository_workdir(info->repo), file->path)) < 0)
Packit Service 20376f
			return error;
Packit Service 20376f
Packit Service 20376f
		/* if path is not a regular file, just skip this item */
Packit Service 20376f
		if (!git_path_isfile(info->data.ptr))
Packit Service 20376f
			return 0;
Packit Service 20376f
Packit Service 20376f
		/* TODO: apply wd-to-odb filters to file data if necessary */
Packit Service 20376f
Packit Service 20376f
		error = opts->metric->file_signature(
Packit Service 20376f
			&cache[info->idx], info->file,
Packit Service 20376f
			info->data.ptr, opts->metric->payload);
Packit Service 20376f
	} else {
Packit Service 20376f
		/* if we didn't initially know the size, we might have an odb_obj
Packit Service 20376f
		 * around from earlier, so convert that, otherwise load the blob now
Packit Service 20376f
		 */
Packit Service 20376f
		if (info->odb_obj != NULL)
Packit Service 20376f
			error = git_object__from_odb_object(
Packit Service 20376f
				(git_object **)&info->blob, info->repo,
Packit Service 20376f
				info->odb_obj, GIT_OBJ_BLOB);
Packit Service 20376f
		else
Packit Service 20376f
			error = git_blob_lookup(&info->blob, info->repo, &file->id);
Packit Service 20376f
Packit Service 20376f
		if (error < 0) {
Packit Service 20376f
			/* if lookup fails, just skip this item in similarity calc */
Packit Service 20376f
			giterr_clear();
Packit Service 20376f
		} else {
Packit Service 20376f
			size_t sz;
Packit Service 20376f
Packit Service 20376f
			/* index size may not be actual blob size if filtered */
Packit Service 20376f
			if (file->size != git_blob_rawsize(info->blob))
Packit Service 20376f
				file->size = git_blob_rawsize(info->blob);
Packit Service 20376f
Packit Service 20376f
			sz = (size_t)(git__is_sizet(file->size) ? file->size : -1);
Packit Service 20376f
Packit Service 20376f
			error = opts->metric->buffer_signature(
Packit Service 20376f
				&cache[info->idx], info->file,
Packit Service 20376f
				git_blob_rawcontent(info->blob), sz, opts->metric->payload);
Packit Service 20376f
		}
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	return error;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static void similarity_unload(similarity_info *info)
Packit Service 20376f
{
Packit Service 20376f
	if (info->odb_obj)
Packit Service 20376f
		git_odb_object_free(info->odb_obj);
Packit Service 20376f
Packit Service 20376f
	if (info->blob)
Packit Service 20376f
		git_blob_free(info->blob);
Packit Service 20376f
	else
Packit Service 20376f
		git_buf_free(&info->data);
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
#define FLAG_SET(opts,flag_name) (((opts)->flags & flag_name) != 0)
Packit Service 20376f
Packit Service 20376f
/* - score < 0 means files cannot be compared
Packit Service 20376f
 * - score >= 100 means files are exact match
Packit Service 20376f
 * - score == 0 means files are completely different
Packit Service 20376f
 */
Packit Service 20376f
static int similarity_measure(
Packit Service 20376f
	int *score,
Packit Service 20376f
	git_diff *diff,
Packit Service 20376f
	const git_diff_find_options *opts,
Packit Service 20376f
	void **cache,
Packit Service 20376f
	size_t a_idx,
Packit Service 20376f
	size_t b_idx)
Packit Service 20376f
{
Packit Service 20376f
	git_diff_file *a_file = similarity_get_file(diff, a_idx);
Packit Service 20376f
	git_diff_file *b_file = similarity_get_file(diff, b_idx);
Packit Service 20376f
	bool exact_match = FLAG_SET(opts, GIT_DIFF_FIND_EXACT_MATCH_ONLY);
Packit Service 20376f
	int error = 0;
Packit Service 20376f
	similarity_info a_info, b_info;
Packit Service 20376f
Packit Service 20376f
	*score = -1;
Packit Service 20376f
Packit Service 20376f
	/* don't try to compare things that aren't files */
Packit Service 20376f
	if (!GIT_MODE_ISBLOB(a_file->mode) || !GIT_MODE_ISBLOB(b_file->mode))
Packit Service 20376f
		return 0;
Packit Service 20376f
Packit Service 20376f
	/* if exact match is requested, force calculation of missing OIDs now */
Packit Service 20376f
	if (exact_match) {
Packit Service 20376f
		if (git_oid_iszero(&a_file->id) &&
Packit Service 20376f
			diff->old_src == GIT_ITERATOR_TYPE_WORKDIR &&
Packit Service 20376f
			!git_diff__oid_for_file(&a_file->id,
Packit Service 20376f
				diff, a_file->path, a_file->mode, a_file->size))
Packit Service 20376f
			a_file->flags |= GIT_DIFF_FLAG_VALID_ID;
Packit Service 20376f
Packit Service 20376f
		if (git_oid_iszero(&b_file->id) &&
Packit Service 20376f
			diff->new_src == GIT_ITERATOR_TYPE_WORKDIR &&
Packit Service 20376f
			!git_diff__oid_for_file(&b_file->id,
Packit Service 20376f
				diff, b_file->path, b_file->mode, b_file->size))
Packit Service 20376f
			b_file->flags |= GIT_DIFF_FLAG_VALID_ID;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	/* check OID match as a quick test */
Packit Service 20376f
	if (git_oid__cmp(&a_file->id, &b_file->id) == 0) {
Packit Service 20376f
		*score = 100;
Packit Service 20376f
		return 0;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	/* don't calculate signatures if we are doing exact match */
Packit Service 20376f
	if (exact_match) {
Packit Service 20376f
		*score = 0;
Packit Service 20376f
		return 0;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	memset(&a_info, 0, sizeof(a_info));
Packit Service 20376f
	memset(&b_info, 0, sizeof(b_info));
Packit Service 20376f
Packit Service 20376f
	/* set up similarity data (will try to update missing file sizes) */
Packit Service 20376f
	if (!cache[a_idx] && (error = similarity_init(&a_info, diff, a_idx)) < 0)
Packit Service 20376f
		return error;
Packit Service 20376f
	if (!cache[b_idx] && (error = similarity_init(&b_info, diff, b_idx)) < 0)
Packit Service 20376f
		goto cleanup;
Packit Service 20376f
Packit Service 20376f
	/* check if file sizes are nowhere near each other */
Packit Service 20376f
	if (a_file->size > 127 &&
Packit Service 20376f
		b_file->size > 127 &&
Packit Service 20376f
		(a_file->size > (b_file->size << 3) ||
Packit Service 20376f
		 b_file->size > (a_file->size << 3)))
Packit Service 20376f
		goto cleanup;
Packit Service 20376f
Packit Service 20376f
	/* update signature cache if needed */
Packit Service 20376f
	if (!cache[a_idx]) {
Packit Service 20376f
		if ((error = similarity_sig(&a_info, opts, cache)) < 0)
Packit Service 20376f
			goto cleanup;
Packit Service 20376f
	}
Packit Service 20376f
	if (!cache[b_idx]) {
Packit Service 20376f
		if ((error = similarity_sig(&b_info, opts, cache)) < 0)
Packit Service 20376f
			goto cleanup;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	/* calculate similarity provided that the metric choose to process
Packit Service 20376f
	 * both the a and b files (some may not if file is too big, etc).
Packit Service 20376f
	 */
Packit Service 20376f
	if (cache[a_idx] && cache[b_idx])
Packit Service 20376f
		error = opts->metric->similarity(
Packit Service 20376f
			score, cache[a_idx], cache[b_idx], opts->metric->payload);
Packit Service 20376f
Packit Service 20376f
cleanup:
Packit Service 20376f
	similarity_unload(&a_info);
Packit Service 20376f
	similarity_unload(&b_info);
Packit Service 20376f
Packit Service 20376f
	return error;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static int calc_self_similarity(
Packit Service 20376f
	git_diff *diff,
Packit Service 20376f
	const git_diff_find_options *opts,
Packit Service 20376f
	size_t delta_idx,
Packit Service 20376f
	void **cache)
Packit Service 20376f
{
Packit Service 20376f
	int error, similarity = -1;
Packit Service 20376f
	git_diff_delta *delta = GIT_VECTOR_GET(&diff->deltas, delta_idx);
Packit Service 20376f
Packit Service 20376f
	if ((delta->flags & GIT_DIFF_FLAG__HAS_SELF_SIMILARITY) != 0)
Packit Service 20376f
		return 0;
Packit Service 20376f
Packit Service 20376f
	error = similarity_measure(
Packit Service 20376f
		&similarity, diff, opts, cache, 2 * delta_idx, 2 * delta_idx + 1);
Packit Service 20376f
	if (error < 0)
Packit Service 20376f
		return error;
Packit Service 20376f
Packit Service 20376f
	if (similarity >= 0) {
Packit Service 20376f
		delta->similarity = (uint16_t)similarity;
Packit Service 20376f
		delta->flags |= GIT_DIFF_FLAG__HAS_SELF_SIMILARITY;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	return 0;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static bool is_rename_target(
Packit Service 20376f
	git_diff *diff,
Packit Service 20376f
	const git_diff_find_options *opts,
Packit Service 20376f
	size_t delta_idx,
Packit Service 20376f
	void **cache)
Packit Service 20376f
{
Packit Service 20376f
	git_diff_delta *delta = GIT_VECTOR_GET(&diff->deltas, delta_idx);
Packit Service 20376f
Packit Service 20376f
	/* skip things that aren't plain blobs */
Packit Service 20376f
	if (!GIT_MODE_ISBLOB(delta->new_file.mode))
Packit Service 20376f
		return false;
Packit Service 20376f
Packit Service 20376f
	/* only consider ADDED, RENAMED, COPIED, and split MODIFIED as
Packit Service 20376f
	 * targets; maybe include UNTRACKED if requested.
Packit Service 20376f
	 */
Packit Service 20376f
	switch (delta->status) {
Packit Service 20376f
	case GIT_DELTA_UNMODIFIED:
Packit Service 20376f
	case GIT_DELTA_DELETED:
Packit Service 20376f
	case GIT_DELTA_IGNORED:
Packit Service 20376f
	case GIT_DELTA_CONFLICTED:
Packit Service 20376f
		return false;
Packit Service 20376f
Packit Service 20376f
	case GIT_DELTA_MODIFIED:
Packit Service 20376f
		if (!FLAG_SET(opts, GIT_DIFF_FIND_REWRITES) &&
Packit Service 20376f
			!FLAG_SET(opts, GIT_DIFF_FIND_RENAMES_FROM_REWRITES))
Packit Service 20376f
			return false;
Packit Service 20376f
Packit Service 20376f
		if (calc_self_similarity(diff, opts, delta_idx, cache) < 0)
Packit Service 20376f
			return false;
Packit Service 20376f
Packit Service 20376f
		if (FLAG_SET(opts, GIT_DIFF_BREAK_REWRITES) &&
Packit Service 20376f
			delta->similarity < opts->break_rewrite_threshold) {
Packit Service 20376f
			delta->flags |= GIT_DIFF_FLAG__TO_SPLIT;
Packit Service 20376f
			break;
Packit Service 20376f
		}
Packit Service 20376f
		if (FLAG_SET(opts, GIT_DIFF_FIND_RENAMES_FROM_REWRITES) &&
Packit Service 20376f
			delta->similarity < opts->rename_from_rewrite_threshold) {
Packit Service 20376f
			delta->flags |= GIT_DIFF_FLAG__TO_SPLIT;
Packit Service 20376f
			break;
Packit Service 20376f
		}
Packit Service 20376f
Packit Service 20376f
		return false;
Packit Service 20376f
Packit Service 20376f
	case GIT_DELTA_UNTRACKED:
Packit Service 20376f
		if (!FLAG_SET(opts, GIT_DIFF_FIND_FOR_UNTRACKED))
Packit Service 20376f
			return false;
Packit Service 20376f
		break;
Packit Service 20376f
Packit Service 20376f
	default: /* all other status values should be checked */
Packit Service 20376f
		break;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	delta->flags |= GIT_DIFF_FLAG__IS_RENAME_TARGET;
Packit Service 20376f
	return true;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static bool is_rename_source(
Packit Service 20376f
	git_diff *diff,
Packit Service 20376f
	const git_diff_find_options *opts,
Packit Service 20376f
	size_t delta_idx,
Packit Service 20376f
	void **cache)
Packit Service 20376f
{
Packit Service 20376f
	git_diff_delta *delta = GIT_VECTOR_GET(&diff->deltas, delta_idx);
Packit Service 20376f
Packit Service 20376f
	/* skip things that aren't blobs */
Packit Service 20376f
	if (!GIT_MODE_ISBLOB(delta->old_file.mode))
Packit Service 20376f
		return false;
Packit Service 20376f
Packit Service 20376f
	switch (delta->status) {
Packit Service 20376f
	case GIT_DELTA_ADDED:
Packit Service 20376f
	case GIT_DELTA_UNTRACKED:
Packit Service 20376f
	case GIT_DELTA_UNREADABLE:
Packit Service 20376f
	case GIT_DELTA_IGNORED:
Packit Service 20376f
	case GIT_DELTA_CONFLICTED:
Packit Service 20376f
		return false;
Packit Service 20376f
Packit Service 20376f
	case GIT_DELTA_DELETED:
Packit Service 20376f
	case GIT_DELTA_TYPECHANGE:
Packit Service 20376f
		break;
Packit Service 20376f
Packit Service 20376f
	case GIT_DELTA_UNMODIFIED:
Packit Service 20376f
		if (!FLAG_SET(opts, GIT_DIFF_FIND_COPIES_FROM_UNMODIFIED))
Packit Service 20376f
			return false;
Packit Service 20376f
		if (FLAG_SET(opts, GIT_DIFF_FIND_REMOVE_UNMODIFIED))
Packit Service 20376f
			delta->flags |= GIT_DIFF_FLAG__TO_DELETE;
Packit Service 20376f
		break;
Packit Service 20376f
Packit Service 20376f
	default: /* MODIFIED, RENAMED, COPIED */
Packit Service 20376f
		/* if we're finding copies, this could be a source */
Packit Service 20376f
		if (FLAG_SET(opts, GIT_DIFF_FIND_COPIES))
Packit Service 20376f
			break;
Packit Service 20376f
Packit Service 20376f
		/* otherwise, this is only a source if we can split it */
Packit Service 20376f
		if (!FLAG_SET(opts, GIT_DIFF_FIND_REWRITES) &&
Packit Service 20376f
			!FLAG_SET(opts, GIT_DIFF_FIND_RENAMES_FROM_REWRITES))
Packit Service 20376f
			return false;
Packit Service 20376f
Packit Service 20376f
		if (calc_self_similarity(diff, opts, delta_idx, cache) < 0)
Packit Service 20376f
			return false;
Packit Service 20376f
Packit Service 20376f
		if (FLAG_SET(opts, GIT_DIFF_BREAK_REWRITES) &&
Packit Service 20376f
			delta->similarity < opts->break_rewrite_threshold) {
Packit Service 20376f
			delta->flags |= GIT_DIFF_FLAG__TO_SPLIT;
Packit Service 20376f
			break;
Packit Service 20376f
		}
Packit Service 20376f
Packit Service 20376f
		if (FLAG_SET(opts, GIT_DIFF_FIND_RENAMES_FROM_REWRITES) &&
Packit Service 20376f
			delta->similarity < opts->rename_from_rewrite_threshold)
Packit Service 20376f
			break;
Packit Service 20376f
Packit Service 20376f
		return false;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	delta->flags |= GIT_DIFF_FLAG__IS_RENAME_SOURCE;
Packit Service 20376f
	return true;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
GIT_INLINE(bool) delta_is_split(git_diff_delta *delta)
Packit Service 20376f
{
Packit Service 20376f
	return (delta->status == GIT_DELTA_TYPECHANGE ||
Packit Service 20376f
			(delta->flags & GIT_DIFF_FLAG__TO_SPLIT) != 0);
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
GIT_INLINE(bool) delta_is_new_only(git_diff_delta *delta)
Packit Service 20376f
{
Packit Service 20376f
	return (delta->status == GIT_DELTA_ADDED ||
Packit Service 20376f
			delta->status == GIT_DELTA_UNTRACKED ||
Packit Service 20376f
			delta->status == GIT_DELTA_UNREADABLE ||
Packit Service 20376f
			delta->status == GIT_DELTA_IGNORED);
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
GIT_INLINE(void) delta_make_rename(
Packit Service 20376f
	git_diff_delta *to, const git_diff_delta *from, uint16_t similarity)
Packit Service 20376f
{
Packit Service 20376f
	to->status     = GIT_DELTA_RENAMED;
Packit Service 20376f
	to->similarity = similarity;
Packit Service 20376f
	to->nfiles     = 2;
Packit Service 20376f
	memcpy(&to->old_file, &from->old_file, sizeof(to->old_file));
Packit Service 20376f
	to->flags &= ~GIT_DIFF_FLAG__TO_SPLIT;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
typedef struct {
Packit Service 20376f
	size_t   idx;
Packit Service 20376f
	uint16_t similarity;
Packit Service 20376f
} diff_find_match;
Packit Service 20376f
Packit Service 20376f
int git_diff_find_similar(
Packit Service 20376f
	git_diff *diff,
Packit Service 20376f
	const git_diff_find_options *given_opts)
Packit Service 20376f
{
Packit Service 20376f
	size_t s, t;
Packit Service 20376f
	int error = 0, result;
Packit Service 20376f
	uint16_t similarity;
Packit Service 20376f
	git_diff_delta *src, *tgt;
Packit Service 20376f
	git_diff_find_options opts = GIT_DIFF_FIND_OPTIONS_INIT;
Packit Service 20376f
	size_t num_deltas, num_srcs = 0, num_tgts = 0;
Packit Service 20376f
	size_t tried_srcs = 0, tried_tgts = 0;
Packit Service 20376f
	size_t num_rewrites = 0, num_updates = 0, num_bumped = 0;
Packit Service 20376f
	size_t sigcache_size;
Packit Service 20376f
	void **sigcache = NULL; /* cache of similarity metric file signatures */
Packit Service 20376f
	diff_find_match *tgt2src = NULL;
Packit Service 20376f
	diff_find_match *src2tgt = NULL;
Packit Service 20376f
	diff_find_match *tgt2src_copy = NULL;
Packit Service 20376f
	diff_find_match *best_match;
Packit Service 20376f
	git_diff_file swap;
Packit Service 20376f
Packit Service 20376f
	if ((error = normalize_find_opts(diff, &opts, given_opts)) < 0)
Packit Service 20376f
		return error;
Packit Service 20376f
Packit Service 20376f
	num_deltas = diff->deltas.length;
Packit Service 20376f
Packit Service 20376f
	/* TODO: maybe abort if deltas.length > rename_limit ??? */
Packit Service 20376f
	if (!git__is_uint32(num_deltas))
Packit Service 20376f
		goto cleanup;
Packit Service 20376f
Packit Service 20376f
	/* No flags set; nothing to do */
Packit Service 20376f
	if ((opts.flags & GIT_DIFF_FIND_ALL) == 0)
Packit Service 20376f
		goto cleanup;
Packit Service 20376f
Packit Service 20376f
	GITERR_CHECK_ALLOC_MULTIPLY(&sigcache_size, num_deltas, 2);
Packit Service 20376f
	sigcache = git__calloc(sigcache_size, sizeof(void *));
Packit Service 20376f
	GITERR_CHECK_ALLOC(sigcache);
Packit Service 20376f
Packit Service 20376f
	/* Label rename sources and targets
Packit Service 20376f
	 *
Packit Service 20376f
	 * This will also set self-similarity scores for MODIFIED files and
Packit Service 20376f
	 * mark them for splitting if break-rewrites is enabled
Packit Service 20376f
	 */
Packit Service 20376f
	git_vector_foreach(&diff->deltas, t, tgt) {
Packit Service 20376f
		if (is_rename_source(diff, &opts, t, sigcache))
Packit Service 20376f
			++num_srcs;
Packit Service 20376f
Packit Service 20376f
		if (is_rename_target(diff, &opts, t, sigcache))
Packit Service 20376f
			++num_tgts;
Packit Service 20376f
Packit Service 20376f
		if ((tgt->flags & GIT_DIFF_FLAG__TO_SPLIT) != 0)
Packit Service 20376f
			num_rewrites++;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	/* if there are no candidate srcs or tgts, we're done */
Packit Service 20376f
	if (!num_srcs || !num_tgts)
Packit Service 20376f
		goto cleanup;
Packit Service 20376f
Packit Service 20376f
	src2tgt = git__calloc(num_deltas, sizeof(diff_find_match));
Packit Service 20376f
	GITERR_CHECK_ALLOC(src2tgt);
Packit Service 20376f
	tgt2src = git__calloc(num_deltas, sizeof(diff_find_match));
Packit Service 20376f
	GITERR_CHECK_ALLOC(tgt2src);
Packit Service 20376f
Packit Service 20376f
	if (FLAG_SET(&opts, GIT_DIFF_FIND_COPIES)) {
Packit Service 20376f
		tgt2src_copy = git__calloc(num_deltas, sizeof(diff_find_match));
Packit Service 20376f
		GITERR_CHECK_ALLOC(tgt2src_copy);
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	/*
Packit Service 20376f
	 * Find best-fit matches for rename / copy candidates
Packit Service 20376f
	 */
Packit Service 20376f
Packit Service 20376f
find_best_matches:
Packit Service 20376f
	tried_tgts = num_bumped = 0;
Packit Service 20376f
Packit Service 20376f
	git_vector_foreach(&diff->deltas, t, tgt) {
Packit Service 20376f
		/* skip things that are not rename targets */
Packit Service 20376f
		if ((tgt->flags & GIT_DIFF_FLAG__IS_RENAME_TARGET) == 0)
Packit Service 20376f
			continue;
Packit Service 20376f
Packit Service 20376f
		tried_srcs = 0;
Packit Service 20376f
Packit Service 20376f
		git_vector_foreach(&diff->deltas, s, src) {
Packit Service 20376f
			/* skip things that are not rename sources */
Packit Service 20376f
			if ((src->flags & GIT_DIFF_FLAG__IS_RENAME_SOURCE) == 0)
Packit Service 20376f
				continue;
Packit Service 20376f
Packit Service 20376f
			/* calculate similarity for this pair and find best match */
Packit Service 20376f
			if (s == t)
Packit Service 20376f
				result = -1; /* don't measure self-similarity here */
Packit Service 20376f
			else if ((error = similarity_measure(
Packit Service 20376f
				&result, diff, &opts, sigcache, 2 * s, 2 * t + 1)) < 0)
Packit Service 20376f
				goto cleanup;
Packit Service 20376f
Packit Service 20376f
			if (result < 0)
Packit Service 20376f
				continue;
Packit Service 20376f
			similarity = (uint16_t)result;
Packit Service 20376f
Packit Service 20376f
			/* is this a better rename? */
Packit Service 20376f
			if (tgt2src[t].similarity < similarity &&
Packit Service 20376f
				src2tgt[s].similarity < similarity)
Packit Service 20376f
			{
Packit Service 20376f
				/* eject old mapping */
Packit Service 20376f
				if (src2tgt[s].similarity > 0) {
Packit Service 20376f
					tgt2src[src2tgt[s].idx].similarity = 0;
Packit Service 20376f
					num_bumped++;
Packit Service 20376f
				}
Packit Service 20376f
				if (tgt2src[t].similarity > 0) {
Packit Service 20376f
					src2tgt[tgt2src[t].idx].similarity = 0;
Packit Service 20376f
					num_bumped++;
Packit Service 20376f
				}
Packit Service 20376f
Packit Service 20376f
				/* write new mapping */
Packit Service 20376f
				tgt2src[t].idx = s;
Packit Service 20376f
				tgt2src[t].similarity = similarity;
Packit Service 20376f
				src2tgt[s].idx = t;
Packit Service 20376f
				src2tgt[s].similarity = similarity;
Packit Service 20376f
			}
Packit Service 20376f
Packit Service 20376f
			/* keep best absolute match for copies */
Packit Service 20376f
			if (tgt2src_copy != NULL &&
Packit Service 20376f
				tgt2src_copy[t].similarity < similarity)
Packit Service 20376f
			{
Packit Service 20376f
				tgt2src_copy[t].idx = s;
Packit Service 20376f
				tgt2src_copy[t].similarity = similarity;
Packit Service 20376f
			}
Packit Service 20376f
Packit Service 20376f
			if (++tried_srcs >= num_srcs)
Packit Service 20376f
				break;
Packit Service 20376f
Packit Service 20376f
			/* cap on maximum targets we'll examine (per "tgt" file) */
Packit Service 20376f
			if (tried_srcs > opts.rename_limit)
Packit Service 20376f
				break;
Packit Service 20376f
		}
Packit Service 20376f
Packit Service 20376f
		if (++tried_tgts >= num_tgts)
Packit Service 20376f
			break;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	if (num_bumped > 0) /* try again if we bumped some items */
Packit Service 20376f
		goto find_best_matches;
Packit Service 20376f
Packit Service 20376f
	/*
Packit Service 20376f
	 * Rewrite the diffs with renames / copies
Packit Service 20376f
	 */
Packit Service 20376f
Packit Service 20376f
	git_vector_foreach(&diff->deltas, t, tgt) {
Packit Service 20376f
		/* skip things that are not rename targets */
Packit Service 20376f
		if ((tgt->flags & GIT_DIFF_FLAG__IS_RENAME_TARGET) == 0)
Packit Service 20376f
			continue;
Packit Service 20376f
Packit Service 20376f
		/* check if this delta was the target of a similarity */
Packit Service 20376f
		if (tgt2src[t].similarity)
Packit Service 20376f
			best_match = &tgt2src[t];
Packit Service 20376f
		else if (tgt2src_copy && tgt2src_copy[t].similarity)
Packit Service 20376f
			best_match = &tgt2src_copy[t];
Packit Service 20376f
		else
Packit Service 20376f
			continue;
Packit Service 20376f
Packit Service 20376f
		s = best_match->idx;
Packit Service 20376f
		src = GIT_VECTOR_GET(&diff->deltas, s);
Packit Service 20376f
Packit Service 20376f
		/* possible scenarios:
Packit Service 20376f
		 * 1. from DELETE to ADD/UNTRACK/IGNORE = RENAME
Packit Service 20376f
		 * 2. from DELETE to SPLIT/TYPECHANGE = RENAME + DELETE
Packit Service 20376f
		 * 3. from SPLIT/TYPECHANGE to ADD/UNTRACK/IGNORE = ADD + RENAME
Packit Service 20376f
		 * 4. from SPLIT/TYPECHANGE to SPLIT/TYPECHANGE = RENAME + SPLIT
Packit Service 20376f
		 * 5. from OTHER to ADD/UNTRACK/IGNORE = OTHER + COPY
Packit Service 20376f
		 */
Packit Service 20376f
Packit Service 20376f
		if (src->status == GIT_DELTA_DELETED) {
Packit Service 20376f
Packit Service 20376f
			if (delta_is_new_only(tgt)) {
Packit Service 20376f
Packit Service 20376f
				if (best_match->similarity < opts.rename_threshold)
Packit Service 20376f
					continue;
Packit Service 20376f
Packit Service 20376f
				delta_make_rename(tgt, src, best_match->similarity);
Packit Service 20376f
Packit Service 20376f
				src->flags |= GIT_DIFF_FLAG__TO_DELETE;
Packit Service 20376f
				num_rewrites++;
Packit Service 20376f
			} else {
Packit Service 20376f
				assert(delta_is_split(tgt));
Packit Service 20376f
Packit Service 20376f
				if (best_match->similarity < opts.rename_from_rewrite_threshold)
Packit Service 20376f
					continue;
Packit Service 20376f
Packit Service 20376f
				memcpy(&swap, &tgt->old_file, sizeof(swap));
Packit Service 20376f
Packit Service 20376f
				delta_make_rename(tgt, src, best_match->similarity);
Packit Service 20376f
				num_rewrites--;
Packit Service 20376f
Packit Service 20376f
				assert(src->status == GIT_DELTA_DELETED);
Packit Service 20376f
				memcpy(&src->old_file, &swap, sizeof(src->old_file));
Packit Service 20376f
				memset(&src->new_file, 0, sizeof(src->new_file));
Packit Service 20376f
				src->new_file.path = src->old_file.path;
Packit Service 20376f
				src->new_file.flags |= GIT_DIFF_FLAG_VALID_ID;
Packit Service 20376f
Packit Service 20376f
				num_updates++;
Packit Service 20376f
Packit Service 20376f
				if (src2tgt[t].similarity > 0 && src2tgt[t].idx > t) {
Packit Service 20376f
					/* what used to be at src t is now at src s */
Packit Service 20376f
					tgt2src[src2tgt[t].idx].idx = s;
Packit Service 20376f
				}
Packit Service 20376f
			}
Packit Service 20376f
		}
Packit Service 20376f
Packit Service 20376f
		else if (delta_is_split(src)) {
Packit Service 20376f
Packit Service 20376f
			if (delta_is_new_only(tgt)) {
Packit Service 20376f
Packit Service 20376f
				if (best_match->similarity < opts.rename_threshold)
Packit Service 20376f
					continue;
Packit Service 20376f
Packit Service 20376f
				delta_make_rename(tgt, src, best_match->similarity);
Packit Service 20376f
Packit Service 20376f
				src->status = (diff->new_src == GIT_ITERATOR_TYPE_WORKDIR) ?
Packit Service 20376f
					GIT_DELTA_UNTRACKED : GIT_DELTA_ADDED;
Packit Service 20376f
				src->nfiles = 1;
Packit Service 20376f
				memset(&src->old_file, 0, sizeof(src->old_file));
Packit Service 20376f
				src->old_file.path = src->new_file.path;
Packit Service 20376f
				src->old_file.flags |= GIT_DIFF_FLAG_VALID_ID;
Packit Service 20376f
Packit Service 20376f
				src->flags &= ~GIT_DIFF_FLAG__TO_SPLIT;
Packit Service 20376f
				num_rewrites--;
Packit Service 20376f
Packit Service 20376f
				num_updates++;
Packit Service 20376f
			} else {
Packit Service 20376f
				assert(delta_is_split(src));
Packit Service 20376f
Packit Service 20376f
				if (best_match->similarity < opts.rename_from_rewrite_threshold)
Packit Service 20376f
					continue;
Packit Service 20376f
Packit Service 20376f
				memcpy(&swap, &tgt->old_file, sizeof(swap));
Packit Service 20376f
Packit Service 20376f
				delta_make_rename(tgt, src, best_match->similarity);
Packit Service 20376f
				num_rewrites--;
Packit Service 20376f
				num_updates++;
Packit Service 20376f
Packit Service 20376f
				memcpy(&src->old_file, &swap, sizeof(src->old_file));
Packit Service 20376f
Packit Service 20376f
				/* if we've just swapped the new element into the correct
Packit Service 20376f
				 * place, clear the SPLIT flag
Packit Service 20376f
				 */
Packit Service 20376f
				if (tgt2src[s].idx == t &&
Packit Service 20376f
					tgt2src[s].similarity >
Packit Service 20376f
					opts.rename_from_rewrite_threshold) {
Packit Service 20376f
					src->status     = GIT_DELTA_RENAMED;
Packit Service 20376f
					src->similarity = tgt2src[s].similarity;
Packit Service 20376f
					tgt2src[s].similarity = 0;
Packit Service 20376f
					src->flags &= ~GIT_DIFF_FLAG__TO_SPLIT;
Packit Service 20376f
					num_rewrites--;
Packit Service 20376f
				}
Packit Service 20376f
				/* otherwise, if we just overwrote a source, update mapping */
Packit Service 20376f
				else if (src2tgt[t].similarity > 0 && src2tgt[t].idx > t) {
Packit Service 20376f
					/* what used to be at src t is now at src s */
Packit Service 20376f
					tgt2src[src2tgt[t].idx].idx = s;
Packit Service 20376f
				}
Packit Service 20376f
Packit Service 20376f
				num_updates++;
Packit Service 20376f
			}
Packit Service 20376f
		}
Packit Service 20376f
Packit Service 20376f
		else if (FLAG_SET(&opts, GIT_DIFF_FIND_COPIES)) {
Packit Service 20376f
			if (tgt2src_copy[t].similarity < opts.copy_threshold)
Packit Service 20376f
				continue;
Packit Service 20376f
Packit Service 20376f
			/* always use best possible source for copy */
Packit Service 20376f
			best_match = &tgt2src_copy[t];
Packit Service 20376f
			src = GIT_VECTOR_GET(&diff->deltas, best_match->idx);
Packit Service 20376f
Packit Service 20376f
			if (delta_is_split(tgt)) {
Packit Service 20376f
				error = insert_delete_side_of_split(diff, &diff->deltas, tgt);
Packit Service 20376f
				if (error < 0)
Packit Service 20376f
					goto cleanup;
Packit Service 20376f
				num_rewrites--;
Packit Service 20376f
			}
Packit Service 20376f
Packit Service 20376f
			if (!delta_is_split(tgt) && !delta_is_new_only(tgt))
Packit Service 20376f
				continue;
Packit Service 20376f
Packit Service 20376f
			tgt->status     = GIT_DELTA_COPIED;
Packit Service 20376f
			tgt->similarity = best_match->similarity;
Packit Service 20376f
			tgt->nfiles     = 2;
Packit Service 20376f
			memcpy(&tgt->old_file, &src->old_file, sizeof(tgt->old_file));
Packit Service 20376f
			tgt->flags &= ~GIT_DIFF_FLAG__TO_SPLIT;
Packit Service 20376f
Packit Service 20376f
			num_updates++;
Packit Service 20376f
		}
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	/*
Packit Service 20376f
	 * Actually split and delete entries as needed
Packit Service 20376f
	 */
Packit Service 20376f
Packit Service 20376f
	if (num_rewrites > 0 || num_updates > 0)
Packit Service 20376f
		error = apply_splits_and_deletes(
Packit Service 20376f
			diff, diff->deltas.length - num_rewrites,
Packit Service 20376f
			FLAG_SET(&opts, GIT_DIFF_BREAK_REWRITES) &&
Packit Service 20376f
			!FLAG_SET(&opts, GIT_DIFF_BREAK_REWRITES_FOR_RENAMES_ONLY));
Packit Service 20376f
Packit Service 20376f
cleanup:
Packit Service 20376f
	git__free(tgt2src);
Packit Service 20376f
	git__free(src2tgt);
Packit Service 20376f
	git__free(tgt2src_copy);
Packit Service 20376f
Packit Service 20376f
	if (sigcache) {
Packit Service 20376f
		for (t = 0; t < num_deltas * 2; ++t) {
Packit Service 20376f
			if (sigcache[t] != NULL)
Packit Service 20376f
				opts.metric->free_signature(sigcache[t], opts.metric->payload);
Packit Service 20376f
		}
Packit Service 20376f
		git__free(sigcache);
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	if (!given_opts || !given_opts->metric)
Packit Service 20376f
		git__free(opts.metric);
Packit Service 20376f
Packit Service 20376f
	return error;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
#undef FLAG_SET