perf: improve time complexity of getLocFromIndex (#19782)

lumirlumir · web-flow · commit e39289596757 · 2025-06-02T23:17:40.000+02:00
* perf: improve `getLocFromIndex` and `getIndexFromLoc`

* wip: binary search

* wip: caching

* wip: use bitwise OR

* wip: remove cache
diff --git a/lib/languages/js/source-code/source-code.js b/lib/languages/js/source-code/source-code.js
@@ -240,6 +240,33 @@ function isSpaceBetween(sourceCode, first, second, checkInsideOfJSXText) {
 	return false;
 }
 
+/**
+ * Performs binary search to find the line number containing a given character index.
+ * Returns the lower bound - the index of the first element greater than the target.
+ * **Please note that the `lineStartIndices` should be sorted in ascending order**.
+ * - Time Complexity: O(log n) - Significantly faster than linear search for large files.
+ * @param {number[]} lineStartIndices Sorted array of line start indices.
+ * @param {number} target The character index to find the line number for.
+ * @returns {number} The 1-based line number for the target index.
+ * @private
+ */
+function findLineNumberBinarySearch(lineStartIndices, target) {
+	let low = 0;
+	let high = lineStartIndices.length;
+
+	while (low < high) {
+		const mid = ((low + high) / 2) | 0; // Use bitwise OR to floor the division
+
+		if (target < lineStartIndices[mid]) {
+			high = mid;
+		} else {
+			low = mid + 1;
+		}
+	}
+
+	return low;
+}
+
 //-----------------------------------------------------------------------------
 // Directive Comments
 //-----------------------------------------------------------------------------
@@ -721,9 +748,9 @@ class SourceCode extends TokenStore {
 
 	/**
 	 * Converts a source text index into a (line, column) pair.
-	 * @param {number} index The index of a character in a file
+	 * @param {number} index The index of a character in a file.
 	 * @throws {TypeError|RangeError} If non-numeric index or index out of range.
-	 * @returns {{line: number, column: number}} A {line, column} location object with a 0-indexed column
+	 * @returns {{line: number, column: number}} A {line, column} location object with 1-indexed line and 0-indexed column.
 	 * @public
 	 */
 	getLocFromIndex(index) {
@@ -758,7 +785,7 @@ class SourceCode extends TokenStore {
 		const lineNumber =
 			index >= this.lineStartIndices.at(-1)
 				? this.lineStartIndices.length
-				: this.lineStartIndices.findIndex(el => index < el);
+				: findLineNumberBinarySearch(this.lineStartIndices, index);
 
 		return {
 			line: lineNumber,
diff --git a/tests/lib/languages/js/source-code/source-code.js b/tests/lib/languages/js/source-code/source-code.js
@@ -2205,9 +2205,9 @@ describe("SourceCode", () => {
 		});
 
 		it("should return the location of a range index", () => {
-			assert.deepStrictEqual(sourceCode.getLocFromIndex(5), {
-				line: 2,
-				column: 1,
+			assert.deepStrictEqual(sourceCode.getLocFromIndex(0), {
+				line: 1,
+				column: 0,
 			});
 			assert.deepStrictEqual(sourceCode.getLocFromIndex(3), {
 				line: 1,
@@ -2217,6 +2217,14 @@ describe("SourceCode", () => {
 				line: 2,
 				column: 0,
 			});
+			assert.deepStrictEqual(sourceCode.getLocFromIndex(5), {
+				line: 2,
+				column: 1,
+			});
+			assert.deepStrictEqual(sourceCode.getLocFromIndex(15), {
+				line: 4,
+				column: 2,
+			});
 			assert.deepStrictEqual(sourceCode.getLocFromIndex(21), {
 				line: 6,
 				column: 0,
