Skip to content

Commit d9e01d4

Browse files
sokrasokra
committed
use more efficient data structures
Parser.definitions and Parser.renames are using Maps now
1 parent 0110035 commit d9e01d4

5 files changed

Lines changed: 141 additions & 50 deletions

File tree

‎lib/Parser.js‎

Lines changed: 134 additions & 43 deletions
Original file line numberDiff line numberDiff line change
@@ -6,6 +6,7 @@
66

77
// Syntax: https://developer.mozilla.org/en/SpiderMonkey/Parser_API
88

9+
const util = require("util");
910
const acorn = require("acorn-dynamic-import").default;
1011
const Tapable = require("tapable");
1112
const json5 = require("json5");
@@ -37,6 +38,92 @@ const POSSIBLE_AST_OPTIONS = [{
3738
}
3839
}];
3940

41+
class StackedSetMap {
42+
constructor(defaultValue, parentStack) {
43+
this.defaultValue = defaultValue;
44+
this.stack = parentStack === undefined ? [] : parentStack.slice();
45+
this.map = new Map();
46+
this.stack.push(this.map);
47+
}
48+
49+
add(item) {
50+
this.map.set(item, true);
51+
}
52+
53+
set(item, value) {
54+
this.map.set(item, value);
55+
}
56+
57+
delete(item) {
58+
this.map.set(item, false);
59+
}
60+
61+
has(item) {
62+
return this.get(item, false);
63+
}
64+
65+
get(item) {
66+
const topValue = this.map.get(item);
67+
if(typeof topValue !== "undefined")
68+
return topValue;
69+
for(var i = this.stack.length - 2; i >= 0; i--) {
70+
const value = this.stack[i].get(item);
71+
if(typeof value !== "undefined") {
72+
this.map.set(item, value);
73+
return value;
74+
}
75+
}
76+
this.map.set(item, this.defaultValue);
77+
return this.defaultValue;
78+
}
79+
80+
createChild() {
81+
return new StackedSetMap(this.defaultValue, this.stack);
82+
}
83+
84+
get length() {
85+
throw new Error("Parser.definitions is no longer an Array");
86+
}
87+
88+
set length(value) {
89+
throw new Error("Parser.definitions is no longer an Array");
90+
}
91+
}
92+
93+
StackedSetMap.prototype.push = util.deprecate(function(item) {
94+
this.add(item);
95+
}, "Parser.definitions is no longer an Array: Use add instead.");
96+
97+
class TrackingSet {
98+
constructor(set) {
99+
this.set = set;
100+
this.set2 = new Set();
101+
this.stack = set.stack;
102+
}
103+
104+
add(item) {
105+
this.set2.add(item);
106+
return this.set.add(item);
107+
}
108+
109+
delete(item) {
110+
this.set2.delete(item);
111+
return this.set.delete(item);
112+
}
113+
114+
has(item) {
115+
return this.set.has(item);
116+
}
117+
118+
createChild() {
119+
return this.set.createChild();
120+
}
121+
122+
getAddedItems() {
123+
return this.set2;
124+
}
125+
}
126+
40127
class Parser extends Tapable {
41128
constructor(options) {
42129
super();
@@ -207,8 +294,8 @@ class Parser extends Tapable {
207294
let res;
208295
let name;
209296
if(expr.argument.type === "Identifier") {
210-
name = this.scope.renames["$" + expr.argument.name] || expr.argument.name;
211-
if(this.scope.definitions.indexOf(name) === -1) {
297+
name = this.scope.renames.get(expr.argument.name) || expr.argument.name;
298+
if(!this.scope.definitions.has(name)) {
212299
res = this.applyPluginsBailResult1("evaluate typeof " + name, expr);
213300
if(res !== undefined) return res;
214301
}
@@ -248,8 +335,8 @@ class Parser extends Tapable {
248335
return new BasicEvaluatedExpression().setString("undefined").setRange(expr.range);
249336
});
250337
this.plugin("evaluate Identifier", function(expr) {
251-
const name = this.scope.renames["$" + expr.name] || expr.name;
252-
if(this.scope.definitions.indexOf(expr.name) === -1) {
338+
const name = this.scope.renames.get(expr.name) || expr.name;
339+
if(!this.scope.definitions.has(expr.name)) {
253340
const result = this.applyPluginsBailResult1("evaluate Identifier " + name, expr);
254341
if(result) return result;
255342
return new BasicEvaluatedExpression().setIdentifier(name).setRange(expr.range);
@@ -258,7 +345,7 @@ class Parser extends Tapable {
258345
}
259346
});
260347
this.plugin("evaluate ThisExpression", function(expr) {
261-
const name = this.scope.renames.$this;
348+
const name = this.scope.renames.get("this");
262349
if(name) {
263350
const result = this.applyPluginsBailResult1("evaluate Identifier " + name, expr);
264351
if(result) return result;
@@ -625,8 +712,8 @@ class Parser extends Tapable {
625712
// Declarations
626713
prewalkFunctionDeclaration(statement) {
627714
if(statement.id) {
628-
this.scope.renames["$" + statement.id.name] = undefined;
629-
this.scope.definitions.push(statement.id.name);
715+
this.scope.renames.set(statement.id.name, null);
716+
this.scope.definitions.add(statement.id.name);
630717
}
631718
}
632719

@@ -649,8 +736,8 @@ class Parser extends Tapable {
649736
this.applyPluginsBailResult("import", statement, source);
650737
statement.specifiers.forEach(function(specifier) {
651738
const name = specifier.local.name;
652-
this.scope.renames["$" + name] = undefined;
653-
this.scope.definitions.push(name);
739+
this.scope.renames.set(name, null);
740+
this.scope.definitions.add(name);
654741
switch(specifier.type) {
655742
case "ImportDefaultSpecifier":
656743
this.applyPluginsBailResult("import specifier", statement, source, "default", name);
@@ -678,9 +765,12 @@ class Parser extends Tapable {
678765
throw new Error("Doesn't occur?");
679766
} else {
680767
if(!this.applyPluginsBailResult("export declaration", statement, statement.declaration)) {
681-
const pos = this.scope.definitions.length;
768+
const originalDefinitions = this.scope.definitions;
769+
const tracker = new TrackingSet(this.scope.definitions);
770+
this.scope.definitions = tracker;
682771
this.prewalkStatement(statement.declaration);
683-
const newDefs = this.scope.definitions.slice(pos);
772+
const newDefs = Array.from(tracker.getAddedItems());
773+
this.scope.definitions = originalDefinitions;
684774
for(let index = newDefs.length - 1; index >= 0; index--) {
685775
const def = newDefs[index];
686776
this.applyPluginsBailResult("export specifier", statement, def, def, index);
@@ -714,9 +804,12 @@ class Parser extends Tapable {
714804

715805
prewalkExportDefaultDeclaration(statement) {
716806
if(/Declaration$/.test(statement.declaration.type)) {
717-
const pos = this.scope.definitions.length;
807+
const originalDefinitions = this.scope.definitions;
808+
const tracker = new TrackingSet(this.scope.definitions);
809+
this.scope.definitions = tracker;
718810
this.prewalkStatement(statement.declaration);
719-
const newDefs = this.scope.definitions.slice(pos);
811+
const newDefs = Array.from(tracker.getAddedItems());
812+
this.scope.definitions = originalDefinitions;
720813
for(let index = 0, len = newDefs.length; index < len; index++) {
721814
const def = newDefs[index];
722815
this.applyPluginsBailResult("export specifier", statement, def, "default");
@@ -756,8 +849,8 @@ class Parser extends Tapable {
756849

757850
prewalkClassDeclaration(statement) {
758851
if(statement.id) {
759-
this.scope.renames["$" + statement.id.name] = undefined;
760-
this.scope.definitions.push(statement.id.name);
852+
this.scope.renames.set(statement.id.name, null);
853+
this.scope.definitions.add(statement.id.name);
761854
}
762855
}
763856

@@ -798,9 +891,8 @@ class Parser extends Tapable {
798891
this.enterPattern(declarator.id, (name, decl) => {
799892
if(!this.applyPluginsBailResult1("var-" + declarator.kind + " " + name, decl)) {
800893
if(!this.applyPluginsBailResult1("var " + name, decl)) {
801-
this.scope.renames["$" + name] = undefined;
802-
if(this.scope.definitions.indexOf(name) < 0)
803-
this.scope.definitions.push(name);
894+
this.scope.renames.set(name, null);
895+
this.scope.definitions.add(name);
804896
}
805897
}
806898
});
@@ -819,9 +911,8 @@ class Parser extends Tapable {
819911
if(renameIdentifier && declarator.id.type === "Identifier" && this.applyPluginsBailResult1("can-rename " + renameIdentifier, declarator.init)) {
820912
// renaming with "var a = b;"
821913
if(!this.applyPluginsBailResult1("rename " + renameIdentifier, declarator.init)) {
822-
this.scope.renames["$" + declarator.id.name] = this.scope.renames["$" + renameIdentifier] || renameIdentifier;
823-
const idx = this.scope.definitions.indexOf(declarator.id.name);
824-
if(idx >= 0) this.scope.definitions.splice(idx, 1);
914+
this.scope.renames.set(declarator.id.name, this.scope.renames.get(renameIdentifier) || renameIdentifier);
915+
this.scope.definitions.delete(declarator.id.name);
825916
}
826917
} else {
827918
this.walkPattern(declarator.id);
@@ -979,23 +1070,22 @@ class Parser extends Tapable {
9791070
if(expression.left.type === "Identifier" && renameIdentifier && this.applyPluginsBailResult1("can-rename " + renameIdentifier, expression.right)) {
9801071
// renaming "a = b;"
9811072
if(!this.applyPluginsBailResult1("rename " + renameIdentifier, expression.right)) {
982-
this.scope.renames["$" + expression.left.name] = renameIdentifier;
983-
const idx = this.scope.definitions.indexOf(expression.left.name);
984-
if(idx >= 0) this.scope.definitions.splice(idx, 1);
1073+
this.scope.renames.set(expression.left.name, renameIdentifier);
1074+
this.scope.definitions.delete(expression.left.name);
9851075
}
9861076
} else if(expression.left.type === "Identifier") {
9871077
if(!this.applyPluginsBailResult1("assigned " + expression.left.name, expression)) {
9881078
this.walkExpression(expression.right);
9891079
}
990-
this.scope.renames["$" + expression.left.name] = undefined;
1080+
this.scope.renames.set(expression.left.name, null);
9911081
if(!this.applyPluginsBailResult1("assign " + expression.left.name, expression)) {
9921082
this.walkExpression(expression.left);
9931083
}
9941084
} else {
9951085
this.walkExpression(expression.right);
9961086
this.walkPattern(expression.left);
9971087
this.enterPattern(expression.left, (name, decl) => {
998-
this.scope.renames["$" + name] = undefined;
1088+
this.scope.renames.set(name, null);
9991089
});
10001090
}
10011091
}
@@ -1061,13 +1151,13 @@ class Parser extends Tapable {
10611151
return !args[idx];
10621152
}), () => {
10631153
if(renameThis) {
1064-
this.scope.renames.$this = renameThis;
1154+
this.scope.renames.set("this", renameThis);
10651155
}
10661156
for(let i = 0; i < args.length; i++) {
10671157
const param = args[i];
10681158
if(!param) continue;
10691159
if(!params[i] || params[i].type !== "Identifier") continue;
1070-
this.scope.renames["$" + params[i].name] = param;
1160+
this.scope.renames.set(params[i].name, param);
10711161
}
10721162
if(functionExpression.body.type === "BlockStatement") {
10731163
this.prewalkStatement(functionExpression.body);
@@ -1079,7 +1169,7 @@ class Parser extends Tapable {
10791169
if(expression.callee.type === "MemberExpression" &&
10801170
expression.callee.object.type === "FunctionExpression" &&
10811171
!expression.callee.computed &&
1082-
(["call", "bind"]).indexOf(expression.callee.property.name) >= 0 &&
1172+
(expression.callee.property.name === "call" || expression.callee.property.name === "bind") &&
10831173
expression.arguments &&
10841174
expression.arguments.length > 0
10851175
) {
@@ -1133,8 +1223,8 @@ class Parser extends Tapable {
11331223
}
11341224

11351225
walkIdentifier(expression) {
1136-
if(this.scope.definitions.indexOf(expression.name) === -1) {
1137-
const result = this.applyPluginsBailResult1("expression " + (this.scope.renames["$" + expression.name] || expression.name), expression);
1226+
if(!this.scope.definitions.has(expression.name)) {
1227+
const result = this.applyPluginsBailResult1("expression " + (this.scope.renames.get(expression.name) || expression.name), expression);
11381228
if(result === true)
11391229
return;
11401230
}
@@ -1145,23 +1235,23 @@ class Parser extends Tapable {
11451235
this.scope = {
11461236
inTry: false,
11471237
inShorthand: false,
1148-
definitions: oldScope.definitions.slice(),
1149-
renames: Object.create(oldScope.renames)
1238+
definitions: oldScope.definitions.createChild(),
1239+
renames: oldScope.renames.createChild()
11501240
};
11511241

1152-
this.scope.renames.$this = undefined;
1242+
this.scope.renames.set("this", null);
11531243

11541244
for(let paramIndex = 0, len = params.length; paramIndex < len; paramIndex++) {
11551245
const param = params[paramIndex];
11561246

11571247
if(typeof param !== "string") {
11581248
this.enterPattern(param, param => {
1159-
this.scope.renames["$" + param] = undefined;
1160-
this.scope.definitions.push(param);
1249+
this.scope.renames.set(param, null);
1250+
this.scope.definitions.add(param);
11611251
});
11621252
} else {
1163-
this.scope.renames["$" + param] = undefined;
1164-
this.scope.definitions.push(param);
1253+
this.scope.renames.set(param, null);
1254+
this.scope.definitions.add(param);
11651255
}
11661256
}
11671257

@@ -1343,8 +1433,8 @@ class Parser extends Tapable {
13431433
const oldComments = this.comments;
13441434
this.scope = {
13451435
inTry: false,
1346-
definitions: [],
1347-
renames: {}
1436+
definitions: new StackedSetMap(false),
1437+
renames: new StackedSetMap(null)
13481438
};
13491439
const state = this.state = initialState || {};
13501440
this.comments = comments;
@@ -1401,11 +1491,11 @@ class Parser extends Tapable {
14011491
}
14021492
let free;
14031493
if(expr.type === "Identifier") {
1404-
free = this.scope.definitions.indexOf(expr.name) === -1;
1405-
exprName.push(this.scope.renames["$" + expr.name] || expr.name);
1494+
free = !this.scope.definitions.has(expr.name);
1495+
exprName.push(this.scope.renames.get(expr.name) || expr.name);
14061496
} else if(expr.type === "ThisExpression" && this.scope.renames.$this) {
14071497
free = true;
1408-
exprName.push(this.scope.renames.$this);
1498+
exprName.push(this.scope.renames.get("this"));
14091499
} else if(expr.type === "ThisExpression") {
14101500
free = false;
14111501
exprName.push("this");
@@ -1429,3 +1519,4 @@ class Parser extends Tapable {
14291519
Parser.ECMA_VERSION = ECMA_VERSION;
14301520

14311521
module.exports = Parser;
1522+
Parser.StackedSetMap = StackedSetMap;

‎lib/dependencies/AMDDefineDependencyParserPlugin.js‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -105,7 +105,7 @@ class AMDDefineDependencyParserPlugin {
105105
if(fnParamsOffset < 0) fnParamsOffset = 0;
106106
}
107107
}
108-
let fnRenames = Object.create(parser.scope.renames);
108+
let fnRenames = parser.scope.renames.createChild();
109109
let identifiers;
110110
if(array) {
111111
identifiers = {};
@@ -114,7 +114,7 @@ class AMDDefineDependencyParserPlugin {
114114
if(!result) return;
115115
if(fnParams) fnParams = fnParams.slice(fnParamsOffset).filter((param, idx) => {
116116
if(identifiers[idx]) {
117-
fnRenames["$" + param.name] = identifiers[idx];
117+
fnRenames.set(param.name, identifiers[idx]);
118118
return false;
119119
}
120120
return true;
@@ -123,7 +123,7 @@ class AMDDefineDependencyParserPlugin {
123123
identifiers = ["require", "exports", "module"];
124124
if(fnParams) fnParams = fnParams.slice(fnParamsOffset).filter((param, idx) => {
125125
if(identifiers[idx]) {
126-
fnRenames["$" + param.name] = identifiers[idx];
126+
fnRenames.set(param.name, identifiers[idx]);
127127
return false;
128128
}
129129
return true;

‎lib/dependencies/CommonJsPlugin.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -65,7 +65,7 @@ class CommonJsPlugin {
6565
const dep = new ConstDependency("var require;", 0);
6666
dep.loc = expr.loc;
6767
parser.state.current.addDependency(dep);
68-
parser.scope.definitions.push("require");
68+
parser.scope.definitions.add("require");
6969
return true;
7070
});
7171
parser.plugin("can-rename require", () => true);

‎lib/dependencies/HarmonyExportDependencyParserPlugin.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -37,7 +37,7 @@ module.exports = class HarmonyExportDependencyParserPlugin {
3737
});
3838
parser.plugin("export declaration", statement => {});
3939
parser.plugin("export specifier", (statement, id, name, idx) => {
40-
const rename = parser.scope.renames[`$${id}`];
40+
const rename = parser.scope.renames.get(id);
4141
let dep;
4242
if(rename === "imported var") {
4343
const settings = parser.state.harmonySpecifier[`$${id}`];

0 commit comments

Comments
 (0)