tags:

views:

491

answers:

8
+7  Q: 

Cannibal Classes

For sometime now, I have been trying to wrap my head around the reason why some “cannibal” classes are allowed to compile.

Before I continue, perhaps I should explain what I call a “cannibal” class. Not sure if I just invented that term or if it has been around for a while or even if I am using it correctly but that is not important right now.

I basically call a cannibal class a class that consumes itself. In other words a class whose interface declares members of its own type. For example:

class Foo
{
    public Foo SomeFoo; 
}

As you can see above, class Foo has a member of type Foo (itself).

Now, the first time I saw this (looong time ago) I didn’t thing it was going to compile but it to my surprise it does compile. The reason why I didn’t thing this would compile is because to me this screams some type of recursive nightmare.

To complicate things a little further, I decided to try the same thing but making the class a struct such as:

struct Foo
{
    public Foo SomeFoo; 
}

Unfortunately, this does not compile, instead you get error: Struct member 'Foo.SomeFoo' of type 'Foo' causes a cycle in the struct layout

To me, a compile error makes more sense that no error but I am sure there most be a logical explanation to this behavior so I was wondering if anyone of you guys could explain this behavior.

Thanks.

A: 

So do you call a Singleton implementation a canibal class?

public class ShopSettings
{
  public static ShopSettings Instance
  {
    get
    {
      if (_Instance == null)
      {
        _Instance = new ShopSettings();
      }

      return _Instance;
    }
  }
}
MartinHN
-1, no, your instance in static and would completely avoid this problem.
Samuel
+23  A: 

The reason you can't design a struct like this is because structs have to be initialized when they are allocated with some default values. So, when you have a struct Foo like you described and you create a Foo...

Foo x; // x = default(Foo)

it calls the default constructor for Foo. However, that default constructor has to give a default value for the Foo.SomeFoo field.

Well, how's it find that? It has to call default(Foo). Which, in order to construct a Foo, has to give a default value for the Foo.SomeFoo field... As you surmised, this is a recursive nightmare.

Since you can create a null reference to a class, and refrain from actually creating an instance of the class immediately, there's no problem; you can call new Foo() and Foo.SomeFoo will just be null. No recursion necessary.

ADDENDUM: When you're thinking about this, if you're still confused, I think the other answers have another good way of considering it (same essential problem, different approach) -- when the program allocates memory for a Foo, how's it supposed to do it? What's sizeof(Foo) when Foo contains some stuff, and then another whole Foo? You can't do that.

Instead, if it were a class, it would just have to allocate a couple bytes for a reference to a Foo, not an actual Foo, and there's no problem.

mquander
To summarize: class = reference type, struct = value type. You can't layout the memory map of a type containing itself. However, reference types will contain only memory reference, not the actual data structure. Therefore, it's not necessary to know how that type is structured at compile time.
spoulson
+1  A: 
class Foo
{
    public Foo SomeFoo; 
}

The SomeFoo in this example just a link - and doesn't make the recursive create problem.
And because of this, canibal classes can exists.

Avram
+11  A: 

The difference lies in the fact that Foo is a reference type. The class memory layout will have a pointer to a Foo instance and this will be fine.

In the case of the structure, you have basically an infintely recusrsive memory layout, that cannot work.

Now, if your class tries to instantiate a Foo in its own constructor, then you will have a Stack overflow problem.

Denis Troller
This is the correct answer. The difference between value types and reference types, which is the difference between structs and classes. The default value problem is a consequence of this.
Conor OG
A: 

As they said it's a valuetype, hence it cant contain itself, as it just cant work (think about it).

You can however do the following:

unsafe struct Foo
{
  public Foo* SomeFoo;
}
leppie
+5  A: 

They are called recursive types, and they are quite common. A tree, for example, is commonly implemented in terms of "nodes" that refer to other nodes. There is nothing paradoxical about this, so long as they refer to each other but don't contain each other.

As one way to wrap your head around this, the square of an integer is always another integer. Nothing odd about that, it's just a reference or relationship between the two integers. But you can't have a string that contains a complete copy of itself as a substring. That's the distinction.

MarkusQ
I just invented a thing that contains a copy of itself... I think I will call it a fractal! :)
DrJokepu
Ah, but fractals _don't_ contain a complete copy of themselves. Instead, portions of a fractal can be put into correspondence with the whole under some mapping, up to some epsilon.
MarkusQ
+1  A: 

Ok, I see.

So to drive home the point, if I understand correctly, the compiler does not care whether the member is of type Foo, Bar or whatever else. All the compiler needs to know is the number of bytes that it needs to allocate for that member variable.

So if this was being compiled to a 32 bit OS, then I assume that the compiler is technically changing the declaration of the Foo type to something like:

class Foo
{
    public Int32 SomeFoo; 
}

Instead of “Foo” the compiler is really seeing 32 bits (kind of).

Thanks.

Rene
ultimately, memory-wise, yes.
Denis Troller
+1  A: 

To understand why this is allowed along with how it can be useful, a classic linked-list implementation is a great example, check out this tutorial

http://cyberkruz.vox.com/library/post/c-tutorial-linked-list.html

You see, they define a node class as follows:

public class LinkedList
{

    Node firstNode;

    public class Node
    {

        Node previous;
        Node next;
        int value;
    }
}

Where each node points to the previous and next node, so thinking of it as a link to another object is a good start.

If you haven't done a Linked List before, I highly recommend it as it is a good exersize.

TJB