Yet another borrow checking error

hello again,
so, today, i was making a tiny FP language interpreter using rust. and I used a greedy reduction algorithm (recursive). but it quickly overflowed the stack on moderate sized input (for FP exprs). so i tried to use a manually managed stack. but rust borrow checker won't let me :sob:

pub fn apply(defs: &[Def], e: &mut Expr) -> bool {
    let mut stack = vec![(true, e)];
    let mut changed = false;

    while let Some((new, e)) = stack.pop() {
        if !new {
            let mut ch = false;
            while defs.iter().any(|def| def.apply(e)) {
                ch = true;
            }
            changed |= ch;
            if !ch {
                continue;
            }
            stack.push((true, e));
        } else {
            stack.push((false, e));
        }
        match &mut *e {
            Expr::Func { args, .. } => {
                for a in args.iter_mut().map(Rc::make_mut) {
                    stack.push((true, a));
                }
            }
            Expr::Var { .. } => {}
        }
    }

    changed
}

relevant structs:

#[derive(Clone, Debug)]
pub struct Def {
    pub loc: Loc,
    pub(crate) pat: Expr,
    pub(crate) rep: Expr,
}

#[derive(Clone, Debug)]
pub enum Expr {
    Var {
        name: String,
        loc: Loc,
    },
    Func {
        loc: Loc,
        name: String,
        args: Vec<Rc<Expr>>,
    },
}

btw, I also tried Mutex and Refcell to solve them. Didn't work.

Before reading the code to understand and address the borrow checking problems I wanted to note: using stacker can also be a useful tool to avoid stack overflows.

1 Like

Since the example code is incomplete, would you mind sharing the exact error message, too? That makes reading the code / spotting the borrow-checking issue(s) easier. Also, feel free to share the recursive alternative implementation that this code is trying to improve upon, too, for comparison – the recursive implementation is probably easier to understand, and then another tool to make your code easier to read.

thanks very much! but I don't want to grow the stack indefinitely. I'll however note it as list of possible performance improvements (which I am not currently focusing).

here is the error message:

error[E0499]: cannot borrow `*e` as mutable more than once at a time
  --> src\lib.rs:47:15
   |
33 |     while let Some((new, e)) = stack.pop() {
   |                                ----------- first borrow later used here
...
43 |             stack.push((true, e));
   |                               - first mutable borrow occurs here
...
47 |         match &mut *e {
   |               ^^^^^^^ second mutable borrow occurs here

No, this is not about performance improvements. Indeed using stacker would probably have some overhead over a straightforward recursive implementation without stacker. The point is that it should be minimal effort to integrate stacker into existing recursive code, and can eliminate the stack overflow case, whilst not creating any borrow-checker problems; but I don’t know about the ergonomics of using it while ultimately still enforcing a (larger) limit. If that’s the goal, you might as well just set a larger constant stack size? (Although of course the error message in exceeding a manually enforced limit would be nicer than just letting it crash with stack overflow.)

2 Likes

recursive impl:

pub fn apply(defs: &[Def], e: &mut Expr) -> bool {
    let mut changed = false;

    match &mut *e {
        Expr::Func { args, .. } => {
            for a in args.iter_mut().map(Rc::make_mut) {
                while apply(defs, a) {
                    changed = true;
                }
            }
        }
        Expr::Var { .. } => {}
    }

    let mut ch = false;
    while defs.iter().any(|def| def.apply(e)) {
        ch = true;
    }
    changed |= ch;
    if ch {
        apply(defs, e);
    }

    changed
}

1 Like

yeah i guess i don't really know about stack and heaps, but what i meant is i don't want any larger limit.
and the stack is limited compared to heap, and because the heap is basically unlimited, i want to use the heap.

speaking of the stack and heap, is it really true that the stack is limited?

Ah… well, I won’t get into a deeper explanation on stack vs. heap, but I might have misunderstood your earlier comment then, if you’re saying you “don’t want any […] limit”, then stacker should be straightforward to use. Doing as little as wrapping the body of apply in a call to maybe_grow

pub fn apply(defs: &[Def], e: &mut Expr) -> bool {
    stacker::maybe_grow(32 * 1024, 1024 * 1024, || {
        let mut changed = false;
    
        match &mut *e {
            Expr::Func { args, .. } => {
                for a in args.iter_mut().map(Rc::make_mut) {
                    while apply(defs, a) {
                        changed = true;
                    }
                }
            }
            Expr::Var { .. } => {}
        }
    
        let mut ch = true;
        while defs.iter().any(|def| def.apply(e)) {
            ch = true;
        }
        changed |= ch;
        if ch {
            apply(defs, e);
        }
    
        changed
    })
    
}

would probably already work. (I don’t actually know what reasonable numbers for the maybe_grow call are, I just copied the ones from the example in the docs. As another data point, serde_stacker by default seems to be using double these sizes for both arguments.)

2 Likes

Regarding the Vec-based solution, that’s difficult. The problem is that in a Vec of &mut Expr, one (later) item cannot reference anything (transitively) owned (or referenced) by the former.

Using anything like Cell or Mutex would probably include changes to methods like Def::apply as well, and also possibly requires adding more Rcs? Also, for concrete suggestions on that point, I would probably have to understand the context in which your current usage of Rc works. I’d presume that’s doing some sort of copy-on-write / sharing abstraction (because make_mut really is good for the “cheaply shared, and copied on-demand when one shared part needs mutation” kind of game).

1 Like

basically, what i meant is this: would the OS deny requests to grow stack sooner than it would the heap, or not?

I had thought yes. and so i wanted to use the heap.
but if the answer is "no", then I am fine using stacker.

yes, you are correct. it basically creates a shallow copy, so that things like a variable in two areas would share the expression assigned to the variable.

Ah I see. No, from the OS point of view, the stack cannot grow at all. You give it a single size at the start of the thread (or the OS determines the size for the main thread, I believe) and that’s it then. If this fixed size is very large, then the virtual addressing system the OS provides will mean that actual memory usage for the stack would grow on-demand, so in a sense the stack can “grow” in that way.

stacker however uses the heap to allocate new chunks of memory which are then used as stack, presumably by just… actually let’s look this up.

(a bit of looking-up later)

Seems like a helper crate called ”psm” is used and there it looks like the stack manipulation is done by using manual assembly instructions that will would – I guess – modify the stack pointer register accordingly.

Anyways… because the heap is used, the same limits apply i.e. essentially no limit at all, especially if your OS would even start swapping to disk once the RAM is full.

2 Likes

ok, thank you for the patience! I believe I have found my solution (thanks to you!), so... which answer to mark as solution?

That’s up to you :wink:

1 Like

oh no, now I've got another problem :joy:

1 Like

so, it turns out that the problem persists even with the use of stacker...

should I open a new topic?

the repo: pro465/rhokell

Yeah, a new topic might make sense, because then the topic is more clearly not about borrow-checking anymore. Either way, besides the repo you should include a description how to reproduce a stack overflow :slight_smile:

1 Like

ok, thank you again!