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]

Jonathan Nieder  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

[Junio C Hamano]

Jonathan Nieder  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...

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

[Jonathan Nieder]

Hi,

Junio C Hamano wrote:
> Kaartic Sivaraam  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]

Kaartic Sivaraam  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

[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

[SZEDER Gábor]

On Tue, Sep 19, 2017 at 3:38 PM, SZEDER Gábor  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...

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  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-sbel...@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

[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

[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

[Junio C Hamano]

Michael Haggerty  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

[Michael Haggerty]

On 09/17/2017 02:59 AM, Junio C Hamano wrote:
> Michael Haggerty  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 : _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
> 
>< 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

[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(, "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(, "push-option %s\n", item->string);
> + }
>   strbuf_addstr(, "\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

[Junio C Hamano]

Michael Haggerty  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 : _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

 < 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

[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(, "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(, "push-option %s\n", item->string);
+   }
strbuf_addstr(, "\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/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

[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 
> ---
[...]
>  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