Avoid scanning the file multiple times for newlines.
Scan the file for newlines only once, then cache these
and perform binary search to locate the line and column
information.
@@ -14,11 +14,48 @@ function util.get_file_contents(filename)
end
end
+local newline_cache = setmetatable({}, { __mode = "k" })
+
+--- Given ordered sequence `xs`, search for `v`,
+-- If `v` is not found, return the position of
+-- the lowest item `x` in `xs` such that `x > v`.
+-- @param xs An ordered sequence of comparable items
+-- @param v A value comparable to the items in the list
+-- @param min (optional) The initial position (default 1)
+-- @param max (optional) The final position (default `#xs`)
+-- @return The position of `v`, or the position of
+-- the lowest item greater than it. Inserting `v` at
+-- the returned position will always keep the sequence
+-- ordered.
+local function binary_search(xs, v, min, max)
+ min, max = min or 1, max or #xs
+ if v < xs[min] then
+ return min
+ elseif v > xs[max] then
+ return max + 1
+ end
+ local i = (min + max) // 2
+ if v < xs[i] then
+ return binary_search(xs, v, min, i - 1)
+ elseif v > xs[i] then
+ return binary_search(xs, v, i + 1, max)
+ end
+ return i
+end
+
function util.get_line_number(subject, pos)
- if pos == 1 then return 1,1 end
- local rest, new_lines = subject:sub(1,pos):gsub("[^\n]*\n", "")
- local col = #rest
- return new_lines + 1, col ~= 0 and col or 1
+ local newlines
+ if newline_cache[subject] then
+ newlines = newline_cache[subject]
+ else
+ newlines = {}
+ for n in subject:gmatch("()\n") do
+ table.insert(newlines, n)
+ end
+ newline_cache[subject] = newlines
+ end
+ local line = binary_search(newlines, pos)
+ return line, pos - (newlines[line - 1] or 0)
end
return util
