-- Module:PythonScript/Runtime/Regexp
-- 三路由混合式正則表達式引擎 (Three-Route Hybrid Regex Engine)
-- Route 1 (Fast-Path): 原生 Lua Pattern C 引擎單次直通 (含 (?#...), (?:...), \1~\9, 八進位跳脫)
-- Route 2 (CISC Slow-Path): 多階段動態拼接與鎖定匹配 (含 (?P=name), \1+, (?>...) 原子群組, \b/\B)
-- Route 3 (Micro-VM): 多分支調度 (|) 與前瞻/後顧斷言 ((?=...), (?!...), (?<=...), (?<!...)) + Bailout 安全閥
local Regexp = {}
local PyClass = require("Module:PythonScript/Class")
local Runtime = require("Module:PythonScript/Runtime")
local RUtils = require("Module:PythonScript/Runtime/Utils")
local ulen = (mw and mw.ustring and mw.ustring.len) or string.len
local usub = (mw and mw.ustring and mw.ustring.sub) or string.sub
local ufind = (mw and mw.ustring and mw.ustring.find) or string.find
local ulower = (mw and mw.ustring and mw.ustring.lower) or string.lower
local uchar = (mw and mw.ustring and mw.ustring.char) or string.char
local ubyte = (mw and mw.ustring and mw.ustring.codepoint) or string.byte
-- ==========================================
-- 1. 旗標常數與專用例外定義
-- ==========================================
local FLAG_NOFLAG = 0
local FLAG_IGNORECASE = 2
local FLAG_LOCALE = 4
local FLAG_MULTILINE = 8
local FLAG_DOTALL = 16
local FLAG_UNICODE = 32
local FLAG_VERBOSE = 64
local FLAG_ASCII = 256
local MAX_BRANCHES = 16
local MAX_ALT_DEPTH = 2
local MAX_REPEAT_COUNT = 200
local MAX_LOOKAROUNDS = 2
local ReErrorClass = nil
local MatchClass = nil
local PatternClass = nil
local compile_cache = {}
local function get_re_error_class()
if not ReErrorClass then
ReErrorClass = PyClass.make_class("error", { Runtime.builtins.Exception }, {})
ReErrorClass.__dict["__module__"] = "re"
end
return ReErrorClass
end
local function raise_re_error(msg)
Runtime.raise(get_re_error_class(), msg)
end
local function raise_bailout(msg)
Runtime.raise("NotImplementedError", msg)
end
local function is_none(v)
return v == nil or v == Runtime.builtins.None or (type(v) == "table" and v.__class and v.__class.__name == "NoneType")
end
local function has_flag(flags, f)
return math.floor((flags or 0) / f) % 2 == 1
end
local function unpack_pattern_input(pat)
if type(pat) == "table" then
if pat.__type == "bytes" or pat.__type == "bytearray" or pat.__type == "memoryview" then
return pat._data or "", true
elseif pat.__type == "instance" and pat.__builtin_value ~= nil then
return unpack_pattern_input(pat.__builtin_value)
end
end
if type(pat) == "string" then return pat, false end
Runtime.raise("TypeError", "first argument must be string or compiled pattern")
end
local function unpack_target_string(s, expect_bytes)
local is_b = false
local raw = s
if type(s) == "table" then
if s.__type == "bytes" or s.__type == "bytearray" or s.__type == "memoryview" then
raw = s._data or ""
is_b = true
elseif s.__type == "instance" and s.__builtin_value ~= nil then
return unpack_target_string(s.__builtin_value, expect_bytes)
else
Runtime.raise("TypeError", "expected string or bytes-like object")
end
elseif type(s) ~= "string" then
Runtime.raise("TypeError", "expected string or bytes-like object")
end
if expect_bytes ~= nil and expect_bytes ~= is_b then
Runtime.raise("TypeError", "cannot use a " .. (expect_bytes and "bytes" or "string") .. " pattern on a " .. (is_b and "bytes" or "string") .. " object")
end
return raw, is_b
end
local function wrap_output(str, is_bytes)
if str == nil then return Runtime.builtins.None end
if is_bytes then return { __type = "bytes", _data = str } end
return str
end
local function lua_escape_char(c)
if c == "\0" then return "%z" end
if c:find("^[%^%$%(%)%%%.%[%]%*%+%-%?]$") then
return "%" .. c
end
return c
end
local function lua_escape_str(s)
local out = {}
for i = 1, #s do
local c = s:sub(i, i)
table.insert(out, lua_escape_char(c))
end
return table.concat(out)
end
local function is_word_char(ch)
if not ch or ch == "" then return false end
return ufind(ch, "^[%w_]$") ~= nil
end
-- ==========================================
-- 2. 階段一：預處理器（剝除 (?#...) 註解、解析行內旗標與 VERBOSE）
-- ==========================================
local INLINE_FLAG_MAP = {
i = FLAG_IGNORECASE, L = FLAG_LOCALE, m = FLAG_MULTILINE,
s = FLAG_DOTALL, u = FLAG_UNICODE, x = FLAG_VERBOSE, a = FLAG_ASCII
}
local function preprocess_pattern(raw_pat, init_flags)
local flags = init_flags or 0
-- 先掃描頂層或開頭的 (?aiLmsux) 旗標以確認是否啟用 VERBOSE
local n = #raw_pat
local i = 1
local in_class = false
local pass1 = {}
while i <= n do
local c = raw_pat:sub(i, i)
if c == "\\" then
if i + 1 > n then raise_re_error("bad escape (end of pattern)") end
table.insert(pass1, raw_pat:sub(i, i + 1))
i = i + 2
elseif in_class then
if c == "]" then in_class = false end
table.insert(pass1, c)
i = i + 1
else
if c == "[" then
in_class = true
table.insert(pass1, "[")
i = i + 1
if i <= n and raw_pat:sub(i, i) == "^" then
table.insert(pass1, "^")
i = i + 1
end
if i <= n and raw_pat:sub(i, i) == "]" then
table.insert(pass1, "]")
i = i + 1
end
elseif c == "(" and raw_pat:sub(i + 1, i + 1) == "?" then
local sub2 = raw_pat:sub(i + 2, i + 2)
if sub2 == "#" then
-- (?#...) 註解：直接尋找未跳脫的 ')' 並剝除
local j = i + 3
while j <= n do
local cj = raw_pat:sub(j, j)
if cj == "\\" then j = j + 2
elseif cj == ")" then break
else j = j + 1 end
end
if j > n then raise_re_error("missing ), unterminated comment") end
i = j + 1
else
local f_str = raw_pat:sub(i + 2):match("^([aiLmsux]+)%)" )
if f_str then
for k = 1, #f_str do
local f_bit = INLINE_FLAG_MAP[f_str:sub(k, k)]
if f_bit and not has_flag(flags, f_bit) then flags = flags + f_bit end
end
i = i + 2 + #f_str + 1
else
table.insert(pass1, c)
i = i + 1
end
end
else
table.insert(pass1, c)
i = i + 1
end
end
end
if in_class then raise_re_error("unterminated character set") end
local cleaned = table.concat(pass1)
-- 若啟用 VERBOSE (re.X)，剝除非跳脫空白與 # 行尾註解
if has_flag(flags, FLAG_VERBOSE) then
local out = {}
local len = #cleaned
local idx = 1
local in_cls = false
while idx <= len do
local ch = cleaned:sub(idx, idx)
if ch == "\\" then
table.insert(out, cleaned:sub(idx, idx + 1))
idx = idx + 2
elseif in_cls then
if ch == "]" then in_cls = false end
table.insert(out, ch)
idx = idx + 1
else
if ch == "[" then
in_cls = true
table.insert(out, "[")
idx = idx + 1
if idx <= len and cleaned:sub(idx, idx) == "^" then
table.insert(out, "^"); idx = idx + 1
end
if idx <= len and cleaned:sub(idx, idx) == "]" then
table.insert(out, "]"); idx = idx + 1
end
elseif ch == "#" then
while idx <= len and cleaned:sub(idx, idx) ~= "\n" do idx = idx + 1 end
idx = idx + 1
elseif ch:match("^%s$") then
idx = idx + 1
else
table.insert(out, ch)
idx = idx + 1
end
end
end
cleaned = table.concat(out)
end
return cleaned, flags
end
-- ==========================================
-- 3. 階段二：Regex AST 解析器與靜態分析器
-- ==========================================
local function parse_regex_ast(pat, flags)
local n = #pat
local pos = 1
local total_groups = 0
local group_index = {} -- name -> group_id
local closed_groups = {} -- group_id -> true
local max_alt_depth = 0
local lookaround_count = 0
local is_ignorecase = has_flag(flags, FLAG_IGNORECASE)
local is_dotall = has_flag(flags, FLAG_DOTALL)
local is_multiline = has_flag(flags, FLAG_MULTILINE)
local function parse_quantifier()
if pos > n then return 1, 1, true, false end
local c = pat:sub(pos, pos)
local min_rep, max_rep = 1, 1
local has_q = false
if c == "*" then
min_rep, max_rep, has_q = 0, math.huge, true
pos = pos + 1
elseif c == "+" then
min_rep, max_rep, has_q = 1, math.huge, true
pos = pos + 1
elseif c == "?" then
min_rep, max_rep, has_q = 0, 1, true
pos = pos + 1
elseif c == "{" then
local m_str, comma, n_str, end_pos = pat:sub(pos):match("^{(%d*)(,?)(%d*)}()")
if m_str and (m_str ~= "" or n_str ~= "") then
pos = pos + end_pos - 1
has_q = true
min_rep = (m_str ~= "") and tonumber(m_str) or 0
if comma == "" then
max_rep = min_rep
else
max_rep = (n_str ~= "") and tonumber(n_str) or math.huge
end
if max_rep < min_rep then
raise_re_error("min repeat greater than max repeat")
end
if min_rep > MAX_REPEAT_COUNT or (max_rep ~= math.huge and max_rep > MAX_REPEAT_COUNT) then
raise_bailout("Quantifier repeat count exceeds sandbox safety limit (" .. MAX_REPEAT_COUNT .. ")")
end
end
end
if not has_q then return 1, 1, true, false end
local greedy = true
if pos <= n and pat:sub(pos, pos) == "?" then
greedy = false
pos = pos + 1
elseif pos <= n and (pat:sub(pos, pos) == "+" or pat:sub(pos, pos) == "*") then
raise_re_error("multiple repeat")
end
return min_rep, max_rep, greedy, true
end
-- 解析 [...] 字元類別：裡面的所有數值跳脫 (\0, \7, \141 等) 一律視為八進位字元
local function parse_char_class()
pos = pos + 1 -- 跳過 '['
local out = { "[" }
if pos <= n and pat:sub(pos, pos) == "^" then
table.insert(out, "^")
pos = pos + 1
end
local first_in_class = true
while pos <= n do
local c = pat:sub(pos, pos)
if c == "]" and not first_in_class then
pos = pos + 1
table.insert(out, "]")
local raw_cls = table.concat(out)
if is_ignorecase then
-- 僅將非 % 跳脫的英文字母轉小寫
raw_cls = raw_cls:gsub("(%%?)(%a)", function(esc, ch)
if esc == "%" then return "%" .. ch end
return ch:lower()
end)
end
return { type = "Atom", lua_item = raw_cls }
end
first_in_class = false
if c == "\\" then
pos = pos + 1
if pos > n then raise_re_error("bad escape (end of pattern)") end
local ec = pat:sub(pos, pos)
if ec:match("^[0-7]$") then
-- 字元類別內的數值跳脫一律視為八進位字元 (最多 3 位)
local oct_s = pat:sub(pos):match("^([0-7][0-7]?[0-7]?)")
pos = pos + #oct_s
local val = tonumber(oct_s, 8) % 256
if val == 0 then table.insert(out, "%z")
else
local ch = uchar(val)
if ch == "]" or ch == "-" or ch == "^" or ch == "%" then
table.insert(out, "%" .. ch)
else
table.insert(out, ch)
end
end
elseif ec == "8" or ec == "9" then
raise_re_error("invalid octal escape \\" .. ec .. " inside character class")
elseif ec == "x" then
local hex_s = pat:sub(pos + 1, pos + 2)
if not hex_s:match("^%x%x$") then raise_re_error("incomplete \\x escape") end
pos = pos + 3
local val = tonumber(hex_s, 16)
if val == 0 then table.insert(out, "%z")
else
local ch = uchar(val)
if ch == "]" or ch == "-" or ch == "^" or ch == "%" then table.insert(out, "%" .. ch)
else table.insert(out, ch) end
end
elseif ec == "d" then table.insert(out, "%d"); pos = pos + 1
elseif ec == "D" then table.insert(out, "%D"); pos = pos + 1
elseif ec == "s" then table.insert(out, "%s"); pos = pos + 1
elseif ec == "S" then table.insert(out, "%S"); pos = pos + 1
elseif ec == "w" then table.insert(out, "%w_"); pos = pos + 1
elseif ec == "W" then table.insert(out, "%W"); pos = pos + 1
elseif ec == "n" then table.insert(out, "\n"); pos = pos + 1
elseif ec == "r" then table.insert(out, "\r"); pos = pos + 1
elseif ec == "t" then table.insert(out, "\t"); pos = pos + 1
elseif ec == "b" then table.insert(out, "\8"); pos = pos + 1
elseif ec == "f" then table.insert(out, "\12"); pos = pos + 1
elseif ec == "v" then table.insert(out, "\11"); pos = pos + 1
elseif ec == "a" then table.insert(out, "\7"); pos = pos + 1
else
if ec == "]" or ec == "-" or ec == "^" or ec == "%" then
table.insert(out, "%" .. ec)
else
table.insert(out, ec)
end
pos = pos + 1
end
else
if c == "%" then
table.insert(out, "%%")
elseif c == "-" and pat:sub(pos + 1, pos + 1) == "]" then
table.insert(out, "%-")
else
table.insert(out, c)
end
pos = pos + 1
end
end
raise_re_error("unterminated character set")
end
local parse_alt
local function parse_seq(in_lookaround, alt_depth)
local items = {}
while pos <= n do
local c = pat:sub(pos, pos)
if c == ")" or c == "|" then break end
local node = nil
local allow_quant = true
if c == "^" then
pos = pos + 1
node = { type = "Anchor", kind = is_multiline and "line_start" or "str_start" }
allow_quant = false
elseif c == "$" then
pos = pos + 1
node = { type = "Anchor", kind = is_multiline and "line_end" or "str_end" }
allow_quant = false
elseif c == "." then
pos = pos + 1
node = { type = "Atom", lua_item = is_dotall and "." or "[^\n]" }
elseif c == "[" then
node = parse_char_class()
elseif c == "(" then
pos = pos + 1
if pos > n then raise_re_error("missing ), unterminated subpattern") end
if pat:sub(pos, pos) == "?" then
pos = pos + 1
if pos > n then raise_re_error("unexpected end of pattern") end
local nc = pat:sub(pos, pos)
if nc == ":" then
pos = pos + 1
local body = parse_alt(in_lookaround, alt_depth)
if pos > n or pat:sub(pos, pos) ~= ")" then raise_re_error("missing ), unterminated subpattern") end
pos = pos + 1
node = { type = "Group", kind = "non_capture", body = body }
elseif nc == ">" then
pos = pos + 1
local body = parse_alt(in_lookaround, alt_depth)
if pos > n or pat:sub(pos, pos) ~= ")" then raise_re_error("missing ), unterminated atomic group") end
pos = pos + 1
node = { type = "Group", kind = "atomic", body = body }
elseif nc == "=" or nc == "!" then
if in_lookaround then
raise_bailout("Nested lookaround assertions are not supported in sandboxed hybrid regex engine")
end
lookaround_count = lookaround_count + 1
if lookaround_count > MAX_LOOKAROUNDS then
raise_bailout("Too many lookaround assertions in a single pattern")
end
pos = pos + 1
local body = parse_alt(true, alt_depth)
if pos > n or pat:sub(pos, pos) ~= ")" then raise_re_error("missing ), unterminated lookahead") end
pos = pos + 1
node = { type = "Lookaround", kind = (nc == "=") and "lookahead_pos" or "lookahead_neg", body = body }
allow_quant = false
elseif nc == "<" then
local nc2 = pat:sub(pos + 1, pos + 1)
if nc2 == "=" or nc2 == "!" then
if in_lookaround then
raise_bailout("Nested lookaround assertions are not supported in sandboxed hybrid regex engine")
end
lookaround_count = lookaround_count + 1
if lookaround_count > MAX_LOOKAROUNDS then
raise_bailout("Too many lookaround assertions in a single pattern")
end
pos = pos + 2
local body = parse_alt(true, alt_depth)
if pos > n or pat:sub(pos, pos) ~= ")" then raise_re_error("missing ), unterminated lookbehind") end
pos = pos + 1
node = { type = "Lookaround", kind = (nc2 == "=") and "lookbehind_pos" or "lookbehind_neg", body = body }
allow_quant = false
else
-- Python 3 亦支援 (?<name>...) 語法
local gname, next_p = pat:sub(pos + 1):match("^([%a_][%w_]*)>()")
if not gname then raise_re_error("unknown extension ?<") end
pos = pos + next_p
if group_index[gname] then raise_re_error("redefinition of group name '" .. gname .. "'") end
total_groups = total_groups + 1
local gid = total_groups
group_index[gname] = gid
local body = parse_alt(in_lookaround, alt_depth)
if pos > n or pat:sub(pos, pos) ~= ")" then raise_re_error("missing ), unterminated subpattern") end
pos = pos + 1
closed_groups[gid] = true
node = { type = "Group", kind = "capture", group_id = gid, name = gname, body = body }
end
elseif nc == "P" then
local p_mode = pat:sub(pos + 1, pos + 1)
if p_mode == "<" then
local gname, next_p = pat:sub(pos + 2):match("^([%a_][%w_]*)>()")
if not gname then raise_re_error("missing >, unterminated name") end
pos = pos + 1 + next_p
if group_index[gname] then raise_re_error("redefinition of group name '" .. gname .. "'") end
total_groups = total_groups + 1
local gid = total_groups
group_index[gname] = gid
local body = parse_alt(in_lookaround, alt_depth)
if pos > n or pat:sub(pos, pos) ~= ")" then raise_re_error("missing ), unterminated subpattern") end
pos = pos + 1
closed_groups[gid] = true
node = { type = "Group", kind = "capture", group_id = gid, name = gname, body = body }
elseif p_mode == "=" then
local gname, next_p = pat:sub(pos + 2):match("^([%a_][%w_]*)%)()")
if not gname then raise_re_error("missing ), unterminated name in (?P=name)") end
pos = pos + 1 + next_p
local target_gid = group_index[gname]
if not target_gid then
raise_re_error("unknown group name '" .. gname .. "'")
end
if not closed_groups[target_gid] then
raise_re_error("cannot refer to an open group")
end
node = { type = "Backref", group_id = target_gid, name = gname, is_named = true }
else
raise_re_error("unknown extension ?P" .. tostring(p_mode))
end
elseif nc == "(" then
raise_bailout("Conditional regex pattern (?(id)yes|no) is not supported in sandboxed hybrid engine")
else
raise_re_error("unknown extension ?" .. tostring(nc))
end
else
total_groups = total_groups + 1
local gid = total_groups
local body = parse_alt(in_lookaround, alt_depth)
if pos > n or pat:sub(pos, pos) ~= ")" then raise_re_error("missing ), unterminated subpattern") end
pos = pos + 1
closed_groups[gid] = true
node = { type = "Group", kind = "capture", group_id = gid, body = body }
end
elseif c == "\\" then
pos = pos + 1
if pos > n then raise_re_error("bad escape (end of pattern)") end
local ec = pat:sub(pos, pos)
if ec:match("^%d$") then
-- 區分八進位跳脫 (\0..., 或 3 位八進位數) 與群組反向參照 (\1 ~ \99)
local oct3 = pat:sub(pos):match("^([0-7][0-7][0-7])")
if ec == "0" then
local oct_z = pat:sub(pos):match("^([0-7][0-7]?[0-7]?)")
pos = pos + #oct_z
local val = tonumber(oct_z, 8) % 256
local ch = (val == 0) and "%z" or lua_escape_char(is_ignorecase and uchar(val):lower() or uchar(val))
node = { type = "Atom", lua_item = ch, raw_char = uchar(val) }
elseif oct3 then
pos = pos + 3
local val = tonumber(oct3, 8) % 256
local ch = (val == 0) and "%z" or lua_escape_char(is_ignorecase and uchar(val):lower() or uchar(val))
node = { type = "Atom", lua_item = ch, raw_char = uchar(val) }
else
local num2 = pat:sub(pos):match("^(%d%d?)")
pos = pos + #num2
local gid = tonumber(num2, 10)
if gid < 1 or gid > total_groups or not closed_groups[gid] then
raise_re_error("invalid group reference " .. num2)
end
node = { type = "Backref", group_id = gid, is_named = false }
end
elseif ec == "x" then
local hex_s = pat:sub(pos + 1, pos + 2)
if not hex_s:match("^%x%x$") then raise_re_error("incomplete \\x escape") end
pos = pos + 3
local val = tonumber(hex_s, 16)
local ch = (val == 0) and "%z" or lua_escape_char(is_ignorecase and uchar(val):lower() or uchar(val))
node = { type = "Atom", lua_item = ch, raw_char = uchar(val) }
elseif ec == "d" then pos = pos + 1; node = { type = "Atom", lua_item = "%d" }
elseif ec == "D" then pos = pos + 1; node = { type = "Atom", lua_item = "%D" }
elseif ec == "s" then pos = pos + 1; node = { type = "Atom", lua_item = "%s" }
elseif ec == "S" then pos = pos + 1; node = { type = "Atom", lua_item = "%S" }
elseif ec == "w" then pos = pos + 1; node = { type = "Atom", lua_item = "[%w_]" }
elseif ec == "W" then pos = pos + 1; node = { type = "Atom", lua_item = "[^%w_]" }
elseif ec == "A" then pos = pos + 1; node = { type = "Anchor", kind = "str_start" }; allow_quant = false
elseif ec == "Z" then pos = pos + 1; node = { type = "Anchor", kind = "str_end" }; allow_quant = false
elseif ec == "b" then pos = pos + 1; node = { type = "Boundary", kind = "b" }; allow_quant = false
elseif ec == "B" then pos = pos + 1; node = { type = "Boundary", kind = "B" }; allow_quant = false
elseif ec == "n" then pos = pos + 1; node = { type = "Atom", lua_item = "\n", raw_char = "\n" }
elseif ec == "r" then pos = pos + 1; node = { type = "Atom", lua_item = "\r", raw_char = "\r" }
elseif ec == "t" then pos = pos + 1; node = { type = "Atom", lua_item = "\t", raw_char = "\t" }
elseif ec == "f" then pos = pos + 1; node = { type = "Atom", lua_item = "\12", raw_char = "\12" }
elseif ec == "v" then pos = pos + 1; node = { type = "Atom", lua_item = "\11", raw_char = "\11" }
elseif ec == "a" then pos = pos + 1; node = { type = "Atom", lua_item = "\7", raw_char = "\7" }
elseif ec:match("^%a$") then
raise_re_error("bad escape \\" .. ec)
else
pos = pos + 1
local ch = is_ignorecase and ulower(ec) or ec
node = { type = "Atom", lua_item = lua_escape_char(ch), raw_char = ch }
end
elseif c == "*" or c == "+" or c == "?" then
raise_re_error("nothing to repeat")
else
-- 讀取單一 UTF-8 字元
local ch = usub(pat, 1, 1)
if pos > 1 then
local rem = pat:sub(pos)
ch = usub(rem, 1, 1)
end
pos = pos + #ch
local norm_ch = is_ignorecase and ulower(ch) or ch
node = { type = "Atom", lua_item = lua_escape_char(norm_ch), raw_char = norm_ch }
end
local min_rep, max_rep, greedy, has_q = parse_quantifier()
if has_q and not allow_quant then
raise_re_error("nothing to repeat")
end
node.min = min_rep
node.max = max_rep
node.greedy = greedy
node.has_q = has_q
table.insert(items, node)
end
return { type = "Seq", items = items }
end
parse_alt = function(in_lookaround, alt_depth)
local first_seq = parse_seq(in_lookaround, alt_depth)
if pos > n or pat:sub(pos, pos) ~= "|" then
return first_seq
end
local new_depth = alt_depth + 1
if new_depth > MAX_ALT_DEPTH then
raise_bailout("Alternation nesting depth (" .. new_depth .. ") exceeds sandbox limit (" .. MAX_ALT_DEPTH .. ")")
end
if new_depth > max_alt_depth then max_alt_depth = new_depth end
local branches = { first_seq }
while pos <= n and pat:sub(pos, pos) == "|" do
pos = pos + 1
table.insert(branches, parse_seq(in_lookaround, new_depth))
end
return { type = "Alt", branches = branches }
end
local root = parse_alt(false, 0)
if pos <= n then
if pat:sub(pos, pos) == ")" then
raise_re_error("unbalanced parenthesis")
end
raise_re_error("unexpected token at position " .. tostring(pos))
end
return {
root = root,
total_groups = total_groups,
group_index = group_index,
max_alt_depth = max_alt_depth,
lookaround_count = lookaround_count,
flags = flags
}
end
-- ==========================================
-- 4. 階段三：分支展開與三路由編譯器 (Route 1 / Route 2 / Route 3)
-- ==========================================
local function format_atom_quantifier(lua_item, min_r, max_r, greedy)
if min_r == 1 and max_r == 1 then return lua_item end
if min_r == 0 and max_r == math.huge then
return lua_item .. (greedy and "*" or "-")
elseif min_r == 1 and max_r == math.huge then
-- 關鍵修復：Lua 的 '-' 是 0 次以上惰性，因此 '+?' (1 次以上惰性) 必須轉為 XX-
if greedy then return lua_item .. "+"
else return lua_item .. lua_item .. "-" end
elseif min_r == 0 and max_r == 1 then
return lua_item .. "?"
else
local parts = {}
for _ = 1, min_r do table.insert(parts, lua_item) end
if max_r == math.huge then
table.insert(parts, lua_item .. (greedy and "*" or "-"))
else
for _ = min_r + 1, max_r do
table.insert(parts, lua_item .. "?")
end
end
return table.concat(parts)
end
end
-- 將 AST 展開為平坦的分支序列陣列 (每個分支為一條無 | 的指令列表)
local function expand_ast_branches(node)
if node.type == "Alt" then
local res = {}
for _, b in ipairs(node.branches) do
local sub_b = expand_ast_branches(b)
for _, sb in ipairs(sub_b) do
table.insert(res, sb)
if #res > MAX_BRANCHES then
raise_bailout("Total expanded regex alternation branches exceed sandbox limit (" .. MAX_BRANCHES .. ")")
end
end
end
return res
elseif node.type == "Seq" then
local branches = { {} }
for _, item in ipairs(node.items) do
if item.type == "Group" then
local g_min = item.min or 1
local g_max = item.max or 1
local inner_branches = expand_ast_branches(item.body)
if item.kind == "atomic" then
if g_min ~= 1 or g_max ~= 1 then
raise_bailout("Quantified atomic groups are not supported in sandboxed engine")
end
for _, br in ipairs(branches) do
table.insert(br, { type = "Atomic", branches = inner_branches })
end
elseif g_min == 1 and g_max == 1 then
local next_branches = {}
for _, prefix in ipairs(branches) do
for _, ib in ipairs(inner_branches) do
local combined = { unpack(prefix) }
if item.kind == "capture" then
table.insert(combined, { type = "CapOpen", group_id = item.group_id })
end
for _, tok in ipairs(ib) do table.insert(combined, tok) end
if item.kind == "capture" then
table.insert(combined, { type = "CapClose", group_id = item.group_id })
end
table.insert(next_branches, combined)
if #next_branches > MAX_BRANCHES then
raise_bailout("Total expanded regex alternation branches exceed sandbox limit (" .. MAX_BRANCHES .. ")")
end
end
end
branches = next_branches
elseif g_min == 0 and g_max == 1 and #inner_branches == 1 then
-- 可選群組 (?:...)? 或 (...)? 展開為 [有匹配, 空匹配] 兩分支
local next_branches = {}
local ib = inner_branches[1]
for _, prefix in ipairs(branches) do
local with_g = { unpack(prefix) }
if item.kind == "capture" then table.insert(with_g, { type = "CapOpen", group_id = item.group_id }) end
for _, tok in ipairs(ib) do table.insert(with_g, tok) end
if item.kind == "capture" then table.insert(with_g, { type = "CapClose", group_id = item.group_id }) end
local without_g = { unpack(prefix) }
if item.greedy ~= false then
table.insert(next_branches, with_g)
table.insert(next_branches, without_g)
else
table.insert(next_branches, without_g)
table.insert(next_branches, with_g)
end
if #next_branches > MAX_BRANCHES then
raise_bailout("Total expanded regex alternation branches exceed sandbox limit (" .. MAX_BRANCHES .. ")")
end
end
branches = next_branches
elseif #inner_branches == 1 and #inner_branches[1] == 1 and inner_branches[1][1].type == "Atom" and not inner_branches[1][1].has_q then
-- 單一 Atom 的重複群組 (如 (?:\d)+ 或 (\d)+)
local atom_tok = {
type = "Atom",
lua_item = inner_branches[1][1].lua_item,
min = g_min, max = g_max, greedy = item.greedy, has_q = true
}
for _, br in ipairs(branches) do
if item.kind == "capture" then table.insert(br, { type = "CapOpen", group_id = item.group_id }) end
table.insert(br, atom_tok)
if item.kind == "capture" then table.insert(br, { type = "CapClose", group_id = item.group_id }) end
end
elseif g_min == g_max and g_max <= 12 and #inner_branches == 1 then
-- 固定次數展開 (如 (?:ab){3})
local ib = inner_branches[1]
for _, br in ipairs(branches) do
for r_i = 1, g_max do
local record_cap = (item.kind == "capture" and r_i == g_max)
if record_cap then table.insert(br, { type = "CapOpen", group_id = item.group_id }) end
for _, tok in ipairs(ib) do table.insert(br, tok) end
if record_cap then table.insert(br, { type = "CapClose", group_id = item.group_id }) end
end
end
elseif #inner_branches == 1 then
-- 多元素重複群組 (如 (?:ab)+) -> 交由 Route 2 RepeatGroup 步驟處理
for _, br in ipairs(branches) do
table.insert(br, {
type = "RepeatGroup",
kind = item.kind,
group_id = item.group_id,
tokens = inner_branches[1],
min = g_min, max = g_max, greedy = item.greedy
})
end
else
raise_bailout("Quantified alternation group is too complex for sandboxed hybrid regex engine")
end
else
for _, br in ipairs(branches) do
table.insert(br, item)
end
end
end
return branches
end
return { { node } }
end
-- 將單一平坦 Token 序列編譯為 Lua Pattern (用於 Fast-Path 或子區段)
local function compile_tokens_to_lua(tokens, base_cap_map)
local pat_parts = {}
local cap_order = {} -- lua_cap_idx -> py_group_id
local py_to_lua_cap = {} -- py_group_id -> lua_cap_idx
if base_cap_map then
for k, v in pairs(base_cap_map) do py_to_lua_cap[k] = v end
end
local lua_cap_count = 0
for _, tok in ipairs(tokens) do
if tok.type == "Anchor" then
if tok.kind == "str_start" then table.insert(pat_parts, "^")
elseif tok.kind == "str_end" then table.insert(pat_parts, "$") end
elseif tok.type == "CapOpen" then
lua_cap_count = lua_cap_count + 1
cap_order[lua_cap_count] = tok.group_id
py_to_lua_cap[tok.group_id] = lua_cap_count
table.insert(pat_parts, "(")
elseif tok.type == "CapClose" then
table.insert(pat_parts, ")")
elseif tok.type == "Atom" then
table.insert(pat_parts, format_atom_quantifier(tok.lua_item, tok.min or 1, tok.max or 1, tok.greedy ~= false))
elseif tok.type == "Backref" then
local l_idx = py_to_lua_cap[tok.group_id]
if l_idx and l_idx <= 9 and (tok.min or 1) == 1 and (tok.max or 1) == 1 then
table.insert(pat_parts, "%" .. tostring(l_idx))
else
return nil, nil -- 需交由 Route 2 動態兩階段替換處理
end
else
return nil, nil
end
end
return table.concat(pat_parts), cap_order
end
-- 編譯單一分支為執行計畫 (Execution Plan)
local function compile_branch_plan(tokens, flags)
local n_tok = #tokens
local idx = 1
local lead_assertions = {}
while idx <= n_tok do
local t = tokens[idx]
if t.type == "Boundary" or (t.type == "Anchor" and t.kind == "line_start") then
table.insert(lead_assertions, t)
idx = idx + 1
elseif t.type == "Lookaround" and (t.kind == "lookbehind_pos" or t.kind == "lookbehind_neg") then
local lb_branches = expand_ast_branches(t.body)
local lb_pats = {}
for _, lbb in ipairs(lb_branches) do
for _, lbt in ipairs(lbb) do
if lbt.type == "Atom" and lbt.max == math.huge then
raise_bailout("Unbounded variable-length lookbehind is not supported in sandboxed engine")
end
end
local l_pat, l_caps = compile_tokens_to_lua(lbb)
if not l_pat then raise_bailout("Complex lookbehind is not supported in sandboxed engine") end
table.insert(lb_pats, { pat = l_pat .. "$", caps = l_caps })
end
table.insert(lead_assertions, { type = "Lookbehind", positive = (t.kind == "lookbehind_pos"), branches = lb_pats })
idx = idx + 1
else
break
end
end
local trail_assertions = {}
local end_idx = n_tok
while end_idx >= idx do
local t = tokens[end_idx]
if t.type == "Boundary" or (t.type == "Anchor" and t.kind == "line_end") then
table.insert(trail_assertions, 1, t)
end_idx = end_idx - 1
elseif t.type == "Lookaround" and (t.kind == "lookahead_pos" or t.kind == "lookahead_neg") then
local la_branches = expand_ast_branches(t.body)
local la_pats = {}
for _, lab in ipairs(la_branches) do
local l_pat, l_caps = compile_tokens_to_lua(lab)
if not l_pat then raise_bailout("Complex lookahead is not supported in sandboxed engine") end
table.insert(la_pats, { raw_pat = l_pat, anchored_pat = "^" .. l_pat, caps = l_caps })
end
table.insert(trail_assertions, 1, { type = "Lookahead", positive = (t.kind == "lookahead_pos"), branches = la_pats })
end_idx = end_idx - 1
else
break
end
end
local body_tokens = {}
local has_named_backref = false
local has_stage2_feature = false
for i = idx, end_idx do
local bt = tokens[i]
if bt.type == "Lookaround" then
raise_bailout("Mid-pattern lookaround assertion is too complex for sandboxed hybrid engine")
end
if bt.type == "Backref" and bt.is_named then has_named_backref = true end
if bt.type == "Atomic" or bt.type == "RepeatGroup" or bt.type == "Boundary" then
has_stage2_feature = true
end
table.insert(body_tokens, bt)
end
-- 嘗試直接編譯主體為單一 Lua Pattern
local fast_pat, fast_caps = compile_tokens_to_lua(body_tokens)
if fast_pat and not has_stage2_feature then
-- 最佳化：若結尾只有單一正前瞻 (?=la) 且無其他斷言，可融合為 (body)la 獲得 C 底層回溯能力
local fused_la = nil
if #trail_assertions == 1 and trail_assertions[1].type == "Lookahead" and trail_assertions[1].positive and #trail_assertions[1].branches == 1 then
local la_b = trail_assertions[1].branches[1]
if not fast_pat:sub(-1):match("%$$") and (#fast_caps + #la_b.caps + 1) <= 30 then
fused_la = {
pat = "(" .. fast_pat .. ")" .. la_b.raw_pat,
body_caps = fast_caps,
la_caps = la_b.caps
}
end
end
return {
mode = "fast_body",
lua_pat = fast_pat,
cap_order = fast_caps,
fused_la = fused_la,
lead_assertions = lead_assertions,
trail_assertions = trail_assertions,
has_named_backref = has_named_backref,
body_tokens = body_tokens
}
end
-- 否則拆解為分段微指令序列 (Segments：支援 Atomic (?>...), 量化 Backref \1+, RepeatGroup (?:ab)+, 中段 \b)
local segments = {}
local cur_chunk = {}
local function flush_chunk()
if #cur_chunk > 0 then
local c_pat, c_caps = compile_tokens_to_lua(cur_chunk)
if not c_pat then raise_bailout("Unsupported complex subpattern in sandboxed hybrid engine") end
table.insert(segments, { kind = "lua", pat = c_pat, anchored_pat = "^" .. c_pat, caps = c_caps })
cur_chunk = {}
end
end
for _, bt in ipairs(body_tokens) do
if bt.type == "Atomic" then
flush_chunk()
local atomic_pats = {}
for _, ab in ipairs(bt.branches) do
local a_pat, a_caps = compile_tokens_to_lua(ab)
if not a_pat then raise_bailout("Complex atomic group is not supported") end
table.insert(atomic_pats, { pat = a_pat, anchored_pat = "^" .. a_pat, caps = a_caps })
end
table.insert(segments, { kind = "atomic", branches = atomic_pats })
elseif bt.type == "Backref" then
flush_chunk()
table.insert(segments, {
kind = "backref",
group_id = bt.group_id,
min = bt.min or 1,
max = bt.max or 1,
greedy = bt.greedy ~= false
})
elseif bt.type == "RepeatGroup" then
flush_chunk()
local r_pat, r_caps = compile_tokens_to_lua(bt.tokens)
if not r_pat then raise_bailout("Complex repeated group is not supported") end
table.insert(segments, {
kind = "repeat_group",
group_id = (bt.kind == "capture") and bt.group_id or nil,
pat = r_pat,
anchored_pat = "^" .. r_pat,
caps = r_caps,
min = bt.min, max = bt.max, greedy = bt.greedy ~= false
})
elseif bt.type == "Boundary" then
flush_chunk()
table.insert(segments, { kind = "boundary", b_kind = bt.kind })
else
table.insert(cur_chunk, bt)
end
end
flush_chunk()
return {
mode = "segmented",
segments = segments,
lead_assertions = lead_assertions,
trail_assertions = trail_assertions,
has_named_backref = has_named_backref
}
end
local function compile_regex(raw_pat, init_flags, is_bytes)
local cache_key = tostring(is_bytes) .. "|" .. tostring(init_flags or 0) .. "|" .. raw_pat
if compile_cache[cache_key] then return compile_cache[cache_key] end
local cleaned, flags = preprocess_pattern(raw_pat, init_flags)
local ast_info = parse_regex_ast(cleaned, flags)
local raw_branches = expand_ast_branches(ast_info.root)
local branch_plans = {}
local route = 1
if #raw_branches > 1 or ast_info.lookaround_count > 0 then
route = 3
end
for _, rb in ipairs(raw_branches) do
local plan = compile_branch_plan(rb, flags)
table.insert(branch_plans, plan)
if route == 1 then
if plan.mode == "segmented" or plan.has_named_backref or #plan.lead_assertions > 0 or #plan.trail_assertions > 0 then
route = 2
end
end
end
local compiled = {
raw_pattern = raw_pat,
flags = flags,
is_bytes = is_bytes,
is_ignorecase = has_flag(flags, FLAG_IGNORECASE),
total_groups = ast_info.total_groups,
group_index = ast_info.group_index,
branches = branch_plans,
route = route
}
compile_cache[cache_key] = compiled
return compiled
end
-- ==========================================
-- 5. 階段四：三路由執行引擎與斷言驗證器
-- ==========================================
local function check_boundary_at(orig_s, pos, len, b_kind)
local prev_c = (pos > 1) and usub(orig_s, pos - 1, pos - 1) or ""
local next_c = (pos <= len) and usub(orig_s, pos, pos) or ""
local is_wb = (is_word_char(prev_c) ~= is_word_char(next_c))
if b_kind == "b" then return is_wb else return not is_wb end
end
local function check_lead_assertions(assertions, search_s, orig_s, start_pos, len, caps_out)
for _, a in ipairs(assertions) do
if a.type == "Anchor" and a.kind == "line_start" then
if start_pos > 1 and usub(orig_s, start_pos - 1, start_pos - 1) ~= "\n" then return false end
elseif a.type == "Boundary" then
if not check_boundary_at(orig_s, start_pos, len, a.kind) then return false end
elseif a.type == "Lookbehind" then
local prefix = (start_pos > 1) and usub(search_s, 1, start_pos - 1) or ""
local matched_lb = false
for _, lbb in ipairs(a.branches) do
local results = { ufind(prefix, lbb.pat) }
if results[1] then
matched_lb = true
if a.positive and lbb.caps then
for c_i, gid in ipairs(lbb.caps) do
caps_out[gid] = results[c_i + 2]
end
end
break
end
end
if a.positive ~= matched_lb then return false end
end
end
return true
end
local function check_trail_assertions(assertions, search_s, orig_s, end_pos, len, caps_out)
local next_pos = end_pos + 1
for _, a in ipairs(assertions) do
if a.type == "Anchor" and a.kind == "line_end" then
if end_pos < len and usub(orig_s, next_pos, next_pos) ~= "\n" then return false end
elseif a.type == "Boundary" then
if not check_boundary_at(orig_s, next_pos, len, a.kind) then return false end
elseif a.type == "Lookahead" then
local suffix = (next_pos <= len) and usub(search_s, next_pos) or ""
local matched_la = false
for _, lab in ipairs(a.branches) do
local results = { ufind(suffix, lab.anchored_pat) }
if results[1] then
matched_la = true
if a.positive and lab.caps then
for c_i, gid in ipairs(lab.caps) do
caps_out[gid] = results[c_i + 2]
end
end
break
end
end
if a.positive ~= matched_la then return false end
end
end
return true
end
-- 執行單一分支於指定範圍 [search_pos, endpos]
local function execute_branch(plan, search_s, orig_s, search_pos, len, anchored_start, anchored_full)
-- [A] Fast-Body 模式 (Route 1 直通，或帶邊界斷言的單段 Pattern)
if plan.mode == "fast_body" then
-- 若已融合正前瞻 (body)la 且非 fullmatch
if plan.fused_la and not anchored_full and #plan.lead_assertions == 0 then
local f_pat = anchored_start and ("^" .. plan.fused_la.pat) or plan.fused_la.pat
local res = { ufind(search_s, f_pat, search_pos) }
if not res[1] then return nil end
local s_idx = res[1]
local body_str = res[3] or ""
local e_idx = s_idx + ulen(body_str) - 1
local caps = {}
local b_caps = plan.fused_la.body_caps
for i, gid in ipairs(b_caps) do
caps[gid] = res[i + 3]
end
local offset = 3 + #b_caps
for i, gid in ipairs(plan.fused_la.la_caps) do
caps[gid] = res[offset + i]
end
return s_idx, e_idx, caps
end
local cur_pos = search_pos
local pat_to_use = plan.lua_pat
if anchored_start then pat_to_use = "^" .. pat_to_use end
if anchored_full and #plan.trail_assertions == 0 then pat_to_use = pat_to_use .. "$" end
while cur_pos <= len + 1 do
local res = { ufind(search_s, pat_to_use, cur_pos) }
if not res[1] then return nil end
local s_idx, e_idx = res[1], res[2]
local lead_caps = {}
if check_lead_assertions(plan.lead_assertions, search_s, orig_s, s_idx, len, lead_caps) then
-- 檢查尾部斷言；若失敗且非原子匹配，嘗試退位回溯 e_try = e_idx - 1 .. s_idx
local min_e = (#plan.trail_assertions > 0) and (s_idx - 1) or e_idx
for e_try = e_idx, min_e, -1 do
local try_res = res
local sub_ok = true
if e_try < e_idx then
local slice_s = usub(search_s, s_idx, e_try)
try_res = { ufind(slice_s, "^" .. plan.lua_pat .. "$") }
if not try_res[1] then sub_ok = false end
end
if sub_ok and (not anchored_full or e_try == len) then
local trail_caps = {}
if check_trail_assertions(plan.trail_assertions, search_s, orig_s, e_try, len, trail_caps) then
local caps = {}
for k, v in pairs(lead_caps) do caps[k] = v end
for i, gid in ipairs(plan.cap_order) do
local c_val = try_res[i + 2]
if type(c_val) == "string" then
caps[gid] = c_val
end
end
for k, v in pairs(trail_caps) do caps[k] = v end
return s_idx, e_try, caps
end
end
end
end
if anchored_start or pat_to_use:sub(1, 1) == "^" then return nil end
cur_pos = s_idx + 1
end
return nil
end
-- [B] Segmented 多階段微指令模式 (Route 2 / Route 3：含 Atomic (?>...), 量化 Backref, RepeatGroup)
local segs = plan.segments
local n_segs = #segs
local function match_seg_from(seg_idx, cur_cursor, caps)
if seg_idx > n_segs then
if anchored_full and (cur_cursor - 1) ~= len then return nil end
local trail_caps = {}
if check_trail_assertions(plan.trail_assertions, search_s, orig_s, cur_cursor - 1, len, trail_caps) then
for k, v in pairs(trail_caps) do caps[k] = v end
return cur_cursor - 1
end
return nil
end
local seg = segs[seg_idx]
local rem_s = (cur_cursor <= len) and usub(search_s, cur_cursor) or ""
if seg.kind == "boundary" then
if check_boundary_at(orig_s, cur_cursor, len, seg.b_kind) then
return match_seg_from(seg_idx + 1, cur_cursor, caps)
end
return nil
elseif seg.kind == "atomic" then
-- 原子群組 (?>...)：一旦匹配成功即鎖定游標，絕不回溯至內部
for _, ab in ipairs(seg.branches) do
local res = { ufind(rem_s, ab.anchored_pat) }
if res[1] then
local saved = {}
for k, v in pairs(caps) do saved[k] = v end
for i, gid in ipairs(ab.caps) do caps[gid] = res[i + 2] end
local next_cur = cur_cursor + res[2]
return match_seg_from(seg_idx + 1, next_cur, caps)
end
end
return nil
elseif seg.kind == "backref" then
-- 階段二動態反向參照匹配 (含 \1+, (?P=name)+ 等量詞支援)
local ref_val = caps[seg.group_id]
if not ref_val then return nil end
local ref_len = ulen(ref_val)
if ref_len == 0 then
return match_seg_from(seg_idx + 1, cur_cursor, caps)
end
local max_possible = 0
local scan_c = cur_cursor
while max_possible < seg.max and (scan_c + ref_len - 1) <= len do
if usub(search_s, scan_c, scan_c + ref_len - 1) == ref_val then
max_possible = max_possible + 1
scan_c = scan_c + ref_len
else
break
end
end
if max_possible < seg.min then return nil end
local start_k = seg.greedy and max_possible or seg.min
local end_k = seg.greedy and seg.min or max_possible
local step_k = seg.greedy and -1 or 1
for k = start_k, end_k, step_k do
local saved = {}
for g_k, g_v in pairs(caps) do saved[g_k] = g_v end
local fin = match_seg_from(seg_idx + 1, cur_cursor + k * ref_len, saved)
if fin then
for g_k, g_v in pairs(saved) do caps[g_k] = g_v end
return fin
end
end
return nil
elseif seg.kind == "repeat_group" then
local positions = { [0] = { cursor = cur_cursor, caps = {} } }
for k, v in pairs(caps) do positions[0].caps[k] = v end
local count = 0
local scan_c = cur_cursor
while count < seg.max and scan_c <= len do
local sub_rem = usub(search_s, scan_c)
local res = { ufind(sub_rem, seg.anchored_pat) }
if not res[1] or res[2] == 0 then break end
count = count + 1
scan_c = scan_c + res[2]
local snap_caps = {}
for k, v in pairs(positions[count - 1].caps) do snap_caps[k] = v end
if seg.group_id then
snap_caps[seg.group_id] = usub( sub_rem, 1, res[2] )
end
for i, gid in ipairs(seg.caps) do snap_caps[gid] = res[i + 2] end
positions[count] = { cursor = scan_c, caps = snap_caps }
end
if count < seg.min then return nil end
local start_k = seg.greedy and count or seg.min
local end_k = seg.greedy and seg.min or count
local step_k = seg.greedy and -1 or 1
for k = start_k, end_k, step_k do
local try_caps = {}
for gk, gv in pairs(positions[k].caps) do try_caps[gk] = gv end
local fin = match_seg_from(seg_idx + 1, positions[k].cursor, try_caps)
if fin then
for gk, gv in pairs(try_caps) do caps[gk] = gv end
return fin
end
end
return nil
elseif seg.kind == "lua" then
local res = { ufind(rem_s, seg.anchored_pat) }
if not res[1] then return nil end
local max_e = res[2]
-- 優先嘗試最長匹配，若後續段失敗則逐步回溯
for try_len = max_e, 0, -1 do
local try_res = res
local ok = true
if try_len < max_e then
local slice_rem = usub(rem_s, 1, try_len)
try_res = { ufind(slice_rem, seg.anchored_pat .. "$") }
if not try_res[1] then ok = false end
end
if ok then
local try_caps = {}
for gk, gv in pairs(caps) do try_caps[gk] = gv end
for i, gid in ipairs(seg.caps) do try_caps[gid] = try_res[i + 2] end
local fin = match_seg_from(seg_idx + 1, cur_cursor + try_len, try_caps)
if fin then
for gk, gv in pairs(try_caps) do caps[gk] = gv end
return fin
end
end
end
return nil
end
return nil
end
local start_p = search_pos
local end_p = anchored_start and search_pos or (len + 1)
local first_seg = segs[1]
while start_p <= end_p do
-- 加速：若第一段是標準 Lua pattern 或 Atomic 且無前置斷言，先用 ufind 快速跳躍至候選點
if not anchored_start and #plan.lead_assertions == 0 and first_seg then
if first_seg.kind == "lua" then
local s_jump = ufind(search_s, first_seg.pat, start_p)
if not s_jump then return nil end
start_p = s_jump
elseif first_seg.kind == "atomic" and #first_seg.branches == 1 then
local s_jump = ufind(search_s, first_seg.branches[1].pat, start_p)
if not s_jump then return nil end
start_p = s_jump
end
end
local caps = {}
if check_lead_assertions(plan.lead_assertions, search_s, orig_s, start_p, len, caps) then
local fin_e = match_seg_from(1, start_p, caps)
if fin_e then
return start_p, fin_e, caps
end
end
if anchored_start then return nil end
start_p = start_p + 1
end
return nil
end
-- 頂層調度器：在所有分支中依據 Python Leftmost-First 規則選出最佳匹配
local function exec_compiled_pattern(compiled, orig_s, pos, endpos, mode)
local full_len = ulen(orig_s)
local s_pos = (pos and pos > 0) and (pos + 1) or 1
local e_pos = (endpos and endpos < full_len) and endpos or full_len
if s_pos > e_pos + 1 then return nil end
local work_orig = (e_pos < full_len) and usub(orig_s, 1, e_pos) or orig_s
local work_search = compiled.is_ignorecase and ulower(work_orig) or work_orig
local work_len = e_pos
local anchored_start = (mode == "match" or mode == "fullmatch")
local anchored_full = (mode == "fullmatch")
local best_s, best_e, best_caps = nil, nil, nil
for _, plan in ipairs(compiled.branches) do
local m_s, m_e, m_caps = execute_branch(plan, work_search, work_orig, s_pos, work_len, anchored_start, anchored_full)
if m_s then
if not best_s or m_s < best_s then
best_s, best_e, best_caps = m_s, m_e, m_caps
if anchored_start then break end
end
end
end
if not best_s then return nil end
-- 若啟用 IGNORECASE，將捕獲到的子字串還原為原字串對應位置的真實大小寫，並計算各群組 span
local final_caps = {}
local group_spans = { [0] = { best_s - 1, best_e } }
local match_slice_search = usub(work_search, best_s, best_e)
local search_cursor = 1
for gid = 1, compiled.total_groups do
local c_val = best_caps[gid]
if c_val ~= nil then
local c_len = ulen(c_val)
local found_rel = ufind(match_slice_search, c_val, search_cursor, true)
if not found_rel then
found_rel = ufind(match_slice_search, c_val, 1, true)
end
if found_rel then
local abs_s = best_s + found_rel - 1
local abs_e = abs_s + c_len - 1
group_spans[gid] = { abs_s - 1, abs_e }
final_caps[gid] = usub(orig_s, abs_s, abs_e)
search_cursor = found_rel + math.max(1, c_len)
else
final_caps[gid] = c_val
group_spans[gid] = { -1, -1 }
end
else
group_spans[gid] = { -1, -1 }
end
end
return {
start_idx = best_s - 1,
end_idx = best_e,
match_str = usub(orig_s, best_s, best_e),
captures = final_caps,
spans = group_spans,
pos = pos or 0,
endpos = e_pos,
orig_s = orig_s
}
end
-- ==========================================
-- 6. Match 與 Pattern 物件模型封裝
-- ==========================================
local function expand_replacement_template(tmpl, m_data, compiled)
local out = {}
local i = 1
local n = #tmpl
while i <= n do
local c = tmpl:sub(i, i)
if c == "\\" and i < n then
local nc = tmpl:sub(i + 1, i + 1)
if nc == "g" and tmpl:sub(i + 2, i + 2) == "<" then
local g_ref, next_p = tmpl:sub(i + 3):match("^([^>]+)>()")
if not g_ref then raise_re_error("missing >, unterminated group name in replacement") end
i = i + 2 + next_p
local gid = tonumber(g_ref, 10) or compiled.group_index[g_ref]
if gid == 0 then
table.insert(out, m_data.match_str or "")
elseif gid and gid >= 1 and gid <= compiled.total_groups then
table.insert(out, m_data.captures[gid] or "")
else
raise_re_error("invalid group reference '" .. g_ref .. "' in replacement")
end
elseif nc:match("^%d$") then
local num_s = tmpl:sub(i + 1):match("^(%d%d?)")
local gid = tonumber(num_s, 10)
if gid > compiled.total_groups and #num_s == 2 then
num_s = num_s:sub(1, 1)
gid = tonumber(num_s, 10)
end
i = i + 1 + #num_s
if gid == 0 then
table.insert(out, "\0")
elseif gid >= 1 and gid <= compiled.total_groups then
table.insert(out, m_data.captures[gid] or "")
else
raise_re_error("invalid group reference \\" .. num_s)
end
elseif nc == "n" then table.insert(out, "\n"); i = i + 2
elseif nc == "t" then table.insert(out, "\t"); i = i + 2
elseif nc == "r" then table.insert(out, "\r"); i = i + 2
elseif nc == "\\" then table.insert(out, "\\"); i = i + 2
else
table.insert(out, "\\" .. nc); i = i + 2
end
else
table.insert(out, c)
i = i + 1
end
end
return table.concat(out)
end
local function make_match_object(m_data, pat_inst, compiled)
if not MatchClass then
local function resolve_group_arg(self, g_arg)
local comp = self.__dict._compiled
local md = self.__dict._mdata
if g_arg == nil or g_arg == 0 then
return 0, md.match_str
end
if type(g_arg) == "table" and g_arg.__type == "int" then
g_arg = RUtils.unwrap_num(g_arg)
end
if type(g_arg) == "number" and math.floor(g_arg) == g_arg then
if g_arg < 0 or g_arg > comp.total_groups then
Runtime.raise("IndexError", "no such group")
end
if g_arg == 0 then return 0, md.match_str end
return g_arg, md.captures[g_arg]
elseif type(g_arg) == "string" then
local gid = comp.group_index[g_arg]
if not gid then Runtime.raise("IndexError", "no such group") end
return gid, md.captures[gid]
end
Runtime.raise("IndexError", "no such group")
end
local match_dict = {
group = {
__type = "builtin_method", __name = "group",
__call = function(args)
local self = args[1]
local is_b = self.__dict._compiled.is_bytes
if #args <= 1 then
local _, val = resolve_group_arg(self, 0)
return wrap_output(val, is_b)
elseif #args == 2 then
local _, val = resolve_group_arg(self, args[2])
return wrap_output(val, is_b)
else
local elts = {}
for i = 2, #args do
local _, val = resolve_group_arg(self, args[i])
table.insert(elts, wrap_output(val, is_b))
end
return { __type = "tuple", elements = elts }
end
end
},
__getitem__ = {
__type = "builtin_method", __name = "__getitem__",
__call = function(args)
local self = args[1]
local _, val = resolve_group_arg(self, args[2])
return wrap_output(val, self.__dict._compiled.is_bytes)
end
},
groups = {
__type = "builtin_method", __name = "groups",
__call = function(args, kwargs)
local self = args[1]
local default_val = (args[2] ~= nil and args[2]) or (kwargs and kwargs.default) or Runtime.builtins.None
local comp = self.__dict._compiled
local md = self.__dict._mdata
local elts = {}
for i = 1, comp.total_groups do
local v = md.captures[i]
if v == nil then table.insert(elts, default_val)
else table.insert(elts, wrap_output(v, comp.is_bytes)) end
end
return { __type = "tuple", elements = elts }
end
},
groupdict = {
__type = "builtin_method", __name = "groupdict",
__call = function(args, kwargs)
local self = args[1]
local default_val = (args[2] ~= nil and args[2]) or (kwargs and kwargs.default) or Runtime.builtins.None
local comp = self.__dict._compiled
local md = self.__dict._mdata
local kv_pairs = {}
for name, gid in pairs(comp.group_index) do
local v = md.captures[gid]
local out_v = (v == nil) and default_val or wrap_output(v, comp.is_bytes)
table.insert(kv_pairs, { key = name, value = out_v })
end
return { __type = "dict", pairs = kv_pairs }
end
},
start = {
__type = "builtin_method", __name = "start",
__call = function(args)
local self = args[1]
local gid = resolve_group_arg(self, args[2] or 0)
local sp = self.__dict._mdata.spans[gid]
return sp and sp[1] or -1
end
},
["end"] = {
__type = "builtin_method", __name = "end",
__call = function(args)
local self = args[1]
local gid = resolve_group_arg(self, args[2] or 0)
local sp = self.__dict._mdata.spans[gid]
return sp and sp[2] or -1
end
},
span = {
__type = "builtin_method", __name = "span",
__call = function(args)
local self = args[1]
local gid = resolve_group_arg(self, args[2] or 0)
local sp = self.__dict._mdata.spans[gid] or { -1, -1 }
return { __type = "tuple", elements = { sp[1], sp[2] } }
end
},
expand = {
__type = "builtin_method", __name = "expand",
__call = function(args)
local self = args[1]
local tmpl = unpack_pattern_input(args[2])
local res = expand_replacement_template(tmpl, self.__dict._mdata, self.__dict._compiled)
return wrap_output(res, self.__dict._compiled.is_bytes)
end
},
__bool__ = { __type = "builtin_method", __call = function() return true end },
__repr__ = {
__type = "builtin_method",
__call = function(args)
local md = args[1].__dict._mdata
return string.format("<re.Match object; span=(%d, %d), match=%s>",
md.start_idx, md.end_idx, RUtils.to_str(wrap_output(md.match_str, args[1].__dict._compiled.is_bytes), true))
end
}
}
match_dict.__str__ = match_dict.__repr__
MatchClass = PyClass.make_class("Match", { Runtime.builtins.object }, match_dict)
MatchClass.__dict["__module__"] = "re"
end
local inst = PyClass.make_instance(MatchClass)
inst.__dict._mdata = m_data
inst.__dict._compiled = compiled
inst.__dict.pos = m_data.pos
inst.__dict.endpos = m_data.endpos
inst.__dict.re = pat_inst
inst.__dict["string"] = wrap_output(m_data.orig_s, compiled.is_bytes)
local last_idx = Runtime.builtins.None
local last_grp = Runtime.builtins.None
for gid = compiled.total_groups, 1, -1 do
if m_data.captures[gid] ~= nil then
last_idx = gid
for name, id_val in pairs(compiled.group_index) do
if id_val == gid then last_grp = name; break end
end
break
end
end
inst.__dict.lastindex = last_idx
inst.__dict.lastgroup = last_grp
return inst
end
local function make_pattern_object(compiled)
if not PatternClass then
local function parse_pos_bounds(args, kwargs, full_len)
local pos = (args[3] ~= nil and not is_none(args[3])) and RUtils.unwrap_num(args[3]) or (kwargs and kwargs.pos and RUtils.unwrap_num(kwargs.pos)) or 0
local endpos = (args[4] ~= nil and not is_none(args[4])) and RUtils.unwrap_num(args[4]) or (kwargs and kwargs.endpos and RUtils.unwrap_num(kwargs.endpos)) or full_len
return math.max(0, pos), math.min(full_len, endpos)
end
local function subn_impl(self, repl, target_in, count)
local comp = self.__dict._compiled
local raw_s = unpack_target_string(target_in, comp.is_bytes)
local full_len = ulen(raw_s)
local max_count = (count and not is_none(count)) and RUtils.unwrap_num(count) or 0
if max_count < 0 then max_count = 0 end
local is_callable = Runtime.builtins.callable({ repl })
local repl_tmpl = nil
if not is_callable then
repl_tmpl = unpack_target_string(repl, comp.is_bytes)
end
local out_parts = {}
local last_end = 0
local search_pos = 0
local n_subs = 0
local Evaluator = is_callable and require("Module:PythonScript/Evaluator") or nil
while search_pos <= full_len do
if max_count > 0 and n_subs >= max_count then break end
local m_data = exec_compiled_pattern(comp, raw_s, search_pos, full_len, "search")
if not m_data then break end
if m_data.start_idx > last_end then
table.insert(out_parts, usub(raw_s, last_end + 1, m_data.start_idx))
end
local rep_piece
if is_callable then
local m_obj = make_match_object(m_data, self, comp)
local r_val = Evaluator.invoke(repl, { m_obj }, {})
rep_piece = unpack_target_string(r_val, comp.is_bytes)
else
rep_piece = expand_replacement_template(repl_tmpl, m_data, comp)
end
table.insert(out_parts, rep_piece)
n_subs = n_subs + 1
last_end = m_data.end_idx
if m_data.end_idx == m_data.start_idx then
if m_data.end_idx < full_len then
table.insert(out_parts, usub(raw_s, m_data.end_idx + 1, m_data.end_idx + 1))
end
last_end = m_data.end_idx + 1
search_pos = m_data.end_idx + 1
else
search_pos = m_data.end_idx
end
end
if last_end <= full_len then
table.insert(out_parts, usub(raw_s, last_end + 1))
end
return wrap_output(table.concat(out_parts), comp.is_bytes), n_subs
end
local pat_dict = {
search = {
__type = "builtin_method", __name = "search",
__call = function(args, kwargs)
local self = args[1]
local comp = self.__dict._compiled
local raw_s = unpack_target_string(args[2], comp.is_bytes)
local pos, endpos = parse_pos_bounds(args, kwargs, ulen(raw_s))
local m_data = exec_compiled_pattern(comp, raw_s, pos, endpos, "search")
if not m_data then return Runtime.builtins.None end
return make_match_object(m_data, self, comp)
end
},
match = {
__type = "builtin_method", __name = "match",
__call = function(args, kwargs)
local self = args[1]
local comp = self.__dict._compiled
local raw_s = unpack_target_string(args[2], comp.is_bytes)
local pos, endpos = parse_pos_bounds(args, kwargs, ulen(raw_s))
local m_data = exec_compiled_pattern(comp, raw_s, pos, endpos, "match")
if not m_data then return Runtime.builtins.None end
return make_match_object(m_data, self, comp)
end
},
fullmatch = {
__type = "builtin_method", __name = "fullmatch",
__call = function(args, kwargs)
local self = args[1]
local comp = self.__dict._compiled
local raw_s = unpack_target_string(args[2], comp.is_bytes)
local pos, endpos = parse_pos_bounds(args, kwargs, ulen(raw_s))
local m_data = exec_compiled_pattern(comp, raw_s, pos, endpos, "fullmatch")
if not m_data then return Runtime.builtins.None end
return make_match_object(m_data, self, comp)
end
},
findall = {
__type = "builtin_method", __name = "findall",
__call = function(args, kwargs)
local self = args[1]
local comp = self.__dict._compiled
local raw_s = unpack_target_string(args[2], comp.is_bytes)
local pos, endpos = parse_pos_bounds(args, kwargs, ulen(raw_s))
local results = {}
local cur_pos = pos
while cur_pos <= endpos do
local m_data = exec_compiled_pattern(comp, raw_s, cur_pos, endpos, "search")
if not m_data then break end
if comp.total_groups == 0 then
table.insert(results, wrap_output(m_data.match_str, comp.is_bytes))
elseif comp.total_groups == 1 then
table.insert(results, wrap_output(m_data.captures[1] or "", comp.is_bytes))
else
local tup = {}
for g = 1, comp.total_groups do
table.insert(tup, wrap_output(m_data.captures[g] or "", comp.is_bytes))
end
table.insert(results, { __type = "tuple", elements = tup })
end
if m_data.end_idx == m_data.start_idx then
cur_pos = m_data.end_idx + 1
else
cur_pos = m_data.end_idx
end
end
return { __type = "list", elements = results }
end
},
finditer = {
__type = "builtin_method", __name = "finditer",
__call = function(args, kwargs)
local self = args[1]
local comp = self.__dict._compiled
local raw_s = unpack_target_string(args[2], comp.is_bytes)
local pos, endpos = parse_pos_bounds(args, kwargs, ulen(raw_s))
local matches = {}
local cur_pos = pos
while cur_pos <= endpos do
local m_data = exec_compiled_pattern(comp, raw_s, cur_pos, endpos, "search")
if not m_data then break end
table.insert(matches, make_match_object(m_data, self, comp))
if m_data.end_idx == m_data.start_idx then
cur_pos = m_data.end_idx + 1
else
cur_pos = m_data.end_idx
end
end
return Runtime.builtins.iter({ { __type = "list", elements = matches } })
end
},
split = {
__type = "builtin_method", __name = "split",
__call = function(args, kwargs)
local self = args[1]
local comp = self.__dict._compiled
local raw_s = unpack_target_string(args[2], comp.is_bytes)
local maxsplit = (args[3] ~= nil and not is_none(args[3])) and RUtils.unwrap_num(args[3]) or (kwargs and kwargs.maxsplit and RUtils.unwrap_num(kwargs.maxsplit)) or 0
local full_len = ulen(raw_s)
local parts = {}
local last_end = 0
local search_pos = 0
local n_splits = 0
while search_pos <= full_len do
if maxsplit > 0 and n_splits >= maxsplit then break end
local m_data = exec_compiled_pattern(comp, raw_s, search_pos, full_len, "search")
if not m_data then break end
if m_data.end_idx == m_data.start_idx and m_data.start_idx == last_end then
search_pos = search_pos + 1
else
table.insert(parts, wrap_output(usub(raw_s, last_end + 1, m_data.start_idx), comp.is_bytes))
for g = 1, comp.total_groups do
local c_val = m_data.captures[g]
table.insert(parts, c_val ~= nil and wrap_output(c_val, comp.is_bytes) or Runtime.builtins.None)
end
last_end = m_data.end_idx
n_splits = n_splits + 1
if m_data.end_idx == m_data.start_idx then
search_pos = m_data.end_idx + 1
else
search_pos = m_data.end_idx
end
end
end
table.insert(parts, wrap_output(usub(raw_s, last_end + 1), comp.is_bytes))
return { __type = "list", elements = parts }
end
},
sub = {
__type = "builtin_method", __name = "sub",
__call = function(args, kwargs)
local count = (args[4] ~= nil) and args[4] or (kwargs and kwargs.count) or 0
local res_s = subn_impl(args[1], args[2], args[3], count)
return res_s
end
},
subn = {
__type = "builtin_method", __name = "subn",
__call = function(args, kwargs)
local count = (args[4] ~= nil) and args[4] or (kwargs and kwargs.count) or 0
local res_s, n_subs = subn_impl(args[1], args[2], args[3], count)
return { __type = "tuple", elements = { res_s, n_subs } }
end
},
__repr__ = {
__type = "builtin_method",
__call = function(args)
local comp = args[1].__dict._compiled
return "re.compile(" .. RUtils.to_str(wrap_output(comp.raw_pattern, comp.is_bytes), true) .. ")"
end
}
}
pat_dict.__str__ = pat_dict.__repr__
PatternClass = PyClass.make_class("Pattern", { Runtime.builtins.object }, pat_dict)
PatternClass.__dict["__module__"] = "re"
end
local inst = PyClass.make_instance(PatternClass)
inst.__dict._compiled = compiled
inst.__dict.pattern = wrap_output(compiled.raw_pattern, compiled.is_bytes)
inst.__dict.flags = compiled.flags
inst.__dict.groups = compiled.total_groups
inst.__dict._route = compiled.route
local gi_pairs = {}
for k, v in pairs(compiled.group_index) do
table.insert(gi_pairs, { key = k, value = v })
end
inst.__dict.groupindex = { __type = "dict", pairs = gi_pairs }
return inst
end
-- ==========================================
-- 7. 頂層模組介面匯出 (re.*)
-- ==========================================
local function ensure_pattern_obj(pat_or_str, flags)
if type(pat_or_str) == "table" and pat_or_str.__type == "instance" and pat_or_str.__class == PatternClass then
if flags and flags ~= 0 then
Runtime.raise("ValueError", "cannot process flags argument with a compiled pattern")
end
return pat_or_str
end
local raw_pat, is_bytes = unpack_pattern_input(pat_or_str)
local f_num = (flags and not is_none(flags)) and RUtils.unwrap_num(flags) or 0
local compiled = compile_regex(raw_pat, f_num, is_bytes)
return make_pattern_object(compiled)
end
local re_mod_cache = nil
function Regexp.get_module()
if re_mod_cache then return re_mod_cache end
local err_cls = get_re_error_class()
-- 觸發初始化 MatchClass 與 PatternClass
make_pattern_object(compile_regex("", 0, false))
local re_dict = {
NOFLAG = FLAG_NOFLAG,
I = FLAG_IGNORECASE, IGNORECASE = FLAG_IGNORECASE,
L = FLAG_LOCALE, LOCALE = FLAG_LOCALE,
M = FLAG_MULTILINE, MULTILINE = FLAG_MULTILINE,
S = FLAG_DOTALL, DOTALL = FLAG_DOTALL,
U = FLAG_UNICODE, UNICODE = FLAG_UNICODE,
X = FLAG_VERBOSE, VERBOSE = FLAG_VERBOSE,
A = FLAG_ASCII, ASCII = FLAG_ASCII,
error = err_cls,
PatternError = err_cls,
Pattern = PatternClass,
Match = MatchClass,
compile = {
__type = "builtin_method", __name = "compile",
__call = function(args, kwargs)
local flags = (args and args[2]) or (kwargs and kwargs.flags) or 0
return ensure_pattern_obj(args and args[1], flags)
end
},
search = {
__type = "builtin_method", __name = "search",
__call = function(args, kwargs)
local flags = (args and args[3]) or (kwargs and kwargs.flags) or 0
local p = ensure_pattern_obj(args[1], flags)
return PatternClass.__dict.search.__call({ p, args[2] }, {})
end
},
match = {
__type = "builtin_method", __name = "match",
__call = function(args, kwargs)
local flags = (args and args[3]) or (kwargs and kwargs.flags) or 0
local p = ensure_pattern_obj(args[1], flags)
return PatternClass.__dict.match.__call({ p, args[2] }, {})
end
},
fullmatch = {
__type = "builtin_method", __name = "fullmatch",
__call = function(args, kwargs)
local flags = (args and args[3]) or (kwargs and kwargs.flags) or 0
local p = ensure_pattern_obj(args[1], flags)
return PatternClass.__dict.fullmatch.__call({ p, args[2] }, {})
end
},
findall = {
__type = "builtin_method", __name = "findall",
__call = function(args, kwargs)
local flags = (args and args[3]) or (kwargs and kwargs.flags) or 0
local p = ensure_pattern_obj(args[1], flags)
return PatternClass.__dict.findall.__call({ p, args[2] }, {})
end
},
finditer = {
__type = "builtin_method", __name = "finditer",
__call = function(args, kwargs)
local flags = (args and args[3]) or (kwargs and kwargs.flags) or 0
local p = ensure_pattern_obj(args[1], flags)
return PatternClass.__dict.finditer.__call({ p, args[2] }, {})
end
},
split = {
__type = "builtin_method", __name = "split",
__call = function(args, kwargs)
local maxsplit = (args and args[3]) or (kwargs and kwargs.maxsplit) or 0
local flags = (args and args[4]) or (kwargs and kwargs.flags) or 0
local p = ensure_pattern_obj(args[1], flags)
return PatternClass.__dict.split.__call({ p, args[2], maxsplit }, {})
end
},
sub = {
__type = "builtin_method", __name = "sub",
__call = function(args, kwargs)
local count = (args and args[4]) or (kwargs and kwargs.count) or 0
local flags = (args and args[5]) or (kwargs and kwargs.flags) or 0
local p = ensure_pattern_obj(args[1], flags)
return PatternClass.__dict.sub.__call({ p, args[2], args[3], count }, {})
end
},
subn = {
__type = "builtin_method", __name = "subn",
__call = function(args, kwargs)
local count = (args and args[4]) or (kwargs and kwargs.count) or 0
local flags = (args and args[5]) or (kwargs and kwargs.flags) or 0
local p = ensure_pattern_obj(args[1], flags)
return PatternClass.__dict.subn.__call({ p, args[2], args[3], count }, {})
end
},
escape = {
__type = "builtin_method", __name = "escape",
__call = function(args)
local s, is_b = unpack_pattern_input(args[1])
local escaped = s:gsub("([%^%$%(%)%%%.%[%]%*%+%-%?%{%}%|\\#%s])", "\\%1")
return wrap_output(escaped, is_b)
end
},
purge = {
__type = "builtin_method", __name = "purge",
__call = function()
compile_cache = {}
return Runtime.builtins.None
end
}
}
re_mod_cache = require("Module:PythonScript/Library").make_namespace("re", re_dict)
return re_mod_cache
end
return Regexp
