[rust-dev] problems with adding an element to a ' @' vector.

Nathan nejucomo at gmail.com
Mon Dec 10 16:13:20 PST 2012


On Mon, Dec 10, 2012 at 4:03 PM, Patrick Walton <pwalton at mozilla.com> wrote:
> On 12/10/12 3:49 PM, arkaitzj at gmail.com wrote:
>>
>> Aren't both ~vector and @vector dynamic memory? why can we append to a
>> ~vector but not to a @vector?
>
>
> Because the pointer points to an object that looks like this:
>
>     ---> [ length ] [ element 1 ] [ element 2 ] [ element 3 ]
>
> Now suppose that the allocator didn't leave any room for more elements after
> it. In general we have to assume this, because we can't leave an infinite
> amount of space after our arrays. Thus in general appending to a vector
> requires reallocating the entire vector and move it to some new location in
> memory. The problem is that, after we do that, we have to update all the
> pointers to point to the new location.
>
> In the case of ~[T] this is easy. There is only one pointer, and it was
> passed into push(), so we can just update it. With @[T] it's not so easy
> though. We have no idea at compile time how many pointers there are to the
> vector, and even at runtime finding all the pointers and updating them would
> be a quite complex and expensive operation. So we have to copy the array.
>


I just read Patrick Walton's response, and I wanted to respond with a
different take, based on types and mutability instead of performance:


Caveat emptor: I'm a semi-lurker on the sidelines of rust, so consider
every assertion that follows as suspect.  I'd like feedback on the
correctness so we can put this kind of clarification in the tutorial:


@[T] is a reference to a local-heap, transitively immutable vector
where each element is a T.

@[mut T] is a reference to a local-heap mutable vector.  Each element
is a mutable T, and the vector itself can be mutated.  As Patrick
described, operations like "extend this vector with new elements"
might be expensive to implement.

~[mut T] is a reference to a shared-heap mutable vector, which can be
mutated along the same lines as @[mut T].

~[T] is a funny type.  Let's think about it by looking at vec::push's signature:

pub fn push<T>(v: &mut ~[T], initval: T) { ... }

When the caller of push passes a ~[T], the code is allowing push to
borrow a *mutable reference*.  Because this is the only reference at
the time of the call, it is safe to mutate the v parameter.

So if such mutable borrowing is possible, then what's the difference
between ~[mut T] and ~[T]?  I think the answer is probably nothing, or
maybe there are weird discrepancies.  The similarities are so close,
that I believe ~[mut T] is actually being deprecated as a type
specification.

The distinction between ~[mut T] and ~T also applies to just ~T and ~mut T.


>
> Patrick
>
> _______________________________________________
> Rust-dev mailing list
> Rust-dev at mozilla.org
> https://mail.mozilla.org/listinfo/rust-dev

Regards,
Nathan Wilcox

ps: Nicholas Matsakis describes the rational around mutability and
types in some blog posts.  These are two relevant posts:

http://smallcultfollowing.com/babysteps/blog/2012/05/28/moving-mutability-into-the-type/

http://smallcultfollowing.com/babysteps/blog/2012/07/24/generalizing-inherited-mutability/

I'm not certain if everything proposed there defines the future of
rust.  The second blog post really helped me understand the motivation
for this design.


More information about the Rust-dev mailing list