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

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:

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.