DST-ification of libraries

[nrc]

We should change our impls to a DST style where appropriate. E.g., impl Ord for str .... This requires changing a bunch of traits to have the Sized? bound.

This kind of works. The problem is that we currently do not unify T with unsized types ([T], str, etc.) during subtyping/type inference and thus trait matching. This means that if do the DST-ification, we will fail to type check in places with references (e.g., a == b where a and b both have type &str). However, if we do unify, we will get coherance errors where impls are defined for, e.g., &T and &str. Thus we have a bit of a catch 22. We could cfg our way to victory, but there are literally hundreds of places that need DST-ification, so that will be extremely painful. I'm not sure if trait reform landing can help us here, or perhaps where clauses with != constraints or something equally exotic. Perhaps we could hack coherance with this special case temporarily. Anyway, we need a plan!

cc @nikomatsakis

[nrc]

Here is my very, very early WIP branch: https://github.com/nick29581/rust/tree/dstify

[nikomatsakis]

I should almost have what is needed here.

[nikomatsakis]

In particular, what is needed to enable unification of types.

[japaric]

@nick29581 Are you working on this atm? I DSTified [T]/str's extension traits like StrSlice, ImmutableSlice, MutableSlice, and both make/make check passed.

Want to coordinate the work in this area?

[japaric]

I've compiled a table with all the traits that [T]/str implement. Not sure which/if-all traits should be DSTified.

[aturon]

@japaric I was in the process of assembling a similar patch myself, but I'd be glad to work with you on this. I'm away from the office this week but should be available early next. Please ping me if you post a PR. What you have so far looks like a good start.

[japaric]

DSTifying PartialEq, PartialOrd causes lots of breakage.

The reason is that, for example, PartialEq is currently implemented for &'a [T], so eq has signature fn eq(&self, other: & &'a [T]). But, once you DSTify it, eq's signature changes to fn eq(&self, other: &[T]) , so the RHS now needs one less level of indirection. And, because of how the operator sugar works, the RHS of the operator now needs to be an unsized array [T] or str.

The following patterns break:

• a[..] == b[..]: Fixed by changing it to a[..] == *b[..]
• a[..].partial_cmp(&b[..]): Fixed by changing it to a[..].partial_cmp(b[..])
• #[deriving(PartialEq]/#[deriving(PartialOrd] on structs that contain either &str/&[T]: error: mismatched types: expected&str, found&&'static str`
• s == "abc": Fixed by changing it to s == *"abc"
• s == [b'i', b'n', b'f']: error: mismatched types: expected[u8], found[u8, ..3](expected unsized array, found array)
• Everything that applies to ==, applies to other operators.

I'll skip those traits for now.

[nikomatsakis]

Some of this (e.g., a[..] == b[..]) seems like it should work. The fact that it doesn't is, I think, because the way we are handling operators like == seems a bit wrong to me.

[japaric]

@aturon I've got other branches where I've DSTified other 4 traits, all them need a newer snapshot (#18259) that includes #18121. Could you review them? Here are the branches + some remarks:

• Show
  • This one was rather trivial nothing else to say here
• Hash
  • This one changed the signature of *_equiv methods from e.g. find_equiv(&"Hello") to find_equiv("Hello"), so some stuff broke.
  • I left a FIXME about adding a test for hashing Box<str>, because there is no way to create that type at the moment (see There is no way to create Box<str> #18283).
  • I also left a FIXME for adding Sized? to the Rc<T> impl, because e.g. Rc<[T]> is not yet allowed (see std::rc::Rc should accept DST #18248).
• ToCStr
  • There was this FIXME message saying that we should take ToCStr implementors by reference instead of by value, so I went ahead with that.
    • This broke stuff like Command::new(path), which needs to be changed to Command::new(&path).
    • Note that methods like Command::new("foo") still work.
  • I've to kept the impl ToCStr for &'a str because of Command::args, one of the uses is cmd.args(["Hello", "World"]) where args has signature fn args<'a, T: ToCStr>(&'a mut self, args: &[T]) -> &'a mut Command, in that case T has to be &str
• BytesContainer
  • As with ToCStr I changed some methods from taking the BytesContainer implementors by value to taking them by reference. This broke some stuff.
  • Since BytesContainer has two methods (container_into_owned_bytes and is_str) that take the receiver by value, so I split the trait in two: BytesContainer for Sized? and SizedBytesContainer: BytesContainer + Sized, but see below.
    • It seems that the container_into_owned_bytes method is not used anywhere so we could just remove it, and
    • There is only one use of the is_str method but AFAICT is not necessary, so we could remove this method as well, therefore
    • if those two methods are removed then we can remove the SizedBytesContainer trait as well.

Each branch passes make check locally but I may have forgotten to fix some Windows/*BSD tests since I can't run those.