Refactor runtime into libraries, better type reps

lib/runtime/_types.js

Index: lib/runtime/_types.js
diff --git a/lib/runtime/_types.js b/lib/runtime/_types.js
new file mode 100644
index 0000000000000000000000000000000000000000..e8dc2d0c38c034a33867abc9f5b2719181fa7fb5
--- /dev/null
+++ b/lib/runtime/_types.js
@@ -0,0 +1,439 @@
+// Copyright (c) 2015, 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.
+
+/* This library defines the representation of runtime types.
+*/
+
+dart_library.library('dart_runtime/_types', null, /* Imports */[
+], /* Lazy Imports */[
+  'dart/core',
+  'dart_runtime/_classes',
+  'dart_runtime/_rtti'
+], function(exports, core, classes, rtti) {
+  'use strict';
+
+  const getOwnPropertyNames = Object.getOwnPropertyNames;
+
+  const assert = dart_utils.assert;
+  const copyProperties = dart_utils.copyProperties;
+  const safeGetOwnProperty = dart_utils.safeGetOwnProperty;
+
+  class TypeRep extends rtti.LazyTagged(() => core.Type) {
+    get name() {return this.toString();}
+  }
+
+  class Dynamic extends TypeRep {
+    toString() { return "dynamic"; }
+  }
+  let dynamicR = new Dynamic();
+  exports.dynamic = dynamicR;
+
+  class Void extends TypeRep {
+    toString() { return "void"; }
+  }
+
+  let voidR = new Void();
+  exports.void = voidR;
+
+  class Bottom extends TypeRep {
+    toString() { return "bottom"; }
+  };
+  let bottomR = new Bottom();
+  exports.bottom = bottomR;
+
+  class AbstractFunctionType extends TypeRep {
+    constructor() {
+      super();
+      this._stringValue = null;
+    }
+
+    toString() { return this.name; }
+
+    get name() {
+      if (this._stringValue) return this._stringValue;
+
+      let buffer = '(';
+      for (let i = 0; i < this.args.length; ++i) {
+        if (i > 0) {
+          buffer += ', ';
+        }
+        buffer += typeName(this.args[i]);
+      }
+      if (this.optionals.length > 0) {
+        if (this.args.length > 0) buffer += ', ';
+        buffer += '[';
+        for (let i = 0; i < this.optionals.length; ++i) {
+          if (i > 0) {
+            buffer += ', ';
+          }
+          buffer += typeName(this.optionals[i]);
+        }
+        buffer += ']';
+      } else if (Object.keys(this.named).length > 0) {
+        if (this.args.length > 0) buffer += ', ';
+        buffer += '{';
+        let names = getOwnPropertyNames(this.named).sort();
+        for (let i = 0; i < names.length; ++i) {
+          if (i > 0) {
+            buffer += ', ';
+          }
+          buffer += names[i] + ': ' + typeName(this.named[names[i]]);
+        }
+        buffer += '}';
+      }
+
+      buffer += ') -> ' + typeName(this.returnType);
+      this._stringValue = buffer;
+      return buffer;
+    }
+  }
+
+  class FunctionType extends AbstractFunctionType {
+    constructor(returnType, args, optionals, named) {
+      super();
+      this.returnType = returnType;
+      this.args = args;
+      this.optionals = optionals;
+      this.named = named;
+    }
+  }
+
+  class Typedef extends AbstractFunctionType {
+    constructor(name, closure) {
+      super();
+      this._name = name;
+      this._closure = closure;
+      this._functionType = null;
+    }
+
+    get name() {
+      return this._name;
+    }
+
+    get functionType() {
+      if (!this._functionType) {
+        this._functionType = this._closure();
+      }
+      return this._functionType;
+    }
+
+    get returnType() {
+      return this.functionType.returnType;
+    }
+
+    get args() {
+      return this.functionType.args;
+    }
+
+    get optionals() {
+      return this.functionType.optionals;
+    }
+
+    get named() {
+      return this.functionType.named;
+    }
+  }
+
+  function functionType(returnType, args, extra) {
+    // TODO(vsm): Cache / memomize?
+    let optionals;
+    let named;
+    if (extra === void 0) {
+      optionals = [];
+      named = {};
+    } else if (extra instanceof Array) {
+      optionals = extra;
+      named = {};
+    } else {
+      optionals = [];
+      named = extra;
+    }
+    return new FunctionType(returnType, args, optionals, named);
+  }
+  exports.functionType = functionType;
+
+  function typedef(name, closure) {
+    return new Typedef(name, closure);
+  }
+  exports.typedef = typedef;
+
+  function isDartType(type) {
+    return rtti.read(type) === core.Type;
+  }
+  exports.isDartType = isDartType;
+
+  function typeName(type) {
+    // Non-instance types
+    if (type instanceof TypeRep) return type.toString();
+    // Instance types
+    let tag = rtti.read(type);
+    if (tag === core.Type) {
+      let name = type.name;
+      let args = classes.getGenericArgs(type);
+      if (args) {
+        name += '<';
+        for (let i = 0; i < args.length; ++i) {
+          if (i > 0) name += ', ';
+          name += typeName(args[i]);
+        }
+        name += '>';
+      }
+      return name;
+    }
+    if (tag) return "Not a type: " + tag.name;
+    return "JSObject<" + type.name + ">";
+  }
+  exports.typeName = typeName;
+
+  function isFunctionType(type) {
+    return type instanceof AbstractFunctionType || type == core.Function;
+  }
+
+  function isFunctionSubType(ft1, ft2) {
+    if (ft2 == core.Function) {
+      return true;
+    }
+
+    let ret1 = ft1.returnType;
+    let ret2 = ft2.returnType;
+
+    if (!isSubtype_(ret1, ret2)) {
+      // Covariant return types
+      // Note, void (which can only appear as a return type) is effectively
+      // treated as dynamic.  If the base return type is void, we allow any
+      // subtype return type.
+      // E.g., we allow:
+      //   () -> int <: () -> void
+      if (ret2 != voidR) {
+        return false;
+      }
+    }
+
+    let args1 = ft1.args;
+    let args2 = ft2.args;
+
+    if (args1.length > args2.length) {
+      return false;
+    }
+
+    for (let i = 0; i < args1.length; ++i) {
+      if (!isSubtype_(args2[i], args1[i], true)) {
+        return false;
+      }
+    }
+
+    let optionals1 = ft1.optionals;
+    let optionals2 = ft2.optionals;
+
+    if (args1.length + optionals1.length < args2.length + optionals2.length) {
+      return false;
+    }
+
+    let j = 0;
+    for (let i = args1.length; i < args2.length; ++i, ++j) {
+      if (!isSubtype_(args2[i], optionals1[j], true)) {
+        return false;
+      }
+    }
+
+    for (let i = 0; i < optionals2.length; ++i, ++j) {
+      if (!isSubtype_(optionals2[i], optionals1[j], true)) {
+        return false;
+      }
+    }
+
+    let named1 = ft1.named;
+    let named2 = ft2.named;
+
+    let names = getOwnPropertyNames(named2);
+    for (let i = 0; i < names.length; ++i) {
+      let name = names[i];
+      let n1 = named1[name];
+      let n2 = named2[name];
+      if (n1 === void 0) {
+        return false;
+      }
+      if (!isSubtype_(n2, n1, true)) {
+        return false;
+      }
+    }
+
+    return true;
+  }
+
+  /**
+   * Computes the canonical type.
+   * This maps JS types onto their corresponding Dart Type.
+   */
+  // TODO(jmesserly): lots more needs to be done here.
+  function canonicalType(t) {
+    if (t === Object) return core.Object;
+    if (t === Function) return core.Function;
+    if (t === Array) return core.List;
+
+    // We shouldn't normally get here with these types, unless something strange
+    // happens like subclassing Number in JS and passing it to Dart.
+    if (t === String) return core.String;
+    if (t === Number) return core.double;
+    if (t === Boolean) return core.bool;
+    return t;
+  }
+
+  const subtypeMap = new Map();
+  function isSubtype(t1, t2) {
+    // See if we already know the answer
+    // TODO(jmesserly): general purpose memoize function?
+    let map = subtypeMap.get(t1);
+    let result;
+    if (map) {
+      result = map.get(t2);
+      if (result !== void 0) return result;
+    } else {
+      subtypeMap.set(t1, map = new Map());
+    }
+    result = isSubtype_(t1, t2)
+    map.set(t2, result);
+    return result;
+  }
+  exports.isSubtype = isSubtype;
+
+  function _isBottom(type, dynamicIsBottom) {
+    return (type == dynamicR && dynamicIsBottom) || type == bottomR;
+  }
+
+  function _isTop(type, dynamicIsBottom) {
+    return type == core.Object || (type == dynamicR && !dynamicIsBottom);
+  }
+
+  function isSubtype_(t1, t2, opt_dynamicIsBottom) {
+    let dynamicIsBottom =
+      opt_dynamicIsBottom === void 0 ? false : opt_dynamicIsBottom;
+
+    t1 = canonicalType(t1);
+    t2 = canonicalType(t2);
+    if (t1 == t2) return true;
+
+    // In Dart, dynamic is effectively both top and bottom.
+    // Here, we treat dynamic as one or the other depending on context,
+    // but not both.
+
+    // Trivially true.
+    if (_isTop(t2, dynamicIsBottom) || _isBottom(t1, dynamicIsBottom)) {
+      return true;
+    }
+
+    // Trivially false.
+    if (_isTop(t1, dynamicIsBottom) || _isBottom(t2, dynamicIsBottom)) {
+      return false;
+    }
+
+    // "Traditional" name-based subtype check.
+    if (isClassSubType(t1, t2)) {
+      return true;
+    }
+
+    // Function subtyping.
+    // TODO(vsm): Handle Objects with call methods.  Those are functions
+    // even if they do not *nominally* subtype core.Function.
+    if (isFunctionType(t1) &&
+        isFunctionType(t2)) {
+      return isFunctionSubType(t1, t2);
+    }
+    return false;
+  }
+
+  function isClassSubType(t1, t2) {
+    // We support Dart's covariant generics with the caveat that we do not
+    // substitute bottom for dynamic in subtyping rules.
+    // I.e., given T1, ..., Tn where at least one Ti != dynamic we disallow:
+    // - S !<: S<T1, ..., Tn>
+    // - S<dynamic, ..., dynamic> !<: S<T1, ..., Tn>
+    t1 = canonicalType(t1);
+    assert(t2 == canonicalType(t2));
+    if (t1 == t2) return true;
+
+    if (t1 == core.Object) return false;
+
+    // If t1 is a JS Object, we may not hit core.Object.
+    if (t1 == null) return t2 == core.Object || t2 == dynamicR;
+
+    // Check if t1 and t2 have the same raw type.  If so, check covariance on
+    // type parameters.
+    let raw1 = classes.getGenericClass(t1);
+    let raw2 = classes.getGenericClass(t2);
+    if (raw1 != null && raw1 == raw2) {
+      let typeArguments1 = classes.getGenericArgs(t1);
+      let typeArguments2 = classes.getGenericArgs(t2);
+      let length = typeArguments1.length;
+      if (typeArguments2.length == 0) {
+        // t2 is the raw form of t1
+        return true;
+      } else if (length == 0) {
+        // t1 is raw, but t2 is not
+        return false;
+      }
+      assert(length == typeArguments2.length);
+      for (let i = 0; i < length; ++i) {
+        if (!isSubtype(typeArguments1[i], typeArguments2[i])) {
+          return false;
+        }
+      }
+      return true;
+    }
+
+    // Check superclass.
+    if (isClassSubType(t1.__proto__, t2)) return true;
+
+    // Check mixins.
+    let mixins = classes.getMixins(t1);
+    if (mixins) {
+      for (let m1 of mixins) {
+        // TODO(jmesserly): remove the != null check once we can load core libs.
+        if (m1 != null && isClassSubType(m1, t2)) return true;
+      }
+    }
+
+    // Check interfaces.
+    let getInterfaces = classes.getImplements(t1);
+    if (getInterfaces) {
+      for (let i1 of getInterfaces()) {
+        // TODO(jmesserly): remove the != null check once we can load core libs.
+        if (i1 != null && isClassSubType(i1, t2)) return true;
+      }
+    }
+
+    return false;
+  }
+
+  // TODO(jmesserly): this isn't currently used, but it could be if we want
+  // `obj is NonGroundType<T,S>` to be rejected at runtime instead of compile
+  // time.
+  function isGroundType(type) {
+    // TODO(vsm): Cache this if we start using it at runtime.
+
+    if (type instanceof AbstractFunctionType) {
+      if (!_isTop(type.returnType, false)) return false;
+      for (let i = 0; i < type.args.length; ++i) {
+        if (!_isBottom(type.args[i], true)) return false;
+      }
+      for (let i = 0; i < type.optionals.length; ++i) {
+        if (!_isBottom(type.optionals[i], true)) return false;
+      }
+      let names = getOwnPropertyNames(type.named);
+      for (let i = 0; i < names.length; ++i) {
+        if (!_isBottom(type.named[names[i]], true)) return false;
+      }
+      return true;
+    }
+
+    let typeArgs = classes.getGenericArgs(type);
+    if (!typeArgs) return true;
+    for (let t of typeArgs) {
+      if (t != core.Object && t != dynamicR) return false;
+    }
+    return true;
+  }
+  exports.isGroundType = isGroundType;
+
+});