Library associative array project v0.0.1

[H. S. Teoh]

On Thu, May 12, 2022 at 01:46:19PM -0400, Steven Schveighoffer via Digitalmars-d-announce wrote:
> On 5/12/22 1:15 PM, H. S. Teoh wrote:
> > On Wed, May 11, 2022 at 11:31:02AM -0400, Steven Schveighoffer via Digitalmars-d-announce wrote:
[...]
> > > 1. Proves that a library implementation is possible, also shows
> > > where shortcomings are.
> > 
> > What are the shortcomings that you found?
[...]
> I was surprised at how short the code is once you throw out all the
> TypeInfo BS that is currently in druntime.

Yeah, the TypeInfo stuff takes up a lot of code. And is hackish and
ugly.


> > > For the future:
> > > 
> > > 1. Implement all the things that AAs can do (which are possible,
> > > some are not).
> > 
> > Which things are not possible to do?
> 
> The whole thing how the compiler knows that an outer AA is being used
> to initialize an inner AA.
> 
> e.g. this works currently, but is impossible to hook for a library (I
> think):
> 
> ```d
> int[int][int] aa;
> aa[0][1] = 5;
> ```

I already saw this problem 8 years ago:

	https://issues.dlang.org/show_bug.cgi?id=7753

Maybe it's time for us to write a DIP for this? ;-)


> There's also possible problems with qualifiers that are
> yet-to-be-discovered, but usually show up when the compiler is
> cheating.

Ugh. AA + qualifiers == one of the dark dirty corners of D that I don't
like looking at. It's a prime example of an issue that's papered over
half-heartedly with a half-solution that doesn't really solve the
problem:

1. In the bad ole days, AA's used to allow unqualified types for the
key. This wasn't a problem with POD or immutable types, but shows up
when you try to make an AA with, say, a char[] key type. You'd insert a
key into the AA, then accidentally overwrite the array contents, and
suddenly the key "vanishes" from the AA -- because the contents changed
without the AA knowing, so it's still sitting in the old slot with the
old hash value.

2. This problem was brought up, so somebody thought it was a good idea
to implicitly force the key type into const. So when you declared an AA
of type int[char[]] for example, it'd get implicitly converted to
int[const(char[])].  But this doesn't solve anything!  All the const
does is ensure the AA cannot modify the key. But the user still can!!
So the original problem still exists.

AA keys really should be immutable, i.e., it should not be modifiable by
*anyone*, not the AA code, not the caller, not anyone else. That's the
only way you can guarantee the consistency of the hash values stored in
the AA vs. the contents of the key.

OTOH, though, you *do* want to accept const-qualified versions of the
key *during lookup*. (It would be onerous to require .idup'ing a char[]
into a string just so you can do a lookup in the AA, for example.) This
gets a bit hairy, though: if the AA entry may not exist and may need to
be created, then the key must be immutable ('cos we'll potentially be
storing a reference to the key in the AA). But if it's a pure lookup
without new entry creation, then const is acceptable.


> > > 2. Look at alternatives to GC for allocation/deallocation.
> > > 3. Possible use with betterC?
> > [...]
> > 
> > Just use malloc/free?  Could have problems with dangling references
> > to buckets, though, if somebody retains the pointer returned by `key
> > in aa` expressions.  Or use ref-counting of some sort.  But hard to
> > do this without changing binary compatibility.
> 
> Yes, the lifetime issues are the real problem with not using the GC.
> Maybe you just avoid the `in` operator in those flavors?
> Instead you can use a match-style operation, something like:
> 
> ```d
> hash.match(k, (ref v) {
>   // work with v
> });
> ```
[...]

That's a great idea.  Should be `scope ref`, though, to avoid the
reference leaking out via a closure / global. ;-)


T

-- 
English is useful because it is a mess. Since English is a mess, it maps well onto the problem space, which is also a mess, which we call reality. Similarly, Perl was designed to be a mess, though in the nicest of all possible ways. -- Larry Wall