Borrowing a reference that is then updated

[StefanFrederiksen]

I'm still rather new to Rust and I am looking into implementing Ukkonen's algorithm for generating a suffix tree in linear time.
One of the tricks for making the algorithm O(n) is that the nodes have a "global end" that is updated via one variable update, rather than looping through all generated nodes and incrementing their end variable.

I would usually implement this using a reference, so the interval would look like [usize, &usize], but I would still need to mutate some variables in the Node, which leads me to a violation of the borrowing rules (cannot mutate variable that is borrowed).

Smallest example I could provide would probably be the following.

struct Node<'n> {
    start: usize,
    end: &'n usize,
}

fn main() {
    let mut global_end = 0;
    let mut n = Node {
        start: 0,
        end: &global_end,
    };

    for _ in 0..10 {
        global_end += 1; // "cannot assign to 'global_end' because it is borrowed"
    }

    n.start = 1;
}

I might be thinking about this wrong, so do I have any alternatives besides going into unsafe rust?

[alice]

You are violating the "others cannot write" rule of immutable references. Try using Cell instead.

use std::cell::Cell;

struct Node<'n> {
    start: usize,
    end: &'n Cell<usize>,
}

fn main() {
    let mut global_end = Cell::new(0);
    let mut n = Node {
        start: 0,
        end: &global_end,
    };

    for _ in 0..10 {
        global_end.set(global_end.get() + 1);
    }

    n.start = 1;
}

I have a blog post on this topic: Temporarily opt-in to shared mutation.

[StefanFrederiksen]

Thank you.
I had looked into RefCell but that seemed to only move the borrowing rules to the runtime rather than compile-time, so that didn't seem to do the trick. But using Cell seems to be the play here for the "interior mutability" stuff and the fact that usize is clone-able.

[TomP]

@alice

I have a blog post on this topic: Temporarily opt-in to shared mutation.

Great post! It's one that should be included in a central library of posts that explain somewhat-obscure facets of Rust.