[rust-dev] Question about lifetimes in type parameters
I have a largeish buffer containing bytes that I would like to avoid copying. The first thing I have to do with this buffer is parse it into a hashmap structure. To that end, I have the following function: fn line_map<'b>(buffer : &'b [u8]) -> ~LinearMap<&'b [u8],&'b [u8]> {...} The problem I am running into is that the type of the LinearMap's find() method (Yes, this is 0.6.) is: fn find(&self, k: &&'b [u8]) -> Option<&'self &'b [u8]> In other words, the key argument is a borrowed pointer to a borrowed pointer to a vector with the same lifetime as the buffer. That argument is kind of difficult to provide. What am I doing wrong? Is there a better way? -- Tommy M. McGuire mcgu...@crsr.net ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Question about lifetimes in type parameters
On Tue, May 28, 2013 at 01:48:55PM -0500, Tommy M. McGuire wrote: > The problem I am running into is that the type of the LinearMap's find() > method (Yes, this is 0.6.) is: > > fn find(&self, k: &&'b [u8]) -> Option<&'self &'b [u8]> > > In other words, the key argument is a borrowed pointer to a borrowed > pointer to a vector with the same lifetime as the buffer. That argument > is kind of difficult to provide. First, I'm sure you've heard this before, but you'll probably be happier if you bite the bullet and upgrade to incoming. There are a lot of bugs fixed around the treatment of lifetimes, and more to come. That said, why is a `&&[u8]` so difficult to provide? You can do something like this: let my_slice: &[u8] = my_vec.slice(from, to); match map.find(&my_slice) { ... } Or even: match map.find(&my_vec.slice(from, to)) { ... } > What am I doing wrong? Is there a better way? I think you are doing it right. You may find it easier to just put indices into the map rather than slices, but slices should work too. Niko ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Question about lifetimes in type parameters
On 05/29/2013 04:55 AM, Niko Matsakis wrote: > On Tue, May 28, 2013 at 01:48:55PM -0500, Tommy M. McGuire wrote: >> The problem I am running into is that the type of the LinearMap's find() >> method (Yes, this is 0.6.) is: >> >> fn find(&self, k: &&'b [u8]) -> Option<&'self &'b [u8]> >> >> In other words, the key argument is a borrowed pointer to a borrowed >> pointer to a vector with the same lifetime as the buffer. That argument >> is kind of difficult to provide. > > First, I'm sure you've heard this before, but you'll probably be > happier if you bite the bullet and upgrade to incoming. There are a > lot of bugs fixed around the treatment of lifetimes, and more to come. Yes, yes. I know. :-) I'm in the process of doing that, now. > That said, why is a `&&[u8]` so difficult to provide? You can do > something like this: > > let my_slice: &[u8] = my_vec.slice(from, to); > match map.find(&my_slice) { ... } > > Or even: > > match map.find(&my_vec.slice(from, to)) { ... } > >> What am I doing wrong? Is there a better way? > > I think you are doing it right. You may find it easier to just put > indices into the map rather than slices, but slices should work too. 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. Here's the complete file: https://gist.github.com/tmmcguire/5674103#file-gistfile1-rs -- Tommy M. McGuire mcgu...@crsr.net ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Question about lifetimes in type parameters
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. Niko ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Question about lifetimes in type parameters
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 mcgu...@crsr.net ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Question about lifetimes in type parameters
Hi, sorry I haven't had a chance to look at this yet, I'll try to get to it today! 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 > mcgu...@crsr.net ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Question about lifetimes in type parameters
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(filename : &str, f : &fn(v : &[u8]) -> U) -> U { fail!() } pub fn each_combination(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(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, th
Re: [rust-dev] Question about lifetimes in type parameters
Ah, one thouht, you may want to be more careful with the def'n of IterBytes on MapKey to be sure that the hashcodes are the same. Niko On Sat, Jun 01, 2013 at 06:46:00AM -0400, Niko Matsakis wrote: > 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(filename : &str, f : &fn(v : &[u8]) -> U) > -> U { > fail!() > } > > pub fn each_combination(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(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