std.container: fork in the road

[Andrei Alexandrescu via Digitalmars-d]

Took a fresh look at std.container from a Design by Introspection 
perspective, and my assessment is as follows:

* The current design of std.container is adequate but requires rather 
verbose implementations because it predates UFCS. For example, 
containers that define "stableRemove" must also alias "remove" to it 
etc. It's quite tedious to define complete containers.

* It is possible to make things a lot better by taking advantage of DbI 
and UFCS. This does break client code, but only really odd cases that 
use advanced introspection to inspect methods of containers.

* Things could and should be taken further to manage memory better. 
However, that's liable to produce subtle code breakages.

Consider e.g. "SList!T.clear()". Right now it's O(1) and only reassigns 
the root to point to no element, thus leaving all elements to be 
collected. Moreover, if there are ranges iterating the now cleared list, 
they'll just continue wandering in the desert as if nothing happened.

What I think SList should do is first switch to a refcounted 
implementation. Then, clear() should call destroy() for payloads of all 
nodes, safely invalidate all ranges, and deallocate memory allocated for 
all nodes.

Even if we implement the change to be memory-safe, there's still changes 
in semantics (e.g. the behavior of orphan ranges changes). And even if 
we change behavior that wasn't specified explicitly in the docs, it's 
still a change in behavior. The same goes for other functions that 
remove elements from containers.

Oh, and one more thing I noticed:

* The documentation is appallingly bad, making std.container worse than 
non-existent. We have a liability squared to deal with here. I've 
pretended to myself I hadn't implemented SList and it was nigh 
impossible to use it competently from documentation alone, let alone 
understand the deeper architectural underpinnings that apply to other 
containers. This is another manifestation of the systemic problem of our 
community that's been discussed here in the past - there are matters 
that greatly affect negatively the uptake of D, yet they stay unresolved 
for literally months and years in spite of being trivially simple. For a 
potential user who sees today "std.container" in the library offering 
list, the subsequent click will lead almost by necessity to a vote of 
non-confidence.

Regarding compatibility, I see three possibilities:

1. Just keep the current spec and deal with it. Some containers are and 
will remain garbage collected because they started as such. Add new 
containers that are better alongside them.

2. Do break compatibility of containers, mainly by taking advantage of 
them being under-documented. In a way we wouldn't break much because not 
much has been specified. There are, however, parts where we'd need to 
change specification.

3. Leave std.container alone and move forward with 
std.experimental.collection. I am confident the language and its 
endorsed idioms have reached enough maturity to not make this addition 
into a regular event.


Andrei