I've been trying to fix bug 5590 and the deeper I go, the worse it looks.

- D's associative arrays cannot be represented with a struct in the current compiler.  They require magic initialization when null, and the current mapping doesn't give a sane way for this to happen.

- They are still implemented in the compiler.  Associative array indexing, creation etc is still done by the compiler inserting druntime calls.  Only some of these are hijacked by the struct in object.di.

- It complicates the compiler.  There are a bunch of places that attempt to detect both object.AssociativeArray and V[K] and handle both sanely, and several more that don't and crash the compiler. Slight changes cause backend crashes or wrong code generation.  The interpreter has implement every operation anyway, so nothing is gained by having the struct in object.d.

- The implementation can't be improved because it is tied to the druntime calls.  As far as I'm aware AssociativeArray was created so AAs could be improved without having to modify the compiler, and to make the compiler simpler.  The compiler is still required for AA literals, indexing, magic initialization, so I don't think this has worked.

- If they're in the library, they should be CTFEable.  Isn't this the whole point?  Even with each operation on AAs handled manually in the interpreter, inlineing will still pull the functions in AssociativeArray apart and reduce them to druntime calls.

The reason it needs to be done before the next release, is that it will break Andrei's recent addition (https://github.com/D-Programming-Language/druntime/pull/128).  (Which doesn't even work at compile time, and I don't think it can unless the _aaXXX functions are implemented as builtins)

Even if that was rolled back, removing the AssociativeArray hack will fix bugs.

AAs as a druntime/library type without compiler magic can be done at a later time when the design and implementation have been considered more carefully.

I'm quite happy to do the work in rolling this back (and implementing a better solution) but I feel the current state is a disaster.

Walter, Andrei, can I get a nod on this?

I agree completely. In Bugzilla, I found FIFTEEN reported compiler regressions caused by the introduction of library AAs. Most were very difficult to fix; in many cases the fix is very fragile.

Another issue that wasn't on your list: AA literals don't have a representation outside of the compiler, yet they are a crucial implementation issue.

Take at look at this code in object.di, it's really incredible:

struct AssociativeArray(Key, Value)
{
   void* p; // really Hashtable*

    Value get(Key key, lazy Value defaultValue)
    {
        auto p = key in *cast(Value[Key]*)(&p);   <------ Think about
what happens here.
        return p ? *p : defaultValue;
    }
}

The CTFE code to cope with this sort of thing is truly awful.

The D2 AA implementation is a pack of cards. If you make a small
change, it will break.
And it's getting worse. So far, every fix has made the compiler more
complicated and more closely tied to the runtime, in very subtle ways.

I think we should cut our losses, and roll it back. This particular approach is a disaster.

Meaning return to before there was an AA type in object.d or complete the transition to just the object.d version (which would include moving the code hidden off in the runtime into either object.d or a file imported publically by object.d)?

I'd prefer the latter.

On 2/2/2012 7:46 AM, Don Clugston wrote:
> I agree completely. In Bugzilla, I found FIFTEEN reported compiler regressions caused by the introduction of library AAs. Most were very difficult to fix; in many cases the fix is very fragile.
> 
> Another issue that wasn't on your list: AA literals don't have a representation outside of the compiler, yet they are a crucial implementation issue.
> 
> Take at look at this code in object.di, it's really incredible:
> 
> struct AssociativeArray(Key, Value)
> {
>    void* p; // really Hashtable*
> 
>     Value get(Key key, lazy Value defaultValue)
>     {
>         auto p = key in *cast(Value[Key]*)(&p);   <------ Think about
> what happens here.
>         return p ? *p : defaultValue;
>     }
> }
> 
> The CTFE code to cope with this sort of thing is truly awful.
> 
> The D2 AA implementation is a pack of cards. If you make a small
> change, it will break.
> And it's getting worse. So far, every fix has made the compiler more
> complicated and more closely tied to the runtime, in very subtle ways.
> 
> I think we should cut our losses, and roll it back. This particular
> approach is a disaster.
> _______________________________________________
> dmd-internals mailing list
> dmd-internals at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/dmd-internals

The former now, then the latter after the release.

It's not just a matter of moving the code into object.d (object.di actually, we need a way too fix the duplication as well)  For the transition to really work, the way AAs are handled in the frontend needs to be redone so that the glue layer, the backend, and the interpreter can completely forget they exist.

On Fri, Feb 3, 2012 at 3:16 AM, Brad Roberts <braddr at puremagic.com> wrote:
> Meaning return to before there was an AA type in object.d or complete the transition to just the object.d version (which would include moving the code hidden off in the runtime into either object.d or a file imported publically by object.d)?
>
> I'd prefer the latter.
>

What speaks against completing the switch to a runtime base AA?

Ouch. We definitely need to fix this, apologies for unknowingly breaking so much stuff.

Long term we must adjust the compiler to simply lower special AA notation into "regular" D code so we can rely on the library implementation. I'm not sure what the best route would be for CTFE (special-case AAs vs. interpreting the implementation in object.d).

BTW what's the awful thing you mention in object.di? You mean the cast must be interpreted during compilation?


Andrei

On 2/2/12 7:46 AM, Don Clugston wrote:
> I agree completely. In Bugzilla, I found FIFTEEN reported compiler regressions caused by the introduction of library AAs. Most were very difficult to fix; in many cases the fix is very fragile.
>
> Another issue that wasn't on your list: AA literals don't have a representation outside of the compiler, yet they are a crucial implementation issue.
>
> Take at look at this code in object.di, it's really incredible:
>
> struct AssociativeArray(Key, Value)
> {
>     void* p; // really Hashtable*
>
>      Value get(Key key, lazy Value defaultValue)
>      {
>          auto p = key in *cast(Value[Key]*)(&p);<------ Think about
> what happens here.
>          return p ? *p : defaultValue;
>      }
> }
>
> The CTFE code to cope with this sort of thing is truly awful.
>
> The D2 AA implementation is a pack of cards. If you make a small
> change, it will break.
> And it's getting worse. So far, every fix has made the compiler more
> complicated and more closely tied to the runtime, in very subtle ways.
>
> I think we should cut our losses, and roll it back. This particular
> approach is a disaster.
> _______________________________________________
> dmd-internals mailing list
> dmd-internals at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/dmd-internals

On 2/2/12 6:55 AM, Daniel Murphy wrote:
> I'm quite happy to do the work in rolling this back (and implementing a better solution) but I feel the current state is a disaster.
>
> Walter, Andrei, can I get a nod on this?

I suggest having Don decide on this. How onerous would it be to fix the issues before the release?

Andrei

For the next release, which we should be doing pretty soon, I think, I'd rather not do either.  For the next release, if it's reasonable to truely finish the conversion w/in one release cycle, I'd prefer to finish it.

On Fri, 3 Feb 2012, Daniel Murphy wrote:

> Date: Fri, 3 Feb 2012 03:23:36 +1100
> From: Daniel Murphy <yebblies at gmail.com>
> Reply-To: Discuss the internals of DMD <dmd-internals at puremagic.com>
> To: Discuss the internals of DMD <dmd-internals at puremagic.com>
> Subject: Re: [dmd-internals] AssociativeArray in druntime should go before the
>      next release
> 
> The former now, then the latter after the release.
> 
> It's not just a matter of moving the code into object.d (object.di actually, we need a way too fix the duplication as well)  For the transition to really work, the way AAs are handled in the frontend needs to be redone so that the glue layer, the backend, and the interpreter can completely forget they exist.
> 
> On Fri, Feb 3, 2012 at 3:16 AM, Brad Roberts <braddr at puremagic.com> wrote:
> > Meaning return to before there was an AA type in object.d or complete the transition to just the object.d version (which would include moving the code hidden off in the runtime into either object.d or a file imported publically by object.d)?
> >
> > I'd prefer the latter.
> >
> _______________________________________________
> dmd-internals mailing list
> dmd-internals at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/dmd-internals
> 

+dmd-internals back with Don's approval

Love this idea (below). If you folks bring things to a stable state for this release, I'll personally work on a library associative array implementation.


Thanks!

Andrei

On 2/2/12 12:55 PM, Don Clugston wrote:
> On 2 February 2012 20:39, Andrei Alexandrescu<andrei at erdani.com>  wrote:
>> Ouch. We definitely need to fix this, apologies for unknowingly breaking so much stuff.
>>
>> Long term we must adjust the compiler to simply lower special AA notation into "regular" D code so we can rely on the library implementation. I'm not sure what the best route would be for CTFE (special-case AAs vs. interpreting the implementation in object.d).
>>
>> BTW what's the awful thing you mention in object.di? You mean the cast must be interpreted during compilation?
>
> No. In that code, we're in an AA value[key] syntax that has been
> changed to an AssocArray!(key, value) struct.
> Now, we cast the first element of that struct into an AA. What it's doing is
> cast(typeof(this))this.
> but the two 'this'es are not the same. The original this is AssocArray
> template, while the typeof(this) is the compiler representation that
> corresponds to.
> They should be the same, but the 'in' syntax only works for the
> compiler 'this', not the runtime 'this'. Then, the poor compiler has
> to change it back into AssocArray!(). The really fun bit for CTFE is
> that with -inline, it all disappears; all you see is a void** getting
> cast to an template struct called 'AssociativeArray'. And that needs
> to work with array literals!!
>
> My feeling is, that the whole approach is doomed to failure. It is
> intrinsic fragile. I would suggest rolling back to the original D1
> AAs, which worked.
> Then, develop the new AA from scratch, _as if the built-in ones did
> not exist_. That includes, no AA literal syntax. Do it in a seperate,
> free-standing module.
> Once that is completely working, connect it up. Compilers role is
> simply to translate
>
> value[key] --->  AssocArray!(key, value)
> [a:b, c:d] -->  AALiteral([a, c], [b, d])   or whatever the chosen syntax is.
> The compiler must not do anything more than that. No semantics, no
> error messages, nothing. Pure syntax sugar, no semantic sugar. The
> type 'Taarray' (Associative array)  and ArrayLiteralExp  should not
> exist except in the parser.
>
> The compiler must either know everything about AAs, or nothing. There is no middle ground.
>
> I _suspect_ that if we try this, we'll find it isn't yet possible to do library AAs. Are we able to generate error messages at compile time when the same key is used twice? Maybe, maybe not. For sure we'll have to deal with template bloat.

>> I _suspect_ that if we try this, we'll find it isn't yet possible to do library AAs. Are we able to generate error messages at compile time when the same key is used twice? Maybe, maybe not. For sure we'll have to deal with template bloat.
No template bloat needed if the implementation would use an untyped
implementation
with comparison/hash callbacks. But this making them templated might be a
performance win.