[boost] Automated Specializations? Choosing Integers? Maybe generic meta-programming

From: scleary_at_[hidden]
Date: 1999-11-29 17:06:24

Note to casual readers: this post is going to be long.  It is also going to
be controversial.  The attached code brings up topics of contention that
have previously been discussed and never resolved.  Read at your own risk!
:)

A long time ago, in a computer far, far away. . . I was just fooling around
and I thought that writing a restricted integer class would be cool.
Basically, what I wanted was to specify the exact number of bits in the
representation, and declare it signed or unsigned.  So I began writing the
"bit_int" class, which turned out to be a bit more of a challenge than I
first thought.

Kevlin Henney had written a similar class, named "exact", which he sent to
me (thanks, Kevlin!).  The only thing I didn't like about "exact" was that
you had to specify the underlying integer type for the bit field as well as
the number of bits.  I wanted a class that would derive its own underlying
integer type, and refuse to compile if it didn't exist.  My "bit_int" class
quickly grew more and more complicated.

About that time (or maybe it was before then), there was some discussion
here about how to choose integers at compile-time (and I downloaded and
evaluated Valentin's Int Choosers lib).  Obviously, these problems were
similar.  The only thing I didn't like about Valentin's int choosers was
that they were not easily extendable to compiler extensions -- for example,
GNU's "long long" or Borland's "__int64".

So I decided to separate the integer choosing from my "bit_int" class and
make it more general-purpose.  And thus started my long journey into what
turned out to be compiler meta-programming (with which I had had no previous
experience).  The next 2 or 3 working versions of "bit_int" and my int
choosers were still fairly hacked, and I won't describe the dead-ends I
tried; let's skip to the current solution.

In order to easily allow compiler extensions, I finally separated the list
of valid types out into a structure, which satisfies "Platform"
requirements.  I ended up requiring "Platform" to have two "compile-time
doubly-linked lists", one for signed and one for unsigned integers.  (Please
note that this is still fairly hacked).  I also ended up writing a
compile-time generic algorithm - the "find" algorithm, and also wrote
requirements for compile-time predicates, compile-time iterators, and
compile-time bidirectional iterators.

When this level of genericity (is that a word? :) had been reached, I simply
have my "bit_int" class find an integer of the correct sign that had at
least a certain number of bits.  The int choosers also become almost
trivial, just declaring a proper predicate and using the compile-time find
to "return" the correct type.

So how about it?  I think we will have to eventually at least get our feet
wet with compile-time meta-programming in the Boost library.  There are
several situations where it is very useful; the one that prompted this post
is the one to automate specializations.  By using the Platform concept, we
can write one specialization for every builtin type, and only have to change
the corresponding platform class when compilers offer more extended types
(__int128 is coming!)

The controversial subjects here are the use of meta-programming and
compile-time asserts.  Meta-programming has already been brought up here,
with the consensus that we did not wish to pursue it for Boost at this time.
Compile-time asserts have been thrown around a _lot_, with no known solution
to the problems raised.  The compile-time assert I include here is the one I
use in my personal programming; it works with BCB4, but maybe nothing else.
. .

The rest of this post deals mainly with explaining the code.  The "bit_int"
class mentioned above is not included.  I just mentioned it so you could see
where I was originally coming from.

-- ChooseInt.h --
The structures in this file choose an integer type based on a number of bits
or a size (in characters), and may match either exactly or "at least" that
number.  The structure "xxx" determines if its second argument is "signed"
or "unsigned" and passes this information on to "xxx_helper".  "xxx_helper"
will traverse one of the compile-time doubly-linked-lists on Platform,
searching for a type satisfying "xxx_pred", which is the predicate for that
integer search.  "xxx" will return "void" if a type is not found (note that
this is the default return value for compile-time find if the predicate is
never satisfied becuase this is the dereference value of the past-the-end
compile-time iterator)

-- CTAssert.h --
The ct_assert is the compile-time assertion.  A simple class, but due to
compiler variancies in when templates are instantiated, it cannot be
depended on to work portably.

-- CTFind.h --
The comments at the top of this file should be useful; they outline the
requirements for compile-time iterators, bidirectional iterators,
containers, predicates, and the ct_find_if algorithm.  This file is the most
generic of any of the code.

-- CTLogical.h --
This file contains some simple structures because Borland C++ Builder 4.0
will often choke if these are in templated classes without being wrapped
like this.  In other words, it's a workaround.

-- Platform.h --
Defines the generic platform.  I also have a platform class for BCB4, if
anyone is interested.

-- PlatformTest.h --
A simple test; more of an example of how to use ct_find_if than anything
else.  Does NOT use ChooseInt.h (though it shows the simple concept all
structures in ChooseInt.h are based on).