Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)

[Rob T]

On Thursday, 8 November 2012 at 21:47:55 UTC, Nick Sabalausky 
wrote:
> It is *not* the case in his code. He has three actual 
> instantiated
> structs:
>
> R
> ------------------
> 1. int value (4 bytes)
> 2. d_list!R Rlist (size: TBD)
>
> d_list!R
> ------------------
> // **JUST POINTERS**
> 1. (d_list!R).node* head (4 bytes, assuming -m32)
> 2. (d_list!R).node* tail (4 bytes, assuming -m32)
>
> (d_list!R).node
> ------------------
> 1. (d_list!R)* outer (4 bytes, assuming -m32)
> 2. R payload (size: TBD)
> 3. (d_list!R).node* (4 bytes, assuming -m32)
> 4. (d_list!R).node* (4 bytes, assuming -m32)
>
> What other concrete types are there? *None*. Just those three.
>
> Now, let's expand *all* of the aggregate value types:
>
> R
> ------------------
> 1. int value (4 bytes)
> 2. d_list!R Rlist (size: 8 bytes)
>     2.1. (d_list!R).node* head (4 bytes, assuming -m32)
>     2.2. (d_list!R).node* tail (4 bytes, assuming -m32)
> Total: 4+8 == 12 bytes
>
> d_list!R
> ------------------
> // *JUST POINTERS*
> 1. (d_list!R).node* head (4 bytes, assuming -m32)
> 2. (d_list!R).node* tail (4 bytes, assuming -m32)
> Total: 4+4 == 8 bytes
>
> (d_list!R).node
> ------------------
> 1. (d_list!R)* outer (4 bytes, assuming -m32)
> 2. R payload (size: 12 bytes)
>     2.1. int value (4 bytes)
>     2.2. d_list!R Rlist (size: 8 bytes)
>         2.2.1. (d_list!R).node* head (4 bytes, assuming -m32)
>         2.2.2. (d_list!R).node* tail (4 bytes, assuming -m32)
> 3. (d_list!R).node* (4 bytes, assuming -m32)
> 4. (d_list!R).node* (4 bytes, assuming -m32)
> Total: 4+12+4+4 == 24 bytes
>
> Now there are NO MORE aggregate types left to be expanded, and 
> ALL 3
> types have an exact, FINITE size.
>
> There *IS NO RECURSION* here.

Nice description!

You have described *exaclty* how I expected the template 
evaluations to work their way out.

I'm very much interested in learning how manfred understands the 
process will unfold.

It could be that the template system simply does not operate as 
we expect, which IMO would be unfortunate because it will 
describe a system somewhat unrelated to actual coding (a problem 
C++ templates are infamous for), or that it is a manifestation of 
the problem where the out-of-order instantiations are not being 
evaluated in a way that works for all *legal* cases, which in 
that case can be considered a bug, esp since D is supposed to 
allow for out-of-order definitions.

Even when we remove the templates, it was noted that it can still 
fail if the node struct is defined inside the list, but that 
situation should be easily resolvable. So it seems we have at 
least one bug, and possibly two, or one bug and a template system 
that works as expected, but operates in a different dimension.

--rt