[dmd-internals] AssociativeArray in druntime should go before the next release

[Steve Schveighoffer]

As someone who's actually developed a hashmap in D2, I'd agree with Don that there are still some things that cannot fully implement how builtin AA's work (most glaring example is lack of constructor that takes literal values).  But it's better to have this part of the system pluggable.  Not only does it allow one to utilize D's power to work on something intrinsic like this, but it makes things simpler to understand from a maintenance perspective.  Not to mention, I could make AA's into dcollections hashmaps with some simple changes to the runtime :)


I agree with the approach below except for 2 things:

1. D1 AA's used a tree to handle bucket collisions, I don't think we should roll back that far (not sure what the state of D1 AAs are today).
2. This conversion:  [a:b, c:d] -->  AALiteral([a, c], [b, d]) should *NOT* use the heap for the two array literals.  I'm not sure how you can declare AALiteral such that this doesn't happen, but this needs to be solved.


-Steve



----- Original Message -----
> From: Andrei Alexandrescu <andrei at erdani.com>
> To: Don Clugston <dclugston at googlemail.com>; Discuss the internals of DMD <dmd-internals at puremagic.com>
> Cc: 
> Sent: Thursday, February 2, 2012 5:11 PM
> Subject: Re: [dmd-internals] AssociativeArray in druntime should go before the next release
> 
> +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.
> _______________________________________________
> dmd-internals mailing list
> dmd-internals at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/dmd-internals
>