init

1 files changed, 1373 insertions, 0 deletions

diff --git a/vendor/lpeglj/lpeglj.lua b/vendor/lpeglj/lpeglj.lua
new file mode 100644
index 0000000..de4fca3
--- /dev/null
+++ b/vendor/lpeglj/lpeglj.lua
@@ -0,0 +1,1373 @@
+--[[
+LPEGLJ
+lpeglj.lua
+Main module and tree generation
+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 ]
+--]]
+
+assert(jit.version_num > 20000, "Use LuaJIT v2.0.1 or higher.")
+
+local ffi = require "ffi"
+local lpcode = require "lpcode"
+local lpprint = require "lpprint"
+local lpvm = require "lpvm"
+
+local band, bor, bnot, rshift, lshift = bit.band, bit.bor, bit.bnot, bit.rshift, bit.lshift
+
+ffi.cdef [[
+ int isalnum(int c);
+ int isalpha(int c);
+ int iscntrl(int c);
+ int isdigit(int c);
+ int isgraph(int c);
+ int islower(int c);
+ int isprint(int c);
+ int ispunct(int c);
+ int isspace(int c);
+ int isupper(int c);
+ int isxdigit(int c);
+]]
+
+local MAXBEHIND = 255
+local MAXRULES = 200
+local VERSION = "1.0.0.0LJ"
+
+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 PEleftrecursion = 2
+
+local newgrammar
+
+local RuleLR = 0x10000
+local Ruleused = 0x20000
+local BCapcandelete = 0x30000
+
+local LREnable = false
+
+-- 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 patternid = 0
+local valuetable = {}
+
+local funcnames = setmetatable({}, { __mode = 'k' })
+
+local treepatternelement = ffi.typeof('TREEPATTERN_ELEMENT')
+local treepattern = ffi.typeof('TREEPATTERN')
+local patternelement = ffi.typeof('PATTERN_ELEMENT')
+local pattern = ffi.typeof('PATTERN')
+local settype = ffi.typeof('int32_t[8]')
+local uint32 = ffi.typeof('uint32_t[1]')
+
+-- Fix a TOpenCall into a TCall node, using table 'postable' to
+-- translate a key to its rule address in the tree. Raises an
+-- error if key does not exist.
+
+local function fixonecall(postable, grammar, index, valuetable)
+    local name = valuetable[grammar.p[index].val] -- get rule's name
+    local n = postable[name] -- query name in position table
+    -- no position?
+    if not n then
+        error(("rule '%s' undefined in given grammar"):format(type(name) == 'table' and '(a table)' or name), 0)
+    end
+    grammar.p[index].tag = TCall;
+    grammar.p[index].ps = n - index -- position relative to node
+    grammar.p[index + grammar.p[index].ps].cap = bit.bor(grammar.p[index + grammar.p[index].ps].cap, Ruleused)
+end
+
+
+-- Transform left associative constructions into right
+-- associative ones, for sequence and choice; that is:
+-- (t11 + t12) + t2  =>  t11 + (t12 + t2)
+-- (t11 * t12) * t2  =>  t11 * (t12 * t2)
+-- (that is, Op (Op t11 t12) t2 => Op t11 (Op t12 t2))
+
+local function correctassociativity(tree, index)
+    local t1 = index + 1
+    assert(tree.p[index].tag == TChoice or tree.p[index].tag == TSeq)
+    while tree.p[t1].tag == tree.p[index].tag do
+        local n1size = tree.p[index].ps - 1; -- t1 == Op t11 t12
+        local n11size = tree.p[t1].ps - 1;
+        local n12size = n1size - n11size - 1
+        for i = 1, n11size do
+            ffi.copy(tree.p + index + i, tree.p + t1 + i, ffi.sizeof(treepatternelement))
+        end
+        tree.p[index].ps = n11size + 1
+        tree.p[index + tree.p[index].ps].tag = tree.p[index].tag
+        tree.p[index + tree.p[index].ps].ps = n12size + 1
+    end
+end
+
+
+-- Make final adjustments in a tree. Fix open calls in tree,
+-- making them refer to their respective rules or raising appropriate
+-- errors (if not inside a grammar). Correct associativity of associative
+-- constructions (making them right associative).
+
+local function finalfix(fix, postable, grammar, index, valuetable)
+
+    local tag = grammar.p[index].tag
+    --subgrammars were already fixed
+    if tag == TGrammar then
+        return
+    elseif tag == TOpenCall then
+        -- inside a grammar?
+        if fix then
+            fixonecall(postable, grammar, index, valuetable)
+            -- open call outside grammar
+        else
+            error(("rule '%s' used outside a grammar"):format(tostring(valuetable[grammar.p[index].val])), 0)
+        end
+    elseif tag == TSeq or tag == TChoice then
+        correctassociativity(grammar, index)
+    end
+    local ns = numsiblings[tag + 1]
+    if ns == 0 then
+    elseif ns == 1 then
+        return finalfix(fix, postable, grammar, index + 1, valuetable)
+    elseif ns == 2 then
+        finalfix(fix, postable, grammar, index + 1, valuetable)
+        return finalfix(fix, postable, grammar, index + grammar.p[index].ps, valuetable)
+    else
+        assert(false)
+    end
+end
+
+
+-- {======================================================
+-- Tree generation
+-- =======================================================
+
+local function newcharset()
+    local tree = treepattern(1)
+    valuetable[tree.id] = { settype() }
+    tree.p[0].tag = TSet
+    tree.p[0].val = 1
+    return tree, valuetable[tree.id][1]
+end
+
+
+-- add to tree a sequence where first sibling is 'sib' (with size
+-- 'sibsize')
+
+local function seqaux(tree, sib, start, sibsize)
+    tree.p[start].tag = TSeq;
+    tree.p[start].ps = sibsize + 1
+    ffi.copy(tree.p + start + 1, sib.p, ffi.sizeof(treepatternelement) * sibsize)
+end
+
+
+-- Build a sequence of 'n' nodes, each with tag 'tag' and 'val' got
+-- from the array 's' (or 0 if array is NULL). (TSeq is binary, so it
+-- must build a sequence of sequence of sequence...)
+
+local function fillseq(tree, tag, start, n, s)
+    -- initial n-1 copies of Seq tag; Seq ...
+    for i = 1, n - 1 do
+        tree.p[start].tag = TSeq
+        tree.p[start].ps = 2
+        tree.p[start + 1].tag = tag
+        if s then
+            tree.p[start + 1].val = s:sub(i, i):byte()
+        end
+        start = start + tree.p[start].ps
+    end
+    tree.p[start].tag = tag -- last one does not need TSeq
+    if s then
+        tree.p[start].val = s:sub(n, n):byte()
+    end
+end
+
+
+-- Numbers as patterns:
+-- 0 == true (always match); n == TAny repeated 'n' times;
+-- -n == not (TAny repeated 'n' times)
+
+local function numtree(n)
+    if n == 0 then
+        local tree = treepattern(1)
+        tree.p[0].tag = TTrue
+        return tree
+    else
+        local tree, start
+        if n > 0 then
+            tree = treepattern(2 * n - 1)
+            start = 0
+            -- negative: code it as !(-n)
+        else
+            n = -n;
+            tree = treepattern(2 * n)
+            tree.p[0].tag = TNot
+            start = 1
+        end
+        fillseq(tree, TAny, start, n) -- sequence of 'n' any's
+        return tree;
+    end
+end
+
+
+-- Convert value to a pattern
+
+local function getpatt(val, name)
+    local typ = type(val)
+    if typ == 'string' then
+        -- empty?
+        if #val == 0 then
+            local pat = treepattern(1)
+            pat.p[0].tag = TTrue -- always match
+            return pat
+        else
+            local tree = treepattern(2 * (#val - 1) + 1)
+            fillseq(tree, TChar, 0, #val, val) -- sequence of '#val' chars
+            return tree
+        end
+    elseif typ == 'number' then
+        return numtree(val)
+    elseif typ == 'boolean' then
+        local pat = treepattern(1)
+        pat.p[0].tag = val and TTrue or TFalse
+        return pat
+    elseif typ == 'table' then
+        return newgrammar(val)
+    elseif typ == 'function' then
+        if name and type(name) == 'string' then
+            funcnames[val] = name
+        end
+        local pat = treepattern(2)
+        valuetable[pat.id] = { val }
+        pat.p[0].tag = TRunTime
+        pat.p[0].val = 1
+        pat.p[1].tag = TTrue
+        return pat
+    elseif ffi.istype(treepattern, val) then
+        assert(val.treesize > 0)
+        return val
+    end
+    assert(false)
+end
+
+local function copykeys(ktable1, ktable2)
+    local ktable, offset = {}, 0
+    if not ktable1 and not ktable2 then
+        return ktable, 0
+    elseif ktable1 then
+        for i = 1, #ktable1 do
+            ktable[#ktable + 1] = ktable1[i]
+        end
+        offset = #ktable1
+        if not ktable2 then
+            return ktable, 0
+        end
+    end
+    if ktable2 then
+        for i = 1, #ktable2 do
+            ktable[#ktable + 1] = ktable2[i]
+        end
+    end
+    assert(#ktable < 65536, "too many Lua values in pattern")
+    return ktable, offset
+end
+
+local function correctkeys(tree, index, offset)
+    local tag = tree.p[index].tag
+    if (tag == TSet or tag == TRule or tag == TCall or tag == TRunTime or tag == TOpenCall or tag == TCapture) and
+            tree.p[index].val ~= 0 then
+        tree.p[index].val = tree.p[index].val + offset
+    end
+    local ns = numsiblings[tag + 1]
+    if ns == 0 then
+    elseif ns == 1 then
+        return correctkeys(tree, index + 1, offset)
+    elseif ns == 2 then
+        correctkeys(tree, index + 1, offset)
+        return correctkeys(tree, index + tree.p[index].ps, offset)
+    else
+        assert(false)
+    end
+end
+
+
+
+-- create a new tree, with a new root and one sibling.
+
+local function newroot1sib(tag, pat)
+    local tree1 = getpatt(pat)
+    local tree = treepattern(1 + tree1.treesize) -- create new tree
+    valuetable[tree.id] = copykeys(valuetable[tree1.id])
+    tree.p[0].tag = tag
+    ffi.copy(tree.p + 1, tree1.p, ffi.sizeof(treepatternelement) * tree1.treesize)
+    return tree
+end
+
+
+-- create a new tree, with a new root and 2 siblings.
+
+local function newroot2sib(tag, pat1, pat2)
+    local tree1 = getpatt(pat1)
+    local tree2 = getpatt(pat2)
+    local tree = treepattern(1 + tree1.treesize + tree2.treesize) -- create new tree
+    local ktable, offset = copykeys(valuetable[tree1.id], valuetable[tree2.id])
+    valuetable[tree.id] = ktable
+    tree.p[0].tag = tag
+    tree.p[0].ps = 1 + tree1.treesize
+    ffi.copy(tree.p + 1, tree1.p, ffi.sizeof(treepatternelement) * tree1.treesize)
+    ffi.copy(tree.p + 1 + tree1.treesize, tree2.p, ffi.sizeof(treepatternelement) * tree2.treesize)
+    if offset > 0 then
+        correctkeys(tree, 1 + tree1.treesize, offset)
+    end
+    return tree;
+end
+
+
+local function lp_P(val, name)
+    assert(type(val) ~= 'nil')
+    return getpatt(val, name)
+end
+
+
+-- sequence operator; optimizations:
+-- false x => false, x true => x, true x => x
+-- (cannot do x . false => false because x may have runtime captures)
+
+local function lp_seq(pat1, pat2)
+    local tree1 = getpatt(pat1)
+    local tree2 = getpatt(pat2)
+    --  false . x == false, x . true = x
+    if tree1.p[0].tag == TFalse or tree2.p[0].tag == TTrue then
+        return tree1
+        -- true . x = x
+    elseif tree1.p[0].tag == TTrue then
+        return tree2
+    else
+        return newroot2sib(TSeq, tree1, tree2)
+    end
+end
+
+
+-- choice operator; optimizations:
+-- charset / charset => charset
+-- true / x => true, x / false => x, false / x => x
+-- (x / true is not equivalent to true)
+
+local function lp_choice(pat1, pat2)
+    local tree1 = getpatt(pat1)
+    local tree2 = getpatt(pat2)
+    local charset1 = lpcode.tocharset(tree1, 0, valuetable[tree1.id])
+    local charset2 = lpcode.tocharset(tree2, 0, valuetable[tree2.id])
+    if charset1 and charset2 then
+        local t, set = newcharset()
+        for i = 0, 7 do
+            set[i] = bor(charset1[i], charset2[i])
+        end
+        return t
+    elseif lpcode.checkaux(tree1, PEnofail, 0) or tree2.p[0].tag == TFalse then
+        return tree1 -- true / x => true, x / false => x
+    elseif tree1.p[0].tag == TFalse then
+        return tree2 -- false / x => x
+    else
+        return newroot2sib(TChoice, tree1, tree2)
+    end
+end
+
+
+-- p^n
+
+local function lp_star(tree1, n)
+    local tree
+    n = tonumber(n)
+    assert(type(n) == 'number')
+    -- seq tree1 (seq tree1 ... (seq tree1 (rep tree1)))
+    if n >= 0 then
+        tree = treepattern((n + 1) * (tree1.treesize + 1))
+        if lpcode.checkaux(tree1, PEnullable, 0) then
+            error("loop body may accept empty string", 0)
+        end
+        valuetable[tree.id] = copykeys(valuetable[tree1.id])
+        local start = 0
+        -- repeat 'n' times
+        for i = 1, n do
+            seqaux(tree, tree1, start, tree1.treesize)
+            start = start + tree.p[start].ps
+        end
+        tree.p[start].tag = TRep
+        ffi.copy(tree.p + start + 1, tree1.p, ffi.sizeof(treepatternelement) * tree1.treesize)
+        -- choice (seq tree1 ... choice tree1 true ...) true
+    else
+        n = -n;
+        -- size = (choice + seq + tree1 + true) * n, but the last has no seq
+        tree = treepattern(n * (tree1.treesize + 3) - 1)
+        valuetable[tree.id] = copykeys(valuetable[tree1.id])
+        local start = 0
+        -- repeat (n - 1) times
+        for i = n, 2, -1 do
+            tree.p[start].tag = TChoice;
+            tree.p[start].ps = i * (tree1.treesize + 3) - 2
+            tree.p[start + tree.p[start].ps].tag = TTrue;
+            start = start + 1
+            seqaux(tree, tree1, start, tree1.treesize)
+            start = start + tree.p[start].ps
+        end
+        tree.p[start].tag = TChoice;
+        tree.p[start].ps = tree1.treesize + 1
+        tree.p[start + tree.p[start].ps].tag = TTrue
+        ffi.copy(tree.p + start + 1, tree1.p, ffi.sizeof(treepatternelement) * tree1.treesize)
+    end
+    return tree
+end
+
+
+-- #p == &p
+
+local function lp_and(pat)
+    return newroot1sib(TAnd, pat)
+end
+
+
+-- -p == !p
+
+local function lp_not(pat)
+    return newroot1sib(TNot, pat)
+end
+
+
+-- [t1 - t2] == Seq (Not t2) t1
+-- If t1 and t2 are charsets, make their difference.
+
+local function lp_sub(pat1, pat2)
+    local tree1 = getpatt(pat1)
+    local tree2 = getpatt(pat2)
+    local charset1 = lpcode.tocharset(tree1, 0, valuetable[tree1.id])
+    local charset2 = lpcode.tocharset(tree2, 0, valuetable[tree2.id])
+    if charset1 and charset2 then
+        local tree, set = newcharset()
+        for i = 0, 7 do
+            set[i] = band(charset1[i], bnot(charset2[i]))
+        end
+        return tree
+    else
+        local tree = treepattern(2 + tree1.treesize + tree2.treesize)
+        local ktable, offset = copykeys(valuetable[tree2.id], valuetable[tree1.id])
+        valuetable[tree.id] = ktable
+        tree.p[0].tag = TSeq; -- sequence of...
+        tree.p[0].ps = 2 + tree2.treesize
+        tree.p[1].tag = TNot; -- ...not...
+        ffi.copy(tree.p + 2, tree2.p, ffi.sizeof(treepatternelement) * tree2.treesize)
+        ffi.copy(tree.p + tree2.treesize + 2, tree1.p, ffi.sizeof(treepatternelement) * tree1.treesize)
+        if offset > 0 then
+            correctkeys(tree, 2 + tree2.treesize, offset)
+        end
+        return tree
+    end
+end
+
+
+local function lp_set(val)
+    assert(type(val) == 'string')
+    local tree, set = newcharset()
+    for i = 1, #val do
+        local b = val:sub(i, i):byte()
+        set[rshift(b, 5)] = bor(set[rshift(b, 5)], lshift(1, band(b, 31)))
+    end
+    return tree
+end
+
+
+local function lp_range(...)
+    local args = { ... }
+    local top = #args
+    local tree, set = newcharset()
+    for i = 1, top do
+        assert(#args[i] == 2, args[i] .. " range must have two characters")
+        for b = args[i]:sub(1, 1):byte(), args[i]:sub(2, 2):byte() do
+            set[rshift(b, 5)] = bor(set[rshift(b, 5)], lshift(1, band(b, 31)))
+        end
+    end
+    return tree
+end
+
+
+-- Look-behind predicate
+
+local function lp_behind(pat)
+    local tree1 = getpatt(pat)
+    local n = lpcode.fixedlenx(tree1, 0, 0, 0)
+    assert(not lpcode.hascaptures(tree1, 0), "pattern have captures")
+    assert(n >= 0, "pattern may not have fixed length")
+    assert(n <= MAXBEHIND, "pattern too long to look behind")
+    local tree = newroot1sib(TBehind, pat)
+    tree.p[0].val = n;
+    return tree
+end
+
+
+-- Create a non-terminal
+
+local function lp_V(val, p)
+    assert(val, "non-nil value expected")
+    local tree = treepattern(1)
+    valuetable[tree.id] = { val }
+    tree.p[0].tag = TOpenCall
+    tree.p[0].val = 1
+    tree.p[0].cap = p or 0
+    return tree
+end
+
+
+-- Create a tree for a non-empty capture, with a body and
+-- optionally with an associated value
+
+local function capture_aux(cap, pat, val)
+    local tree = newroot1sib(TCapture, pat)
+    tree.p[0].cap = cap
+    if val then
+        local ind = #valuetable[tree.id] + 1
+        assert(ind <= 65536, "too many Lua values in pattern" .. ind)
+        valuetable[tree.id][ind] = val
+        tree.p[0].val = ind
+    end
+    return tree
+end
+
+
+-- Fill a tree with an empty capture, using an empty (TTrue) sibling.
+
+local function auxemptycap(tree, cap, par, start)
+    tree.p[start].tag = TCapture;
+    tree.p[start].cap = cap
+    if type(par) ~= 'nil' then
+        local ind = #valuetable[tree.id] + 1
+        assert(ind <= 65536, "too many Lua values in pattern")
+        valuetable[tree.id][ind] = par
+        tree.p[start].val = ind
+    end
+    tree.p[start + 1].tag = TTrue;
+end
+
+
+-- Create a tree for an empty capture
+
+local function newemptycap(cap, par)
+    local tree = treepattern(2)
+    if type(par) ~= 'nil' then valuetable[tree.id] = {} end
+    auxemptycap(tree, cap, par, 0)
+    return tree
+end
+
+
+-- Captures with syntax p / v
+-- (function capture, query capture, string capture, or number capture)
+
+local function lp_divcapture(pat, par, xxx)
+    local typ = type(par)
+    if typ == "function" then
+        return capture_aux(Cfunction, pat, par)
+    elseif typ == "table" then
+        return capture_aux(Cquery, pat, par)
+    elseif typ == "string" then
+        return capture_aux(Cstring, pat, par)
+    elseif typ == "number" then
+        local tree = newroot1sib(TCapture, pat)
+        assert(0 <= par and par <= 0xffff, "invalid number")
+        tree.p[0].cap = Cnum;
+        local ind = #valuetable[tree.id] + 1
+        assert(ind <= 65536, "too many Lua values in pattern")
+        valuetable[tree.id][ind] = par
+        tree.p[0].val = ind
+        return tree
+    else
+        error("invalid replacement value", 0)
+    end
+end
+
+
+local function lp_substcapture(pat)
+    return capture_aux(Csubst, pat)
+end
+
+
+local function lp_tablecapture(pat)
+    return capture_aux(Ctable, pat, 0)
+end
+
+
+local function lp_groupcapture(pat, val)
+    if not val then
+        return capture_aux(Cgroup, pat)
+    else
+        return capture_aux(Cgroup, pat, val)
+    end
+end
+
+
+local function lp_foldcapture(pat, fce)
+    assert(type(fce) == 'function')
+    return capture_aux(Cfold, pat, fce)
+end
+
+
+local function lp_simplecapture(pat)
+    return capture_aux(Csimple, pat)
+end
+
+
+local function lp_poscapture()
+    return newemptycap(Cposition)
+end
+
+
+local function lp_argcapture(val)
+    assert(type(val) == 'number')
+    local tree = newemptycap(Carg, 0)
+    local ind = #valuetable[tree.id] + 1
+    assert(ind <= 65536, "too many Lua values in pattern")
+    valuetable[tree.id][ind] = val
+    tree.p[0].val = ind
+    assert(0 < val and val <= 0xffff, "invalid argument index")
+    return tree
+end
+
+
+local function lp_backref(val)
+    return newemptycap(Cbackref, val)
+end
+
+
+-- Constant capture
+
+local function lp_constcapture(...)
+    local tree
+    local args = { ... }
+    local n = select('#', ...) -- number of values
+    -- no values?
+    if n == 0 then
+        tree = treepattern(1) -- no capture
+        tree.p[0].tag = TTrue
+    elseif n == 1 then
+        tree = newemptycap(Cconst, args[1]) -- single constant capture
+        -- create a group capture with all values
+    else
+        tree = treepattern(3 + 3 * (n - 1))
+        valuetable[tree.id] = {}
+        tree.p[0].tag = TCapture
+        tree.p[0].cap = Cgroup
+        local start = 1
+        for i = 1, n - 1 do
+            tree.p[start].tag = TSeq
+            tree.p[start].ps = 3
+            auxemptycap(tree, Cconst, args[i], start + 1)
+            start = start + tree.p[start].ps
+        end
+        auxemptycap(tree, Cconst, args[n], start)
+    end
+    return tree
+end
+
+
+local function lp_matchtime(pat, fce, name)
+    assert(type(fce) == 'function')
+    if name and type(name) == 'string' then
+        funcnames[fce] = name
+    end
+    local tree = newroot1sib(TRunTime, pat)
+    local ind = #valuetable[tree.id] + 1
+    assert(ind <= 65536, "too many Lua values in pattern")
+    valuetable[tree.id][ind] = fce
+    tree.p[0].val = ind
+    return tree
+end
+
+-- ======================================================
+
+
+
+-- ======================================================
+-- Grammar - Tree generation
+-- =======================================================
+
+
+-- return index and the pattern for the
+-- initial rule of grammar;
+-- also add that index into position table.
+
+local function getfirstrule(pat, postab)
+    local key
+    -- access first element
+    if type(pat[1]) == 'string' then
+        key = pat[1]
+    else
+        key = 1
+    end
+    local rule = pat[key]
+    if not rule then
+        error("grammar has no initial rule", 0)
+    end
+    -- initial rule not a pattern?
+    if not ffi.istype(treepattern, rule) then
+        error(("initial rule '%s' is not a pattern"):format(tostring(key)), 0)
+    end
+    postab[key] = 1
+    return key, rule
+end
+
+
+-- traverse grammar, collect  all its keys and patterns
+-- into rule table. Create a new table (before all pairs key-pattern) to
+-- collect all keys and their associated positions in the final tree
+-- (the "position table").
+-- Return the number of rules and the total size
+-- for the new tree.
+
+local function collectrules(pat)
+    local n = 1; -- to count number of rules
+    local postab = {}
+    local firstkeyrule, firstrule = getfirstrule(pat, postab)
+    local rules = { firstkeyrule, firstrule }
+    local size = 2 + firstrule.treesize -- TGrammar + TRule + rule
+    for key, val in pairs(pat) do
+        -- initial rule?
+        if key ~= 1 and tostring(val) ~= tostring(firstrule) then
+            -- value is not a pattern?
+            if not ffi.istype(treepattern, val) then
+                error(("rule '%s' is not a pattern"):format(tostring(key)), 0)
+            end
+            rules[#rules + 1] = key
+            rules[#rules + 1] = val
+            postab[key] = size
+            size = 1 + size + val.treesize
+            n = n + 1
+        end
+    end
+    size = size + 1; -- TTrue to finish list of rules
+    return n, size, rules, postab
+end
+
+
+local function buildgrammar(grammar, rules, n, index, valuetable)
+    local ktable, offset = {}, 0
+    -- add each rule into new tree
+    for i = 1, n do
+        local size = rules[i * 2].treesize
+        grammar.p[index].tag = TRule;
+        grammar.p[index].cap = i; -- rule number
+        grammar.p[index].ps = size + 1; -- point to next rule
+        local ind = #ktable + 1
+        ktable[ind] = rules[i * 2 - 1]
+        grammar.p[index].val = ind
+        ffi.copy(grammar.p + index + 1, rules[i * 2].p, ffi.sizeof(treepatternelement) * size) -- copy rule
+        ktable, offset = copykeys(ktable, valuetable[rules[i * 2].id])
+        if offset > 0 then
+            correctkeys(grammar, index + 1, offset)
+        end
+        index = index + grammar.p[index].ps; -- move to next rule
+    end
+    grammar.p[index].tag = TTrue; -- finish list of rules
+    return ktable
+end
+
+
+-- Check whether a tree has potential infinite loops
+
+local function checkloops(tree, index)
+    local tag = tree.p[index].tag
+    if tag == TRep and lpcode.checkaux(tree, PEnullable, index + 1) then
+        return true
+    elseif tag == TGrammar then
+        return -- sub-grammars already checked
+    else
+        local tag = numsiblings[tree.p[index].tag + 1]
+        if tag == 0 then
+            return
+        elseif tag == 1 then
+            return checkloops(tree, index + 1)
+        elseif tag == 2 then
+            if checkloops(tree, index + 1) then
+                return true
+            else
+                return checkloops(tree, index + tree.p[index].ps)
+            end
+        else
+            assert(false)
+        end
+    end
+end
+
+-- Check whether a rule can be left recursive; returns PEleftrecursion in that
+-- case; otherwise return 1 iff pattern is nullable.
+
+local function verifyrule(rulename, tree, passed, nullable, index, valuetable)
+    local tag = tree.p[index].tag
+    if tag == TChar or tag == TSet or tag == TAny or tag == TFalse then
+        return nullable; -- cannot pass from here
+    elseif tag == TTrue or tag == TBehind then
+        return true;
+    elseif tag == TNot or tag == TAnd or tag == TRep then
+        return verifyrule(rulename, tree, passed, true, index + 1, valuetable)
+    elseif tag == TCapture or tag == TRunTime then
+        return verifyrule(rulename, tree, passed, nullable, index + 1, valuetable)
+    elseif tag == TCall then
+        local rule = valuetable[tree.p[index].val]
+        if rule == rulename then return PEleftrecursion end
+        if passed[rule] and passed[rule] > MAXRULES then
+            return nullable
+        end
+        return verifyrule(rulename, tree, passed, nullable, index + tree.p[index].ps, valuetable)
+        -- only check 2nd child if first is nullable
+    elseif tag == TSeq then
+        local res = verifyrule(rulename, tree, passed, false, index + 1, valuetable)
+        if res == PEleftrecursion then
+            return res
+        elseif not res then
+            return nullable
+        else
+            return verifyrule(rulename, tree, passed, nullable, index + tree.p[index].ps, valuetable)
+        end
+        -- must check both children
+    elseif tag == TChoice then
+        nullable = verifyrule(rulename, tree, passed, nullable, index + 1, valuetable)
+        if nullable == PEleftrecursion then return nullable end
+        return verifyrule(rulename, tree, passed, nullable, index + tree.p[index].ps, valuetable)
+    elseif tag == TRule then
+        local rule = valuetable[tree.p[index].val]
+        passed[rule] = (passed[rule] or 0) + 1
+        return verifyrule(rulename, tree, passed, nullable, index + 1, valuetable)
+    elseif tag == TGrammar then
+        return lpcode.checkaux(tree, PEnullable, index) -- sub-grammar cannot be left recursive
+    else
+        assert(false)
+    end
+end
+
+
+local function verifygrammar(rule, index, valuetable)
+    -- check left-recursive rules
+    local LR = {}
+    local ind = index + 1
+    while rule.p[ind].tag == TRule do
+        local rulename = valuetable[rule.p[ind].val]
+        -- used rule
+        if rulename then
+            if verifyrule(rulename, rule, {}, false, ind + 1, valuetable) == PEleftrecursion then
+                if not LREnable then
+                    error(("rule '%s' may be left recursive"):format(rulename), 0)
+                end
+                LR[rulename] = true
+            end
+        end
+        ind = ind + rule.p[ind].ps
+    end
+    assert(rule.p[ind].tag == TTrue)
+
+    for i = 0, rule.treesize - 1 do
+        if rule.p[i].tag == TRule and LR[valuetable[rule.p[i].val]] then
+            rule.p[i].cap = bor(rule.p[i].cap, RuleLR) --TRule can be left recursive
+        end
+        if rule.p[i].tag == TCall and LR[valuetable[rule.p[i].val]] then
+            if rule.p[i].cap == 0 then
+                rule.p[i].cap = 1 --TCall can be left recursive
+            end
+        end
+    end
+
+    -- check infinite loops inside rules
+    ind = index + 1
+    while rule.p[ind].tag == TRule do
+        -- used rule
+        if rule.p[ind].val then
+            if checkloops(rule, ind + 1) then
+                error(("empty loop in rule '%s'"):format(tostring(valuetable[rule.p[ind].val])), 0)
+            end
+        end
+        ind = ind + rule.p[ind].ps
+    end
+    assert(rule.p[ind].tag == TTrue)
+end
+
+
+-- Give a name for the initial rule if it is not referenced
+
+local function initialrulename(grammar, val, valuetable)
+    grammar.p[1].cap = bit.bor(grammar.p[1].cap, Ruleused)
+    -- initial rule is not referenced?
+    if grammar.p[1].val == 0 then
+        local ind = #valuetable + 1
+        assert(ind <= 65536, "too many Lua values in pattern")
+        valuetable[ind] = val
+        grammar.p[1].val = ind
+    end
+end
+
+
+function newgrammar(pat)
+    -- traverse grammar. Create a new table (before all pairs key-pattern) to
+    -- collect all keys and their associated positions in the final tree
+    -- (the "position table").
+    -- Return new tree.
+
+    local n, size, rules, postab = collectrules(pat)
+    local grammar = treepattern(size)
+    local start = 0
+    grammar.p[start].tag = TGrammar
+    grammar.p[start].val = n
+    valuetable[grammar.id] = buildgrammar(grammar, rules, n, start + 1, valuetable)
+    finalfix(true, postab, grammar, start + 1, valuetable[grammar.id])
+    initialrulename(grammar, rules[1], valuetable[grammar.id])
+    verifygrammar(grammar, 0, valuetable[grammar.id])
+    return grammar
+end
+
+-- ======================================================
+
+-- remove duplicity from value table
+
+local function reducevaluetable(p)
+    local vtable = valuetable[p.id]
+    local value = {}
+    local newvaluetable = {}
+
+    local function check(v)
+        if v > 0 then
+            local ord = value[vtable[v]]
+            if not ord then
+                newvaluetable[#newvaluetable + 1] = vtable[v]
+                ord = #newvaluetable
+                value[vtable[v]] = ord
+            end
+            return ord
+        end
+        return 0
+    end
+
+    local function itertree(p, index)
+        local tag = p.p[index].tag
+        if tag == TSet or tag == TCall or tag == TOpenCall or
+                tag == TRule or tag == TCapture or tag == TRunTime then
+            p.p[index].val = check(p.p[index].val)
+        end
+        local ns = numsiblings[tag + 1]
+        if ns == 0 then
+        elseif ns == 1 then
+            return itertree(p, index + 1)
+        elseif ns == 2 then
+            itertree(p, index + 1)
+            return itertree(p, index + p.p[index].ps)
+        else
+            assert(false)
+        end
+    end
+
+    if p.treesize > 0 then
+        itertree(p, 0)
+    end
+    if p.code ~= nil then
+        for i = 0, p.code.size - 1 do
+            local code = p.code.p[i].code
+            if code == ICall or code == IJmp then
+                p.code.p[i].aux = check(p.code.p[i].aux)
+            elseif code == ISet or code == ITestSet or code == ISpan then
+                p.code.p[i].val = check(p.code.p[i].val)
+            elseif code == IOpenCapture or code == IFullCapture then
+                p.code.p[i].offset = check(p.code.p[i].offset)
+            end
+        end
+    end
+    valuetable[p.id] = newvaluetable
+end
+
+
+local function checkalt(tree)
+    local notchecked = {}
+    local notinalternativerules = {}
+
+    local function iter(tree, index, choice, rule)
+        local tag = tree[index].tag
+        if tag == TCapture and bit.band(tree[index].cap, 0xffff) == Cgroup then
+            if not choice then
+                if rule then
+                    notchecked[rule] = index
+                end
+            else
+                tree[index].cap = bit.bor(tree[index].cap, BCapcandelete)
+            end
+        elseif tag == TChoice then
+            choice = true
+        elseif tag == TRule then
+            rule = tree[index].val
+            if bit.band(tree[index].cap, 0xffff) - 1 == 0 then
+                notinalternativerules[rule] = notinalternativerules[rule] or true
+            end
+        elseif tag == TCall then
+            local r = tree[index].val
+            if not choice then
+                notinalternativerules[r] = notinalternativerules[r] or true
+            end
+        end
+        local sibs = numsiblings[tree[index].tag + 1] or 0
+        if sibs >= 1 then
+            iter(tree, index + 1, choice, rule)
+            if sibs >= 2 then
+                return iter(tree, index + tree[index].ps, choice, rule)
+            end
+        end
+    end
+
+    iter(tree, 0)
+    for k, v in pairs(notchecked) do
+        if not notinalternativerules[k] then
+            tree[v].cap = bit.bor(tree[v].cap, BCapcandelete)
+        end
+    end
+end
+
+
+local function prepcompile(p, index)
+    finalfix(false, nil, p, index, valuetable[p.id])
+    checkalt(p.p)
+    lpcode.compile(p, index, valuetable[p.id])
+    reducevaluetable(p)
+    return p.code
+end
+
+
+local function lp_printtree(pat, c)
+    assert(pat.treesize > 0)
+    if c then
+        finalfix(false, nil, pat, 0, valuetable[pat.id])
+    end
+    lpprint.printtree(pat.p, 0, 0, valuetable[pat.id])
+end
+
+
+local function lp_printcode(pat)
+    -- not compiled yet?
+    if pat.code == nil then
+        prepcompile(pat, 0)
+    end
+    lpprint.printpatt(pat.code, valuetable[pat.id])
+end
+
+
+-- Main match function
+
+local function lp_match(pat, s, init, ...)
+    local p = ffi.istype(treepattern, pat) and pat or getpatt(pat)
+    p.code = p.code ~= nil and p.code or prepcompile(p, 0)
+    return lpvm.match(p, s, init, valuetable[p.id], ...)
+end
+
+local function lp_streammatch(pat, init, ...)
+    local p = ffi.istype(treepattern, pat) and pat or getpatt(pat)
+    p.code = p.code ~= nil and p.code or prepcompile(p, 0)
+    return lpvm.streammatch(p, init, valuetable[p.id], ...)
+end
+
+-- Only for testing purpose
+-- stream emulation (send all chars from string one char after char)
+local function lp_emulatestreammatch(pat, s, init, ...)
+    local p = ffi.istype(treepattern, pat) and pat or getpatt(pat)
+    p.code = p.code ~= nil and p.code or prepcompile(p, 0)
+    return lpvm.emulatestreammatch(p, s, init, valuetable[p.id], ...)
+end
+
+-- {======================================================
+-- Library creation and functions not related to matching
+-- =======================================================
+
+local function lp_setmax(val)
+    lpvm.setmax(val)
+end
+
+local function lp_setmaxbehind(val)
+    lpvm.setmaxbehind(val)
+end
+
+local function lp_enableleftrecursion(val)
+    LREnable = val
+end
+
+local function lp_version()
+    return VERSION
+end
+
+
+local function lp_type(pat)
+    if ffi.istype(treepattern, pat) then
+        return "pattern"
+    end
+end
+
+
+local function createcat(tab, catname, catfce)
+    local t, set = newcharset()
+    for i = 0, 255 do
+        if catfce(i) ~= 0 then
+            set[rshift(i, 5)] = bor(set[rshift(i, 5)], lshift(1, band(i, 31)))
+        end
+    end
+    tab[catname] = t
+end
+
+
+local function lp_locale(tab)
+    tab = tab or {}
+    createcat(tab, "alnum", function(c) return ffi.C.isalnum(c) end)
+    createcat(tab, "alpha", function(c) return ffi.C.isalpha(c) end)
+    createcat(tab, "cntrl", function(c) return ffi.C.iscntrl(c) end)
+    createcat(tab, "digit", function(c) return ffi.C.isdigit(c) end)
+    createcat(tab, "graph", function(c) return ffi.C.isgraph(c) end)
+    createcat(tab, "lower", function(c) return ffi.C.islower(c) end)
+    createcat(tab, "print", function(c) return ffi.C.isprint(c) end)
+    createcat(tab, "punct", function(c) return ffi.C.ispunct(c) end)
+    createcat(tab, "space", function(c) return ffi.C.isspace(c) end)
+    createcat(tab, "upper", function(c) return ffi.C.isupper(c) end)
+    createcat(tab, "xdigit", function(c) return ffi.C.isxdigit(c) end)
+    return tab
+end
+
+
+local function lp_new(ct, size)
+    local pat = ffi.new(ct, size)
+    pat.treesize = size
+    patternid = patternid + 1
+    pat.id = patternid
+    return pat
+end
+
+
+local function lp_gc(ct)
+    valuetable[ct.id] = nil
+    if ct.code ~= nil then
+        ffi.C.free(ct.code.p)
+        ffi.C.free(ct.code)
+    end
+end
+
+local function lp_eq(ct1, ct2)
+    return tostring(ct1) == tostring(ct2)
+end
+
+local function lp_load(str, fcetab)
+    local pat, t = lpvm.load(str, fcetab, true)
+    valuetable[pat.id] = t
+    return pat
+end
+
+local function lp_loadfile(fname, fcetab)
+    local pat, t = lpvm.loadfile(fname, fcetab, true)
+    valuetable[pat.id] = t
+    return pat
+end
+
+local function lp_dump(ct, tree)
+    local funccount = 0
+    -- not compiled yet?
+    if ct.code == nil then
+        prepcompile(ct, 0)
+    end
+    local out = {}
+    if tree then
+        out[#out + 1] = ffi.string(uint32(ct.treesize), 4)
+        out[#out + 1] = ffi.string(ct.p, ffi.sizeof(treepatternelement) * ct.treesize)
+    else
+        out[#out + 1] = ffi.string(uint32(0), 4)
+    end
+    out[#out + 1] = ffi.string(uint32(ct.code.size), 4)
+    out[#out + 1] = ffi.string(ct.code.p, ct.code.size * ffi.sizeof(patternelement))
+    local t = valuetable[ct.id]
+    local len = t and #t or 0
+    out[#out + 1] = ffi.string(uint32(len), 4)
+    if len > 0 then
+        for _, val in ipairs(t) do
+            local typ = type(val)
+            if typ == 'string' then
+                out[#out + 1] = 'str'
+                out[#out + 1] = ffi.string(uint32(#val), 4)
+                out[#out + 1] = val
+            elseif typ == 'number' then
+                local val = tostring(val)
+                out[#out + 1] = 'num'
+                out[#out + 1] = ffi.string(uint32(#val), 4)
+                out[#out + 1] = val
+            elseif typ == 'cdata' then
+                out[#out + 1] = 'cdt'
+                out[#out + 1] = ffi.string(val, ffi.sizeof(val))
+            elseif typ == 'function' then
+                out[#out + 1] = 'fnc'
+                funccount = funccount + 1
+                local name = funcnames[val] or ('FNAME%03d'):format(funccount)
+                out[#out + 1] = ffi.string(uint32(#name), 4)
+                out[#out + 1] = name
+                if not funcnames[val] and debug.getupvalue(val, 1) then
+                    io.write(("Patterns function (%d) contains upvalue (%s) - use symbol name for function (%s).\n"):format(funccount, debug.getupvalue(val, 1), name), 0)
+                end
+                local data = string.dump(val, true)
+                out[#out + 1] = ffi.string(uint32(#data), 4)
+                out[#out + 1] = data
+            else
+                error(("Type '%s' NYI for dump"):format(typ), 0)
+            end
+        end
+    end
+    return table.concat(out)
+end
+
+local function lp_save(ct, fname, tree)
+    local file = assert(io.open(fname, 'wb'))
+    file:write(lp_dump(ct, tree))
+    file:close()
+end
+
+
+local pattreg = {
+    ["ptree"] = lp_printtree,
+    ["pcode"] = lp_printcode,
+    ["match"] = lp_match,
+    ["streammatch"] = lp_streammatch,
+    ["emulatestreammatch"] = lp_emulatestreammatch,
+    ["setmaxbehind"] = lp_setmaxbehind,
+    ["B"] = lp_behind,
+    ["V"] = lp_V,
+    ["C"] = lp_simplecapture,
+    ["Cc"] = lp_constcapture,
+    ["Cmt"] = lp_matchtime,
+    ["Cb"] = lp_backref,
+    ["Carg"] = lp_argcapture,
+    ["Cp"] = lp_poscapture,
+    ["Cs"] = lp_substcapture,
+    ["Ct"] = lp_tablecapture,
+    ["Cf"] = lp_foldcapture,
+    ["Cg"] = lp_groupcapture,
+    ["P"] = lp_P,
+    ["S"] = lp_set,
+    ["R"] = lp_range,
+    ["L"] = lp_and,
+    ["locale"] = lp_locale,
+    ["version"] = lp_version,
+    ["setmaxstack"] = lp_setmax,
+    ["type"] = lp_type,
+    ["enableleftrecursion"] = lp_enableleftrecursion,
+    ["enablememoization"] = lpvm.enablememoization,
+    ["enabletracing"] = lpvm.enabletracing,
+    ["save"] = lp_save,
+    ["dump"] = lp_dump,
+    ["load"] = lp_load,
+    ["loadfile"] = lp_loadfile,
+    ["__mul"] = lp_seq,
+    ["__add"] = lp_choice,
+    ["__pow"] = lp_star,
+    ["__len"] = lp_and,
+    ["__div"] = lp_divcapture,
+    ["__unm"] = lp_not,
+    ["__sub"] = lp_sub,
+}
+
+local metareg = {
+    ["__gc"] = lp_gc,
+    ["__new"] = lp_new,
+    ["__mul"] = lp_seq,
+    ["__add"] = lp_choice,
+    ["__pow"] = lp_star,
+    ["__len"] = lp_and,
+    ["__div"] = lp_divcapture,
+    ["__unm"] = lp_not,
+    ["__sub"] = lp_sub,
+    ["__eq"] = lp_eq,
+    ["__index"] = pattreg
+}
+
+ffi.metatype(treepattern, metareg)
+
+return pattreg