| /* |
| * Copyright 2009 Google Inc. |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); you may not |
| * use this file except in compliance with the License. You may obtain a copy of |
| * the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT |
| * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the |
| * License for the specific language governing permissions and limitations under |
| * the License. |
| */ |
| package com.google.gwt.dev.jjs.impl; |
| |
| import com.google.gwt.core.ext.soyc.Range; |
| import com.google.gwt.dev.jjs.JsSourceMap; |
| import com.google.gwt.dev.util.editdistance.GeneralEditDistance; |
| import com.google.gwt.dev.util.editdistance.GeneralEditDistances; |
| import com.google.gwt.thirdparty.guava.common.collect.Lists; |
| |
| import java.util.ArrayList; |
| import java.util.Arrays; |
| import java.util.Collections; |
| import java.util.Comparator; |
| import java.util.HashMap; |
| import java.util.LinkedList; |
| import java.util.List; |
| import java.util.Map; |
| import java.util.regex.Pattern; |
| |
| /** |
| * Re-orders function declarations according to a given metric and clustering |
| * algorithm in order to boost gzip/deflation compression efficiency. This |
| * version uses the edit-distance algorithm as a metric, and a semi-greedy |
| * strategy for grouping functions together. |
| */ |
| public class JsFunctionClusterer extends JsAbstractTextTransformer { |
| |
| /** |
| * Used by isFunctionDeclaration to check a statement is a function |
| * declaration or not. This should match standard declarations, such as |
| * "function a() { ... }" and "jslink.a=function() { ... }". The latter form |
| * is typically emitted by the cross-site linker. |
| */ |
| private static final Pattern functionDeclarationPattern = Pattern |
| .compile("function |[a-zA-Z][.$_a-zA-Z0-9]*=function"); |
| |
| /** |
| * Functions which have an edit-distance greater than this limit are |
| * considered equally different. |
| */ |
| private static final int MAX_DISTANCE_LIMIT = 100; |
| |
| /** |
| * Maximum number of functions to search for minimal edit-distance before |
| * giving up. |
| */ |
| private static final int SEARCH_LIMIT = 10; |
| |
| /** |
| * Tells whether a statement is a function declaration or not. |
| */ |
| private static boolean isFunctionDeclaration(String code) { |
| return functionDeclarationPattern.matcher(code).lookingAt(); |
| } |
| |
| /** |
| * Number of function declarations found. |
| */ |
| private int numFunctions; |
| |
| /** |
| * The statement indices after clustering. The element at index j represents |
| * the index of the statement in the original code that is moved to index j |
| * in the new code after clustering. |
| */ |
| private int[] reorderedIndices; |
| |
| public JsFunctionClusterer(JsAbstractTextTransformer xformer) { |
| super(xformer); |
| } |
| |
| @Override |
| public void exec() { |
| LinkedList<Integer> functionIndices = new LinkedList<Integer>(); |
| |
| // gather up all of the indices of function decl statements |
| for (int i = 0; i < statementRanges.numStatements(); i++) { |
| String code = getJsForRange(i); |
| if (isFunctionDeclaration(code)) { |
| functionIndices.add(i); |
| } |
| } |
| |
| numFunctions = functionIndices.size(); |
| |
| if (functionIndices.size() < 2) { |
| // No need to sort 0 or 1 functions. |
| return; |
| } |
| |
| // sort the indices according to size of statement range |
| Collections.sort(functionIndices, new Comparator<Integer>() { |
| @Override |
| public int compare(Integer index1, Integer index2) { |
| return stmtSize(index1) - (stmtSize(index2)); |
| } |
| }); |
| |
| // used to hold the new output order |
| int[] clusteredIndices = new int[functionIndices.size()]; |
| int currentFunction = 0; |
| |
| // remove the first function and stick it in the output array |
| clusteredIndices[currentFunction] = functionIndices.get(0); |
| functionIndices.remove(0); |
| while (!functionIndices.isEmpty()) { |
| // get the last outputted function to match against |
| String currentCode = getJsForRange(clusteredIndices[currentFunction]); |
| final GeneralEditDistance editDistance = |
| GeneralEditDistances.getLevenshteinDistance(currentCode); |
| |
| int bestIndex = 0; |
| int bestFunction = functionIndices.getFirst(); |
| int bestDistance = MAX_DISTANCE_LIMIT; |
| |
| int count = 0; |
| for (int functionIndex : functionIndices) { |
| if (count >= SEARCH_LIMIT) { |
| break; |
| } |
| String testCode = getJsForRange(functionIndex); |
| int dist = editDistance.getDistance(testCode, bestDistance); |
| if (dist < bestDistance) { |
| bestDistance = dist; |
| bestIndex = count; |
| bestFunction = functionIndex; |
| } |
| count++; |
| } |
| // output the best match and remove it from worklist of functions |
| currentFunction++; |
| clusteredIndices[currentFunction] = bestFunction; |
| functionIndices.remove(bestIndex); |
| } |
| |
| reorderedIndices = Arrays.copyOf(clusteredIndices, statementRanges.numStatements()); |
| recomputeJsAndStatementRanges(clusteredIndices); |
| } |
| |
| @Override |
| protected void endStatements(StringBuilder newJs, ArrayList<Integer> starts, |
| ArrayList<Integer> ends) { |
| int j = numFunctions; |
| // Then output everything else that is not a function. |
| for (int i = 0; i < statementRanges.numStatements(); i++) { |
| String code = getJsForRange(i); |
| if (!isFunctionDeclaration(code)) { |
| addStatement(j, code, newJs, starts, ends); |
| reorderedIndices[j] = i; |
| j++; |
| } |
| } |
| super.endStatements(newJs, starts, ends); |
| } |
| |
| /** |
| * Fixes the index ranges of individual expressions in the generated |
| * JS after function clustering has reordered statements. Loops over |
| * each expression, determines which statement it falls in, and shifts |
| * the indices according to where that statement moved. |
| */ |
| @Override |
| protected void updateSourceInfoMap() { |
| if (sourceInfoMap != null) { |
| // create mapping of statement ranges |
| Map<Range, Range> statementShifts = new HashMap<Range, Range>(); |
| for (int j = 0; j < statementRanges.numStatements(); j++) { |
| int permutedStart = statementRanges.start(j); |
| int permutedEnd = statementRanges.end(j); |
| int originalStart = originalStatementRanges.start(reorderedIndices[j]); |
| int originalEnd = originalStatementRanges.end(reorderedIndices[j]); |
| |
| statementShifts.put(new Range(originalStart, originalEnd), |
| new Range(permutedStart, permutedEnd)); |
| } |
| |
| Range[] oldStatementRanges = statementShifts.keySet().toArray(new Range[0]); |
| Arrays.sort(oldStatementRanges, Range.SOURCE_ORDER_COMPARATOR); |
| |
| List<Range> oldExpressionRanges = Lists.newArrayList(sourceInfoMap.getRanges()); |
| Collections.sort(oldExpressionRanges, Range.SOURCE_ORDER_COMPARATOR); |
| |
| // iterate over expression ranges and shift |
| List<Range> updatedRanges = Lists.newArrayList(); |
| Range entireProgram = |
| new Range(0, oldStatementRanges[oldStatementRanges.length - 1].getEnd()); |
| for (int i = 0, j = 0; j < oldExpressionRanges.size(); j++) { |
| Range oldExpression = oldExpressionRanges.get(j); |
| if (oldExpression.equals(entireProgram)) { |
| updatedRanges.add(oldExpression); |
| continue; |
| } |
| |
| Range oldStatement = oldStatementRanges[i]; |
| Range newStatement = statementShifts.get(oldStatement); |
| int shift = newStatement.getStart() - oldStatement.getStart(); |
| |
| Range oldExpressionRange = oldExpressionRanges.get(j); |
| Range newExpressionRange = new Range(oldExpressionRange.getStart() + shift, |
| oldExpressionRange.getEnd() + shift, oldExpressionRange.getSourceInfo()); |
| updatedRanges.add(newExpressionRange); |
| } |
| |
| sourceInfoMap = |
| new JsSourceMap(updatedRanges, sourceInfoMap.getBytes(), sourceInfoMap.getLines()); |
| } |
| } |
| |
| private int stmtSize(int index1) { |
| return statementRanges.end(index1) - statementRanges.start(index1); |
| } |
| } |