Jump to page: 1 27  
Page
Thread overview
Recursive data structure using template won't compile
Nov 08, 2012
Rob T
Nov 08, 2012
Rob T
Nov 08, 2012
Nick Sabalausky
Nov 08, 2012
Dmitry Olshansky
Nov 08, 2012
Rob T
Nov 08, 2012
Philippe Sigaud
Nov 08, 2012
Rob T
Nov 08, 2012
Rob T
Nov 08, 2012
Manfred Nowak
Nov 08, 2012
Rob T
Nov 08, 2012
Rob T
Compilable Recursive Data Structure ( was: Recursive data structure using template won't compile)
Nov 08, 2012
Manfred Nowak
Nov 08, 2012
Manfred Nowak
Nov 08, 2012
Rob T
Nov 08, 2012
Manfred Nowak
Nov 08, 2012
Rob T
Nov 08, 2012
Nick Sabalausky
Nov 08, 2012
Nick Sabalausky
Nov 08, 2012
Rob T
Nov 08, 2012
Nick Sabalausky
Nov 08, 2012
Andrej Mitrovic
Nov 09, 2012
Rob T
Nov 08, 2012
Rob T
Nov 09, 2012
Manfred Nowak
Nov 09, 2012
Nick Sabalausky
Nov 09, 2012
Manfred Nowak
Nov 09, 2012
Rob T
Nov 09, 2012
Manfred Nowak
Nov 10, 2012
Nick Sabalausky
Nov 10, 2012
Manfred Nowak
Nov 10, 2012
Nick Sabalausky
Nov 11, 2012
Manfred Nowak
Nov 10, 2012
Rob T
Nov 10, 2012
Rob T
Nov 10, 2012
Nick Sabalausky
Nov 10, 2012
Rob T
Nov 12, 2012
Don Clugston
Nov 12, 2012
1100110
Nov 12, 2012
Andrej Mitrovic
Nov 12, 2012
Andrej Mitrovic
Nov 13, 2012
Rob T
Nov 13, 2012
Andrej Mitrovic
Nov 13, 2012
Don Clugston
Nov 13, 2012
Andrej Mitrovic
Nov 13, 2012
Nick Sabalausky
Nov 13, 2012
Nick Sabalausky
Nov 13, 2012
Rob T
Nov 10, 2012
Nick Sabalausky
Nov 10, 2012
Manfred Nowak
Nov 09, 2012
Rob T
Nov 09, 2012
Manfred Nowak
Nov 09, 2012
Timon Gehr
Nov 09, 2012
Philippe Sigaud
Nov 09, 2012
Timon Gehr
Nov 10, 2012
Artur Skawina
Nov 09, 2012
Manfred Nowak
Nov 09, 2012
Timon Gehr
Nov 10, 2012
Manfred Nowak
Nov 10, 2012
Timon Gehr
Nov 10, 2012
Manfred Nowak
Nov 10, 2012
Rob T
Nov 10, 2012
Manfred Nowak
Nov 08, 2012
Nick Sabalausky
Nov 08, 2012
Dmitry Olshansky
Nov 08, 2012
Nick Sabalausky
Nov 08, 2012
Rob T
Nov 10, 2012
Manfred Nowak
November 08, 2012
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
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
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
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
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
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
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
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
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
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
« First   ‹ Prev
1 2 3 4 5 6 7