Rust 用に書いた木構造ライブラリ dendron の内部構造の解説

木構造、ほしくない?

この記事は Rust Advent Calendar 2022 その2 の8日目の記事です。

既存実装

木構造といったって、用途次第でいろいろ楽する方法があるわけです。 まずはよく知られた方法の実装について簡単に見てみましょう。

一気に作ってそれ以降は読み出すだけなら Box を使うのが楽です。

      /// ノード。
#[derive(Default, Debug, Clone)]
struct Node<T> {
    /// ノードに紐付いたデータ。
    data: T,
    /// 子ノード。
    children: Vec<Box<Node<T>>>,
}
    

ただし、このような持ち方だとノードの参照を保持しながら別の箇所を編集するといった用法はほぼ無理です。 参照を持ちながら編集もしたいなら、 Box の代わりに Rc と RefCell を使うのが鉄板です。

      /// ノード。
#[derive(Default, Debug, Clone)]
struct Node<T> {
    /// ノードに紐付いたデータ。
    data: T,
    /// 子ノード。
    children: Vec<Rc<RefCell<Node<T>>>>,
}
    

時点で563kダウンロードを誇る rctree クレートはこのパターンです。 ただし、あるノードから近隣ノードの参照も取得できるよう、実際には Vec ではなく隣接ノードへの Rc / Weak 参照を持つようになっています。

      use std::rc::{Rc, Weak};

/// ノード。
// rctree と書き方は多少異なるが、本質的には同じ。
#[derive(Default, Debug, Clone)]
struct Node<T> {
    /// ノードに紐付いたデータ。
    data: T,

    /// 次の兄弟ノード。
    // このノードが所有する。
    next_sibling: Option<Rc<RefCell<Node<T>>>>,
    /// 最初の子ノード。
    // このノードが所有する。
    first_child: Option<Rc<RefCell<Node<T>>>>,

    /// 親ノード。
    // 所有者は親の親なので、弱参照を持つ。
    parent: Option<Weak<RefCell<Node<T>>>>,
    /// 前の兄弟ノード。
    // 所有者は前の前の兄弟ノードか親ノードなので、弱参照を持つ。
    prev_sibling: Option<Weak<RefCell<Node<T>>>>,
    /// 最後の子ノード。
    // 所有者は最後の子の前の兄弟ノードか `first_child` フィールドなので、
    //弱参照を持つ。
    last_child: Option<Weak<RefCell<Node<T>>>>,
}
    

あるいはマルチスレッドとかメモリアクセスの効率とか破棄のタイミング次第では、アリーナを使っても良いでしょう。 時点で218kダウンロードを誇る indextree クレートはこのパターンです。

      /// ノードの ID。
///
/// ユーザはノードを直接保持するのではなく、 ID を保持する。
/// これにより木全体を長期間借用せずにノードを参照する手段を確保しておける。
#[derive(Default, Debug, Clone, Copy, PartialEq, Eq)]
struct NodeId(usize);

/// 木。アリーナとも呼ばれる。
#[derive(Default, Debug, Clone)]
struct Tree<T> {
    /// ノード。
    ///
    /// 削除されたら `None` を置く。
    data: Vec<Option<Node<T>>>,
}

/// ノード。
#[derive(Default, Debug, Clone)]
struct Node<T> {
    /// ノードに紐付いたデータ。
    data: T,
    /// 子ノードの ID。
    children: Vec<NodeId>,
}
    

例のごとく、 indextree でも近隣ノードへのアクセスを可能にするため子ノードのリストではなく隣接ノードを記憶するようになっています。

      // indextree よりだいぶ単純化したが、本質部分は同じ。

/// ノードの ID。
///
/// ユーザはノードを直接保持するのではなく、 ID を保持する。
/// これにより木全体を長期間借用せずにノードを参照する手段を確保しておける。
#[derive(Default, Debug, Clone, Copy, PartialEq, Eq)]
struct NodeId(usize);

/// 木。アリーナとも呼ばれる。
#[derive(Default, Debug, Clone)]
struct Arena<T> {
    /// ノード。
    ///
    /// 削除されたら `None` を置く。
    data: Vec<Option<Node<T>>>,
}

/// ノード。
#[derive(Default, Debug, Clone)]
struct Node<T> {
    /// ノードに紐付いたデータ。
    data: T,
    /// 親ノード。
    parent: Option<NodeId>,
    /// 次の兄弟ノード。
    next_sibling: Option<NodeId>,
    /// 前の兄弟ノード。
    prev_sibling: Option<NodeId>,
    /// 最初の子ノード。
    first_child: Option<NodeId>,
    /// 最後の子ノード。
    last_child: Option<NodeId>,
}
    

この2種の実装のどちらかで事足りるなら、 rctree か indextree を使うのが現時点では鉄板の選択かと思います。 ところが、これでも木の扱いについては制約が多く、用途によっては不足があるのです。

要件

まともな木

木構造の典型的な用途として、たとえばマークアップ文書を HTML や XML の DOM のようなインターフェースで作成・編集・アクセスすることを想像してみてください。 いくらか欲しい性質があります。

  • 親、兄弟、子などの近隣ノードに容易にアクセスできる
  • 任意のノードへの参照が木全体を生存させる
  • 参照しているノードが勝手に破棄されない
  • 部分木の分離や接合が簡単である
  • 木は、親と兄弟を持たないルートノードをちょうど1つ持っている

まず「親、兄弟、子などの近隣ノードに容易にアクセスできる」こと。 今見ているリスト項目の次の項目の中身を弄りたいなどの場合に、いちいち項目の順番 n を取得したうえで親ノード経由で n+1 番目の子にアクセスする必要があるのではあまりに面倒です。

そして「任意のノードへの参照が木全体を生存させる」こと。 リスト項目を覚えておいたのに、親であるリスト全体がいつの間にか解放されて項目1つしか残らなかった、では困ります。 たとえユーザがリスト項目ひとつだけを持っていたとしても、兄弟のリスト項目や文書全体が残っていないと、周辺の文脈や遠いところにあるかもしれないメタデータにアクセスできなくなってしまいます。 そのため、深いところにあるノードをあちこちで持ち回っても、木全体が生存し続けてほしいわけです。

さらに「参照しているノードが勝手に破棄されない」こと。 当たり前に聞こえるでしょうが、アリーナ方式ではこの保証は与えられません。 ノード ID は所詮は木の寿命や借用関係とは独立して存在するデータに過ぎないので、ノード ID を持っているからといって木やノードが破棄されるのを防ぐことはできません。

加えて「部分木の分離や接合が簡単である」こと。 部分木を元の木から新たな独立した木として切り離したり、別の場所で作っておいた木を別の木の下にまとめて接合する、といったことができると便利です。 アリーナ型だとノードのデータがアリーナを跨ぐ必要があるため一手間かかるのは容易に想像できるでしょう。 Rc ベースの実装であっても、適切な手順を踏まないと木を越えたノードの移動はうまくいかないことがありえます。

それから「木は、親と兄弟を持たないルートノードをちょうど1つ持っている」こと。 というか、木の定義とはそもそもそういうものです。 一番上位にあるノードが兄弟を持っていたら、それはもはや木ではないわけですね。 とはいえ通常そのような場合、それら兄弟をまとめて子として持つような仮想的なルートノードを考えてやれば普通の木として捉えられるので、理論上はそこまで深刻な問題ではありません。実践上は……型を付けるのが面倒になるので地味に厄介な問題です。

単純な Rc による木やアリーナによる木では、実はこれらの要件すべてを満たすことはできません。

既存実装の良くない性質

dendron のドキュメントの焼き直しになりますが、前節で紹介した性質について既存実装がどうなっているか調べると、あまり喜ばしい状況ではないことがわかります。

性質 rctree indextree dendron (自作ライブラリ)
親、兄弟、子などの近隣ノードに容易にアクセスできる
任意のノードへの参照が木全体を生存させる × ×
参照しているノードが勝手に破棄されない ×
部分木の分離や接合が簡単である ×
ルートノードのある「ちゃんとした木」であることが保証される × ×

まず「任意のノードへの参照が木全体を生存させる」性質は rctree も indextree も持ち合わせていません。 rctree は先祖への参照がなくなったら容赦なく先祖側を破棄してしまいます。 indextree ではノード ID はアリーナやノードを延命させないため、ノードやアリーナ自体が削除されることは阻止できません。 (参考)

「参照しているノードが勝手に破棄されない」性質は rctree は持っています (Rc なので当然といえば当然です) が、 indextree は持っていません。ノード ID の存在はアリーナやノードに対して制約を与えません。 (参考)

「部分木の分離や接合が簡単である」という性質は rctree も indextree も持っていません。 indextree では同じアリーナ内であれば楽をできますが、別アリーナに移動する場合は自分で走査しながら木を作り直す必要があります。 rctree ではノードを detach することで別の木に接合できるようになりますが、detach や deep copy を忘れると木構造は意図せぬ状態になって壊れることがあります。 つまり「操作自体は簡単だが、誤りやすく検査もない」という状態です。

「ルートノードのある『ちゃんとした木』であることが保証される」という性質も、実は rctree も indextree も備えていません。 どちらのクレートも、 safe な操作によって最上位ノードが兄弟を持つような状態に仕立て上げることができます。 つまり「本当の木」であることを前提としたアルゴリズムやプログラムが誤動作してしまうような状態がありうるということです。 (参考)

dendron の紹介

欲しいものがなければ作るしかない、ということで作りました。

dendron は以下の性質を持つように作られました。

  • 親、兄弟、子などの近隣ノードに容易にアクセスできる (既出)
  • 任意のノードへの参照が木全体を生存させる (既出)
  • 参照しているノードが勝手に破棄されない (既出)
  • 部分木の分離や接合が簡単である (既出)
  • 木は、親と兄弟を持たないルートノードをちょうど1つ持っている (既出)
  • 木構造の一時凍結ができる
  • ノードだけでなく「木そのもの」への参照を持てる
  • メソッド名が慣習を踏まえずとも明確である

既出のものについては先に説明したとおりなので良いでしょう。 加えて言うなら、部分木の分離や接合については、木を跨ぐ操作もシームレスにできるようにしています。 「別の木に接合する前にデタッチを忘れないように」とか「同じノードが複数の木で共有されないようにしなければ」といった注意は不要です。 型システムと API によって自然に強制されます。

「木構造の一時凍結ができる」というのは、機能というよりは保証の話です。 たとえば「リストの項目を順番に処理するつもりでいろいろな関数に渡していたら、注目していたリスト項目がいつのまにか別のリスト内へと移動されていた」のような事故があると、正しくリストを走査できず悲しみを味わうことになります。 C++ 経験者であれば、意図せずイテレータを invalidate してしまっていたときのがっかり感を思い出すかもしれません。 木全体がその構造を変化させないことを型システムによって保証できれば、ユーザはバグや検査漏れに怯えることなくノードを扱えるようになります。

「ノードだけでなく『木そのもの』への参照を持てる」というのはそのままの意味で、ルートノードが別のノードになった場合でも同じ木全体を参照し続けられるということです。 ノードしか扱えないようなライブラリでは、「これがルートノードである」とユーザが決めたうえでそのノードを保持することで擬似的に木を保持していると見做します。 しかしそのノードに親ノードを追加することを考えたとき、追加した当事者は新しいルートノードを保持しなおすことができますが、他の箇所のコードでは旧ルートノードしか持っていないかもしれません。 さらに運が悪ければ、旧ルートノードが木から分離 (デタッチ) されて別の木になった場合、本来の意図とは違う木を参照する状態になってしまうことさえありえます。

「メソッド名が慣習を踏まえずとも明確である」というのは、 DOM (Document Object Model) のようなわかりづらい命名をしないということです。 たとえば A.insertBefore(B, C); というコードについて考えてみましょう。これは何を意味しているのでしょうか? A, B, C の3つのノードが登場しますが、誰が、どこに、何を、挿入するのでしょうか。

  • A が、 B の前に、 C を?
  • A が、 C の前に、 B を?
  • C が、 B の前に、 A を?
  • C が、 A の前に、 B を?

正解は「A を親として、 C の前に、 B を挿入」です。 すなわち parent.insertBefore(new, reference); (parent を親として、 new を、 reference の前に) となっています。 非自明ですね。

そもそも「誰が」とか「誰を親として」の部分は本当に必要なのでしょうか。 「X を Y の前に挿入する」の2つのノード指定だけで十分だと思いませんか? 親ノードを与えさせることでルートノードの兄弟作成を阻止するという意図は考えられるかもしれませんが、どうせ親として渡されたノードが無関係だったらエラーにするのですから、最初から「ルートノードに兄弟を作ろうとしたらエラー」としても十分なはずです。

このように、 DOM はよく知られた API ではあるものの、非英語ネイティブとしてはその命名に非常に納得のいかないものがあり、また型の面でもデザインが最善であるとは思えません。 内部構造だけでなくインターフェースについても、ライブラリは必然性があり曖昧さの排除されたものを提供すべきです。 dendron では、このようなコードを new.detach_insert_subtree(InsertAs::PreviousSiblingOf(reference)); と書きます。 字面は多少長いですが、「new を、reference の前の兄弟として、元の位置から分離 (detach) したうえで部分木ごと挿入する」というのが一目瞭然です。 曖昧さも誤解の余地もありません。

実装の詳細

概要

大雑把には、 dendron は以下のようにしてデータを保持します。

  • 木もノードも、内部的なオブジェクト (TreeCore, NodeCore) と、ユーザが外部から参照するためのスマートポインタ型 (Tree, Node) で別々に用意されている。
  • 木 (TreeCore) がルートノード (NodeCore)を所有し、各ノード (NodeCore)は最初の子と次の兄弟 (いずれも NodeCore) を所有する。
  • 木のユーザ用スマートポインタ (Tree) は、木の内部オブジェクト (TreeCore) を所有する。
  • ノードのユーザ用スマートポインタ (Node) は、ノードの内部オブジェクト (NodeCore) を所有し、また、ノードの内部オブジェクト (MembershipCore) に対して木の生存を強制させる。
所有権の流れ。 ユーザが持つ Tree または Node から所有関係が伝播し、最終的にどのノードや木への参照であろうと木全体が所有される状態になることがわかる。

端的には「ユーザの意志でしか作成されない特殊なスマートポインタを基点として、それらから辿れるオブジェクトは生存させる」という発想です。 参照カウント方式をベースに、循環参照まわりの問題を解決することで実現しました。

構成要素

ノードへのアクセスは Node<T> 型から、木へのアクセスは Tree<T> 型から提供されています。 この図のなかでユーザに露出されている型はこの2つだけです。

NodeCore

ノードに紐付いたデータと近隣ノードへのリンクを保持するのが NodeCore 型です。 すなわち、 NodeCore 型は木構造データそのものを単純に表現しています。

本当は近隣ノードへのリンクとして次の兄弟、前の兄弟 (循環)、最初の子、親の4つを持っていますが、図では単純化のためノードが参照先の所有権を持つ (すなわち参照先の生存を担保する) ようなリンク、すなわち最初の子と次の兄弟についてのみ図示しています。

            /// Internal node data.
// ↓図で強調したノード
struct NodeCore<T> {
    /// Data associated to the node.
    data: RefCell<T>,
    /// Neighbors.
    // ↓図では NodeCore に含めて (まとめて) 表現している
    neighbors: RefCell<Neighbors<T>>,
    /// Membership to a tree.
    // membership については、また後で。
    membership: WeakMembership<T>,
    /// The number of children.
    num_children: Cell<usize>,
}

/// A collection of links to neighbor nodes.
struct Neighbors<T> {
    /// Parent.
    // ↓図では省略
    parent: IntraTreeLinkWeak<T>,
    /// First child.
    // ↓図で強調したエッジ
    first_child: Option<IntraTreeLink<T>>,
    /// Next sibling.
    // ↓図で強調したエッジ
    next_sibling: Option<IntraTreeLink<T>>,
    /// Previous sibling.
    // ↓図では省略
    prev_sibling_cyclic: IntraTreeLinkWeak<T>,
}

/// An intra-tree owning reference to a node.
pub(crate) struct IntraTreeLink<T> {
    /// Target node core.
    core: Rc<NodeCore<T>>,
}
          
dendron v0.1.5 における NodeCore 型の定義 (解説用にコメントを一部改変) (NodeCore, Neighbors, IntraTreeLink)

NodeCore にだけ着目して観察すれば、これが本質的には Rc ベースの木構造であることは簡単に納得してもらえることでしょう。 dendron における木に都合の良い性質を与えている重要な要素は、 NodeCore 以外の部分です。

TreeCore, Tree

利便性と必要性の両面から、「木」そのものを表現する型 TreeCoreTree が用意されています。

TreeCore 型は、個々のノードではなく木全体が持つべき情報を保持する内部的な型で、1つの木につきちょうど1つ存在します。 今のところはルートノードへの参照とロックマネージャくらいしか持っていませんが、たとえば「木の名前」のようなものも持たせるような変更も簡単にできます[0]

Tree 型は、 TreeCore を共有するような型で、ユーザ向けに露出されています。 TreeCore は木につき1つだけ存在しますが、 Tree は1つの木 (1つの TreeCore) に対して複数存在できます。

TreeCore 型は所有権つきでルートノードへの参照を持っています。 つまり TreeCore の所有権を持つことで、間接的・連鎖的にルートノードの子孫すべての NodeCore (そしてそれらが所有する MembershipCore) の生存も保証されることになります。 このことが、後で説明する、任意のノードへの参照が木全体を生存させる機構に利用されています。

            /// A core data of a tree.
///
/// This also represents an ownership of a tree. Every tree has just one
/// corresponding `TreeCore`.
///
/// A value of this type is shared among nodes in the tree, so this will be
/// referred as `Rc<RefCell<TreeCore<T>>>` or `Weak<RefCell<TreeCore<T>>>`.
pub(crate) struct TreeCore<T> {
    /// Root node.
    root: RefCell<IntraTreeLink<T>>,
    /// Hierarchy lock manager.
    lock_manager: HierarchyLockManager,
}

/// A reference to the tree, with shared ownership.
pub struct Tree<T> {
    /// A reference to the tree core.
    core: Rc<TreeCore<T>>,
}
          
dendron v0.1.5 における TreeCore 型の定義 (解説用にコメントを一部改変) (TreeCore, Tree)

MembershipCore

MembershipCore まわりには、 dendron で最も重要なアイデアが実装されています。

MembershipCore 型は、ノードが自身の属する木を知るための、また必要に応じて木の生存を担保するための型です。 この図において、点線は弱参照 (std::rc::Weak のような、参照先の生存を保証しない参照)、実線は強参照 (std::rc::Rc のような、参照先の生存を保証する参照) です。 ただしこの強弱の参照の区別は、 Rc / Weak の機構だけでなく、自前の参照カウント機構も加えた二段階の管理によって実現しています。

MembershipCore から TreeCore への参照が強参照 (実線) になっている箇所と弱参照 (点線) になっている部分があることに注目してください。 この参照は、後で解説する Node 型から参照されているときにだけ強参照になるようコントロールされています。 こうすることで、「木のノードがひとつでも Node 型としてユーザから参照されていれば、 (間接的に TreeCore の所有権も共有されるため) 木全体が生存し続ける」という状況を作ることができます。

            /// A membership of a node to a tree.
///
/// Note that nodes may change its affiliation to another tree. In this case,
/// membership should also be changed for all `Node` objects referring to the
/// node, so this will be usually shared as `Rc<RefCell<<T>>>`.
enum MembershipCore<T> {
    /// Non-owning reference to the tree core.
    ///
    /// If there are no `Node<T>`s for the node, the membership will stay in
    /// this state.
    // ↓`Node<T>` がないときには弱参照を持っておく
    Weak {
        /// A weak reference to the tree core.
        tree_core: Weak<TreeCore<T>>,
    },
    /// Shared owning reference to the tree core, and strong refcounts.
    ///
    /// If there are any `Node<T>`s for the node, the membership will stay in
    /// this state.
    // ↓`Node<T>` がある間は強参照を持つ
    Strong {
        /// A strong reference to the tree core.
        tree_core: Rc<TreeCore<T>>,
        /// Strong reference count for the tree core from this membership.
        tree_refcount: NonZeroUsize,
        /// Lock aggregator.
        lock_aggregator: LockAggregatorForNode,
    },
}

/// A reference to the membership of a node, with strong ownership of a tree.
#[derive(Debug)]
pub(crate) struct Membership<T> {
    /// Target membership core.
    inner: Rc<RefCell<MembershipCore<T>>>,
}

/// A reference to the membership of a node, without ownership of a tree.
#[derive(Debug)]
pub(crate) struct WeakMembership<T> {
    /// Target membership core.
    inner: Rc<RefCell<MembershipCore<T>>>,
}
          
dendron v0.1.5 における Membership 型関係の定義 (解説用にコメントを一部改変) (MembershipCore, Membership, WeakMembership)

MembershipWeakMembership はフィールドだけ見ると同じですが、値の作成であったり CloneDrop トレイトの実装であったりなどの関数実装で差があります。 Membership は「木が必ず生存していて Rc<TreeCore<T>> を必ず取得できる」という状況でのみ存在でき、作成や破棄で参照カウント (tree_refcount) の増減を引き起こします。 一方 WeakMembership は木が今もまだ存在しているということを強制も保証もしません。

また、 NodeCore から MembershipCore への参照も、意図せぬ循環参照を防ぐため WeakMembership で保持されています。 木を生存させるか決めるのはあくまで Node 型を扱うユーザなのであって、ユーザから参照されていないノードは木に生かされる立場ではあっても木を生かす立場ではないのです。

Node が木 (TreeCore) への参照を直接持たないのは、ノードが木から分離されたときに備えてです。 たとえば node0: Node<i32>node1: Node<i32>node_i: NodeCore<i32>tree_i0: TreeCore<i32> を直接に参照していたとしましょう。 ユーザが node0 経由で node_i を別の木 tree_i1: TreeCore<i32> に移動した場合を考えると、 node1node_i が所属する木が変わったことに気付かないまま tree_i0 への参照を持ち続けてしまうことになり、不整合状態になってしまいます。 このような木とノードのミスマッチを防ぐため、必ず対象のノードの情報を経由して木へアクセスするようにしているのです。

Node

Node 型は、ノードやその属する木を強制的に生かす仕組みを持ったスマートポインタです。

            /// A shared owning reference to a node.
pub struct Node<T> {
    /// Target node core.
    intra_link: IntraTreeLink<T>,
    /// Membership of a node with ownership of the tree.
    membership: Membership<T>,
}

/// A [`Node`] with a tree hierarchy edit prohibition bundled.
pub struct FrozenNode<T> {
    /// Target node core.
    intra_link: IntraTreeLink<T>,
    /// Membership of a node with ownership of the tree.
    membership: MembershipWithEditProhibition<T>,
}

/// A [`Node`] with a tree hierarchy edit grant bundled.
pub struct HotNode<T> {
    /// Target node core.
    intra_link: IntraTreeLink<T>,
    /// Membership of a node with ownership of the tree.
    membership: MembershipWithEditGrant<T>,
}
          
dendron v0.1.5 における Node 型関係の定義 (解説用にコードを一部改変) (Node, FrozenNode, HotNode)

Node 型は一番プレーンなもので、木構造の編集を許可も拒否もしません。 FrozenNode 型は、作成の際に木に対して木構造の編集を拒絶するようなロックをかけ、また破棄される際にロックを解放します。 HotNode 型は逆に、作成の際に木に対して木構造の編集を許可する (正確には「木構造の編集の拒絶を拒絶する」) ようなロックをかけ、また破棄される際にロックを解放します。

NodeIntraTreeLink を持っているのに Membership まで持っているのは無駄に思われるかもしれません。 実際これは何が何でも必要というわけではなく、単に実装で誤りづらくするための選択です。 真面目に書けば NodeCoreMembership は分離されている必要すらないはずですが (何故なら常に一対一対応するものだからです)、そのような実装にするとすべての関数で「この瞬間にノードや関数は破棄された後である可能性があるか」のようなことに気を配る必要があり、エンバグのリスクが高くなります。 そのため、初期の実装ではオーバーヘッドがあっても型システムによる保証を与えるようにして、まともに動作する段階まで持っていく方を優先しました。 ただし現状では問題なく動いていそうなので、将来的にはこの辺りはもっと効率化するかもしれません。

まとめ

大雑把で説明しなかった部分も多くありましたが、ひとまず根本的な原理の部分は解説しました。 一度思い付いてしまえば単純なもので、何故いままで誰も実装していなかったのか不思議なくらいです[1]

dendron を実装することで、以下のような良い性質を持つ木構造ライブラリが手に入りました。

最近ちょっとした文書編集のライブラリみたいなのを書きかけているので、その中で使ったりしています。 自分で実装したライブラリだと新規設計で始められるし機能追加や不具合修正もすぐにできるので、全体的にとても楽です。 皆さんも既存実装に不満があったらさっさと代替を書いて公開してしまいましょう。

最後に再掲: