Zephyr: sys/util: add support for mapping lists with per-element terminal symbols

[pabigot]

tl;dr: we could use FOR_EACH_TERM() as a companion to FOR_EACH().

Background

The existing FOR_EACH(macro,sep,...list) generates the sequence from running macro on each element of list, with sep between each invocation's result. It has two limitations:

• If list is empty a cascade of errors is produced;
• It requires an externally supplied sep after the last element if a terminator is required rather than a separator.

26062 includes a commit that introduces FOR_EACH_NONEMPTY(macro,sep,list) that behaves correctly when list is empty, but does not address the lack of a separator. This means it cannot be repeated when initializing arrays. For example, if used to combine dependencies from a node with external dependencies, as in:

static const device_handle_t ordinals[] = {
    FOR_EACH_NONEMPTY(DT_DEP_ORD, (,), DT_SUPPORTS(NODE)),
    OTHER_ORDINALS
};

a syntax error would be diagnosed if DT_SUPPORTS(NODE) had no elements, because the separating , would be the first token in the array initialization. If there were node elements , is required when OTHER_ORDINALS is not empty.

Proposal

I would like to see this capability: FOR_EACH_TERM(macro,term,...list) which runs produces the sequence from running macro on each element of list and appending term after each invocation's result. I.e. with #define IDENTITY(x) x:

• FOR_EACH_TERM(IDENTITY,(;)) produces the empty sequence;
• FOR_EACH_TERM(IDENTITY,(;),a) produces the sequence a;;
• FOR_EACH_TERM(IDENTITY,(;),a,b,c) produces the sequence a;b;c;.

This functionality enables generating arrays of values that represent a set of sets. E.g. in support of providing runtime access to node parent/child and dependency information it would allow me to do:

static const device_handle_t ordinals[] = {
    DT_DEP_ORD(NODE),
    DT_DEP_ORD(DT_PARENT(NODE)),
    FOR_EACH_TERM(DT_DEP_ORD, (,), DT_CHILDREN(NODE))
    DEVICE_HANDLE_SEP,
    FOR_EACH_TERM(DT_DEP_ORD, (,), DT_REQUIRES(NODE))
    DEVICE_HANDLE_SEP,
    FOR_EACH_TERM(DT_DEP_ORD, (,), DT_SUPPORTS(NODE))
    DEVICE_HANDLE_ENDS,
};

This would encode all node relations in a single compact array referenced from struct device.

[mbolivar-nordic]

I have so far tried and failed to make this work.

The trouble is that with the function-like macro "signature" FOR_EACH_TERM(macro, term, ...), there is a subtle difference between these:

1. FOR_EACH_TERM(IDENTITY, (;))
2. FOR_EACH_TERM(IDENTITY, (;), )

The first one receives zero arguments in __VA_ARGS__. The second receives one, but it's empty.

So this, for example:

FOR_EACH_TERM(DT_DEP_ORD, (,), DT_SUPPORTS(NODE))

is equivalent to:

DT_DEP_ORD(EMPTY) ,

whenever DT_SUPPORTS(NODE) is EMPTY. That causes build errors, and this isn't a fix either for the same reason:

FOR_EACH_TERM(DT_DEP_ORD, (,), LIST_DROP_EMPTY(DT_SUPPORTS(NODE)))

I will propose combining our two existing proposals, to create a new macro FOR_EACH_NONEMPTY_TERM(macro, term, ...), for which:

• FOR_EACH_NONEMPTY_TERM(IDENTITY, (;)) produces the empty sequence
• FOR_EACH_NONEMPTY_TERM(IDENTITY, (;), ) also produces the empty sequence
• FOR_EACH_NONEMPTY_TERM(IDENTITY, (;), ,) also produces the empty sequence (you get the idea)
• FOR_EACH_NONEMPTY_TERM(IDENTITY, (;), a) produces a;
• FOR_EACH_NONEMPTY_TERM(IDENTITY, (;), a, b) produces a; b;
• FOR_EACH_NONEMPTY_TERM(IDENTITY, (;), a, , b) also produces a; b;

Since DT_SUPPORTS and DT_REQUIRES expand to an empty sequence or a sequence of comma-separated tokens without any empty elements, dropping the empties is a no-op except exactly when we need it to be.

[pabigot]

It looks like your FOR_EACH_NONEMPTY_TERM() implements the behavior I requested for FOR_EACH_TERM(). Why can't we just use that name?

I ask in part because FOR_EACH_NONEMPTY() bothers me because I read it as saying "This is a for-each that works as long as the passed list is not empty", and I don't think I should have to check for that as a special case. (I think it rather means "for each element that expands to a non-empty token sequence", which is useful but is something different.)

Having FOR_EACH() fail to compile when given an empty sequence is arguably a bug. Is there anything that would break if FOR_EACH() was re-implemented in the way you propose for FOR_EACH_NONEMPTY() in #26062? I.e. are there uses that expect it to produce something for empty arguments?

[pabigot]

@nordic-krch @de-nordic please provide input on this API and FOR_EACH generally.

[nordic-krch]

maybe FOR_EACH should execute macro only on non-empty items so FOR_EACH(F,(,),,,,) resolves to nothing. Not sure if it is doable. Even if there is a use case for applying macro to empty elements that should probably be an exception, i mean FOR_EACH_EMPTY.

[mbolivar-nordic]

It looks like your FOR_EACH_NONEMPTY_TERM() implements the behavior I requested for FOR_EACH_TERM(). Why can't we just use that name?

It's not the same. Your request was:

produces the sequence from running macro on each element of list

Not "each nonempty element of list". That is the subtle difference I am referring to in https://github.com/zephyrproject-rtos/zephyr/issues/26219#issuecomment-645739619.

maybe FOR_EACH should execute macro only on non-empty items so FOR_EACH(F,(,),,,,) resolves to nothing. Not sure if it is doable. Even if there is a use case for applying macro to empty elements that should probably be an exception, i mean FOR_EACH_EMPTY.

That's fine with me too; thanks, @nordic-krch. I just didn't want to change the existing API.

OK, so conclusion is we will make FOR_EACH filter out empties. This makes sense to me as well.

[nordic-krch]

OK, so conclusion is we will make FOR_EACH filter out empties.

Easier said than done. Unfortunately, emptiness detection relies on concatenation and it won't work for arguments which will not generate valid token (e.g. parentheses) so it cannot be applied to generic macro like FOR_EACH which no accepts every argument. Added clarification to IS_EMPTY #26293.

[de-nordic]

Maybe we should drop support for FOR_EACH with empty lists (i.e.: FOR_EACH_NONEMPTY_TERM(IDENTITY, (;))), and request the list param to be in ( ), the same way the separator is provided.

This would give us one FOR_EACH macro: FOR_EACH(macro, (separator), (list)).

Would it be possible for us to manipulate the list parameter to figure out whether it is empty and just do nothing (COND_CODE_? way or sth?) or process it or internally drop all "empty" elements prior to passing it for further evaluation in in internal FOR_EACH implementation?

[nordic-krch]

I've found ISEMPTY alternative which handles all arguments:
https://gustedt.wordpress.com/2010/06/08/detect-empty-macro-arguments/

tried to incorporate that into FOR_EACH with promising results.

@de-nordic @pabigot @mbolivar-nordic do you know how licensing for things like this look like? Can we take it into util_internal.h?

[mbolivar-nordic]

@pabigot @nordic-krch I suggest that bd860783761b2a6a2d4ae6d0f4276035f1de6317 resolves this issue -- @pabigot please close if you agree.

[pabigot]

This went back and forth on so many levels I have no idea what the status is, but since I will have what I need once #26062 and #27761 get in I'm pretty sure this isn't relevant any more.