www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Mixin layers and cyclic dependencies

reply Steve Horne <stephenwantshornenospam100 aol.com> writes:
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.
Sep 11 2006
parent reply Don Clugston <dac nospam.com.au> writes:
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);
Sep 12 2006
parent Steve Horne <stephenwantshornenospam100 aol.com> writes:
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.
Sep 13 2006