Professionally, I develop primarily in Ada. When I do get a chance to program in C++, I miss some of the features that Ada provides. Ranged types is one of these features. Ada allows the programmer to constrain a numerical type to a particular range. Intermediate expression results are allowed to exceed the range, but an exception is raised if an attempt is made to assign an out-of-range value to a variable. An exception is also raised if a result of an expression overflows the bounds of the ranged type's base type. This article details a class template I have created to implement a C++ type with similar behavior.
Design Goals
One requirement I have for the class is that it must be written in strictly conforming Standard C++. This conflicts with the desire that the code be efficient as possible. Checking for overflow in C++ without resorting to inline assembly can be expensive. One of the reasons Ada has efficient ranged checked types is because these types are part of the language. An Ada compiler can analyze the code and remove those checks that are unnecessary. I decided to implement this behavior in my class using templates. What is needed is a method to determine at compile-time if a given mathematical operation can overflow.
The possible occurrence of two conditions needs to be determined at compile-time. These conditions are overflow and out-of-range. Overflow occurs when the result of an operation exceeds the limits of the primitive used in defining the ranged type. An out-of-range condition occurs when an attempt is made to assign a value to a variable that is outside the bounds of the variable's defined range.
Method of Analysis
The simplest condition is out-of-range. This is merely a matter of checking that the constructor is only called with values within the allowed range. The bounds of the argument type dictate whether checks are made. If either the upper or lower bound of the type is within the range, the check is removed. For example, assume the range of type signed char is [-128, 127]. If a variable with a range of [0, 65536] is constructed with a value of type signed char, only the lower bound would be checked. Since the value cannot exceed the variable's upper bound, the check can be removed.
The more thorny issue is how to determine if an overflow is possible. Keeping track of the maximum range resulting from an operation is one possible way. For example, if two variables of a type with the range [-100, 100] are multiplied, then the resulting range is [-10000, 10000]. Any possibility of overflow may be determined by doing this for each sub-expression. This is messy and overly complex, because it requires overflow checking when calculating each new range.
There is an easier way. Instead of keeping track of maximum and minimum range values, the code keeps track of the maximum possible digits. Ignoring the sign bit, a variable with the range [-100, 100] will have a maximum of 7 binary digits. The maximum resulting binary digits may be determined for every mathematical operation. Multiplying two numbers, each with a maximum of 7 binary digits, creates a product with at most 14 binary digits. So, for each sub-expression: 1) calculate the maximum digits required to hold the result, based on the maximum digits of each operand and the type of operation; 2) locate a primitive type with the same signedness as the base type that will hold a value of at least the resulting number of digits; 3) if the implementation has no such primitive type, flag the operation as having a possibility of overflowing; 4) do the operation, checking for overflow if necessary. Obviously, this method only works for integral types. So, currently floating point types are not supported.
