"Conflicting requirements" 作为参数传递给方法的迭代器项的生命周期

Question

我正在尝试编译此代码：

use std::collections::HashMap;

#[derive(PartialEq, Eq, Hash, Clone)]
struct Key<'a> {
    v: &'a str
}

fn make_key_iter(s: &str) -> Box<Iterator<Item = Key>> {
    Box::new(s.split('.').map(|e| Key { v: e }))
}

struct Node<'a> {
    children: HashMap<Key<'a>, Box<Node<'a>>>
}

impl<'a> Node<'a> {
    fn lookup<'b>(&self, mut iter: Box<Iterator<Item = Key<'b>>>) -> bool {
        match iter.next() {
            Some(key) => match self.children.get(&key) {
                             Some(node) => node.lookup(iter),
                             None => false
                         },
            None => true
        }
    }
}

fn main() {
    let s = "a.b.c.d".to_string();
    let iter = make_key_iter(s.as_slice());
    let node = Node { children: HashMap::new() };
    node.lookup(iter);
}

Playpen link

编译出现以下错误：

<anon>:18:20: 18:26 error: cannot infer an appropriate lifetime due to conflicting requirements
<anon>:18         match iter.next() {
                         ^~~~~~
<anon>:17:5: 25:6 help: consider using an explicit lifetime parameter as shown: fn lookup(&self, mut iter: Box<Iterator<Item = Key<'b>>>) -> bool

真正令人困惑的是，编译器建议的签名完全无效，因为它使用了未定义的生命周期。

Answer 1

我同意诊断不太理想。我建议提交错误；也许那个建议者还不知道关联类型的生命周期。

为了解决您的问题，我建议您使用与您已经拥有的生命周期相同的生命周期：

impl<'a> Node<'a> {
    fn lookup(&self, mut iter: Box<Iterator<Item = Key<'a>>>) -> bool { //'
        match iter.next() {
            Some(key) => match self.children.get(&key) {
                             Some(node) => node.lookup(iter),
                             None => false
                         },
            None => true
        }
    }
}

实际上我不清楚您的原始代码试图做什么。您定义了一个新的生命周期参数 'b。该生命周期将由调用者为每次调用确定。这是个坏消息，因为该生命周期可能比 Node 本身持续时间更长，从而导致对不再有效的内存的引用。耶！ Rust 拯救了我们！

另一个解决方案是有一个显式的生命周期 'b，但是告诉 Rust 它 ~~比 'a 短或等于 'a（说 "a outlives b"）~~长于等于'a（表示"b outlives a"）：

fn lookup<'b : 'a>(&self, mut iter: Box<Iterator<Item = Key<'b>>>) -> bool

进一步阐述

这是一个显示相同问题的小例子：

use std::collections::HashSet;

fn example<'a, 'b>(set: HashSet<&'a u8>, key: &'b u8) -> bool {
    set.contains(&key)
}

fn main() {}

类似地，如果您设置生命周期之间的关系 (<'a, 'b : 'a>) 或使两个参数具有相同的生命周期，则此代码将编译。

两者 HashSet::contains and HashMap::get lookup the key by taking a reference to the key type (or something that can lend out a reference 到密钥类型）。但是，您正在查找的密钥必须与您存储的类型（或子类型）相同。在这种情况下，类型 还包括生命周期 。这就是为什么使用相同的生命周期（或超过密钥的生命周期）允许它编译的原因。

Answer 2

首先，一个建议：由于盒装迭代器也是迭代器，您可以将查找函数更改为

fn lookup<'b, I: Iterator<Item = Key<'b>>>(&self, mut iter: I) -> bool {
    match iter.next() {
        Some(key) => match self.children.get(&key) {
                         Some(node) => node.lookup(iter),
                         None => false
                     },
        None => true
    }
}

这有点笼统。但问题仍然存在。您正在尝试将 self.children.get(&key) 中的 &Key<'b> 传递给实际上需要 &Q 的 HashMap，其中 Q 实现 BorrowFrom<Key<'a>>。编译器的建议是现在将 'b 替换为 'a，如下所示：

fn lookup<I: Iterator<Item = Key<'a>>>(&self, mut iter: I) -> bool { //'
    match iter.next() {
        Some(key) => match self.children.get(&key) {
                         Some(node) => node.lookup(iter),
                         None => false
                     },
        None => true
    }
}

这肯定会让编译器满意。但这并不是您真正想要的！它会不必要地限制您可以用作查找参数的字符串切片集。这样，您只能使用引用内存的字符串切片，这些内存至少与 'a 所引用的范围一样长。但对于查找，实际上不需要此限制。

解决方案是完全去掉 HashMap 的 get 函数的类型参数 Q 中的任何生命周期参数。我们实际上可以使用 Q=str 而不是 Q=Key<'something>。我们只需要添加以下 BorrowFrom 实现

impl<'a> BorrowFrom<Key<'a>> for str {
    fn borrow_from<'s>(owned: &'s Key<'a>) -> &'s str {
        owned.v
    }
}

并使 Key 类型为 public（因为它被用作 public 特征中的参数）。对我有用的查找函数如下所示：

fn lookup_iter<'b, I: Iterator<Item = Key<'b>>>(&self, mut i: I) -> bool {
    if let Some(key) = i.next() {
        match self.children.get(key.v) {
            Some(node_box_ref) => node_box_ref.lookup_iter(i),
            None => false
        }
    } else {
        true
    }
}

如果我们把所有东西拼凑起来，我们会得到

#![feature(core)]
#![feature(hash)]
#![feature(std_misc)]
#![feature(collections)]

use std::collections::HashMap;
use std::collections::hash_map::Entry::{ Occupied, Vacant };
use std::borrow::BorrowFrom;

#[derive(PartialEq, Eq, Hash, Clone)]
pub struct Key<'a> {
    v: &'a str
}

impl<'a> BorrowFrom<Key<'a>> for str {
    fn borrow_from<'s>(owned: &'s Key<'a>) -> &'s str {
        owned.v
    }
}

fn str_to_key(s: &str) -> Key { 
    Key { v: s }
}

struct Node<'a> {
    children: HashMap<Key<'a>, Box<Node<'a>>>
}

impl<'a> Node<'a> {
    fn add_str(&mut self, s: &'a str) {
        self.add_iter(s.split('.').map(str_to_key))
    }

    fn add_iter<I>(&mut self, mut i: I) where I: Iterator<Item = Key<'a>> { //'
        if let Some(key) = i.next() {
            let noderef =
                match self.children.entry(key) {
                    Vacant(e) => {
                        let n = Node { children: HashMap::new() };
                        e.insert(Box::new(n))
                    }
                    Occupied(e) => {
                        e.into_mut()
                    }
                };
            noderef.add_iter(i);
        }
    }

    fn lookup_str(&self, s: &str) -> bool {
        self.lookup_iter(s.split('.').map(str_to_key))
    }

    fn lookup_iter<'b, I>(&self, mut i: I) -> bool where I: Iterator<Item = Key<'b>> {
        if let Some(key) = i.next() {
            match self.children.get(key.v) {
                Some(node_box_ref) => node_box_ref.lookup_iter(i),
                None => false
            }
        } else {
            true
        }
    }
}

fn main() {
    let mut node: Node<'static> = Node { children: HashMap::new() }; //'
    node.add_str("one.two.three");
    { // <-- "inner scope"
        let s = String::from_str("one.two.three");
        println!("lookup: {:?}", node.lookup_str(&*s));
    }
    println!("The End");
}

大家可以看到，我特意把node弄成了Node<'static>，所以节点的生命周期参数'a其实就是指整个程序的生命周期。在此示例中没问题，因为它将存储的唯一字符串切片是字符串文字。请注意，对于查找，我创建了一个短暂的 String 对象。所以，node.lookup_str中的生命周期参数'b会引用明显比'a='static短的"inner scope"。一切顺利！ :)

哦，我也摆脱了迭代器装箱。

"Conflicting requirements" 作为参数传递给方法的迭代器项的生命周期

"Conflicting requirements" for lifetime of item of iterator passed as parameter to method

rust

lifetime

进一步阐述