dymokomi/luce-regex
Source of release 0.6.1
0.6.1 / src / regex / es_parse.lucb
#==============================================================================================
#
# es_parse - The ECMAScript front end: pattern bytes to AST
#
# DESCRIPTION:
# Port of libregexp.c's re_parse_term, re_parse_alternative and re_parse_disjunction
# (lines 1845-2440). Where the C parser emits bytecode as it goes, this one builds the
# engine's AST; the direction of matching (forward, or backward inside a lookbehind),
# the loop layout of a quantifier and the capture resets are decided when the AST is
# compiled (es_compile.lucb). The syntax accepted, the errors and their messages are
# QuickJS's, including the Annex B extensions allowed without the u or v flag.
#
#==============================================================================================
# mark: Nodes ==================================================================================
func es_flags(ps: const EsParse*) -> u8:
var f: u8 = 0
if ps.ignore_case:
f |= F_IC
if ps.dotall:
f |= F_DOTALL
if ps.multi_line:
f |= F_MULTI
return f
func es_node(ps: EsParse*, kind: u8) -> i32!:
let n = try new_node(ps.re, kind)
ps.re.nodes.data[(usize)n].flags = es_flags(ps)
return n
func es_parent(ps: EsParse*, kind: u8, child: i32) -> i32!:
let n = try es_node(ps, kind)
ps.re.nodes.data[(usize)n].first_child = child
return n
# A backreference to the groups `list`.
func es_backref(ps: EsParse*, list: const Vec[i32]*) -> i32!:
let re = ps.re
let n = try es_node(ps, K_BACKREF)
re.nodes.data[(usize)n].x = (i32)re.ref_lists.used
re.nodes.data[(usize)n].y = (i32)list.used
var i: usize = 0
while i < list.used:
_ = try re.ref_lists.push(list.data[i])
i += 1
return n
# A class atom that is a set (C's CLASS_RANGE_BASE answer), as a node.
func es_set_atom(ps: EsParse*, s: StrSet*, c: i32) -> i32!:
defer set_free(s)
let n = try set_to_node(ps, s)
# the common 'space' tests: C emits REOP_space / REOP_not_space, which ignore the i flag
if c == CLASS_RANGE_BASE + (i32)CLASS_s or c == CLASS_RANGE_BASE + (i32)CLASS_S:
ps.re.nodes.data[(usize)n].flags = 0
return n
func es_char_atom(ps: EsParse*, c0: u32) -> i32!:
var c = c0
if ps.ignore_case:
c = (u32)unicode.lre_canonicalize(c, ps.is_unicode)
let n = try es_node(ps, K_CHAR)
ps.re.nodes.data[(usize)n].ch = c
return n
# mark: Disjunctions ===========================================================================
func es_parse_disjunction(ps: EsParse*) -> i32!:
try es_check_stack(ps)
let first = try es_parse_alternative(ps)
if cur(ps) != '|':
return first
var head = first
var tail = first
while cur(ps) == '|':
ps.p += 1
ps.group_name_scope +%= 1
let alt = try es_parse_alternative(ps)
try link_sibling(ps.re, &head, &tail, alt)
return try es_parent(ps, K_ALT, head)
func es_parse_alternative(ps: EsParse*) -> i32!:
var head: i32 = -1
var tail: i32 = -1
while true:
if ps.p >= ps.src.length:
break
let c = cur(ps)
if c == '|' or c == ')':
break
let term = try es_parse_term(ps)
try link_sibling(ps.re, &head, &tail, term)
if head < 0:
return try es_node(ps, K_EMPTY)
if head == tail:
return head
return try es_parent(ps, K_CONCAT, head)
# mark: Terms ==================================================================================
func es_parse_term(ps: EsParse*) -> i32!:
let re = ps.re
var atom: i32 = -1 # a quantifiable atom (C's last_atom_start >= 0)
var last_capture_count: i32 = 0
var class_atom = false # C's goto parse_class_atom
var char_value: i32 = -1 # C's goto normal_char with c
let c = cur(ps)
if c == '^':
ps.p += 1
return try mk_anchor(re, AN_ES_BOL_M if ps.multi_line else AN_ES_BOL)
elif c == '$':
ps.p += 1
return try mk_anchor(re, AN_ES_EOL_M if ps.multi_line else AN_ES_EOL)
elif c == '.':
ps.p += 1
last_capture_count = ps.capture_count
atom = try es_node(ps, K_ANY)
elif c == '{':
if ps.is_unicode:
return try es_fail(ps, "syntax error")
elif not is_ascii_digit(ch_at(ps, ps.p + 1)):
# Annex B: we accept '{' not followed by digits as a normal atom
class_atom = true
else:
var p1 = ps.p + 1
# Annex B: error if it is like a repetition count
_ = parse_digits(ps, &p1, true)
if ch_at(ps, p1) == ',':
p1 += 1
if is_ascii_digit(ch_at(ps, p1)):
_ = parse_digits(ps, &p1, true)
if ch_at(ps, p1) != '}':
class_atom = true
else:
return try es_fail(ps, "nothing to repeat")
elif c == '*' or c == '+' or c == '?':
return try es_fail(ps, "nothing to repeat")
elif c == '(':
let quantifiable = try es_parse_paren(ps, &last_capture_count)
if quantifiable.1:
atom = quantifiable.0
else:
return quantifiable.0
elif c == '\\':
let c1 = ch_at(ps, ps.p + 1)
if c1 == 'b' or c1 == 'B':
let i_variant = ps.ignore_case and ps.is_unicode
var kind = AN_ES_WB_I if i_variant else AN_ES_WB
if c1 == 'B':
kind = AN_ES_NWB_I if i_variant else AN_ES_NWB
ps.p += 2
return try mk_anchor(re, kind)
elif c1 == 'k':
let backref = try es_parse_named_backref(ps)
if backref >= 0:
last_capture_count = ps.capture_count
atom = backref
else:
class_atom = true
elif c1 == '0':
ps.p += 2
var v: i32 = 0
if ps.is_unicode:
if is_ascii_digit(cur(ps)):
return try es_fail(ps, "invalid decimal escape in regular expression")
else:
# Annex B.1.4: accept legacy octal
if cur(ps) >= '0' and cur(ps) <= '7':
v = (i32)(cur(ps) - '0')
ps.p += 1
if cur(ps) >= '0' and cur(ps) <= '7':
v = (v << 3) + (i32)(cur(ps) - '0')
ps.p += 1
char_value = v
elif c1 >= '1' and c1 <= '9':
ps.p += 1
let q = ps.p
var pp = ps.p
var v = parse_digits(ps, &pp, false)
ps.p = pp
if v < 0 or (v >= ps.capture_count and v >= try count_captures(ps)):
if ps.is_unicode:
return try es_fail(ps, "back reference out of range in regular expression")
# Annex B.1.4: accept legacy octal
ps.p = q
if cur(ps) <= '7':
v = 0
if cur(ps) <= '3':
v = (i32)(cur(ps) - '0')
ps.p += 1
if cur(ps) >= '0' and cur(ps) <= '7':
v = (v << 3) + (i32)(cur(ps) - '0')
ps.p += 1
if cur(ps) >= '0' and cur(ps) <= '7':
v = (v << 3) + (i32)(cur(ps) - '0')
ps.p += 1
else:
v = (i32)cur(ps)
ps.p += 1
char_value = v
else:
last_capture_count = ps.capture_count
var list = Vec[i32](heap = re.heap)
defer list.free_all()
_ = try list.push(v)
atom = try es_backref(ps, &list)
else:
class_atom = true
elif c == '[':
last_capture_count = ps.capture_count
var s: StrSet = ---
try parse_nested_class(ps, &s)
atom = try es_set_atom(ps, &s, CLASS_RANGE_BASE)
elif c == ']' or c == '}':
if ps.is_unicode:
return try es_fail(ps, "syntax error")
class_atom = true
else:
class_atom = true
if class_atom:
var s: StrSet = ---
let v = try get_class_atom(ps, &s, false)
last_capture_count = ps.capture_count
if v >= CLASS_RANGE_BASE:
atom = try es_set_atom(ps, &s, v)
else:
char_value = v
if char_value >= 0:
last_capture_count = ps.capture_count
atom = try es_char_atom(ps, (u32)char_value)
return try es_parse_quantifier(ps, atom, last_capture_count)
# A parenthesised term at '(': the node and whether a quantifier may follow it.
func es_parse_paren(ps: EsParse*, last_capture_count: i32*) -> (i32, bool)!:
let re = ps.re
if ch_at(ps, ps.p + 1) != '?':
ps.p += 1
# capture without group name
_ = try re.group_names.push(0)
_ = try re.group_names.push(0)
return (try es_parse_capture(ps, last_capture_count), true)
let c2 = ch_at(ps, ps.p + 2)
if c2 == ':':
ps.p += 3
*last_capture_count = ps.capture_count
let inner = try es_parse_disjunction(ps)
try es_expect(ps, ')')
return (inner, true)
if c2 == 'i' or c2 == 'm' or c2 == 's' or c2 == '-':
ps.p += 2
var remove_mask: i32 = 0
let add_mask = try parse_modifiers(ps)
if cur(ps) == '-':
ps.p += 1
remove_mask = try parse_modifiers(ps)
if (add_mask == 0 and remove_mask == 0) or (add_mask & remove_mask) != 0:
_ = try es_fail(ps, "invalid modifiers")
try es_expect(ps, ':')
let saved_ignore_case = ps.ignore_case
let saved_multi_line = ps.multi_line
let saved_dotall = ps.dotall
ps.ignore_case = update_modifier(ps.ignore_case, add_mask, remove_mask, es_ignore_case)
ps.multi_line = update_modifier(ps.multi_line, add_mask, remove_mask, es_multiline)
ps.dotall = update_modifier(ps.dotall, add_mask, remove_mask, es_dotall)
*last_capture_count = ps.capture_count
let inner = try es_parse_disjunction(ps)
try es_expect(ps, ')')
ps.ignore_case = saved_ignore_case
ps.multi_line = saved_multi_line
ps.dotall = saved_dotall
return (inner, true)
var is_neg = false
var is_backward = false
if c2 == '=' or c2 == '!':
is_neg = c2 == '!'
ps.p += 3
elif c2 == '<' and (ch_at(ps, ps.p + 3) == '=' or ch_at(ps, ps.p + 3) == '!'):
is_neg = ch_at(ps, ps.p + 3) == '!'
is_backward = true
ps.p += 4
elif c2 == '<':
ps.p += 3
var p = ps.p
if not parse_group_name(ps, ps.name, &ps.name_len, &p):
_ = try es_fail(ps, "invalid group name")
ps.p = p
let name = ps.name[0..<ps.name_len]
# poor's man method to test duplicate group names.
# XXX: this method does not catch all the errors
if is_duplicate_group_name(ps, name, ps.group_name_scope):
_ = try es_fail(ps, "duplicate group name")
# group name with a trailing zero
for b in name:
_ = try re.group_names.push(b)
_ = try re.group_names.push(0)
_ = try re.group_names.push(ps.group_name_scope)
ps.has_named_captures = 1
return (try es_parse_capture(ps, last_capture_count), true)
else:
_ = try es_fail(ps, "invalid group")
# a lookaround. Annex B allows a lookahead to be used as an atom for the quantifiers.
let quantifiable = not ps.is_unicode and not is_backward
if quantifiable:
*last_capture_count = ps.capture_count
let inner = try es_parse_disjunction(ps)
try es_expect(ps, ')')
let n = try es_parent(ps, K_LOOK, inner)
re.nodes.data[(usize)n].ahead = not is_backward
re.nodes.data[(usize)n].negate = is_neg
return (n, quantifiable)
# The body of a capture group, with `ps.p` after its opening.
func es_parse_capture(ps: EsParse*, last_capture_count: i32*) -> i32!:
if ps.capture_count >= CAPTURE_COUNT_MAX:
return try es_fail(ps, "too many captures")
*last_capture_count = ps.capture_count
let capture_index = ps.capture_count
ps.capture_count += 1
let inner = try es_parse_disjunction(ps)
try es_expect(ps, ')')
let n = try es_parent(ps, K_GROUP, inner)
ps.re.nodes.data[(usize)n].a = capture_index
return n
# \k<name> at `ps.p`: the backreference node, or -1 when Annex B makes it the atom 'k'.
func es_parse_named_backref(ps: EsParse*) -> i32!:
var p1 = ps.p
if ch_at(ps, p1 + 2) != '<':
# annex B: we tolerate invalid group names in non unicode mode if there is no named
# capture definition
if ps.is_unicode or try has_named_captures(ps):
_ = try es_fail(ps, "expecting group name")
return -1
p1 += 3
if not parse_group_name(ps, ps.name, &ps.name_len, &p1):
if ps.is_unicode or try has_named_captures(ps):
_ = try es_fail(ps, "invalid group name")
return -1
let name = ps.name[0..<ps.name_len]
var list = Vec[i32](heap = ps.re.heap)
defer list.free_all()
var n = try find_group_name(ps, name, &list)
if n == 0:
# no capture name parsed before, try to look after (inefficient, but hopefully not
# common)
var dummy: i32 = 0
n = try parse_captures(ps, &dummy, name, &list)
if n == 0:
if ps.is_unicode or try has_named_captures(ps):
_ = try es_fail(ps, "group name not defined")
return -1
ps.p = p1
# a backreference to all the captures matching the group name
return try es_backref(ps, &list)
# mark: Quantifiers ============================================================================
# The quantifier after `atom`, if any (none may follow when `atom` is -1).
func es_parse_quantifier(ps: EsParse*, atom: i32, last_capture_count: i32) -> i32!:
if atom < 0:
trap("es_parse_quantifier: no atom")
var quant_min: i32 = 0
var quant_max: i32 = 0
let c = cur(ps)
if c == '*':
ps.p += 1
quant_min = 0
quant_max = INT32_MAX
elif c == '+':
ps.p += 1
quant_min = 1
quant_max = INT32_MAX
elif c == '?':
ps.p += 1
quant_min = 0
quant_max = 1
elif c == '{':
let p1 = ps.p
# As an extension (see ES6 annex B), we accept '{' not followed by digits as a
# normal atom
if not is_ascii_digit(ch_at(ps, ps.p + 1)):
if ps.is_unicode:
return try es_fail(ps, "invalid repetition count")
return atom
ps.p += 1
var pp = ps.p
quant_min = parse_digits(ps, &pp, true)
ps.p = pp
quant_max = quant_min
if cur(ps) == ',':
ps.p += 1
if is_ascii_digit(cur(ps)):
pp = ps.p
quant_max = parse_digits(ps, &pp, true)
ps.p = pp
if quant_max < quant_min:
return try es_fail(ps, "invalid repetition count")
else:
quant_max = INT32_MAX # infinity
if cur(ps) != '}' and not ps.is_unicode:
# Annex B: normal atom if invalid '{' syntax
ps.p = p1
return atom
try es_expect(ps, '}')
else:
return atom
var greedy = true
if cur(ps) == '?':
ps.p += 1
greedy = false
let re = ps.re
let n = try es_parent(ps, K_REPEAT, atom)
re.nodes.data[(usize)n].a = quant_min
re.nodes.data[(usize)n].b = quant_max
re.nodes.data[(usize)n].greedy = greedy
re.nodes.data[(usize)n].x = last_capture_count
re.nodes.data[(usize)n].y = ps.capture_count
return n