rapidcheck-crdt-example.cxx

#include <list>
    using std::list;
#include <map>
    using std::map;
#include <set>
    using std::set;
#include <utility>
    using std::pair;

#include <rapidcheck.h>

// Properties //////////////////////////////////////////////////////////////////

template <typename A>
bool plus_associativity(A x, A y, A z) {
    return (x + y) + z == x + (y + z);
}

template <typename A>
bool plus_commutativity(A x, A y) {
    return x + y == y + x;
}

// merge interface /////////////////////////////////////////////////////////////

// template <typename A>
// concept Mergeable = requires(A x, A y) {
//     { merge(x, y) } -> A;
// };

// merge implementation for std ////////////////////////////////////////////////

template <typename A>
set<A> merge(set<A> x, set<A> y) {
    x.merge(y);
    return x;
}

template <typename K, typename V>
map<K, V> merge(map<K, V> x, map<K, V> const & y) {
    for (auto const [k, v] : y) {
        auto const it = x.find(k);
        if (it != x.end())
            it->second = merge(it->second, v);
        else
            x.emplace(k, v);
    }
    return x;
}

// Generalized properties //////////////////////////////////////////////////////

template <typename A>
bool associativity(A const & x, A const & y, A const & z) {
    return merge(merge(x, y), z) == merge(x, merge(y, z));
}

template <typename A>
bool commutativity(A const & x, A const & y) {
    return merge(x, y) == merge(y, x);
}

template <typename A>
bool idempotence(A const & x) {
    return merge(x, x) == x;
}

// All merges bools by && //////////////////////////////////////////////////////

struct All {
    bool value;
    operator bool() const { return value; }
    bool operator==(const All & other) const { return value == other.value; }
};

All merge(All const & x, All const & y) { return {x.value && y.value}; }

namespace rc {
    template<>
    struct Arbitrary<All> {
        static Gen<All> arbitrary() {
            return gen::build<All>(gen::set(&All::value));
        }
    };
}

// Observed-Remove-set /////////////////////////////////////////////////////////

using Pid = unsigned;

template <typename A>
struct ORSet {
    using Serial = unsigned;
    using Tag = pair<Pid, Serial>;

    map<A, map<Tag, All>> data;

    bool operator==(ORSet<A> const & other) const { return data == other.data; }

    void add(Pid const pid, A const & value) {
        Serial maxKnownSerial = 0;
        for (auto const & [tag, _] : data[value])
            if (tag.second > maxKnownSerial)
                maxKnownSerial = tag.second;
        data[value][Tag{pid, maxKnownSerial + 1}] = All{true};
    }

    void remove(A const & value) {
        for (auto & tag_flag : data[value])
            tag_flag.second = All{false};
    }

    bool contains(A const & value) const {
        auto const v = data.find(value);
        if (v != data.end())
            for (auto & tag_flag : v->second)
                if (tag_flag.second)
                    return true;
        return false;
    }
};

template <typename A>
std::ostream & operator<<(std::ostream & os, ORSet<A> const & s) {
    os << "ORSet{data = ";
    rc::show(s.data, os);
    return os << "}";
}

template <typename A>
ORSet<A> merge(ORSet<A> const & x, ORSet<A> const & y) {
    return ORSet<A>{merge(x.data, y.data)};
}

namespace rc {
    template<typename A>
    struct Arbitrary<ORSet<A>> {
        static Gen<ORSet<A>> arbitrary() {
            return gen::build<ORSet<A>>(
                gen::set(&ORSet<A>::data)
            );
        }
    };
}

// utility /////////////////////////////////////////////////////////////////////

template <typename Range>
bool all(Range r) { return all_of(begin(r), end(r), [](bool x){return x;}); }

// Quick! Check! ///////////////////////////////////////////////////////////////

int main() {
    using rc::check;
    list const checks {
        check("plus_associativity<int>",   plus_associativity<int>),
        check("plus_associativity<float>", plus_associativity<float>),

        check("plus_commutativity<int>", plus_commutativity<int>),

        check("associativity<set>", associativity<set<char>>),
        check("commutativity<set>", commutativity<set<char>>),
        check("idempotence<set>",   idempotence<set<char>>),

        check("ORSet::contains", [](char c){
            return not ORSet<char>{}.contains(c);
        }),

        check("ORSet::add", [](Pid pid, ORSet<char> s, char c){
            s.add(pid, c);
            return s.contains(c);
        }),

        check("ORSet::remove", [](ORSet<char> s, char c){
            s.remove(c);
            return not s.contains(c);
        }),

        check(
            "ORSet::remove doesn't remove other items",
            [](ORSet<char> s, char char_to_remove, char char_to_keep) {
                // RC_PRE(false);
                RC_PRE(char_to_remove != char_to_keep);
                RC_PRE(s.contains(char_to_keep));

                s.remove(char_to_remove);
                return s.contains(char_to_keep);
            }
        ),

        check(
            "ORSet: remove observed only",
            [](Pid pid1, ORSet<char> s1, char c){
                auto s2 = s1;
                s1.add(pid1, c);
                s2.remove(c);
                return merge(s1, s2).contains(c);
            }
        ),

        check("associativity<ORSet>", associativity<ORSet<char>>),
        check("commutativity<ORSet>", commutativity<ORSet<char>>),
        check("idempotence<ORSet>",   idempotence<ORSet<char>>),
    };
    return !all(checks);
}