Chess program stack borrow problem

Hello,
I am learning the Rust language but stuck now on something impossible.
In the below code I encounter a borrowing problem, using a mutable stack of chess-movegenerators.
If anyone knows how to solve that and what is the general problem, I would be very happy!
Best wishes
Eric

use types::*;
use position::*;
use movgen::*;
use timer::*;

pub struct MoveStack
{
    Generators: Vec<MovGen>
}

impl MoveStack
{
    pub fn new(size: usize) -> Self
    {
        let mut result = 
        MoveStack
        {
            Generators: Vec::with_capacity(size) 
        };
        for i in 0..size
        {
            result.Generators.push(MovGen::new());
        }
        result
    }


    #[inline]
    fn get_generator(&mut self, depth: usize) -> &mut MovGen
    {
        debug_assert!(depth < self.Generators.len());
        &mut *self.Generators.get_mut(depth).unwrap()
    }

}

pub struct Perft
{
    Stack: MoveStack,
    Timer: Timer,
}

impl Perft
{
    /// Private constructor
    fn new(maxdepth: i32) -> Self
    {
        let mut result: Self =
        Self
        {
            Stack: MoveStack::new(maxdepth as usize + 1),
            Timer: Timer::new(),
        };

        for i in 0..maxdepth
        {
            result.Stack.Generators.push(MovGen::new());
        }
        result
    }

    /// Static perft function. Creates a Perft struct and runs it.
    pub fn execute(pos: &mut Position, depth: i32)
    {
        assert!(depth >= 0 && depth <= 16, "Invalid depth {}", depth);
        let mut perft: Perft = Perft::new(depth + 1);
        perft.exec(pos, depth);
    }

    fn exec(&mut self, pos: &mut Position, depth: i32)
    {
        self.Timer.start();
        let nodes: u64 = self.run(pos, depth, true);
        self.Timer.stop();
        println!("nodes: {}, time: {}, nps: {}", nodes, self.Timer.elapsed_ms(), nps(nodes, self.Timer.elapsed_micro()));
    }

    fn run(&mut self, pos: &mut Position, depth: i32, root: bool) -> u64
    {
        let mut count: u64;
        let mut nodes: u64 = 0;
        let leaf: bool = depth == 2;

        let generator: &mut MovGen = self.Stack.get_generator(pos.depth());
        generator.generate_legal_moves(&pos);

        for mov in &generator.Moves
        {
            if root && depth <= 1
            {
                count = 1;
                nodes += 1;
            }
            else
            {
                pos.make_move(mov);
                if leaf
                {
                    let leafcounter: &mut MovGen = self.Stack.get_generator(pos.depth() + 1); // PROBLEM 1: cannot borrow 'self.Stack' as mutable more than once at a time
                    leafcounter.generate_legal_moves(pos);
                    count = leafcounter.count() as u64;
                    nodes += count;
                }
                else
                {
                    count = self.run(pos, depth - 1, false); // PROBLEM 2: cannot borrow '*self' as mutable more than once at a time
                    nodes += count;
                }
                pos.unmake_move();
            }
            if root
            {
                println!("{}: {}", mov.to_string(), count);
            }
        }
        nodes
    }

}

It will help people help you if you reduce this to a minimal reproducible example.

Your example isn't reproducible because it uses some code that isn't included, and it doesn't look minimal.

1 Like

Okidoki. this is a complete standalone reproduction which does not compile :slight_smile:

pub struct Generator {
    pub MoveList: Vec<i32>,
}

impl Generator {
    fn new() -> Self {
        let mut result = Self {
            MoveList: Vec::with_capacity(256),
        };
        result
    }

    fn gen_moves(&mut self) {
        self.MoveList.clear();
        for i in 0..4 {
            self.MoveList.push(i);
        }
    }
}

pub struct MoveStack {
    Generators: Vec<Generator>,
}

impl MoveStack {
    fn new(size: usize) -> Self {
        let mut result = Self {
            Generators: Vec::with_capacity(size),
        };
        for i in 0..size {
            result.Generators.push(Generator::new());
        }
        result
    }

    fn get_gen(&mut self, depth: usize) -> &mut Generator {
        self.Generators.get_mut(depth).unwrap()
    }
}

pub struct PerftTest {
    Stack: MoveStack,
}

impl PerftTest {
    fn new(depth: usize) -> Self {
        Self {
            Stack: MoveStack::new(depth),
        }
    }

    pub fn execute(depth: usize) -> u64 {
        let mut Perft = PerftTest::new(depth);
        Perft.run(depth)
    }

    fn run(&mut self, depth: usize) -> u64 {
        if depth == 0 {
            let mg = self.Stack.get_gen(depth);
            mg.gen_moves();
            return mg.MoveList.len() as u64;
        }

        let mut nodes: u64 = 0;

        let mg = self.Stack.get_gen(depth);
        for m in &mg.MoveList {
            let mg2 = self.Stack.get_gen(depth + 1); // cannot borrow `self.Stack` as mutable more than once at a time second mutable borrow occurs here
            mg2.gen_moves(); // (dummy call)
            nodes += self.run(depth - 1); // cannot borrow `*self` as mutable more than once at a time second mutable borrow occurs here
        }

        nodes
    }
}

Compiles just fine in the Playground ... though there are a lot of warnings you might want to attend to, eg like this.

I know, but no severe ones. the code is about showing the problem, which i really can't understand how to solve it: "how to have a mutable stack in this run function".

We need to see code that produces the borrow error you want help with, rather than code that compiles successfully or code that fails to compile for other reasons.

ok. added a main function. it certainly does not compile.

pub struct Generator {
    pub MoveList: Vec<i32>,
}

impl Generator {
    fn new() -> Self {
        let mut result = Self {
            MoveList: Vec::with_capacity(256),
        };
        result
    }

    fn gen_moves(&mut self) {
        self.MoveList.clear();
        for i in 0..4 {
            self.MoveList.push(i);
        }
    }
}

pub struct MoveStack {
    Generators: Vec<Generator>,
}

impl MoveStack {
    fn new(size: usize) -> Self {
        let mut result = Self {
            Generators: Vec::with_capacity(size),
        };
        for i in 0..size {
            result.Generators.push(Generator::new());
        }
        result
    }

    fn get_gen(&mut self, depth: usize) -> &mut Generator {
        self.Generators.get_mut(depth).unwrap()
    }
}

pub struct PerftTest {
    Stack: MoveStack,
}

impl PerftTest {
    fn new(depth: usize) -> Self {
        Self {
            Stack: MoveStack::new(depth),
        }
    }

    pub fn execute(depth: usize) -> u64 {
        let mut Perft = PerftTest::new(depth);
        Perft.run(depth)
    }

    fn run(&mut self, depth: usize) -> u64 {
        if depth == 0 {
            let mg = self.Stack.get_gen(depth);
            mg.gen_moves();
            return mg.MoveList.len() as u64;
        }

        let mut nodes: u64 = 0;

        let mg = self.Stack.get_gen(depth);
        for m in &mg.MoveList {
            let mg2 = self.Stack.get_gen(depth + 1); // cannot borrow `self.Stack` as mutable more than once at a time second mutable borrow occurs here
            mg2.gen_moves(); // (dummy call)
            nodes += self.run(depth - 1); // cannot borrow `*self` as mutable more than once at a time second mutable borrow occurs here
        }

        nodes
    }
}

fn main()
{
    PerftTest::execute(3);
}

You can try using RefCell to defer borrow checking to runtime, like this: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=9f7045ceeac13b189d37208eea82345f

But you will still only be able to hold a single mutable reference to each Generator at any given time, that is a restriction of the language.

And that is exactly what i do not understand.
The ownership has a strict hierarchy. So in my mind all things should be mutable.
Instead of in my recursive routine creating a local Generator (which works perfectly) I just want some buffer of pre-allocated Generators.

This doesn’t quite work – (playground where the test data is fixed to make the relevant code reachable) – as the borrows of the refcell on different depths overlap. The inside of self.run(depth - 1) tries to make mutable access of self.Stack.get_gen_mut((dept - 1) + 1);, conflicting with the ongoing outer for m in &mg.MoveList loop (let mg = self.Stack.get_gen(depth);).

I’d say that is however a clear logic error in the implementation that fundamentally can’t be fixed with RefCell. It doesn’t make sense to be wanting to .clear() and re-populate the MoveList, as gen_moves, while currently iterating over it.

Or in case it is supposed to be sensible, then iterating over a copy of the original list is desired, in which case RefCell probably wouldn’t be needed at all to resolve the error.

1 Like

That last comment seems also logical to me. I reverted the code back to local generators.
Until I really know how to have a mutable stack. Which saves an insane amount of heap allocations.