-
Notifications
You must be signed in to change notification settings - Fork 1.1k
/
ShadowVariables.java
329 lines (289 loc) · 11.5 KB
/
ShadowVariables.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
/*
* Copyright 2011 The Closure Compiler Authors.
*
* 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.javascript.jscomp;
import com.google.common.collect.HashMultimap;
import com.google.common.collect.Multimap;
import com.google.javascript.jscomp.NodeTraversal.AbstractPostOrderCallback;
import com.google.javascript.jscomp.NodeTraversal.ScopedCallback;
import com.google.javascript.jscomp.RenameVars.Assignment;
import com.google.javascript.rhino.Node;
import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.SortedSet;
/**
* Tries to compute a list of variables that can shadow a variable in the
* outer scope.
*
* For example:
*
* <code>
* var a = function() {
* var b = getB();
* b();
* return function(y) {};
* };
* </code>
*
* Normally, b would be mapped to variable L0, y would be L1.
*
* Instead we are going to make y shadows L0 in hope of using less variables
* and reusing frequently used local names.
*
*/
class ShadowVariables implements CompilerPass {
// Keep a map of Upward Referencing name nodes of each scope.
// A name is upward referencing name of a scope if:
//
// 1) It refers to (or defines) a name that is defined in the current
// scope or any scope above the current scope that isn't the
// global scope.
//
// 2) It is a upward referencing name of a child scope of this scope.
//
// Example:
// var x; var y; function foo(a) { function bar(b) { x, a } }
// The upward referencing names in scope 'foo' is bar, b, x and a;
// The key to this map is the root node of the scope.
//
// We can see that for any variable x in the current scope, we can shadow
// a variable y in an outer scope given that y is not a upward referencing
// name of the current scope.
// TODO(user): Maps scope to string instead of Node to string.
// Make sure of scope memorization to minimize scope creation cost.
private final Multimap<Node, String> scopeUpRefMap = HashMultimap.create();
// Maps each local variable to all of its referencing NAME nodes in any scope.
private final Multimap<Var, Reference> varToNameUsage = HashMultimap.create();
private final AbstractCompiler compiler;
// All the information used for renaming.
private final SortedSet<Assignment> varsByFrequency;
private final Map<String, Assignment> assignments;
private final Map<Node, String> oldPseudoNameMap;
private final Map<Node, String> deltaPseudoNameMap;
/**
* @param assignments Map of old variable names to its assignment Objects.
* @param varsByFrequency Sorted variable assignments by Frequency.
* @param pseudoNameMap The current pseudo name map so this pass can update
* it accordingly.
*/
ShadowVariables(
AbstractCompiler compiler,
Map<String, Assignment> assignments,
SortedSet<Assignment> varsByFrequency,
Map<Node, String> pseudoNameMap) {
this.compiler = compiler;
this.assignments = assignments;
this.varsByFrequency = varsByFrequency;
this.oldPseudoNameMap = pseudoNameMap;
this.deltaPseudoNameMap = new LinkedHashMap<>();
}
@Override
public void process(Node externs, Node root) {
// The algorithm is divided into two stages:
//
// 1. Information gathering (variable usage, upward referencing)
//
// 2. Tries to find shadows for each variables, updates the
// variable usage frequency map.
//
// 3. Updates the pseudo naming map if needed.
NodeTraversal.traverseEs6(compiler, root, new GatherReferenceInfo());
NodeTraversal.traverseEs6(compiler, root, new DoShadowVariables());
if (oldPseudoNameMap != null) {
oldPseudoNameMap.putAll(deltaPseudoNameMap);
}
}
private class GatherReferenceInfo extends AbstractPostOrderCallback {
@Override
public void visit(NodeTraversal t, Node n, Node parent) {
// Skipping over non-name nodes and empty function names.
if (!NodeUtil.isReferenceName(n)) {
return;
}
// We focus on shadowing local variables as their name occurs much more
// than global names.
// TODO(user): Alternatively, we could experiment with using a local
// name to shadow a global variable.
if (t.inGlobalScope()) {
return;
}
Scope scope = t.getScope();
Var var = scope.getVar(n.getString());
if (var == null) {
// extern name or undefined name.
return;
}
if (var.getScope().isGlobal()) {
// We will not shadow a global variable name.
return;
}
// Using the definition of upward referencing, fill in the map.
if (var.getScope() != scope) {
for (Scope s = scope; s != var.getScope() && s.isLocal(); s = s.getParent()) {
scopeUpRefMap.put(s.getRootNode(), var.name);
}
} else {
scopeUpRefMap.put(t.getScopeRoot(), var.name);
}
// Make sure that we don't shadow function parameters or function names from a function block
// scope, eg.:
// function f(a) { ... var a; ... } // Unsafe
if (scope.isFunctionScope() && var.getScope() == scope) {
scopeUpRefMap.put(scope.getRootNode().getLastChild(), var.name);
}
// Find in the usage map that tracks a var and all of its usage.
varToNameUsage.put(var, new Reference(n, scope));
}
}
private class DoShadowVariables extends AbstractPostOrderCallback
implements ScopedCallback {
@Override
public void enterScope(NodeTraversal t) {
if (t.inGlobalScope()) {
return;
}
// Since we don't shadow global, there is nothing to be done in the
// first immediate local scope as well.
Node scopeRoot = t.getScopeRoot();
if ((scopeRoot.isFunction()
&& NodeUtil.getEnclosingFunction(scopeRoot.getParent()) == null)
|| (NodeUtil.isFunctionBlock(scopeRoot)
&& NodeUtil.getEnclosingFunction(scopeRoot.getGrandparent()) == null)) {
return;
}
Scope s = t.getScope();
for (Var var : s.getVarIterable()) {
// Don't shadow variables that are bleed-out functions or caught exceptions to workaround
// IE8 bugs.
// TODO(moz): Gate this behind languageMode=ES3.
if (var.isBleedingFunction() || var.isCatch()) {
continue;
}
// Don't shadow an exported local.
if (compiler.getCodingConvention().isExported(var.name, s.isLocal())) {
continue;
}
// The name assignment being shadowed.
Assignment localAssignment = assignments.get(var.getName());
if (localAssignment == null) {
continue;
}
// Try to run this check last as it is more expensive than the above checks.
// Try to look for the best shadow for the current candidate.
Assignment bestShadow = findBestShadow(s, var);
if (bestShadow == null) {
continue;
}
// Only shadow if this increases the number of occurrences of the
// shadowed variable.
if (bestShadow.count < localAssignment.count) {
continue; // Hope the next local variable would have a smaller count.
}
doShadow(localAssignment, bestShadow, var);
if (oldPseudoNameMap != null) {
String targetPseudoName =
oldPseudoNameMap.get(s.getVar(bestShadow.oldName).nameNode);
for (Reference use : varToNameUsage.get(var)) {
deltaPseudoNameMap.put(use.nameNode, targetPseudoName);
}
}
}
}
@Override
public void exitScope(NodeTraversal t) {}
@Override
public void visit(NodeTraversal t, Node n, Node parent) {}
/**
* @return An assignment that can be used as a shadow for a local variable
* in the scope defined by curScopeRoot.
*/
private Assignment findBestShadow(Scope curScope, Var var) {
// Search for the candidate starting from the most used local.
for (Assignment assignment : varsByFrequency) {
if (assignment.isLocal) {
if (!scopeUpRefMap.containsEntry(curScope.getRootNode(), assignment.oldName)) {
if (curScope.isDeclared(assignment.oldName, true)) {
// Don't shadow if the scopes are the same eg.:
// function f() { var a = 1; { var a = 2; } } // Unsafe
Var toShadow = curScope.getVar(assignment.oldName);
if (var.getScope() != toShadow.getScope()) {
return assignment;
}
}
}
}
}
return null;
}
private void doShadow(Assignment original, Assignment toShadow, Var var) {
Scope s = var.getScope();
// We are now shadowing 'bestShadow' with localAssignment.
// All of the reference NAME node of this variable.
Collection<Reference> references = varToNameUsage.get(var);
// First remove both assignments from the sorted list since they need
// to be re-sorted.
varsByFrequency.remove(original);
varsByFrequency.remove(toShadow);
// Adjust the count offset by the inner scope variable.
original.count -= references.size();
toShadow.count += references.size();
// Add it back to the sorted list after re-adjustment.
varsByFrequency.add(original);
varsByFrequency.add(toShadow);
// This is an important step. If variable L7 is going to be renamed to
// L1, by definition of upward referencing, The name L1 is now in the
// set of upward referencing names of the current scope up to the
// declaring scope of the best shadow variable.
Var shadowed = s.getVar(toShadow.oldName);
if (shadowed != null) {
if (s.isFunctionScope() && s.getRootNode().getLastChild().isNormalBlock()) {
scopeUpRefMap.put(s.getRootNode().getLastChild(), toShadow.oldName);
scopeUpRefMap.remove(s.getRootNode().getLastChild(), original.oldName);
}
for (Scope curScope = s; curScope != shadowed.scope; curScope = curScope.getParent()) {
scopeUpRefMap.put(curScope.getRootNode(), toShadow.oldName);
scopeUpRefMap.remove(curScope.getRootNode(), original.oldName);
}
}
// Mark all the references as shadowed.
for (Reference ref : references) {
Node n = ref.nameNode;
n.setString(toShadow.oldName);
if (ref.scope.getRootNode() == s.getRootNode()) {
if (var.getNameNode() != ref.nameNode) {
scopeUpRefMap.put(s.getRootNode(), toShadow.oldName);
scopeUpRefMap.remove(s.getRootNode(), original.oldName);
}
} else {
for (Scope curScope = ref.scope;
curScope.getRootNode() != s.getRootNode();
curScope = curScope.getParent()) {
scopeUpRefMap.put(curScope.getRootNode(), toShadow.oldName);
scopeUpRefMap.remove(curScope.getRootNode(), original.oldName);
}
}
}
}
}
private static final class Reference {
private final Node nameNode;
private final Scope scope;
private Reference(Node nameNode, Scope scope) {
this.nameNode = nameNode;
this.scope = scope;
}
}
}