WasmTreeFrontEnd ... in C++ Experiments

a_Wasm_Tree_cpp.md

Wasmtree-front-end but in C++ experiments

In this gist, we explore the possibilites offered by emscripten/embind to implement WasmTree backend. This evaluation is obviously biaised as WasmTree was conceived with wasm-bindgen possibilites and contraints in mind

embind documentation: https://emscripten.org/docs/porting/connecting_cpp_and_javascript/embind.html

Getting started

• Install emscripten: https://emscripten.org/docs/getting_started/downloads.html
• Get every files from this gist
• emcc --bind -o wasm_tree_back_cpp.js wasm_tree_back.cpp -std=c++2a
• python3 -m http.server
• Visit http://0.0.0.0:8000/wasm_tree_back_cpp.html

wasm_tree_back.cpp

#include <array>
// #include <compare>
#include <map>
#include <optional>
#include <set>
#include <vector>

#include <emscripten/bind.h>

using namespace emscripten;

// SPOG
struct IdentifierQuad {
    uint32_t subject;
    uint32_t predicate;
    uint32_t object;
    uint32_t graph;

    //[[nodiscard]] constexpr auto operator<=>(const IdentifierQuad & other) const noexcept;

    [[nodiscard]] constexpr bool operator<(const IdentifierQuad & other) const noexcept {
        if (subject   < other.subject  ) return true;       if (subject   > other.subject  ) return false;
        if (predicate < other.predicate) return true;       if (predicate > other.predicate) return false;
        if (object    < other.object   ) return true;       if (object    > other.object   ) return false;
        if (graph     < other.graph    ) return true;       if (graph     > other.graph    ) return false;

        return false;
    }

    [[nodiscard]] constexpr std::array<uint32_t, 4> to_array() const noexcept {
        return std::array<uint32_t, 4> { subject, predicate, object, graph };
    }

    [[nodiscard]] static IdentifierQuad from_identifier_list(const std::vector<uint32_t> & id_list, size_t i) {
        return IdentifierQuad{ id_list[i], id_list[i + 1], id_list[i + 2], id_list[i + 3] };
    }
};

// S? P? O? G?
struct QuadMatcher {
    std::optional<uint32_t> subject;
    std::optional<uint32_t> predicate;
    std::optional<uint32_t> object;
    std::optional<uint32_t> graph;

    constexpr QuadMatcher(std::optional<uint32_t> s, std::optional<uint32_t> p, std::optional<uint32_t> o, std::optional<uint32_t> g)
    : subject(s), predicate(p), object(o), graph(g) {}

    // uint32_t only interface -> 0 == ?
    [[nodiscard]] constexpr static std::optional<uint32_t> map(uint32_t js_parameter) {
        if (js_parameter == 0) return std::nullopt;
        return js_parameter;
    }

    constexpr QuadMatcher(uint32_t s, uint32_t p, uint32_t o, uint32_t g) 
    : subject(map(s)), predicate(map(p)), object(map(o)), graph(map(g)) {}


    // Returns true if the passed quad complies with this S? P? O? G? pattern
    [[nodiscard]] constexpr bool operator()(const IdentifierQuad & quad) const noexcept {
        if (subject   && *subject   != quad.subject  ) return false;
        if (predicate && *predicate != quad.predicate) return false;
        if (object    && *object    != quad.object   ) return false;
        if (graph     && *graph     != quad.graph    ) return false;

        return true;
    }
};

// A forest of trees... with only one tree which is a SPOG tree.
class QuadForest {
    std::set<IdentifierQuad> spog_tree;

public:
    QuadForest() = default;

    // std::vector as a parameter is supported
    static QuadForest from(const std::vector<uint32_t> & identifier_list) {
        QuadForest retval;
        for (size_t i = 0 ; i != identifier_list.size() ; i += 4) {
            retval.spog_tree.insert(IdentifierQuad::from_identifier_list(identifier_list, i));
        }
        return retval;
    }

    void insert(uint32_t s, uint32_t p, uint32_t o, uint32_t g) {
        spog_tree.insert(IdentifierQuad{ s, p , o, g });
    }

    // match : returns the list of quads complying with the pattern in the format
    // [s1, p1, o1, g1, s2, o2, o2, g2, ... sn, pn, on, gn]

    // optional is impossible
    // std::vector<uint32_t> match(std::optional<uint32_t> s, std::optional<uint32_t> p, std::optional<uint32_t> o, std::optional<uint32_t> g) {
    [[nodiscard]] std::vector<uint32_t> match(uint32_t s, uint32_t p, uint32_t o, uint32_t g) const {
        std::vector<uint32_t> retval;

        const QuadMatcher quad_matcher(s, p, o, g);

        for (const auto & identifier_quad : spog_tree) {
            if (quad_matcher(identifier_quad)) {
                for (auto id : identifier_quad.to_array()) {
                    retval.push_back(id);
                }
            }
        }

        return retval;
    }

    // optional is kind of possible with emscripten::val, but some extra mapping could be offered
    [[nodiscard]] std::vector<uint32_t> match_emsval(emscripten::val s, emscripten::val p, emscripten::val o, emscripten::val g) const {
        std::vector<uint32_t> retval;

        constexpr auto to_optional = [](const emscripten::val & v) -> std::optional<uint32_t> {
            if (v.isNull() || v.isUndefined()) {
                return std::nullopt;
            } else if (v.isNumber()) {
                return v.as<uint32_t>();
            } else {
                // ???
                return std::nullopt;
            }
        };

        const QuadMatcher quad_matcher(
            to_optional(s),
            to_optional(p),
            to_optional(o),
            to_optional(g)
        );

        for (const auto & identifier_quad : spog_tree) {
            if (quad_matcher(identifier_quad)) {
                for (auto id : identifier_quad.to_array()) {
                    retval.push_back(id);
                }
            }
        }

        return retval;
    }
};

// Binding code
EMSCRIPTEN_BINDINGS(cpp_quad_forest) {
  class_<QuadForest>("CppQuadForest")
    .constructor<>()
    .function("insert", &QuadForest::insert)
    .function("matchNumbers", &QuadForest::match)
    .function("match", &QuadForest::match_emsval)
    .class_function("fromIdentifierList", &QuadForest::from)
    ;

    register_vector<uint32_t>("vector<uint32_t>");
}

// It could have been attributes (we have these in C++, see nodiscard attribute which is heavily used in this code)
// instead of a macro
// But it is not intrusive so it is nice (we can export classes we don't own)
// + typically a class is declared several times, while I guess the binding only needs to happen once?

wasm_tree_back_cpp.html

wasm_tree_back.cpp<!doctype html>
<html>
    <body>
        <textarea rows="30" cols="120" id="text"></textarea>
    </body>
  <script>
    var Module = {
      onRuntimeInitialized: function() {
        let text = "";
        function append(line) { text += line + "\n"; } // 2020 Javascript quality code

        function appendToText(header, identifierList) {
            append("== " + header + " ==");

            // identifierList is not iterable
            // In this case, it's not a real problem as the loop 4 by 4 but in other context
            // it could be annoying
            for (let i = 0 ; i != identifierList.size() ; i += 4) {
                append("["
                    + identifierList.get(i)
                    + ", " + identifierList.get(i + 1)
                    + ", " + identifierList.get(i + 2)
                    + ", " + identifierList.get(i + 3)
                    + "]"
                );
            }

            // identifierList doesn't free itself unlike in Rust/wasm-bindgen
            identifierList.delete();
        }

        const quadForest = new Module.CppQuadForest();
        quadForest.insert(1, 2, 3, 4);
        quadForest.insert(1, 2, 3, 5);
        quadForest.insert(6, 2, 3, 4);

        //appendToText("QuadForest", quadForest.matchNumbers(0, 0, 0, 0));
        appendToText("QuadForest", quadForest.match(null, null, null, null));
        appendToText("SPOx", quadForest.match(1, 2, 3, null));

        const newForest = Module.CppQuadForest.fromIdentifierList(quadForest.matchNumbers(1, 2, 3, 0));
        appendToText("NewForest", newForest.match(null, null, null, null));

        quadForest.delete();
        newForest.delete();

        document.getElementById("text").value = text;
      }
    };
  </script>
  <script src="wasm_tree_back_cpp.js"></script>
</html>