View mode: basic / threaded / horizontal-split · Log in · Help
September 11, 2006
Mixin layers and cyclic dependencies
I wrote the following as a quick test if an idea. The idea in itself
worked out fine, but I hit a problem I wasn't expecting. The problem
is that the code tries to set up a cyclic dependency through
templates...

template t_ML_Init (alias FINAL, int p_Leaf_Max, int p_Branch_Max)
{
 alias FINAL  m_Final;

 const int m_Leaf_Max   = p_Leaf_Max;
 const int m_Branch_Max = p_Branch_Max;
 
 struct c_Common_Head
 {
   int m_Size;
   int m_Height;
 }

 struct c_Leaf_Item
 {
 }

 struct c_Branch_Item
 {
   void*  m_Child;
 }

 typedef m_Final.c_Leaf_Item  [m_Leaf_Max  ]  c_Leaf_Items;
 typedef m_Final.c_Branch_Item[m_Branch_Max]  c_Branch_Items;

 struct c_Leaf
 {
   m_Final.c_Common_Head            m_Head;
   m_Final.c_Leaf_Item[m_Leaf_Max]  m_Items;
 }

 struct c_Branch
 {
   m_Final.c_Common_Head               m_Head;
   m_Final.c_Branch_Item[m_Branch_Max] m_Items;
 }
 
 int* Size (m_Final.c_Leaf* p)
 {
   return &((cast(c_Common_Head*) p).m_Size);
 }

 int* Size (m_Final.c_Branch* p)
 {
   return &((cast(c_Common_Head*) p).m_Size);
 }

 int* Height (m_Final.c_Leaf* p)
 {
   return &((cast(c_Common_Head*) p).m_Height);
 }

 int* Height (m_Final.c_Branch* p)
 {
   return &((cast(c_Common_Head*) p).m_Height);
 }
 
 c_Leaf_Items* Items (m_Final.c_Leaf* p)
 {
   return &((cast(c_Leaf*) p).m_Items);
 }

 c_Branch_Items* Items (m_Final.c_Branch* p)
 {
   return &((cast(c_Branch*) p).m_Items);
 }

 void** Child (m_Final.c_Branch_Item* p)
 {
   return &((cast(c_Branch_Item*) p).m_Child);
 }
}

template t_ML_Keys (alias PL, c_Key)
{
 mixin PL;
 
 struct c_Leaf_Item
 {
   PL.c_Leaf_Item  m_Previous;
   c_Key           m_Key;
 }

 struct c_Branch_Item
 {
   PL.c_Branch_Item  m_Previous;
   c_Key             m_Key;
 }

 c_Key* Key (m_Final.c_Leaf_Item* p)
 {
   return &((cast(c_Leaf_Item*) p).m_Key);
 }

 c_Key* Key (m_Final.c_Branch_Item* p)
 {
   return &((cast(c_Branch_Item*) p).m_Key);
 }
}

template t_ML_Data (alias PL, c_Data)
{
 mixin PL;
 
 struct c_Leaf_Item
 {
   PL.c_Leaf_Item  m_Previous;
   c_Data          m_Data;
 }

 c_Data* Data (m_Final.c_Leaf_Item* p)
 {
   return &((cast(c_Leaf_Item*) p).m_Data);
 }
}

//  Shorthand form
template t_ML_Keys_Data(alias PL, c_Key, c_Data)
{
 mixin t_ML_Keys!(t_ML_Data!(PL,c_Data),c_Key);
}

void main (char[][] args)
{
 alias t_ML_Keys_Data!(t_ML_Init!(ti_Test, 4, 4),int,int) ti_Test;
}


I get the error "alias ti_Test recursive alias declaration" - clearly
the cyclic dependency isn't liked.

I also tried to use the C++ form of mix-in layers, using an outer
class as a container for definitions. That didn't work either. It
didn't complain about the cyclic dependency, but it couldn't resolve
it either. Kept complaining about definitions being missing from
FINAL.

Funny how you can get used to an idea, and forget what the compiler is
having to do to handle it. I've been just working on the assumption
that I could do these things in D.

The cyclic dependency thing isn't a fundamental feature of mix-in
layers, and I don't actually need it despite the concept-testing code
above - there are other ways using 'static if' - but I just wanted to
ask if this no-cyclic-dependencies rule is permanent or whether it
might be changed in the future.

-- 
Remove 'wants' and 'nospam' from e-mail.
September 12, 2006
Re: Mixin layers and cyclic dependencies
Steve Horne wrote:
> I wrote the following as a quick test if an idea. The idea in itself
> worked out fine, but I hit a problem I wasn't expecting. The problem
> is that the code tries to set up a cyclic dependency through
> templates...
> 
> template t_ML_Init (alias FINAL, int p_Leaf_Max, int p_Branch_Max)
> {
>   alias FINAL  m_Final;
> 
>   const int m_Leaf_Max   = p_Leaf_Max;
>   const int m_Branch_Max = p_Branch_Max;
>   
>   struct c_Common_Head
>   {
>     int m_Size;
>     int m_Height;
>   }
> 
>   struct c_Leaf_Item
>   {
>   }
> 
>   struct c_Branch_Item
>   {
>     void*  m_Child;
>   }
> 
>   typedef m_Final.c_Leaf_Item  [m_Leaf_Max  ]  c_Leaf_Items;
>   typedef m_Final.c_Branch_Item[m_Branch_Max]  c_Branch_Items;
> 
>   struct c_Leaf
>   {
>     m_Final.c_Common_Head            m_Head;
>     m_Final.c_Leaf_Item[m_Leaf_Max]  m_Items;
>   }
> 
>   struct c_Branch
>   {
>     m_Final.c_Common_Head               m_Head;
>     m_Final.c_Branch_Item[m_Branch_Max] m_Items;
>   }
>   
>   int* Size (m_Final.c_Leaf* p)
>   {
>     return &((cast(c_Common_Head*) p).m_Size);
>   }
> 
>   int* Size (m_Final.c_Branch* p)
>   {
>     return &((cast(c_Common_Head*) p).m_Size);
>   }
> 
>   int* Height (m_Final.c_Leaf* p)
>   {
>     return &((cast(c_Common_Head*) p).m_Height);
>   }
> 
>   int* Height (m_Final.c_Branch* p)
>   {
>     return &((cast(c_Common_Head*) p).m_Height);
>   }
>   
>   c_Leaf_Items* Items (m_Final.c_Leaf* p)
>   {
>     return &((cast(c_Leaf*) p).m_Items);
>   }
> 
>   c_Branch_Items* Items (m_Final.c_Branch* p)
>   {
>     return &((cast(c_Branch*) p).m_Items);
>   }
> 
>   void** Child (m_Final.c_Branch_Item* p)
>   {
>     return &((cast(c_Branch_Item*) p).m_Child);
>   }
> }
> 
> template t_ML_Keys (alias PL, c_Key)
> {
>   mixin PL;
>   
>   struct c_Leaf_Item
>   {
>     PL.c_Leaf_Item  m_Previous;
>     c_Key           m_Key;
>   }
> 
>   struct c_Branch_Item
>   {
>     PL.c_Branch_Item  m_Previous;
>     c_Key             m_Key;
>   }
> 
>   c_Key* Key (m_Final.c_Leaf_Item* p)
>   {
>     return &((cast(c_Leaf_Item*) p).m_Key);
>   }
> 
>   c_Key* Key (m_Final.c_Branch_Item* p)
>   {
>     return &((cast(c_Branch_Item*) p).m_Key);
>   }
> }
> 
> template t_ML_Data (alias PL, c_Data)
> {
>   mixin PL;
>   
>   struct c_Leaf_Item
>   {
>     PL.c_Leaf_Item  m_Previous;
>     c_Data          m_Data;
>   }
> 
>   c_Data* Data (m_Final.c_Leaf_Item* p)
>   {
>     return &((cast(c_Leaf_Item*) p).m_Data);
>   }
> }
> 
> //  Shorthand form
> template t_ML_Keys_Data(alias PL, c_Key, c_Data)
> {
>   mixin t_ML_Keys!(t_ML_Data!(PL,c_Data),c_Key);
> }
> 
> void main (char[][] args)
> {
>   alias t_ML_Keys_Data!(t_ML_Init!(ti_Test, 4, 4),int,int) ti_Test;
> }
> 
> 
> I get the error "alias ti_Test recursive alias declaration" - clearly
> the cyclic dependency isn't liked.
> 
> I also tried to use the C++ form of mix-in layers, using an outer
> class as a container for definitions. That didn't work either. It
> didn't complain about the cyclic dependency, but it couldn't resolve
> it either. Kept complaining about definitions being missing from
> FINAL.
> 
> Funny how you can get used to an idea, and forget what the compiler is
> having to do to handle it. I've been just working on the assumption
> that I could do these things in D.
> 
> The cyclic dependency thing isn't a fundamental feature of mix-in
> layers, and I don't actually need it despite the concept-testing code
> above - there are other ways using 'static if' - but I just wanted to
> ask if this no-cyclic-dependencies rule is permanent or whether it
> might be changed in the future.

I don't see how it could ever work. An alias contains the fully 
qualified name, with type information. You're asking it for a name where 
part of the name is the full name; this results in an infinitely long 
recursive name. Somehow, you need to prevent the alias from becoming 
part of the type. Well, that's what I thought. But...

...there's hope, because in the example below I've managed to get the 
name of the variable 'shark' included in the type of 'shark'! It's not 
very stable, though -- it's not hard to ICE the compiler.

template frog(alias x)
{
    alias x frog;
}

template reptile(alias y)
{
    class fish {}
}

// But if you swap the order of these next two lines, it doesn't work!
reptile!(shark).fish turtle;
typedef typeof(frog!(turtle)) shark;

pragma(msg, shark.mangleof);
September 13, 2006
Re: Mixin layers and cyclic dependencies
On Tue, 12 Sep 2006 09:39:34 +0200, Don Clugston <dac@nospam.com.au>
wrote:

>I don't see how it could ever work. An alias contains the fully 
>qualified name, with type information. You're asking it for a name where 
>part of the name is the full name; this results in an infinitely long 
>recursive name.

Depends how you represent the name. It's possible to have explicit
recursion. Generate UIDs for each instance, defining what they refer
to on the first reference. In principle, you could end up with a
mangled name something like...

 0!A( 1!B( 0 ))

The second reference to UID '0' refers back to the first, using the
same template name and parameters. It's fairly easy to generate a form
like this from a symbol graph and visa versa, so it's fairly easy to
derive one mangled name from the other (eg determine the mangled name
of a templates parameter).

 0!A( 1!B( 0 ))

Becomes...

 +-+  --->  +-+
 |A|        |B|
 +-+  <---  +-+

Becomes...

 0!B( 1!A( 0 ))

The UIDs are generated from scratch in order of reference to ensure
that the names are generated consistently. Attempting to give each
instance a unique identifier that stays the same from build to build
would probably be very fragile.

So - possible, but it would probably need a new name mangling system.
That's bad - a compiler upgrade would invalidate all objs and libs,
and that can create problems esp. with third party libraries where you
don't have the source.

Also, since the mangleof thing is supplied by the compiler, people may
be dependent on it in strange ways. I wouldn't be surprised if people
have values in files that were derived somehow from mangled names.
Something serialization related, perhaps.

Definitely not something to be changed lightly.

-- 
Remove 'wants' and 'nospam' from e-mail.
Top | Discussion index | About this forum | D home