Allow borrowing a whole vec of pointers

[jruderman]

Most library functions can take & pointers, which is awesome. But library functions that take a vec of pointers have to decide how those pointers will be allocated, limiting their flexibility.

The motivating example is str::concat. It is a pure function that takes &[~str] and creates a new string with the concatenation of the input strings. It seems to me that it would be safe for it to take &[&str] instead. (The slice is constant, and the callee is pure, so the pointers should remain valid.) But currently, that prevents a vec of ~strs from being passed.

(For the special case of strings, there's the slight complication that sys::size_of::<&static/str>() is larger than sys::size_of::<~str>()...)

use str;

/// Concatenate a vector of strings
pure fn my_concat(v: &[&str]) -> ~str {
    let mut s: ~str = ~"";
    for vec::each(v) |ss| {
        unsafe { str::push_str(&mut s, *ss) };
    }
    move s
}

pure fn my_sum(v: &[&int]) -> int {
    let mut sum = 0;
    for vec::each(v) |summand| {
        sum += **summand;
    }
    sum
}

fn main()
{
    // These are allowed
    assert my_concat(["1", "A"]) == ~"1A";
    assert my_sum([&42, &13]) == 55;

    // These are not allowed. Why not?
    assert my_concat([~"1", ~"A"]) == ~"1A";
    assert my_concat([@"1", @"A"]) == ~"1A";
    assert my_sum([~42, ~13]) == 55;
    assert my_sum([@42, @13]) == 55;
}

gives me errors like

29:22: 29:33 error: mismatched types: expected `&/[&int]` but found `[~<VI4>]/2` (expected &-ptr but found ~-ptr)
29         assert my_sum([~42, ~13]) == 55;
                         ^~~~~~~~~~~

[nikomatsakis]

This would be quite complex. It's unlikely to happen purely automatically. However, we could perhaps add a method like borrow_all()---it'd be interesting to see if we can push traits far enough to make this work for things like ~str, @str, ~[] and so forth. Should be possible though it might take some improvement to our type inference.

Incidentally, @pcwalton has made the case to remove borrowing for function arguments altogether. I am not sure how I feel about it. On the one hand, I do prefer to err on the side of less magic. And borrowing and inference have the potential for surprising failures (though they seem to occur rarely in practice). On the other hand, it'll mean strictly more sigils than we have now (i.e., to convert an @T to &T would be &*x), and I fear it will discourage the use of &T.

[bblum]

It couldn't happen automatically without special-case runtime support -- borrowing a ~ or @ into a & actually changes the value of the pointer (the &T skips past the refcount header). Borrowing the entire vector would have to mutate the contents of the whole vector.

It's a shame that using a function like "borrow_all" would require memory allocation, though.

[catamorphism]

Since this is 3 months old and there wasn't much enthusiasm, I'm closing.

[jruderman]

Could we change the representation of @ and ~ so that borrowing it doesn't require changing its value? (Subtract to reach the header, rather than add to reach the interior)

[nikomatsakis]

Could we change the representation of @ and ~ so that borrowing it
doesn't require changing its value? (Subtract to reach the header,
rather than add to reach the interior)

Yes, I've thought about that from time to time. The only downside I can
see is that, if we ever manage to shrink the size of the header, it
might require more memory in order to ensure that the payload is always
located at an appropriate alignment (particularly if we care about
vector instructions like AVE2, which I believe can require up to 32-byte
alignment). The reason is that the header would have to be located at a
fixed offset from the payload since sometimes we don't know the type of
the payload, and we must load the header to determine that.

[jruderman]

I don't see the connection between pointer representation (pointing at payload vs header) and payload alignment.

[nikomatsakis]

So, imagine we had a one word header (I wish...) and a one character payload. In that event, today, we could build a tightly packed struct like struct BoxChar { void *header; char payload; }. If on the other hand the payload were 32-byte aligned, we would have struct BoxChar { void *header; /*padding*/ vector payload; }. Basically we can insert padding as needed.

But if the pointer is always at the payload, then we have to be able to find the header at a fixed negative offset, because sometimes we don't know the type of the payload and so we need to consult the header to figure it out. This means we'd have to always pad to the maximum supported alignment, regardless of the payload type.

I'm not sure how big a problem this is in practice. It's just the only complication I could think of.

[bblum]

the BoxChar children