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.

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

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

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).

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

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

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

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

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./

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