Consider reverting the merge of collections into alloc

[brson]

This PR merges the collections crate into the alloc crate, with the intent of enabling this PR.

Here are some reasons against the merge:

• It is a violation of layering / seperation of responsibilities. There is no conceptual reason for collections and allocation to be in the same crate. It seems to have been done to solve a language limitation, for the enablement of a fairly marginal feature. The tradeoff does not seem worth it to me.

• It forces any no_std projects that want allocation to also take collections with it. There are presumably use cases for wanting allocator support without the Rust collections design (we know the collections are insufficient for some use cases).

• It gives the std collections crate special capabilities that other collections may not implement themselves - no other collections will be able to achieve feature parity with the conversion this merger is meant to enable.

Personally I value the decomposition of the standard library into individual reusable components and think the merge is moving in the wrong direction.

I am curious to know what embedded and os developers think of this merge cc @japaric @jackpot51 .

[joshlf]

@tarcieri

My singular goal getting allocators working in my code was always to unlock Box, Vec, and String (and in some cases things like BTreeMap), and in that regard I thought the original liballoc/libcollections merger made sense. Having a "batteries included" set of heap allocated types that come free with an allocator is much more important to me than being able to craft my own artisanal data structures, although I could see how that might be different for someone writing a kernel.

I assume the current proposal of moving the Alloc trait to libcore but keeping Heap in libcollections and having collections take an Alloc parameter that defaults to Heap works for this use case?

[tarcieri]

This is perhaps getting a bit off topic, but what I really want is Box, String, and Vec added to the prelude if an #[allocator] is defined:

https://internals.rust-lang.org/t/sgx-target-and-no-operating-system-x86-x86-64-targets-in-general/5493/5?u=bascule

[Ericson2314]

@tarcieri the best solution to that is custom preludes.

[tarcieri]

@Ericson2314 custom preludes don't really solve the problem I'd like to solve, which is allowing crates to leverage Box, Vec, and String from no_std without explicit dependencies on nightly. Since custom preludes are scoped to individual crates, every crate that wants to consume Box, Vec, and/or String still needs to do #[feature(alloc)] (or if this change goes through, #[feature(collections)] again)

The whole point of automatically adding them to a core/alloc prelude would be to remove this explicit dependency. Then use of Box, Vec, and/or String could just be gated on cargo features with no explicit ties to nightly.

[Ericson2314]

@tarcieri I'm not sure what to tell you, sorry. Some insta-stable trick to expose items through abnormal means based on whether anything implements allocator anywhere is....unwise in my book. I'd say stabilize the crates quicker, but @whitequark bring up a good point that our current story around handling allocation failure in everything but the allocator trait itself is atrocious: unergonomic and unsafe. I'm loath to stabilize the "beneath the facade" interfaces until that is fixed.

[whitequark]

unergonomic and unsafe

What? That's the exact opposite of reality. It is safe (because crashes are safe), and it's ergonomic, because explicicly handling allocation failures in typical server, desktop, or even hosted embedded software has a high cost/benefit ratio.

Consider this. With mandatory explicit representation of allocation failure, almost every function that returns or mutates a Vec, Box or String would have to return Result<X>, where X is an error representing allocation failure. The caller then has two choices, both of them bad:

• either call unwrap, or
• use ? and return Result<Error>, which may fail because Error has a Box in it! If the crate defines its own error type, then that can contain OutOfMemory, but this still pessimizes standalone impls. We'll also need to add OutOfMemory to io::ErrorKind.

Also, let's say you have a public function that returns T. You want to optimize it by using a hashmap or a cache or something, but that means it'd now need to return Result<T>, and that breaks your public interface. So you use unwrap(), resulting in essentially the same thing as what we have today, but with ugly source code (don't we all say that unwrap is an antipattern?) and bloated machine code (because of the inlined condition).

The only remotely workable solution I see is extending the API of Box, Vec, etc, adding a fallible sibling to every function that may allocate. But I believe the libs policy is explicitly against that.

[whitequark]

To add to this, the majority of small embedded devices whose memory is truly scarce cope in one of the two ways:

• they partition memory statically or early in boot, so that any fallible allocations, e.g. network packet buffers, happen in pools and can be easily handled, or
• they acknowledge that recovering from an out-of-memory condition is a complicated affair--you have to have some logic for what to free, you may just have memory too fragmented, etc--and instead, reset, just like in a case of a panic resulting from a violated invariant, an assertion, a lockup, a cosmic ray hitting the CPU core, etc.

As such, I feel like the primary structure providing fallible allocations would be some sort of memory pool. This can be easily handled outside the alloc crate.

[Gankra]

As a former libs team member, I'm not opposed to adding try_push, try_reserve, etc to the stdlib at this point in time. Someone just needs to put in the legwork to design the API, which I think was partially blocked on landing allocator APIs -- to provide guidance on what allocation error types are like -- when this first came up.

I believe the gecko team broadly wants these functions, as there are some allocations (often user-controlled, like images) which are relatively easy and useful to make fallible.

[Ericson2314]

@whitequark Sorry, I meant handling allocation in the client is unergonomic/unsafe. Everyone agrees that what we do today is both safe and ergonomic, but not flexible in that regard.

[whitequark]

As a former libs team member, I'm not opposed to adding try_push, try_reserve, etc to the stdlib at this point in time.

Then this sounds like the best solution to me, yeah.

[brson]

This thread has gone in a lot of different directions, and I'm having a hard time following it now, but it is originally about how to respond to the out-of-process merge of the collections and alloc crate.

I'm afraid I framed this incorrectly by presenting a defense of the unmerged crates, but the onus here is on proponents of merged collections and alloc crates to justify that design, and to do it in a way that is fair to the rest of us. I don't believe that argument has been made successfully.

This was a major breaking architectural decision, done out of process. In cases like this our default stance should be, and usually is, to revert. This needs to be done before the change hits stable. We have about 6 weeks right now.

I suggest we take the following actions:

• Immediately un-deprecate the collections crate to stem the downstream churn

• Revert the merge of collections and alloc

• Implement #43112 some other way. It has been said that it can be done without the merge, so please do it.

• Proponents of changing the std facade write an RFC

[tarcieri]

My gut feeling is there are some complex interrelationships between these types which are difficult to model given the previous alloc/collections split. I think that was the motivation for the merge in the first place.

As an example, at the error-chain meeting we discussed moving std::error::Error to liballoc. My gut feeling (and it seems at least @whitequark agrees) is that it belongs in libcore. However, because blanket impls for Box required knowing that &str: !Error (or so says the comments in error.rs), it's coupled to Box, which I guess was the motivation to moving it to std in the first place.

This means any crates that want to work with no_std can't use std::error::Error, which unfortunately is a big blocker for making much of the extant crate ecosystem available in no_std.

I guess my question is: is there still a path forward for unlocking std::error::Error in no_std if this merge is reverted? Could std::error::Error be moved to libcollections instead of liballoc? (which feels even weirder, but I'm not sure there are other options due to its entanglement with Box)

[Ericson2314]

@tarcieri with or without the revert, it can go in alloc. If Box is moved to collections, it can go in there. [Based on http://aturon.github.io/blog/2017/04/24/negative-chalk/, I now think we actually will be able to get negative impls (but not necessarily user-writable negative bounds). Then it can be in core. But I digress.]

@brson Ah, I wasn't actually sure what the process is for changing crates whose very existence is unstable. Thanks for clarifying.

[tarcieri]

My apologies if that's all orthogonal to the revert. If that's the case, I have no objections.

[aturon]

A couple of process points:

• I don't know that this unstable arrangement of crates needed the full RFC process, but it should've gotten buy-in from more stakeholders, clearly.

• That said, my feeling is that this has landed on nightly, it's already caused churn, and it would be better to see if we can quickly reach a rough consensus on the direction we want to take things before changing direction. We should try to minimize pain and confusion in the ecosystem while we try to correct our process mistake.

From the libs team meeting, it sounded like @alexcrichton was quite confident that the original crate organization was buying us nothing, and that the problems people are interested in solving are better addressed in some other way. I think it'd be good for @alexcrichton and @brson to sync up, and then summarize their joint perspective on thread, before we make more changes here.

[shepmaster]

There doesn't seem to have been any progress on this in the last 3 weeks; and PR #42565 is blocked on this resolving one way or the other. What steps do we need to take to unstick this?

^{"Watch me hit this beehive with a big ol' stick", he said, pressing Comment}

[tarcieri]

42565 was the sort of thing I was alluding to earlier. Is there a path forward for that if the merger were to be reverted?

[RalfJung]

42565 was the sort of thing I was alluding to earlier. Is there a path forward for that if the merger were to be reverted?

Yes -- move just Arc and Rc to libcollections. As long as Arc, Rc and Vec are all in the same crate, the orphan impl check (or whatever we call it in Rust ;) should go through.

[aturon]

I've re-read this entire thread, and to me the key points are:

Clarity of layering. I think @whitequark put it best:

• libcore: no allocation, no I/O
• liballoc: infallible allocation, no I/O
• libstd: infallible allocation, hosted I/O

though we are working toward supporting fallible allocation in liballoc as well. But the point is that there's a crystal clear rationale for this coarse-grained organization, in terms of requirements imposed.

Crates providing features that aren't used. It's true that the crates.io ecosystem in general skews toward small crates, but these core library crates are a very important exception to that. The thread has made clear that bloat isn't an issue (due to linkers), nor is compilation time (which is trivial here, due to generics).

Special treatment of core crates. Grouping type and/or trait definitions together can enable impls that are not possible externally. However, (1) the very same issues apply to any choice of breaking up crates and (2) the standard library already makes substantial and vital use of its ability to provide impls locally.

Separating collections from the global heap assumption. There is not currently a plausible path to do this, but with some language additions there may eventually be. But by the same token, this kind of question also seems amenable to a feature flag treatment.

Personally, I find the new organization has a much more clear rationale than the current one, and is simpler as well. Stakeholders from impacted communities (the no_std and embedded communities) also appear to be on board. I think we should stay the course.

@rfcbot fcp close

[rfcbot]

Team member @aturon has proposed to close this. The next step is review by the rest of the tagged teams:

• [x] @BurntSushi
• [x] @Kimundi
• [x] @alexcrichton
• [x] @aturon
• [x] @brson
• [x] @dtolnay
• [x] @sfackler

No concerns currently listed.

Once these reviewers reach consensus, this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

[Ericson2314]

Bummer. Then I suppose the next fronts for pushing for modularity are:

• Whose's still interested in moving the Alloc trait and friends to core? @alexcrichton? @whitequark?
• In https://github.com/rust-lang/rust/issues/42774#issuecomment-317279035 Can we discuss the type Collection<T> = Collection<T, GlobalAlloc> stop-gap I raised previously in this thread?

[rfcbot]

:bell: This is now entering its final comment period, as per the review above. :bell:

[jackpot51]

Please don't revert it. This change has been out in the wild for a long time, and many projects have updated to the new organization of alloc. The new organization has benefits as listed above (https://github.com/rust-lang/rust/issues/40475), and the downsides seem to be smaller than the benefits, especially considering that us folks tracking the nightly, and using the allocation API, have already adjusted to it.

[aturon]

I'm going to close this issue now that the full libs team has signed off. (@jackpot51, to be clear, that means: we will not revert.)