X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diffcore-rename.c;h=6a52699f732c76540d71ce1500bd8d838ee8a265;hb=28818ffada5c811b215b8fef7b61f8ae696abd17;hp=81e4d9df3dcb0ba8646fa8f902f6ac918d04bdb7;hpb=a00d7d106aa333c4b4d0095f58e05c0c4621bbc2;p=git.git

diff --git a/diffcore-rename.c b/diffcore-rename.c
index 81e4d9df..6a52699f 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -52,14 +52,15 @@ static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,
 	return &(rename_dst[first]);
 }
 
+/* Table of rename/copy src files */
 static struct diff_rename_src {
 	struct diff_filespec *one;
-	unsigned src_used : 1;
+	unsigned src_stays : 1;
 } *rename_src;
 static int rename_src_nr, rename_src_alloc;
 
-static struct diff_rename_src *locate_rename_src(struct diff_filespec *one,
-						 int insert_ok)
+static struct diff_rename_src *register_rename_src(struct diff_filespec *one,
+						   int src_stays)
 {
 	int first, last;
 
@@ -77,9 +78,7 @@ static struct diff_rename_src *locate_rename_src(struct diff_filespec *one,
 		}
 		first = next+1;
 	}
-	/* not found */
-	if (!insert_ok)
-		return NULL;
+
 	/* insert to make it at "first" */
 	if (rename_src_alloc <= rename_src_nr) {
 		rename_src_alloc = alloc_nr(rename_src_alloc);
@@ -91,7 +90,7 @@ static struct diff_rename_src *locate_rename_src(struct diff_filespec *one,
 		memmove(rename_src + first + 1, rename_src + first,
 			(rename_src_nr - first - 1) * sizeof(*rename_src));
 	rename_src[first].one = one;
-	rename_src[first].src_used = 0;
+	rename_src[first].src_stays = src_stays;
 	return &(rename_src[first]);
 }
 
@@ -100,8 +99,11 @@ static int is_exact_match(struct diff_filespec *src, struct diff_filespec *dst)
 	if (src->sha1_valid && dst->sha1_valid &&
 	    !memcmp(src->sha1, dst->sha1, 20))
 		return 1;
-	if (diff_populate_filespec(src) || diff_populate_filespec(dst))
-		/* this is an error but will be caught downstream */
+	if (diff_populate_filespec(src, 1) || diff_populate_filespec(dst, 1))
+		return 0;
+	if (src->size != dst->size)
+		return 0;
+	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))
@@ -113,7 +115,6 @@ struct diff_score {
 	int src; /* index in rename_src */
 	int dst; /* index in rename_dst */
 	int score;
-	int rank;
 };
 
 static int estimate_similarity(struct diff_filespec *src,
@@ -127,12 +128,15 @@ static int estimate_similarity(struct diff_filespec *src,
 	 * dst, and then some edit has been applied to dst.
 	 *
 	 * Compare them and return how similar they are, representing
-	 * the score as an integer between 0 and 10000, except
-	 * where they match exactly it is considered better than anything
-	 * else.
+	 * the score as an integer between 0 and MAX_SCORE.
+	 *
+	 * When there is an exact match, it is considered a better
+	 * match than anything else; the destination does not even
+	 * call into this function in that case.
 	 */
 	void *delta;
-	unsigned long delta_size, base_size;
+	unsigned long delta_size, base_size, src_copied, literal_added;
+	unsigned long delta_limit;
 	int score;
 
 	/* We deal only with regular files.  Symlink renames are handled
@@ -149,6 +153,7 @@ static int estimate_similarity(struct diff_filespec *src,
 	/* We would not consider edits that change the file size so
 	 * drastically.  delta_size must be smaller than
 	 * (MAX_SCORE-minimum_score)/MAX_SCORE * min(src->size, dst->size).
+	 *
 	 * Note that base_size == 0 case is handled here already
 	 * and the final score computation below would not have a
 	 * divide-by-zero issue.
@@ -156,9 +161,16 @@ static int estimate_similarity(struct diff_filespec *src,
 	if (base_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE)
 		return 0;
 
+	if (diff_populate_filespec(src, 0) || diff_populate_filespec(dst, 0))
+		return 0; /* error but caught downstream */
+
+	delta_limit = base_size * (MAX_SCORE-minimum_score) / MAX_SCORE;
 	delta = diff_delta(src->data, src->size,
 			   dst->data, dst->size,
-			   &delta_size);
+			   &delta_size, delta_limit);
+	if (!delta)
+		/* If delta_limit is exceeded, we have too much differences */
+		return 0;
 
 	/* A delta that has a lot of literal additions would have
 	 * big delta_size no matter what else it does.
@@ -167,10 +179,17 @@ static int estimate_similarity(struct diff_filespec *src,
 		return 0;
 
 	/* Estimate the edit size by interpreting delta. */
-	delta_size = count_delta(delta, delta_size);
-	free(delta);
-	if (delta_size == UINT_MAX)
+	if (count_delta(delta, delta_size, &src_copied, &literal_added)) {
+		free(delta);
 		return 0;
+	}
+	free(delta);
+
+	/* 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
@@ -201,14 +220,13 @@ static void record_rename_pair(struct diff_queue_struct *renq,
 
 	dp = diff_queue(renq, one, two);
 	dp->score = score;
-
-	rename_src[src_index].src_used = 1;
+	dp->source_stays = rename_src[src_index].src_stays;
 	rename_dst[dst_index].pair = dp;
 }
 
 /*
  * We sort the rename similarity matrix with the score, in descending
- * order (more similar first).
+ * order (the most similar first).
  */
 static int score_compare(const void *a_, const void *b_)
 {
@@ -216,24 +234,6 @@ static int score_compare(const void *a_, const void *b_)
 	return b->score - a->score;
 }
 
-int diff_scoreopt_parse(const char *opt)
-{
-	int diglen, num, scale, i;
-	if (opt[0] != '-' || (opt[1] != 'M' && opt[1] != 'C'))
-		return -1; /* that is not a -M nor -C option */
-	diglen = strspn(opt+2, "0123456789");
-	if (diglen == 0 || strlen(opt+2) != diglen)
-		return 0; /* use default */
-	sscanf(opt+2, "%d", &num);
-	for (i = 0, scale = 1; i < diglen; i++)
-		scale *= 10;
-
-	/* user says num divided by scale and we say internally that
-	 * is MAX_SCORE * num / scale.
-	 */
-	return MAX_SCORE * num / scale;
-}
-
 void diffcore_rename(int detect_rename, int minimum_score)
 {
 	struct diff_queue_struct *q = &diff_queued_diff;
@@ -243,7 +243,7 @@ void diffcore_rename(int detect_rename, int minimum_score)
 	int num_create, num_src, dst_cnt;
 
 	if (!minimum_score)
-		minimum_score = DEFAULT_MINIMUM_SCORE;
+		minimum_score = DEFAULT_RENAME_SCORE;
 	renq.queue = NULL;
 	renq.nr = renq.alloc = 0;
 
@@ -254,10 +254,16 @@ void diffcore_rename(int detect_rename, int minimum_score)
 				continue; /* unmerged */
 			else
 				locate_rename_dst(p->two, 1);
-		else if (!DIFF_FILE_VALID(p->two))
-			locate_rename_src(p->one, 1);
-		else if (1 < detect_rename) /* find copy, too */
-			locate_rename_src(p->one, 1);
+		else if (!DIFF_FILE_VALID(p->two)) {
+			/* If the source is a broken "delete", and
+			 * they did not really want to get broken,
+			 * that means the source actually stays.
+			 */
+			int stays = (p->broken_pair && !p->score);
+			register_rename_src(p->one, stays);
+		}
+		else if (detect_rename == DIFF_DETECT_COPY)
+			register_rename_src(p->one, 1);
 	}
 	if (rename_dst_nr == 0)
 		goto cleanup; /* nothing to do */
@@ -281,7 +287,7 @@ void diffcore_rename(int detect_rename, int minimum_score)
 	 * doing the delta matrix altogether.
 	 */
 	if (renq.nr == rename_dst_nr)
-		goto flush_rest;
+		goto cleanup;
 
 	num_create = (rename_dst_nr - renq.nr);
 	num_src = rename_src_nr;
@@ -308,64 +314,90 @@ void diffcore_rename(int detect_rename, int minimum_score)
 		if (dst->pair)
 			continue; /* already done, either exact or fuzzy. */
 		if (mx[i].score < minimum_score)
-			break; /* there is not any more diffs applicable. */
+			break; /* there is no more usable pair. */
 		record_rename_pair(&renq, mx[i].dst, mx[i].src, mx[i].score);
 	}
 	free(mx);
 	diff_debug_queue("done detecting fuzzy", &renq);
 
- flush_rest:
+ cleanup:
 	/* At this point, we have found some renames and copies and they
 	 * are kept in renq.  The original list is still in *q.
-	 *
-	 * Scan the original list and move them into the outq; we will sort
-	 * outq and swap it into the queue supplied to pass that to
-	 * downstream, so we assign the sort keys in this loop.
-	 *
-	 * See comments at the top of record_rename_pair for numbers used
-	 * to assign rename_rank.
 	 */
 	outq.queue = NULL;
 	outq.nr = outq.alloc = 0;
 	for (i = 0; i < q->nr; i++) {
 		struct diff_filepair *p = q->queue[i];
-		struct diff_rename_src *src = locate_rename_src(p->one, 0);
-		struct diff_rename_dst *dst = locate_rename_dst(p->two, 0);
 		struct diff_filepair *pair_to_free = NULL;
 
-		if (dst) {
-			/* creation */
-			if (dst->pair) {
-				/* renq has rename/copy already to produce
-				 * this file, so we do not emit the creation
-				 * record in the output.
-				 */
+		if (!DIFF_FILE_VALID(p->one) && DIFF_FILE_VALID(p->two)) {
+			/*
+			 * Creation
+			 *
+			 * We would output this create record if it has
+			 * not been turned into a rename/copy already.
+			 */
+			struct diff_rename_dst *dst =
+				locate_rename_dst(p->two, 0);
+			if (dst && dst->pair) {
 				diff_q(&outq, dst->pair);
 				pair_to_free = p;
 			}
 			else
-				/* no matching rename/copy source, so record
-				 * this as a creation.
+				/* no matching rename/copy source, so
+				 * record this as a creation.
 				 */
 				diff_q(&outq, p);
 		}
-		else if (!diff_unmodified_pair(p))
-			/* all the other cases need to be recorded as is */
-			diff_q(&outq, p);
-		else {
-			/* unmodified pair needs to be recorded only if
-			 * it is used as the source of rename/copy
+		else if (DIFF_FILE_VALID(p->one) && !DIFF_FILE_VALID(p->two)) {
+			/*
+			 * Deletion
+			 *
+			 * We would output this delete record if:
+			 *
+			 * (1) this is a broken delete and the counterpart
+			 *     broken create remains in the output; or
+			 * (2) this is not a broken delete, and renq does
+			 *     not have a rename/copy to move p->one->path
+			 *     out.
+			 *
+			 * Otherwise, the counterpart broken create
+			 * has been turned into a rename-edit; or
+			 * delete did not have a matching create to
+			 * begin with.
 			 */
-			if (src && src->src_used)
-				diff_q(&outq, p);
+			if (DIFF_PAIR_BROKEN(p)) {
+				/* broken delete */
+				struct diff_rename_dst *dst =
+					locate_rename_dst(p->one, 0);
+				if (dst && dst->pair)
+					/* counterpart is now rename/copy */
+					pair_to_free = p;
+			}
+			else {
+				for (j = 0; j < renq.nr; j++)
+					if (!strcmp(renq.queue[j]->one->path,
+						    p->one->path))
+						break;
+				if (j < renq.nr)
+					/* this path remains */
+					pair_to_free = p;
+			}
+
+			if (pair_to_free)
+				;
 			else
-				pair_to_free = p;
-		}
-		if (pair_to_free) {
-			diff_free_filespec_data(pair_to_free->one);
-			diff_free_filespec_data(pair_to_free->two);
-			free(pair_to_free);
+				diff_q(&outq, p);
 		}
+		else if (!diff_unmodified_pair(p))
+			/* all the usual ones need to be kept */
+			diff_q(&outq, p);
+		else
+			/* no need to keep unmodified pairs */
+			pair_to_free = p;
+
+		if (pair_to_free)
+			diff_free_filepair(pair_to_free);
 	}
 	diff_debug_queue("done copying original", &outq);
 
@@ -374,7 +406,6 @@ void diffcore_rename(int detect_rename, int minimum_score)
 	*q = outq;
 	diff_debug_queue("done collapsing", q);
 
- cleanup:
 	free(rename_dst);
 	rename_dst = NULL;
 	rename_dst_nr = rename_dst_alloc = 0;