What is a circular include dependency, why is it bad and how do I fix it?

Question

Suppose I have two data structures that reference each other. I want to put them into their separate header files like this:

 // datastruct1.h
 #ifndef DATA_STRUCT_ONE
 #define DATA_STRUCT_ONE

 #include <datastruct2.h>
 typedef struct DataStructOne_t
 {
   DataStructTwo* two;
 } DataStructOne;
 #endif

and

 // datastruct2.h
 #ifndef DATA_STRUCT_TWO
 #define DATA_STRUCT_TWO

 #include <datastruct1.h>
 typedef struct DataStructTwo_t
 {
   DataStructOne* one;
 } DataStructTwo;

 #endif

and I have a main function:

 #include <datastruct1.h>
 #include <datastruct2.h>

 int main() 
 {
    DataStructOne* one;
    DataStructTwo* two;
 }

However my compiler complains:

$ gcc -I. -c main.c
In file included from ./datastruct1.h:4,
                 from main.c:1:
./datastruct2.h:8:2: error: unknown type name ‘DataStructOne’
    8 |  DataStructOne* one;
      |  ^~~~~~~~~~~~~

Why is that? What can I do to fix this?

Answer 1

Well, if both structures reference each other, it is clear that they must be related. The best thing you can do is to put both in one include file (as they are related) but putting them in different and making the compiler to read from one include the other will make the compiler to read the main file... .from main file start reading include A until it gets to the point to include B, and start reading B to the point of the include A again(we'll start reading A again in a recursive manner that has no end) you will never stop reading each file and worse, you will get an error the second time you see the same struct definition (because it has been already defined before)

To allow the user to include any or both files without a problem, a define is made when include file A is encountered:

File A.h

#ifndef INCLUDE_FILE_A
#define INCLUDE_FILE_A
/* ... the whole stuff of file A with the proper includes of other files.*/
#include "B.h"
#endif /* INCLUDE_FILE_A */

and in

File B.h

#ifndef INCLUDE_FILE_B
#define INCLUDE_FILE_B
/* ... the whole stuff of file B with the proper includes of other files.*/
#include "A.h"
#endif /* INCLUDE_FILE_B */

so the definitions made in file A are only used if INCLUDE_FILE_A has not been included previously, and skip them if file A has been included already (and the same for B.h, of course).

If you make the same on file B (but instead with INCLUDE_FILE_B) then you will be secure that both files will be included in either order (depending on how you did it in the first case) and will never be included again (making th e inclussion secure of returning back to the main file.

Answer 2

One way to resolve the circular dependency and still use the typedefs where possible is to split the headers into two parts with a separate guard macro for each part. The first part provides typedefs for incomplete struct types and the second part completes the declarations of the struct types.

For example :-

datastruct1.h

#ifndef DATA_STRUCT_ONE_PRIV
#define DATA_STRUCT_ONE_PRIV
/* First part of datastruct1.h. */

typedef struct DataStructOne_t DataStructOne;

#endif

#ifndef DATA_STRUCT_ONE
#define DATA_STRUCT_ONE
/* Second part of datastruct1.h */

#include <datastruct2.h>

struct DataStructOne_t
{
    DataStructTwo *two;
};

#endif

datastruct2.h

#ifndef DATA_STRUCT_TWO_PRIV
#define DATA_STRUCT_TWO_PRIV
/* First part of datastruct2.h. */

typedef struct DataStructTwo_t DataStructTwo;

#endif

#ifndef DATA_STRUCT_TWO
#define DATA_STRUCT_TWO
/* Second part of datastruct2.h */

#include <datastruct1.h>

struct DataStructTwo_t
{
    DataStructOne *one;
};

#endif

main.c

/*
 * You can reverse the order of these #includes or omit one of them
 * if you want.
 */
#include <datastruct1.h>
#include <datastruct2.h>

int main(void)
{
    DataStructOne *one;
    DataStructTwo *two;
}

As mentioned in the comment in main.c above, only one of the headers needs to be included since the other header will be included indirectly anyway.

Answer 3

Why?

In order to understand why, we need to think like a compiler. Let's do that while analysing main.c line by line. What would a compiler do?

• #include <datastruct1.h>: Put "main.c" aside (push to the stack of files being processed) and switch to "datastruct1.h"
• #ifndef DATA_STRUCT_ONE: hmm, this is not defined, let's continue.
• #define DATA_STRUCT_ONE: OK, defined!
• #include <datastruct2.h>: Put "datastruct1.h" aside and switch to "datastruct2.h"
• #ifndef DATA_STRUCT_TWO: hmm, this is not defined, let's continue.
• #define DATA_STRUCT_TWO: OK, defined!
• #include <datastruct1.h>: Put "datastruct2.h" aside and switch to "datastruct1.h"
• #ifndef DATA_STRUCT_ONE: this is now defined, so go straigh to #endif.
• (end of "datastruct1.h"): close "datastruct1.h" and pop current file from the stack of filles. What were I doing? Ahh, "datastruct2.h". Let's continue from the place where we left.
• typedef struct DataStructTwo_t ok, starting a struct definition
• DataStructOne* one; Wait, what is DataStructOne? We have not seen it? (looking up the list of processed lines) Nope, no DataStructOne in sight. Panic!

What happened? In order to compile "datastruct2.h", the compiler needs "datastruct1.h", but the #include guards in it "datastruct1.h" prevent its content from being actually included where it's needed.

The situation is symmetrical, so if we switch the order of #include directives in "main.c", we get the same result with the roles of the two files reversed. We cannot remove the guards either, because that would cause an infinite chain of file inclusions.

It appears that we need "datastruct2.h" to appear before "datastruct1.h" and we need "datastruct1.h" to appear before "datastruct2.h". This does not seem possible.

What?

The situation where file A #includes file B which in turn #includes file A is clearly unacceptable. We need to break the vicious cycle.

Fortunately C and C++ have forward declarations. We can use this language feature to rewrite our header files:

 #ifndef DATA_STRUCT_ONE
 #define DATA_STRUCT_ONE

 // No, do not #include <datastruct2.h>
 struct DataStructTwo_t; // this is forward declaration

 typedef struct DataStructOne_t
 {
   struct DataStructTwo_t* two;
 } DataStructOne;
 #endif

In this case we can rewrite "datastruct2.h" the same way, eliminating its dependency on "datastruct1.h", breaking the cycle in two places (strictly speaking, this is not needed, but less dependencies is always good). Alas. this is not always the case. Often there is only one way to introduce a forward declaration and break the cycle. For ecample, if, instead of

DataStructOne* one;

we had

DataStructOne one; // no pointer

then a forward declaration would not work in this place.

What if I cannot use a forward declaration anywhare?

Then you have a design problem. For example, if instead of both DataStructOne* one; and DataStructTwo* two; you had DataStructOne one; and DataStructTwo two;, then this data structure is not realisable in C or C++. You need to change one of the fields to be a pointer (in C++: a smart pointer), or eliminate it altogether.