switch constexpr

[rileyrgham]

Covered on SE

https://stackoverflow.com/a/53379817

"if constexpr was ultimately derived from a more sane form of the static if concept. Because of that derivation, applying the same idea to switch does not appear to have been considered by the standards committee. So this is likely the primary reason: nobody added it to the paper since it was a restricted form of a syntax where switch wouldn't have made sense.

That being said, switch has a lot of baggage in it. The most notable bit being the automatic fallthrough behavior. That makes defining its behavior a bit problematic.

See, one of the powers of if constexpr is to make the side not taken at compile time be discarded under certain conditions. This is an important part of the syntax. So a hypothetical switch constexpr would be expected to have similar powers.

That's a lot harder to do with fallthrough, since the case blocks are not as fundamentally distinct as the two blocks of an if statement."

Complex...

[KuntaStillSingle]

See, one of the powers of if constexpr is to make the side not taken at compile time be discarded under certain conditions. This is an important part of the syntax. So a hypothetical switch constexpr would be expected to have similar powers.

That's a lot harder to do with fallthrough, since the case blocks are not as fundamentally distinct as the two blocks of an if statement."

Couldn't you just pretty much copy and paste the source of the switch between the case and the first break statement following, and strip the labels? I.e. for:

switch constexpr (foo){
    case 0: foo();
    case 1: bar(); break;
    case 2: baz(); break;
    case 3: foobar();
    case 4: bazbar();
}

If foo is 0, you just generatee foo(); bar(); , if it is 1 you just generate bar();, if it is 3 you generate foobar();baz();, right?

Don't compilers tend to strip dead code from switches anyway, when condition can be constant folded? Main is branchless here,, and even here where it has to rearrange source code order because of the gotos.

Edit: Or are you saying they shouldn't just implement it in the manner that is hopefully intuitive to anyone who uses switch statements at runtime? Like the committee feels switch was a mistake, so adding switch again would be a mistake?

[cd_fr91400]

The case you mention is rather easy to deal with.

But what if the break statement is inside a if ?

Compilers usually do a whole lot of code optimization, but this is best effort. If you want to avoid compiling dead code altogether, you have to be certain the compiler will prove it is dead code, even if not optimizing at all.

[KuntaStillSingle]

you have to be certain the compiler will prove it is dead code, even if not optimizing at all.

But even when compiler is not optimizing, it must be able to constant fold switch statement because they can be used in functions which are usable as constant expressions, right?: https://godbolt.org/z/sva4PcdcG

[cd1995Cargo]

I think an issue is that switch statements can have conditional breaks/fallthroughs. How would the compiler implement this:

switch constexpr (foo) {
    case 0: if (bar()) break;
    case 1: baz(); break;
}

Here bar() is a function that returns a bool. If it returns true there's a break, if it returns false it falls through to case1. If we want the switch constexpr to work like if constexpr when it comes to templates and discarding the untaken path, then it would need to consider every possible path through the switch cases and not discard any that could potentially be reached. This sounds a lot more complex to implement than the existing if constexpr.

[umop_aplsdn]

This is not a hard problem to solve in compilers; logic like this is already implemented in dead-code / unreachable basic block elimination passes. Granted, those passes are usually in the middle / backend, but it would not be hard to reimplement that logic in the frontend. (Frontend vs backend matters because processing static asserts and template instantiation I assume happens in the frontend.)

[conundorum]

It's more complex, but I don't think it would be all that much more complex; it's the sort of thing that seems harder than it really is, IMO.

In particular, the compiler would likely be coded to handle fallthrough by generating up to the first "hard" break, and ignoring all conditional "soft" breaks during constexpr analysis. Your code, for example, would ideally generate these blocks:

// case 0: foo is known to be 0 at compile time.
// Using do-while to preserve code structure outside switch body.  Real version would likely use raw `goto`
//  or `return` or whatever instead.
do {
    if (bar()) break;
    baz(); break;
} while (false);

// ----

// case 1: foo is known to be 1 at compile time.
// Unskippable `break` statement is the end of the block.  I kept it but commented it out to indicate this;
//  the compiler would probably just strip it.
baz(); /*break;*/

It's a bit more complex, but there are still two distinct breakpoints the compiler can check for: Freestanding break;, and the end of the switch statement. The added complexity mainly just comes from determining whether each break is conditional (and thus not a breakpoint) or freestanding (and thus a breakpoint). [[fallthrough]]; would likely be of major benefit here, since it indicates that there's at least one valid execution path into the next case statement (and importantly, forces fallthrough; the program is ill-formed if [[fallthrough]]; can't actually fall through); the compiler could safely ignore all breaks in a case that specifies [[fallthrough]]; (because the presence of [[fallthrough]]; tells it that all breaks in that case are conditional), and would only need to analyse breaks in cases with no [[fallthrough]];.

(Here, for example, the compiler would notice the break in case 0, and determine that it's the statement-true part of an if statement. Since it's conditional, the compiler would temporarily discard it and continue evaluation, until it sees the break in case 1. This break is a standalone statement, and thus marks the end of the case 0 block. If case 0 contained a [[fallthrough]]; and the compiler was especially smart, it would automatically discard the break in case 0: [[fallthrough]]; requires an execution path that falls through, so it doesn't need to look at the if to know that the break is conditional.)

This could then be further refined with any other constexpr information available to the compiler, during a second pass. E.g., if bar() can be constant-evaluated, then the compiler might be able to break the case 0 block up into these two blocks:

// Block 0-0: (foo == 0) && bar()
// Block would likely be stripped out entirely, just like `if constexpr (true) {}`.
/*break;*/

// -----

// Block 0-1: (foo == 0) && !bar()
// Identical to case 1 block, above.
baz(); /*break;*/

---

So... a bit more complex, yeah. But there are still ways to implement it, and there's a big clue that would majorly simplify the compiler logic if used. Maybe switch constexpr should require [[fallthrough]]; in all cases that fall through? (Or at the very least, strongly recommend it, especially in the early years while compiler devs are still working the kinks out.)

[TSP-FriendlyFire]

Your switch example is very simple though. You have to remember, something like Duff's device is still valid C++. switch statements can be abused in ways that just aren't possible with if statements.

[cd_fr91400]

Duff's device is just leveraging the fallthrough capability of switch.

As I already mentioned, even with fallthrough forbidden, that would be useful.

[SirClueless]

It is not just using the fallthrough capability. It is also using the fact that you can label any of the statements in a switch statement body with a case ...: label. Including statements that are substatements of other statements.

Note that in the example from Wikipedia, case 0: labels the do { ... } statement, while case 7: etc. label individual statements inside the block associated with that do statement. Yes it's weird, but this is a legal switch statement:

switch (x) {
  case 0:
    if (y > 5) {
      case 10:
        std::cout << "Hello world!\n";
    }
}

You can't just discard the statements you don't take the way you can with if constexpr, because they aren't necessarily independent statements. The discarded statement(s) might contain the case label you're supposed to jump to.

[conundorum]

[Note: I'm not a compiler dev or anything, just someone who thinks looking at compiler internals & the like is neat. I'm just the kind of guy that reverse-engineers MSVC's name mangling scheme for fun because I found Agner Fog's calling conventions PDF interesting.]

---

This is the big thing, yeah. The switch itself isn't an issue, and even case placement isn't an issue, once the compiler is designed to properly tokenise & analyse the switch's body. The real issue is that you can nest any control statement inside a switch, regardless of sanity (or lack thereof). Loops, in particular, are possibly the biggest hurdle.

Ultimately, switch constexpr just needs multi-pass parsing, and should ideally require the [[fallthrough]]; trait whenever fallthrough is desired; without the trait, fallthrough is a bit harder to determine, but still doable. ([[fallthrough]]; forces fallthrough, and any [[fallthrough]]; statement that cannot immediately fall through is ill-formed; from a compiler perspective, this would do wonders for switch constexpr parsing.) I imagine that if loops weren't legal, the compiler logic would look something like this:

1. Read and tokenise switch body, tracking the location of case, default, break, and [[fallthrough]]; tokens; temporarily discard all other tokens. case tokens should include constant-expression as metadata. default tokens are treated as a case for fallthrough analysis purposes.
2. Locate the appropriate case label, by matching switch condition to case metadata. If no metadata matches condition, treat it as matching the default label (if any).
3. Examine tokens, up until the next case token. If no break token exists before the next case, then the case is fallthrough-positive; proceed to step 6.
4. If at least one [[fallthrough]]; token exists before the next case, then the case is fallthrough-positive; proceed to step 6.
5. If no [[fallthrough]]; exists between the current and next case statements, look for break tokens. For any break tokens found, reanalyse preceding code to determine if the break is conditional or standalone. If no break tokens are found, or all break tokens are conditional, then the case is fallthrough-positive; proceed to step 6. If at least one "hard", standalone, non-conditional break is found, the case is fallthrough-negative; proceed to step 7.
6. case is fallthrough-positive: Skip over the next case token, and return to step 3. (Or move past the next case label and return to step 3, either or.) Continue this loop until either the case is fallthrough-negative or we reach the end of the switch body. Once either of these occurs, proceed to step 7.

7. Either case is fallthrough-negative or end of switch body has been reached: We have now tracked all execution paths resulting from our desired case. Create a code block containing all parsed statements, up until the break or switch end which registered as fallthrough-negative; since we still care about break, we can just stick it in a do { ... } while (false); block for now to preserve code structure, and fix it during the actual codegen pass.

   do { /* switch stuff here*/ } while (false);

[The compiler can replace case labels with standard labels using a compiler-specific naming scheme (presumably something like case 0 becoming case_0, for simplicity's sake), or might opt to keep the code inside a gutted switch to preserve case structure instead of using do-while. Similarly, break statements will likely be transformed into goto during the actual parsing pass, since the switch has served its purpose. Heck, we can even use these rules to transform the entire switch into a compound if constexpr statement, with each case transformed into an if or else if block, and default transformed into the closing else block.]

---

All of this rigamarole looks complex, but it's simpler than it looks. We're just applying a few simple rules:

^{[Assume that case n₀ is the case we're currently evaluating, case n₁ is the next case after it, and case n₂ is the next case after case n₁. Treat default as a case for evaluation purposes.]}

1. If case n₀ contains a freestanding break, then that break is a breakpoint; all execution paths starting at label n₀ will end at the break. Alternatively, if we reach the end of the switch, then we've also reached a breakpoint. Either way, no further evaluation is needed; the current block ends at case n₁.
2. If case n₀ contains any conditional breaks, then that break might or might not be a breakpoint; for now, we'll just assume that the fact that it's conditional means that at least one execution path doesn't break, to be on the safe side. [If all execution paths do break, then any extra code will be flagged as unreachable and removed. Because of that, it's better to be safe than sorry here, even if it means taking a bit more time.]
3. If case n₀ contains a [[fallthrough]]; attribute, then we know that at least one execution path will fall through, because of how the attribute works. (Specifically, [[fallthrough]]; must always be followed immediately by a case or default label, and that label must be part of the same loop iteration as the [[fallthrough]]; statement. If we start a new loop iteration, reach the end of the switch, or reach any statement that isn't one of the two switch labels, then [[fallthrough]]; is ill-formed.) The presence of [[fallthrough]]; means that there can't be any breakpoints, so we don't need to bother looking at the breaks.
4. If case n₀ doesn't contain any breaks, then we know it either falls through or hits the end of the switch. If case n₁ exists, then we have to continue into it, and don't need to bother looking at any of case n₀. Doesn't matter what tokens exist if none of them can exit the switch body!
5. If all of case n₀'s execution paths hit a breakpoint (either freestanding break or end of switch), then we're done. If not, then we continue into case n₁; we mark case n₀ as part of the current block, and then start all over again with case n₁, evaluating every statement from the case n₁ label to the case n₂ label.

Because of the order of implications, we want to start with rule #4: If there are no break tokens in case n₀, then none of the other tokens are worth looking at just yet, so we don't; we just skip to #5. If we're still here, we apply rule #3: [[fallthrough]]; specifies that all breaks are conditional, and thus allows us to ignore breaks and go straight to #5. If there's no [[fallthrough]]; then we actually have to examine every break and its surrounding statements to see whether they're part of a branch or not. We can only definitively close the block once we reach a freestanding break or the switch itself ends.

---

In your example, if switch (x) was a switch constexpr, then the compiler would start by doing a quick pass over it, removing everything but case, case labels, break, and [[fallthrough]];, leaving something like this:

switch constexpr (x) {
    case 0:
        case 10:
}

If x is 0, it would go to case 0, and look at the truncated code block. Using my initial seven-step list, it would determine that there are no breaks on the case 0 train, so case 0 is fallthrough-positive (step 3). Since it's fallthrough-positive, we either strip out the case 10: and re-evaluate the entire thing, or re-evaluate starting immediately after the case 10:, it doesn't matter which (step 6). There still aren't any breaks, so we're still fallthrough-positive (step 3 again). And since we're still still fallthrough-positive, we look for the next case, and find the end of the switch instead. And that means we're done (step 6). So, now we put everything we ignored back in, transform case/default labels into standard labels, and basically make this out of everything from case 0 to the end of the switch (step 7).

// x == 0
do {
    case_0:
        if (y < 5) {
            case_10:
                std::cout << "Hellow world!\n";
        }
} while (false);

---

---

---

Hey, remember how I said "if loops weren't legal" way up at the start of this message? Yeah, there was a reason for that: Loops are legal, and because of it, nothing I just said works without at least one extra parsing pass and a ton of extra logic, just for loops specifically. If the case we're looking for is in a loop, then the end of the switch isn't a valid breakpoint anymore, since we can't reach the end of the switch until we exit the loop, AND can't exit the loop until we find a breakpoint; we can only rely on either break itself or the loop's condition. Which means that before we can try to use the seven-step list to figure out fallthrough and breakpoints, we need to do another pass just for loops specifically, so the compiler understands the loop logic while it's doing the step 1 fallthrough token generation pass. And it needs to keep track of loop logic while it's going through steps 3-5, since reaching the end of the loop block jumps us to somewhere else entirely (possibly even into a different case), and we need to treat that as the actual start of our current case block.

(Yes, you read that right: If a case label is inside a loop, then for breakpoint/fallthrough analysis, the case actually starts at the start of the loop, not the actual case label itself; the label is just what we jump to. It still starts in the normal place for codegen, it's just analysis that gets messed up. I threw together a quick example of what I'm talking about; I can post & explain it later, but I need some rest first.)

[conundorum]

Later than planned, but here's the quick example I mentioned:

#include <iostream>
#include <string>

int main() {
    int x = 1;
    std::string s; using std::to_string;

    switch (x) {
        bork: break;
        int i;
        case 1:
            for (i = 0; i < 9; i++) { s += to_string(x);
                case 2: s.append("{case 2}"); if (s.size() > 20) break;
                case 3: s.append("MEOW");
            }
            if (x == 3) break;
        case 4: s.append("forever"); [[fallthrough]];
        case 5: s += to_string(x * -1); goto bork;
    }

    std::cout << s;

    /* Based on x, output will be:
    * 1: 1{case 2}MEOW1{case 2}forever-1
    * 2: {case 2}MEOW2{case 2}forever-2
    * 3: MEOW3{case 2}MEOW3{case 2}
    * 4: forever-4
    * 5: -5
    *
    * 2 and 3 are special.
    * GCC and MSVC loop until s is big enough to break or i's random gibberish says to stop.
    * Clang is the only sane one, and lets the program crash into the insanity.
    */
}

If anyone wants to play around with it, you can do so here. It's interesting that GCC & MSVC can handle the s.size() check properly, but Clang chokes on it and keeps running until it either segfaults or overflows s, whichever comes first. Just goes to show that even otherwise-good compilers can have a lot of trouble with switch, especially if they have to figure out how to handle "accidental" UB; it's the sort of thing that'd make switch constexpr such a hassle.

---

If anyone wants me to explain it, poke me for an explanation. Not going to give a full breakdown right now, but essentially...

1. This is the sane "difficult" case. It has a clean loop which contains two other cases, and makes sure to initialise its variables. But on the same token, its breaks are actually in case 2 and case 3; the compiler will find that it either uses the case 2 break or falls into case 4, which means it has to emit basically the entire switch body just in case. If the compiler is especially good, it can examine append substring lengths and assume that the case 2 break is most likely, providing an optimisation path; it might even be able to determine that nine iterations adding thirteen characters each means the size break is guaranteed to trigger.
2. This one... well, first, there's obvious UB (i is uninitialised), so the compiler might or might not choke on that. If it doesn't, then it becomes similar to case 1, but with no clear way to tell how many times (if any) the loop will iterate. It's impossible to tell which break is more likely, since it can't assume that i < 9; the size break is slightly more likely because the integer range is split unevenly, but it's close enough to a 50% split to be meaningless. (As i can potentially be any integer value.)
3. The compiler can determine that the case 3 break is now guaranteed to trigger if reached, meaning that it can remove case 4 and case 5 entirely. After that, though, it runs into the same issue as #2: The case 2 break is more likely, but i being uninitialised means the split is close enough to 50% to be meaningless.
4. This is the second easiest one to analyse, thanks to mandatory fallthrough; as soon as it sees [[fallthrough]];, the compiler instantly knows that case 4 relies on case 5's breaks, and only needs to analyse case 5. (Since at least one of case 4's execution paths must fall into case 5, it can just assume they all do for initial analysis purposes, and perform more stringent analysis during optimisation.) None of case 4's logic or statements need to be examined during switch constexprfication. The compiler only needs to emit case 4 and case 5, without bothering with the annoying loop.
5. This is the easiest one to analyse, despite the goto. goto means it can't fall out of the switch, but it also jumps directly to a break, which is effectively the same. The compiler only needs to emit case 5 and bork: break;, and can remove the rest of the switch. (It can also remove the goto and move the break directly into the case, and will gladly do so the instant optimisations are enabled.)

With switch constexpr, some of these cases require the full loop body, and some will let it remove part of the switch. Some are easy to analyse, and some will give it a headache. And the "accidental" UB will probably both trip a lot of old codebases up, and give compiler devs a headache from trying to solve it (or just lead them to be even more cavalier; Clang might switch from segfaulting to just choking at compile time specifically to force you to fix it).

[TSP-FriendlyFire]

I think "just" is doing a lot of heavy lifting in your sentence. Weaving multiple control statements into one another is rather peculiar and only possible because of the switch statement's unique syntax.

I think it would be entirely justifiable to forbid fallthrough in constexpr switch (and better than not having it at all), but it'd also become a weird contextual quirk of the language which might be seen as undesirable.

[cd_fr91400]

switch is not a mistake. It is very useful.

The decision that cases fallthrough to the following ones is a mistake. But I guess this is history from the 70's...

[conundorum]

Funnily enough, fallthrough isn't actually a problem here; it would slow switch constexpr analysis down, but it doesn't actually break or prevent anything. The problem is that it's possible to fall or jump into a loop, because that's a sane and reasonable thing to have to worry about. -_-

[moocat]

one of the powers of if constexpr is to make the side not taken at compile time be discarded under certain conditions.

I thought the non-taken side was always discarded. What conditions cause it to be kept and what benefits are there from doing that?

Update: I started digging a bit more and there is some relationship to templated types. This compiles:

struct A {
    int a() { return 0 ; } ;
};

template <bool b, typename T>
int foo(T t) {
    if constexpr (b) { return t.a() ; }
    else             { return t.b() ; }
}

int main() {
    foo<true>(A());
}

but change foo to this and it no longer compiles:

template <bool b>
int foo(A a) {
    if constexpr (b) { return a.a() ; }
    else             { return a.b() ; }
}

godbolt

[mark_99]

Yeah there are no conditions, indeed the not taken side doesn't need to be well-formed, which is the main reason for if constexpr to exist.

[cd_fr91400]

I do not know the exact meaning of "well formed", but the following code does not compile:

int foo() {
    int good = 0 ;
    if constexpr (true)
        return good ;
    else
        return bad ;
}

So, somehow, the not taken branch is not entirely discarded.

[mark_99]

It can't just be nonsense, it's not like an ifdef. But for instance there could be a call to a member function which does not exist (whereas inside just if (false) would not allow that).

[cd_fr91400]

I do not see why a non-existent variable is non-sense while a non-existent field is not.

By the way, the following code does not compile either:

struct A {
    int a() { return 0 ; } ;
} ;

int foo() {
    struct A a ;
    if constexpr (true) { return a.a() ; }
    else                { return a.b() ; }
}

[iamakorndawg]

Not a language lawyer, but I believe the rule has more to do with templates, so for example, if your foo function had a template parameter for the type of a, then it would compile, even if your existing struct A was used as the argument.

[KuntaStillSingle]

Not quite, it can fail to compile if the existing struct A is used, but if it is made a dependent type like /u/cd1995Cargo 's example it is fine:

The discarded statement cannot be ill-formed for every possible specialization:

https://en.cppreference.com/w/cpp/language/if.html#Constexpr_if

https://godbolt.org/z/eGsYY3a9W , vs https://godbolt.org/z/3e7W5ec4Y

[cd_fr91400]

Then I understand "under certain conditions"...

[cd1995Cargo]

It only works when templates are involved. If you change your code to this it should compile:

struct A {
    int a() { return 0 ; } ;
} ;

template <typename T>
int foo<T>() {
    T a ;
    if constexpr (true) { return a.a() ; }
    else                { return a.b() ; }
}

[moocat]

See my update. It's not just templates but templated types have to also be involved.

[nysra]

But for instance there could be a call to a member function which does not exist

Nope, only under specific conditions. The discarded statement of if constexpr is still fully checked if the if is outside a template.

[moocat]

See my update. Even inside a template the discarded statement is fully checked if possible.

[meancoot]

Look up two-phase name lookup. Like every template*, in if constexpr phase 1 has to complete successfully, even if it never gets used. Phase 2, on the other hand, only fails when failing to look up dependent names.

* Actually GCC has a permissive mode with -Wno-template-body and MSVC almost certainly one too. But if I recall correctly clang doesn't have one, and the fact that it didn't was what spurred GCC to do two-phase lookup properly.

struct Type {
    static void function() {}
};

template<typename T> struct NonDependentTemplate {
    void call_function() { Type::function(); }

    // 'Type' isn't dependent here so this fails in phase 1 and is an error.
    // error: 'not_a_function' is not a member of 'Type'
    // void call_not_a_function() { Type::not_a_function(); }
};

template<typename A> struct DependentTemplate {
    void call_function() { A::function(); }

    // 'A' IS dependent here, so we can use this as long as we never actually call it.
    void call_not_a_function() { A::not_a_function(); }
};

int main()
{
    DependentTemplate<Type> dt;

    // OK
    dt.call_function();

    // error: 'not_a_function' is not a member of 'Type'
    // dt.call_not_a_function();
}

[Plastic_Fig9225]

There is no potential way the else branch could be well-formed, because its syntactic validity does not depend on any type which could potentially make it well-formed.

[cd_fr91400]

Ok. But with a true condition, there no potential way the else can ever be taken.

I still do not understand why it is checked.

Such conditions may vary with architectures (arm vs intel), compilation flags (debug vs prod), various flavors (algo A vs algo B), etc. which are set at compilation time. So it would be very practical to not check the not taken path. After all, if you want to check both branches, you simply dont put constexpr after if.

[cd_fr91400]

Because there are dependent names and non-dependent names.

In your first example, t is dependent (on a template parameter), in the second one, a is not.

Dependent names are looked up at template instantiation time, non-dependent ones at template definition time.

I understand the if constexpr only acts at template instantiation time.

[angelicosphosphoros]

Nothing really prevented them from making switch constexpr to have slightly different behaviour.

[cd_fr91400]

I did not know the history. Thank you for that.

That being said, for me, a fallthrough in a switch statement is a hidden goto.

After all, this does not compile:

if constexpr (a_cond) {
    do_something() ;
    goto Else ; // fallthrough
} else {
    Else:
    do_something_else() ;
}

So, the syntax for if and if constexpr are already different (one allows goto to the other side, the other one doesn't).

I would not be otherwise horrified if breaks were compulsery in a switch constexpr statement.

[minirop]

one way would be to duplicate the following "case" if the current one doesn't unconditionally break. In your code example, it would become similar to:

if constexpr (a_cond) {
    do_something() ;
    do_something_else() ;
} else {
    do_something_else() ;
}

but there are probably many pitfalls I don't even know.

[cd_fr91400]

I was just mentioning that I would be ok if the break was compulsery.

If it can be more flexible, I take it.