質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.83%

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

解決済

回答 1

投稿

  • 評価
  • クリップ 0
  • VIEW 1,586

baban

score 16

前提・実現したいこと

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の2つが一時的に子のノードの所有者にならないとツリーは作れないので、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());
        }
      },
      _ =>{},
    };
  }
}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

checkベストアンサー

+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が必要)
  • スタックとヒープのメモリ配置が最適にならない

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

// 節の定義
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>>>
}

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

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

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

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


追記

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

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

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/06/01 10:20 編集

    ありがとうございます。
    ここ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>とかのよく使いそうだけど長い書式があったり

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.83%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る