Posted at

Rustのstrをコピーなしで連結する


はじめに

Rustにおいてstrを連結する方法としては、例えばformat!を使ったものがあります。

format!("{}{}", a, b);

これは確かに連結できるのですが、新しくStringのメモリ領域を確保してabの内容をそれぞれコピーする、という実装になります。

これをコピーなしに行う方法はないだろうか、という話です。


方法を考える

要は

fn concat(a: &str, b: &str) -> &str

なる関数を実装したいということです。

残念ながら任意の引数についてこれを満たす関数を実装することはできません。なぜなら、1つのstrはメモリ上で連続した領域を取る必要があり、もしaとbのメモリ領域が離れていた場合、コピーなしにこの条件を満たすことができないからです。

逆に言えば、aとbがメモリ上で連続していれば1つのstrにすることも可能、ということになります。

また、aとbのライフタイムが違っていた場合、生成するstrのライフタイムを決められなくなるので、2つのライフタイムが等しいという制約も付きます。

というわけで

fn concat<'a>(a: &'a str, b: &'a str) -> Option<&'a str>

であれば実装可能ということになります。

これは、もしaとbがメモリ上で連続していれば連結したSome(&str)を、そうでなければNoneを返す関数です。

実装方法としては、aとbのポインタと長さから隣接しているかどうかを判定して、隣接していればそのポインタからスライスを生成する形になります。当然内部はunsafeです。


str-concatクレート

もし既存の実装がなければ作ろうと思っていましたが、さすがにありました。

str-concat

というわけでこれを使うと

let s = "0123456789";

assert_eq!("0123456", concat(&s[..5], &s[5..7]).unwrap());

こんなことができます。


使い道

隣接した2つのstrという条件はかなり厳しいので「使い道があるのか?」と思われるかもしれませんが、パーサ(というかLexer)を書くときに重宝したりします。

例えば、nomで_区切りの数値を受理するパーサは以下のように書けます。

(ここではnomの解説はしません。「Rustのパーサコンビネータライブラリnom 5.0を使ってみた」に簡単な解説を書いたのでそちらを見てください。)

pub fn unsigned_number(s: &str) -> IResult<&str, Vec<&str>> {

let (s, x) = digit1(s)?;
fold_many0(alt((tag("_"), digit1)), vec![x], |mut acc: Vec<_>, item| {
acc.push(item);
acc
})(s)
}

これを使って"123_456"をパースすると結果はvec!["123", "_", "456"]のように受理したパーサコンビネータの部品(この場合は数値を受理するdigit1_を受理するtag("_"))ごとにばらばらになってしまいます。

構文木を作るようなレベルのパーサならともかく、Lexerとしてはこんなに細切れにされてもしょうがないのでなんとか1つの"123_456"で受け取りたいところです。

ここでstr-concatを使うと

pub fn unsigned_number(s: &str) -> IResult<&str, &str> {

let (s, x) = digit1(s)?;
fold_many0(alt((tag("_"), digit1)), x, |acc: &str, item| {
str_concat::concat(acc, item).unwrap()
})(s)
}

という感じでコピーなしに連結できます。パーサが受理する以上必ず隣接しているはずなのでunwrapしても問題ありません。