How does D allow delegates as template parameters?

Question

In "The D Programming Language" by Andrei Alexandrescu,

there's an example where a delegate is taken as a template parameter:

T[] find(alias pred, T)(T[] input)
  if(is(typeof(pred(input[0])) == bool))
{
  for(; input.length > 0; input = input[1 .. $]) {
    if (pred(input[0])) break;
  }
  return input;
}

unittest {
  int[] a = [1,2,3,4,-5,3,-4];
  int z = -2;
  auto b = find!(delegate(x) { return x < z; })(a);
  asssert(b == a[4..$]);
}

Alexandrescu explains that this works because a delegate is actually a fat pointer consisting of two parts: the function pointer and the pointer to its stack frame (which is why z is accessible inside its body). Except that find takes "pred" as a TEMPLATE parameter, not as an argument. And template arguments can only be compile-time constants.

I'm sure the address of the anonymous delegate in our unit test is indeed a compile-time constant, but the address of its stack-frame certainly shouldn't be, so how can the delegate be taken as a template parameter?

What's really going on here?

Answer 1

An alias parameter generates new code custom made for the particular symbol given, which includes stuff in-context.

Let's take a look at the disassembly:

0805c850 <_D6test564mainFZv20__T12__dgliteral1TiZ12__dgliteral1MFNbNfiZb>:
805c850:       55                      push   ebp
805c851:       8b ec                   mov    ebp,esp
805c853:       83 ec 04                sub    esp,0x4
805c856:       8b 48 d8                mov    ecx,DWORD PTR [eax-0x28]
805c859:       3b 4d 08                cmp    ecx,DWORD PTR [ebp+0x8]
805c85c:       0f 9f c0                setg   al
805c85f:       0f b6 c0                movzx  eax,al
805c862:       c9                      leave
805c863:       c2 04 00                ret    0x4

This is the literal delegate created here (without optimizations btw). The interesting lines are the mov and cmp in the middle.

Note that the context pointer is passed to a delegate in the eax register. Let's see where this is called:

0805c868 <_D6test5632__T4findS18main12__dgliteral1TiZ4findMFNaNbNfAiZAi>:
 // snip a bunch of irrelevant code
805c870:       89 45 fc                mov    DWORD PTR [ebp-0x4],eax
// snip
805c892:       8b 45 fc                mov    eax,DWORD PTR [ebp-0x4]
805c895:       89 95 f8 ff ff ff       mov    DWORD PTR [ebp-0x8],edx
805c89b:       e8 b0 ff ff ff          call   805c850 <_D6test564mainFZv20__T12__dgliteral1TiZ12__dgliteral1MFNbNfiZb>

Notice two things there: first, the name: notice that dgliteral is in there - this is a special-generated function for this specific argument!

Second, notice that whatever was passed to this function in eax gets stored and ultimately passed to the other function too.

Let's go up the call stack one more time, now we're in _Dmain where the find call appears:

 805c7da:       89 e8                   mov    eax,ebp
 805c7dc:       e8 87 00 00 00          call   805c868 <_D6test5632__T4findS18main12__dgliteral1TiZ4findMFNaNbNfAiZAi>

It is passing the base pointer! BTW, remember that 0x28? We can see it in _Dmain too, a couple lines up:

 805c7d1:       c7 45 d8 fe ff ff ff    mov    DWORD PTR [ebp-0x28],0xfffffffe

That's the int z = -2; line (-2 is represented as fffffffe in 32 bit). It is stored in the stack like a regular local variable.

Bottom line, what happens is that particular alias argument generates a whole new function which knows where all the local variables are found. When it is called, the base pointer to them is forwarded to it, which is all it needs to know.

Note btw that you can also pass local variables as alias params and get similar code, it makes a function which pokes the offset directly rather than taking a pointer.

Also, if you try to pass a runtime delegate to the alias argument, or if you try to store the alias dg somewhere else, that will not compile. This is a special function with case-specific code, a lot of generic delegate stuff doesn't quite work for it.