Semi-circular definitions (plus circular references)

[Kiuhnm]

Is there an elegant way to deal with semi-circular definitions?

Semi-circular definition:
A { B };
B { *A };
Circular reference:
A { *B };
B { *A };

The problems arise when there are more semi-circular definitions and
circular references.

Consider the following sample code:

--- inc1.h ---
#ifndef INC1_INCLUDE
#define INC1_INCLUDE

typedef struct _struc2
{
struct _struc1 *s1;
} struc2;
typedef struct _struc3
{
struct _struc1 *s1;
} struc3;

typedef struct _struc1
{
struct _struc2 s2;
struct _struc3 s3;
} struc1;

typedef struct _struc4
{
struct _struc1 s1;
} struc4;

#endif

--- test.cpp ---

#include "inc1.h"

int main()
{
struc1 s1;
s1.s2;

return 1;
}

------

The previous code is obviously correct.
Now I want to split the include file in two separated files.
The original include file contains 4 definitions:
A
B
C
D
The problem arises when the splitting is such that the original include
file cannot be obtained by reattaching the 2 include files.
For Example, inc1.h could contain A and D, and inc2.h B and C.

--- inc1.h ---
#ifndef INC1_INCLUDE
#define INC1_INCLUDE

#include "inc2.h"

typedef struct _struc2
{
struct _struc1 *s1;
} struc2;

typedef struct _struc4
{
struct _struc1 s1;
} struc4;

#endif

--- inc2.h ---
#ifndef INC2_INCLUDE
#define INC2_INCLUDE

#include "inc1.h"

typedef struct _struc3
{
struct _struc1 *s1;
} struc3;

typedef struct _struc1
{
struct _struc2 s2;
struct _struc3 s3;
} struc1;

#endif

-------

Someone affirms that this situation is index of bad organization, but I
disagree, then I do not seek an obvious workaround, but a solution to
the *original* problem.
Yes, I could use a pointer instead of the struct itself, but I do not
want to use an unneeded indirection.
I could even use a dummy structure but that solution is very inelegant.

Is there a particular directive which instructs the compiler to analyze
the entire file before giving up?

Is there a better solution than using a bunch of #if..[...]..#endif? :)

Thanks, Kiuhnm

[Jonathan Bartlett]

Kiuhnm wrote:

Is there an elegant way to deal with semi-circular definitions?

You just need to restructure it a bit. Here's my solution which seems
to work:

inc1.h:
---------

#ifndef INC1_INCLUDE
#define INC1_INCLUDE


typedef struct _struc2
{
struct _struc1 *s1;
} struc2;
#include "inc2.h"
typedef struct _struc4
{
struct _struc1 s1;
} struc4;
#endif

----------------
inc2.h:
----------------#include "inc1.h"
#ifndef INC2_INCLUDE
#define INC2_INCLUDE


typedef struct _struc3
{
struct _struc1 *s1;
} struc3;


typedef struct _struc1
{
struct _struc2 s2;
struct _struc3 s3;
} struc1;


#endif
--------

Compiles cleanly for me.

Jon
----
Learn to program using Linux assembly language
http://www.cafeshops.com/bartlettpublish.8640017

[Kiuhnm]

Jonathan Bartlett wrote:

Kiuhnm wrote:

Is there an elegant way to deal with semi-circular definitions?

You just need to restructure it a bit. Here's my solution which seems
to work:

[cut]

You recomposed the original file!
Is it always possible?
No, unfortunately.

--- inc1.h ---
s1 {s3}
s2 {s4}
--- inc2.h ---
s3 {s2}
s4 {}
--------------

Let "a < b" mean "a must appear before b".

s3 < s1,
s4 < s2
s2 < s3

=>

s4 < s2 < s3 < s1

then that's the only correct arrangement.

By partially reordering the structures in each include file, we obtain:
--- inc1.h ---
s2 {s4}
s1 {s3}
--- inc2.h ---
s4 {}
s3 {s2}
--------------

s2 s1
s4 s3

How can we obtain that arrangement without splitting any file?
Why are the compilers so stupid?
The compiler could simply perform a first pass and compile a table of
the sizes of all the structures and then use that table in the
successive passes.

Perhaps the documentation of the preprocessor could help...

Thank you anyway!

Kiuhnm

[Dave Rahardja]

Kiuhnm wrote:

You recomposed the original file!
Is it always possible?
No, unfortunately.

Yes, it is *always* possible to rearrange the way data structures are
declared so that entities are declared before they are needed. It may
entail declaring each data structure in its own header file, but it is
always possible.

Consider what happens when a truly circular dependency is declared:

struct A { B b };
struct B ( A a };

This implies that B includes a copy of A, which includes a copy of B,
which includes a copy of A, ad infinitum. This struct has infinite size
and is not possible to instantiate.

In other words, in order for a data structure to have finite size, its
composition graph must have no loops. Thus, all finite data structures
can be described by a sequence of declarations with no "forward dependency".

Sometimes it is not possible to properly declare data structures if
multiple data structures are declared within one or more header files.
Your problem in this case in not with the language definition or the
compiler, but with the way that your modules are organized.

-dr

[Kiuhnm]

Dave Rahardja wrote:

Kiuhnm wrote:

You recomposed the original file!
Is it always possible?
No, unfortunately.

Yes, it is *always* possible to rearrange the way data structures are
declared so that entities are declared before they are needed. It may
entail declaring each data structure in its own header file, but it is
always possible.

I've just *proved* that (with the restrictions I imposed) it is impossible.
Sometimes it is not possible to properly declare data structures if
multiple data structures are declared within one or more header files.
Your problem in this case in not with the language definition or the
compiler, but with the way that your modules are organized.

No, the problem resides in the c/c++ compilers/language.
If something could have been done better, then it should have been done
better.
A smart compiler would scan the entire preprocessed file and build a
graph with the dependencies in order to quickly determine the structure
sizes.
I can understand that you consider the compiler something untouchable,
but, IMHO, a compiler is a tool, not a religion.

Do you know C#? In this language, the forward definitions are handled
seamlessly.
I think I'll pass to C#... or maybe I could write a little preprocessor
for the C++ compiler (portability is not an issue to me).

Kiuhnm

[Jonathan Mcdougall]

Kiuhnm wrote:

Dave Rahardja wrote:

Kiuhnm wrote:

You recomposed the original file!
Is it always possible?
No, unfortunately.
Yes, it is *always* possible to rearrange the way data structures are
declared so that entities are declared before they are needed. It may
entail declaring each data structure in its own header file, but it is
always possible.

I've just *proved* that (with the restrictions I imposed) it is impossible.

If you cannot change the headers, C++ cannot do
anything for you.

Sometimes it is not possible to properly declare data structures if
multiple data structures are declared within one or more header files.
Your problem in this case in not with the language definition or the
compiler, but with the way that your modules are organized.

No, the problem resides in the c/c++ compilers/language.

It is because of the language, but it is not a
problem, it is called "type checking". To use a
name, you need to declare it and to instanciate a
class, you need its definition.
If something could have been done better, then it should have been done
better.
A smart compiler would scan the entire preprocessed file and build a
graph with the dependencies in order to quickly determine the structure
sizes.
If you think compilers are dumb, write one.
I can understand that you consider the compiler something untouchable,
but, IMHO, a compiler is a tool, not a religion.
Do you know C#?
No one is forcing you to use C++. If a language
cannot do what you want, change it! Languages are
tools, not religions.
In this language, the forward definitions are handled seamlessly.

If I recall correctly, C# only deals with
references, not with stack-based objects. You
never need the size of the classes in this case.
It's like replacing automatic objects with
pointers in your example, which solves your
problem. Before falling in love with this, read
about the problems (and advantages) associated
with this behavior.
Jonathan

[Kiuhnm]

Jonathan Mcdougall wrote:

If you cannot change the headers, C++ cannot do anything for you.
The headers are thematically divided, then I don't want to move a
definition from a file to another.
It is because of the language, but it is not a problem, it is called
"type checking". To use a name, you need to declare it and to
instanciate a class, you need its definition.
I know, but you omitted a detail: C++ uses a "chronologi cal type
checking". The mathematical language is ABSOLUTELY UNAMBIGUOUS and
doesn't have such a limitation.
Besides, why should the programmer tolerate such a restriction when a
simple algorithm could completely resolve the problem?
If you think compilers are dumb, write one.
Very humorous, but I prefer to write a preprocessor.
If I recall correctly, C# only deals with references, not with
stack-based objects. You never need the size of the classes in this
case. It's like replacing automatic objects with pointers in your
example, which solves your problem. Before falling in love with this,
read about the problems (and advantages) associated with this behavior.

Then C# is not a language for me (I'm developing a real-time OS).

Kiuhnm

[Jonathan Mcdougall]

"Kiuhnm" <ki******@yahoo .it.invalid> a écrit dans le message de news:
qN************* *********@news3 .tin.it...

Jonathan Mcdougall wrote:

If you cannot change the headers, C++ cannot do anything for you.
The headers are thematically divided, then I don't want to move a
definition from a file to another.

There are situations where you must sacrifice a bit of design in order to
make the program work. It seems to be your case, but you only can tell.

It is because of the language, but it is not a problem, it is called
"type checking". To use a name, you need to declare it and to
instanciate a class, you need its definition.

I know, but you omitted a detail: C++ uses a "chronologi cal type
checking". The mathematical language is ABSOLUTELY UNAMBIGUOUS and doesn't
have such a limitation.

I don't understand that.
Besides, why should the programmer tolerate such a restriction when a
simple algorithm could completely resolve the problem?

Because that's how the language works.

A a;

class A
{
};

does not work, not because the compiler cannot make it work (postponing the
checking of names until the translation unit is completly processed would be
a solution to this example but has many drawbacks for others, more
complicated constructs), but because the language mandates it.
Jonathan

[Kiuhnm]

Jonathan Mcdougall wrote:

There are situations where you must sacrifice a bit of design in order to
make the program work. It seems to be your case, but you only can tell.
I moved the most referenced structure to a separated file.

I know, but you omitted a detail: C++ uses a "chronologi cal type
checking". The mathematical language is ABSOLUTELY UNAMBIGUOUS and doesn't
have such a limitation.

I don't understand that.

|u+v| <= |u|+|v| for each u,v in C(T, R).

u and v are used before the definition.

Another example:
for each x > 0, there exists K in N : d(u_k,u_h) < eps, for each k,h in
N, h,k > K.
A a;

class A
{
};

does not work, not because the compiler cannot make it work (postponing the
checking of names until the translation unit is completly processed would be
a solution to this example but has many drawbacks for others, more
complicated constructs), but because the language mandates it.

The languages C and C++ are a bit incoherent: it is possible to define a
pointer to an undefined object, because you will need the object
definition only when you will use the pointer, but it is impossible to
define an object which contains an undefined object, even if the object
definition will not be used before the first instantiation.
You call that a feature? IMHO, that is a flaw.

Kiuhnm

[Jonathan Mcdougall]

"Kiuhnm" <ki******@yahoo .it.invalid> a écrit dans le message de news:
Vl************* *********@news3 .tin.it...

Jonathan Mcdougall wrote:

A a;

class A
{
};

does not work, not because the compiler cannot make it work (postponing
the checking of names until the translation unit is completly processed
would be a solution to this example but has many drawbacks for others,
more complicated constructs), but because the language mandates it.
The languages C and C++ are a bit incoherent: it is possible to define a
pointer to an undefined object,

Undefined, but declared.
because you will need the object definition only when you will use the
pointer,
Not when you use it, only when you need the definition of the class.

class A;

void f(A *a);

int main()
{
A *a=0;
f(a);
}

This example does not need the definition of A, only its declaration.
but it is impossible to define an object which contains an undefined
object,
Of course, because its size is needed. If you have a pointer or reference,
you don't need the class' definition to define one.
You call that a feature? IMHO, that is a flaw.

Requiring the class's definition for everything would not only be
unnecessary but also a pain. It is the base for a common technique of
reducing compilation dependencies.

I wouldn't say C++ does a good job at separating modules, but I think the
language *is* consistent. When the compiler does not need the class's
definition to operate, you don't have to specify it.
Jonathan