Anyway to get Ref::map functionality for Rc?

1

I swear I've used a Rc::map before, similar to Ref::map and RefMut::map, e.g. taking an Rc<T> and giving back a Rc<U>, where U is some inner component of T, but I can't find it in the docs. I've also tried searching crates.io for "rc map" and can't seem to locate it. IIRC the single pointer representation for Rc makes this not possible out of the box, so it's possible I had to use a different Rc implementation. Anyone know where I can get this functionality?

2

There is mappable-rc. I don't know if this is the one you were talking about. It doesn't look very popular, but it appears to do what you describe.

2 Likes
3

It's also easy to roll your own.

2 Likes
4

That's not supported because Rc is just the pointer to the allocated thing, and its code knows how to go backwards from that to where the ref count is found.

C++'s shared_ptr supports that, but at the cost of it being two pointers, so that it can have one to the reference counts and one to the data, and thus support arbitrary mapping.

So as always, it's a tradeoff.

2 Likes
5

I was wondering how it was going to be easy without getting into OwningRef style problems but just storing the projection and reapplying it every use is pretty elegant (although potentially expensive if the projection is complex).

1 Like
6

I'd probably recommend using mappable-rc at the moment, but for completeness, I've also published a shared-rc crate. The main difference is that shared-rc offers a bit more control, including having a non-'static and/or non-dyn owning type if you want, along with offering Weak versions. I wasn't able to find mappable-rc when I made shared-rc, though I know I've seen it before.

(@jgarvin pointed out an annoying type bug where I bounded my Clone impl improperly so shared-rc is kinda useless at the moment...)

... And my crate is probably completely unsound at the moment due to improper Send/Sync impl bounds. Oof.

2 Likes
7

Although I'd take that any time over OwningRef and other hacks. When I start dealing with Rcs, my brain shouts "cache miss", and so I don't generally care about performance when I see fn(&T) -> &U projections.)

1 Like
8

I tried your RcMap and ran into the obvious limitation that fn can't store any data. It seems silly though, because surely I could augment the RcMap to have a user_data field, and users could choose to make it a ZST type when not using it. But real closures in Rust won't let you return references to captured data which seems equivalent? My confusion over this should maybe be another thread :stuck_out_tongue:

9

That is certainly not correct. You can absolutely return a reference to captured data, see this example.

The reason why I used fn is two-fold:

  1. I had trouble getting the correct HRTB annotations necessary for this to work. I don't think it's actually possible: closures are not generic, so as far as I understand, one can't create a closure with a higher-rank lifetime annotation.
  2. Storing a concrete fn type avoids noise (and makes the type easier to use as an explicit annotation) by not requiring a third generic parameter F to describe the type of the projection function.

However, I'm curious why you require a non-pure projection. It seems surprising (in a bad way) not to derive the value of map() exclusively from the provided original data.

10

Ah I recently ran into this and falsely generalized it to shared refs: Rust Playground

For this what I said about manually passing in the user data being equivalent and allowed still stands though? I'm not sure where this requirement comes from.

11

No. One problem with that I can immediately notice is invariance. If you desugar the closure manually, you'll see that this essentially leads to the fn(&mut self) -> &'a mut T anti-pattern, the same one that makes many people struggle with implementing mutable lending iterators.

Perhaps you were thinking that the desugaring would have been to put the value directly inside the Closure (equivalent with move |y| ...), but that doesn't help, because then calling the closure's FnOnce impl would drop the captured variable, so you couldn't return a reference to it, either.

1 Like
12

Trying to develop minimal examples of each Rust snag I run into results in finding 2-3 more mysterious things and now I'm so deep I'm not sure where I started :joy: I think I got here because thread locals require you to use LocalKey::with to get access, and I wanted to use information in the outer scope to do a lookup inside a thread local container of containers and return an iterator into the looked up container. But the reference passed into with can't escape the closure scope, so I changed the thread local to be an Rc<ContainerContainer> instead of just ContainerContainer, so I could have the with block just return a clone of the Rc, and then use it outside with. But then I ran into the fact that my goal is to return an iterator into the looked up container, but the Rc is what keeps the outer container alive, so now I have the ouroboros/reffers/rental problem, so I need RcMap or something like it. In other words trying to get some version of this to compile (the x in the closure passed to project is the captured use):

type Foo = Vec<i32>;

type Bar = i8;

#[derive(Default)]
struct ContainerTable(Vec<i8>);

impl ContainerTable {
    fn lookup(&self, _i: &i32) -> &Vec<i8> {
        // For brevity don't have a real implementation, but imagine
        // passing different i32 values return references to different
        // subcontainers.
        &self.0
    }
}

thread_local!(
    static TABLE: shared_rc::Rc<ContainerTable> = shared_rc::Rc::new(ContainerTable::default());
);

fn yield_inner4<'a>(foo: &'a Foo) -> impl Iterator<Item = &'a Bar> {
    foo.iter().flat_map(|x| {
        let mut table: shared_rc::Rc<ContainerTable> = TABLE.with(|table_rc| (*table_rc).clone());
        shared_rc::Rc::project(table, |table: &ContainerTable| &table.lookup(x).iter())
    })
}
1 Like
13

Your real problem (i.e., the root cause) seems to be that you are trying to return a reference into a thread-local. You simply can't do that; the API of LocalKey intentionally only makes it possible for the callable passed to with to use the reference locally.

14

I've used the Rc thread local trick before, you definitely can clone a thread local Rc to outside the with, and you can definitely get a reference to a thing inside an Rc. The error is on the line after I clone the Rc -- I want to return an iterator from project, but project wants me to return a reference, not a new object that happens to have a compatible lifetime attached (Iter has the same lifetime parameter a regular reference would, but since it's not an actual reference my closure won't have the type project wants -- I want to return iter(), but fruitlessly to try to fix have returned &iter()). I have tried permutations where I do more work inside the with block and they do have the problem you're describing, but not this version. But I'll probably make a separate thread about it.

15

Sorry, I thought you were trying to return a reference directly from the closure passed to with.

Looking at the code in more detail, it's clear that you are trying to return a reference to a temporary (the .iter()). Unfortunately, if the projection requires returning a reference, then returning something that isn't a reference (even though it contains one) is not possible unless the return value lives inside the ContainerTable (i.e., it's a real projection as opposed to an arbitrary function). The interface of Rc::project() would need to be changed to allow returning any type with the prescribed lifetime, not only literal references.

16

(The conversation moved on, but anyway...)

This works because it captures some &'a String and returns &'a str; the 'a is a specific lifetime and it's not higher-ranked:

    let x = String::from("hello world");
    let f = |y: usize| -> &str { &x[..y] };

The next one fails because it tries to be a FnMut capturing a &'a mut String and returning a &'a mut str, again with a specific lifetime 'a. That would in turn mean handing out aliasing &muts.

    let mut x = String::from("hello world");
    let f = |y: usize| -> &mut str { &mut x[..y] };

If you can convince the compiler to make this just a FnOnce, it works. (But it's annoying to do so.)

Next, an attempt at what I would describe as "returning a reference to captured data":

    let x = String::from("hello world");
    let f = move |y: usize| -> &str { &x[..y] };

And this can't work in current Rust for similar reasons that lending iterators need a GAT:

  • If you're Fn, you're FnMut
  • If you're FnMut, you're FnOnce
  • FnOnce has a (non-generic) associated type for the output type
    • And that output type is shared with FnMut and Fn

The non-generic associated type is a problem for Fn and FnMut because you can never return a borrow from things you own; you need call(&self, usize) -> &str where the output type is generic based on the input lifetime. A GAT would help here (significantly but not completely, I think).

This is also what you would need to return shorter reborrows of a captured &mut.

The supertrait relationships are a problem because there's no way to soundly have call_once(self, usize) -> &str in the example... other than leaking the closure and everything it owns I suppose. Or rephrased, a (non-generic) associated type is proper for FnOnce, but the implication of FnOnce given FnMut or Fn would have to be broken if they gain GATs / the ability to return distinct types given the same input types more generally. (This would also allow implementing FnMut and Fn for unsized types, hmm...)

Or maybe there could be LendingFn and LendingFnMut or such, or more meta outlandish things; anyway I don't expect any of this to change any time soon.

17

This is exactly how I would have expected Fns to work, because it's how regular functions work with respect to their input arguments. My intuition was that whatever is captured by a closure is equivalent to having a function where the captured data is automatically passed as an argument every call.

18

That is mostly accurate — it's the &self argument.

Where it isn't accurate is that that argument/reference doesn't participate in the signature. When you have impl Fn(&T) -> &U, you get essentially fn [closure]::call<'a>(&self, &'a T) -> &'a U, and the lifetime signature is completely independent of &self.

This was, of course, necessary before GATs were a thing, since the input/output types are set in the signature. This could potentially be relaxed, but we'd need some way of adding in the &self lifetime to the trait signature. It's honestly much simpler to have specific traits for specific use cases here than try to attach it to function call syntax.

2 Likes
19

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.