Advent of Code 2024 を完走した

Algorithm Puzzle

毎年12月に開催されている Advent of Code に、2019年から参加している。

過去記事:

2024年のAdvent of Codeにも挑戦し、今年も無事に25日すべての問題に解答して 50 個のスターを集めることができた。

やった！！！ I really enjoyed this year as well. Thanks @was.tl, and happy 10th anniversary! / I just completed all 25 days of Advent of Code 2024! #AdventOfCode adventofcode.com

[image or embed]

— すぎゃーん (@sugyan.com) December 25, 2024 at 11:46 PM

2015年から始まっているAdvent of Codeは今年で10回目、ということで今までの歴史を振り返りながら過去に登場した場所や登場人物などと再会しながら進んでいくストーリーだった。自分はここ5年くらいしかやっていないので半分くらい知ってる、という感じ。もちろん過去の問題は解いていなくても関係なく挑戦できるので、まだ挑戦したことのない方は是非やってみてほしい。

今年はそこまで難しい問題や 異常に実装が大変な問題はなかった、という印象だが、day17, day21, day24あたりは「なんとなく実装して正解は出せたけど よく分かっていなくて自信ない」みたいな感じだったり。後でRedditなど参照しながらちゃんと復習したい。 day14はpart2が予想外すぎて笑った。

今のところはRustでだけ解いているが、他の言語でも解き直したりしつつ解答メモも最後まで完成させたいところ。

publish.obsidian.md

Repository

ブラウザで動く3D螺旋葉序シミュレータ

TypeScript React Three

先日、Eテレ「ミミクリーズ」で、「あのもよう」という回が放送されていたのを子と一緒に観た。

www.nhk.jp

その中で、自然界に出現する不思議な模様として黄金比・黄金角によって作られる模様を紹介していた。 実際に木に模した棒に等間隔で等角度ずつずらして順番に葉をつけていくと、どのような模様になるか、といったシミュレーションをしていて面白い。

用語としては「葉序 (Phyllotaxis)」というらしい。

en.wikipedia.org

ja.wikipedia.org

これをブラウザ上で同じようにシミュレーションできるものがあると便利だな、と思い作ってみることにした。

成果物

sugyan.com

3Dで木の幹(植物の茎)と、まわりに等間隔で伸びる葉が描画され、マウスやタッチ操作で回転/拡大縮小させることができる。 葉の数、そして葉と葉の間の角度(開度 と呼ぶらしい？)を変更するとリアルタイムで描画が更新される。

プリセットの角度として、黄金角(約137.5° = 360 * (1 - 1 / Φ))や、キレイに重なる π/4 などを選択できる。

少しずつ動かしてみると色々な模様と変化を観測できて意外と楽しい。

開発

使っているのは Vite + React + TypeScript, Three.js, あと Tailwind。

フロントエンド不慣れな自分でも、ChatGPTのおかげで3時間くらいで作れた。ありがたい。

とにかく3D空間内に葉を薄い円柱で表現して配置していく。角度をθとすると、n番目の葉の位置は (r * cos(θ * n), r * sin(θ * n), n * h) といった感じで求められる。あとは高さに合わせて半径rをちょっと調整したり。

Reactによって inputの値が変更された場合にそれを反映する。どうやるのかな、と思ったがカメラや光源やrendererはそのまま変えずに済むよう、useRef で THREE.Scene を保持しておいて、そこから children を一度削除して新しいパラメータで再配置、という方法で実現できた。 オブジェクトの数が変わらない場合は座標や角度を変更するだけにする、といった最適化もできたかもしれないけど、まあいいか。

ただ削除は簡単ではなく、ループで回しながら条件にあるものを remove() していくと何故か消え残るものがあったり、まとめて消すようにしてみても何度も削除&再配置を繰り返すとメモリがどんどん枯渇していってフリーズしたり、といった問題にぶつかった。結局削除する場合はただ scene から remove() するだけでなく、それぞれ geometry や material を明示的に disopose() する必要があったようだ。 そのあたりを改善した結果、スマホでもサクサク動くようになったと思う。

Repository

「だんご屋のひまつぶし」完全解析

Rust Algorithm Puzzle

「だんご屋のひまつぶし」とは

「ハノイの塔」の派生型のようなパズル。 高さ3の串が3本あり、3色の団子2個ずつ計6個が刺さっている。これらを1個ずつ移し替えて、ある状態からある状態へと遷移させる、というゲーム。

  • 移動できるのは各串で一番上にある団子だけ。
  • 団子の大きさのような概念はなく、高さ3以内であればどこにでも動かせる。

単純なルールだがなかなかに奥が深く、じっくり考えて動かさないと最適な手順で達成するのは意外に難しい。

パズルオーディションというもので最優秀賞を受賞した作品らしい。 www.jpuzzle.jp

これがめでたく商品化されたもの、のようだ。

ビバリー(BEVERLY) 【最優秀賞受賞】 だんご屋のひまつぶし 脳トレパズル ビバリー お部屋においてもかわいいスタンド付き

ビバリー(BEVERLY) 【最優秀賞受賞】 だんご屋のひまつぶし 脳トレパズル ビバリー お部屋においてもかわいいスタンド付き

Amazon

最長手順の問題は…？

「だんご屋のひまつぶし」の中には問題集が同梱されており、始点と終点を指定した全52問の問題が収録されている。序盤の「初級」は最短5〜6手程度だが、最後の「特級」は最短でも14手の手順が必要なものとなっている。

ここで疑問が湧いたので考えてみることにした。

「だんご屋のひまつぶし」というパズルを妻が見つけて、面白そうだったので買ってみた。(知育にもなるかな？と思ったが子どもたちは団子をぶん投げて遊ぶだけだった…。) be-en.co.jp/products/bog... ルールは簡単で、高さ3の3本の串に積まれた2個ずつ3色のだんごを、1個ずつ他の串に移動して ある状態からある状態に変えられるか、というもの。同梱の問題集には難易度ごとに52問のものが載っている。 最高難度のものは14手、だったのだが 果たしてこれが最長なのだろうか？という疑問が湧いたので考えてみたい。

[image or embed]

— すぎゃーん (@sugyan.com) October 9, 2024 at 10:20 PM

組み合わせ、グラフ問題

まず、この「(高さ3)×(3本)の串に、(3色)の団子(2個)ずつを積む」という条件で、何種類の状態があるかを考える。

だんごの数の配置だけを考えると、左から [3, 3, 0] の他、

  • [3, 0, 3], [0, 3, 3] の2本が埋まって1本が空のパターン
  • [2, 2, 2] の同数で埋まっているパターン
  • [3, 2, 1], [2, 3, 1], ... のようなパターン å…¨6通り

で合計 10通り が存在することがすぐにわかる。 (ちなみに問題集では 最後の [3, 2, 1] のようなパターンが始点・終点に指定されるものは存在していない)

次に6個の団子の並び方を考える。 最初の色で6個のうち2個を選ぶのが 6C2 = 15 通り、次の色で残った4個から2個を選ぶのが 4C2 = 6 通り、最後の色は 2C2 = 1 通りで、これらを掛け合わせた 15 * 6 * 1 = 90 通りが存在する。

よって、それぞれの配置パターン10通りに、それぞれ90通りの並び方が存在するので、有り得る状態の組み合わせは全部で 900通り となる。

ある状態から団子を他の串へ移動する操作は、この900通りある中で別の状態へと遷移する操作、ということになる。1回の操作で遷移できる状態同士を辺として繋ぐことで、900頂点の無向グラフを構築することができる。 そうすると、「ある状態からある状態へ遷移させる最短の手順」は、このグラフ上での最短経路を求めることに相当する。

ということで、このパズルの問題の最適解の導出はすべてグラフ上での最短経路問題であり、最長手順の問題を考えるのは、このグラフの「直径」を求めることに相当する。

プログラムで解く

最短経路を求めるグラフ問題と分かれば、プログラムで簡単に解くことができる。

状態の列挙

まずは、900通りの全状態を列挙する。

並び替えの列挙は、ここでは同色のものを区別しないため、先にそれぞれの個数をカウントしておいてからそれを使ってbacktrackingで列挙する。

use std::collections::BTreeMap;

pub fn unique_permutations(elems: Vec<u8>) -> Vec<Vec<u8>> {
    fn backtrack(
        n: usize,
        curr: &mut Vec<u8>,
        counts: &mut BTreeMap<u8, u32>,
        result: &mut Vec<Vec<u8>>,
    ) {
        if n == 0 {
            return result.push(curr.clone());
        }
        for key in counts.keys().copied().collect::<Vec<_>>() {
            if counts[&key] == 0 {
                continue;
            }
            counts.entry(key).and_modify(|e| *e -= 1);
            curr.push(key);
            backtrack(n - 1, curr, counts, result);
            curr.pop();
            counts.entry(key).and_modify(|e| *e += 1);
        }
    }

    let mut result = Vec::new();
    let mut counts = BTreeMap::new();
    for &elem in &elems {
        *counts.entry(elem).or_insert(0) += 1;
    }
    backtrack(
        elems.len(),
        &mut Vec::with_capacity(elems.len()),
        &mut counts,
        &mut result,
    );
    result
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_unique_permutations() {
        let perms = unique_permutations(vec![1, 1, 2, 2, 3, 3]);
        assert_eq!(perms.len(), 90);
    }
}

そして、配置個数のパターンは上限つきの整数分割の列挙となる。こちらはbacktrackingするまでもないので再帰関数だけで列挙する。

pub fn bounded_partitions(len: usize, upper_limit: u32, target_sum: u32) -> Vec<Vec<u32>> {
    fn recursive(
        i: usize,
        upper_limit: u32,
        remain: u32,
        curr: &mut Vec<u32>,
        results: &mut Vec<Vec<u32>>,
    ) {
        if i == 0 {
            if remain == 0 {
                results.push(curr.clone());
            }
            return;
        }
        for n in 0..=upper_limit.min(remain) {
            curr[i - 1] = n;
            recursive(i - 1, upper_limit, remain - n, curr, results);
        }
    }

    let mut results = Vec::new();
    recursive(
        len,
        upper_limit,
        target_sum,
        &mut vec![0; len],
        &mut results,
    );
    results
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_bounded_partitions() {
        let partitions = bounded_partitions(3, 3, 6);
        assert_eq!(partitions.len(), 10);
    }
}

これでそれぞれ列挙できたので、あとはこれらを組み合わせて各並び換えから各配置パターンを適用する。

    let permutations = unique_permutations(vec![1, 1, 2, 2, 3, 3]);
    for stacks in bounded_partitions(3, 3, 6)
        .iter()
        .flat_map(|partition| {
            permutations.iter().map(|p| {
                let mut stacks = vec![Vec::new(); 3];
                let mut iter = p.iter();
                for (i, num) in partition.iter().enumerate() {
                    for _ in 0..*num {
                        stacks[i].push(*iter.next().unwrap());
                    }
                }
                stacks
            })
        })
    {
        println!("{:?}", stacks);
    }

これで900通りの状態が全列挙できる。

[[1, 1, 2], [2, 3, 3], []]
[[1, 1, 2], [3, 2, 3], []]
[[1, 1, 2], [3, 3, 2], []]
[[1, 1, 3], [2, 2, 3], []]
[[1, 1, 3], [2, 3, 2], []]
[[1, 1, 3], [3, 2, 2], []]
[[1, 2, 1], [2, 3, 3], []]
[[1, 2, 1], [3, 2, 3], []]
[[1, 2, 1], [3, 3, 2], []]
[[1, 2, 2], [1, 3, 3], []]
[[1, 2, 2], [3, 1, 3], []]
[[1, 2, 2], [3, 3, 1], []]

...

ちなみに Pythonなら itertools とかを使って3行くらいで全列挙できそう。

>>> from itertools import islice, permutations, product, repeat
>>> for perm, part in product(sorted(set(permutations([1, 1, 2, 2, 3, 3]))), (a for a in product(*repeat(range(4), 3)) if sum(a) == 6)):
...     it=iter(perm)
...     print(*tuple(list(islice(it, n)) for n in part))
...
[] [1, 1, 2] [2, 3, 3]
[1] [1, 2] [2, 3, 3]
[1] [1, 2, 2] [3, 3]
[1, 1] [2] [2, 3, 3]
[1, 1] [2, 2] [3, 3]
[1, 1] [2, 2, 3] [3]
[1, 1, 2] [] [2, 3, 3]
[1, 1, 2] [2] [3, 3]
[1, 1, 2] [2, 3] [3]
[1, 1, 2] [2, 3, 3] []
[] [1, 1, 2] [3, 2, 3]
[1] [1, 2] [3, 2, 3]
[1] [1, 2, 3] [2, 3]

...

グラフの構築

次に、各状態間の遷移を辺としたグラフの構築を考える。 Vec をstackとして利用して、空でないstackから1つ pop して その要素を高さが上限に達しない他のstackへ push する、という操作で遷移先の状態を得られる。全状態に対して可能な全遷移を列挙する必要があるが、1状態から遷移可能なのは移動元の串の選択肢が3本で移動先がの選択肢が残る2本なので高々6通り。

#[derive(Hash, Eq, PartialEq)]
struct State([Vec<u8>; 3]);

impl State {
    pub fn next_states(&self, max_len: usize) -> Vec<Self> {
        let mut results = Vec::new();
        for i in 0..3 {
            for j in 0..3 {
                if i == j || self.0[i].is_empty() || self.0[j].len() == max_len {
                    continue;
                }
                let mut v = self.0.clone();
                let ball = v[i].pop().unwrap();
                v[j].push(ball);
                results.push(Self(v));
             }
         }
        results
     }
}

あとは全900通りの状態に振ったindexを使って、それぞれの状態から遷移可能な状態のindexの配列を持つようにしておくと、その後の計算が楽になる。

use std::collections::HashMap;

struct Graph {
    nodes: Vec<State>,
    edges: Vec<Vec<usize>>,
}

impl Graph {
    pub fn new(nodes: Vec<State>, max_len: usize) -> Self {
        let mut edges = vec![Vec::with_capacity(6); nodes.len()];
        let node_map = nodes
            .iter()
            .enumerate()
            .map(|(i, node)| (node, i))
            .collect::<HashMap<_, _>>();
        for src in &nodes {
            for dst in src.next_state(max_len) {
                edges[node_map[src]].push(node_map[&dst]);
            }
        }
        Self { nodes, edges }
    }
}

これで、 900頂点 3,240辺のグラフが構築できた。

最短経路問題を解く

あとは、有名な Dijkstra's algorithm を使えば、任意の始点から各頂点への最短距離(とその経路も)を求めることができる。

use std::cmp::Reverse;
use std::collections::BinaryHeap;

impl Graph {
    fn distances(&self, src: usize) -> Vec<Option<u32>> {
        let mut distances = vec![None; self.nodes.len()];
        let mut bh = BinaryHeap::new();
        distances[src] = Some(0);
        bh.push((Reverse(0), src));
        while let Some((Reverse(d), i)) = bh.pop() {
            for &j in &self.edges[i] {
                if distances[j].is_none() {
                    distances[j] = Some(d + 1);
                    bh.push((Reverse(d + 1), j));
                }
            }
        }
        distances
    }
}

グラフの直径、すなわち全頂点対に対する最短経路のうち最長のもの、を求めるには Floyd–Warshall algorithm がよく知られていると思うが、このグラフの場合は頂点数に対して辺数が少なめなので、全頂点を始点としてDijkstraを使った方がむしろ計算量は少ないようだった。

どちらにしろこの程度の規模なら手元のPCでも十分に速く、900 * 900 = 810,000 通りのすべての始点・終点の組み合わせでの最短距離を求めるのに 50ms程度で計算が終わる。

そして以下のような結果が得られた。

distance  0:    900
distance  1:   3240
distance  2:   7128
distance  3:  13716
distance  4:  21924
distance  5:  32544
distance  6:  48636
distance  7:  72684
distance  8:  90162
distance  9:  99990
distance 10: 115788
distance 11: 108144
distance 12:  88266
distance 13:  66816
distance 14:  33618
distance 15:   6264
distance 16:    180

total: 810000

ということで、最短手順が16手の組み合わせが存在することが分かった。

WASM化して、ブラウザ上で解く

この程度の計算量ならJavaScriptで書いてもそれなりに速く動くとは思うが、せっかくRustで書いたので wasm-pack を使ってWASMにして、ブラウザ上で動かしてみることにした。

始点と終点をドラッグ&ドロップで編集すると、瞬時に最短手順を解いて示してくれる。URLのqueryで指定もできる。

例えば、最長の16手の問題とその最短解の例。

WASMをロードしてグラフまで構築してしまえば、始点指定してのDijkstraは百μs程度で探索できるのでWebWorkerなどに移譲する必要すら無い。 各nodeへの最短距離を計算する際に遷移元のnode情報も記録しておけば、再帰的に逆に辿ることで経路も(あくまで1例だが)求めることができる。

もしもすべて異なる団子だったら

ここからは「だんご屋のひまつぶし」から離れて考えていく。

「3色の団子2個ずつ計6個」という条件で計算していたが、これがもし「すべて異なる6色」に塗り分けられているものだったらどうなるだろうか。

団子の総数は変わらないので配置パターンは同じ10通りだが、並べ替えの列挙が 6C2 * 4C2 * 2C2 = 15 * 6 * 1 = 90 通りだったのが、 6! = 720 通りに増えることになる。つまり状態数が8倍の 7200通り に増えることになる。

上述のようなプログラムで解く場合、 vec![1, 1, 2, 2, 3, 3] としていた入力を vec![1, 2, 3, 4, 5, 6] に変えるだけで良い。 7,200頂点 25,920辺 のグラフが構築され、最長19手の問題が存在することが分かる。

distance  0:    7200
distance  1:   25920
distance  2:   64800
distance  3:  138240
distance  4:  257040
distance  5:  437760
distance  6:  738720
distance  7: 1311120
distance  8: 2088720
distance  9: 2954880
distance 10: 4080240
distance 11: 5700240
distance 12: 6947280
distance 13: 7223040
distance 14: 7778160
distance 15: 6809760
distance 16: 3745440
distance 17: 1298160
distance 18:  224640
distance 19:    8640

total: 51840000

最長19手は 8,640通りがあるが、始点を [[1, 2, 3], [4, 5, 6], []] のように固定すると4通りだけに絞られ、あとはこれらの並び順や配置される串が入れ替わるだけで本質的に同じ問題となる。

どれも1番下の団子同士が入れ替わり、2段目にあったものは3段目のどちらかに、3段目にあったものは2段目のどちらかに入れ替わる、という操作のもののようだ。

さらに一般化していくと

「高さ3の3本の串に」という条件も変えていってみる。 高さHの N本の串に、H * (N - 1)色の団子を積む、と考えるとどうだろうか。任意の状態に遷移可能だろうか。

到達可能性

最大で H * N の空間となるが、少なくとも H個分の隙間はないと一番下の団子を移動することができないので任意の状態に遷移することは不可能になる。 団子はH * (N - 1)個以下であることは必須だ。

Nは 3以上である必要がありそうだ。「高さ2で2本で2色の団子」の場合を考えると明らかに1本の中で積まれた2色の団子を入れ替える操作が不可能。3本あればどれかを退避させて入れ替える手順が可能になりそうだ(証明は略)。

3本を使って任意の位置のものを一番下に潜り込ませる手順の存在を示すことさえできれば、それを繰り返すことで残りは高さH-1の問題に帰着できる。高さ1で3本なら明らかに任意の状態に遷移可能なので、帰納法で証明できるかもしれない。おそらく3本あればどんな高さでも可能そう。

任意の3本の間で任意の状態に遷移可能であれば、N+1本になってもやはり遷移可能になるはずだ。

従って、ちゃんと証明はできていないけど おそらく「高さHの N本の串に、H * (N - 1)色の団子を積む」というルールは N >= 3 であれば任意の状態に遷移可能である、ということになるだろう。

頂点数

ではそれらの場合に、有り得る状態の総数、つまりグラフの頂点数はどうなるだろうか。

団子の並び方は、 (H \times (N - 1))! 通り。 N = 3, H = 3 なら 6! = 720 通りだった。 配置パターンは、N本の串に H * (N - 1)個の団子を配置する場合の上限つき整数分割の列挙となるが、これは逆にH個分の隙間をどの串に分割するか、と考えた方が簡単。 H個のものをN個に分割するのであれば、N-1個の仕切りとH個の隙間の並べ替えの数となる。これは \binom{H + N - 1}{H} と計算できる。

よって、これらを掛け合わせた (H \times (N - 1))! \times \binom{H + N - 1}{H} が全状態数となる。

>>> from math import comb, prod
>>> f = lambda n, h: prod(range(1, h * (n - 1) + 1)) * comb(n + h - 1, h)
>>> f(3, 3)
7200
>>> f(3, 4)
604800

N = 3 なら

H = 1:          6
H = 2:        144
H = 3:      7,200
H = 4:    604,800
H = 5: 76,204,800

と高さ5でかなりの計算量になることが見込まれる。

N = 4 だと

H = 1:                 24
H = 2:              7,200
H = 3:          7,257,600
H = 4:     16,765,056,000
H = 5: 73,229,764,608,000

N = 5 だと

H = 1:                         120
H = 2:                     604,800
H = 3:              16,765,056,000
H = 4:       1,464,595,292,160,000
H = 5: 306,545,653,030,256,640,000

となり、高さ3でもちょっと計算量が大変なことになりそうだ…。団子の個数が増えるととにかく大変。

数千万になってくると計算が少しでも速くなるよう工夫が必要で、複数のStackを使うかわりに高さが8を超えない前提で u64 に8bitずつ詰めて固定数の u64配列で表現したり、それらを格納する HashMap が標準だと遅いので ahash を使って高速化したり、といったチューニングを施した。

本数を固定し、高さを変える

N = 3 で固定して、高さHを変えるとどうなるだろうか。

H = 3 は前述した通り、 7,200頂点 25,920辺 のグラフで 19手が最長の問題だった。

H = 4 だと 604,800頂点 2,419,200辺 のグラフになる。 最長手数は 27手で、[[1, 2, 3, 4], [5, 6, 7, 8], []] のように2本を埋めているものから初めるパターンは11通り存在するようだった。

例:

H = 5 だと 76,204,800頂点 326,592,000辺 のグラフになる。 最長手数は 36手で、同様に6通りほど見つかる。

例:

ちょっと法則は見つからなかったが、少なくとも「ハノイの塔」のように指数関数的に手数が増えるということはなさそうだ。

高さを固定し、本数を変える

H = 3 だと計算量が膨大になるので、 H = 2 で固定して N を変えてみる。

N = 3 だと 144頂点 432辺 のグラフになる。 最長は 10手 になる。

N = 4 だと 7,200頂点 34,560辺 のグラフになる。最長は 15手 で、これは [[1, 2], [3, 4], [5, 6], []] のような形ではなく [[1, 2], [3, 4], [5], [6]] のような形から始めるパターンだけで現れるようだ。

N = 5 だと 604,800頂点 4,032,000頂点 のグラフになる。最長は 19手 で、これもやはり [[1, 2], [3, 4], [5, 6], [7], [8]] のような形からのものだ。

H = 2, N = 4 は H = 3, N = 3 と同じ頂点数だが、辺数が多くなり最長手も短い。 同様に H = 2, N = 5 も H = 3, N = 4 と同じ頂点数だが、辺数が多くなり最長手も短い。高さが無いぶん深く掘るような面倒な手順が減るだろうから、それはそうか。

まとめ

  • 「だんご屋のひまつぶし」という面白いパズルがある
  • グラフ問題としてプログラムで解くことができる
  • 問題集では14手の問題が載っていたが、16手の問題が存在することが分かった
  • Webブラウザで動く、一瞬で最短経路を求めることができるものを作った
  • 団子の色がすべて異なる場合、串が増えた場合、串がより高くなった場合などについて考察した

Repository

BlueskyのTUI Client Appを作り始めてしまった

Rust ATProto ATrium Bluesky TUI

memo.sugyan.com

の続き…？

I've published `tuisky`, a TUI Client for Bluesky, as v0.0.1. (It's still a work in progress.) Were there already other clients available for use in the terminal? #atdev #bluesky-client #tui crates.io/crates/tuisky

[image or embed]

— すぎゃーん (@sugyan.com) Jul 1, 2024 at 12:12 AM

経緯

TauriでのDesktop Clientはある程度動くところまで出来たが、問題点も発覚してきた。

大きくはmulti columnへの対応問題。React Routerで画面管理していたが、複数の画面を管理することになると厄介そう。 そもそもの問題点として、フロントエンドとバックエンドで画面状態やデータをどう持つか、が上手く役割分担できていなくて中途半端で複雑になってしまっていた。

↓

なので、まずはバックエンド側での状態保持やデータ更新の仕組みを整理して作り直してみよう、と思い立った。

↓

だが、その動作確認にいちいちTauriビルドしてフロントエンドで表示して…というのが面倒だなと思い。 一旦Tauriから離れてターミナル上だけでどうにかしたくなった。

↓

しかしunit testだけで完結するのも難しく、動作確認のための何らかの表示UIは欲しい。

↓

そこで TUI(terminal user interfaces)。

最近のTUIフレームワークなど全然知らなかったが、それなりに高機能なものも作れそうで面白そうだったので、やってみることにした。

RatatuiによるTUI開発

選択したのは Ratatui。

ratatui.rs

詳しい経緯は知らないが、元々は tui-rs という個人で作られた人気ライブラリがあったが、メンテナンスできなくなってきた結果コミュニティでforkして引き続き開発されている、というもののようだ。いい話(？)。

有名どころでは bottom などで使われているっぽい。

Ratatuiの主な特徴としては、複数のターミナルライブラリをbackendとして選択でき、UI widgetを配置して描画するための枠組みを提供している(そして基本的なwidgetがbuilt-inされている)、というところだろうか。

ターミナルのbackendは crossterm, termion, そして termwiz の3つから選択できるようだが、基本的にはcrosstermを使っておくのが無難そうだ。

Comparison of Backends | Ratatui

Asynchronous Event Handling

Ratatuiで簡単なTUIアプリケーションを作る場合、以下のようなループ処理を書くだけで実装できる。

    loop {
        terminal.draw(|frame| {
            // draw the UI
        })?;
        match event::read()? {
            Event::Key(key_event) if key_event.kind == KeyEventKind::Press => {
                // handle key events
            }
            _ => {}
        };
    }

メインのループの中で描画処理があり、キー操作などのEventを待ち受けて、そのEventによって状態変更するなどして描画内容を更新する、という基本的な流れ。

だが、このような作りだとEventを受け取るまでblockingして待ち続けるしかないし、バックグラウンドで処理されたものをUIに反映させるのも難しい。

より複雑なアプリケーションを作る際には、非同期Event処理を導入する。

Full Async Events | Ratatui

crossterm には event-stream featureがあり、これを有効にすることで非同期でEventを受け取ることができるようになる。

use futures::{FutureExt, StreamExt};
use tokio::{sync::mpsc, task::JoinHandle};

fn async_events() {
    let task = tokio::spawn(async move {
        let mut reader = crossterm::event::EventStream::new();
        let mut interval = tokio::time::interval(std::time::Duration::from_millis(250));
        loop {
            let delay = interval.tick();
            let crossterm_event = reader.next().fuse();
            tokio::select! {
                maybe_event = crossterm_event => {
                    match maybe_event {
                        Some(Ok(evt)) => {
                            ...
                        }
                        _ => { ... }
                    }
                },
                _ = delay => {
                    ...
                },
            }
        }
    });
    ...
}

このようにして、 crossterm からのEventを非同期で待ち受けることができるし、定期的なEventなども tokio::select! によって非同期で受け付けられるようになる。あとはここから tokio::sync::mpsc::unbounded_channel() などを使ってメインのUIスレッドに通信することでそれらを処理できるようになる。 キー操作など受け付けつつ定期的に描画するEventを発火させることで安定した画面更新もできるし、逆に特定のEventが発生しない限り無駄な描画をしない、といった調整も可能だ。

Components Architecture

様々なUI widgetを使用して複雑なアプリケーションを作る場合の設計パターンとして、幾つかのアーキテクチャが提案されている。その中の一つとして、「Component Architecture」というものがある。

Component Architecture | Ratatui

Component というTraitを定義し、これが

  • 初期化
  • 設定やAction handlerの登録
  • Event handling
  • Actionを受けての状態更新
  • Rendering

などのメソッドを持つ。メインのApp内でこれを実装した components を Vec<Box<dyn Component>> で持つようにして、メインループ内で「Eventを渡しActionを受ける、そのActionを処理して状態を更新、そして描画」という流れをそれぞれのComponentに対し透過的に行うようにする設計だ。

impl App {
  pub async fn run(&mut self) -> Result<()> {
    ...
    // componentsの初期化など 事前準備
    for component in self.components.iter_mut() {
      component.register_action_handler(action_tx.clone())?;
    }
    for component in self.components.iter_mut() {
      component.register_config_handler(self.config.clone())?;
    }
    for component in self.components.iter_mut() {
      component.init(tui.size()?)?;
    }
    // メインループ
    loop {
      // Event処理 (Actionへの変換)
      if let Some(e) = tui.next().await {
        ... // メインのEvent処理
        for component in self.components.iter_mut() {
          if let Some(action) = component.handle_events(Some(e.clone()))? {
            action_tx.send(action)?;
          }
        }
      }
      // Action処理
      while let Ok(action) = action_rx.try_recv() {
        match action {
          ...
          Action::Render => {
            // 各Componentの描画
            tui.draw(|f| {
              for component in self.components.iter_mut() {
                component.draw(f, f.size());
              }
            })?;
          }
        }
        for component in self.components.iter_mut() {
          if let Some(action) = component.update(action.clone())? {
            action_tx.send(action)?
          };
        }
      }
      if self.should_quit {
        break;
      }
    }
    Ok(())
  }
}

それぞれのComponentが独立したAppとして動作する感じになり、新しい要素を追加する場合も Component Traitを実装して components に追加するだけで良い。

自作Clientでは、これを参考にアレンジして設計してみた。

自作Client用の設計

機能

まずは盛り込みたかった機能について。

完全に分離された Multi Column

まずやりたかったのが、Multi Columnでの分割表示。ログインセッションなども完全に分離し、互いに干渉しない。あるColumnに対して操作をする際はそれ以外のColumnは表示のみで同時に操作することは無い。

履歴を保持しての画面遷移

Feedの一覧からPost詳細を見て、ThreadのReplyなどを辿り、またPost詳細を見てそのユーザのAuthorFeedを見て…、そしてまた最初のFeedまで戻って、と ブラウザで遷移して履歴から戻るような操作を各Columnで

Feedなどの自動更新

自分で操作しなくても定期的に新しいFeedを取得して自動で更新してくれる機能。

FocusとColumnを管理する MainComponent

まず適当に画面を縦に分割して複数のColumnを作るが、前述のComponents Architectureでそのまま各Columnを実装すると、どのColumnもすべて同じEventを受けて同じActionを処理してしまうことになる。

なので、このMainComponentでそこを整理して各ColumnへのEventやActionの伝達を行うようにした。

struct State {
    selected: Option<usize>,
}

pub struct MainComponent {
    columns: Vec<ColumnComponent>,
    state: State,
}


impl Component for MainComponent {
    ...

    fn handle_key_events(&mut self, key: KeyEvent) -> Result<Option<Action>> {
        // 選択中のColumnに対してのみEventを渡す
        if let Some(selected) = self.state.selected {
            self.columns[selected].handle_key_events(key)
        } else {
            Ok(None)
        }
    }
    fn update(&mut self, action: Action) -> Result<Option<Action>> {
        match action {
            Action::NextFocus => {
                self.state.selected = ...;
                return Ok(Some(Action::Render));
            }
            ...
            _ => {
                for column in self.columns.iter_mut() {
                    if let Some(action) = column.update(action.clone())? {
                        return Ok(Some(action));
                    }
                }
            }
        }
    }
}

Eventは選択中のColumnだけに渡すが、Actionは基本的にすべてのColumnに対して伝播させる。操作はしていないが非同期的にデータが更新される、といった場合に通知する必要があるからだ。 そういったもの以外は、受け取るColumn側でIDを保持し、Action発行時に自分のIDを載せるようにした。そして自分のIDと異なるIDのActionは無視するようにしている。

履歴を保持する ColumnComponent

各Columnでは、 ViewComponent Traitを実装したものを Vec<Box<dyn ViewComponent>> で保持し、その末尾要素に対してのみEvent/Actionを渡し、Renderする。 画面遷移するごとに新しいViewComponentを push() し、戻るときには pop() する。 ViewComponent Traitは概ね Component と同じだが、activate() deactivate() というメソッドを追加している。末尾のViewComponentのみActiveな状態として機能し、それ以外は非Activeな状態としてバックグラウンドでのデータ更新などを停止する。

    pub(crate) fn transition(&mut self, transition: &Transition) -> Result<Option<Action>> {
        match transition {
            Transition::Push(view) => {
                if let Some(current) = self.views.last_mut() {
                    current.deactivate()?;
                }
                let mut next = self.view(view)?;
                next.as_mut().activate()?;
                self.views.push(next);
            }
            Transition::Pop => {
                if let Some(mut view) = self.views.pop() {
                    view.deactivate()?;
                }
                if let Some(current) = self.views.last_mut() {
                    current.activate()?;
                }
            }
            ...
        }
        Ok(Some(Action::Render))
    }

設計まとめ

Component Architectureを倣って各Componentsで独立してEvent処理やRenderをできるようにしつつ、

  • Mainでは分割されたColumnsのFocus中のものだけにEventを渡し、またActionの伝播を行う
  • 各Columnでは履歴で最新のものだけをActiveなものとしてEvent処理/描画などを行う

という制御をいれることでMulti Columnで画面遷移を可能にした。

IndexMapを使ったFeed管理

ちょっとだけアルゴリズムとデータ構造的な話を。

Following feedでのtimelineに限った話ではあるけれど、ここではFeedの内容としてfollowingからのPostが流れてくる。 基本的には同じものが流れることは無いが、一つだけ例外があって、followingユーザがRepostしたものだけは同じものが複数回出現し得る。この場合は .post の内容は同一だが .reason が異なるものになる。

で、公式と同様の挙動を実現しようと思うと、表示すべきfeedの配列は

  • 基本的には出現した順に表示される
  • 一意なID(cidなど)で区別され、同一のものは出現しない
  • 既に存在するが.reasonだけ異なるものが出現した場合は、先頭に挿入(移動)される

という形であることが望まれる。 つまり A,B,C,D,B,E という順で出現した場合は、 A,B,C,D の後に B の再出現により A,C,D,B という並びになり、最終的な出力は A,C,D,B,E という表示になる。

基本的には Vec で管理して、既に存在するか否かを毎回 .contains() で検索するか または HashSet でID管理しておけば判定できる。しかし末尾に移動することになると 一旦 .remove() して .pop() する必要があり、そもそも何番目にそれが存在するのかを調べる必要も出てくる。 HashMap でindexを管理するようにすれば良さそうだが 移動によってそのindexも変化するので厳しそうだ。

別に何百万とか何億とかのデータを扱うわけでもないのでそんなにパフォーマンスを気にせず O(N)で処理しても困ることは無さそうではあるが、できるなら効率的に処理したい。

…ってことでどうするのが良いかChatGPTに相談したところ、「Pythonなら OrderedDict を使うことで効率的に処理できます」ということだった。Rustで同等な機能を持つものとして IndexMap があるようだったので、それを使うことにした。

    let mut feed_map: IndexMap<Cid, FeedViewPost> = Default::default();
    for post in feed {
        if let Some(entry) = feed_map.get_mut(&post.post.cid) {
            // Is the feed view a new repost?
            if ... {
                // Remove the old entry
                feed_map.swap_remove(&post.post.cid);
            } else {
                continue;
            }
        }
        feed_map.insert(post.post.cid.clone(), post.clone());
    }

ほぼ HashMap と同様の使い方で、こうして更新されたものから feed_map.values().rev().cloned().collect::<Vec<_>>() といった感じで出現順に並べられたFeedの配列を取得できる。

これなら重複時の移動も O(1)で実現できている、はず？

まとめ

  • Ratatuiを使ってTUIアプリケーションを作ってみた
    • TUIアプリちゃんと作ったことなかったので色々な知見を得られて楽しい
    • ターミナルで色々動かせるとテンション上がる
  • Clientのバックエンド処理を整理してブラッシュアップできそう
  • Blueskyクライアント欲しいだけなのにどんどん寄り道してる

Expressに22個以上の要素の配列クエリを渡すときは気をつける

Rust Node.js

自作ライブラリを使ったBlueskyクライアントを実装していて遭遇したバグ。

ATriumからのfeed.getPostsでurisが21個までなら大丈夫だが22個以上だとエラーになることが発覚した。問題切り分け中… ここまで自作クライアント実装してようやく気付く問題があるんだから やっぱりドッグフーディング大事やな、、

— すぎゃーん (@sugyan.com) Apr 21, 2024 at 10:21 AM

問題の詳細と対応は以下の通り。

Expressで使っている qs が、[] を含むキーのときに配列として扱おうとするが、そのindexの大きさによって結果がarrayではなくobjectになったりする、というもの。 その境界のdefault値が20なので、順番にindexをつけているとuris[0]=...&urls[1]=...&uris[20]=... という 21個までなら問題ないが 22個になると突然objectとして扱われるようになってしまう、と。

www.npmjs.com

確かにindex指定したものを読んでくれるのは便利だが… そんな挙動があると知らずにrequestを送っているとハマる。

const qs = require("qs");

console.log(qs.parse("ids=foo&ids=bar"));
console.log(qs.parse("ids[]=foo&ids[]=bar"));
console.log(qs.parse("ids[0]=foo&ids[1]=bar"));
console.log(qs.parse("ids[1]=foo&ids[0]=bar"));
console.log(qs.parse("ids[20]=foo"));
console.log(qs.parse("ids[21]=foo"));

{ ids: [ 'foo', 'bar' ] }
{ ids: [ 'foo', 'bar' ] }
{ ids: [ 'foo', 'bar' ] }
{ ids: [ 'bar', 'foo' ] }
{ ids: [ 'foo' ] }
{ ids: { '21': 'foo' } }

わりとみんなハマっているようで困っている人も多そうではあるが、とにかくそういう仕様なようなので express なserverにリクエストを送るときは気をつけるしかなさそう。

github.com

BlueskyのDesktop Client Appを作り始めている

Rust ATProto ATrium Tauri React

ATProtocolのRustライブラリを作っている 活動の続きとして、ライブラリの動作確認も兼ねてDesktop Applicationを作ってみることにした。

Tauri

RustでDesktop Application作成、といえば今もっとも普及しているのがTauriだろう。

tauri.app

ステータスとしてはMobile Application対応を含む v2のリリースに向けてBeta versionが公開されている、という状態のようだ。

Tarium

で、AT ProtocolのためのRustライブラリである ATrium をバックエンドで使ったTauri製のBluesky Client、ということで「Tarium」という名前にした。

github.com

Frontend

フロントエンドは各プラットフォームでのWebView上で動くわけで、結局HTMLやJavaScriptで用意することになる。 気合いでFull Rustで実装しようとすれば Yew などで構築することもできるようだったが、自分はまだ使ったことがなく学習が大変そうだったので、結局 Vite + React でTypeScriptで書くことにした。あとは React Router と Tailwind。

Backend

普通にWeb Applicationが作れるので、Bluesky Clientとしてはatproto公式のTypeScriptライブラリを使ってフロントエンドで完結するものも作れてしまう。

しかし自分の目的としては ATriumの動作確認なので、意地でもAT Protocolの処理はバックエンドにやらせることにしている。 結局バックエンドは command を介してフロントエンドからのXRPC Requestをproxyするだけ、になってしまいがちで 何のためにRustバックエンドが存在しているんだ… という感じにはなってしまうけど。

一応役割としては内部のStateとしてAtpAgentを持ってSession管理などをしている、くらい。単にproxyするだけだと悔しいので、feedの取得などはバックグラウンドタスクで定期的に実行して新しく表示すべきものをEventのemitによってフロントエンドに通知する、という方式にしている。まぁそれもフロントエンドでsetIntervalで実装するのとたいして変わらないんだろうけど…。

今のところPWAと比較して「Native Appならでは」というのはあまり無く、ようやくデスクトップ通知ができるようになった、くらいか？ 今後はもしかしたらショートカットキーを使った操作などが実装できるとNativeならでは感がでるかもしれない。

型定義生成

ということで結局は書くコードの大半はTypeScriptになる。 そしてデータはバックエンドから取得するが IPC を介して結局JSONでやりとりすることになるので、Lexiconに沿った型にmappingさせて表示に使うにはどうしても型定義が必要になる。

最新のLexiconから対応する型定義などを生成したものが @atproto/api パッケージなどに含まれていて、公式appや他の多くのWeb Clientなどではこれを使っているはず。 Tariumのフロントエンドでもこれを素直に使えば良いが、この api パッケージにはXRPCのためのClient機能なども含まれていて、折角バックエンドでXRPC処理するようにしているのに本末転倒、というか「負けた」感じになってしまう…。

なので、意地でも @atproto/api は使わずに必要な型定義だけを得たい！ということで この api のためのコードを生成している @atproto/lex-cli をハックして必要なものだけを生成して使う、ということをした。

https://github.com/sugyan/tarium/tree/main/gen-types

現在の状況

v0.0.8 で、FollowingのタイムラインとCustom Feeds、あと通知がようやく表示できるようになって あとはテキストのみの単純な投稿ならできる、というくらい。まだまだ足りない機能だらけではあるが ちょっとずつ使えるようになってきている、とは思う。 自分が満足いくところまでは頑張って機能実装していくつもり。

実際、ここまで実装する過程でATriumがgetPreferencesを正しく取得できないバグに気付いたりできたので、当初の目的としては正しく達成できている。

Rustのserdeで、データフォーマットによって異なる型にserialize/deserializeする

Rust ATrium

背景

BlueskyのAT ProtocolのRust版ライブラリを作っている。

memo.sugyan.com

github.com

その中で最近実装した機能の話。

AT Protocolで扱うデータモデルのSpecは、以下のページで書かれている。

atproto.com

この中に、Lexiconでcid-linkという名前で扱われる型がある。

https://atproto.com/specs/lexicon#cid-link

つまりIPLDのLinkをCIDで表現する型、ということのようだ。

で、これらのデータを扱うわけだが、そのデータフォーマットが2種類ある。 IPLDではデータ送信のためのCodecとして、binary formatのDAG-CBORと human-readable formatのDAG-JSONを定めている。

https://ipld.io/docs/codecs/

AT Protocolでは、効率的にデータを扱いたい場合にはDAG-CBORを用い、XRPCのHTTP APIなどではDAG-JSONとは異なる規約のJSONフォーマットを扱う、らしい。

で、cid-linkについては以下のように書かれている。

link field type (Lexicon type cid-link). In DAG-CBOR encodes as a binary CID (multibase type 0x00) in a bytestring with CBOR tag 42. In JSON, encodes as $link object

DAG-CBORでは、以下のようなバイナリ表現のCIDを含むバイト列、

0xd8, 0x2a, 0x58, 0x25, 0x00, 0x01, 0x71, 0x12, 0x20, 0x65, 0x06, 0x2a, 0x5a, 0x5a, 0x00, 0xfc,
0x16, 0xd7, 0x3c, 0x69, 0x44, 0x23, 0x7c, 0xcb, 0xc1, 0x5b, 0x1c, 0x4a, 0x72, 0x34, 0x48, 0x93,
0x36, 0x89, 0x1d, 0x09, 0x17, 0x41, 0xa2, 0x39, 0xd0,

JSONでは、以下のような $link という単一のキーを含むオジェクト、

{
  "$link": "bafyreidfayvfuwqa7qlnopdjiqrxzs6blmoeu4rujcjtnci5beludirz2a"
}

として表現されるらしい。

serde_json, serde_ipld_dagcbor

RustでJSONなどのデータフォーマットで Serialize/Deserialize する、となるとまず間違いなく serde を使うことになるだろう。 serde自体は Serialize/Deserialize を行うわけではなく、あくまでRustのデータ構造に対して汎用的にそれらを可能にするためのフレームワーク、という感じ。

ATriumではLexiconから生成された各XRPCに関連するデータの型をライブラリとして提供するので、それらの型に対して基本的にはserdeのattributesを付与するだけで、実際に何らかのデータフォーマットに対応した Seriazlier/Deserializer を使って変換操作をするのはライブラリのユーザ、ということになる。

実際のところ、JSONデータを扱うなら serde_json 一択だろう。 DAG-CBORについては、CBORデータを扱うことができるライブラリが幾つか存在しているが、2024-03時点でIPLDのLinkを正しく扱えるものとしては serde_ipld_dagcbor が現実的な選択肢になるようだった。

ので、この2つを使って実際に使われるデータに対して正しく Serialize/Deserialize できるようにする、ということを考える。

問題点: データフォーマットによって対象の型が異なる

JSONの場合/DAG-CBORの場合をそれぞれ独立して考えれば、構造に合わせて型を定義するだけなので簡単だ。

#[derive(Serialize, Deserialize, Debug)]
struct CidLink {
    #[serde(rename = "$link")]
    link: String,
}

fn main() {
    let cid_link_from_json = serde_json::from_str::<CidLink>(...);
    println!("{cid_link_from_json:?}");
    // => Ok(CidLink { link: "bafyreidfayvfuwqa7qlnopdjiqrxzs6blmoeu4rujcjtnci5beludirz2a" })
}

#[derive(Serialize, Deserialize, Debug)]
struct CidLink(cid::Cid);

fn main() {
    let cid_link_from_dagcbor = serde_ipld_dagcbor::from_slice::<CidLink>(...);
    println!("{cid_link_from_dagcbor:?}");
    // => Ok(CidLink(Cid(bafyreidfayvfuwqa7qlnopdjiqrxzs6blmoeu4rujcjtnci5beludirz2a)))
}

で、問題は両方に対応しようとする場合。ライブラリのユーザがJSONを使うか DAG-CBORを使うかどちらかだけであればまだ feature flags で切り替えるなどの対応が可能だが、「どちらも使う」というユースケースも考えられるので、

  • serde_json を使っている場合は $link キーを含むオブジェクト
  • serde_ipld_dagcbor を使っている場合は cid::Cid

として同じ CidLink という名前の型に情報を格納できるようにしたい。

最初の解決策: is_human_readable() による分岐

基本的には serde 自体は、呼ばれる Serializer/Deserializer についての情報を知ることができない。 が、 Serialize や Deserialize を自分で実装すると、そのときに引数に含まれる serializer や deserializer に対して .is_human_readable() というメソッドを呼ぶことで一つ情報を得られる。 これは serde_json を使っていると true になり、 serde_ipld_dagcbor を使っていると基本的には false になるので、以下のように分岐させることで統一した CidLink で両方のデータフォーマットを扱うことができる。

#[derive(Debug)]
struct CidLink(Cid);

#[derive(Serialize, Deserialize)]
struct LinkObject {
    #[serde(rename = "$link")]
    link: String,
}

impl Serialize for CidLink {
    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
        if serializer.is_human_readable() {
            LinkObject {
                link: self.0.to_string(),
            }
            .serialize(serializer)
        } else {
            self.0.serialize(serializer)
        }
    }
}

impl<'de> Deserialize<'de> for CidLink {
    fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
        if deserializer.is_human_readable() {
            let obj = LinkObject::deserialize(deserializer)?;
            Ok(Self(
                Cid::try_from(obj.link.as_str()).map_err(serde::de::Error::custom)?,
            ))
        } else {
            Ok(Self(Cid::deserialize(deserializer)?))
        }
    }
}

これで解決、めでたしめでたし… といきたいところだが、そうもいかない。

うまくいかないケース

CidLink 単体が上手く処理されていても、それを子にもつ enum を "Internally tagged" や "Untagged" で区別しようとすると、問題が生じるようだ。

例えば、以下のようなもの。

#[derive(Serialize, Deserialize, Debug)]
#[serde(tag = "tag", rename_all = "lowercase")]
enum Parent {
    Foo(Child),
    Bar(Child),
}

#[derive(Serialize, Deserialize, Debug)]
struct Child {
    cid: CidLink,
}

これは、 "tag" キーで指定されたvariantとしてdeserializeを試みる。JSONでいうと

[
  {
    "tag": "foo",
    "cid": {
      "$link": "bafyreidfayvfuwqa7qlnopdjiqrxzs6blmoeu4rujcjtnci5beludirz2a"
    }
  },
  {
    "tag": "bar",
    "cid": {
      "$link": "bafyreidfayvfuwqa7qlnopdjiqrxzs6blmoeu4rujcjtnci5beludirz2a"
    }
  }
]

といった配列で渡されたとき、1つめの要素は Parent::Foo(Child) 、2つ目の要素は Parent::Bar(Child) としてdeserializeすることになる。

これと同様の構造を持つDAG-CBORのデータを serde_ipld_dagcbor でdeserializeすると (そもそもこういうケースでCidを含むものをdeserializeできないという問題 もあったが)

Error: Msg("invalid type: newtype struct, expected struct LinkObject")

といったエラーになってしまう。

deserializer.is_human_readable() で分岐しているところでdebug printしてみると分かるが、このような構造のデータをdeserializeするときは、 serde_ipld_dagcbor を使っていても .is_human_readable() は true になってしまうらしい。 serde の細かい挙動を知らないけど、 Internally tagged や Untagged の場合は一度mapデータとして保持してからtagや内容を見て型を決定する必要があるため？そこから目的の型にマッピングする際に使われるdeserializerはまた別物になるらしく、 .is_human_readable() は意図したものにはならないようだ。 おそらくこのあたり。

なので、上述のように enum を使っている箇所の下では .is_human_readable() による分岐は機能しない。

解決策(？): Ipld を経由しデータの構造によって分岐する

serde_ipld_dagcbor という名前の通り、これは Ipld というデータモデルを利用することを想定されている。このデータモデルは(互換性どれくらいか把握できていないけれど) serde_json::Value と同じように構造化されたデータを保持できる。JSONには無い Link というものがある点でJSONの上位互換と考えても良いかもしれない。

ということで、deserializeしたいデータを一度 Ipld に変換してしまい、その構造を見てデータフォーマットを推定して分岐する、という手段をとった。

use libipld_core::ipld::Ipld;

impl<'de> Deserialize<'de> for CidLink {
    fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
        let ipld = Ipld::deserialize(deserializer)?;
        match &ipld {
            Ipld::Link(cid) => {
                return Ok(Self(*cid));
            }
            Ipld::Map(map) => {
                if map.len() == 1 {
                    if let Some(Ipld::String(link)) = map.get("$link") {
                        return Ok(Self(
                            Cid::try_from(link.as_str()).map_err(serde::de::Error::custom)?,
                        ));
                    }
                }
            }
            _ => {}
        }
        Err(serde::de::Error::custom("Invalid cid-link"))
    }
}

少なくとも CidLink としてのデータであれば、 Ipld::deserialize(deserializer) は問題なく成功する。その結果は Ipld::Link か、 "$link"キーを含む Ipld::Map かどちらか、になるはずで、前者ならそのまま得られるCidを利用し、後者であればその "$link" の値からCidを復元する。

この手法であれば、 .is_human_readable() に依存せずに正しく判別でき、どちらのデータも同様にdeserializeできる。

fn main() {
    let parents_json = serde_json::from_str::<Vec<Parent>>(...)?;
    println!("{parents_json:?}");
    // => Ok([Foo(Child { cid: CidLink(Cid(bafyreidfayvfuwqa7qlnopdjiqrxzs6blmoeu4rujcjtnci5beludirz2a)) }), Bar(Child { cid: CidLink(Cid(bafyreidfayvfuwqa7qlnopdjiqrxzs6blmoeu4rujcjtnci5beludirz2a)) })])

    let parents_dagcbor = serde_ipld_dagcbor::from_slice::<Vec<Parent>>(...)?;
    println!("{parents_dagcbor:?}");
    // => Ok([Foo(Child { cid: CidLink(Cid(bafyreidfayvfuwqa7qlnopdjiqrxzs6blmoeu4rujcjtnci5beludirz2a)) }), Bar(Child { cid: CidLink(Cid(bafyreidfayvfuwqa7qlnopdjiqrxzs6blmoeu4rujcjtnci5beludirz2a)) })])
}

今回のようなケースでしか機能しないかもしれないが、一応これで問題は解決した。

(他にもっと良い方法をご存知の方がいれば教えてください…)

汎用的？ な解決策: Untagged

一般的には、このように場合によって異なる型にdeserializeしたい場合は Untagged なenumを使うのが良いのかもしれない。

#[derive(Serialize, Deserialize)]
#[serde(untagged)]
pub enum CidLink {
    Raw(Cid),
    LinkObject {
        #[serde(rename = "$link")]
        link: String,
    },
}

serde(untagged) の場合はvariantを順番に試し、最初にdeserializeに成功したものを結果として返す。 ので、上の例の場合はまず Cid 単体としてdeserializeしてみて、失敗したら "$link" キーを持つオブジェクトとしてdeserializeしてみる、という動作になる。記述の順序を変えれば試行の順序も変化する。

ベンチマーク

上述した"Untagged"の場合は、記述の順序が大事になる。上の例の通りだとJSONのデータは毎回最初にCidとしてdeserialize試行して失敗してようやくオブジェクトとして試行、となり効率が悪い。しかし順序を逆にすると今度はDAG-CBORのデータを処理する際に毎回オブジェクトとして試行して失敗して…となる。 今回は対象が2種類だけなので差は小さいかもしれないが、これが何種類もあると…。

その点ではIpldを経由する手法の方が、中間の変換処理は入るが安定した効率は期待できる。

当然ながら、JSONなら最初からオブジェクトとして DAG-CBORなら最初からCidとしてdeserializeするのが最も効率的で速い。 それぞれを基準として、「Raw→LinkObjectのuntagged (untagged_1)」「LinkObject→Rawのuntagged (untagged_2)」「Ipld経由 (via_ipld)」のそれぞれのdeserializeをベンチマークとってみた。

running 8 tests
test bench_cbor_only       ... bench:          59 ns/iter (+/- 1)
test bench_cbor_untagged_1 ... bench:          83 ns/iter (+/- 2)
test bench_cbor_untagged_2 ... bench:         172 ns/iter (+/- 8)
test bench_cbor_via_ipld   ... bench:          63 ns/iter (+/- 1)
test bench_json_only       ... bench:          77 ns/iter (+/- 2)
test bench_json_untagged_1 ... bench:         276 ns/iter (+/- 4)
test bench_json_untagged_2 ... bench:         134 ns/iter (+/- 9)
test bench_json_via_ipld   ... bench:         325 ns/iter (+/- 6)

DAG-CBORに関しては、 untagged_2 がやはり毎回LinkObjectの試行の後になるので3倍ほど遅くなってしまう。一方で via_ipld はほぼ同等の速度で処理できているようだ。

JSONに関しては、どれも大きく遅くなるようだ。意外にも untagged_2 でも2倍くらい遅くなる…。via_ipld はcidのparse処理も入るので当然ながら最も遅くなってしまう、という結果だった。

実装結果

ということで、

  • どうしてもJSONだけを扱うときと比較すると遅くなる
  • そもそもXRPC RequstにはJSONしか使わない
    • DAG-CBORが必要になるのはSubscriptionなどrepoデータを読むときのみ

ということもあって、dag-cbor featureを有効にしたときのみ、Ipldを経由する方式で両方のデータフォーマットに対応するようにした。

その後

この実装をした後、 types::string::Cid という型が導入されて、Cidの文字列表現であるものはこの型でvalidationするようになった。LinkObjectのものも値は String ではなくこの types::string::Cid を使うべきで、そうなるともはやJSONの速度差もそんなに気にしても仕方ない感じになってくる。

running 8 tests
test bench_cbor_only       ... bench:          59 ns/iter (+/- 0)
test bench_cbor_untagged_1 ... bench:          78 ns/iter (+/- 3)
test bench_cbor_untagged_2 ... bench:         169 ns/iter (+/- 3)
test bench_cbor_via_ipld   ... bench:          63 ns/iter (+/- 3)
test bench_json_only       ... bench:         227 ns/iter (+/- 4)
test bench_json_untagged_1 ... bench:         426 ns/iter (+/- 6)
test bench_json_untagged_2 ... bench:         288 ns/iter (+/- 5)
test bench_json_via_ipld   ... bench:         324 ns/iter (+/- 6)

もはや feature flags での切り替えは廃止して、必ずIpldを経由する方式にしてしまって良いかもしれない。