cavi is an open-source library that aims to provide performant utilities for closed hierarchies (i.e. all class types of the hierarchy are known at compile time).

cavi

cavi is an open-source library that aims to provide performant utilities for closed hierarchies (i.e. all class types of the hierarchy are known at compile time).

Requires C++17 or above.

  1. Utilities
  2. Visitation
  3. Dynami Casting
  4. Supported Hierarchies
  5. Hierarchy Setup
  6. Code Reuse / Libraries
  7. Additional Notes
  8. To Do List

Utilities

Currently the library comes with the following utilities:

  • Hierarchy-aware visitation
  • Fast dynamic casting

Visitation

cavi::visit

template<typename Visitor, typename... Os>
decltype(auto) visit(Visitor&& visitor, Os&& ... os)
  • The return type is deduced by decltype
  • All invocations of the visitor must have the same return type and value category

template<typename R, typename Visitor, typename... Os>
R visit(Visitor&& visitor, Os&& ... os)
  • The return type is R
  • The result of all invocations of the visitor must be implicitly convertible to R
  • If R is (possible cv-qualified) void, then the value returned by the visitor invocation is discarded

For both of the above:

  • Applies the visitor to the objects os...

  • None of the objects os... may be pointer values (ill-formed otherwise)

  • Objects os... must be of complete type

  • No exceptions are thrown if and only if the visitor does not throw any exceptions

  • The runtime time complexity is constant

  • Let S(x) be the set containing all types of the hierarchy that the object x belongs to. Let N := |S(os)| * ... * 1, where |A| is the size of the set A. Then, for N <= 256, the implementation uses a switch statement; otherwise a dispatch table is used. The (N=256) threshold can easily be increased or decreased by modfying the library source but increasing it means longer compile times.

  • Let Z(x) be the set consisting of x and all classes that inherit — directly or indirectly — object x as a base class. Let set W be defined as follows:

    • If sizeof...(os) == 0, then let W := {},
    • If sizeof...(os) == 1, then let W := Z(os).
    • Otherwise, let W := Z(os) × ..., where A × B is the cartesian product of sets A and B.

    If the set W is empty, then the only invocation of the visitor is one with no arguments. Otherwise, the visitor is invoked only for arguments of type(s) and form in set W. See Example 2 for further reading.

  • The behaviour of cavi::visit invoked with an object undergoing construction/destruction (or invoked with any of its base class subobjects) is as follows:

    • If cavi::visit is used during destruction, the behaviour is undefined
    • cavi::visit can be used in a constructor (including the mem-initializer or default member initializer when either is used for a non-static data member — if used in a mem-initializer that initializes a base class subobject, the behaviour is undefined). When cavi::visit is used in a constructor, the most derived object is considered to be the constructors class type and is pointed to by the this pointer. If the operand of cavi::visit is not the said object considered to be the most derived or any of its base class subobjects, the behaviour is undefined.

Example 1

Suppose you had the following hierarchy for a console variables implementation (often found in video games):

struct var {
protected:
    var() = default;
    var(const var&) = default;
    var(var&&) = default;
};

struct var_string : var {
    std::string value;
    var_string(std::string val) : value(std::move(val)) {}
};

struct var_vector2 : var { 
    float x, y;
    var_vector2(float x_, float y_) : x(x_), y(y_) {}
};

struct var_arith : var {
protected:
    var_arith() = default;
    var_arith(const var_arith&) = default;
    var_arith(var_arith&&) = default;
};

struct var_u32 : var_arith {
    uint32_t value;
    var_u32(uint32_t val) : value(val) {}
};

struct var_flt : var_arith {
    float value;
    var_flt(float val) : value(val) {}
};

After the setup for the hierarchy, visitation can be done in the same fashion as std::visit :

) { std::cout << v.value << '\n'; } else { static_assert(cavi::dependent_false, "unhandled type"); } }, vr); } int main() { var_u32 v1{150}; var_flt v2{3.14f}; var_string v3{"Hello World"}; var_vector2 v4{1.5f, 3.0f}; print_var(v1); print_var(v2); print_var(v3); print_var(v4); return 0; } ">
void print_var(const var& vr) {
    cavi::visit([](const auto& v) {
        using T = cavi::remove_cvref_t<decltype(v)>;
        if constexpr(cavi::is_same_as_any_of_v) {
            // var & var_arith can't be instantiated on their own - only derived classes can construct them.
            // if that changes in the future we want to catch that so this implementation can be updated too.
            // a compile time assert ensuring var & var_arith can't be instantiated would be even better if possible
            assert(false);
        }
        else if constexpr(cavi::is_same_v) {
            std::cout << '(' << v.x << ", " << v.y << ")\n";
        }
        else if constexpr(cavi::is_same_as_any_of_v) {
            std::cout << v.value << '\n';
        }
        else {
            static_assert(cavi::dependent_false, "unhandled type");
        }
    }, vr);
}

int main() {
    var_u32 v1{150};
    var_flt v2{3.14f};
    var_string v3{"Hello World"};
    var_vector2 v4{1.5f, 3.0f};

    print_var(v1);
    print_var(v2);
    print_var(v3);
    print_var(v4);
    return 0;
}

Alternatively, the overload pattern popular with std::visit can also be used:

, "unhandled type"); } }, vr); } ">
template<class... Ts> struct overloaded : Ts... { using Ts::operator()...; };
template<class... Ts> overloaded(Ts...) -> overloaded;

void print_var(const var& vr) {
    cavi::visit(overloaded {
        [](const var&) { assert(false); },
        [](const var_arith&) { assert(false); },
        [](const var_vector2& v) { std::cout << '(' << v.x << ", " << v.y << ")\n"; },
        [](const var_string& v) { std::cout << v.value << '\n'; },
        [](const var_u32& v) { std::cout << v.value << '\n'; },
        [](const var_flt& v) { std::cout << v.value << '\n'; },
        [](auto&& v) { static_assert(cavi::dependent_false<decltype(v)>, "unhandled type"); }
    }, vr);
}

Output:

150
3.14
Hello World
(1.5, 3)

Example 2

I mentioned above that the visitation is "hierarchy-aware" — this means that the visitation utility uses the information it has about the hierarchy aswell the type of the input object to reduce the set of types for which the visitor has to provide an implementation for.

For example, suppose you have a reference/pointer value of type var_arith. Then the most derived object type possibilites are var_arith itself or it's derived classes, and so from the hierarchy above this gives us the set: {var_arith, var_u32, var_flt}. Therefore, a visitor only has to provide implementation for these three possibilites. Also note that the most derived type can't be var_arith either as it can't be instantiated, however, this is not possible for the visitation utility to deduce from the information it has access to.

To illustrate, the following function compiles:

, "unhandled type"); } }, r); } ">
std::string arith_to_string_representation(const var_arith& r) {
    return cavi::visit(overloaded {
        [](const var_arith&) { assert(false); return std::string(""); },
        [](const var_u32& v) { return std::to_string(v.value); },
        [](const var_flt& v) { return std::to_string(v.value); },
        [](auto&& v) { static_assert(cavi::dependent_false<decltype(v)>, "unhandled type"); }
    }, r);
}

Hierarchy-aware visitation also extends into multiple dispatch. The set of possibilities that the visitor has to cover is the cartesian product of all of the sets of possibilities. E.g. suppose that in addition to a reference/pointer of type var_arith as above, you also have a reference/pointer of type var_string. The set of most derived object type possibilities for latter is just {var_string} as var_string has no derived classes. Applying a visitor to both of the aforementioned objects would therefore require the visitor to cover the cartesian product of the two sets:
{var_arith, var_u32, var_flt} × {var_string} = {(var_arith, var_string), (var_u32, var_string), (var_flt, var_string)}

Again, to illustrate, the following function compiles as it covers all combinations from the set:

, "unhandled type"); } }, r1, r2); } ">
std::string arith_str_to_string_representation(const var_arith& r1, const var_string& r2) {
    return cavi::visit(overloaded {
        [](const var_arith&, const var_string&) { 
            assert(false); 
            return "";
        },
        [](const var_u32& v1, const var_string& v2) {
            return std::string("v1: ") + std::to_string(v1.value) + std::string(", v2: ") + v2.value;
        },
        [](const var_flt& v1, const var_string& v2) {
            return std::string("v1: ") + std::to_string(v1.value) + std::string(", v2: ") + v2.value;
        },
        [](auto&& v1, auto&& v2) {
            static_assert(cavi::dependent_false<decltype(v1)>, "unhandled type");
        }
    }, r1, r2);
}

Dynamic Casting

cavi::cast

template<typename T, typename F>
T cast(F&& obj)
template<typename T, typename F>
T cast(F* obj) noexcept

The specification is the same as of dynamic_cast in the C++17 standard except for some differences:

  • If you are casting to a pointer type, then dynamic_cast requires that the input is also a pointer, whereas cavi::cast permits non-pointer inputs so the nullptr check can be avoided. Example:

    void do_downcast(var_arith& from) {
        var_u32* p1 = cavi::cast(from); // OK
        var_u32* p2 = dynamic_cast(from); // ill-formed
    }
  • For downcasts and crosscasts dynamic_cast requires that the input object is of polymorphic type (i.e. for which std::is_polymorphic is true), whereas cavi::cast does not have this requirement

  • A failed cast to a reference type via dynamic_cast throws an exception of a type that matches a handler of type std::bad_cast, whereas cavi::cast calls a user defined function in namespace cavi declared as:

    [[noreturn]] void throw_bad_cast();

    You must define this function once in a translation unit if you want to cast to reference types via cavi::cast, otherwise you will get a linker error. Example:

    //some_file.cpp
    #include <typeinfo>
    namespace cavi {
        [[noreturn]] void throw_bad_cast() {
            throw std::bad_cast{};
        }
    }
  • The behaviour of cavi::cast invoked with an object undergoing construction/destruction (or invoked with any of its base class subobjects) is as follows:

    • If cavi::cast is used during destruction, the behaviour is undefined
    • cavi::cast can be used in a constructor (including the mem-initializer or default member initializer when either is used for a non-static data member — if used in a mem-initializer that initializes a base class subobject, the behaviour is undefined). When cavi::cast is used in a constructor, the most derived object is considered to be the constructors class type and is pointed to by the this pointer. If the operand of cavi::cast is not the said object considered to be the most derived or any of its base class subobjects, the behaviour is undefined.

cavi::isa

template<typename... TestTs, typename F>
bool isa(F&& obj) noexcept
template<typename... TestTs, typename F>
bool isa(F* obj) noexcept

Returns true if and only if cavi::cast will succeed in casting the input object to one or more of the TestTs... types. It is the equivalent of invoking cavi::cast for all TestTs... and testing if one of them succeeds (although, it is implemented more efficiently). Therefore, the specification cavi::cast applies here as it is just a series of of calls to cavi::cast, except for one key difference: if any of the TestTs... types are reference types, [[noreturn]] void throw_bad_cast() is not called.

Generated Assembly

Consider the following function that tests if we can cast a var* to a var_u32*:

var* get_var();
int main() {
    var* v = get_var();
    if(cavi::isa(v)) {
        printf("isa: true\n");
    }
    return 0;
}

Generated assembly on clang 10.0 with -O3 and -flto (same result with -flto=thin instead of -flto). MSVC 2019 with /O2 and /GL also generates the same. GCC 9.3 also generates the same for the important part i've commented on with -O3 and -flto.

50                     push    rax
E8 1A 00 00 00         call    _Z7get_varv
48 85 C0               test    rax, rax            ; test v == nullptr
74 0F                  jz      short loc_4011AA    ; conditional jump on result
80 38 04               cmp     byte ptr [rax], 4   ; test v->type_id == 4
75 0A                  jnz     short loc_4011AA    ; conditional jmp on result
BF 04 20 40 00         mov     edi, offset s
E8 B6 FE FF FF         call    _puts
                  loc_4011AA:
31 C0                  xor     eax, eax
59                     pop     rcx
C3                     retn

The nullptr check can avoided if you know the ptr is not null by dereferencing: if(cavi::isa(*v)), then the important part from above reduces to:

80 38 04               cmp     byte ptr [rax], 4
75 0C                  jnz     short loc_14000124A

Code is changed to test if we can cast to var_arith* which is more difficult as you can no longer just do one comparison of the type_id. And thats because if the most derived type was any of {var_arith, var_u32, var_flt}, they could all be casted to var_arith*. It now becomes a bit test, generated assembly for Clang and GCC:

0F B6 00               movzx   eax, byte ptr [rax]
B9 34 00 00 00         mov     ecx, 38h
48 0F A3 C1            bt      rcx, rax
73 05                  jnb     short loc_14000101C

MSVC:

0F B6 08               movzx   ecx, byte ptr [rax]
B8 01 00 00 00         mov     eax, 1
48 D3 E0               shl     rax, cl
A8 34                  test    al, 38h
74 0C                  jz      short loc_140001254

Code is changed to test multiple types at once: if(cavi::isa(*v)), then the generated assembly is again a bit test on all three compilers. Clang:

0F B6 00               movzx   eax, byte ptr [rax]
B9 2A 00 00 00         mov     ecx, 2Ah       
48 0F A3 C1            bt      rcx, rax
73 05                  jnb     short loc_14000101C

Example of typical assembly generated from cavi::cast, involving a type check (compare or bit test) + pointer adjustment.

48 89 C6               mov     rsi, rax
48 8D 56 E8            lea     rdx, [rsi-18h]
31 C0                  xor     eax, eax
80 7E 08 06            cmp     byte ptr [rsi], 6
48 0F 45 D0            cmovnz  rdx, rax

The majority of cavi::isa and cavi::cast calls will transform to assembly similar to above, infact for a single inheritance hierarchy with no virtual bases, every single one will be of the above form. However, not every cast can be so simply done on multiple inheritance hierarchies — crosscasts and a subset of downcasts require more assembly to do them correctly.

Supported Hierarchies

All closed hierarchies are supported except for those with:

  1. >256 classes
  2. Virtual bases
  3. Ambiguous direct bases

In regards to (1) and (2), the limit of 256 classes is due to a macro (CAVI_INSTANTIATE), however, it can easily be increased or reduced to any arbitrary number. It's just that increasing it leads to slighly higher compile times and thus 256 was chosen as the sweet spot. And support for hierarchies with virtual base classes is on the to-do list.

Moreover, in regards to (3), here is an example of such:

struct A {};
struct B : A {};
struct C : A, B {};

The direct base class A of C cannot be accessed from C due to ambiguity. However, it can be made non-ambiguous via a proxy class:

struct A {};
struct B : A {};
struct proxyA : A {};
struct C : proxyA, B {};

Now, it is accessible via the route: C → proxyA → A. Also, note that inaccessible in this context means purely in terms of ambiguity and not whether the base class is inherited publicly or not.

Hierarchy Setup

The hierarchy from Example 1 will be used to demonstrate the setup.

Step 1

Create a new header file for your hierarchy and include the header: cavi/core.h. Declare the classes of your hierarchy and their base classes using the template type cavi::hierarchy_decl. Lastly, use either the CAVI_DEF_BAREBONES_BASE or CAVI_DEF_STANDARD_BASE macro to define a base class for your hierarchy.

var_HY.h

, cavi::class_, cavi::class_, cavi::class_, cavi::class_, cavi::class_ >; CAVI_DEF_BAREBONES_BASE(var_HY, var_HYB) ">
#include "cavi/core.h"

using var_HY = cavi::hierarchy_decl<
    cavi::class_<struct var>,
    cavi::class_<struct var_string, var>,
    cavi::class_<struct var_vector2, var>,
    cavi::class_<struct var_arith, var>,
    cavi::class_<struct var_u32, var_arith>,
    cavi::class_<struct var_flt, var_arith>
>;

CAVI_DEF_BAREBONES_BASE(var_HY, var_HYB)

To clarify, the CAVI_DEF_BAREBONES_BASE and CAVI_DEF_STANDARD_BASE macros define a templated base class that the classes in the hierarchy will inherit from in step 2. The first parameter of the macros is the hierarchy declaration and second is the name of the base that will be defined.

The type of hierarchies they support:

  • The barebones base works only on single inheritance hierarchies (with no virtual bases)
  • The standard base works on single and multiple inheritance hierarchies (with no virtual bases)

The templated base class defined by the macro can be empty or have data members — it only has data members when it is inherited by a class with zero base classes. For example, in the var hierarchy above, only struct var will inherit a base that has data members as it has zero base classes. All others classes will inherit an empty base which will not add any extra size due to the empty base class optimization.

The difference in data members of the bases:

  • The barebones base has only one data member and that is an integral type_id. The type of this integral id could be any of {unsigned char, unsigned short, unsigned long, unsigned long long} depending the range it needs to cover. E.g. if you have up to 256 classes in the hierarchy then the id will fit in unsigned char and require only 1 byte in size
  • The standard base has integral type_id + void* pointer. The type of the integral type_id is determined in the same way as in the barebones case

Step 2

Now for every class in the hierarchy, include the relevant header file created in step 1 and inherit from the base class (publicly and non-virtually) at the end of the base list. The template parameter for the base is the class inherting the base itself. Like so:

var.h

{ protected: var() = default; var(const var&) = default; var(var&&) = default; }; struct var_string : var, var_HYB { std::string value; var_string(std::string val) : value(std::move(val)) {} }; struct var_vector2 : var, var_HYB { float x, y; var_vector2(float x_, float y_) : x(x_), y(y_) {} }; struct var_arith : var, var_HYB { protected: var_arith() = default; var_arith(const var_arith&) = default; var_arith(var_arith&&) = default; }; struct var_u32 : var_arith, var_HYB { uint32_t value; var_u32(uint32_t val) : value(val) {} }; struct var_flt : var_arith, var_HYB { float value; var_flt(float val) : value(val) {} }; ">
#include "var_HY.h"
struct var : var_HYB {
protected:
    var() = default;
    var(const var&) = default;
    var(var&&) = default;
};

struct var_string : var, var_HYB {
    std::string value;
    var_string(std::string val) : value(std::move(val)) {}
};

struct var_vector2 : var, var_HYB {
    float x, y;
    var_vector2(float x_, float y_) : x(x_), y(y_) {}
};

struct var_arith : var, var_HYB {
protected:
    var_arith() = default;
    var_arith(const var_arith&) = default;
    var_arith(var_arith&&) = default;
};

struct var_u32 : var_arith, var_HYB {
    uint32_t value;
    var_u32(uint32_t val) : value(val) {}
};

struct var_flt : var_arith, var_HYB {
    float value;
    var_flt(float val) : value(val) {}
};

Make sure that the base class is the last one in the base list as that is important. If you would really like you can also inherit the base as protected/private, but then you need to make some relevant machinery of cavi a friend via the CAVI_MAKE_FRIEND macro like so:

struct var_string : var, private var_HYB {
    CAVI_MAKE_FRIEND;
    std::string value;
    var_string(std::string val) : value(std::move(val)) {}
};

Step 3

Finally, make a new cpp file for your hierarchy, include the header cavi/instantiate.h and include the headers of all the classes in the hierarchy so this translation unit has the definition of all classes in the hierarchy. And, invoke the CAVI_INSTANTIATE macro with the hierarchy declaration and the base class. Like so (var.h has the definitions of the var_* structs):

var_HY.cpp

#include "cavi/instantiate.h"
#include "var.h"

CAVI_INSTANTIATE(var_HY, var_HYB)

And that's it.

Include cavi/visit.h when you need to use cavi::visit and cavi/cast.h for cavi::cast and cavi::isa.

What to look out for

There are compile time checks in place to check for incorrect setup but not everything can be checked for correctness.

Step 1

Make sure the hierarchy declaration is correct as its almost impossible to verify

Step 2

Mistakes that are caught at compile time:

  • If you put in the wrong type as the template parameter to the base
  • If any type listed in the hierarchy declaration does not inherit the hierarchy base
  • If you inherit the base non-publicy and do not make use of the CAVI_MAKE_FRIEND macro

Mistakes that aren't caught:

  • Hierarchy base class is not placed at the end of the base list

Step 3

This step completely checked, if it not done or done wrongly, it results in a compiler or linker error.

Code Reuse / Libraries

What if you wanted to turn the above hierarchy and functionality with it into a library, so that you or others could reuse it in other projects? We would need a way to allow new types to be added to the hierarchy and to allow new operations/functionality. Here's how it could be done with cavi.

Making The Library

Let's start with library itself first and lets call it 'convar'. Since we don't know the full hierarchy from a library point of view, we can't yet define the base for the hierarchy with the macros. That also means we can't inherit from a cavi generated base because we dont have a base defined yet. We have to make use of templates:

convar_types.h

namespace convar {
template<template <typename> class HYB>
struct var : HYB> {
protected:
    var() = default;
    var(const var&) = default;
    var(var&&) = default;
};

template<template <typename> class HYB>
struct var_string : var, HYB> {
    std::string value;
    var_string(std::string val) : value(std::move(val)) {}
};

template<template <typename> class HYB>
struct var_vector2 : var, HYB> {
    float x, y;
    var_vector2(float x_, float y_) : x(x_), y(y_) {}
};

template<template <typename> class HYB>
struct var_arith : var, HYB> {
protected:
    var_arith() = default;
    var_arith(const var_arith&) = default;
    var_arith(var_arith&&) = default;
};

template<template <typename> class HYB>
struct var_u32 : var_arith, HYB> {
    uint32_t value;
    var_u32(uint32_t val) : value(val) {}
};

template<template <typename> class HYB>
struct var_flt : var_arith, HYB> {
    float value;
    var_flt(float val) : value(val) {}
};
}

Now, you want to update your hierarchy decl to take into account the templates. The user will use this to extend the hierarchy if he needs to.

convar_hierarchy.h

class HYB> struct var; template