Linked list with compile time checks in C++

Question

I am trying to implement a linked list with compile time checks for in and out capabilities. These capabilities (or caps) shall provide information wether a valid linking can take place. Therefore the out caps of an element are intersected with the in caps of the next element. If a valid intersection can be found, the link is established. Please see provided code for such kind of check at runtime.

While this is rather easy to accomplish at runtime, i do not know the direction for meta/template programming to handle it at compile time. I already started reading into std::variant<>, std::visit<>, template instantiation, template specialization.

Basically, i know about meta/template programming, but only on a pre C++11 level. Please let me ask this open question, how and if this is feasible with meta/template programming.

Thanks in advance.

#include <assert.h>
#include <list>

enum class NodeType {
    Type1,
    Type2,
    Type3
};

class Caps {
public:
    NodeType type;
    int      minValue;
    int      maxValue;
};

bool intersect(const std::list<Caps>& in, const std::list<Caps>& out)
{
    for (auto i : in) {
        for (auto o : out) {
            if (i.type == o.type) {
                auto minValue = std::max(i.minValue, o.minValue);
                auto maxValue = std::min(i.maxValue, o.maxValue);
                if (maxValue >= minValue) {
                    return true;
                }
            }
        }
    }

    return false;
}

class Node
{
public:
    virtual bool link(Node& next) {
        if (intersect(this->outCaps(), next.inCaps())) {
            m_next = &next;
            return true;
        }
        return false;
    }

    virtual std::list<Caps> inCaps() { return {}; }
    virtual std::list<Caps> outCaps() { return {}; }

protected:
    Node* m_next = nullptr;
};

class DerivedNode1 : public Node
{
public:
    std::list<Caps> outCaps() override {
        return { { NodeType::Type1, 1, 10 },
                 { NodeType::Type2, 5, 20 } };
    }
};

class DerivedNode2 : public Node
{
    std::list<Caps> inCaps() override { return { { NodeType::Type1, 8, 12 } }; }
};

class DerivedNode3 : public Node
{
    std::list<Caps> inCaps() override { return { { NodeType::Type2, 1, 4 } }; }
};

class DerivedNode4 : public Node
{
    std::list<Caps> inCaps() override { return { { NodeType::Type3, 1, 99 } }; }
};

int main()
{
    DerivedNode1 node1;
    DerivedNode2 node2;
    DerivedNode3 node3;
    DerivedNode4 node4;

    assert(node1.link(node2));  // This shall link due to matching types and ranges
    assert(!node1.link(node3)); // This shall fail due to non-matching range for a specific type
    assert(!node1.link(node4)); // This shall fail due to non-matching types
}

Answer 1

The below does what you presumably want. If you don't like the Link class, Node::link2 could be renamed to Node::link, but otherwise it needs to have a different name.

You can use either Node::link2(a, b) or a.link(b) syntax depending on what you prefer. The former doesn't need injection of the single-argument link method to derived classes, so may be preferable. The latter requires a bit more work for deep derivation to work

// Wouldn't work because `DerivedNodeY::link` and `DerivedNodeX::link` are ambiguous;
class DerivedNodeX : public DerivedNodeY, Link<DerivedNodeX>
{
public:
    static constexpr std::array<Caps,1> inCaps() { ... }
    // but this makes it work:
    using Link<DerivedNodeX>::link;
};

Without the Link class, a derived node looks simply like:

class DerivedNode : public Node
{
public:
    static constexpr std::array<Caps,1> inCaps() {
        return {{ { NodeType::Type3, 1, 99 } }};
    }
};

The code is C++17, it compiles with gcc and clang, but it crashes MSVC (up to 19.22) with an internal error :(. Kudos for writing a nice compiler testcase!

#include <array>
#include <type_traits>

enum class NodeType {
    Type1,
    Type2,
    Type3
};

struct Caps {
    NodeType type;
    int      minValue;
    int      maxValue;
};

class Node
{
public:
    static constexpr std::array<Caps,0> inCaps() { return {}; }
    static constexpr std::array<Caps,0> outCaps() { return {}; }

    template <class InCaps, class OutCaps>
    static constexpr bool intersect(const InCaps &in, const OutCaps &out);

    template <class N1, class N2>
    static std::enable_if_t<
        std::is_base_of_v<Node, N1> &&
        std::is_base_of_v<Node, N2> &&
        intersect(N1::outCaps(), N2::inCaps()), void>
    link2(N1 &prev, N2 &next) {
        prev.m_next = &next;
    }

protected:
    Node* m_next = nullptr;
};

template <typename ThisNode>
class Link
{
public:
    template <class N2> void link(N2 &next) {
        Node::link2(*static_cast<ThisNode*>(this), next);
    }
};

template <class InCaps, class OutCaps>
constexpr bool Node::intersect(const InCaps &in, const OutCaps &out)
{
    for (auto i : in) {
        for (auto o : out) {
            if (i.type == o.type) {
                auto minValue = std::max(i.minValue, o.minValue);
                auto maxValue = std::min(i.maxValue, o.maxValue);
                if (maxValue >= minValue) {
                    return true;
                }
            }
        }
    }
    return false;
}

class DerivedNode1 : public Node, public Link<DerivedNode1>
{
public:
    static constexpr std::array<Caps,2> outCaps() {
        return {{ { NodeType::Type1, 1, 10 },
                  { NodeType::Type2, 5, 20 } }};
    }
};

class DerivedNode2 : public Node, public Link<DerivedNode2>
{
public:
    static constexpr std::array<Caps,1> inCaps() {
        return {{ { NodeType::Type1, 8, 12 } }};
    }
};

class DerivedNode3 : public Node, public Link<DerivedNode3>
{
public:
    static constexpr std::array<Caps,1> inCaps() {
        return {{ { NodeType::Type2, 1, 4 } }};
    }
};

class DerivedNode4 : public Node, public Link<DerivedNode4>
{
public:
    static constexpr std::array<Caps,1> inCaps() {
        return {{ { NodeType::Type3, 1, 99 } }};
    }
};

int main()
{
    DerivedNode1 node1;
    DerivedNode2 node2;
    DerivedNode3 node3;
    DerivedNode4 node4;

    Node::link2(node1, node2); // compiles
    node1.link(node2);
#if 0
    Node::link2(node1, node3); // fails to compile
    node1.link(node3);
    Node::link2(node1, node4); // fails to compile
    node1.link(node3);
#endif
}

Answer 2

C++ doesn't have proper intersection types. But you can fake it a bit with compile-time template logic.

Say I define some capabilities as mixins:

struct cap_a {
    void foo();
};
struct cap_b {
    void bar();
};
struct cap_c {
    void baz();
};

And a container like this that inherits from all the capabilities:

template<typename... TCaps>
struct intersectable : public TCaps... {};

I can create an intersection of two intersectable's with a mix of SFINAE and variadic templates. The resulting type only has capabilities that both inputs have.

First step of doing a cross-join is to check if a type is in a list. This is a pretty basic variadic macro. Each iteration pops off a type, checks if its the target type, and or's it with the next iteration.

template<typename TCap, typename... TCaps>
struct has_capability_impl;

template<typename TCap, typename TCapFirst, typename... TCaps>
struct has_capability_impl<TCap, TCapFirst, TCaps...> {
    static constexpr bool value = std::is_convertible<TCap, TCapFirst>::value || has_capability_impl<TCap, TCaps...>::value;
};

template<typename TCap>
struct has_capability_impl<TCap> {
    static constexpr bool value = false;
};

template<typename TCap, typename... TCaps>
constexpr bool has_capability = has_capability_impl<TCap, TCaps...>::value;

You can do this with fold expressions in C++17, but this works in older versions.

Next is the intersection. This a template with 3 types: An empty result itersectable, the left hand side, and branches with enable_if. If the type is present on the right intersectable, move the type over to the result in the inherited base type. OTherwise, don't.

For each iteration, pop a type off a

template<typename TLRhs, typename TLhs, typename TRhs, typename = void> 
struct intersect_impl;

template<typename... TLRCaps, typename TFirst, typename... TLCaps, typename... TRCaps>
struct intersect_impl<intersectable<TLRCaps...>, intersectable<TFirst, TLCaps...>, intersectable<TRCaps...>, std::enable_if_t<has_capability<TFirst, TRCaps...>>> : intersect_impl<intersectable<TLRCaps..., TFirst>, intersectable<TLCaps...>, intersectable<TRCaps...>> { };

template<typename... TLRCaps, typename TFirst, typename... TLCaps, typename... TRCaps>
struct intersect_impl<intersectable<TLRCaps...>, intersectable<TFirst, TLCaps...>, intersectable<TRCaps...>, std::enable_if_t<!has_capability<TFirst, TRCaps...>>> : intersect_impl<intersectable<TLRCaps...>, intersectable<TLCaps...>, intersectable<TRCaps...>> { };

By the time there are no types left on the left hand side, the result only has capabilities present from both sides:

template<typename... TLRCaps, typename... TRCaps>
struct intersect_impl<intersectable<TLRCaps...>, intersectable<>, intersectable<TRCaps...>> {
    using type = intersectable<TLRCaps...>;
};

template<typename TLhs, typename TRhs>
using intersection = typename intersect_impl<intersectable<>, TLhs, TRhs, void>::type;

Package that in a trivial function to combine instances:

template<typename TLhs, typename TRhs>
intersection<TLhs, TRhs> intersect(TLhs lhs, TRhs rhs) {
    return intersection<TLhs, TRhs>{}; // runtime link logic goes here
}

...and the result is type-safe capability intersections:

int main() {
    intersectable<cap_a, cap_c> ac;
    ac.foo();
    ac.baz();

    intersectable<cap_a, cap_b> ab;
    ab.foo();
    ab.bar();

    auto a = intersect(ac, ab);
    a.foo();
    a.bar(); // error
    a.baz(); // error
}

Demo: https://godbolt.org/z/-kd2Qj

Again, this doesn't actually do anything, it just intersects the types. But you can use something like this to make your linked list logic type-safe.

Anyway, to add range checking, it's just a matter of working in compile-time properties for range into the definition of intersectable

#include <cstdint>
#include <functional>
#include <type_traits>
#include <unordered_set>

struct cap_a {
    void foo();
};
struct cap_b {
    void bar();
};
struct cap_c {
    void baz();
};

template<int Min, int Max, typename... TCaps>
struct intersectable : public TCaps... {
};

template<typename TCap, typename... TCaps>
struct has_capability_impl;

template<typename TCap, typename TCapFirst, typename... TCaps>
struct has_capability_impl<TCap, TCapFirst, TCaps...> {
    static constexpr bool value = std::is_convertible<TCap, TCapFirst>::value || has_capability_impl<TCap, TCaps...>::value;
};

template<typename TCap>
struct has_capability_impl<TCap> {
    static constexpr bool value = false;
};

template<typename TCap, typename... TCaps>
constexpr bool has_capability = has_capability_impl<TCap, TCaps...>::value;

template<typename TLRhs, typename TLhs, typename TRhs, typename = void> 
struct intersect_impl;

template<int LRMin, int LRMax, int LMin, int LMax, int RMin, int RMax, typename... TLRCaps, typename TFirst, typename... TLCaps, typename... TRCaps>
struct intersect_impl<
    intersectable<LRMin, LRMax, TLRCaps...>, 
    intersectable<LMin, LMax, TFirst, TLCaps...>, 
    intersectable<RMin, RMax, TRCaps...>, 
    std::enable_if_t<(has_capability<TFirst, TRCaps...>)>> 
    : intersect_impl<
        intersectable<LRMin, LRMax, TLRCaps..., TFirst>, 
        intersectable<LMin, LMax, TLCaps...>,
        intersectable<RMin, RMax, TRCaps...>> { };

template<int LRMin, int LRMax, int LMin, int LMax, int RMin, int RMax, typename... TLRCaps, typename TFirst, typename... TLCaps, typename... TRCaps>
struct intersect_impl<
    intersectable<LRMin, LRMax, TLRCaps...>, 
    intersectable<LMin, LMax, TFirst, TLCaps...>, 
    intersectable<RMin, RMax, TRCaps...>, 
    std::enable_if_t<(!has_capability<TFirst, TRCaps...>)>>
    : intersect_impl<
        intersectable<LRMin, LRMax, TLRCaps...>, 
        intersectable<LMin, LMax, TLCaps...>, 
        intersectable<RMin, RMax, TRCaps...>> { };

template<int LMin, int LMax, int RMin, int RMax, typename TResult, typename... TRCaps>
struct intersect_impl<TResult, intersectable<LMin, LMax>, intersectable<RMin, RMax, TRCaps...>> {
    using type = TResult;
};

template <typename T>
struct props;

template<int Min, int Max, typename... Caps>
struct props<intersectable<Min, Max, Caps...>> {
    static constexpr int min = Min;
    static constexpr int max = Max;
};

template<typename TLhs, typename TRhs>
using intersection = typename intersect_impl<
    intersectable<(std::max(props<TLhs>::min, props<TRhs>::min)), (std::min(props<TLhs>::max, props<TRhs>::max))>, 
    TLhs, 
    TRhs>::type;

template<typename TLhs, typename TRhs>
intersection<TLhs, TRhs> intersect(TLhs lhs, TRhs rhs) {
    static_assert((props<TLhs>::max >= props<TRhs>::min && props<TLhs>::min <= props<TRhs>::max)  || 
                  (props<TRhs>::max >= props<TLhs>::min && props<TRhs>::min <= props<TLhs>::max), "out of range");
    return intersection<TLhs, TRhs>{}; // runtime intersection logic?
}

int main() {
    intersectable<1, 5, cap_a, cap_c> ac;
    ac.foo();
    ac.baz();

    intersectable<3, 8, cap_a, cap_b> ab;
    ab.foo();
    ab.bar();

    auto a = intersect(ac, ab); // result is a intersectable<3, 5, cap_a>
    a.foo();
    a.bar(); // error
    a.baz(); // error

    intersectable<10, 15, cap_a, cap_b> ab_out_of_range;
    auto a0 = intersect(ac, ab_out_of_range);
}

demo: https://godbolt.org/z/zz9-Vg