One of the most common software bugs is the humble buffer overflow. In its simplest form this can happen when an array is accessed out of bounds:
1 | int arr[5]; 2 | 3 | int foo(int i) { 4 | return arr[i]; 5 | } 6 | 7 | int main() { 8 | return foo(5); 9 | }
The code above causes 🌩Undefined Behavior🌩TM (or UB for short). That is to say that a standard-compliant compiler can produce code that does literally anything. Roughly speaking this is to give the compiler more leeway in making aggressive optimizations: it means that it can assume UB never happens and optimize the code based on that assumption.
So more likely than not foo will simply compile to
machine code that reads and returns the memory at
&arr + i (in fact you can click the little green
“Run”-button in the corner of the code to see that clang’s codegen goes
exactly that). Since the array only occupies memory up to
&arr + 4, calling foo like above will try
to read the memory of whatever object the compiler decided to place
after arr. If that object is always the same, then
executing the binary will consistently produce the same return code. Or
maybe there is no object after arr and the address right
after arr is not mapped to a region that the created
process is allowed to read, resulting in a SEGFAULT.
# std::array
In this respect C-style arrays are considered unsafe, and many
“modern” C++ style guides suggest using std::array instead.
Objects of this type implement the at function which checks
that the supplied index is within the bounds of the array. If it isn’t,
it throws an exception.
1 | #include <array> 2 | 3 | std::array<int, 5> arr; 4 | 5 | int foo(int i) { 6 | return arr.at(i); 7 | } 8 | 9 | int main() { 10 | return foo(5); 11 | }
Now the program will (predictably!) fail; And of course we could add
error handling by catching the exception. Somewhat annoyingly though,
there are also lots of folks who consider using exceptions at all to be
bad
practice. If we compile the code with clang and
-fno-exceptions the code above will still compile (and
still fail) but whenever any element is accessed out of bounds, the
program will call abort killing the process and precluding
any error handling.
And besides, who wants bounds checks anyway? We are writing C++ after all. What we want is performance! Every unnecessary CPU cycle brings dishonor to us and our family.
When iterating such an array the fancy new type can still help us out. Using a range based for-loop allows us to access all array elements without bounds checking, and the guarantee that we don’t overflow the buffer.
1 | #include <array> 2 | 3 | std::array<int, 5> arr; 4 | 5 | int sum() { 6 | int x = 0; 7 | for (int el : arr) { 8 | x += el; 9 | } 10 | 11 | return x; 12 | }
But what about accessing just a single element? In some other
languages it is possible to create integer subtypes, where only certain
values allowed. Then the api for array accesses could explicitly take
only elements of that subtype; let’s call it
InRange<T, n, m>, where T is an integral
type, and n and m are of type T.
These objects then carry a value of type T that is somehow
guaranteed to be >= n and < m. Leaving
aside the question of how to implement this behavior for now, this is
what array’s subscript operator could look like:
1 | #include <cstddef> 2 | 3 | template<typename T, T n, T m> 4 | class InRange; 5 | 6 | template<typename T, size_t n> 7 | class safe_array { 8 | //... 9 | public: 10 | T& operator[](InRange<size_t, 0, n> x) { 11 | return data[x]; 12 | } 13 | //... 14 | private: 15 | T data[n]; 16 | };
Another way of thinking about this is that we are encoding a precondition
of safe_array’s subscript operator in the type system. So
how can we design InRange to guarantee this implied
precondition? Ideally we would want to be able to use it just like the
integral type T that it is built on top of, i.e. being able
to do arithmetic, performing comparisons, etc.
# Constraining the argument
For one thing whenever we create a new InRange object or
assign to an existing one from an arbitrary integer we need to obviously
check that the constraint is satisfied:
1 | template<typename T, T n, T m>
2 | class InRange {
3 | using Self = InRange<T, n, m>;
4 | public:
5 | InRange(T value) : x(value) {
6 | if (!check_constraint(value))
7 | throw 1;
8 | }
9 | Self& operator=(T value) {
10 | if (!check_constraint(value))
11 | throw 1;
12 | x = value;
13 | return *this;
14 | }
15 |
16 | private:
17 | static bool check_constraint(T x) {
18 | return (x >= n && x < m);
19 | }
20 | T x;
21 | };With the single-argument constructor objects of type T
can now also implicitly convert to InRange<T, ...> ,
meaning the introductory example already almost works with our custom
integer subtype. The only thing missing is some way of retrieving the
x from within InRange. By adding a conversion
operator back to T we can both fix this and partly achieve
our objective of being able to use InRange<T, ...>
just like T:
1 | operator T() {
2 | return x;
3 | }The code below will now compile:
1 | #include "in_range_naive.h" 2 | 3 | safe_array<int, 5> arr; 4 | 5 | int main() { 6 | InRange<int, 0, 5> var(3); 7 | var = var + 1; 8 | return arr[5] + var; 9 | }
… however, we still have all the same problems as with
std::array and .at: a runtime check takes
place when the 5 is implicitly converted to
InRange<size_t, 0, 5>, and when it fails an exception
is thrown that has to either be caught or else the process will
terminate.
We also have runtime checks on the creation of, and assignment to
var. While any half-descent optimizer will likely be able
to get rid of these here (after all the compiler can see all the integer
literals involved in the calculations) this is not always the case and
we would like a stronger guarantee that the information available at
compile-time is in fact used to eliminate unnecessary checks.
Ideally it should also realize at compile-time that the
access to arr[5] is illegal, refusing to compile, instead
of throwing an exception at run-time.
# Compile-time checks
Since C++ 20 there is a very simple solution: add the
consteval keyword to the constructor, and assignment
operator of InRange:
1 | template<typename T, T n, T m>
2 | class InRange {
3 | using Self = InRange<T, n, m>;
4 | public:
5 | consteval InRange(T value) : x(value) {
6 | if (!check_constraint(value))
7 | throw 1;
8 | }
9 | consteval Self& operator=(T value) {
10 | if (!check_constraint(value))
11 | throw 1;
12 | x = value;
13 | return *this;
14 | }
15 |
16 | private:
17 | constexpr bool check_constraint(T x) {
18 | return (x >= n && x < m);
19 | }
20 | T x;
21 | };This guarantees that the functions will be called at a compile time, and when it throws this results in a compilation failure. Try compiling the same code as before in compiler explorer; this time with our new implementation:
1 | #include "in_range.h" 2 | 3 | safe_array<int, 5> arr; 4 | 5 | int main() { 6 | InRange<int, 0, 5> var(3); 7 | return arr[5] + var; 8 | }
Right now we are getting an error, but if you change
arr[5] to arr[4] the code will compile
successfully, and there are no runtime checks involved.
We can make sure of it by simplifying to the (now correct version of the) introductory example and looking at the generated assembly (I’m showing arm assembly because that’s what I’m most used to, but you can switch to x86 or whatever isa you prefer in compiler explorer):
1 | #include "in_range.h" 2 | 3 | safe_array<int, 5> arr; 4 | 5 | int foo(InRange<size_t, 0, 5> i) { 6 | return arr[i]; 7 | }
1 | foo(InRange<unsigned int, 0u, 5u>): 2 | ldr r1, .LCPI0_0 3 | .LPC0_0: 4 | add r1, pc, r1 5 | ldr r0, [r1, r0, lsl #2] 6 | bx lr 7 | .LCPI0_0: 8 | .long arr-(.LPC0_0+8) 9 | 10 | arr: 11 | .zero 20
The first two ldr and add instructions load
the address of arr into r0. Then that memory
is read at an offset based on the value of i (coming from
r0; the lsl #2 multiplies the offset by 4
which is the size of an int) and the result is
returned.
This is in fact exactly the same code that is generated for out
initial unsafe foo implementation, but since the compiler
prevents us from providing an out-of-bounds index, we can be sure that
no UB will occur at runtime.
# Problems
There are unfortunately some problems to working with
InRange objects as it is. The only way to create or assign
to one is with constants known at compile-time. On the one hand that is
kind of the point, but it is also too restrictive. We don’t need to know
exactly what the value is, only that it falls within the right
range.
The first thing to add would be a way of explicitly doing a bounds
check that allows transforming any old integer into an
InRange at run-time if it satisfies the
constraint:
1 | #include <optional> 2 | 3 | using std::optional; 4 | 5 | template<typename T, T n, T m> 6 | class InRange { 7 | private: 8 | InRange(T value, bool) : x(value) {} 9 | public: 10 | static optional<InRange<T, n, m>> try_create(T value) { 11 | if (check_constraint(value)) { 12 | return InRange<T, n, m>(value, true); 13 | } else { 14 | return std::nullopt; 15 | } 16 | } 17 | //... 18 | }
Now I know the point was to avoid runtime checks, but the nice thing
here is that we only have to perform it once. We could imagine a
function that is part of a public API, which is responsible for
validating user input, but then forwards the arguments internally using
InRange to ensure safety without further checks:
1 | #include <iostream> 2 | #include "in_range.h" 3 | 4 | safe_array<int, 100> arr; 5 | 6 | void process(InRange<size_t, 0, 100> index) { 7 | std::cout 8 | << "Array at " << index 9 | << ": " << arr[index] << "\n"; 10 | } 11 | 12 | int main() { 13 | size_t user_input; 14 | std::cin >> user_input; 15 | 16 | auto index = InRange<size_t, 0, 100> 17 | ::try_create(user_input); 18 | if (index) { 19 | process(*index); 20 | } else { 21 | std::cerr 22 | << "Error: index out of range\n"; 23 | } 24 | }
However this still only works as long as we never transform
InRange objects in any way. To do any arithmetic for
example we first need to get convert back to T, do the
arithmetic, and then convert back to InRange. Since we’re
not working with a compile constant at that point the only way to do
that is with another try_create, i.e. another runtime
bounds check.
In general we won’t be able to get around this, because the result of
e.g. addition with an arbitrary integer can be anything. But when both
operands are of type InRange then we can deduce
something about the result. For example if we add two
InRange<int, 0, 5> objects the result must be at
least 0 and never be more than 8. So we can implement addition like
this:
1 | template<typename T, T n, T m>
2 | class InRange {
3 | public:
4 | //...
5 | template<T n2, T m2>
6 | InRange<T, n + n2, m + m2 - 1> operator+(InRange<T, n2, m2> y) {
7 | return InRange<T, n + n2, m + m2 - 1>(x + y, true);
8 | }
9 | }C++ Quiz time:
Why won’t this code compile yet, even with the addition operator overloaded?1 | InRange<int, 0, 19> foo(InRange<int, 0, 10> x) { 2 | return x + InRange<int, 0, 10>(5); 3 | }The non-consteval constructor is private, and the operator isn’t creating an object of the same type as the class we are in . What we need is a
frienddeclaration for all possible instances of the class:1 | // ... 2 | template<typename T, T n, T m> 3 | class InRange { 4 | template<typename U, U a, U b> 5 | friend class InRange; 6 | //... 7 | };