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

Question

I'm trying to get this code to compile:

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

Compiling that gives the following error:

<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

What's really confusing is that the signature the compiler suggests is invalid altogether because it uses an undefined lifetime.

Answer 1

First, one suggestion: Since a boxed iterator is also an iterator, you can change your lookup function to

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
    }
}

which is a bit more general. But the problem still persists. You're trying to pass a &Key<'b> in self.children.get(&key) to the HashMap which actually expects a &Q where Q implements BorrowFrom<Key<'a>>. The compiler's suggestion is now to replace 'b with 'a like this:

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
    }
}

which surely will make the compiler happy. But this is not really what you want! It would unnecessarily restrict the set of string slices you could use as parameters for your lookup. This way, you can only use string slices which refer to memory that is at least as long-lived as the scope that 'a is referring to. But for a lookup this restriction is not actually needed.

The solution is to completely get rid of any lifetime parameters in the type parameter Q of the HashMap's get function. Instead of using Q=Key<'something>, we can actually use Q=str. We just need to add the following BorrowFrom implementation

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

and make the Key type public (since it's used as parameter in a public trait). The lookup function that worked for me looks like this:

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
    }
}

And if we piece everything together, we get

#![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");
}

As you can see, I deliberately made node a Node<'static>, so the node's lifetime parameter 'a actually refers to the lifetime of the whole program. It's OK in this example because the only string slice it will store is a string literal. Note that for the lookup I created a short-lived String object. So, the lifetime parameter 'b in node.lookup_str will refer to the "inner scope" which is obviously shorter than 'a='static. And it all works out! :)

Oh, I also got rid of the iterator boxing.

Answer 2

I agree that the diagnostics are less-than-ideal. I would recommend that a bug is filed; perhaps that suggester doesn't know about lifetimes in associated types yet.

To fix your problem, I'd suggest using the same lifetime that you are already holding:

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
        }
    }
}

I actually am unclear what your original code was trying to do. You define a new lifetime parameter 'b. That lifetime will be determined by the caller for each call made. That's bad news, because that lifetime might last longer than the Node itself, leading to references to memory that are no longer valid. Yay! Rust saved us!

Another solution would be to have an explicit lifetime 'b, but inform Rust that it's shorter or equal to than 'a (said "a outlives b") longer than or equal to 'a (said "b outlives a"):

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

Further exposition

Here's a smaller example that shows the same problem:

use std::collections::HashSet;

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

fn main() {}

Similarly, if you setup a relationship between the lifetimes (<'a, 'b : 'a>) or make both parameters the same lifetime, then this code will compile.

Both HashSet::contains and HashMap::get lookup the key by taking a reference to the key type (or something that can lend out a reference to the key type). However, the key that you are looking up must be the same type (or subtype) that you have stored. In this case, the type also includes the lifetime. That's why using the same lifetime (or one that outlives the key) allows it to compile.