path: root/vendor/lpeglj/lpcode.lua

--[[
LPEGLJ
lpcode.lua
Generating code from tree
Copyright (C) 2014 Rostislav Sacek.
based on LPeg v1.0 - PEG pattern matching for Lua
Lua.org & PUC-Rio  written by Roberto Ierusalimschy
http://www.inf.puc-rio.br/~roberto/lpeg/

** Permission is hereby granted, free of charge, to any person obtaining
** a copy of this software and associated documentation files (the
** "Software"), to deal in the Software without restriction, including
** without limitation the rights to use, copy, modify, merge, publish,
** distribute, sublicense, and/or sell copies of the Software, and to
** permit persons to whom the Software is furnished to do so, subject to
** the following conditions:
**
** The above copyright notice and this permission notice shall be
** included in all copies or substantial portions of the Software.
**
** THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
** EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
** MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
** IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
** CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
** TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
** SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
**
** [ MIT license: http://www.opensource.org/licenses/mit-license.php ]
--]]
local ffi = require "ffi"
require "lpvm"

local band, bor, bnot, rshift, lshift = bit.band, bit.bor, bit.bnot, bit.rshift, bit.lshift

local TChar = 0
local TSet = 1
local TAny = 2 -- standard PEG elements
local TTrue = 3
local TFalse = 4
local TRep = 5
local TSeq = 6
local TChoice = 7
local TNot = 8
local TAnd = 9
local TCall = 10
local TOpenCall = 11
local TRule = 12 -- sib1 is rule's pattern, sib2 is 'next' rule
local TGrammar = 13 -- sib1 is initial (and first) rule
local TBehind = 14 -- match behind
local TCapture = 15 -- regular capture
local TRunTime = 16 -- run-time capture


local IAny = 0 -- if no char, fail
local IChar = 1 -- if char != val, fail
local ISet = 2 -- if char not in val, fail
local ITestAny = 3 -- in no char, jump to 'offset'
local ITestChar = 4 -- if char != val, jump to 'offset'
local ITestSet = 5 -- if char not in val, jump to 'offset'
local ISpan = 6 -- read a span of chars in val
local IBehind = 7 -- walk back 'val' characters (fail if not possible)
local IRet = 8 -- return from a rule
local IEnd = 9 -- end of pattern
local IChoice = 10 -- stack a choice; next fail will jump to 'offset'
local IJmp = 11 -- jump to 'offset'
local ICall = 12 -- call rule at 'offset'
local IOpenCall = 13 -- call rule number 'offset' (must be closed to a ICall)
local ICommit = 14 -- pop choice and jump to 'offset'
local IPartialCommit = 15 -- update top choice to current position and jump
local IBackCommit = 16 -- "fails" but jump to its own 'offset'
local IFailTwice = 17 -- pop one choice and then fail
local IFail = 18 -- go back to saved state on choice and jump to saved offset
local IGiveup = 19 -- internal use
local IFullCapture = 20 -- complete capture of last 'off' chars
local IOpenCapture = 21 -- start a capture
local ICloseCapture = 22
local ICloseRunTime = 23


local Cclose = 0
local Cposition = 1
local Cconst = 2
local Cbackref = 3
local Carg = 4
local Csimple = 5
local Ctable = 6
local Cfunction = 7
local Cquery = 8
local Cstring = 9
local Cnum = 10
local Csubst = 11
local Cfold = 12
local Cruntime = 13
local Cgroup = 14


local PEnullable = 0
local PEnofail = 1
local RuleLR = 0x10000
local NOINST = -2


local MAXBEHINDPREDICATE = 255
local MAXRULES = 200
local MAXOFF = 0xF

-- number of siblings for each tree
local numsiblings = {
    0, 0, 0, -- char, set, any
    0, 0, -- true, false
    1, -- rep
    2, 2, -- seq, choice
    1, 1, -- not, and
    0, 0, 2, 1, -- call, opencall, rule, grammar
    1, -- behind
    1, 1 -- capture, runtime capture
}


local patternelement = ffi.typeof('PATTERN_ELEMENT')
local pattern = ffi.typeof('PATTERN')
local settype = ffi.typeof('int32_t[8]')
local fullset = settype(-1, -1, -1, -1, -1, -1, -1, -1)

-- {======================================================
-- Analysis and some optimizations
-- =======================================================

local codegen


-- Check whether a charset is empty (IFail), singleton (IChar),
-- full (IAny), or none of those (ISet).

local function charsettype(cs)
    local count = 0;
    local candidate = -1; -- candidate position for a char
    for i = 0, 8 - 1 do
        local b = cs[i];
        if b == 0 then
            if count > 1 then
                return ISet; -- else set is still empty
            end
        elseif b == -1 then
            if count < (i * 32) then
                return ISet;
            else
                count = count + 32; -- set is still full
            end
            -- byte has only one bit?
        elseif band(b, (b - 1)) == 0 then
            if count > 0 then
                return ISet; -- set is neither full nor empty
                -- set has only one char till now; track it
            else
                count = count + 1;
                candidate = i;
            end
        else
            return ISet; -- byte is neither empty, full, nor singleton
        end
    end
    if count == 0 then
        return IFail, 0 -- empty set
        -- singleton; find character bit inside byte
    elseif count == 1 then
        local b = cs[candidate];
        local c = candidate * 32;
        for i = 1, 32 do
            if b == 1 then
                c = c + i - 1
                break
            end
            b = rshift(b, 1)
        end
        return IChar, c
    elseif count == 256 then
        return IAny, 0 -- full set
    else
        assert(false) -- should have returned by now
    end
end


-- A few basic operations on Charsets

local function cs_complement(cs)
    for i = 0, 8 - 1 do
        cs[i] = bnot(cs[i])
    end
end


local function cs_equal(cs1, cs2)
    for i = 0, 8 - 1 do
        if cs1[i] ~= cs2[i] then
            return
        end
    end
    return true
end


-- computes whether sets st1 and st2 are disjoint

local function cs_disjoint(st1, st2)
    for i = 0, 8 - 1 do
        if band(st1[i], st2[i]) ~= 0 then
            return
        end
    end
    return true
end


-- Convert a 'char' pattern (TSet, TChar, TAny) to a charset

local function tocharset(tree, index, valuetable)
    local val = settype()
    if tree.p[index].tag == TSet then
        ffi.copy(val, valuetable[tree.p[index].val], ffi.sizeof(val))
        return val
    elseif tree.p[index].tag == TChar then
        local b = tree.p[index].val
        -- only one char
        -- add that one
        val[rshift(b, 5)] = lshift(1, band(b, 31))
        return val
    elseif tree.p[index].tag == TAny then
        ffi.fill(val, ffi.sizeof(val), 0xff)
        return val
    end
end


-- checks whether a pattern has captures

local function hascaptures(tree, index)
    if tree.p[index].tag == TCapture or tree.p[index].tag == TRunTime then
        return true
    elseif tree.p[index].tag == TCall then
        return hascaptures(tree, index + tree.p[index].ps)
    else
        local ns = numsiblings[tree.p[index].tag + 1]
        if ns == 0 then
            return
        elseif ns == 1 then
            return hascaptures(tree, index + 1)
        elseif ns == 2 then
            if hascaptures(tree, index + 1) then
                return true
            elseif tree.p[index].tag ~= TRule then
                return hascaptures(tree, index + tree.p[index].ps)
            end
        else
            assert(false)
        end
    end
end


-- Checks how a pattern behaves regarding the empty string,
-- in one of two different ways:
-- A pattern is *nullable* if it can match without consuming any character;
-- A pattern is *nofail* if it never fails for any string
-- (including the empty string).
-- The difference is only for predicates; for patterns without
-- predicates, the two properties are equivalent.
-- (With predicates, &'a' is nullable but not nofail. Of course,
-- nofail => nullable.)
-- These functions are all convervative in the following way:
-- p is nullable => nullable(p)
-- nofail(p) => p cannot fail
-- (The function assumes that TOpenCall and TRunTime are not nullable:
-- TOpenCall must be checked again when the grammar is fixed;
-- TRunTime is an arbitrary choice.)

local function checkaux(tree, pred, index, lrcall)
    lrcall = lrcall or {}
    local tag = tree.p[index].tag
    if tag == TChar or tag == TSet or tag == TAny or
            tag == TFalse or tag == TOpenCall then
        return -- not nullable
    elseif tag == TRep or tag == TTrue then
        return true -- no fail
    elseif tag == TNot or tag == TBehind then
        -- can match empty, but may fail
        if pred == PEnofail then
            return
        else
            return true -- PEnullable
        end
    elseif tag == TAnd then
        -- can match empty; fail iff body does
        if pred == PEnullable then
            return true
        else
            return checkaux(tree, pred, index + 1, lrcall)
        end
        -- can fail; match empty iff body does
    elseif tag == TRunTime then
        if pred == PEnofail then
            return
        else
            return checkaux(tree, pred, index + 1, lrcall)
        end
    elseif tag == TSeq then
        if not checkaux(tree, pred, index + 1, lrcall) then
            return
        else
            return checkaux(tree, pred, index + tree.p[index].ps, lrcall)
        end
    elseif tag == TChoice then
        if checkaux(tree, pred, index + tree.p[index].ps, lrcall) then
            return true
        else
            return checkaux(tree, pred, index + 1, lrcall)
        end
    elseif tag == TCapture or tag == TGrammar or tag == TRule then
        return checkaux(tree, pred, index + 1, lrcall)
    elseif tag == TCall then
        --left recursive rule
        if bit.band(tree.p[index].cap, 0xffff) ~= 0 then
            local lr = index + tree.p[index].ps
            if lrcall[lr] then
                return
            end
            lrcall[lr] = true
        end
        return checkaux(tree, pred, index + tree.p[index].ps, lrcall)
    else
        assert(false)
    end
end


-- number of characters to match a pattern (or -1 if variable)
-- ('count' avoids infinite loops for grammars)

local function fixedlenx(tree, count, len, index)
    local tag = tree.p[index].tag
    if tag == TChar or tag == TSet or tag == TAny then
        return len + 1;
    elseif tag == TFalse or tag == TTrue or tag == TNot or tag == TAnd or tag == TBehind then
        return len;
    elseif tag == TRep or tag == TRunTime or tag == TOpenCall then
        return -1;
    elseif tag == TCapture or tag == TRule or tag == TGrammar then
        return fixedlenx(tree, count, len, index + 1)
    elseif tag == TCall then
        if count >= MAXRULES then
            return -1; -- may be a loop
        else
            return fixedlenx(tree, count + 1, len, index + tree.p[index].ps)
        end
    elseif tag == TSeq then
        len = fixedlenx(tree, count, len, index + 1)
        if (len < 0) then
            return -1;
        else
            return fixedlenx(tree, count, len, index + tree.p[index].ps)
        end
    elseif tag == TChoice then
        local n1 = fixedlenx(tree, count, len, index + 1)
        if n1 < 0 then return -1 end
        local n2 = fixedlenx(tree, count, len, index + tree.p[index].ps)
        if n1 == n2 then
            return n1
        else
            return -1
        end
    else
        assert(false)
    end
end


-- Computes the 'first set' of a pattern.
-- The result is a conservative aproximation:
--   match p ax -> x' for some x ==> a in first(p).
--   match p '' -> ''            ==> returns 1.
-- The set 'follow' is the first set of what follows the
-- pattern (full set if nothing follows it)

local function getfirst(tree, follow, index, valuetable, lrcall)
    lrcall = lrcall or {}
    local tag = tree.p[index].tag
    if tag == TChar or tag == TSet or tag == TAny then
        local firstset = tocharset(tree, index, valuetable)
        return 0, firstset
    elseif tag == TTrue then
        local firstset = settype()
        ffi.copy(firstset, follow, ffi.sizeof(firstset))
        return 1, firstset
    elseif tag == TFalse then
        local firstset = settype()
        return 0, firstset
    elseif tag == TChoice then
        local e1, firstset = getfirst(tree, follow, index + 1, valuetable, lrcall)
        local e2, csaux = getfirst(tree, follow, index + tree.p[index].ps, valuetable, lrcall)
        for i = 0, 8 - 1 do
            firstset[i] = bor(firstset[i], csaux[i])
        end
        return bor(e1, e2), firstset
    elseif tag == TSeq then
        if not checkaux(tree, PEnullable, index + 1) then
            return getfirst(tree, fullset, index + 1, valuetable, lrcall)
            -- FIRST(p1 p2, fl) = FIRST(p1, FIRST(p2, fl))
        else
            local e2, csaux = getfirst(tree, follow, index + tree.p[index].ps, valuetable, lrcall)
            local e1, firstset = getfirst(tree, csaux, index + 1, valuetable, lrcall)
            if e1 == 0 then -- 'e1' ensures that first can be used
            return 0, firstset
            -- one of the children has a matchtime?
            elseif band(bor(e1, e2), 2) == 2 then
                return 2, firstset -- pattern has a matchtime capture
            else
                return e2, firstset -- else depends on 'e2'
            end
        end
    elseif tag == TRep then
        local _, firstset = getfirst(tree, follow, index + 1, valuetable, lrcall)
        for i = 0, 8 - 1 do
            firstset[i] = bor(firstset[i], follow[i])
        end
        return 1, firstset -- accept the empty string
    elseif tag == TCapture or tag == TGrammar or tag == TRule then
        return getfirst(tree, follow, index + 1, valuetable, lrcall)
        -- function invalidates any follow info.
    elseif tag == TRunTime then
        local e, firstset = getfirst(tree, fullset, index + 1, valuetable, lrcall)
        if e ~= 0 then
            return 2, firstset -- function is not "protected"?
        else
            return 0, firstset -- pattern inside capture ensures first can be used
        end
    elseif tag == TCall then
        -- left recursive rule
        if bit.band(tree.p[index].cap, 0xffff) ~= 0 then
            local lr = index + tree.p[index].ps
            if lrcall[lr] then
                return 0, settype()
            else
                lrcall[lr] = true
            end
        end
        return getfirst(tree, follow, index + tree.p[index].ps, valuetable, lrcall)
    elseif tag == TAnd then
        local e, firstset = getfirst(tree, follow, index + 1, valuetable, lrcall)
        for i = 0, 8 - 1 do
            firstset[i] = band(firstset[i], follow[i])
        end
        return e, firstset
    elseif tag == TNot then
        local firstset = tocharset(tree, index + 1, valuetable)
        if firstset then
            cs_complement(firstset)
            return 1, firstset
        end
        local e, firstset = getfirst(tree, follow, index + 1, valuetable, lrcall)
        ffi.copy(firstset, follow, ffi.sizeof(firstset))
        return bor(e, 1), firstset -- always can accept the empty string
        -- instruction gives no new information
    elseif tag == TBehind then
        -- call 'getfirst' to check for math-time captures
        local e, firstset = getfirst(tree, follow, index + 1, valuetable, lrcall)
        ffi.copy(firstset, follow, ffi.sizeof(firstset))
        return bor(e, 1), firstset -- always can accept the empty string
    else
        assert(false)
    end
end


-- If it returns true, then pattern can fail only depending on the next
-- character of the subject

local function headfail(tree, index, lrcall)
    lrcall = lrcall or {}
    local tag = tree.p[index].tag
    if tag == TChar or tag == TSet or tag == TAny or tag == TFalse then
        return true
    elseif tag == TTrue or tag == TRep or tag == TRunTime or tag == TNot or tag == TBehind then
        return
    elseif tag == TCapture or tag == TGrammar or tag == TRule or tag == TAnd then
        return headfail(tree, index + 1, lrcall)
    elseif tag == TCall then
        -- left recursive rule
        if bit.band(tree.p[index].cap, 0xffff) ~= 0 then
            local lr = index + tree.p[index].ps
            if lrcall[lr] then
                return true
            else
                lrcall[lr] = true
            end
        end
        return headfail(tree, index + tree.p[index].ps, lrcall)
    elseif tag == TSeq then
        if not checkaux(tree, PEnofail, index + tree.p[index].ps) then
            return
        else
            return headfail(tree, index + 1, lrcall)
        end
    elseif tag == TChoice then
        if not headfail(tree, index + 1, lrcall) then
            return
        else
            return headfail(tree, index + tree.p[index].ps, lrcall)
        end
    else
        assert(false)
    end
end


-- Check whether the code generation for the given tree can benefit
-- from a follow set (to avoid computing the follow set when it is
-- not needed)

local function needfollow(tree, index)
    local tag = tree.p[index].tag
    if tag == TChar or tag == TSet or tag == TAny or tag == TFalse or tag == TTrue or tag == TAnd or tag == TNot or
            tag == TRunTime or tag == TGrammar or tag == TCall or tag == TBehind then
        return
    elseif tag == TChoice or tag == TRep then
        return true
    elseif tag == TCapture then
        return needfollow(tree, index + 1)
    elseif tag == TSeq then
        return needfollow(tree, index + tree.p[index].ps)
    else
        assert(false)
    end
end

-- ======================================================


-- {======================================================
-- Code generation
-- =======================================================


-- code generation is recursive; 'opt' indicates that the code is
-- being generated under a 'IChoice' operator jumping to its end.
-- 'tt' points to a previous test protecting this code. 'fl' is
-- the follow set of the pattern.


local function addinstruction(code, op, val)
    local size = code.size
    if size >= code.allocsize then
        code:doublesize()
    end
    code.p[size].code = op
    code.p[size].val = val
    code.size = size + 1
    return size
end


local function setoffset(code, instruction, offset)
    code.p[instruction].offset = offset;
end


-- Add a capture instruction:
-- 'op' is the capture instruction; 'cap' the capture kind;
-- 'key' the key into ktable; 'aux' is optional offset

local function addinstcap(code, op, cap, key, aux)
    local i = addinstruction(code, op, bor(cap, lshift(aux, 4)))
    setoffset(code, i, key)
    return i
end


local function jumptothere(code, instruction, target)
    if instruction >= 0 then
        setoffset(code, instruction, target - instruction)
    end
end


local function jumptohere(code, instruction)
    jumptothere(code, instruction, code.size)
end


-- Code an IChar instruction, or IAny if there is an equivalent
-- test dominating it

local function codechar(code, c, tt)
    assert(tt ~= -1)
    if tt >= 0 and code.p[tt].code == ITestChar and
            code.p[tt].val == c then
        addinstruction(code, IAny, 0)
    else
        addinstruction(code, IChar, c)
    end
end


-- Code an ISet instruction

local function coderealcharset(code, cs, valuetable)
    local ind = #valuetable + 1
    valuetable[ind] = cs
    return addinstruction(code, ISet, ind)
end


-- code a char set, optimizing unit sets for IChar, "complete"
-- sets for IAny, and empty sets for IFail; also use an IAny
-- when instruction is dominated by an equivalent test.

local function codecharset(code, cs, tt, valuetable)
    local op, c = charsettype(cs)
    if op == IChar then
        codechar(code, c, tt)
    elseif op == ISet then
        assert(tt ~= -1)
        if tt >= 0 and code.p[tt].code == ITestSet and
                cs_equal(cs, valuetable[code.p[tt].val]) then
            addinstruction(code, IAny, 0)
        else
            coderealcharset(code, cs, valuetable)
        end
    else
        addinstruction(code, op, c)
    end
end


-- code a test set, optimizing unit sets for ITestChar, "complete"
-- sets for ITestAny, and empty sets for IJmp (always fails).
-- 'e' is true iff test should accept the empty string. (Test
-- instructions in the current VM never accept the empty string.)

local function codetestset(code, cs, e, valuetable)
    if e ~= 0 then
        return NOINST -- no test
    else
        local pos = code.size
        codecharset(code, cs, NOINST, valuetable)
        local inst = code.p[pos]
        local code = inst.code
        if code == IFail then
            inst.code = IJmp -- always jump
        elseif code == IAny then
            inst.code = ITestAny
        elseif code == IChar then
            inst.code = ITestChar
        elseif code == ISet then
            inst.code = ITestSet
        else
            assert(false)
        end
        return pos
    end
end


-- Find the final destination of a sequence of jumps

local function finaltarget(code, i)
    while code.p[i].code == IJmp do
        i = i + code.p[i].offset
    end
    return i
end


-- final label (after traversing any jumps)

local function finallabel(code, i)
    return finaltarget(code, i + code.p[i].offset)
end

-- <behind(p)> == behind n; <p>   (where n = fixedlen(p))

local function codebehind(code, tree, index, valuetable)
    if tree.p[index].val > 0 then
        addinstruction(code, IBehind, tree.p[index].val)
    end
    codegen(code, tree, fullset, false, NOINST, index + 1, valuetable) --  NOINST
end


-- Choice; optimizations:
-- - when p1 is headfail
-- - when first(p1) and first(p2) are disjoint; than
-- a character not in first(p1) cannot go to p1, and a character
-- in first(p1) cannot go to p2 (at it is not in first(p2)).
-- (The optimization is not valid if p1 accepts the empty string,
-- as then there is no character at all...)
-- - when p2 is empty and opt is true; a IPartialCommit can resuse
-- the Choice already active in the stack.

local function codechoice(code, tree, fl, opt, p1, p2, valuetable)
    local emptyp2 = tree.p[p2].tag == TTrue
    local e1, st1 = getfirst(tree, fullset, p1, valuetable)
    local _, st2 = getfirst(tree, fl, p2, valuetable)
    if headfail(tree, p1) or (e1 == 0 and cs_disjoint(st1, st2)) then
        -- <p1 / p2> == test (fail(p1)) -> L1 ; p1 ; jmp L2; L1: p2; L2:
        local test = codetestset(code, st1, 0, valuetable)
        local jmp = NOINST;
        codegen(code, tree, fl, false, test, p1, valuetable)
        if not emptyp2 then
            jmp = addinstruction(code, IJmp, 0)
        end
        jumptohere(code, test)
        codegen(code, tree, fl, opt, NOINST, p2, valuetable)
        jumptohere(code, jmp)
    elseif opt and emptyp2 then
        -- p1? == IPartialCommit; p1
        jumptohere(code, addinstruction(code, IPartialCommit, 0))
        codegen(code, tree, fullset, true, NOINST, p1, valuetable)
    else
        -- <p1 / p2> ==
        --  test(fail(p1)) -> L1; choice L1; <p1>; commit L2; L1: <p2>; L2:
        local test = codetestset(code, st1, e1, valuetable)
        local pchoice = addinstruction(code, IChoice, 0)
        codegen(code, tree, fullset, emptyp2, test, p1, valuetable)
        local pcommit = addinstruction(code, ICommit, 0)
        jumptohere(code, pchoice)
        jumptohere(code, test)
        codegen(code, tree, fl, opt, NOINST, p2, valuetable)
        jumptohere(code, pcommit)
    end
end


-- And predicate
-- optimization: fixedlen(p) = n ==> <&p> == <p>; behind n
-- (valid only when 'p' has no captures)

local function codeand(code, tree, tt, index, valuetable)
    local n = fixedlenx(tree, 0, 0, index)
    if n >= 0 and n <= MAXBEHINDPREDICATE and not hascaptures(tree, index) then
        codegen(code, tree, fullset, false, tt, index, valuetable)
        if n > 0 then
            addinstruction(code, IBehind, n)
        end
    else
        -- default: Choice L1; p1; BackCommit L2; L1: Fail; L2:
        local pchoice = addinstruction(code, IChoice, 0)
        codegen(code, tree, fullset, false, tt, index, valuetable)
        local pcommit = addinstruction(code, IBackCommit, 0)
        jumptohere(code, pchoice)
        addinstruction(code, IFail, 0)
        jumptohere(code, pcommit)
    end
end


-- Captures: if pattern has fixed (and not too big) length, use
-- a single IFullCapture instruction after the match; otherwise,
-- enclose the pattern with OpenCapture - CloseCapture.

local function codecapture(code, tree, fl, tt, index, valuetable)
    local len = fixedlenx(tree, 0, 0, index + 1)
    if len >= 0 and len <= MAXOFF and not hascaptures(tree, index + 1) then
        codegen(code, tree, fl, false, tt, index + 1, valuetable)
        addinstcap(code, IFullCapture, tree.p[index].cap, tree.p[index].val, len)
    else
        addinstcap(code, IOpenCapture, tree.p[index].cap, tree.p[index].val, 0)
        codegen(code, tree, fl, false, tt, index + 1, valuetable)
        addinstcap(code, ICloseCapture, Cclose, 0, 0)
    end
end


local function coderuntime(code, tree, tt, index, valuetable)
    addinstcap(code, IOpenCapture, Cgroup, tree.p[index].val, 0)
    codegen(code, tree, fullset, false, tt, index + 1, valuetable)
    addinstcap(code, ICloseRunTime, Cclose, 0, 0)
end


-- Repetion; optimizations:
-- When pattern is a charset, can use special instruction ISpan.
-- When pattern is head fail, or if it starts with characters that
-- are disjoint from what follows the repetions, a simple test
-- is enough (a fail inside the repetition would backtrack to fail
-- again in the following pattern, so there is no need for a choice).
-- When 'opt' is true, the repetion can reuse the Choice already
-- active in the stack.

local function coderep(code, tree, opt, fl, index, valuetable)
    local st = tocharset(tree, index, valuetable)
    if st then
        local op = coderealcharset(code, st, valuetable)
        code.p[op].code = ISpan;
    else
        local e1, st = getfirst(tree, fullset, index, valuetable)
        if headfail(tree, index) or (e1 == 0 and cs_disjoint(st, fl)) then
            -- L1: test (fail(p1)) -> L2; <p>; jmp L1; L2:
            local test = codetestset(code, st, 0, valuetable)
            codegen(code, tree, fullset, false, test, index, valuetable)
            local jmp = addinstruction(code, IJmp, 0)
            jumptohere(code, test)
            jumptothere(code, jmp, test)
        else
            -- test(fail(p1)) -> L2; choice L2; L1: <p>; partialcommit L1; L2:
            -- or (if 'opt'): partialcommit L1; L1: <p>; partialcommit L1;
            local test = codetestset(code, st, e1, valuetable)
            local pchoice = NOINST;
            if opt then
                jumptohere(code, addinstruction(code, IPartialCommit, 0))
            else
                pchoice = addinstruction(code, IChoice, 0)
            end
            local l2 = code.size
            codegen(code, tree, fullset, false, NOINST, index, valuetable)
            local commit = addinstruction(code, IPartialCommit, 0)
            jumptothere(code, commit, l2)
            jumptohere(code, pchoice)
            jumptohere(code, test)
        end
    end
end


-- Not predicate; optimizations:
-- In any case, if first test fails, 'not' succeeds, so it can jump to
-- the end. If pattern is headfail, that is all (it cannot fail
-- in other parts); this case includes 'not' of simple sets. Otherwise,
-- use the default code (a choice plus a failtwice).

local function codenot(code, tree, index, valuetable)
    local e, st = getfirst(tree, fullset, index, valuetable)
    local test = codetestset(code, st, e, valuetable)
    -- test (fail(p1)) -> L1; fail; L1:
    if headfail(tree, index) then
        addinstruction(code, IFail, 0)
    else
        -- test(fail(p))-> L1; choice L1; <p>; failtwice; L1:
        local pchoice = addinstruction(code, IChoice, 0)
        codegen(code, tree, fullset, false, NOINST, index, valuetable)
        addinstruction(code, IFailTwice, 0)
        jumptohere(code, pchoice)
    end
    jumptohere(code, test)
end


-- change open calls to calls, using list 'positions' to find
-- correct offsets; also optimize tail calls

local function correctcalls(code, positions, from, to)
    for i = from, to - 1 do
        if code.p[i].code == IOpenCall then
            local n = code.p[i].offset; -- rule number
            local rule = positions[n]; -- rule position
            assert(rule == from or code.p[rule - 1].code == IRet)
            -- call; ret ?
            if bit.band(code.p[i].val, 0xffff) == 0 and code.p[finaltarget(code, i + 1)].code == IRet then
                code.p[i].code = IJmp; -- tail call
            else
                code.p[i].code = ICall;
            end
            jumptothere(code, i, rule) -- call jumps to respective rule
        end
    end
end


-- Code for a grammar:
-- call L1; jmp L2; L1: rule 1; ret; rule 2; ret; ...; L2:

local function codegrammar(code, tree, index, valuetable)
    local positions = {}
    local rulenumber = 1;
    --    tree.p[rule].tag
    local rule = index + 1
    assert(tree.p[rule].tag == TRule)
    local LR = 0
    if band(RuleLR, tree.p[rule].cap) ~= 0 then LR = 1 end
    local firstcall = addinstruction(code, ICall, LR) -- call initial rule
    code.p[firstcall].aux = tree.p[rule].val
    local jumptoend = addinstruction(code, IJmp, 0) -- jump to the end
    jumptohere(code, firstcall) -- here starts the initial rule
    while tree.p[rule].tag == TRule do
        positions[rulenumber] = code.size -- save rule position
        rulenumber = rulenumber + 1
        codegen(code, tree, fullset, false, NOINST, rule + 1, valuetable) -- code rule
        addinstruction(code, IRet, 0)
        rule = rule + tree.p[rule].ps
    end
    assert(tree.p[rule].tag == TTrue)
    jumptohere(code, jumptoend)
    correctcalls(code, positions, firstcall + 2, code.size)
end


local function codecall(code, tree, index, val)
    local c = addinstruction(code, IOpenCall, tree.p[index].cap) -- to be corrected later
    code.p[c].aux = val
    assert(tree.p[index + tree.p[index].ps].tag == TRule)
    setoffset(code, c, band(tree.p[index + tree.p[index].ps].cap, 0x7fff)) -- offset = rule number
end


local function codeseq(code, tree, fl, opt, tt, p1, p2, valuetable)
    if needfollow(tree, p1) then
        local _, fll = getfirst(tree, fl, p2, valuetable) -- p1 follow is p2 first
        codegen(code, tree, fll, false, tt, p1, valuetable)
    else
        -- use 'fullset' as follow
        codegen(code, tree, fullset, false, tt, p1, valuetable)
    end
    -- can p1 consume anything?
    if (fixedlenx(tree, 0, 0, p1) ~= 0) then
        tt = NOINST; -- invalidate test
    end
    return codegen(code, tree, fl, opt, tt, p2, valuetable)
end


-- Main code-generation function: dispatch to auxiliar functions
-- according to kind of tree

-- code generation is recursive; 'opt' indicates that the code is being
-- generated as the last thing inside an optional pattern (so, if that
-- code is optional too, it can reuse the 'IChoice' already in place for
-- the outer pattern). 'tt' points to a previous test protecting this
-- code (or NOINST). 'fl' is the follow set of the pattern.

function codegen(code, tree, fl, opt, tt, index, valuetable)
    local tag = tree.p[index].tag
    if tag == TChar then
        return codechar(code, tree.p[index].val, tt)
    elseif tag == TAny then
        return addinstruction(code, IAny, 0)
    elseif tag == TSet then
        return codecharset(code, valuetable[tree.p[index].val], tt, valuetable)
    elseif tag == TTrue then
    elseif tag == TFalse then
        return addinstruction(code, IFail, 0)
    elseif tag == TSeq then
        return codeseq(code, tree, fl, opt, tt, index + 1, index + tree.p[index].ps, valuetable)
    elseif tag == TChoice then
        return codechoice(code, tree, fl, opt, index + 1, index + tree.p[index].ps, valuetable)
    elseif tag == TRep then
        return coderep(code, tree, opt, fl, index + 1, valuetable)
    elseif tag == TBehind then
        return codebehind(code, tree, index, valuetable)
    elseif tag == TNot then
        return codenot(code, tree, index + 1, valuetable)
    elseif tag == TAnd then
        return codeand(code, tree, tt, index + 1, valuetable)
    elseif tag == TCapture then
        return codecapture(code, tree, fl, tt, index, valuetable)
    elseif tag == TRunTime then
        return coderuntime(code, tree, tt, index, valuetable)
    elseif tag == TGrammar then
        return codegrammar(code, tree, index, valuetable)
    elseif tag == TCall then
        return codecall(code, tree, index, tree.p[index].val)
    else
        assert(false)
    end
end


-- Optimize jumps and other jump-like instructions.
-- * Update labels of instructions with labels to their final
-- destinations (e.g., choice L1; ... L1: jmp L2: becomes
-- choice L2)
-- * Jumps to other instructions that do jumps become those
-- instructions (e.g., jump to return becomes a return; jump
-- to commit becomes a commit)

local function peephole(code)
    local i = 0
    while i < code.size do
        local tag = code.p[i].code
        if tag == IChoice or tag == ICall or tag == ICommit or tag == IPartialCommit or
                tag == IBackCommit or tag == ITestChar or tag == ITestSet or tag == ITestAny then
            -- instructions with labels
            jumptothere(code, i, finallabel(code, i)) -- optimize label

        elseif tag == IJmp then
            local ft = finaltarget(code, i)
            local tag = code.p[ft].code -- jumping to what?
            -- instructions with unconditional implicit jumps
            if tag == IRet or tag == IFail or tag == IFailTwice or tag == IEnd then
                ffi.copy(code.p + i, code.p + ft, ffi.sizeof(patternelement)) -- jump becomes that instruction
            elseif tag == ICommit or tag == IPartialCommit or tag == IBackCommit then
                -- inst. with unconditional explicit jumps
                local fft = finallabel(code, ft)
                ffi.copy(code.p + i, code.p + ft, ffi.sizeof(patternelement)) -- jump becomes that instruction...
                jumptothere(code, i, fft) -- but must correct its offset
                i = i - 1 -- reoptimize its label
            else
                jumptothere(code, i, ft) -- optimize label
            end
        end
        i = i + 1
    end
end


-- Compile a pattern

local function compile(tree, index, valuetable)
    local code = pattern()
    codegen(code, tree, fullset, false, NOINST, index, valuetable)
    addinstruction(code, IEnd, 0)
    peephole(code)
    ffi.C.free(tree.code)
    tree.code = code
end

local function pat_new(ct, size)
    size = size or 0
    local allocsize = size
    if allocsize < 10 then
        allocsize = 10
    end
    local pat = ffi.cast('PATTERN*', ffi.C.malloc(ffi.sizeof(pattern)))
    assert(pat ~= nil)
    pat.allocsize = allocsize
    pat.size = size
    pat.p = ffi.C.malloc(ffi.sizeof(patternelement) * allocsize)
    assert(pat.p ~= nil)
    ffi.fill(pat.p, ffi.sizeof(patternelement) * allocsize)
    return pat
end

local function doublesize(ct)
    ct.p = ffi.C.realloc(ct.p, ffi.sizeof(patternelement) * ct.allocsize * 2)
    assert(ct.p ~= nil)
    ffi.fill(ct.p + ct.allocsize, ffi.sizeof(patternelement) * ct.allocsize)
    ct.allocsize = ct.allocsize * 2
end

local pattreg = {
    doublesize = doublesize,
}

local metareg = {
    ["__new"] = pat_new,
    ["__index"] = pattreg
}

ffi.metatype(pattern, metareg)

return {
    checkaux = checkaux,
    tocharset = tocharset,
    fixedlenx = fixedlenx,
    hascaptures = hascaptures,
    compile = compile,
}