rustでborrowしてきた値のlifetimeを伸ばす方法

Question

前提・実現したいこと

rustの勉強中ですが、自分なりに課題で作っているコードで解決できない問題に当たったので
質問をさせてください。

発生している問題・エラーメッセージ

話を要約すると、for文の中でborrowしてきた値がfor文の外にlifetimeを持っているデータに引き渡せない
という問題です。

error[E0597]: `new_tree_node` does not live long enough
   --> catalan.rs:91:26
    |
91  |               stack.push(new_tree_node.borrow_mut());
    |                          ^^^^^^^^^^^^^ borrowed value does not live long enough

該当のソースコード

プログラムの全体像は以下のリンクにあります。

https://github.com/baban/rust_test/blob/master/catalan.rs

要約だけ抜き取ったものを下に張り付けておきます。

このアルゴリズムでは、親のノードと、stackの２つが一時的に子のノードの所有者にならないとツリーは作れないので、RefCellを使って複数の所有者を持てるようにしました。
ただ、borrowしてきた値のlifetimeが短すぎてfor文を抜ける前に死んでしまうのでコンパイルが通りませんでした。
他のアルゴリズムを考えるのも検討したのですが、そもそもC言語やC++では動くはずのアルゴリズムです
そうであればRustでも、コンパイラに釈明を重ねれば動くはずで何かしら私の知識の抜けの問題と思い
軽く本を読みなおしてみたのですが、lifetimeをいじる方法は、関数の引数か構造体にしか言及がありませんでした。
何かしら書き方の問題で動かないだけの様な気がするのですが、教えていただけないでしょうか？

// vec![ノード,ノード,リーフ,リーフ,ノード,リーフ,リーフ] の様なVectorから
// stackを使ってツリーを生成します。

struct RefTreeNode<'a> {
  left: RefTree<'a>,
  right: RefTree<'a>
}

enum RefTree<'b> {
  Node(Ref<'b, RefTreeNode<'b>>),
  Leaf { value: i32 },
  Empty
}

fn build_tree(path: Vec<i32>) {
  // pathから要素を一個取り出す
  // nodeならstackに積む
  // leafならstackからnodeをpopしてnodeのrightかleft空いている方に紐付ける
  // nodeの片方しか埋まっていないときはstackにnodeを戻す
  // nodeの両方が埋まったらstackに戻さない
  // pathの最後までこの処理を行ったら、最後に持っているnodeがtreeのroot
  let mut stack = Vec::<RefMut<RefTreeNode>>::new();
  let mut parent_node = RefTreeNode { left: RefTree::Empty, right: RefTree::Empty };
  let new_tree_node = RefCell::new(RefTreeNode { left: RefTree::Empty, right: RefTree::Empty });
  for pnt in path {
    match pnt {
      // node
      2 => {
        let latest_node = stack.pop();
        if let Some(mut parent_node) = latest_node {
          match parent_node.left {
            RefTree::Empty => {
              let new_tree_node = RefCell::new(RefTreeNode { left: RefTree::Empty, right: RefTree::Empty });
              // parent_node.left = RefTree::Node(new_tree_node.borrow());
              stack.push(parent_node);
              // stack.push(new_tree_node.borrow_mut());
            },
            _ => {
              let new_tree_node = RefCell::new(RefTreeNode { left: RefTree::Empty, right: RefTree::Empty });
              // parent_node.left = RefTree::Node(new_tree_node.borrow());
              stack.push(parent_node);
              // stack.push(new_tree_node.borrow_mut());
            },
          }
        } else {
          // 最初のnodeはstackが空なのでココが呼ばれる
          let new_tree_node = RefCell::new(RefTreeNode { left: RefTree::Empty, right: RefTree::Empty });
          // stack.push(new_tree_node.borrow_mut());
        }
        println!("stack length : {}", stack.len());
      },
      // leaf 
      1 => {
        let latest_node = stack.pop();
        if let Some(mut parent_node) = latest_node {
          match parent_node.left {
            RefTree::Empty => {
              parent_node.left = RefTree::Leaf { value: 4 };
              stack.push(parent_node);
            },
            _ => {
              parent_node.right = RefTree::Leaf { value: 4 };
            },
          }
          println!("stack length : {}", stack.len());
        }
      },
      _ =>{},
    };
  }
}

Answer 1

enum RefTree<'b> {
  Node(Ref<'b, RefTreeNode<'b>>),

ツリーのデータ構造内で Ref を使っていますが、これは 対象を所有しない ポインタです。このような構造ですとライフタイムの関係でうまくいきません。なぜならツリーが要素を所有しておらず、ツリー自体の寿命よりも早く、その要素がメモリから解放されてしまうからです。

つまりデータ構造を変えて、ツリーが要素を所有するようにしないといけません。そうすればツリー自体が生きている間は、その要素もメモリ上に存在することが保証されます。そのためには 対象を所有する Box ポインタを使う必要があります。

おすすめはしませんが、ひとつの修正方法としては、いまの struct RefTreeNode と enum RefTree のフィールドで、RefTree か RefTreeNode を持つフィールドの型を、Box<RefTree> や Box<RefTreeNode> に変えることが考えられます。

これをおすすめしない理由は以下のとおりです。

• match 式で box syntax という非安定な機能が必要になる（nightly版のRustが必要）
• スタックとヒープのメモリ配置が最適にならない

ではどういう構造をとったらいいかというと、こちらで紹介されている、「二分木の定義２ (Option 型を使う方法)」を真似るのがおすすめです。

• お気楽 Rust プログラミング超入門 -- 二分木

// 節の定義
struct Node<T : Ord> {
    item:  T,
    left:  Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>
}

// 二分木
struct Tree<T: Ord> {
    root: Option<Box<Node<T>>>
}

なぜこのような定義が良いのか一言で説明するのは難しく、英語ですみませんが、まずはこちらのチュートリアルを読んでもらうのがよいと思います。

• Learning Rust With Entirely Too Many Linked Lists -- 2.1 Basic Layout
• Learning Rust With Entirely Too Many Linked Lists -- 3.1 Using Option

これらのページでは単方向リンクリストのデータ構造を設計しています。このチュートリアルの2章（A Bad Singly-Linked Stack）と3章（An Ok Singly-Linked Stack）の内容はツリーの設計と実装にも大いに役立つと思いますので、上で紹介したページだけでなく、前後のページもぜひ読んでみてください。

そのあと「お気楽 Rust プログラミング超入門 -- 二分木」の設計と実装を参考に、ツリーの構造を変えて、再度チャレンジするのが良いと思います。回答として動作するプログラムを示せなくて残念なのですが、大幅な書き直しになってしまいそうなのです。

やってみてわからないところがあれば、再度質問してください。（コードが大きく変わりそうなので新しい質問を立ててもらったほうがよいかもしれません）

---

追記

RefCellを使って複数の所有者を持てるようにしました。

最初の回答で書き忘れましたが、RefCell は複数の所有者を持てる型ではなくて、内側のミュータビリティ（interior mutability）を提供する型です。複数の所有者を持てる型は Rc（Reference Counted、参照カウントの意味）になります。

今回のbuild_tree関数ではRcは使わなくても大丈夫そうです。

Comments

[baban]

ありがとうございます。
ここ2，3日試行錯誤した結果、動くところまで出来ました。

https://github.com/baban/rust_test/blob/master/catalan.rs

詳しい解説をありがとうございます。
色々、理解が進みました。

オライリーの本を一通り読んだはずですが
Refを使うと所有権を持たないからライフタイムは伸びない
本を読んだ限りそんなもん書いてあるかー、という感想です。

大幅な書き換えは、正しいコードに比べれば安いもので全然問題ないです。
ただ、結果としては、`Rc`、使って書きました

stackとツリーの両方でデータを所有する関数自体を必要としてしまったので。
Rcのcloneメソッドの存在をやっと理解しました。

Rustは安全なC++を書けるようにならないと動くことすらないので難しいと噂ですが
C++と違って、古い歴史の依存が無い分仕様がスッキリしていますし

C++だとnewだけなのが、Box::newになったり
パターンマッチでboxがマッチできないとか
Rc<RefCell>とかのよく使いそうだけど長い書式があったり

メモリにやさしくないパターンは絶対簡潔に書かせないという信念を感じます。
慣れた頃にこのあたりシンタックスシュガーが欲しいと思いそうです。