Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-regex

Source of release 0.6.1

0.6.1 / src / regex / onig_parse.lucb

#==============================================================================================
#
#   onig_parse - The Oniguruma front end: pattern text to AST
#
#   DESCRIPTION:
#       The parser of the Oniguruma subset TextMate grammars use: literals, `.`, classes
#       ([...], ranges, negation, \d \w \s \h and negated forms, a POSIX/\p subset), anchors
#       (^ $ \b \B \A \G \z \Z), groups (capturing, (?:), named), alternation `|`,
#       quantifiers (* + ? {n} {n,} {n,m}, greedy and lazy), backreferences (numeric and
#       named), lookahead and lookbehind, case-insensitive matching, and the inline flags
#       (?i) (?x) (?s) (?m). It is lenient: an unknown property falls back to the word set so
#       an exotic grammar still loads.
#
#==============================================================================================

# mark: Build ==================================================================================

func onig_build(re: Regex*, pattern: str, ignore_case: bool) -> !:
    re.ic = ignore_case
    re.budget = 200000
    try decode_subj(pattern, &re.pat)
    let root = try onig_parse_alt(re)
    if re.pp < re.pat.used:
        error(syntax_error, "trailing characters in pattern")
    re.ncap = re.ngroups + 1
    let ncap = (usize)(2 * re.ncap)
    re.caps = try new i32[ncap] --- in memory.heap
    var i: usize = 0
    while i < ncap:
        re.caps[i] = -1
        i += 1
    try compile_node(re, root, &re.code)
    _ = try re.code.push(Inst(op = OP_MATCH))
    if re.mark_count > 0:
        re.marks = try new i32[(usize)re.mark_count] --- in memory.heap
        var m: usize = 0
        while m < (usize)re.mark_count:
            re.marks[m] = 0
            m += 1
    try compute_first(re)
    re.pat.free_all()
    re.nodes.free_all()

# mark: Parser =================================================================================

func onig_cur_cp(re: const Regex*) -> u32:
    return re.pat.data[re.pp] if re.pp < re.pat.used else 0

func new_node(re: Regex*, kind: u8) -> i32!:
    var node = Node()
    node.kind = kind
    let index = try re.nodes.push(node)
    return (i32)index

func mk_char(re: Regex*, cp: u32) -> i32!:
    let n = try new_node(re, K_CHAR)
    re.nodes.data[(usize)n].ch = cp
    return n

func mk_anchor(re: Regex*, kind: u8) -> i32!:
    let n = try new_node(re, K_ANCHOR)
    re.nodes.data[(usize)n].a = (i32)kind
    return n

func onig_parse_alt(re: Regex*) -> i32!:
    let first = try onig_parse_concat(re)
    var tail = first
    var count: i32 = 1
    while re.pp < re.pat.used and re.pat.data[re.pp] == (u32)'|':
        re.pp += 1
        let branch = try onig_parse_concat(re)
        re.nodes.data[(usize)tail].next_sibling = branch
        tail = branch
        count += 1
    if count == 1:
        return first
    let node = try new_node(re, K_ALT)
    re.nodes.data[(usize)node].first_child = first
    return node

func onig_parse_concat(re: Regex*) -> i32!:
    var head: i32 = -1
    var tail: i32 = -1
    var count: i32 = 0
    while true:
        if re.ext:
            onig_skip_ws(re)
        if re.pp >= re.pat.used:
            break
        let ch = re.pat.data[re.pp]
        if ch == (u32)'|' or ch == (u32)')':
            break
        let part = try onig_parse_repeat(re)
        if head == -1:
            head = part
            tail = part
        else:
            re.nodes.data[(usize)tail].next_sibling = part
            tail = part
        count += 1
    if count == 0:
        return try new_node(re, K_EMPTY)
    if count == 1:
        return head
    let node = try new_node(re, K_CONCAT)
    re.nodes.data[(usize)node].first_child = head
    return node

func onig_parse_repeat(re: Regex*) -> i32!:
    let atom = try onig_parse_atom(re)
    if re.ext:
        onig_skip_ws(re)
    if re.pp >= re.pat.used:
        return atom
    let ch = re.pat.data[re.pp]
    var lo: i32 = 0
    var hi: i32 = 0
    var has = false
    if ch == (u32)'*':
        lo = 0
        hi = -1
        has = true
        re.pp += 1
    elif ch == (u32)'+':
        lo = 1
        hi = -1
        has = true
        re.pp += 1
    elif ch == (u32)'?':
        lo = 0
        hi = 1
        has = true
        re.pp += 1
    elif ch == (u32)'{':
        let saved = re.pp
        re.pp += 1
        var mins: i32 = 0
        var has_min = false
        while re.pp < re.pat.used and is_digit(re.pat.data[re.pp]):
            mins = mins * 10 + (i32)(re.pat.data[re.pp] - (u32)'0')
            has_min = true
            re.pp += 1
        if not has_min:
            re.pp = saved
            return atom
        var maxv: i32 = mins
        var comma = false
        if re.pp < re.pat.used and re.pat.data[re.pp] == (u32)',':
            comma = true
            re.pp += 1
            var has_max = false
            maxv = 0
            while re.pp < re.pat.used and is_digit(re.pat.data[re.pp]):
                maxv = maxv * 10 + (i32)(re.pat.data[re.pp] - (u32)'0')
                has_max = true
                re.pp += 1
            if not has_max:
                maxv = -1
        if re.pp < re.pat.used and re.pat.data[re.pp] == (u32)'}':
            re.pp += 1
            lo = mins
            hi = maxv if comma else mins
            has = true
        else:
            re.pp = saved
            return atom
    if not has:
        return atom
    var greedy = true
    if re.pp < re.pat.used and re.pat.data[re.pp] == (u32)'?':
        greedy = false
        re.pp += 1
    elif re.pp < re.pat.used and re.pat.data[re.pp] == (u32)'+':
        re.pp += 1
    let node = try new_node(re, K_REPEAT)
    re.nodes.data[(usize)node].a = lo
    re.nodes.data[(usize)node].b = hi
    re.nodes.data[(usize)node].greedy = greedy
    re.nodes.data[(usize)node].first_child = atom
    return node

func onig_parse_atom(re: Regex*) -> i32!:
    if re.ext:
        onig_skip_ws(re)
    if re.pp >= re.pat.used:
        return try new_node(re, K_EMPTY)
    let ch = re.pat.data[re.pp]
    if ch == (u32)'(':
        return try onig_parse_group(re)
    if ch == (u32)'[':
        return try onig_parse_class(re)
    if ch == (u32)'.':
        re.pp += 1
        return try new_node(re, K_ANY)
    if ch == (u32)'^':
        re.pp += 1
        return try mk_anchor(re, AN_BOL)
    if ch == (u32)'$':
        re.pp += 1
        return try mk_anchor(re, AN_EOL)
    if ch == (u32)'\\':
        return try onig_parse_escape(re)
    re.pp += 1
    return try mk_char(re, ch)

func onig_parse_group(re: Regex*) -> i32!:
    re.pp += 1
    if re.pp < re.pat.used and re.pat.data[re.pp] == (u32)'?':
        re.pp += 1
        let c = onig_cur_cp(re)
        if c == (u32)':':
            re.pp += 1
            return try onig_grouped(re, 0)
        if c == (u32)'=':
            re.pp += 1
            return try onig_parse_look(re, true, false)
        if c == (u32)'!':
            re.pp += 1
            return try onig_parse_look(re, true, true)
        if c == (u32)'>':
            re.pp += 1
            return try onig_grouped(re, 0)
        if c == (u32)'<':
            re.pp += 1
            let d = onig_cur_cp(re)
            if d == (u32)'=':
                re.pp += 1
                return try onig_parse_look(re, false, false)
            if d == (u32)'!':
                re.pp += 1
                return try onig_parse_look(re, false, true)
            let span = try onig_read_name(re, (u32)'>')
            return try onig_parse_named(re, span)
        if c == (u32)'\'':
            re.pp += 1
            let span = try onig_read_name(re, (u32)'\'')
            return try onig_parse_named(re, span)
        return try onig_parse_flags(re)
    re.ngroups += 1
    let index = re.ngroups
    return try onig_grouped(re, index)

func onig_grouped(re: Regex*, index: i32) -> i32!:
    let inner = try onig_parse_alt(re)
    try onig_expect(re, (u32)')')
    let node = try new_node(re, K_GROUP)
    re.nodes.data[(usize)node].a = index
    re.nodes.data[(usize)node].first_child = inner
    return node

func onig_parse_named(re: Regex*, name: Span) -> i32!:
    re.ngroups += 1
    let index = re.ngroups
    _ = try re.names.push(NameEntry(start = name.start, len = name.len, group = index))
    return try onig_grouped(re, index)

func onig_parse_look(re: Regex*, ahead: bool, negate: bool) -> i32!:
    let inner = try onig_parse_alt(re)
    try onig_expect(re, (u32)')')
    let node = try new_node(re, K_LOOK)
    re.nodes.data[(usize)node].ahead = ahead
    re.nodes.data[(usize)node].negate = negate
    re.nodes.data[(usize)node].first_child = inner
    return node

func onig_parse_flags(re: Regex*) -> i32!:
    var on = true
    while re.pp < re.pat.used:
        let c = re.pat.data[re.pp]
        if c == (u32)':' or c == (u32)')':
            break
        if c == (u32)'-':
            on = false
        elif c == (u32)'i':
            if on:
                re.ic = true
        elif c == (u32)'s':
            if on:
                re.dotall = true
        elif c == (u32)'m':
            if on:
                re.multi = true
        elif c == (u32)'x':
            re.ext = on
        re.pp += 1
    if re.pp < re.pat.used and re.pat.data[re.pp] == (u32)':':
        re.pp += 1
        return try onig_grouped(re, 0)
    try onig_expect(re, (u32)')')
    return try new_node(re, K_EMPTY)

func onig_parse_escape(re: Regex*) -> i32!:
    re.pp += 1
    if re.pp >= re.pat.used:
        return try mk_char(re, (u32)'\\')
    let c = re.pat.data[re.pp]
    re.pp += 1
    if is_builtin(c):
        let ci = try new_class(re, false, builtin_bit(c))
        return try class_node(re, ci)
    if c == (u32)'b':
        return try mk_anchor(re, AN_WORDB)
    if c == (u32)'B':
        return try mk_anchor(re, AN_NWORDB)
    if c == (u32)'A':
        return try mk_anchor(re, AN_BUFS)
    if c == (u32)'G':
        re.has_g = true
        return try mk_anchor(re, AN_G)
    if c == (u32)'z' or c == (u32)'Z':
        return try mk_anchor(re, AN_BUFE)
    if is_digit(c) and c != (u32)'0':
        var ds: i32 = (i32)(c - (u32)'0')
        while re.pp < re.pat.used and is_digit(re.pat.data[re.pp]):
            ds = ds * 10 + (i32)(re.pat.data[re.pp] - (u32)'0')
            re.pp += 1
        let n = try new_node(re, K_BACKREF)
        re.nodes.data[(usize)n].a = ds
        return n
    if c == (u32)'k' and re.pp < re.pat.used and (re.pat.data[re.pp] == (u32)'<' or re.pat.data[re.pp] == (u32)'\''):
        let term = (u32)'>' if re.pat.data[re.pp] == (u32)'<' else (u32)'\''
        re.pp += 1
        let span = try onig_read_name(re, term)
        let n = try new_node(re, K_BACKREF)
        re.nodes.data[(usize)n].a = onig_find_name(re, span)
        return n
    if c == (u32)'p' or c == (u32)'P':
        let ci = try new_class(re, c == (u32)'P', 0)
        let span = try onig_read_property(re)
        try onig_add_property(re, ci, span)
        return try class_node(re, ci)
    let n = try new_node(re, K_CHAR)
    re.nodes.data[(usize)n].ch = onig_decode_escape(re, c)
    return n

func onig_parse_class(re: Regex*) -> i32!:
    re.pp += 1
    var negate = false
    if re.pp < re.pat.used and re.pat.data[re.pp] == (u32)'^':
        negate = true
        re.pp += 1
    let ci = try new_class(re, negate, 0)
    var first = true
    while re.pp < re.pat.used:
        let ch = re.pat.data[re.pp]
        if ch == (u32)']' and not first:
            break
        first = false
        if ch == (u32)'[' and re.pp + 1 < re.pat.used and re.pat.data[re.pp + 1] == (u32)':':
            try onig_parse_posix(re, ci)
            continue
        if ch == (u32)'\\':
            let lit = try onig_class_escape(re, ci)
            if lit >= 0:
                try onig_maybe_range(re, ci, (u32)lit)
            continue
        re.pp += 1
        try onig_maybe_range(re, ci, ch)
    try onig_expect(re, (u32)']')
    return try class_node(re, ci)

func onig_maybe_range(re: Regex*, ci: i32, lo: u32) -> !:
    if re.pp < re.pat.used and re.pat.data[re.pp] == (u32)'-' and re.pp + 1 < re.pat.used and re.pat.data[re.pp + 1] != (u32)']':
        re.pp += 1
        var hi: u32 = 0
        if re.pat.data[re.pp] == (u32)'\\':
            hi = try onig_class_escape_char(re)
        else:
            hi = re.pat.data[re.pp]
            re.pp += 1
        try add_range(re, ci, lo, hi)
    else:
        try add_range(re, ci, lo, lo)

func onig_class_escape(re: Regex*, ci: i32) -> i32!:
    re.pp += 1
    if re.pp >= re.pat.used:
        return (i32)(u32)'\\'
    let c = re.pat.data[re.pp]
    re.pp += 1
    if is_builtin(c):
        onig_add_builtin(re, ci, builtin_bit(c))
        return -1
    if c == (u32)'p' or c == (u32)'P':
        let span = try onig_read_property(re)
        try onig_add_property(re, ci, span)
        return -1
    return (i32)onig_decode_escape(re, c)

func onig_class_escape_char(re: Regex*) -> u32!:
    re.pp += 1
    if re.pp >= re.pat.used:
        return (u32)'\\'
    let c = re.pat.data[re.pp]
    re.pp += 1
    return onig_decode_escape(re, c)

## The literal codepoint a simple escape denotes.
func onig_decode_escape(re: Regex*, c: u32) -> u32:
    if c == (u32)'n':
        return 10
    if c == (u32)'t':
        return 9
    if c == (u32)'r':
        return 13
    if c == (u32)'f':
        return 12
    if c == (u32)'v':
        return 11
    if c == (u32)'0':
        return 0
    if c == (u32)'a':
        return 7
    if c == (u32)'e':
        return 27
    if c == (u32)'b':
        return 8
    if c == (u32)'x':
        return onig_read_hex(re, 2)
    if c == (u32)'u':
        return onig_read_hex(re, 4)
    return c

func onig_read_hex(re: Regex*, fixed: i32) -> u32:
    var value: u32 = 0
    if re.pp < re.pat.used and re.pat.data[re.pp] == (u32)'{':
        re.pp += 1
        while re.pp < re.pat.used and re.pat.data[re.pp] != (u32)'}':
            value = value * 16 + (u32)hex_digit(re.pat.data[re.pp])
            re.pp += 1
        if re.pp < re.pat.used:
            re.pp += 1
    else:
        var n: i32 = 0
        while n < fixed and re.pp < re.pat.used and is_hex(re.pat.data[re.pp]):
            value = value * 16 + (u32)hex_digit(re.pat.data[re.pp])
            re.pp += 1
            n += 1
    return value

func onig_parse_posix(re: Regex*, ci: i32) -> !:
    re.pp += 2
    let start = (i32)re.name_cps.used
    var len: i32 = 0
    while re.pp < re.pat.used and re.pat.data[re.pp] != (u32)':':
        _ = try re.name_cps.push(re.pat.data[re.pp])
        len += 1
        re.pp += 1
    if re.pp < re.pat.used:
        re.pp += 1
    if re.pp < re.pat.used:
        re.pp += 1
    try onig_add_property(re, ci, Span(start = start, len = len))

func onig_read_property(re: Regex*) -> Span!:
    let start = (i32)re.name_cps.used
    var len: i32 = 0
    if re.pp < re.pat.used and re.pat.data[re.pp] == (u32)'{':
        re.pp += 1
        while re.pp < re.pat.used and re.pat.data[re.pp] != (u32)'}':
            _ = try re.name_cps.push(re.pat.data[re.pp])
            len += 1
            re.pp += 1
        if re.pp < re.pat.used:
            re.pp += 1
    elif re.pp < re.pat.used:
        _ = try re.name_cps.push(re.pat.data[re.pp])
        len += 1
        re.pp += 1
    return Span(start = start, len = len)

## Map a POSIX or Unicode property name to an ASCII approximation. Never fails: an unknown
## name falls back to the word set, so an exotic grammar still loads.
func onig_add_property(re: Regex*, ci: i32, name: Span) -> !:
    if onig_name_is(re, name, "digit") or onig_name_is(re, name, "Digit") or onig_name_is(re, name, "Nd") or onig_name_is(re, name, "Number"):
        onig_add_builtin(re, ci, B_d)
    elif onig_name_is(re, name, "space") or onig_name_is(re, name, "Space") or onig_name_is(re, name, "White_Space"):
        onig_add_builtin(re, ci, B_s)
    elif onig_name_is(re, name, "xdigit") or onig_name_is(re, name, "XDigit"):
        onig_add_builtin(re, ci, B_h)
    elif onig_name_is(re, name, "upper") or onig_name_is(re, name, "Upper") or onig_name_is(re, name, "Lu"):
        try add_range(re, ci, (u32)'A', (u32)'Z')
    elif onig_name_is(re, name, "lower") or onig_name_is(re, name, "Lower") or onig_name_is(re, name, "Ll"):
        try add_range(re, ci, (u32)'a', (u32)'z')
    elif onig_name_is(re, name, "alpha") or onig_name_is(re, name, "Alpha") or onig_name_is(re, name, "Alphabetic") or onig_name_is(re, name, "L") or onig_name_is(re, name, "Letter"):
        try add_range(re, ci, (u32)'A', (u32)'Z')
        try add_range(re, ci, (u32)'a', (u32)'z')
    elif onig_name_is(re, name, "alnum") or onig_name_is(re, name, "Alnum"):
        onig_add_builtin(re, ci, B_d)
        try add_range(re, ci, (u32)'A', (u32)'Z')
        try add_range(re, ci, (u32)'a', (u32)'z')
    elif onig_name_is(re, name, "punct") or onig_name_is(re, name, "Punct"):
        try add_range(re, ci, (u32)'!', (u32)'/')
        try add_range(re, ci, (u32)':', (u32)'@')
        try add_range(re, ci, (u32)'[', (u32)'`')
        try add_range(re, ci, (u32)'{', (u32)'~')
    else:
        onig_add_builtin(re, ci, B_w)

func new_class(re: Regex*, negate: bool, builtins: u32) -> i32!:
    var cc = CharClass()
    cc.negate = negate
    cc.builtins = builtins
    cc.range_start = re.ranges.used
    cc.range_count = 0
    let index = try re.classes.push(cc)
    return (i32)index

func onig_add_builtin(re: Regex*, ci: i32, bit: u32):
    re.classes.data[(usize)ci].builtins = re.classes.data[(usize)ci].builtins | bit

func add_range(re: Regex*, ci: i32, lo: u32, hi: u32) -> !:
    _ = try re.ranges.push(lo)
    _ = try re.ranges.push(hi)
    re.classes.data[(usize)ci].range_count += 1

func class_node(re: Regex*, ci: i32) -> i32!:
    let n = try new_node(re, K_CLASS)
    re.nodes.data[(usize)n].a = ci
    return n

func onig_read_name(re: Regex*, term: u32) -> Span!:
    let start = (i32)re.name_cps.used
    var len: i32 = 0
    while re.pp < re.pat.used and re.pat.data[re.pp] != term:
        _ = try re.name_cps.push(re.pat.data[re.pp])
        len += 1
        re.pp += 1
    try onig_expect(re, term)
    return Span(start = start, len = len)

func onig_find_name(re: const Regex*, span: Span) -> i32:
    var i: usize = 0
    while i < re.names.used:
        let entry = re.names.data[i]
        if entry.len == span.len and onig_span_eq(re, entry.start, span):
            return entry.group
        i += 1
    return 0

func onig_span_eq(re: const Regex*, a_start: i32, b: Span) -> bool:
    var i: i32 = 0
    while i < b.len:
        if re.name_cps.data[(usize)(a_start + i)] != re.name_cps.data[(usize)(b.start + i)]:
            return false
        i += 1
    return true

func onig_name_is(re: const Regex*, span: Span, lit: str) -> bool:
    let bytes = lit.bytes
    if (usize)span.len != bytes.length:
        return false
    var i: usize = 0
    while i < (usize)span.len:
        if re.name_cps.data[(usize)span.start + i] != (u32)bytes[i]:
            return false
        i += 1
    return true

func onig_expect(re: Regex*, cp: u32) -> !:
    if re.pp < re.pat.used and re.pat.data[re.pp] == cp:
        re.pp += 1
        return
    error(syntax_error, "missing a delimiter in pattern")

func onig_skip_ws(re: Regex*):
    while re.pp < re.pat.used:
        let c = re.pat.data[re.pp]
        if c == (u32)' ' or c == (u32)'\t' or c == (u32)'\n' or c == (u32)'\r':
            re.pp += 1
        elif c == (u32)'#':
            while re.pp < re.pat.used and re.pat.data[re.pp] != (u32)'\n':
                re.pp += 1
        else:
            break