[rust-dev] Question about lifetimes in type parameters

Niko Matsakis niko at alum.mit.edu
Sat Jun 1 03:46:00 PDT 2013


OK, I finally got a chance to take a look. Indeed, this is not a bug,
I just misunderstood what was going on. The problem is that the key is
`&'b [u8]` but you can't supply precisely that type, because the key
you are using to do th elookup has a shorter lifetime. This is true and
the type checker is right to complain.

What you want is to do in these situations is to use the `find_equiv`
method, which demands a key that is not necessarily the *same* type as
what is in the map but just one comparable to it. Unfortunately, we
don't have an equivalence for two slices of unequal lifetimes right
now (and we can't right one at the moment due to some limitations that
I am supposed to be lifting). Annoyingly, we also don't have an
equivalence from ~[u8] to &[u8], only in the reverse direction. We
should fix this, but usually people have ~[u8] as the key and &[u8] as
the equivalent lookup key, not the other way around.

However, you can workaround this limitation using a "new type" struct.
Here is a version that works. The main trick is to add a temporary
type `MapKey` for which we can define the `Equiv` trait so that it can
be compared to the slices that are in your table.


```
extern mod extra;
use std::vec;
use std::hashmap::*;
use std::os;
use std::str;
use std::uint;
use std::cmp::eq;

#[deriving(IterBytes)]
struct MapKey(~[u8]);
impl<'self> Equiv<&'self [u8]> for MapKey {
    fn equiv(&self, other: & &'self [u8]) -> bool {
        let slice1: &[u8] = **self;
        let slice2: &[u8] = *other;
        slice1 == slice2
    }
}

pub fn with_mmap_file_contents<U>(filename : &str, f : &fn(v : &[u8]) -> U) -> U {
    fail!()
}

pub fn each_combination<T:Copy>(values : &[T], r : uint, fun : &fn(combo : &[T]) -> bool) -> bool {
    fail!()
}

fn get_letters(s : &str) -> ~[u8] {
    let mut t = str::to_chars(s);
    extra::sort::quick_sort(t, |a,b| *a <= *b);
    return vec::from_fn(t.len(), |i| t[i] as u8);
}

fn line_map<'b>(buffer : &'b [u8]) -> ~HashMap<&'b [u8],&'b [u8]> {
    let length = buffer.len();
    let mut map = ~HashMap::new();
    let mut i = 0;
    while i < length {
        let mut j = i;
        while j < length && buffer[j] != ' ' as u8 { j += 1; }
        let mut k = j+1;
        while k < length && buffer[k] != '\n' as u8 { k += 1; }
        map.insert(vec::slice(buffer, i, j), vec::slice(buffer, j+1, k));
        i = k + 1;
    }
    return map;
}

fn search<'b>(letters : &[u8], dictionary : &'b HashMap<&'b [u8],&'b [u8]>) -> ~HashSet<&'b [u8]>
{
    let mut set = ~HashSet::new();
    for uint::range(2, letters.len() + 1) |i| {
        let mut key = MapKey(vec::from_elem(i, 0));
        // pub fn each_combination<T:Copy>(values : &[T], r : uint, fun : &fn(combo : &[T]) -> bool) -> bool
        for each_combination(letters,i) |combo| {
            for combo.eachi |j,&ch| { key[j] = ch; }
            {
                match dictionary.find_equiv(&key) {
                    Some(val) => {
                        set.insert(*val);
                    }
                    None => { }
                }
            }
        }
    }
    return set;
}

fn main() {
    let args = os::args();
    if args.len() < 2 {
        fail!(~"Usage: anagrams letters");
    }
    let letters = get_letters(args[1]);
    do with_mmap_file_contents("anadict-rust.txt") |buf| {
        let map = line_map(buf);
        let set = search(letters, map);
        // Just count them for now...
        let mut count = 0;
        for set.each |ln| {
            count += 1 + vec::count(*ln, &(' ' as u8));
        }
        println(fmt!("%?", count));
    }
}
```


Niko

On Thu, May 30, 2013 at 09:00:32AM -0500, Tommy M. McGuire wrote:
> On 05/30/2013 05:09 AM, Niko Matsakis wrote:
> > On Wed, May 29, 2013 at 04:55:31PM -0500, Tommy M. McGuire wrote:
> >> The problem is that I want to use a completely unrelated vector as the
> >> argument to find() instead of an alias for part of the buffer or a pair
> >> of indices into the buffer.
> >>
> >> Currently, with my quick change to incoming, the code
> >>
> >>                 let kkey : &[u8] = key;       // key : ~[u8]
> >>                 match dictionary.find(&kkey) {
> >>
> >> produces:
> >>
> >> 55:38 error: borrowed value does not live long enough
> >>             let kkey : &[u8] = key;
> >>                                ^~~
> >> 67:1 note: borrowed pointer must be valid for the lifetime
> >> &br_named({repr: 83, ctxt: 0})  as defined on the block at 48:0...
> >> ...
> >> 65:5 note: ...but borrowed value is only valid for the block at 50:46
> >>
> >> The lifetime '&br_named(...)' stuff should be "'b", the lifetime
> >> parameter of the function (the block at 48:0) that is associated with
> >> the keys and values from the HashMap (was LinearMap) and the buffer.
> > 
> > This seems like a bug (also, what a lousy error message! sorry.), I
> > will further investigate.
> 
> Thanks! (The error message changed when I updated incoming, so it's
> something recent.)
> 
> I'm not sure it is a bug, though. I may not be understanding lifetimes
> well enough, but I think the interaction between that and generics is
> problematic. In this case, there doesn't seem to be enough information
> to tell the difference between find(), for which the lifetime argument
> is not terribly useful, and insert(), where it would be.
> 
> 
> -- 
> Tommy M. McGuire
> mcguire at crsr.net


More information about the Rust-dev mailing list