migrate to 12.0

[ta-parkour.git] / parkour / node.lua

-- SPDX-License-Identifier: GPL-3.0-or-later
-- © 2020 Georgi Kirilov

require'lpeg'
local l = lpeg
local P, S, V, Cc, Cmt, Cp, Ct = l.P, l.S, l.V, l.Cc, l.Cmt, l.Cp, l.Ct

local hspace = S" \t"
local newline = S"\n\r"
local function past(_, position, pos) return position <= pos end

local M = {}

local function startof(node) return node.start end
local function finishof(node) return node.finish end

function M.new(read)

local function at_pos(_, position, start, finish, range)
        if range.start + 1 >= start and range.start < finish and range.finish < finish then
                return position, start - 1, finish - 1
        end
end

local function gt(pos, val)
        return val and pos > val
end

local function le(pos, val)
        return val and pos <= val
end

-- binary search a list for the nearest node before pos
local function before(t, pos, key, skip)
        local left, right = 1, #t
        while left <= right do
                local m = math.floor(left + (right - left) / 2)
                local m_val = key(t[m])
                if gt(pos, m_val) and (m == #t or le(pos, key(t[m + 1]))) then
                        if skip then
                                while (t[m] and skip(t[m])) do
                                        m = m - 1
                                end
                        end
                        return t[m], m
                end
                if le(pos, m_val) then right = m - 1 else left = m + 1 end
        end
end

-- binary search a list for the nearest node after pos
local function after(t, pos, key, skip)
        if t.is_root and (#t == 0 or pos >= t[#t].start) then
                -- XXX: if we are at the last parsed top-level node, try to access the next one
                -- to get it parsed as well. Otherwise the search will stop prematurely.
                local _ = t[#t + 1]
        end
        local left, right = 1, #t
        while left <= right do
                local m = math.floor(left + (right - left) / 2)
                local m_val = key(t[m])
                if le(pos, m_val) and (m == 1 or gt(pos, key(t[m - 1]))) then
                        if skip then
                                while (t[m] and skip(t[m])) do
                                        m = m + 1
                                end
                        end
                        return t[m], m
                end
                if le(pos, m_val) then right = m - 1 else left = m + 1 end
        end
end

-- binary search a list for the node that contains pos
local function around(t, range)
        if not (range.start and range.finish) then return end
        local left, right = 1, #t
        while left <= right do
                local m = math.floor(left + (right - left) / 2)
                local e = t[m]
                local nxt = t[m + 1]
                if e.start and range.start >= e.start and e.finish and range.finish <= e.finish + 1 and
                        (not nxt or nxt.start > range.start) -- if adjoined - asdf|(qwer) - this will prefer (qwer)
                        then return e, m end
                if e.start and range.start < e.start then right = m - 1 else left = m + 1 end
        end
end

local function find_after(t, selection, pred, stop)
        local _, n = t.after(selection.start, startof)
        while t[n] do
                if pred(t[n]) then return t[n], n
                elseif stop and stop(t[n]) then return end
                n = n + 1
        end
end

local function find_before(t, selection, pred, stop)
        local _, n = t.before(selection.finish, finishof)
        while t[n] do
                if pred(t[n]) then return t[n], n
                elseif stop and stop(t[n]) then return end
                n = n - 1
        end
end

local function intersects(t, range)
        local start = t.start + (t.p and #t.p or 0)
        return start >= range.start and t.finish >= range.finish and start < range.finish
                or start < range.start and t.finish < range.finish and range.start <= t.finish
end

local function touches(t, range)
        return t.start + (t.p and #t.p or 0) >= range.start and t.start <= range.start or t.finish == range.finish - 1
end

local function contains(t, range)
        if t.is_list then
                return t.start + (t.p and #t.p or 0) < range.start and t.finish > range.finish - 1
        else
                return t.start <= range.start and t.finish >= range.finish - 1
        end
end

local function sexp_around(t, range)
        if t.is_root or (t.is_list and contains(t, range)) then
                local child, nth = t.around(range)
                if child and child.is_list and not touches(child, range) then
                        return sexp_around(child, range)
                else
                        return child, t, nth
                end
        end
end

-- save the current logical position in terms of sexps, not offsets
local function _sexp_path(t, range, indices, nodes)
        if t.is_root or (t.is_list and contains(t, range)) then
                local child, nth = t.around(range)
                table.insert(indices, nth)
                table.insert(nodes, child)
                if child and child.is_list and not touches(child, range) then
                        _sexp_path(child, range, indices, nodes)
                elseif not child then
                        table.insert(indices, false)
                        table.insert(nodes, false)
                end
        end
        return indices, nodes
end

local function sexp_path(t, range)
        return _sexp_path(t, range, {}, {})
end

-- find a sexp by following a previously-saved "sexp path"
local function goto_path(root, path)
        local dest = root
        local parent, nth
        for n, i in ipairs(path) do
                dest = dest[i]
                nth = i
                parent = not parent and root or parent[path[n - 1]]
        end
        return dest, parent, nth
end

local function catchup(tree, range)
        if range.finish and range.finish >= tree.first_invalid then
                tree.parse_to(range.finish + 1)
        end
end

local function ensure_reparse(func)
        return function(t)
                return function(range, ...)
                        -- TODO: get rid of this type check. It is here because .after and .before take pos, not range
                        catchup(t, type(range) == "number" and {finish = range} or range)
                        return func(t, range, ...)
                end
        end
end

local root_methods = {
        around = around,
        before = before,
        after = after,
        find_after = find_after,
        find_before = find_before,
        sexp_at = sexp_around,
        sexp_path = sexp_path,
}

local function bind(func)
        return function(t)
                return function(...)
                        return func(t, ...)
                end
        end
end

local list_methods = {
        is_list = function(_) return true end,
        is_empty = function(t) return #t == 0 end,
        around = bind(around),
        before = bind(before),
        after = bind(after),
        find_after = bind(find_after),
        find_before = bind(find_before),
}

local atom_methods = {}

local quasiatom_methods = {}  -- "quasi atom" is a word inside a string or comment

local function text(t)
        local len = t.finish + 1 - t.start
        return read(t.start, len)
end

atom_methods.text = text
list_methods.text = text
quasiatom_methods.text = text

local function dispatch(vtable)
        return function(self, key)
                if vtable[key] then
                        return vtable[key](self)
                end
        end
end

local quasiatom_node = {
        __index = dispatch(quasiatom_methods)
}

local quasilist_methods = (function(word)  -- "quasi list" is a string or comment
        return {
                start_before = function(t, pos)
                        local base = t.start + #t.d + (t.p and #t.p or 0)
                        local stops = P{Ct(((1 - word)^0 * Cp() * Cmt(Cc(pos - base), past) * word)^0)}:match(t.itext)
                        local newpos = stops and stops[#stops]
                        return newpos and (base + newpos - 1)
                end,

                start_after = function(t, pos)
                        local base = t.start + #t.d + (t.p and #t.p or 0)
                        if pos >= base then
                                local stop = P{(1 - word) * Cp() * word + 1 * V(1)}:match(t.itext, pos - base + 1)
                                return stop and (base + stop - 1)
                        else
                                local stop = P{(1 - word)^1 * Cp() * word}:match(t.itext)
                                return stop and (base + stop - 1) or base
                        end
                end,

                finish_before = function(t, pos)
                        local base = t.start + #t.d + (t.p and #t.p or 0)
                        local stops = P{Ct(((1 - word)^0 * word * Cp() * Cmt(Cc(pos - base), past))^0)}:match(t.itext)
                        local newpos = stops and stops[#stops]
                        return newpos and (base + newpos - 1)
                end,

                finish_after = function(t, pos)
                        local base = t.start + #t.d + (t.p and #t.p or 0)
                        local stop = P{word * Cp() + 1 * V(1)}:match(t.itext, (pos > base and pos - base + 1 or nil))
                        return stop and (base + stop - 1)
                end,

                word_at = function(t, range)
                        local r = {}
                        local base = t.start + #t.d + (t.p and #t.p or 0)
                        r.start = range.start - base
                        r.finish = range.finish - base
                        local start, finish = P{Cmt(Cp() * word * Cp() * Cc(r), at_pos) +
                        Cmt(1 * Cc(r.finish + 1), past) * V(1)}:match(t.itext)
                        if not start then return end
                        local node = {start = base + start, finish = base + finish - 1}
                        return setmetatable(node, quasiatom_node)
                end,

                spaces_after = function(t, pos)
                        local base = t.start + #t.d + (t.p and #t.p or 0)
                        if pos >= base then
                                local stop = P{(hspace + newline)^1 * Cp()}:match(t.itext, pos - base + 1)
                                return stop and (base + stop - 1)
                        end
                end,

                spaces_before = function(t, pos)
                        local base = t.start + #t.d + (t.p and #t.p or 0)
                        local stops = P{Ct(((1 - word)^0 * word * Cp() * Cmt(Cc(pos - base), past))^0) * (hspace + newline)^1}:match(t.itext)
                        local newpos = stops and stops[#stops]
                        return newpos and (base + newpos - 1)
                end,
        }
end)(P{"\\" * P(1 - hspace - newline) + P(1 - hspace - newline)^1})

local function quasilist_is_empty(t)
        return not t.finish_after(t.start + (t.p and #t.p or 0) + #t.d)
end

local function quasilist_new(opposite)
        local methods = {}
        for k, v in pairs(quasilist_methods) do
                methods[k] = bind(v)
        end
        methods.is_empty = quasilist_is_empty
        methods.text = text
        function methods.itext(t)
                local start = t.start + (t.p and #t.p or 0) + #t.d
                local len = t.finish + 1 - #opposite[t.d] - start
                return read(start, len) or ""
        end

        local quasilist_node = {
                __index = dispatch(methods)
        }

        return quasilist_node
end

local atom_node = {
        __index = dispatch(atom_methods)
}

local list_node = {
        __index = dispatch(list_methods)
}

local function root_rewind(t)
        return function(index)
                assert(index <= t.first_invalid, ("%d > %d - You can only rewind backwards!"):format(index, t.first_invalid))
                t.first_invalid = index
        end
end

local function root_is_parsed(t)
        return function(index)
                return index < t.first_invalid
        end
end

local function root_goto_path(t)
        return function(path)
                local range = {start = t[path[1]].finish, finish = t[path[1]].finish}
                catchup(t, range)
                return goto_path(t, path)
        end
end

local function root_new(opposite)
        local methods = {}
        for k, v in pairs(root_methods) do
                methods[k] = ensure_reparse(v)
        end

        methods.rewind = root_rewind
        methods.is_parsed = root_is_parsed
        methods.goto_path = root_goto_path

        local function unbalanced_delimiters(t, range)
                if t.d or t.is_root then
                        for i = 1, #t do
                                if t[i].d and (contains(t[i], range) or intersects(t[i], range)) then
                                        unbalanced_delimiters(t[i], range)
                                end
                        end
                        if not t.is_root then
                                local start = t.start + (t.p and #t.p or 0) + #t.d
                                local finish = t.finish + 1 - #opposite[t.d]
                                if start <= range.start and finish < range.finish then
                                        coroutine.yield({start = finish, finish = math.min(t.finish + 1, range.finish), closing = true})
                                elseif start > range.start and t.finish >= range.finish then
                                        coroutine.yield({start = math.max(range.start, t.start), finish = start, opening = true})
                                end
                        end
                end
        end

        function methods.unbalanced_delimiters(t)
                local slice_at = coroutine.wrap(unbalanced_delimiters)
                return function(range)
                        local skips = {}
                        catchup(t, range)
                        repeat
                                local slice_pos = slice_at(t, range)
                                if slice_pos then table.insert(skips, slice_pos) end
                        until not slice_pos
                        return skips
                end
        end

        return methods
end

return {
        atom = atom_node,
        list = list_node,
        quasilist = quasilist_new,
        root = root_new,
        _before = before,
        _around = around,
}

end

return M