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 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
prev sibling next 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 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
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 equvalent 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 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 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 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 next sibling parent 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
prev sibling 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:
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 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 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 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 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
parent 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
prev sibling 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 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
prev sibling next sibling parent "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
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--20cf3074b298e59cfc04cdff8f51
Content-Type: text/plain; charset=UTF-8

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.

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.


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

--20cf3074b298e59cfc04cdff8f51 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Rob, your original code:<div><br></div><div><span style=3D"color:rgb(80,0,8= 0);font-family:arial,sans-serif;font-size:12.666666984558105px">// d-linked= list with templated payload</span><br style=3D"color:rgb(80,0,80);font-fam= ily:arial,sans-serif;font-size:12.666666984558105px"> <span style=3D"color:rgb(80,0,80);font-family:arial,sans-serif;font-size:12= .666666984558105px">struct d_list( T )</span><br style=3D"color:rgb(80,0,80= );font-family:arial,sans-serif;font-size:12.666666984558105px"><span style= =3D"color:rgb(80,0,80);font-family:arial,sans-serif;font-size:12.6666669845= 58105px">{</span><br style=3D"color:rgb(80,0,80);font-family:arial,sans-ser= if;font-size:12.666666984558105px"> <span style=3D"color:rgb(80,0,80);font-family:arial,sans-serif;font-size:12= .666666984558105px">=C2=A0 =C2=A0 struct node</span><br style=3D"color:rgb(= 80,0,80);font-family:arial,sans-serif;font-size:12.666666984558105px"><span= style=3D"color:rgb(80,0,80);font-family:arial,sans-serif;font-size:12.6666= 66984558105px">=C2=A0 =C2=A0 {</span><br style=3D"color:rgb(80,0,80);font-f= amily:arial,sans-serif;font-size:12.666666984558105px"> <span style=3D"color:rgb(80,0,80);font-family:arial,sans-serif;font-size:12= .666666984558105px">=C2=A0 =C2=A0 =C2=A0 =C2=A0T payload;</span><br style= =3D"color:rgb(80,0,80);font-family:arial,sans-serif;font-size:12.6666669845= 58105px"><span style=3D"color:rgb(80,0,80);font-family:arial,sans-serif;fon= t-size:12.666666984558105px">=C2=A0 =C2=A0 =C2=A0 =C2=A0node* pred;</span><= br style=3D"color:rgb(80,0,80);font-family:arial,sans-serif;font-size:12.66= 6666984558105px"> <span style=3D"color:rgb(80,0,80);font-family:arial,sans-serif;font-size:12= .666666984558105px">=C2=A0 =C2=A0 =C2=A0 =C2=A0node* succ;</span><br style= =3D"color:rgb(80,0,80);font-family:arial,sans-serif;font-size:12.6666669845= 58105px"><span style=3D"color:rgb(80,0,80);font-family:arial,sans-serif;fon= t-size:12.666666984558105px">=C2=A0 =C2=A0 }</span><br style=3D"color:rgb(8= 0,0,80);font-family:arial,sans-serif;font-size:12.666666984558105px"> <span style=3D"color:rgb(80,0,80);font-family:arial,sans-serif;font-size:12= .666666984558105px">=C2=A0 =C2=A0 node* head;</span><br style=3D"color:rgb(= 80,0,80);font-family:arial,sans-serif;font-size:12.666666984558105px"><span= style=3D"color:rgb(80,0,80);font-family:arial,sans-serif;font-size:12.6666= 66984558105px">=C2=A0 =C2=A0 node* tail;</span><br style=3D"color:rgb(80,0,= 80);font-family:arial,sans-serif;font-size:12.666666984558105px"> <span style=3D"color:rgb(80,0,80);font-family:arial,sans-serif;font-size:12= .666666984558105px">}</span><br></div><div><span style=3D"color:rgb(80,0,80= );font-family:arial,sans-serif;font-size:12.666666984558105px"><br></span><= /div> <div><span style=3D"color:rgb(80,0,80);font-family:arial,sans-serif;font-si= ze:12.666666984558105px">compiles just fine for me (Linux 32bits, DMD 2.060= ).</span></div><div><span style=3D"color:rgb(80,0,80);font-family:arial,san= s-serif;font-size:12.666666984558105px"><br> </span></div><div><span style=3D"color:rgb(80,0,80);font-family:arial,sans-= serif;font-size:12.666666984558105px">Even with some exercising, the templa= te doesn&#39;t fail:</span></div><div><span style=3D"color:rgb(80,0,80);fon= t-family:arial,sans-serif;font-size:12.666666984558105px"><br> </span></div><div><span style=3D"color:rgb(80,0,80);font-family:arial,sans-= serif;font-size:12.666666984558105px">void main()</span></div><div><span st= yle=3D"color:rgb(80,0,80);font-family:arial,sans-serif;font-size:12.6666669= 84558105px">{</span></div> <div><span style=3D"color:rgb(80,0,80);font-family:arial,sans-serif;font-si= ze:12.666666984558105px">=C2=A0 =C2=A0 auto list =3D d_list!(int)();</span>= </div><div><span style=3D"color:rgb(80,0,80);font-family:arial,sans-serif;f= ont-size:12.666666984558105px">}</span></div> <div class=3D"gmail_extra"><br><br><div class=3D"gmail_quote">On Thu, Nov 8= , 2012 at 6:49 PM, Rob T <span dir=3D"ltr">&lt;<a href=3D"mailto:rob ucora.= com" target=3D"_blank">rob ucora.com</a>&gt;</span> wrote:<br><blockquote c= lass=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;= padding-left:1ex"> <div class=3D"im">On Thursday, 8 November 2012 at 15:19:56 UTC, Dmitry Olsh= ansky wrote:<br> <blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p= x #ccc solid;padding-left:1ex"> <br> Naturally C++ doesn&#39;t have nested struct definitions.<br> <br> </blockquote> <br></div> I don&#39;t have a nested struct, the struct definition defines the type on= ly, and the nodes are allocated as pointers from a new operation when the l= ist 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 b= e a struct just fine.<div class=3D"im"> <br> <br> <blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p= x #ccc solid;padding-left:1ex"><blockquote class=3D"gmail_quote" style=3D"m= argin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> I also want to template the recursive structure itself to specify the<br> value type, ie struct R(T){ T value; d_list!R Rlist; }, but I left that<br> out to keep the example more simple.<br> <br> </blockquote> <br> <blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p= x #ccc solid;padding-left:1ex"> I&#39;ve been stuck on this problem all day, so any help is appreciated!<br=

<br> See if it helps.<br> </blockquote> <br></div> 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.<br> <br> The solution so far is to do it the C++ way, using pointers, which sucks.<b= r> <br> 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.<br> <br> I&#39;ll wait a bit longer for more comments before filing a bug report.<sp= an class=3D"HOEnZb"><font color=3D"#888888"><br> <br> --rt<br> <br> <br> </font></span></blockquote></div><br></div> --20cf3074b298e59cfc04cdff8f51--
Nov 08 2012
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling 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 next sibling parent 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;
 }

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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent 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
prev sibling next sibling parent 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
prev sibling next sibling 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 next sibling 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 next sibling parent "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
prev sibling next sibling parent 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
prev sibling next sibling parent 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
prev sibling next 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 next sibling 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 next sibling parent 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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--001636eefacf726c1304ce169312
Content-Type: text/plain; charset=UTF-8

Timon:

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

Developed in D, I suppose? --001636eefacf726c1304ce169312 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable <br><div class=3D"gmail_extra">Timon:<br><div class=3D"gmail_quote"><blockq= uote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc = solid;padding-left:1ex"> The D front end I am developing can already handle it.<br></blockquote><div=
<br></div><div>Developed in D, I suppose?=C2=A0</div></div><br></div>

--001636eefacf726c1304ce169312--
Nov 09 2012
prev sibling next sibling parent "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
prev sibling next sibling parent 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
prev sibling next sibling parent "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
prev sibling next sibling parent 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
prev sibling next sibling parent "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
prev sibling next sibling parent 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
prev sibling next sibling parent "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
prev sibling next 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
prev sibling next sibling parent 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
prev sibling 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 next sibling parent 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
prev sibling next 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

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
prev sibling next 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 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 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 next sibling parent 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
prev sibling 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