JS tree shaking for incremental builds.

compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java

Index: compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java
diff --git a/compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java b/compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java
new file mode 100644
index 0000000000000000000000000000000000000000..3aeccc6d094f9c2a360cb82ff3d1983c02f01e28
--- /dev/null
+++ b/compiler/java/com/google/dart/compiler/backend/js/analysis/TreeShaker.java
@@ -0,0 +1,181 @@
+// Copyright (c) 2011, 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.
+
+package com.google.dart.compiler.backend.js.analysis;
+
+import com.google.common.io.CharStreams;
+
+import org.mozilla.javascript.EvaluatorException;
+import org.mozilla.javascript.Parser;
+import org.mozilla.javascript.ast.AstNode;
+import org.mozilla.javascript.ast.AstRoot;
+import org.mozilla.javascript.ast.NodeVisitor;
+
+import java.io.IOException;
+import java.io.Reader;
+import java.io.Writer;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * A JavaScript tree shaker that is specialized for the output produced by dartc.
+ */
+public class TreeShaker {
+  private static class VisitorIOException extends RuntimeException {
+    public VisitorIOException(IOException e) {
+      super(e);
+    }
+    
+    @Override
+    public IOException getCause() {
+      return (IOException) super.getCause();
+    }
+  }
+  
+  private static final class OutputFileWriter implements NodeVisitor {
+    private final Set<AstNode> nodesProcessed;
+    private final Writer outputFile;
+    private final Reader inputFile;
+    private long currentPosition = 0;
+    private long outputSize = 0;
+
+    private OutputFileWriter(Set<AstNode> nodesProcessed, Writer outputFile, Reader inputFile) {

[zundel, 2011/11/30 15:09:57]

maybe a better name for nodesProcessed is nodesToEmit?

[mmendez, 2011/12/01 21:31:30]

Done.

[zundel, 2011/12/02 12:33:43]

FYI - you didn't actually change it

[mmendez, 2011/12/02 13:26:52]

Sorry, I lost that delta when I rolled back some experiments yesterday.


On 2011/12/02 12:33:43, zundel wrote:

+      this.nodesProcessed = nodesProcessed;
+      this.outputFile = outputFile;
+      this.inputFile = inputFile;
+    }
+
+    @Override
+    public boolean visit(AstNode node) {
+      if (node.getAstRoot() == node) {
+        return true;
+      }
+
+      try {
+        int nodePosition = node.getAbsolutePosition();
+        inputFile.skip(nodePosition - currentPosition);
+
+        if (nodesProcessed.contains(node)) {
+          char[] buffer = new char[node.getLength()];
+          int charsRead = inputFile.read(buffer);
+          assert (charsRead == buffer.length);
+          outputFile.write(buffer);
+          outputFile.write("\n");
+          outputSize += charsRead + 1;
+        } else {
+          inputFile.skip(node.getLength());

[zundel, 2011/11/30 15:09:57]

Why not just set currentPostion only after reading the file?  Then the
inputFile.skip() at the top of the try block handles this case.

[mmendez, 2011/12/01 21:31:30]

Done.

+        }
+
+        currentPosition = nodePosition + node.getLength();
+
+      } catch (IOException e) {
+        throw new VisitorIOException(e);
+      }
+
+      return false;
+    }
+    
+    public long getOutputSize() {
+      return outputSize;
+    }
+  }
+
+  private static final boolean DEBUG = false;
+
+  /**
+   * Returns the set of {@link AstNode}s that should be emitted into the final JS code. 
+   */
+  private static Set<AstNode> computeNodesToEmit(AstRoot root) {
+    List<AstNode> globals = new ArrayList<AstNode>();
+    Map<String, List<JavascriptElement>> namesToElements =
+        new HashMap<String, List<JavascriptElement>>();
+    TopLevelElementIndexer declVisitor = new TopLevelElementIndexer(namesToElements, globals);
+    root.visit(declVisitor);
+
+    if (DEBUG) {
+      TopLevelElementIndexer.printNamesToElements(namesToElements);
+      TopLevelElementIndexer.printGlobals(globals);
+    }
+
+    List<AstNode> worklist = new ArrayList<AstNode>();
+    for (AstNode global : globals) {
+      worklist.add(global);
+    }
+
+    worklist.addAll(declVisitor.getEntryPoints());

[codefu, 2011/11/30 23:43:33]

aren't entry points technically global?

[mmendez, 2011/12/01 21:31:30]

They are global but we treat them as roots that seed the worklist.

On 2011/11/30 23:43:33, codefu wrote:

+    DependencyComputer dependencyComputer = new DependencyComputer(namesToElements);
+    final Set<AstNode> nodesProcessed = new LinkedHashSet<AstNode>();
+    while (!worklist.isEmpty()) {
+      AstNode node = worklist.remove(worklist.size() - 1);
+      if (!nodesProcessed.add(node)) {
+        continue;
+      }
+
+      if (DEBUG) {
+        try {
+          System.out.println(node.toSource());
+          System.out.println("Dependencies:");
+        } catch (Exception e) {
+          // Ignore exceptions thrown by rhino's toSource method...
+        }
+      }
+      
+      List<JavascriptElement> dependencies = dependencyComputer.computeDependencies(node);
+      for (JavascriptElement dependency : dependencies) {
+        if (dependency.isNative() || nodesProcessed.contains(dependency.getNode())) {
+          // Skip natives since they don't have a node in the AST
+          continue;
+        }
+
+        if (DEBUG) {
+          System.out.println("\t" + dependency.getQualifiedName());
+        }
+
+        worklist.add(dependency.getNode());
+      }
+    }
+    return nodesProcessed;
+  }
+
+  /**
+   * Reduce the input JS file by following the conservative "call graph" and pruning dead code.
+   */
+  public static long reduce(final Reader inputFile, final Writer outputFile, long fileSize)
+      throws IOException {
+    // Mark beyond the expected length so we can reset back to zero
+    inputFile.mark((int) (fileSize + 16));

[zundel, 2011/11/30 15:09:57]

FYI: From reading the BufferedReader source, I'm pretty sure this causes the
entire file to be cached in memory.   I don't have any good suggestions on how
to prevent it, other than modifying the ArtifactProvider to return you an actual
File object so you can create a second reader from scratch for the second pass.

If you wanted to go a middle route, you could just have your computeNodesToEmit
save the node text to emit as it encounters it in the parse.  You'd still be
storing lots of data in memory, but not as much as the entire file.

[mmendez, 2011/12/01 21:31:30]

It will.  The research version of this code bypassed the whole artifact provider
and didn't suffer from this problem.  

Rather than tweak the artifcat provider API at this point, I'll just pass the
app and context the code will call back to get the Readers.
On 2011/11/30 15:09:57, zundel wrote:

+
+    AstRoot root = null;
+    try {
+      Parser parser = new Parser();
+      root = parser.parse(inputFile, "", 1);
+    } catch (EvaluatorException e) {
+      /*
+       * This can happen if we generate bad JS code. For example, the negative
+       * tests may cause invalid control flow constructs to be generated. In
+       * this case we will swallow the exception and simply copy the input file
+       * to the output file.
+       */
+      inputFile.reset();
+      CharStreams.copy(inputFile, outputFile);
+      return fileSize;
+    }
+
+    final Set<AstNode> nodesProcessed = computeNodesToEmit(root);
+
+    inputFile.reset();
+
+    OutputFileWriter outputFileWriter = new OutputFileWriter(nodesProcessed, outputFile, inputFile);
+    try {
+      root.visit(outputFileWriter);
+      return outputFileWriter.getOutputSize();
+    } catch (VisitorIOException e) {
+      throw e.getCause();
+    }
+  }
+}