Using templates to enforce compile-time bounds checking

[Dave Rahardja]

I have the following program that uses an array of chars to simulate a bit
set:

---------

// An out-of-bounds exception
class BoundsException {};

template <int bits = 1>
class Bitset
{
public:

Bitset()
{
// Clear all the bits in the bit flag bytes
for (int i = 0; i < charCount; ++i) {
bitFlags = 0;
}
}

// Sets a bit in the bitset.
void set(int bit)
{
if (bit >= bits || bit < 0) {
throw BoundsException();
}
int byteNum = bit / 8;
int bitNum = bit % 8;
bitFlags[byteNum] |= (1 << bitNum);
}

private:
static const int charCount = (bits + 7) / 8;
unsigned char bitFlags[charCount];
};

int main()
{
Bitset<9> bitset9;
bitset9.set(0); // OK
bitset9.set(-1); // BoundsException thrown

bitset9.set(8); // OK
bitset9.set(9); // BoundsException thrown

return 0;
}

---------

As you can see, I'm using runtime checks to bounds-check the bit number each
time set() is called.

However, it turns out that set() will only receive compile-time constants, and
never runtime computed values.

Is there a way to perform _compile-time_ bounds checking for the indexes? A
little template trickery maybe?

-dr

 

[Bob Hairgrove]

I have the following program that uses an array of chars to simulate a bit
set:

---------

// An out-of-bounds exception
class BoundsException {};

template <int bits = 1>
class Bitset
{
public:

Bitset()
{
// Clear all the bits in the bit flag bytes
for (int i = 0; i < charCount; ++i) {
bitFlags = 0;
}
}

// Sets a bit in the bitset.
void set(int bit)
{
if (bit >= bits || bit < 0) {
throw BoundsException();
}
int byteNum = bit / 8;
int bitNum = bit % 8;
bitFlags[byteNum] |= (1 << bitNum);
}

private:
static const int charCount = (bits + 7) / 8;
unsigned char bitFlags[charCount];
};

int main()
{
Bitset<9> bitset9;
bitset9.set(0); // OK
bitset9.set(-1); // BoundsException thrown

bitset9.set(8); // OK
bitset9.set(9); // BoundsException thrown

return 0;
}

---------

As you can see, I'm using runtime checks to bounds-check the bit number each
time set() is called.

However, it turns out that set() will only receive compile-time constants, and
never runtime computed values.

Is there a way to perform _compile-time_ bounds checking for the indexes? A
little template trickery maybe?

-dr

First of all, there is std::bitset<size_t> as well as
std::vector<bool>. No need to re-invent the wheel here.

Not sure about your last question -- runtime and compile-time are two
orthogonal concepts, actually they are somewhat diametrically opposed.
It seems that you would like to have your cake and eat it, too. If you
want to use runtime values to create a bitset, you have to allocate
the memory dynamically. You could do this if you implement the storage
as a vector and not as an array.

BTW, there are standard exception classes in <stdexcept> you could use
instead of your own BoundsException (std:ut_of_range or
std::invalid_argument come to mind). You could also inherit
BoundsException from one of these, or from std::exception.

 

[peter steiner]

However, it turns out that set() will only receive compile-time constants, and

never runtime computed values.

Is there a way to perform _compile-time_ bounds checking for the indexes? A
little template trickery maybe?

a simple compile time check could be performed with the following set()
variant:

template <int bits = 1>
class Bitset
{
public:
...
// Sets a bit in the bitset.
template <int bit>
void set()
{
static char check_bounds__[(bit >= bits || bit < 0) ? 0 : 1];
int byteNum = bit / 8;
int bitNum = bit % 8;
bitFlags[byteNum] |= (1 << bitNum);
}
...
}

int main()
{
Bitset<9> bitset9;
bitset9.set<0>(); // OK
bitset9.set<-1>(); // compile time error

bitset9.set<8>(); // OK
bitset9.set<9>(); // compile time error
return 0;

}

this is a template trick that relies on the compiler evaluating the
array size expression at compile time, and complaining about an illegal
size of 0.

maybe you should have a look at BOOST_STATIC_ASSERT for a portable and
more fletched out variant of static assertion.

see http://www.boost.org/doc/html/boost_staticassert.html

-- peter

 

[Gianni Mariani]

Dave Rahardja wrote:

See the code I added.

// An out-of-bounds exception
class BoundsException {};

template <int bits = 1>
class Bitset
{
public:

Bitset()
{
// Clear all the bits in the bit flag bytes
for (int i = 0; i < charCount; ++i) {
bitFlags = 0;
}
}

// Sets a bit in the bitset.
void set(int bit)
{
if (bit >= bits || bit < 0) {
throw BoundsException();
}
int byteNum = bit / 8;
int bitNum = bit % 8;
bitFlags[byteNum] |= (1 << bitNum);
}

template <int N>
void set()
{
static_assert( (N<=bits) && (N>=0) );
set( N );
}

private:
static const int charCount = (bits + 7) / 8;
unsigned char bitFlags[charCount];
};

int main()
{
Bitset<9> bitset9;
bitset9.set(0); // OK

bitset9.set(-1); // BoundsException thrown

bitset9.set(8); // OK

bitset9.set(9); // BoundsException thrown

return 0;
}

---------

As you can see, I'm using runtime checks to bounds-check the bit number each
time set() is called.

However, it turns out that set() will only receive compile-time constants, and
never runtime computed values.

Is there a way to perform _compile-time_ bounds checking for the indexes? A
little template trickery maybe?

You need to change the parameter and make it a template parameter. You
can either do it by passing a special type or by passing a parameter
specifically.

Anything you can catch at compile time is better than catching at run-time.

 

[Dave Rahardja]

static char check_bounds__[(bit >= bits || bit < 0) ? 0 : 1];
....

this is a template trick that relies on the compiler evaluating the
array size expression at compile time, and complaining about an illegal
size of 0.

Nice! This is just what I'm looking for.

maybe you should have a look at BOOST_STATIC_ASSERT for a portable and
more fletched out variant of static assertion.

Right.

Thanks to all the other posters who suggested using the std::bitset and
std::vector<bool> implementations, but I'm writing code for an embedded
product for which the STL implementations are overkill. All the code I posted
is virtually all that's needed.

Besides, I'm still going to resort to a similar trick to make the std::
containers provide me compile-time checks.

-dr