Recursive data structure using template won't compile

[Dmitry Olshansky]

11/9/2012 12:35 AM, Nick Sabalausky пишет:
> On Thu, 08 Nov 2012 19:19:52 +0400
> Dmitry Olshansky <dmitry.olsh at gmail.com> wrote:
>
>> 11/8/2012 10:39 AM, Rob T пишет:
>>> I want to create a simple recursive data structure as follows:
>>>
>>> struct R
>>> {
>>>      int value;
>>>      d_list!R Rlist;
>>> }
>>
>> Not possible - you don't know the size of R at this point. So
>> determine it compiler looks inside of d_list, and then encounters
>> _node_. It naturally sees T which is R and starts this loop anew.
>>
>
> That's incorrect behavior. The size of R is NOT needed to determine
> the size of "d_list!R":
>
> Note that "d_list!R" has exactly 2 data members, and BOTH of them are
> pointers. Therefore, the size of "d_list!R" is trivially determined
> *regardless* of its template parameter or "nested" type: Two pointers
> == 8 bytes on 32-bit, 16 bytes on 64-bit, *regardless* of what the
> pointers point to.
>
> Also note that "node" is not actually a *data* member of d_list, and
> does not contribute to the size or internal structure of d_list.

Yeah, that's all good and well, I mean that I can calculate the size. 
But well I'm far smarter then DMD :)

And most like the problem is not size. I was mistaken as it must be 
template instantiation itself.

Basically:
to analyze R -> inst-te d_list!R ---during which---> (in fact) inst-te 
node!R ---during which---> inst-te d_list!R -> ...

and d_list!R is not yet ready since we analyze node!R

Now it could probably improve on it to handle this somehow. I dunno how 
general it can be or special cased it will be.


Now the extra fun - 2 snippets.

First one dies with forward ref.
Probably because inside of node it issues forward reference to R and 
inside of R forward reference for d_list and it wasn't finished because 
of node waiting on forward reference to R?
Just coming up with an idea how it may fail, not arguing for it being 
correct ;)

struct d_list
{
struct node
{
       R payload;
       node* pred;
       node* succ;
}

     node* _head;
     node*  _tail;
}

struct R
{
    int value;
    d_list Rlist;
}

void main(){
	R r;	
}


But this one doesn't.

struct node
{
       R payload;
       node* pred;
       node* succ;
}

struct d_list
{
     node* _head;
     node*  _tail;
}

struct R
{
    int value;
    d_list Rlist;
}

void main(){
	R r;	
}


-- 
Dmitry Olshansky