如何为添加两个泛型类型的引用编写特质限定？

Question

我有一个 Fibonacci 结构体，可以用作任何实现了 One、Zero、Add 和 Clone 的迭代器。这对于所有整数类型都很有效。

我想要将此结构体用于实现了 Vec 的 BigInteger 类型，但是调用 clone() 的开销很大。我希望可以在两个 T 的引用上使用 Add，然后返回一个新的 T（不需要克隆）。

但是我尝试编写代码始终无法成功编译...

以下是可行的代码：

extern crate num;

use std::ops::Add;
use std::mem;
use num::traits::{One, Zero};

pub struct Fibonacci<T> {
    curr: T,
    next: T,
}

pub fn new<T: One + Zero>() -> Fibonacci<T> {
    Fibonacci {
        curr: T::zero(),
        next: T::one(),
    }
}

impl<'a, T: Clone + Add<T, Output = T>> Iterator for Fibonacci<T> {
    type Item = T;

    fn next(&mut self) -> Option<T> {
        mem::swap(&mut self.next, &mut self.curr);
        self.next = self.next.clone() + self.curr.clone();
        Some(self.curr.clone())
    }
}

#[test]
fn test_fibonacci() {
    let first_12 = new::<i64>().take(12).collect::<Vec<_>>();
    assert_eq!(vec![1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144], first_12);
}

期望的结果：

extern crate num;

use std::ops::Add;
use std::mem;
use num::traits::{One, Zero};

pub struct Fibonacci<T> {
    curr: T,
    next: T,
}

pub fn new<T: One + Zero>() -> Fibonacci<T> {
    Fibonacci {
        curr: T::zero(),
        next: T::one(),
    }
}

impl<'a, T: Clone + 'a> Iterator for Fibonacci<T>
where
    &'a T: Add<&'a T, Output = T>,
{
    type Item = T;

    fn next(&mut self) -> Option<T> {
        mem::swap(&mut self.next, &mut self.curr);
        self.next = &self.next + &self.curr;
        Some(self.curr.clone())
    }
}

#[test]
fn test_fibonacci() {
    let first_12 = new::<i64>().take(12).collect::<Vec<_>>();
    assert_eq!(vec![1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144], first_12);
}

这会导致错误。

error[E0495]: cannot infer an appropriate lifetime for borrow expression due to conflicting requirements
  --> src/main.rs:27:21
   |
27 |         self.next = &self.next + &self.curr;
   |                     ^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 25:5...
  --> src/main.rs:25:5
   |
25 | /     fn next(&mut self) -> Option<T> {
26 | |         mem::swap(&mut self.next, &mut self.curr);
27 | |         self.next = &self.next + &self.curr;
28 | |         Some(self.curr.clone())
29 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> src/main.rs:27:21
   |
27 |         self.next = &self.next + &self.curr;
   |                     ^^^^^^^^^^
note: but, the lifetime must be valid for the lifetime 'a as defined on the impl at 19:1...
  --> src/main.rs:19:1
   |
19 | / impl<'a, T: Clone + 'a> Iterator for Fibonacci<T>
20 | | where
21 | |     &'a T: Add<&'a T, Output = T>,
22 | | {
...  |
29 | |     }
30 | | }
   | |_^
note: ...so that types are compatible (expected std::ops::Add, found std::ops::Add<&'a T>)
  --> src/main.rs:27:32
   |
27 |         self.next = &self.next + &self.curr;
   |                                ^

error[E0495]: cannot infer an appropriate lifetime for borrow expression due to conflicting requirements
  --> src/main.rs:27:34
   |
27 |         self.next = &self.next + &self.curr;
   |                                  ^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 25:5...
  --> src/main.rs:25:5
   |
25 | /     fn next(&mut self) -> Option<T> {
26 | |         mem::swap(&mut self.next, &mut self.curr);
27 | |         self.next = &self.next + &self.curr;
28 | |         Some(self.curr.clone())
29 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> src/main.rs:27:34
   |
27 |         self.next = &self.next + &self.curr;
   |                                  ^^^^^^^^^^
note: but, the lifetime must be valid for the lifetime 'a as defined on the impl at 19:1...
  --> src/main.rs:19:1
   |
19 | / impl<'a, T: Clone + 'a> Iterator for Fibonacci<T>
20 | | where
21 | |     &'a T: Add<&'a T, Output = T>,
22 | | {
...  |
29 | |     }
30 | | }
   | |_^
note: ...so that reference does not outlive borrowed content
  --> src/main.rs:27:34
   |
27 |         self.next = &self.next + &self.curr;
   |                                  ^^^^^^^^^^

- dten

---

你可能会对std::ops::AddAssign感兴趣，它的RFC处于最终评论期：它允许您重载“+=”运算符。这将允许避免至少一些.clone()调用来进行加法操作。 - Matthieu M.

那将会少一个克隆 :) 不过我不能同时去掉两个。不过，我猜还有12周左右呢。 - dten

实际上少了两个克隆：self.next = self.next.clone() + self.curr.clone(); 将被替换为 self.next += &self.curr;。 - Matthieu M.

奇怪，我以为“由于冲突的要求无法推断生命周期……”会列出这些冲突的要求。 - Jan Hudec

Answer 1

如何编写用于添加泛型类型的两个引用的特质绑定？ 让我们从一个简化的例子开始：

fn add_things<T>(a: &T, b: &T) {
    a + b;
}

这里有一个错误

error[E0369]: binary operation `+` cannot be applied to type `&T`
 --> src/lib.rs:2:5
  |
2 |     a + b;
  |     ^^^^^
  |
  = note: an implementation of `std::ops::Add` might be missing for `&T`

正如编译器提示的那样，我们需要保证对于 &T，Add 得到了实现。我们可以通过为类型添加显式生命周期并在 trait 约束中使用它来直接表达这一点：

use std::ops::Add;

fn add_things<'a, T>(a: &'a T, b: &'a T)
where
    &'a T: Add,
{
    a + b;
}

接下来，让我们尝试一种略微不同的方法——不是被交给一个引用，而是在函数内部创建一个引用：

fn add_things<T>(a: T, b: T) {
    let a_ref = &a;
    let b_ref = &b;

    a_ref + b_ref;
}

我们遇到了相同的错误：

error[E0369]: binary operation `+` cannot be applied to type `&T`
 --> src/lib.rs:5:5
  |
5 |     a_ref + b_ref;
  |     ^^^^^^^^^^^^^
  |
  = note: an implementation of `std::ops::Add` might be missing for `&T`

然而，尝试像之前一样添加修复程序并不起作用。这也有点棘手，因为生命周期与传递的任何参数都没有关联：

use std::ops::Add;

fn add_things<'a, T: 'a>(a: T, b: T)
where
    &'a T: Add,
{
    let a_ref = &a;
    let b_ref = &b;

    a_ref + b_ref;
}

error[E0597]: `a` does not live long enough
  --> src/lib.rs:7:17
   |
3  | fn add_things<'a, T: 'a>(a: T, b: T)
   |               -- lifetime `'a` defined here
...
7  |     let a_ref = &a;
   |                 ^^
   |                 |
   |                 borrowed value does not live long enough
   |                 assignment requires that `a` is borrowed for `'a`
...
11 | }
   | - `a` dropped here while still borrowed

将生命周期'a放在impl上意味着方法的调用者决定生命周期应该是什么。由于引用是在方法内部获取的，调用者甚至无法看到那个生命周期是什么。

相反，您希望对任意生命周期的引用施加实现特征的限制。这被称为高阶特质边界（HRTB）：

use std::ops::Add;

fn add_things<T>(a: T, b: T)
where
    for<'a> &'a T: Add,
{
    let a_ref = &a;
    let b_ref = &b;

    a_ref + b_ref;
}

---

应用到你的原始代码中，你已经非常接近了：

impl<T> Iterator for Fibonacci<T>
where
    T: Clone,
    for<'a> &'a T: Add<Output = T>,
{
    type Item = T;

    fn next(&mut self) -> Option<T> {
        mem::swap(&mut self.next, &mut self.curr);
        self.next = &self.next + &self.curr;
        Some(self.curr.clone())
    }
}

另请参阅:

• 当其中一个是本地引用时，如何编写类型约束中引用的生命周期?
• for<>语法与常规生命周期限定有何不同?
• 在泛型函数中如何要求泛型类型实现Add、Sub、Mul或Div等操作?

- Shepmaster

---

你知道如何消除最后一个克隆吗？直觉上，我认为实际数字必须在迭代器之外，但我无法使其工作。 - Matthieu M.

@MatthieuM。我不知道如何消除这个克隆，因为“current”值被结构保存，但我们也想从迭代器中返回它。我的下一个想法是返回对“current”的引用，但这需要给“self”加上生命周期，这是不可行的。你能详细说明一下你的“在迭代器之外”的想法吗？ - Shepmaster

我的想法是创建一个状态 struct 来保存状态，然后再创建另一个迭代器 struct 引用第一个 (&mut) 并在“前进”时对其进行修改，以便迭代器可以返回到状态的引用；但我无法管理好我的借用。 - Matthieu M.

@MatthieuM. 很有趣。类似于这个吗？它似乎有与将引用返回到迭代器本身相同的问题。这两种实现似乎是同构的，但我无法确定原因。 - Shepmaster

@MatthieuM。这一定是由于别名引起的。如果我们返回一个引用，那么在后续对next的调用之前，该引用必须消失，否则就会出现别名引用，尤其是存在可变引用和不可变引用的情况下更容易出问题。 - Shepmaster

类似于http://is.gd/NmZFNs，我怀疑问题在于返回的引用需要借用当前迭代器以确保它不会在我们的脚下迭代。 - Matthieu M.