Skip to content

Commit dad20ad

Browse files
not-an-aardvarknot-an-aardvark
authored
New: add SourceCode#getLocFromIndex and #getIndexFromLoc (fixes #8073) (#8158)
1 parent 18a519f commit dad20ad

8 files changed

Lines changed: 227 additions & 122 deletions

File tree

‎docs/developer-guide/working-with-rules.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -282,6 +282,8 @@ Once you have an instance of `SourceCode`, you can use the methods on it to work
282282
* `getTokensBetween(nodeOrToken1, nodeOrToken2)` - returns all tokens between two nodes.
283283
* `getTokenByRangeStart(index, rangeOptions)` - returns the token whose range starts at the given index in the source.
284284
* `getNodeByRangeIndex(index)` - returns the deepest node in the AST containing the given source index.
285+
* `getLocFromIndex(index)` - returns an object with `line` and `column` properties, corresponding to the location of the given source index. `line` is 1-based and `column` is 0-based.
286+
* `getIndexFromLoc(loc)` - returns the index of a given location in the source code, where `loc` is an object with a 1-based `line` key and a 0-based `column` key.
285287

286288
> `skipOptions` is an object which has 3 properties; `skip`, `includeComments`, and `filter`. Default is `{skip: 0, includeComments: false, filter: null}`.
287289
> - `skip` is a positive integer, the number of skipping tokens. If `filter` option is given at the same time, it doesn't count filtered tokens as skipped.

‎lib/ast-utils.js‎

Lines changed: 0 additions & 67 deletions
Original file line numberDiff line numberDiff line change
@@ -10,7 +10,6 @@
1010
//------------------------------------------------------------------------------
1111

1212
const esutils = require("esutils");
13-
const lodash = require("lodash");
1413

1514
//------------------------------------------------------------------------------
1615
// Helpers
@@ -403,40 +402,6 @@ function createGlobalLinebreakMatcher() {
403402
return new RegExp(LINEBREAK_MATCHER.source, "g");
404403
}
405404

406-
const lineIndexCache = new WeakMap();
407-
408-
/**
409-
* Gets the range index for the first character in each of the lines of `sourceCode`.
410-
* @param {SourceCode} sourceCode A sourceCode object
411-
* @returns {number[]} The indices of the first characters in the each of the lines of the code
412-
*/
413-
function getLineIndices(sourceCode) {
414-
415-
if (!lineIndexCache.has(sourceCode)) {
416-
const lineIndices = [0];
417-
const lineEndingPattern = createGlobalLinebreakMatcher();
418-
let match;
419-
420-
/*
421-
* Previously, this function was implemented using a regex that
422-
* matched a sequence of non-linebreak characters followed by a
423-
* linebreak, then adding the lengths of the matches. However,
424-
* this caused a catastrophic backtracking issue when the end
425-
* of a file contained a large number of non-newline characters.
426-
* To avoid this, the current implementation just matches newlines
427-
* and uses match.index to get the correct line start indices.
428-
*/
429-
430-
while ((match = lineEndingPattern.exec(sourceCode.text))) {
431-
lineIndices.push(match.index + match[0].length);
432-
}
433-
434-
// Store the sourceCode object in a WeakMap to avoid iterating over all of the lines every time a sourceCode object is passed in.
435-
lineIndexCache.set(sourceCode, lineIndices);
436-
}
437-
return lineIndexCache.get(sourceCode);
438-
}
439-
440405
//------------------------------------------------------------------------------
441406
// Public Interface
442407
//------------------------------------------------------------------------------
@@ -1207,38 +1172,6 @@ module.exports = {
12071172
};
12081173
},
12091174

1210-
/*
1211-
* Converts a range index into a (line, column) pair.
1212-
* @param {SourceCode} sourceCode A SourceCode object
1213-
* @param {number} rangeIndex The range index of a character in a file
1214-
* @returns {Object} A {line, column} location object with a 0-indexed column
1215-
*/
1216-
getLocationFromRangeIndex(sourceCode, rangeIndex) {
1217-
const lineIndices = getLineIndices(sourceCode);
1218-
1219-
/*
1220-
* lineIndices is a sorted list of indices of the first character of each line.
1221-
* To figure out which line rangeIndex is on, determine the last index at which rangeIndex could
1222-
* be inserted into lineIndices to keep the list sorted.
1223-
*/
1224-
const lineNumber = lodash.sortedLastIndex(lineIndices, rangeIndex);
1225-
1226-
return { line: lineNumber, column: rangeIndex - lineIndices[lineNumber - 1] };
1227-
1228-
},
1229-
1230-
/**
1231-
* Converts a (line, column) pair into a range index.
1232-
* @param {SourceCode} sourceCode A SourceCode object
1233-
* @param {Object} loc A line/column location
1234-
* @param {number} loc.line The line number of the location (1-indexed)
1235-
* @param {number} loc.column The column number of the location (0-indexed)
1236-
* @returns {number} The range index of the location in the file.
1237-
*/
1238-
getRangeIndexFromLocation(sourceCode, loc) {
1239-
return getLineIndices(sourceCode)[loc.line - 1] + loc.column;
1240-
},
1241-
12421175
/**
12431176
* Gets the parenthesized text of a node. This is similar to sourceCode.getText(node), but it also includes any parentheses
12441177
* surrounding the node.

‎lib/rules/no-multiple-empty-lines.js‎

Lines changed: 2 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -5,8 +5,6 @@
55
*/
66
"use strict";
77

8-
const astUtils = require("../ast-utils");
9-
108
//------------------------------------------------------------------------------
119
// Rule Definition
1210
//------------------------------------------------------------------------------
@@ -114,8 +112,8 @@ module.exports = {
114112
data: { max: maxAllowed, pluralizedLines: maxAllowed === 1 ? "line" : "lines" },
115113
fix(fixer) {
116114
return fixer.removeRange([
117-
astUtils.getRangeIndexFromLocation(sourceCode, { line: lastLineNumber + 1, column: 0 }),
118-
astUtils.getRangeIndexFromLocation(sourceCode, { line: lineNumber - maxAllowed, column: 0 })
115+
sourceCode.getIndexFromLoc({ line: lastLineNumber + 1, column: 0 }),
116+
sourceCode.getIndexFromLoc({ line: lineNumber - maxAllowed, column: 0 })
119117
]);
120118
}
121119
});

‎lib/rules/no-unused-vars.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -568,7 +568,7 @@ module.exports = {
568568
function getLocation(variable) {
569569
const comment = variable.eslintExplicitGlobalComment;
570570

571-
return astUtils.getLocationFromRangeIndex(sourceCode, comment.range[0] + 2 + getColumnInComment(variable, comment));
571+
return sourceCode.getLocFromIndex(comment.range[0] + 2 + getColumnInComment(variable, comment));
572572
}
573573

574574
//--------------------------------------------------------------------------

‎lib/rules/no-useless-escape.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -94,7 +94,7 @@ module.exports = {
9494
function report(node, startOffset, character) {
9595
context.report({
9696
node,
97-
loc: astUtils.getLocationFromRangeIndex(sourceCode, astUtils.getRangeIndexFromLocation(sourceCode, node.loc.start) + startOffset),
97+
loc: sourceCode.getLocFromIndex(sourceCode.getIndexFromLoc(node.loc.start) + startOffset),
9898
message: "Unnecessary escape character: \\{{character}}.",
9999
data: { character }
100100
});

‎lib/util/source-code.js‎

Lines changed: 99 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -10,7 +10,8 @@
1010

1111
const TokenStore = require("../token-store"),
1212
Traverser = require("./traverser"),
13-
astUtils = require("../ast-utils");
13+
astUtils = require("../ast-utils"),
14+
lodash = require("lodash");
1415

1516
//------------------------------------------------------------------------------
1617
// Private
@@ -138,7 +139,26 @@ function SourceCode(text, ast) {
138139
* This is done to avoid each rule needing to do so separately.
139140
* @type string[]
140141
*/
141-
this.lines = SourceCode.splitLines(this.text);
142+
this.lines = [];
143+
this.lineStartIndices = [0];
144+
145+
const lineEndingPattern = astUtils.createGlobalLinebreakMatcher();
146+
let match;
147+
148+
/*
149+
* Previously, this was implemented using a regex that
150+
* matched a sequence of non-linebreak characters followed by a
151+
* linebreak, then adding the lengths of the matches. However,
152+
* this caused a catastrophic backtracking issue when the end
153+
* of a file contained a large number of non-newline characters.
154+
* To avoid this, the current implementation just matches newlines
155+
* and uses match.index to get the correct line start indices.
156+
*/
157+
while ((match = lineEndingPattern.exec(this.text))) {
158+
this.lines.push(this.text.slice(this.lineStartIndices[this.lineStartIndices.length - 1], match.index));
159+
this.lineStartIndices.push(match.index + match[0].length);
160+
}
161+
this.lines.push(this.text.slice(this.lineStartIndices[this.lineStartIndices.length - 1]));
142162

143163
this.tokensAndComments = sortedMerge(ast.tokens, ast.comments);
144164

@@ -312,6 +332,83 @@ SourceCode.prototype = {
312332
const text = this.text.slice(first.range[1], second.range[0]);
313333

314334
return /\s/.test(text.replace(/\/\*.*?\*\//g, ""));
335+
},
336+
337+
/**
338+
* Converts a source text index into a (line, column) pair.
339+
* @param {number} index The index of a character in a file
340+
* @returns {Object} A {line, column} location object with a 0-indexed column
341+
*/
342+
getLocFromIndex(index) {
343+
if (typeof index !== "number") {
344+
throw new TypeError("Expected `index` to be a number.");
345+
}
346+
347+
if (index < 0 || index > this.text.length) {
348+
throw new RangeError(`Index out of range (requested index ${index}, but source text has length ${this.text.length}).`);
349+
}
350+
351+
/*
352+
* For an argument of this.text.length, return the location one "spot" past the last character
353+
* of the file. If the last character is a linebreak, the location will be column 0 of the next
354+
* line; otherwise, the location will be in the next column on the same line.
355+
*
356+
* See getIndexFromLoc for the motivation for this special case.
357+
*/
358+
if (index === this.text.length) {
359+
return { line: this.lines.length, column: this.lines[this.lines.length - 1].length };
360+
}
361+
362+
/*
363+
* To figure out which line rangeIndex is on, determine the last index at which rangeIndex could
364+
* be inserted into lineIndices to keep the list sorted.
365+
*/
366+
const lineNumber = lodash.sortedLastIndex(this.lineStartIndices, index);
367+
368+
return { line: lineNumber, column: index - this.lineStartIndices[lineNumber - 1] };
369+
370+
},
371+
372+
/**
373+
* Converts a (line, column) pair into a range index.
374+
* @param {Object} loc A line/column location
375+
* @param {number} loc.line The line number of the location (1-indexed)
376+
* @param {number} loc.column The column number of the location (0-indexed)
377+
* @returns {number} The range index of the location in the file.
378+
*/
379+
getIndexFromLoc(loc) {
380+
if (typeof loc !== "object" || typeof loc.line !== "number" || typeof loc.column !== "number") {
381+
throw new TypeError("Expected `loc` to be an object with numeric `line` and `column` properties.");
382+
}
383+
384+
if (loc.line <= 0) {
385+
throw new RangeError(`Line number out of range (line ${loc.line} requested). Line numbers should be 1-based.`);
386+
}
387+
388+
if (loc.line > this.lineStartIndices.length) {
389+
throw new RangeError(`Line number out of range (line ${loc.line} requested, but only ${this.lineStartIndices.length} lines present).`);
390+
}
391+
392+
const lineStartIndex = this.lineStartIndices[loc.line - 1];
393+
const lineEndIndex = loc.line === this.lineStartIndices.length ? this.text.length : this.lineStartIndices[loc.line];
394+
const positionIndex = lineStartIndex + loc.column;
395+
396+
/*
397+
* By design, getIndexFromLoc({ line: lineNum, column: 0 }) should return the start index of
398+
* the given line, provided that the line number is valid element of this.lines. Since the
399+
* last element of this.lines is an empty string for files with trailing newlines, add a
400+
* special case where getting the index for the first location after the end of the file
401+
* will return the length of the file, rather than throwing an error. This allows rules to
402+
* use getIndexFromLoc consistently without worrying about edge cases at the end of a file.
403+
*/
404+
if (
405+
loc.line === this.lineStartIndices.length && positionIndex > lineEndIndex ||
406+
loc.line < this.lineStartIndices.length && positionIndex >= lineEndIndex
407+
) {
408+
throw new RangeError(`Column number out of range (column ${loc.column} requested, but the length of line ${loc.line} is ${lineEndIndex - lineStartIndex}).`);
409+
}
410+
411+
return positionIndex;
315412
}
316413
};
317414

‎tests/lib/ast-utils.js‎

Lines changed: 0 additions & 47 deletions
Original file line numberDiff line numberDiff line change
@@ -911,53 +911,6 @@ describe("ast-utils", () => {
911911
});
912912
});
913913

914-
describe("getLocationFromRangeIndex()", () => {
915-
it("should return the location of a range index", () => {
916-
917-
const CODE =
918-
"foo\n" +
919-
"bar\r\n" +
920-
"baz\r" +
921-
"qux\u2028" +
922-
"foo\u2029" +
923-
"qux\n";
924-
const ast = espree.parse(CODE, ESPREE_CONFIG);
925-
const sourceCode = new SourceCode(CODE, ast);
926-
927-
assert.deepEqual(astUtils.getLocationFromRangeIndex(sourceCode, 5), { line: 2, column: 1 });
928-
assert.deepEqual(astUtils.getLocationFromRangeIndex(sourceCode, 3), { line: 1, column: 3 });
929-
assert.deepEqual(astUtils.getLocationFromRangeIndex(sourceCode, 4), { line: 2, column: 0 });
930-
assert.deepEqual(astUtils.getLocationFromRangeIndex(sourceCode, 21), { line: 6, column: 0 });
931-
});
932-
933-
});
934-
935-
describe("getRangeIndexFromLocation()", () => {
936-
it("should return the range index of a location", () => {
937-
const CODE =
938-
"foo\n" +
939-
"bar\r\n" +
940-
"baz\r" +
941-
"qux\u2028" +
942-
"foo\u2029" +
943-
"qux\n";
944-
const ast = espree.parse(CODE, ESPREE_CONFIG);
945-
const sourceCode = new SourceCode(CODE, ast);
946-
947-
assert.strictEqual(astUtils.getRangeIndexFromLocation(sourceCode, { line: 2, column: 1 }), 5);
948-
assert.strictEqual(astUtils.getRangeIndexFromLocation(sourceCode, { line: 1, column: 3 }), 3);
949-
assert.strictEqual(astUtils.getRangeIndexFromLocation(sourceCode, { line: 2, column: 0 }), 4);
950-
assert.strictEqual(astUtils.getRangeIndexFromLocation(sourceCode, { line: 6, column: 0 }), 21);
951-
952-
sourceCode.lines.forEach((line, index) => {
953-
assert.strictEqual(
954-
line[0],
955-
sourceCode.text[astUtils.getRangeIndexFromLocation(sourceCode, { line: index + 1, column: 0 })]
956-
);
957-
});
958-
});
959-
});
960-
961914
describe("getParenthesisedText", () => {
962915
const expectedResults = {
963916
"(((foo))); bar;": "(((foo)))",

0 commit comments

Comments
 (0)