Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-js

Source of release 0.6.1

0.6.1 / src / engine / stack_size.lucb

#==============================================================================================
#
#   stack_size - The maximum interpreter stack size a function's bytecode needs
#
#   DESCRIPTION:
#       Port of quickjs.c "compute the maximum stack size needed by the function"
#       (lines 35699-35952): StackSizeState, ss_check and compute_stack_size. The final
#       bytecode (short opcodes included, no temporary opcodes) is explored breadth
#       first from pc 0; every reachable pc records its stack level and the pc of the
#       innermost catch, and must be reached with the same ones on every path.
#
#       The two per-pc tables are spans over their js_malloc'ed blocks, so a bad pc
#       traps instead of reading outside them; ss_check tests the bound first, as C.
#
#==============================================================================================

# mark: State ===================================================================================

## The state of compute_stack_size (StackSizeState).
struct StackSizeState:
    var bc_len: i32
    var stack_len_max: i32
    ## The stack level at each pc, 0xffff if not explored yet.
    var stack_level_tab: u16[]
    ## The pc of the innermost catch (or for_of_start) at each pc, -1 if none.
    var catch_pos_tab: i32[]
    ## The pcs left to explore.
    var pc_stack: i32*?
    var pc_stack_len: i32
    var pc_stack_size: i32

# Release the pc stack (the one table compute_stack_size does not free by itself).
func ss_free_pc_stack(ctx: Context*, s: StackSizeState*):
    if let pc_stack = s.pc_stack:
        js_free(ctx, pc_stack)
    s.pc_stack = none

# mark: Exploring ===============================================================================

# 'op' is only used for error indication
# Reach `pos` with `stack_len` values on the stack and the catch `catch_pos`: record it
# and queue it the first time, check it is consistent the next ones.
func ss_check(ctx: Context*, s: StackSizeState*, pos: i32, op: i32, stack_len: i32, catch_pos: i32) -> !:
    if (u32)pos >= (u32)s.bc_len:
        try js_throw_internal_error(ctx, f"bytecode buffer overflow (op={op}, pc={pos})")
    if stack_len > s.stack_len_max:
        s.stack_len_max = stack_len
        if s.stack_len_max > js_stack_size_max:
            try js_throw_internal_error(ctx, f"stack overflow (op={op}, pc={pos})")
    let level = s.stack_level_tab[(usize)pos]
    if level != 0xffff:
        # already explored: check that the stack size is consistent
        if (i32)level != stack_len:
            try js_throw_internal_error(ctx, f"inconsistent stack size: {level} {stack_len} (pc={pos})")
        elif s.catch_pos_tab[(usize)pos] != catch_pos:
            let previous = s.catch_pos_tab[(usize)pos]
            try js_throw_internal_error(ctx, f"inconsistent catch position: {previous} {catch_pos} (pc={pos})")
        else:
            return

    # mark as explored and store the stack size
    s.stack_level_tab[(usize)pos] = (u16)stack_len
    s.catch_pos_tab[(usize)pos] = catch_pos

    # queue the new PC to explore
    try js_resize_array(ctx, (void*?*)&s.pc_stack, (i32)memory.size_of(i32), &s.pc_stack_size,
                        s.pc_stack_len + 1)
    let pc_stack = s.pc_stack else trap("ss_check: no pc stack")
    pc_stack[(isize)s.pc_stack_len] = pos
    s.pc_stack_len += 1

# The catch position after an opcode that may remove the catch offset entry when the
# stack level before it is `catch_level` (the check_catch label of compute_stack_size).
func ss_check_catch(s: StackSizeState*, bc_buf: const u8*, catch_pos: i32, catch_level: i32) -> i32:
    # Note: for for_of_start/for_await_of_start we consider
    # the catch offset is on the first stack entry instead of
    # the thirst
    if catch_pos >= 0:
        var level = (i32)s.stack_level_tab[(usize)catch_pos]
        if bc_buf[(isize)catch_pos] != (u8)Op.catch_:
            level += 1  # for_of_start, for_wait_of_start
        # catch_level = stack_level before op_catch is executed ?
        if catch_level == level:
            return s.catch_pos_tab[(usize)catch_pos]
    return catch_pos

# The signed 32-bit jump offset stored at `p`.
func ss_get_diff32(p: const u8*) -> i32:
    return (i32)cutils.get_u32(p)

# mark: compute_stack_size ======================================================================

## The maximum stack size the final bytecode of `fd` needs; throws an InternalError when
## the bytecode is inconsistent.
func compute_stack_size(ctx: Context*, fd: FunctionDef*) -> i32!:
    # bc_len > 0
    let bc_buf: const u8* = fd.byte_code.buf else trap("compute_stack_size: empty bytecode")
    let bc_len = (i32)fd.byte_code.size
    let level_tab = (u16*)try js_malloc(ctx, memory.size_of(u16) * (usize)bc_len)
    defer js_free(ctx, level_tab)
    for i in 0..<(usize)bc_len:
        level_tab[i] = 0xffff
    let catch_tab = (i32*)try js_malloc(ctx, memory.size_of(i32) * (usize)bc_len)
    defer js_free(ctx, catch_tab)

    var s = StackSizeState(bc_len = bc_len, stack_len_max = 0,
                           stack_level_tab = u16[](level_tab, (usize)bc_len),
                           catch_pos_tab = i32[](catch_tab, (usize)bc_len),
                           pc_stack = none, pc_stack_len = 0, pc_stack_size = 0)
    defer ss_free_pc_stack(ctx, &s)

    # breadth-first graph exploration
    try ss_check(ctx, &s, 0, (i32)Op.invalid, 0, -1)

    while s.pc_stack_len > 0:
        let pc_stack = s.pc_stack else trap("compute_stack_size: no pc stack")
        s.pc_stack_len -= 1
        let pos = pc_stack[(isize)s.pc_stack_len]
        var stack_len = (i32)s.stack_level_tab[(usize)pos]
        var catch_pos = s.catch_pos_tab[(usize)pos]
        let op = (i32)bc_buf[(isize)pos]
        if op == 0 or (u32)op >= op_count:
            try js_throw_internal_error(ctx, f"invalid opcode (op={op}, pc={pos})")
        let oi = op_info((u8)op, false)
        var pos_next = pos + (i32)oi.size
        if pos_next > s.bc_len:
            try js_throw_internal_error(ctx, f"bytecode buffer overflow (op={op}, pc={pos})")
        var n_pop = (i32)oi.n_pop
        # call pops a variable number of arguments
        if oi.fmt == OpFormat.npop or oi.fmt == OpFormat.npop_u16:
            n_pop += (i32)cutils.get_u16(bc_buf + (isize)(pos + 1))
        elif oi.fmt == OpFormat.npopx:
            n_pop += op - (i32)Op.call0

        if stack_len < n_pop:
            try js_throw_internal_error(ctx, f"stack underflow (op={op}, pc={pos})")
        stack_len += (i32)oi.n_push - n_pop
        if stack_len > s.stack_len_max:
            s.stack_len_max = stack_len
            if s.stack_len_max > js_stack_size_max:
                try js_throw_internal_error(ctx, f"stack overflow (op={op}, pc={pos})")
        match (Op)(u8)op:
            .tail_call, .tail_call_method, .return_, .return_undef, .return_async:
                # done_insn: no successor
                continue
            .throw, .throw_error, .ret:
                continue
            .goto_:
                let diff = ss_get_diff32(bc_buf + (isize)(pos + 1))
                pos_next = pos + 1 + diff
            .goto16:
                let diff = (i32)(i16)cutils.get_u16(bc_buf + (isize)(pos + 1))
                pos_next = pos + 1 + diff
            .goto8:
                let diff = (i32)(i8)bc_buf[(isize)(pos + 1)]
                pos_next = pos + 1 + diff
            .if_true8, .if_false8:
                let diff = (i32)(i8)bc_buf[(isize)(pos + 1)]
                try ss_check(ctx, &s, pos + 1 + diff, op, stack_len, catch_pos)
            .if_true, .if_false:
                let diff = ss_get_diff32(bc_buf + (isize)(pos + 1))
                try ss_check(ctx, &s, pos + 1 + diff, op, stack_len, catch_pos)
            .gosub:
                let diff = ss_get_diff32(bc_buf + (isize)(pos + 1))
                try ss_check(ctx, &s, pos + 1 + diff, op, stack_len + 1, catch_pos)
            .with_get_var, .with_delete_var:
                let diff = ss_get_diff32(bc_buf + (isize)(pos + 5))
                try ss_check(ctx, &s, pos + 5 + diff, op, stack_len + 1, catch_pos)
            .with_make_ref, .with_get_ref:
                let diff = ss_get_diff32(bc_buf + (isize)(pos + 5))
                try ss_check(ctx, &s, pos + 5 + diff, op, stack_len + 2, catch_pos)
            .with_put_var:
                let diff = ss_get_diff32(bc_buf + (isize)(pos + 5))
                try ss_check(ctx, &s, pos + 5 + diff, op, stack_len - 1, catch_pos)
            .catch_:
                let diff = ss_get_diff32(bc_buf + (isize)(pos + 1))
                try ss_check(ctx, &s, pos + 1 + diff, op, stack_len, catch_pos)
                catch_pos = pos
            .for_of_start, .for_await_of_start:
                catch_pos = pos
            # we assume the catch offset entry is only removed with
            # some op codes
            .drop:
                catch_pos = ss_check_catch(&s, bc_buf, catch_pos, stack_len)
            .nip, .nip1:
                catch_pos = ss_check_catch(&s, bc_buf, catch_pos, stack_len - 1)
            .iterator_close:
                catch_pos = ss_check_catch(&s, bc_buf, catch_pos, stack_len + 2)
            .nip_catch:
                if catch_pos < 0:
                    try js_throw_internal_error(ctx, f"nip_catch: no catch op (pc={pos})")
                stack_len = (i32)s.stack_level_tab[(usize)catch_pos]
                if bc_buf[(isize)catch_pos] != (u8)Op.catch_:
                    stack_len += 1  # for_of_start, for_wait_of_start
                stack_len += 1  # no stack overflow is possible by construction
                catch_pos = s.catch_pos_tab[(usize)catch_pos]
            _:
                _ = 0
        try ss_check(ctx, &s, pos_next, op, stack_len, catch_pos)
    return s.stack_len_max