Rustのライフタイムエラーが解決できない：lifetime may not live long enough

Question

実現したいこと

スタックを模倣したプログラムを作ります。
nestメソッドで新しいStackを返し、そのStackがドロップされるまでnest元のStack経由でメモリ確保はできません。これをmut借用の特性を使って表現したのが次のコードです。
解決にあたって変えてはいけないのは次のことです。

• main関数内の処理を変えてはいけない。

できれば回避したいことは次です。

• RefCellやRcは使いたくない

発生している問題・分からないこと

ライフタイム関連のエラーが出ます。

エラーメッセージ

error: lifetime may not live long enough
  --> src/main.rs:84:36
   |
65 | impl<'a, 'b, T> Stack<'a, 'b, T> {
   |      --  -- lifetime `'b` defined here
   |      |
   |      lifetime `'a` defined here
...
84 |             parent: Parent::Parent(self),
   |                                    ^^^^ this usage requires that `'b` must outlive `'a`
   |
   = help: consider adding the following bound: `'b: 'a`
   = note: requirement occurs because of a mutable reference to `Stack<'_, '_, T>`
   = note: mutable references are invariant over their type parameter
   = help: see <https://doc.rust-lang.org/nomicon/subtyping.html> for more information about variance

該当のソースコード

use std::collections::HashMap;

fn main() {
    let mut mem = Memory::new();
    let mut stack = Stack::new(&mut mem);
    stack.alloc(0, "v1");
    {
        let mut nest = stack.nest();
        nest.push(1, "v2");
        assert_eq!(nest.len(), 2);
    }
    assert_eq!(stack.len(), 1);
    stack.alloc(2, "v3");
    assert_eq!(stack.len(), 2);
}
struct Memory<T> {
    data: HashMap<u32, T>,
}
impl<T> Memory<T> {
    fn new() -> Self {
        Self {
            data: HashMap::new(),
        }
    }
    fn alloc(&mut self, id: u32, value: T) {
        self.data.insert(id, value).unwrap();
    }
    fn free(&mut self, id: u32) {
        if self.data.remove(&id).is_some() {
            panic!()
        }
    }
}
struct Stack<'a, 'b, T> {
    ids: Vec<u32>,
    parent: Parent<'a, 'b, T>,
}
enum Parent<'a, 'b, T>
where
    'a: 'b,
{
    Root(&'a mut Memory<T>),
    Parent(&'b mut Stack<'a, 'a, T>),
}
impl<'a, 'b, T> Parent<'a, 'b, T> {
    fn alloc(&mut self, id: u32, value: T) {
        match self {
            Parent::Root(memory) => memory.alloc(id, value),
            Parent::Parent(stack) => stack.alloc(id, value),
        }
    }
    fn free(&mut self, id: u32) {
        match self {
            Parent::Root(memory) => memory.free(id),
            Parent::Parent(stack) => stack.free(id),
        }
    }
    fn len(&self) -> usize {
        match self {
            Parent::Root(memory) => memory.data.len(),
            Parent::Parent(stack) => stack.len(),
        }
    }
}
impl<'a, 'b, T> Stack<'a, 'b, T> {
    fn new(mem: &'a mut Memory<T>) -> Self {
        Self {
            ids: vec![],
            parent: Parent::Root(mem),
        }
    }
    fn push(&mut self, id: u32, value: T){
        self.ids.push(id);
        self.alloc(id, value);
    }
    fn alloc(&mut self, id: u32, value: T) {
        self.parent.alloc(id, value);
    }
    fn free(&mut self, id: u32) {
        self.parent.free(id);
    }
    fn nest<'c>(&'c mut self) -> Stack<'a, 'c, T>
    where
        'b: 'c,
    {
        Stack {
            ids: vec![],
            parent: Parent::Parent(self),
        }
    }
    fn len(&self) -> usize {
        self.parent.len()
    }
}
impl<'a, 'b, T> Drop for Stack<'a, 'b, T> {
    fn drop(&mut self) {
        for id in &self.ids {
            self.parent.free(*id);
        }
    }
}

試したこと・調べたこと

• teratailやGoogle等で検索した
• ソースコードを自分なりに変更した
• 知人に聞いた
• その他

上記の詳細・結果

なお張り付けたコードのnest関数を現在の

fn nest<'c>(&'c mut self) -> Stack<'a, 'c, T>
    where
        'b: 'c,

ではなく、

fn nest(&'b mut self)->Stack<'a, 'b, T>

とすると、nestのエラーは消えますが、以下の(2)のエラーが代わりに出ます。

error[E0597]: stack does not live long enough
--> src/main.rs:8:24
|
5 | let mut stack = Stack::new(&mut mem);
| --------- binding stack declared here
...
8 | let mut nest = stack.nest();
| ^^^^^ borrowed value does not live long enough
...
15 | }
| -
| |
| stack dropped here while still borrowed
| borrow might be used here, when stack is dropped and runs the Drop code for type Stack

error[E0502]: cannot borrow stack as immutable because it is also borrowed as mutable
--> src/main.rs:12:16
|
8 | let mut nest = stack.nest();
| ----- mutable borrow occurs here
...
12 | assert_eq!(stack.len(), 1);
| ^^^^^
| |
| immutable borrow occurs here
| mutable borrow later used here

error[E0499]: cannot borrow stack as mutable more than once at a time
--> src/main.rs:13:5
|
8 | let mut nest = stack.nest();
| ----- first mutable borrow occurs here
...
13 | stack.alloc(2, "v3");
| ^^^^^
| |
| second mutable borrow occurs here
| first borrow later used here

error[E0502]: cannot borrow stack as immutable because it is also borrowed as mutable
--> src/main.rs:14:16
|
8 | let mut nest = stack.nest();
| ----- mutable borrow occurs here
...
14 | assert_eq!(stack.len(), 1);
| ^^^^^
| |
| immutable borrow occurs here
| mutable borrow later used here

error: lifetime may not live long enough
--> src/main.rs:82:36
|
65 | impl<'a, 'b, T> Stack<'a, 'b, T> {
| -- -- lifetime 'b defined here
| |
| lifetime 'a defined here
...
82 | parent: Parent::Parent(self),
| ^^^^ this usage requires that 'b must outlive 'a
|
= help: consider adding the following bound: 'b: 'a
= note: requirement occurs because of a mutable reference to Stack<'_, '_, T>
= note: mutable references are invariant over their type parameter
= help: see https://doc.rust-lang.org/nomicon/subtyping.html for more information about variance

Some errors have detailed explanations: E0499, E0502, E0597.
For more information about an error, try rustc --explain E0499.
error: could not compile workspace (bin "workspace") due to 5 previous errors

補足

特になし

Answer 1

parent を enum で実装していますが、trait を導入してジェネリクスにしてしまうのはどうでしょう。(下記ではPhantomData とかがでてきて面倒な形になってしまいましたが、もっといい実装があるかもしれません)

わたしもぼんやりとしか理解できていませんが、元のコードが動かない理由には variance とかがかかわっているように思います。https://blog.ymgyt.io/entry/lifetime-and-variance/
&'a mut T は T に対して invariant なので、参照を含むものの &mut をとると、ライフタイムの関係が壊れてしまいそうです。
(Parent(&'b mut Stack<'a, 'a, T>)のところの'a)
そこを別のライフタイムにしてどうにかしようとすると、別回答のコメントにあるように任意回のネストをうまく表現することができないです。ジェネリクスにすれば、そのあたりをコンパイラがいい感じにしてくれているように思います。

use std::collections::HashMap;
use std::marker::PhantomData;

fn main() {
    let mut mem: Memory<&'static str> = Memory::new();
    let mut stack = Stack::new(&mut mem);
    stack.alloc(0, "v1");
    {
        let mut nest = stack.nest();
        nest.push(1, "v2");
        {
            let mut nest = nest.nest();
            nest.push(2, "v1");
            nest.push(3, "v2");
            assert_eq!(nest.len(), 4);
        }
        assert_eq!(nest.len(), 2);
    }
    stack.alloc(2, "v3");
    assert_eq!(stack.len(), 2);
}

struct Memory<T> {
    data: HashMap<u32, T>,
}

impl<T> Memory<T> {
    fn new() -> Self {
        Self {
            data: HashMap::new(),
        }
    }
}

trait Parent<T> {
    fn alloc(&mut self, id: u32, value: T);
    fn free(&mut self, id: u32);
    fn len(&self) -> usize;
}

impl<T> Parent<T> for Memory<T> {
    fn alloc(&mut self, id: u32, value: T) {
        if self.data.insert(id, value).is_some() {
            panic!()
        }
    }

    fn free(&mut self, id: u32) {
        if self.data.remove(&id).is_none() {
            panic!()
        }
    }

    fn len(&self) -> usize {
        self.data.len()
    }
}

struct Stack<'a, T, U: Parent<T>> {
    ids: Vec<u32>,
    parent: &'a mut U,
    _p: PhantomData<T>,
}

impl<'a, T> Stack<'a, T, Memory<T>> {
    fn new(mem: &'a mut Memory<T>) -> Self {
        Self {
            ids: vec![],
            parent: mem,
            _p: PhantomData,
        }
    }
}

impl<'a, T, U: Parent<T>> Stack<'a, T, U> {
    fn nest<'b>(&'b mut self) -> Stack<'b, T, Self> {
        Stack {
            ids: vec![],
            parent: self,
            _p: PhantomData,
        }
    }

    fn push(&mut self, id: u32, value: T) {
        self.ids.push(id);
        self.alloc(id, value);
    }
}

impl<T, U: Parent<T>> Parent<T> for Stack<'_, T, U> {
    fn alloc(&mut self, id: u32, value: T) {
        self.parent.alloc(id, value);
    }

    fn free(&mut self, id: u32) {
        self.parent.free(id);
    }

    fn len(&self) -> usize {
        self.parent.len()
    }
}

impl<T, U: Parent<T>> Drop for Stack<'_, T, U> {
    fn drop(&mut self) {
        for id in &self.ids {
            self.parent.free(*id);
        }
    }
}

Comments

[tt-44]

解決策とエラーの要因も示した丁寧な回答ありがとうございます。
ベストアンサーに選ばせていただきたいと思います

Answer 2

エラーメッセージにあるとおり 'b: 'a をつけてあげるとエラーは解決します。

    fn nest<'c>(&'c mut self) -> Stack<'a, 'c, T>
    where
        'b: 'a,
        'b: 'c,
    {
        Stack {
            ids: vec![],
            parent: Parent::Parent(self),
        }
    }

ところで元のコードを走らせると2箇所パニックになります。
どちらも HashMap への操作で、操作前に値が入っていた場合と入っていなかった場合を表わす Option が返っているのに対して期待と実際が異なっているのが原因です。

impl<T> Memory<T> {
    // ...
    fn alloc(&mut self, id: u32, value: T) {
        // idに対応する値が既に入っていた場合に `Some` が返る。
        // 入っていないのが期待する動作と思われる
        if self.data.insert(id, value).is_some() {
            panic!()
        }
    }
    fn free(&mut self, id: u32) {
        // idに対応する値が既に入っていた場合に `Some` が返る
        // 入っているのが期待する動作と思われる。
        if self.data.remove(&id).is_none() {
            panic!()
        }
    }
}

2関数を上記のコードに差し替えたらプログラムがエラーなく動作することを確認できました。

Comments

[tt-44]

丁寧な回答ありがとうございます。確かにエラーが消えました。
ただ、確認後少しコードを変えてみて、コードにおける意図を鑑みた同様のコードとして、ネストをさらに深くした次のコードはいまだエラーが出ます。
```rust
fn main(){
let mut mem: Memory<&'static str> = Memory::new();
let mut stack = Stack::new(&mut mem);
stack.alloc(0, "v1");
{
let mut nest = stack.nest();
nest.push(1, "v2");
{
let mut nest = nest.nest();
nest.push(2, "v1");
nest.push(3, "v2");
}
}
stack.alloc(2, "v3");
}
```
```
のようにしたところ、エラーが出ます。もしくは
```rust
fn se<'a, 'b>(mut stack: Stack<'a, 'b, &'static str>) {
stack.push(2, "v1");
stack.push(3, "v2");
}
fn main(){
let mut mem: Memory<&'static str> = Memory::new();
let mut stack = Stack::new(&mut mem);
stack.alloc(0, "v1");
{
let mut nest = stack.nest();
nest.push(1, "v2");
se(nest.nest());
}
stack.alloc(2, "v3");
}
```
これは回避可能でしょうか。

[blackenedgold]

それは難しそうです。パラメータ2つ使って2つ分のライフタイムを表現していたところを任意回のネストにすると表現できなくなるみたいです

[tt-44]

了解です。今回はベストアンサーは別の方になりましたが、非常に参考になりました。改めて回答ありがとうございました。