First step for modular output in fasta.

pkg/front_end/lib/src/fasta/kernel/kernel_outline_shaker.dart

Index: pkg/front_end/lib/src/fasta/kernel/kernel_outline_shaker.dart
diff --git a/pkg/front_end/lib/src/fasta/kernel/kernel_outline_shaker.dart b/pkg/front_end/lib/src/fasta/kernel/kernel_outline_shaker.dart
new file mode 100644
index 0000000000000000000000000000000000000000..3873795ccf6445c56911127b6ce00b36d34ea925
--- /dev/null
+++ b/pkg/front_end/lib/src/fasta/kernel/kernel_outline_shaker.dart
@@ -0,0 +1,433 @@
+// Copyright (c) 2016, 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.
+
+/// A transformation to create a self-contained modular kernel without
+/// unnecessary references to other libraries.
+library fasta.kernel.kernel_outline_shaker;
+
+import 'package:kernel/ast.dart';
+import 'package:kernel/core_types.dart';
+
+import '../errors.dart' show internalError;
+
+/// Removes from [program] unnecessary libraries, classes, and members.

[ahe, 2017/05/22 12:04:24]

Removes unnecessary libraries, classes, and members from [program].

+///
+/// This applies a simple "tree-shaking" technique: the full body of libraries
+/// whose URI match [isIncluded] are preserved, and so is the outline of the
+/// members and classes which are referred to transitively from these included
+/// libraries.
+///
+/// The intent is that the resulting program has the entire code that is meant
+/// to be included and the minimum required to prevent dangling references and
+/// allow modular program transformations.
+///
+/// Note that the resulting program may include libraries not in [isIncluded],
+/// but those will be marked as external. There should be no method bodies for
+/// any members of those libraries.
+///
+/// When [retainClassMembers] is true, all members of retained classes will be
+/// retained as well.
+void trimProgram(Program program, bool isIncluded(Uri uri),
+    {bool retainClassMembers: true}) {
+  var result = new _Analysis(program, isIncluded, retainClassMembers).run();
+  new _Shaker(result, isIncluded).transform(program);
+}
+
+/// Result of analyzing a program before tree-shaking it.
+abstract class _AnalysisResult {
+  /// Whether a library should be preserved and mark as external.
+  bool isLibraryUsed(Library library);
+
+  /// Whether a class should be preserved. If a class is preserved, its
+  /// supertypes will be preserved too, but some of it members may not be
+  /// included.
+  bool isClassUsed(Class cls);
+
+  /// Whether a member should be preserved. If so, its enclosing class/library
+  /// will be preserved too.
+  bool isMemberUsed(Member member);
+}
+
+/// Visitor used by [trimProgram] to collects which libraries, classes, and
+/// members should be preserved.
+class _Analysis extends RecursiveVisitor implements _AnalysisResult {
+  /// The program being analyzed.
+  final Program program;
+
+  /// Helper to fetch classes and members of the core libraries.
+  final CoreTypes coreTypes;
+
+  /// Filter to determine libraries that should be analyzed.
+  final Filter isIncluded;
+
+  /// When retaining a class, whether to retain all of its members.
+  // TODO(sigmund): delete this option once we figure out the long term plan. Do
+  // we need to do this? Today it seems necessary because some transformations
+  // require it, but maybe we don't need them all (e.g. only constructors and
+  // members whose inferenceTarget is referred do in the sources?) Do we need a
+  // different retention policy for including the type hierarchy with and
+  // without members?
+  final bool retainClassMembers;
+
+  /// Libraries that contained code that is transitively reachable from the
+  /// included libraries.
+  final Set<Library> _libraries = new Set<Library>();
+
+  /// Classes that are transitively reachable from the included libraries.
+  final Set<Class> _classes = new Set<Class>();
+
+  /// Members that are transitively reachable from the included libraries.
+  final Set<Member> _members = new Set<Member>();
+
+  @override
+  bool isLibraryUsed(Library library) => _libraries.contains(library);
+
+  @override
+  bool isClassUsed(Class cls) => _classes.contains(cls);
+
+  @override
+  bool isMemberUsed(Member m) => _members.contains(m);
+
+  _Analysis(this.program, this.isIncluded, this.retainClassMembers)
+      : coreTypes = new CoreTypes(program);
+
+  _AnalysisResult run() {
+    _markRequired();
+    _markMember(program.mainMethod);
+    for (var library in program.libraries) {
+      if (isIncluded(library.importUri)) {
+        library.accept(this);
+      }
+    }
+    return this;
+  }
+
+  /// Marks classes and members that are assumed to exist by fasta or by
+  /// transformers.
+  void _markRequired() {
+    coreTypes.objectClass.members.forEach(_markMember);
+
+    // These are assumed to be available by fasta:
+    _markClass(coreTypes.objectClass);
+    _markClass(coreTypes.nullClass);
+    _markClass(coreTypes.boolClass);
+    _markClass(coreTypes.intClass);
+    _markClass(coreTypes.numClass);
+    _markClass(coreTypes.doubleClass);
+    _markClass(coreTypes.stringClass);
+    _markClass(coreTypes.listClass);
+    _markClass(coreTypes.mapClass);
+    _markClass(coreTypes.iterableClass);
+    _markClass(coreTypes.iteratorClass);
+    _markClass(coreTypes.futureClass);
+    _markClass(coreTypes.streamClass);
+    _markClass(coreTypes.symbolClass);
+    _markClass(coreTypes.internalSymbolClass);
+    _markClass(coreTypes.typeClass);
+    _markClass(coreTypes.functionClass);
+    _markClass(coreTypes.invocationClass);
+    _markMember(coreTypes.getMember("dart:_internal", "ExternalName", ""));
+
+    // These are needed by the continuation (async/await) transformer:
+    _markClass(coreTypes.getClass('dart:core', 'Iterator'));
+    _markClass(coreTypes.getClass('dart:async', 'Future'));
+    _markClass(coreTypes.getClass('dart:async', 'FutureOr'));
+    _markClass(coreTypes.getClass('dart:async', 'Completer'));
+    _markMember(coreTypes.getMember('dart:async', 'Completer', 'sync'));
+    _markMember(coreTypes.getMember('dart:core', '_SyncIterable', ''));
+    _markMember(coreTypes.getMember('dart:async', '_StreamIterator', ''));
+    _markMember(coreTypes.getMember('dart:async', 'Future', 'microtask'));
+    _markMember(
+        coreTypes.getMember('dart:async', '_AsyncStarStreamController', ''));
+    _markMember(coreTypes.getTopLevelMember('dart:core', 'print'));
+    _markMember(
+        coreTypes.getTopLevelMember('dart:async', '_asyncThenWrapperHelper'));
+    _markMember(
+        coreTypes.getTopLevelMember('dart:async', '_asyncErrorWrapperHelper'));
+    _markMember(coreTypes.getTopLevelMember('dart:async', '_awaitHelper'));
+
+    // These are needed by the mixin transformer
+    _markMember(coreTypes.getMember('dart:core', '_InvocationMirror', ''));
+    _markMember(coreTypes.getMember('dart:core', 'List', 'from'));
+  }
+
+  /// Mark a library as used.
+  _markLibrary(Library lib) {
+    if (!_libraries.add(lib)) return;
+  }
+
+  /// Mark a class and it's supertypes as used.
+  void _markClass(Class cls) {
+    if (cls == null || !_classes.add(cls)) return;
+    _markLibrary(cls.parent);
+    visitList(cls.annotations, this);
+    cls.supertype?.accept(this);
+    cls.mixedInType?.accept(this);
+    visitList(cls.implementedTypes, this);
+    visitList(cls.typeParameters, this);
+
+    if (retainClassMembers) cls.members.forEach(_markMember);
+  }
+
+  _markMember(Member m) {
+    if (m == null || !_members.add(m)) return;
+    _markMemberInterface(m);
+    var parent = m.parent;
+    if (parent is Library) {
+      _markLibrary(parent);
+    } else if (parent is Class) {
+      _markClass(parent);
+    }
+  }
+
+  void _markMemberInterface(Member node) {
+    if (node is Field) {
+      node.type.accept(this);
+    } else if (node is Procedure) {
+      _markFunctionInterface(node.function);
+    }
+  }
+
+  _markFunctionInterface(FunctionNode node) {
+    for (var parameter in node.typeParameters) {
+      parameter.bound.accept(this);
+    }
+    for (var parameter in node.positionalParameters) {
+      parameter.type.accept(this);
+    }
+    for (var parameter in node.namedParameters) {
+      parameter.type.accept(this);
+    }
+    node.returnType.accept(this);
+  }
+
+  @override
+  visitFunctionNode(FunctionNode node) {
+    switch (node.asyncMarker) {
+      case AsyncMarker.Sync:
+        break;
+      case AsyncMarker.SyncStar:
+        _markClass(coreTypes.iterableClass);

[scheglov, 2017/05/18 15:54:08]

These classes are already included in _markRequired().

[Siggi Cherem (dart-lang), 2017/05/19 04:37:32]

good point. I removed them from here. Also - now that async is not in outlines,
we never hit this case.

+        break;
+      case AsyncMarker.Async:
+        _markClass(coreTypes.futureClass);
+        break;
+      case AsyncMarker.AsyncStar:
+        _markClass(coreTypes.streamClass);
+        break;
+      case AsyncMarker.SyncYielding:
+        break;
+    }
+    node.visitChildren(this);
+  }
+
+  @override
+  visitSuperInitializer(SuperInitializer node) {
+    _markMember(node.target);
+    node.visitChildren(this);
+  }
+
+  @override
+  visitRedirectingInitializer(RedirectingInitializer node) {
+    _markMember(node.target);
+    node.visitChildren(this);
+  }
+
+  @override
+  visitConstructorInvocation(ConstructorInvocation node) {
+    _markMember(node.target);
+    node.visitChildren(this);
+  }
+
+  @override
+  visitStaticInvocation(StaticInvocation node) {
+    _markMember(node.target);
+    node.visitChildren(this);
+  }
+
+  @override
+  visitDirectMethodInvocation(DirectMethodInvocation node) {
+    if (node.receiver is! ThisExpression) {
+      return internalError('Direct calls are only supported on "this"');
+    }
+    _markMember(node.target);
+    node.visitChildren(this);
+  }
+
+  @override
+  visitMethodInvocation(MethodInvocation node) {
+    _markMember(node.interfaceTarget);
+    node.visitChildren(this);
+  }
+
+  @override
+  visitStaticGet(StaticGet node) {
+    _markMember(node.target);
+    node.visitChildren(this);
+  }
+
+  @override
+  visitStaticSet(StaticSet node) {
+    _markMember(node.target);
+    node.visitChildren(this);
+  }
+
+  @override
+  visitDirectPropertyGet(DirectPropertyGet node) {
+    _markMember(node.target);
+    node.visitChildren(this);
+  }
+
+  @override
+  visitDirectPropertySet(DirectPropertySet node) {
+    _markMember(node.target);
+    node.visitChildren(this);
+  }
+
+  @override
+  visitSuperPropertyGet(SuperPropertyGet node) {
+    _markMember(node.interfaceTarget);
+    node.visitChildren(this);
+  }
+
+  @override
+  visitSuperPropertySet(SuperPropertySet node) {
+    _markMember(node.interfaceTarget);
+    node.visitChildren(this);
+  }
+
+  @override
+  visitPropertyGet(PropertyGet node) {
+    _markMember(node.interfaceTarget);
+    node.visitChildren(this);
+  }
+
+  @override
+  visitPropertySet(PropertySet node) {
+    _markMember(node.interfaceTarget);
+    node.visitChildren(this);
+  }
+
+  @override
+  visitListLiteral(ListLiteral node) {
+    _markClass(coreTypes.listClass);
+    node.visitChildren(this);
+  }
+
+  @override
+  visitMapLiteral(MapLiteral node) {
+    _markClass(coreTypes.mapClass);
+    node.visitChildren(this);
+  }
+
+  @override
+  visitStringConcatenation(StringConcatenation node) {
+    node.visitChildren(this);
+  }
+
+  @override
+  visitInterfaceType(InterfaceType node) {
+    _markClass(node.classNode);
+    node.visitChildren(this);
+  }
+
+  @override
+  visitSupertype(Supertype node) {
+    _markClass(node.classNode);
+    node.visitChildren(this);
+  }
+
+  @override
+  visitDoubleLiteral(DoubleLiteral node) {
+    _markClass(coreTypes.doubleClass);
+  }
+
+  @override
+  visitSymbolLiteral(SymbolLiteral node) {
+    _markClass(coreTypes.symbolClass);
+  }
+
+  @override
+  visitTypeLiteral(TypeLiteral node) {
+    _markClass(coreTypes.typeClass);
+    node.visitChildren(this);
+  }
+
+  @override
+  visitTypedefReference(Typedef node) {
+    return internalError('not implemented');
+  }
+}
+
+/// Transformer that trims everything in the excluded libraries that is not
+/// marked as preserved by the [_Analysis] above. For every member in these
+/// excluded libraries, this transformer also removes function bodies and
+/// initializers.
+class _Shaker extends Transformer {
+  final _AnalysisResult result;
+  final Filter isIncluded;
+
+  _Shaker(this.result, this.isIncluded);
+
+  void transform(Program program) {
+    var toRemove = new Set<Library>();
+    for (var library in program.libraries) {
+      if (!isIncluded(library.importUri)) {
+        if (!result.isLibraryUsed(library)) {
+          toRemove.add(library);
+        } else {
+          library.isExternal = true;
+          library.transformChildren(this);
+        }
+      }
+    }
+    program.libraries.removeWhere(toRemove.contains);
+  }
+
+  Class visitClass(Class node) {
+    if (!result.isClassUsed(node)) {
+      node.canonicalName?.unbind();
+      return null; // Remove the class.
+    } else {
+      node.transformChildren(this);
+      return node;
+    }
+  }
+
+  Member defaultMember(Member node) {
+    if (!result.isMemberUsed(node)) {
+      node.canonicalName?.unbind();
+      return null;
+    } else {
+      if (node is Procedure) {
+        _clearFunction(node.function);
+      } else if (node is Field) {
+        node.initializer = null;
+      } else if (node is Constructor) {
+        node.initializers.clear();
+        _clearFunction(node.function);
+      }
+      return node;
+    }
+  }
+
+  _clearFunction(FunctionNode function) {
+    function.body = null;
+    // TODO(sigmund): Fix directly the continuation transformer. The async/await
+    // continuation transformer fails if it finds a function with no body that
+    // it is marked with async/async*/sync*, we shouldn't be patching that here.
+    function.dartAsyncMarker = function.asyncMarker;
+    function.asyncMarker = AsyncMarker.Sync;
+  }
+
+  /// Types appear to be encoded directly, so we have no need to preserve
+  /// typedefs.
+  // TODO(sigmund): revisit if this is not the case, the `inputError` in the
+  // analysis step is meant to detect this.
+  Typedef visitTypedef(Typedef node) => null;
+
+  TreeNode defaultTreeNode(TreeNode node) => node;
+}
+
+typedef bool Filter(Uri uri);