Borrow Checker, Lifetimes and Destructor Arguments in C++

Advanced compile-time validation with stateful metaprogramming

Posted on Sunday, February 18, 2024

Library and Code

Below is a detailed explanation, but if you prefer to dive straight into the complete implementation code, you can find it on this GitHub repository:
https://github.com/a10nw01f/Mitzi/

Or on compiler explorer:
https://godbolt.org/z/71qs619Ge

Safety in C++

In the realm of modern software development, ensuring memory safety and guarding against security vulnerabilities remains paramount, particularly in languages like C++ which faced some criticism.

Bjarne Stroustrup addressed this topic in this year’s CppCon opening keynote which I had both the great pleasure of hearing in person and the immense stress of presenting immediately after.

He talked about the profiles proposal where each profile provides different restrictions and validations of what can be used in a specific code section. He also explored leveraging attributes and static analysis tools to enhance validation, such as detecting reference invalidation after modifying a container.

His insights sparked my curiosity: could we leverage modern C++ compile-time programming techniques to implement these validations?

Stateful Metaprogramming

Stateful metaprogramming involves manipulating friend functions and template instantiation in C++ to introduce usable state into compilation, allowing for surprising behaviors like impure constexpr functions.

An in-depth explanation of stateful metaprogramming including its history and implementation is available in this amazing blog post: https://mc-deltat.github.io/articles/stateful-metaprogramming-cpp20

Meta State

I wrapped the stateful metaprogramming facilities described above in class which represents a meta state that holds a type along with getters and a setter to change the type stored in the meta state.

template<class Init = none, auto tag = [] {} >
class meta_state {
public:
    // set the type stored in the meta state
    template<
        typename T,
        auto eval = [] {}
    >
    using set = decltype(set_state<T, tag, eval>());

    // get current type stored in the meta state
    template<auto eval = [] {} >
    using get = typename get_state<tag, eval>::type;

    // another getter
    template<auto eval = [] {} >
    constexpr auto type() const->meta_state::get<eval>; 
private:
    // set the initial meta state type
    static constexpr setter<0, Init, tag> init = {}; 
};

How to use it:

// initalize a state to store the int type
using state = meta_state<int>;

// state::get<> == int
state::get<> a = 42;
static_assert(std::is_same_v<decltype(a), int>, "");

// set state to const char*
using T = state::set<const char*>();

// and this is how you use it
state::get<> b = "this is amazing";
static_assert(std::is_same_v<decltype(b), const char*>, "");

Modifying Meta States

One thing to keep in mind is that meta states don’t work like regular variables, for example, the following code will not change the meta state:

template<class state>
void modify(){
    using T = state::template set<const char*>;
}

int main(){
    using state = meta_state<int>;
    state::get<> a = 42;
    static_assert(std::is_same_v<decltype(a), int>, "");

    modify<state>(); // will not change the meta state
    state::get<> b = "this will cause a compilation error";
    static_assert(std::is_same_v<decltype(b), const char*>, "");
}

The only way that I’m aware of to reliably modify a meta state is with template parameters:

template<
    class state,
    // modify the meta state
    class T = state::template set<const char*, eval>>
void modify(){}

int main(){
    using state = meta_state<int>;
    state::get<> a = 42;
    static_assert(std::is_same_v<decltype(a), int>, "");

    modify<state>();
    state::get<> b = "this will compile";
    static_assert(std::is_same_v<decltype(b), const char*>, "");
}

Destructor Arguments

Although it may not be the most thrilling aspect discussed here, we’ll utilize it as a foundational element for implementing more advanced features like borrow checking and lifetimes.

So, why the emphasis on destructor arguments? Well, the need arises in scenarios where an object creates other objects that must be subsequently destroyed. While this necessity is prevalent across various domains, it’s particularly notable in fields such as computer graphics.

auto my_device = device(context);
auto texture = my_device.create_texture();
auto texture_view = my_device.create_texture_view(texture);

And then either destroy them manually in which case we have to remember to call destroy:

my_device.destroy(texture);
my_device.destroy(texture_view);

Or with RAII and then we have to store the device with every object:

template<class T, class deleter>
class handle {
    device m_device;
    T m_value;
    /*...*/
};

I want to avoid storing the device with every object but still get a compilation error if I forget to destroy an object. Let’s implement it in runtime before transitioning to compile-time:

class handle {
    texture m_texture;
    bool m_destroyed = false;
public:
    handle(texture tex): 
        m_texture(tex)
    {}

    auto& get() { 
        if(m_destroyed){
            panic("object already destroyed");
        }
        return m_value; 
    }

    destroy(device owner_device){
        if(m_destroyed){
            panic("object already destroyed");
        }
        owner_device.destory(m_texture);
        m_destroyed = true;
    }

    ~handle(){
        if(!m_destroyed){
            panic("forgot to call destroy");
        }
    }
};

The runtime validation uses the m_destroyed data member. Let’s transition to compile-time validation by replacing m_destroyed with a meta state.

struct none{};
struct destroyed{};

template<auto eval = []{}>
class handle {
    using state = meta_state<none, eval>;
    texture m_texture;
public:
    handle(texture tex): 
        m_texture(tex)
    {}

    template<
        class T = typename state::template get<>
    >
    auto& get() {
        static_assert(!std::is_same_v<T, destroyed>, "object already destroyed");

        return m_value; 
    }

    template<
        class prev_state = typename state::template get<>,
        class T = typename state::template set<destroyed>,
    >
    destroy(device owner_device){
        static_assert(!std::is_same_v<prev_state, destroyed>, "object already destroyed");

        owner_device.destory(m_texture);
    }

    template<
        class T = typename state::template get<>
    >
    ~handle(){
        static_assert(std::is_same_v<T, destroyed>, "forgot to destroy object");
    }
};

There is problem with the code above: destructors can’t be templates, and we need template parameters to reliably read and write the meta state.

We know that the destructor will be called in the end of the scope, so one option is to manually validate that the state is destroyed.

{
    /* create the handle */

    // end of scope - validate everything is destroyed
    static_assert(std::is_same_v<decltype(texture_view)::state::get<>, destroyed>, "");
    static_assert(std::is_same_v<decltype(texture)::state::get<>, destroyed>, "");
}

But this can quickly become tedious if we have many variables or have robust validation logic where the order of calls to validate matters.

Defer

To alleviate the burden of manually validating the state destruction at the end of the scope, we can use the following defer class. This class acts as a deferred executor for meta state validation and modification, ensuring that certain operations are postponed until the end of the scope.

template<auto eval = [] {} >
struct defer {
	using state = meta_state<type_list<>, eval>;

    template<
        class T,
        class U = /* push T into the state type_list */
    >
    constexpr void push(){}

    template</*...*/>
    constexpr auto apply(){
        // iterate and call every function
        for_each_type(list, [](auto func){
            func.apply</*...*/>();
        });
    }
};

The constructor of the handle class defers the call that validates the resource has been destroyed.

template<
    class defer,
    class T = typename defer::template push<
        defer_assert<state, destroyed>
    >
>
handle(defer, texture tex) /*...*/

Using handles with defer:

{
    using defer_scope = defer<>;
    
    auto my_device = device{};
    auto my_texture = make_handle(
        defer_scope{}, 
        my_device.create_texture()
    );
    auto my_texture_view = make_handle(
        defer_scope{}, 
        my_device.create_texture_view(my_texture.get())
    );

    my_texture_view.destroy(my_device, my_texture.get());
    my_texture.destroy(my_device);
    /*
        removing or changing the order of destroy calls will cause a static assert
    */

    defer_scope{}.apply();
}

Implementing a scope guard becomes straightforward using this approach. Rather than altering the meta state immediately, we defer it until the end of the scope. Defer calls are executed in the reverse order of their insertion, akin to how destructors are invoked in the reverse order of constructors.

template<
    class defer,
    class v = DEFER_PUSH(defer, defer_set<state, destroyed>), // change to destroyed
    class v1 = DEFER_PUSH(defer, defer_assert<state, none>) // validate it wasn't destroyed before
>
auto make_scope_guard(defer, device owner_device) {
    return scope_guard([this, owner_device] {
        owner_device.destory(this->m_value);
    });
}

Lifetimes

In Rust, lifetimes are a concept used in the type system to ensure memory safety without the need for a garbage collector. Lifetimes specify the scope for which references are valid, helping prevent dangling references and memory errors.

In C++ the compiler doesn’t prevent us from having dangling references

int x = 42;
int* outer_ptr = &x;

{
    int y = 43;
    int *inner_ptr = &y;

    outer_ptr = innert_ptr;
}

// outer_ptr points to y which was already destroyed
std::cout << *outer_ptr;

We can represent the lifetime of a variable with two integers: depth and counter.
Depth: how deep it is in the scope stack.
Counter: a counter that is inceremented for each variable.

int v0; // counter = 0, depth = 0
int v1; // counter = 1, depth = 0
{
    int v2; // counter = 2, depth = 1
    {
        int v3; // counter = 3, depth = 2
    }
} 
int v4; // counter = 4, depth = 0

Let’s turn it into a struct:

struct lifetime {
    int counter = 0;
    int depth = 0;

    constexpr bool outlives(const lifetime other) const {
        if (depth < other.depth) {
            return true;
        }
        else if (other.depth < depth) {
            return false;
        }

        return counter > other.counter;
    }
}

The current lifetime will be stored as meta state.
On scope entry - increment depth
On scope exit (will use the defer mechanism) - decrement depth
On new variable - increment counter and return the current lifetime

struct lifetime_manager {
    using state = meta_state<value_wrapper<lifetime{0,0}>>;

    template<
        class next_lifetime = // get current lifetime and increment counter
        class v = typename state::template set<next_lifetime>
    >
    constexpr next_lifetime add_lifetime() const {
        return {};
    }

    template<
        class defer_scope = defer<>,
        class next_lifetime = // increment depth
        class v = typename state::template set<next_lifetime>,
        class v1 = DEFER_PUSH(defer_scope, decrement_depth)  // defer decrement depth
    >
    constexpr auto begin_scope(defer_scope arg = {}) const {
        return defer_scope{};
    }
};

With this we can create a pointer type that validates lifetimes on assingment:

template<
    class T,
    auto lifetime
>
class ptr {
public:
    ptr(T& value, value_wrapper<lifetime>) : m_value(&value) {}

    template<auto other_lifetime>
    ptr& operator=(ptr<T, other_lifetime> other) {
        static_assert(other_lifetime.outlives(lifetime), "lifetime is not long enough");
        m_value = other.get();
        return *this;
    }

    auto get() const { return m_value; }
private:
    T* m_value;
};

Changing the C++ pointers to the lifetime checked pointers in the dangling pointer example results in a static assert “lifetime is not long enough”

constexpr auto lifetimes = lifetime_factory<>{};
using defer_scope = decltype(lifetimes.begin_scope());

int x = 42;
auto outer_ptr = ptr(x, lifetimes.add_lifetime());
{
    using defer_scope = decltype(lifetimes.begin_scope());

    int y = 43;
    auto inner_ptr = ptr(y, lifetimes.add_lifetime());

    outer_ptr = inner_ptr; // static_assert "lifetime is not long enough"

    defer_scope{}.apply();
}
defer_scope{}.apply();

Borrow Checker

The borrow checker in Rust enforces a strict set of rules governing references to data: each piece of data can have either one mutable reference (&mut T) or multiple immutable references (&T) at any given time. This constraint prevents data races, dangling pointers, and memory corruption by ensuring exclusive mutation rights or concurrent read-only access to data.

We can represent the borrow state of a variable with two integers - read_count and write_count:

struct borrow_state {
    int read_count = 0;
    int write_count = 0;
};

The borrowable class holds a private data member that can be accessed with two member functions:

ref() const -> const T&

  • asserts write_count == 0
  • read_count++
  • defer read_count–

mut() -> T&

  • asserts write_count == 0 && read_count == 0
  • write_count++
  • defer write_count–

And this is how it can be used:

using defer_scope = defer<>;
auto value = borrowable(42);
{
    using defer_scope = defer<>;

    // can have multiple immutable references
    auto& ref1 = value.ref(defer_scope{});
    auto& ref2 = value.ref(defer_scope{});
    auto& ref3 = value.ref(defer_scope{});

    // auto& mut1 = value.mut(defer_scope{});
    // uncommenting the line above will cause a static assert

    defer_scope{}.apply();
}

{
    using defer_scope = defer<>;

    // must only have a single mutable reference
    auto& mut1 = value.mut(defer_scope{});

    // auto& ref1 = value.ref(defer_scope{});
    // auto& mut2 = value.mut(defer_scope{});
    // uncommenting any of the lines above will cause a static assert

    defer_scope{}.apply();
}

defer_scope{}.apply();

Compiler Specific Behaviour

Here are some compiler-specific behaviours that I encountered while working on this:

Reading/writing a meta state will not always work inside of a nested template. This can be solved by passing a unique lambda along the template instantiation:

template</*...*/>
struct defer{
    template<
        auto eval = [] {},
        class F,
        class v = typename state::template set<
            typename state::template get<eval>::template push_front<F>, eval
        >
    >
    constexpr auto push(F) const {}
}

GCC generates errors when a template parameter is not provided to a member function call with a default template parameter of a unique lambda:

defer_scope{}.apply(); // compilation error only in GCC
defer_scope{}.apply<[]{}>(); // works on all 3 major compilers

When expanding a template parameter pack Clang evaluates the templates in reverse order:

#ifdef __clang__
    auto list = reverse(List{}); // reverse order for Clang
#else
    auto list = List{}; // regular order for MSVC and GCC
#endif

    for_each_type([]<class T>(type_wrapper<T>) {
        /*...*/
    }, list);

Future Direction

This compile-time validation library is still in early development, but here is the direction that I currently have in mind for its future:

More robust analysis based on the type of the current scope and parent scopes

enum class scope_type {
    regular, // inline scope { int x = 42; }
    function, // beginning of a function
    branch, // if, if else, switch case
    fallback, // else, switch default
    loop // for, while, do while, etc...
};

template<class previous_scope, scope_type type, auto eval = []{}>
class defer {
    /*...*/
};

This can enable more robust validation, for example, that a handle is destroyed in all branch cases.

using scope0 = defer<none, scope_type::function>;
auto x = make_handle(scope0{}, device.create_texture());

if(condition1){
    using scope1 = defer<scope0, scope_type::branch>;
    x.destory(device);
    scope1{}.apply();
}
else if(condition2){
    using scope1 = defer<scope0, scope_type::branch>;
    x.destory(device);
    scope1{}.apply();
}
else {
    using scope1 = defer<scope0, scope_type::fallback>;
    x.destory(device);
    scope1{}.apply();
}

// validate that all the paths lead to x being detroyed
scope0{}.apply();

Or that it isn’t destroyed multiple times in a loop:

using scope0 = defer<none, scope_type::function>;
auto x = make_handle(scope0{}, device.create_texture());

for(int i = 0; i < 10; i++){
    using scope1 = defer<scope0, scope_type::loop>;
    x.destroy(device); // error, outside variable destroyed in a loop
    scope1{}.apply();
}
scope0{}.apply();

I also want to eliminate the need to pass scope{} everywhere, maybe it will be possible with a global meta state:


using current_scope = meta_state<>;

template<
    /*...*/
    current_scope::set<defer>
>
struct defer { /*...*/ };

template<
    /*...*/
    class defer = current_scope::get<>
>
struct ptr {/*...*/};

For a higher level abstraction I plan to separate the validation logic from the data types.

using validate_ptr_lifetimes = decltype([]<class T, auto lifetime, auto other_lifetime>
    (meta_info<
        func_name<"operator=">,
        ptr<T, lifetime>,
        ptr<T, other_lifetime>
    >){
        static_assert(other_lifetime.outlives(lifetime), "lifetime is not long enough");
    });

This may be the way to implement profiles in current C++:

using safe_profile = profile<
    validate_ptr_lifetimes,
    validate_borrows,
    validate_destructors
>;

The borrowable, ptr, and handle classes will be wrappers that call validate. It will allow reusing these types with different validation logic. Hopefully, when we get reflection in C++ we will be able to generate these wrapper classes automatically.

template<
    class T,
    auto lifetime
>
class ptr {
/*...*/
    template<
        auto other_lifetime,
        auto v = current_scope::get<>::validate(meta_info<
            func_name<"operator=">,
            ptr<T, lifetime>,
            ptr<T, other_lifetime>
        >{})
    >
    ptr& operator=(ptr<T, other_lifetime> other) {
        m_value = other.get();
        return *this;
    }
/*...*/
};

Lastly, I want to remove the calls at the beginning and end of every scope, maybe with macros.

Pros and Cons

Pros

  • Flexibility and Extensibility: The use of templates and meta programming allows for highly flexible and extensible solutions. Developers can easily customize validation logic and adapt it to specific project requirements.

  • Compile-time Validation: By leveraging stateful metaprogramming and compile-time techniques, we shift many safety checks from runtime to compile-time, catching errors before code execution.

  • Enhanced Memory Safety: The techniques discussed in this blog post significantly enhance memory safety in C++, guarding against common pitfalls such as dangling pointers, memory leaks, and invalid references.

Cons

  • Complexity: While powerful, these techniques introduce a level of complexity that might be daunting for developers unfamiliar with advanced C++ features or metaprogramming.

  • Non-Standardized Approach: Stateful metaprogramming, being non-standardized in C++, lacks universal support and may lead to portability issues across different compilers or future language versions. This reliance on non-standard techniques can pose maintenance challenges and compromise long-term code sustainability.

  • Early Development Stage: This library is still in its early development stage and requires further exploration and refinement. As a result, there may be undiscovered limitations or unforeseen complications that need to be addressed before it can be considered stable for widespread adoption.

Conclusion

In this post, we explored advanced C++ techniques for compile-time validation, focusing on stateful metaprogramming, destructor arguments, lifetimes, and borrow checking. These methods offer flexibility and extensibility, enhancing memory safety and error prevention.

However, they come with complexity and non-standardized approaches, potentially complicating code maintenance. Despite this, leveraging these techniques can significantly improve software quality.

By embracing advanced compile-time validation and metaprogramming, developers can create safer, more reliable C++ codebases, mitigating common pitfalls and enhancing overall software quality.