Module:User:Cscott/llpeg
 | This module is rated as beta, and is ready for widespread use. It is still new and should be used with some caution to ensure the results are as expected. |
This is a port to Scribunto lua of lpeglabel, which itself is a minor extension of the lua lpeg parser generator. The API should be identical to that of lpeglabel, except that the regular expressions are "natively unicode"; that is, the . pattern matches a single unicode codepoint, not a single byte as in the original.
These files have been packaged using a script to turn them into a single lua file.
Usage
[edit]{{#invoke:User:Cscott/llpeg|function_name}}
return (function()
local builders = {}
local function register(name, f)
builders[name] = f
end
register('advent.compat', function() return require [[Module:User:Cscott/compat]] end)
register('llpeg.types', function(myrequire)
myrequire('strict')
local compat = myrequire('advent.compat')
local CHARMAX = 0x7F -- maximum codepoint for charsets
-- metatable for pattern objects; will be filled in later
local metareg = {}
local enum = function(keys)
local Enum = {}
Enum.__index = Enum
function Enum:__tostring() return self.name end
function Enum:pairs() return keys end
function Enum:type() return Enum end
for name, value in pairs(keys) do
Enum[name] = setmetatable({ name = name, value = value }, Enum)
end
return Enum
end
local CapKind = enum{
close = "close", -- not used in trees */
position = "position",
const = "constant", -- ktable[key] is Lua constant
backref = "backref", -- ktable[key] is "name" of group to get capture
arg = "argument", -- 'key' is arg's number
simple = "simple", -- next node is pattern
table = "table", -- next node is pattern
["function"] = "function", -- ktable[key] is function; next node is pattern
acc = "acc", -- ktable[key] is function; next node is pattern
query = "query", -- ktable[key] is table; next node is pattern
string = "string", -- ktable[key] is string; next node is pattern
num = "num", -- numbered capture; 'key' is number of value to return
subst = "substitution", -- substitution capture; next node is pattern
fold = "fold", -- ktable[key] is function; next node is pattern
runtime = "runtime", -- not used in trees (is uses another type for tree)
group = "group", -- ktable[key] is group's "name"
}
local TTag = enum{
Char = "char", -- 'n' has unicode codepoint
Set = "set", -- 'set' has sparse array codepoint->true for codepoint <=CHARMAX
-- 'rest' indicates whether all codepoints > CHARMAX should be
-- part of the set (true) or not (false)
Any = "any",
True = "true",
False = "false",
UTFR = "utf8.range", --[[ range of UTF-8 codepoints;
'from' has initial codepoint; 'to' has final codepoint ]]--
Rep = "rep", -- 'sib1' *
Seq = "seq", -- 'sib1' 'sib2'
Choice = "choice", -- 'sib1' / 'sib2'
Not = "not", -- !'sib1'
And = "and", -- &'sib1'
Call = "call", -- 'sib2' is rule being called; otherwise same as TOpenCall
OpenCall = "opencall", -- 'key' is rule name
Rule = "rule", --[[ 'key' is rule name (but key == nil for unused rules);
'sib1' is rule's pattern pre-rule; 'sib2' is next rule;
'n' is rule's sequential number, 'name' is rule name (even
for unused rules) ]]--
XInfo = "xinfo", -- extra info (not used)
Grammar = "grammar", -- 'sib1' is initial (and first) rule, 'n' is # rules
Behind = "behind", -- 'sib1' is pattern, 'n' is how much to go back
Capture = "capture", --[[ captures: 'cap' is kind of capture (enum 'CapKind');
'key' is Lua value associated with capture;
'sib1' is capture body ]]--
RunTime = "run-time", --[[ run-time capture: 'key' is Lua function;
'sib1' is capture body ]]--
Throw = "throw", -- labeled failure: 'key' is label's name,
-- sib2 is associated recovery rule
}
local PE = enum{
nullable = "nullable",
nofail = "nofail",
}
-- virtual machine instructions
local Opcode = enum{
Any = "any", -- if no char, fail
Char = "char", -- if char != aux, fail
Set = "set", -- if char not in buff, fail
TestAny = "testany", -- in no char, jump to 'offset'
TestChar = "testchar", -- if char != aux, jump to 'offset'
TestSet = "testset", -- if char not in buff, jump to 'offset'
Span = "span", -- read a span of chars in buff
UTFR = "utf-range", -- if codepoint not in range [offset, utf_to], fail
Behind = "behind", -- walk back 'aux' characters (fail if not possible)
Ret = "ret", -- return from a rule
End = "end", -- end of pattern
Choice = "choice", -- stack a choice; next fail will jump to 'offset'
PredChoice = "pred_choice", -- labeled failure: stack a choice; changes label env next fail will jump to 'offset'
Jmp = "jmp", -- jump to 'offset'
Call = "call", -- call rule at 'offset'
OpenCall = "open_call", -- call rule number 'key' (must be closed to a ICall)
Commit = "commit", -- pop choice and jump to 'offset'
PartialCommit = "partial_commit", -- update top choice to current position and jump
BackCommit = "back_commit", -- backtrack like "fail" but jump to its own 'offset'
FailTwice = "failtwice", -- pop one choice and then fail
Fail = "fail", -- go back to saved state on choice and jump to saved offset
Giveup = "giveup", -- internal use
FullCapture = "fullcapture", -- complete capture of last 'off' chars
OpenCapture = "opencapture", -- start a capture
CloseCapture = "closecapture",
CloseRunTime = "closeruntime",
Throw = "throw", -- fails with a given label --labeled failure
ThrowRec = "throw_rec", -- fails with a given label and call rule at 'offset' --labeled failure
Empty = "--", -- to fill empty slots left by optimizations
}
-- helper for visitor pattern definitions
function define(dispatch, which, f)
for _,v in pairs(which) do
assert(v ~= nil) -- catch typos
dispatch[v] = f
end
end
local numsiblings = {}
define(numsiblings, {
TTag.Char, TTag.Set, TTag.Any,
TTag.True, TTag.False, TTag.UTFR,
TTag.Call, TTag.OpenCall,
TTag.Throw,
}, 0)
define(numsiblings, {
TTag.Rep, TTag.Not, TTag.And, TTag.Grammar,
TTag.Behind, TTag.Capture, TTag.RunTime,
}, 1)
define(numsiblings, {
TTag.Seq, TTag.Choice, TTag.Rule,
}, 2)
-- more help for visitor functions
local function_name_registry = {}
function register_fname(name, f)
assert(type(name) == "string")
assert(type(f) == "function")
function_name_registry[f] = name
end
function report_ferror(f, msg)
local fname = function_name_registry[f]
if fname ~= nil then
msg = fname .. ": " .. msg
end
error(msg)
end
function define_type_visitor(tbl)
local dispatch = {}
for keys,func in pairs(tbl) do
if type(keys) ~= "table" then
keys = { keys }
end
define(dispatch, keys, func)
end
local visit
visit = function(val, ...)
local a = dispatch["assert"]
if a ~= nil then a(val, ...) end -- assert preconditions
local ty = type(val)
if ty == 'table' and getmetatable(val) == metareg then
ty = 'pattern'
end
local f = dispatch[ty]
if f ~= nil then return f(val, ...) end
f = dispatch.default
if f == nil then
report_ferror(visit, "no default for " .. ty)
end
return f(val, ...)
end
return visit
end
function define_tree_visitor(tbl, opt_name)
local dispatch = {}
for keys,func in pairs(tbl) do
if type(keys) ~= "table" or getmetatable(keys) == TTag then
keys = { keys }
end
define(dispatch, keys, func)
end
local visit
visit = function(tree, ...)
if tree == nil then report_ferror(visit, "nil tree") end
local a = dispatch["assert"]
if a ~= nil then a(tree, ...) end -- assert preconditions
local f = dispatch[tree.tag]
if f ~= nil then return f(tree, ...) end
f = dispatch.default
if f == nil then
report_ferror(visit, "no default for " .. tree.tag)
end
return f(tree, ...)
end
return visit
end
function define_opcode_visitor(tbl)
local dispatch = {}
for keys,func in pairs(tbl) do
if type(keys) ~= "table" or getmetatable(keys) == Opcode then
keys = { keys }
end
define(dispatch, keys, func)
end
local visit
visit = function(op, ...)
if op == nil then report_ferror(visit, "nil op") end
local a = dispatch["assert"]
if a ~= nil then a(op, ...) end -- assert preconditions
local f = dispatch[op.code]
if f ~= nil then return f(op, ...) end
f = dispatch.default
if f == nil then
report_ferror(visit, "no default for " .. op.code)
end
return f(op, ...)
end
return visit
end
-- helper for module imports
function from(mod, list)
local result = {}
for _,v in ipairs(list) do
table.insert(result, mod[v])
end
return compat.unpack(result)
end
function newcharset()
return setmetatable({
tag = TTag.Set,
code = nil,
rest = false,
set = {}
}, metareg)
end
local fullset = newcharset()
for i = 0,CHARMAX do
fullset.set[i] = true
end
fullset.rest = true -- make sure non-ascii unicode chars are included!
assert(fullset.tag == TTag.Set)
return {
CHARMAX = CHARMAX,
CapKind = CapKind,
Opcode = Opcode,
PE = PE,
TTag = TTag,
define = define,
define_tree_visitor = define_tree_visitor,
enum = enum,
from = from,
fullset = fullset,
metareg = metareg,
newcharset = newcharset,
numsiblings = numsiblings,
register_fname = register_fname,
}
end)
register('llpeg.print', function(myrequire)
myrequire('strict')
local compat = myrequire('advent.compat')
local from = myrequire('llpeg.types').from
local
CHARMAX,
CapKind,
Opcode,
TTag,
define,
define_tree_visitor,
numsiblings,
_ = from(myrequire('llpeg.types'), {
'CHARMAX',
'CapKind',
'Opcode',
'TTag',
'define',
'define_tree_visitor',
'numsiblings',
})
function printcharset(tree)
local result = "["
local i = 0
while i <= CHARMAX do
local first = i
while tree.set[i] and i <= CHARMAX do
i = i + 1
end
if first == (i - 1) then -- unary range
result = result .. string.format("(%02x)", first)
elseif first < (i-1) then -- non-empty range
result = result .. string.format("(%02x-%02x)", first, i - 1)
end
i = i + 1
end
if tree.rest then
result = result .. "(80-FFFF)"
end
return result .. "]"
end
function printjmp(op, pc)
return "-> " .. op.target
end
local printinst_helper = define_opcode_visitor{
[Opcode.Char] = function(op, pc)
return string.format("'%c' (%02x)", op.aux, op.aux)
end,
[Opcode.TestChar] = function(op, pc)
return string.format("'%c' (%02x)", op.aux, op.aux) .. printjmp(op, pc)
end,
[Opcode.UTFR] = function(op, pc)
return string.format("%d - %d", op.from, op.to)
end,
[Opcode.FullCapture] = function(op, pc)
return string.format("%s (size = %s) (idx = %s)",
op.cap.value, op.aux, op.key)
end,
[Opcode.OpenCapture] = function(op, pc)
return string.format("%s (idx = %s)",
op.cap.value, op.key)
end,
[Opcode.Set] = function(op, pc)
return printcharset(op)
end,
[Opcode.TestSet] = function(op, pc)
return printcharset(op) .. printjmp(op, pc)
end,
[Opcode.Span] = function(op, pc)
return printcharset(op)
end,
[Opcode.OpenCall] = function(op, pc)
return string.format("-> %d", op.target) -- rule number
end,
[Opcode.Behind] = function(op, pc)
return string.format("%d", op.aux)
end,
[{Opcode.Jmp, Opcode.Call, Opcode.Commit, Opcode.Choice,
Opcode.PartialCommit, Opcode.BackCommit, Opcode.TestAny,
Opcode.PredChoice}] = function(op, pc)
return printjmp(op, pc)
end,
[Opcode.Throw] = function(op, pc) -- labeled failure
return string.format("(idx = %s)", op.key)
end,
[Opcode.ThrowRec] = function(op, pc)
return printjmp(op, pc) .. string.format("(idx = %s)", op.key)
end,
default = function() return '' end,
}
function printinst(pc, op, accum)
table.insert(accum, string.format("%02d: %s ", pc, op.code.value))
table.insert(accum, printinst_helper(op, pc))
table.insert(accum, "\n")
return accum
end
function printpatt(code, accum)
for pc,op in ipairs(code) do
printinst(pc, op, accum)
end
return accum
end
function printcap(cap, indent)
print(string.format("%s%s", string.rep(' ', indent), cap))
end
function printcap2close(captures, ncaptures, i, indent)
local head = captures[i]
i = i + 1
printcap(head, indent) -- print head capture
while i <= ncaptures and head:inside(captures[i]) do
i = printcap2close(captures, ncaptures, i, indent + 2) -- print nested captures
end
if i <= ncaptures and head:isopencap() then
assert(captures[i]:isclosecap())
printcap(captures[i], indent) -- print and skip close capture
i = i + 1
end
return i
end
function printcaplist(captures, ncaptures)
-- for debugging, first print a raw list of captures
if ncaptures == nil then ncaptures = #captures end
for i=1,ncaptures do
printcap(captures[i], 0)
end
print(">======");
local i=1
while i <= ncaptures and not captures[i]:isclosecap() do
i = printcap2close(captures, ncaptures, i, 0)
end
if i > ncaptures then
print("<unmatched>")
end
print("=======");
end
local printtree_helper = define_tree_visitor{
[TTag.Char] = function(tree)
local c = compat.utf8char(tree.n)
if c:find("%C") ~= nil then -- printable?
return " '" .. c .. "'"
else
return string.format(" (%02X)", tree.n)
end
end,
[TTag.Set] = function(tree)
return printcharset(tree)
end,
[TTag.UTFR] = function(tree)
return " " .. tree.from .. " - " .. tree.to
end,
[{TTag.OpenCall, TTag.Call}] = function(tree)
local ret = string.format(" key: %s", tree.key)
local rule = tree.sib2
if rule ~= nil then
ret = ret .. " (rule: " .. rule.n .. ")"
end
return ret
end,
[TTag.Behind] = function(tree)
return " " .. tree.n
end,
[TTag.Capture] = function(tree)
return string.format(" kind: '%s' key: %s", tree.cap.value, tree.key)
end,
[TTag.Rule] = function(tree)
return string.format(" key: %s", tree.key)
end,
[TTag.XInfo] = function(tree)
return " n: " .. tree.n
end,
[TTag.Grammar] = function(tree)
return " " .. tree.n -- number of rules
end,
[TTag.Throw] = function(tree)
return string.format(" key: %s", tree.key)
end,
default = function(tree) return '' end
}
function printtree(tree, indent, accum)
local sibs = numsiblings[tree.tag]
table.insert(accum, string.rep(' ', indent))
table.insert(accum, tree.tag.value)
table.insert(accum, printtree_helper(tree))
table.insert(accum, "\n")
if tree.tag == TTag.Rule then
sibs = 1 -- don't print sib2
elseif tree.tag == TTag.Grammar then
local rule = tree.sib1
for i=1,tree.n do
printtree(rule, indent + 2, accum)
rule = rule.sib2
end
sibs = 0 -- siblings already handled
end
if sibs >= 1 then
printtree(tree.sib1, indent + 2, accum)
if sibs >= 2 then
printtree(tree.sib2, indent + 2, accum)
end
end
return accum
end
local PREFIX = "" -- could also be "l." or "lpeg." etc
local printrepl_helper
printrepl_helper = define_tree_visitor{
[TTag.True] = function(tree, buf)
table.insert(buf, PREFIX .. 'P""')
end,
[TTag.Any] = function(tree, buf)
table.insert(buf, PREFIX .. 'P(1)')
end,
[TTag.Char] = function(tree, buf)
table.insert(buf, PREFIX .. 'P"')
local c = compat.utf8char(tree.n)
if c:find("%C") ~= nil then -- printable?
table.insert(buf, c)
else
table.insert(buf, string.format('\\%02X', tree.n))
end
table.insert(buf, '"')
end,
[TTag.Set] = function(tree, buf)
local nbuf = {}
local insertchar = function(cp)
local c = compat.utf8char(cp)
if string.find(c, "^[^%w%p ]") ~= nil then
table.insert(nbuf, string.format('\\x%02X', cp))
else
table.insert(nbuf, c)
end
end
local nargs = 0
local inserttwo = function(cp1, cp2)
if nargs > 0 then table.insert(nbuf, ',') end
nargs = nargs + 1
table.insert(nbuf, '"')
insertchar(cp1)
insertchar(cp2)
table.insert(nbuf, '"')
end
local i = 0
while i <= CHARMAX do
local first = i
while tree.set[i] and i <= CHARMAX do
i = i + 1
end
if first == (i - 1) then -- unary range
inserttwo(first, first)
elseif first < (i-1) then -- non-empty range
inserttwo(first, i-1)
end
i = i + 1
end
local r = table.concat(nbuf)
if nargs == 1 then
r = PREFIX .. 'S' .. r
else
r = PREFIX .. 'S(' .. r .. ')'
end
if tree.rest then
table.insert(buf, '(')
table.insert(buf, r)
table.insert(buf, ' + ')
table.insert(buf, PREFIX)
table.insert(buf, 'utfR(0x80, 0x10FFFF))')
else
table.insert(buf, r)
end
end,
[TTag.UTFR] = function(tree, buf)
table.insert(buf, string.format("%sutfR(0x%04X, 0x%04X)", PREFIX, tree.from, tree.to))
end,
[{TTag.OpenCall, TTag.Call}] = function(tree, buf)
table.insert(buf, string.format('%sV"%s"', PREFIX, tree.key))
end,
[TTag.Not] = function(tree, buf)
table.insert(buf, '-(')
printrepl_helper(tree.sib1, buf)
table.insert(buf, ')')
end,
[TTag.Seq] = function(tree, buf)
table.insert(buf, "(")
printrepl_helper(tree.sib1, buf)
table.insert(buf, " * ")
printrepl_helper(tree.sib2, buf)
table.insert(buf, ")")
end,
[TTag.Choice] = function(tree, buf)
table.insert(buf, "(")
printrepl_helper(tree.sib1, buf)
table.insert(buf, " + ")
printrepl_helper(tree.sib2, buf)
table.insert(buf, ")")
end,
[TTag.Rep] = function(tree, buf)
printrepl_helper(tree.sib1, buf)
table.insert(buf, "^0")
end,
--[[
[TTag.Behind] = function(tree)
return " " .. tree.n
end,
]]--
[TTag.Capture] = function(tree, buf)
local repl = define_type_visitor{
string = function(v)
return '"' .. v .. '"' -- xxx should handle escapes
end,
default = tostring,
}
local name = nil
local show_patt = false
local show_key = false
if tree.cap == CapKind.simple then
name = 'C'
show_patt = true
elseif tree.cap == CapKind.subst then
name = 'Cs'
show_patt = true
elseif tree.cap == CapKind.table then
name = 'Ct'
show_patt = true
elseif tree.cap == CapKind.pos then
name = 'Cp'
elseif tree.cap == CapKind.arg then
name = 'Carg'
show_key = true
elseif tree.cap == CapKind.backref then
name = 'Cb'
show_key = true
elseif tree.cap == CapKind.group then
name = 'Cg'
show_patt = true
show_key = (tree.key ~= nil)
end
if name ~= nil then
table.insert(buf, PREFIX)
table.insert(buf, name)
table.insert(buf, '(')
if show_patt then
printrepl_helper(tree.sib1, buf)
if show_key then
table.insert(buf, ', ')
end
end
if show_key then
table.insert(buf, repl(tree.key))
end
table.insert(buf, ')')
return
end
if tree.cap == CapKind.string or
tree.cap == CapKind.num or
tree.cap == CapKind.query or
tree.cap == CapKind['function'] then
printrepl_helper(tree.sib1, buf)
table.insert(buf, ' / ')
table.insert(buf, repl(tree.key))
return
end
-- fallback
table.insert(buf, string.format("<pattern %s>", tostring(tree.tag)))
end,
[TTag.Rule] = function(tree, buf)
local key = tree.name
if type(key) == 'number' then key = string.format("[%d]", key) end
table.insert(buf, key)
table.insert(buf, " = ")
printrepl_helper(tree.sib1, buf)
end,
[TTag.Grammar] = function(tree, buf)
table.insert(buf, PREFIX .. "P{")
local rule = tree.sib1
local r = {}
local first_rule_name = rule.name
r[first_rule_name] = rule
rule = rule.sib2
local names = {}
for i=2,tree.n do
table.insert(names, rule.name)
r[rule.name] = rule
rule = rule.sib2
end
-- sort rule names
table.sort(names)
table.insert(names, 1, first_rule_name)
-- now print in order
for _,name in ipairs(names) do
printrepl_helper(r[name], buf)
table.insert(buf, ", ")
end
table.insert(buf, "}")
end,
--[[
[TTag.Throw] = function(tree)
return " key: " .. tree.key .. " (rule: " .. tree.sib2.cap .. ")"
end,
]]--
default = function(tree, buf)
table.insert(buf, string.format("<pattern %s>", tostring(tree.tag)))
end,
}
function printrepl(tree)
local buf = {}
printrepl_helper(tree, buf)
return table.concat(buf)
end
return {
printcaplist = printcaplist,
printcharset = printcharset,
printinst = printinst,
printpatt = printpatt,
printrepl = printrepl,
printtree = printtree,
}
end)
register('llpeg.code', function(myrequire)
myrequire('strict')
local compat = myrequire('advent.compat')
local from = myrequire('llpeg.types').from
local
CHARMAX,
CapKind,
Opcode,
PE,
TTag,
define,
define_tree_visitor,
fullset,
newcharset,
numsiblings,
register_fname,
_ = from(myrequire('llpeg.types'), {
'CHARMAX',
'CapKind',
'Opcode',
'PE',
'TTag',
'define',
'define_tree_visitor',
'fullset',
'newcharset',
'numsiblings',
'register_fname',
})
local printinst = myrequire('llpeg.print').printinst
local TRACE_INSTRUCTIONS = false
-- signals a "no-instruction"
local NOINST = nil
-- don't optimize captures longer than this
local MAXOFF = 15
-- forward declarations
local codegen
local CompileState = {}
CompileState.__index = CompileState
--[[
** {======================================================
** Analysis and some optimizations
** =======================================================
]]--
--[[
** Check whether a charset is empty (returns IFail), singleton (IChar),
** full (IAny), or none of those (ISet). When singleton, '*c' returns
** which character it is. (When generic set, the set was the input,
** so there is no need to return it.)
]]--
function charsettype(cs)
local count = 0
local candidate
for i,_ in pairs(cs.set) do
candidate = i
count = count + 1
end
if cs.rest then
if count == (CHARMAX + 1) then
return Opcode.Any -- full set
end
elseif count == 0 then
return Opcode.Fail -- empty set
elseif count == 1 then
return Opcode.Char, candidate -- single char
end
return Opcode.Set -- neither full nor empty nor singleton
end
-- A few basic operations on charsets; returns new object
function cs_clone(cs)
local result = newcharset()
for i,_ in pairs(cs.set) do
result.set[i] = true
end
result.rest = cs.rest
return result
end
function cs_complement(cs)
local result = newcharset()
for i=0,CHARMAX do
if not cs.set[i] then
result.set[i] = true
end
end
result.rest = not cs.rest
return result
end
function cs_intersection(a, b)
local result = newcharset()
for i,_ in pairs(a.set) do
if a.set[i] and b.set[i] then
result.set[i] = true
end
end
result.rest = a.rest and b.rest
return result
end
function cs_union(a, b)
local result = newcharset()
for i=0,CHARMAX do
if a.set[i] or b.set[i] then
result.set[i] = true
end
end
result.rest = a.rest or b.rest
return result
end
function cs_diff(a, b)
local result = newcharset()
for i=0,CHARMAX do
if a.set[i] and not b.set[i] then
result.set[i] = true
end
end
result.rest = a.rest and not b.rest
return result
end
function cs_disjoint(a, b)
if a.rest == b.rest then return false end
for i,_ in pairs(a.set) do
if b.set[i] then return false end
end
for i,_ in pairs(b.set) do
if a.set[i] then return false end
end
return true
end
function cs_equal(a, b)
if a.rest ~= b.rest then return false end
for i,_ in pairs(a.set) do
if not b.set[i] then return false end
end
for i,_ in pairs(b.set) do
if not a.set[i] then return false end
end
return true
end
--[[
** If 'tree' is a 'char' pattern (TSet, TChar, TAny), convert it into a
** charset and return it; else return nil.
]]--
local tocharset = define_tree_visitor{
[TTag.Set] = function(v)
return v -- copy set
end,
[TTag.Char] = function(v)
-- only one char
if v.n <= CHARMAX then
local t = newcharset()
t.set[v.n] = true
return t
else
return nil
end
end,
[TTag.Any] = function(v)
return fullset
end,
[TTag.False] = function(v)
return newcharset()
end,
default = function(v)
return nil
end,
}
register_fname("tocharset", tocharset)
--[[
** Visit a TCall node taking care to stop recursion. If node not yet
** visited, return 'f(rule for call)', otherwise return 'def' (default
** value)
]]--
function CompileState:callrecursive(tree, f, default_value, ...)
if tree.tag ~= TTag.Call then
error("unexpected tree tag")
end
local rule = self.grammar.ruletab[tree.key]
if rule.tag ~= TTag.Rule then
error("unexpected tree sibling")
end
if tree.seen == true then
return default_value -- node already visited
else
-- first visit
local oldseen = tree.seen
tree.seen = true
local result = f(rule, ...)
tree.seen = oldseen -- restore tree
return result
end
end
--[[
** Check whether a pattern tree has captures
]]--
local hascaptures
hascaptures = define_tree_visitor{
[{TTag.Capture, TTag.RunTime}] = function(tree, cs)
return true
end,
[TTag.Call] = function(tree, cs)
assert(cs ~= nil)
return cs:callrecursive(tree, hascaptures, false, cs)
end,
[TTag.Rule] = function(tree, cs)
-- do not follow siblings
return hascaptures(tree.sib1, cs)
end,
[TTag.OpenCall] = function(tree, cs)
error("should not happen")
end,
[TTag.Grammar] = function(tree, cs)
-- make a fake compile state to hold the grammar, if necessary
if cs == nil then cs = CompileState:new(nil) end
return cs:withGrammar(tree, hascaptures, tree.sib1, cs)
end,
default = function(tree, cs)
local n = numsiblings[tree.tag]
if n == 1 then
return hascaptures(tree.sib1, cs) -- tail call
elseif n == 2 then
if hascaptures(tree.sib1, cs) then return true end
return hascaptures(tree.sib2, cs) -- tail call
elseif n == 0 then
return false
else
error("how many siblings does this have?")
end
end,
}
function CompileState:hascaptures(t) return hascaptures(t, self) end
register_fname("hascaptures", hascaptures)
--[[
** 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 and run-time captures;
** for other patterns, 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 is not nullable;
** this will be checked again when the grammar is fixed.
** Run-time captures can do whatever they want, so the result
** is conservative.
]]--
local checkaux
checkaux = define_tree_visitor{
[{
TTag.Char, TTag.Set, TTag.Any, TTag.UTFR, TTag.False,
TTag.OpenCall, TTag.Throw,
}] = function(tree, pred, cs)
return false -- not nullable
end,
[{TTag.Rep,TTag.True}] = function(tree, pred, cs)
return true -- no fail
end,
[{TTag.Not,TTag.Behind}] = function(tree, pred, cs)
-- can match empty, but can fail
if pred == PE.nofail then
return false
else
return true
end
end,
[TTag.And] = function(tree, pred, cs)
-- can match empty; fail iff body does
if pred == PE.nullable then
return true
end
return checkaux(tree.sib1, pred, cs) -- tail call
end,
[TTag.RunTime] = function(tree, pred, cs)
-- can fail; match empty iff body does
if pred == PE.nofail then
return false
end
return checkaux(tree.sib1, pred, cs) -- tail call
end,
[TTag.Seq] = function(tree, pred, cs)
if not checkaux(tree.sib1, pred, cs) then
return false
end
return checkaux(tree.sib2, pred, cs) -- tail call
end,
[TTag.Choice] = function(tree, pred, cs)
if checkaux(tree.sib2, pred, cs) then
return true
end
return checkaux(tree.sib1, pred, cs) -- tail call
end,
[{ TTag.Capture, TTag.Rule, TTag.XInfo, }] = function(tree, pred, cs)
return checkaux(tree.sib1, pred, cs)
end,
[TTag.Grammar] = function(tree, pred, cs)
-- make a fake compile state to hold the grammar, if necessary
if cs == nil then cs = CompileState:new(nil) end
return cs:withGrammar(tree, checkaux, tree.sib1, pred, cs)
end,
[TTag.Call] = function(tree, pred, cs)
-- open calls are assumed not nullable; checked again after grammar
-- is fixed
if cs == nil then return false end
return checkaux(cs.grammar.ruletab[tree.key], pred, cs)
end,
}
register_fname("checkaux", checkaux)
function nofail(t, cs) return checkaux(t, PE.nofail, cs) end
function CompileState:nofail(t) return nofail(t, self) end
function nullable(t, cs) return checkaux(t, PE.nullable, cs) end
function CompileState:nullable(t) return nullable(t, self) end
function nullable_with_grammar(t, grm)
local cs = CompileState:new(nil)
return cs:withGrammar(grm, nullable, t, cs)
end
-- Note that we are counting characters, not bytes
local fixedlen, fixedlen_helper
fixedlen_helper = define_tree_visitor{
[{TTag.Char, TTag.Set, TTag.Any, TTag.UTFR}] = function(tree, len)
return len + 1
end,
[{TTag.False, TTag.True, TTag.Not, TTag.And, TTag.Behind}] = function(tree, len)
return len
end,
[{TTag.Rep, TTag.RunTime, TTag.OpenCall, TTag.Throw,}] = function(tree, len)
return -1 -- variable
end,
[{TTag.Capture, TTag.Rule, TTag.XInfo,}] = function(tree, len, cs)
return fixedlen_helper(tree.sib1, len, cs)
end,
[TTag.Grammar] = function(tree, len, cs)
-- make a fake compile state to hold the grammar, if necessary
if cs == nil then cs = CompileState:new(nil) end
return cs:withGrammar(tree, fixedlen_helper, tree.sib1, len, cs)
end,
[TTag.Call] = function(tree, len, cs)
-- If evaluating outside the context of a grammar, conservatively
-- return "variable"
if cs == nil then return -1 end
-- otherwise, carefully recurse
local n1 = cs:callrecursive(tree, fixedlen, -1, cs)
if n1 < 0 then return -1 end -- variable
return len + n1
end,
[TTag.Seq] = function(tree, len, cs)
local n1 = fixedlen_helper(tree.sib1, len, cs)
if n1 < 0 then return -1 end -- variable
return fixedlen_helper(tree.sib2, n1, cs)
end,
[TTag.Choice] = function(tree, len, cs)
local n1 = fixedlen_helper(tree.sib1, len, cs)
local n2 = fixedlen_helper(tree.sib2, len, cs)
if n1 ~= n2 or n1 < 0 then
return -1
else
return n1
end
end,
}
function fixedlen(tree, cs)
return fixedlen_helper(tree, 0, cs) -- supply default 0 for 'len'
end
function CompileState:fixedlen(t) return fixedlen(t, self) end
register_fname("fixedlen_helper", fixedlen_helper)
--[[
** Computes the 'first set' of a pattern.
** The result is a conservative aproximation:
** match p ax -> x (for some x) ==> a belongs to first(p)
** or
** a not in first(p) ==> match p ax -> fail (for all x)
**
** The set 'follow' is the first set of what follows the
** pattern (full set if nothing follows it).
**
** The function returns 0 when this resulting set can be used for
** test instructions that avoid the pattern altogether.
** A non-zero return can happen for two reasons:
** 1) match p '' -> '' ==> return has bit 1 set
** (tests cannot be used because they would always fail for an empty input);
** 2) there is a match-time capture ==> return has bit 2 set
** (optimizations should not bypass match-time captures).
]]--
local getfirst
getfirst = define_tree_visitor{
[TTag.Char] = function(t, follow, cs)
if t.n <= CHARMAX then return 0, tocharset(t) end
-- conservative approximation!
local s = newcharset()
s.rest = true
return 0, s
end,
[{ TTag.Set, TTag.Any, TTag.False }] = function(t, follow, cs)
return 0, tocharset(t)
end,
[TTag.UTFR] = function(t, follow, cs)
-- conservative approximation!
local firstset = newcharset()
if t.from <= CHARMAX then
for i=t.from, math.min(CHARMAX, t.to) do
firstset.set[i] = true
end
end
if t.to > CHARMAX then
-- conservative approximation of non-ascii unicode range
firstset.rest = true
end
return 0, firstset
end,
[TTag.True] = function(t, follow, cs)
return 1, follow -- 1 because this accepts the empty string
end,
[TTag.Throw] = function(t, follow, cs)
-- labeled failure: must always throw the label
return 1, fullset
end,
[TTag.Choice] = function(t, follow, cs)
local firstset = newcharset()
local e1,e1set = getfirst(t.sib1, follow, cs)
local e2,e2set = getfirst(t.sib2, follow, cs)
local firstset = cs_union(e1set, e2set)
local ret = 0 -- awkward lua5.1 way to say "e1 | e2"
if (e1 % 2) == 1 or (e2 % 2) == 1 then
ret = ret + 1
end
e1,e2 = compat.rshift(e1, 1), compat.rshift(e2, 1)
if (e1 % 2) == 1 or (e2 % 2) == 1 then
ret = ret + 2
end
return ret, firstset
end,
[TTag.Seq] = function(t, follow, cs)
if not nullable(t.sib1, cs) then
-- when p1 is not nullable, p2 has nothing to contribute
return getfirst(t.sib1, fullset, cs) -- tail call
else -- FIRST(p1 p2, fl) = FIRST(p1, FIRST(p2, fl))
local e2,csaux = getfirst(t.sib2, follow, cs)
local e1,firstset = getfirst(t.sib1, csaux, cs)
if e1 == 0 then
return 0, firstset -- 'e1' ensures that first can be used
elseif compat.rshift(e1, 1) % 2 == 1 or compat.rshift(e2, 1) % 2 == 1 then
-- one of the children has a matchtime?
return 2, firstset -- pattern has a matchtime capture
else
return e2, firstset -- else depends on e2
end
end
end,
[TTag.Rep] = function(t, follow, cs)
local _,firstset = getfirst(t.sib1, follow, cs)
return 1, cs_union(firstset, follow, cs) -- accepts the empty string
end,
[{ TTag.Capture,TTag.Rule,TTag.XInfo }] = function(t, follow, cs)
return getfirst(t.sib1, follow, cs) -- tail call
end,
[TTag.Grammar] = function(t, follow, cs)
return cs:withGrammar(t, getfirst, t.sib1, follow, cs)
end,
[TTag.RunTime] = function(t, follow, cs)
-- function invalidates any follow info
local e,firstset = getfirst(t.sib1, fullset, cs)
if e ~= 0 then
-- function is not "protected"?
return 2,firstset
else
-- pattern inside capture ensures first can be used
return 0,firstset
end
end,
[TTag.Call] = function(t, follow, cs)
local rule = cs.grammar.ruletab[t.key]
return getfirst(rule, follow, cs) -- tail call
end,
[TTag.And] = function(t, follow, cs)
local e,firstset = getfirst(t.sib1, follow, cs)
return e, cs_intersection(firstset, follow, cs)
end,
[{ TTag.Not, TTag.Behind }] = function(t, follow, cs)
if t.tag == TTag.Not then
local firstset = tocharset(t.sib1)
if firstset ~= nil then
return 1,cs_complement(firstset) -- could match empty input
end
end
-- the TNot or TBehind gives no new information
-- call getfirst only to check for math-time captures
local e,_ = getfirst(t.sib1, follow, cs)
if e%2 == 0 then e = e + 1 end -- set the lsb; could match empty input
return e, follow -- uses follow
end,
}
function CompileState:getfirst(t, follow) return getfirst(t, follow, self) end
register_fname("getfirst", getfirst)
--[[
** If 'headfail(tree)' true, then 'tree' can fail only depending on the
** next character of the subject.
-- ie, a single character of lookahead is enough to evaluate the pattern
-- rooted at this node
]]--
local headfail
headfail = define_tree_visitor{
[{TTag.Char, TTag.Set, TTag.Any,
TTag.False}] = function(t, cs)
return true
end,
[{TTag.True, TTag.Rep, TTag.RunTime, TTag.Not,
-- even though we are codepoint-based, we don't have a TestUTFR instruction
-- so we can't use a Test instruction on the first character, which is
-- implicitly what headfail is checking for.
TTag.UTFR,
TTag.Behind, TTag.Throw}] = function(t, cs)
return false
end,
[{TTag.Capture, TTag.Rule,
TTag.XInfo, TTag.And}] = function(t, cs)
return headfail(t.sib1, cs) -- tail call
end,
[TTag.Grammar] = function(t, cs)
return cs:withGrammar(t, headfail, t.sib1, cs)
end,
[TTag.Call] = function(t, cs)
local rule = cs.grammar.ruletab[t.key]
return headfail(rule, cs) -- tail call
end,
[TTag.Seq] = function(t, cs)
if not nofail(t.sib2, cs) then
-- if the second child could possibly fail, then we can't
-- evaluate the entire seq based just on the first child
return false
end
return headfail(t.sib1, cs) -- tail call
end,
[TTag.Choice] = function(t, cs)
-- both children need to be headfail for this to be headfail
if not headfail(t.sib1, cs) then
return false
end
return headfail(t.sib2, cs) -- tail call
end,
}
function CompileState:headfail(t) return headfail(t, self) end
register_fname("headfail", headfail)
--[[
** 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 needfollow
needfollow = define_tree_visitor{
[{TTag.Char, TTag.Set, TTag.Any, TTag.UTFR,
TTag.False, TTag.True, TTag.And, TTag.Not,
TTag.RunTime, TTag.Grammar, TTag.Call, TTag.Behind,
TTag.Throw, }] = function(tree) return false end,
[{TTag.Choice, TTag.Rep}] = function(tree) return true end,
[TTag.Capture] = function(tree) return needfollow(tree.sib1) end,
[TTag.Seq] = function(tree) return needfollow(tree.sib2) end,
}
register_fname("needfollow", needfollow)
--[[
** ======================================================
** Code generation
** ======================================================
]]--
local Instruction = {}
Instruction.__index = Instruction
function Instruction:new(arg)
local opcode = arg[1]
if opcode == nil then error("no opcode") end
-- target is rule # for open calls before correction, and absolute pc after
local instr = {
code = opcode,
exec = opcode.exec, -- copy the exec function from the opcode!
aux = arg.aux, -- used for the "primary argument"
key = arg.key, -- used for string-valued arguments
target = arg.target, -- used for jmp-like instructions
from = arg.from, -- inclusive start, for ranges
to = arg.to, -- inclusive end, for ranges
set = arg.set, -- charset <= CHARMAX
rest = arg.rest, -- include characters above CHARMAX?
cap = arg.cap, -- used for "capture kind"
}
setmetatable(instr, self)
instr:setCode(opcode) -- opportunity to add tracing logic!
return instr
end
function Instruction:setCode(opcode)
self.code = opcode
local exec = opcode.exec
if TRACE_INSTRUCTIONS then
local str
self.exec = function(self, state, ...)
if str == nil then
str = table.concat(printinst(0, self, { "Executing " })):gsub("\n","")
end
print(state.bytePos, state.codepoint, str)
return exec(self, state, ...)
end
else
self.exec = exec
end
end
-- state for the compiler
function CompileState:new(p)
local cs = {
p = p,
}
setmetatable(cs, self)
return cs
end
function CompileState:withGrammar(g, f, ...)
local lastGrammar = self.grammar
self.grammar = g
local result = compat.pack(f(...))
self.grammar = lastGrammar
return compat.unpack(result)
end
function CompileState:codegen(tree, opt, tt, fl)
assert(fl.tag == TTag.Set)
-- just a little helper
return codegen(tree, self, opt, tt, fl)
end
function CompileState:getinstr(i)
return self.p.code[i]
end
function CompileState:addinstruction(arg)
local code = self.p.code
table.insert(code, Instruction:new(arg))
return #code
end
function CompileState:gethere()
local code = self.p.code
return 1 + #code
end
function CompileState:jumptothere(pc, where)
if pc ~= NOINST then
local code = self.p.code
code[pc].target = where
end
end
function CompileState:jumptohere(pc)
self:jumptothere(pc, self:gethere())
end
function codethrow(cs, throw)
local rule = nil
if cs.grammar ~= nil then
-- we only lookup/match *string* rule names, not numeric indices
rule = cs.grammar.ruletab[tostring(throw.key)]
end
if rule ~= nil then
return cs:addinstruction{
Opcode.ThrowRec,
key=throw.key, -- rule name / error label
target=rule.n -- recovery rule number
}
else
return cs:addinstruction{
Opcode.Throw,
key=throw.key, -- rule name / error label
-- no recovery rule
}
end
end
function codeutfr(cs, tree)
return cs:addinstruction{
Opcode.UTFR,
from = tree.from,
to = tree.to,
}
end
--[[
** Code an IChar instruction, or IAny if there is an equivalent
** test dominating it
]]--
function codechar(cs, codepoint, tt)
if tt ~= NOINST and
cs:getinstr(tt).code == Opcode.TestChar and
cs:getinstr(tt).aux == codepoint then
cs:addinstruction{Opcode.Any}
else
cs:addinstruction{Opcode.Char, aux=codepoint,}
end
end
--[[
** Add a charset posfix to an instruction
]]--
function addcharset(cs, codepoint)
--[[
static void addcharset (CompileState *compst, const byte *cs) {
int p = gethere(compst);
int i;
for (i = 0; i < (int)CHARSETINSTSIZE - 1; i++)
nextinstruction(compst); /* space for buffer */
/* fill buffer with charset */
loopset(j, getinstr(compst, p).buff[j] = cs[j]);
]]--
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.
]]--
function codecharset(cs, tree, tt)
local op,codepoint = charsettype(tree)
if op == Opcode.Char then
return codechar(cs, codepoint, tt)
elseif op == Opcode.Set then
-- non-trivial set?
if tt ~= NOINST and
cs:getinstr(tt).code == Opcode.TestSet and
cs_equal(tree, cs:getinstr(tt)) then
return cs:addinstruction{Opcode.Any}
else
return cs:addinstruction{
Opcode.Set,
set = tree.set, -- XXX ensure immutable
rest = tree.rest,
}
end
else
return cs:addinstruction{op} -- Any or Fail
end
end
--[[
** code a test set, optimizing unit sets for ITestChar, "complete"
** sets for ITestAny, and empty sets for IJmp (always fails).
** 'e' is nonzero iff test should accept the empty string. (Test
** instructions in the current VM never accept the empty string.)
]]--
function codetestset(cs, tree, e)
if e ~= 0 then return NOINST end
local op,codepoint = charsettype(tree)
if op == Opcode.Fail then
return cs:addinstruction{Opcode.Jmp, target = NOINST} -- always jump
elseif op == Opcode.Any then
return cs:addinstruction{Opcode.TestAny, target = NOINST}
elseif op == Opcode.Char then
return cs:addinstruction{
Opcode.TestChar,
target = NOINST,
aux = codepoint,
}
elseif op == Opcode.Set then
return cs:addinstruction{
Opcode.TestSet,
target = NOINST,
set = tree.set, -- XXX ensure immutable
rest = tree.rest,
}
else
error("unreachable")
end
end
--[[
** <behind(p)> == behind n; <p> (where n = fixedlen(p))
]]--
function codebehind(cs, tree)
if tree.n > 0 then
cs:addinstruction{ Opcode.Behind, aux = tree.n }
end
return cs:codegen(tree.sib1, false, NOINST, fullset)
end
--[[
** Choice; optimizations:
** - when p1 is headfail or 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, either because p1 will accept
** (headfail) or because it is not in first(p2) (disjoint).
** (The second case 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 reuse
** the Choice already active in the stack.
]]--
function codechoice(cs, p1, p2, opt, fl)
local emptyp2 = (p2.tag == TTag.True)
local e1, cs1 = cs:getfirst(p1, fullset)
local headfailp1 = cs:headfail(p1)
local e2, cs2
if not headfailp1 and e1 == 0 then
e2, cs2 = cs:getfirst(p2, fl) -- avoid computing unless necessary
end
if headfailp1 or (e1 == 0 and cs_disjoint(cs1, cs2)) then
-- <p1 / p2> == test (fail(p1)) -> L1 ; p1 ; jmp L2; L1: p2; L2:
local test = codetestset(cs, cs1, 0)
local jmp = NOINST
cs:codegen(p1, false, test, fl)
if not emptyp2 then
jmp = cs:addinstruction{Opcode.Jmp, target = NOINST }
end
cs:jumptohere(test)
cs:codegen(p2, opt, NOINST, fl)
cs:jumptohere(jmp)
elseif opt and emptyp2 then
-- p1? == IPartialCommit; p1
cs:jumptohere(cs:addinstruction{Opcode.PartialCommit, target = NOINST})
cs:codegen(p1, true, NOINST, fullset)
else
-- <p1 / p2> ==
-- test(first(p1)) -> L1; choice L1; <p1>; commit L2; L1: <p2>; L2:
local test = codetestset(cs, cs1, e1)
local pchoice = cs:addinstruction{Opcode.Choice, target = NOINST}
cs:codegen(p1, emptyp2, test, fullset)
local pcommit = cs:addinstruction{Opcode.Commit, target = NOINST}
cs:jumptohere(pchoice)
cs:jumptohere(test)
cs:codegen(p2, opt, NOINST, fl)
cs:jumptohere(pcommit)
end
end
--[[
** And predicate
** optimization: fixedlen(p) = n ==> <&p> == <p>; behind n
** (valid only when 'p' has no captures)
]]--
function codeand(cs, tree, tt)
--[[ labeled failure: optimization disabled because in case of a failure it
does not report the expected error position (the current subject position
when begin the matching of <&p>) ]]--
local pchoice = cs:addinstruction{Opcode.PredChoice, target = NOINST}
cs:codegen(tree, false, tt, fullset)
local pcommit = cs:addinstruction{Opcode.BackCommit, target = NOINST}
cs:jumptohere(pchoice)
cs:addinstruction{Opcode.Fail}
cs:jumptohere(pcommit)
end
--[[
** Captures: if pattern has fixed (and not too big) length, and it
** has no nested captures, use a single IFullCapture instruction
** after the match; otherwise, enclose the pattern with OpenCapture -
** CloseCapture.
]]--
function codecapture(cs, tree, tt, fl)
local len = cs:fixedlen(tree.sib1)
if len >= 0 and len <= MAXOFF and not cs:hascaptures(tree.sib1) then
cs:codegen(tree.sib1, false, tt, fl)
cs:addinstruction{
Opcode.FullCapture,
cap = tree.cap,
key = tree.key, -- capture name
aux = len,
}
else
assert(tree.cap ~= nil)
cs:addinstruction({
Opcode.OpenCapture,
cap = tree.cap,
key = tree.key, -- capture name
})
cs:codegen(tree.sib1, false, tt, fl)
cs:addinstruction({
Opcode.CloseCapture,
cap = CapKind.close,
})
end
end
function coderuntime(cs, tree, tt)
cs:addinstruction({
Opcode.OpenCapture,
cap = CapKind.group,
key = tree.key, -- capture *function*
})
cs:codegen(tree.sib1, false, tt, fullset)
cs:addinstruction({
Opcode.CloseRunTime,
cap = CapKind.close,
})
end
--[[
** Repetition; 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.
]]--
function coderep(cs, tree, opt, fl)
local st = tocharset(tree)
if st ~= nil then
return cs:addinstruction{
Opcode.Span,
set = st.set,
rest = st.rest,
}
end
local e1,st = cs:getfirst(tree, fullset)
if cs:headfail(tree) or (e1 == 0 and cs_disjoint(st, fl)) then
-- L1: test (fail(p1)) -> L2; <p>; jmp L1; L2:
local test = codetestset(cs, st, 0)
cs:codegen(tree, false, test, fullset)
local jmp = cs:addinstruction{Opcode.Jmp, target = NOINST}
cs:jumptohere(test)
cs:jumptothere(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(cs, st, e1)
local pchoice = NOINST
if opt then
cs:jumptohere(cs:addinstruction{Opcode.PartialCommit, target = NOINST})
else
pchoice = cs:addinstruction{Opcode.Choice, target = NOINST}
end
local l2 = cs:gethere()
cs:codegen(tree, false, NOINST, fullset)
local commit = cs:addinstruction{Opcode.PartialCommit, target = NOINST}
cs:jumptothere(commit, l2)
cs:jumptohere(pchoice)
cs:jumptohere(test)
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).
]]--
function codenot(cs, tree)
local e,st = cs:getfirst(tree, fullset)
local test = codetestset(cs, st, e)
if cs:headfail(tree) then
-- test (fail(p1)) -> L1; fail; L1:
cs:addinstruction{Opcode.Fail}
else
-- test(fail(p))-> L1; choice L1; <p>; failtwice; L1:
local pchoice = cs:addinstruction{Opcode.PredChoice, target = NOINST }
cs:codegen(tree, false, NOINST, fullset)
cs:addinstruction{Opcode.FailTwice}
cs:jumptohere(pchoice)
end
cs:jumptohere(test)
end
-- find the final destination of a sequence of jumps
function finaltarget(code, pc)
while code[pc].code == Opcode.Jmp do
pc = code[pc].target
end
return pc
end
-- final label (after traversing any jumps)
function finallabel(code, pc)
return finaltarget(code, code[pc].target)
end
--[[
** change open calls to calls, using list 'positions' to find
** correct offsets; also optimize tail calls
]]--
function correctcalls(cs, positions, from, to)
local code = cs.p.code
for i=from,(to-1) do
local op = code[i]
if op.code == Opcode.OpenCall or op.code == Opcode.ThrowRec then
local n = op.target -- rule number
local rule = positions[n] -- rule position
if rule == from or code[rule - 1].code == Opcode.Ret then
-- sanity check! ok!
else
error("bad rule position")
end
if op.code == Opcode.OpenCall then
if code[finaltarget(code, i+1)].code == Opcode.Ret then
-- call; ret => tail call
op:setCode(Opcode.Jmp)
else
op:setCode(Opcode.Call) -- open call no more
end
end
op.target = rule
end
end
end
--[[
** Code for a grammar:
** call L1; jmp L2; L1: rule 1; ret; rule 2; ret; ...; L2:
]]--
function codegrammar(cs, tree)
local firstcall = cs:addinstruction{Opcode.Call, target = NOINST} -- call initial rule
local jumptoend = cs:addinstruction{Opcode.Jmp, target = NOINST} -- jump to the end
local start = cs:gethere() -- here starts the initial rule
cs:jumptohere(firstcall)
local positions = {}
local rule = tree.sib1
for i=1,tree.n do
local pattern = rule.sib1
positions[i] = cs:gethere() -- save rule position
cs:codegen(rule.sib1, false, NOINST, fullset) -- code rule
cs:addinstruction{Opcode.Ret}
rule = rule.sib2
end
if rule.tag ~= TTag.True then error("impossible") end
cs:jumptohere(jumptoend)
correctcalls(cs, positions, start, cs:gethere())
end
function codecall(cs, tree)
local rule = cs.grammar.ruletab[tree.key]
assert(rule ~= nil)
assert(rule.n ~= nil)
return cs:addinstruction{
Opcode.OpenCall, -- to be corrected later
target = rule.n -- rule number
}
end
--[[
** Code first child of a sequence
** (second child is called in-place to allow tail call)
** Return 'tt' for second child
]]--
function codeseq1(cs, p1, p2, tt, fl)
assert(fl.tag == TTag.Set)
if needfollow(p1) then
local _, fl1 = cs:getfirst(p2, fl) -- p1 follow is p2 first
cs:codegen(p1, false, tt, fl1)
else
-- use fullset as follow
cs:codegen(p1, false, tt, fullset)
end
if cs:fixedlen(p1) ~= 0 then -- can 'p1' consume anything?
return NOINST -- invalidate test
else
return tt -- else 'tt' still protects sib2
end
end
--[[
** Main code-generation function: dispatch to auxiliar functions
** according to kind of tree. ('needfollow' should return true
** only for consructions that use 'fl'.)
]]--
--[[
** 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.
]]--
codegen = define_tree_visitor{
[TTag.Char] = function(tree, cs, opt, tt, fl)
return codechar(cs, tree.n, tt)
end,
[TTag.Any] = function(tree, cs, opt, tt, fl)
return cs:addinstruction{Opcode.Any}
end,
[TTag.Set] = function(tree, cs, opt, tt, fl)
return codecharset(cs, tree, tt)
end,
[TTag.True] = function(tree, cs, opt, tt, fl)
return -- do nothing
end,
[TTag.False] = function(tree, cs, opt, tt, fl)
return cs:addinstruction{Opcode.Fail}
end,
[TTag.UTFR] = function(tree, cs, opt, tt, fl)
return codeutfr(cs, tree)
end,
[TTag.Choice] = function(tree, cs, opt, tt, fl)
return codechoice(cs, tree.sib1, tree.sib2, opt, fl)
end,
[TTag.Rep] = function(tree, cs, opt, tt, fl)
return coderep(cs, tree.sib1, opt, fl)
end,
[TTag.Behind] = function(tree, cs, opt, tt, fl)
return codebehind(cs, tree)
end,
[TTag.Not] = function(tree, cs, opt, tt, fl)
return codenot(cs, tree.sib1)
end,
[TTag.And] = function(tree, cs, opt, tt, fl)
return codeand(cs, tree.sib1, tt)
end,
[TTag.Capture] = function(tree, cs, opt, tt, fl)
return codecapture(cs, tree, tt, fl)
end,
[TTag.RunTime] = function(tree, cs, opt, tt, fl)
return coderuntime(cs, tree, tt)
end,
[TTag.Grammar] = function(tree, cs, opt, tt, fl)
return cs:withGrammar(tree, codegrammar, cs, tree)
end,
[TTag.Call] = function(tree, cs, opt, tt, fl)
return codecall(cs, tree)
end,
[TTag.Seq] = function(tree, cs, opt, tt, fl)
tt = codeseq1(cs, tree.sib1, tree.sib2, tt, fl) -- code 'p1'
return cs:codegen(tree.sib2, opt, tt, fl) -- tail call
end,
[TTag.Throw] = function(tree, cs, opt, tt, fl)
return codethrow(cs, tree)
end,
["assert"] = function(tree, cs, opt, tt, fl)
assert(fl.tag == TTag.Set)
assert(opt ~= 0)
end,
}
register_fname("codegen", codegen)
--[[
** 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)
]]--
function peephole(cs)
local code = cs.p.code
local jmpswitch
local switch = define_opcode_visitor{
-- instructions with labels
[{Opcode.Choice, Opcode.Call, Opcode.Commit, Opcode.PartialCommit,
Opcode.BackCommit, Opcode.TestChar, Opcode.TestSet,
Opcode.TestAny}] = function(op, i)
cs:jumptothere(i, finallabel(code, i))
end,
[Opcode.Jmp] = function(op, i)
local ft = finaltarget(code, i)
jmpswitch(code[ft], i, ft) -- jumping to what?
end,
default = function() end,
}
jmpswitch = define_opcode_visitor{
-- instructions with unconditional implicit jumps
[{Opcode.Ret,Opcode.Fail,Opcode.FailTwice,Opcode.End}] = function(op, i, ft)
code[i]:setCode(code[ft].code) -- jump becomes that instruction
end,
-- instructions with unconditional explicit jumps
[{Opcode.Commit, Opcode.PartialCommit, Opcode.BackCommit}] = function(op, i, ft)
local fft = finallabel(code, ft)
code[i]:setCode(code[ft].code) -- jump becomes that instruction
cs:jumptothere(i, fft) -- with an optimized target
switch(code[i], i) -- reoptimize the label
end,
default = function(op, i, ft)
cs:jumptothere(i, ft) -- optimize label
end,
}
for i=1,#code do
switch(code[i], i)
end
end
-- thread the instructions to speed up dispatch during execution
function thread(cs)
local code = cs.p.code
for i=1,#code-1 do
code[i].next = code[i+1]
if code[i].target ~= nil then
code[i].branch = code[code[i].target]
end
end
end
function compile(p)
local compst = CompileState:new(p)
p.code = {}
assert(fullset.tag == TTag.Set)
compst:codegen(p, false, NOINST, fullset)
compst:addinstruction{Opcode.End}
peephole(compst)
thread(compst)
return p.code
end
return {
Instruction = Instruction,
compile = compile,
cs_clone = cs_clone,
cs_complement = cs_complement,
cs_diff = cs_diff,
cs_intersection = cs_intersection,
cs_union = cs_union,
fixedlen = fixedlen,
hascaptures = hascaptures,
nofail = nofail,
nullable = nullable,
nullable_with_grammar = nullable_with_grammar,
tocharset = tocharset,
}
end)
register('llpeg.utf8util', function(myrequire)
myrequire('strict')
local utf8util = {}
function utf8util.codepointAt(s, pos)
local c1 = string.byte(s, pos)
if c1 <= 0x7F then
return c1, 1
end
local c2 = string.byte(s, pos + 1)
if c1 <= 0xDF then
return ((c1 % 0x20 ) * 0x40) + (c2 % 0x40), 2
end
local c3 = string.byte(s, pos + 2)
if c1 <= 0xEF then
return (((c1 % 0x10) * 0x40) + (c2 % 0x40)) * 0x40 + (c3 % 0x40), 3
end
local c4 = string.byte(s, pos + 3)
if c1 <= 0xF7 then
return ((((c1 % 0x08) * 0x40) + (c2 % 0x40)) * 0x40 + (c3 % 0x40)) * 0x40 + (c4 % 0x40), 4
end
error( "bad utf8" )
end
-- same as utf8.offset in Lua 5.3 standard library
function utf8util.offset(s, n, i)
if n > 0 then error("unimplemented") end
while n < 0 do
i = i - 1
if i < 1 then return nil end
local c = string.byte(s, i)
if c < 0x80 or c > 0xBF then
n = n + 1
end
end
return i
end
return utf8util
end)
register('llpeg.list', function(myrequire)
local List = {}
List.__index = List
function List:new()
return setmetatable({ n = 0 }, self)
end
function List:__len()
return self.n
end
function List:push(val)
local n = self.n + 1
self[n] = val
self.n = n
end
function List:pop()
local n = self.n
assert(n > 0)
local old = self[n]
self[n] = nil
self.n = n - 1
return old
end
function List:insert(pos, val)
for i=self.n,pos,-1 do
self[i+1] = self[i]
end
self[pos] = val
self.n = self.n + 1
end
return List
end)
register('llpeg.cap', function(myrequire)
myrequire('strict')
local compat = myrequire('advent.compat')
local from = myrequire('llpeg.types').from
local
CapKind,
_ = from(myrequire('llpeg.types'), {
'CapKind',
})
local
printcaplist,
_ = from(myrequire('llpeg.print'), {
'printcaplist',
})
local List = myrequire('llpeg.list')
local MAXRECLEVEL = 200
local Capture = {}
Capture.__index = Capture
-- kind is CapKind of the capture
-- bytePos is the subject position (in bytes)
-- byteLen is the length of the capture (in bytes)
-- extra is extra info (group name, arg index, etc)
function Capture:new(kind, bytePos, byteLen, extra)
assert(getmetatable(kind) == CapKind)
return setmetatable({
kind = kind, bytePos = bytePos, byteLen = byteLen, extra = extra,
}, self)
end
function Capture:__tostring()
return string.format("Capture{kind=%s, pos=%d, len=%s, extra=%s}",
self.kind, self.bytePos, self.byteLen, self.extra)
end
function Capture:isopencap()
return self.byteLen == nil
end
-- true if c2 is (any number of levels) inside self
function Capture:inside(c2)
if self:isopencap() then
return not c2:isclosecap()
else
return c2.bytePos < (self.bytePos + self.byteLen)
end
end
function Capture:isclosecap()
return self.kind == CapKind.close
end
--[[
** Return the size of capture 'cap'. If it is an open capture, 'close'
** must be its corresponding close.
]]--
function Capture:size(close)
if self:isopencap() then
assert(close:isclosecap())
return close.bytePos - self.bytePos
else
return self.byteLen
end
end
function CapKind:newCapture(bytePos, byteLen, extra)
return Capture:new(self, bytePos, byteLen, extra)
end
local CapState = {}
CapState.__index = CapState
-- Capture cap: current capture
-- Capture ocap: (original) capture list
-- int ptop: index of last argument to 'match'
-- string s: original string
-- int valuecached: value stored in cache slot
-- int reclevel: recursion level
function CapState:new(captures, source, extraArgs)
return setmetatable({
captures = captures,
index = 1,
source = source,
valuecached = {},
reclevel = 0,
extraArgs = extraArgs,
}, self)
end
function CapState:cap() -- helper
return self.captures[self.index]
end
function CapState:advance() -- helper
local i = self.index
local cap = self.captures[i]
self.index = i + 1
return cap, i
end
function CapState:substr(start, len) -- helper
return string.sub(self.source, start, start + len - 1)
end
function CapState:skipclose(head)
if head:isopencap() then
assert(self.captures[self.index]:isclosecap())
self.index = self.index + 1
end
end
function CapState:closesize(head)
return head:size(self:cap())
end
--[[
** Go to the next capture at the same level
]]--
function CapState:nextcap()
local cap = self:cap()
if cap:isopencap() then -- must look for a close
local n = 0 -- number of opens waiting a close
while true do -- look for corresponding close
self.index = self.index + 1
cap = self:cap()
if cap:isopencap() then
n = n + 1
elseif cap:isclosecap() then
if n == 0 then break end
n = n - 1
end
end
self.index = self.index + 1 -- skip last close (or entire single capture)
else
self.index = self.index + 1
while cap:inside(self:cap()) do
self.index = self.index + 1 -- skip captures inside the current one
end
end
end
--[[
** Goes back in a list of captures looking for an open capture
** corresponding to a close
]]--
function CapState:findopen(i) -- captures[i] is the close that we want to match
assert(self.captures[i]:isclosecap())
local n = 0 -- number of closes waiting an open
while i > 1 do
i = i - 1
local cap = self.captures[i]
if cap:isclosecap() then
n = n + 1 -- one more open to skip
elseif cap:isopencap() then
if n == 0 then return cap,i end
n = n - 1
end
end
error("couldn't find open")
end
--[[
** Checks whether group 'grp' is visible to 'ref', that is, 'grp' is
** not nested inside a full capture that does not contain 'ref'. (We
** only need to care for full captures because the search at 'findback'
** skips open-end blocks; so, if 'grp' is nested in a non-full capture,
** 'ref' is also inside it.) To check this, we search backward for the
** inner full capture enclosing 'grp'. A full capture cannot contain
** non-full captures, so a close capture means we cannot be inside a
** full capture anymore.
]]--
function CapState:capvisible(igrp, ref)
local i = igrp
local grp = self.captures[igrp]
while i > 1 do
i = i - 1
local cap = self.captures[i]
if cap:isclosecap() then
return true -- can stop the search
elseif cap:inside(grp) then -- is 'grp' inside cap?
return cap:inside(ref) -- ok iff cap also contains ref
end
end
return true -- 'grp' is not inside any capture
end
--[[
** Try to find a named group capture with the name given;
** goes backward from 'i'.
]]--
function CapState:findback(name, i)
if i == nil then i = self.index end
local ref = self.captures[i]
while i > 1 do
i = i - 1
local cap = self.captures[i]
if cap:isclosecap() or not cap:inside(ref) then
if cap:isclosecap() then
cap,i = self:findopen(i)
end
if cap.kind == CapKind.group and self:capvisible(i, ref) then
if cap.extra == name then
return cap,i
end
end
end
end
error("back reference '"..name.."' not found")
end
function CapState:getcaptures()
local result = List:new()
while not self:cap():isclosecap() do
self:pushcapture(result)
end
return result
end
function CapState:pushcapture(result)
self.reclevel = self.reclevel + 1
if self.reclevel > MAXRECLEVEL then
error("subcapture nesting too deep")
end
local cap = self.captures[self.index]
assert(cap.kind.push ~= nil)
local res = cap.kind.push(self, cap, result)
self.reclevel = self.reclevel - 1
return res
end
-- helper functions for pushcapture
--[[
** Push on the Lua stack all values generated by nested captures inside
** the current capture. Returns number of values pushed. 'addextra'
** makes it push the entire match after all captured values. The
** entire match is pushed also if there are no other nested values,
** so the function never returns zero.
]]--
function CapState:pushnestedvalues(result, addextra)
local head = self:advance()
local n = 0 -- number of pushed subvalues
-- repeat for all nested patterns
while head:inside(self:cap()) do
n = n + self:pushcapture(result)
end
if addextra or n == 0 then -- need extra?
result:push(self:substr(head.bytePos, self:closesize(head)))
n = n + 1
end
self:skipclose(head)
return n
end
--[[
** Push only the first value generated by nested captures
]]--
function CapState:pushonenestedvalue(result)
local n = self:pushnestedvalues(result, false)
if n == 0 then
result:push(nil) -- ensure there's exactly one value
return 1
end
while n > 1 do
result:pop() -- pop extra values
n = n - 1
end
return n
end
-- visitor patterns for pushcapture
function CapKind.position.push(capstate, cap, result)
result:push(cap.bytePos)
capstate.index = capstate.index + 1
return 1
end
function CapKind.const.push(capstate, cap, result)
result:push(cap.extra)
capstate.index = capstate.index + 1
return 1
end
function CapKind.arg.push(capstate, cap, result)
local n = cap.extra
if n > capstate.extraArgs.n then
error(string.format("reference to absent extra argument #%d", n))
end
result:push(capstate.extraArgs[n])
capstate.index = capstate.index + 1
return 1
end
function CapKind.simple.push(capstate, cap, result)
local k = capstate:pushnestedvalues(result, true)
-- reorder so that the whole match is the first result, not the last
local last = result:pop()
result:insert(2 + #result - k, last)
return k
end
-- missing a bunch
--[[
** Table capture: creates a new table and populates it with nested
** captures.
]]--
function CapKind.table.push(capstate, cap, result) -- aka tablecap
local t = {}
result:push(t)
local head = capstate:advance()
local n = 0
while head:inside(capstate:cap()) do
cap = capstate:cap()
if cap.kind == CapKind.group and cap.extra ~= nil then -- named group?
capstate:pushonenestedvalue(result)
t[cap.extra] = result:pop() -- move it into table
else -- not a named group
local k = capstate:pushcapture(result)
for i=k,1,-1 do
t[n + i] = result:pop() -- move it into table (indexed)
end
n = n + k
end
end
capstate:skipclose(head)
return 1 -- number of values pushed (only the table)
end
--[[
** Table-query capture
]]--
function CapKind.query.push(capstate, cap, result) -- aka querycap
capstate:pushonenestedvalue(result)
local key = result:pop()
local tbl = cap.extra
assert(type(tbl) == "table")
local val = tbl[key]
if val ~= nil then
result:push(val)
return 1
else
return 0
end
end
--[[
** Fold capture
]]--
function CapKind.fold.push(capstate, cap, result) -- aka foldcap
local f = cap.extra
assert(type(f) == "function")
local head = capstate:advance()
if capstate:cap():isclosecap() then
-- no nested captures? (large subject)
error("no initial value for fold capture")
end
local args = List:new()
local n = capstate:pushcapture(args)
if n == 0 then
-- nested captures with no values?
error("no initial value for fold capture")
end
local accum = args[1] -- leave only one result for accumulator
while head:inside(capstate:cap()) do
args = List:new()
args:push( accum ) -- put accumulator first
n = capstate:pushcapture(args) -- get next capture's values
accum = f(compat.unpack(args))
end
capstate:skipclose(head)
-- only accumulator left in result
result:push(accum)
return 1
end
--[[
** Function capture
]]--
CapKind["function"].push = function(capstate, cap, result)
local f = cap.extra
assert(type(f) == "function")
local args = List:new()
local n = capstate:pushnestedvalues(args, false)
local r = compat.pack(f(compat.unpack(args)))
for i=1,r.n do
result:push(r[i])
end
return r.n
end
--[[
** Accumulator capture
]]--
function CapKind.acc.push(capstate, cap, result) -- aka accumulatorcap
if #result == 0 then
error("no previous value for accumulator capture")
end
local f = cap.extra
assert(type(f) == "function")
local prev = #result
local args = List:new()
args:push(result[prev])
local n = capstate:pushnestedvalues(args, false)
result[prev] = f(compat.unpack(args))
return 0 -- did not add any extra value
end
--[[
** Select capture
]]--
function CapKind.num.push(capstate, cap, result) -- aka numcap
local idx = cap.extra -- value to select
if idx == 0 then -- no values?
capstate:nextcap() -- skip entire capture
return 0 -- no value produced
else
local vals = List:new()
local n = capstate:pushnestedvalues(vals, false)
if n < idx then -- invalid index?
error("no capture '"..idx.."'")
else
result:push(vals[idx])
return 1
end
end
end
function CapState:runtimecap(closePos)
local close = self.captures[closePos]
local open,openPos = self:findopen(closePos) -- get open group capture
assert(open.kind == CapKind.group)
self.index = openPos -- set state to the open capture
local args = List:new()
args:push( self.source) -- original subject
args:push( close.bytePos ) -- current position
local n = self:pushnestedvalues(args, false) -- push nested captures
local func = open.extra
local funcRet = compat.pack(func(compat.unpack(args)))
local res = closePos - openPos -- number of captures to be removed
return res, funcRet
end
function CapKind.runtime.push(capstate, cap, result) -- aka runtimecap
result:push(cap.extra)
capstate.index = capstate.index + 1
return 1
end
local MAXSTRCAPS = 10
--[[
** Collect values from current capture into array 'cps'. Current
** capture must be Cstring (first call) or Csimple (recursive calls).
** (In first call, fills %0 with whole match for Cstring.)
** Returns number of elements in the array that were filled.
]]--
function CapState:getstrcaps(cps, n)
local k = n
n = n + 1
cps[k] = {
isstring = true, -- get string value
bytePos = self:cap().bytePos, -- starts here
}
local head = self:advance()
while head:inside(self:cap()) do
if n > MAXSTRCAPS then -- too many captures?
self:nextcap() -- skip extra captures (will not need them)
elseif self:cap().kind == CapKind.Simple then -- string?
n = self:getstrcaps(cps, n) -- put info into array
else
cps[n] = {
isstring = false, -- not a string
cap = self.index, -- keep original capture
}
self:nextcap()
n = n + 1
end
end
cps[k].endPos = head.bytePos + self:closesize(head)
self:skipclose(head)
return n
end
function CapState:addonestring(buffer, what)
local cap = self:cap()
if cap.kind == CapKind.string then
-- add capture directly to buffer
return stringcap(self, buffer)
elseif cap.kind == CapKind.subst then
-- add capture directly to buffer
return substcap(self, buffer)
elseif cap.kind == CapKind.acc then
error("invalid context for an accumulator capture")
end
local result = List:new()
local n = self:pushcapture(result)
if n == 0 then return 0 end -- no values to add
local val = result[1] -- take only one result (the first)
if type(val) == "number" then
val = tostring(val)
elseif type(val) ~= "string" then
error("invalid "..what.." value (a "..type(val)..")")
end
table.insert(buffer, val)
return 1
end
--[[
** String capture: add result to buffer 'b' (instead of pushing
** it into the stack)
]]--
function stringcap(capstate, buffer)
local fmt = capstate:cap().extra
local cps = {}
local n = capstate:getstrcaps(cps, 1) - 1 -- collect nested captures
local sawEscape = false
for _,c in compat.utf8codes(fmt) do
if sawEscape then
sawEscape = false
if c < 48 or c > 57 then -- not followed by a digit
table.insert(buffer, compat.utf8char(c))
else
local l = 1 + c - 48 -- capture index (1-based)
if l > n then
error("invalid capture index ("..(l-1)..")")
elseif cps[l].isstring then
table.insert(buffer, capstate:substr(cps[l].bytePos, cps[l].endPos - cps[l].bytePos))
else
-- go back to evaluate that nested capture
local curr = capstate.index
capstate.index = cps[l].cap
if capstate:addonestring(buffer, "capture") == 0 then
error("no values in capture index "..l)
end
capstate.index = curr
end
end
elseif c ~= 37 then -- not a % escape?
table.insert(buffer, compat.utf8char(c))
else
sawEscape = true
end
end
return 1
end
--[[
** Substitution capture: add result to buffer 'b'
]]--
function substcap(capstate, buffer)
local head = capstate:advance()
local curr = head.bytePos
while head:inside(capstate:cap()) do
local cap = capstate:cap()
local nextPos = cap.bytePos
local s = capstate:substr(curr, nextPos - curr)
table.insert(buffer, s) -- add text up to capture
if capstate:addonestring(buffer, "replacement") == 0 then
-- no capture value, keep original text in final result
curr = nextPos
else
-- continue after match
local lastCap = capstate.captures[capstate.index - 1]
curr = nextPos + cap:size(lastCap)
end
end
-- add last piece of text
local s = capstate:substr(curr, head.bytePos + capstate:closesize(head) - curr)
table.insert(buffer, s)
capstate:skipclose(head)
end
function CapKind.subst.push(capstate, cap, result) -- aka substcap
local buffer = {}
substcap(capstate, buffer)
result:push(table.concat(buffer))
return 1
end
function CapKind.string.push(capstate, cap, result) -- aka stringcap
local buffer = {}
stringcap(capstate, buffer)
result:push(table.concat(buffer))
return 1
end
function CapKind.group.push(capstate, cap, result)
if cap.extra == nil then -- anonymous group?
return capstate:pushnestedvalues(result, false) -- add all nested values
else -- named group: add no values
capstate:nextcap()
return 0
end
end
--[[
** Back-reference capture. Return number of values pushed.
]]--
function CapKind.backref.push(capstate, cap, result)
local curr = capstate.index
local _,i = capstate:findback(cap.extra)
capstate.index = i
local n = capstate:pushnestedvalues(result, false)
capstate.index = curr + 1
return n
end
return {
CapState = CapState,
Capture = Capture,
}
end)
register('llpeg.vm', function(myrequire)
myrequire('strict')
local compat = myrequire('advent.compat')
local utf8util = myrequire('llpeg.utf8util')
local from = myrequire('llpeg.types').from
local
CHARMAX,
CapKind,
Opcode,
enum,
_ = from(myrequire('llpeg.types'), {
'CHARMAX',
'CapKind',
'Opcode',
'enum',
})
local
CapState,
Capture,
__ = from(myrequire('llpeg.cap'), {
'CapState',
'Capture',
})
local
Instruction,
___ = from(myrequire('llpeg.code'), {
'Instruction',
})
local
printcaplist,
___ = from(myrequire('llpeg.print'), {
'printcaplist',
})
local LFAIL = {}
local InsidePred = enum{
OUTPRED = 0,
INPRED = 1,
}
local Stack = {}
Stack.__index = Stack
-- Stack prev: previous entry in the stack
-- int bytePos: saved position, or NULL for calls
-- Instruction pc: saved instruction
-- int caplevel
-- int labenv -- for labeled failure
-- bool predchoice -- for labeled failure
function Stack:new(prev, bytePos, pc, caplevel, labenv, predchoice)
return setmetatable({
prev = prev,
bytePos = bytePos, pc = pc, caplevel = caplevel,
labenv = labenv, predchoice = predchoice,
}, self)
end
function Stack:__tostring()
return string.format(
"Stack{ bytePos=%d, caplevel=%d, labenv=%s, predchoice=%s }",
self.bytePos, self.caplevel, self.labenv, self.predchoice
)
end
function Stack:print()
local s = self
while s ~= nil do
print("Stack", s)
s = s.prev
end
end
local MatchResult = {}
MatchResult.__index = MatchResult
function MatchResult:new()
return setmetatable({
labelf = nil, -- failure label
sfail = -1, -- farthest failure
}, self)
end
local State = {}
State.__index = State
function State:new(source, bytePos, ...)
local giveup = Instruction:new{Opcode.Giveup}
local insidepred = InsidePred.OUTPRED -- label environment is off inside predicates
local stack = Stack:new(nil, bytePos, giveup, 0, insidepred, nil)
local cp,cpLen
if bytePos <= #source then
cp, cpLen = utf8util.codepointAt(source, bytePos)
else
cp, cpLen = nil, nil
end
assert(bytePos ~= nil)
return setmetatable({
source = source, -- the source string
bytePos = bytePos, -- current position in the string, in bytes
codepoint = cp, -- the codepoint at 'bytePos' in 'source'
codepointLen = cpLen, -- the length of the codepoint at 'bytePos'
stack = stack, -- top of stack
captures = {}, -- list of captures
captop = 1, -- point to first empty slot in captures (1-based)
extraArgs = compat.pack(...),
-- labeled failures:
insidepred = insidepred,
labelf = nil, -- failure label
sfail = -1, -- farthest failure
}, self)
end
function State:advance()
return self:resetPosTo(self.bytePos + self.codepointLen)
end
function State:resetPosTo(newPos)
assert(newPos ~= nil)
self.bytePos = newPos
local source = self.source
if newPos <= #source then
local cp, cpLen = utf8util.codepointAt(source, newPos)
self.codepoint = cp
self.codepointLen = cpLen
return cp
else
self.codepoint = nil
self.codepointLen = nil
return nil
end
end
function State:backtrack(n)
local off = utf8util.offset(self.source, -n, self.bytePos)
if off == nil then return false end -- can't backtrack that far!
self:resetPosTo(off)
return true
end
function State:updatefarthest(label)
self.labelf = label
if self.bytePos > self.sfail then
self.sfail = self.bytePos
end
end
function State:pushcapture(cap)
self.captures[self.captop] = cap
self.captop = self.captop + 1
end
function State:fail()
-- pattern failed, try to backtrack
local lastStack
repeat
lastStack = self.stack
self.stack = lastStack.prev
until lastStack.bytePos ~= nil
self:resetPosTo(lastStack.bytePos)
self.captop = lastStack.caplevel
self.insidepred = lastStack.labenv -- labeled failure
return lastStack.pc:exec(self)
end
function State:giveup()
local r = nil
local lab = "fail"
local errpos = self.sfail
if self.labelf ~= nil and self.labelf ~= LFAIL then
lab = self.labelf
end
return r, lab, errpos
end
function State:getcaptures()
local results = {}
if self.captures[1].kind == CapKind.close then -- are there any captures?
return results -- no captures
end
return CapState:new(self.captures, self.source, self.extraArgs):getcaptures()
end
function Opcode.End:exec(state)
state:pushcapture(CapKind.close:newCapture(state.bytePos, 0))
-- trim table to proper length
while #state.captures > state.captop - 1 do
table.remove(state.captures)
end
-- printcaplist(state.captures, #state.captures) -- for debugging
local results = state:getcaptures()
if #results == 0 then -- no captured values?
return state.bytePos -- return only end position
else
return compat.unpack(results)
end
end
function Opcode.Giveup:exec(state)
return state:giveup()
end
function Opcode.Ret:exec(state)
local lastStack = state.stack
state.stack = lastStack.prev
return lastStack.pc:exec(state)
end
function Opcode.Any:exec(state)
if state.codepoint ~= nil then
state:advance()
return self.next:exec(state)
end
state:updatefarthest(LFAIL)
return state:fail()
end
function Opcode.TestAny:exec(state)
if state.codepoint ~= nil then
return self.next:exec(state)
else
return self.branch:exec(state)
end
end
function Opcode.UTFR:exec(state)
local cp = state.codepoint
if cp ~= nil and self.from <= cp and cp <= self.to then
state:advance()
return self.next:exec(state)
end
state:updatefarthest(LFAIL)
return state:fail()
end
function Opcode.Char:exec(state)
if state.codepoint == self.aux then
state:advance()
return self.next:exec(state)
end
state:updatefarthest(LFAIL)
return state:fail()
end
function Opcode.TestChar:exec(state)
if state.codepoint == self.aux then
return self.next:exec(state)
else
return self.branch:exec(state)
end
end
function Opcode.Set:exec(state)
local cp = state.codepoint
if cp ~= nil then
if cp <= CHARMAX then
if self.set[cp] then
state:advance()
return self.next:exec(state)
end
else
if self.rest then
state:advance()
return self.next:exec(state)
end
end
end
state:updatefarthest(LFAIL)
return state:fail()
end
function Opcode.TestSet:exec(state)
local cp = state.codepoint
if cp ~= nil then
if cp <= CHARMAX then
if self.set[cp] then
return self.next:exec(state)
end
elseif self.rest then
return self.next:exec(state)
end
end
return self.branch:exec(state)
end
function Opcode.Behind:exec(state)
local n = self.aux
-- XXX SLOW self.aux is in *characters* not *bytes*
if state:backtrack(n) then
return self.next:exec(state)
end
state:updatefarthest(LFAIL)
return state:fail()
end
function Opcode.Span:exec(state)
local cp = state.codepoint
while true do
local match = false
if cp ~= nil then
if cp <= CHARMAX then
if self.set[cp] then match = true end
else
if self.rest then match = true end
end
end
if not match then break end
cp = state:advance()
end
return self.next:exec(state)
end
function Opcode.Jmp:exec(state)
return self.branch:exec(state)
end
function Opcode.Choice:exec(state)
state.stack = Stack:new(
state.stack, state.bytePos, self.branch, state.captop, state.insidepred
)
return self.next:exec(state)
end
function Opcode.PredChoice:exec(state)
state.stack = Stack:new(
state.stack, state.bytePos, self.branch, state.captop, state.insidepred,
true -- predchoice
)
state.insidepred = InsidePred.INPRED
return self.next:exec(state)
end
function Opcode.Call:exec(state)
state.stack = Stack:new(
state.stack, nil, self.next
)
return self.branch:exec(state)
end
function Opcode.Commit:exec(state)
state.stack = state.stack.prev
return self.branch:exec(state)
end
function Opcode.PartialCommit:exec(state)
local stack = state.stack
stack.bytePos = state.bytePos
stack.caplevel = state.captop
return self.branch:exec(state)
end
function Opcode.BackCommit:exec(state)
local stack = state.stack
state.stack = stack.prev -- pop the stack
state:resetPosTo(stack.bytePos) -- but reset the position to that stored
state.insidepred = stack.labenv -- labeled failure
state.captop = stack.caplevel
return self.branch:exec(state)
end
function Opcode.Throw:exec(state)
if state.insidepred == InsidePred.OUTPRED then
state.labelf = self.key
-- pop entire stack
while state.stack.prev ~= nil do
state.stack = state.stack.prev
end
else
state.labelf = LFAIL
-- pop until you read a 'predchoice' state
while not state.stack.predchoice do
state.stack = state.stack.prev
end
end
state.sfail = state.bytePos
return state:fail()
end
function Opcode.ThrowRec:exec(state) -- with recovery
state.sfail = state.bytePos
if state.insidepred == InsidePred.OUTPRED then
state.labelf = self.key
state.stack = Stack:new(
state.stack, nil, self.next, state.captop
)
return self.branch:exec(state)
else
state.labelf = LFAIL
-- pop until you read a 'predchoice' state
while not state.stack.predchoice do
state.stack = state.stack.prev
end
return state:fail()
end
end
function Opcode.FailTwice:exec(state)
state.stack = state.stack.prev
state:updatefarthest(LFAIL)
return state:fail()
end
function Opcode.Fail:exec(state)
state:updatefarthest(LFAIL)
return state:fail()
end
function Opcode.CloseRunTime:exec(state)
-- close the group
state:pushcapture(self.cap:newCapture(state.bytePos, 0))
-- trim table to proper length
while #state.captures > state.captop - 1 do
table.remove(state.captures)
end
local cs = CapState:new(state.captures, state.source, state.extraArgs)
local n, funcRet = cs:runtimecap(state.captop - 1)
state.captop = state.captop - n -- remove nested captures
-- resdyncaptures: resolve returned values in `funcRet`
-- first argument false=fail, true=keep current pos, number=next position
local firstArg = funcRet[1]
if funcRet.n == 0 then
firstArg = false -- returning void means we'll fail
end
if not firstArg then -- if it is falsey, discard rest of returned vals & fail
state:updatefarthest(LFAIL)
return state:fail() -- tail call
elseif type(firstArg) == "boolean" then
-- keep current position, nothing needs to be done
else
local npos = tonumber(firstArg)
if npos < state.bytePos or npos > (1 + #(state.source)) then
error("invalid position returned by match-time capture")
end
state:resetPosTo(npos)
end
-- push the rest of the funcRet values as new captures
local n = funcRet.n - 1 -- number of new captures
if n == 0 then -- no new captures?
state.captop = state.captop - 1 -- remove open group
else
-- new captures, keep original open group
-- add new captures + close group to 'capture' list
-- adddyncaptures:
assert(state.captures[state.captop - 1].kind == CapKind.group)
assert(state.captures[state.captop - 1]:isopencap())
-- make group capture an anonymous group (this used to hold match-time f)
state.captures[state.captop - 1].extra = nil
for i=2,funcRet.n do -- add runtime captures
state:pushcapture(CapKind.runtime:newCapture(state.bytePos, 0, funcRet[i]))
end
-- close group
state:pushcapture(CapKind.close:newCapture(state.bytePos, 0))
end
return self.next:exec(state)
end
local MAXLOP = 20
function findopen(captures, i, currPos)
i = i - 1 -- check last captop
local cap = captures[i]
if (not cap:isopencap()) and cap.bytePos == currPos then
return nil -- current one cannot be a full capture
end
-- else, look for an 'open' capture
for j=1,MAXLOP do
if cap:isopencap() then -- open capture?
return cap,i -- that's the one to be closed
elseif cap.kind == CapKind.close then
return nil -- a full capture should not nest a non-full one
end
i = i - 1
if i<1 then break end
cap = captures[i]
end
return nil -- not found within allowed search limit
end
function Opcode.CloseCapture:exec(state)
-- if possible, turn capture into a full capture
assert(state.captop > 1)
local open,_ = findopen(state.captures, state.captop, state.bytePos)
if open ~= nil then -- if possible, turn capture into a full capture
open.byteLen = state.bytePos - open.bytePos
else
-- non-nil length to mark entry as closed
state:pushcapture(self.cap:newCapture(state.bytePos, 0))
end
return self.next:exec(state)
end
function Opcode.OpenCapture:exec(state)
state:pushcapture(self.cap:newCapture(
-- byteLen = nil marks entry as open
state.bytePos, nil, self.key
))
return self.next:exec(state)
end
function Opcode.FullCapture:exec(state)
-- XXX SLOW: self.aux is in *characters* not *bytes*
local nPos = utf8util.offset(state.source, -self.aux, state.bytePos)
state:pushcapture(self.cap:newCapture(
nPos, state.bytePos - nPos, self.key
))
return self.next:exec(state)
end
function match(s, init, code, ...)
local state = State:new(s, init, ...)
return code[1]:exec(state)
end
return {
match = match,
}
end)
register('llpeg', function(myrequire)
local VERSION = '0.0.1'
local MAXSTACK = 400 -- maximum backtracking
local MAXBEHIND = 255 -- maximum look-behind
local MAXRULES = 1000 -- maximum number of rules
local LPEG_COMPAT = true
myrequire('strict')
local compat = myrequire('advent.compat')
local from = myrequire('llpeg.types').from
local
CHARMAX,
CapKind,
TTag,
define,
define_tree_visitor,
metareg,
newcharset,
numsiblings,
_ = from(myrequire('llpeg.types'), {
'CHARMAX',
'CapKind',
'TTag',
'define',
'define_tree_visitor',
'metareg',
'newcharset',
'numsiblings',
})
local
compile,
cs_diff,
cs_union,
fixedlen,
hascaptures,
nofail,
nullable,
nullable_with_grammar,
tocharset,
__ = from(myrequire('llpeg.code'), {
'compile',
'cs_diff',
'cs_union',
'fixedlen',
'hascaptures',
'nofail',
'nullable',
'nullable_with_grammar',
'tocharset',
})
local
match,
___ = from(myrequire('llpeg.vm'), {
'match',
})
local
printpatt,
printrepl,
printtree,
____ = from(myrequire('llpeg.print'), {
'printpatt',
'printrepl',
'printtree',
})
function checkint(v)
if type(v) == 'string' then
v = tonumber(v)
end
if type(v) ~= "number" then
error("not a number")
end
return math.floor(v)
end
local is_pattern = define_type_visitor{
pattern = function() return true end,
default = function() return false end,
}
local ptype = define_type_visitor{
pattern = function() return "pattern" end,
default = function(v) return type(v) end,
}
function val2str(v)
if type(v) == 'number' then return tostring(v) end
if type(v) == 'string' then return v end
return string.format("(a %s)", ptype(v))
end
--[[ lpltree.c ]]--
function newtree(tag)
local t = {
tag = tag,
code = nil,
}
setmetatable(t, metareg)
return t
end
function newleaf(tag, n)
return setmetatable({
tag = tag,
code = nil,
n = n,
}, metareg)
end
function newroot1sib(tag, sib1)
return setmetatable({
tag = tag,
code = nil,
sib1 = sib1,
}, metareg)
end
function newroot2sib(tag, sib1, sib2)
return setmetatable({
tag = tag,
code = nil,
sib1 = sib1,
sib2 = sib2,
}, metareg)
end
--[[ Build a sequence of #s nodes from the array 's' with the tag 'tag' ]]--
function fillseq(tag, s)
if type(s) == 'number' then
local len = checkint(s)
s = setmetatable({}, {__len = function() return len end})
end
if #s == 0 then
return newleaf(tag, 0)
end
local i = #s
local result = newleaf(tag, s[i])
while i > 1 do
i = i - 1
result = newroot2sib(
TTag.Seq,
newleaf(tag, s[i]),
result
)
end
return result
end
--[[ Numbers as patterns:
0 == true (always match); n == TAny repeated 'n' times;
-n == not (TAny repeated 'n' times)
]]--
function numtree(n)
n = checkint(n)
if n == 0 then
return newleaf(TTag.True)
elseif n > 0 then
return fillseq(TTag.Any, n) -- sequence of 'n' anys
else
return newroot1sib(TTag.Not, fillseq(TTag.Any, -n))
end
end
-- Convert value v to a pattern
local getpatt = define_type_visitor{
["string"] = function(s)
if #s == 0 then
return newleaf(TTag.True) -- always match if string is empty
end
local cp = {}
for _,c in compat.utf8codes(s) do
table.insert(cp, c)
end
return fillseq(TTag.Char, cp)
end,
["number"] = function(n)
return numtree(n)
end,
["boolean"] = function(b)
if b then
return newleaf(TTag.True)
else
return newleaf(TTag.False)
end
end,
["function"] = function(f)
return setmetatable({
tag = TTag.RunTime,
code = nil,
key = f,
sib1 = newleaf(TTag.True),
}, metareg)
end,
["pattern"] = function(v)
return v
end,
["table"] = function(v)
return newgrammar(v)
end,
default = function(v)
error("Not a pattern")
end,
}
-- labeled failure begin
function newthrowleaf(label)
return setmetatable({
tag = TTag.Throw,
code = nil,
sib2 = nil, -- no recovery rule associated (yet)
key = label,
}, metareg)
end
-- labeled failure end
function lp_P(v)
return getpatt(v)
end
--[[
** sequence operator; optimizations:
** false x => false, x true => x, true x => x
** (cannot do x . false => false because x may have runtime captures)
]]--
function lp_seq(tree1, tree2)
tree1 = getpatt(tree1)
tree2 = getpatt(tree2)
if tree1.tag == TTag.False or tree2.tag == TTag.True then
-- false . x = false, x . true = x
return tree1
elseif tree1.tag == TTag.True then
-- true . x = x
return tree2
else
return newroot2sib(TTag.Seq, 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)
]]--
function lp_choice(t1, t2)
t1 = getpatt(t1)
t2 = getpatt(t2)
local t1c = tocharset(t1)
local t2c = tocharset(t2)
if t1c ~= nil and t2c ~= nil then
local t = cs_union(t1c, t2c)
return t
elseif nofail(t1) or t2.tag == TTag.False then
-- true / x => true, x / false => x
return t1
elseif t1.tag == TTag.False then
-- false / x => x
return t2
else
return newroot2sib(TTag.Choice, t1, t2)
end
end
--[[
p^n
]]--
function lp_star(p, n)
local tree1 = getpatt(p)
n = checkint(n)
if n >= 0 then -- seq tree1 (seq tree1 ... (seq tree1 (rep tree1)))
if nullable(tree1) then
error("loop body may accept empty string")
end
local tree = newroot1sib(TTag.Rep, tree1)
while n > 0 do
tree = newroot2sib(TTag.Seq, tree1, tree)
n = n - 1
end
return tree
else -- choice (seq tree1 ... choice tree1 true ...) true
n = -n
local tree = newroot2sib( -- at most 1
TTag.Choice,
tree1,
newleaf(TTag.True)
)
while n > 1 do
tree = newroot2sib( -- at most (n-1)
TTag.Seq,
tree1,
tree
)
tree = newroot2sib(TTag.Choice, tree, newleaf(TTag.True))
n = n - 1
end
return tree
end
end
--[[
** #p == &p
]]--
function lp_and(v)
return newroot1sib(TTag.And, getpatt(v))
end
--[[
** -p == !p
]]--
function lp_not(v)
return newroot1sib(TTag.Not, getpatt(v))
end
--[[
** [t1 - t2] == Seq (Not t2) t1
** If t1 and t2 are charsets, make their difference.
]]--
function lp_sub(t1, t2)
t1 = getpatt(t1)
t2 = getpatt(t2)
local t1c = tocharset(t1)
local t2c = tocharset(t2)
if t1c ~= nil and t2c ~= nil then
return cs_diff(t1c, t2c)
else
return newroot2sib(
TTag.Seq,
newroot1sib(TTag.Not, t2),
t1
)
end
end
--[[
A set with the given characters
]]--
function lp_set(s)
local t = newcharset()
local extra = nil
for _,c in compat.utf8codes(s) do
if c > CHARMAX then
-- non ascii, we can't use charset for these
local one = newleaf(TTag.Char, c)
if extra == nil then
extra = one
else
extra = newroot2sib(TTag.Choice, extra, one)
end
else
t.set[c] = true
end
end
if extra == nil then
return t
else
return newroot2sib(TTag.Choice, t, extra)
end
end
function lp_range(...)
local t = newcharset()
local extra = nil
for _,v in ipairs{...} do
if type(v) ~= "string" then
error("argument must be string")
else
local first, second
for _,c in compat.utf8codes(v) do
if first == nil then
first = c
elseif second == nil then
second = c
else
error("range must have two characters")
end
end
if first == nil or second == nil then
error("range must have two characters")
end
if first > second then
if LPEG_COMPAT then
-- ignore, just silently create an empty range
else
error("empty range")
end
elseif second <= CHARMAX then -- ascii range
for i = first, second do
t.set[i] = true
end
else
local r = lp_utfr(first, second)
if extra == nil then
extra = r
else
extra = newroot2sib(TTag.Choice, extra, one)
end
end
end
end
if extra == nil then
return t
else
return newroot2sib(TTag.Choice, t, extra)
end
end
function lp_utfr(from, to)
from = checkint(from)
to = checkint(to)
if from > to then
error("empty range")
end
if to > 0x10FFFF then
error("invalid code point")
end
if to <= CHARMAX then -- ascii range?
local t = newcharset() -- code it as a regular charset
for i = from, to do
t.set[i] = true
end
return t
end
-- multibyte utf-8 range
return setmetatable({
tag = TTag.UTFR,
code = nil,
from = from,
to = to,
}, metareg)
end
--[[
Look-behind predicate
]]--
function lp_behind(v)
local tree1 = getpatt(v)
local n = fixedlen(tree1)
if n < 0 then
error("pattern may not have fixed length")
end
if hascaptures(tree1) then
error("pattern has captures")
end
if n > MAXBEHIND then
error("pattern too long to look behind")
end
return setmetatable({
tag = TTag.Behind,
code = nil,
sib1 = tree1,
n = n,
}, metareg)
end
--[[ labeled failure begin ]]--
--[[
** Throws a label
]]--
local lp_throw = define_type_visitor{
[{"string","number"}] = newthrowleaf,
default = function() error("not a string") end,
}
--[[ labeled failure end ]]--
--[[
** Create a non-terminal
]]--
function lp_V(v)
if v == nil then
error("non-nil value expected")
end
return setmetatable({
tag = TTag.Call,
code = nil,
key = v,
}, metareg)
end
--[[
** Create a tree for a non-empty capture, with a body and
** optionally with an associated Lua value (at index 'labelidx' in the
** stack)
]]--
function capture_aux(capkind, patt, val)
local t = newroot1sib(TTag.Capture, getpatt(patt))
t.cap = capkind
t.key = val
return t
end
function newemptycap(capkind, val)
return capture_aux(capkind, newleaf(TTag.True), val)
end
--[[
** Captures with syntax p / v
** (function capture, query capture, string capture, or number capture)
]]--
local divcapture_helper = define_type_visitor{
["function"] = function(v, p)
return capture_aux(CapKind["function"], p, v)
end,
["table"] = function(v, p)
return capture_aux(CapKind.query, p, v)
end,
["string"] = function(v, p)
return capture_aux(CapKind.string, p, v)
end,
["number"] = function(v, p)
v = checkint(v)
if v < 0 or v > 65536 then
error("invalid number")
end
return capture_aux(CapKind.num, p, v)
end,
default = function(v)
error("unexpected "..ptype(v).." as 2nd operand to LPeg '/'") end,
}
function lp_divcapture(p, v)
return divcapture_helper(v, p) -- dispatch on v
end
function lp_acccapture(p, v)
return capture_aux(CapKind.acc, p, v)
end
-- the match for patt with the values from nested captures replacing their
-- matches
function lp_substcapture(patt)
return capture_aux(CapKind.subst, patt)
end
-- a table with all captures from patt
function lp_tablecapture(patt)
return capture_aux(CapKind.table, patt)
end
-- the values produced by patt, optionally tagged with key
function lp_groupcapture(patt, key)
-- key can be nil
return capture_aux(CapKind.group, patt, key)
end
-- folding capture (deprecated)
function lp_foldcapture(patt, func)
if type(func) ~= "function" then
error("Bad function argument")
end
return capture_aux(CapKind.fold, patt, func)
end
-- the match for patt plus all captures made by patt
function lp_simplecapture(patt)
return capture_aux(CapKind.simple, patt)
end
-- the current position (matches the empty string)
function lp_poscapture()
return newemptycap(CapKind.position)
end
-- the value of the nth extra argument to lpeg.match (matches the empty string)
function lp_argcapture(n)
n = checkint(n)
if n <= 0 or n > 65536 then error("invalid argument index") end
return newemptycap(CapKind.arg, n)
end
-- the value produced by the previous group capture named `key`
-- (matches the empty string)
function lp_backref(key)
return newemptycap(CapKind.backref, key)
end
-- Constant capture (matches the empty string)
function lp_constcapture(...)
local arg = compat.pack(...)
if arg.n == 0 then -- no values?
return newleaf(TTag.True) -- no capture
else
local i = arg.n
local tree = newemptycap(CapKind.const, arg[i])
while i > 1 do
i = i - 1
tree = newroot2sib(
TTag.Seq,
newemptycap(CapKind.const, arg[i]),
tree
)
end
if arg.n == 1 then
-- single constant capture
return tree
else
-- create a group capture with all values
return lp_groupcapture( tree )
end
end
end
-- the returns of function applied to the captures of patt; the application
-- is done at match time
function lp_matchtime(patt, func)
if type(func) ~= 'function' then
error('not a function')
end
return setmetatable({
tag = TTag.RunTime,
code = nil,
key = func,
sib1 = getpatt(patt),
}, metareg)
end
--[[======================================================]]--
--[[
** ======================================================
** Grammar - Tree generation
** ======================================================
]]--
--[[
** push on the stack the index and the pattern for the
** initial rule of grammar at index 'arg' in the stack;
** also add that index into position table.
]]--
function getfirstrule(tbl)
local first_name, first_rule
first_name = tbl[1]
-- is this the name of an initial rule?
if type(first_name) == 'number' or type(first_name) == 'string' then
first_rule = tbl[first_name] -- get associated rule
else
first_name,first_rule = 1,first_name
end
if not is_pattern(first_rule) then
if first_rule == nil then
error("grammar has no initial rule")
else
error(string.format("initial rule '%s' is not a pattern", first_name))
end
end
-- rule position (after TGrammar)
-- return map from name to position, and from position to name
return { [first_name] = 1 }, { first_name }
end
--[[
** traverse grammar at index 'arg', pushing all its keys and patterns
** into the stack. 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 (in 'totalsize') the total size
** for the new tree.
]]--
function collectrules(tbl)
-- find the first rule and put in position table
local postab, rpostab = getfirstrule(tbl)
-- collect and sort rule names (for repeatability)
local names = {}
for k,v in pairs(tbl) do
if k == 1 or postab[k] == 1 then -- initial rule?
-- skip the initial rules, it's already in the position table
else
table.insert(names, k)
end
end
table.sort(names, function(a,b)
return tostring(a) < tostring(b)
end)
-- fill out rule, name, and position maps
for _,k in ipairs(names) do
local v = tbl[k]
if not is_pattern(v) then
error("rule '" .. val2str(k) .. "' is not a pattern")
end
table.insert(rpostab, k)
postab[k] = #rpostab
end
return postab, rpostab
end
function buildgrammar(g, tbl, postab, rpostab)
local trees = {}
for i,name in ipairs(rpostab) do
local rule = setmetatable({
tag = TTag.Rule,
code = nil,
key = nil, -- will be fixed when rule is used
n = i, -- rule number
name = name,
sib1 = tbl[name], -- pattern
sib2 = nil,
}, metareg)
table.insert(trees, rule)
g.ruletab[name] = rule
end
-- link up siblings
for i = 1, #trees-1 do
trees[i].sib2 = trees[i+1]
end
trees[#trees].sib2 = newleaf(TTag.True) -- finish list of rules
g.sib1 = trees[1]
end
--[[
** Check whether a tree has potential infinite loops
]]--
function checkloops(grammar, tree)
local n = numsiblings[tree.tag]
if tree.tag == TTag.Rep and nullable_with_grammar(tree.sib1, grammar) then
return true
elseif tree.tag == TTag.Grammar then
return false -- sub-grammars already checked
elseif n == 1 then
return checkloops(grammar, tree.sib1) -- tail call
elseif n == 2 then
if checkloops(grammar, tree.sib1) then
return true
else
return checkloops(grammar, tree.sib2) -- tail call
end
elseif n == 0 then
return false
else
error("surprising number of siblings")
end
end
--[[
** Give appropriate error message for 'verifyrule'. If a rule appears
** twice in 'passed', there is path from it back to itself without
** advancing the subject.
]]--
function verifyerror(grammar, passed, npassed)
local i, j
for i = npassed,1,-1 do -- search for a repetition
for j = i-1,1,-1 do
if passed[i] == passed[j] then
error(string.format("rule '%s' may be left recursive", val2str(passed[i])))
end
end
end
error("too many left calls in grammar")
end
--[[
** Check whether a rule can be left recursive; raise an error in that
** case; otherwise return 1 iff pattern is nullable.
** The return value is used to check sequences, where the second pattern
** is only relevant if the first is nullable.
** Parameter 'nb' works as an accumulator, to allow tail calls in
** choices. ('nb' true makes function returns true.)
** Parameter 'passed' is a list of already visited rules, 'npassed'
** counts the elements in 'passed'.
** Assume ktable at the top of the stack.
]]--
local verifyrule
verifyrule = define_tree_visitor{
[{
TTag.Char, TTag.Set, TTag.Any, TTag.False, TTag.UTFR,
TTag.Throw, -- labeled failure
}] = function(tree, g, passed, n, nb)
return nb -- cannot pass from here
end,
[{
TTag.True, TTag.Behind, -- look-behind cannot have calls
}] = function(tree, g, passed, n, nb)
return true
end,
[{ TTag.Not, TTag.And, TTag.Rep, }] = function(tree, g, passed, n, nb)
return verifyrule(tree.sib1, g, passed, n, true) -- tail call
end,
[{ TTag.Capture, TTag.RunTime, TTag.XInfo, }] = function(tree, g, passed, n, nb)
return verifyrule(tree.sib1, g, passed, n, nb) -- tail call
end,
[ TTag.Call ] = function(tree, g, passed, n, nb)
local rule = g.ruletab[tree.key] -- look up rule
return verifyrule(rule, g, passed, n, nb) -- tail call
end,
[ TTag.Seq ] = function(tree, g, passed, n, nb)
-- only check 2nd child if first is nb
if not verifyrule(tree.sib1, g, passed, n, false) then
return nb
else
-- note that we don't propagate new npassed from 1st child
return verifyrule(tree.sib2, g, passed, n, nb) -- tail call
end
end,
[ TTag.Choice ] = function(tree, g, passed, n, nb)
-- must check both children
nb = verifyrule(tree.sib1, g, passed, n, nb)
-- note that we don't propagate new npassed from 1st child
return verifyrule(tree.sib2, g, passed, n, nb) -- tail call
end,
[ TTag.Rule ] = function(tree, g, passed, n, nb)
if n >= MAXRULES then -- too many steps?
return verifyerror(g, passed, n) -- error
else
passed[n+1] = tree.key -- add rule to path
return verifyrule(tree.sib1, g, passed, n + 1, nb) -- tail call
end
end,
[ TTag.Grammar ] = function(tree, g, passed, n, nb)
return nullable(tree) -- sub-grammar cannot be left recursive
end,
}
function verifygrammar(grammar)
local passed = {}
-- check left-recursive rules
local rule = grammar.sib1
while rule.tag == TTag.Rule do
if rule.key ~= nil then -- skip unused rules
verifyrule(rule.sib1, grammar, passed, 0, false)
end
rule = rule.sib2
end
if rule.tag ~= TTag.True then
error("assertion failure")
end
-- check infinite loops inside rules
rule = grammar.sib1
while rule.tag == TTag.Rule do
if rule.key ~= nil then -- skip unused rules
if checkloops(grammar, rule.sib1) then
error("empty loop in rule '" .. val2str(rule.name) .. "'")
end
end
rule = rule.sib2
end
if rule.tag ~= TTag.True then
error("assertion failure")
end
end
--[[
** 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.
]]--
function fixonecall(g, t, postab)
local name = t.key
local rule = g.ruletab[name]
if t.tag == TTag.Call then
if rule == nil then
error(string.format("rule '%s' undefined in given grammar", val2str(name)))
end
-- unlike our upstream, we don't clone patterns when we build a grammar
-- so we can't mutate this tree w/o possibly breaking any other grammars
-- which might hold an alias of this call. So we don't distinguish
-- Call and OpenCall and we don't mutate the tag here and
-- don't link it up. However, we can mutate the Rule
-- as those are not shared
rule.key = name -- mark this as used
elseif rule ~= nil then -- TTag.Throw
-- As before, we can't mutate the tree
rule.key = name -- mark this as used
end
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))
]]--
function correctassociativity (tree)
local tag = tree.tag
if tag ~= TTag.Choice and tag ~= TTag.Seq then
error("impossible")
end
local t1 = tree.sib1
while t1.tag == tree.tag do
local t11, t12 = t1.sib1, t1.sib2
local t2 = tree.sib2
-- don't mutate t1 in place as others may be keeping copies of it;
-- mutating 'tree' in place is okay as we're not changing its semantics
tree.sib1 = t11
tree.sib2 = newroot2sib(tag, t12, t2)
t1 = tree.sib1
end
return tree
end
--[[
** Make final adjustments in a tree. Fix open calls in tree 't',
** 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). Assume that tree's
** ktable is at the top of the stack (for error messages).
]]--
local finalfix_helper = define_tree_visitor{
[TTag.Grammar] = function(t)
return t -- subgrammars were already fixed
end,
[TTag.Call] = function(t, g, postab)
if g == nil then
error("rule '" .. val2str(t.key) .. "' used outside a grammar")
else
return fixonecall(g, t, postab)
end
end,
[TTag.Throw] = function(t, g, postab)
if g ~= nil then
return fixonecall(g, t, postab)
end
end,
[{TTag.Seq, TTag.Choice}] = function(t, g, postab)
return correctassociativity(t)
end,
default = function(t) return t end,
}
function finalfix(g, t, postab)
finalfix_helper(t, g, postab)
if t.tag == TTag.Grammar then return end
local n = numsiblings[t.tag]
if n == 1 then
return finalfix(g, t.sib1, postab) -- tail call
elseif n == 2 then
finalfix(g, t.sib1, postab)
return finalfix(g, t.sib2, postab) -- tail call
elseif n == 0 then
return
else
error("strange number of siblings")
end
end
--[[
** Give a name for the initial rule if it is not referenced
]]--
function initialrulename(grammar)
if grammar.sib1.key == nil then -- initial rule is not referenced?
grammar.sib1.key = grammar.sib1.name
end
end
function newgrammar(tbl)
local postab, rpostab = collectrules(tbl)
local g = setmetatable({
tag = TTag.Grammar,
code = nil,
sib1 = nil, -- will fill this in
n = #rpostab, -- number of rules
ruletab = {}, -- map rule names to rules
}, metareg)
buildgrammar(g, tbl, postab, rpostab)
finalfix(g, g.sib1, postab)
initialrulename(g)
verifygrammar(g)
return g
end
--[[ ====================================================== ]]--
function prepcompile(p)
finalfix(nil, p, {}) -- correct associativity
return compile(p)
end
function lp_printtree(patt, c)
local tree = getpatt(patt)
if c then
finalfix(nil, tree, {}) -- correct associativity
end
print("[]") -- for compatibility, this is a fake 'ktable'
io.write(table.concat(printtree(tree, 0, {})))
end
function lp_printcode(patt)
local p = getpatt(patt)
if p.code == nil then
prepcompile(p)
end
print("[]") -- for compatibility, this is a fake 'ktable'
io.write(table.concat(printpatt(p.code, {})))
end
--[[
** Get the initial position for the match, interpreting negative
** values from the end of the subject. Result is 1-based.
]]--
function initposition(ii, len)
if ii > 0 then -- positive index?
if ii <= len then -- inside the string?
return ii -- return it (no correction to 0-base)
else
return len + 1 -- crop at the end
end
else -- negative index
if (-ii) <= len then -- inside the string?
return len + 1 - (-ii) -- return position from the end
else
return 1
end
end
end
-- Main match function
function lp_match(pattern, subject, init, ...)
local p = getpatt(pattern)
if p.code == nil then prepcompile(p) end
local code = p.code
if type(subject) ~= 'string' then error("subject is not a string") end
local i
if init == nil then
i = 1
else
i = initposition(checkint(init), #subject)
end
return match(subject, i, code, ...)
end
--[[
** ======================================================
** Library creation and functions not related to matching
** ======================================================
]]--
function lp_setmax(lim)
lim = 0 + lim -- convert to integer
if lim <= 0 then
error("out of range")
end
MAXSTACK = lim
end
local lp_type = define_type_visitor{
pattern = function() return "pattern" end,
default = function() return nil end,
}
function lp_gc(p)
p._code = nil
end
function createcat(charspec)
local t = newcharset()
for i=0,CHARMAX do -- XXX not unicode safe
local s = compat.utf8char(i)
if s:find(charspec) ~= nil then
t.set[i] = true
end
end
return t
end
function lp_locale(tbl)
if tbl == nil then
tbl = {}
end
tbl.alnum = createcat("%w")
tbl.alpha = createcat("%a")
tbl.cntrl = createcat("%c")
tbl.digit = createcat("%d")
tbl.graph = createcat("[%p%w]") -- printable except space
tbl.lower = createcat("%l")
tbl.print = createcat("%C") -- printable = "not a control character"?
tbl.punct = createcat("%p") -- "printable but not space or alnum
tbl.space = createcat("%s")
tbl.upper = createcat("%u")
tbl.xdigit = createcat("%x")
return tbl
end
--[[ lpltree.c ]]--
metareg.__mul = lp_seq
metareg.__add = lp_choice
metareg.__pow = lp_star
metareg.__gc = lp_gc
metareg.__len = lp_and
metareg.__div = lp_divcapture
metareg.__mod = lp_acccapture
metareg.__unm = lp_not
metareg.__sub = lp_sub
metareg.__tostring = printrepl
local pattreg = {
ptree = lp_printtree,
pcode = lp_printcode,
match = lp_match,
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,
utfR = lp_utfr,
locale = lp_locale,
version = "LLPegLabel " .. VERSION,
setmaxstack = lp_setmax,
type = lp_type,
T = lp_throw, -- labeled failure throw
}
metareg.__index = pattreg
return pattreg
end)
local modules = {}
modules['bit32'] = require('bit32')
modules['string'] = require('string')
modules['strict'] = {}
modules['table'] = require('table')
local function myrequire(name)
if modules[name] == nil then
modules[name] = true
modules[name] = (builders[name])(myrequire)
end
return modules[name]
end
return myrequire('llpeg')
end)()