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 .

[alexcrichton]

@brson I'm not sure I agree with the reasons you laid out. In my mind liballoc provides the ability to depend on dynamic memory allocation, but nothing else. On top of that one assumption you can build up the entire crate (pointers + collections) with no more assumptions than libcore already has. In that sense I don't see this as a violation of layering but rather just giving you one layer and then everything else that it implies.

It forces any no_std projects that want allocation to also take collections with it.

Is this a problem? Linkers gc'ing sections should take care of this? Isn't this equivalent to libcore bringing utf-8 formatting when you otherwise don't need it?

It gives the std collections crate special capabilities that other collections may not implement themselves

Do you have an example of this?

[japaric]

I'm in favor of undoing the merge.

In general, I'd prefer not to reduce the number of crates in the std facade. I'm
afraid that these seemingly "small" changes may eventually become hard, if not
impossible, to undo once stable std API depends on these crates being merged
(cf. HashMap confined to std even though it doesn't depend on OS mechanisms).
And that may lock us from creating a set of stable fine grained standard /
blessed crates for no-std development.

In the particular case of alloc / collections it feels odd to have a full suite
of collections available to me when I'm implementing the Allocator trait.
Things are likely to go wrong if I use those collections in the implementation
of my allocator, right? I think allocators are not supposed to do any dynamic
allocation for their internal data structures.

Personally, I'd prefer if alloc only contained the Allocator interface and
Arc was in another crate since it depends on dynamic allocation.

cc @Ericson2314 @whitequark

[alexcrichton]

If we're going to separate this crate then I think we need to be super clear about why. For example the previous incarnation of alloc I don't think made any sense to keep collections separate because it already had smart pointers and such. If we wanted to remove everything then we should just move the Alloc trait to core in my opinion, not make a whole new crate for just a trait. The purpose of alloc is to provide the assumption of a global allocator, notably the Heap type and value.

Things are likely to go wrong if I use those collections in the implementation
of my allocator, right?

Yes, and to me this is not a reason to separate the crates. This is already a "problem" in the standard library where the "fix" is otherwise too unergonomic to work with.

[est31]

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.

If cargo had the ability to run with multiple different forks of std see this RFC, this would be much less of an issue.

[brson]

Is this a problem? Linkers gc'ing sections should take care of this? Isn't this equivalent to libcore bringing utf-8 formatting when you otherwise don't need it?

It is a problem. I do not think depending on linker to throw away unwanted code is a reasonable excuse to make unsatisfactory architectural decisions. If this were an out-of-tree project where people have to spend CPU time compiling code, then telling people to just merge your abstraction layers, compile it all, and throw most of it away later, would not be acceptable.

Do you have an example of this?

Yes. The entire motivation for this merge is to follow it up with this PR, which is seemingly not possible without the collections being literally in the alloc crate. No other collections crate can achieve this.

For example the previous incarnation of alloc I don't think made any sense to keep collections separate because it already had smart pointers and such.

This was indeed a weakness of the previous alloc crate. I'd love to pull the smart pointers out if possible, and would love to not make the conflation worse.

If we wanted to remove everything then we should just move the Alloc trait to core in my opinion, not make a whole new crate for just a trait

I don't think this follows. Each layer in the facade adds new capabilities. Alloc is a crucial capability that separates different classes of Rust software.

[RalfJung]

I'd love to pull the smart pointers out if possible, and would love to not make the conflation worse.

So merging alloc and collections happened to be able to impl<T> From<Vec<T>> for Arc<[T]>. If instead Arc (and Rc) moved to collections, the impl would also be fine -- right?

[sfackler]

If the goal is to minimize library code bloat, should we move to libbtree_map, libbtree_set, libvec, libvec_deque, libbinary_heap, etc?

[Ericson2314]

@brson thanks for reopening discussion, and @japaric thanks for the ping.

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

Exactly. I have a few reasons why I think combining facade crates relating to allocation is bad, but I want to start positively with why I think breaking facde crates further apart in general is good. Writing this with @joshlf's help.

Small, quickly compiled binaries are nice, but more important is the efficiency of the development process. We want a large, diverse, and flexible no-std ecosystem, because ultimately we are targeting a large diverse space of projects. Small libraries are key to this both because they reduce the cognitive load of everyone developing those libraries, and allow more developers to participate.

For cognitive load, it's important both to be utterly ignorant of the code that doesn't matter---as in, don't know what you don't know---and incrementally learn the code that does. --gc-sections or super lazy incremental compilation strip away the noise after the the fact, but do nothing to help the developer reading the code doing the same task. Small libraries help ensure as little dead code as possible, allowing the developer and tools alike to stay happily ignorant of everything else out there. For incremental learning, it's crucial to be able to digest the code one small bite at a time. Rust libraries allow all sorts of intra-crate (inter-module) cycles meaning that given a big huge unknown library, it can be really hard to know where to begin as first-time reader. But fine-grained dependency graphs on crates enforce acyclicity--both a top-down learning approach (start with the nice abstractions) or bottom-up one (complete understanding every step of the way) have clear curricula.

For distributed development and diverse goals, the benefits are probably more obvious. Lighter coupling means less coordination so more people can scratch their own itches in isolation. But it also allows complexity to be managed by splitting the ecosystem into small, modular components - this allows people to take only what they need, and thus only opt-in to as much complexity as their application requires.

All this begs the question---how far do we go down the road of splitting coarse crates into fine crates? I think quite far. It is my hope that as crates behind the facade and the language mature, more crates will be able to be written in stable (or otherwise trustworthy) code, and be moved outside rust-lang/rust into their own repo. Likewise, std should be able to (immediately and transitively) depend on third party crates just fine---the lockfile keeps this safe. Rustbuild, and my RFC #1133 are our friends here. To put it another way, there should be as little magic in rust-lang/rust as possible because magic cannot be replicated outside of rust-lang/rust. By splitting crates, we decrease the risk that a given piece of near-stable code will be bundled with code that cannot be stabilized, thus preventing the former from ever becoming stabilized and thus "de-magicked" in the sense of becoming eligible for being moved outside of rust-lang/rust. This runs counter to the arguments in favor of the collections/alloc merge.

---

In concrete terms, I recall there being talk of incorporating lazy_static into std, and I know there was talk of using parking_lot for locks too. lazy_static optionally uses spin and so should parking_lot, but spin probably shouldn't be exposed in std because it's a bad idea in hosted environments outside bootstrapping such core abstractions abstractions. Yet it would also weird if spin was included in the main repo as a dependency, but not exposed:I generally like the idea of shrinking, not enlarging the main repo, but would feel especially weird about including non-reexported functionality in the main repo.

Back to allocation in particular, @joshlf's been doing some great work with object allocation (type-parametric allocators that only allocate objects of a particular type and cache initialized objects for performance), and it would be nice to use the default collections with that: the fact is, most collections only need to allocate a few types of objects, and so could work with object allocators just fine. Now if we were to combine alloc and collections and the object allocator traits in one crate, that would be a very unwieldy crate playing not just double but triple duty.

---

if we wanted to remove everything then we should just move the Alloc trait to core in my opinion, not make a whole new crate for just a trait.

Besides the technical reasons, as @japaric and I mentioned elsewhere, including anything allocation related in core, even something as harmless as a trait that need not be used, will scare away developers of real-time systems.

OTOH, I like the idea of allocator types being usable without Heap. Heap represents "ambient authority " for allocation, to use the capabilities lingo. As a general principle, ambient authority is suspicious, and in particular this complicates safely booting an OS where one doesn't want to allocate accidentally before any allocator is set up.

Also, there's an analogous problematic cycle to avoid when defining the static allocator even if it is initialized statically: For crates which implement global allocators it's incorrect for them to use Heap, yet so long as it's in the same crate as the alloc traits, there's nothing to prevent them from doing so. Technically the language still wouldn't stop them if it's in another crate, but at least they would have to import something suspicious explicitly. This is just like @japaric's concern with allocators accidentally using collections.

CC @eternaleye

[joshlf]

Given @Ericson2314 's comment, we (again, jointly) would like to make a proposal for how all of these various components might be structured.

We have the following goals:

• The Alloc trait should have no dependencies other than core. Its dependencies include other items in its own crate such as collections or the Heap.
• collections should have no dependencies other than core and the Alloc trait (e.g., it should not depend on the Heap); it should be possible for a no-std program to define its own allocator and use it to back the standard collections.
• On the other hand, it is desirable for ergonomics to provide variants of each of the collections that default to using the Heap.

Thus, we propose the following:

• The Alloc trait should either be in core or in its own crate (we'll call it alloc here). The former is simpler, but may be off-putting to embedded/real-time developers, and goes against the original philosophy of core - the bare minimum of nice abstractions to define the always-needed parts of the runtime, not every self-contained abstraction under the sun. The latter involves making a tiny crate whose sole purpose is to hold Alloc and related types (although it would become less tiny if an ObjectAlloc trait were added later). We lean towards a separate crate, but either works.
• collections should be its own crate with dependencies only on core and alloc (if it exists). It should be no-std.
• Heap can either be defined in its own crate with dependencies only on core and alloc (if it exists) or simply be defined in std.
• std will re-export all of the collections with a default Alloc parameter of Heap. There may be other default values that std needs to set as well (e.g., the OS-dependent randomness provider for HashMap).

[joshlf]

@sfackler

If the goal is to minimize library code bloat, should we move to libbtree_map, libbtree_set, libvec, libvec_deque, libbinary_heap, etc?

I don't think that the arguments provided suggest that that should happen. Keeping all of the collections together doesn't increase the difficulty of understanding how things work because, for the most part, collections do not depend on one another, and do not share magic under the hood. From a usability perspective, they're logically related, so it would not be surprising to a developer to find them together in the same crate. The arguments we and others have presented do suggest splitting collections into its own thing - separate from, e.g., Alloc - but do not suggest further splitting collections into multiple crates.

[sfackler]

All this begs the question---how far do we go down the road of splitting coarse crates into fine crates? I think quite far.

@joshlf ^ seems to imply to me that it would suggest that level of granularity.