C/C++ structure incomplete member type inconsistency?

Question

Lets say we define two structures in either C or C++ (I get the same result in both C and C++ and I think the rules are the same, tell me if they are not).

one with a value member of an incomplete type:

struct abc{
  int data;
  struct nonexsitnow next; //error: field ‘next’ has incomplete type, makes sense since "struct nonexsitnow" hasn't been declared or defined.
};

and one with a pointer member of an incomplete type:

struct abc{
  int data;
  struct nonexsitnow *next; //pass?!
};

Why doesn't the second definition cause any issue? It uses struct nonexsitnow which hasn't been created!

UPDATE:

I conclude this sheet from answers and comments below, hoping they're right and helpful for elaborations.

As @ArneVogel has mentioned, both struct Foo p; and struct Foo *p; is an implicit declaration of Foo, and struct Foo; explicitly does this job(thanks @John Bollinger). This means nearly nothing for c but makes a difference for c++, and behaviors:

               In a situation where struct Foo is:
_______________________________________________________
|               | undeclared | declared but | defined |
|               |            | not defined  |         |
-------------------------------------------------------
|               |  C | C++   |  C  |  C++   | C | C++ |
-------------------------------------------------------
|struct Foo  p; |  × |  ×    |  ×  |   ×    | √ |  √  |
|struct Foo* p; |  √ |  √    |  √  |   √    | √ |  √  |
|       Foo  p; |  × |  ×    |  ×  |   ×    | × |  √  |
|       Foo* p; |  × |  ×    |  ×  |   √    | × |  √  |

Answer 1

Why does second struct definition doesn't cause any problem?

Because it is a pointer. The size of the pointer is known to the compiler even if the type the pointer is pointing to is incomplete.

Answer 2

The short answer is, because the c and c++ standard both say so.

---

Others have answered "because the compiler knows how big pointers are". But that really doesn't answer why. There are languages that permit incomplete types inside other types, and they work fine.

If any of these assumptions are changed, C/C++ would support incomplete structs within structs:

1. C/C++ actually stores values. Many languages, when given a composite data type (a class or struct) within another, store a reference or pointer instead of actual values of that composite data type

2. C/C++ wants to know how big complete types are. It wants to be able to create arrays, calculate their size, calculate the offset between elements.

3. C/C++ wants single-pass compiling. If the compiler was willing to note that there was an incomplete type there, continue compiling until it finds out later how big it is, then come back and insert the size of the type into the generated code, incomplete types would be fine.

4. C/C++ wants types to be complete after you define them. You could easily insert a rule stating that abc was only complete once nonexistnow's definition was visible. Instead, C++ wants abc to be complete right after the closing }, probably for simplicities sake.

Finally, pointers to structs satisfy all of these requirements because the C++ standard demands that they do. Which seems like a cop out, but it is true:

On some platforms, the size of a pointer varies with the features of the thing pointed to (in particular, pointers to single-byte characters on platforms where native pointers address quad words are larger). C/C++ permits this, but requires that void* be large enough for the largest pointer, and that pointers-to-struct have a fixed size. This hurts such platforms, but they are willing to do this in order to permit pointers to incomplete structs inside complete structs.

Quite possibly the compiler would rather than a struct small { char c; } be 1 byte in size, and hence pointers to it be "wide"; but because all pointers-to-struct must have the same size, and they don't want to use wide pointers for every struct, instead we have sizeof(small) == 4 on such systems.

It isn't a law of computing that all pointers are the same size, and it isn't a law that structs have to know how big they are. These are both laws of c++ and c that where chosen for reasons.

But once you have those reasons, you are forced to conclude that members of structs have to have known size (and alignment), and incomplete structs don't. Meanwhile, pointers to incomplete structs do. So one is permitted, and the other not.

Answer 3

Compiler needs the size of a struct / class in order to know how much memory has to be allocated when such type is instantiated.

On a given platform, sizeof(T*) will always return the same value, for any type T that is a struct or class type.

That is why you can use pointers to forward-declared types with no errors. Of course, to access content of an object pointed to by such pointer or dereference it, definition must be provided. You can, however assign value to such pointer (as long as it is allowed in terms of type compatibility).

An important fact:

In C, where you typically use so-called "C-style cast", pointer assignment can usually be performed regardless the types (it is your responsibility to ensure the correct behavior and fulfill alignment requirements).

In C++ however, whether cast between incomplete types is possible depends on the type of the cast. Consider two polymorphic types:

class A; // forward declaration only
class B; // forward declaration only, actually inherits from A

A* aptr;
B* bptr;

bptr = (B*)(aptr); // ok
bptr = dynamic_cast<B*>(aptr); // error

dynamic_cast<> will fail if compiler does not have access to the definition of types involved in the cast (which is necessary to perform runtime-check). Example: Ideone.

Answer 4

In the first place, you need to understand what it means for a type to be "incomplete". C defines it this way:

At various points within a translation unit an object type may be incomplete (lacking sufficient information to determine the size of objects of that type) or complete (having sufficient information).

(C2011, 6.2.5/1)

Note well that type completeness is a function of the scope and visibility of declarations, not an inherent characteristic of types. A type can be incomplete at one point in a translation unit, and complete at a different point.

However,

A pointer type may be derived from a function type or an object type, called the referenced type. [...] A pointer type is a complete object type.

(C2011, 6.2.5/20; emphasis added)

Without qualification, then, all pointer types are complete types, even pointers whose referenced types are not themselves complete. How a particular implementation makes this work is not addressed by the standard, but ordinarily, all pointer-to-structure types have the same size and representation (which has nothing to do with the representation of their referenced types).

This turns out to be important, because a structure type is incomplete until the closing brace of its definition, so if pointers to incomplete types were not themselves complete, then a structure could not contain a pointer to another structure of its own type, such as is commonly used to implement linked lists, trees, and other data structures.

On the other hand,

A structure or union type of unknown content [...] is an incomplete type. It is completed, for all declarations of that type, by declaring the same structure or union tag with its defining content later in the same scope.

(C2011, 6.2.5/22)

This stands to reason, since the compiler cannot know how big a structure type is if it does not know what its members are. It then furthermore makes sense that

A structure or union shall not contain a member with incomplete or function type (hence, a structure shall not contain an instance of itself, but may contain a pointer to an instance of itself), except that the last member of a structure with more than one named member may have incomplete array type [...].

(C2011, 6.7.2.1/3; emphasis added)

The exception describes a C feature called a "flexible array member", which comes with several caveats and restrictions. That's a tangential matter that you can read (or ask) about separately.

Additionally, all of the foregoing is consistent with the fact that C and C++ permit you to reference a structure type by its tag prior to its members being declared; that is, when it is an incomplete. This can be done on its own as a forward declaration ...

struct foo;

... but that doesn't serve any but documentary purposes, because forward declaration of structure types is not required. You can think again of the linked-list usage, but this characteristic is in no way limited to such contexts.

Indeed, a relatively common use case is to implement opaque types. In such a case, a library produces and consumes a data type whose implementation it does not want to disclose, for any of a variety of reasons. It can nevertheless hand out appropriately-typed pointers to instances of such structures to client code, and expect to receive such pointers back. If it never provides a definition of the referenced type, then the client code has to treat the referenced objects as opaque blobs.