add a trait for smart pointer dereference

[thestinger]

At a minimum, a trait for obtaining an immutable reference from a type used to overload *x and &*x.

Obtaining mutable references and moving out of pointers can be left out, as they're only useful on a unique pointer type. It can be revisited in the future if a compelling use case ever comes up.

[pnkfelix]

Visiting for bug triage, email from 2013-08-12
@thestinger : My best guess is that you want a trait that provides something analogous to operator new(size_t) allocation static method in C++, and then when one uses the ~<expr> or @<expr> forms, it would implicitly call out to the trait's implementation of that allocation method? Can you confirm this, or provide more specific information on what you are proposing?

(Thinking off the top of my head, the GC guy in me figures we might need or at least want to have two methods in the Trait, or via some other analogous manner provide information about whether the context of the invocation is ~ or @.)

[pnkfelix]

Also, I think pcwalton's blog post and his plans for smart-pointers, moving GC to a library, etc, are relevant material here.

[brson]

Being able to override dereference is looking increasingly important as we jettison pointer types, and probably newtype dereferencing (#6246), from the language. Nominating.

[nikomatsakis]

cc me

[pnkfelix]

i'm not sure what I was thinking in my first comment above, since @thestinger is clearly talking about pointer-dereference, not memory allocation.

[pnkfelix]

accepted for 1.0 backcompat lang.

[pcwalton]

Nominating as I believe this is out of scope for 1.0. We can just special case GC.

[huonw]

What about Rc?

[pnkfelix]

deferring decision about any change in p-status for this bug until we can meet with pcwalton

[pnkfelix]

leaving on 1.0 for now. (If later work with box construct proves it to be unneeded, we'll remove it then.)

[larsbergstrom]

I'd love to see this for use in Rc and Cell \ RefCell scenarios. We have code all over Servo post-@mut removal that looks like source_frame.borrow().children.borrow_mut().get().mut_iter() and reads much better as source_frame.children.mut_iter().

[nikomatsakis]

I've been wanting to write up something more detailed but failing, so let me sketch out the design I had in mind.

Basically we had two traits:

trait DerefImm<E> {
    fn deref<'a>(&'a self) -> &'a E;
}

trait DerefMut<E> : DerefImm<E> {
    fn deref<'a>(&'a mut self) -> &'a mut E;
}

The structure of these traits encodes an "inherited mutability" like structure -- in other words, these traits can faithfully model Rc<T>, Gc<T>, and ~T but not &mut T nor RefCell<T>, which each have their own complications.

I don't intend to ever permit smart pointers that act like &mut T. Basically an &mut T is mutable if it's in a unique location, whereas these smart pointers (like ~T) are mutable if they are in a mutable (note: implies unique) location. At worst this means smart pointers need an extra mut declaration.

RefCell<T> we might like to support someday but I'm not sure. There is value in having the fallible borrows be highlighted. Note however that we can use this trait for the Ref and RefMut types that RefCell returns (in fact, RefMut is a good example of a case where it might be nice to act like &mut but oh well).

I think the implementation here has to go in two phases:

1. Add support for explicit uses, e.g. *x, &*x, or (*x).method().
2. Add support for implicit autoderefs. This has additional complications I don't want to go into just yet since I don't have time.

For step 1, one challenge is that we have to instrument type check to pass down more context. In particular, to type check an expression, we have to know whether it is in a "mutable lvalue" context or not. For example, when we type check the expression *E in &mut *E, we will want to use the DerefMut trait. But if we type check the same *E in the context of &*E it will use the DerefImm trait.

The other challenge is that the trait returns a reference &T, but the "type" of *E is T. That means we need to insert an autoderef adjustment. Currently our system is geared to the idea that when we type check an expression there are no adjustments, and then the context may add adjustments. In this case, the type check of the expression itself would insert an adjustment. This means we have to modify the various routines in the function context to take into account the possible presence of an adjustment:

• write_autoderef_adjustment()
• write_adjustment()
• expr_ty() probably wants to return the adjusted type (and maybe to be renamed to reflect that)

The adjustment data structure itself could be refactored to make this nicer (into something more layerable, like a cons list of adjustments), but I'd hold off on that since it's adequate for the current purpose.

OK, that's a high-level sketch, happy to provide more details on request.

[nikomatsakis]

(And I do plan to write up a proper RFC with more details and examples... but I'm working on several of those)

[nikomatsakis]

Ah, one other comment: I have intentionally not provided a way to move out of a Smaht<T>. This is tricky because you want to invalidate the pointer iff T is POD, and there's not a good way to write that in a trait. Perhaps it's better to have a separate trait not tied to an operator with a method like get(). This (might) also imply that we do not permit moves out of ~, preferring the trait version -- or else we make ~ just a little sweeter than a smart pointer can be, just as &mut is just a little sweeter. I'm basically fine with either path.

[nikomatsakis]

Actually, thinking more, I think it's plausible to support an additional trait:

trait DerefMove<E> : DerefImm<E> {
    fn deref_copy(&self) -> E;
}

But it should be added as a later step, because there are some significant complications (actually similar to support auto-deref). Basically we have to first type one way (assuming no move, most likely) and then go back and patch things up once we know the type of E, which may impact how other expressions are typed. This is going to take a bit of work to figure out the most elegant way to implement -- I'm envisioning some kind of "prospective" vtable resolution.

Note that I've been careful to ensure that, if you implement DerefImm<E>, all other deref traits deref to the same type E (though I'm vaguely worried about variance; but I think it works out ok, since even if you implemented DerefMove for a type F <: E, we'd just wind up typing the expression as E which is a valid typing).

[pnkfelix]

@nikomatsakis wrote:

I don't intend to ever permit smart pointers that act like &mut T. Basically an &mut T is mutable if it's in a unique location, whereas these smart pointers (like ~T) are mutable if they are in a mutable (note: implies unique) location. At worst this means smart pointers need an extra mut declaration.

We used to have @mut T, and that was one way to hold a mutable reference within an otherwise immutable structure. I take it that we would not be able to support whatever replaces @mut T as a first-class smart-pointer, at least not under the policy you describe above. (Maybe that is exactly what you were talking about when you said "RefCell we might like to support someday but I'm not sure" ? Just checking my understanding.)

(edit: I mean "first-class smart pointer" in the sense that one could do fn foo(x: ~@mut int) { **x = 3; })

[nikomatsakis]

Right, the official way to do @mut is a refcell in a gc pointer. It won't be as seamless as @mut was but that it at least partially considered to be a feature.

[glaebhoerl]

@nikomatsakis:

I have intentionally not provided a way to move out of a Smaht<T>. This is tricky because you want to invalidate the pointer iff T is POD

Did you mean "isn't"? (I hope so, otherwise I understand nothing.)

If you wanted to copy out a POD type wouldn't DerefImm suffice?

trait DerefMove<E> : DerefImm<E> {
    fn deref_copy(&self) -> E;
}

I also don't quite grok this... was this meant to be called DerefCopy rather than DerefMove, with the intention that it would only be implemented for E: Pod types? (If it's actually for moving something out, then the types don't seem very appropriate.)

[nikomatsakis]

@glaebhoerl indeed, I meant isn't, and I think the DerefMove trait I had in mind was rather something like:

trait DerefMove<E> : DerefImm<E> {
    fn deref_move(self) -> E;
}