* [PATCH v2 0/2] fix broken range_set tests and coalescing
@ 2013-07-09 5:55 Eric Sunshine
2013-07-09 5:55 ` [PATCH v2 1/2] t4211: fix broken test when one -L range is subset of another Eric Sunshine
2013-07-09 5:55 ` [PATCH v2 2/2] range_set: fix coalescing bug when range is a " Eric Sunshine
0 siblings, 2 replies; 4+ messages in thread
From: Eric Sunshine @ 2013-07-09 5:55 UTC (permalink / raw)
To: git; +Cc: Eric Sunshine, Thomas Rast, Bo Yang
This is a re-roll of a patch [1] which fixes the
line-log.c:sort_and_merge_range_set() coalescing bug. This re-roll
inserts a new patch before the lone patch from v1.
patch 1/2: Fix broken tests in t4211 which should have detected the
sort_and_merge_range_set() bug but didn't due to incorrect
"expected" state. Mark the tests as expect-failure.
patch 2/2: Fix the sort_and_merge_range_set() coalesce bug. Same as v1
but also flips the tests to expect-success.
[1]: http://article.gmane.org/gmane.comp.version-control.git/229774
Eric Sunshine (2):
t4211: fix broken test when one -L range is subset of another
range_set: fix coalescing bug when range is a subset of another
line-log.c | 3 +-
t/t4211/expect.multiple-superset | 134 ++++++++++++++++++++++++++++++++++++++-
2 files changed, 133 insertions(+), 4 deletions(-)
--
1.8.3.2
^ permalink raw reply [flat|nested] 4+ messages in thread
* [PATCH v2 1/2] t4211: fix broken test when one -L range is subset of another
2013-07-09 5:55 [PATCH v2 0/2] fix broken range_set tests and coalescing Eric Sunshine
@ 2013-07-09 5:55 ` Eric Sunshine
2013-07-09 5:55 ` [PATCH v2 2/2] range_set: fix coalescing bug when range is a " Eric Sunshine
1 sibling, 0 replies; 4+ messages in thread
From: Eric Sunshine @ 2013-07-09 5:55 UTC (permalink / raw)
To: git; +Cc: Eric Sunshine, Thomas Rast, Bo Yang
t4211 attempts to test multiple git-log -L ranges where one range is a
superset of the other, and falsely succeeds because its "expected"
output is incorrect.
Overlapping -L ranges handed to git-log are coalesced by
line-log.c:sort_and_merge_range_set() into a set of non-overlapping,
disjoint ranges. When one range is a subset of another,
sort_and_merge_range_set() should coalesce both ranges to the superset
range, but instead the coalesced range often is incorrectly truncated to
the end of the subset range. For example, ranges 2-8 and 3-4 are
coalesced incorrectly to 2-4.
One can observe this incorrect behavior with git-log -L using the test
repository created by t4211. The superset/subset ranges t4211 employs
are 4-$ and 8-12 (where $ represents end-of-file). The coalesced range
should be 4-$. Manually invoking git-log with the same ranges the test
employs, we see:
% git log -L 4:a.c simple |
awk '/^commit [0-9a-f]{40}/ { print substr($2,1,7) }'
4659538
100b61a
39b6eb2
a6eb826
f04fb20
de4c48a
% git log -L 8,12:a.c simple | awk ...
f04fb20
de4c48a
% git log -L 4:a.c -L 8,12:a.c simple | awk ...
a6eb826
f04fb20
de4c48a
This last output is incorrect. 8-12 is a subset of 4-$, hence the output
of the coalesced range should be the same as the 4-$ output shown first.
In fact, the above incorrect output is the truncated bogus range 4-12:
% git log -L 4,12:a.c simple | awk ...
a6eb826
f04fb20
de4c48a
Fix the test to correctly fail in the presence of the
sort_and_merge_range_set() coalescing bug. Do so by changing the
"expected" output to the commits mentioned in the 4-$ output above.
Signed-off-by: Eric Sunshine <sunshine@sunshineco.com>
---
t/t4211-line-log.sh | 4 +-
t/t4211/expect.multiple-superset | 134 ++++++++++++++++++++++++++++++++++++++-
2 files changed, 133 insertions(+), 5 deletions(-)
diff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh
index 7776f93..549df9e 100755
--- a/t/t4211-line-log.sh
+++ b/t/t4211-line-log.sh
@@ -50,8 +50,8 @@ canned_test "-M -L ':f:b.c' parallel-change" parallel-change-f-to-main
canned_test "-L 4,12:a.c -L :main:a.c simple" multiple
canned_test "-L 4,18:a.c -L :main:a.c simple" multiple-overlapping
canned_test "-L :main:a.c -L 4,18:a.c simple" multiple-overlapping
-canned_test "-L 4:a.c -L 8,12:a.c simple" multiple-superset
-canned_test "-L 8,12:a.c -L 4:a.c simple" multiple-superset
+canned_test_failure "-L 4:a.c -L 8,12:a.c simple" multiple-superset
+canned_test_failure "-L 8,12:a.c -L 4:a.c simple" multiple-superset
test_bad_opts "-L" "switch.*requires a value"
test_bad_opts "-L b.c" "argument.*not of the form"
diff --git a/t/t4211/expect.multiple-superset b/t/t4211/expect.multiple-superset
index a1f5bc4..d930b6e 100644
--- a/t/t4211/expect.multiple-superset
+++ b/t/t4211/expect.multiple-superset
@@ -1,3 +1,100 @@
+commit 4659538844daa2849b1a9e7d6fadb96fcd26fc83
+Author: Thomas Rast <trast@student.ethz.ch>
+Date: Thu Feb 28 10:48:43 2013 +0100
+
+ change back to complete line
+
+diff --git a/a.c b/a.c
+--- a/a.c
++++ b/a.c
+@@ -4,19 +4,21 @@
+ long f(long x)
+ {
+ int s = 0;
+ while (x) {
+ x >>= 1;
+ s++;
+ }
+ return s;
+ }
+
+ /*
+ * This is only an example!
+ */
+
+ int main ()
+ {
+ printf("%ld\n", f(15));
+ return 0;
+-}
+\ No newline at end of file
++}
++
++/* incomplete lines are bad! */
+
+commit 100b61a6f2f720f812620a9d10afb3a960ccb73c
+Author: Thomas Rast <trast@student.ethz.ch>
+Date: Thu Feb 28 10:48:10 2013 +0100
+
+ change to an incomplete line at end
+
+diff --git a/a.c b/a.c
+--- a/a.c
++++ b/a.c
+@@ -4,19 +4,19 @@
+ long f(long x)
+ {
+ int s = 0;
+ while (x) {
+ x >>= 1;
+ s++;
+ }
+ return s;
+ }
+
+ /*
+ * This is only an example!
+ */
+
+ int main ()
+ {
+ printf("%ld\n", f(15));
+ return 0;
+-}
++}
+\ No newline at end of file
+
+commit 39b6eb2d5b706d3322184a169f666f25ed3fbd00
+Author: Thomas Rast <trast@student.ethz.ch>
+Date: Thu Feb 28 10:45:41 2013 +0100
+
+ touch comment
+
+diff --git a/a.c b/a.c
+--- a/a.c
++++ b/a.c
+@@ -3,19 +3,19 @@
+ long f(long x)
+ {
+ int s = 0;
+ while (x) {
+ x >>= 1;
+ s++;
+ }
+ return s;
+ }
+
+ /*
+- * A comment.
++ * This is only an example!
+ */
+
+ int main ()
+ {
+ printf("%ld\n", f(15));
+ return 0;
+ }
+
commit a6eb82647d5d67f893da442f8f9375fd89a3b1e2
Author: Thomas Rast <trast@student.ethz.ch>
Date: Thu Feb 28 10:45:16 2013 +0100
@@ -7,7 +104,7 @@ Date: Thu Feb 28 10:45:16 2013 +0100
diff --git a/a.c b/a.c
--- a/a.c
+++ b/a.c
-@@ -3,9 +3,9 @@
+@@ -3,19 +3,19 @@
-int f(int x)
+long f(long x)
{
@@ -18,6 +115,17 @@ diff --git a/a.c b/a.c
}
return s;
}
+
+ /*
+ * A comment.
+ */
+
+ int main ()
+ {
+- printf("%d\n", f(15));
++ printf("%ld\n", f(15));
+ return 0;
+ }
commit f04fb20f2c77850996cba739709acc6faecc58f7
Author: Thomas Rast <trast@student.ethz.ch>
@@ -28,7 +136,7 @@ Date: Thu Feb 28 10:44:55 2013 +0100
diff --git a/a.c b/a.c
--- a/a.c
+++ b/a.c
-@@ -3,8 +3,9 @@
+@@ -3,18 +3,19 @@
int f(int x)
{
int s = 0;
@@ -38,6 +146,16 @@ diff --git a/a.c b/a.c
}
+ return s;
}
+
+ /*
+ * A comment.
+ */
+
+ int main ()
+ {
+ printf("%d\n", f(15));
+ return 0;
+ }
commit de4c48ae814792c02a49c4c3c0c757ae69c55f6a
Author: Thomas Rast <trast@student.ethz.ch>
@@ -48,7 +166,7 @@ Date: Thu Feb 28 10:44:48 2013 +0100
diff --git a/a.c b/a.c
--- /dev/null
+++ b/a.c
-@@ -0,0 +3,8 @@
+@@ -0,0 +3,18 @@
+int f(int x)
+{
+ int s = 0;
@@ -57,3 +175,13 @@ diff --git a/a.c b/a.c
+ s++;
+ }
+}
++
++/*
++ * A comment.
++ */
++
++int main ()
++{
++ printf("%d\n", f(15));
++ return 0;
++}
--
1.8.3.2
^ permalink raw reply related [flat|nested] 4+ messages in thread
* [PATCH v2 2/2] range_set: fix coalescing bug when range is a subset of another
2013-07-09 5:55 [PATCH v2 0/2] fix broken range_set tests and coalescing Eric Sunshine
2013-07-09 5:55 ` [PATCH v2 1/2] t4211: fix broken test when one -L range is subset of another Eric Sunshine
@ 2013-07-09 5:55 ` Eric Sunshine
2013-07-09 9:31 ` Thomas Rast
1 sibling, 1 reply; 4+ messages in thread
From: Eric Sunshine @ 2013-07-09 5:55 UTC (permalink / raw)
To: git; +Cc: Eric Sunshine, Thomas Rast, Bo Yang
When coalescing ranges, sort_and_merge_range_set() unconditionally
assumes that the end of a range being folded into a preceding range
should become the end of the coalesced range. This assumption, however,
is invalid when one range is a subset of another. For example, given
ranges 1-5 and 2-3 added via range_set_append_unsafe(),
sort_and_merge_range_set() incorrectly coalesces them to range 1-3
rather than the correct union range 1-5. Fix this bug.
Signed-off-by: Eric Sunshine <sunshine@sunshineco.com>
---
line-log.c | 3 ++-
t/t4211-line-log.sh | 4 ++--
2 files changed, 4 insertions(+), 3 deletions(-)
diff --git a/line-log.c b/line-log.c
index 4bbb09b..8cc29a0 100644
--- a/line-log.c
+++ b/line-log.c
@@ -116,7 +116,8 @@ static void sort_and_merge_range_set(struct range_set *rs)
for (i = 1; i < rs->nr; i++) {
if (rs->ranges[i].start <= rs->ranges[o-1].end) {
- rs->ranges[o-1].end = rs->ranges[i].end;
+ if (rs->ranges[o-1].end < rs->ranges[i].end)
+ rs->ranges[o-1].end = rs->ranges[i].end;
} else {
rs->ranges[o].start = rs->ranges[i].start;
rs->ranges[o].end = rs->ranges[i].end;
diff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh
index 549df9e..7776f93 100755
--- a/t/t4211-line-log.sh
+++ b/t/t4211-line-log.sh
@@ -50,8 +50,8 @@ canned_test "-M -L ':f:b.c' parallel-change" parallel-change-f-to-main
canned_test "-L 4,12:a.c -L :main:a.c simple" multiple
canned_test "-L 4,18:a.c -L :main:a.c simple" multiple-overlapping
canned_test "-L :main:a.c -L 4,18:a.c simple" multiple-overlapping
-canned_test_failure "-L 4:a.c -L 8,12:a.c simple" multiple-superset
-canned_test_failure "-L 8,12:a.c -L 4:a.c simple" multiple-superset
+canned_test "-L 4:a.c -L 8,12:a.c simple" multiple-superset
+canned_test "-L 8,12:a.c -L 4:a.c simple" multiple-superset
test_bad_opts "-L" "switch.*requires a value"
test_bad_opts "-L b.c" "argument.*not of the form"
--
1.8.3.2
^ permalink raw reply related [flat|nested] 4+ messages in thread
* Re: [PATCH v2 2/2] range_set: fix coalescing bug when range is a subset of another
2013-07-09 5:55 ` [PATCH v2 2/2] range_set: fix coalescing bug when range is a " Eric Sunshine
@ 2013-07-09 9:31 ` Thomas Rast
0 siblings, 0 replies; 4+ messages in thread
From: Thomas Rast @ 2013-07-09 9:31 UTC (permalink / raw)
To: Eric Sunshine; +Cc: git, Bo Yang
Eric Sunshine <sunshine@sunshineco.com> writes:
> When coalescing ranges, sort_and_merge_range_set() unconditionally
> assumes that the end of a range being folded into a preceding range
> should become the end of the coalesced range. This assumption, however,
> is invalid when one range is a subset of another. For example, given
> ranges 1-5 and 2-3 added via range_set_append_unsafe(),
> sort_and_merge_range_set() incorrectly coalesces them to range 1-3
> rather than the correct union range 1-5. Fix this bug.
>
> Signed-off-by: Eric Sunshine <sunshine@sunshineco.com>
> ---
> line-log.c | 3 ++-
> t/t4211-line-log.sh | 4 ++--
> 2 files changed, 4 insertions(+), 3 deletions(-)
>
> diff --git a/line-log.c b/line-log.c
> index 4bbb09b..8cc29a0 100644
> --- a/line-log.c
> +++ b/line-log.c
> @@ -116,7 +116,8 @@ static void sort_and_merge_range_set(struct range_set *rs)
>
> for (i = 1; i < rs->nr; i++) {
> if (rs->ranges[i].start <= rs->ranges[o-1].end) {
> - rs->ranges[o-1].end = rs->ranges[i].end;
> + if (rs->ranges[o-1].end < rs->ranges[i].end)
> + rs->ranges[o-1].end = rs->ranges[i].end;
Ouch. Thanks for finding and fixing this.
Acked-by: Thomas Rast <trast@inf.ethz.ch>
--
Thomas Rast
trast@{inf,student}.ethz.ch
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2013-07-09 9:31 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2013-07-09 5:55 [PATCH v2 0/2] fix broken range_set tests and coalescing Eric Sunshine
2013-07-09 5:55 ` [PATCH v2 1/2] t4211: fix broken test when one -L range is subset of another Eric Sunshine
2013-07-09 5:55 ` [PATCH v2 2/2] range_set: fix coalescing bug when range is a " Eric Sunshine
2013-07-09 9:31 ` Thomas Rast
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).