 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Kiuhnm
Guest
|
 Posted: Thu Dec 30, 2004 5:40 pm Post subject: Semi-circular definitions (plus circular references) |
 |
|
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
|
|
| Back to top |
|
 |
Jonathan Bartlett
Guest
|
| Posted: Thu Dec 30, 2004 9:47 pm Post subject: Re: Semi-circular definitions (plus circular references) |
|
|
Kiuhnm wrote:
| Quote: | 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
|
|
| Back to top |
|
|
Kiuhnm
Guest
|
| Posted: Fri Dec 31, 2004 12:53 am Post subject: Re: Semi-circular definitions (plus circular references) |
|
|
Jonathan Bartlett wrote:
| Quote: | 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
|
|
| Back to top |
|
|
Dave Rahardja
Guest
|
| Posted: Fri Dec 31, 2004 4:33 am Post subject: Re: Semi-circular definitions (plus circular references) |
|
|
Kiuhnm wrote:
| Quote: | 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
|
|
| Back to top |
|
|
Kiuhnm
Guest
|
| Posted: Fri Dec 31, 2004 12:16 pm Post subject: Re: Semi-circular definitions (plus circular references) |
|
|
Dave Rahardja wrote:
| Quote: | 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.
| Quote: | 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
|
|
| Back to top |
|
|
Jonathan Mcdougall
Guest
|
| Posted: Fri Dec 31, 2004 4:03 pm Post subject: Re: Semi-circular definitions (plus circular references) |
|
|
Kiuhnm wrote:
| Quote: | 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.
| Quote: | 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.
| Quote: | 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.
| Quote: | 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.
| Quote: | 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
|
|
| Back to top |
|
|
Kiuhnm
Guest
|
| Posted: Fri Dec 31, 2004 5:13 pm Post subject: Re: Semi-circular definitions (plus circular references) |
|
|
Jonathan Mcdougall wrote:
| Quote: | 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.
| Quote: | 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 "chronological 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?
| Quote: | If you think compilers are dumb, write one.
|
Very humorous, but I prefer to write a preprocessor.
| Quote: | 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
|
|
| Back to top |
|
|
Jonathan Mcdougall
Guest
|
| Posted: Fri Dec 31, 2004 8:32 pm Post subject: Re: Semi-circular definitions (plus circular references) |
|
|
"Kiuhnm" <kiuhnm03 (AT) yahoo (DOT) it.invalid> a écrit dans le message de news:
qNfBd.351294$b5.17252185 (AT) news3 (DOT) tin.it...
| Quote: | 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.
| Quote: | 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 "chronological type
checking". The mathematical language is ABSOLUTELY UNAMBIGUOUS and doesn't
have such a limitation.
|
I don't understand that.
| Quote: | 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
|
|
| Back to top |
|
|
Kiuhnm
Guest
|
| Posted: Sat Jan 01, 2005 3:29 pm Post subject: Re: Semi-circular definitions (plus circular references) |
|
|
Jonathan Mcdougall wrote:
| Quote: | 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.
| Quote: | I know, but you omitted a detail: C++ uses a "chronological 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.
| Quote: | 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
|
|
| Back to top |
|
|
Jonathan Mcdougall
Guest
|
| Posted: Sat Jan 01, 2005 6:00 pm Post subject: Re: Semi-circular definitions (plus circular references) |
|
|
"Kiuhnm" <kiuhnm03 (AT) yahoo (DOT) it.invalid> a écrit dans le message de news:
VlzBd.353091$b5.17333521 (AT) news3 (DOT) tin.it...
| Quote: | 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.
| Quote: | 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.
| Quote: | 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.
| Quote: | 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
|
|
| Back to top |
|
|
Dave Rahardja
Guest
|
| Posted: Sat Jan 01, 2005 7:01 pm Post subject: Re: Semi-circular definitions (plus circular references) |
|
|
Kiuhnm wrote:
| Quote: | |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.
|
There is a need for a balance between mathematical purity,
comprehensibility, economy of compile time, and ease of implementation
that one needs to consider while writing a language. Allowing the "use
before definition" paradigm would necessitate a multiple-pass
compilation (beyond the preprocessor stage), increase compile times, and
would lead to confusing paradoxes like this:
class A { B b; };
class B { A a; };
Which the compiler must detect.
The benefits of allowing such behavior is dubious--certainly nothing
that can't be achieved by the language as it stands today.
| Quote: | 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.
|
In C and C++, you can define a pointer (or a reference) to an undefined
(but declared) entity because the size of a pointer is known. You cannot
use an undefined data structure as a member of another because the
compiler needs to know how much space to allocate for the data storage.
That doesn't make the language "incoherent". The rules of the language
are coherent and sensible once you understand the needed compromise.
The definition-before-use requirement of C++ doesn't give me any
headaches, and I've worked on embedded applications that have upward of
100 compilation units. I'm afraid you'd either have to change the way
you analyze your problem, or look for another language that more closely
matches your expectations.
My advice is not to get too hung up on a peculiarity of the language and
try to work around any limitations that you may find. Sure beats halting
your development schedule.
|
|
| Back to top |
|
|
Kiuhnm
Guest
|
| Posted: Sat Jan 01, 2005 10:31 pm Post subject: Re: Semi-circular definitions (plus circular references) |
|
|
Jonathan Mcdougall wrote:
| Quote: | 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.
|
I meant when you use the pointer to access the members of the pointed
object. My mistake.
| Quote: | Of course, because its size is needed. If you have a pointer or reference,
you don't need the class' definition to define one.
|
When is it needed? A definition does not require any allocation. If I
instantiate the object after all the definitions, there should be no
problem.
| Quote: | 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.
|
But the compiler requires the definitions when these are not
intrinsically required. A definition is a model, not a physical object
and thus does not require space.
Kiuhnm
|
|
| Back to top |
|
|
Kiuhnm
Guest
|
| Posted: Sat Jan 01, 2005 11:02 pm Post subject: Re: Semi-circular definitions (plus circular references) |
|
|
Dave Rahardja wrote:
[cut]
| Quote: | compilation (beyond the preprocessor stage), increase compile times, and
would lead to confusing paradoxes like this:
class A { B b; };
class B { A a; };
Which the compiler must detect.
|
There are many methods to minimize the increase in compilation time. The
compiler could use a graph only when needed or in the presence of a hint
(e.g. a special forward declaration).
| Quote: | In C and C++, you can define a pointer (or a reference) to an undefined
(but declared) entity because the size of a pointer is known. You cannot
use an undefined data structure as a member of another because the
compiler needs to know how much space to allocate for the data storage.
|
This is not completely exact: a definition does not require space.
And if all the definitions appear before the first instantiation...
| Quote: | My advice is not to get too hung up on a peculiarity of the language and
try to work around any limitations that you may find. Sure beats halting
your development schedule.
|
Don't worry. The major difficulty is devising the algorithms! The last
took me 6 months!!!
Kiuhnm
|
|
| Back to top |
|
|
Jonathan Mcdougall
Guest
|
| Posted: Sun Jan 02, 2005 6:14 pm Post subject: Re: Semi-circular definitions (plus circular references) |
|
|
"Kiuhnm" <kiuhnm03 (AT) yahoo (DOT) it.invalid> a écrit dans le message de news:
yxFBd.354018$b5.17414335 (AT) news3 (DOT) tin.it...
| Quote: | Jonathan Mcdougall wrote:
Of course, because its size is needed. If you have a pointer or
reference, you don't need the class' definition to define one.
When is it needed? A definition does not require any allocation. If I
instantiate the object after all the definitions, there should be no
problem.
|
I don't understand that. A class definition
class A
{
};
does not require space in itself, but it is required to instantiate objects
because the compiler needs the size of the class.
class A;
int main()
{
A *a = new A; // how many bytes?
delete a; // ditto
}
Since all pointers are of the same size (excluding member function
pointers), you only need to declare the name you are using.
class A;
A *p;
That's ok, because the compiler knows the size of 'A*' (typically 4 bytes),
but
class A;
A a;
is not not, because the compiler needs the size of A, which depends on its
members.
| Quote: | 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.
But the compiler requires the definitions when these are not intrinsically
required. A definition is a model, not a physical object and thus does not
require space.
|
The compiler needs the space for the object, not for the class.
Jonathan
|
|
| Back to top |
|
|
Jonathan Mcdougall
Guest
|
| Posted: Sun Jan 02, 2005 6:18 pm Post subject: Re: Semi-circular definitions (plus circular references) |
|
|
"Kiuhnm" <kiuhnm03 (AT) yahoo (DOT) it.invalid> a écrit dans le message de news:
p_FBd.354060$b5.17419989 (AT) news3 (DOT) tin.it...
| Quote: | Dave Rahardja wrote:
[cut]
compilation (beyond the preprocessor stage), increase compile times, and
would lead to confusing paradoxes like this:
class A { B b; };
class B { A a; };
Which the compiler must detect.
There are many methods to minimize the increase in compilation time. The
compiler could use a graph only when needed or in the presence of a hint
(e.g. a special forward declaration).
|
The language forbids that and the compiler would be non compliant.,
| Quote: | In C and C++, you can define a pointer (or a reference) to an undefined
(but declared) entity because the size of a pointer is known. You cannot
use an undefined data structure as a member of another because the
compiler needs to know how much space to allocate for the data storage.
This is not completely exact: a definition does not require space.
|
You understanding of classes and objects seems to be flawed. A class does
not take memory, only objects do.
class A
{
}; // no memory
int main()
{
A a; // 1 byte of memory
}
| Quote: | And if all the definitions appear before the first instantiation...
|
What?
Jonathan
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
