www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Recursive data structure using template won't compile

reply "Rob T" <rob ucora.com> writes:
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
Nov 07 2012
next sibling parent "Rob T" <rob ucora.com> writes:
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
Nov 07 2012
prev sibling next sibling parent Nick Sabalausky <SeeWebsiteToContactMe semitwist.com> writes:
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/
Nov 08 2012
prev sibling next sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
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
Nov 08 2012
next sibling parent reply "Rob T" <rob ucora.com> writes:
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
Nov 08 2012
parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
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





 Nov 08 2012



  parent reply "Rob T" <rob ucora.com>  writes:


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



 Nov 08 2012



  parent reply "Rob T" <rob ucora.com>  writes:


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





 Nov 08 2012



 next sibling parent reply Manfred Nowak <svv1999 hotmail.com>  writes:


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

 



 Nov 08 2012



  parent reply "Rob T" <rob ucora.com>  writes:


On Thursday, 8 November 2012 at 18:45:08 UTC, Manfred Nowak wrote:

 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

 


I'm afraid I don't follow what you mean by mooring and anchor 
given the example at hand.

The structure as described allows for the implementation of a 
real-world useful structure, such as a property tree, where a 
value may have an associated list of sub-values, (recursive) 
forming a tree of values. The list of associated values is of 
arbitrary length and a d-list is not necessarily required, so 
long as it's a list.

This is a simple yet very usefull structure, which I can define 
apparently legally in D so long as I do not make use of a 
template. If I can define it legally without a template, then I 
expected to be able to define it with a template.

Obviously infinite recursive structs cannot be allowed, and dmd 
does detect these cases. In my case, the struct that implements 
the list contains nothing but pointers, therefore it should allow 
for lists of lists, and indeed it does, but only if I do not use 
templates OR I use templates but also change the payload to be a 
pointer.

Why the difference in ability to compile as a template vs a 
non-template if the all of the template structures can be 
completely resolved into defined states during compile time - 
just as it would be if I hard coded the same types?

--rt



 Nov 08 2012



  parent  "Rob T" <rob ucora.com>  writes:


Before I forget, it is important to note that the structure 
consists of two parts, the value with a list of associated 
sub-values, along with the list.

struct R
{
    int value;
    d_list!R Rlist;
}

struct d_list( T )
{
    struct node
    {
       T payload;
       node* pred;
       node* succ;
    }
    node* head;
    node* tail;
}

--rt



 Nov 08 2012



prev sibling  parent reply Manfred Nowak <svv1999 hotmail.com>  writes:


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   



 Nov 08 2012



  parent reply Manfred Nowak <svv1999 hotmail.com>  writes:


Manfred Nowak wrote:


 or `T' itself must take the lead.


`T' was given as:
| struct R
| {
|     int value;
|     d_list!R Rlist;
| }

... and using the given changes as well as D-parlor `T' becomes:
| struct R {
|     int value;
|     Ancor!R list;
| }

Because `R' can recurse infinitely over `Ancor' a mooring and a way 
to that mooring is needed. Let the mooring be, when there are no more 
`Ancor' to expect, i.e. the way to that mooring leads from some 
height down to zero.

That means `R' has to know its height. `R' roughly becomes: 
| struct R( int height) {
|     int value;
|     Ancor!R( height-1) list;
| }

That describes the way. Of course the mooring is still missing:
| struct R( int height)
|   if( height > 0) {
|     int value;
|     Ancor!R( height-1) list;
| }
| struct R( int height)
|   if( height <= 0) {
|     int value;
| }

That's it. Only missing some testing:

import std.stdio: writeln;
void main(){

  alias R!(1) First;
  First elem;
  elem.value= 1;
  writeln( elem);

  alias Ancor!First.Node Node;
  Node n;
  n.payload= elem;
  n.pred= null;
  n.succ= null;
  writeln( n);

  alias Ancor!First Ancor1;
  Ancor1 ancor;
  ancor.head= &n;
  ancor.tail= &n;
  writeln( ancor);
}

-manfred



 Nov 08 2012



  parent reply "Rob T" <rob ucora.com>  writes:


On Thursday, 8 November 2012 at 20:39:29 UTC, Manfred Nowak wrote:

 Manfred Nowak wrote:


 or `T' itself must take the lead.


 `T' was given as:
 | struct R
 | {
 |     int value;
 |     d_list!R Rlist;
 | }

 ... and using the given changes as well as D-parlor `T' becomes:
 | struct R {
 |     int value;
 |     Ancor!R list;
 | }

 Because `R' can recurse infinitely over `Ancor' a mooring and a 
 way
 to that mooring is needed. Let the mooring be, when there are 
 no more
 `Ancor' to expect, i.e. the way to that mooring leads from some
 height down to zero.

 That means `R' has to know its height. `R' roughly becomes:
 | struct R( int height) {
 |     int value;
 |     Ancor!R( height-1) list;
 | }

 That describes the way. Of course the mooring is still missing:
 | struct R( int height)
 |   if( height > 0) {
 |     int value;
 |     Ancor!R( height-1) list;
 | }
 | struct R( int height)
 |   if( height <= 0) {
 |     int value;
 | }

 That's it. Only missing some testing:

 import std.stdio: writeln;
 void main(){

   alias R!(1) First;
   First elem;
   elem.value= 1;
   writeln( elem);

   alias Ancor!First.Node Node;
   Node n;
   n.payload= elem;
   n.pred= null;
   n.succ= null;
   writeln( n);

   alias Ancor!First Ancor1;
   Ancor1 ancor;
   ancor.head= &n;
   ancor.tail= &n;
   writeln( ancor);
 }

 -manfred


I still don't follow what you are trying to point out.

I use this form of structure in real world applications, and they 
work just fine as-is.

If you mean by 'anchor' a way to end the recursion, that's a 
trivial problem already solved - the recursion ends when the list 
is empty. Of course I've left out the associated logic that does 
the necessary work, since that is not relevant to the problem at 
hand and clutters the issue.

No matter if there's merit to what you are describing, or not, 
the structure as-is should be legally definable as a template. In 
fact, I can define the structure just fine provided that I do not 
use a template.

--rt



 Nov 08 2012



  parent reply Manfred Nowak <svv1999 hotmail.com>  writes:


Rob T wrote:


 In fact, I can define the structure just fine provided that I do not 
 use a template.


.. and if one uses a template one can get an infinite recursion, 
because templates include recursion. This is the case in your code.

The code I gave elimates that infinite recursion. The code compiles 
although it uses a template.

Not seeing e recursion does not mean that there is none. Not every 
recursion is as simple to see as:

| alias X Y;
| alias Y X;

-manfred 



 Nov 08 2012



 next sibling parent reply "Rob T" <rob ucora.com>  writes:


On Thursday, 8 November 2012 at 21:15:17 UTC, Manfred Nowak wrote:

 Rob T wrote:


 In fact, I can define the structure just fine provided that I 
 do not use a template.


 .. and if one uses a template one can get an infinite recursion,
 because templates include recursion. This is the case in your 
 code.

 The code I gave elimates that infinite recursion. The code 
 compiles
 although it uses a template.

 Not seeing e recursion does not mean that there is none. Not 
 every
 recursion is as simple to see as:

 | alias X Y;
 | alias Y X;

 -manfred


I think I'm starting to understand what you are doing, however 
we're operating on two separate planes of existence.

What you are describing, is a different structure than what I 
want. The template creates two separate struct types for R, one 
with a list and one without (R1 & R2), but I want only one type 
R, otherwise it will introduce a ton of complications in the form 
of me having to make just about eveything that uses these two 
different structures a template and/or duplicated overloaded 
functions.

Perhaps I just don't understand the in's and out's of D 
templates, but it's just not doing what I want.

So is there a way to retain identical struct types for R by 
disabling the not-so-useful-in-my-case template recursion?

--rt



 Nov 08 2012



  parent  Nick Sabalausky <SeeWebsiteToContactMe semitwist.com>  writes:


On Thu, 08 Nov 2012 22:46:46 +0100
"Rob T" <rob ucora.com> wrote:

 
 So is there a way to retain identical struct types for R by 
 disabling the not-so-useful-in-my-case template recursion?
 


There is no template recursion in your code (you have *exactly* 3
concrete types even after all template instantiations), see my reply to
Manfred.



 Nov 08 2012



prev sibling  parent reply Nick Sabalausky <SeeWebsiteToContactMe semitwist.com>  writes:


On Thu, 8 Nov 2012 21:15:17 +0000 (UTC)
Manfred Nowak <svv1999 hotmail.com> wrote:


 Rob T wrote:
 

 In fact, I can define the structure just fine provided that I do
 not use a template.


 
 .. and if one uses a template one can get an infinite recursion, 
 because templates include recursion. This is the case in your code.
 


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.



 Nov 08 2012



 next sibling parent reply "Rob T" <rob ucora.com>  writes:


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



 Nov 08 2012



  parent reply Nick Sabalausky <SeeWebsiteToContactMe semitwist.com>  writes:


On Thu, 08 Nov 2012 23:28:05 +0100
"Rob T" <rob ucora.com> wrote:

 
 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.
 


Historically, DMD tended to have a lot of trouble actually resolving
forward references according to spec (perhaps due to it's C/C++ roots?).
Most of big glaring problems have been fixed since then, but
unfortunately there's still a number of edge cases yet to be ironed out.

It *is* possible to construct types in a way that is inherently
ambiguous, and cannot be correctly handled by the compiler even
in theory. So naturally those cases will end up being "forward
reference", or perhaps more accurately "circular definition". But your
example is definitely not such a case, so however the compiler is
currently processing it, it needs to be fixed.

FWIW, you should be able to work around the issue by making some of the
pointers "void*". You'll lose some type safety and have to remember to
cast things correctly, but it should at least make it compile (although
I haven't tried it).



 Nov 08 2012



 next sibling parent reply Andrej Mitrovic <andrej.mitrovich gmail.com>  writes:


On 11/9/12, Nick Sabalausky <SeeWebsiteToContactMe semitwist.com> wrote:

 FWIW, you should be able to work around the issue by making some of the
 pointers "void*". You'll lose some type safety and have to remember to
 cast things correctly, but it should at least make it compile (although
 I haven't tried it).


Perhaps another possible workaround is to use 'alias this'.

struct R
{
    struct Data
    {
        int value;
    }

    Data data;
    alias data this;

    d_list!Data Rlist;
}

May not work in all cases though..



 Nov 08 2012



  parent  "Rob T" <rob ucora.com>  writes:


Interestingly, this is a workaround that may be workable somehow. 
I've even been able to expand it so that the R.value type is 
determined by a temnplate.

struct node( P )
{
    P payload;
    node* pred;
    node* succ;
}

struct R( V )
{
    V value;
    alias node!R N;
    d_list!N Rlist;
}

struct d_list( N )
{
    N* head;
    N* tail;
    // even this works
    ref typeof(N.payload) getFirstValue(){
       return head.payload;
    }
}


--rt



 Nov 08 2012



prev sibling  parent  "Rob T" <rob ucora.com>  writes:


On Thursday, 8 November 2012 at 23:05:33 UTC, Nick Sabalausky 
wrote:

 Most of big glaring problems have been fixed since then, but
 unfortunately there's still a number of edge cases yet to be 
 ironed out.


Clearly.


 FWIW, you should be able to work around the issue by making 
 some of the
 pointers "void*". You'll lose some type safety and have to 
 remember to
 cast things correctly, but it should at least make it compile 
 (although
 I haven't tried it).


The T* pointers don't seem to be the problem, it's the T payload. 
If I switch to T* payload it all works OK, but I'll have to 
perform allocations on each instance of payload which is not 
desirable. I may still get away with it in my case, but I'm very 
concerned that it will start eating up memory needlessly because 
the GC appears to come with a ton of issues yet to be resolved.

--rt



 Nov 08 2012



prev sibling  parent reply Manfred Nowak <svv1999 hotmail.com>  writes:


Nick Sabalausky wrote:


 ALL 3 types have an exact, FINITE size.
 There *IS NO RECURSION* here.


This conclusion is wrong. Otherwise one can conclude that `s' is not 
recursing on itself in this code:

struct S{ S* next;}
S s;
s.next= &s;

... because `s' has a fixed and finite size.

One way to see the recursion in the problem given is to evaluate the 
exact types of the three entities starting with `(d_list!R).(node!
R)'---yes, `node' is templated implicitely---and yes, not starting 
names of types with upper case might confuse the senses.

Reaching `R' one might see, that
  `typeof( R)'
must be equal to
  `typeof( int x &( R x &( (d_list!R).(node!R))^2)^2 )'

where `T x U' is equívalent to put types `T' and `U' into a record,
      `&T' is an adress of some variabkle of type `T' and
      `T^2' is short hand for `T x T'.

If there is no such `R' for which this equality holds, then recursion 
is not avoidable.

Please guess what I believe.

-manfred

      
 
 



 Nov 08 2012



 next sibling parent reply Nick Sabalausky <SeeWebsiteToContactMe semitwist.com>  writes:


On Fri, 9 Nov 2012 01:17:09 +0000 (UTC)
Manfred Nowak <svv1999 hotmail.com> wrote:


 Nick Sabalausky wrote:
 

 ALL 3 types have an exact, FINITE size.
 There *IS NO RECURSION* here.


 
 This conclusion is wrong. Otherwise one can conclude that `s' is not 
 recursing on itself in this code:
 
 struct S{ S* next;}
 S s;
 s.next= &s;
 
 ... because `s' has a fixed and finite size.
 


Wait a minute, are you or are you not saying that the OP's original
example is impossible (due to recursion)?

Because "struct S{ S* next;}" is *not* an example of an impossible data
structure. It works perfectly fine because of the indirection
introduced by the pointer. The OP's original example is also perfectly
possible for the same reason reason as "struct S{ S* next;}".

There are two forms of recursion that can render a type impossible:

    // Recursive data layout:
    struct S
    {
        int i; // <-- Seed
        S s;   // <-- Kaboom!
    }

Or:

    // Recursive symbols (impossible in D, not sure about ML):
    alias S!int Foo; // <-- Light the fuse...
    struct S(T)
    {
        S!(typeof(this))* s;  // <-- Kaboom!
    }

Neither of those two "bad recursions" occur in the OP's original
example. It only has the perfectly benign "struct S{ S* next;}" form of
recursion. So the OP is using a perfectly legit, perfectly feasible
data structure. DMD just happens to mishandle it and then chokes.

So ok:

s/There *IS NO RECURSION* here./There is no _IMPOSSIBLE_ recursion here./



 Nov 08 2012



  parent reply Manfred Nowak <svv1999 hotmail.com>  writes:


Nick Sabalausky wrote:


 So ok:
 
 s/There *IS NO RECURSION* here./There is no _IMPOSSIBLE_ recursion
 here./ 


That's one correection only. Several more are to come.

Sorrily no one seems to have recognized this sentence in 
digitalmars.D.learn:40918:


 Because `R' can recurse infinitely over `Ancor' a mooring and a way 
 to that mooring is needed.


In regex-parlor this meens, that `( R!Ancor!)*' is the type the 
compiler should be able to handle according to the template definitions 
given.

But the compiler currently can only handle types with a finite length 
of description on instantiation. For me it is in doubt that this 
restriction can be declared as a bug.

-manfred



 Nov 09 2012



 next sibling parent reply "Rob T" <rob ucora.com>  writes:


On Friday, 9 November 2012 at 14:04:26 UTC, Manfred Nowak wrote:

 Nick Sabalausky wrote:


 So ok:
 
 s/There *IS NO RECURSION* here./There is no _IMPOSSIBLE_ 
 recursion
 here./


 That's one correection only. Several more are to come.

 Sorrily no one seems to have recognized this sentence in
 digitalmars.D.learn:40918:


 Because `R' can recurse infinitely over `Ancor' a mooring and 
 a way to that mooring is needed.


 In regex-parlor this meens, that `( R!Ancor!)*' is the type the
 compiler should be able to handle according to the template 
 definitions
 given.

 But the compiler currently can only handle types with a finite 
 length
 of description on instantiation. For me it is in doubt that this
 restriction can be declared as a bug.

 -manfred


I'm not sure if you commented on why the non-templated version 
compiled. Since it does compile as I expected it would, it means 
that the templates operate in another dimension from what I was 
expecting, i.e., there's two languages in D, one for templates 
and another for non-temnplate code. My understanding of D from 
what I read, was that templates are supposed to work in the same 
way as regular code. The (T) is only there to introduce a type, 
so that code can be reused over multiple types. What is happening 
however, is that the templates are not doing what would be 
expected if the type was introduced manually, and to me this is 
plain wrong, or at best very unfortunate for D.

--rt



 Nov 09 2012



  parent reply Manfred Nowak <svv1999 hotmail.com>  writes:


Rob T wrote:


 What is happening however, is that the templates are not doing
 what would be expected if the type was introduced manually


The expectations might be wrong.

With Templates one is able to introduce recursive definitions of types 
into the type system. As with recursive functions, the feedom, thereby 
generated, can introduce relaxation as well as strain.

-manfred



 Nov 09 2012



 next sibling parent reply Nick Sabalausky <SeeWebsiteToContactMe semitwist.com>  writes:


On Fri, 9 Nov 2012 20:57:42 +0000 (UTC)
Manfred Nowak <svv1999 hotmail.com> wrote:


 Rob T wrote:
 

 What is happening however, is that the templates are not doing
 what would be expected if the type was introduced manually


 
 The expectations might be wrong.
 
 With Templates one is able to introduce recursive definitions of
 types into the type system. As with recursive functions, the feedom,
 thereby generated, can introduce relaxation as well as strain.
 


One is indeed *able* to do that with templates, but the OP never
actually did so, so I really don't see the relevance.



 Nov 09 2012



  parent reply Manfred Nowak <svv1999 hotmail.com>  writes:


Nick Sabalausky wrote:


 I really don't see the relevance


Please look at the definition of R:
struct R
{
    int value;
    d_list!R Rlist;
}

If no recursion was wanted the OP should have written:
    d_list!(R*) Rlist;

In digitalmars.D.learn:40990 I already asked for an explanation.

-manfred



 Nov 10 2012



  parent reply Nick Sabalausky <SeeWebsiteToContactMe semitwist.com>  writes:


On Sat, 10 Nov 2012 10:33:39 +0000 (UTC)
Manfred Nowak <svv1999 hotmail.com> wrote:


 Nick Sabalausky wrote:
 

 I really don't see the relevance


 
 Please look at the definition of R:
 struct R
 {
     int value;
     d_list!R Rlist;
 }
 
 If no recursion was wanted the OP should have written:
     d_list!(R*) Rlist;
 


Ok, I see what you're saying, but you're mistaken: That line "d_list!R
Rlist;" is not a problematic recursion.

Imagine if d_list had been defined like this:

struct d_list(T)
{
    int i;
}

Then would this still be problematic recursion?:

struct R
{
    d_list!R Rlist;
}

No, because R is never actually used anywhere in that d_list (only
int is used). In this case, R is nothing more that part of the *name* of
a particular instantiation of the d_list template.

And indeed, just like the above example, the OP's definition of d_list
also does *not* use R:

struct d_list( T )
{
    node* head;
    node* tail;
}

Now, yes, that "node" type does use R (instead of R*), *but* "head"
and "tail" are merely pointers to "node", so it's ok.


 In digitalmars.D.learn:40990 I already asked for an explanation.
 


Actually, my newsreader is kinda shitty, and (AFAIK) doesn't give me
any way to lookup a message by ID, so I'm not really sure which message
you're referring to :/



 Nov 10 2012



  parent  Manfred Nowak <svv1999 hotmail.com>  writes:


Nick Sabalausky wrote:


 *but* "head" and "tail" are merely pointers to "node"


Thank you. I do recognize now, that my flow of thought stopped 
at the same point at which the flow of control of the compiler 
stopped.

-manfred



 Nov 11 2012



prev sibling  parent reply "Rob T" <rob ucora.com>  writes:


On Friday, 9 November 2012 at 20:57:42 UTC, Manfred Nowak wrote:

 Rob T wrote:


 What is happening however, is that the templates are not doing
 what would be expected if the type was introduced manually


 The expectations might be wrong.

 With Templates one is able to introduce recursive definitions 
 of types
 into the type system. As with recursive functions, the feedom, 
 thereby
 generated, can introduce relaxation as well as strain.

 -manfred


I agree that you can introduce recursive definitions into a 
template, and you have demonstrated that ability rather well, 
however the definitions in my template does not do this, and so 
far I have not seen a demonstration of how it could be doing so.

The type expansion is definitely finite, there's several posts 
following through with the expansion, and they all show that the 
compiler must stop expanding at the pointers. All of the pointers 
are of a known finite size (standard pointer type) and the type 
they represent for dereferencing is definitely knowable.

The problem appears to be with the compiler failing to evaluate 
all of the type definitions fully, and as a result it 
inappropriately fails with a "forwarded reference" error.

I've seen a somewhat related problem with functions that return 
"auto". If the body conatins something that needs to know the 
return value, the compiler may fail with a "forwarded reference" 
error. There's absolutely no valid reason why the compiler should 
be doing this, and it exposes a weakness in the way it does type 
evaluations (in at least that case). On the other hand, I've seen 
the compiler do very good work evaluating out-of-order type 
definitions that are all over the place.

If I'm to take the D specification (what little of it there is) 
at face value, out-of-order type definitions are always perfectly 
legal provided that they are legal definitions of course, so when 
the compiler fails on them, then it's a bug that needs to be 
fixed.

--rt



 Nov 09 2012



  parent reply "Rob T" <rob ucora.com>  writes:


If anyone is interested, here's my current work-a-round ...

// original code that fails ...

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;
}

// modified code that works ...

// no changes made
struct R
{
    int value;
    d_list!R Rlist;
}

// definition moved out of d_list
struct node( T )
{
    T payload;
    node* pred;
    node* succ;
}

// Added default type N = node!(T)
struct d_list( T, N = node!(T) )
{
    N* head;
    N* tail;
}

Thanks again for all your help!

--rt



 Nov 09 2012



  parent reply Nick Sabalausky <SeeWebsiteToContactMe semitwist.com>  writes:


On Sat, 10 Nov 2012 06:29:02 +0100
"Rob T" <rob ucora.com> wrote:


 If anyone is interested, here's my current work-a-round ...
 
 // original code that fails ...
 


[...]

 
 // modified code that works ...
 


[...]

 
 Thanks again for all your help!
 


I've gone ahead and filed a minimized test case, and also included your
workaround:
http://d.puremagic.com/issues/show_bug.cgi?id=8990

I didn't make that one struct nested since that's not needed to
reproduce the error.



 Nov 09 2012



  parent reply "Rob T" <rob ucora.com>  writes:


On Saturday, 10 November 2012 at 06:09:41 UTC, Nick Sabalausky 
wrote:

 I've gone ahead and filed a minimized test case, and also 
 included your
 workaround:
 http://d.puremagic.com/issues/show_bug.cgi?id=8990

 I didn't make that one struct nested since that's not needed to
 reproduce the error.


Thanks for filing it.

Looking at the bug reports, there's 2000+ unresolved? Yikes.

--rt



 Nov 09 2012



  parent reply Don Clugston <dac nospam.com>  writes:


On 10/11/12 08:53, Rob T wrote:

 On Saturday, 10 November 2012 at 06:09:41 UTC, Nick Sabalausky wrote:

 I've gone ahead and filed a minimized test case, and also included your
 workaround:
 http://d.puremagic.com/issues/show_bug.cgi?id=8990

 I didn't make that one struct nested since that's not needed to
 reproduce the error.


 Thanks for filing it.

 Looking at the bug reports, there's 2000+ unresolved? Yikes.

 --rt


Yeah. Though note that 1000 bug reports are from bearophile.



 Nov 12 2012



 next sibling parent  1100110 <0b1100110 gmail.com>  writes:


 Yeah. Though note that 1000 bug reports are from bearophile.


Well, at least he's persistent.

-- 
Using Opera's revolutionary email client: http://www.opera.com/mail/



 Nov 12 2012



prev sibling next sibling parent  Andrej Mitrovic <andrej.mitrovich gmail.com>  writes:


On 11/12/12, Don Clugston <dac nospam.com> wrote:

 Yeah. Though note that 1000 bug reports are from bearophile.


Actually only around 300 remain open:
http://d.puremagic.com/issues/buglist.cgi?query_format=3Dadvanced&emailrepo=
rter2=3D1&emailtype2=3Dsubstring&order=3DImportance&bug_status=3DUNCONFIRME=
D&bug_status=3DNEW&bug_status=3DASSIGNED&bug_status=3DREOPENED&bug_status=
=3DVERIFIED&email2=3Dbearophile&component=3DDMD&product=3DD



 Nov 12 2012



prev sibling  parent reply Andrej Mitrovic <andrej.mitrovich gmail.com>  writes:


On 11/12/12, Andrej Mitrovic <andrej.mitrovich gmail.com> wrote:

 On 11/12/12, Don Clugston <dac nospam.com> wrote:

 Yeah. Though note that 1000 bug reports are from bearophile.


 Actually only around 300 remain open:
 http://d.puremagic.com/issues/buglist.cgi?query_format=advanced&emailreporter2=1&emailtype2=substring&order=Importance&bug_status=UNCONFIRMED&bug_status=NEW&bug_status=ASSIGNED&bug_status=REOPENED&bug_status=VERIFIED&email2=bearophile


Oh wait, that's only for DMD. It's 559 in total:
http://d.puremagic.com/issues/buglist.cgi?query_format=advanced&emailreporter2=1&emailtype2=substring&order=Importance&bug_status=UNCONFIRMED&bug_status=NEW&bug_status=ASSIGNED&bug_status=REOPENED&bug_status=VERIFIED&email2=bearophile



 Nov 12 2012



 next sibling parent reply "Rob T" <rob ucora.com>  writes:


On Monday, 12 November 2012 at 14:28:53 UTC, Andrej Mitrovic 
wrote:

 On 11/12/12, Andrej Mitrovic <andrej.mitrovich gmail.com> wrote:

 On 11/12/12, Don Clugston <dac nospam.com> wrote:

 Yeah. Though note that 1000 bug reports are from bearophile.


 Actually only around 300 remain open:
 http://d.puremagic.com/issues/buglist.cgi?query_format=advanced&emailreporter2=1&emailtype2=substring&order=Importance&bug_status=UNCONFIRMED&bug_status=NEW&bug_status=ASSIGNED&bug_status=REOPENED&bug_status=VERIFIED&email2=bearophile


 Oh wait, that's only for DMD. It's 559 in total:
 http://d.puremagic.com/issues/buglist.cgi?query_format=advanced&emailreporter2=1&emailtype2=substring&order=Importance&bug_status=UNCONFIRMED&bug_status=NEW&bug_status=ASSIGNED&bug_status=REOPENED&bug_status=VERIFIED&email2=bearophile


Issue 8990 and 6969, both related to this thread and unresolved, 
are not in the list, so I suspect there's a lot more missing too.

PS: I could not figure out how to make a useful report using that 
bug report tool either.

--rt



 Nov 12 2012



 next sibling parent  Andrej Mitrovic <andrej.mitrovich gmail.com>  writes:


On 11/13/12, Rob T <rob ucora.com> wrote:

 PS: I could not figure out how to make a useful report using that
 bug report tool either.


You will need to register, and then use this page:
http://d.puremagic.com/issues/enter_bug.cgi?product=D

Then select a component (usually DMD, druntime, or Phobos). D2 is
selected by default, all that's left is to write a summary and
description. You can also click on "Show Advanced Fields" (top left),
and in the Keywords field (way down) you can add things like
accepts-invalid, or rejects-valid. The list of keywords is here:
http://d.puremagic.com/issues/describekeywords.cgi



 Nov 12 2012



prev sibling  parent reply Don Clugston <dac nospam.com>  writes:


On 13/11/12 06:51, Rob T wrote:

 On Monday, 12 November 2012 at 14:28:53 UTC, Andrej Mitrovic wrote:

 On 11/12/12, Andrej Mitrovic <andrej.mitrovich gmail.com> wrote:

 On 11/12/12, Don Clugston <dac nospam.com> wrote:

 Yeah. Though note that 1000 bug reports are from bearophile.


 Actually only around 300 remain open:
 http://d.puremagic.com/issues/buglist.cgi?query_format=advanced&emailreporter2=1&emailtype2=substring&order=Importance&bug_status=UNCONFIRMED&bug_status=NEW&bug_status=ASSIGNED&bug_status=REOPENED&bug_status=VERIFIED&email2=bearophile


 Oh wait, that's only for DMD. It's 559 in total:
 http://d.puremagic.com/issues/buglist.cgi?query_format=advanced&emailreporter2=1&emailtype2=substring&order=Importance&bug_status=UNCONFIRMED&bug_status=NEW&bug_status=ASSIGNED&bug_status=REOPENED&bug_status=VERIFIED&email2=bearophile


 Issue 8990 and 6969, both related to this thread and unresolved, are not
 in the list, so I suspect there's a lot more missing too.

 PS: I could not figure out how to make a useful report using that bug
 report tool either.

 --rt


I recommend deskzilla lite. D is on its list of supported open-source 
projects. It maintains a local copy of the entire bugzilla database, so 
you're not restricted to the slow and horrible html interface.



 Nov 13 2012



 next sibling parent  Andrej Mitrovic <andrej.mitrovich gmail.com>  writes:


On 11/13/12, Don Clugston <dac nospam.com> wrote:

 I recommend deskzilla lite. D is on its list of supported open-source
 projects. It maintains a local copy of the entire bugzilla database, so
 you're not restricted to the slow and horrible html interface.


Wow, I had no idea they had this. I've added a note about it here:
http://prowiki.org/wiki4d/wiki.cgi?D__Tutorial/BugReports Thanks!



 Nov 13 2012



prev sibling  parent reply Nick Sabalausky <SeeWebsiteToContactMe semitwist.com>  writes:


On Tue, 13 Nov 2012 11:56:57 +0100
Don Clugston <dac nospam.com> wrote:

 I recommend deskzilla lite. D is on its list of supported open-source 
 projects. It maintains a local copy of the entire bugzilla database,
 so you're not restricted to the slow and horrible html interface.
 


Awesome! I wish GitHub had something like that. (Hell, I wish every web
"app" had something like that.)

Although, $189 for anything with > 2k issues or anything non-OSS? Geez
that's expensive, what are they, Adobe?



 Nov 13 2012



  parent  Nick Sabalausky <SeeWebsiteToContactMe semitwist.com>  writes:


On Tue, 13 Nov 2012 11:19:36 -0500
Nick Sabalausky <SeeWebsiteToContactMe semitwist.com> wrote:


 On Tue, 13 Nov 2012 11:56:57 +0100
 Don Clugston <dac nospam.com> wrote:

 I recommend deskzilla lite. D is on its list of supported
 open-source projects. It maintains a local copy of the entire
 bugzilla database, so you're not restricted to the slow and
 horrible html interface.
 


 
 Awesome! I wish GitHub had something like that. (Hell, I wish every
 web "app" had something like that.)
 
 Although, $189 for anything with > 2k issues or anything non-OSS? Geez
 that's expensive, what are they, Adobe?
 


Oh, upon using it, it looks like the free version is for OSS projects
with any number of issues *and* non-OSS projects with <= 2k issues.
Guess I misread their download page.



 Nov 13 2012



prev sibling  parent  "Rob T" <rob ucora.com>  writes:


On Monday, 12 November 2012 at 14:28:53 UTC, Andrej Mitrovic 
wrote:

 On 11/12/12, Andrej Mitrovic <andrej.mitrovich gmail.com> wrote:

 On 11/12/12, Don Clugston <dac nospam.com> wrote:

 Yeah. Though note that 1000 bug reports are from bearophile.


 Actually only around 300 remain open:
 http://d.puremagic.com/issues/buglist.cgi?query_format=advanced&emailreporter2=1&emailtype2=substring&order=Importance&bug_status=UNCONFIRMED&bug_status=NEW&bug_status=ASSIGNED&bug_status=REOPENED&bug_status=VERIFIED&email2=bearophile


 Oh wait, that's only for DMD. It's 559 in total:
 http://d.puremagic.com/issues/buglist.cgi?query_format=advanced&emailreporter2=1&emailtype2=substring&order=Importance&bug_status=UNCONFIRMED&bug_status=NEW&bug_status=ASSIGNED&bug_status=REOPENED&bug_status=VERIFIED&email2=bearophile


NM, you were talking about bugs reported by bearophile. Back to 
sleep ...

--rt



 Nov 12 2012



prev sibling  parent reply Nick Sabalausky <SeeWebsiteToContactMe semitwist.com>  writes:


On Fri, 9 Nov 2012 14:04:26 +0000 (UTC)
Manfred Nowak <svv1999 hotmail.com> wrote:

 
 Sorrily no one seems to have recognized this sentence in 
 digitalmars.D.learn:40918:
 

 Because `R' can recurse infinitely over `Ancor' a mooring and a way 
 to that mooring is needed.


 
 In regex-parlor this meens, that `( R!Ancor!)*' is the type the 
 compiler should be able to handle according to the template
 definitions given.
 
 But the compiler currently can only handle types with a finite length 
 of description on instantiation. For me it is in doubt that this 
 restriction can be declared as a bug.
 


But all of the OP's types *do* have a finite length of description.

I do understand what you are trying to doing with the mooring (although
I admit I wasn't familiar with the word "mooring" until this
discussion), and I definitely understand what that technique is used
for. But it's not relevant to the OP's example, as he's not trying to
do anything that for which that "mooring" is actually needed.

Note that the following structs do NOT require "mooring" and *already*
work perfectly fine with DMD:

struct S1 { S1* s; }

struct S2(T) { S2!(T)* s; }

Those work perfectly fine, even once you actually instantiate S2. The
OP's example follows the same pattern as those.

If, OTOH, there had been something like this:

struct S3(T) { S3!(S3)* s; }

Then *that* would require the mooring you described. But the OP was
never trying to do anything like that.



 Nov 09 2012



  parent  Manfred Nowak <svv1999 hotmail.com>  writes:


Nick Sabalausky wrote:


 But the OP was never trying to do anything like that.


See digitalmars.D.learn:40991

-manfred



 Nov 10 2012



prev sibling  parent reply "Rob T" <rob ucora.com>  writes:


There is clearly no recursion in the struct, it terminates at the 
pointers, therefore it is of finite and knowable size during 
compile time.

R looks like this if value is int

dlist!R = struct{ struct*, struct* }
R = struct{ int, struct{ struct*, struct* } }
node!R = struct{ struct{ int, struct{ struct*, struct* } }, 
struct*, struct* }

The the structs are now fully defined.

I will argue that there's actually no recursion in the definition 
when the definition is looked at from the POV of what the 
compiler should be seeing.

struct R =
{
    int = int; // STOP
    d_list!R =
    { node!(R)* = pointer; // STOP
      node!(R)* = pointer; // STOP
    } // STOP d_list is now 100% defined

We still need to know what node!R is in order to dereference the 
node!(R)* pointers inside d_list.

struct node!(R) =
{
   R = R; // STOP, R is fully defined already.
   node* = pointer; // STOP
   node* = pointer; // STOP
} // STOP node!(R) is 100% defined.

We now know the size and contents of R, d_list!R, and node!R, and 
we have all the information required to dereference the pointers 
properly.

How is the recursion in the definition stoping the compiler from 
doing its job?

Finally, take note that this altenate recursive definition 
compiles and works as expected:

struct node( P )
{
    P payload;
    node* pred;
    node* succ;
}

struct R( V )
{
    V value;
    alias node!R N;
    d_list!N Rlist;
}

struct d_list( N )
{
    N* head;
    N* tail;
    // even this works
    ref typeof(N.payload) getFirstValue(){
       return head.payload;
    }
}

The above template definitions define exactly the same structure 
as the original, it's just done in a different way, by supplying 
the entire node definition to the d_list instead of just the 
payload type.

Why should this version work and not the other?

--rt



 Nov 08 2012



  parent reply Manfred Nowak <svv1999 hotmail.com>  writes:


Rob T wrote:


 The above template definitions define exactly the same structure 
 as the original


No, they implement not _exactly_ the same structure, because they 
supply more freedom than the original templates version. The original 
version forced a recursion onto every implementation, whereas this new 
templates version allows non-recursive implementations.

It might be helpfull to reintroduce the forced recursion using the new 
template definitions.

Hint:
start with
| alias d_list!node00 d_list00;
| d_list00 var;
and publish whether it is possible to compile this line:
| alias R!d_list00 R0; 

-manfred



 Nov 09 2012



  parent reply Timon Gehr <timon.gehr gmx.ch>  writes:


On 11/09/2012 02:17 PM, Manfred Nowak wrote:

 Rob T wrote:


 The above template definitions define exactly the same structure
 as the original


 No, they implement not _exactly_ the same structure, because they
 supply more freedom than the original templates version. The original
 version forced a recursion onto every implementation, whereas this new
 templates version allows non-recursive implementations.

 It might be helpfull to reintroduce the forced recursion using the new
 template definitions.

 Hint:
 start with
 | alias d_list!node00 d_list00;
 | d_list00 var;
 and publish whether it is possible to compile this line:
 | alias R!d_list00 R0;

 -manfred


The example definitely exposes a bug in DMD.
The D front end I am developing can already handle it.



 Nov 09 2012



 next sibling parent reply Philippe Sigaud <philippe.sigaud gmail.com>  writes:


Timon:


 The D front end I am developing can already handle it.


Developed in D, I suppose?



 Nov 09 2012



  parent reply Timon Gehr <timon.gehr gmx.ch>  writes:


On 11/09/2012 10:24 PM, Philippe Sigaud wrote:

 Timon:

     The D front end I am developing can already handle it.


 Developed in D, I suppose?


Yes.



 Nov 09 2012



  parent  Artur Skawina <art.08.09 gmail.com>  writes:


On 11/09/12 23:45, Timon Gehr wrote:

 On 11/09/2012 10:24 PM, Philippe Sigaud wrote:

 Timon:

     The D front end I am developing can already handle it.


 Developed in D, I suppose?


 
 Yes.


Public? License? URL?

artur



 Nov 10 2012



prev sibling  parent reply Manfred Nowak <svv1999 hotmail.com>  writes:


Timon Gehr wrote:


 The example definitely exposes a bug in DMD.
 The D front end I am developing can already handle it.


May I guess, that your front end is also able to handle this code:

struct Elem( size_t myNumber) {
  Elem!( myNumber +1)* next;
}
void main(){
  Elem!0 list;
  list.next= new Elem!1;
}

-manfred



 Nov 09 2012



 next sibling parent reply Timon Gehr <timon.gehr gmx.ch>  writes:


On 11/09/2012 10:32 PM, Manfred Nowak wrote:

 Timon Gehr wrote:


 The example definitely exposes a bug in DMD.
 The D front end I am developing can already handle it.


 May I guess, that your front end is also able to handle this code:

 struct Elem( size_t myNumber) {
    Elem!( myNumber +1)* next;
 }
 void main(){
    Elem!0 list;
    list.next= new Elem!1;
 }

 -manfred


In theory yes, but it takes a long time and uses a lot of memory, 
especially on a 64 bit build. This is a very different example from the 
OT's though.



 Nov 09 2012



  parent reply Manfred Nowak <svv1999 hotmail.com>  writes:


Timon Gehr wrote:


 In theory yes, but


[...]

What a pity. Because in the code given only the types Elem!0 and Elem!1 
must be indeed initialized.

The fact, that the specification of the template describes a family of 
types with an infinite number of members should not force the front end 
to check wether all those members are initializable.

If the executable is not allowed to build new types, which seems to be 
canonically, it is sufficient for the front end to check the 
initializability of those members, for which an initialization is 
imperative.

This polishes my claim in digitalmars.D.learn:40939. For me now it 
appears as a bug, when the front end assumes, that the executable is 
allowed to build new types.

-manfred
  



 Nov 10 2012



  parent reply Timon Gehr <timon.gehr gmx.ch>  writes:


On 11/10/2012 10:12 AM, Manfred Nowak wrote:

 Timon Gehr wrote:


 In theory yes, but


 [...]

 What a pity. Because in the code given only the types Elem!0 and Elem!1
 must be indeed initialized.
 ...


In this specific case, yes. But as this is an undecidable property in 
general, detecting and exploiting it would merely be an optimization 
that cannot generally be relied upon. Depending on how powerful it is, 
it would slow down analysis most of the time. Furthermore, I do not see 
use cases. I'll look into it when the front end is finished though.



 Nov 10 2012



  parent  Manfred Nowak <svv1999 hotmail.com>  writes:


Timon Gehr wrote:


 But as this is an undecidable property in general


I do not see, that the compiler has to solve the general case---
at least when compiling monolithic code and the executable is 
only allowed to use types which are initialized at compile time.

Upon using several modules the modules might follow some 
restrictions and I am currently not able to specify that 
restrictions.

-manfred   



 Nov 10 2012



prev sibling  parent reply "Rob T" <rob ucora.com>  writes:


On Friday, 9 November 2012 at 21:32:01 UTC, Manfred Nowak wrote:

 Timon Gehr wrote:


 The example definitely exposes a bug in DMD.
 The D front end I am developing can already handle it.


 May I guess, that your front end is also able to handle this 
 code:

 struct Elem( size_t myNumber) {
   Elem!( myNumber +1)* next;
 }
 void main(){
   Elem!0 list;
   list.next= new Elem!1;
 }

 -manfred


With the unmodified template as posted, I get a very specific 
error about "recusive expansion", but I can see why using that 
form of template - it will expand into multiple types forever 
Elem!(0), Elem!(1), Elem!(2) ... Elem!(infinity).

Now take note that with the modified code below, it works fine, 
and exactly as I would expect:

struct Elem(T) {
  Elem* next;
}

My attempt to mess up the compiler did not succeed, the code 
below still compiles as expected.

struct Elem(T) {
  Elem!(T)* next;
}


If it works above, then it should also work with the code I 
introduced in the OP because it's the exact same scenario, only 
much more simplified. The type expansion should stop at the 
pointers, and the error message indicates that it does (there's 
no recursive expansion message), but it fails to evaluate all the 
types correctly (forwarded reference message).

I think this example clears the matter up nicely, and the problem 
I'm experiencing is definitely a compiler bug. I'd like to see 
this problem resolved, so I'll file a bug report.

BTW, thanks for all the attention to this matter, I've learned a 
lot more about D templates, such as the recusivness of templates 
demonstrated by manfred, and the dialogue in here helped me to 
find a reasonable work-a-round for my particular application.

--rt



 Nov 09 2012



  parent  Manfred Nowak <svv1999 hotmail.com>  writes:


Rob T wrote:


 and the problem I'm experiencing is definitely a compiler bug


I do not see that. Please work on my messages digitalmars.D.learn:40990
and digitalmars.D.learn:40991.

-manfred



 Nov 10 2012



prev sibling  parent reply Nick Sabalausky <SeeWebsiteToContactMe semitwist.com>  writes:


On Thu, 08 Nov 2012 19:19:52 +0400
Dmitry Olshansky <dmitry.olsh gmail.com> wrote:


 11/8/2012 10:39 AM, Rob T =D0=BF=D0=B8=D1=88=D0=B5=D1=82:

 I want to create a simple recursive data structure as follows:

 struct R
 {
     int value;
     d_list!R Rlist;
 }


=20
 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.
=20


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
=3D=3D 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.



 To break this chain make node a separate templated struct outside of=20
 d_list. Then peeking inside of d_list compiler shouldn't go crazy.
=20


No, I tried that, and it still fails. This is definitely a compiler bug.



 Nov 08 2012



  parent reply Dmitry Olshansky <dmitry.olsh gmail.com>  writes:


11/9/2012 12:35 AM, Nick Sabalausky пишет:

 On Thu, 08 Nov 2012 19:19:52 +0400
 Dmitry Olshansky <dmitry.olsh 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



 Nov 08 2012



  parent reply Nick Sabalausky <SeeWebsiteToContactMe semitwist.com>  writes:


On Fri, 09 Nov 2012 01:26:44 +0400
Dmitry Olshansky <dmitry.olsh gmail.com> wrote:

 
 Just coming up with an idea how it may fail, not arguing for it being 
 correct ;)


Right. Point is, it's a compiler bug.



 Nov 08 2012



  parent  "Rob T" <rob ucora.com>  writes:


On Thursday, 8 November 2012 at 21:50:02 UTC, Nick Sabalausky 
wrote:

 On Fri, 09 Nov 2012 01:26:44 +0400
 Dmitry Olshansky <dmitry.olsh gmail.com> wrote:

 
 Just coming up with an idea how it may fail, not arguing for 
 it being correct ;)


 Right. Point is, it's a compiler bug.


For D, as opposed to C/C++, my understanding was that specifying 
forward references to deal with out-of-order difinitions, or 
situations like the one I'm experiencing, was not required, so I 
have to agree it's a "bug" rather than just a limitation of the 
language and compiler. There's no reason why the compiler should 
fail in either case, other than due to a less-than-adequate 
method of evaluating the different structs.

--rt



 Nov 08 2012



prev sibling  parent  Manfred Nowak <svv1999 hotmail.com>  writes:


Rob T wrote:


 I want to create a simple recursive data structure as follows:
 
 struct R
 {
     int value;
     d_list!R Rlist;
 }


I do not see any usage for the member `d_list!R Rlist'.

Please explain.

-manfred



 Nov 10 2012