Associative arrays

[Mathias LANG]

On Tuesday, 18 May 2021 at 08:08:10 UTC, Chris Piker wrote:
> On Tuesday, 18 May 2021 at 07:50:06 UTC, Ola Fosheim Grostad 
> wrote:
>> I hope it stays unimplemented. AAs should be replaced by a 
>> library solution and AA literals should work with custom AAs. 
>> The special casing is not good for metaprogramming.
>
> I'm new to D and don't come from a hard-core C++ background.  
> On naive first take, the fact that D had a construct resembling 
> python dictionaries made D more attractive. In fact, it was AAs 
> that finally tipped me in favor of trying D.
>
> Can you tell me more about why AAs are an undesirable language 
> feature?

AA are definitely a great D feature IMO. But unlike other D 
features, they are not as composable as we'd like.

Take slices for example. They compose fairly well. You can get an 
`int[]` from the GC, a static array, `malloc`, or even some other 
library-provided buffer. While extending them is tied to the GC 
(`a ~= b` will always call the GC), sub-slicing them, batch 
operations (`a[] = b` or `a[] = b[]`) will work just the same no 
matter what underlying memory you have.

Associative arrays have none of that. They are tied to the way 
they've been implemented in the runtime, and predate a lot of 
features. They only work with qualifiers because of the C 
interfacing. You can't control the underlying memory, which means 
you can't reuse it or bind it to a buffer if you know the AA size 
in advance. They don't work well with qualifiers, because the 
compiler will error on `myAA[key] = value;` if 
`is(typeof(myAA[key]) : const)` because it can't know if it's an 
update or an insertion. We have require and update in druntime 
but those are not recognized by the compiler so they don't solve 
the problem.

The following doesn't even compile:
```
void main () nothrow
{
     int[int] aa;
     foreach (k, v; aa) {}
}
```

Because:
> onlineapp.d(4): Error: `_aaApply2` is not `nothrow`
> onlineapp.d(1): Error: `nothrow` function `D main` may throw

Now as to why AA don't work at CT: They still use the "old" 
druntime approach, namely hiding all runtime magic behind 
`extern(C)` functions which are declared in the compiler frontend 
and defined in druntime (the linker doing the magic). This 
approach has the "upside" of bypassing all attributes checks (you 
can say that a function is `@safe pure nothrow @nogc` in the 
compiler frontend but not mark it as such in the `extern(C)` 
function and things will link), but it has many downsides: First, 
it's not CTFEable, meaning many things depending on the runtime 
had to be duplicated in the frontend; second, it can hurt 
performances, as it can't be inlined (although LTO might do a 
good job here); lastly, well, it bypass all attributes checks so 
when you actually have a mismatch all hell breaks loose.

There's been a few discussions about this over the year. For 
example, [this PR from a few years ago wanted to at least allow 
builtin types](https://github.com/dlang/dmd/pull/4571). 
@IgorStepanov did some work, e.g. 
[here](https://github.com/dlang/dmd/pull/3904) and 
[here](https://github.com/dlang/dmd/pull/4175) (and more). Martin 
Nowak IIRC also did quite some work on it.