GATsでreborrowがtrait化できるんじゃないか？　(完全には無理)

概要

reborrowできる型(&mut Tなど)を一般に(例えば(&mut T, &mut U)などを)取って構造体に格納し、さらに他のtrait(Iteratorなど)と一緒に運用したい場合がある。しかし現状reborrowをそのままtraitにしようとすると、reborrow後の型が寿命を短くした自分自身であると保証できないため、他のtrait実装の保証を失ってしまう。

代わりにGATsを用いてSelf::Target<'borrow>をreborrowされる型に設定すれば、selfを取る代わりにSelf::Target<'borrow>を取る関連関数を持つtraitが定義でき、trait実装の保証が保たれる。ただしそれらのtraitからは、methodとしての運用性が失われる(必ずSelfの注釈が必要)。新しい構造体でwrapするとそれなりに扱いやすくはなる。

これらをrelendとして公開したのでどうぞ

reborrowとは？

(可変)参照の(可変)参照から(可変)参照を暗黙に作り出す操作。Copyと違って寿命が違うものが生成される。

fn add(x: &mut &mut u8) {
    let y: &mut u8 = x;
    *y += 1
}
let mut x = 0;
let mut y = &mut x;
add(&mut y);
assert_eq!(x, 1);

これによって可変参照を何度も使うことが可能になる:

fn add(x: &mut u8) {
    *x += 1
}
fn add3(x: &mut u8) {
    add(x);
    add(x);
    add(x);
}
let mut x = 0;
add3(&mut x);
assert_eq!(x, 3);

非常に有用な仕組みであるが、ドキュメントには未だ(2024-10-17現在)書かれておらず、また、&mut Tや&T以外の参照に対してreborrowを行うことはできない。

struct MyRef<'a>(&'a mut u8);

fn add(x: MyRef) {
    *x.0 += 1
}
fn add2(x: MyRef) {
    add(x);
    add(x);   // type error: "use of moved value: `x`. value used here after move"
}

reborrowの個別実装と既存の一般化

MyRefにreborrowと同じものをmethodとして追加してみよう:

impl MyRef<'_> {
    fn reborrow<'short>(&'short mut self) -> MyRef<'short> {
        MyRef(&mut self.0)
    }
}
fn add2(mut x: MyRef) {
    add(x.reborrow());
    add(x);
}

let mut x = 5;
add2(MyRef(&mut x));
assert_eq!(x, 7);

これでReborrowができるようになったが、これを一般化することは可能だろうか？

純粋なreborrowの実装は原理的に不可能

Cloneの実装はfn clone(&self) -> Self;という関数が実装できるので定式化できるが、reborrowは「複数作成できない」制約を作るために寿命が変わったものが作成される。

trait Reborrow {
    fn reborrow<'short>(&'short mut self) -> Self<'short>;
}

みたいに書ければ楽だが、Selfに寿命パラメータを含めることは一切できない。

自作の型が個別にreborrowできるだけでよいなら、既存のreborrowの実装としてreborrowというcrateが知られている。具体的な定義は次の通り:

pub trait ReborrowMut<'short, _Outlives = &'short Self> {
    type Target;

    // Required method
    fn rb_mut(&'short mut self) -> Self::Target;
}

しかし、reborrowした後の型が自分自身と互換性を持つかは全く保証されない。例えばT: Debug + ReborrowMut<'_>としてOption<T>をreborrowすると、結果の型はOption<<T as Reborrow<'short>>::Target>であり、これがDebugを実装するかは全く保証されない。

reborrowをtraitにして他のtraitを追加できるようにするには、別の工夫が必要である。

GATs(Generic Associated Types)を使う

実際に定義を見た方が早いので、見てもらう。

trait Reborrow {
    type Target<'borrow> where Self: 'borrow;
    fn reborrow<'short, 'long>(this: &'short mut Self::Target<'long>) -> Self::Target<'short>;
}
impl<T> Reborrow for &mut T {
    type Target<'borrow> = &'borrow mut T where Self: 'borrow;
    fn reborrow<'short, 'long>(this: &'short mut &'long mut T) -> &'short mut T {
        this
    }
}
impl<T, U> Reborrow for (T, U) {
    type Target<'borrow> = (T::Target<'borrow>, U::Target<'borrow>) where Self: 'borrow;
    fn reborrow<'short, 'long>(this: &'short mut Self::Target<'long>) -> Self::Target<'short> {
        (T::reborrow(&mut self.0), U::reborrow(&mut self.1))
    }
}

関連型をパラメトリックにできるので、それを用いて寿命の異なる型をいっぺんに表記できるようにした。Selfと等しいかは全く保証されないが、Self::Target<'borrow>に対して実装を与えるようなtraitがreborrowの後も利用できる。例えばIteratorを次の様に書き直し、一般化できる。

trait ReborrowIterator: Reborrow {
    type Item;
    fn next(this: Self::Target<'_>) -> Option<Self::Item>;
}
impl<T: Iterator> ReborrowIterator for &mut T {
    type Item = T::Item;
    fn next(this: &mut T) -> Option<Self::Item> {
        this.next()
    }
}
impl<T: ReborrowIterator, U: ReborrowIterator> ReborrowIterator for (T, U) {
    type Item = (T::Item, U::Item);
    fn next(this: Self::Target<'_>) -> Option<Self::Item> {
        Some((T::next(this.0)?, U::next(this.1)?))
    }
}

ここで(&mut T, &mut U)にもiteratorのような実装ができたことがわかる。

実際の運用

ここでnextを呼ぶときにいちいち<(Chars, slice::Iter<u8>)>::next(...)のように書いていては面白くないので、wrapperを作成しよう。そのために次のショートハンドを設定する:

trait IntoReborrow<'borrow>: Reborrow<Target<'borrow> = Self> + 'borrow {}
impl<'borrow, T: Reborrow<Target<'borrow> = T> + 'borrow> IntoReborrow<'borrow> for T {}

これを用いて新しい型BorrowIterを定義しよう:

struct BorrowIter<'borrow, T: Reborrow + 'borrow>(T::Target<'borrow>);
impl<'borrow, T: IntoReborrow<'borrow>> BorrowIter<'borrow, T> {
    fn new(iter: T) -> BorrowIter<'borrow, T> {
        BorrowIter(iter)
    }
}
impl<T: ReborrowIterator> BorrowIter<'_, T> {
    fn next(self) -> Option<Self::Item> {
        T::next(self.0)
    }
    fn rb<'short>(&'short mut self) -> BorrowIter<'short, T> {
        BorrowIter(T::reborrow(&mut self.0))
    }
}

こうすることで、次のコードが動作する:

let (mut iter1, mut iter2) = ([0, 1, 2].into_iter(), [3, 4, 5, 6].into_iter());
let mut iter = BorrowIter::new((&mut iter1, &mut iter2));

assert_eq!(iter.rb().next(), Some((0, 3)));
assert_eq!(iter.rb().next(), Some((1, 4)));
assert_eq!(iter.rb().next(), Some((2, 5)));
assert_eq!(iter.next(), None);

その他の利点

省メモリな参照構造体

通常の参照ありの構造体を定義するなら

struct Arg<'a, T, U>(&'a mut T, &'a mut U);

のようになるが、ここでU=()としても構造体の大きさは全く削減されない。&mut ()はusizeと同じ大きさを持ってしまうためだ。これを次の様に書き換える:

struct Arg<'a, T: Reborrow + 'a, U: Reborrow + 'a>(T::Target<'a>, U::Target<'a>);

無論()にReborrowを実装する必要はあるが、このときにU=()としてもreborrowが可能かつ必要な参照を含められる。

dereferenceの削減

「Iteratorに一時的に番号を振る」という操作はiter.by_ref().enumerate()とするが、ReborrowIteratorであれば自分自身を.enumerate()するような操作が可能であり、新しい参照は要らなくなる。

struct WithIndex<'a, T: Reborrow + 'a> {
    index: &'a mut usize,
    iter: T::Target<'a>,
}
impl<'a, T: ReborrowIterator + IntoReborrow<'a>> WithIndex<'a, T> {
    pub fn new(iter: T, index: &'a mut usize) -> Self {
        Self { index, iter }
    }
}
impl<T: ReborrowIterator> Reborrow for WithIndex<'_, T> {
    type Target<'short> = WithIndex<'short, T> where Self: 'short;
    fn reborrow<'short, 'long>(this: &'short mut WithIndex<'long, T>) -> WithIndex<'short, T> {
        WithIndex { index: this.index, iter: T::reborrow(&mut this.iter) }
    }
}
impl<T: ReborrowIterator> ReborrowIterator for WithIndex<'_, T> {
    type Item = T::Item;
    fn next(this: WithIndex<'_, T>) -> Option<Self::Item> {
        let item = T::next(this.iter)?;
        *this.index += 1;
        Some(item)
    }
}

// Usage
let (mut index, mut iter1, mut iter2) = (0, [0, 1, 2].into_iter(), [3, 4, 5, 6].into_iter());
let mut iter = BorrowIter::new((WithIndex::new(&mut iter1, &mut index), &mut iter2));

assert_eq!(iter.rb().next(), Some((0, 3)));
assert_eq!(iter.rb().next(), Some((1, 4)));
assert_eq!(iter.rb().next(), Some((2, 5)));
assert_eq!(iter.rb().next(), None);
assert_eq!(index, 3);

公開

これを毎回定義するのがだるいのでrelend crateにまとめた。主に自分用だけど使いたければどうぞ。