[RFC PATCH] line-log: clarify [a,b) notation for ranges

[RFC PATCH] line-log: clarify [a,b) notation for ranges

[Andrei Rybak]

line-log.[ch] use left-closed, right-open interval logic. Change comment
and debug output to square brackets+parentheses notation to help
developers avoid off-by-one errors.
---

Original idea for this change in recent thread about line-log changes:

  https://public-inbox.org/git/9776862d-18b2-43ec-cfeb-829418d4d967@gmail.com/

line-log.c also uses ASCII graphics |---| in some comments, like:

	/*
	 * a:         |-------
	 * b: ------|
	 */

But I'm not sure if replacing them with

	/*
	 * a:         [-------
	 * b: ------)
	 */

will be helpful.  Another possibility is to update comment for
range_set_append_unsafe to read

  /* tack on a _new_ range [a,b) _at the end_ */
  void range_set_append_unsafe(struct range_set *rs, long a, long b)

 line-log.c | 4 ++--
 line-log.h | 2 +-
 2 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/line-log.c b/line-log.c
index fa9cfd5bd..60f3174ac 100644
--- a/line-log.c
+++ b/line-log.c
@@ -353,7 +353,7 @@ static void dump_range_set(struct range_set *rs, const char *desc)
 	int i;
 	printf("range set %s (%d items):\n", desc, rs->nr);
 	for (i = 0; i < rs->nr; i++)
-		printf("\t[%ld,%ld]\n", rs->ranges[i].start, rs->ranges[i].end);
+		printf("\t[%ld,%ld)\n", rs->ranges[i].start, rs->ranges[i].end);
 }
 
 static void dump_line_log_data(struct line_log_data *r)
@@ -373,7 +373,7 @@ static void dump_diff_ranges(struct diff_ranges *diff, const char *desc)
 	printf("diff ranges %s (%d items):\n", desc, diff->parent.nr);
 	printf("\tparent\ttarget\n");
 	for (i = 0; i < diff->parent.nr; i++) {
-		printf("\t[%ld,%ld]\t[%ld,%ld]\n",
+		printf("\t[%ld,%ld)\t[%ld,%ld)\n",
 		       diff->parent.ranges[i].start,
 		       diff->parent.ranges[i].end,
 		       diff->target.ranges[i].start,
diff --git a/line-log.h b/line-log.h
index e2a5ee7c6..488c86409 100644
--- a/line-log.h
+++ b/line-log.h
@@ -6,7 +6,7 @@
 struct rev_info;
 struct commit;
 
-/* A range [start,end].  Lines are numbered starting at 0, and the
+/* A range [start,end).  Lines are numbered starting at 0, and the
  * ranges include start but exclude end. */
 struct range {
 	long start, end;
-- 
2.18.0

Re: [RFC PATCH] line-log: clarify [a,b) notation for ranges

[Eric Sunshine]

On Tue, Aug 7, 2018 at 9:54 AM Andrei Rybak <rybak.a.v@gmail.com> wrote:
> line-log.[ch] use left-closed, right-open interval logic. Change comment
> and debug output to square brackets+parentheses notation to help
> developers avoid off-by-one errors.
> ---

This seems sensible. There might be some reviewers who suggest
different notation since "[...)" is not universal (see [1]), but I
think this is fine.

You'll want to add your sign-off, of course, when taking this out of RFC.

[1]: https://en.wikipedia.org/wiki/Interval_(mathematics)#Notations_for_intervals

> line-log.c also uses ASCII graphics |---| in some comments, like:
>
>         /*
>          * a:         |-------
>          * b: ------|
>          */
>
> But I'm not sure if replacing them with
>
>         /*
>          * a:         [-------
>          * b: ------)
>          */
>
> will be helpful.

Those comments seem to use horizontal ruling to make it clear where
one range ends and another begins, so they already do a good job
conveying what they represent. Changing them to use "["" and ")" might
make them less clear.

> Another possibility is to update comment for
> range_set_append_unsafe to read
>
>   /* tack on a _new_ range [a,b) _at the end_ */
>   void range_set_append_unsafe(struct range_set *rs, long a, long b)

It shouldn't hurt (though the existing "_at the end_" is rather
superfluous since "append" in the name says the that already).

Re: [RFC PATCH] line-log: clarify [a,b) notation for ranges

[Johannes Schindelin]

Hi Eric,

On Tue, 7 Aug 2018, Eric Sunshine wrote:

> On Tue, Aug 7, 2018 at 9:54 AM Andrei Rybak <rybak.a.v@gmail.com> wrote:
> > line-log.[ch] use left-closed, right-open interval logic. Change comment
> > and debug output to square brackets+parentheses notation to help
> > developers avoid off-by-one errors.
> > ---
> 
> This seems sensible. There might be some reviewers who suggest
> different notation since "[...)" is not universal (see [1]), but I
> think this is fine.

Indeed. When I started out studying mathematics, I learned the notation
[...[ (which makes a lot more sense, if you think about it).

Besides, it's not like we start from a fresh slate. Git is already over a
decade old. Our commit ranges are "half open", i.e. the exact thing that
is described here. There's gotta be some precedent in the documentation,
and introducing something willfully inconsistent is probably a pretty bad
idea.

Ciao,
Dscho

[PATCH v2] line-log: clarify [a,b) notation for ranges

[Andrei Rybak]

line-log.[ch] use left-closed, right-open interval logic. Update
comments and debug output to use square brackets+parentheses notation
to help developers avoid off-by-one errors.

Signed-off-by: Andrei Rybak <rybak.a.v@gmail.com>
---

Applies on top of c0babbe69 (range-set: publish API for re-use by
git-blame -L, 2013-08-06). When applied on the original commit 12da1d1f6
(Implement line-history search (git log -L), 2013-03-28), the conflict
is in removal of "static" from some functions.

Changes since v1:

 - reword commit message a bit
 - sign-off
 - add [a,b) to comment of range_set_append_unsafe

I decided not to remove "_at the end_", as

  /* tack on a _new_ range [a,b) */

seems a bit less readable to me.

 line-log.c | 6 +++---
 line-log.h | 2 +-
 2 files changed, 4 insertions(+), 4 deletions(-)

diff --git a/line-log.c b/line-log.c
index fa9cfd5bd..9ab6d51cc 100644
--- a/line-log.c
+++ b/line-log.c
@@ -56,7 +56,7 @@ static void range_set_move(struct range_set *dst, struct range_set *src)
 	src->alloc = src->nr = 0;
 }
 
-/* tack on a _new_ range _at the end_ */
+/* tack on a _new_ range [a,b) _at the end_ */
 void range_set_append_unsafe(struct range_set *rs, long a, long b)
 {
 	assert(a <= b);
@@ -353,7 +353,7 @@ static void dump_range_set(struct range_set *rs, const char *desc)
 	int i;
 	printf("range set %s (%d items):\n", desc, rs->nr);
 	for (i = 0; i < rs->nr; i++)
-		printf("\t[%ld,%ld]\n", rs->ranges[i].start, rs->ranges[i].end);
+		printf("\t[%ld,%ld)\n", rs->ranges[i].start, rs->ranges[i].end);
 }
 
 static void dump_line_log_data(struct line_log_data *r)
@@ -373,7 +373,7 @@ static void dump_diff_ranges(struct diff_ranges *diff, const char *desc)
 	printf("diff ranges %s (%d items):\n", desc, diff->parent.nr);
 	printf("\tparent\ttarget\n");
 	for (i = 0; i < diff->parent.nr; i++) {
-		printf("\t[%ld,%ld]\t[%ld,%ld]\n",
+		printf("\t[%ld,%ld)\t[%ld,%ld)\n",
 		       diff->parent.ranges[i].start,
 		       diff->parent.ranges[i].end,
 		       diff->target.ranges[i].start,
diff --git a/line-log.h b/line-log.h
index e2a5ee7c6..488c86409 100644
--- a/line-log.h
+++ b/line-log.h
@@ -6,7 +6,7 @@
 struct rev_info;
 struct commit;
 
-/* A range [start,end].  Lines are numbered starting at 0, and the
+/* A range [start,end).  Lines are numbered starting at 0, and the
  * ranges include start but exclude end. */
 struct range {
 	long start, end;
-- 
2.18.0