Thread overview | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
November 08, 2012 Recursive data structure using template won't compile | ||||
---|---|---|---|---|
| ||||
I want to create a simple recursive data structure as follows: struct R { int value; d_list!R Rlist; } // d-linked list with templated payload struct d_list( T ) { struct node { T payload; node* pred; node* succ; } node* head; node* tail; } The compiler complains about node having "forward references". I was able to get something like this to work in C++, so I imagine I can also get it to work in D, but does anyone know how? I also want to template the recursive structure itself to specify the value type, ie struct R(T){ T value; d_list!R Rlist; }, but I left that out to keep the example more simple. I've been stuck on this problem all day, so any help is appreciated! --rt |
November 08, 2012 Re: Recursive data structure using template won't compile | ||||
---|---|---|---|---|
| ||||
Posted in reply to Rob T | If I use a pointer as the payload type for my d_list, it compiles OK. I'd rather not use a pointer for the payload, and it will compile in D if I hard code in the payload type. --rt |
November 08, 2012 Re: Recursive data structure using template won't compile | ||||
---|---|---|---|---|
| ||||
Posted in reply to Rob T | On Thu, 08 Nov 2012 07:39:27 +0100 "Rob T" <rob@ucora.com> wrote: > I want to create a simple recursive data structure as follows: > > struct R > { > int value; > d_list!R Rlist; > } > > // d-linked list with templated payload > struct d_list( T ) > { > struct node > { > T payload; > node* pred; > node* succ; > } > node* head; > node* tail; > } > > The compiler complains about node having "forward references". > Looks like a compiler bug. You should report it: http://d.puremagic.com/issues/ |
November 08, 2012 Re: Recursive data structure using template won't compile | ||||
---|---|---|---|---|
| ||||
Posted in reply to Rob T | 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. To break this chain make node a separate templated struct outside of d_list. Then peeking inside of d_list compiler shouldn't go crazy. > > // d-linked list with templated payload > struct d_list( T ) > { > struct node > { > T payload; > node* pred; > node* succ; > } > node* head; > node* tail; > } > > The compiler complains about node having "forward references". > > I was able to get something like this to work in C++, so I imagine I can > also get it to work in D, but does anyone know how? > Naturally C++ doesn't have nested struct definitions. > I also want to template the recursive structure itself to specify the > value type, ie struct R(T){ T value; d_list!R Rlist; }, but I left that > out to keep the example more simple. > > I've been stuck on this problem all day, so any help is appreciated! See if it helps. -- Dmitry Olshansky |
November 08, 2012 Re: Recursive data structure using template won't compile | ||||
---|---|---|---|---|
| ||||
Posted in reply to Dmitry Olshansky | On Thursday, 8 November 2012 at 15:19:56 UTC, Dmitry Olshansky wrote: > > Naturally C++ doesn't have nested struct definitions. > I don't have a nested struct, the struct definition defines the type only, and the nodes are allocated as pointers from a new operation when the list is composed. The node struct has a member var that may or may not be a struct type, it does not matter, and C++ will allow a member data type to be a struct just fine. >> I also want to template the recursive structure itself to specify the >> value type, ie struct R(T){ T value; d_list!R Rlist; }, but I left that >> out to keep the example more simple. >> > >> I've been stuck on this problem all day, so any help is appreciated! > > See if it helps. I tried moving the node struct outside the d_list struct, but no luck, and I think it should not matter anyway since I can get it to work in that way without a template. The solution so far is to do it the C++ way, using pointers, which sucks. I think in this case the D template should work just fine, and the problem is either a bug or a design flaw with how templates are evaluated. I'll wait a bit longer for more comments before filing a bug report. --rt |
November 08, 2012 Re: Recursive data structure using template won't compile | ||||
---|---|---|---|---|
| ||||
Posted in reply to Rob T Attachments:
| Rob, your original code:
// d-linked list with templated payload
struct d_list( T )
{
struct node
{
T payload;
node* pred;
node* succ;
}
node* head;
node* tail;
}
compiles just fine for me (Linux 32bits, DMD 2.060).
Even with some exercising, the template doesn't fail:
void main()
{
auto list = d_list!(int)();
}
On Thu, Nov 8, 2012 at 6:49 PM, Rob T <rob@ucora.com> wrote:
> On Thursday, 8 November 2012 at 15:19:56 UTC, Dmitry Olshansky wrote:
>
>>
>> Naturally C++ doesn't have nested struct definitions.
>>
>>
> I don't have a nested struct, the struct definition defines the type only, and the nodes are allocated as pointers from a new operation when the list is composed. The node struct has a member var that may or may not be a struct type, it does not matter, and C++ will allow a member data type to be a struct just fine.
>
>
> I also want to template the recursive structure itself to specify the
>>> value type, ie struct R(T){ T value; d_list!R Rlist; }, but I left that out to keep the example more simple.
>>>
>>>
>> I've been stuck on this problem all day, so any help is appreciated!
>>>
>>
>> See if it helps.
>>
>
> I tried moving the node struct outside the d_list struct, but no luck, and I think it should not matter anyway since I can get it to work in that way without a template.
>
> The solution so far is to do it the C++ way, using pointers, which sucks.
>
> I think in this case the D template should work just fine, and the problem is either a bug or a design flaw with how templates are evaluated.
>
> I'll wait a bit longer for more comments before filing a bug report.
>
> --rt
>
>
>
|
November 08, 2012 Re: Recursive data structure using template won't compile | ||||
---|---|---|---|---|
| ||||
Posted in reply to Philippe Sigaud | On Thursday, 8 November 2012 at 17:57:11 UTC, Philippe Sigaud wrote:
> Rob, your original code:
>
> // d-linked list with templated payload
> struct d_list( T )
> {
> struct node
> {
> T payload;
> node* pred;
> node* succ;
> }
> node* head;
> node* tail;
> }
>
> compiles just fine for me (Linux 32bits, DMD 2.060).
>
> Even with some exercising, the template doesn't fail:
>
> void main()
> {
> auto list = d_list!(int)();
> }
>
>
Yes that part works fine, but that's only the d_list part. When I try to use my supposedly re-usable d-list to define a recursive struct, that's when it fails. Take another look at the original post, you'll see what I mean.
--rt
|
November 08, 2012 Re: Recursive data structure using template won't compile | ||||
---|---|---|---|---|
| ||||
Posted in reply to Rob T | I want to be clear that I'm trying to define a recursive data structure, not a recursive D struct, which of course is not possible.
The nodes in the d_list are allocated as pointers, and the node size syhould be knowable during compile time, so this is IMO a design flaw with how templates are being evaluated. It's possible that I'm doing something wrong, so correct me if there's a reasonable way to get this job done (eg no use of mixin hacks).
--rt
On Thursday, 8 November 2012 at 18:07:45 UTC, Rob T wrote:
> On Thursday, 8 November 2012 at 17:57:11 UTC, Philippe Sigaud wrote:
>> Rob, your original code:
>>
>> // d-linked list with templated payload
>> struct d_list( T )
>> {
>> struct node
>> {
>> T payload;
>> node* pred;
>> node* succ;
>> }
>> node* head;
>> node* tail;
>> }
>>
>> compiles just fine for me (Linux 32bits, DMD 2.060).
>>
>> Even with some exercising, the template doesn't fail:
>>
>> void main()
>> {
>> auto list = d_list!(int)();
>> }
>>
>>
>
> Yes that part works fine, but that's only the d_list part. When I try to use my supposedly re-usable d-list to define a recursive struct, that's when it fails. Take another look at the original post, you'll see what I mean.
>
> --rt
|
November 08, 2012 Re: Recursive data structure using template won't compile | ||||
---|---|---|---|---|
| ||||
Posted in reply to Rob T | Rob T wrote: > I want to be clear that I'm trying to define a recursive data structure [...] > so correct me if there's a reasonable way to get this job done A recursive data structure needs a mooring ... and such a mooring is missing in the code given. -manfred |
November 08, 2012 Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile) | ||||
---|---|---|---|---|
| ||||
Posted in reply to Rob T | Rob T wrote: | struct d_list( T ) | { | struct node | { | T payload; | node* pred; | node* succ; | } | node* head; | node* tail; | } This doesn't loo like a list. It looks like the ancor of a list. Let me rewrite it and use D-parlor. | struct Ancor( T){ | struct Node | { | T payload; | Node* pred; | Node* succ; | } | Node* head; | Node* tail; | } This might be the ancor of a doubly linked list for a `payload' of generic type `T'. But there is a problem: generic type `T' might be itself a double linked list using an ancor of type `Ancor'. If this would be true and there would be no mooring everyone, compiler included, would plunge into an infinite loop. Therefore `T' must inform `Ancor' wether that condition comes true---or `T' itself must take the lead. -manfred |
Copyright © 1999-2021 by the D Language Foundation