dart2dart: Support for inner functions in new IR.

sdk/lib/_internal/compiler/implementation/dart_backend/dart_codegen.dart

 // Copyright (c) 2014, 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 dart_codegen;
 
 import 'dart_tree.dart' as tree;
 import 'dart_printer.dart';
 import 'dart_tree_printer.dart' show TreePrinter;
 import '../tree/tree.dart' as frontend;
 import '../dart2jslib.dart' as dart2js;
 import '../elements/elements.dart';
 import '../dart_types.dart';
 import '../elements/modelx.dart' as modelx;
 import '../universe/universe.dart';
 import '../tree/tree.dart' as tree show Modifiers;
 import '../ir/const_expression.dart';
 
 /// Translates the dart_tree IR to Dart frontend AST.
 frontend.FunctionExpression emit(FunctionElement element,
                                  dart2js.TreeElementMapping treeElements,
                                  tree.FunctionDefinition definition) {
-  FunctionExpression fn = new ASTEmitter().emit(element, definition);
+  FunctionExpression fn = new ASTEmitter().emit(definition);
   return new TreePrinter(treeElements).makeExpression(fn);
 }
 
 /// Translates the dart_tree IR to Dart backend AST.
 /// An instance of this class should only be used once; a fresh emitter
 /// must be created for each function to be emitted.
 class ASTEmitter extends tree.Visitor<dynamic, Expression> {
   /// Variables to be hoisted at the top of the current function.
   List<VariableDeclaration> variables = <VariableDeclaration>[];
 
   /// Maps variables to their name.
   Map<tree.Variable, String> variableNames = <tree.Variable, String>{};
 
   /// Maps local constants to their name.
   Map<VariableElement, String> constantNames = <VariableElement, String>{};
 
-  /// Maps variables to their declarations.
-  Map<tree.Variable, VariableDeclaration> variableDeclarations =
-      <tree.Variable, VariableDeclaration>{};
+  /// Variables that have had their declaration created.
+  Set<tree.Variable> declaredVariables = new Set<tree.Variable>();
 
   /// Variable names that have already been used. Used to avoid name clashes.
-  Set<String> usedVariableNames = new Set<String>();
+  Set<String> usedVariableNames;
 
   /// Statements emitted by the most recent call to [visitStatement].
   List<Statement> statementBuffer = <Statement>[];
 
   /// The function currently being emitted.
   FunctionElement functionElement;
 
   /// Bookkeeping object needed to synthesize a variable declaration.
   modelx.VariableList variableList
       = new modelx.VariableList(tree.Modifiers.EMPTY);
 
   /// Input to [visitStatement]. Denotes the statement that will execute next
   /// if the statements produced by [visitStatement] complete normally.
   /// Set to null if control will fall over the end of the method.
   tree.Statement fallthrough = null;
 
   /// Labels that could not be eliminated using fallthrough.
   Set<tree.Label> usedLabels = new Set<tree.Label>();
 
   /// The first dart_tree statement that is not converted to a variable
   /// initializer.
   tree.Statement firstStatement;
 
-  FunctionExpression emit(FunctionElement element,
-                          tree.FunctionDefinition definition) {
-    functionElement = element;
+  /// Emitter for the enclosing function, or null if the current function is
+  /// not a local function.
+  ASTEmitter parent;
 
-    Parameters parameters = emitParameters(definition.parameters);
+  ASTEmitter() : usedVariableNames = new Set<String>();
+
+  ASTEmitter.inner(ASTEmitter parent)
+      : this.parent = parent,
+        usedVariableNames = parent.usedVariableNames;
+
+  FunctionExpression emit(tree.FunctionDefinition definition) {
+    functionElement = definition.element;
+
+    Parameters parameters = emitParameters(definition.element.functionSignature);
+
+    // Declare parameters.
+    for (tree.Variable param in definition.parameters) {
+      variableNames[param] = param.element.name;
+      usedVariableNames.add(param.element.name);
+      declaredVariables.add(param);
+    }
+
     firstStatement = definition.body;
     visitStatement(definition.body);
     removeTrailingReturn();
-    Statement body = new Block(statementBuffer);
 
     // Some of the variable declarations have already been added
     // if their first assignment could be pulled into the initializer.
     // Add the remaining variable declarations now.
     for (tree.Variable variable in variableNames.keys) {
-      if (variable.element is ParameterElement) continue;
-      if (variableDeclarations.containsKey(variable)) continue;
-      addDeclaration(variable);
+      if (!declaredVariables.contains(variable)) {
+        addDeclaration(variable);
+      }
     }
 
     // Add constant declarations.
     List<VariableDeclaration> constants = <VariableDeclaration>[];
     for (ConstDeclaration constDecl in definition.localConstants) {
       if (!constantNames.containsKey(constDecl.element))
         continue; // Discard unused constants declarations.
       String name = getConstantName(constDecl.element);
       Expression value = emitConstant(constDecl.expression);
       VariableDeclaration decl = new VariableDeclaration(name, value);
       decl.element = constDecl.element;
       constants.add(decl);
     }
 
     List<Statement> bodyParts = [];
     if (constants.length > 0) {
       bodyParts.add(new VariableDeclarations(constants, isConst: true));
     }
     if (variables.length > 0) {
       bodyParts.add(new VariableDeclarations(variables));
     }
-    bodyParts.add(body);
+    bodyParts.addAll(statementBuffer);
 
-    FunctionType functionType = element.type;
+    FunctionType functionType = functionElement.type;
 
     return new FunctionExpression(
         parameters,
         new Block(bodyParts),
-        name: element.name,
+        name: functionElement.name,
         returnType: emitOptionalType(functionType.returnType))
-        ..element = element;
+        ..element = functionElement;
   }
 
   void addDeclaration(tree.Variable variable, [Expression initializer]) {
-    assert(!variableDeclarations.containsKey(variable));
+    assert(!declaredVariables.contains(variable));
     String name = getVariableName(variable);
     VariableDeclaration decl = new VariableDeclaration(name, initializer);
     decl.element = variable.element;
-    variableDeclarations[variable] = decl;
+    declaredVariables.add(variable);
     variables.add(decl);
   }
 
   /// Removes a trailing "return null" from [statementBuffer].
   void removeTrailingReturn() {
     if (statementBuffer.isEmpty) return;
     if (statementBuffer.last is! Return) return;
     Return ret = statementBuffer.last;
     Expression expr = ret.expression;
     if (expr is Literal && expr.value is dart2js.NullConstant) {
       statementBuffer.removeLast();
     }
   }
 
   Parameter emitParameterFromElement(ParameterElement element, [String name]) {
     if (name == null) {
       name = element.name;
     }
     if (element.functionSignature != null) {
       FunctionSignature signature = element.functionSignature;
       TypeAnnotation returnType = emitOptionalType(signature.type.returnType);
-      Parameters innerParameters = new Parameters(
-          signature.requiredParameters.mapToList(emitParameterFromElement),
-          signature.optionalParameters.mapToList(emitParameterFromElement),
-          signature.optionalParametersAreNamed);
+      Parameters innerParameters = emitParameters(signature);
       return new Parameter.function(name, returnType, innerParameters)
                  ..element = element;
     } else {
       TypeAnnotation type = emitOptionalType(element.type);
       return new Parameter(name, type:type)
                  ..element = element;
     }
   }
 
-  Parameter emitParameter(tree.Variable param) {
-    return emitParameterFromElement(param.element, getVariableName(param));
-  }
-
-  Parameters emitParameters(List<tree.Variable> params) {
-    return new Parameters(params.map(emitParameter).toList(growable:false));
+  Parameters emitParameters(FunctionSignature signature) {
+    return new Parameters(
+        signature.requiredParameters.mapToList(emitParameterFromElement),
+        signature.optionalParameters.mapToList(emitParameterFromElement),
+        signature.optionalParametersAreNamed);
   }
 
   /// True if the two expressions are a reference to the same variable.
   bool isSameVariable(Receiver e1, Receiver e2) {
     // TODO(asgerf): Using the annotated element isn't the best way to do this
     // since elements are supposed to go away from codegen when we discard the
     // old backend.
     return e1 is Identifier &&
            e2 is Identifier &&
            e1.element is VariableElement &&
@@ skipping 51 matching lines @@
       savedBuffer.add(new Block(statementBuffer));
     }
     fallthrough = savedFallthrough;
     statementBuffer = savedBuffer;
     visitStatement(stmt.next);
   }
 
   /// Generates a name for the given variable and synthesizes an element for it,
   /// if necessary.
   String getVariableName(tree.Variable variable) {
+    // If the variable belongs to an enclosing function, ask the parent emitter
+    // for the variable name.
+    if (variable.host.element != functionElement) {
+      return parent.getVariableName(variable);
+    }
+
+    // Get the name if we already have one.
     String name = variableNames[variable];
     if (name != null) {
       return name;
     }
+
+    // Synthesize a variable name that isn't used elsewhere.
+    // The [usedVariableNames] set is shared between nested emitters,
+    // so this also prevents clash with variables in an enclosing/inner scope.
+    // The renaming phase after codegen will further prefix local variables
+    // so they cannot clash with top-level variables or fields.
     String prefix = variable.element == null ? 'v' : variable.element.name;
     int counter = 0;
     name = variable.element == null ? '$prefix$counter' : variable.element.name;
     while (!usedVariableNames.add(name)) {
       ++counter;
       name = '$prefix$counter';
     }
     variableNames[variable] = name;
 
     // Synthesize an element for the variable
     if (variable.element == null || name != variable.element.name) {
       variable.element = new modelx.VariableElementX(
           name,
           ElementKind.VARIABLE,
           functionElement,
           variableList,
           null);
     }
     return name;
   }
 
   String getConstantName(VariableElement element) {
+    assert(element.kind == ElementKind.VARIABLE);
+    if (element.enclosingElement != functionElement) {
+      return parent.getConstantName(element);
+    }
     String name = constantNames[element];
     if (name != null) {
       return name;
     }
     String prefix = element.name;
     int counter = 0;
     name = element.name;
     while (!usedVariableNames.add(name)) {
       ++counter;
       name = '$prefix$counter';
     }
     constantNames[element] = name;
     return name;
   }
 
+  bool isNullLiteral(Expression exp) => exp is Literal && exp.value.isNull;
+
   void visitAssign(tree.Assign stmt) {
+    // Try to emit a local function declaration. This is useful for functions
+    // that may occur in expression context, but could not be inlined anywhere.
+    if (stmt.variable.element is FunctionElement &&
+        stmt.definition is tree.FunctionExpression &&
+        !declaredVariables.contains(stmt.variable)) {
+      tree.FunctionExpression functionExp = stmt.definition;
+      FunctionExpression function = makeSubFunction(functionExp.definition);
+      FunctionDeclaration decl = new FunctionDeclaration(function);
+      statementBuffer.add(decl);
+      declaredVariables.add(stmt.variable);
+      visitStatement(stmt.next);
+      return;
+    }
+
     bool isFirstOccurrence = (variableNames[stmt.variable] == null);
+    bool isDeclaredHere = stmt.variable.host.element == functionElement;
     String name = getVariableName(stmt.variable);
     Expression definition = visitExpression(stmt.definition);
-    if (firstStatement == stmt && isFirstOccurrence) {
+
+    // Try to pull into initializer.
+    if (firstStatement == stmt && isFirstOccurrence && isDeclaredHere) {
+      if (isNullLiteral(definition)) definition = null;
       addDeclaration(stmt.variable, definition);
       firstStatement = stmt.next;
-    } else {
-      statementBuffer.add(new ExpressionStatement(makeAssignment(
-          visitVariable(stmt.variable),
-          definition)));
+      visitStatement(stmt.next);
+      return;
     }
+
+    // Emit a variable declaration if we are required to do so.
+    // This is to ensure that a fresh closure variable is created.
+    if (stmt.isDeclaration) {
+      assert(isFirstOccurrence);
+      assert(isDeclaredHere);
+      if (isNullLiteral(definition)) definition = null;
+      VariableDeclaration decl = new VariableDeclaration(name, definition)
+                                     ..element = stmt.variable.element;
+      declaredVariables.add(stmt.variable);
+      statementBuffer.add(new VariableDeclarations([decl]));
+      visitStatement(stmt.next);
+      return;
+    }
+
+    statementBuffer.add(new ExpressionStatement(makeAssignment(
+        visitVariable(stmt.variable),
+        definition)));
     visitStatement(stmt.next);
   }
 
   void visitReturn(tree.Return stmt) {
     Expression inner = visitExpression(stmt.value);
     statementBuffer.add(new Return(inner));
   }
 
   void visitBreak(tree.Break stmt) {
     tree.Statement fall = fallthrough;
@@ skipping 25 matching lines @@
     List<Statement> thenBuffer = statementBuffer = <Statement>[];
     visitStatement(stmt.thenStatement);
     List<Statement> elseBuffer = statementBuffer = <Statement>[];
     visitStatement(stmt.elseStatement);
     savedBuffer.add(
         new If(condition, new Block(thenBuffer), new Block(elseBuffer)));
     statementBuffer = savedBuffer;
   }
 
   void visitWhileTrue(tree.WhileTrue stmt) {
-    List<Expression> updates = stmt.updates.reversed
-                                           .map(visitExpression)
-                                           .toList(growable:false);
-
     List<Statement> savedBuffer = statementBuffer;
     tree.Statement savedFallthrough = fallthrough;
     statementBuffer = <Statement>[];
     fallthrough = stmt;
 
     visitStatement(stmt.body);
     Statement body = new Block(statementBuffer);
-    Statement statement = new For(null, null, updates, body);
+    Statement statement = new While(new Literal(new dart2js.TrueConstant()),
+                                    body);
     if (usedLabels.remove(stmt.label.name)) {
       statement = new LabeledStatement(stmt.label.name, statement);
     }
     savedBuffer.add(statement);
 
     statementBuffer = savedBuffer;
     fallthrough = savedFallthrough;
   }
 
   void visitWhileCondition(tree.WhileCondition stmt) {
     Expression condition = visitExpression(stmt.condition);
-    List<Expression> updates = stmt.updates.reversed
-                                           .map(visitExpression)
-                                           .toList(growable:false);
 
     List<Statement> savedBuffer = statementBuffer;
     tree.Statement savedFallthrough = fallthrough;
     statementBuffer = <Statement>[];
     fallthrough = stmt;
 
     visitStatement(stmt.body);
     Statement body = new Block(statementBuffer);
     Statement statement;
-    if (updates.isEmpty) {
-      // while(E) is the same as for(;E;), but the former is nicer
-      statement = new While(condition, body);
-    } else {
-      statement = new For(null, condition, updates, body);
-    }
+    statement = new While(condition, body);
     if (usedLabels.remove(stmt.label.name)) {
       statement = new LabeledStatement(stmt.label.name, statement);
     }
     savedBuffer.add(statement);
 
     statementBuffer = savedBuffer;
     fallthrough = savedFallthrough;
 
     visitStatement(stmt.next);
   }
 
   Expression visitConstant(tree.Constant exp) {
     return emitConstant(exp.expression);
   }
 
   Expression visitThis(tree.This exp) {
     return new This();
   }
 
   Expression visitReifyTypeVar(tree.ReifyTypeVar exp) {
-    return new ReifyTypeVar(exp.element.name)
-               ..element = exp.element;
+    return new ReifyTypeVar(exp.typeVariable.name)
+               ..element = exp.typeVariable;
   }
 
   Expression visitLiteralList(tree.LiteralList exp) {
     return new LiteralList(
         exp.values.map(visitExpression).toList(growable: false),
         typeArgument: emitOptionalType(exp.type.typeArguments.single));
   }
 
   Expression visitLiteralMap(tree.LiteralMap exp) {
     List<LiteralMapEntry> entries = new List<LiteralMapEntry>.generate(
@@ skipping 124 matching lines @@
 
   Expression visitNot(tree.Not exp) {
     return new UnaryOperator('!', visitExpression(exp.operand));
   }
 
   Expression visitVariable(tree.Variable exp) {
     return new Identifier(getVariableName(exp))
                ..element = exp.element;
   }
 
+  FunctionExpression makeSubFunction(tree.FunctionDefinition function) {
+    return new ASTEmitter.inner(this).emit(function);
+  }
+
+  Expression visitFunctionExpression(tree.FunctionExpression exp) {
+    return makeSubFunction(exp.definition)..name = null;
+  }
+
+  void visitFunctionDeclaration(tree.FunctionDeclaration node) {
+    assert(variableNames[node.variable] == null);
+    String name = getVariableName(node.variable);
+    FunctionExpression inner = makeSubFunction(node.definition);
+    inner.name = name;
+    FunctionDeclaration decl = new FunctionDeclaration(inner);
+    declaredVariables.add(node.variable);
+    statementBuffer.add(decl);
+    visitStatement(node.next);
+  }
+
   TypeAnnotation emitType(DartType type) {
     if (type is GenericType) {
       return new TypeAnnotation(
           type.element.name,
           type.typeArguments.map(emitType).toList(growable:false))
           ..dartType = type;
     } else if (type is VoidType) {
       return new TypeAnnotation('void')
           ..dartType = type;
     } else if (type is TypeVariableType) {
@@ skipping 78 matching lines @@
     return new LiteralSymbol(exp.name);
   }
 
   Expression visitType(TypeConstExp exp) {
     DartType type = exp.type;
     return new LiteralType(type.name)
                ..type = type;
   }
 
   Expression visitVariable(VariableConstExp exp) {
-    String name = parent.getConstantName(exp.element);
+    Element element = exp.element;
+    if (element.kind != ElementKind.VARIABLE) {
+      return new Identifier(element.name)..element = element;
+    }
+    String name = parent.getConstantName(element);
     return new Identifier(name)
-               ..element = exp.element;
+               ..element = element;
   }
 
   Expression visitFunction(FunctionConstExp exp) {
     return new Identifier(exp.element.name)
                ..element = exp.element;
   }
 
 }
+
+/// Moves function parameters into a separate variable if one of its uses is
+/// shadowed by an inner function parameter.
+/// This artifact is necessary because function parameters cannot be renamed.
+class UnshadowParameters extends tree.RecursiveVisitor {
+
+  /// Maps parameter names to their bindings.
+  Map<String, tree.Variable> environment = <String, tree.Variable>{};
+
+  /// Parameters that are currently shadowed by another parameter.
+  Set<tree.Variable> shadowedParameters = new Set<tree.Variable>();
+
+  /// Parameters that are used in a context where it is shadowed.
+  Set<tree.Variable> hasShadowedUse = new Set<tree.Variable>();
+
+  void unshadow(tree.FunctionDefinition definition) {
+    visitFunctionDefinition(definition);
+  }
+
+  visitFunctionDefinition(tree.FunctionDefinition definition) {
+    var oldShadow = shadowedParameters;
+    var oldEnvironment = environment;
+    environment = new Map<String, tree.Variable>.from(environment);
+    shadowedParameters = new Set<tree.Variable>.from(shadowedParameters);
+    for (tree.Variable param in definition.parameters) {
+      tree.Variable oldVariable = environment[param.element.name];
+      if (oldVariable != null) {
+        shadowedParameters.add(oldVariable);
+      }
+      environment[param.element.name] = param;
+    }
+    visitStatement(definition.body);
+    environment = oldEnvironment;
+    shadowedParameters = oldShadow;
+
+    for (int i=0; i<definition.parameters.length; i++) {
+      tree.Variable param = definition.parameters[i];
+      if (hasShadowedUse.remove(param)) {
+        tree.Variable newParam = new tree.Variable(definition, param.element);
+        definition.parameters[i] = newParam;
+        definition.body = new tree.Assign(param, newParam, definition.body);
+        newParam.writeCount = 1; // Being a parameter counts as a write.
+      }
+    }
+  }
+
+  visitVariable(tree.Variable variable) {
+    if (shadowedParameters.contains(variable)) {
+      hasShadowedUse.add(variable);
+    }
+  }
+
+}