Assignment of incompatible type and different namespaces in C

Question

I have a chained hash table with the following structure:

typedef struct{
    char* phrase; 
    struct phrase_struct* next; 
}phrase_struct;

My immediate concern about this structure was that the pointer actually referred to a typedef that may not have been defined yet .. but it compiled so I figured it was valid syntax. I have several functions that either allocate memory and manipulate the pointer next that points to the next node.

Consider pointers of the following type and an automatically allocated struct:

phrase_struct* ptr1

phrase_struct* ptr2

phrase_struct test_s;

If I did the following assignments:

ptr1 = &test_s

ptr2 = test_s.next; <- this pointer would be set to NULL elsewhere in the code

I would continually get error complaining about incompatible assignments of the type:

'=' : incompatible types - from 'phrase_struct *' to 'phrase_struct *'

And then it hit me .. I recalled having previously read something regarding namespaces of typedef and actual structure names being independent.

---

typedef struct test{
    char* phrase; 
    struct test* next; 
}phrase_struct;

Changing the structure definition to this fixed all the warnings.

Can someone explain this?

Answer 1

This definition

typedef struct{                 // 1
    char* phrase; 
    struct phrase_struct* next; // 2
}phrase_struct;                 // 3

defines 3 things:

1. An anonymous structure
2. A member which is a pointer to a forward-declared structure named struct phrase_struct
3. A typedef for the anonymous structure called phrase_struct

Whenever you refer to a plain phrase_struct, it refers to the typedef. Whenever you refer to struct typedef, it refers to the structure named phrase_struct within the struct tag namespace; this structure has been forward-declared (in (2)) and is an incomplete type, but it hasn't actually been fully defined yet.

The error message is unfortunately confusing. What the error is trying to say is this:

'=' : incompatible types - from 'struct phrase_struct *' to the typedef
      'phrase_struct *'

because the undefined, forward-declared structure has no relation to the typedef which has been defined.

The fix, as you found, is straightforward: instead of defining an anonymous structure, give the structure a name, and refer to that same name (in the struct tag namespace) in the member definition:

typedef struct phrase_struct{   // 1
    char* phrase;
    struct phrase_struct* next; // 2
}phrase_struct;                 // 3

This defines:

1. A structure named struct phrase_struct in the struct tag namespace
2. A member with a type of pointer to a struct phrase_struct instance (i.e. the type defined in (1))
3. A typedef named phrase_struct, defined as an alias for struct phrase_struct

It's confusing because the tag namespaces (struct, union, and enum) are separate from the ordinary typedef namespace.

See also Difference between struct and typedef struct in C++? and What is a typedef enum in Objective-C?.

Answer 2

With this:

typedef struct{
    char* phrase; 
    struct phrase_struct* next; 
}phrase_struct;

you've never defined struct phrase_struct, so struct phrase_struct * is a pointer to an incomplete type which you likely never define. phrase_struct here is a typedefd name for an anonymous structure. That anonymous structure is not the same thing as struct phrase_struct, so your compiler rightly points out that the types of the pointers differ.

When you say "it compiled so I figured it was valid syntax", this is because you are allowed to define pointers to types you have not yet defined, since all the compiler needs to know is how much memory a pointer requires, which it can figure out without needing to know the details of the type. But you have to provide a definition for such a type before you can actually create any objects of that type, and before you can dereference a pointer to it to access its members, etc.

So the mystery is that you do (or initially did) have valid syntax, but that syntax does not do what you thought it did.