[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
