September 11, 2006
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
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
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