Commit 3db9632585e for nodejs
commit 3db9632585ee428b57f758b7e0287bcd24202503
Author: Jacky Zhao <j.zhao2k19@gmail.com>
Date: Tue Nov 17 06:58:30 2026 -0800
module: store source map mappings in a typed array
SourceMap kept one six-element array per mapping segment. Bundled
applications have millions of segments, and with --enable-source-maps
a parsed map lives for the life of the process: a 63 MB source map with
2.9 million segments retained about 290 MiB of heap.
Store the segments in a single Int32Array, six fields per segment, and
resolve source URLs and names through per-map tables. Segments are
counted before parsing so storage is allocated once, and sorting is
skipped when the mappings are already in order. The public API and the
objects returned by findEntry() and findOrigin() are unchanged.
Signed-off-by: Jacky Zhao <j.zhao2k19@gmail.com>
PR-URL: https://github.com/nodejs/node/pull/66261
Reviewed-By: Chengzhong Wu <legendecas@gmail.com>
Reviewed-By: James M Snell <jasnell@gmail.com>
Reviewed-By: Matteo Collina <matteo.collina@gmail.com>
diff --git a/lib/internal/source_map/source_map.js b/lib/internal/source_map/source_map.js
index 42e7bca3c4c..c083dbc4a00 100644
--- a/lib/internal/source_map/source_map.js
+++ b/lib/internal/source_map/source_map.js
@@ -71,13 +71,21 @@ const {
ArrayPrototypePush,
ArrayPrototypeSlice,
ArrayPrototypeSort,
+ Int32Array,
+ MathMax,
ObjectFreeze,
ObjectPrototypeHasOwnProperty,
StringPrototypeCharAt,
Symbol,
+ TypedArrayPrototypeSet,
+ TypedArrayPrototypeSlice,
+ TypedArrayPrototypeSubarray,
} = primordials;
-const { validateObject } = require('internal/validators');
+const {
+ validateInt32,
+ validateObject,
+} = require('internal/validators');
let base64Map;
@@ -85,7 +93,18 @@ const VLQ_BASE_SHIFT = 5;
const VLQ_BASE_MASK = (1 << 5) - 1;
const VLQ_CONTINUATION_MASK = 1 << 5;
-const kMappings = Symbol('kMappings');
+const kFirstEntry = Symbol('kFirstEntry');
+
+// Each entry is stored as kEntrySize consecutive Int32 fields: generated line,
+// generated column, source index, original line, original column and name
+// index. Large maps have millions of entries, and one array per entry costs
+// several times more memory than the numbers it holds.
+const kEntrySize = 6;
+// Source index of an entry that has only a generated column.
+const kNoSource = -1;
+// Source index of an entry whose source index is outside `sources`.
+const kUnknownSource = -2;
+const kNoName = -1;
class StringCharIterator {
/**
@@ -126,7 +145,15 @@ class StringCharIterator {
*/
class SourceMap {
#payload;
- #mappings = [];
+ #entries;
+ #entryCount = 0;
+ #sourceURLs = [];
+ // Names of each map, indexed by the entries through a single index space
+ // that starts at #nameBases[i] for #nameTables[i]. Kept as is instead of
+ // being copied into one array.
+ #nameTables = [];
+ #nameBases = [];
+ #nameCount = 0;
#sources = {};
#sourceContentByURL = {};
#lineLengths = undefined;
@@ -156,8 +183,8 @@ class SourceMap {
return this.#payload;
}
- get [kMappings]() {
- return this.#mappings;
+ get [kFirstEntry]() {
+ return this.#entryCount ? this.#entryAt(0) : {};
}
/**
@@ -168,20 +195,138 @@ class SourceMap {
}
#parseMappingPayload = () => {
- if (this.#payload.sections) {
- this.#parseSections(this.#payload.sections);
+ const { sections } = this.#payload;
+ let segments = 0;
+ if (sections) {
+ for (let i = 0; i < sections.length; ++i) {
+ segments += estimateSegments(sections[i]?.map?.mappings);
+ }
+ } else {
+ segments = estimateSegments(this.#payload.mappings);
+ }
+ this.#entries = new Int32Array(segments * kEntrySize);
+ if (sections) {
+ this.#parseSections(sections);
} else {
this.#parseMap(this.#payload, 0, 0);
}
- ArrayPrototypeSort(this.#mappings, compareSourceMapEntry);
+ this.#sortEntries();
};
+ #sortEntries() {
+ const entries = this.#entries;
+ const count = this.#entryCount;
+ const compare = (a, b) => {
+ const lineDelta = entries[a * kEntrySize] - entries[b * kEntrySize];
+ return lineDelta ||
+ entries[a * kEntrySize + 1] - entries[b * kEntrySize + 1];
+ };
+ let sorted = true;
+ for (let i = 1; i < count; ++i) {
+ if (compare(i - 1, i) > 0) {
+ sorted = false;
+ break;
+ }
+ }
+ if (sorted) {
+ if (entries.length !== count * kEntrySize) {
+ this.#entries =
+ TypedArrayPrototypeSlice(entries, 0, count * kEntrySize);
+ }
+ return;
+ }
+ // Sorting indices keeps equal positions in insertion order, like the
+ // stable sort of entries this replaces.
+ const order = [];
+ for (let i = 0; i < count; ++i) {
+ ArrayPrototypePush(order, i);
+ }
+ ArrayPrototypeSort(order, compare);
+ const sortedEntries = new Int32Array(count * kEntrySize);
+ for (let i = 0; i < count; ++i) {
+ const offset = order[i] * kEntrySize;
+ TypedArrayPrototypeSet(
+ sortedEntries,
+ TypedArrayPrototypeSubarray(entries, offset, offset + kEntrySize),
+ i * kEntrySize,
+ );
+ }
+ this.#entries = sortedEntries;
+ }
+
+ #pushEntry(lineNumber, columnNumber, sourceIndex, sourceLineNumber,
+ sourceColumnNumber, nameIndex) {
+ const offset = this.#entryCount * kEntrySize;
+ if (offset === this.#entries.length) {
+ // Only reached when the parser finds more segments than
+ // estimateSegments(), which happens for malformed mappings.
+ const grown =
+ new Int32Array(MathMax(this.#entries.length * 2, kEntrySize * 16));
+ TypedArrayPrototypeSet(grown, this.#entries);
+ this.#entries = grown;
+ }
+ const entries = this.#entries;
+ entries[offset] = lineNumber;
+ entries[offset + 1] = columnNumber;
+ entries[offset + 2] = sourceIndex;
+ entries[offset + 3] = sourceLineNumber;
+ entries[offset + 4] = sourceColumnNumber;
+ entries[offset + 5] = nameIndex;
+ this.#entryCount++;
+ }
+
+ #nameAt(index) {
+ const bases = this.#nameBases;
+ // Find the last table starting at or before the index.
+ let low = 0;
+ let high = bases.length - 1;
+ while (low < high) {
+ const middle = (low + high + 1) >> 1;
+ if (bases[middle] <= index) {
+ low = middle;
+ } else {
+ high = middle - 1;
+ }
+ }
+ return this.#nameTables[low][index - bases[low]];
+ }
+
+ #entryAt(index) {
+ const entries = this.#entries;
+ const offset = index * kEntrySize;
+ const sourceIndex = entries[offset + 2];
+ if (sourceIndex === kNoSource) {
+ return {
+ generatedLine: entries[offset],
+ generatedColumn: entries[offset + 1],
+ originalSource: undefined,
+ originalLine: undefined,
+ originalColumn: undefined,
+ name: undefined,
+ };
+ }
+ const nameIndex = entries[offset + 5];
+ return {
+ generatedLine: entries[offset],
+ generatedColumn: entries[offset + 1],
+ originalSource: sourceIndex === kUnknownSource ?
+ undefined : this.#sourceURLs[sourceIndex],
+ originalLine: entries[offset + 3],
+ originalColumn: entries[offset + 4],
+ name: nameIndex === kNoName ? undefined : this.#nameAt(nameIndex),
+ };
+ }
+
/**
* @param {Array.<SourceMapV3.Section>} sections
*/
#parseSections = (sections) => {
for (let i = 0; i < sections.length; ++i) {
const section = sections[i];
+ // The offsets seed the Int32Array entries below, so reject anything
+ // that would otherwise be implicitly coerced.
+ validateInt32(section.offset.line, 'section.offset.line', 0);
+ validateInt32(section.offset.column, 'section.offset.column', 0);
this.#parseMap(section.map, section.offset.line, section.offset.column);
}
};
@@ -192,35 +337,30 @@ class SourceMap {
* @returns {object} representing start of range if found, or empty object
*/
findEntry(lineOffset, columnOffset) {
+ const entries = this.#entries;
let first = 0;
- let count = this.#mappings.length;
+ let count = this.#entryCount;
+ if (!count) {
+ return {};
+ }
while (count > 1) {
const step = count >> 1;
const middle = first + step;
- const mapping = this.#mappings[middle];
- if (lineOffset < mapping[0] ||
- (lineOffset === mapping[0] && columnOffset < mapping[1])) {
+ const line = entries[middle * kEntrySize];
+ if (lineOffset < line ||
+ (lineOffset === line &&
+ columnOffset < entries[middle * kEntrySize + 1])) {
count = step;
} else {
first = middle;
count -= step;
}
}
- const entry = this.#mappings[first];
- if (!first && entry && (lineOffset < entry[0] ||
- (lineOffset === entry[0] && columnOffset < entry[1]))) {
- return {};
- } else if (!entry) {
+ if (!first && (lineOffset < entries[0] ||
+ (lineOffset === entries[0] && columnOffset < entries[1]))) {
return {};
}
- return {
- generatedLine: entry[0],
- generatedColumn: entry[1],
- originalSource: entry[2],
- originalLine: entry[3],
- originalColumn: entry[4],
- name: entry[5],
- };
+ return this.#entryAt(first);
}
/**
@@ -260,18 +400,24 @@ class SourceMap {
const sources = [];
const originalToCanonicalURLMap = {};
+ const sourceBase = this.#sourceURLs.length;
for (let i = 0; i < map.sources.length; ++i) {
const url = map.sources[i];
originalToCanonicalURLMap[url] = url;
ArrayPrototypePush(sources, url);
+ ArrayPrototypePush(this.#sourceURLs, url);
this.#sources[url] = true;
if (map.sourcesContent?.[i])
this.#sourceContentByURL[url] = map.sourcesContent[i];
}
+ const names = map.names ?? [];
+ const nameBase = this.#nameCount;
+ ArrayPrototypePush(this.#nameTables, names);
+ ArrayPrototypePush(this.#nameBases, nameBase);
+ this.#nameCount += names.length;
const stringCharIterator = new StringCharIterator(map.mappings);
- let sourceURL = sources[sourceIndex];
while (true) {
if (stringCharIterator.peek() === ',')
stringCharIterator.next();
@@ -287,33 +433,51 @@ class SourceMap {
columnNumber += decodeVLQ(stringCharIterator);
if (isSeparator(stringCharIterator.peek())) {
- ArrayPrototypePush(this.#mappings, [lineNumber, columnNumber]);
+ this.#pushEntry(lineNumber, columnNumber, kNoSource, 0, 0, kNoName);
continue;
}
- const sourceIndexDelta = decodeVLQ(stringCharIterator);
- if (sourceIndexDelta) {
- sourceIndex += sourceIndexDelta;
- sourceURL = sources[sourceIndex];
- }
+ sourceIndex += decodeVLQ(stringCharIterator);
sourceLineNumber += decodeVLQ(stringCharIterator);
sourceColumnNumber += decodeVLQ(stringCharIterator);
- let name;
+ let entryNameIndex = kNoName;
if (!isSeparator(stringCharIterator.peek())) {
nameIndex += decodeVLQ(stringCharIterator);
- name = map.names?.[nameIndex];
+ if (nameIndex >= 0 && nameIndex < names.length) {
+ entryNameIndex = nameBase + nameIndex;
+ }
}
- ArrayPrototypePush(
- this.#mappings,
- [lineNumber, columnNumber, sourceURL, sourceLineNumber,
- sourceColumnNumber, name],
+ this.#pushEntry(
+ lineNumber,
+ columnNumber,
+ sourceIndex >= 0 && sourceIndex < sources.length ?
+ sourceBase + sourceIndex : kUnknownSource,
+ sourceLineNumber,
+ sourceColumnNumber,
+ entryNameIndex,
);
}
}
}
+/**
+ * Estimates the number of segments in a mappings string, so entry storage
+ * can be allocated up front without a separate pass over the string. A
+ * segment takes four to five VLQ digits and a separator in typical maps.
+ * #pushEntry grows the storage if the estimate turns out to be too low, and
+ * #sortEntries trims it if it is too high.
+ * @param {string} mappings
+ * @returns {number}
+ */
+function estimateSegments(mappings) {
+ if (typeof mappings !== 'string') {
+ return 0;
+ }
+ return (mappings.length + 3) >> 2;
+}
+
/**
* @param {string} char
* @returns {boolean}
@@ -370,22 +534,7 @@ function cloneSourceMapV3(payload) {
return ObjectFreeze(payload);
}
-/**
- * @param {Array} entry1 source map entry [lineNumber, columnNumber, sourceURL,
- * sourceLineNumber, sourceColumnNumber]
- * @param {Array} entry2 source map entry.
- * @returns {number}
- */
-function compareSourceMapEntry(entry1, entry2) {
- const { 0: lineNumber1, 1: columnNumber1 } = entry1;
- const { 0: lineNumber2, 1: columnNumber2 } = entry2;
- if (lineNumber1 !== lineNumber2) {
- return lineNumber1 - lineNumber2;
- }
- return columnNumber1 - columnNumber2;
-}
-
module.exports = {
- kMappings,
+ kFirstEntry,
SourceMap,
};
diff --git a/lib/internal/test_runner/coverage.js b/lib/internal/test_runner/coverage.js
index 3d0fcde700a..fdfd4d4cdd2 100644
--- a/lib/internal/test_runner/coverage.js
+++ b/lib/internal/test_runner/coverage.js
@@ -31,7 +31,7 @@ const { isWindows, setupCoverageHooks } = require('internal/util');
const { tmpdir } = require('os');
const { join, resolve, relative } = require('path');
const { fileURLToPath, pathToFileURL, URL } = require('internal/url');
-const { kMappings, SourceMap } = require('internal/source_map/source_map');
+const { kFirstEntry, SourceMap } = require('internal/source_map/source_map');
const {
codes: {
ERR_OPERATION_FAILED,
@@ -521,7 +521,7 @@ class TestCoverage {
if (!startEntry.originalSource && endEntry.originalSource &&
lines[0].line === 1 && startOffset === 0 && lines[0].startOffset === 0) {
// Edge case when the first line is not mappable
- const { 2: originalSource, 3: originalLine, 4: originalColumn } = sourceMap[kMappings][0];
+ const { originalSource, originalLine, originalColumn } = sourceMap[kFirstEntry];
startEntry = { __proto__: null, originalSource, originalLine, originalColumn };
}
diff --git a/test/parallel/test-source-map-entry-indices.js b/test/parallel/test-source-map-entry-indices.js
new file mode 100644
index 00000000000..e1e8406ae57
--- /dev/null
+++ b/test/parallel/test-source-map-entry-indices.js
@@ -0,0 +1,70 @@
+'use strict';
+require('../common');
+const assert = require('assert');
+const { SourceMap } = require('node:module');
+
+// Segments listed out of column order are looked up by generated position.
+{
+ const sm = new SourceMap({
+ version: 3,
+ sources: ['a.js'],
+ names: [],
+ mappings: 'KAAA,LAAC',
+ });
+
+ assert.strictEqual(sm.findEntry(0, 0).originalColumn, 1);
+ assert.strictEqual(sm.findEntry(0, 6).originalColumn, 0);
+}
+
+// In an index map, a source or name index outside its own section's lists
+// does not resolve to an entry of another section.
+{
+ const sm = new SourceMap({
+ version: 3,
+ sections: [
+ {
+ offset: { line: 0, column: 0 },
+ map: {
+ version: 3,
+ sources: ['a.js'],
+ names: ['first'],
+ mappings: 'AAAAA,ECAAC',
+ },
+ },
+ {
+ offset: { line: 1, column: 0 },
+ map: {
+ version: 3,
+ sources: ['b.js'],
+ names: ['second'],
+ mappings: 'AAAAA',
+ },
+ },
+ ],
+ });
+
+ assert.deepStrictEqual(sm.findEntry(0, 0), {
+ generatedLine: 0,
+ generatedColumn: 0,
+ originalSource: 'a.js',
+ originalLine: 0,
+ originalColumn: 0,
+ name: 'first',
+ });
+ assert.deepStrictEqual(sm.findEntry(0, 2), {
+ generatedLine: 0,
+ generatedColumn: 2,
+ originalSource: undefined,
+ originalLine: 0,
+ originalColumn: 0,
+ name: undefined,
+ });
+ assert.deepStrictEqual(sm.findEntry(1, 0), {
+ generatedLine: 1,
+ generatedColumn: 0,
+ originalSource: 'b.js',
+ originalLine: 0,
+ originalColumn: 0,
+ name: 'second',
+ });
+}
diff --git a/test/parallel/test-source-map-invalid-section-offset.js b/test/parallel/test-source-map-invalid-section-offset.js
new file mode 100644
index 00000000000..3a0783a2ea7
--- /dev/null
+++ b/test/parallel/test-source-map-invalid-section-offset.js
@@ -0,0 +1,42 @@
+'use strict';
+require('../common');
+const assert = require('assert');
+const { SourceMap } = require('node:module');
+
+// Section offsets are stored in an Int32Array, so they must be validated
+// instead of being implicitly coerced.
+function sectionedMap(offset) {
+ return {
+ version: 3,
+ sections: [{
+ offset,
+ map: {
+ version: 3,
+ sources: ['a.js'],
+ names: [],
+ mappings: 'AAAA',
+ },
+ }],
+ };
+}
+
+{
+ const sm = new SourceMap(sectionedMap({ line: 1, column: 2 }));
+ assert.deepStrictEqual(sm.findEntry(1, 2), {
+ generatedLine: 1,
+ generatedColumn: 2,
+ originalSource: 'a.js',
+ originalLine: 0,
+ originalColumn: 0,
+ name: undefined,
+ });
+}
+
+for (const value of ['1', 1.5, 2 ** 31, null, {}]) {
+ assert.throws(() => new SourceMap(sectionedMap({ line: value, column: 0 })), {
+ code: /^ERR_(INVALID_ARG_TYPE|OUT_OF_RANGE)$/,
+ });
+ assert.throws(() => new SourceMap(sectionedMap({ line: 0, column: value })), {
+ code: /^ERR_(INVALID_ARG_TYPE|OUT_OF_RANGE)$/,
+ });
+}
diff --git a/test/parallel/test-source-map-section-names.js b/test/parallel/test-source-map-section-names.js
new file mode 100644
index 00000000000..22c342951ef
--- /dev/null
+++ b/test/parallel/test-source-map-section-names.js
@@ -0,0 +1,35 @@
+'use strict';
+require('../common');
+const assert = require('assert');
+const { SourceMap } = require('node:module');
+
+// Names are looked up across sections, including sections that have no names.
+const sm = new SourceMap({
+ version: 3,
+ sections: [
+ {
+ offset: { line: 0, column: 0 },
+ map: { version: 3, sources: ['a.js'], names: ['a0', 'a1'],
+ mappings: 'AAAAA,CAAAC' },
+ },
+ {
+ offset: { line: 1, column: 0 },
+ map: { version: 3, sources: ['b.js'], mappings: 'AAAA' },
+ },
+ {
+ offset: { line: 2, column: 0 },
+ map: { version: 3, sources: ['c.js'], names: [], mappings: 'AAAA' },
+ },
+ {
+ offset: { line: 3, column: 0 },
+ map: { version: 3, sources: ['d.js'], names: ['d0'],
+ mappings: 'AAAAA' },
+ },
+ ],
+});
+
+assert.strictEqual(sm.findEntry(0, 0).name, 'a0');
+assert.strictEqual(sm.findEntry(0, 1).name, 'a1');
+assert.strictEqual(sm.findEntry(1, 0).name, undefined);
+assert.strictEqual(sm.findEntry(2, 0).name, undefined);
+assert.strictEqual(sm.findEntry(3, 0).name, 'd0');