How to transpile labelled break/continue statements to a high-level language which lacks them?

Question

Suppose I am writing a source-to-source compiler (also called a transpiler) from one high-level imperative language to another, where the source language allows labelled statements to be targeted by break and continue, while the target language doesn't. For example, from Javascript to Python.

Manual translation is possible by inserting a flag variable, but there may be many other places besides the loop conditions where this flag will need to be checked, so it is not as simple as just including the flag in the loop condition. For example:

// Javascript code
outer:
while(cond1) {
    foo();
    while(cond2) {
        bar();
        if(cond3) {
            break outer;
        }
        baz();
    }
    qux();
}

# Translated Python code
flag = True
while flag and cond1:
    foo()
    while flag and cond2:
        bar()
        if cond3:
            flag = False
        if flag:
            baz()
    if flag:
        qux()

How can a program transformation like the above be done automatically ─ either by inserting a flag variable or otherwise? Answers which make use of single-level break/continue in the target language are fine, but answers which can eliminate break/continue entirely are even better.

Ideally I would like to preserve the original code structure as much as possible, so e.g. replacing the whole outer loop with a loop-and-switch state machine is not a preferred solution.

---

This question is distinct from What are the different options for breaking out of an inner loop? as that question is about alternatives to labelled break and continue when designing a language, whereas this question is about how to transpile between existing languages.

Answer 1

Here's a method using unlabelled break/continue. I'll use slightly different JS code:

outer:
while (cond) {
    foo();
    inner:
    while (cond) {
        bar();
        while (cond) {
            if (cond) {
                break outer;
            } else if (cond) {
                continue inner;
            }
        }
        if (cond) break;
    }
    baz();
}

The idea is, rather than using just a boolean flag, to include enough information to fully describe what you're doing with which loop.

1. Construct a map labelDepths from labels to their loops’ nesting depth. In this example, if the translator is written in JS, our map might be the object {"outer": 0, "inner": 1}.
2. Within each function declaration in the output, write two local variable declarations (with unique names), e.g. depth=0 and action=None. These will control, respectively, break/continue propagation and which action to take at the end of propagation.
3. For each labelled break/continue statement in the input, replace the statement in the output with depth=_D_; action=_A_; break, where _D_ is the value of labelDepths[label] and _A_ is either "break" or "continue". For example, break inner; would become depth=1;action="continue";break. Write unlabelled break/continue statements to the output normally.
4. For each loop statement with depth greater than 0, append the following as the next sibling of the loop statement, replacing _D_ with (the depth of the loop) - 1:

if action != None:
    if depth < _D_:
        break
    if action == "continue":
        action = None
        continue
    action = None
    break

Our JS example then ends up as the following Python code:

action = None
depth = 0

# outer:
while cond: # depth = 0
    foo()
    # inner:
    while cond: # depth = 1
        bar()
        while cond: # depth = 2
            if cond:
                # break outer
                depth=0;action="break";break
            elif cond:
                # continue inner
                depth=1;action="continue";break
        if action != None:
            if depth < 1:
                break
            if action == "continue":
                action = None
                continue
            action = None
            break
        if cond:
            break
    if action != None:
        if depth < 0:
            break
        if action == "continue":
            action = None
            continue
        action = None
        break
    baz()

There are a few ways we could make the output more efficient, such as using integers for the action constants or only including propagation code after loops that transitively contain labelled break/continue statements, but hopefully this gives you the basic idea.

Answer 2

One possible transpilation, if the language supports exceptions, is to rely on those, producing:

class BreakOuter(BaseException):pass
try: 
   while cond1:
      foo()
      while cond2:
         bar()
         if cond3:
             raise BreakOuter()
         baz()
except BreakOuter:
    pass

This, while a bit verbose, has the advantage that code only needs to get added in one place (the outer loop at the end of the break), making transpilation only require replacing that while loop with a verbose but constant bit of boilerplate and no analysis of the code inside the loop.

For a multi-level continue, you swap the order of the try and the outer while loop.

while cond1:
   try: 
      ...
   except ContinueOuter:
     pass

If the base code has multiple nested breaks, then they can use different exception classes for each label.

Answer 3

A simple solution would be to extract the (outer) loop into a function and return early. The function could take all variables that the loops needs as parameters. If it needs to modify any of the variables it can take pointers or references to them, or, if your target language does not support those, return the modified value and assign that to the original variable.

Your example would result in the following code:

mutated_variable = ...

def outer(mutated_var):
    while cond1:
        foo()
        while cond2:
            bar()
            # mutated_var is passed as a parameter, 
            # mutated and returned
            mutated_var += 1 
            if cond3:
                return mutated_var
            baz()
        qux()
    return mutated_var

mutated_variable = outer(mutated_variable)

Only if your target language does not support mutating references or multiple return values this approach won't work when multiple variables are mutated in the loop. But then you can still group them in a struct or similar.

Answer 4

If your target language lacks labelled breaks but has goto (for example, if the target language is C), you could transpile loops of this form:

outer: while cond {
  ...
}

to loops of this form:

while (cond) {
  ...
  continue_outer:
}
break_outer:

Then, continue outer and break outer become goto continue_outer and goto break_outer respectively. Depending on your target language, you may have to be careful not to generate two labels of the same name in the same file.