3

以下はパスカルの三角形からnCkmod 1,000,000,000+7にて求めるプログラムです。

MUsize は演算の際自動でmodをとる構造体です。

演算子オーバーロードを実装した構造体をVectorに格納し実行したところ以下のようなワーニングが出力されてしまいます。Vectorの中身をMUsizeではなくusizeで同じように実装したところワーニングは出ませんでした。MUsizeとそのメソッドをどの様に改変すればワーニングが取れますでしょうか? よろしくお願いします。

この理由としてMUsizeにderiveするトレイトがusizeと比べ何か足りないのではないかと考えております。

/*
AtCoder abc 132 解説より
https://www.youtube.com/watch?v=mso8tE1yMl8
*/
/*
    1
   1 1
  1 2 1
 1 3 3 1

aCb はa段目のb番目
*/

static MOD: usize = 1_000_000_000 + 7;
use std::ops::{AddAssign, SubAssign, MulAssign};
use std::ops::{Add, Sub, Mul};
#[derive(Copy, Clone, Debug)]
struct MUsize {x: usize}
impl MUsize {
    fn new(x: usize) -> MUsize {
        MUsize{x: x%MOD}
    }
}
impl AddAssign for MUsize {
    fn add_assign(&mut self, other: MUsize) {
        let tmp = self.x + other.x;
        *self = MUsize {
            x: if tmp >= MOD {tmp - MOD} else {tmp}
        };
    }
}
impl<'a> AddAssign<&'a MUsize> for MUsize {
    fn add_assign(&mut self, other: &MUsize) {
        let tmp = self.x + other.x;
        *self = MUsize {
            x: if tmp >= MOD {tmp - MOD} else {tmp}
        };
    }
}
impl SubAssign for MUsize {
    fn sub_assign(&mut self, other: MUsize) {
        let tmp = self.x + MOD - other.x;
        *self = MUsize {
            x: if tmp >= MOD {tmp - MOD} else {tmp}
        };
    }
}
impl MulAssign for MUsize {
    fn mul_assign(&mut self, other: MUsize) {
        *self = MUsize {
            x: self.x * other.x % MOD
        };
    }
}
impl Add for MUsize {
    type Output = MUsize;
    fn add(self, other: MUsize) -> MUsize {
        let mut res = MUsize::new(self.x);
        res += other;
        res
    }
}
impl<'a> Add<&'a MUsize> for MUsize {
    type Output = MUsize;
    fn add(self, other: &MUsize) -> MUsize {
        let mut res = MUsize::new(self.x);
        res += other;
        res
    }
}
impl Sub for MUsize {
    type Output = MUsize;
    fn sub(self, other: MUsize) -> MUsize {
        let mut res = MUsize::new(self.x);
        res -= other;
        res
    }
}
impl Mul for MUsize {
    type Output = MUsize;
    fn mul(self, other: MUsize) -> MUsize {
        let mut res = MUsize::new(self.x);
        res *= other;
        res
    }
}

struct C {
    c: Vec<Vec<MUsize>>
}
impl C {
    fn new(max: usize) -> C {
        let mut c = vec![vec![MUsize::new(0); max+2]; max+2];
        c[0][0] = MUsize::new(1);
        for i in 0..max+1 {
            for j in 0..i+1 {
                c[i+1][j] += c[i][j];
                c[i+1][j+1] += c[i][j];
            }
        }
        C {c}
    }
    fn c(&self, n: usize, k: usize) -> usize {
        self.c[n][k].x
    }
}

fn main() {
    let c = C::new(40);
    println!("{}", c.c(5, 2));
}
    warning[E0502]: cannot borrow `c` as immutable because it is also borrowed as mutable
      --> src/main.rs:83:30
       |
    83 |                 c[i+1][j] += c[i][j];
       |                 -------------^------
       |                 |            |
       |                 |            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

    warning[E0502]: cannot borrow `c` as immutable because it is also borrowed as mutable
      --> src/main.rs:84:32
       |
    84 |                 c[i+1][j+1] += c[i][j];
       |                 ---------------^------
       |                 |              |
       |                 |              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

2 件の回答 2

4

今回の現象を説明するには、3段階のステップがあります。

  1. 普通は1つの式の中で同じ値に対する可変参照を2個作ったり、可変参照と共有参照を両方作ったりはできない(借用の基本ルール)
  2. ただし、一時変数を作る手間を省くために、共有参照を使うのが可変参照を使うより前で終了することが明確に示せるシンプルな場合のみ、例外的に許可されて一時変数を作っているのと等価な扱いになる。(two-phase borrow)
  3. プリミティブ型の += はユーザー定義型(標準ライブラリのものも含む)と違う扱いになっている(トレイト実装を経由しない)ので、プリミティブ型だけはシンプルな例外ケースに該当して、スライスでもtwo-phase borrowが有効になる。

スライスのインデキシングとユーザー定義型のAddAssignは両方ともトレイト実装の関数呼び出しに展開されるので、内部的にはadd_assign(index(v, i), index(v, j))のような形になっており、two-phase borrowが有効になりません。

詳細な話は https://blog.cardina1.red/2019/07/29/borrowck-and-builtin-compound-assign/ にあります。

修正法は、きちんと一時変数を置いて共有参照を使う部分と可変参照を使う部分を分離することです。
これがエラーにならず警告止まりなのは互換性維持のための経過措置なので、利用することは好ましくありません。

以下は実際にプリミティブ型とユーザー定義型で挙動が変わる例です。

use std::ops::AddAssign;

fn main() {
    two_phase_borrow_exception_with_primitive_type();
    two_phase_borrow_not_works_with_non_primitive_type();
}

fn two_phase_borrow_exception_with_primitive_type() {
    let mut v: Vec<usize> = vec![1, 2];
    v[0] += v[1];
    println!("With usize: {:?}", v);
}

fn two_phase_borrow_not_works_with_non_primitive_type() {
    let mut v: Vec<UserUsize> = vec![UserUsize(1), UserUsize(2)];
    v[0] += v[1];
    println!("With UserUsize: {:?}", v);
}

#[derive(Debug, Clone, Copy)]
struct UserUsize(usize);

impl AddAssign for UserUsize {
    fn add_assign(&mut self, other: UserUsize) {
        self.0 += other.0;
    }
}
0
- c[i+1][j] += tmp;
- c[i+1][j+1] += tmp;

+ let tmp = c[i][j];
+ c[i+1][j] += tmp;
+ c[i+1][j+1] += tmp;

以上の修正でワーニングが出なくなりましたが、良い方法とは言えません

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。