How does BOOST_PP_SEQ_FOLD_LEFT work?

Question

I need to write a macro that processes an arbitrarily long list of things like (A)(B)(C). If I could take a Boost dependency, I would just use one of the BOOST_PP_SEQ_ family of macros. Unfortunately, I can't so I am left trying to figure out how it works. This Stuff Is Not Obvious.

Can anybody here write a simple, stand-alone implementation of, say, BOOST_PP_SEQ_FOLD_LEFT for me to look at? In particular, I would like to transform:

template_(class A, class B, class C)(
    requires IsFoo<A> && IsBar<B>)(
    requires IsBaz<C>)
void frobozzle(A, B, C);

to be rewritten as:

template<class A, class B, class C,
    int dummy = 0,
    std::enable_if_t<dummy == 0 && (IsFoo<A> && IsBar<B>), int> = 0,
    std::enable_if_t<dummy == 0 && (IsBaz<C>), int> = 0>
void frobozzle(A, B, C);

There could be an arbitrary number of requires clauses, and they should each get their own enable_if_t. I have it working with one requires clause, but I exhausted my C preprocessor-fu in the process.

It's OK to assume a std-compliant preprocessor, since I don't need MSVC support.

Answer 1

If you add an extra set of parentheses in your syntax, it's possible without a limit on the number of 'required' clauses, with relatively few macros:

template_((class A, class B, class C)
    (requires IsFoo<A> && IsBar<B>)
    (requires IsBaz<C>)
)
void frobozzle(A, B, C);

Macros:

#define template_(...) template_impl_ADD_END(template_impl_LIST __VA_ARGS__) >

#define template_impl_ADD_END(...) template_impl_ADD_END2(__VA_ARGS__)
#define template_impl_ADD_END2(...) __VA_ARGS__ ## _END

#define template_impl_LIST(...) template<__VA_ARGS__, int dummy = 0 template_impl_LIST_1

#define template_impl_LIST_1(...) , std::enable_if_t<dummy == 0 && template_impl_REQUIRES(__VA_ARGS__), int> = 0 template_impl_LIST_2
#define template_impl_LIST_2(...) , std::enable_if_t<dummy == 0 && template_impl_REQUIRES(__VA_ARGS__), int> = 0 template_impl_LIST_1

#define template_impl_REQUIRES(...) (template_impl_REQUIRES_ ## __VA_ARGS__)
#define template_impl_REQUIRES_requires

#define template_impl_LIST_END
#define template_impl_LIST_1_END
#define template_impl_LIST_2_END

With these macros, the example above expands to:

template <class A, class B, class C,
          int dummy = 0,
          std::enable_if_t<dummy == 0 && (IsFoo<A> && IsBar<B>), int> = 0,
          std::enable_if_t<dummy == 0 && (IsBaz<C>), int> = 0>

void frobozzle(A, B, C);

Explanation

Consider these macros:

#define a(x) [x] b
#define b(x) [x] a

With these, this:

a (1) (2) (3) (4)

Will cause a 'chain reaction' of expansion as follows:

a (1) (2) (3) (4)
[1] b (2) (3) (4)
[1] [2] a (3) (4)
[1] [2] [3] b (4)
[1] [2] [3] [4] a

Recursion isn't allowed in the preprocessor, but this type of chain reaction isn't recursion since the invocation of the macro only happens after expansion of the previous one, not during, since the ( isn't part of the expansion. (Although, see https://wg21.link/cwg268)

Unfortunately, although this will nicely loop over a sequence of (A)(B)(C), it'll leave an extra token at the end: the name of one of the two used macros. The trick I used to get rid of that one, is to wrap the entire list with another macro invocation, that will append (with the concat operator ##) _END after the full expansion, so it will become:

[1] [2] [3] [4] a_END

Then we can simply get rid of this last token by defining:

#define a_END
#define b_END

If we can't wrap the entire list, there's no way to know when we've reached the last element. The only thing that happens is that the last a or b is left over without a ( that follows it, meaning that it simply won't expand, as a and b are function-style macros. (And we can't just define a and b to expand to nothing, because a and b are already macros, although they won't expand without a (.)

Why two macros?

When we try to cause a chain reaction like the above, with just one macro like this:

#define a(x) [x] a

It won't work:

a (1) (2) (3) (4)
[1] a (2) (3) (4) // Doesn't expand further

This is because of how the '(infinite) recursion protection' works: If during the expansion of a macro, a token with the name of the macro being expanded is produced, it is marked as 'unexpandable', meaning that it will never ever expand again. See http://eel.is/c++draft/cpp.rescan#2

This means that the expanded a is marked as 'unexpandable', and our chain reaction stops right there after the first step. We avoid this by using two macros to work around this rule: a(..) will not produce any token with its own name, but only with the name of the other macro b. The expansion of a ends right there, before b is expanded, because there is no ( yet after b, since we're 'inside' the expansion of a. After the expansion is done, and we're no longer 'inside' a, the tokens get re-examined, and a proper invocation of b is found: b(..). That one will produce a token with the name of a again, but since we're no longer in the expansion of the first a, this one will not be marked as 'unexpandable', and the chain reaction continues.

Answer 2

Alright, here's a quick and dirty thing I whipped up that I think you can use:

#include <iostream>

#define LIST (1)(2)(3)(4)

#define EAT2(list)
#define EAT(list) EAT2 list
#define KEEP(x) x EAT2(
#define STRINGIFY2(x) #x
#define STRINGIFY(x) STRINGIFY2(x)

#define HEAD(list) KEEP list )
#define TAIL(list) EAT(list)
int main()
{
    std::cout << STRINGIFY(HEAD(LIST)) << std::endl;
    std::cout << STRINGIFY(TAIL(LIST)) << std::endl;
}

Basically, you need to get tricky with how you call macros.
Take for example:

HEAD((1)(2))

expands to

KEEP (1)(2) )

which expands to

1 EAT2 ((2))

which expands to

1

This isn't a full answer, but I think can be a starting point for what you want to to do.

EDIT

I have now figured out how BOOST.PP does its iterations and it's not pretty, you basically manually write out iterations up to some maximum size.

#define CONCAT2(x, y) x##y
#define CONCAT(x, y) CONCAT2(x, y)

#define SEQ_SIZE(seq) CONCAT(SEQ_SIZE_, SEQ_SIZE_0 seq)

# define SEQ_SIZE_0(_) SEQ_SIZE_1
# define SEQ_SIZE_1(_) SEQ_SIZE_2
# define SEQ_SIZE_2(_) SEQ_SIZE_3
# define SEQ_SIZE_3(_) SEQ_SIZE_4
# define SEQ_SIZE_4(_) SEQ_SIZE_5
# define SEQ_SIZE_5(_) SEQ_SIZE_6
# define SEQ_SIZE_6(_) SEQ_SIZE_7
# define SEQ_SIZE_7(_) SEQ_SIZE_8
# define SEQ_SIZE_8(_) SEQ_SIZE_9
# define SEQ_SIZE_9(_) SEQ_SIZE_10
# define SEQ_SIZE_10(_) SEQ_SIZE_11
# define SEQ_SIZE_SEQ_SIZE_0 0
# define SEQ_SIZE_SEQ_SIZE_1 1
# define SEQ_SIZE_SEQ_SIZE_2 2
# define SEQ_SIZE_SEQ_SIZE_3 3
# define SEQ_SIZE_SEQ_SIZE_4 4
# define SEQ_SIZE_SEQ_SIZE_5 5
# define SEQ_SIZE_SEQ_SIZE_6 6
# define SEQ_SIZE_SEQ_SIZE_7 7
# define SEQ_SIZE_SEQ_SIZE_8 8
# define SEQ_SIZE_SEQ_SIZE_9 9
# define SEQ_SIZE_SEQ_SIZE_10 10

#define MAKE_VAR(elem)                         \
    float CONCAT(var_, elem) = 0;

#define MAKE_LIST_0(op, list)
#define MAKE_LIST_1(op, list)  op (HEAD(list)) MAKE_LIST_0(op, TAIL(list))
#define MAKE_LIST_2(op, list)  op (HEAD(list)) MAKE_LIST_1(op, TAIL(list))
#define MAKE_LIST_3(op, list)  op (HEAD(list)) MAKE_LIST_2(op, TAIL(list))
#define MAKE_LIST_4(op, list)  op (HEAD(list)) MAKE_LIST_3(op, TAIL(list))
#define MAKE_LIST_5(op, list)  op (HEAD(list)) MAKE_LIST_4(op, TAIL(list))
#define MAKE_LIST_6(op, list)  op (HEAD(list)) MAKE_LIST_5(op, TAIL(list))
#define MAKE_LIST_7(op, list)  op (HEAD(list)) MAKE_LIST_6(op, TAIL(list))
#define MAKE_LIST_8(op, list)  op (HEAD(list)) MAKE_LIST_7(op, TAIL(list))
#define MAKE_LIST_9(op, list)  op (HEAD(list)) MAKE_LIST_8(op, TAIL(list))
#define MAKE_LIST_10(op, list)  op (HEAD(list)) MAKE_LIST_9(op, TAIL(list))

#define MAKE_LIST(op, list) CONCAT(MAKE_LIST_, SEQ_SIZE(list)) (op, list)

int main()
{
    MAKE_LIST(MAKE_VAR, LIST)
}

Running the preprocessor on this gives the following:

int main()
{
    float var_1 = 0; float var_2 = 0; float var_3 = 0; float var_4 = 0; float var_5 = 0;
}

As desired. I'm sure this could be streamlined a bit, but I hope this helps.