Placement protocol should not consume Placer

[hanna-kruppe]

This came up in the discussion of #1228, but it's mostly independent from the syntax change proposed there. Currently creating a Place for "placement box" will consume the value that produces the place (the one that's written out in the placement expression, i.e. PLACE in box (PLACE) EXPR). This hasn't been an issue so far because the only implementation (in std and, as far as I can tell, on GitHub overall) in ExchangeHeapSingleton which is Copy. That type (and its public name, boxed::HEAP) is hanging by a thread though, box thing is widely preferred to in (HEAP) thing or in HEAP { thing } or HEAP <- thing or any variant of that.

Some hypothetical types that would implement Placer in the future (such as &Arena and the results of map.entry(k), vec.back()) would likely be Copy or inherently "one-off", but other possible uses of placement box would be ruled out by taking self. Examples raised in #1228 are vec <- thing; (instead of vec.push(thing)), set <- thing; and (disclaimer: my example and pet interest) allocators that can't be behind a & reference.

@pnkfelix said:

I am personally becoming more convinced that it should be &mut self. I spent a while last night looking through my notes to see why I had picked self but did not find a motivating example.

[pnkfelix]

For reference purposes, this issue is proposing that we amend RFC 809, which is what documented the placement protocol. See also potentially relevant discussion at its associated PR #809

[pnkfelix]

The issue description isn't clear about whether it is asking for the argument to be &self or &mut self.

Obviously some use cases would not be satisfied by requiring &mut self, but my gut feeling is that the options here are either leaving it as self or changing it to &mut self -- by default, I want to be able to write a Placer implementation and not have to worry about it being aliased within make_place.

(This should mesh in with the Allocator design, where I am currently planning to use &mut self, and so it should mesh with this.)

[nagisa]

Being one who proposed it initially, I’m personally very strongly in favour (of &mut self).

[hanna-kruppe]

The issue description isn't clear about whether it is asking for the argument to be &self or &mut self.

That's because I haven't made up my mind on that yet. &mut self is the obvious alternative, and I expect that it will turn out to be the best option, but anything that allows the use cases mentioned above can be discussed here. (But for the record, I agree that &self seems undesirable for most use cases because aliasing.)

One such alternative would be leaving the signature to be self but make it easy and neat to have an impl for &mut A even when PLACE usually won't be a &mut reference. In other words, if we can write vec <- thing; and have it desugar to something involving Placer::make_place(&mut vec) while also allowing Placer::make_place(one_off_placer), that's also fine by me. I simply don't know yet if this feasible and a good trade off (implementation complexity etc.).

[arielb1]

@rkruppe

Doesn't malloc use &self (or self with a zero-sized type)?

[hanna-kruppe]

I don't really know what you mean. If this is about "allocators that can't be behind a & reference" in the issue text, I'm not talking about some global allocator like C's malloc, I mean weirder, more specialized ones like Scope Stacks.

[bluss]

You need to be very careful about evaluation order and panic safety, as well as forcing the placer to be used:

vector.back() <- x()

How do we handle panics in x() here? back() will already have ran and created more space in the vector; but it cannot update the length of the vector until after x() has completed without panic.

for just

vector.back(); panic!()

This cannot be allowed, would it leave an unitinialized slot?

[hanna-kruppe]

That's what InPlace::finalize(self) is for, isn't it? Regardless of whether the Placer is Vec or some one-off VecBack type returned by vec.back(), the placement protocol will first retrieve an InPlace from it, get a raw pointer from it, then evaluate x() and ptr::write the result. At the last and final step, InPlace::finalize is called. Only this last step would update the length and it would run after the evaluation of x(). In the case of panics, at worst the vector has re-allocated pointlessly.

All of this is completely independent of whether the first step consumes the Placer or not. Or am I missing something?

[nagisa]

@bluss I see what you mean, but I don’t think it is a problem, because the protocol explicitly addresses preconditions for panic safety:

If evaluating EXPR fails, then the destructor for the implementation of Place to clean up any intermediate state (e.g. deallocate box storage, pop a stack, etc).

-- Last paragraph of std::ops::Place documentation.

---

EDIT: actually it might be worse than I initially thought, because destructors are safe to not run now (mem::leak is safe) and we cannot rely on them to ensure safety, can we?

e.g.

let something = Something::new();
let place = something.make_place();
// place relies on destructors running for panic safety (e.g. decreasing length in vector case)
mem::forget(place);
panic!();
// destructor for Something reads uninitialized data?

[bluss]

@nagisa Thanks, looks like I didn't realize this was well enough covered, it's hopefully a matter of adjusting the mockup implementations and it should be possible to solve with the protocol.

Not sure the protocol is at risk because of mem::forget, it should be baked into sugar anyway. Worst case is that more methods need to be marked unsafe.

[glaebhoerl]

Just a note that the way to make mem::forget(place) impossible, other than by making it impossible for safe code to even get its hands on one, would be to make it a linear type (just like &out, unsurprisingly).

[shepmaster]

because the only implementation

FWIW, I created one for TypedArena and had no issues with consuming the Placer.

[hanna-kruppe]

Yes, because the Placer is a & reference, which is also Copy. But now I wonder whether GitHub search will find your PR.

[shepmaster]

I can't fully articulate this, but &mut self seems like it will be annoying. At least in the cases that I have been using (arenas), the arena has internal mutability, so suddenly needing to thread mutability throughout seems likely to cause pain.

[hanna-kruppe]

Ugh, you're right, if it takes &mut self, then in any function that takes a &Arena, it has to declare its parameter as mut arena: &Arena instead of arena: &Arena. That's a bummer.

Luckily, this is a local change, it doesn't affect the type (so it doesn't affect callers and data strutures) and it is only necessary if you want to use placement syntax. Still sad.

And I had all but convinced myself that &mut self was fine and a two-track solution that allows self as well as &mut self would be pointless.

[seanmonstar]

If you have an &Arena, you cannot call any method on it that requires
&mut self. Adding mut to the local binding won't change that.

On Sun, Oct 4, 2015, 7:31 AM rkruppe notifications@github.com wrote:

Ugh, you're right, if it takes &mut self, then in any function that takes
a &Arena, it has to declare its parameter as mut arena: &Arena instead of arena:
&Arena. That's a bummer.

Luckily, this is a local change, it doesn't affect the signature (so it
doesn't affect callers and data strutures) and it is only necessary if you
want to use placement syntax. Still sad.

And just when I had all but convinced myself that &mut self was fine and
a two-track solution that allows self as well as &mut self would be
pointless.

—
Reply to this email directly or view it on GitHub
#1286 (comment).

[nagisa]

Probably the only thing you can’t do with &mut that you can do with plain values, is moving out of the borrow.

[hanna-kruppe]

@seanmonstar

The trait would still be implemented for &Arena, so &mut self (edit: in the trait) would mean you get a &mut &Arena. That can be coerced to &Arena, and auto-deref will make all existing Arena methods work seamlessly. The only issue is that creating the &mut &Arena from a local variable requires that the binding is tagged mut.

[pnkfelix]

@rkruppe I was playing around with this last night. I'm a little worried that we would not want to make this change without higher kinded types (HKT).

But, my opinion has revised somewhat over the course of writing this comment and trying to make demonstrative examples. Maybe we should make the change you suggest, under the expectation that it might cause some pain in the short term, but in the longer term it is the "right thing" and will yield better code once we do have HKT (assuming that comes in the future).

(Explanation follows)

---

In particular: we want the Placer protocol to work with vec.push. As part of that, the allocated place needs to ensure that its mutable borrow of the vec is safe; the easiest way to do this is to have the place implementation for Vec be lifetime-parametric:

pub struct VecEndPlace<'a, T:'a> {
    v: &'a mut Vec<T>,
}

impl<'a, T> Placer<T> for &'a mut Vec<T> {
    type Place = VecEndPlace<'a, T>;
    fn make_place(self) -> Self::Place {
        self.reserve(1);
        VecEndPlace { v: self }
    }
}

If we try to change the Placer protocol in the manner you suggest, passing &mut self in make_place rather than self, the most obvious rewrite of the above is:

impl<T> Placer<T> for Vec<T> {
    type Place<'a> = VecEndPlace<'a, T>; // <-- needs HKT! 
    fn make_place<'a>(&'a mut self) -> Self::Place<'a> {
        self.reserve(1);
        VecEndPlace { v: self }
    }
}

Now, there is a way to get this to work compile, but it makes me nervous...

While trying to fix this, I tried having it pass &mut self in the method, but continue implementing
Placer for &'a mut Vec, just so that the lifetime I need is in scope (I thought this was going to work):

impl<'a, T:'a> Placer<T> for &'a mut Vec<T> {
    type Place = VecEndPlace<'a, T>;
    fn make_place(&mut self) -> Self::Place {
        self.reserve(1);
        VecEndPlace { v: *self }
    }
}

Unfortunately that does not compile, due to a lifetime inference failure, shown here: http://is.gd/35E1lk

Frustrated by the latter, which seems like a case of "this should obviously work", I resorted to a transmute of the &mut Vec<T> just to work around the lifetime inference failure:

impl<'a, T:'a> Placer<T> for &'a mut Vec<T> {
    type Place = VecEndPlace<'a, T>;
    fn make_place(&mut self) -> Self::Place {
        self.reserve(1);
        VecEndPlace { v: unsafe { ::std::mem::transmute::<&mut Vec<T>, &'a mut Vec<T>>(*self) } }
    }
}

This does "work" _unsoundly: http://is.gd/KvlwI8 ... but it scares the hell out of me _{because it is unsound}. (Maybe future fixes to the compiler's region inference will get the transmute-free version to compile again ...)

• Update: The transmute is unsound. The code without unsafe will never work. Here is a demo showing how if you do the transmute, you can end up with two &mut-references to the same vec: http://is.gd/hbsW3j

(One option that I did not try: remove the lifetime parameter from VecEndPlace and just use unsafe pointers entirely within that. I did not explore this option because I worry that doing this will expose soundness holes; e.g. scenarios where the Vec is mutated from within the VALUE_EXPR of the placement expression, invalidating the unsafe pointer stored within the VecEndPlace.)

If you or others have another way to address this problem, I would appreciate you demonstrating it by modifying the following running example (which uses the current self API): http://is.gd/SUcBSX

---

Anyway, as I said at the beginning, my opinion has changed somewhat over the course of writing this comment. (Originally I thought that this example was a deal-breaker for the change you suggest, but then I did the experiments above. I am willing to use workarounds, and continue doing impl<'a, T:'a> Placer for &'a mut Vec<T>, as long as we do get wins elsewhere by passing &mut self instead of self in fn make_place.)

[hanna-kruppe]

It seems we are in violent agreement. Your first option is basically everything I want. I'm just thinking beyond that, how real code will look when using placement syntax liberally, and I'm unhappy that it will probably be littered with &muts. That's why I keep talking about auto-ref (playground).

As I said, I am not insisting on make_place(&mut self). I simply want the placer to not be consumed, without having to write (&mut PLACE) <- VALUE_EXPR every time. In particular, if the desugaring would insert an auto-ref, the signature could remain make_place(self) for all I care. This is your first code snippet.

Admittedly, it makes for a rather strange protocol if the signature says self but the trait always must be implemented for &mut $something. It very clearly screams "HKT-ify me", but since blocking on HKT is not an option anybody wants, perhaps this strange protocol is the least bad option.

[arielb1]

@rkruppe

If we want map.entry(k) <- v to work, we need pass-by-value or ugly mem::replace (actually, the mem::replace would be natural with map.entry).

[hanna-kruppe]

@arielb1

That's a good point, and AFAIK the first solid argument for by-value self. (The mem::replace remarks are not immediately obvious for me though, can you elaborate?) That rekindles my interest in a solution that allows both consuming and not-consuming the placer. Not-consuming would be required for vec <- item; (with that convenient syntax). Unfortunately, I can't think of an implementation that doesn't lead to HKT or to the placement syntax being magic rather than a simple desugaring.

[nagisa]

@arielb1 I don’t see how not consuming hash_map::Entry prevents it from being used as a PLACE.

[arielb1]

@nagisa

Actually Entry would do just fine with not being consumed. vec.back() would be more of a problem.

[hanna-kruppe]

Is vec.back() a thing that should work, though? I thought it would be vec <- item; which fits a non-consuming protocol perfectly. Of course, there might be other collections where it does not work out as well as in those two cases, so I'm definitely not saying "screw your example let's do this".

[nagisa]

Some relevant IRC discussion.

[Stebalien]

Could someone list the arguments for making Placer take self by reference? The only argument I can see allowing vec <- value but I think vec.back() <- value is clearer anyways.

[nagisa]

The only argument I can see allowing vec <- value but I think vec.back() <- value is clearer anyways.

Its taking self by value (or alternatively, auto-ref of LHS) that enables this pattern, not by reference. Note, that you shouldn’t only consider the standard library but the ecosystem as a whole as well where people may or may not want to use the something <- blah.

[Stebalien]

@nagisa you sure? If Placer::make_pace takes self by value, we'd need &mut vec <- data or some auto ref. If it took it by reference by default, vec <- data would work out of the box.

[nagisa]

Ah, of course. I’m dumb, and shouldn’t comment on things without checking them again if I hadn’t seen them for a month. Sorry!

[pnkfelix]

@Stebalien I think it hasn't changed much since @rkruppe wrote the description of the issue. Namely this sentence:

[...] other possible uses of placement box would be ruled out by taking self. Examples raised in #1228 are vec <- thing; (instead of vec.push(thing)), set <- thing; and (disclaimer: [rkruppe's] example and pet interest) allocators that can't be behind a & reference.

You've already noted that you would prefer vec.back() <- value, and I assume you have a similar opinion about set <- thing ...

• (which may not really be a valid example anyway, since as @petrochenkov pointed out, you need to evaluate thing into a temporary slot so that you can compute its hash anyway)

... so the remaining item is allocators that aren't &-references.

Sad to admit as the author of the current Allocator RFC, I have not yet taken the time to personally experiment with mixing together placement-in and allocators in the manner described elsewhere.

I hope to get a chance to do so, but I also don't mind when our awesome community beats me to the punch when it comes to things like this. :)

[Stebalien]

Actually, allocators are why I first asked. As noted in #1401, let something: Box<_> = HEAP <- value won't work with Placer as specified. The solution you proposed was:

let b = BoxPlace(HEAP) <- value;

However, we can also do something like

let b: Box<_> = HEAP.alloc() <- value

Which gets rid of the problem of taking HEAP by value.

[hanna-kruppe]

Methods have auto-ref, so obviously they would address this (that's exactly why vec.back() and map.entry(k) could work as-is). For Vec it's debatable if the .back() isn't a valuable hint for the semantics, but for allocators there's is only one possible meaning of the placement syntax, adding an alloc method would be line noise at best (and likewise for the other possible workaround, &mut place <- value). It might even be confusing, if there is a second method that also allocates memory but returns a raw pointer rather than a placer. I have only skimmed "Allocators, take III" so far, but I think such a method would undoubtedly exist, leaving only the question of whether the "placement allocator" and the "raw allocator" will be the same type.

[mahkoh]

&mut self makes writing reliable code harder. For example,

try!(vec.insert(n)) <- value;

which reserves a slot and moves things to the right. The placer does nothing and neither does the place (which simply points to the free slot) unless it is dropped in which case it moves things back and reduces the length by one. Since the placer cannot allocate memory if you want to do error handling, the placer would have to manually track if it has already been called once and abort the process in this case. Unless make_place is unsafe in which case calling make_place twice would simply be a contract violation in generic code and cause the behavior to be undefined.

[mahkoh]

It also prevents the Placer and Place from being the same object which is what one wants if the real make_place operation already happens in the code that creates the Placer as in the example above.

[mahkoh]

Or another example:

try!(Rc::with_pool(allocator)) <- obj;

In this case it is impossible to call the Placer twice because the first call consumes the memory pool.

[hanna-kruppe]

These are nice example. I could quibble a bit with each, but collectively and together with the examples earlier in this discussion, they make pretty clear that by-value self can also be valuable.

Additionally, &mut self has been shown to probably require HKT, if done correctly. Already since then I've favored the "keep self but somehow add auto-ref to the syntactic sugar" route, and the discussion since then has strengthened my belief in that.

So, I hereby officially propose shifting the focus of this issue from "make Placer::make_place take &mut self" to "find an ergonomic way to opt into not consuming the place". Perhaps that's better as a separate issue, to be filed once I actually got my hands dirty and can show some real code that would benefit from such sugar.

[Centril]

Closing as this is moot now.