From Token Sequences to operator for
Iterating Ranges, Insanely and Then Properly
operator for A year and a half ago now, I wrote a post about using token sequences to iterate ranges. In that post, I talked about the overhead that certain range adaptors fundamentally have because they don’t neatly fit into the regular C++ for loop (particularly views::take_while and views::reverse), how Tristan Brindle’s Flux library addresses these limitations with its own for_each implementation that uses internal iteration to just do the optimal thing, and then I walked through an insane solution using token sequences with an early implementation of that feature that Daveed Vandevoorde provided in EDG.
That token sequence implementation is old though. Since then, we’ve iterated on the token sequence injection proposal quite a bit, I have a new implementation up in Clang, so I wanted to revisit my implementation here. But I didn’t just want to translate what I had before, that’s pretty boring. So instead, I’m going to significantly up the insanity.
The point here isn’t necessarily to say that what I’m going to present is actually a good idea for people to use in their code. But I think it’s a good demonstration of what sorts of things might be possible, and the value that allowing these sorts of shenanigans can provide.
Let’s get started.
With Great Power Comes Great Potential For Fun
The original implementation, which is still usable on compiler explorer, used this syntax:
consteval {
for2(
^^{ int& i },
^^{ v | std::views::filter(is_even) | std::views::reverse },
^^{
i += 1;
});
}
That’s pretty syntactically heavy. A lot of the characters here are just machinery to pass the right arguments that you need, and I don’t like that. With the new model, we’re proposing a new kind of macro (not to be confused with C preprocessor macros, with which they have very little in common), that would instead allow this syntax:
for_each!(int& i : v | std::views::filter(is_even) | std::views::reverse, {
i += 1;
});
Which looks pretty close to a regular range-based for loop! That’s a pretty significant improvement.
Before I get to talking about how to declare, and then implement, this new for_each macro, there’s one more aspect of syntax that needs to be considered: the range side. How does a particular range adapter opt-in to internal iteration? In the original implementation, the filter_view opt-in looked like this:
template <class R, class P, int I>
struct inject_tokens_impl<std::ranges::filter_view<R, P>, I> {
static consteval auto apply(Direction dir, info init, info body) -> void {
inject_tokens(^^{ auto \id("__r"sv, I+1) = \id("__r"sv, I).base(); });
inject_tokens(^^{ auto \id("__pred"sv, I+1) = \id("__r"sv, I).pred(); });
inject_tokens_impl<R, I+1>::apply(dir,
^^{ auto&& \id("__elem"sv, I+1) },
^^{
if (\id("__pred"sv, I+1)(\id("__elem"sv, I+1))) {
\tokens(init) = \id("__elem"sv, I+1);
\tokens(body);
}
}
);
}
};
The recursive call to apply here is how we iterate the next layer down, and then you can sort of see what we’re doing is just an if statement and then doing the body. That’s what a filter is, after all.
Now there’s a lot that would look different if I were to simply translate this approach to my current ideas for token injection, but rather than simply translating, let’s have some fun. Internal iteration is sort of like a generator — I want to be able to express that I’m just pushing elements out. And the way in C++ that we write a generator is by using co_yield. What would the filter_view loop look like if we write it as a generator?
Well, it might look like this:
template <class V, class P>
struct loop_traits<std::ranges::filter_view<V, P>> {
static consteval auto loop(token_sequence self, direction dir)
-> token_sequence
{
auto pred = unique_id("p");
auto elem = unique_id("e");
return ^^{
auto&& $pred = $self.pred();
iter::for_each_dir!($dir, auto&& $elem : $self.base(), {
if ($pred($elem)) {
co_yield $elem;
}
});
};
}
};
Again, we have another macro that will do our iteration for us, that is trying to look like a regular range-based for loop. And rather than passing around declarations and bodies, we’re pushing them out. We’re using a new reflection API, std::meta::unique_id(), to give us a unique identifier, which makes everything a lot easier to deal with.
Note that we’re not actually going to be using C++20 coroutines. I’m just using the
co_yieldkeyword.
Skipping ahead to the end — the example I had in the original post, translated to the new macro API, looks like this:
auto make_rng = [&]{
return v
| std::views::take_while(lt5)
| std::views::filter(is_even)
| std::views::reverse
;
};
for_each!(int i : make_rng(), {
std::cout << "* got " << i << '\n';
if (i > 10) {
break;
}
});
What actual code does that emit? It looks something like this (this is the -Xclang -ast-print output, with the formatting slightly cleaned up):
auto &&r#1 = make_rng();
{
auto &&r#4 = std::move(r#1).base();
auto &&filter_pred#5 = std::move(r#4).pred();
{
auto &&r#8 = std::move(r#4).base();
auto &&tw_pred#9 = std::move(r#8).pred();
auto &&tw_full#11 = std::move(r#8).base();
auto tw_sr#12 = std::ranges::subrange(
std::ranges::begin(tw_full#11),
std::ranges::find_if_not(tw_full#11, tw_pred#9));
{
auto &&r#14 = tw_sr#12;
auto last#15 = std::ranges::begin(r#14);
auto it#16 = std::ranges::next(last#15, std::ranges::end(r#14));
while (it#16 != last#15)
{
-- it#16;
auto &&tw_elem#10 = * it#16;
{
auto &&filter_elem#6 = tw_elem#10;
do {
if (filter_pred#5(filter_elem#6)) {
auto &&rev_elem#2 = filter_elem#6;
do {
int i = rev_elem#2;
do {
std::cout << "* got " << i << '\n';
if (i > 10) {
goto done#3;
}
} while (false);
} while (false);
}
} while (false);
}
}
}
}
}
done#3:
Some important points to note here right off the bat. You’ll note that there are no co_yields in the emitted code. Also the break that I had in the macro invocation turned into a goto to a new label that didn’t used to exist either. You’ll see lots of variables whose identifiers aren’t really valid C++ identifiers, that’s what std::meta::unique_id() produces in order to help ensure uniqueness — the prefixes on those variables can also help track where each bit came from. There’s a bunch of extra identifiers in here that could probably be removed if the goal were maximum clarity (e.g. here, i is initialized to rev_elem#2 which is just a binding for filter_elem#6 which is just a binding for tw_elem#10 which is itself a binding to *it#16) — we could collapse them all away too, but I’m keeping them in the post for clarity.
And in terms of the resultant code structure — we see that the loop here is the right shape for reverse iteration: it’s a while loop that decrements before dereferencing. The take_while search happens up front, and the filter turns into a simple if. Optimal.
Now how do we actually implement this? Let’s start from the macro invocation side and work our way towards rewriting the body.
Working our way outside in
Our entry point is the for_each macro. That one’s pretty simple, since we’re just forwarding to a different macro with another argument:
// for_each!(decl : range, stmt)
__macro for_each(std::meta::token_sequence head, std::meta::token_sequence body) {
return ^^{ iter::for_each_dir!(iter::direction::forward, $head, $body) };
}
In order to implement looping optimally, we need to have first-class support for directionality. In this case, I’m just doing it with an enum. for_each_dir also has a pretty simple job: parse the head into the decl and the range and forward each along so that we can deduce the type of the range. In order to split head properly, we need to find the : — which of course isn’t trivial because the spelling of the type could be arbitrarily complex and I want to be able to handle decltype(a ? b : c) d : e. So we need to do a balanced find, not just a simple find, where we’re keeping track of nested ()s, []s, and {}s (but not <>s!). This has come up enough in my examples that I just added it as a member function on token_sequence:
// for_each_dir!(dir, decl : range, stmt)
__macro for_each_dir(direction dir, token_sequence head, token_sequence body) {
auto [elem, range] = head.balanced_split_at(punctuator::colon);
if (range.empty()) {
std::constexpr_error_str("for_each", "expected 'declaration : range'");
}
return ^^{ iter::for_each_range!($dir, $elem, $range, $body) };
}
for_each_dir is what the range adapters will actually call (as shown earlier), but for_each_range is what does the work. There are three cases here:
- the range type provides its own custom looping implementation, use that
- otherwise, if we’re iterating forward, write the usual forward loop
- otherwise, we’re iterating in reverse, so write the correct reverse loop
That looks like this:
template <class R>
__macro for_each_range(direction _dir,
token_sequence elem,
R&& range,
token_sequence body) {
auto r = unique_id("r");
auto dir = extract<direction>(constant_of(_dir));
if (auto fn = loop_function(^^R)) {
auto loop = extract<token_sequence(*)(token_sequence, direction)>(*fn);
auto src = is_lvalue_reference_type(^^R) ? ^^{ $r } : ^^{ std::move($r) };
return ^^{
auto&& $r = $range;
${paste_yields(loop(src, dir), elem, body)};
};
}
auto last = unique_id("last");
auto it = unique_id("it");
if (dir == direction::forward) {
return ^^{
auto&& $r = $range;
auto $it = std::ranges::begin($r);
auto $last = std::ranges::end($r);
for (; $it != $last; ++$it) {
$elem = *$it;
$body
}
};
} else {
return ^^{
auto&& $r = $range;
auto $last = std::ranges::begin($r);
auto $it = std::ranges::next($last, std::ranges::end($r));
while ($it != $last) {
--$it;
$elem = *$it;
$body
}
};
}
}
The bottom two-thirds of the implementation here are, outside of all the novelty with token sequences and $s, I think fairly straightforward. We evaluate the range argument, and iterate whichever way we need to, and the body ultimately evaluates the declaration and then the body. In these cases, we don’t have to do anything special to handle the body having break or continue — since we’re inside of a single loop, they will just do the right thing.
Already here we see one of the big open questions for this design — which is what to do about hygiene. In the previous post’s implementation, I passed around the layer — so all the variables were named stuff like
r0,r1,r2, etc. Here, I’m no longer doing that, and relying onunique_id()to give me unique names. That’s because this token sequence model is very “what you write is what you get.” The behavior of an injected identifier is the same as if you’d written that by hand. In other words, there is no hygiene in this direction.A very different model would be that an identifier in a token sequence would look up what’s visible from where it’s written in source, while also adding barriers for what names can be found in what contexts when it comes to token sequences. Such a model adds complexity to what a token sequence is (every identifier token would have to track where it came from), but it would make it easier to write this sort of code —
unique_idwouldn’t be necessary. And the full qualification I’m writing in some cases wouldn’t be necessary either, because my local helpers would be looked up from the context I wrote them, not the context they’re injected into. Which is appealing, but would mean that token sequence injection is no longer a simple “just inject these tokens.”
The customization point is where we actually have to do very interesting things… and completely go off the rails.
Customizing loop bodies
Customization has three parts: we need to find the customization, we need to get the customized loop body, and then we need to swap it out for real code.
The actual customization is the easy part. There will be a loop_traits<R> class template and we’ll look for either R::loop or loop_traits<R>::loop:
template <class R> struct loop_traits;
consteval auto loop_function(info R) -> std::optional<info> {
R = remove_cvref(R);
for (info target : {R, substitute(^^loop_traits, {R})}) {
if (is_complete_type(target) and is_class_type(target)) {
auto fn = lookup(target, "loop", access_context::unchecked());
if (fn) {
return fn;
}
}
}
return std::nullopt;
}
std::meta::lookup(tgt, name, ctx) is a new function that I added that… basically just does what it sounds like: looks up name in tgt, returning an optional<info> that is either what lookup found or nothing.
Now, if one of these lookups succeeds, then we’ll get a reflection representing a function, which we’ve already seen one example of. That function needs to take a token_sequence (the range we’re looping over) and a direction (which direction we’re looping in) and needs to return the code necessary to do that looping. Let’s look at that customization again, now that we know a little bit more about what we’re doing. In fact, let’s look at a few different ones:
// filter
template <class V, class P>
struct loop_traits<std::ranges::filter_view<V, P>> {
static consteval auto loop(token_sequence self, direction dir)
-> token_sequence
{
auto pred = unique_id("filter_pred");
auto elem = unique_id("filter_elem");
return ^^{
auto&& $pred = $self.pred();
iter::for_each_dir!($dir, auto&& $elem : $self.base(), {
if ($pred($elem)) {
co_yield $elem;
}
});
};
}
};
// join: just two nested loops. note that iterating backwards is just
// a matter of iterating the outer loop backwards and then the inner
// loop backwards, that's all we need to do
template <class V>
struct loop_traits<std::ranges::join_view<V>> {
static consteval auto loop(token_sequence self, direction dir)
-> token_sequence
{
auto inner = unique_id("inner");
auto elem = unique_id("elem");
return ^^{
iter::for_each_dir!($dir, auto&& $inner : $self.base(), {
iter::for_each_dir!($dir, auto&& $elem : $inner, {
co_yield $elem;
});
});
};
}
};
// reverse: just flip the direction. our enum supports negation
template <class V>
struct loop_traits<std::ranges::reverse_view<V>> {
static consteval auto loop(token_sequence self, direction dir)
-> token_sequence
{
auto elem = unique_id("rev_elem");
return ^^{
iter::for_each_dir!(${not dir}, auto&& $elem : $self.base(), {
co_yield $elem;
});
};
}
};
// take_while: this one is actually interesting, because we
// specifically do different things for the two directions
template <class V, class P>
struct loop_traits<std::ranges::take_while_view<V, P>> {
static consteval auto loop(token_sequence self, direction dir)
-> token_sequence
{
auto pred = unique_id("tw_pred");
auto elem = unique_id("tw_elem");
if (dir == direction::forward) {
return ^^{
auto&& $pred = $self.pred();
iter::for_each_dir!($dir, auto&& $elem : $self.base(), {
if (!$pred($elem)) {
break;
}
co_yield $elem;
});
};
} else {
// first find where it stops, then iterate that subrange.
auto full = unique_id("tw_full");
auto sr = unique_id("tw_sr");
return ^^{
auto&& $pred = $self.pred();
auto&& $full = $self.base();
auto $sr = std::ranges::subrange(
std::ranges::begin($full),
std::ranges::find_if_not($full, $pred));
iter::for_each_dir!($dir, auto&& $elem : $sr, {
co_yield $elem;
});
};
}
}
};
Hopefully you get the idea. Which is that none of these customizations are actually all that complex. That shouldn’t be surprising — internal iteration is fundamentally much simpler than external iteration. Imagine how much code it would take to support this using iterators?
But the code we’re generating so far has a co_yield in it. The code we’re actually emitting needs to not have co_yield, since we’re not really using C++20 coroutines. I just picked syntax that I thought was pretty. Plus, how can we properly handle break — which very much needs to break the entire loop and not just the inner one, if what we have is join_view!
That’s what paste_yields() is for. Its job is to take the body and replace the uses of co_yield <E>; with something that makes the actual loop structure work. So the first thing we would think to do is to replace co_yield <E>; with the statement:
{
$elem = <E>;
$body
}
The problem with this approach is that it doesn’t necessarily handle continue or break properly. I say necessarily, because it actually could already handle both fine. Indeed, for filter, when the base is a single loop, it’s already correct. But for join, a break would only break out of the inner loop, not the outer loop.
Let’s do continue first, because it turns out that’s very easy to handle. We just need to ensure that $body is in a loop:
{
$elem = <E>;
do {
$body
} while(false);
}
If you were wondering why the generated code I showed earlier had all these do { ... } while(false) loops, that’s why — I’m simply wrapping the body so that continue does the right thing. Which — all it needs to do is move onto the next iteration, which is to say that all we need to do is get to the end of $body. To that end, this is a cheap way to do so.
break is much harder, for two reasons. First, we can’t just leave break; by itself in the body, since now it would just break out of that loop we stuck in there, so it’d have the same meaning as continue, which makes it hard to differentiate between the two. There might be some clever approach to actually constructing this loop that helps you differentiate the cases, but in a way that would probably push the implementations of join and concat to have to manually handle control flow — which I don’t really want to do. Instead, what we have to do is create a new label at the end of the loop and rewrite any break; that appears into a goto $done;. And make sure you don’t inject the label if we don’t actually need to.
But second, okay, we know we need to rewrite the break; statements but… how do we know which breaks are this loop and which are some other loop that shows up in the body? Only way I think is to actually parse the body to keep track of whether we’re in a loop (or switch), similar to how balanced_find keeps track of brackets.
Incidentally, Jai’s approach to loop customization involves explicit
breakrewriting as a language feature. And also has loop direction as a first class loop feature.
Rewriting the breaks is the hard part here, the rest is fairly straightforward:
consteval auto paste_yields(token_sequence loop,
token_sequence elem,
token_sequence body) -> token_sequence
{
auto done = unique_id("done");
// find all the breaks and rewrite them into a goto
// returning true if any were actually rewritten
// rewrite_breaks mutates body (if necessary)
bool used_break = rewrite_breaks(body, ^^{ goto $done });
token_sequence out;
size_t i = 0;
while (true) {
size_t const next = loop.find(^^{ co_yield }, i);
out += loop.subseq(i, next);
if (next == loop.npos) {
break;
}
size_t const semi = loop.balanced_find(^^{ ; }, next + 1);
// in co_yield <E>; value is <E>
token_sequence value = loop.subseq(next + 1, semi - next - 1);
// this is the substitution we just discussed
out += ^^{ { $elem = $value; do { $body } while (false); } };
i = semi + 1;
}
if (used_break) {
return ^^{ { $out } $done:; };
} else {
return out;
}
}
Where rewrite_breaks is… well, it’s pretty tedious. I don’t think it’s super interesting compared to everything else here, except to note that it’s (a) doable (b) definitely buggy and (c) surprisingly only about 100 lines of code.
You can see the full implementation on, of course, Compiler Explorer. You can pass -Xclang -ast-print to see the generated code (you’ll have to scroll way down though, it starts on line 79,974). The implementation of rewrite_breaks starts on line 44.
Disposition
Now, as I mentioned earlier, it’s very cool that this is implementable at all. I think it can easily lead to a lot of experimenting with new ideas, some of which could turn into very cool libraries. Surprisingly to me, the compile time for this isn’t even all that bad. The cost to compile a call to iter::for_each!(...) is only about 3x the cost of compiling a regular range-based for loop! And given that it can be significantly more runtime-efficient, maybe that’s not even all that bad a trade-off.
But also, it’s kind of a ridiculous thing. So it might be nice to produce something… less ridiculous?
A Proper Language Feature: operator for
What if I could take my ideas from this token sequence range-based for loop rewriting and stick them into the language directly? What could that look like?
Previous work
Three years ago, Jonathan Müller and I cowrote a paper on a generator-based for loop: P2881. He presented it in Varna (I wasn’t there), but Evolution wasn’t really keen on the idea. That proposal suggested to allow an object with a call operator to be used as a generator, by rewriting the body into a callable that is passed to that object — rewriting break and continue into different return values from that callable.
For instance, a generator might look like this:
struct generator123 {
auto operator()(auto&& sink) const -> std::control_flow {
std::control_flow flow;
flow = sink(1);
if (!flow) return flow;
flow = sink(2);
if (!flow) return flow;
return sink(3);
}
};
Which would allow the user code
for (int x : generator123())
{
if (x == 0)
continue;
if (x == 2)
break;
std::printf("%d\n", x);
}
to be rewritten into
auto __body = [&](int&& __element) -> std::control_flow {
int x = __element;
if (x == 0)
return std::continue_;
if (x == 2)
return std::break_;
std::printf("%d\n", x);
return std::continue_;
};
(void)generator123()(__body);
Notably, this is similar to the D language’s
opApplyhook, which you can see here.
This isn’t actually too dissimilar to the kinds of rewriting I walked through in the token sequence approach — but it has severe limitations, particularly in handling other control flow out of the loop body.
operator for
In order to handle return properly, not to mention co_await, co_yield, and co_return, we cannot rewrite loop bodies into callables, because we cannot introduce other function scopes. We can only rewrite loop bodies into other loop bodies. That’s what the token sequence solution does. So… why don’t we just do exactly the same thing as a proper language feature?
That is, instead of opting into internal iteration for join_view like this:
template <class V>
struct loop_traits<std::ranges::join_view<V>> {
static consteval auto loop(token_sequence self, direction dir)
-> token_sequence
{
auto inner = unique_id("inner");
auto elem = unique_id("elem");
return ^^{
iter::for_each_dir!($dir, auto&& $inner : $self.base(), {
iter::for_each_dir!($dir, auto&& $elem : $inner, {
co_yield $elem;
});
});
};
}
};
How about we opt-in like this instead:
template <input_range V>
requires /* ... */
class join_view : public view_interface<join_view<V>> {
V base_ = V();
public:
operator for() {
for (auto&& inner : base_) {
for (auto&& e : inner) {
co_yield e;
}
}
}
};
That is, writing the exact same code, with the very same co_yield statement, just without any token sequence stuff or interpolation in the way. Well, it’s not quite exactly the same, since there is only one direction in the above (forward, always), I’ll get to that in a bit. But other than that, this is still a co_yield that’s not in a C++20 coroutine.
How does this work? Well, basically the same way as the token sequence approach: the body of the user’s for loop is parsed and the binding is substituted into any co_yield statements. Except this works much better because it’s a real compiler doing it, that really knows how to parse code. And because we’re rewriting the user’s loop into other loops, there is no issue with proper handling of other control flow like return and coroutine support stuff.
Tristan threw together a bunch of flux adapters very quickly using this approach, since it turns out that internal iteration is much, much, much easier to implement than anything else, so you can see how it optimizes very well too.
Handling directionality, though, is a little tricky. Because the only hook for this is a range-based for loop, and our loop doesn’t have a place to mark direction, and I don’t think adding one like for<D>(...) is a good idea… the only place to control direction is via the type. This part of the solution ends up being much more tedious than the token sequence approach since you have to make a separate overload entirely. For join, that looks like this:
friend operator for(backward_t<join_view> b) {
for (auto&& inner : ranges::backward(b.range.base_)) {
for (auto&& e : ranges::backward(inner)) {
co_yield e;
}
}
}
Where backward is just a simple wrapper around an lvalue reference, that purely exists to do this sort of thing. For many range adapters, they don’t care which direction they’re going in, and the earlier hook I showed just passed $dir down unchanged (or, for reverse, flipped it). Instead, what I have so far is just duplicating code. filter, for instance, is:
operator for() {
for (auto&& e : base_) {
if (std::invoke(*pred_, e)) {
co_yield e;
}
}
}
friend operator for(backward_t<filter_view> b) {
for (auto&& e : ranges::backward(b.range.base_)) {
if (std::invoke(*b.range.pred_, e)) {
co_yield e;
}
}
}
I’m sure there’s something better here. Suggestions very much welcome.
But here is that same range adapter stacking example, comparing what a regular for loop looks like with this feature disabled (i.e. C++ as it stands today) and enabled. It’s easy to see the difference.
Conclusion
A lot of people have written about internal iteration in some form or other over the years. I was trying to explore what’s possible with token sequence injection by trying to get something resembling a usable internal iteration library. It was a pretty crazy approach, but syntactically too messy, and we only had limited functionality with token sequences so couldn’t really do much.
But now, our token sequence model has matured, and we both have a lot more functionality in them, and also have macros. Which enables both a usage syntax that actually at least resembles a real loop:
for_each!(int i : make_rng(), {
std::cout << "* got " << i << '\n';
if (i > 10) {
break;
}
});
And allowed me to implement a pretty involved transformation — rewriting a fake co_yield statement into an arbitrary loop body, and looking for a top-level break statement (accounting for enclosing loops!) and rewriting it into a goto. That’s a very, very complicated solution, but it’s actually, I think, within the realm of viability. At least for the more adventurous.
But everything about that process could be done as a first-class language facility, which I went ahead and implemented too, with the same approach of using co_yield, because I liked how it looked.
Now, whether operator for is something that will be considered as a viable language feature or not (and hopefully with a better solution for directionality), I think it’s pretty clear that having a powerful enough token injection facility that allows for this sort of experimentation will really open the door for trying out new ideas and iterating on them. Who knows what people will come up with next.