Design Problem: "Smart Paramaters"

[Michael Olea]

Here is a design problem I ran into this am - and I have cleaned the
bathroom,
scrubbed toilet sink and tub, windexed all glass, mopped the floor, and
vacuumed the house - no dice, the problem is still there. Maybe y'all have
some ideas?

Background
==========

The basic idea behind templates, of course, is that much code is independent
of the data types it works on: the basic operations of a doubly linked list,
for example, are identical whether it is a list of donuts or a list of cops.
Rather than duplicate the code for each list of items of type T we just
create a template for all lists independently of type by writing the list
in terms of a template argument: template<typename T> class DList, using T
wherever we normally would use a specific concrete data type - we let the
compiler duplicate the code. So far so good (ignoring "code bloat" issues
here).

But in truth we do not always want the code *entirely* independent of the
types it works on. A case in point is how we pass read-only paramaters to
functions (and to member functions). For "big" types (or types that are
expensive to construct) we want to pass a const reference, for other types
we would prefer to pass them by value - more efficient that way. So the
only difference, in this scenario, is how we declare function arguments.

A Solution?
===========
Vandervoode and Josuttis discuss, in C++ Templates: The Complete Guide, a
way out. My (very simple and nearly verbatim copied) implimentation is:

template<typename T>
class TROM
{
public:
typedef typename IfElse< sizeof(T) <= 2 * sizeof(void *),
T,
T const&>::Type Type;
};

Where IfElse is a "type function" that "returns" its second argument if the
first argument evaluates to true, its third argument otherwise:

template<bool C, typename T1, typename T2> class IfElse;
template<typename T1, typename T2> class IfElse<true, T1, T2>
{ public: typedef T1 Type; };
template<typename T1, typename T2> class IfElse<false, T1, T2>
{ public: typedef T2 Type; };

Now, I know TROM is naive in that a class or struct might be "small" yet
expensive to construct - that is not the issue here.

The Problem
===========
The prolem arises when some member functions of a class take instances of
the class itself as arguments:

struct XTest
{
unsigned int x;
void DoOr(typename TROM<XTest>::Type src) {x |= src.x;}
};

This fails to compile:
....
/usr/home/olea/binfosys/operations/base/include/binfosys/trom.h:44: `sizeof'
applied to incomplete type `XTest'

In this particular case I don't need TROM to tell me to pass XTest by value,
not by const reference, but if instead of "unsigned int" I use type T I do
need it:

template <typename T>
struct XTest
{
T x;
void DoOr(typename TROM<XTest<T> >::Type src) {x |= src.x;}
};

Any ideas?

Thanks for your consideration - Michael

ps:
tayfun.2wire.net.olea (118) g++ -v
Using built-in specs.
Configured with: FreeBSD/i386 system compiler
Thread model: posix
gcc version 3.2.2 [FreeBSD] 20030205 (release)

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

[Manvel Avetisian]

Just add parameter, describing your class to TROM:

// T -- parameter type
// C -- our class type
template<class T,class C>
class TROM {
typedef typename IfElse< sizeof(T) <= 2 * sizeof(void *),
T,
T const&>::Type Type;
};

// and if type of parameter and type of our class is equal -- result is
// reference to class
template<typename C>
class TROM<C,C>
{
public:
typedef C& Type;
};

[Michael Olea]

Manvel Avetisian wrote:

Just add parameter, describing your class to TROM:

// T -- parameter type
// C -- our class type
template<class T,class C>
class TROM {
typedef typename IfElse< sizeof(T) <= 2 * sizeof(void *),
T,
T const&>::Type
Type;
};

// and if type of parameter and type of our class is equal -- result is
// reference to class
template<typename C>
class TROM<C,C>
{
public:
typedef C& Type;
};

I don't think I described the problem very clearly last night, but this
reply did give me an idea for a work-around:

//
// TCROM: A workaround version of TROM for the special case of classes
// that have member functions that take instances of themselves as
// arguments: class X { ... void Foo(const X&); ...}; - call by referene,
// or class X { ... void Foo(X); ...}; - call by value. The problem with
// using TROM in this case: void Foo(typename TROM<X>::Type) is that at
// this point X is an "incomplete type", and the sizeof test above fails.
// The solution here is to pass TCROM a "storage type" T, which is a
complete
// type, and the class type C. If T is small then we "return" C, otherwise
// we return C const&.
//
template<typename T, class C>
class TCROM
{
public:
typedef typename IfElse< sizeof(T) <= 2 * sizeof(void *),
C,
C const&>::Type Type;
};

[Swampmonster]

Michael Olea wrote:

template<typename T>
class TROM
{
public:
typedef typename IfElse< sizeof(T) <= 2 * sizeof(void *),
T,
T const&>::Type Type;
};
....
template<bool C, typename T1, typename T2> class IfElse;
template<typename T1, typename T2> class IfElse<true, T1, T2>
{ public: typedef T1 Type; };
template<typename T1, typename T2> class IfElse<false, T1, T2>
{ public: typedef T2 Type; };
....
template <typename T>
struct XTest
{
T x;
void DoOr(typename TROM<XTest<T> >::Type src) {x |= src.x;}
};

Any ideas?

Well, to take the size of "XTest<T>" (which "TROM<XTest<T> >" does), the
compiler has to instantiate the template "XTest<T>". Since instantiating
"XTest<T>" requires knowing (taking) the size of "XTest<T>" that's
infinite recursion - even if you rewrite it so that the "incomplete
type" error goes away (*a).
So you can only use the size of something else.

You could add an additional template parameter that tells the template
whether to use references to itself or copies or automatically decide
what to use. The first two versions can be implemented whithout
recursion, and the "auto" version could e.g. use the size of the "by
reference" version to decide what parameter-type to use.

---

*a: Which is possible by adding a "static const MySize" in "XTest<T>"
and make "TROM" use "T::MySize" instead of "sizeof(T)". The code would
look like the following, which also makes the recursion pretty clear:

template<typename T>
class TROM
{
public:
typedef typename IfElse< T::MySize <= 2 * sizeof(void *),
....
template <typename T, size_t S = sizeof(XTest<T>)>
struct XTest
{
static const MySize = S;
....

Here you could break the recursion by changing "size_t S =
sizeof(XTest<T>)" to "size_t S = sizeof(XTest<T,0>)" which should have
the effect that the size of the "by-value" version is used to decide
which version to instantiate.

bye, Paul

[Graeme Prentice]

On 6 Jun 2005 05:25:24 -0400, Michael Olea wrote:

This fails to compile:
...
/usr/home/olea/binfosys/operations/base/include/binfosys/trom.h:44: `sizeof'
applied to incomplete type `XTest'

In this particular case I don't need TROM to tell me to pass XTest by value,
not by const reference, but if instead of "unsigned int" I use type T I do
need it:

template <typename T>
struct XTest
{
T x;
void DoOr(typename TROM<XTest<T> >::Type src) {x |= src.x;}
};

Any ideas?

Since you're using TROM to select the function parameter type based on
the size of XTest<T> (which doesn't work because the size of XTest<T> is
unknown until the compiler comes to the end of the class definition
(during instantiation)), you can instead pass the size of XTest<T>
member x to a NewTROM template

template<typename T, size_t size>
class NewTROM
{
public:
typedef typename IfElse< size <= 2 * sizeof(void *),
T,
T const&>::Type Type;
};
void DoOr(typename TROM<XTest<T>,sizeof(x) >::Type src) {x |= src.x;}

because in this case, you know roughly how to calculate the size of
XTest<T>.
A couple of things to note : member functions of a class can have a
parameter type that is an incomplete class only if the class in question
is the class the function is a member of. Data members of a class
cannot have zero size even if their type is an empty class. You might
have to calculate an amount to allow for packing.

To overcome the unknown packing size allowance, you can create a "mirror
class" and use that to get the size i.e.
template <typename T>
struct XTestMirror
{
T x;
};

void DoOr(typename TROM<XTest<T>,sizeof(XTestMirror<T>) >::Type src)
{x |= src.x;}

and hope that the mirror class has the same size as its counterpart.
With some effort, you may be able to automatically check that
sizeof(XTest<T>) is the same as sizeof(XTestMirror<T>) e.g. by using a
static data member of XTest<T> whose definition follows the XTest class
and whose initializer uses sizeof(XTest<T>) == sizeof(XTestMirror<T>) in
a way that causes a compile time error if not equal.

Graeme

[Michael Olea]

Graeme Prentice wrote:

On 6 Jun 2005 05:25:24 -0400, Michael Olea wrote:

This fails to compile:
...
/usr/home/olea/binfosys/operations/base/include/binfosys/trom.h:44:
`sizeof'
applied to incomplete type `XTest'

In this particular case I don't need TROM to tell me to pass XTest by
value, not by const reference, but if instead of "unsigned int" I use type
T I do need it:

template <typename T>
struct XTest
{
T x;
void DoOr(typename TROM<XTest<T> >::Type src) {x |= src.x;}
};

Any ideas?

Since you're using TROM to select the function parameter type based on
the size of XTest<T> (which doesn't work because the size of XTest<T> is
unknown until the compiler comes to the end of the class definition
(during instantiation)), you can instead pass the size of XTest<T>
member x to a NewTROM template

template<typename T, size_t size>
class NewTROM
{
public:
typedef typename IfElse< size <= 2 * sizeof(void *),
T,
T const&>::Type Type;
};
void DoOr(typename TROM<XTest<T>,sizeof(x) >::Type src) {x |= src.x;}

because in this case, you know roughly how to calculate the size of
XTest<T>.
A couple of things to note : member functions of a class can have a
parameter type that is an incomplete class only if the class in question
is the class the function is a member of. Data members of a class
cannot have zero size even if their type is an empty class. You might
have to calculate an amount to allow for packing.

To overcome the unknown packing size allowance, you can create a "mirror
class" and use that to get the size i.e.
template <typename T>
struct XTestMirror
{
T x;
};

void DoOr(typename TROM<XTest<T>,sizeof(XTestMirror<T>) >::Type src)
{x |= src.x;}

and hope that the mirror class has the same size as its counterpart.
With some effort, you may be able to automatically check that
sizeof(XTest<T>) is the same as sizeof(XTestMirror<T>) e.g. by using a
static data member of XTest<T> whose definition follows the XTest class
and whose initializer uses sizeof(XTest<T>) == sizeof(XTestMirror<T>) in
a way that causes a compile time error if not equal.

Graeme

Thanks for the suggestions. NewTROM is similar to what I ended up doing:

template<typename T, class C>
class TCROM
{
public:
typedef typename IfElse< sizeof(T) <= 2 * sizeof(void *),
C,
C const&>::Type Type;
};

The idea is that T is a "storage type" for C. I'll have to look more closely
at the "unknown packing" issues. I was assuming that given:

template<typename A, typename B, typename C...>
struct Store
{
A anA;
B aB;
C aC;
...
};

template<typename A, typename B, typename C...>
class X
{
Store<A,B,C...> myStorage;
};

that sizeof(Store<A,B,C...>) would equal sizeof(X<A,B,C...>)
but I suppose that need not be the case.

Thanks again for the comments.
- Michael