[cppx] How to avoid disastrous integer wrap-around

The time is 65535:65535 PM, and the temperature is a nice comfy 4294967295 degrees… Oops. Clearly some signed integer values have been promoted to unsigned somewhere, or perhaps the program has just used unsigned integer arithmetic incorrectly.

There are two main cures for that:

• make sure that you’re only using unsigned arithmetic in expressions that involve unsigned type numerical values, or …
• make sure that you’re only using signed arithmetic in expressions that involve unsigned type numerical values.

As of 2010 most programmers still choose the first cure, attempting to use unsigned arithmetic wherever there are unsigned numerical values involved, e.g. being careful to use size_t instead of int for some loop counter. I think the main reason is that it’s an old convention (which is propagated by e.g. the C++ standard library), a case of “frozen history”, but it may also have something to do with each intrusion of unsigned numerical values being viewed as a purely local problem, suggesting that a purely local fix, each time, is appropriate. This then leads to a bug-attracting mix of signed and unsigned type expression, which moreover are difficult to recognize as respectively signed and unsigned type, and are easy to get wrong.

Here I’m advocating the second cure, a single global convention: do not mix signed and unsigned numerical types. The unsigned types are for bit-level operations (only), while the signed types are for numerical values (only). But since the standard library was designed before the advantages of this clear usage separation were fully realized, and indeed at a time when some computer architectures still conferred some advantages to e.g. an unsigned size(), adopting this more rational and work-saving convention requires some support.

A signed size type

It’s only on a 32-bit architecture that int can be safe instead of size_t. In particular, in 64-bit Windows long int is 32-bit while size_t is 64-bit, although in 64-bit *nix long int is typically 64-bit (see e.g. Wikipedia). Hence, some other signed type is needed for sizes and indexes, and that type is the standard library’s ptrdiff_t. It’s guaranteed to be large enough for any array except for an array of char filling more than half of the available address space. And that single special case is not only so rare as to not occur in practice, at all (except possibly for some embedded computer programming); it’s also a case that’s simply not fully supported by current C++.

The standard library defines two types, size_t and ptrdiff_t, not only to provide a choice between signed and unsigned but because these types are used differently: the names indicate different usages. size_t is used for sizes, corresponding to the cppx Size type below. And ptrdiff_t is used for array indices and pointer offsets, corresponding to the cppx Index type below.

In [progrock/cppx/primitive_types.h]:

namespace progrock{ namespace cppx{
    // Some more stuff (e.g. definition of Byte) first, then ...

    namespace signedSize
    {
        CPPX_STATIC_ASSERT( sizeof( size_t ) == sizeof( ptrdiff_t ) );

        typedef ptrdiff_t   T;
        enum
        {
            maximum = ptrdiff_t( size_t( -1 ) / 2 ),
            minimum = -maximum - 1      // Assumes two's complement form.
        };

        // Assert that at least ptrdiff_t is two's complement form. This assertion
        // is stronger, asserting also that there's no bounds checking. But AFAIK
        // it's all that's available from the standard library.
        CPPX_STATIC_ASSERT( std::numeric_limits<T>::is_modulo );
    }  // namespace signedSize

    typedef signedSize::T   Size;
    typedef signedSize::T   Index;

} }  // namespace progrock::cppx

Wrapper functions

C-style casts are generally bad, e.g. easily hiding or inadvertently introducing some reinterpretation or const-casting, so writing Size(v.size()) is ungood. And C++-style casts are verbose, so writing static_cast<Size>(v.size()) is also ungood. Hence, a wrapper function is called for, writing just size(v) :-).

Wrapper functions for size- and indexing- related things also allow you to treat raw arrays and container classes in a uniform way, writing e.g. just endOf(a), instead of a+sizeof(a)/sizeof(*a) if a is a raw array and a.end() if a is e.g. a std::vector. Similarly, in cppx I define a startOf function. These names are intentionally slightly unlike begin and end, so as to avoid any confusion (for size I found it difficult to come up with some different name, though):

In [progrock/cppx/collections/iterator_range_util.h]:

namespace progrock{ namespace cppx{

    template< typename T >
    inline Size size( T const& c )              { return static_cast<Size>( c.size() ); }

    template< typename T, Size N >
    inline Size size( T (&)[N] )                { return N; }

    template< typename T >
    inline typename It<T>::T startOf( T& c )    { return c.begin(); }

    template< typename T, Size N >
    inline T* startOf( T (&a)[N] )              { return a; }

    template< typename T >
    inline typename It<T>::T endOf( T& c )      { return c.end(); }

    template< typename T, Size N >
    inline T* endOf( T (&a)[N] )                { return a + N; }

    #define CPPX_ALL_OF( v )   \
        ::progrock::cppx::startOf( v), ::progrock::cppx::endOf( v )

} }  // namespace progrock::cppx

It’s possible to redesign size so that it can be used at compile time, then wrapped via a macro, but although it’s an interesting academic exercise I have never needed that in practice, and the necessary macro for that complicates things. Another limitation is that with C++98 these functions can’t be used for locally defined classes, since in C++98 such classes have no linkage and template instantiation requires external linkage. However, like the first point this is not a problem in practice, and anyway as I understand it it’s been fixed in C++0x.

Summing up, with the above you can write e.g. for (Index i = size(s)-1; i >= 0; --i), and other such natural constructions, with no fear of value wrapping bugs. 🙂

Automatic iterator type deduction

For e.g. a std::vector<int> const the startOf and endOf functions above automatically deduce the proper iterator type, via the cppx It utility class template:

In [progrock/cppx/collections/It.h]:

namespace progrock{ namespace cppx{

    template< typename Type >
    struct It
    {
        typedef typename Type::iterator T;
    };

    template< typename Type >
    struct It< Type const >
    {
        typedef typename Type::const_iterator T;
    };

    template< typename ElemType, Size N >
    struct It< ElemType[N] >
    {
        typedef ElemType* T;
    };

} }  // namespace progrock::cppx

Cheers, & … enjoy! 🙂