Work in progress: changes to interpretation

frog/gen.dart

Index: frog/gen.dart
diff --git a/frog/gen.dart b/frog/gen.dart
index 029c1a600d342812e4c0c82147c8fda705bb46e3..16098f59caf86f350177608201683aa66db77931 100644
--- a/frog/gen.dart
+++ b/frog/gen.dart
@@ -56,8 +56,8 @@ class WorldGenerator {
 
       // Generate callbacks from JS to isolate code if needed
       if (corejs.useWrap0 || corejs.useWrap1) {
-        genMethod(world.coreimpl.types['IsolateContext'].getMember('eval'));
-        genMethod(world.coreimpl.types['EventLoop'].getMember('run'));
+        invokeMethod(world.coreimpl.types['IsolateContext'].getMember('eval'));
+        invokeMethod(world.coreimpl.types['EventLoop'].getMember('run'));
       }
 
       corejs.useIsolates = true;
@@ -102,11 +102,11 @@ class WorldGenerator {
     type.factories.forEach((f) => members.add(f));
     for (var member in members) {
       if (member is PropertyMember) {
-        if (member.getter != null) genMethod(member.getter);
-        if (member.setter != null) genMethod(member.setter);
+        if (member.getter != null) invokeMethod(member.getter);
+        if (member.setter != null) invokeMethod(member.setter);
       }
 
-      if (member is MethodMember) genMethod(member);
+      if (member is MethodMember) invokeMethod(member);
     }
   }
 
@@ -226,10 +226,16 @@ class WorldGenerator {
     }
   }
 
-  genMethod(Member meth, [MethodGenerator enclosingMethod=null]) {
-    if (!meth.isGenerated && !meth.isAbstract && meth.definition != null) {
-      new MethodGenerator(meth, enclosingMethod).run();
+  Type invokeMethod(Member method, [Value target, Arguments args]) {
+    if (method.isAbstract || method.definition == null) {
+      return method.returnType;
     }
+
+    var s = method.specializer;
+    if (s == null) {
+      s = new MethodSpecializer(method);
+    }
+    return s.run(target, args);
   }
 
   String _prototypeOf(Type type, String name) {
@@ -373,8 +379,7 @@ class WorldGenerator {
       }
     } else {
       Member standardConstructor = type.constructors[''];
-      if (standardConstructor == null ||
-          standardConstructor.generator == null) {
+      if (standardConstructor == null || !standardConstructor.isUsed) {
         if (!type.isNative) {
           writer.writeln('function ${type.jsname}() {}');
         }
@@ -383,7 +388,7 @@ class WorldGenerator {
       }
 
       for (var c in type.constructors.getValues()) {
-        if (c.generator != null && c != standardConstructor) {
+        if (c.isUsed && c != standardConstructor) {
           c.generator.writeDefinition(writer, null);
         }
       }
@@ -459,16 +464,8 @@ class WorldGenerator {
    * This predicate determines when we need to define lib_Float32Array.
    */
   _typeNeedsHolderForStaticMethods(Type type) {
-    for (var member in type.members.getValues()) {
-      if (member.isMethod) {
-        if (member.isConstructor || member.isStatic) {
-          if (member.isGenerated) {
-            return true;
-          }
-        }
-      }
-    }
-    return false;
+    return type.members.getValues().some(
+        (m) => m.isUsed && m.isMethod && (m.isConstructor || m.isStatic));
   }
 
   /**
@@ -558,7 +555,7 @@ function $inheritsMembers(child, parent) {
   }
 
   _writeMethod(Member m) {
-    if (m.generator != null) {
+    if (m.isUsed) {
       m.generator.writeDefinition(writer, null);
     } else if (m is MethodMember && m.isNative
         && m._providePropertySyntax && !m._provideFieldSyntax) {
@@ -745,13 +742,112 @@ function $inheritsMembers(child, parent) {
 
 
 /**
- * A naive code generator for Dart.
+ * When inferring types, this will support potentially creating multiple
+ * copies of a method with different signatures. We don't implement that yet,
+ * though. Right now it's just a way of guarding against recursive invokes
+ * and tracking [option.inferTypes] specific state for a method.
  */
+// TODO(jmesserly): better name for this and MethodGenerator? (Perhaps
+// this should be named MethodGenerator and the other one should be
+// MethodInterpreter or something like that.)
+class MethodSpecializer {
+  final Member method;
+  final MethodGenerator enclosingMethod;
+
+  // These are used to track what inferred types are assumed by the generated
+  // code. Eventually we may want to use this as a key and generate multiple
+  // typed copies of a method. However that needs good heuristics to avoid
+  // making the code too big.
+  Value _thisObject;
+  List<VariableValue> _arguments;
+  int _evalCount = 0;
+
+  MethodGenerator generator;
+
+  MethodSpecializer(this.method, [this.enclosingMethod]) {
+    assert(method.specializer === null);
+    // TODO(jmesserly): I don't like side effects from constructors, but
+    // otherwise we rely on our callers to maintain this invariant which isn't
+    // great either.
+    method.specializer = this;
+    reset();
+  }
+
+  reset() {
+    _thisObject = new VariableValue(method.declaringType, 'this', null);
+    _arguments = method.parameters.map(
+        (p) => new VariableValue(p.type, p.name, p.span));
+  }
+
+  // TODO(jmesserly): Should this be renamed invoke?
+  // Also our caller has already taken care of named/missing args, but that's
+  // probably not what we want. Instead that could be handled here, and we
+  // could return a Value that performs the method call. (In other words,
+  // absorb some of MethodMember.invoke's current implementation.)
+  Type run([Value target, Arguments args]) {
+    method.markUsed();
+
+    // If this is the first time we've seen this call, or the argument types are
+    // now different, we'll need to interpret the method body.
+    bool shouldEval = _evalCount == 0;
+    bool infer = options.inferTypes && _evalCount <= options.maxInferenceCalls;
+
+    // Unless type inference is on, ignore passed in target & arg types.
+    if (infer) {
+      // TODO(jmesserly): should unify the target type too!
+      List<Value> argValues;
+      if (args == null) {
+        // TODO(jmesserly): we should always be passing in arguments
+        argValues = method.parameters.map(
+            (p) => new Value(p.type, p.name, p.span));
+      } else {
+        argValues = args.values;
+      }
+
+      for (int i = 0; i < _arguments.length; i++) {
+        var orig = _arguments[i].value;
+        var updated = Value.union(orig, argValues[i]);
+        if (updated !== orig) {
+          _arguments[i] = _arguments[i].replaceValue(updated);
+          shouldEval = true;
+        }
+      }
+    }
+
+    if (shouldEval) {
+      _evalCount++;
+
+      if (infer && _evalCount > options.maxInferenceCalls) {
+        // If we've tried too many times and haven't converged, rerun without
+        // inference.
+        world.info('inference failed to converge for method "${method.name}"',
+            method.span);
+
+        // Discard inferred things so we do a fresh run.
+        reset();
+      }
+
+      // Note: this might replace a generator from higher up on our call stack,
+      // if we're calling this method recursively (which is rather common, e.g.
+      // toString methods are potentially recursive). That's okay: the later
+      // generator will have collected more type info, so let it win.
+      // (Eventually we'll have some specialization, and key these off of the
+      // input types.)
+      generator = new MethodGenerator(method, enclosingMethod);
+      generator.evalBody(_thisObject, new Arguments(null, _arguments));
+    }
+
+    return generator._inferResult();
+  }
+}
+
+
+/** A code generator and abstract interpreter for Dart function/method. */
 class MethodGenerator implements TreeVisitor {
-  Member method;
+  final Member method;
+  final MethodGenerator enclosingMethod;
   CodeWriter writer;
   BlockScope _scope;
-  MethodGenerator enclosingMethod;
   bool needsThis;
   List<String> _paramCode;
 
@@ -769,9 +865,11 @@ class MethodGenerator implements TreeVisitor {
    */
   Set<String> captures;
 
+  /** The inferred result type. */
+  Value _inferredResult;
   CounterLog counters;
 
-  MethodGenerator(this.method, this.enclosingMethod)
+  MethodGenerator(this.method, [this.enclosingMethod])
       : writer = new CodeWriter(), needsThis = false {
     if (enclosingMethod != null) {
       _scope = new BlockScope(this, enclosingMethod._scope, method.definition);
@@ -784,6 +882,10 @@ class MethodGenerator implements TreeVisitor {
     counters = world.counters;
   }
 
+  // TODO(jmesserly): do we need anything else here? (e.g. do we need to replace
+  // the scope with an empty scope so variables don't leak?)
+  Value evalExpression(Expression expr) => expr.visit(this);
+
   Library get library() => method.library;
 
   // TODO(jimhug): Where does this really belong?
@@ -833,43 +935,48 @@ class MethodGenerator implements TreeVisitor {
     */
   }
 
-  run() {
-    if (method.isGenerated) return;
-
-    // This avoids any attempts to infer across recursion.
-    method.isGenerated = true;
-    method.generator = this;
-
-    // Create most generic possible call for this method.
-    var thisObject;
-    if (method.isConstructor) {
-      thisObject = new ObjectValue(false, method.declaringType, method.span);
-      thisObject.initFields();
-    } else {
-      thisObject = new Value(method.declaringType, 'this', null);
-    }
-    var values = [];
-    for (var p in method.parameters) {
-      values.add(new Value(p.type, p.name, null));
+  Type _inferResult() {
+    if (method.isNative || !options.inferTypes) {
+      // If it's a native, use the return type.
+      var t = method.returnType;
+      if (t.isBool && (method.library.isCore || method.library.isCoreImpl)) {
+        // We trust our core libraries not to return null from bools.
+        // I hope this trust is well placed!
+        t = world.nonNullBool;
+      }
+      return t;
     }
-    var args = new Arguments(null, values);
 
-    evalBody(thisObject, args);
+    if (_inferredResult == null) {
+      // Handle the implicit 'return null;'
+      // TODO(jmesserly): this needs to be added in more cases, e.g. if there
+      // is a "return" statement in one control flow path but not another
+      // path.
+      _inferredResult = Value.fromNull(null);
+    }
+    return _inferredResult.type;
+  }
 
-    if (method.definition.nativeBody != null) {
+  _evalNativeBody() {
+    // TODO: the .dynamic here is annoying
+    var nativeBody = method.definition.dynamic.nativeBody;
+    if (nativeBody != null) {
       // Throw away the code--it was just used for tree shaking purposes.
-      writer = new CodeWriter();
-      if (method.definition.nativeBody == '') {
-        method.generator = null;
+      if (nativeBody == '') {
+        // Set this to null so we don't try to write code.
+        writer = null;
       } else {
         _paramCode = map(method.parameters, (p) => p.name);
-        writer.write(method.definition.nativeBody);
+        writer = new CodeWriter();
+        writer.write(nativeBody);
       }
     }
   }
 
-
   writeDefinition(CodeWriter defWriter, LambdaExpression lambda/*=null*/) {
+    // No need to write anything for natives with no native body.
+    if (writer == null) return;
+
     // To implement block scope: capture any variables we need to.
     var paramCode = _paramCode;
     var names = null;
@@ -1015,25 +1122,31 @@ class MethodGenerator implements TreeVisitor {
     return newObject.setField(field, value, duringInit: true);
   }
 
-  evalBody(Value newObject, Arguments args) {
+  void evalBody(thisObject, Arguments args) {
+    if (method.isConstructor && thisObject is! ObjectValue) {
+      // TODO(jmesserly): fix how contructors interact...
+      thisObject = new ObjectValue(false, method.declaringType, method.span);
+      thisObject.initFields();
+    }
+
     bool fieldsSet = false;
-    if (method.isNative && method.isConstructor && newObject is ObjectValue) {
-      newObject.dynamic.seenNativeInitializer = true;
+    if (method.isNative && method.isConstructor) {
+      thisObject.dynamic.seenNativeInitializer = true;
     }
     // Collects parameters for writing signature in the future.
     _paramCode = [];
     for (int i = 0; i < method.parameters.length; i++) {
       var p = method.parameters[i];
       Value currentArg = null;
-      // TODO(jimhug): bareCount is O(N)
       if (i < args.bareCount) {
         currentArg = args.values[i];
       } else {
-        // Handle named or missing arguments
+        // TODO(jmesserly): right now we're evaluating named/missing args on
+        // the call site side. That should probably move into here.
         currentArg = args.getValue(p.name);
         if (currentArg === null) {
           // Ensure default value for param has been generated
-          p.genValue(method, method.generator);
+          p.genValue(method, this);
           currentArg = p.value;
         }
       }
@@ -1041,18 +1154,19 @@ class MethodGenerator implements TreeVisitor {
       if (p.isInitializer) {
         _paramCode.add(p.name);
         fieldsSet = true;
-        _initField(newObject, p.name, currentArg, p.definition.span);
+        _initField(thisObject, p.name, currentArg, p.definition.span);
       } else {
         var paramValue = _scope.declareParameter(p);
         _paramCode.add(paramValue.code);
-        if (newObject != null && newObject.isConst) {
+        if (thisObject != null && thisObject.isConst) {
           _scope.assign(p.name, currentArg.convertTo(this, p.type));
         }
       }
     }
 
     var initializerCall = null;
-    final declaredInitializers = method.definition.initializers;
+    var methodDef = method.definition;
+    final declaredInitializers = methodDef.initializers;
     if (declaredInitializers != null) {
       for (var init in declaredInitializers) {
         if (init is CallExpression) {
@@ -1073,7 +1187,7 @@ class MethodGenerator implements TreeVisitor {
           // context, so "this." is not in scope
           var initValue = visitValue(init.y);
           fieldsSet = true;
-          _initField(newObject, left.name.name, initValue, left.span);
+          _initField(thisObject, left.name.name, initValue, left.span);
         } else {
           world.error('invalid initializer', init.span);
         }
@@ -1090,8 +1204,8 @@ class MethodGenerator implements TreeVisitor {
       }
     }
 
-    if (method.isConstructor && newObject is ObjectValue) {
-      var fields = newObject.dynamic.fields;
+    if (method.isConstructor && thisObject is ObjectValue) {
+      var fields = thisObject.dynamic.fields;
       for (var field in fields.getKeys()) {
         var value = fields[field];
         if (value !== null) {
@@ -1102,25 +1216,25 @@ class MethodGenerator implements TreeVisitor {
 
     // TODO(jimhug): Doing this call last does not match spec.
     if (initializerCall != null) {
-      evalInitializerCall(newObject, initializerCall, fieldsSet);
+      evalInitializerCall(thisObject, initializerCall, fieldsSet);
     }
 
-    if (method.isConstructor && newObject !== null && newObject.isConst) {
-      newObject.validateInitialized(method.span);
+    if (method.isConstructor && thisObject !== null && thisObject.isConst) {
+      thisObject.validateInitialized(method.span);
     } else if (method.isConstructor) {
-      var fields = newObject.dynamic.fields;
+      var fields = thisObject.dynamic.fields;
       for (var field in fields.getKeys()) {
         var value = fields[field];
         if (value === null && field.isFinal &&
             field.declaringType == method.declaringType &&
-            !newObject.dynamic.seenNativeInitializer) {
+            !thisObject.dynamic.seenNativeInitializer) {
           world.error('uninitialized final field "${field.name}"',
             field.span, method.span);
         }
       }
     }
 
-    var body = method.definition.body;
+    var body = methodDef.body;
 
     if (body === null) {
       // TODO(jimhug): Move check into resolve on method.
@@ -1131,6 +1245,8 @@ class MethodGenerator implements TreeVisitor {
     } else {
       visitStatementsInBlock(body);
     }
+
+    _evalNativeBody();
   }
 
   evalInitializerCall(ObjectValue newObject, CallExpression node,
@@ -1178,7 +1294,7 @@ class MethodGenerator implements TreeVisitor {
 
     var newArgs = _makeArgs(node.arguments);
     // ???? wacky stuff ????
-    world.gen.genMethod(m);
+    world.gen.invokeMethod(m);
 
     m._evalConstConstructor(newObject, newArgs);
 
@@ -1413,7 +1529,7 @@ class MethodGenerator implements TreeVisitor {
     var funcValue = _scope.create(meth.name, meth.functionType,
         method.definition.span, isFinal:true);
 
-    world.gen.genMethod(meth, this);
+    new MethodSpecializer(meth, this).run();
     meth.generator.writeDefinition(writer, null);
     return false;
   }
@@ -1425,13 +1541,15 @@ class MethodGenerator implements TreeVisitor {
   bool visitReturnStatement(ReturnStatement node) {
     if (node.value == null) {
       // This is essentially "return null".
-      // It can't issue a warning because every type is nullable.
+      // TODO(jmesserly): this should be a warning in non-void methods
       writer.writeln('return;');
+      _inferredResult = Value.union(_inferredResult, Value.fromNull(null));
     } else {
       if (method.isConstructor) {
         world.error('return of value not allowed from constructor', node.span);
       }
       var value = visitTypedValue(node.value, method.returnType);
+      _inferredResult = Value.union(_inferredResult, value);
       writer.writeln('return ${value.code};');
     }
     return true;
@@ -1511,9 +1629,8 @@ class MethodGenerator implements TreeVisitor {
     var exit1 = node.trueBranch.visit(this);
     if (node.falseBranch != null) {
       writer.write('else ');
-      if (node.falseBranch.visit(this) && exit1) {
-        return true;
-      }
+      var exit2 = node.falseBranch.visit(this);
+      return exit1 && exit2;
     }
     return false;
   }
@@ -1887,17 +2004,24 @@ class MethodGenerator implements TreeVisitor {
     var name = (node.func.name != null) ? node.func.name.name : '';
 
     MethodMember meth = _makeLambdaMethod(name, node.func);
-    final lambdaGen = new MethodGenerator(meth, this);
     if (name != '') {
-      // Note: we don't want to put this in our enclosing scope because the
-      // name shouldn't be visible except inside the lambda. We also don't want
-      // to put the name directly in the lambda's scope because parameters are
-      // allowed to shadow it. So we create an extra scope for it to go into.
-      lambdaGen._scope.create(name, meth.functionType, meth.definition.span,
+      // Note: create a block scope for the lambda's name to go into. This keeps
+      // it from leaking into our current scope, and also allows the lambda's
+      // parameters to shadow it.
+      _pushBlock(node);
+      _scope.create(name, meth.functionType, meth.definition.span,
           isFinal:true);
-      lambdaGen._pushBlock(node);
     }
-    lambdaGen.run();
+
+    // TODO(jmesserly): if we wanted to, we could track this as a function
+    // value, and let it be invoked (or not) by whoever uses it.
+    // (Since the number of lambdas is bounded in the program it may be
+    // viable to track them all individually as Values.)
+    new MethodSpecializer(meth, this).run();
+
+    if (name != '') {
+      _popBlock(node);
+    }
 
     var w = new CodeWriter();
     meth.generator.writeDefinition(w, node);