Rust の借用検査は組込の複合代入演算子に対して特殊な動作を行う

Rust 1.36.0 stable, edition 2018 での情報。 TL;DR: 結論

正直なところ †完全に理解† するには遠く及ばない状況なので、もっと詳しく理解している人がいたら解説記事など書いてもらえると私が喜びます。

問題

下記コードは、組込の i64 の Vec とユーザ定義^[0]の std::num::Wrapping<i64> の Vec について同じ演算を行った結果、後者のみにエラーが発生している様子である。

        use std::num::Wrapping;

fn main() {
    // Type with built-in add-subst operator.
    let mut vec_bi = vec![0i64, 1];
    vec_bi[0] += vec_bi[1]; // No errors.

    // Type with user-defined add-subst operator.
    let mut vec_ud = vec![Wrapping(0i64), Wrapping(1)];
    vec_ud[0] += vec_ud[1]; // Error here.
}

           Compiling playground v0.0.1 (/playground)
warning[E0502]: cannot borrow `vec_ud` as immutable because it is also borrowed as mutable
  --> src/main.rs:10:18
   |
10 |     vec_ud[0] += vec_ud[1]; // Error here.
   |     -------------^^^^^^---
   |     |            |
   |     |            immutable borrow occurs here
   |     mutable borrow occurs here
   |     mutable borrow later used here
   |
   = warning: this error has been downgraded to a warning for backwards compatibility with previous releases
   = warning: this represents potential undefined behavior in your code and this warning will become a hard error in the future

    Finished dev [unoptimized + debuginfo] target(s) in 0.47s
     Running `target/debug/playground`

Rust Playground での 2019-07-28 の実行結果。この時点での Rust は 1.36 が最新の stable 。

なぜ i64 で許されるコードが同じく Copy trait や AddAssign trait を実装している std::num::Wrapping<i64> では許されないのか。

two-phase borrow

two-phase borrow とは、同じ式の中で同じ値に対する mutable borrow が複数記述できるようにする特例のようなルールである。このルールは今のところ、特殊な状況下のみで適用されることになっている。詳細やコード例は rustc guide で説明されているが、簡単に説明すると「mutable borrow が発生する点と実際にそれが使われる点の間で、一時的に mutable borrow を immutable borrow であるかのように扱う」といった挙動になる。たとえば以下の例を見てみよう。

      fn main() {
    let mut vec = vec![];
    vec.push(vec.len());
}

vec.push() で vec の mutable borrow を要求しており、かつ引数の vec.len() で vec の immutable borrow を要求している。よって、素朴なルールでは &mut vec と &vec を同時に必要とすることになってしまい借用検査に失敗するが、このコードはコンパイルが通る。それを可能にするのが two-phase borrow である。

この例では、 vec.push() のために &mut vec が予約されるが、これが実際に使用されるのは引数の評価が終わった後であるため、それまでは排他的な借用を抑制し、あたかも &vec しか要求されていないかのように振る舞う。そして、 &vec が他の場所に存在したところで vec.len() は可能であり、またその結果が &mut vec と共存できるため、無事に vec.push() が実行可能であると判断される。

&mut vec を &vec かのように見做すというのが肝で、たとえば次のようなコードはコンパイルが通らない。

      fn main() {
    let mut vec = vec![];
    vec.push({
        vec.clear();
        0
    });
}

         Compiling playground v0.0.1 (/playground)
error[E0499]: cannot borrow `vec` as mutable more than once at a time
 --> src/main.rs:4:9
  |
3 |     vec.push({
  |     --- ---- first borrow later used by call
  |     |
  |     first mutable borrow occurs here
4 |         vec.clear();
  |         ^^^ second mutable borrow occurs here

error: aborting due to previous error

For more information about this error, try `rustc --explain E0499`.
error: Could not compile `playground`.

To learn more, run the command again with --verbose.

vec.push() のための &mut vec の予約ゆえ、 push の引数のブロック内では vec は immutable borrow が他に存在するものとして借用検査が行われる。その結果、 vec.clear() は vec を mutable に借用できないため、 two-phase borrow のルールでは許されずエラーとなる^[1]^[2]。

immutable reference を持ち越せない例も見てみよう。

      fn main() {
    let mut vec: Vec<()> = vec![];
    vec.extend(&vec);
}

         Compiling playground v0.0.1 (/playground)
error[E0502]: cannot borrow `vec` as mutable because it is also borrowed as immutable
 --> src/main.rs:3:5
  |
3 |     vec.extend(&vec);
  |     ^^^^------^----^
  |     |   |      |
  |     |   |      immutable borrow occurs here
  |     |   immutable borrow later used by call
  |     mutable borrow occurs here

error: aborting due to previous error

For more information about this error, try `rustc --explain E0502`.
error: Could not compile `playground`.

To learn more, run the command again with --verbose.

引数の &vec の時点では他にもうひとつの &vec が存在するだけなので問題ないが、 vec.push() 時点で本当に &mut vec が必要になってもまだ引数の &vec の借用が生きているため、(当然ながら) two-phase borrow でこのコードは許されない。

複合代入演算子

通常の場合

Rust では、ユーザ定義型などに対する演算子の定義は trait により行う。そして、 a += b という式は、基本的にコンパイル時に std::ops::AddAssign::add_assign(&mut a, b) のような通常の関数呼び出しに変換される ^[3] 。

問題のコードの vec_ud[0] += vec_ud[1]; も関数呼び出しスタイルに変換され、以下のようになる。

        <Vec<Wrapping<i64>> as std::ops::AddAssign<Wrapping<i64>>>::add_assign(
    &mut *<Vec<Wrapping<i64>> as std::ops::IndexMut<usize>>::index_mut(&mut vec_ud, 0),
    *<Vec<Wrapping> as std::ops::Index<usize>>::index(&vec_ud, 1)
);

two-phase borrow について「特殊な状況下のみで適用される」と説明した。具体的には、 x += x のように左辺が単純な場合には two-phase borrow が利用される。しかし残念ながら vec_ud[0] += vec_ud[1] において、左辺は <Vec<Wrapping<i64>> as std::ops::IndexMut<usize>>::index_mut(&mut vec_ud, 0) である。このように左辺が通常の変数などでない一般的な状況では two-phase borrow は利用されない^[4]。この場合の複合代入は、通常の関数呼び出しと同じように処理され、 two-phase borrow は行われない。

関数呼び出しにおいて、関数の引数は左から順に評価されることになっている。つまりこの例では、 &mut *IndexMut::index_mut() が先に評価され、次に *Index::index() を評価しようとする。これは two-phase borrow が使われない状況では当然エラーとなる。単純化するなら、下記のようなコードと同じ原因である。

        fn substitute(a: &mut i64, b: i64) {
    *a = b;
}

fn main() {
    let mut x = 42;
    substitute(&mut x, x);
}

           Compiling playground v0.0.1 (/playground)
error[E0503]: cannot use `x` because it was mutably borrowed
 --> src/main.rs:7:24
  |
7 |     substitute(&mut x, x);
  |     ---------- ------  ^ use of borrowed `x`
  |     |          |
  |     |          borrow of `x` occurs here
  |     borrow later used by call

error: aborting due to previous error

For more information about this error, try `rustc --explain E0503`.
error: Could not compile `playground`.

To learn more, run the command again with --verbose.

本題ではないがついでに書いておくと、引数は左から右に評価されるため、引数の順を逆にすると (不思議なことにというべきか) コンパイルは通る。

        fn substitute_rev(b: i64, a: &mut i64) {
    *a = b;
}

fn main() {
    let mut x = 42;
    substitute_rev(x, &mut x);
}

           Compiling playground v0.0.1 (/playground)
    Finished dev [unoptimized + debuginfo] target(s) in 0.65s
     Running `target/debug/playground`

つまり、通常なら vec_ud[0] += vec_ud[1]; のような式の借用検査が通らないのは当然であり、エラーにならない方が特殊なのである。

組込型の演算子の場合

組込型の += 演算子は事情が異なる。 i64 などの組込型についての += などの演算子の利用は、対応する trait の関数呼び出しに変換されない。このことは rustc guide でも説明されている。

組込型の演算子の利用はコンパイラによって特別に取り扱われ、対応する LLVM IR に変換されるらしい。このとき複合代入演算子については、関数呼び出し形式の場合とは異なり、右辺の代入される値が先に評価され、その後で左辺の代入先が評価される。

The warning is correct. Overloaded compound assignment operators unfortunately evaluate their operands in the opposite order to the built in ones.

— @matthewjasper, https://github.com/rust-lang/rust/issues/59645#issuecomment-479233265

このことは、それぞれのケースに対応する MIR (中間言語) を観察することでも確認できる。

          use std::num::Wrapping;

fn main() {
    // Type with user-defined add-subst operator.
    let mut vec_ud = vec![Wrapping(0i64), Wrapping(1)];
    vec_ud[0] += vec_ud[1]; // Error here.
}

              bb2: {
        StorageDead(_2);                 // bb2[0]: scope 0 at <::alloc::macros::vec macros>:3:47: 3:48
        StorageLive(_8);                 // bb2[1]: scope 2 at src/main.rs:6:5: 6:14
        StorageLive(_9);                 // bb2[2]: scope 2 at src/main.rs:6:5: 6:14
        StorageLive(_10);                // bb2[3]: scope 2 at src/main.rs:6:5: 6:11
        _10 = &mut _1;                   // bb2[4]: scope 2 at src/main.rs:6:5: 6:11
        _9 = const std::ops::IndexMut::index_mut(move _10, const 0usize) -> [return: bb3, unwind: bb4]; // bb2[5]: scope 2 at src/main.rs:6:5: 6:14
                                         // ty::Const
                                         // + ty: for<'r> fn(&'r mut std::vec::Vec<std::num::Wrapping<i64>>, usize) -> &'r mut <std::vec::Vec<std::num::Wrapping<i64>> as std::ops::Index<usize>>::Output {<std::vec::Vec<std::num::Wrapping<i64>> as std::ops::IndexMut<usize>>::index_mut}
                                         // + val: Scalar(Bits { size: 0, bits: 0 })
                                         // mir::Constant
                                         // + span: src/main.rs:6:5: 6:14
                                         // + ty: for<'r> fn(&'r mut std::vec::Vec<std::num::Wrapping<i64>>, usize) -> &'r mut <std::vec::Vec<std::num::Wrapping<i64>> as std::ops::Index<usize>>::Output {<std::vec::Vec<std::num::Wrapping<i64>> as std::ops::IndexMut<usize>>::index_mut}
                                         // + literal: Const { ty: for<'r> fn(&'r mut std::vec::Vec<std::num::Wrapping<i64>>, usize) -> &'r mut <std::vec::Vec<std::num::Wrapping<i64>> as std::ops::Index<usize>>::Output {<std::vec::Vec<std::num::Wrapping<i64>> as std::ops::IndexMut<usize>>::index_mut}, val: Scalar(Bits { size: 0, bits: 0 }) }
                                         // ty::Const
                                         // + ty: usize
                                         // + val: Scalar(Bits { size: 8, bits: 0 })
                                         // mir::Constant
                                         // + span: src/main.rs:6:12: 6:13
                                         // + ty: usize
                                         // + literal: Const { ty: usize, val: Scalar(Bits { size: 8, bits: 0 }) }
    }

    bb3: {
        _8 = _9;                         // bb3[0]: scope 2 at src/main.rs:6:5: 6:14
        StorageDead(_10);                // bb3[1]: scope 2 at src/main.rs:6:13: 6:14
        StorageLive(_11);                // bb3[2]: scope 2 at src/main.rs:6:18: 6:27
        StorageLive(_12);                // bb3[3]: scope 2 at src/main.rs:6:18: 6:27
        StorageLive(_13);                // bb3[4]: scope 2 at src/main.rs:6:18: 6:24
        _13 = &_1;                       // bb3[5]: scope 2 at src/main.rs:6:18: 6:24
        _12 = const std::ops::Index::index(move _13, const 1usize) -> [return: bb5, unwind: bb4]; // bb3[6]: scope 2 at src/main.rs:6:18: 6:27
                                         // ty::Const
                                         // + ty: for<'r> fn(&'r std::vec::Vec<std::num::Wrapping<i64>>, usize) -> &'r <std::vec::Vec<std::num::Wrapping<i64>> as std::ops::Index<usize>>::Output {<std::vec::Vec<std::num::Wrapping<i64>> as std::ops::Index<usize>>::index}
                                         // + val: Scalar(Bits { size: 0, bits: 0 })
                                         // mir::Constant
                                         // + span: src/main.rs:6:18: 6:27
                                         // + ty: for<'r> fn(&'r std::vec::Vec<std::num::Wrapping<i64>>, usize) -> &'r <std::vec::Vec<std::num::Wrapping<i64>> as std::ops::Index<usize>>::Output {<std::vec::Vec<std::num::Wrapping<i64>> as std::ops::Index<usize>>::index}
                                         // + literal: Const { ty: for<'r> fn(&'r std::vec::Vec<std::num::Wrapping<i64>>, usize) -> &'r <std::vec::Vec<std::num::Wrapping<i64>> as std::ops::Index<usize>>::Output {<std::vec::Vec<std::num::Wrapping<i64>> as std::ops::Index<usize>>::index}, val: Scalar(Bits { size: 0, bits: 0 }) }
                                         // ty::Const
                                         // + ty: usize
                                         // + val: Scalar(Bits { size: 8, bits: 1 })
                                         // mir::Constant
                                         // + span: src/main.rs:6:25: 6:26
                                         // + ty: usize
                                         // + literal: Const { ty: usize, val: Scalar(Bits { size: 8, bits: 1 }) }
    }

MIR の抜粋 (playground)。ユーザ定義の += では、第一引数つまり左辺 (<Vec<Wrapping<i64>> as IndexMut<usize>>::index_mut(_10, 0usize) が先に評価され、その後で右辺 <Vec<i64> as Index<usize>>::index(_13, 1usize) が評価されている様子が読み取れる。

          fn main() {
    // Type with built-in add-subst operator.
    let mut vec_bi = vec![0i64, 1];
    vec_bi[0] += vec_bi[1]; // No errors.
}

              bb2: {
        StorageDead(_2);                 // bb2[0]: scope 0 at <::alloc::macros::vec macros>:3:47: 3:48
        StorageLive(_5);                 // bb2[1]: scope 2 at src/main.rs:4:18: 4:27
        StorageLive(_6);                 // bb2[2]: scope 2 at src/main.rs:4:18: 4:27
        StorageLive(_7);                 // bb2[3]: scope 2 at src/main.rs:4:18: 4:24
        _7 = &_1;                        // bb2[4]: scope 2 at src/main.rs:4:18: 4:24
        _6 = const std::ops::Index::index(move _7, const 1usize) -> [return: bb3, unwind: bb4]; // bb2[5]: scope 2 at src/main.rs:4:18: 4:27
                                         // ty::Const
                                         // + ty: for<'r> fn(&'r std::vec::Vec<i64>, usize) -> &'r <std::vec::Vec<i64> as std::ops::Index<usize>>::Output {<std::vec::Vec<i64> as std::ops::Index<usize>>::index}
                                         // + val: Scalar(Bits { size: 0, bits: 0 })
                                         // mir::Constant
                                         // + span: src/main.rs:4:18: 4:27
                                         // + ty: for<'r> fn(&'r std::vec::Vec<i64>, usize) -> &'r <std::vec::Vec<i64> as std::ops::Index<usize>>::Output {<std::vec::Vec<i64> as std::ops::Index<usize>>::index}
                                         // + literal: Const { ty: for<'r> fn(&'r std::vec::Vec<i64>, usize) -> &'r <std::vec::Vec<i64> as std::ops::Index<usize>>::Output {<std::vec::Vec<i64> as std::ops::Index<usize>>::index}, val: Scalar(Bits { size: 0, bits: 0 }) }
                                         // ty::Const
                                         // + ty: usize
                                         // + val: Scalar(Bits { size: 8, bits: 1 })
                                         // mir::Constant
                                         // + span: src/main.rs:4:25: 4:26
                                         // + ty: usize
                                         // + literal: Const { ty: usize, val: Scalar(Bits { size: 8, bits: 1 }) }
    }

    bb3: {
        _5 = (*_6);                      // bb3[0]: scope 2 at src/main.rs:4:18: 4:27
        StorageDead(_7);                 // bb3[1]: scope 2 at src/main.rs:4:26: 4:27
        StorageLive(_8);                 // bb3[2]: scope 2 at src/main.rs:4:5: 4:14
        StorageLive(_9);                 // bb3[3]: scope 2 at src/main.rs:4:5: 4:11
        _9 = &mut _1;                    // bb3[4]: scope 2 at src/main.rs:4:5: 4:11
        _8 = const std::ops::IndexMut::index_mut(move _9, const 0usize) -> [return: bb5, unwind: bb4]; // bb3[5]: scope 2 at src/main.rs:4:5: 4:14
                                         // ty::Const
                                         // + ty: for<'r> fn(&'r mut std::vec::Vec<i64>, usize) -> &'r mut <std::vec::Vec<i64> as std::ops::Index<usize>>::Output {<std::vec::Vec<i64> as std::ops::IndexMut<usize>>::index_mut}
                                         // + val: Scalar(Bits { size: 0, bits: 0 })
                                         // mir::Constant
                                         // + span: src/main.rs:4:5: 4:14
                                         // + ty: for<'r> fn(&'r mut std::vec::Vec<i64>, usize) -> &'r mut <std::vec::Vec<i64> as std::ops::Index<usize>>::Output {<std::vec::Vec<i64> as std::ops::IndexMut<usize>>::index_mut}
                                         // + literal: Const { ty: for<'r> fn(&'r mut std::vec::Vec<i64>, usize) -> &'r mut <std::vec::Vec<i64> as std::ops::Index<usize>>::Output {<std::vec::Vec<i64> as std::ops::IndexMut<usize>>::index_mut}, val: Scalar(Bits { size: 0, bits: 0 }) }
                                         // ty::Const
                                         // + ty: usize
                                         // + val: Scalar(Bits { size: 8, bits: 0 })
                                         // mir::Constant
                                         // + span: src/main.rs:4:12: 4:13
                                         // + ty: usize
                                         // + literal: Const { ty: usize, val: Scalar(Bits { size: 8, bits: 0 }) }
    }

MIR の抜粋 (playground)。組込型の += では、右辺 (<Vec<i64> as Index<usize>>::index(_7, 1usize) が先に評価され、その後で左辺 <Vec<i64> as IndexMut<usize>>::index_mut(_9, 0usize) が評価されている様子が読み取れる。

結論

一言で言うと: 組込型の複合代入は特殊

x += foo(&x) のような左辺が極めて単純な例であれば、 two-phase borrow が利用され借用検査が通る
- vec_ud[0] += vec_ud[1]; のようなケースはこれに該当しない
+= などの演算子は通常、関数呼び出しの形式に変換され処理される
- x += y であれば std::ops::AddAssign::add_assign(&mut x, y) になる
- ただし組込型の演算子利用は例外で、関数呼び出しに変換されず特別に処理される
関数呼び出しにおいて、引数は左 (最初の引数) から順に評価される
- このため、たとえば x の型が Copy トレイトを実装しているとき、 foo(&mut x, x) のようなコードは借用検査が通らず、 foo(x, &mut x) のようなコードは借用検査が通る
- std::ops::AddAssign::add_assign(&mut vec_ud[0], vec_ud[1]) は前者の形式にあたるためコンパイルエラーとなる
組込型の複合代入演算子では、 (関数呼び出しの形式とは異なり) 右辺が先に評価され、左辺が後に評価される
- よって、 vec_bi[0] += vec_bi[1] では vec_bi[1] が先に借用され、値がコピーされる。その後 vec_bi[0] が mutable に借用される。このとき vec_bi[1] の借用は既に終了しているため、問題なく mutable borrow が成功し、借用検査が通る。

参考

おまけ: safe で unsound なコード

“this represents potential undefined behavior in your code” などと言われると、実際に UB を引き起こしてみたくなるのが人情というものである (?)。やってみた (playground)。

      use std::rc::Rc;

struct MyString(String);

impl std::ops::AddAssign<String> for MyString {
    fn add_assign(&mut self, rhs: String) {
        self.0.push_str(&rhs);
    }
}

fn main() {
    let mut foo = Rc::new(vec![MyString("foo".to_owned())]);
    Rc::get_mut(&mut foo).unwrap()[0] += {
        *Rc::get_mut(&mut foo).unwrap() = vec![];
        "suffix".to_owned()
    };
}

         Compiling playground v0.0.1 (/playground)
warning[E0499]: cannot borrow `foo` as mutable more than once at a time
  --> src/main.rs:14:22
   |
13 |       Rc::get_mut(&mut foo).unwrap()[0] += {
   |       -           -------- first mutable borrow occurs here
   |  _____|
   | |
14 | |         *Rc::get_mut(&mut foo).unwrap() = vec![];
   | |                      ^^^^^^^^ second mutable borrow occurs here
15 | |         "suffix".to_owned()
16 | |     };
   | |_____- first borrow later used here
   |
   = warning: this error has been downgraded to a warning for backwards compatibility with previous releases
   = warning: this represents potential undefined behavior in your code and this warning will become a hard error in the future

    Finished dev [unoptimized + debuginfo] target(s) in 0.76s
     Running `target/debug/playground`
timeout: the monitored command dumped core
/root/entrypoint.sh: line 8:     7 Segmentation fault      timeout --signal=KILL ${timeout} "$@"

ユーザ定義の演算子 (ここでは <MyString as std::ops::AddAssign<String>>::add_assign) で左辺を先に評価することと two-phase borrow が組み合わさると unsound になるという例である。ただ気になるのは、 rustc guide で説明されているルールと違って mutable borrow が2つ存在することが何故か許されているところ。もしかして過去の (NLL 以前の) rustc はこのようなコードも許していたのだろうか……？謎である。

脚注

この文脈での「ユーザ定義」は、組込でない型すべてを指すものであり、標準ライブラリで定義された型も含んでいる。 [0]
エラーメッセージとしては、実際のコードに合わせて「mutable borrow が二度行われている」というメッセージになっている。 [1]
もし vec.push({vec.clear(); 42}); のような引数中での mutable borrow を許すと、 vec.last().map(|last| { *vec = vec![]; *last = 42; }); のようなコードで dangling pointer への参照が発生してしまい soundness hole になる。 [2]
このような変換を lowering と呼ぶらしい: MIR construction - Guide to Rustc Development [3]
複合代入演算子について該当する項目は rustc guide では The implicit mutable borrow in an overloaded compound assignment operator. と説明されており、 "implicit mutable borrow" とは何なのかは語られていない。例から察するに、通常の変数を明示的な &mut の記述なしに &mut として必要とするような状況のことを言っていそうである。 [4]