Skip to content

Commit 8386d49

Browse files
author
Andy Hanson
committed
Use sparse arrays for number-keyed maps
1 parent b53b5cf commit 8386d49

17 files changed

Lines changed: 240 additions & 221 deletions

File tree

‎src/compiler/checker.ts‎

Lines changed: 4 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -4054,16 +4054,15 @@ namespace ts {
40544054
enumType.symbol = symbol;
40554055
if (enumHasLiteralMembers(symbol)) {
40564056
const memberTypeList: Type[] = [];
4057-
const memberTypes = createMap<EnumLiteralType>();
4057+
const memberTypes = sparseArray<EnumLiteralType>();
40584058
for (const declaration of enumType.symbol.declarations) {
40594059
if (declaration.kind === SyntaxKind.EnumDeclaration) {
40604060
computeEnumMemberValues(<EnumDeclaration>declaration);
40614061
for (const member of (<EnumDeclaration>declaration).members) {
40624062
const memberSymbol = getSymbolOfNode(member);
40634063
const value = getEnumMemberValue(member);
4064-
if (!memberTypes.has(value)) {
4065-
const memberType = createEnumLiteralType(memberSymbol, enumType, "" + value);
4066-
memberTypes.set(value, memberType);
4064+
if (!memberTypes[value]) {
4065+
const memberType = memberTypes[value] = createEnumLiteralType(memberSymbol, enumType, "" + value);
40674066
memberTypeList.push(memberType);
40684067
}
40694068
}
@@ -4085,7 +4084,7 @@ namespace ts {
40854084
if (!links.declaredType) {
40864085
const enumType = <EnumType>getDeclaredTypeOfEnum(getParentOfSymbol(symbol));
40874086
links.declaredType = enumType.flags & TypeFlags.Union ?
4088-
enumType.memberTypes.get(getEnumMemberValue(<EnumMember>symbol.valueDeclaration)) :
4087+
enumType.memberTypes[getEnumMemberValue(<EnumMember>symbol.valueDeclaration)] :
40894088
enumType;
40904089
}
40914090
return links.declaredType;

‎src/compiler/core.ts‎

Lines changed: 19 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -39,6 +39,8 @@ namespace ts {
3939
return map;
4040
}
4141

42+
export const sparseArray: <T>() => SparseArray<T> = createMapLike;
43+
4244
/** Create a new map. If a template object is provided, the map will copy entries from it. */
4345
export function createMap<T>(template?: MapLike<T>): Map<T> {
4446
const map: Map<T> = new MapCtr<T>();
@@ -52,17 +54,6 @@ namespace ts {
5254
return map;
5355
}
5456

55-
/** Create a map from [key, value] pairs. This avoids casting keys to strings. */
56-
export function createMapFromPairs<T>(...pairs: [number, T][]): Map<T> {
57-
const map: Map<T> = new MapCtr<T>();
58-
59-
for (const [key, value] of pairs) {
60-
map.set(key, value);
61-
}
62-
63-
return map;
64-
}
65-
6657
/** Methods on native maps but not on shim maps. Only used in this file. */
6758
interface ES6Map<T> extends Map<T> {
6859
entries(): Iterator<[string, T]>;
@@ -92,21 +83,21 @@ namespace ts {
9283
return class<T> implements ShimMap<T> {
9384
private data = createMapLike<T>();
9485

95-
get(key: MapKey): T {
86+
get(key: string): T {
9687
return this.data[key];
9788
}
9889

99-
set(key: MapKey, value: T): this {
90+
set(key: string, value: T): this {
10091
this.data[key] = value;
10192
return this;
10293
}
10394

104-
has(key: MapKey): boolean {
95+
has(key: string): boolean {
10596
// tslint:disable-next-line:no-in-operator
10697
return key in this.data;
10798
}
10899

109-
delete(key: MapKey): boolean {
100+
delete(key: string): boolean {
110101
const had = this.has(key);
111102
if (had) {
112103
delete this.data[key];
@@ -890,7 +881,7 @@ namespace ts {
890881
* Array of every key in a map.
891882
* May not actually return string[] if numbers were put into the map.
892883
*/
893-
export function keysOfMap<T>(map: Map<T>): string[] {
884+
export function keysOfMap(map: Map<{}>): string[] {
894885
const keys: string[] = [];
895886
forEachKeyInMap(map, key => {
896887
keys.push(key);
@@ -1040,7 +1031,7 @@ namespace ts {
10401031
* Adds the value to an array of values associated with the key, and returns the array.
10411032
* Creates the array if it does not already exist.
10421033
*/
1043-
export function multiMapAdd<V>(map: Map<V[]>, key: string | number, value: V): V[] {
1034+
export function multiMapAdd<V>(map: Map<V[]>, key: string, value: V): V[] {
10441035
let values = map.get(key);
10451036
if (values) {
10461037
values.push(value);
@@ -1051,6 +1042,17 @@ namespace ts {
10511042
return values;
10521043
}
10531044

1045+
export function multiMapSparseArrayAdd<V>(map: SparseArray<V[]>, key: number, value: V): V[] {
1046+
let values = map[key];
1047+
if (values) {
1048+
values.push(value);
1049+
}
1050+
else {
1051+
map[key] = values = [value];
1052+
}
1053+
return values;
1054+
}
1055+
10541056
/**
10551057
* Removes a value from an array of values associated with the key.
10561058
* Does not preserve the order of those values.

‎src/compiler/factory.ts‎

Lines changed: 16 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
/// <reference path="core.ts"/>
1+
/// <reference path="core.ts"/>
22
/// <reference path="utilities.ts"/>
33

44
/* @internal */
@@ -2641,9 +2641,11 @@ namespace ts {
26412641
return destEmitNode;
26422642
}
26432643

2644-
function mergeTokenSourceMapRanges(sourceRanges: Map<TextRange>, destRanges: Map<TextRange>) {
2645-
if (!destRanges) destRanges = createMap<TextRange>();
2646-
copyMapEntries(sourceRanges, destRanges);
2644+
function mergeTokenSourceMapRanges(sourceRanges: SparseArray<TextRange>, destRanges: SparseArray<TextRange>) {
2645+
if (!destRanges) destRanges = [];
2646+
for (const key in sourceRanges) {
2647+
destRanges[key] = sourceRanges[key];
2648+
}
26472649
return destRanges;
26482650
}
26492651

@@ -2745,7 +2747,7 @@ namespace ts {
27452747
export function getTokenSourceMapRange(node: Node, token: SyntaxKind) {
27462748
const emitNode = node.emitNode;
27472749
const tokenSourceMapRanges = emitNode && emitNode.tokenSourceMapRanges;
2748-
return tokenSourceMapRanges && tokenSourceMapRanges.get(token);
2750+
return tokenSourceMapRanges && tokenSourceMapRanges[token];
27492751
}
27502752

27512753
/**
@@ -2757,8 +2759,8 @@ namespace ts {
27572759
*/
27582760
export function setTokenSourceMapRange<T extends Node>(node: T, token: SyntaxKind, range: TextRange) {
27592761
const emitNode = getOrCreateEmitNode(node);
2760-
const tokenSourceMapRanges = emitNode.tokenSourceMapRanges || (emitNode.tokenSourceMapRanges = createMap<TextRange>());
2761-
tokenSourceMapRanges.set(token, range);
2762+
const tokenSourceMapRanges = emitNode.tokenSourceMapRanges || (emitNode.tokenSourceMapRanges = []);
2763+
tokenSourceMapRanges[token] = range;
27622764
return node;
27632765
}
27642766

@@ -3270,7 +3272,7 @@ namespace ts {
32703272
externalImports: (ImportDeclaration | ImportEqualsDeclaration | ExportDeclaration)[]; // imports of other external modules
32713273
externalHelpersImportDeclaration: ImportDeclaration | undefined; // import of external helpers
32723274
exportSpecifiers: Map<ExportSpecifier[]>; // export specifiers by name
3273-
exportedBindings: Map<Identifier[]>; // exported names of local declarations
3275+
exportedBindings: SparseArray<Identifier[]>; // exported names of local declarations
32743276
exportedNames: Identifier[]; // all exported names local to module
32753277
exportEquals: ExportAssignment | undefined; // an export= declaration if one was present
32763278
hasExportStarsToExportValues: boolean; // whether this module contains export*
@@ -3279,7 +3281,7 @@ namespace ts {
32793281
export function collectExternalModuleInfo(sourceFile: SourceFile, resolver: EmitResolver, compilerOptions: CompilerOptions): ExternalModuleInfo {
32803282
const externalImports: (ImportDeclaration | ImportEqualsDeclaration | ExportDeclaration)[] = [];
32813283
const exportSpecifiers = createMap<ExportSpecifier[]>();
3282-
const exportedBindings = createMap<Identifier[]>();
3284+
const exportedBindings = sparseArray<Identifier[]>();
32833285
const uniqueExports = createMap<boolean>();
32843286
let exportedNames: Identifier[];
32853287
let hasExportDefault = false;
@@ -3338,7 +3340,7 @@ namespace ts {
33383340
|| resolver.getReferencedValueDeclaration(name);
33393341

33403342
if (decl) {
3341-
multiMapAdd(exportedBindings, getOriginalNodeId(decl), specifier.name);
3343+
multiMapSparseArrayAdd(exportedBindings, getOriginalNodeId(decl), specifier.name);
33423344
}
33433345

33443346
uniqueExports.set(specifier.name.text, true);
@@ -3368,15 +3370,15 @@ namespace ts {
33683370
if (hasModifier(node, ModifierFlags.Default)) {
33693371
// export default function() { }
33703372
if (!hasExportDefault) {
3371-
multiMapAdd(exportedBindings, getOriginalNodeId(node), getDeclarationName(<FunctionDeclaration>node));
3373+
multiMapSparseArrayAdd(exportedBindings, getOriginalNodeId(node), getDeclarationName(<FunctionDeclaration>node));
33723374
hasExportDefault = true;
33733375
}
33743376
}
33753377
else {
33763378
// export function x() { }
33773379
const name = (<FunctionDeclaration>node).name;
33783380
if (!uniqueExports.get(name.text)) {
3379-
multiMapAdd(exportedBindings, getOriginalNodeId(node), name);
3381+
multiMapSparseArrayAdd(exportedBindings, getOriginalNodeId(node), name);
33803382
uniqueExports.set(name.text, true);
33813383
exportedNames = append(exportedNames, name);
33823384
}
@@ -3389,15 +3391,15 @@ namespace ts {
33893391
if (hasModifier(node, ModifierFlags.Default)) {
33903392
// export default class { }
33913393
if (!hasExportDefault) {
3392-
multiMapAdd(exportedBindings, getOriginalNodeId(node), getDeclarationName(<ClassDeclaration>node));
3394+
multiMapSparseArrayAdd(exportedBindings, getOriginalNodeId(node), getDeclarationName(<ClassDeclaration>node));
33933395
hasExportDefault = true;
33943396
}
33953397
}
33963398
else {
33973399
// export class x { }
33983400
const name = (<ClassDeclaration>node).name;
33993401
if (!uniqueExports.get(name.text)) {
3400-
multiMapAdd(exportedBindings, getOriginalNodeId(node), name);
3402+
multiMapSparseArrayAdd(exportedBindings, getOriginalNodeId(node), name);
34013403
uniqueExports.set(name.text, true);
34023404
exportedNames = append(exportedNames, name);
34033405
}

‎src/compiler/sourcemap.ts‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -362,7 +362,7 @@ namespace ts {
362362

363363
const emitNode = node && node.emitNode;
364364
const emitFlags = emitNode && emitNode.flags;
365-
const range = emitNode && emitNode.tokenSourceMapRanges && emitNode.tokenSourceMapRanges.get(token);
365+
const range = emitNode && emitNode.tokenSourceMapRanges && emitNode.tokenSourceMapRanges[token];
366366

367367
tokenPos = skipTrivia(currentSourceText, range ? range.pos : tokenPos);
368368
if ((emitFlags & EmitFlags.NoTokenLeadingSourceMaps) === 0 && tokenPos >= 0) {

‎src/compiler/transformer.ts‎

Lines changed: 12 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
/// <reference path="visitor.ts" />
1+
/// <reference path="visitor.ts" />
22
/// <reference path="transformers/ts.ts" />
33
/// <reference path="transformers/jsx.ts" />
44
/// <reference path="transformers/esnext.ts" />
@@ -13,14 +13,16 @@
1313

1414
/* @internal */
1515
namespace ts {
16-
const moduleTransformerMap = createMapFromPairs<Transformer>(
17-
[ModuleKind.ES2015, transformES2015Module],
18-
[ModuleKind.System, transformSystemModule],
19-
[ModuleKind.AMD, transformModule],
20-
[ModuleKind.CommonJS, transformModule],
21-
[ModuleKind.UMD, transformModule],
22-
[ModuleKind.None, transformModule],
23-
);
16+
function getModuleTransformer(moduleKind: ModuleKind): Transformer {
17+
switch (moduleKind) {
18+
case ModuleKind.ES2015:
19+
return transformES2015Module;
20+
case ModuleKind.System:
21+
return transformSystemModule;
22+
default:
23+
return transformModule;
24+
}
25+
}
2426

2527
const enum SyntaxKindFeatureFlags {
2628
Substitution = 1 << 0,
@@ -56,7 +58,7 @@ namespace ts {
5658
transformers.push(transformGenerators);
5759
}
5860

59-
transformers.push(moduleTransformerMap.get(moduleKind) || moduleTransformerMap.get(ModuleKind.None));
61+
transformers.push(getModuleTransformer(moduleKind));
6062

6163
// The ES5 transformer is last so that it can substitute expressions like `exports.default`
6264
// for ES3.

‎src/compiler/transformers/generators.ts‎

Lines changed: 15 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
/// <reference path="../factory.ts" />
1+
/// <reference path="../factory.ts" />
22
/// <reference path="../visitor.ts" />
33

44
// Transforms generator functions into a compatible ES5 representation with similar runtime
@@ -217,13 +217,15 @@ namespace ts {
217217
Endfinally = 7,
218218
}
219219

220-
const instructionNames = createMapFromPairs<string>(
221-
[Instruction.Return, "return"],
222-
[Instruction.Break, "break"],
223-
[Instruction.Yield, "yield"],
224-
[Instruction.YieldStar, "yield*"],
225-
[Instruction.Endfinally, "endfinally"],
226-
);
220+
function getInstructionName(instruction: Instruction): string {
221+
switch (instruction) {
222+
case Instruction.Return: return "return";
223+
case Instruction.Break: return "break";
224+
case Instruction.Yield: return "yield";
225+
case Instruction.YieldStar: return "yield*";
226+
case Instruction.Endfinally: return "endfinally";
227+
}
228+
}
227229

228230
export function transformGenerators(context: TransformationContext) {
229231
const {
@@ -241,7 +243,7 @@ namespace ts {
241243

242244
let currentSourceFile: SourceFile;
243245
let renamedCatchVariables: Map<boolean>;
244-
let renamedCatchVariableDeclarations: Map<Identifier>;
246+
let renamedCatchVariableDeclarations: SparseArray<Identifier>;
245247

246248
let inGeneratorFunctionBody: boolean;
247249
let inStatementContainingYield: boolean;
@@ -1926,7 +1928,7 @@ namespace ts {
19261928
if (isIdentifier(original) && original.parent) {
19271929
const declaration = resolver.getReferencedValueDeclaration(original);
19281930
if (declaration) {
1929-
const name = renamedCatchVariableDeclarations.get(getOriginalNodeId(declaration));
1931+
const name = renamedCatchVariableDeclarations[getOriginalNodeId(declaration)];
19301932
if (name) {
19311933
const clone = getMutableClone(name);
19321934
setSourceMapRange(clone, node);
@@ -2092,12 +2094,12 @@ namespace ts {
20922094

20932095
if (!renamedCatchVariables) {
20942096
renamedCatchVariables = createMap<boolean>();
2095-
renamedCatchVariableDeclarations = createMap<Identifier>();
2097+
renamedCatchVariableDeclarations = sparseArray<Identifier>();
20962098
context.enableSubstitution(SyntaxKind.Identifier);
20972099
}
20982100

20992101
renamedCatchVariables.set(text, true);
2100-
renamedCatchVariableDeclarations.set(getOriginalNodeId(variable), name);
2102+
renamedCatchVariableDeclarations[getOriginalNodeId(variable)] = name;
21012103

21022104
const exception = <ExceptionBlock>peekBlock();
21032105
Debug.assert(exception.state < ExceptionBlockState.Catch);
@@ -2401,7 +2403,7 @@ namespace ts {
24012403
*/
24022404
function createInstruction(instruction: Instruction): NumericLiteral {
24032405
const literal = createLiteral(instruction);
2404-
literal.trailingComment = instructionNames.get(instruction);
2406+
literal.trailingComment = getInstructionName(instruction);
24052407
return literal;
24062408
}
24072409

0 commit comments

Comments
 (0)