[PATCH] for_each_string_list_item(): behave correctly for empty list

[PATCH] for_each_string_list_item(): behave correctly for empty list

[Michael Haggerty]

If you pass a newly-initialized or newly-cleared `string_list` to
`for_each_string_list_item()`, then the latter does

    for (
            item = (list)->items; /* note, this is NULL */
            item < (list)->items + (list)->nr; /* note: NULL + 0 */
            ++item)

Even though this probably works almost everywhere, it is undefined
behavior, and it could plausibly cause highly-optimizing compilers to
misbehave.

It would be a pain to have to change the signature of this macro, and
we'd prefer not to add overhead to each iteration of the loop. So
instead, whenever `list->items` is NULL, initialize `item` to point at
a dummy `string_list_item` created for the purpose.

This problem was noticed by Coverity.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
Just a little thing I noticed in a Coverity report. This macro has
been broken since it was first introduced, in 2010.

This patch applies against maint. It is also available from my Git
fork [1] as branch `iter-empty-string-list`.

Michael

[1] https://github.com/mhagger/git

 string-list.c | 2 ++
 string-list.h | 7 +++++--
 2 files changed, 7 insertions(+), 2 deletions(-)

diff --git a/string-list.c b/string-list.c
index 806b4c8723..7eacf6037f 100644
--- a/string-list.c
+++ b/string-list.c
@@ -1,6 +1,8 @@
 #include "cache.h"
 #include "string-list.h"
 
+struct string_list_item dummy_string_list_item;
+
 void string_list_init(struct string_list *list, int strdup_strings)
 {
 	memset(list, 0, sizeof(*list));
diff --git a/string-list.h b/string-list.h
index 29bfb7ae45..79bb78d80a 100644
--- a/string-list.h
+++ b/string-list.h
@@ -32,8 +32,11 @@ void string_list_clear_func(struct string_list *list, string_list_clear_func_t c
 typedef int (*string_list_each_func_t)(struct string_list_item *, void *);
 int for_each_string_list(struct string_list *list,
 			 string_list_each_func_t, void *cb_data);
-#define for_each_string_list_item(item,list) \
-	for (item = (list)->items; item < (list)->items + (list)->nr; ++item)
+extern struct string_list_item dummy_string_list_item;
+#define for_each_string_list_item(item,list)                                 \
+	for (item = (list)->items ? (list)->items : &dummy_string_list_item; \
+	     item < (list)->items + (list)->nr;                              \
+	     ++item)
 
 /*
  * Apply want to each item in list, retaining only the ones for which
-- 
2.14.1

Re: [PATCH] for_each_string_list_item(): behave correctly for empty list

[Jonathan Nieder]

Hi,

Michael Haggerty wrote:

> If you pass a newly-initialized or newly-cleared `string_list` to
> `for_each_string_list_item()`, then the latter does
>
>     for (
>             item = (list)->items; /* note, this is NULL */
>             item < (list)->items + (list)->nr; /* note: NULL + 0 */
>             ++item)
>
> Even though this probably works almost everywhere, it is undefined
> behavior, and it could plausibly cause highly-optimizing compilers to
> misbehave.

Wait, NULL + 0 is undefined behavior?

*checks the standard*  C99 section 6.5.6.8 says

	"If both the pointer operand and the result point to elements
	of the same array object, or one past the last element of the
	array object, the evaluation shall not produce an overflow;
	otherwise, the behavior is undefined."

C99 section 7.17.3 says

	"NULL

	which expands to an implementation-defined null pointer constant"

6.3.2.3.3 says

	"An integer constant expression with the value 0, or such an
	expression cast to type void *, is called a null pointer
	constant.  If a null pointer constant is converted to a
	pointer type, the resulting pointer, called a null pointer, is
	guaranteed to compare unequal to a pointer to any object or
	function."

NULL doesn't point to anything so it looks like adding 0 to a null
pointer is indeed undefined.  (As a piece of trivia, strictly speaking
NULL + 0 would be undefined on some implementations and defined on
others, since an implementation is permitted to #define NULL to 0.)

So Coverity is not just warning because it is not able to guarantee
that list->nr is 0.  Huh.

> It would be a pain to have to change the signature of this macro, and
> we'd prefer not to add overhead to each iteration of the loop. So
> instead, whenever `list->items` is NULL, initialize `item` to point at
> a dummy `string_list_item` created for the purpose.

What signature change do you mean?  I don't understand what this
paragraph is alluding to.

> This problem was noticed by Coverity.
>
> Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
> ---
[...]
>  string-list.c | 2 ++
>  string-list.h | 7 +++++--
>  2 files changed, 7 insertions(+), 2 deletions(-)

Does the following alternate fix work?  I think I prefer it because
it doesn't require introducing a new global.

Thanks,
Jonathan

diff --git i/string-list.h w/string-list.h
index 29bfb7ae45..dae33fbb89 100644
--- i/string-list.h
+++ w/string-list.h
@@ -33,7 +33,9 @@ typedef int (*string_list_each_func_t)(struct string_list_item *, void *);
 int for_each_string_list(struct string_list *list,
 			 string_list_each_func_t, void *cb_data);
 #define for_each_string_list_item(item,list) \
-	for (item = (list)->items; item < (list)->items + (list)->nr; ++item)
+	for (item = (list)->items; \
+	     (list)->items && item < (list)->items + (list)->nr; \
+	     ++item)
 
 /*
  * Apply want to each item in list, retaining only the ones for which

Re: [PATCH] for_each_string_list_item(): behave correctly for empty list

[Michael Haggerty]

On 09/15/2017 08:43 PM, Jonathan Nieder wrote:
> Michael Haggerty wrote:
> 
>> If you pass a newly-initialized or newly-cleared `string_list` to
>> `for_each_string_list_item()`, then the latter does
>>
>>     for (
>>             item = (list)->items; /* note, this is NULL */
>>             item < (list)->items + (list)->nr; /* note: NULL + 0 */
>>             ++item)
>>
>> Even though this probably works almost everywhere, it is undefined
>> behavior, and it could plausibly cause highly-optimizing compilers to
>> misbehave.
> 
> Wait, NULL + 0 is undefined behavior?
> 
> *checks the standard*  [...]
> NULL doesn't point to anything so it looks like adding 0 to a null
> pointer is indeed undefined.

Thanks for the legal work :-)

>                             (As a piece of trivia, strictly speaking
> NULL + 0 would be undefined on some implementations and defined on
> others, since an implementation is permitted to #define NULL to 0.)

Isn't that the very definition of "undefined behavior", in the sense of
a language standard?

> [...]
>> It would be a pain to have to change the signature of this macro, and
>> we'd prefer not to add overhead to each iteration of the loop. So
>> instead, whenever `list->items` is NULL, initialize `item` to point at
>> a dummy `string_list_item` created for the purpose.
> 
> What signature change do you mean?  I don't understand what this
> paragraph is alluding to.

I was thinking that one solution would be for the caller to provide a
`size_t` variable for the macro's use as a counter (since I don't see a
way for the macro to declare its own counter). The options are pretty
limited because whatever the macro expands to has to play the same
syntactic role as `for (...; ...; ...)`.

> [...]
> Does the following alternate fix work?  I think I prefer it because
> it doesn't require introducing a new global. [...]
>  #define for_each_string_list_item(item,list) \
> -	for (item = (list)->items; item < (list)->items + (list)->nr; ++item)
> +	for (item = (list)->items; \
> +	     (list)->items && item < (list)->items + (list)->nr; \
> +	     ++item)

This is the possibility that I was referring to as "add[ing] overhead to
each iteration of the loop". I'd rather not add an extra test-and-branch
to every iteration of a loop in which `list->items` is *not* NULL, which
your solution appears to do. Or are compilers routinely able to optimize
the check out?

The new global might be aesthetically unpleasant, but it only costs two
words of memory, so I don't see it as a big disadvantage.

Another, more invasive change would be to initialize
`string_list::items` to *always* point at `dummy_string_list_item`,
rather similar to how `strbuf_slopbuf` is pointed at by empty `strbuf`s.
But I really don't think the effort would be justified.

Michael

Re: [PATCH] for_each_string_list_item(): behave correctly for empty list

[SZEDER Gábor]

> >> It would be a pain to have to change the signature of this macro, and
> >> we'd prefer not to add overhead to each iteration of the loop. So
> >> instead, whenever `list->items` is NULL, initialize `item` to point at
> >> a dummy `string_list_item` created for the purpose.
> > 
> > What signature change do you mean?  I don't understand what this
> > paragraph is alluding to.
> 
> I was thinking that one solution would be for the caller to provide a
> `size_t` variable for the macro's use as a counter (since I don't see a
> way for the macro to declare its own counter). The options are pretty
> limited because whatever the macro expands to has to play the same
> syntactic role as `for (...; ...; ...)`.

Another option to consider is to squeeze in an if-else before the for
loop header to handle the empty list case like this:

diff --git a/string-list.h b/string-list.h
index 29bfb7ae4..9eed47de0 100644
--- a/string-list.h
+++ b/string-list.h
@@ -32,8 +32,11 @@ void string_list_clear_func(struct string_list *list, string_list_clear_func_t c
 typedef int (*string_list_each_func_t)(struct string_list_item *, void *);
 int for_each_string_list(struct string_list *list,
 			 string_list_each_func_t, void *cb_data);
-#define for_each_string_list_item(item,list) \
-	for (item = (list)->items; item < (list)->items + (list)->nr; ++item)
+#define for_each_string_list_item(item,list) 	\
+	if ((list)->items == NULL) {		\
+		/* empty list, do nothing */	\
+	} else					\
+		for (item = (list)->items; item < (list)->items + (list)->nr; ++item)
 
 /*
  * Apply want to each item in list, retaining only the ones for which

This way there would be neither additional overhead in each iteration
nor a new global.

Alas, there is a catch.  We can't use curly braces in the macro's else
branch, because the macro would contain only the opening brace but not
the closing one, which must come after the end of the loop's body.
This means that the modified macro couldn't be used in if-else
branches which themselves don't have curly braces, because it causes
ambiguity:

  if (condition)
      for_each_string_list_item(item, list)
          a_simple_oneliner(item);

Our coding guidelines encourage this style for one-liner loop bodies,
and there is indeed one such place in our codebase, so the following
hunk is needed as well:

diff --git a/send-pack.c b/send-pack.c
index 11d6f3d98..00fa1622f 100644
--- a/send-pack.c
+++ b/send-pack.c
@@ -295,9 +295,10 @@ static int generate_push_cert(struct strbuf *req_buf,
 	}
 	if (push_cert_nonce[0])
 		strbuf_addf(&cert, "nonce %s\n", push_cert_nonce);
-	if (args->push_options)
+	if (args->push_options) {
 		for_each_string_list_item(item, args->push_options)
 			strbuf_addf(&cert, "push-option %s\n", item->string);
+	}
 	strbuf_addstr(&cert, "\n");
 
 	for (ref = remote_refs; ref; ref = ref->next) {


Luckily, reasonably modern compilers warn about such ambiguity, so
perhaps this is an acceptable compromise?


> > [...]
> > Does the following alternate fix work?  I think I prefer it because
> > it doesn't require introducing a new global. [...]
> >  #define for_each_string_list_item(item,list) \
> > -	for (item = (list)->items; item < (list)->items + (list)->nr; ++item)
> > +	for (item = (list)->items; \
> > +	     (list)->items && item < (list)->items + (list)->nr; \
> > +	     ++item)
> 
> This is the possibility that I was referring to as "add[ing] overhead to
> each iteration of the loop". I'd rather not add an extra test-and-branch
> to every iteration of a loop in which `list->items` is *not* NULL, which
> your solution appears to do. Or are compilers routinely able to optimize
> the check out?
> 
> The new global might be aesthetically unpleasant, but it only costs two
> words of memory, so I don't see it as a big disadvantage.
> 
> Another, more invasive change would be to initialize
> `string_list::items` to *always* point at `dummy_string_list_item`,
> rather similar to how `strbuf_slopbuf` is pointed at by empty `strbuf`s.
> But I really don't think the effort would be justified.

Re: [PATCH] for_each_string_list_item(): behave correctly for empty list

[Michael Haggerty]

On 09/16/2017 01:51 PM, SZEDER Gábor wrote:
>>>> It would be a pain to have to change the signature of this macro, and
>>>> we'd prefer not to add overhead to each iteration of the loop. So
>>>> instead, whenever `list->items` is NULL, initialize `item` to point at
>>>> a dummy `string_list_item` created for the purpose.
>>>
>>> What signature change do you mean?  I don't understand what this
>>> paragraph is alluding to.
>>
>> I was thinking that one solution would be for the caller to provide a
>> `size_t` variable for the macro's use as a counter (since I don't see a
>> way for the macro to declare its own counter). The options are pretty
>> limited because whatever the macro expands to has to play the same
>> syntactic role as `for (...; ...; ...)`.
> 
> Another option to consider is to squeeze in an if-else before the for
> loop header to handle the empty list case like this:
> 
> diff --git a/string-list.h b/string-list.h
> index 29bfb7ae4..9eed47de0 100644
> --- a/string-list.h
> +++ b/string-list.h
> @@ -32,8 +32,11 @@ void string_list_clear_func(struct string_list *list, string_list_clear_func_t c
>  typedef int (*string_list_each_func_t)(struct string_list_item *, void *);
>  int for_each_string_list(struct string_list *list,
>  			 string_list_each_func_t, void *cb_data);
> -#define for_each_string_list_item(item,list) \
> -	for (item = (list)->items; item < (list)->items + (list)->nr; ++item)
> +#define for_each_string_list_item(item,list) 	\
> +	if ((list)->items == NULL) {		\
> +		/* empty list, do nothing */	\
> +	} else					\
> +		for (item = (list)->items; item < (list)->items + (list)->nr; ++item)
>  
>  /*
>   * Apply want to each item in list, retaining only the ones for which
> 
> This way there would be neither additional overhead in each iteration
> nor a new global.
> 
> Alas, there is a catch.  We can't use curly braces in the macro's else
> branch, because the macro would contain only the opening brace but not
> the closing one, which must come after the end of the loop's body.
> This means that the modified macro couldn't be used in if-else
> branches which themselves don't have curly braces, because it causes
> ambiguity:
> 
>   if (condition)
>       for_each_string_list_item(item, list)
>           a_simple_oneliner(item);

It's not ambiguous as far as the language standard is concerned. The
latter is clear that an `else` binds to the nearest `if`. The problem is
that this is a common programmer error, so compilers "helpfully" warn
about it even though it would do exactly what we want.

> Our coding guidelines encourage this style for one-liner loop bodies,
> and there is indeed one such place in our codebase, so the following
> hunk is needed as well:
> 
> diff --git a/send-pack.c b/send-pack.c
> index 11d6f3d98..00fa1622f 100644
> --- a/send-pack.c
> +++ b/send-pack.c
> @@ -295,9 +295,10 @@ static int generate_push_cert(struct strbuf *req_buf,
>  	}
>  	if (push_cert_nonce[0])
>  		strbuf_addf(&cert, "nonce %s\n", push_cert_nonce);
> -	if (args->push_options)
> +	if (args->push_options) {
>  		for_each_string_list_item(item, args->push_options)
>  			strbuf_addf(&cert, "push-option %s\n", item->string);
> +	}
>  	strbuf_addstr(&cert, "\n");
>  
>  	for (ref = remote_refs; ref; ref = ref->next) {
> 
> 
> Luckily, reasonably modern compilers warn about such ambiguity, so
> perhaps this is an acceptable compromise?

This change kindof goes *against* our coding guidelines, so it's not
ideal either, but I suppose we could probably live with it.

Michael

Re: [PATCH] for_each_string_list_item(): behave correctly for empty list

[Kaartic Sivaraam]

On Saturday 16 September 2017 09:36 AM, Michael Haggerty wrote:
>> Does the following alternate fix work?  I think I prefer it because
>> it doesn't require introducing a new global. [...]
>>   #define for_each_string_list_item(item,list) \
>> -	for (item = (list)->items; item < (list)->items + (list)->nr; ++item)
>> +	for (item = (list)->items; \
>> +	     (list)->items && item < (list)->items + (list)->nr; \
>> +	     ++item)
> This is the possibility that I was referring to as "add[ing] overhead to
> each iteration of the loop". I'd rather not add an extra test-and-branch
> to every iteration of a loop in which `list->items` is *not* NULL, which
> your solution appears to do. Or are compilers routinely able to optimize
> the check out?

It seems at least 'gcc' is able to optimize this out even with a -O1
and 'clang' optimizes this out with a -O2. Taking a sneak peek at
the 'Makefile' shows that our default is -O2.

For a proof, see https://godbolt.org/g/CPt73L

---
Kaartic

Re: [PATCH] for_each_string_list_item(): behave correctly for empty list

[Junio C Hamano]

Kaartic Sivaraam <kaarticsivaraam91196@gmail.com> writes:

> On Saturday 16 September 2017 09:36 AM, Michael Haggerty wrote:
>>> Does the following alternate fix work?  I think I prefer it because
>>> it doesn't require introducing a new global. [...]
>>>   #define for_each_string_list_item(item,list) \
>>> -	for (item = (list)->items; item < (list)->items + (list)->nr; ++item)
>>> +	for (item = (list)->items; \
>>> +	     (list)->items && item < (list)->items + (list)->nr; \
>>> +	     ++item)
>> This is the possibility that I was referring to as "add[ing] overhead to
>> each iteration of the loop". I'd rather not add an extra test-and-branch
>> to every iteration of a loop in which `list->items` is *not* NULL, which
>> your solution appears to do. Or are compilers routinely able to optimize
>> the check out?
>
> It seems at least 'gcc' is able to optimize this out even with a -O1
> and 'clang' optimizes this out with a -O2. Taking a sneak peek at
> the 'Makefile' shows that our default is -O2.

But doesn't the versions of gcc and clang currently available do the
right thing with the current code without this change anyway?  I've
been operating under the assumption that this is to future-proof the
code even when the compilers change to use the "NULL+0 is undefined"
as an excuse to make demons fly out of your nose, so unfortunately I
do not think it is not so huge a plus to find that the current
compilers do the right thing to the code with proposed updates.

Re: [PATCH] for_each_string_list_item(): behave correctly for empty list

[Jonathan Nieder]

Hi,

Junio C Hamano wrote:
> Kaartic Sivaraam <kaarticsivaraam91196@gmail.com> writes:
>> On Saturday 16 September 2017 09:36 AM, Michael Haggerty wrote:
>>> Jonathan Nieder wrote:

>>>> Does the following alternate fix work?  I think I prefer it because
>>>> it doesn't require introducing a new global. [...]
>>>>   #define for_each_string_list_item(item,list) \
>>>> -	for (item = (list)->items; item < (list)->items + (list)->nr; ++item)
>>>> +	for (item = (list)->items; \
>>>> +	     (list)->items && item < (list)->items + (list)->nr; \
>>>> +	     ++item)
>>>
>>> This is the possibility that I was referring to as "add[ing] overhead to
>>> each iteration of the loop". I'd rather not add an extra test-and-branch
>>> to every iteration of a loop in which `list->items` is *not* NULL, which
>>> your solution appears to do. Or are compilers routinely able to optimize
>>> the check out?
>>
>> It seems at least 'gcc' is able to optimize this out even with a -O1
>> and 'clang' optimizes this out with a -O2. Taking a sneak peek at
>> the 'Makefile' shows that our default is -O2.
>
> But doesn't the versions of gcc and clang currently available do the
> right thing with the current code without this change anyway?  I've
> been operating under the assumption that this is to future-proof the
> code even when the compilers change to use the "NULL+0 is undefined"
> as an excuse to make demons fly out of your nose, so unfortunately I
> do not think it is not so huge a plus to find that the current
> compilers do the right thing to the code with proposed updates.

I think you and Kaartic are talking about different things.  Kaartic
was checking that this wouldn't introduce a performance regression
(thanks!).  You are concerned about whether the C standard and common
practice treat the resulting code as exhibiting undefined behavior.

Fortunately the C standard is pretty clear about this.  The undefined
behavior here is at run time, not compile time.  As you suggested in
an earlier reply, the 'list->items &&' effectively guards the
'list->items + list->nr' to prevent that undefined behavior.

I'll send a patch with a commit message saying so to try to close out
this discussion.

Thanks,
Jonathan

Re: [PATCH] for_each_string_list_item(): behave correctly for empty list

[Junio C Hamano]

Jonathan Nieder <jrnieder@gmail.com> writes:

> I'll send a patch with a commit message saying so to try to close out
> this discussion.

Thanks.  One less thing we have to worry about ;-)

Re: [PATCH] for_each_string_list_item(): behave correctly for empty list

[Jonathan Nieder]

Hi,

Kaartic Sivaraam wrote:
> On Saturday 16 September 2017 09:36 AM, Michael Haggerty wrote:
>> Jonathan Nieder wrote:

>>> Does the following alternate fix work?  I think I prefer it because
>>> it doesn't require introducing a new global. [...]
>>>   #define for_each_string_list_item(item,list) \
>>> -	for (item = (list)->items; item < (list)->items + (list)->nr; ++item)
>>> +	for (item = (list)->items; \
>>> +	     (list)->items && item < (list)->items + (list)->nr; \
>>> +	     ++item)
>>
>> This is the possibility that I was referring to as "add[ing] overhead to
>> each iteration of the loop". I'd rather not add an extra test-and-branch
>> to every iteration of a loop in which `list->items` is *not* NULL, which
>> your solution appears to do. Or are compilers routinely able to optimize
>> the check out?
>
> I t seems at least 'gcc' is able to optimize this out even with a -O1
> and 'clang' optimizes this out with a -O2. Taking a sneak peek at
> the 'Makefile' shows that our default is -O2.
>
> For a proof, see https://godbolt.org/g/CPt73L

From that link:

    for ( ;valid_int && *valid_int < 10; (*valid_int)++) {
        printf("Valid instance");
    }

Both gcc and clang are able to optimize out the 'valid_int &&' because
it is dereferenced on the RHS of the &&.

For comparison, 'item < (list)->items + (list)->nr' does not
dereference (list)->items.  So that optimization doesn't apply here.

A smart compiler could be able to take advantage of there being no
object pointed to by a null pointer, which means

	item < (list)->items + (list)->nr

is always false when (list)->items is NULL, which in turn makes a
'(list)->items &&' test redundant.  But a quick test with gcc 4.8.4
-O2 finds that at least this compiler does not contain such an
optimization.  The overhead Michael Haggerty mentioned is real.

Thanks and hope that helps,
Jonathan

Re: [PATCH] for_each_string_list_item(): behave correctly for empty list

[Junio C Hamano]

Jonathan Nieder <jrnieder@gmail.com> writes:

> ...  But a quick test with gcc 4.8.4
> -O2 finds that at least this compiler does not contain such an
> optimization.  The overhead Michael Haggerty mentioned is real.

Still, I have a feeling that users of string_list wouldn't care 
the overhead of single pointer NULL-ness check.

 - apply.c collects conflicted paths and reports them with fprintf().

 - builtin/clean.c uses the function to walk the list of paths to be
   removed, and either does a human interaction (for "-i" codepath)
   or goes to the filesystem to remove things.

 - builtin/config.c uses it in get_urlmatch() in preparation for
   doing network-y things.

 - builtin/describe.c walks the list of exclude and include patterns
   to run wildmatch on the candidate reference name to filter it out.

 ...

In all of these examples, what happens for each item in the loop
seems to me far heavier than the overhead this macro adds.

So...

[PATCH v2] for_each_string_list_item: avoid undefined behavior for empty list

[Jonathan Nieder]

From: Michael Haggerty <mhagger@alum.mit.edu>

If you pass a newly initialized or newly cleared `string_list` to
`for_each_string_list_item()`, then the latter does

    for (
            item = (list)->items; /* NULL */
            item < (list)->items + (list)->nr; /* NULL + 0 */
            ++item)

Even though this probably works almost everywhere, it is undefined
behavior, and it could plausibly cause highly-optimizing compilers to
misbehave.  C99 section 6.5.6 paragraph 8 explains:

    If both the pointer operand and the result point to elements
    of the same array object, or one past the last element of the
    array object, the evaluation shall not produce an overflow;
    otherwise, the behavior is undefined.

and (6.3.2.3.3) a null pointer does not point to anything.

Guard the loop with a NULL check to make the intent crystal clear to
even the most pedantic compiler.  A suitably clever compiler could let
the NULL check only run in the first iteration, but regardless, this
overhead is likely to be dwarfed by the work to be done on each item.

This problem was noticed by Coverity.

[jn: using a NULL check instead of a placeholder empty list;
 fleshed out the commit message based on mailing list discussion]

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Jonathan Nieder <jrnieder@gmail.com>
---
 string-list.h | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

Junio C Hamano wrote:
> Jonathan Nieder <jrnieder@gmail.com> writes:

>> ...  But a quick test with gcc 4.8.4
>> -O2 finds that at least this compiler does not contain such an
>> optimization.  The overhead Michael Haggerty mentioned is real.
>
> Still, I have a feeling that users of string_list wouldn't care
> the overhead of single pointer NULL-ness check.
>
>  - apply.c collects conflicted paths and reports them with fprintf().
>
>  - builtin/clean.c uses the function to walk the list of paths to be
>    removed, and either does a human interaction (for "-i" codepath)
>    or goes to the filesystem to remove things.
>
>  - builtin/config.c uses it in get_urlmatch() in preparation for
>    doing network-y things.
>
>  - builtin/describe.c walks the list of exclude and include patterns
>    to run wildmatch on the candidate reference name to filter it out.
>
>  ...
>
> In all of these examples, what happens for each item in the loop
> seems to me far heavier than the overhead this macro adds.

Yes, agreed.  As a small tweak,

   #define for_each_string_list_item(item, list) \
	for (item = ...; item && ...; ...)

produces nicer assembly than

   #define for_each_string_list_item(item, list) \
	for (item = ...; list->items && ...; ...)

(By the way, the potential optimization I described isn't valid: we
know that when item == NULL and list->items == NULL, list->nr is
always zero, but the compiler has no way to know that.  So it can't
eliminate the NULL test.  For comparison, a suitably smart compiler
should be able to eliminate a 'list->nr != 0 &&' guard if 'list'
doesn't escape in the loop body.)

Recapping the other proposed fixes:

A. Make it an invariant of string_list that items is never NULL and
   update string_list_init et al to use an empty array.  This is
   pretty painless until you notice some other structs that embed
   string_list without using STRING_LIST_INIT.  Updating all those
   would be too painful.

B. #define for_each_string_list_item(item, list) \
	if (list->items) \
		for (item = ...; ...; ... )

   This breaks a caller like
	if (foo)
		for_each_string_list_item(item, list)
			...
	else
		...

   making it a non-starter.

C. As Gábor suggested,
   #define for_each_string_list_item(item, list) \
   	if (!list->items) \
		; /* nothing to do */ \
	else \
		for (item = ...; ...; ...)

   This handles the caller from (B) correctly.  But it produces
   compiler warnings for a caller like

	if (foo)
		for_each_string_list_item(item, list)
			...

   There is only one instance of that construct in git today.  It
   looks nicer anyway with braces, so this approach would also be
   promising.

D. Eliminate for_each_string_list_item and let callers just do

	unsigned int i;
	for (i = 0; i < list->nr; i++) {
		struct string_list_item *item = list->items[i];
		...
	}

   Having to declare item is unnecessarily verbose, decreasing the
   appeal of this option.  I think I like it anyway, but I wasn't able
   to convince coccinelle to do it.

E. Use subtraction instead of addition:
   #define for_each_string_list_item(item, list) \
   	for (item = ...; \
	     (item == list->items ? 0 : item - list->items) < nr; \
	     item++)

   I expected the compiler to figure out that this is a long way of writing
   (item - list->items), but at least with gcc 4.8.4 -O2, no such
   luck.  This generates uglier assembly than the NULL check.

diff --git a/string-list.h b/string-list.h
index 29bfb7ae45..79ae567cbc 100644
--- a/string-list.h
+++ b/string-list.h
@@ -32,8 +32,10 @@ void string_list_clear_func(struct string_list *list, string_list_clear_func_t c
 typedef int (*string_list_each_func_t)(struct string_list_item *, void *);
 int for_each_string_list(struct string_list *list,
 			 string_list_each_func_t, void *cb_data);
-#define for_each_string_list_item(item,list) \
-	for (item = (list)->items; item < (list)->items + (list)->nr; ++item)
+#define for_each_string_list_item(item,list)            \
+	for (item = (list)->items;                      \
+	     item && item < (list)->items + (list)->nr; \
+	     ++item)
 
 /*
  * Apply want to each item in list, retaining only the ones for which
-- 
2.14.1.821.g8fa685d3b7

Re: [PATCH v2] for_each_string_list_item: avoid undefined behavior for empty list

[Junio C Hamano]

Jonathan Nieder <jrnieder@gmail.com> writes:

> D. Eliminate for_each_string_list_item and let callers just do
>
> 	unsigned int i;
> 	for (i = 0; i < list->nr; i++) {
> 		struct string_list_item *item = list->items[i];
> 		...
> 	}
>
>    Having to declare item is unnecessarily verbose, decreasing the
>    appeal of this option.  I think I like it anyway, but I wasn't able
>    to convince coccinelle to do it.

When using the macro, item still needs to be declared outside by the
user, so it's not all that unpleasant, though.

> E. Use subtraction instead of addition:
>    #define for_each_string_list_item(item, list) \
>    	for (item = ...; \
> 	     (item == list->items ? 0 : item - list->items) < nr; \
> 	     item++)
>
>    I expected the compiler to figure out that this is a long way of writing
>    (item - list->items), but at least with gcc 4.8.4 -O2, no such
>    luck.  This generates uglier assembly than the NULL check.

Yuck.  You cannot easily unsee such an ugliness X-<.

The patch and explanation above --- looked quite nicely written.
Will queue.

Thanks.

> diff --git a/string-list.h b/string-list.h
> index 29bfb7ae45..79ae567cbc 100644
> --- a/string-list.h
> +++ b/string-list.h
> @@ -32,8 +32,10 @@ void string_list_clear_func(struct string_list *list, string_list_clear_func_t c
>  typedef int (*string_list_each_func_t)(struct string_list_item *, void *);
>  int for_each_string_list(struct string_list *list,
>  			 string_list_each_func_t, void *cb_data);
> -#define for_each_string_list_item(item,list) \
> -	for (item = (list)->items; item < (list)->items + (list)->nr; ++item)
> +#define for_each_string_list_item(item,list)            \
> +	for (item = (list)->items;                      \
> +	     item && item < (list)->items + (list)->nr; \
> +	     ++item)
>  
>  /*
>   * Apply want to each item in list, retaining only the ones for which

Re: [PATCH v2] for_each_string_list_item: avoid undefined behavior for empty list

[Michael Haggerty]

On 09/20/2017 07:27 AM, Jonathan Nieder wrote:
> From: Michael Haggerty <mhagger@alum.mit.edu>
> 
> If you pass a newly initialized or newly cleared `string_list` to
> `for_each_string_list_item()`, then the latter does
> 
>     for (
>             item = (list)->items; /* NULL */
>             item < (list)->items + (list)->nr; /* NULL + 0 */
>             ++item)
> 
> Even though this probably works almost everywhere, it is undefined
> behavior, and it could plausibly cause highly-optimizing compilers to
> misbehave.  C99 section 6.5.6 paragraph 8 explains:
> 
>     If both the pointer operand and the result point to elements
>     of the same array object, or one past the last element of the
>     array object, the evaluation shall not produce an overflow;
>     otherwise, the behavior is undefined.
> 
> and (6.3.2.3.3) a null pointer does not point to anything.
> 
> Guard the loop with a NULL check to make the intent crystal clear to
> even the most pedantic compiler.  A suitably clever compiler could let
> the NULL check only run in the first iteration, but regardless, this
> overhead is likely to be dwarfed by the work to be done on each item.
> 
> This problem was noticed by Coverity.
> 
> [jn: using a NULL check instead of a placeholder empty list;
>  fleshed out the commit message based on mailing list discussion]

Thanks for taking this over. This version LGTM.

> [...]
Michael

Re: [PATCH v2] for_each_string_list_item: avoid undefined behavior for empty list

[Kaartic Sivaraam]

On Wednesday 20 September 2017 10:57 AM, Jonathan Nieder wrote:
> Guard the loop with a NULL check to make the intent crystal clear to
> even the most pedantic compiler.  A suitably clever compiler could let
> the NULL check only run in the first iteration,

Noted this just now. So, the overhead doesn't occur when the compilers
are clever enough. And as I said in my previous email to this thread, at
least 'gcc' and 'clang' seem to be clever enough.
> ... but regardless, this
> overhead is likely to be dwarfed by the work to be done on each item.

:-) That's of course seems to be true.

[PATCH v2] doc: camelCase the config variables to improve readability

[Kaartic Sivaraam]

A few configuration variable names of Git are composite words. References
to such variables in manpages are hard to read because they use all-lowercase
names, without indicating where each word ends and begins.

Improve its readability by using camelCase instead.  Git treats these
names case-insensitively so this does not affect functionality. This
also ensures consistency with other parts of the docs that use camelCase
fo refer to configuration variable names.

Signed-off-by: Kaartic Sivaraam <kaarticsivaraam91196@gmail.com>
Reviewed-by: Jonathan Nieder <jrnieder@gmail.com>
---
 Documentation/git-branch.txt | 4 ++--
 Documentation/git-tag.txt    | 2 +-
 2 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/Documentation/git-branch.txt b/Documentation/git-branch.txt
index e292737b9c5ab..58f1e5c9c74e1 100644
--- a/Documentation/git-branch.txt
+++ b/Documentation/git-branch.txt
@@ -92,10 +92,10 @@ OPTIONS
 	all changes made to the branch ref, enabling use of date
 	based sha1 expressions such as "<branchname>@\{yesterday}".
 	Note that in non-bare repositories, reflogs are usually
-	enabled by default by the `core.logallrefupdates` config option.
+	enabled by default by the `core.logAllRefUpdates` config option.
 	The negated form `--no-create-reflog` only overrides an earlier
 	`--create-reflog`, but currently does not negate the setting of
-	`core.logallrefupdates`.
+	`core.logAllRefUpdates`.
 
 -f::
 --force::
diff --git a/Documentation/git-tag.txt b/Documentation/git-tag.txt
index 543fb425ee7c1..95e9f391d88fc 100644
--- a/Documentation/git-tag.txt
+++ b/Documentation/git-tag.txt
@@ -174,7 +174,7 @@ This option is only applicable when listing tags without annotation lines.
 	`core.logAllRefUpdates` in linkgit:git-config[1].
 	The negated form `--no-create-reflog` only overrides an earlier
 	`--create-reflog`, but currently does not negate the setting of
-	`core.logallrefupdates`.
+	`core.logAllRefUpdates`.
 
 <tagname>::
 	The name of the tag to create, delete, or describe.

--
https://github.com/git/git/pull/407

Re: [PATCH v2] for_each_string_list_item: avoid undefined behavior for empty list

[Andreas Schwab]

On Sep 19 2017, Jonathan Nieder <jrnieder@gmail.com> wrote:

> B. #define for_each_string_list_item(item, list) \
> 	if (list->items) \
> 		for (item = ...; ...; ... )
>
>    This breaks a caller like
> 	if (foo)
> 		for_each_string_list_item(item, list)
> 			...
> 	else
> 		...
>
>    making it a non-starter.

That can be fixed with a dangling else.

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: [PATCH v2] for_each_string_list_item: avoid undefined behavior for empty list

[Jonathan Nieder]

Andreas Schwab wrote:
> On Sep 19 2017, Jonathan Nieder <jrnieder@gmail.com> wrote:

>> B. #define for_each_string_list_item(item, list) \
>> 	if (list->items) \
>> 		for (item = ...; ...; ... )
>>
>>    This breaks a caller like
>> 	if (foo)
>> 		for_each_string_list_item(item, list)
>> 			...
>> 	else
>> 		...
>>
>>    making it a non-starter.
>
> That can be fixed with a dangling else.

I believe the fix you're referring to is option C, from the same email
you are replying to.  If not, please correct me.

Thanks,
Jonathan

Re: [PATCH v2] for_each_string_list_item: avoid undefined behavior for empty list

[Andreas Schwab]

On Sep 20 2017, Jonathan Nieder <jrnieder@gmail.com> wrote:

> Andreas Schwab wrote:
>> On Sep 19 2017, Jonathan Nieder <jrnieder@gmail.com> wrote:
>
>>> B. #define for_each_string_list_item(item, list) \
>>> 	if (list->items) \
>>> 		for (item = ...; ...; ... )
>>>
>>>    This breaks a caller like
>>> 	if (foo)
>>> 		for_each_string_list_item(item, list)
>>> 			...
>>> 	else
>>> 		...
>>>
>>>    making it a non-starter.
>>
>> That can be fixed with a dangling else.
>
> I believe the fix you're referring to is option C, from the same email
> you are replying to.  If not, please correct me.

A variant thereof, yes.

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: [PATCH v2] for_each_string_list_item: avoid undefined behavior for empty list

[Junio C Hamano]

Andreas Schwab <schwab@linux-m68k.org> writes:

> On Sep 20 2017, Jonathan Nieder <jrnieder@gmail.com> wrote:
>
>> Andreas Schwab wrote:
>>> On Sep 19 2017, Jonathan Nieder <jrnieder@gmail.com> wrote:
>>
>>>> B. #define for_each_string_list_item(item, list) \
>>>> 	if (list->items) \
>>>> 		for (item = ...; ...; ... )
>>>>
>>>>    This breaks a caller like
>>>> 	if (foo)
>>>> 		for_each_string_list_item(item, list)
>>>> 			...
>>>> 	else
>>>> 		...
>>>>
>>>>    making it a non-starter.
>>>
>>> That can be fixed with a dangling else.
>>
>> I believe the fix you're referring to is option C, from the same email
>> you are replying to.  If not, please correct me.
>
> A variant thereof, yes.

Now you make me curious.  How would that variant be different from
option C. in Jonathan's message?  Perhaps that different version may
be a solution to work around the potential issue mentioned in the
description of option C.?

Re: [PATCH v2] for_each_string_list_item: avoid undefined behavior for empty list

[Andreas Schwab]

On Sep 21 2017, Junio C Hamano <gitster@pobox.com> wrote:

> Now you make me curious.  How would that variant be different from
> option C. in Jonathan's message?

Only in the parity of the condition.

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: [PATCH] for_each_string_list_item(): behave correctly for empty list

[Kaartic Sivaraam]

Hi,

Though this thread seems to have reached a conclusion, I just wanted to
know what I was missing about the optimisation.

On Wednesday 20 September 2017 08:00 AM, Jonathan Nieder wrote:
> From that link:
>      for ( ;valid_int && *valid_int < 10; (*valid_int)++) {
>          printf("Valid instance");
>      }
>
> Both gcc and clang are able to optimize out the 'valid_int &&' because
> it is dereferenced on the RHS of the &&.
>
> For comparison, 'item < (list)->items + (list)->nr' does not
> dereference (list)->items.  So that optimization doesn't apply here.
>
> A smart compiler could be able to take advantage of there being no
> object pointed to by a null pointer, which means
>
> 	item < (list)->items + (list)->nr
>
> is always false when (list)->items is NULL, which in turn makes a
> '(list)->items &&' test redundant.  But a quick test with gcc 4.8.4
> -O2 finds that at least this compiler does not contain such an
> optimization.  The overhead Michael Haggerty mentioned is real.
>

I thought the compiler optimized that check out of the loop because the
check was "invariant" across loop runs. IOW, the values used in the check
didn't change across loop runs so the compiler thought it's better to do
the check once outside the loop rather than doing it each time inside
the loop. I guess this is some kind of "loop unswitching"[1]. I don't 
see how
dereferencing influences the optimization here.

Just to be sure, I tried once more to see whether the compiler optimizes 
this
or not. This time with a more similar example and even using the macro 
of concern.
Surprisingly, the compiler did optimize the check out of the loop. This 
time both
'gcc' and 'clang' with an -O1 !

https://godbolt.org/g/Y6rHc1
https://godbolt.org/g/EMrftw

So, is the overhead still real or am I missing something?

[1] : https://en.wikipedia.org/wiki/Loop_unswitching

---
Kaartic

Re: [PATCH] for_each_string_list_item(): behave correctly for empty list

[Junio C Hamano]

Michael Haggerty <mhagger@alum.mit.edu> writes:

> If you pass a newly-initialized or newly-cleared `string_list` to
> `for_each_string_list_item()`, then the latter does
>
>     for (
>             item = (list)->items; /* note, this is NULL */
>             item < (list)->items + (list)->nr; /* note: NULL + 0 */
>             ++item)
>
> Even though this probably works almost everywhere, it is undefined
> behavior, and it could plausibly cause highly-optimizing compilers to
> misbehave.
> ...
> It would be a pain to have to change the signature of this macro, and
> we'd prefer not to add overhead to each iteration of the loop. So
> instead, whenever `list->items` is NULL, initialize `item` to point at
> a dummy `string_list_item` created for the purpose.
> ...
> -#define for_each_string_list_item(item,list) \
> -	for (item = (list)->items; item < (list)->items + (list)->nr; ++item)
> +extern struct string_list_item dummy_string_list_item;
> +#define for_each_string_list_item(item,list)                                 \
> +	for (item = (list)->items ? (list)->items : &dummy_string_list_item; \
> +	     item < (list)->items + (list)->nr;                              \
> +	     ++item)

Sorry, but I am confused.

So when (list)->items is NULL, the loop termination condition that
used to be

	NULL < NULL + 0

that was problematic because NULL + 0 is problematic now becomes

	&dummy < NULL + 0

in the new code?  What made NULL + 0 not problematic now?

Re: [PATCH] for_each_string_list_item(): behave correctly for empty list

[Michael Haggerty]

On 09/17/2017 02:59 AM, Junio C Hamano wrote:
> Michael Haggerty <mhagger@alum.mit.edu> writes:
> 
>> If you pass a newly-initialized or newly-cleared `string_list` to
>> `for_each_string_list_item()`, then the latter does
>>
>>     for (
>>             item = (list)->items; /* note, this is NULL */
>>             item < (list)->items + (list)->nr; /* note: NULL + 0 */
>>             ++item)
>>
>> Even though this probably works almost everywhere, it is undefined
>> behavior, and it could plausibly cause highly-optimizing compilers to
>> misbehave.
>> ...
>> It would be a pain to have to change the signature of this macro, and
>> we'd prefer not to add overhead to each iteration of the loop. So
>> instead, whenever `list->items` is NULL, initialize `item` to point at
>> a dummy `string_list_item` created for the purpose.
>> ...
>> -#define for_each_string_list_item(item,list) \
>> -	for (item = (list)->items; item < (list)->items + (list)->nr; ++item)
>> +extern struct string_list_item dummy_string_list_item;
>> +#define for_each_string_list_item(item,list)                                 \
>> +	for (item = (list)->items ? (list)->items : &dummy_string_list_item; \
>> +	     item < (list)->items + (list)->nr;                              \
>> +	     ++item)
> 
> Sorry, but I am confused.
> 
> So when (list)->items is NULL, the loop termination condition that
> used to be
> 
> 	NULL < NULL + 0
> 
> that was problematic because NULL + 0 is problematic now becomes
> 
> 	&dummy < NULL + 0
> 
> in the new code?  What made NULL + 0 not problematic now?

*sigh* of course you're right. I should know better than to "fire off a
quick fix to the mailing list".

I guess the two proposals that are still in the running for rescuing
this macro are Jonathan's and Gábor's. I have no strong preference
either way.

Michael

Re: [PATCH] for_each_string_list_item(): behave correctly for empty list

[Junio C Hamano]

Michael Haggerty <mhagger@alum.mit.edu> writes:

> *sigh* of course you're right. I should know better than to "fire off a
> quick fix to the mailing list".
>
> I guess the two proposals that are still in the running for rescuing
> this macro are Jonathan's and Gábor's. I have no strong preference
> either way.

If somebody is writing this outisde a macro as a one-shot thing, the
most natural and readable way I would imagine would be

	if (the list is empty)
        	;
	else
		for (each item in the list)
			work on item

I would think.  That "work on item" part may not be a single
expression statement and instead be a compound statement inside a
pair of braces {}.  Making a shorter version, i.e.

	if (!the list is empty)
		for (each item in the list)
			work on item

into a macro probably has syntax issues around cascading if/else
chain, e.g.

	if (condition caller cares about)
		for_each_string_list_item() {
			do this thing
		}
	else
		do something else

would expand to

	if (condition caller cares about)
		if (!the list is empty)
			for (each item in the list) {
				do this thing
			}
	else
		do something else

which is wrong.  But I couldn't think of a way to break the longer
one with the body of the macro in the "else" clause in a similar
way.  An overly helpful compiler might say

	if (condition caller cares about)
		if (the list is empty)
			;
		else
			for (each item in the list) {
				do this thing
			}
	else
		do something else

that it wants a pair of {} around the then-clause of the outer if;
if we can find a way to squelch such warnings only with this
construct that comes from the macro, then this solution may be ideal.

If we cannot do that, then

	for (item = (list)->items; /* could be NULL */
	     (list)->items && item < (list)->items + (list)->nr;
	     item++)
		work on item

may be an obvious way to write it without any such syntax worries,
but I am unclear how a "undefined behaviour" contaminate the code
around it.  My naive reading of the termination condition of the
above is:

	"(list)->items &&" clearly means that (list)->items is not
	NULL in what follows it, i.e. (list->items + (list)->nr
	cannot be a NULL + 0, so we are not allowed to make demon
	fly out of your nose.

but I wonder if this alternative reading is allowed:

	(list)->items is not assigned to in this expression and is
	used in a subexpression "(list)->items + (list)->nr" here;
	for that subexpression not to be "undefined", it cannot be
	NULL, so we can optimize out "do this only (list)->items is
	not NULL" part.

which takes us back to where we started X-<.  So I dunno.

I am hoping that this last one is not allowed and we can use the
"same condition is checked every time we loop" version that hides
the uglyness inside the macro.

Re: [PATCH] for_each_string_list_item(): behave correctly for empty list

[Stefan Beller]

> I am hoping that this last one is not allowed and we can use the
> "same condition is checked every time we loop" version that hides
> the uglyness inside the macro.

By which you are referring to Jonathans solution posted.
Maybe we can combine the two solutions (checking for thelist
to not be NULL once, by Jonathan) and using an outer structure
(SZEDERs solution) by replacing the condition by a for loop,
roughly (untested):

#define for_each_string_list_item(item,list) \
-       for (item = (list)->items; item < (list)->items + (list)->nr; ++item)
+    for (; list; list = NULL)
+        for (item = (list)->items; item < (list)->items + (list)->nr; ++item)

as that would not mingle with any dangling else clause.
It is also just one statement, such that

    if (bla)
      for_each_string_list_item {
        baz(item);
      }
    else
      foo;

still works.

Are there downsides to this combined approach?

Re: [PATCH] for_each_string_list_item(): behave correctly for empty list

[Michael Haggerty]

On 09/19/2017 02:08 AM, Stefan Beller wrote:
>> I am hoping that this last one is not allowed and we can use the
>> "same condition is checked every time we loop" version that hides
>> the uglyness inside the macro.
> 
> By which you are referring to Jonathans solution posted.
> Maybe we can combine the two solutions (checking for thelist
> to not be NULL once, by Jonathan) and using an outer structure
> (SZEDERs solution) by replacing the condition by a for loop,
> roughly (untested):
> 
> #define for_each_string_list_item(item,list) \
> -       for (item = (list)->items; item < (list)->items + (list)->nr; ++item)
> +    for (; list; list = NULL)
> +        for (item = (list)->items; item < (list)->items + (list)->nr; ++item)
> 
> as that would not mingle with any dangling else clause.
> It is also just one statement, such that
> 
>     if (bla)
>       for_each_string_list_item {
>         baz(item);
>       }
>     else
>       foo;
> 
> still works.
> 
> Are there downsides to this combined approach?

On the plus side, it's pleasantly devious; I wouldn't have thought of
using a `for` loop for the initial test. But it doesn't work as written,
because (1) we don't need to guard against `list` being NULL, but rather
`list->items`; and (2) we don't have the liberty to set `list = NULL`
(or `list->items = NULL`, because `list` is owned by the caller and we
shouldn't modify it.

The following is a bit closer:

#define for_each_string_list_item(item,list) \
	for (item = (list)->items; item; item = NULL) \
        	for (; item < (list)->items + (list)->nr; ++item)

But I think that also fails, because a callsite that does

	for_each_string_list_item(myitem, mylist)
		if (myitem.util)
			break;

would expect that `myitem` is still set after breaking out of the loop,
whereas the outer `for` loop would reset it to NULL.

If `break` were an expression we could do something like

#define for_each_string_list_item(item,list) \
	for (item = (list)->items; item; break) \
        	for (; item < (list)->items + (list)->nr; ++item)

So I think we're still left with the suggestions of Jonathan or Gábor.
Or the bigger change of initializing `string_list::items` to point at an
empty sentinal array (similar to `strbuf_slopbuf`) rather than NULL.
Personally, I think that Jonathan's approach makes the most sense,
unless somebody wants to jump in an implement a `string_list_slopbuf`.

By the way, I wonder if any open-coded loops over `string_lists` make
the same mistake as the macro?

Michael

Re: [PATCH] for_each_string_list_item(): behave correctly for empty list

[SZEDER Gábor]

On Tue, Sep 19, 2017 at 8:51 AM, Michael Haggerty <mhagger@alum.mit.edu> wrote:
> On 09/19/2017 02:08 AM, Stefan Beller wrote:
>>> I am hoping that this last one is not allowed and we can use the
>>> "same condition is checked every time we loop" version that hides
>>> the uglyness inside the macro.
>>
>> By which you are referring to Jonathans solution posted.
>> Maybe we can combine the two solutions (checking for thelist
>> to not be NULL once, by Jonathan) and using an outer structure
>> (SZEDERs solution) by replacing the condition by a for loop,
>> roughly (untested):
>>
>> #define for_each_string_list_item(item,list) \
>> -       for (item = (list)->items; item < (list)->items + (list)->nr; ++item)
>> +    for (; list; list = NULL)
>> +        for (item = (list)->items; item < (list)->items + (list)->nr; ++item)
>>
>> as that would not mingle with any dangling else clause.
>> It is also just one statement, such that
>>
>>     if (bla)
>>       for_each_string_list_item {
>>         baz(item);
>>       }
>>     else
>>       foo;
>>
>> still works.
>>
>> Are there downsides to this combined approach?
>
> On the plus side, it's pleasantly devious; I wouldn't have thought of
> using a `for` loop for the initial test. But it doesn't work as written,
> because (1) we don't need to guard against `list` being NULL, but rather
> `list->items`; and (2) we don't have the liberty to set `list = NULL`
> (or `list->items = NULL`, because `list` is owned by the caller and we
> shouldn't modify it.
>
> The following is a bit closer:
>
> #define for_each_string_list_item(item,list) \
>         for (item = (list)->items; item; item = NULL) \
>                 for (; item < (list)->items + (list)->nr; ++item)
>
> But I think that also fails, because a callsite that does
>
>         for_each_string_list_item(myitem, mylist)
>                 if (myitem.util)
>                         break;
>
> would expect that `myitem` is still set after breaking out of the loop,
> whereas the outer `for` loop would reset it to NULL.
>
> If `break` were an expression we could do something like
>
> #define for_each_string_list_item(item,list) \
>         for (item = (list)->items; item; break) \
>                 for (; item < (list)->items + (list)->nr; ++item)

A bit "futuristic" option along these lines could be something like
this, using a scoped loop variable in the outer loop to ensure that
it's executed at most once:

  #define for_each_string_list_item(item,list) \
      for (int f_e_s_l_i = 1; (list)->items && f_e_s_l_i; f_e_s_l_i = 0) \
          for (item = (list)->items; item < (list)->items + (list)->nr; ++item)

The high number of underscores are an attempt to make reasonably sure
that the macro's loop variable doesn't shadow any variable in its
callers or isn't being shadowed in the loop body, which might(?)
trigger warnings in some compilers.

Alas we don't allow scoping the loop variable in for loops, and even a
test balloon patch didn't make it into git.git.

  https://public-inbox.org/git/20170719181956.15845-1-sbeller@google.com/T/#u


> So I think we're still left with the suggestions of Jonathan or Gábor.
> Or the bigger change of initializing `string_list::items` to point at an
> empty sentinal array (similar to `strbuf_slopbuf`) rather than NULL.
> Personally, I think that Jonathan's approach makes the most sense,
> unless somebody wants to jump in an implement a `string_list_slopbuf`.
>
> By the way, I wonder if any open-coded loops over `string_lists` make
> the same mistake as the macro?

Re: [PATCH] for_each_string_list_item(): behave correctly for empty list

[SZEDER Gábor]

On Tue, Sep 19, 2017 at 3:38 PM, SZEDER Gábor <szeder.dev@gmail.com> wrote:
> A bit "futuristic" option along these lines could be something like
> this, using a scoped loop variable in the outer loop to ensure that
> it's executed at most once:
>
>   #define for_each_string_list_item(item,list) \
>       for (int f_e_s_l_i = 1; (list)->items && f_e_s_l_i; f_e_s_l_i = 0) \
>           for (item = (list)->items; item < (list)->items + (list)->nr; ++item)
>
> The high number of underscores are an attempt to make reasonably sure
> that the macro's loop variable doesn't shadow any variable in its
> callers or isn't being shadowed in the loop body, which might(?)
> trigger warnings in some compilers.

Well, and a poor attempt at that, because, of course, the loop
variable would still be shadowed in nested for_each_string_list_item
loops...  And our codebase has these loops nested in
entry.c:finish_delayed_checkout().

OTOH, we don't seem to care too much about shadowed variables, since
building with -Wshadow gives 91 warnings in current master...