dart2js: CPS translation of switches with continue to their labels.

pkg/compiler/lib/src/cps_ir/cps_ir_builder_task.dart

 // Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 library dart2js.ir_builder_task;
 
 import '../closure.dart' as closure;
 import '../common.dart';
 import '../common/names.dart' show
     Names,
@@ skipping 1155 matching lines @@
       }
     } else {
       irBuilder.buildReturn(
           value: build(node.expression),
           sourceInformation: source);
     }
   }
 
   visitSwitchStatement(ast.SwitchStatement node) {
     assert(irBuilder.isOpen);
-    // We do not handle switch statements with continue to labeled cases.
-    for (ast.SwitchCase switchCase in node.cases) {
+    // Preprocess: compute a list of cases that are the target of continue.
+    // These are the so-called 'recursive' cases.
+    List<JumpTarget> continueTargets = <JumpTarget>[];
+    List<ast.SwitchCase> switchCases = node.cases.nodes.toList();
+    for (ast.SwitchCase switchCase in switchCases) {
       for (ast.Node labelOrCase in switchCase.labelsAndCases) {
         if (labelOrCase is ast.Label) {
           LabelDefinition definition = elements.getLabelDefinition(labelOrCase);
           if (definition != null && definition.isContinueTarget) {
-            return giveup(node, "continue to a labeled switch case");
+            continueTargets.add(definition.target);
           }
         }
       }
     }
 
-    // Each switch case contains a list of interleaved labels and expressions
-    // and a non-empty body.  We can ignore the labels because they are not
-    // jump targets.
+    // If any cases are continue targets, use an anonymous local value to
+    // implement a state machine.  The initial value is -1.
+    ir.Primitive initial;
+    int stateIndex;
+    if (continueTargets.isNotEmpty) {
+      initial = irBuilder.buildIntegerConstant(-1);
+      stateIndex = irBuilder.environment.length;
+      irBuilder.environment.extend(null, initial);
+    }
+
+    // Use a simple switch for the non-recursive cases.  A break will go to the
+    // join-point after the switch.  A continue to a labeled case will assign
+    // to the state variable and go to the join-point.
+    ir.Primitive value = visit(node.expression);
+    JumpCollector join = new ForwardJumpCollector(irBuilder.environment,
+        target: elements.getTargetDefinition(node));
+    irBuilder.state.breakCollectors.add(join);
+    for (int i = 0; i < continueTargets.length; ++i) {
+      // The state value is i, the case's position in the list of recursive
+      // cases.
+      irBuilder.state.continueCollectors.add(new GotoJumpCollector(
+          continueTargets[i], stateIndex, i, join));
+    }
+
+    // For each non-default case use a pair of functions, one to translate the
+    // condition and one to translate the body.  For the default case use a
+    // function to translate the body.  Use continueTargetIterator as a pointer
+    // to the next recursive case.
+    Iterator<JumpTarget> continueTargetIterator = continueTargets.iterator;
+    continueTargetIterator.moveNext();
     List<SwitchCaseInfo> cases = <SwitchCaseInfo>[];
-    SwitchCaseInfo defaultCase;
-    for (ast.SwitchCase switchCase in node.cases) {
-      SwitchCaseInfo caseInfo =
-          new SwitchCaseInfo(subbuildSequence(switchCase.statements));
+    SubbuildFunction buildDefaultBody;
+    for (ast.SwitchCase switchCase in switchCases) {
+      JumpTarget nextContinueTarget = continueTargetIterator.current;
       if (switchCase.isDefaultCase) {
-        defaultCase = caseInfo;
+        if (nextContinueTarget != null &&
+            switchCase == nextContinueTarget.statement) {
+          // In this simple switch, recursive cases are as if they immediately
+          // continued to themselves.

[asgerf, 2016/01/19 22:45:24]

I don't understand what's going one here, and the comment is not helping.

It seems to me that code:

case 1: continue LABEL;
LABEL:
default: BODY

gets translated to:

case 1: continue LABEL;
LABEL:
default: continue LABEL; // discard BODY

It would help a lot with some pseudo-code as an example of what case we are
looking at.

[Kevin Millikin (Google), 2016/01/25 12:46:37]

Sorry.  I originally had such an example but I didn't think it helped much. 
There are too many different possibilities with continue in branches, loops,
etc. that it seemed better just to describe the translation compositionally.

I've tried to add an example.

You're basically right, except that there is no LABEL in the translation:

var state = -1;
switch (...) {
  ...
  case 1: state = N; break;
  default: state = N; break;  // discard (?) BODY
}
while (state != -1) {
  switch (state) {
    ...
    case N: BODY
  }
}

Maybe "continue to itself" is too cute, but that's how I think of it.

+          buildDefaultBody = nested(() {
+            irBuilder.buildContinue(nextContinueTarget);
+          });
+          continueTargetIterator.moveNext();
+        } else {
+          // Non-recursive cases consist of the translation of the body.
+          // For the default case, there is implicitly a break if control
+          // flow reaches the end.
+          buildDefaultBody = nested(() {
+            irBuilder.buildSequence(switchCase.statements, visit);
+            if (irBuilder.isOpen) irBuilder.jumpTo(join);
+          });
+        }
+        continue;
+      }
+
+      ir.Primitive buildCondition(IrBuilder builder) {
+        // There can be multiple cases sharing the same body, because empty
+        // cases are allowed to fall through to the next one.  Each case is
+        // a comparison, build a short-circuited disjunction of all of them.
+        return withBuilder(builder, () {
+          ir.Primitive condition;
+          for (ast.Node labelOrCase in switchCase.labelsAndCases) {
+            if (labelOrCase is ast.CaseMatch) {
+              ir.Primitive buildComparison() {
+                ir.Primitive constant =
+                    translateConstant(labelOrCase.expression);
+                return irBuilder.buildIdentical(value, constant);
+              }
+
+              if (condition == null) {
+                condition = buildComparison();
+              } else {
+                condition = irBuilder.buildLogicalOperator(condition,
+                    nested(buildComparison), isLazyOr: true);
+              }
+            }
+          }
+          return condition;
+        });
+      }
+
+      SubbuildFunction buildBody;
+      if (nextContinueTarget != null &&
+          switchCase == nextContinueTarget.statement) {
+        // Recursive cases are as if they immediately continued to themselves.

[asgerf, 2016/01/19 22:45:24]

Same as above, I just can't tell what the branch condition means.

+        buildBody = nested(() {
+          irBuilder.buildContinue(nextContinueTarget);
+        });
+        continueTargetIterator.moveNext();
       } else {
-        cases.add(caseInfo);
-        for (ast.Node labelOrCase in switchCase.labelsAndCases) {
-          if (labelOrCase is ast.CaseMatch) {
-            ir.Primitive constant = translateConstant(labelOrCase.expression);
-            caseInfo.addConstant(constant);
+        // Non-recursive cases consist of the translation of the body.  It is a
+        // runtime error if control-flow reaches the end of the body of any but
+        // the last case.
+        buildBody = (IrBuilder builder) {
+          withBuilder(builder, () {
+            irBuilder.buildSequence(switchCase.statements, visit);
+            if (irBuilder.isOpen) {
+              if (switchCase == switchCases.last) {
+                irBuilder.jumpTo(join);
+              } else {
+                Element error = helpers.fallThroughError;
+                ir.Primitive exception = irBuilder.buildInvokeStatic(
+                    error,
+                    new Selector.fromElement(error),
+                    <ir.Primitive>[],
+                    sourceInformationBuilder.buildGeneric(node));
+                irBuilder.buildThrow(exception);
+              }
+            }
+          });
+          return null;
+        };
+      }
+
+      cases.add(new SwitchCaseInfo(buildCondition, buildBody));
+    }
+
+    irBuilder.buildSimpleSwitch(join, cases, buildDefaultBody);
+    irBuilder.state.breakCollectors.removeLast();
+    irBuilder.state.continueCollectors.length -= continueTargets.length;
+    if (continueTargets.isEmpty) return;
+
+    // If there were recursive cases build a while loop whose body is a
+    // switch containing (only) the recursive cases.  The condition is
+    // 'state != initialValue' so the loop is not taken when the state variable
+    // has not been assigned.
+    //
+    // 'loop' is the join-point of the exits from the inner switch which will
+    // perform another iteration of the loop.  'exit' is the join-point of the
+    // breaks from the switch, outside the loop.
+    JumpCollector loop = new ForwardJumpCollector(irBuilder.environment);
+    JumpCollector exit = new ForwardJumpCollector(irBuilder.environment,
+        target: elements.getTargetDefinition(node));
+    irBuilder.state.breakCollectors.add(exit);
+    for (int i = 0; i < continueTargets.length; ++i) {
+      irBuilder.state.continueCollectors.add(new GotoJumpCollector(
+          continueTargets[i], stateIndex, i, loop));
+    }
+    cases.clear();
+    for (int i = 0; i < continueTargets.length; ++i) {
+      // The conditions compare to the recursive case index.
+      ir.Primitive buildCondition(IrBuilder builder) {
+        ir.Primitive constant = builder.buildIntegerConstant(i);
+        return builder.buildIdentical(
+            builder.environment.index2value[stateIndex], constant);
+      }
+
+      ir.Primitive buildBody(IrBuilder builder) {
+        withBuilder(builder, () {
+          ast.SwitchCase switchCase = continueTargets[i].statement;
+          irBuilder.buildSequence(switchCase.statements, visit);
+          if (irBuilder.isOpen) {
+            if (switchCase == switchCases.last) {
+              irBuilder.jumpTo(exit);
+            } else {
+              Element error = helpers.fallThroughError;
+              ir.Primitive exception = irBuilder.buildInvokeStatic(
+                  error,
+                  new Selector.fromElement(error),
+                  <ir.Primitive>[],
+                  sourceInformationBuilder.buildGeneric(node));
+              irBuilder.buildThrow(exception);
+            }
           }
-        }
-      }
-    }
-    ir.Primitive value = visit(node.expression);
-    JumpTarget target = elements.getTargetDefinition(node);
-    Element error = helpers.fallThroughError;
-    irBuilder.buildSimpleSwitch(target, value, cases, defaultCase, error,
-        sourceInformationBuilder.buildGeneric(node));
+        });
+        return null;
+      }
+
+      cases.add(new SwitchCaseInfo(buildCondition, buildBody));
+    }
+
+    // A loop with a simple switch in the body.
+    IrBuilder whileBuilder = irBuilder.makeDelimitedBuilder();
+    whileBuilder.buildWhile(
+        buildCondition: (IrBuilder builder) {
+          ir.Primitive condition = builder.buildIdentical(
+              builder.environment.index2value[stateIndex], initial);
+          return builder.buildNegation(condition);
+        },
+        buildBody: (IrBuilder builder) {
+          builder.buildSimpleSwitch(loop, cases, null);
+        });
+    // Jump to the exit continuation.  This jump is the body of the loop exit
+    // continuation, so the loop exit continuation can be eta-reduced.  The
+    // jump is here for simplicity because `buildWhile` does not expose the
+    // loop's exit continuation directly and has already emitted all jumps
+    // to it anyway.
+    whileBuilder.jumpTo(exit);
+    irBuilder.add(new ir.LetCont(exit.continuation, whileBuilder.root));
+    irBuilder.environment = exit.environment;
+    irBuilder.environment.discard(1);  // Discard the state variable.
+    irBuilder.state.breakCollectors.removeLast();
+    irBuilder.state.continueCollectors.length -= continueTargets.length;
   }
 
   visitTryStatement(ast.TryStatement node) {
     List<CatchClauseInfo> catchClauseInfos = <CatchClauseInfo>[];
     for (ast.CatchBlock catchClause in node.catchBlocks.nodes) {
       LocalVariableElement exceptionVariable;
       if (catchClause.exception != null) {
         exceptionVariable = elements[catchClause.exception];
       }
       LocalVariableElement stackTraceVariable;
@@ skipping 2326 matching lines @@
   }
 
   Element get closureConverter {
     return _backend.helpers.closureConverter;
   }
 
   void addNativeMethod(FunctionElement function) {
     _backend.emitter.nativeEmitter.nativeMethods.add(function);
   }
 }