threads / patch / 8705

patchdiff: round down similarity index

Subject: [PATCH] diff: round down similarity index

## tl;dr

8 messages between Jun 24, 2007 and Jun 25, 2007. Diffs are folded; open one to read it.

replies: 7people: 4as markdown or json

René Scharfe· Jun 24, 2007, 22:23 UTC · lore

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 <rene.scharfe@lsrfire.ath.cx>
---

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(-)
Show changes to 2 files +26 −11

Documentation/diff-format.txt, diff.c

diff --git a/Documentation/diff-format.txt b/Documentation/diff-format.txt
index 18d49d2..0015032 100644
--- a/Documentation/diff-format.txt
+++ b/Documentation/diff-format.txt
@@ -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 --git a/diff.c b/diff.c
index 4aa9bbc..f1db55d 100644
--- a/diff.c
+++ b/diff.c
@@ -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);
Johannes Schindelin· Jun 24, 2007, 23:25 UTC · re: René Scharfe · lore

Re: [PATCH] diff: round down similarity index

Hi,
On Mon, 25 Jun 2007, René Scharfe wrote:
Show 18 quoted lines
> 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.
>
> [...]
> 
> +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;
> +}

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· Jun 24, 2007, 23:27 UTC · re: Johannes Schindelin · lore

Re: [PATCH] diff: round down similarity index

Hi,
On Mon, 25 Jun 2007, Johannes Schindelin wrote:
Show 28 quoted lines
> On Mon, 25 Jun 2007, Ren� Scharfe wrote:
> 
> > 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.
> >
> > [...]
> > 
> > +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;
> > +}
> 
> 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.
Just ignore that, please.
> 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· Jun 25, 2007, 01:29 UTC · re: Johannes Schindelin · lore

Re: [PATCH] diff: round down similarity index

Johannes Schindelin schrieb:
Show 24 quoted lines
> Hi,
> 
> On Mon, 25 Jun 2007, Johannes Schindelin wrote:
> 
>> On Mon, 25 Jun 2007, Ren� Scharfe wrote:
>>
>>> 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.
>>>
>>> [...]
>>>
>>> +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;
>>> +}
>> 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é
David Kastrup· Jun 25, 2007, 05:08 UTC · re: René Scharfe · lore

Re: [PATCH] diff: round down similarity index

René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:
> +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.

Show 5 quoted lines
> +	/* 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.
-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum
Junio C Hamano· Jun 25, 2007, 06:18 UTC · re: René Scharfe · lore

Re: [PATCH] diff: round down similarity index

René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:
Show 12 quoted lines
> +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· Jun 25, 2007, 10:34 UTC · re: Junio C Hamano · lore

[PATCH] 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 <rene.scharfe@lsrfire.ath.cx>
---

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(-)
Show changes to 2 files +18 −11

Documentation/diff-format.txt, diff.c

diff --git a/Documentation/diff-format.txt b/Documentation/diff-format.txt
index 18d49d2..0015032 100644
--- a/Documentation/diff-format.txt
+++ b/Documentation/diff-format.txt
@@ -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 --git a/diff.c b/diff.c
index 9938969..81527bf 100644
--- a/diff.c
+++ b/diff.c
@@ -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);
René Scharfe· Jun 25, 2007, 10:34 UTC · lore

Re: [PATCH] diff: round down similarity index

David Kastrup schrieb:
Show 27 quoted lines
> Junio C Hamano <gitster@pobox.com> writes:
> 
>> René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:
>>
>>> +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.
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..

> 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.
> 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é

← back to recent threads