How to improve: use types to enforce stack discipline

help
1

I'm trying to encode stack discipline using types, my previous version just uses runtime checks, and panics if slot usage is invalid. by far, I managed to utilize a scoped API with callbacks:

let stack_base = thread.base();
stack_base.push(4, |frame| {
    // bind variables to individual slots, slots borrows frame
    let [a, b, c, d] = frame.slots() else { unreachable!() };
    if some_condition(a, b) {
        frame.push(1, |frame| {
            // technically we don't need to shadow the outer frame
            // but we already bound individual slots, we don't need the outer frame
            let e = frame.top_slot();
            do_some_work(c, d, e);
        });
    }
    for i in 0..100 {
        frame.push(2, |frame| {
            let &[k, v] = frame.slots() else { unreachable!() };
            do_some_more_work(i, k, v, a, b, c);
        });
    }
});

of course there's plenty room for improvements, for example I can use const generics to eliminate more runtime checks, but over all, I think the stack based VM runtime fits nicely with a scoped API.

I just want to explore some other possibilities: can we somehow make use of lifetimes to design an alternative API style? here's what I got so far:

trait StackDiscipline {
// ...
}
struct Empty;
impl StackDiscipline for Empty {}
struct Frame<'a, Below> {
    below: &'a Below,
    // ...
}
impl<'a, Below: StackDiscipline> StackDiscipline for Frame<'a, Below> {}
//-----------------------------------------------------------------------------
let stack_base = thread.base(); // stack_base: `Empty`
let frame = stack_base.push(4); // frame: `Frame<'1, Empty>`
let [a, b, c, d] = frame.slots() else { unreachable!() };
for i in 0..100 {
    // the inner frame borrows the outer frame
    let frame = frame.push(2); // frame: `Frame<'2, Frame<'1, Empty>>`
    let &[k, v] = frame.slots() else { unreachable!() };
    do_some_more_work(i, k, v, a, b, c);
}

I think (I might be wrong) the two styles of API should be equivalent and can be transformed mechanically. what the current API cannot guarantee (at compile time) however, is to prevent the user from accidentally "forking" the stack.

because user code needs to access to slots both from the inner most frame as well as from outer frames, so an inner frame can only hold shared reference to the outer frame. if, on the other hand, the inner frame borrows the outer frame exclusively, user code will not be able to access the outer frame slots anymore.

so my question is, without runtime checks, is possible to enforce a linear sequence of stack frames without invalidating slots of outer frames under the current lifetime rules?

2

What exactly do you mean by "encode stack discipline" or "enforce stack discipline"? Your high-level goal is not clear from the provided example.

3

sorry, my bad. here's some context: I'm creating a wrapper for a C library. it's a patched Lua interpreter from an earlier version (Lua 5.1), and it's API is mostly unchanged or follows closely the original Lua C API.

for those who is not familiar with Lua, the C API doesn't give you direct access to the underlying value, instead it transfers data using a stack. for example, to get the value of a global variable and convert it to an float point (double in C, f64 in rust), you should make these API calls:

// this function pushes the value on top of the stack
lua_getglobal(L, "variable_name");
// this function check the type of value at given stack index
// and return a f64 if it's convertible to float point number
// negative index counts from top of stack downwards
double number = lua_tonumber(L, -1);
// depending on context, we might need to manually balance the stack
lua_pop(L, 1);

if the variable is a string instead of number, we must be extra careful: the stack is one of the root references for the garbage collector. if we popped the value from the stack and called other APIs, GC might be triggered and we have a potential dangling pointer! in the following example though, it's a global variable so it's unlikely to happen.

lua_getglobal(L, "message");
char const *message = lua_tostring(L, -1);
lua_pop(L, 1);
//... many APIs would allocate and thus trigger GC
printf("the message is %s\n", message);

the stack is also used to pass arguments and return values when calling functions

lua_getglobal(L, "some_function_name"); // push the function we we going to call
lua_pushstring(L, "a string argument"); // push first argument
lua_pushnumber(L, 3.14); // push second argument
lua_call(L, 2, LUA_MULTRET); // lua function can return multiple values
int num_result = lua.gettop(L); // the number of return values

the API is simple and flexible, but not the most ergonomic one to use. my goal is to maintain the balance of stack automatically, and most importantly, avoid dangling pointers.

PS: I'm aware mlua (and similar crates), which is a safe rust wrapper for Lua. they did it differently and completely abstract away the stack. I don't plan to go that way, and I'm doing ok with the current scoped API. I just want to explore more possibilities.