Containers

[Alexandru Ermicioi]

On Tuesday, 31 August 2021 at 17:21:02 UTC, deadalnix wrote:
> I want to start working on a container library. Interestingly 
> enough, I don't think we have what we need on that front.
>
> I'll describe here what are the design I intend to go for, and 
> the rationales for it, but before, there is an unsolved problem 
> that I don't know how to work around that is somewhat of a 
> blocker. If one of you guys have an idea how to solve it, I'm 
> taking. If I'm being honest, this is probably the most 
> important problem that need to be solved for D right now. That 
> problem is turtling down type qualifiers.
>
> For instance, if we have a Vector!T, then we want it to convert 
> to a Vector!(const T) and we want const(Vector!T) == 
> const(Vector!(const T)), all of it implicitly. Same goes for 
> other qualifiers.

Converting from Vector!T to Vector!(const T) should be possible 
through copy constructors and opAssign overloads, same for 
const(Vector!T) to const(Vector!(const T)).

having something like this should suffice for initialization for 
example:

```
static if (is(T == const)) {
   this(Vector!(Unqual!T) mutable) {
     this.array = mutable.array;  // Or you can do a complete copy.
   }

   static if (is(this == const)) {
     // ... well case for const T and const this
   }
}
```

>
> To put it bluntly, I have no idea how to achieve this. And I 
> don't think we'll have a good set of collection before this is 
> sorted out.
>
> Now onto the design:
>  - Value types. It is very easy to turn a value into a 
> reference type, not so much the other way around.

Would be nice if even as value types different implementations 
say of a list would follow a well defined interface, same for 
other type of collections.

> reference type also come with a bag of edges cases, like the 
> collection being null vs empty, that cause confusion and 
> problems in practice.

Imho, there is no problem here. null pointer to collection class 
means no collection present, while empty collection is just an 
empty collection. There should not be any conflation between 
these notions, in general, and could be made clear in the 
documentation.

>  - Not expose much of its internals. This like iterators being 
> raw pointers (or the result of using the in operator) for 
> instance, impose constraint on the internal that almost always 
> end up costing a ton of perf as new techniques are discovered 
> (recent exemples include open addressing with SSE probing for 
> instance). All of this needs to be wrapped.

It would be nice if the collection api would have rich and 
consistent api for working with it. I.e have common interfaces 
for lists, sets, queues and etc. that value and reference type 
collections implement. And that is not only about the list of 
methods they implement, but also the behavior they exhibit.

Java for example has a good api for collections, from which your 
collection library can take inspiration, and ofc with D twist of 
features.

I also tried poking around with a collection implementation, 
though not value types but ref types, and found it being 
problematic to implement, due to limitations of how safety 
annotations work.

You basically cannot force the interface being 
@safe/trusted/system based on element it contains without doing 
extensive compile time introspection...
So if you plan to add ref wrappers this one should be also 
resolved somehow to have a @safe lib, otherwise I'm afraid class 
wrappers will be only for @system code.

Best regards,
Alexandru.