diff: round down similarity index

PATCH In review René Scharfe 4 participants 8 messages Jun 15, 2016 1 message not in the archive Documentation

Share & tools

René Scharfe

author

2016-06-15 22:43 UTC #0 lore raw

PATCH 1/1 diff: round down similarity index

Rounding down the printed (dis)similarity index allows us to use "100%" as a special value that indicates complete rewrites and fully equal file contents, respectively.

Signed-off-by Rene Scharfe <[email protected]>

---

The added documentation is only correct if you apply the diffcore-rename patch, too.

 Documentation/diff-format.txt |    7 +++++++
 diff.c                        |   30 +++++++++++++++++++-----------
 2 files changed, 26 insertions(+), 11 deletions(-)

Documentation/diff-format.txt +7 -0

index 18d49d2..0015032 100644
@@ -126,6 +126,13 @@ the file that rename/copy produces, respectively.
     If there is need for such substitution then the whole
     pathname is put in double quotes.
 
+The similarity index is the percentage of unchanged lines, and
+the dissimilarity index is the percentage of changed lines.  It
+is a rounded down integer, followed by a percent sign.  The
+similarity index value of 100% is thus reserved for two equal
+files, while 100% dissimilarity means that no line from the old
+file made it into the new one.
+
 
 combined diff format
 --------------------

diff.c +19 ~~-11~~

index 4aa9bbc..f1db55d 100644
@@ -1813,6 +1813,19 @@ static void diff_fill_sha1_info(struct diff_filespec *one)
 		hashclr(one->sha1);
 }
 
+static int similarity_index(struct diff_filepair *p)
+{
+	int result = p->score * 100.0 / MAX_SCORE;
+
+	/* Paranoia: guard against floating point rounding errors. */
+	if (p->score == MAX_SCORE)
+		result = 100;
+	else if (result == 100)
+		result = 99;
+
+	return result;
+}
+
 static void run_diff(struct diff_filepair *p, struct diff_options *o)
 {
 	const char *pgm = external_diff();

@@ -1847,23 +1860,20 @@ static void run_diff(struct diff_filepair *p, struct diff_options *o)
 				"similarity index %d%%\n"
 				"copy from %s\n"
 				"copy to %s\n",
-				(int)(0.5 + p->score * 100.0/MAX_SCORE),
-				name_munged, other_munged);
+				similarity_index(p), name_munged, other_munged);
 		break;
 	case DIFF_STATUS_RENAMED:
 		len += snprintf(msg + len, sizeof(msg) - len,
 				"similarity index %d%%\n"
 				"rename from %s\n"
 				"rename to %s\n",
-				(int)(0.5 + p->score * 100.0/MAX_SCORE),
-				name_munged, other_munged);
+				similarity_index(p), name_munged, other_munged);
 		break;
 	case DIFF_STATUS_MODIFIED:
 		if (p->score) {
 			len += snprintf(msg + len, sizeof(msg) - len,
 					"dissimilarity index %d%%\n",
-					(int)(0.5 + p->score *
-					      100.0/MAX_SCORE));
+					similarity_index(p));
 			complete_rewrite = 1;
 			break;
 		}

@@ -2385,8 +2395,7 @@ static void diff_flush_raw(struct diff_filepair *p,
 	}
 
 	if (p->score)
-		sprintf(status, "%c%03d", p->status,
-			(int)(0.5 + p->score * 100.0/MAX_SCORE));
+		sprintf(status, "%c%03d", p->status, similarity_index(p));
 	else {
 		status[0] = p->status;
 		status[1] = 0;

@@ -2668,8 +2677,7 @@ static void show_rename_copy(const char *renamecopy, struct diff_filepair *p)
 {
 	char *names = pprint_rename(p->one->path, p->two->path);
 
-	printf(" %s %s (%d%%)\n", renamecopy, names,
-	       (int)(0.5 + p->score * 100.0/MAX_SCORE));
+	printf(" %s %s (%d%%)\n", renamecopy, names, similarity_index(p));
 	free(names);
 	show_mode_change(p, 0);
 }

@@ -2693,7 +2701,7 @@ static void diff_summary(struct diff_filepair *p)
 		if (p->score) {
 			char *name = quote_one(p->two->path);
 			printf(" rewrite %s (%d%%)\n", name,
-				(int)(0.5 + p->score * 100.0/MAX_SCORE));
+			       similarity_index(p));
 			free(name);
 			show_mode_change(p, 0);
 		} else	show_mode_change(p, 1);

Junio C Hamano

2016-06-15 22:43 UTC #1 lore raw

diff.c static void diff_fill_sha1_info(struct diff_filespec *one) · line 1827

Quoted 12 lines · René Scharfe

diff.c +12 -0

+static int similarity_index(struct diff_filepair *p)
+{
+	int result = p->score * 100.0 / MAX_SCORE;
+
+	/* Paranoia: guard against floating point rounding errors. */
+	if (p->score == MAX_SCORE)
+		result = 100;
+	else if (result == 100)
+		result = 99;
+
+	return result;
+}

Why not simply do this?

        static int similarity_index(struct diff_filepair *p)
        {
                if (p->score == MAX_SCORE)
                        return 100;
                return p->score * 100 / MAX_SCORE;
        }

MAX_SCORE and p->score run up to 60000 and we assume int is at least 32-bit, so I do not think there is no risk of overflowing.

René Scharfe

author

2016-06-15 22:43 UTC #2 lore raw

PATCH 1/1 diff: round down similarity index, take 2

Rounding down the printed (dis)similarity index allows us to use "100%" as a special value that indicates complete rewrites and fully equal file contents, respectively.

While at it, switch index calculation to integer arithmetic as suggested by Junio and David Kastrup.

Signed-off-by Rene Scharfe <[email protected]>

---

The added documentation is only correct if you apply the diffcore-rename patch, too.

 Documentation/diff-format.txt |    7 +++++++
 diff.c                        |   22 +++++++++++-----------
 2 files changed, 18 insertions(+), 11 deletions(-)

Documentation/diff-format.txt +7 -0

index 18d49d2..0015032 100644
@@ -126,6 +126,13 @@ the file that rename/copy produces, respectively.
     If there is need for such substitution then the whole
     pathname is put in double quotes.
 
+The similarity index is the percentage of unchanged lines, and
+the dissimilarity index is the percentage of changed lines.  It
+is a rounded down integer, followed by a percent sign.  The
+similarity index value of 100% is thus reserved for two equal
+files, while 100% dissimilarity means that no line from the old
+file made it into the new one.
+
 
 combined diff format
 --------------------

diff.c +11 ~~-11~~

index 9938969..81527bf 100644
@@ -1813,6 +1813,11 @@ static void diff_fill_sha1_info(struct diff_filespec *one)
 		hashclr(one->sha1);
 }
 
+static int similarity_index(struct diff_filepair *p)
+{
+	return p->score * 100 / (int)MAX_SCORE;
+}
+
 static void run_diff(struct diff_filepair *p, struct diff_options *o)
 {
 	const char *pgm = external_diff();

@@ -1847,23 +1852,20 @@ static void run_diff(struct diff_filepair *p, struct diff_options *o)
 				"similarity index %d%%\n"
 				"copy from %s\n"
 				"copy to %s\n",
-				(int)(0.5 + p->score * 100.0/MAX_SCORE),
-				name_munged, other_munged);
+				similarity_index(p), name_munged, other_munged);
 		break;
 	case DIFF_STATUS_RENAMED:
 		len += snprintf(msg + len, sizeof(msg) - len,
 				"similarity index %d%%\n"
 				"rename from %s\n"
 				"rename to %s\n",
-				(int)(0.5 + p->score * 100.0/MAX_SCORE),
-				name_munged, other_munged);
+				similarity_index(p), name_munged, other_munged);
 		break;
 	case DIFF_STATUS_MODIFIED:
 		if (p->score) {
 			len += snprintf(msg + len, sizeof(msg) - len,
 					"dissimilarity index %d%%\n",
-					(int)(0.5 + p->score *
-					      100.0/MAX_SCORE));
+					similarity_index(p));
 			complete_rewrite = 1;
 			break;
 		}

@@ -2387,8 +2389,7 @@ static void diff_flush_raw(struct diff_filepair *p,
 	}
 
 	if (p->score)
-		sprintf(status, "%c%03d", p->status,
-			(int)(0.5 + p->score * 100.0/MAX_SCORE));
+		sprintf(status, "%c%03d", p->status, similarity_index(p));
 	else {
 		status[0] = p->status;
 		status[1] = 0;

@@ -2670,8 +2671,7 @@ static void show_rename_copy(const char *renamecopy, struct diff_filepair *p)
 {
 	char *names = pprint_rename(p->one->path, p->two->path);
 
-	printf(" %s %s (%d%%)\n", renamecopy, names,
-	       (int)(0.5 + p->score * 100.0/MAX_SCORE));
+	printf(" %s %s (%d%%)\n", renamecopy, names, similarity_index(p));
 	free(names);
 	show_mode_change(p, 0);
 }

@@ -2695,7 +2695,7 @@ static void diff_summary(struct diff_filepair *p)
 		if (p->score) {
 			char *name = quote_one(p->two->path);
 			printf(" rewrite %s (%d%%)\n", name,
-				(int)(0.5 + p->score * 100.0/MAX_SCORE));
+			       similarity_index(p));
 			free(name);
 			show_mode_change(p, 0);
 		} else	show_mode_change(p, 1);

A message that is not in the archive (sent off-list or not yet received): [email protected]

René Scharfe

author

2016-06-15 22:43 UTC #4 lore raw

Quoted 25 lines · David Kastrup

Quoted 23 lines · Junio C Hamano

diff.c static void diff_fill_sha1_info(struct diff_filespec *one) · line 1827

Quoted 12 lines · René Scharfe

diff.c +12 -0

+static int similarity_index(struct diff_filepair *p)
+{
+	int result = p->score * 100.0 / MAX_SCORE;
+
+	/* Paranoia: guard against floating point rounding errors. */
+	if (p->score == MAX_SCORE)
+		result = 100;
+	else if (result == 100)
+		result = 99;
+
+	return result;
+}

Why not simply do this?

        static int similarity_index(struct diff_filepair *p)
        {
                if (p->score == MAX_SCORE)
                        return 100;
                return p->score * 100 / MAX_SCORE;
        }

Quoted 2 lines

Quoted 2 lines
MAX_SCORE and p->score run up to 60000 and we assume int is at least 32-bit, so I do not think there is no risk of overflowing.

Good idea! *smacks himself against the forehead*

I just copied the old code (sans the addition of 0.5) and then tried to work around it's rounding problem (which I'm not even certain exists and matters). Look out for an updated patch..

Quoted 3 lines

You bet me to it on the way to work. Anyway, when working with integers, the first two lines are definitely not required (I am assuming that p->score is integer as well but have not checked).

Right.

Quoted 4 lines

What probably requires more thought is the calculation of p->score
itself: if one has large numbers as a ratio (original vs changes lines), multiplying by 60000 before dividing by the second large numbers might exceed the size of the integers.

MAX_SCORE is defined as 60000.0, which makes it a double. AFAICS all the multiplications with MAX_SCORE are done using floating point arithmetic for that reason.

René

David Kastrup

2016-06-15 22:43 UTC #5 lore raw

In reply to René Scharfe

diff.c static void diff_fill_sha1_info(struct diff_filespec *one) · line 1818

Quoted 3 lines · René Scharfe

diff.c +3 -0

+static int similarity_index(struct diff_filepair *p)
+{
+	int result = p->score * 100.0 / MAX_SCORE;

Use floor(p->score ... MAX_SCORE) here: I don't think that C otherwise specifies a preferred way of rounding on float->int conversions.

diff.c static void diff_fill_sha1_info(struct diff_filespec *one) · line 1824

Quoted 5 lines

diff.c +5 -0

+	/* Paranoia: guard against floating point rounding errors. */
+	if (p->score == MAX_SCORE)
+		result = 100;
+	else if (result == 100)
+		result = 99;

Also, p->score itself must be calculated by truncating.

Signature · 1 line

David Kastrup, Kriemhildstr. 15, 44793 Bochum

Johannes Schindelin

2016-06-15 22:43 UTC #6 lore raw

In reply to René Scharfe

Hi,

Quoted 8 lines · René Scharfe

Rounding down the printed (dis)similarity index allows us to use "100%" as a special value that indicates complete rewrites and fully equal file contents, respectively.
[...]
diff.c +2 -0
+static int similarity_index(struct diff_filepair *p)
+{

diff.c static void diff_fill_sha1_info(struct diff_filespec *one) · line 1827

Quoted 10 lines

diff.c +10 -0

+	int result = p->score * 100.0 / MAX_SCORE;
+
+	/* Paranoia: guard against floating point rounding errors. */
+	if (p->score == MAX_SCORE)
+		result = 100;
+	else if (result == 100)
+		result = 99;
+
+	return result;
+}

That's not even properly rounding down. The correct formula (correct in the sense for "what you want") would be

	p->score * 100.0 / MAX_SCORE

if p->score == MAX_SCORE, iff the files are identical. And yes, that is the old formula.

Besides, AFAIR p->score is not even calculated if the files are identical, because that hits a different code path.

Ciao,
Dscho

Johannes Schindelin

2016-06-15 22:43 UTC #7 lore raw

Hi,

Quoted 24 lines · Johannes Schindelin

Quoted 8 lines · Ren� Scharfe
Rounding down the printed (dis)similarity index allows us to use "100%" as a special value that indicates complete rewrites and fully equal file contents, respectively.
[...]
diff.c +2 -0
+static int similarity_index(struct diff_filepair *p)
+{
diff.c static void diff_fill_sha1_info(struct diff_filespec *one) · line 1827
Quoted 10 lines
diff.c +10 -0
+	int result = p->score * 100.0 / MAX_SCORE;
+
+	/* Paranoia: guard against floating point rounding errors. */
+	if (p->score == MAX_SCORE)
+		result = 100;
+	else if (result == 100)
+		result = 99;
+
+	return result;
+}
That's not even properly rounding down. The correct formula (correct in the sense for "what you want") would be

Quoted 4 lines

	p->score * 100.0 / MAX_SCORE
if p->score == MAX_SCORE, iff the files are identical. And yes, that is the old formula.

Just ignore that, please.

Quoted 2 lines

Besides, AFAIR p->score is not even calculated if the files are identical, because that hits a different code path.

But this still holds true.

Ciao,
Dscho

René Scharfe

author

2016-06-15 22:43 UTC #8 lore raw

Quoted 27 lines · Johannes Schindelin

Hi,
Quoted 23 lines · Johannes Schindelin
Quoted 8 lines · Ren� Scharfe
Rounding down the printed (dis)similarity index allows us to use "100%" as a special value that indicates complete rewrites and fully equal file contents, respectively.
[...]
diff.c +2 -0
+static int similarity_index(struct diff_filepair *p)
+{
diff.c static void diff_fill_sha1_info(struct diff_filespec *one) · line 1827
Quoted 10 lines
diff.c +10 -0
+	int result = p->score * 100.0 / MAX_SCORE;
+
+	/* Paranoia: guard against floating point rounding errors. */
+	if (p->score == MAX_SCORE)
+		result = 100;
+	else if (result == 100)
+		result = 99;
+
+	return result;
+}
Besides, AFAIR p->score is not even calculated if the files are identical, because that hits a different code path.

True, ->score is set to MAX_SCORE for identical files by a different code path than the one that actually compares the contents and calculates a score. That doesn't matter for printing the "similarity index nn%" line etc., though. Or is there a way for identical files to end up with a ->score of 0 (or some other value != MAX_SCORE) that I missed?

In any case, the patch doesn't change the way the score is calculated, i.e. its value is the same as before. It only changes how it is displayed.

René