| /* |
| * Copyright 2015 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.dev.jjs.ast.Context; |
| import com.google.gwt.dev.jjs.ast.JBlock; |
| import com.google.gwt.dev.jjs.ast.JFieldRef; |
| import com.google.gwt.dev.jjs.ast.JMethodBody; |
| import com.google.gwt.dev.jjs.ast.JProgram; |
| import com.google.gwt.dev.jjs.ast.JVariable; |
| import com.google.gwt.dev.jjs.ast.JVariableRef; |
| import com.google.gwt.dev.jjs.ast.JVisitor; |
| import com.google.gwt.thirdparty.guava.common.collect.LinkedHashMultimap; |
| import com.google.gwt.thirdparty.guava.common.collect.Maps; |
| import com.google.gwt.thirdparty.guava.common.collect.Multimap; |
| import com.google.gwt.thirdparty.guava.common.collect.Sets; |
| |
| import java.util.Collection; |
| import java.util.Map; |
| import java.util.Set; |
| |
| /** |
| * The GWT Java AST might contain different local variables with the same name in the same |
| * scope. This fixup pass renames variables in the case they clash in a scope. |
| */ |
| public class NameClashesFixer { |
| |
| private static class FixNameClashesVisitor extends JVisitor { |
| |
| /** |
| * Represents the scope tree defined by nested statement blocks. It is a temporary structure to |
| * track local variable lifetimes. |
| */ |
| private static class Scope { |
| private Scope parent; |
| |
| // Keeps track what names are used in children. |
| private Set<String> usedInChildScope = Sets.newHashSet(); |
| |
| // Keeps track what names have this scope as its lifetime. |
| private Set<String> namesInThisScope = Sets.newHashSet(); |
| |
| /** |
| * The depth at which this scope is in the tree. |
| */ |
| private int level; |
| |
| private Scope() { |
| this.parent = null; |
| this.level = 0; |
| } |
| |
| private Scope(Scope parent) { |
| this.parent = parent; |
| this.level = parent.level + 1; |
| } |
| |
| private static Scope getInnermostEnclosingScope(Scope thisScope, Scope thatScope) { |
| if (thisScope == null) { |
| return thatScope; |
| } |
| |
| if (thatScope == null) { |
| return thisScope; |
| } |
| |
| if (thisScope == thatScope) { |
| return thisScope; |
| } |
| |
| if (thisScope.level > thatScope.level) { |
| return getInnermostEnclosingScope(thatScope, thisScope); |
| } |
| |
| if (thisScope.level == thatScope.level) { |
| return getInnermostEnclosingScope(thisScope.parent, thatScope.parent); |
| } |
| return getInnermostEnclosingScope(thisScope, thatScope.parent); |
| } |
| |
| private void addChildUsage(String name) { |
| usedInChildScope.add(name); |
| if (parent != null) { |
| parent.addChildUsage(name); |
| } |
| } |
| |
| protected void addUsedName(String name) { |
| namesInThisScope.add(name); |
| if (parent != null) { |
| parent.addChildUsage(name); |
| } |
| } |
| |
| private boolean isUsedInParent(String name) { |
| return namesInThisScope.contains(name) || |
| (parent != null && parent.isUsedInParent(name)); |
| } |
| |
| protected boolean isConflictingName(String name) { |
| return usedInChildScope.contains(name) || isUsedInParent(name); |
| } |
| } |
| |
| private Scope currentScope; |
| private Map<JVariable, Scope> scopesByLocal; |
| private Multimap<String, JVariable> localsByName; |
| |
| @Override |
| public boolean visit(JMethodBody x, Context ctx) { |
| // Start constructing the scope tree. |
| currentScope = new Scope(); |
| scopesByLocal = Maps.newHashMap(); |
| localsByName = LinkedHashMultimap.create(); |
| return true; |
| } |
| |
| @Override |
| public boolean visit(JBlock x, Context ctx) { |
| currentScope = new Scope(currentScope); |
| return true; |
| } |
| |
| @Override |
| public void endVisit(JBlock x, Context ctx) { |
| currentScope = currentScope.parent; |
| } |
| |
| @Override |
| public void endVisit(JVariableRef x, Context ctx) { |
| // We use the a block scope as a proxy for a lifetime which is safe to do albeit non optimal. |
| // |
| // Keep track of the scope that encloses a variable lifetime. E.g. assume the following code. |
| // { // scope 1 |
| // { // scope 1.1 |
| // ... a... b... |
| // { // scope 1.1.1 |
| // ... a ... |
| // } |
| // } |
| // { // scope 1.2 |
| // ... b... |
| // } |
| // } |
| // Scope 1.1 is the innermost scope that encloses the lifetime of variable a and |
| // scope 1 is the innermost scope that encloses the lifetime of variable b. |
| if (x instanceof JFieldRef) { |
| // Skip fields as they are always qualified in JavaScript and their name resolution logic |
| // is in {@link CreateNameAndScopesVisitor}. |
| return; |
| } |
| JVariable local = x.getTarget(); |
| Scope oldVariableScope = scopesByLocal.get(local); |
| Scope newVariableScope = Scope.getInnermostEnclosingScope(oldVariableScope, currentScope); |
| newVariableScope.addUsedName(local.getName()); |
| if (newVariableScope != oldVariableScope) { |
| scopesByLocal.put(local, newVariableScope); |
| } |
| localsByName.put(local.getName(), local); |
| } |
| |
| @Override |
| public void endVisit(JMethodBody x, Context ctx) { |
| // Fix clashing variables here. Two locals are clashing if they have the same name and their |
| // computed lifetimes are intersecting. By using the scope to model lifetimes two variables |
| // clash if their computed scopes are nested. |
| for (String name : localsByName.keySet()) { |
| Collection<JVariable> localSet = localsByName.get(name); |
| if (localSet.size() == 1) { |
| continue; |
| } |
| |
| JVariable[] locals = localSet.toArray(new JVariable[localSet.size()]); |
| // TODO(rluble): remove n^2 behaviour in conflict checking. |
| // In practice each method has only a handful of locals so this process is not expected |
| // to be a performance problem. |
| for (int i = 0; i < locals.length; i++) { |
| // See if local i conflicts with any local j > i |
| for (int j = i + 1; j < locals.length; j++) { |
| Scope iLocalScope = scopesByLocal.get(locals[i]); |
| Scope jLocalScope = scopesByLocal.get(locals[j]); |
| Scope commonAncestor = Scope.getInnermostEnclosingScope(iLocalScope, jLocalScope); |
| if (commonAncestor != iLocalScope && commonAncestor != jLocalScope) { |
| // no conflict |
| continue; |
| } |
| // conflicting locals => find a unique name rename local i to it; |
| int n = 0; |
| String baseName = locals[i].getName(); |
| String newName; |
| do { |
| // The active namer will clean up these potentially long names. |
| newName = baseName + n++; |
| } while (iLocalScope.isConflictingName(newName)); |
| locals[i].setName(newName); |
| iLocalScope.addUsedName(newName); |
| // There is no need to update the localsByNameMap as newNames are always guaranteed to |
| // be clash free. |
| break; |
| } |
| } |
| } |
| |
| // Only valid for the duration of one method body visit/endVisit pair. |
| currentScope = null; |
| scopesByLocal = null; |
| localsByName = null; |
| } |
| } |
| |
| public static void exec(JProgram program) { |
| new FixNameClashesVisitor().accept(program); |
| } |
| private NameClashesFixer() { |
| } |
| } |