diff options
Diffstat (limited to 'lua')
| -rw-r--r-- | lua/clever_f/text_topology.lua | 991 |
1 files changed, 991 insertions, 0 deletions
diff --git a/lua/clever_f/text_topology.lua b/lua/clever_f/text_topology.lua new file mode 100644 index 0000000..3b9bf0f --- /dev/null +++ b/lua/clever_f/text_topology.lua @@ -0,0 +1,991 @@ +local domain = require("clever_f.domain") + +local M = {} +local TextView = {} +local MatchStartBounds = {} +M.TextView = TextView +M.MatchStartBounds = MatchStartBounds + +local view_records = setmetatable({}, { __mode = "k" }) +local bounds_records = setmetatable({}, { __mode = "k" }) + +local function fail(message, level) + error(message, (level or 1) + 1) +end + +local function is_integer(value) + return type(value) == "number" + and value > -math.huge + and value < math.huge + and value == math.floor(value) +end + +local function require_nonempty_string(value, name) + if type(value) ~= "string" or value == "" then + fail((name or "value") .. " must be a nonempty string", 2) + end + return value +end + +local function canonical_encoding(encoding) + encoding = require_nonempty_string(encoding, "effective encoding"):lower() + encoding = encoding:gsub("_", "-") + + local aliases = { + ["utf8"] = "utf-8", + ["cp-932"] = "cp932", + ["932"] = "cp932", + ["windows-31j"] = "cp932", + ["eucjp"] = "euc-jp", + ["ujis"] = "euc-jp", + ["unix-jis"] = "euc-jp", + } + return aliases[encoding] or encoding +end + +M.normalize_encoding = canonical_encoding + +local function utf8_character_length(text, offset) + local first = text:byte(offset) + if first == nil then + return nil + end + if first < 0x80 then + return 1 + end + + local length + local minimum + if first >= 0xc2 and first <= 0xdf then + length = 2 + minimum = 0x80 + elseif first >= 0xe0 and first <= 0xef then + length = 3 + minimum = 0x800 + elseif first >= 0xf0 and first <= 0xf4 then + length = 4 + minimum = 0x10000 + else + fail("text contains an invalid UTF-8 character", 3) + end + + if offset + length - 1 > #text then + fail("text contains an incomplete UTF-8 character", 3) + end + + local codepoint = first % (2 ^ (8 - length - 1)) + for index = offset + 1, offset + length - 1 do + local byte = text:byte(index) + if byte < 0x80 or byte > 0xbf then + fail("text contains an invalid UTF-8 character", 3) + end + codepoint = codepoint * 0x40 + (byte - 0x80) + end + + if codepoint < minimum + or codepoint > 0x10ffff + or (codepoint >= 0xd800 and codepoint <= 0xdfff) + then + fail("text contains an invalid UTF-8 character", 3) + end + return length +end + +local function split_utf8_codepoints(text) + local characters = {} + local offset = 1 + while offset <= #text do + local length = utf8_character_length(text, offset) + characters[#characters + 1] = text:sub(offset, offset + length - 1) + offset = offset + length + end + return characters +end + +local function nvim_split_segment(segment, result) + if segment == "" then + return + end + + local count = vim.fn.strchars(segment, true) + for character_index = 0, count - 1 do + local first = vim.fn.byteidx(segment, character_index) + local following = vim.fn.byteidx(segment, character_index + 1) + if first < 0 or following <= first then + fail("Nvim could not index an editor character", 3) + end + result[#result + 1] = segment:sub(first + 1, following) + end +end + +local function default_split_editor_characters(text) + local runtime = rawget(_G, "vim") + if type(runtime) ~= "table" + or type(runtime.fn) ~= "table" + or type(runtime.fn.strchars) ~= "function" + or type(runtime.fn.byteidx) ~= "function" + then + return split_utf8_codepoints(text) + end + + local result = {} + local offset = 1 + while offset <= #text do + local nul = text:find("\0", offset, true) + local last = nul and (nul - 1) or #text + nvim_split_segment(text:sub(offset, last), result) + if nul == nil then + break + end + result[#result + 1] = "\0" + offset = nul + 1 + end + return result +end + +local function default_encode(text, encoding) + if encoding == "utf-8" then + return text + end + + local runtime = rawget(_G, "vim") + if type(runtime) ~= "table" or type(runtime.iconv) ~= "function" then + fail("text encoding conversion requires Nvim or an encoder", 3) + end + + local ok, encoded = pcall(runtime.iconv, text, "utf-8", encoding) + if not ok or encoded == nil then + fail("text could not be converted to " .. encoding, 3) + end + return encoded +end + +local function require_character_list(characters) + if type(characters) ~= "table" then + fail("editor character splitter must return a list", 3) + end + + local result = {} + local item_count = 0 + for key, character in pairs(characters) do + if not is_integer(key) or key < 1 or key > #characters then + fail("editor character splitter must return a list", 3) + end + if type(character) ~= "string" or character == "" then + fail("editor character splitter must return nonempty strings", 3) + end + result[key] = character + item_count = item_count + 1 + end + if item_count ~= #characters then + fail("editor character splitter must return a list", 3) + end + return result +end + +local function snapshot_value(text) + if domain.TextSnapshot.is(text) then + return text + end + if type(text) == "table" and text.lines ~= nil then + text = text.lines + end + return domain.TextSnapshot.new(text) +end + +local function require_options(options) + if options == nil then + return {} + end + if type(options) == "function" then + return { encoder = options } + end + if type(options) ~= "table" then + fail("TextView options must be a table", 2) + end + return options +end + +local function selected_function(options, primary, alternate, fallback) + local value = options[primary] + if value == nil and alternate ~= nil then + value = options[alternate] + end + if value == nil then + return fallback + end + if type(value) ~= "function" then + fail("TextView " .. primary .. " must be a function", 3) + end + return value +end + +local function index_line(text, encoding, splitter, encoder) + if text:find("\n", 1, true) ~= nil then + fail("a text snapshot line must not contain a newline", 3) + end + + local characters = require_character_list(splitter(text)) + if table.concat(characters) ~= text then + fail("editor character splitter must preserve the complete line", 3) + end + + local entries = {} + local starts = {} + local by_start = {} + local encoded_parts = {} + local next_column = 1 + + for index, character in ipairs(characters) do + local encoded = encoder(character, encoding) + if type(encoded) ~= "string" or encoded == "" then + fail("TextView encoder must return a nonempty byte string", 3) + end + + local byte_length = #encoded + local entry = { + character = character, + encoded = encoded, + byte_start = next_column, + byte_end = next_column + byte_length - 1, + byte_length = byte_length, + } + entries[index] = entry + starts[index] = next_column + by_start[next_column] = index + encoded_parts[index] = encoded + next_column = next_column + byte_length + end + + return { + text = text, + encoded = table.concat(encoded_parts), + entries = entries, + starts = starts, + by_start = by_start, + byte_length = next_column - 1, + character_count = #entries, + } +end + +local text_view_metatable = { + __index = function(view, key) + local method = TextView[key] + if method ~= nil then + return method + end + + local record = view_records[view] + if key == "encoding" or key == "effective_encoding" then + return record.encoding + end + if key == "requested_encoding" then + return record.requested_encoding + end + if key == "line_count" then + return record.snapshot.line_count + end + return nil + end, + __newindex = function() + fail("TextView values are immutable", 2) + end, + __tostring = function(view) + local record = view_records[view] + return "text-view:" .. record.encoding .. ":" .. tostring(record.snapshot.line_count) + end, + __metatable = "clever_f.text_topology.TextView", +} + +function TextView.new(text, effective_encoding, options) + if TextView.is(text) and effective_encoding == nil and options == nil then + return text + end + + local snapshot = snapshot_value(text) + local requested_encoding = require_nonempty_string( + effective_encoding, + "effective encoding" + ) + local encoding = canonical_encoding(requested_encoding) + options = require_options(options) + local splitter = selected_function( + options, + "splitter", + "split_editor_characters", + default_split_editor_characters + ) + local encoder = selected_function(options, "encoder", "encode", default_encode) + + local lines = {} + for line_number = 1, snapshot.line_count do + lines[line_number] = index_line( + snapshot:line(line_number), + encoding, + splitter, + encoder + ) + end + + local view = setmetatable({}, text_view_metatable) + view_records[view] = { + snapshot = snapshot, + requested_encoding = requested_encoding, + encoding = encoding, + lines = lines, + } + return view +end + +function TextView.from_host(host, options) + if type(host) ~= "table" + or type(host.read_text) ~= "function" + or type(host.read_encoding) ~= "function" + then + fail("TextView host must provide read_text and read_encoding", 2) + end + local text = host:read_text() + local encoding = host:read_encoding() + return TextView.new(text, encoding, options) +end + +function TextView.is(value) + return type(value) == "table" and view_records[value] ~= nil +end + +local function view_record(view) + if not TextView.is(view) then + fail("value must be a TextView", 3) + end + return view_records[view] +end + +local function line_record(view, line_number) + local record = view_record(view) + if not is_integer(line_number) + or line_number < 1 + or line_number > record.snapshot.line_count + then + fail("line_number must identify a line in the TextView", 3) + end + return record.lines[line_number] +end + +local function require_character_index(line, character_index) + if not is_integer(character_index) + or character_index < 1 + or character_index > line.character_count + then + fail("character_index must identify an editor character", 3) + end + return character_index +end + +local function require_byte_column(byte_column) + if not is_integer(byte_column) or byte_column < 1 then + fail("byte_column must be a positive one-based integer", 3) + end + return byte_column +end + +local function position_arguments(position_or_line, byte_column, name) + if byte_column == nil then + local position = domain.Position.coerce(position_or_line) + return position.line, position.byte_column + end + if not is_integer(position_or_line) or position_or_line < 1 then + fail((name or "line_number") .. " must be a positive integer", 3) + end + return position_or_line, require_byte_column(byte_column) +end + +function TextView:text_snapshot() + return view_record(self).snapshot +end + +function TextView:line_text(line_number) + return line_record(self, line_number).text +end + +function TextView:line_encoded_text(line_number) + return line_record(self, line_number).encoded +end + +function TextView:line_byte_length(line_number) + return line_record(self, line_number).byte_length +end + +function TextView:line_character_count(line_number) + return line_record(self, line_number).character_count +end + +function TextView:line_is_empty(line_number) + return self:line_character_count(line_number) == 0 +end + +function TextView:character_at_index(line_number, character_index) + local line = line_record(self, line_number) + require_character_index(line, character_index) + return line.entries[character_index].character +end + +function TextView:encoded_character_at_index(line_number, character_index) + local line = line_record(self, line_number) + require_character_index(line, character_index) + return line.entries[character_index].encoded +end + +function TextView:byte_column_for_character_index(line_number, character_index) + local line = line_record(self, line_number) + require_character_index(line, character_index) + return line.starts[character_index] +end + +function TextView:position_for_character_index(line_number, character_index) + return domain.Position.new( + line_number, + self:byte_column_for_character_index(line_number, character_index) + ) +end + +function TextView:try_character_index_for_byte_column(line_number, byte_column) + local line = line_record(self, line_number) + require_byte_column(byte_column) + return line.by_start[byte_column] +end + +function TextView:character_index_for_byte_column(line_number, byte_column) + local line = line_record(self, line_number) + require_byte_column(byte_column) + local character_index = line.by_start[byte_column] + if character_index == nil then + if byte_column <= line.byte_length then + fail("byte_column points inside an editor character", 2) + end + fail("byte_column does not identify an editor character", 2) + end + return character_index +end + +function TextView:character_index_for_position(position) + position = domain.Position.coerce(position) + return self:character_index_for_byte_column(position.line, position.byte_column) +end + +local function copy_span(line_number, character_index, entry) + local position = domain.Position.new(line_number, entry.byte_start) + return { + line = line_number, + character_index = character_index, + character = entry.character, + encoded = entry.encoded, + position = position, + byte_column = entry.byte_start, + byte_start = entry.byte_start, + byte_end = entry.byte_end, + start_byte_column = entry.byte_start, + end_byte_column = entry.byte_end, + byte_length = entry.byte_length, + } +end + +function TextView:byte_span_for_character_index(line_number, character_index) + local line = line_record(self, line_number) + require_character_index(line, character_index) + return copy_span(line_number, character_index, line.entries[character_index]) +end + +function TextView:byte_span_at(position_or_line, byte_column) + local line_number, column = position_arguments(position_or_line, byte_column) + local character_index = self:character_index_for_byte_column(line_number, column) + return self:byte_span_for_character_index(line_number, character_index) +end + +function TextView:character_at(position_or_line, byte_column) + local line_number, column = position_arguments(position_or_line, byte_column) + local character_index = self:character_index_for_byte_column(line_number, column) + return self:character_at_index(line_number, character_index) +end + +function TextView:is_character_start(position_or_line, byte_column) + local line_number, column = position_arguments(position_or_line, byte_column) + local record = view_record(self) + if line_number > record.snapshot.line_count then + return false + end + return record.lines[line_number].by_start[column] ~= nil +end + +function TextView:is_valid_cursor_position(position_or_line, byte_column) + local line_number, column = position_arguments(position_or_line, byte_column) + local record = view_record(self) + if line_number > record.snapshot.line_count then + return false + end + local line = record.lines[line_number] + if line.character_count == 0 then + return column == 1 + end + return line.by_start[column] ~= nil +end + +local function containing_character_index(line, byte_column) + for index = 1, line.character_count do + local entry = line.entries[index] + if byte_column >= entry.byte_start and byte_column <= entry.byte_end then + return index + end + end + return nil +end + +function TextView:normalize_endpoint(position_or_line, byte_column) + local line_number, column = position_arguments(position_or_line, byte_column) + local line = line_record(self, line_number) + if line.character_count == 0 then + return domain.Position.new(line_number, 1) + end + + if column > line.byte_length then + return self:position_for_character_index(line_number, line.character_count) + end + + local character_index = line.by_start[column] + or containing_character_index(line, column) + return self:position_for_character_index(line_number, character_index) +end + +local function first_cursor_position(view, line_number) + local line = line_record(view, line_number) + if line.character_count == 0 then + return domain.Position.new(line_number, 1) + end + return view:position_for_character_index(line_number, 1) +end + +local function last_cursor_position(view, line_number) + local line = line_record(view, line_number) + if line.character_count == 0 then + return domain.Position.new(line_number, 1) + end + return view:position_for_character_index(line_number, line.character_count) +end + +function TextView:first_cursor_position(line_number) + return first_cursor_position(self, line_number) +end + +function TextView:last_cursor_position(line_number) + return last_cursor_position(self, line_number) +end + +function TextView:predecessor(position) + position = domain.Position.coerce(position) + local line = line_record(self, position.line) + + if line.character_count > 0 then + local character_index = self:character_index_for_byte_column( + position.line, + position.byte_column + ) + if character_index > 1 then + return self:position_for_character_index(position.line, character_index - 1) + end + elseif position.byte_column ~= 1 then + fail("an empty line cursor position must use byte column one", 2) + end + + if position.line == 1 then + return nil + end + return last_cursor_position(self, position.line - 1) +end + +function TextView:successor(position) + position = domain.Position.coerce(position) + local record = view_record(self) + local line = line_record(self, position.line) + + if line.character_count > 0 then + local character_index = self:character_index_for_byte_column( + position.line, + position.byte_column + ) + if character_index < line.character_count then + return self:position_for_character_index(position.line, character_index + 1) + end + elseif position.byte_column ~= 1 then + fail("an empty line cursor position must use byte column one", 2) + end + + if position.line == record.snapshot.line_count then + return nil + end + return first_cursor_position(self, position.line + 1) +end + +local bounds_metatable = { + __index = function(bounds, key) + local method = MatchStartBounds[key] + if method ~= nil then + return method + end + return bounds_records[bounds][key] + end, + __newindex = function() + fail("MatchStartBounds values are immutable", 2) + end, + __tostring = function(bounds) + local record = bounds_records[bounds] + if record.empty then + return "match-start-bounds:empty" + end + return "match-start-bounds:" .. tostring(record.first) .. ":" .. tostring(record.last) + end, + __metatable = "clever_f.text_topology.MatchStartBounds", +} + +local function new_bounds(scope, first_line, last_line, first, last) + local bounds = setmetatable({}, bounds_metatable) + bounds_records[bounds] = { + scope = scope, + first_line = first_line, + last_line = last_line, + first = first, + last = last, + start = first, + finish = last, + empty = first == nil, + } + return bounds +end + +function MatchStartBounds.is(value) + return type(value) == "table" and bounds_records[value] ~= nil +end + +function MatchStartBounds:is_empty() + return bounds_records[self].empty +end + +function MatchStartBounds:contains(position) + position = domain.Position.coerce(position) + local record = bounds_records[self] + if record.empty then + return false + end + return domain.Position.compare(position, record.first) >= 0 + and domain.Position.compare(position, record.last) <= 0 +end + +function MatchStartBounds:to_table() + local record = bounds_records[self] + return { + scope = record.scope.value, + first_line = record.first_line, + last_line = record.last_line, + first = record.first and record.first:to_table() or nil, + last = record.last and record.last:to_table() or nil, + empty = record.empty, + } +end + +function TextView:line_match_start_bounds(line_number) + local line = line_record(self, line_number) + local first + local last + if line.character_count > 0 then + first = self:position_for_character_index(line_number, 1) + last = self:position_for_character_index(line_number, line.character_count) + end + return new_bounds( + domain.SearchScope.CURRENT_LINE, + line_number, + line_number, + first, + last + ) +end + +function TextView:buffer_match_start_bounds() + local record = view_record(self) + local first + local last + + for line_number = 1, record.snapshot.line_count do + local line = record.lines[line_number] + if line.character_count > 0 then + first = self:position_for_character_index(line_number, 1) + break + end + end + + for line_number = record.snapshot.line_count, 1, -1 do + local line = record.lines[line_number] + if line.character_count > 0 then + last = self:position_for_character_index(line_number, line.character_count) + break + end + end + + return new_bounds( + domain.SearchScope.BUFFER, + 1, + record.snapshot.line_count, + first, + last + ) +end + +local function scope_value(scope) + if scope == nil then + return domain.SearchScope.BUFFER + end + if scope == "line" then + return domain.SearchScope.CURRENT_LINE + end + return domain.SearchScope.from_string(scope) +end + +function TextView:match_start_bounds(scope, origin) + if domain.Position.is(scope) + or type(scope) == "number" + or (type(scope) == "table" and scope.line ~= nil) + then + scope, origin = origin, scope + end + + scope = scope_value(scope) + if scope == domain.SearchScope.BUFFER then + return self:buffer_match_start_bounds() + end + + if origin == nil then + fail("current-line match bounds require an origin line", 2) + end + local line_number = type(origin) == "number" + and origin + or domain.Position.coerce(origin).line + return self:line_match_start_bounds(line_number) +end + +local function empty_iterator() + return nil +end + +local function iteration_endpoint(view, position, name) + position = domain.Position.coerce(position) + if not view:is_character_start(position) then + fail((name or "iterator endpoint") .. " must start an editor character", 3) + end + return position +end + +local function step_character(view, position, direction) + local record = view_record(view) + local line = record.lines[position.line] + local character_index = line.by_start[position.byte_column] + + if direction == domain.Direction.FORWARD then + if character_index < line.character_count then + return view:position_for_character_index(position.line, character_index + 1) + end + for line_number = position.line + 1, record.snapshot.line_count do + if record.lines[line_number].character_count > 0 then + return view:position_for_character_index(line_number, 1) + end + end + return nil + end + + if character_index > 1 then + return view:position_for_character_index(position.line, character_index - 1) + end + for line_number = position.line - 1, 1, -1 do + local previous_line = record.lines[line_number] + if previous_line.character_count > 0 then + return view:position_for_character_index( + line_number, + previous_line.character_count + ) + end + end + return nil +end + +local function position_iterator(view, direction, start_position, boundary) + if start_position == nil then + return empty_iterator + end + + start_position = iteration_endpoint(view, start_position, "iterator start") + boundary = iteration_endpoint(view, boundary, "iterator boundary") + local comparison = domain.Position.compare(start_position, boundary) + if direction == domain.Direction.FORWARD and comparison > 0 then + fail("a forward iterator start must not follow its boundary", 3) + end + if direction == domain.Direction.BACKWARD and comparison < 0 then + fail("a backward iterator start must not precede its boundary", 3) + end + + local current = start_position + local finished = false + return function() + if finished then + return nil + end + + local position = current + local character_index = view:character_index_for_position(position) + local character = view:character_at_index(position.line, character_index) + local span = view:byte_span_for_character_index(position.line, character_index) + + if position == boundary then + finished = true + else + current = step_character(view, position, direction) + if current == nil then + fail("iterator reached the text boundary before its selected boundary", 2) + end + end + return position, character, span + end +end + +local function iteration_arguments(view, direction, first, second) + if MatchStartBounds.is(first) then + local record = bounds_records[first] + if record.empty then + return nil, nil + end + if direction == domain.Direction.FORWARD then + return record.first, record.last + end + return record.last, record.first + end + + if type(first) == "number" and second == nil then + local bounds = view:line_match_start_bounds(first) + return iteration_arguments(view, direction, bounds) + end + + if first == nil then + local bounds = view:buffer_match_start_bounds() + return iteration_arguments(view, direction, bounds) + end + + first = domain.Position.coerce(first) + if second ~= nil then + return first, domain.Position.coerce(second) + end + + local bounds = view:buffer_match_start_bounds() + if bounds.empty then + return nil, nil + end + return first, direction == domain.Direction.FORWARD and bounds.last or bounds.first +end + +function TextView:iterate(direction, first, second) + direction = domain.Direction.from_string(direction) + local start_position, boundary = iteration_arguments(self, direction, first, second) + return position_iterator(self, direction, start_position, boundary) +end + +function TextView:iter_forward(first, boundary) + return self:iterate(domain.Direction.FORWARD, first, boundary) +end + +function TextView:iter_backward(first, boundary) + return self:iterate(domain.Direction.BACKWARD, first, boundary) +end + +function TextView:iter_line_forward(line_number) + return self:iter_forward(self:line_match_start_bounds(line_number)) +end + +function TextView:iter_line_backward(line_number) + return self:iter_backward(self:line_match_start_bounds(line_number)) +end + +function TextView:iter_buffer_forward() + return self:iter_forward(self:buffer_match_start_bounds()) +end + +function TextView:iter_buffer_backward() + return self:iter_backward(self:buffer_match_start_bounds()) +end + +local function strict_scope_bounds(view, origin, scope_or_bounds) + if MatchStartBounds.is(scope_or_bounds) then + return scope_or_bounds + end + local scope = scope_value(scope_or_bounds) + return view:match_start_bounds(scope, origin) +end + +function TextView:iter_strict(origin, direction, scope_or_bounds) + origin = domain.Position.coerce(origin) + line_record(self, origin.line) + if not self:is_valid_cursor_position(origin) then + fail("strict iterator origin must be a valid editor cursor position", 2) + end + + direction = domain.Direction.from_string(direction) + local bounds = strict_scope_bounds(self, origin, scope_or_bounds) + local candidates = self:iterate(direction, bounds) + + return function() + while true do + local position, character, span = candidates() + if position == nil then + return nil + end + local comparison = domain.Position.compare(position, origin) + if (direction == domain.Direction.FORWARD and comparison > 0) + or (direction == domain.Direction.BACKWARD and comparison < 0) + then + return position, character, span + end + end + end +end + +function TextView:iter_strict_forward(origin, scope_or_bounds) + return self:iter_strict(origin, domain.Direction.FORWARD, scope_or_bounds) +end + +function TextView:iter_strict_backward(origin, scope_or_bounds) + return self:iter_strict(origin, domain.Direction.BACKWARD, scope_or_bounds) +end + +TextView.character_index_to_byte_column = TextView.byte_column_for_character_index +TextView.byte_column_to_character_index = TextView.character_index_for_byte_column +TextView.character_count = TextView.line_character_count +TextView.byte_length = TextView.line_byte_length +TextView.character_span = TextView.byte_span_for_character_index +TextView.predecessor_endpoint = TextView.predecessor +TextView.successor_endpoint = TextView.successor +TextView.normalize_boundary_endpoint = TextView.normalize_endpoint +TextView.bounds_for_line = TextView.line_match_start_bounds +TextView.bounds_for_buffer = TextView.buffer_match_start_bounds +TextView.iterate_forward = TextView.iter_forward +TextView.iterate_backward = TextView.iter_backward +TextView.forward = TextView.iter_forward +TextView.backward = TextView.iter_backward +TextView.strict_forward = TextView.iter_strict_forward +TextView.strict_backward = TextView.iter_strict_backward + +function M.new(text, effective_encoding, options) + return TextView.new(text, effective_encoding, options) +end + +function M.from_host(host, options) + return TextView.from_host(host, options) +end + +M.build = M.new +M.build_from_host = M.from_host +M.is = TextView.is + +return M |