Official DMD compiler written in D

[H. S. Teoh]

On Thu, Jan 10, 2013 at 04:51:35AM +0100, Timon Gehr wrote:
> On Wednesday, 9 January 2013 at 18:45:56 UTC, H. S. Teoh wrote:
[...]
> >Whoa!!! Now you really caught my interest!
> >
> >Can it handle CTFE-computed mixins that declare and reference
> >variables?  If it can, I will finally be able to write a library AA
> >implementation that allows static AA literals (no runtime
> >init/allocation needed)!
> 
> Probably yes, but I am not sure what you mean. Can you provide an
> example?

The basic idea behind static AA literals is to use CTFE to compute the
hashes of the keys, and therefore which slot(s) they will fall in, at
compile time. Armed with this information, we can create an array of
slots at compile-time that contains the AA entries by declaring each
slot as a static variable and using the slot assignment information to
initialize the hash table (array of pointers to slots) to point to these
slots.

Now, there are some challenges to be overcome here. For example, the
slots need to be declared as local variables, and therefore need unique
names (the hash table array needs to be able to refer to the addresses
of these variables), so the only way I can think of to do this at
compile-time is to have the CTFE code generate mixins to declare those
variables. So here's the tricky part. Suppose you have this CTFE code:

	// Not the real code, just a rough sketch to give the idea
	string aaComputeAASlots(K,V)(K[V] aaLiteral) {
		// Create slots
		string slotVars;
		foreach (key, value; aaLiteral) {
			size_t slotNum = hashOf(key) % numKeys;
			string slotName = "aaSlot" ~ slotNum;
			slotVars ~= "immutable Slot " ~ slotName ~
				" = Slot(" ~ key ~ ", " ~ value ~ ");";
		}

		string mainTable = q{
			immutable Slot*[] aaTable = {
				&aaSlot0,
				&aaSlot1,
				... // generate these programmatically
			};
		};

		return slotVars ~ mainTable;
	}

	// Instantiate AA here, at compile time.
	mixin(aaComputeAASlots(myLiteral));

The mixin string would look something like this:

	"immutable Slot aaSlot0 = Slot(..., ...);
	 immutable Slot aaSlot1 = Slot(..., ...);
	 immutable Slot*[] aaTable = {
	 	&aaSlot0, &aaSlot1, ...
	 }"

The question is, will the compile be able to resolve &aaSlot0, &aaSlot1,
etc., at compile-time?

Obviously, this code works if you copy-n-paste it into a .d source file.
It also works if I write it as a string literal, then use mixin().
However, on DMD, if the string is returned by a CTFE function that
builds it using ~, for some reason all the pointers in aaTable are null.
Strangely enough, if I assign the returned string to a string variable
and print it out at runtime, the correct string is produced.

So I concluded that somehow, DMD was unable to correctly interpret
&aaSlot0 inside a mixin string at compile-time.


T

-- 
It's bad luck to be superstitious. -- YHL