souffle-haskell 3.1.0 → 3.2.0
raw patch · 37 files changed
+4239/−976 lines, 37 filesdep +profunctorsdep ~bytestring
Dependencies added: profunctors
Dependency ranges changed: bytestring
Files
- CHANGELOG.md +4/−0
- README.md +1/−1
- cbits/souffle/CompiledSouffle.h +10/−35
- cbits/souffle/RecordTable.h +24/−11
- cbits/souffle/SignalHandler.h +9/−0
- cbits/souffle/SouffleInterface.h +32/−4
- cbits/souffle/datastructure/BTree.h +1/−198
- cbits/souffle/datastructure/BTreeDelete.h +2698/−0
- cbits/souffle/datastructure/BTreeUtil.h +222/−0
- cbits/souffle/datastructure/Brie.h +32/−30
- cbits/souffle/datastructure/ConcurrentFlyweight.h +119/−69
- cbits/souffle/datastructure/ConcurrentInsertOnlyHashMap.h +14/−9
- cbits/souffle/datastructure/EquivalenceRelation.h +33/−11
- cbits/souffle/datastructure/UnionFind.h +1/−1
- cbits/souffle/io/ReadStream.h +1/−2
- cbits/souffle/io/ReadStreamSQLite.h +9/−4
- cbits/souffle/io/SerialisationStream.h +12/−5
- cbits/souffle/io/WriteStream.h +1/−3
- cbits/souffle/io/WriteStreamSQLite.h +13/−6
- cbits/souffle/utility/ContainerUtil.h +37/−54
- cbits/souffle/utility/DynamicCasting.h +104/−0
- cbits/souffle/utility/FunctionalUtil.h +0/−166
- cbits/souffle/utility/General.h +27/−0
- cbits/souffle/utility/Iteration.h +53/−40
- cbits/souffle/utility/MiscUtil.h +26/−69
- cbits/souffle/utility/ParallelUtil.h +19/−17
- cbits/souffle/utility/StreamUtil.h +18/−9
- cbits/souffle/utility/StringUtil.h +40/−6
- cbits/souffle/utility/Types.h +74/−7
- cbits/souffle/utility/span.h +6/−2
- lib/Language/Souffle/Analysis.hs +134/−0
- lib/Language/Souffle/Interpreted.hs +4/−4
- souffle-haskell.cabal +31/−11
- tests/Test/Language/Souffle/AnalysisSpec.hs +249/−0
- tests/fixtures/edge_cases.cpp +74/−81
- tests/fixtures/path.cpp +23/−30
- tests/fixtures/round_trip.cpp +84/−91
CHANGELOG.md view
@@ -3,6 +3,10 @@ All notable changes to this project (as seen by library users) will be documented in this file. The CHANGELOG is available on [Github](https://github.com/luc-tielen/souffle-haskell.git/CHANGELOG.md). +## [3.2.0] - 2022-02-20++- Add `Analysis` type for composing multiple Datalog programs.+- souffle-haskell now supports Souffle version 2.2. ## [3.1.0] - 2021-09-30
README.md view
@@ -1,7 +1,7 @@ # Souffle-haskell [](https://github.com/luc-tielen/souffle-haskell/blob/master/LICENSE)-[](https://circleci.com/gh/luc-tielen/souffle-haskell)+ [](https://hackage.haskell.org/package/souffle-haskell) This repo provides Haskell bindings for performing analyses with the
cbits/souffle/CompiledSouffle.h view
@@ -21,39 +21,16 @@ #include "souffle/SignalHandler.h" #include "souffle/SouffleInterface.h" #include "souffle/SymbolTable.h"+#include "souffle/datastructure/BTreeDelete.h" #include "souffle/datastructure/Brie.h" #include "souffle/datastructure/EquivalenceRelation.h" #include "souffle/datastructure/Table.h" #include "souffle/io/IOSystem.h" #include "souffle/io/WriteStream.h"-#include "souffle/utility/CacheUtil.h"-#include "souffle/utility/ContainerUtil.h" #include "souffle/utility/EvaluatorUtil.h"-#include "souffle/utility/FileUtil.h"-#include "souffle/utility/FunctionalUtil.h"-#include "souffle/utility/MiscUtil.h"-#include "souffle/utility/ParallelUtil.h"-#include "souffle/utility/StreamUtil.h"-#include "souffle/utility/StringUtil.h" #ifndef __EMBEDDED_SOUFFLE__ #include "souffle/CompiledOptions.h"-#include "souffle/profile/Logger.h"-#include "souffle/profile/ProfileEvent.h" #endif-#include <array>-#include <atomic>-#include <cassert>-#include <cmath>-#include <cstdint>-#include <cstdlib>-#include <exception>-#include <iostream>-#include <iterator>-#include <memory>-#include <regex>-#include <string>-#include <utility>-#include <vector> #if defined(_OPENMP) #include <omp.h>@@ -194,7 +171,7 @@ bool value; public:- typedef std::forward_iterator_tag iterator_category;+ using iterator_category = std::forward_iterator_tag; using value_type = RamDomain*; using difference_type = ptrdiff_t; using pointer = value_type*;@@ -358,7 +335,6 @@ t_tuple value; public:- iterator_0() = default; iterator_0(const nested_iterator& iter) : nested(iter), value(*iter) {} iterator_0(const iterator_0& other) = default; iterator_0& operator=(const iterator_0& other) = default;@@ -386,7 +362,6 @@ t_tuple value; public:- iterator_1() = default; iterator_1(const nested_iterator& iter) : nested(iter), value(reorder(*iter)) {} iterator_1(const iterator_1& other) = default; iterator_1& operator=(const iterator_1& other) = default;@@ -424,7 +399,7 @@ bool insert(const RamDomain* ramDomain) { RamDomain data[2]; std::copy(ramDomain, ramDomain + 2, data);- const t_tuple& tuple = reinterpret_cast<const t_tuple&>(data);+ auto& tuple = reinterpret_cast<const t_tuple&>(data); context h; return insert(tuple, h); }@@ -432,13 +407,13 @@ RamDomain data[2] = {a1, a2}; return insert(data); }- void extend(const t_eqrel& other) {- ind.extend(other.ind);+ void extendAndInsert(t_eqrel& other) {+ ind.extendAndInsert(other.ind); } bool contains(const t_tuple& t) const { return ind.contains(t[0], t[1]); }- bool contains(const t_tuple& t, context& h) const {+ bool contains(const t_tuple& t, context&) const { return ind.contains(t[0], t[1]); } std::size_t size() const {@@ -447,10 +422,10 @@ iterator find(const t_tuple& t) const { return ind.find(t); }- iterator find(const t_tuple& t, context& h) const {+ iterator find(const t_tuple& t, context&) const { return ind.find(t); }- range<iterator> lowerUpperRange_10(const t_tuple& lower, const t_tuple& upper, context& h) const {+ range<iterator> lowerUpperRange_10(const t_tuple& lower, const t_tuple& /*upper*/, context& h) const { auto r = ind.template getBoundaries<1>((lower), h.hints); return make_range(iterator(r.begin()), iterator(r.end())); }@@ -458,7 +433,7 @@ context h; return lowerUpperRange_10(lower, upper, h); }- range<iterator_1> lowerUpperRange_01(const t_tuple& lower, const t_tuple& upper, context& h) const {+ range<iterator_1> lowerUpperRange_01(const t_tuple& lower, const t_tuple& /*upper*/, context& h) const { auto r = ind.template getBoundaries<1>(reorder(lower), h.hints); return make_range(iterator_1(r.begin()), iterator_1(r.end())); }@@ -466,7 +441,7 @@ context h; return lowerUpperRange_01(lower, upper, h); }- range<iterator> lowerUpperRange_11(const t_tuple& lower, const t_tuple& upper, context& h) const {+ range<iterator> lowerUpperRange_11(const t_tuple& lower, const t_tuple& /*upper*/, context& h) const { auto r = ind.template getBoundaries<2>((lower), h.hints); return make_range(iterator(r.begin()), iterator(r.end())); }
cbits/souffle/RecordTable.h view
@@ -458,7 +458,7 @@ void setNumLanes(const std::size_t) override {} /** @brief converts record to a record reference */- RamDomain pack(const std::vector<RamDomain>& Vector) override {+ RamDomain pack([[maybe_unused]] const std::vector<RamDomain>& Vector) override { assert(Vector.size() == 0); return EmptyRecordIndex; };@@ -469,33 +469,35 @@ } /** @brief converts record to a record reference */- RamDomain pack(const std::initializer_list<RamDomain>& List) override {+ RamDomain pack([[maybe_unused]] const std::initializer_list<RamDomain>& List) override { assert(List.size() == 0); return EmptyRecordIndex; } /** @brief convert record reference to a record pointer */- const RamDomain* unpack(RamDomain Index) const override {+ const RamDomain* unpack([[maybe_unused]] RamDomain Index) const override { assert(Index == EmptyRecordIndex); return EmptyRecordData; } }; /** The interface of any Record Table. */-class RecordTableInterface {+class RecordTable { public:- virtual ~RecordTableInterface() {}+ virtual ~RecordTable() {} virtual void setNumLanes(const std::size_t NumLanes) = 0; virtual RamDomain pack(const RamDomain* Tuple, const std::size_t Arity) = 0; + virtual RamDomain pack(const std::initializer_list<RamDomain>& List) = 0;+ virtual const RamDomain* unpack(const RamDomain Ref, const std::size_t Arity) const = 0; }; /** A concurrent Record Table with some specialized record maps. */ template <std::size_t... SpecializedArities>-class SpecializedRecordTable : public RecordTableInterface {+class SpecializedRecordTable : public RecordTable { private: // The current size of the Maps vector. std::size_t Size;@@ -540,16 +542,24 @@ virtual void setNumLanes(const std::size_t NumLanes) override { Lanes.setNumLanes(NumLanes); for (auto& Map : Maps) {- Map->setNumLanes(NumLanes);+ if (Map) {+ Map->setNumLanes(NumLanes);+ } } } - /** @brief convert record to record reference */+ /** @brief convert tuple to record reference */ virtual RamDomain pack(const RamDomain* Tuple, const std::size_t Arity) override { auto Guard = Lanes.guard(); return lookupMap(Arity).pack(Tuple); } + /** @brief convert tuple to record reference */+ virtual RamDomain pack(const std::initializer_list<RamDomain>& List) override {+ auto Guard = Lanes.guard();+ return lookupMap(List.size()).pack(std::data(List));+ }+ /** @brief convert record reference to a record */ virtual const RamDomain* unpack(const RamDomain Ref, const std::size_t Arity) const override { auto Guard = Lanes.guard();@@ -600,9 +610,6 @@ } }; -/** Default record table uses specialized record maps for arities 0 to 12. */-using RecordTable = SpecializedRecordTable<0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12>;- /** @brief helper to convert tuple to record reference for the synthesiser */ template <class RecordTableT, std::size_t Arity> RamDomain pack(RecordTableT&& recordTab, Tuple<RamDomain, Arity> const& tuple) {@@ -613,6 +620,12 @@ template <class RecordTableT, std::size_t Arity> RamDomain pack(RecordTableT&& recordTab, span<const RamDomain, Arity> tuple) { return recordTab.pack(tuple.data(), Arity);+}++/** @brief helper to pack using an initialization-list of RamDomain values. */+template <class RecordTableT>+RamDomain pack(RecordTableT&& recordTab, const std::initializer_list<RamDomain>&& initlist) {+ return recordTab.pack(std::data(initlist), initlist.size()); } } // namespace souffle
cbits/souffle/SignalHandler.h view
@@ -25,7 +25,13 @@ #include <iostream> #include <mutex> #include <string>++#ifdef _WIN32+#include <io.h>+#define STDERR_FILENO 2 /* Standard error output. */+#else #include <unistd.h>+#endif //_WIN32 namespace souffle { @@ -171,6 +177,9 @@ auto write = [](std::initializer_list<char const*> const& msgs) { for (auto&& msg : msgs) {+ // assign to variable to suppress ignored-return-value error.+ // I don't think we care enough to handle this fringe failure mode.+ // Worse case we don't get an error message. [[maybe_unused]] auto _ = ::write(STDERR_FILENO, msg, ::strlen(msg)); } };
cbits/souffle/SouffleInterface.h view
@@ -689,7 +689,7 @@ * Abstract base class for generated Datalog programs. */ class SouffleProgram {-private:+protected: /** * Define a relation map for external access, when getRelation(name) is called, * the relation with the given name will be returned from this map,@@ -717,13 +717,23 @@ * allRelations store all the relation in a vector. */ std::vector<Relation*> allRelations;+ /** * The number of threads used by OpenMP */ std::size_t numThreads = 1; -protected: /**+ * Enable I/O+ */+ bool performIO = false;++ /**+ * Prune Intermediate Relations when there is no further use for them.+ */+ bool pruneImdtRels = true;++ /** * Add the relation to relationMap (with its name) and allRelations, * depends on the properties of the relation, if the relation is an input relation, it will be added to * inputRelations, else if the relation is an output relation, it will be added to outputRelations,@@ -763,7 +773,8 @@ virtual ~SouffleProgram() = default; /**- * Execute the souffle program, without any loads or stores.+ * Execute the souffle program, without any loads or stores, and live-profiling (in case it is switched+ * on). */ virtual void run() {} @@ -773,8 +784,11 @@ * * @param inputDirectory If non-empty, specifies the input directory * @param outputDirectory If non-empty, specifies the output directory+ * @param performIO Enable I/O operations+ * @param pruneImdtRels Prune intermediate relations */- virtual void runAll(std::string inputDirectory = "", std::string outputDirectory = "") = 0;+ virtual void runAll(std::string inputDirectory = "", std::string outputDirectory = "",+ bool performIO = false, bool pruneImdtRels = true) = 0; /** * Read all input relations.@@ -1003,6 +1017,20 @@ tuple t1(relation); tuple_insert<decltype(t), sizeof...(Args)>::add(t, t1); return relation->contains(t1);+ }++ /**+ * Set perform-I/O flag+ */+ void setPerformIO(bool performIOArg) {+ performIO = performIOArg;+ }++ /**+ * Set prune-intermediate-relations flag+ */+ void setPruneImdtRels(bool pruneImdtRelsArg) {+ pruneImdtRels = pruneImdtRelsArg; } };
cbits/souffle/datastructure/BTree.h view
@@ -17,6 +17,7 @@ #pragma once +#include "souffle/datastructure/BTreeUtil.h" #include "souffle/utility/CacheUtil.h" #include "souffle/utility/ContainerUtil.h" #include "souffle/utility/MiscUtil.h"@@ -36,204 +37,6 @@ namespace souffle { namespace detail {--// ---------- comparators ----------------/**- * A generic comparator implementation as it is used by- * a b-tree based on types that can be less-than and- * equality comparable.- */-template <typename T>-struct comparator {- /**- * Compares the values of a and b and returns- * -1 if a<b, 1 if a>b and 0 otherwise- */- int operator()(const T& a, const T& b) const {- return (a > b) - (a < b);- }- bool less(const T& a, const T& b) const {- return a < b;- }- bool equal(const T& a, const T& b) const {- return a == b;- }-};--// ---------- search strategies ----------------/**- * A common base class for search strategies in b-trees.- */-struct search_strategy {};--/**- * A linear search strategy for looking up keys in b-tree nodes.- */-struct linear_search : public search_strategy {- /**- * Required user-defined default constructor.- */- linear_search() = default;-- /**- * Obtains an iterator referencing an element equivalent to the- * given key in the given range. If no such element is present,- * a reference to the first element not less than the given key- * is returned.- */- template <typename Key, typename Iter, typename Comp>- inline Iter operator()(const Key& k, Iter a, Iter b, Comp& comp) const {- return lower_bound(k, a, b, comp);- }-- /**- * Obtains a reference to the first element in the given range that- * is not less than the given key.- */- template <typename Key, typename Iter, typename Comp>- inline Iter lower_bound(const Key& k, Iter a, Iter b, Comp& comp) const {- auto c = a;- while (c < b) {- auto r = comp(*c, k);- if (r >= 0) {- return c;- }- ++c;- }- return b;- }-- /**- * Obtains a reference to the first element in the given range that- * such that the given key is less than the referenced element.- */- template <typename Key, typename Iter, typename Comp>- inline Iter upper_bound(const Key& k, Iter a, Iter b, Comp& comp) const {- auto c = a;- while (c < b) {- if (comp(*c, k) > 0) {- return c;- }- ++c;- }- return b;- }-};--/**- * A binary search strategy for looking up keys in b-tree nodes.- */-struct binary_search : public search_strategy {- /**- * Required user-defined default constructor.- */- binary_search() = default;-- /**- * Obtains an iterator pointing to some element within the given- * range that is equal to the given key, if available. If multiple- * elements are equal to the given key, an undefined instance will- * be obtained (no guaranteed lower or upper boundary). If no such- * element is present, a reference to the first element not less than- * the given key will be returned.- */- template <typename Key, typename Iter, typename Comp>- Iter operator()(const Key& k, Iter a, Iter b, Comp& comp) const {- Iter c;- auto count = b - a;- while (count > 0) {- auto step = count >> 1;- c = a + step;- auto r = comp(*c, k);- if (r == 0) {- return c;- }- if (r < 0) {- a = ++c;- count -= step + 1;- } else {- count = step;- }- }- return a;- }-- /**- * Obtains a reference to the first element in the given range that- * is not less than the given key.- */- template <typename Key, typename Iter, typename Comp>- Iter lower_bound(const Key& k, Iter a, Iter b, Comp& comp) const {- Iter c;- auto count = b - a;- while (count > 0) {- auto step = count >> 1;- c = a + step;- if (comp(*c, k) < 0) {- a = ++c;- count -= step + 1;- } else {- count = step;- }- }- return a;- }-- /**- * Obtains a reference to the first element in the given range that- * such that the given key is less than the referenced element.- */- template <typename Key, typename Iter, typename Comp>- Iter upper_bound(const Key& k, Iter a, Iter b, Comp& comp) const {- Iter c;- auto count = b - a;- while (count > 0) {- auto step = count >> 1;- c = a + step;- if (comp(k, *c) >= 0) {- a = ++c;- count -= step + 1;- } else {- count = step;- }- }- return a;- }-};--// ---------- search strategies selection ----------------/**- * A template-meta class to select search strategies for b-trees- * depending on the key type.- */-template <typename S>-struct strategy_selection {- using type = S;-};--struct linear : public strategy_selection<linear_search> {};-struct binary : public strategy_selection<binary_search> {};--// by default every key utilizes binary search-template <typename Key>-struct default_strategy : public binary {};--template <>-struct default_strategy<int> : public linear {};--template <typename... Ts>-struct default_strategy<std::tuple<Ts...>> : public linear {};--/**- * The default non-updater- */-template <typename T>-struct updater {- void update(T& /* old_t */, const T& /* new_t */) {}-}; /** * The actual implementation of a b-tree data structure.
+ cbits/souffle/datastructure/BTreeDelete.h view
@@ -0,0 +1,2698 @@+/*+ * Souffle - A Datalog Compiler+ * Copyright (c) 2013, 2015, Oracle and/or its affiliates. All rights reserved+ * Licensed under the Universal Permissive License v 1.0 as shown at:+ * - https://opensource.org/licenses/UPL+ * - <souffle root>/licenses/SOUFFLE-UPL.txt+ */++/************************************************************************+ *+ * @file BTreeDelete.h+ *+ * An implementation of a generic B-tree data structure including+ * interfaces for utilizing instances as set or multiset containers+ * and deletion.+ *+ ***********************************************************************/++#pragma once++#include "souffle/datastructure/BTreeUtil.h"+#include "souffle/utility/CacheUtil.h"+#include "souffle/utility/ContainerUtil.h"+#include "souffle/utility/MiscUtil.h"+#include "souffle/utility/ParallelUtil.h"+#include <algorithm>+#include <cassert>+#include <cstddef>+#include <cstdint>+#include <iostream>+#include <iterator>+#include <string>+#include <tuple>+#include <type_traits>+#include <typeinfo>+#include <vector>++namespace souffle {++namespace detail {++/**+ * The actual implementation of a b-tree data structure.+ *+ * @tparam Key .. the element type to be stored in this tree+ * @tparam Comparator .. a class defining an order on the stored elements+ * @tparam Allocator .. utilized for allocating memory for required nodes+ * @tparam blockSize .. determines the number of bytes/block utilized by leaf nodes+ * @tparam SearchStrategy .. enables switching between linear, binary or any other search strategy+ * @tparam isSet .. true = set, false = multiset+ */+template <typename Key, typename Comparator,+ typename Allocator, // is ignored so far - TODO: add support+ unsigned blockSize, typename SearchStrategy, bool isSet, typename WeakComparator = Comparator,+ typename Updater = detail::updater<Key>>+class btree_delete {+public:+ class iterator;+ using const_iterator = iterator;++ using key_type = Key;+ using element_type = Key;+ using chunk = range<iterator>;++protected:+ /* ------------- static utilities ----------------- */++ const static SearchStrategy search;++ /* ---------- comparison utilities ---------------- */++ mutable Comparator comp;++ bool less(const Key& a, const Key& b) const {+ return comp.less(a, b);+ }++ bool equal(const Key& a, const Key& b) const {+ return comp.equal(a, b);+ }++ mutable WeakComparator weak_comp;++ bool weak_less(const Key& a, const Key& b) const {+ return weak_comp.less(a, b);+ }++ bool weak_equal(const Key& a, const Key& b) const {+ return weak_comp.equal(a, b);+ }++ /* -------------- updater utilities ------------- */++ mutable Updater upd;+ void update(Key& old_k, const Key& new_k) {+ upd.update(old_k, new_k);+ }++ /* -------------- the node type ----------------- */++ using size_type = std::size_t;+ using field_index_type = uint8_t;+ using lock_type = OptimisticReadWriteLock;++ struct node;++ /**+ * The base type of all node types containing essential+ * book-keeping information.+ */+ struct base {+#ifdef IS_PARALLEL++ // the parent node+ node* volatile parent;++ // a lock for synchronizing parallel operations on this node+ lock_type lock;++ // the number of keys in this node+ volatile size_type numElements;++ // the position in the parent node+ volatile field_index_type position;+#else+ // the parent node+ node* parent;++ // the number of keys in this node+ size_type numElements;++ // the position in the parent node+ field_index_type position;+#endif++ // a flag indicating whether this is a inner node or not+ const bool inner;++ /**+ * A simple constructor for nodes+ */+ base(bool inner) : parent(nullptr), numElements(0), position(0), inner(inner) {}++ bool isLeaf() const {+ return !inner;+ }++ bool isInner() const {+ return inner;+ }++ node* getParent() const {+ return parent;+ }++ field_index_type getPositionInParent() const {+ return position;+ }++ size_type getNumElements() const {+ return numElements;+ }+ };++ struct inner_node;++ /**+ * The actual, generic node implementation covering the operations+ * for both, inner and leaf nodes.+ */+ struct node : public base {+ /**+ * The number of keys/node desired by the user.+ */+ static constexpr std::size_t desiredNumKeys =+ ((blockSize > sizeof(base)) ? blockSize - sizeof(base) : 0) / sizeof(Key);++ /**+ * The actual number of keys/node corrected by functional requirements.+ */+ static constexpr std::size_t maxKeys = (desiredNumKeys > 3) ? desiredNumKeys : 3;+ static constexpr std::size_t split_point = std::min(3 * maxKeys / 4, maxKeys - 2);+ static constexpr std::size_t minKeys = std::min(maxKeys - (split_point + 1), split_point + 1);++ // the keys stored in this node+ Key keys[maxKeys];++ // a simple constructor+ node(bool inner) : base(inner) {}++ /**+ * A deep-copy operation creating a clone of this node.+ */+ node* clone() const {+ // create a clone of this node+ node* res = (this->isInner()) ? static_cast<node*>(new inner_node())+ : static_cast<node*>(new leaf_node());++ // copy basic fields+ res->position = this->position;+ res->numElements = this->numElements;++ for (size_type i = 0; i < this->numElements; ++i) {+ res->keys[i] = this->keys[i];+ }++ // if this is a leaf we are done+ if (this->isLeaf()) {+ return res;+ }++ // copy child nodes recursively+ auto* ires = (inner_node*)res;+ for (size_type i = 0; i <= this->numElements; ++i) {+ ires->children[i] = this->getChild(i)->clone();+ ires->children[i]->parent = res;+ }++ // that's it+ return res;+ }++ /**+ * A utility function providing a reference to this node as+ * an inner node.+ */+ inner_node& asInnerNode() {+ assert(this->inner && "Invalid cast!");+ return *static_cast<inner_node*>(this);+ }++ /**+ * A utility function providing a reference to this node as+ * a const inner node.+ */+ const inner_node& asInnerNode() const {+ assert(this->inner && "Invalid cast!");+ return *static_cast<const inner_node*>(this);+ }++ /**+ * Computes the number of nested levels of the tree rooted+ * by this node.+ */+ size_type getDepth() const {+ if (this->isLeaf()) {+ return 1;+ }+ return getChild(0)->getDepth() + 1;+ }++ /**+ * Counts the number of nodes contained in the sub-tree rooted+ * by this node.+ */+ size_type countNodes() const {+ if (this->isLeaf()) {+ return 1;+ }+ size_type sum = 1;+ for (unsigned i = 0; i <= this->numElements; ++i) {+ sum += getChild(i)->countNodes();+ }+ return sum;+ }++ /**+ * Counts the number of entries contained in the sub-tree rooted+ * by this node.+ */+ size_type countEntries() const {+ if (this->isLeaf()) {+ return this->numElements;+ }+ size_type sum = this->numElements;+ for (unsigned i = 0; i <= this->numElements; ++i) {+ sum += getChild(i)->countEntries();+ }+ return sum;+ }++ /**+ * Determines the amount of memory used by the sub-tree rooted+ * by this node.+ */+ size_type getMemoryUsage() const {+ if (this->isLeaf()) {+ return sizeof(leaf_node);+ }+ size_type res = sizeof(inner_node);+ for (unsigned i = 0; i <= this->numElements; ++i) {+ res += getChild(i)->getMemoryUsage();+ }+ return res;+ }++ /**+ * Obtains a pointer to the array of child-pointers+ * of this node -- if it is an inner node.+ */+ node** getChildren() {+ return asInnerNode().children;+ }++ /**+ * Obtains a pointer to the array of const child-pointers+ * of this node -- if it is an inner node.+ */+ node* const* getChildren() const {+ return asInnerNode().children;+ }++ /**+ * Obtains a reference to the child of the given index.+ */+ node* getChild(size_type s) const {+ return asInnerNode().children[s];+ }++ /**+ * Checks whether this node is empty -- can happen due to biased insertion.+ */+ bool isEmpty() const {+ return this->numElements == 0;+ }++ /**+ * Checks whether this node is full.+ */+ bool isFull() const {+ return this->numElements == maxKeys;+ }++ /**+ * Obtains the point at which full nodes should be split.+ * Conventional b-trees always split in half. However, in cases+ * where in-order insertions are frequent, a split assigning+ * larger portions to the right fragment provide higher performance+ * and a better node-filling rate.+ */+ int getSplitPoint(int /*unused*/) {+ return static_cast<int>(split_point);+ }++ /**+ * Splits this node.+ *+ * @param root .. a pointer to the root-pointer of the enclosing b-tree+ * (might have to be updated if the root-node needs to be split)+ * @param idx .. the position of the insert causing the split+ */+#ifdef IS_PARALLEL+ void split(node** root, lock_type& root_lock, int idx, std::vector<node*>& locked_nodes) {+ assert(this->lock.is_write_locked());+ assert(!this->parent || this->parent->lock.is_write_locked());+ assert((this->parent != nullptr) || root_lock.is_write_locked());+ assert(this->isLeaf() || souffle::contains(locked_nodes, this));+ assert(!this->parent || souffle::contains(locked_nodes, const_cast<node*>(this->parent)));+#else+ void split(node** root, lock_type& root_lock, int idx) {+#endif+ assert(this->numElements == maxKeys);++ // get middle element+ int split_point = getSplitPoint(idx);++ // create a new sibling node+ node* sibling = (this->inner) ? static_cast<node*>(new inner_node())+ : static_cast<node*>(new leaf_node());++#ifdef IS_PARALLEL+ // lock sibling+ sibling->lock.start_write();+ locked_nodes.push_back(sibling);+#endif++ // move data over to the new node+ for (unsigned i = split_point + 1, j = 0; i < maxKeys; ++i, ++j) {+ sibling->keys[j] = keys[i];+ }++ // move child pointers+ if (this->inner) {+ // move pointers to sibling+ auto* other = static_cast<inner_node*>(sibling);+ for (unsigned i = split_point + 1, j = 0; i <= maxKeys; ++i, ++j) {+ other->children[j] = getChildren()[i];+ other->children[j]->parent = other;+ other->children[j]->position = static_cast<field_index_type>(j);+ }+ }++ // update number of elements+ this->numElements = split_point;+ sibling->numElements = maxKeys - split_point - 1;++ // update parent+#ifdef IS_PARALLEL+ grow_parent(root, root_lock, sibling, locked_nodes);+#else+ grow_parent(root, root_lock, sibling);+#endif+ }++ /**+ * Moves keys from this node to one of its siblings or splits+ * this node to make some space for the insertion of an element at+ * position idx.+ *+ * Returns the number of elements moved to the left side, 0 in case+ * of a split. The number of moved elements will be <= the given idx.+ *+ * @param root .. the root node of the b-tree being part of+ * @param idx .. the position of the insert triggering this operation+ */+ // TODO: remove root_lock ... no longer needed+#ifdef IS_PARALLEL+ int rebalance_or_split(node** root, lock_type& root_lock, int idx, std::vector<node*>& locked_nodes) {+ assert(this->lock.is_write_locked());+ assert(!this->parent || this->parent->lock.is_write_locked());+ assert((this->parent != nullptr) || root_lock.is_write_locked());+ assert(this->isLeaf() || souffle::contains(locked_nodes, this));+ assert(!this->parent || souffle::contains(locked_nodes, const_cast<node*>(this->parent)));+#else+ int rebalance_or_split(node** root, lock_type& root_lock, int idx) {+#endif++ // this node is full ... and needs some space+ assert(this->numElements == maxKeys);++ // get snap-shot of parent+ auto parent = this->parent;+ auto pos = this->position;++ // Option A) re-balance data+ if (parent && pos > 0) {+ node* left = parent->getChild(pos - 1);++#ifdef IS_PARALLEL+ // lock access to left sibling+ if (!left->lock.try_start_write()) {+ // left node is currently updated => skip balancing and split+ split(root, root_lock, idx, locked_nodes);+ return 0;+ }+#endif++ // compute number of elements to be movable to left+ // space available in left vs. insertion index+ size_type num = static_cast<size_type>(+ std::min<int>(static_cast<int>(maxKeys - left->numElements), idx));++ // if there are elements to move ..+ if (num > 0) {+ Key* splitter = &(parent->keys[this->position - 1]);++ // .. move keys to left node+ left->keys[left->numElements] = *splitter;+ for (size_type i = 0; i < num - 1; ++i) {+ left->keys[left->numElements + 1 + i] = keys[i];+ }+ *splitter = keys[num - 1];++ // shift keys in this node to the left+ for (size_type i = 0; i < this->numElements - num; ++i) {+ keys[i] = keys[i + num];+ }++ // .. and children if necessary+ if (this->isInner()) {+ auto* ileft = static_cast<inner_node*>(left);+ auto* iright = static_cast<inner_node*>(this);++ // move children+ for (field_index_type i = 0; i < num; ++i) {+ ileft->children[left->numElements + i + 1] = iright->children[i];+ }++ // update moved children+ for (size_type i = 0; i < num; ++i) {+ iright->children[i]->parent = ileft;+ iright->children[i]->position =+ static_cast<field_index_type>(left->numElements + i) + 1;+ }++ // shift child-pointer to the left+ for (size_type i = 0; i < this->numElements - num + 1; ++i) {+ iright->children[i] = iright->children[i + num];+ }++ // update position of children+ for (size_type i = 0; i < this->numElements - num + 1; ++i) {+ iright->children[i]->position = static_cast<field_index_type>(i);+ }+ }++ // update node sizes+ left->numElements += num;+ this->numElements -= num;++#ifdef IS_PARALLEL+ left->lock.end_write();+#endif++ // done+ return static_cast<int>(num);+ }++#ifdef IS_PARALLEL+ left->lock.abort_write();+#endif+ }++ // Option B) split node+#ifdef IS_PARALLEL+ split(root, root_lock, idx, locked_nodes);+#else+ split(root, root_lock, idx);+#endif+ return 0; // = no re-balancing+ }++ private:+ /**+ * Inserts a new sibling into the parent of this node utilizing+ * the last key of this node as a separation key. (for internal+ * use only)+ *+ * @param root .. a pointer to the root-pointer of the containing tree+ * @param sibling .. the new right-sibling to be add to the parent node+ */+#ifdef IS_PARALLEL+ void grow_parent(node** root, lock_type& root_lock, node* sibling, std::vector<node*>& locked_nodes) {+ assert(this->lock.is_write_locked());+ assert(!this->parent || this->parent->lock.is_write_locked());+ assert((this->parent != nullptr) || root_lock.is_write_locked());+ assert(this->isLeaf() || souffle::contains(locked_nodes, this));+ assert(!this->parent || souffle::contains(locked_nodes, const_cast<node*>(this->parent)));+#else+ void grow_parent(node** root, lock_type& root_lock, node* sibling) {+#endif++ if (this->parent == nullptr) {+ assert(*root == this);++ // create a new root node+ auto* new_root = new inner_node();+ new_root->numElements = 1;+ new_root->keys[0] = keys[this->numElements];++ new_root->children[0] = this;+ new_root->children[1] = sibling;++ // link this and the sibling node to new root+ this->parent = new_root;+ sibling->parent = new_root;+ sibling->position = 1;++ // switch root node+ *root = new_root;++ } else {+ // insert new element in parent element+ auto parent = this->parent;+ auto pos = this->position;++#ifdef IS_PARALLEL+ parent->insert_inner(+ root, root_lock, pos, this, keys[this->numElements], sibling, locked_nodes);+#else+ parent->insert_inner(root, root_lock, pos, this, keys[this->numElements], sibling);+#endif+ }+ }++ /**+ * Inserts a new element into an inner node (for internal use only).+ *+ * @param root .. a pointer to the root-pointer of the containing tree+ * @param pos .. the position to insert the new key+ * @param key .. the key to insert+ * @param newNode .. the new right-child of the inserted key+ */+#ifdef IS_PARALLEL+ void insert_inner(node** root, lock_type& root_lock, unsigned pos, node* predecessor, const Key& key,+ node* newNode, std::vector<node*>& locked_nodes) {+ assert(this->lock.is_write_locked());+ assert(souffle::contains(locked_nodes, this));+#else+ void insert_inner(node** root, lock_type& root_lock, unsigned pos, node* predecessor, const Key& key,+ node* newNode) {+#endif++ // check capacity+ if (this->numElements >= maxKeys) {+#ifdef IS_PARALLEL+ assert(!this->parent || this->parent->lock.is_write_locked());+ assert((this->parent) || root_lock.is_write_locked());+ assert(!this->parent || souffle::contains(locked_nodes, const_cast<node*>(this->parent)));+#endif++ // split this node+#ifdef IS_PARALLEL+ pos -= rebalance_or_split(root, root_lock, pos, locked_nodes);+#else+ pos -= rebalance_or_split(root, root_lock, pos);+#endif++ // complete insertion within new sibling if necessary+ if (pos > this->numElements) {+ // correct position+ pos = pos - static_cast<unsigned int>(this->numElements) - 1;++ // get new sibling+ auto other = this->parent->getChild(this->position + 1);++#ifdef IS_PARALLEL+ // make sure other side is write locked+ assert(other->lock.is_write_locked());+ assert(souffle::contains(locked_nodes, other));++ // search for new position (since other may have been altered in the meanwhile)+ size_type i = 0;+ for (; i <= other->numElements; ++i) {+ if (other->getChild(i) == predecessor) {+ break;+ }+ }++ pos = (i > static_cast<unsigned>(other->numElements)) ? 0 : static_cast<unsigned>(i);+ other->insert_inner(root, root_lock, pos, predecessor, key, newNode, locked_nodes);+#else+ other->insert_inner(root, root_lock, pos, predecessor, key, newNode);+#endif+ return;+ }+ }++ // move bigger keys one forward+ for (int i = static_cast<int>(this->numElements) - 1; i >= (int)pos; --i) {+ keys[i + 1] = keys[i];+ getChildren()[i + 2] = getChildren()[i + 1];+ ++getChildren()[i + 2]->position;+ }++ // ensure proper position+ assert(getChild(pos) == predecessor);++ // insert new element+ keys[pos] = key;+ getChildren()[pos + 1] = newNode;+ newNode->parent = this;+ newNode->position = static_cast<field_index_type>(pos) + 1;+ ++this->numElements;+ }++ public:+ /**+ * Prints a textual representation of this tree to the given output stream.+ * This feature is mainly intended for debugging and tuning purposes.+ *+ * @see btree::printTree+ */+ void printTree(std::ostream& out, const std::string& prefix) const {+ // print the header+ out << prefix << "@" << this << "[" << ((int)(this->position)) << "] - "+ << (this->inner ? "i" : "") << "node : " << this->numElements << "/" << maxKeys << " [";++ // print the keys+ for (unsigned i = 0; i < this->numElements; i++) {+ out << keys[i];+ if (i != this->numElements - 1) {+ out << ",";+ }+ }+ out << "]";++ // print references to children+ if (this->inner) {+ out << " - [";+ for (unsigned i = 0; i <= this->numElements; i++) {+ out << getChildren()[i];+ if (i != this->numElements) {+ out << ",";+ }+ }+ out << "]";+ }++#ifdef IS_PARALLEL+ // print the lock state+ if (this->lock.is_write_locked()) {+ std::cout << " locked";+ }+#endif++ out << "\n";++ // print the children recursively+ if (this->inner) {+ for (unsigned i = 0; i < this->numElements + 1; ++i) {+ static_cast<const inner_node*>(this)->children[i]->printTree(out, prefix + " ");+ }+ }+ }++ /**+ * A function decomposing the sub-tree rooted by this node into approximately equally+ * sized chunks. To minimize computational overhead, no strict load balance nor limit+ * on the number of actual chunks is given.+ *+ * @see btree::getChunks()+ *+ * @param res .. the list of chunks to be extended+ * @param num .. the number of chunks to be produced+ * @param begin .. the iterator to start the first chunk with+ * @param end .. the iterator to end the last chunk with+ * @return the handed in list of chunks extended by generated chunks+ */+ std::vector<chunk>& collectChunks(+ std::vector<chunk>& res, size_type num, const iterator& begin, const iterator& end) const {+ assert(num > 0);++ // special case: this node is empty+ if (isEmpty()) {+ if (begin != end) {+ res.push_back(chunk(begin, end));+ }+ return res;+ }++ // special case: a single chunk is requested+ if (num == 1) {+ res.push_back(chunk(begin, end));+ return res;+ }++ // cut-off+ if (this->isLeaf() || num < (this->numElements + 1)) {+ auto step = this->numElements / num;+ if (step == 0) {+ step = 1;+ }++ size_type i = 0;++ // the first chunk starts at the begin+ res.push_back(chunk(begin, iterator(this, static_cast<field_index_type>(step) - 1)));++ // split up the main part+ for (i = step - 1; i < this->numElements - step; i += step) {+ res.push_back(chunk(iterator(this, static_cast<field_index_type>(i)),+ iterator(this, static_cast<field_index_type>(i + step))));+ }++ // the last chunk runs to the end+ res.push_back(chunk(iterator(this, static_cast<field_index_type>(i)), end));++ // done+ return res;+ }++ // else: collect chunks of sub-set elements++ auto part = num / (this->numElements + 1);+ assert(part > 0);+ getChild(0)->collectChunks(res, part, begin, iterator(this, 0));+ for (size_type i = 1; i < this->numElements; i++) {+ getChild(i)->collectChunks(res, part, iterator(this, static_cast<field_index_type>(i - 1)),+ iterator(this, static_cast<field_index_type>(i)));+ }+ getChild(this->numElements)+ ->collectChunks(res, num - (part * this->numElements),+ iterator(this, static_cast<field_index_type>(this->numElements) - 1), end);++ // done+ return res;+ }++ /**+ * A function to verify the consistency of this node.+ *+ * @param root ... a reference to the root of the enclosing tree.+ * @return true if valid, false otherwise+ */+ template <typename Comp>+ bool check(Comp& comp, const node* root) const {+ bool valid = true;++ // check fill-state+ if (this->numElements > maxKeys || (this->parent != nullptr && this->numElements < minKeys)) {+ std::cout << "Node with " << this->numElements << "/" << maxKeys << " encountered!\n";+ valid = false;+ }++ // check root state+ if (root == this) {+ if (this->parent != nullptr) {+ std::cout << "Root not properly linked!\n";+ valid = false;+ }+ } else {+ // check parent relation+ if (!this->parent) {+ std::cout << "Invalid null-parent!\n";+ valid = false;+ } else {+ if (this->parent->getChildren()[this->position] != this) {+ std::cout << "Parent reference invalid!\n";+ std::cout << " Node: " << this << "\n";+ std::cout << " Parent: " << this->parent << "\n";+ std::cout << " Position: " << ((int)this->position) << "\n";+ valid = false;+ }++ // check parent key+ if (valid && this->position != 0 &&+ !(comp(this->parent->keys[this->position - 1], keys[0]) < ((isSet) ? 0 : 1))) {+ std::cout << "Left parent key not lower bound!\n";+ std::cout << " Node: " << this << "\n";+ std::cout << " Parent: " << this->parent << "\n";+ std::cout << " Position: " << ((int)this->position) << "\n";+ std::cout << " Key: " << (this->parent->keys[this->position]) << "\n";+ std::cout << " Lower: " << (keys[0]) << "\n";+ valid = false;+ }++ // check parent key+ if (valid && this->position != this->parent->numElements &&+ !(comp(keys[this->numElements - 1], this->parent->keys[this->position]) <+ ((isSet) ? 0 : 1))) {+ std::cout << "Right parent key not lower bound!\n";+ std::cout << " Node: " << this << "\n";+ std::cout << " Parent: " << this->parent << "\n";+ std::cout << " Position: " << ((int)this->position) << "\n";+ std::cout << " Key: " << (this->parent->keys[this->position]) << "\n";+ std::cout << " Upper: " << (keys[0]) << "\n";+ valid = false;+ }+ }+ }++ // check element order+ if (this->numElements > 0) {+ for (unsigned i = 0; i < this->numElements - 1; i++) {+ if (valid && !(comp(keys[i], keys[i + 1]) < ((isSet) ? 0 : 1))) {+ std::cout << "Element order invalid!\n";+ std::cout << " @" << this << " key " << i << " is " << keys[i] << " vs "+ << keys[i + 1] << "\n";+ valid = false;+ }+ }+ }++ // check state of sub-nodes+ if (this->inner) {+ for (unsigned i = 0; i <= this->numElements; i++) {+ valid &= getChildren()[i]->check(comp, root);+ }+ }++ return valid;+ }+ }; // namespace detail++ /**+ * The data type representing inner nodes of the b-tree. It extends+ * the generic implementation of a node by the storage locations+ * of child pointers.+ */+ struct inner_node : public node {+ // references to child nodes owned by this node+ node* children[node::maxKeys + 1];++ // a simple default constructor initializing member fields+ inner_node() : node(true) {}++ // clear up child nodes recursively+ ~inner_node() {+ for (unsigned i = 0; i <= this->numElements; ++i) {+ if (children[i] != nullptr) {+ if (children[i]->isLeaf()) {+ delete static_cast<leaf_node*>(children[i]);+ } else {+ delete static_cast<inner_node*>(children[i]);+ }+ }+ }+ }+ };++ /**+ * The data type representing leaf nodes of the b-tree. It does not+ * add any capabilities to the generic node type.+ */+ struct leaf_node : public node {+ // a simple default constructor initializing member fields+ leaf_node() : node(false) {}+ };++ // ------------------- iterators ------------------------++public:+ /**+ * The iterator type to be utilized for scanning through btree instances.+ */+ class iterator : public std::iterator<std::bidirectional_iterator_tag, Key> {+ public:+ // a pointer to the node currently referred to+ // node const* cur;+ node* cur;++ // the index of the element currently addressed within the referenced node+ field_index_type pos = 0;++ using iterator_category = std::forward_iterator_tag;+ using value_type = Key;+ using difference_type = ptrdiff_t;+ using pointer = value_type*;+ using reference = value_type&;++ // default constructor -- creating an end-iterator+ iterator() : cur(nullptr) {}++ // creates an iterator referencing a specific element within a given node+ // iterator(node const* cur, field_index_type pos) : cur(cur), pos(pos) {}+ // iterator(node* cur, field_index_type pos) : cur(cur), pos(pos) {}+ iterator(node const* cur, field_index_type pos) : cur(const_cast<node*>(cur)), pos(pos) {}++ // a copy constructor+ iterator(const iterator& other) : cur(other.cur), pos(other.pos) {}++ // an assignment operator+ iterator& operator=(const iterator& other) {+ cur = other.cur;+ pos = other.pos;+ return *this;+ }++ // the equality operator as required by the iterator concept+ bool operator==(const iterator& other) const {+ return cur == other.cur && pos == other.pos;+ }++ // the not-equality operator as required by the iterator concept+ bool operator!=(const iterator& other) const {+ return !(*this == other);+ }++ // the deref operator as required by the iterator concept+ const Key& operator*() const {+ return cur->keys[pos];+ }++ // Resolve an ambiguous position at the end of a leaf by moving forward.+ // Must be called from the end of a leaf or behaviour is undefined.+ void resolvePosition() {+ // Save current node in case we are at the end of the tree+ auto temp = cur;++ // While we are at the end of node, move up to parent+ do {+ pos = cur->getPositionInParent();+ cur = cur->getParent();+ } while (cur && pos == cur->getNumElements());++ // Check if we were at the end of the tree.+ // If so, reset iterator+ if (!cur) {+ cur = temp;+ pos = static_cast<field_index_type>(cur->getNumElements());+ }+ }++ // the increment operator as required by the iterator concept+ iterator& operator++() {+ if (cur) {+ if (cur->isInner()) {+ // Currently in an inner node so move forward one place+ cur = cur->getChild(pos + 1);+ while (cur->isInner()) {+ cur = cur->getChild(0);+ }+ pos = 0;+ } else {+ // In a leaf so just increment the position+ ++pos;+ // If we have reached the end of the leaf walk up to an inner node+ if (pos == cur->getNumElements()) {+ resolvePosition();+ }+ }+ }+ return *this;+ }++ // the decrement operator as required by the iterator concept+ iterator& operator--() {+ if (cur) {+ if (cur->isInner()) {+ // Currently in an inner node so move back one place+ cur = cur->getChild(pos);+ while (cur->isInner()) {+ cur = cur->getChild(cur->getNumElements());+ }+ pos = static_cast<field_index_type>(cur->getNumElements()) - 1;+ } else {+ // In a leaf so decrement the position+ // Check if pos > 0 to avoid unsigned wrap-around issues+ if (pos > 0) {+ --pos;+ } else {+ // Save the current node in case we are at the beginning+ auto temp = cur;++ // Walk back up the tree.+ do {+ pos = cur->getPositionInParent();+ cur = cur->getParent();+ } while (cur && pos == 0);++ // If we were at the beginning of the tree, reset the iterator+ if (!cur) {+ cur = temp;+ }+ }+ }+ }+ return *this;+ }++ // prints a textual representation of this iterator to the given stream (mainly for debugging)+ void print(std::ostream& out = std::cout) const {+ out << cur << "[" << (int)pos << "]";+ }+ };++ /**+ * A collection of operation hints speeding up some of the involved operations+ * by exploiting temporal locality.+ */+ template <unsigned size = 1>+ struct btree_operation_hints {+ using node_cache = LRUCache<node*, size>;++ // the node where the last insertion terminated+ node_cache last_insert;++ // the node where the last find-operation terminated+ node_cache last_find_end;++ // the node where the last lower-bound operation terminated+ node_cache last_lower_bound_end;++ // the node where the last upper-bound operation terminated+ node_cache last_upper_bound_end;++ // default constructor+ btree_operation_hints() = default;++ // resets all hints (to be triggered e.g. when deleting nodes)+ void clear() {+ last_insert.clear(nullptr);+ last_find_end.clear(nullptr);+ last_lower_bound_end.clear(nullptr);+ last_upper_bound_end.clear(nullptr);+ }+ };++ using operation_hints = btree_operation_hints<1>;++protected:+#ifdef IS_PARALLEL+ // a pointer to the root node of this tree+ node* volatile root;++ // a lock to synchronize update operations on the root pointer+ lock_type root_lock;+#else+ // a pointer to the root node of this tree+ node* root;++ // required to not duplicate too much code+ lock_type root_lock;+#endif++ // a pointer to the left-most node of this tree (initial note for iteration)+ leaf_node* leftmost;++ /* -------------- operator hint statistics ----------------- */++ // an aggregation of statistical values of the hint utilization+ struct hint_statistics {+ // the counter for insertion operations+ CacheAccessCounter inserts;++ // the counter for contains operations+ CacheAccessCounter contains;++ // the counter for lower_bound operations+ CacheAccessCounter lower_bound;++ // the counter for upper_bound operations+ CacheAccessCounter upper_bound;+ };++ // the hint statistic of this b-tree instance+ mutable hint_statistics hint_stats;++public:+ // the maximum number of keys stored per node+ static constexpr std::size_t max_keys_per_node = node::maxKeys;++ // -- ctors / dtors --++ // the default constructor creating an empty tree+ btree_delete(Comparator comp = Comparator(), WeakComparator weak_comp = WeakComparator())+ : comp(std::move(comp)), weak_comp(std::move(weak_comp)), root(nullptr), leftmost(nullptr) {}++ // a constructor creating a tree from the given iterator range+ template <typename Iter>+ btree_delete(const Iter& a, const Iter& b) : root(nullptr), leftmost(nullptr) {+ insert(a, b);+ }++ // a move constructor+ btree_delete(btree_delete&& other)+ : comp(other.comp), weak_comp(other.weak_comp), root(other.root), leftmost(other.leftmost) {+ other.root = nullptr;+ other.leftmost = nullptr;+ }++ // a copy constructor+ btree_delete(const btree_delete& set)+ : comp(set.comp), weak_comp(set.weak_comp), root(nullptr), leftmost(nullptr) {+ // use assignment operator for a deep copy+ *this = set;+ }++protected:+ /**+ * An internal constructor enabling the specific creation of a tree+ * based on internal parameters.+ */+ btree_delete(size_type /* size */, node* root, leaf_node* leftmost) : root(root), leftmost(leftmost) {}++public:+ // the destructor freeing all contained nodes+ ~btree_delete() {+ clear();+ }++ // -- mutators and observers --++ // emptiness check+ bool empty() const {+ return root == nullptr;+ }++ // determines the number of elements in this tree+ size_type size() const {+ return (root) ? root->countEntries() : 0;+ }++ /**+ * Inserts the given key into this tree.+ */+ bool insert(const Key& k) {+ operation_hints hints;+ return insert(k, hints);+ }++ /**+ * Inserts the given key into this tree.+ */+ bool insert(const Key& k, operation_hints& hints) {+#ifdef IS_PARALLEL++ // special handling for inserting first element+ while (root == nullptr) {+ // try obtaining root-lock+ if (!root_lock.try_start_write()) {+ // somebody else was faster => re-check+ continue;+ }++ // check loop condition again+ if (root != nullptr) {+ // somebody else was faster => normal insert+ root_lock.end_write();+ break;+ }++ // create new node+ leftmost = new leaf_node();+ leftmost->numElements = 1;+ leftmost->keys[0] = k;+ root = leftmost;++ // operation complete => we can release the root lock+ root_lock.end_write();++ hints.last_insert.access(leftmost);++ return true;+ }++ // insert using iterative implementation++ node* cur = nullptr;++ // test last insert hints+ lock_type::Lease cur_lease;++ auto checkHint = [&](node* last_insert) {+ // ignore null pointer+ if (!last_insert) return false;+ // get a read lease on indicated node+ auto hint_lease = last_insert->lock.start_read();+ // check whether it covers the key+ if (!weak_covers(last_insert, k)) return false;+ // and if there was no concurrent modification+ if (!last_insert->lock.validate(hint_lease)) return false;+ // use hinted location+ cur = last_insert;+ // and keep lease+ cur_lease = hint_lease;+ // we found a hit+ return true;+ };++ if (hints.last_insert.any(checkHint)) {+ // register this as a hit+ hint_stats.inserts.addHit();+ } else {+ // register this as a miss+ hint_stats.inserts.addMiss();+ }++ // if there is no valid hint ..+ if (!cur) {+ do {+ // get root - access lock+ auto root_lease = root_lock.start_read();++ // start with root+ cur = root;++ // get lease of the next node to be accessed+ cur_lease = cur->lock.start_read();++ // check validity of root pointer+ if (root_lock.end_read(root_lease)) {+ break;+ }++ } while (true);+ }++ while (true) {+ // handle inner nodes+ if (cur->inner) {+ auto a = &(cur->keys[0]);+ auto b = &(cur->keys[cur->numElements]);++ auto pos = search.lower_bound(k, a, b, weak_comp);+ auto idx = pos - a;++ // early exit for sets+ if (isSet && pos != b && weak_equal(*pos, k)) {+ // validate results+ if (!cur->lock.validate(cur_lease)) {+ // start over again+ return insert(k, hints);+ }++ // update provenance information+ if (typeid(Comparator) != typeid(WeakComparator) && less(k, *pos)) {+ if (!cur->lock.try_upgrade_to_write(cur_lease)) {+ // start again+ return insert(k, hints);+ }+ update(*pos, k);+ cur->lock.end_write();+ return true;+ }++ // we found the element => no check of lock necessary+ return false;+ }++ // get next pointer+ auto next = cur->getChild(idx);++ // get lease on next level+ auto next_lease = next->lock.start_read();++ // check whether there was a write+ if (!cur->lock.end_read(cur_lease)) {+ // start over+ return insert(k, hints);+ }++ // go to next+ cur = next;++ // move on lease+ cur_lease = next_lease;++ continue;+ }++ // the rest is for leaf nodes+ assert(!cur->inner);++ // -- insert node in leaf node --++ auto a = &(cur->keys[0]);+ auto b = &(cur->keys[cur->numElements]);++ auto pos = search.upper_bound(k, a, b, weak_comp);+ auto idx = pos - a;++ // early exit for sets+ if (isSet && pos != a && weak_equal(*(pos - 1), k)) {+ // validate result+ if (!cur->lock.validate(cur_lease)) {+ // start over again+ return insert(k, hints);+ }++ // update provenance information+ if (typeid(Comparator) != typeid(WeakComparator) && less(k, *(pos - 1))) {+ if (!cur->lock.try_upgrade_to_write(cur_lease)) {+ // start again+ return insert(k, hints);+ }+ update(*(pos - 1), k);+ cur->lock.end_write();+ return true;+ }++ // we found the element => done+ return false;+ }++ // upgrade to write-permission+ if (!cur->lock.try_upgrade_to_write(cur_lease)) {+ // something has changed => restart+ hints.last_insert.access(cur);+ return insert(k, hints);+ }++ if (cur->numElements >= node::maxKeys) {+ // -- lock parents --+ auto priv = cur;+ auto parent = priv->parent;+ std::vector<node*> parents;+ do {+ if (parent) {+ parent->lock.start_write();+ while (true) {+ // check whether parent is correct+ if (parent == priv->parent) {+ break;+ }+ // switch parent+ parent->lock.abort_write();+ parent = priv->parent;+ parent->lock.start_write();+ }+ } else {+ // lock root lock => since cur is root+ root_lock.start_write();+ }++ // record locked node+ parents.push_back(parent);++ // stop at "sphere of influence"+ if (!parent || !parent->isFull()) {+ break;+ }++ // go one step higher+ priv = parent;+ parent = parent->parent;++ } while (true);++ // split this node+ auto old_root = root;+ idx -= cur->rebalance_or_split(+ const_cast<node**>(&root), root_lock, static_cast<int>(idx), parents);++ // release parent lock+ for (auto it = parents.rbegin(); it != parents.rend(); ++it) {+ auto parent = *it;++ // release this lock+ if (parent) {+ parent->lock.end_write();+ } else {+ if (old_root != root) {+ root_lock.end_write();+ } else {+ root_lock.abort_write();+ }+ }+ }++ // insert element in right fragment+ if (((size_type)idx) > cur->numElements) {+ // release current lock+ cur->lock.end_write();++ // insert in sibling+ return insert(k, hints);+ }+ }++ // ok - no split necessary+ assert(cur->numElements < node::maxKeys && "Split required!");++ // move keys+ for (int j = static_cast<int>(cur->numElements); j > static_cast<int>(idx); --j) {+ cur->keys[j] = cur->keys[j - 1];+ }++ // insert new element+ cur->keys[idx] = k;+ cur->numElements++;++ // release lock on current node+ cur->lock.end_write();++ // remember last insertion position+ hints.last_insert.access(cur);+ return true;+ }++#else+ // special handling for inserting first element+ if (empty()) {+ // create new node+ leftmost = new leaf_node();+ leftmost->numElements = 1;+ leftmost->keys[0] = k;+ root = leftmost;++ hints.last_insert.access(leftmost);++ return true;+ }++ // insert using iterative implementation+ node* cur = root;++ auto checkHints = [&](node* last_insert) {+ if (!last_insert) return false;+ if (!weak_covers(last_insert, k)) return false;+ cur = last_insert;+ return true;+ };++ // test last insert+ if (hints.last_insert.any(checkHints)) {+ hint_stats.inserts.addHit();+ } else {+ hint_stats.inserts.addMiss();+ }++ while (true) {+ // handle inner nodes+ if (cur->inner) {+ auto a = &(cur->keys[0]);+ auto b = &(cur->keys[cur->numElements]);++ auto pos = search.lower_bound(k, a, b, weak_comp);+ auto idx = pos - a;++ // early exit for sets+ if (isSet && pos != b && weak_equal(*pos, k)) {+ // update provenance information+ if (typeid(Comparator) != typeid(WeakComparator) && less(k, *pos)) {+ update(*pos, k);+ return true;+ }++ return false;+ }++ cur = cur->getChild(idx);+ continue;+ }++ // the rest is for leaf nodes+ assert(!cur->inner);++ // -- insert node in leaf node --++ auto a = &(cur->keys[0]);+ auto b = &(cur->keys[cur->numElements]);++ auto pos = search.upper_bound(k, a, b, weak_comp);+ auto idx = pos - a;++ // early exit for sets+ if (isSet && pos != a && weak_equal(*(pos - 1), k)) {+ // update provenance information+ if (typeid(Comparator) != typeid(WeakComparator) && less(k, *(pos - 1))) {+ update(*(pos - 1), k);+ return true;+ }++ return false;+ }++ if (cur->numElements >= node::maxKeys) {+ // split this node+ idx -= cur->rebalance_or_split(&root, root_lock, static_cast<int>(idx));++ // insert element in right fragment+ if (((size_type)idx) > cur->numElements) {+ idx -= cur->numElements + 1;+ cur = cur->parent->getChild(cur->position + 1);+ }+ }++ // ok - no split necessary+ assert(cur->numElements < node::maxKeys && "Split required!");++ // move keys+ for (int j = static_cast<int>(cur->numElements); j > idx; --j) {+ cur->keys[j] = cur->keys[j - 1];+ }++ // insert new element+ cur->keys[idx] = k;+ cur->numElements++;++ // remember last insertion position+ hints.last_insert.access(cur);++ return true;+ }+#endif+ }++ /**+ * Inserts the given range of elements into this tree.+ */+ template <typename Iter>+ void insert(const Iter& a, const Iter& b) {+ // TODO: improve this beyond a naive insert+ operation_hints hints;+ // a naive insert so far .. seems to work fine+ for (auto it = a; it != b; ++it) {+ // use insert with hint+ insert(*it, hints);+ }+ }++ /**+ * Compute the number of instances of a key in the tree+ */+ size_type get_count(const Key& k) const {+ if (empty()) {+ return 0;+ }+ if (isSet) {+ auto iter = internal_find(k);+ if (iter != end()) {+ return 1;+ } else {+ return 0;+ }+ } else {+ auto lower_iter = internal_lower_bound(k);+ if (lower_iter != end() && equal(*lower_iter, k)) {+ return distance(lower_iter, internal_upper_bound(k));+ } else {+ return 0;+ }+ }+ }++ /**+ * Erase the given key from the tree.+ * Return the number of erased keys.+ */+ size_type erase(const Key& k) {+ if (empty()) {+ return 0;+ }+ if (isSet) {+ iterator iter = internal_find(k);+ if (iter == end()) {+ // Key not found+ return 0;+ } else {+ erase(iter);+ return 1;+ }+ } else {+ iterator lower_iter = internal_lower_bound(k);+ if (lower_iter != end() && equal(*lower_iter, k)) {+ size_type count = distance(lower_iter, internal_upper_bound(k));+ for (size_type i = 0; i < count; i++) {+ erase(lower_iter);+ }+ return count;+ } else {+ return 0;+ }+ }+ }++ /**+ * Erase the key pointed to by the iterator.+ * Advance the iterator to the next position.+ */+ void erase(iterator& iter) {+ bool internal_delete = false;+ // @julienhenry+ // iter.cur->lock.start_write();+ if (iter.cur->isInner()) {+ // In an inner node so swap key with previous key+ iterator temp_iter(iter);+ --iter;+ Key temp_key = temp_iter.cur->keys[temp_iter.pos];+ temp_iter.cur->keys[temp_iter.pos] = iter.cur->keys[iter.pos];+ iter.cur->keys[iter.pos] = temp_key;+ internal_delete = true;+ }+ // Now on a leaf node+ assert(iter.cur->isLeaf());++ // Delete the key, move other keys backwards and update size+ iter.cur->keys[iter.pos].~Key();+ for (size_type i = iter.pos + 1; i < iter.cur->getNumElements(); ++i) {+ iter.cur->keys[i - 1] = iter.cur->keys[i];+ }+ iter.cur->numElements--;++ // Next, ensure nodes have not become too small+ iterator res(iter);+ while (true) {+ auto parent = iter.cur->parent;+ if (!parent) {+ // cur is root+ if (iter.cur->getNumElements() == 0) {+ // Root has become empty+ if (iter.cur->isLeaf()) {+ // Whole tree has become empty+ root = nullptr;+ leftmost = nullptr;+ res.cur = nullptr;+ res.pos = 0;+ } else {+ // Whole tree now contained in child at position 0+ root = iter.cur->getChild(0);+ root->parent = nullptr;+ }+ delete iter.cur;+ }+ break;+ }+ if (iter.cur->getNumElements() >= node::minKeys) {+ break;+ }+ bool merged = merge_or_rebalance(iter);+ if (iter.cur->isLeaf()) {+ res = iter;+ }+ if (!merged) {+ break;+ }+ iter.cur = iter.cur->getParent();+ }+ iter = res;++ // Finally, check the iterator points to the right position+ if (iter.cur) {+ // Tree hasn't become empty+ // If iterator is at end of node, resolve the position+ if (iter.pos == iter.cur->getNumElements()) {+ iter.resolvePosition();+ }++ // If we deleted internally, increment the iterator+ if (internal_delete) {+ ++iter;+ }+ }+ // iter.cur->lock.end_write(); //@julienhenry+ }++private:+ /**+ * Find the given key in a non-empty tree.+ * If found, return an iterator pointing to the key.+ * Otherwise, return end()+ */+ iterator internal_find(const Key& k) const {+ auto iter = iterator(root, 0);+ while (true) {+ auto a = &(iter.cur->keys[0]);+ auto b = &(iter.cur->keys[iter.cur->numElements]);++ auto pos = search(k, a, b, comp);+ iter.pos = static_cast<field_index_type>(pos - a);++ if (pos < b && equal(*pos, k)) {+ return iter;+ }++ if (!iter.cur->inner) {+ return end();+ }++ // continue search in child node+ iter.cur = iter.cur->getChild(iter.pos);+ }+ }++ /**+ * Find the first key in the tree greater or equal to the given key.+ * If found, return an iterator pointing to the key.+ * Otherwise, return end().+ */+ iterator internal_lower_bound(const Key& k) const {+ iterator iter = iterator(root, 0);+ iterator res;+ while (true) {+ auto a = &(iter.cur->keys[0]);+ auto b = &(iter.cur->keys[iter.cur->numElements]);++ auto pos = search.lower_bound(k, a, b, comp);+ iter.pos = static_cast<field_index_type>(pos - a);++ if (pos < b) {+ res = iter;+ if (isSet && equal(*pos, k)) {+ // Early exit for sets+ break;+ }+ }++ if (!iter.cur->inner) {+ break;+ }++ iter.cur = iter.cur->getChild(iter.pos);+ }+ if (!res.cur) {+ res = iter;+ }+ return res;+ }++ /**+ * Find the first key in the tree strictly greater than the given key.+ * If found, return an iterator pointing to the key.+ * Otherwise, return end().+ */+ iterator internal_upper_bound(const Key& k) const {+ iterator iter = iterator(root, 0);+ iterator res;+ while (true) {+ auto a = &(iter.cur->keys[0]);+ auto b = &(iter.cur->keys[iter.cur->numElements]);++ auto pos = search.upper_bound(k, a, b, comp);++ iter.pos = static_cast<field_index_type>(pos - a);++ if (pos < b) {+ res = iter;+ }++ if (!iter.cur->inner) {+ break;+ }++ iter.cur = iter.cur->getChild(iter.pos);+ }+ if (!res.cur) {+ res = iter;+ }+ return res;+ }++ /**+ * Merge or rebalance the current node of the iterator.+ * Update the iterator to point to its new position.+ * Return true if a merge occured, else false.+ */+ bool merge_or_rebalance(iterator& iter) {+ // Only called when the current node is too small+ assert(iter.cur->getNumElements() < node::minKeys);++ auto parent = iter.cur->getParent();+ auto siblings = parent->getChildren();+ auto pos = iter.cur->getPositionInParent();+ if (pos < parent->getNumElements()) {+ // Has right sibling+ auto right = siblings[pos + 1];+ if (iter.cur->getNumElements() + right->getNumElements() + 1 <= node::maxKeys) {+ // Merge with right sibling+ merge_with_right_sibling(iter, right);+ return true;+ } else if (pos > 0) {+ // Has a left sibling+ auto left = siblings[pos - 1];+ if (left->getNumElements() + iter.cur->getNumElements() + 1 <= node::maxKeys) {+ // Merge into left sibling+ merge_into_left_sibling(left, iter);+ return true;+ } else {+ // Rebalance from left sibling+ rebalance_from_left_sibling(left, iter);+ return false;+ }+ } else {+ // Can't merge with right and no left sibling so must rebalance from right+ rebalance_from_right_sibling(iter, right);+ return false;+ }+ } else {+ // No right sibling, so must have a left sibling+ assert(pos > 0);+ auto left = siblings[pos - 1];+ if (left->getNumElements() + iter.cur->getNumElements() + 1 <= node::maxKeys) {+ // Merge into left sibling+ merge_into_left_sibling(left, iter);+ return true;+ } else {+ // Rebalance from left sibling+ rebalance_from_left_sibling(left, iter);+ return false;+ }+ }+ }++ /**+ * Merge an iterator with its right sibling, updating the position of the iterator+ */+ void merge_with_right_sibling(iterator& iter, node* right) {+ merge(iter.cur, right);+ }++ /**+ * Merge an iterator into its left sibling, updating the position of the iterator+ */+ void merge_into_left_sibling(node* left, iterator& iter) {+ auto left_size = left->getNumElements();+ merge(left, iter.cur);+ iter.cur = left;+ iter.pos += static_cast<field_index_type>(left_size) + 1;+ }++ /**+ * Merge nodes, destroying the sibling on the right.+ */+ void merge(node* left, node* right) {+ auto parent = left->getParent();+ // Left must have a parent+ assert(parent);+ auto siblings = parent->getChildren();++ auto pos = left->getPositionInParent();+ // Node isn't the right-most node in its parent+ assert(pos < parent->getNumElements());++ // Update the parent node by:+ // 1. Moving dividing key to left node+ left->keys[left->getNumElements()] = parent->keys[pos];+ // 2. Moving keys and siblings found to the right of the+ // dividing key back one place+ for (size_type i = pos + 1; i < parent->getNumElements(); ++i) {+ parent->keys[i - 1] = parent->keys[i];+ auto sibling = siblings[i + 1];+ sibling->position--;+ siblings[i] = sibling;+ }+ // 3. Decrementing its size+ parent->numElements--;++ // Move keys from right node to left+ for (size_type i = left->getNumElements() + 1, j = 0; j < right->getNumElements(); ++i, ++j) {+ left->keys[i] = right->keys[j];+ }++ // If left is an inner node, move children from right to left+ if (left->isInner()) {+ // Right must also be an inner node+ assert(right->isInner());+ auto left_children = left->getChildren();+ auto right_children = right->getChildren();+ for (size_type i = left->getNumElements() + 1, j = 0; j <= right->getNumElements(); ++i, ++j) {+ auto child = right_children[j];+ child->parent = left;+ child->position = static_cast<field_index_type>(i);+ left_children[i] = child;+ }+ }++ // Update the number of elements in the left+ left->numElements += right->getNumElements() + 1;++ // Delete the right node+ delete right;+ }++ /**+ * Rebalance the given iterator node by moving keys from the right.+ * Update the iterator position.+ */+ void rebalance_from_right_sibling(iterator& iter, node* right) {+ auto left = iter.cur;+ auto parent = left->getParent();+ // Left must have a parent+ assert(parent);++ auto pos = left->getPositionInParent();+ // Node isn't the right-most node in its parent+ assert(pos < parent->getNumElements());++ // Number of keys to move+ size_type to_move = (right->getNumElements() - node::minKeys) / 2 + 1;++ // Move down dividing key from parent+ left->keys[left->getNumElements()] = parent->keys[pos];++ // Move keys from right sibling+ for (size_type i = left->getNumElements() + 1, j = 0; j < to_move - 1; ++i, ++j) {+ left->keys[i] = right->keys[j];+ }++ // Move key up to dividing position+ parent->keys[pos] = right->keys[to_move - 1];++ // Move remaining keys in right node back+ for (size_type i = to_move; i < right->getNumElements(); ++i) {+ right->keys[i - to_move] = right->keys[i];+ }++ // If left is an inner node, move children+ if (left->isInner()) {+ // Right must also be an inner node+ assert(right->isInner());+ auto left_children = left->getChildren();+ auto right_children = right->getChildren();++ // Move children from right node to left+ for (size_type i = left->getNumElements() + 1, j = 0; j < to_move; ++i, ++j) {+ auto child = right_children[j];+ child->parent = left;+ child->position = static_cast<field_index_type>(i);+ left_children[i] = child;+ }++ // Move right children back+ for (size_type i = to_move; i <= right->getNumElements(); ++i) {+ auto child = right_children[i];+ child->position = static_cast<field_index_type>(i - to_move);+ right_children[i - to_move] = child;+ }+ }++ // Update sizes+ left->numElements += to_move;+ right->numElements -= to_move;+ }++ /**+ * Rebalance the given iterator node by moving keys from the left sibling.+ * Update the iterator to its new position.+ */+ void rebalance_from_left_sibling(node* left, iterator& iter) {+ auto right = iter.cur;+ auto parent = right->getParent();+ // Left must have a parent+ assert(parent);++ auto pos = right->getPositionInParent();+ // Node isn't the left-most node in its parent+ assert(pos > 0);++ // Number of keys to move+ size_type to_move = (left->getNumElements() - node::minKeys) / 2 + 1;++ // Move keys in right node along+ for (size_type i = right->getNumElements() + to_move - 1; i >= to_move; --i) {+ right->keys[i] = right->keys[i - to_move];+ }++ // Move down dividing key from parent+ right->keys[to_move - 1] = parent->keys[pos - 1];++ // Move keys from left sibling+ for (size_type i = left->getNumElements() - to_move + 1, j = 0; j < to_move - 1; ++i, ++j) {+ right->keys[j] = left->keys[i];+ }++ // Move key up to dividing position+ parent->keys[pos - 1] = left->keys[left->getNumElements() - to_move];++ // If right is an inner node, move children+ if (right->isInner()) {+ // Left must also be an inner node+ assert(left->isInner());+ auto left_children = left->getChildren();+ auto right_children = right->getChildren();++ // Move right children along+ for (size_type i = right->getNumElements() + to_move; i >= to_move; --i) {+ auto child = right_children[i - to_move];+ child->position = static_cast<field_index_type>(i);+ right_children[i] = child;+ }++ // Move children from left node to right+ for (size_type i = left->getNumElements() - to_move + 1, j = 0; j < to_move; ++i, ++j) {+ auto child = left_children[i];+ child->parent = right;+ child->position = static_cast<field_index_type>(j);+ right_children[j] = child;+ }+ }++ // Update iterator position+ iter.pos += static_cast<field_index_type>(to_move);++ // Update sizes+ left->numElements -= to_move;+ right->numElements += to_move;+ }++public:+ /**+ * Return the rightmost node in the tree.+ * Currently inefficient as tree contains no reference to rightmost.+ */+ node* rightmost() const {+ auto rightmost = root;+ if (rightmost) {+ while (rightmost->isInner()) {+ rightmost = rightmost->getChild(rightmost->getNumElements());+ }+ }+ return rightmost;+ }++ // Obtains an iterator referencing the first element of the tree.+ iterator begin() const {+ return iterator(leftmost, 0);+ }++ // Obtains an iterator referencing the position after the last element of the tree.+ iterator end() const {+ node* rightmost = this->rightmost();+ if (rightmost) {+ return iterator(rightmost, static_cast<field_index_type>(rightmost->getNumElements()));+ } else {+ return iterator();+ }+ }++ /**+ * Partitions the full range of this set into up to a given number of chunks.+ * The chunks will cover approximately the same number of elements. Also, the+ * number of chunks will only approximate the desired number of chunks.+ *+ * @param num .. the number of chunks requested+ * @return a list of chunks partitioning this tree+ */+ std::vector<chunk> partition(size_type num) const {+ return getChunks(num);+ }++ std::vector<chunk> getChunks(size_type num) const {+ std::vector<chunk> res;+ if (empty()) {+ return res;+ }+ return root->collectChunks(res, num, begin(), end());+ }++ /**+ * Determines whether the given element is a member of this tree.+ */+ bool contains(const Key& k) const {+ operation_hints hints;+ return contains(k, hints);+ }++ /**+ * Determines whether the given element is a member of this tree.+ */+ bool contains(const Key& k, operation_hints& hints) const {+ return find(k, hints) != end();+ }++ /**+ * Locates the given key within this tree and returns an iterator+ * referencing its position. If not found, an end-iterator will be returned.+ */+ iterator find(const Key& k) const {+ operation_hints hints;+ return find(k, hints);+ }++ /**+ * Locates the given key within this tree and returns an iterator+ * referencing its position. If not found, an end-iterator will be returned.+ */+ iterator find(const Key& k, operation_hints& hints) const {+ if (empty()) {+ return end();+ }++ node* cur = root;++ auto checkHints = [&](node* last_find_end) {+ if (!last_find_end) return false;+ if (!covers(last_find_end, k)) return false;+ cur = last_find_end;+ return true;+ };++ // test last location searched (temporal locality)+ if (hints.last_find_end.any(checkHints)) {+ // register it as a hit+ hint_stats.contains.addHit();+ } else {+ // register it as a miss+ hint_stats.contains.addMiss();+ }++ // an iterative implementation (since 2/7 faster than recursive)++ while (true) {+ auto a = &(cur->keys[0]);+ auto b = &(cur->keys[cur->numElements]);++ auto pos = search(k, a, b, comp);++ if (pos < b && equal(*pos, k)) {+ hints.last_find_end.access(cur);+ return iterator(cur, static_cast<field_index_type>(pos - a));+ }++ if (!cur->inner) {+ hints.last_find_end.access(cur);+ return end();+ }++ // continue search in child node+ cur = cur->getChild(pos - a);+ }+ }++ /**+ * Obtains a lower boundary for the given key -- hence an iterator referencing+ * the smallest value that is not less the given key. If there is no such element,+ * an end-iterator will be returned.+ */+ iterator lower_bound(const Key& k) const {+ operation_hints hints;+ return lower_bound(k, hints);+ }++ /**+ * Obtains a lower boundary for the given key -- hence an iterator referencing+ * the smallest value that is not less the given key. If there is no such element,+ * an end-iterator will be returned.+ */+ iterator lower_bound(const Key& k, operation_hints& hints) const {+ if (empty()) {+ return end();+ }++ node* cur = root;++ auto checkHints = [&](node* last_lower_bound_end) {+ if (!last_lower_bound_end) return false;+ if (!covers(last_lower_bound_end, k)) return false;+ cur = last_lower_bound_end;+ return true;+ };++ // test last searched node+ if (hints.last_lower_bound_end.any(checkHints)) {+ hint_stats.lower_bound.addHit();+ } else {+ hint_stats.lower_bound.addMiss();+ }++ iterator res = end();+ while (true) {+ auto a = &(cur->keys[0]);+ auto b = &(cur->keys[cur->numElements]);++ auto pos = search.lower_bound(k, a, b, comp);+ auto idx = static_cast<field_index_type>(pos - a);++ if (!cur->inner) {+ hints.last_lower_bound_end.access(cur);+ return (pos != b) ? iterator(cur, idx) : res;+ }++ if (isSet && pos != b && equal(*pos, k)) {+ return iterator(cur, idx);+ }++ if (pos != b) {+ res = iterator(cur, idx);+ }++ cur = cur->getChild(idx);+ }+ }++ /**+ * Obtains an upper boundary for the given key -- hence an iterator referencing+ * the first element that the given key is less than the referenced value. If+ * there is no such element, an end-iterator will be returned.+ */+ iterator upper_bound(const Key& k) const {+ operation_hints hints;+ return upper_bound(k, hints);+ }++ /**+ * Obtains an upper boundary for the given key -- hence an iterator referencing+ * the first element that the given key is less than the referenced value. If+ * there is no such element, an end-iterator will be returned.+ */+ iterator upper_bound(const Key& k, operation_hints& hints) const {+ if (empty()) {+ return end();+ }++ node* cur = root;++ auto checkHints = [&](node* last_upper_bound_end) {+ if (!last_upper_bound_end) return false;+ if (!coversUpperBound(last_upper_bound_end, k)) return false;+ cur = last_upper_bound_end;+ return true;+ };++ // test last search node+ if (hints.last_upper_bound_end.any(checkHints)) {+ hint_stats.upper_bound.addHit();+ } else {+ hint_stats.upper_bound.addMiss();+ }++ iterator res = end();+ while (true) {+ auto a = &(cur->keys[0]);+ auto b = &(cur->keys[cur->numElements]);++ auto pos = search.upper_bound(k, a, b, comp);+ auto idx = static_cast<field_index_type>(pos - a);++ if (!cur->inner) {+ hints.last_upper_bound_end.access(cur);+ return (pos != b) ? iterator(cur, idx) : res;+ }++ if (pos != b) {+ res = iterator(cur, idx);+ }++ cur = cur->getChild(idx);+ }+ }++ /**+ * Clears this tree.+ */+ void clear() {+ if (root != nullptr) {+ if (root->isLeaf()) {+ delete static_cast<leaf_node*>(root);+ } else {+ delete static_cast<inner_node*>(root);+ }+ }+ root = nullptr;+ leftmost = nullptr;+ }++ /**+ * Swaps the content of this tree with the given tree. This+ * is a much more efficient operation than creating a copy and+ * realizing the swap utilizing assignment operations.+ */+ void swap(btree_delete& other) {+ // swap the content+ std::swap(root, other.root);+ std::swap(leftmost, other.leftmost);+ }++ // Implementation of the assignment operation for trees.+ btree_delete& operator=(const btree_delete& other) {+ // check identity+ if (this == &other) {+ return *this;+ }++ // create a deep-copy of the content of the other tree+ // shortcut for empty sets+ if (other.empty()) {+ return *this;+ }++ // clone content (deep copy)+ root = other.root->clone();++ // update leftmost reference+ auto tmp = root;+ while (!tmp->isLeaf()) {+ tmp = tmp->getChild(0);+ }+ leftmost = static_cast<leaf_node*>(tmp);++ // done+ return *this;+ }++ // Implementation of an equality operation for trees.+ bool operator==(const btree_delete& other) const {+ // check identity+ if (this == &other) {+ return true;+ }++ // check size+ if (size() != other.size()) {+ return false;+ }+ if (size() < other.size()) {+ return other == *this;+ }++ // check content+ for (const auto& key : other) {+ if (!contains(key)) {+ return false;+ }+ }+ return true;+ }++ // Implementation of an inequality operation for trees.+ bool operator!=(const btree_delete& other) const {+ return !(*this == other);+ }++ // -- for debugging --++ // Determines the number of levels contained in this tree.+ size_type getDepth() const {+ return (empty()) ? 0 : root->getDepth();+ }++ // Determines the number of nodes contained in this tree.+ size_type getNumNodes() const {+ return (empty()) ? 0 : root->countNodes();+ }++ // Determines the amount of memory used by this data structure+ size_type getMemoryUsage() const {+ return sizeof(*this) + (empty() ? 0 : root->getMemoryUsage());+ }++ /*+ * Prints a textual representation of this tree to the given+ * output stream (mostly for debugging and tuning).+ */+ void printTree(std::ostream& out = std::cout) const {+ out << "B-Tree with " << size() << " elements:\n";+ if (empty()) {+ out << " - empty - \n";+ } else {+ root->printTree(out, "");+ }+ }++ /**+ * Prints a textual summary of statistical properties of this+ * tree to the given output stream (for debugging and tuning).+ */+ void printStats(std::ostream& out = std::cout) const {+ auto nodes = getNumNodes();+ out << " ---------------------------------\n";+ out << " Elements: " << size() << "\n";+ out << " Depth: " << (empty() ? 0 : root->getDepth()) << "\n";+ out << " Nodes: " << nodes << "\n";+ out << " ---------------------------------\n";+ out << " Size of inner node: " << sizeof(inner_node) << "\n";+ out << " Size of leaf node: " << sizeof(leaf_node) << "\n";+ out << " Size of Key: " << sizeof(Key) << "\n";+ out << " max keys / node: " << node::maxKeys << "\n";+ out << " avg keys / node: " << (size() / (double)nodes) << "\n";+ out << " avg filling rate: " << ((size() / (double)nodes) / node::maxKeys) << "\n";+ out << " ---------------------------------\n";+ out << " insert-hint (hits/misses/total): " << hint_stats.inserts.getHits() << "/"+ << hint_stats.inserts.getMisses() << "/" << hint_stats.inserts.getAccesses() << "\n";+ out << " contains-hint(hits/misses/total):" << hint_stats.contains.getHits() << "/"+ << hint_stats.contains.getMisses() << "/" << hint_stats.contains.getAccesses() << "\n";+ out << " lower-bound-hint (hits/misses/total):" << hint_stats.lower_bound.getHits() << "/"+ << hint_stats.lower_bound.getMisses() << "/" << hint_stats.lower_bound.getAccesses() << "\n";+ out << " upper-bound-hint (hits/misses/total):" << hint_stats.upper_bound.getHits() << "/"+ << hint_stats.upper_bound.getMisses() << "/" << hint_stats.upper_bound.getAccesses() << "\n";+ out << " ---------------------------------\n";+ }++ /**+ * Checks the consistency of this tree.+ */+ bool check() {+ auto ok = empty() || root->check(comp, root);+ if (!ok) {+ printTree();+ }+ return ok;+ }++ /**+ * A static member enabling the bulk-load of ordered data into an empty+ * tree. This function is much more efficient in creating a index over+ * an ordered set of elements than an iterative insertion of values.+ *+ * @tparam Iter .. the type of iterator specifying the range+ * it must be a random-access iterator+ */+ template <typename R, typename Iter>+ static typename std::enable_if<std::is_same<typename std::iterator_traits<Iter>::iterator_category,+ std::random_access_iterator_tag>::value,+ R>::type+ load(const Iter& a, const Iter& b) {+ // quick exit - empty range+ if (a == b) {+ return R();+ }++ // resolve tree recursively+ auto root = buildSubTree(a, b - 1);++ // find leftmost node+ node* leftmost = root;+ while (!leftmost->isLeaf()) {+ leftmost = leftmost->getChild(0);+ }++ // build result+ return R(b - a, root, static_cast<leaf_node*>(leftmost));+ }++protected:+ /**+ * Determines whether the range covered by the given node is also+ * covering the given key value.+ */+ bool covers(const node* node, const Key& k) const {+ if (isSet) {+ // in sets we can include the ends as covered elements+ return !node->isEmpty() && !less(k, node->keys[0]) && !less(node->keys[node->numElements - 1], k);+ }+ // in multi-sets the ends may not be completely covered+ return !node->isEmpty() && less(node->keys[0], k) && less(k, node->keys[node->numElements - 1]);+ }++ /**+ * Determines whether the range covered by the given node is also+ * covering the given key value.+ */+ bool weak_covers(const node* node, const Key& k) const {+ if (isSet) {+ // in sets we can include the ends as covered elements+ return !node->isEmpty() && !weak_less(k, node->keys[0]) &&+ !weak_less(node->keys[node->numElements - 1], k);+ }+ // in multi-sets the ends may not be completely covered+ return !node->isEmpty() && weak_less(node->keys[0], k) &&+ weak_less(k, node->keys[node->numElements - 1]);+ }++private:+ /**+ * Determines whether the range covered by this node covers+ * the upper bound of the given key.+ */+ bool coversUpperBound(const node* node, const Key& k) const {+ // ignore edges+ return !node->isEmpty() && !less(k, node->keys[0]) && less(k, node->keys[node->numElements - 1]);+ }++ // Utility function for the load operation above.+ template <typename Iter>+ static node* buildSubTree(const Iter& a, const Iter& b) {+ const int N = node::maxKeys;++ // divide range in N+1 sub-ranges+ int length = (b - a) + 1;++ // terminal case: length is less then maxKeys+ if (length <= N) {+ // create a leaf node+ node* res = new leaf_node();+ res->numElements = length;++ for (int i = 0; i < length; ++i) {+ res->keys[i] = a[i];+ }++ return res;+ }++ // recursive case - compute step size+ int numKeys = N;+ int step = ((length - numKeys) / (numKeys + 1));++ while (numKeys > 1 && (step < N / 2)) {+ numKeys--;+ step = ((length - numKeys) / (numKeys + 1));+ }++ // create inner node+ node* res = new inner_node();+ res->numElements = numKeys;++ Iter c = a;+ for (int i = 0; i < numKeys; i++) {+ // get dividing key+ res->keys[i] = c[step];++ // get sub-tree+ auto child = buildSubTree(c, c + (step - 1));+ child->parent = res;+ child->position = i;+ res->getChildren()[i] = child;++ c = c + (step + 1);+ }++ // and the remaining part+ auto child = buildSubTree(c, b);+ child->parent = res;+ child->position = numKeys;+ res->getChildren()[numKeys] = child;++ // done+ return res;+ }+}; // namespace souffle++// Instantiation of static member search.+template <typename Key, typename Comparator, typename Allocator, unsigned blockSize, typename SearchStrategy,+ bool isSet, typename WeakComparator, typename Updater>+const SearchStrategy btree_delete<Key, Comparator, Allocator, blockSize, SearchStrategy, isSet,+ WeakComparator, Updater>::search;++} // end namespace detail++/**+ * A b-tree based set implementation.+ *+ * @tparam Key .. the element type to be stored in this set+ * @tparam Comparator .. a class defining an order on the stored elements+ * @tparam Allocator .. utilized for allocating memory for required nodes+ * @tparam blockSize .. determines the number of bytes/block utilized by leaf nodes+ * @tparam SearchStrategy .. enables switching between linear, binary or any other search strategy+ */+template <typename Key, typename Comparator = detail::comparator<Key>,+ typename Allocator = std::allocator<Key>, // is ignored so far+ unsigned blockSize = 256,+ typename SearchStrategy = typename souffle::detail::default_strategy<Key>::type,+ typename WeakComparator = Comparator, typename Updater = souffle::detail::updater<Key>>+class btree_delete_set : public souffle::detail::btree_delete<Key, Comparator, Allocator, blockSize,+ SearchStrategy, true, WeakComparator, Updater> {+ using super = souffle::detail::btree_delete<Key, Comparator, Allocator, blockSize, SearchStrategy, true,+ WeakComparator, Updater>;++ friend class souffle::detail::btree_delete<Key, Comparator, Allocator, blockSize, SearchStrategy, true,+ WeakComparator, Updater>;++public:+ /**+ * A default constructor creating an empty set.+ */+ btree_delete_set(+ const Comparator& comp = Comparator(), const WeakComparator& weak_comp = WeakComparator())+ : super(comp, weak_comp) {}++ /**+ * A constructor creating a set based on the given range.+ */+ template <typename Iter>+ btree_delete_set(const Iter& a, const Iter& b) {+ this->insert(a, b);+ }++ // A copy constructor.+ btree_delete_set(const btree_delete_set& other) : super(other) {}++ // A move constructor.+ btree_delete_set(btree_delete_set&& other) : super(std::move(other)) {}++private:+ // A constructor required by the bulk-load facility.+ template <typename s, typename n, typename l>+ btree_delete_set(s size, n* root, l* leftmost) : super(size, root, leftmost) {}++public:+ // Support for the assignment operator.+ btree_delete_set& operator=(const btree_delete_set& other) {+ super::operator=(other);+ return *this;+ }++ // Support for the bulk-load operator.+ template <typename Iter>+ static btree_delete_set load(const Iter& a, const Iter& b) {+ return super::template load<btree_delete_set>(a, b);+ }+};++/**+ * A b-tree based multi-set implementation.+ *+ * @tparam Key .. the element type to be stored in this set+ * @tparam Comparator .. a class defining an order on the stored elements+ * @tparam Allocator .. utilized for allocating memory for required nodes+ * @tparam blockSize .. determines the number of bytes/block utilized by leaf nodes+ * @tparam SearchStrategy .. enables switching between linear, binary or any other search strategy+ */+template <typename Key, typename Comparator = detail::comparator<Key>,+ typename Allocator = std::allocator<Key>, // is ignored so far+ unsigned blockSize = 256,+ typename SearchStrategy = typename souffle::detail::default_strategy<Key>::type,+ typename WeakComparator = Comparator, typename Updater = souffle::detail::updater<Key>>+class btree_delete_multiset : public souffle::detail::btree_delete<Key, Comparator, Allocator, blockSize,+ SearchStrategy, false, WeakComparator, Updater> {+ using super = souffle::detail::btree_delete<Key, Comparator, Allocator, blockSize, SearchStrategy, false,+ WeakComparator, Updater>;++ friend class souffle::detail::btree_delete<Key, Comparator, Allocator, blockSize, SearchStrategy, false,+ WeakComparator, Updater>;++public:+ /**+ * A default constructor creating an empty set.+ */+ btree_delete_multiset(+ const Comparator& comp = Comparator(), const WeakComparator& weak_comp = WeakComparator())+ : super(comp, weak_comp) {}++ /**+ * A constructor creating a set based on the given range.+ */+ template <typename Iter>+ btree_delete_multiset(const Iter& a, const Iter& b) {+ this->insert(a, b);+ }++ // A copy constructor.+ btree_delete_multiset(const btree_delete_multiset& other) : super(other) {}++ // A move constructor.+ btree_delete_multiset(btree_delete_multiset&& other) : super(std::move(other)) {}++private:+ // A constructor required by the bulk-load facility.+ template <typename s, typename n, typename l>+ btree_delete_multiset(s size, n* root, l* leftmost) : super(size, root, leftmost) {}++public:+ // Support for the assignment operator.+ btree_delete_multiset& operator=(const btree_delete_multiset& other) {+ super::operator=(other);+ return *this;+ }++ // Support for the bulk-load operator.+ template <typename Iter>+ static btree_delete_multiset load(const Iter& a, const Iter& b) {+ return super::template load<btree_delete_multiset>(a, b);+ }+};++} // end of namespace souffle
+ cbits/souffle/datastructure/BTreeUtil.h view
@@ -0,0 +1,222 @@+/*+ * Souffle - A Datalog Compiler+ * Copyright (c) 2013, 2015, Oracle and/or its affiliates. All rights reserved+ * Licensed under the Universal Permissive License v 1.0 as shown at:+ * - https://opensource.org/licenses/UPL+ * - <souffle root>/licenses/SOUFFLE-UPL.txt+ */++/************************************************************************+ *+ * @file BTreeUtil.h+ *+ * Utilities for a generic B-tree data structure+ *+ ***********************************************************************/++#pragma once++namespace souffle {++namespace detail {++// ---------- comparators --------------++/**+ * A generic comparator implementation as it is used by+ * a b-tree based on types that can be less-than and+ * equality comparable.+ */+template <typename T>+struct comparator {+ /**+ * Compares the values of a and b and returns+ * -1 if a<b, 1 if a>b and 0 otherwise+ */+ int operator()(const T& a, const T& b) const {+ return (a > b) - (a < b);+ }+ bool less(const T& a, const T& b) const {+ return a < b;+ }+ bool equal(const T& a, const T& b) const {+ return a == b;+ }+};++// ---------- search strategies --------------++/**+ * A common base class for search strategies in b-trees.+ */+struct search_strategy {};++/**+ * A linear search strategy for looking up keys in b-tree nodes.+ */+struct linear_search : public search_strategy {+ /**+ * Required user-defined default constructor.+ */+ linear_search() = default;++ /**+ * Obtains an iterator referencing an element equivalent to the+ * given key in the given range. If no such element is present,+ * a reference to the first element not less than the given key+ * is returned.+ */+ template <typename Key, typename Iter, typename Comp>+ inline Iter operator()(const Key& k, Iter a, Iter b, Comp& comp) const {+ return lower_bound(k, a, b, comp);+ }++ /**+ * Obtains a reference to the first element in the given range that+ * is not less than the given key.+ */+ template <typename Key, typename Iter, typename Comp>+ inline Iter lower_bound(const Key& k, Iter a, Iter b, Comp& comp) const {+ auto c = a;+ while (c < b) {+ auto r = comp(*c, k);+ if (r >= 0) {+ return c;+ }+ ++c;+ }+ return b;+ }++ /**+ * Obtains a reference to the first element in the given range that+ * such that the given key is less than the referenced element.+ */+ template <typename Key, typename Iter, typename Comp>+ inline Iter upper_bound(const Key& k, Iter a, Iter b, Comp& comp) const {+ auto c = a;+ while (c < b) {+ if (comp(*c, k) > 0) {+ return c;+ }+ ++c;+ }+ return b;+ }+};++/**+ * A binary search strategy for looking up keys in b-tree nodes.+ */+struct binary_search : public search_strategy {+ /**+ * Required user-defined default constructor.+ */+ binary_search() = default;++ /**+ * Obtains an iterator pointing to some element within the given+ * range that is equal to the given key, if available. If multiple+ * elements are equal to the given key, an undefined instance will+ * be obtained (no guaranteed lower or upper boundary). If no such+ * element is present, a reference to the first element not less than+ * the given key will be returned.+ */+ template <typename Key, typename Iter, typename Comp>+ Iter operator()(const Key& k, Iter a, Iter b, Comp& comp) const {+ Iter c;+ auto count = b - a;+ while (count > 0) {+ auto step = count >> 1;+ c = a + step;+ auto r = comp(*c, k);+ if (r == 0) {+ return c;+ }+ if (r < 0) {+ a = ++c;+ count -= step + 1;+ } else {+ count = step;+ }+ }+ return a;+ }++ /**+ * Obtains a reference to the first element in the given range that+ * is not less than the given key.+ */+ template <typename Key, typename Iter, typename Comp>+ Iter lower_bound(const Key& k, Iter a, Iter b, Comp& comp) const {+ Iter c;+ auto count = b - a;+ while (count > 0) {+ auto step = count >> 1;+ c = a + step;+ if (comp(*c, k) < 0) {+ a = ++c;+ count -= step + 1;+ } else {+ count = step;+ }+ }+ return a;+ }++ /**+ * Obtains a reference to the first element in the given range that+ * such that the given key is less than the referenced element.+ */+ template <typename Key, typename Iter, typename Comp>+ Iter upper_bound(const Key& k, Iter a, Iter b, Comp& comp) const {+ Iter c;+ auto count = b - a;+ while (count > 0) {+ auto step = count >> 1;+ c = a + step;+ if (comp(k, *c) >= 0) {+ a = ++c;+ count -= step + 1;+ } else {+ count = step;+ }+ }+ return a;+ }+};++// ---------- search strategies selection --------------++/**+ * A template-meta class to select search strategies for b-trees+ * depending on the key type.+ */+template <typename S>+struct strategy_selection {+ using type = S;+};++struct linear : public strategy_selection<linear_search> {};+struct binary : public strategy_selection<binary_search> {};++// by default every key utilizes binary search+template <typename Key>+struct default_strategy : public binary {};++template <>+struct default_strategy<int> : public linear {};++template <typename... Ts>+struct default_strategy<std::tuple<Ts...>> : public linear {};++/**+ * The default non-updater+ */+template <typename T>+struct updater {+ void update(T& /* old_t */, const T& /* new_t */) {}+};++} // end of namespace detail+} // end of namespace souffle
cbits/souffle/datastructure/Brie.h view
@@ -1379,7 +1379,7 @@ */ static Node* findFirst(Node* node, int level) { while (level > 0) {- bool found = false;+ [[maybe_unused]] bool found = false; for (int i = 0; i < NUM_CELLS; i++) { Node* cur = node->cell[i].ptr; if (cur) {@@ -2795,42 +2795,44 @@ template <unsigned levels> range<iterator> getBoundaries(const_entry_span_type entry, op_context& ctxt) const { // if nothing is bound => just use begin and end- if constexpr (levels == 0) return make_range(begin(), end());+ if constexpr (levels == 0) {+ return make_range(begin(), end());+ } else { // HACK: explicit `else` branch b/c OSX compiler doesn't do DCE before `0 < limit` warning+ // check context+ if (ctxt.lastBoundaryLevels == levels) {+ bool fit = true;+ for (unsigned i = 0; i < levels; ++i) {+ fit = fit && (entry[i] == ctxt.lastBoundaryRequest[i]);+ } - // check context- if (ctxt.lastBoundaryLevels == levels) {- bool fit = true;- for (unsigned i = 0; i < levels; ++i) {- fit = fit && (entry[i] == ctxt.lastBoundaryRequest[i]);+ // if it fits => take it+ if (fit) {+ base::hint_stats.get_boundaries.addHit();+ return ctxt.lastBoundaries;+ } } - // if it fits => take it- if (fit) {- base::hint_stats.get_boundaries.addHit();- return ctxt.lastBoundaries;- }- }-- // the hint has not been a hit- base::hint_stats.get_boundaries.addMiss();+ // the hint has not been a hit+ base::hint_stats.get_boundaries.addMiss(); - // start with two end iterators- iterator begin{};- iterator end{};+ // start with two end iterators+ iterator begin{};+ iterator end{}; - // adapt them level by level- auto found = fix_binding<levels, 0, Dim>()(store, begin, end, entry);- if (!found) return make_range(iterator(), iterator());+ // adapt them level by level+ auto found = fix_binding<levels, 0, Dim>()(store, begin, end, entry);+ if (!found) return make_range(iterator(), iterator()); - // update context- static_assert(std::tuple_size_v<decltype(ctxt.lastBoundaryRequest)> == Dim);- static_assert(std::tuple_size_v<decltype(entry)> == Dim);- ctxt.lastBoundaryLevels = levels;- std::copy_n(entry.begin(), Dim, ctxt.lastBoundaryRequest.begin());- ctxt.lastBoundaries = make_range(begin, end);+ // update context+ static_assert(std::tuple_size_v<decltype(ctxt.lastBoundaryRequest)> == Dim);+ static_assert(std::tuple_size_v<decltype(entry)> == Dim);+ ctxt.lastBoundaryLevels = levels;+ std::copy_n(entry.begin(), Dim, ctxt.lastBoundaryRequest.begin());+ ctxt.lastBoundaries = make_range(begin, end); - // use the result- return ctxt.lastBoundaries;+ // use the result+ return ctxt.lastBoundaries;+ } } /**
cbits/souffle/datastructure/ConcurrentFlyweight.h view
@@ -39,6 +39,35 @@ using pointer = const value_type*; using reference = const value_type&; +private:+ // Effectively:+ // data slot_type = NONE | END | Idx index_type+ // The last two values in the domain of `index_type` are used to represent cases `NONE` and `END`+ // TODO: strong type-def wrap this to prevent implicit conversions+ using slot_type = index_type;+ static constexpr slot_type NONE = std::numeric_limits<slot_type>::max(); // special case: `std::nullopt`+ static constexpr slot_type END = NONE - 1; // special case: end iterator+ static constexpr slot_type SLOT_MAX = END; // +1 the largest non-special slot value++ static_assert(std::is_same_v<slot_type, index_type>,+ "conversion helpers assume they're the underlying type, "+ "with the last two values reserved for special cases");+ static_assert(std::is_unsigned_v<slot_type>);++ /// Converts from index to slot.+ static slot_type slot(const index_type I) {+ // not expected to happen. you'll run out of memory long before.+ assert(I < SLOT_MAX && "can't represent index in `slot_type` domain");+ return static_cast<slot_type>(I);+ }++ /// Converts from slot to index.+ static index_type index(const slot_type S) {+ assert(S < SLOT_MAX && "slot is sentinal value; can't convert to index !!");+ return static_cast<index_type>(S);+ }++public: /// Iterator with concurrent access to the datastructure. struct Iterator { using iterator_category = std::input_iterator_tag;@@ -47,8 +76,6 @@ using reference = ConcurrentFlyweight::reference; private:- using slot_type = int64_t;- const ConcurrentFlyweight* This; /// Access lane to the datastructure.@@ -61,41 +88,23 @@ slot_type NextMaybeUnassignedSlot; /// Handle that owns the next slot that might be unassigned.- int64_t NextMaybeUnassignedHandle;-- static constexpr int64_t End = std::numeric_limits<slot_type>::max();- static constexpr int64_t None = -1;-- /// Converts from index to slot.- static slot_type slot(const index_type I) {- assert(I >= 0 && I <= std::numeric_limits<slot_type>::max());- return static_cast<int64_t>(I);- }-- /// Converts from slot to index.- static index_type index(const slot_type S) {- assert(S >= 0 && S <= std::numeric_limits<index_type>::max());- return static_cast<index_type>(S);- }+ slot_type NextMaybeUnassignedHandle = NONE; public: // The 'begin' iterator Iterator(const ConcurrentFlyweight* This, const lane_id H)- : This(This), Lane(H), Slot(None), NextMaybeUnassignedSlot(0),- NextMaybeUnassignedHandle(None) {+ : This(This), Lane(H), Slot(NONE), NextMaybeUnassignedSlot(0) { FindNextMaybeUnassignedSlot(); MoveToNextAssignedSlot(); } // The 'end' iterator Iterator(const ConcurrentFlyweight* This)- : This(This), Lane(0), Slot(End), NextMaybeUnassignedSlot(End),- NextMaybeUnassignedHandle(None) {}+ : This(This), Lane(0), Slot(END), NextMaybeUnassignedSlot(END) {} // The iterator starting at slot I, using access lane H. Iterator(const ConcurrentFlyweight* This, const lane_id H, const index_type I)- : This(This), Lane(H), Slot(slot(I)), NextMaybeUnassignedSlot(slot(I)),- NextMaybeUnassignedHandle(None) {+ : This(This), Lane(H), Slot(slot(I)), NextMaybeUnassignedSlot(slot(I)) { FindNextMaybeUnassignedSlot(); MoveToNextAssignedSlot(); }@@ -148,7 +157,7 @@ } bool operator==(const Iterator& That) const {- return (&This == &That.This) && (Slot == That.Slot);+ return (This == That.This) && (Slot == That.Slot); } bool operator!=(const Iterator& That) const {@@ -158,45 +167,48 @@ private: /** Find next slot after Slot that is maybe unassigned. */ void FindNextMaybeUnassignedSlot() {- NextMaybeUnassignedSlot = End;+ NextMaybeUnassignedSlot = END; for (lane_id I = 0; I < This->Lanes.lanes(); ++I) { const auto Lane = This->Lanes.guard(I);- if (This->Handles[I].NextSlot > Slot && This->Handles[I].NextSlot < NextMaybeUnassignedSlot) {+ if ((Slot == NONE || This->Handles[I].NextSlot > Slot) &&+ This->Handles[I].NextSlot < NextMaybeUnassignedSlot) { NextMaybeUnassignedSlot = This->Handles[I].NextSlot; NextMaybeUnassignedHandle = I; } }- if (NextMaybeUnassignedSlot == End) {- NextMaybeUnassignedSlot = This->NextSlot;- NextMaybeUnassignedHandle = None;+ if (NextMaybeUnassignedSlot == END) {+ NextMaybeUnassignedSlot = This->NextSlot.load(std::memory_order_acquire);+ NextMaybeUnassignedHandle = NONE; } } /** * Move Slot to next assigned slot and return true.- * Otherwise the end is reached and Slot is assigned int64_t::max and return false.+ * Otherwise the end is reached and Slot is assigned `END` and return false. */ bool MoveToNextAssignedSlot() {- while (Slot != End) {+ static_assert(NONE == std::numeric_limits<slot_type>::max(),+ "required for wrap around to 0 for begin-iterator-scan");+ static_assert(NONE + 1 == 0, "required for wrap around to 0 for begin-iterator-scan");+ while (Slot != END) {+ assert(Slot + 1 < SLOT_MAX); if (Slot + 1 < NextMaybeUnassignedSlot) { // next unassigned slot not reached Slot = Slot + 1; return true; } - if (NextMaybeUnassignedHandle == None) { // reaching end- Slot = End;- NextMaybeUnassignedSlot = End;- NextMaybeUnassignedHandle = None;+ if (NextMaybeUnassignedHandle == NONE) { // reaching end+ Slot = END;+ NextMaybeUnassignedSlot = END;+ NextMaybeUnassignedHandle = NONE; return false; } - if (NextMaybeUnassignedHandle != None) { // maybe reaching the next unassigned slot+ if (NextMaybeUnassignedHandle != NONE) { // maybe reaching the next unassigned slot This->Lanes.lock(NextMaybeUnassignedHandle); const bool IsAssigned = (Slot + 1 < This->Handles[NextMaybeUnassignedHandle].NextSlot); This->Lanes.unlock(NextMaybeUnassignedHandle);- if (IsAssigned) {- Slot = Slot + 1;- }+ Slot = Slot + 1; FindNextMaybeUnassignedSlot(); if (IsAssigned) { return true;@@ -218,7 +230,7 @@ Slots = std::make_unique<const value_type*[]>(InitialCapacity); Handles = std::make_unique<Handle[]>(HandleCount); NextSlot = (ReserveFirst ? 1 : 0);- MaxSlotBeforeGrow = InitialCapacity - 1;+ SlotCount = InitialCapacity; } /// Initialize the datastructure with a capacity of 8 elements.@@ -275,6 +287,7 @@ /// Assumption: the index is mapped in the datastructure. const Key& fetch(const lane_id H, const index_type Idx) const { const auto Lane = Lanes.guard(H);+ assert(Idx < SlotCount.load(std::memory_order_relaxed)); return Slots[Idx]->first; } @@ -285,35 +298,61 @@ template <class... Args> std::pair<index_type, bool> findOrInsert(const lane_id H, Args&&... Xs) { const auto Lane = Lanes.guard(H);- int64_t Slot = Handles[H].NextSlot; node_type Node; - if (Slot == -1) {- // reserve a slot in the index, be it for now or later usage.- Slot = NextSlot++;- Node = Mapping.node(static_cast<index_type>(Slot));+ slot_type Slot = Handles[H].NextSlot; - Handles[H].NextSlot = Slot;- Handles[H].NextNode = Node;+ // Getting the next insertion slot for the current lane may require+ // more than one attempts if the datastructure must grow and other+ // threads are waiting for the same lane @p H.+ while (true) {+ if (Slot == NONE) {+ // Reserve a slot for the lane, the datastructure might need to+ // grow before the slot memory location becomes available.+ Slot = NextSlot++;+ Handles[H].NextSlot = Slot;+ Handles[H].NextNode = Mapping.node(static_cast<index_type>(Slot));+ } - if (Slot > MaxSlotBeforeGrow) {+ if (Slot >= SlotCount.load(std::memory_order_relaxed)) {+ // The slot memory location is not yet available, try to+ // grow the datastructure. Other threads in other lanes might+ // be attempting to grow the datastructure concurrently.+ //+ // Anyway when this call returns the Slot memory location is+ // available. tryGrow(H);++ // Reload the Slot for the current lane since another thread+ // using the same lane may take-over the lane during tryGrow()+ // and consume the slot before the current thread is+ // rescheduled on the lane.+ Slot = Handles[H].NextSlot;+ } else {+ // From here the slot is known, allocated and available.+ break; }- } else {- Node = Handles[H].NextNode; } - // insert key in the index in advance+ Node = Handles[H].NextNode;++ // Insert key in the index in advance. Slots[Slot] = &Node->value(); auto Res = Mapping.get(H, Node, std::forward<Args>(Xs)...); if (Res.second) {- // inserted by self- Handles[H].NextSlot = -1;- Handles[H].NextNode = node_type{};+ // Inserted by self, slot is consumed, clear the lane's state.+ Handles[H].clear(); return std::make_pair(static_cast<index_type>(Slot), true); } else {- // inserted concurrently by another handle,+ // Inserted concurrently by another thread, clearing the slot is+ // not strictly needed but it avoids leaving a dangling pointer+ // there.+ //+ // The reserved slot and node remains in the lane state so that+ // they can be consumed by the next insertion operation on this+ // lane.+ Slots[Slot] = nullptr; return std::make_pair(Res.first->second, false); } }@@ -323,8 +362,12 @@ using node_type = typename map_type::node_type; struct Handle {- /// Slot where this handle will store its next value- int64_t NextSlot = -1;+ void clear() {+ NextSlot = NONE;+ NextNode = nullptr;+ }++ slot_type NextSlot = NONE; node_type NextNode = nullptr; }; @@ -346,15 +389,23 @@ map_type Mapping; // Next available slot.- std::atomic<std::int64_t> NextSlot;+ std::atomic<slot_type> NextSlot; - // Maximum allowed slot index before growing- std::int64_t MaxSlotBeforeGrow;+ // Number of slots.+ std::atomic<slot_type> SlotCount; + /// Grow the datastructure if needed. bool tryGrow(const lane_id H) {+ // This call may release and re-acquire the lane to+ // allow progress of a concurrent growing operation.+ //+ // It is possible that another thread is waiting to+ // enter the same lane, and that other thread might+ // take and leave the lane before the current thread+ // re-acquires it. Lanes.beforeLockAllBut(H); - if (NextSlot <= MaxSlotBeforeGrow) {+ if (NextSlot < SlotCount) { // Current size is fine Lanes.beforeUnlockAllBut(H); return false;@@ -363,12 +414,15 @@ Lanes.lockAllBut(H); { // safe section- const std::size_t CurrentSize = MaxSlotBeforeGrow + 1;- const std::size_t NewSize = (CurrentSize << 1); // double size policy+ const std::size_t CurrentSize = SlotCount;+ std::size_t NewSize = (CurrentSize << 1); // double size policy+ while (NewSize < NextSlot) {+ NewSize <<= 1; // double size+ } std::unique_ptr<const value_type*[]> NewSlots = std::make_unique<const value_type*[]>(NewSize); std::memcpy(NewSlots.get(), Slots.get(), sizeof(const value_type*) * CurrentSize); Slots = std::move(NewSlots);- MaxSlotBeforeGrow = NewSize - 1;+ SlotCount = NewSize; } Lanes.beforeUnlockAllBut(H);@@ -394,8 +448,6 @@ const KeyEqual& key_equal = KeyEqual(), const KeyFactory& key_factory = KeyFactory()) : Base(LaneCount, InitialCapacity, ReserveFirst, hash, key_equal, key_factory) {} - ~OmpFlyweight() {}- iterator begin() const { return Base::begin(Base::Lanes.threadLane()); }@@ -438,8 +490,6 @@ const bool ReserveFirst = false, const Hash& hash = Hash(), const KeyEqual& key_equal = KeyEqual(), const KeyFactory& key_factory = KeyFactory()) : Base(NumLanes, InitialCapacity, ReserveFirst, hash, key_equal, key_factory) {}-- ~SeqFlyweight() {} iterator begin() const { return Base::begin(0);
cbits/souffle/datastructure/ConcurrentInsertOnlyHashMap.h view
@@ -145,7 +145,7 @@ } LoadFactor = 1.0; Buckets = std::make_unique<std::atomic<BucketList*>[]>(BucketCount);- MaxSizeBeforeGrow = std::ceil(LoadFactor * BucketCount);+ MaxSizeBeforeGrow = std::ceil(LoadFactor * (double)BucketCount); } ConcurrentInsertOnlyHashMap(const Hash& hash = Hash(), const KeyEqual& key_equal = KeyEqual(),@@ -190,7 +190,7 @@ const auto Guard = Lanes.guard(H); const size_t Bucket = HashValue % BucketCount; - BucketList* L = Buckets[Bucket].load(std::memory_order_consume);+ BucketList* L = Buckets[Bucket].load(std::memory_order_acquire); while (L != nullptr) { if (EqualTo(L->Value.first, X)) { // found the key@@ -239,7 +239,7 @@ * */ template <class... Args>- std::pair<const value_type*, bool> get(const lane_id H, node_type N, Args&&... Xs) {+ std::pair<const value_type*, bool> get(const lane_id H, const node_type N, Args&&... Xs) { // At any time a concurrent lane may insert the key before this lane. // // The synchronisation point is the atomic compare-and-exchange of the@@ -302,11 +302,11 @@ // 4) // the head of the bucket's list last time we checked- BucketList* LastKnownHead = Buckets[Bucket].load(std::memory_order_relaxed);+ BucketList* LastKnownHead = Buckets[Bucket].load(std::memory_order_acquire); // the head of the bucket's list we already searched from BucketList* SearchedFrom = nullptr; // the node we want to insert- BucketList* Node = static_cast<BucketList*>(N);+ BucketList* const Node = static_cast<BucketList*>(N); // Loop until either the node is inserted or the key is found in the bucket. // Assuming bucket collisions are rare this loop is not executed more than once.@@ -318,8 +318,11 @@ while (L != SearchedFrom) { if (EqualTo(L->Value.first, std::forward<Args>(Xs)...)) { // 6)- // found the key+ // Found the key, no need to insert.+ // Although it's not strictly necessary, clear the node+ // chaining to avoid leaving a dangling pointer there. Value = &(L->Value);+ Node->Next = nullptr; goto Done; } L = L->Next;@@ -343,7 +346,6 @@ Inserted = true; NewSize = ++Size; Value = &(Node->Value);- Node = nullptr; goto AfterInserted; } @@ -410,7 +412,7 @@ // Chose a prime number of buckets that ensures the desired load factor // given the current number of elements in the map. const std::size_t CurrentSize = Size;- const std::size_t NeededBucketCount = std::ceil(CurrentSize / LoadFactor);+ const std::size_t NeededBucketCount = std::ceil((double)CurrentSize / LoadFactor); std::size_t NewBucketCount = NeededBucketCount; for (std::size_t I = 0; I < details::ToPrime.size(); ++I) { const uint64_t N = details::ToPrime[I].first;@@ -430,6 +432,9 @@ // and insert in the new bucket. // // Maybe concurrent lanes could help using some job-stealing algorithm.+ //+ // Use relaxed memory ordering since the whole operation takes place+ // in a critical section. for (std::size_t B = 0; B < BucketCount; ++B) { BucketList* L = Buckets[B].load(std::memory_order_relaxed); while (L) {@@ -446,7 +451,7 @@ Buckets = std::move(NewBuckets); BucketCount = NewBucketCount;- MaxSizeBeforeGrow = (NewBucketCount * LoadFactor);+ MaxSizeBeforeGrow = ((double)NewBucketCount * LoadFactor); } Lanes.beforeUnlockAllBut(H);
cbits/souffle/datastructure/EquivalenceRelation.h view
@@ -34,6 +34,7 @@ #include <shared_mutex> #include <stdexcept> #include <tuple>+#include <unordered_set> #include <utility> #include <vector> @@ -100,7 +101,7 @@ bool insert(value_type x, value_type y, operation_hints) { // indicate that iterators will have to generate on request this->statesMapStale.store(true, std::memory_order_relaxed);- bool retval = contains(x, y);+ bool retval = !contains(x, y); sds.unionNodes(x, y); return retval; }@@ -128,19 +129,27 @@ } /**- * Extend this relation with another relation, expanding this equivalence relation- * The supplied relation is the old knowledge, whilst this relation only contains- * explicitly new knowledge. After this operation the "implicitly new tuples" are now- * explicitly inserted this relation.+ * Extend this relation with another relation, expanding this equivalence+ * relation and inserting it into the other relation.+ *+ * The supplied relation is the old knowledge, whilst this relation only+ * contains explicitly new knowledge. After this operation the "implicitly+ * new tuples" are now explicitly inserted this relation, and all of the new+ * tuples in this relation are inserted into the old relation. */- void extend(const EquivalenceRelation<TupleType>& other) {- // nothing to extend if there's no new/original knowledge- if (other.size() == 0 || this->size() == 0) return;+ void extendAndInsert(EquivalenceRelation<TupleType>& other) {+ if (other.size() == 0 && this->size() == 0) return; - this->genAllDisjointSetLists();- other.genAllDisjointSetLists();+ std::unordered_set<value_type> repsCovered; - std::set<value_type> repsCovered;+ // This vector holds all of the elements of this equivalence relation+ // that aren't yet in other, which get inserted after extending this+ // relation by other. These operations are interleaved for maximum+ // efficiency - either extend or inserting first would make the other+ // operation unnecessarily slow.+ std::vector<std::pair<value_type, value_type>> toInsert;+ auto size = std::distance(this->sds.sparseToDenseMap.begin(), this->sds.sparseToDenseMap.end());+ toInsert.reserve(size); // find all the disjoint sets that need to be added to this relation // that exist in other (and exist in this)@@ -156,8 +165,11 @@ repsCovered.emplace(rep); } }+ toInsert.emplace_back(el, this->sds.findNode(el)); } }+ assert(size >= 0);+ assert(toInsert.size() == (std::size_t)size); // add the intersecting dj sets into this one {@@ -171,6 +183,16 @@ if (repsCovered.count(rep) != 0) { this->insert(el, rep); }+ }+ }++ // Insert all new tuples from this relation into the old relation+ {+ value_type el;+ value_type rep;+ for (std::pair<value_type, value_type> p : toInsert) {+ std::tie(el, rep) = p;+ other.insert(el, rep); } } }
cbits/souffle/datastructure/UnionFind.h view
@@ -342,7 +342,7 @@ toDense(val); }; - /* whether we the supplied node exists */+ /* whether the supplied node exists */ inline bool nodeExists(const SparseDomain val) const { return sparseToDenseMap.contains({val, -1}); };
cbits/souffle/io/ReadStream.h view
@@ -176,8 +176,7 @@ return branchIdx; } - const RamDomain empty[] = {};- RamDomain emptyArgs = recordTable.pack(empty, 0);+ RamDomain emptyArgs = recordTable.pack(toVector<RamDomain>().data(), 0); const RamDomain record[] = {branchIdx, emptyArgs}; return recordTable.pack(record, 2); }
cbits/souffle/io/ReadStreamSQLite.h view
@@ -64,19 +64,24 @@ uint32_t column; for (column = 0; column < arity; column++) {- std::string element(reinterpret_cast<const char*>(sqlite3_column_text(selectStatement, column)));-- if (element.empty()) {+ std::string element;+ if (0 == sqlite3_column_bytes(selectStatement, column)) { element = "n/a";+ } else {+ element = reinterpret_cast<const char*>(sqlite3_column_text(selectStatement, column));++ if (element.empty()) {+ element = "n/a";+ } } try { auto&& ty = typeAttributes.at(column); switch (ty[0]) { case 's': tuple[column] = symbolTable.encode(element); break;+ case 'f': tuple[column] = ramBitCast(RamFloatFromString(element)); break; case 'i': case 'u':- case 'f': case 'r': tuple[column] = RamSignedFromString(element); break; default: fatal("invalid type attribute: `%c`", ty[0]); }
cbits/souffle/io/SerialisationStream.h view
@@ -29,7 +29,7 @@ namespace souffle { -class RecordTableInterface;+class RecordTable; class SymbolTable; using json11::Json;@@ -43,23 +43,29 @@ template <typename A> using RO = std::conditional_t<readOnlyTables, const A, A>; - SerialisationStream(RO<SymbolTable>& symTab, RO<RecordTableInterface>& recTab, Json types,+ SerialisationStream(RO<SymbolTable>& symTab, RO<RecordTable>& recTab, Json types, std::vector<std::string> relTypes, std::size_t auxArity = 0) : symbolTable(symTab), recordTable(recTab), types(std::move(types)), typeAttributes(std::move(relTypes)), arity(typeAttributes.size() - auxArity), auxiliaryArity(auxArity) {} - SerialisationStream(RO<SymbolTable>& symTab, RO<RecordTableInterface>& recTab, Json types)+ SerialisationStream(RO<SymbolTable>& symTab, RO<RecordTable>& recTab, Json types) : symbolTable(symTab), recordTable(recTab), types(std::move(types)) { setupFromJson(); } - SerialisationStream(RO<SymbolTable>& symTab, RO<RecordTableInterface>& recTab,+ SerialisationStream(RO<SymbolTable>& symTab, RO<RecordTable>& recTab, const std::map<std::string, std::string>& rwOperation) : symbolTable(symTab), recordTable(recTab) { std::string parseErrors; types = Json::parse(rwOperation.at("types"), parseErrors); assert(parseErrors.size() == 0 && "Internal JSON parsing failed.");+ if (rwOperation.count("params") > 0) {+ params = Json::parse(rwOperation.at("params"), parseErrors);+ assert(parseErrors.size() == 0 && "Internal JSON parsing failed.");+ } else {+ params = Json::object();+ } auxiliaryArity = RamSignedFromString(getOr(rwOperation, "auxArity", "0")); @@ -67,8 +73,9 @@ } RO<SymbolTable>& symbolTable;- RO<RecordTableInterface>& recordTable;+ RO<RecordTable>& recordTable; Json types;+ Json params; std::vector<std::string> typeAttributes; std::size_t arity = 0;
cbits/souffle/io/WriteStream.h view
@@ -124,9 +124,7 @@ auto&& adtInfo = types["ADTs"][name]; assert(!adtInfo.is_null() && "Missing adt type information");-- const std::size_t numBranches = adtInfo["arity"].long_value();- assert(numBranches > 0);+ assert(adtInfo["arity"].long_value() > 0); // adt is encoded in one of three possible ways: // [branchID, [branch_args]] when |branch_args| != 1
cbits/souffle/io/WriteStreamSQLite.h view
@@ -210,6 +210,9 @@ void createRelationView() { // Create view with symbol strings resolved++ const auto columnNames = params["relation"]["params"].array_items();+ std::stringstream createViewText; createViewText << "CREATE VIEW IF NOT EXISTS '" << relationName << "' AS "; std::stringstream projectionClause;@@ -218,22 +221,26 @@ std::stringstream whereClause; bool firstWhere = true; for (unsigned int i = 0; i < arity; i++) {- std::string columnName = std::to_string(i);+ const std::string tableColumnName = std::to_string(i);+ const auto& viewColumnName =+ (columnNames[i].is_string() ? columnNames[i].string_value() : tableColumnName); if (i != 0) { projectionClause << ","; } if (typeAttributes.at(i)[0] == 's') {- projectionClause << "'_symtab_" << columnName << "'.symbol AS '" << columnName << "'";- fromClause << ",'" << symbolTableName << "' AS '_symtab_" << columnName << "'";+ projectionClause << "'_symtab_" << tableColumnName << "'.symbol AS '" << viewColumnName+ << "'";+ fromClause << ",'" << symbolTableName << "' AS '_symtab_" << tableColumnName << "'"; if (!firstWhere) { whereClause << " AND "; } else { firstWhere = false; }- whereClause << "'_" << relationName << "'.'" << columnName << "' = "- << "'_symtab_" << columnName << "'.id";+ whereClause << "'_" << relationName << "'.'" << tableColumnName << "' = "+ << "'_symtab_" << tableColumnName << "'.id"; } else {- projectionClause << "'_" << relationName << "'.'" << columnName << "'";+ projectionClause << "'_" << relationName << "'.'" << tableColumnName << "' AS '"+ << viewColumnName << "'"; } } createViewText << "SELECT " << projectionClause.str() << " FROM " << fromClause.str();
cbits/souffle/utility/ContainerUtil.h view
@@ -16,8 +16,10 @@ #pragma once +#include "souffle/utility/DynamicCasting.h" #include "souffle/utility/Iteration.h" #include "souffle/utility/MiscUtil.h"+#include "souffle/utility/Types.h" #include <algorithm> #include <functional>@@ -56,25 +58,17 @@ * A utility to check generically whether a given element is contained in a given * container. */-template <typename C>+template <typename C, typename = std::enable_if_t<!is_associative<C>>> bool contains(const C& container, const typename C::value_type& element) { return std::find(container.begin(), container.end(), element) != container.end(); } -// TODO: Detect and generalise to other set types?-template <typename A>-bool contains(const std::set<A>& container, const A& element) {- return container.find(element) != container.end();-}- /**- * Version of contains specialised for maps.- *- * This workaround is needed because of set container, for which value_type == key_type,- * which is ambiguous in this context.+ * A utility to check generically whether a given key exists within a given+ * associative container. */-template <typename C>-bool contains(const C& container, const typename C::value_type::first_type& element) {+template <typename C, typename A, typename = std::enable_if_t<is_associative<C>>>+bool contains(const C& container, A&& element) { return container.find(element) != container.end(); } @@ -82,19 +76,18 @@ * Returns the first element in a container that satisfies a given predicate, * nullptr otherwise. */-template <typename C>-typename C::value_type getIf(const C& container, std::function<bool(const typename C::value_type)> pred) {- auto res = std::find_if(container.begin(), container.end(),- [&](const typename C::value_type item) { return pred(item); });- return res == container.end() ? nullptr : *res;+template <typename C, typename F>+auto getIf(C&& container, F&& pred) {+ auto it = std::find_if(container.begin(), container.end(), std::forward<F>(pred));+ return it == container.end() ? nullptr : *it; } /** * Get value for a given key; if not found, return default value. */-template <typename C>+template <typename C, typename A, typename = std::enable_if_t<is_associative<C>>> typename C::mapped_type const& getOr(- const C& container, typename C::key_type key, const typename C::mapped_type& defaultValue) {+ const C& container, A&& key, const typename C::mapped_type& defaultValue) { auto it = container.find(key); if (it != container.end()) {@@ -104,20 +97,7 @@ } } -namespace detail {-inline auto allOfBool = [](bool b) { return b; };-}- /**- * Return true if all elements (optionally after applying up)- * are true- */-template <typename R, typename UnaryP = decltype(detail::allOfBool) const&>-bool all(R const& range, UnaryP&& up = detail::allOfBool) {- return std::all_of(range.begin(), range.end(), std::forward<UnaryP>(up));-}--/** * Append elements to a container */ template <class C, typename R>@@ -141,37 +121,31 @@ * of arbitrary length. */ template <typename T, typename... R>-std::vector<T> toVector(const T& first, const R&... rest) {- return {first, rest...};+std::vector<T> toVector(T first, R... rest) {+ // Init-lists are effectively const-arrays. You can't `move` out of them.+ // Combine with `vector`s not having variadic constructors, can't do:+ // `vector{Own<A>{}, Own<A>{}}`+ // This is inexcusably awful and defeats the purpose of having init-lists.+ std::vector<T> xs;+ T ary[] = {std::move(first), std::move(rest)...};+ for (auto& x : ary) {+ xs.push_back(std::move(x));+ }+ return xs; } /** * A utility function enabling the creation of a vector of pointers. */-template <typename T>-std::vector<T*> toPtrVector(const VecOwn<T>& v) {- std::vector<T*> res;+template <typename A = void, typename T, typename U = std::conditional_t<std::is_same_v<A, void>, T, A>>+std::vector<U*> toPtrVector(const VecOwn<T>& v) {+ std::vector<U*> res; for (auto& e : v) { res.push_back(e.get()); } return res; } -/**- * Applies a function to each element of a vector and returns the results.- */-template <typename A, typename F /* : A -> B */>-auto map(const std::vector<A>& xs, F&& f) {- // FIXME: We can rewrite this using makeTransformRange now,- // or remove the usage of this completely- std::vector<decltype(f(xs[0]))> ys;- ys.reserve(xs.size());- for (auto&& x : xs) {- ys.emplace_back(f(x));- }- return ys;-}- // ------------------------------------------------------------------------------- // Equality Utilities // -------------------------------------------------------------------------------@@ -256,12 +230,21 @@ a, b, [&comp](auto& a, auto& b) { return a.first == b.first && comp(a.second, b.second); }); } +/**+ * A function testing whether two maps are equivalent using projected values.+ */+template <typename Key, typename Value, typename F>+bool equal_targets_map(const std::map<Key, Value>& a, const std::map<Key, Value>& b, F&& comp) {+ return equal_targets(+ a, b, [&](auto& a, auto& b) { return a.first == b.first && comp(a.second, b.second); });+}+ // ------------------------------------------------------------------------------- // Checking Utilities // ------------------------------------------------------------------------------- template <typename R> bool allValidPtrs(R const& range) {- return all(makeTransformRange(range, [](auto const& ptr) { return ptr != nullptr; }));+ return std::all_of(range.begin(), range.end(), [](auto&& p) { return (bool)p; }); } } // namespace souffle
+ cbits/souffle/utility/DynamicCasting.h view
@@ -0,0 +1,104 @@++/*+ * Souffle - A Datalog Compiler+ * Copyright (c) 2021, The Souffle Developers. All rights reserved.+ * Licensed under the Universal Permissive License v 1.0 as shown at:+ * - https://opensource.org/licenses/UPL+ * - <souffle root>/licenses/SOUFFLE-UPL.txt+ */++/************************************************************************+ *+ * @file DynamicCasting.h+ *+ * Common utilities for dynamic casting.+ *+ ***********************************************************************/++#pragma once++#include "souffle/utility/Types.h"+#include <cassert>+#include <type_traits>++namespace souffle {++/**+ * This class is used to tell as<> that cross-casting is allowed.+ * I use a named type rather than just a bool to make the code stand out.+ */+class AllowCrossCast {};++namespace detail {+template <typename A>+constexpr bool is_valid_cross_cast_option = std::is_same_v<A, void> || std::is_same_v<A, AllowCrossCast>;+}++/**+ * Helpers for `dynamic_cast`ing without having to specify redundant type qualifiers.+ * e.g. `as<AstLiteral>(p)` instead of `as<AstLiteral>(p)`.+ */+template <typename B, typename CastType = void, typename A,+ typename = std::enable_if_t<detail::is_valid_cross_cast_option<CastType>>>+auto as(A* x) {+ if constexpr (!std::is_same_v<CastType, AllowCrossCast> &&+ !std::is_base_of_v<std::remove_const_t<B>, std::remove_const_t<A>>) {+ static_assert(std::is_base_of_v<std::remove_const_t<A>, std::remove_const_t<B>>,+ "`as<B, A>` does not allow cross-type dyn casts. "+ "(i.e. `as<B, A>` where `B <: A` is not true.) "+ "Such a cast is likely a mistake or typo.");+ }+ return dynamic_cast<copy_const<A, B>*>(x);+}++template <typename B, typename CastType = void, typename A,+ typename = std::enable_if_t<std::is_same_v<CastType, AllowCrossCast> || std::is_base_of_v<A, B>>,+ typename = std::enable_if_t<std::is_class_v<A> && !is_pointer_like<A>>>+auto as(A& x) {+ return as<B, CastType>(&x);+}++template <typename B, typename CastType = void, typename A, typename = std::enable_if_t<is_pointer_like<A>>>+auto as(const A& x) {+ return as<B, CastType>(x.get());+}++template <typename B, typename CastType = void, typename A>+auto as(const std::reference_wrapper<A>& x) {+ return as<B, CastType>(x.get());+}++/**+ * Down-casts and checks the cast has succeeded+ */+template <typename B, typename CastType = void, typename A>+auto& asAssert(A&& a) {+ auto* cast = as<B, CastType>(std::forward<A>(a));+ assert(cast && "Invalid cast");+ return *cast;+}++template <typename B, typename CastType = void, typename A>+Own<B> UNSAFE_cast(Own<A> x) {+ if constexpr (std::is_assignable_v<Own<B>, Own<A>>) {+ return x;+ } else {+ if (!x) return {};++ auto y = Own<B>(as<B, CastType>(x));+ assert(y && "incorrect typed return");+ x.release(); // release after assert so dbgr can report `x` if it fails+ return y;+ }+}++/**+ * Checks if the object of type Source can be casted to type Destination.+ */+template <typename B, typename CastType = void, typename A>+// [[deprecated("Use `as` and implicit boolean conversion instead.")]]+bool isA(A&& src) {+ return as<B, CastType>(std::forward<A>(src));+}++} // namespace souffle
− cbits/souffle/utility/FunctionalUtil.h
@@ -1,166 +0,0 @@-/*- * Souffle - A Datalog Compiler- * Copyright (c) 2021, The Souffle Developers. All rights reserved- * Licensed under the Universal Permissive License v 1.0 as shown at:- * - https://opensource.org/licenses/UPL- * - <souffle root>/licenses/SOUFFLE-UPL.txt- */--/************************************************************************- *- * @file FunctionalUtil.h- *- * @brief Datalog project utilities- *- ***********************************************************************/--#pragma once--#include <algorithm>-#include <functional>-#include <set>-#include <utility>-#include <vector>--namespace souffle {--// --------------------------------------------------------------------------------// Functional Utils-// ---------------------------------------------------------------------------------/**- * A functor comparing the dereferenced value of a pointer type utilizing a- * given comparator. Its main use case are sets of non-null pointers which should- * be ordered according to the value addressed by the pointer.- */-template <typename T, typename C = std::less<T>>-struct deref_less {- bool operator()(const T* a, const T* b) const {- return C()(*a, *b);- }-};--// --------------------------------------------------------------------------------// Lambda Utils-// ---------------------------------------------------------------------------------namespace detail {--template <typename T>-struct lambda_traits_helper;--template <typename R>-struct lambda_traits_helper<R()> {- using result_type = R;-};--template <typename R, typename A0>-struct lambda_traits_helper<R(A0)> {- using result_type = R;- using arg0_type = A0;-};--template <typename R, typename A0, typename A1>-struct lambda_traits_helper<R(A0, A1)> {- using result_type = R;- using arg0_type = A0;- using arg1_type = A1;-};--template <typename R, typename... Args>-struct lambda_traits_helper<R(Args...)> {- using result_type = R;-};--template <typename R, typename C, typename... Args>-struct lambda_traits_helper<R (C::*)(Args...)> : public lambda_traits_helper<R(Args...)> {};--template <typename R, typename C, typename... Args>-struct lambda_traits_helper<R (C::*)(Args...) const> : public lambda_traits_helper<R (C::*)(Args...)> {};-} // namespace detail--/**- * A type trait enabling the deduction of type properties of lambdas.- * Those include so far:- * - the result type (result_type)- * - the first argument type (arg0_type)- */-template <typename Lambda>-struct lambda_traits : public detail::lambda_traits_helper<decltype(&Lambda::operator())> {};--// --------------------------------------------------------------------------------// General Algorithms-// ---------------------------------------------------------------------------------/**- * A generic test checking whether all elements within a container satisfy a- * certain predicate.- *- * @param c the container- * @param p the predicate- * @return true if for all elements x in c the predicate p(x) is true, false- * otherwise; for empty containers the result is always true- */-template <typename Container, typename UnaryPredicate>-bool all_of(const Container& c, UnaryPredicate p) {- return std::all_of(c.begin(), c.end(), p);-}--/**- * A generic test checking whether any elements within a container satisfy a- * certain predicate.- *- * @param c the container- * @param p the predicate- * @return true if there is an element x in c such that predicate p(x) is true, false- * otherwise; for empty containers the result is always false- */-template <typename Container, typename UnaryPredicate>-bool any_of(const Container& c, UnaryPredicate p) {- return std::any_of(c.begin(), c.end(), p);-}--/**- * A generic test checking whether all elements within a container satisfy a- * certain predicate.- *- * @param c the container- * @param p the predicate- * @return true if for all elements x in c the predicate p(x) is true, false- * otherwise; for empty containers the result is always true- */-template <typename Container, typename UnaryPredicate>-bool none_of(const Container& c, UnaryPredicate p) {- return std::none_of(c.begin(), c.end(), p);-}--/**- * Filter a vector to exclude certain elements.- */-template <typename A, typename F>-std::vector<A> filterNot(std::vector<A> xs, F&& f) {- xs.erase(std::remove_if(xs.begin(), xs.end(), std::forward<F>(f)), xs.end());- return xs;-}--/**- * Filter a vector to include certain elements.- */-template <typename A, typename F>-std::vector<A> filter(std::vector<A> xs, F&& f) {- return filterNot(std::move(xs), [&](auto&& x) { return !f(x); });-}--// --------------------------------------------------------------------------------// Set Utilities-// ---------------------------------------------------------------------------------template <typename A>-std::set<A> operator-(const std::set<A>& lhs, const std::set<A>& rhs) {- std::set<A> result;- std::set_difference(- lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), std::inserter(result, result.begin()));- return result;-}--} // namespace souffle
+ cbits/souffle/utility/General.h view
@@ -0,0 +1,27 @@+/*+ * Souffle - A Datalog Compiler+ * Copyright (c) 2021, The Souffle Developers. All rights reserved+ * Licensed under the Universal Permissive License v 1.0 as shown at:+ * - https://opensource.org/licenses/UPL+ * - <souffle root>/licenses/SOUFFLE-UPL.txt+ */++/************************************************************************+ *+ * @file General.h+ *+ * @brief Lightweight / cheap header for misc utilities.+ *+ * Misc utilities that require non-trivial headers should go in `MiscUtil.h`+ *+ ***********************************************************************/++#if defined(_MSC_VER)+#define SOUFFLE_ALWAYS_INLINE /* TODO: MSVC equiv */+#else+// clang / gcc recognize this attribute+// NB: GCC will only inline when optimisation is on, and will warn about it.+// Adding `inline` (even though the KW nominally has nothing to do with+// inlining) will force it to inline in all cases. Lovely.+#define SOUFFLE_ALWAYS_INLINE [[gnu::always_inline]] inline+#endif
cbits/souffle/utility/Iteration.h view
@@ -29,7 +29,8 @@ // This is a helper in the cases when the lambda is stateless template <typename F>-F const& makeFun() {+F makeFun() {+ static_assert(std::is_empty_v<F>); // Even thought the lambda is stateless, it has no default ctor // Is this gross? Yes, yes it is. // FIXME: Remove after C++20@@ -52,36 +53,22 @@ template <typename Iter, typename F> class TransformIterator { using iter_t = std::iterator_traits<Iter>;++public: using difference_type = typename iter_t::difference_type;- using reference = decltype(std::declval<F&>()(*std::declval<Iter>()));+ // TODO: The iterator concept doesn't map correctly to ephemeral views.+ // e.g. there is no l-value store for a deref.+ // Figure out what these should be set to.+ using value_type = decltype(std::declval<F>()(*std::declval<Iter>()));+ using pointer = std::remove_reference_t<value_type>*;+ using reference = value_type; static_assert(std::is_empty_v<F>, "Function object must be stateless"); -public: // some constructors- template <typename It>- TransformIterator(It iter, std::enable_if_t<std::is_empty_v<F>, void*> = nullptr)- : iter(std::move(iter)), fun(detail::makeFun<F>()) {}+ template <typename = std::enable_if_t<std::is_empty_v<F>>>+ TransformIterator(Iter iter) : TransformIterator(std::move(iter), detail::makeFun<F>()) {} TransformIterator(Iter iter, F f) : iter(std::move(iter)), fun(std::move(f)) {} - // defaulted copy and move constructors- TransformIterator(const TransformIterator& other) : iter(other.iter), fun(other.fun) {}- TransformIterator(TransformIterator&& other) : iter(std::move(other.iter)), fun(std::move(other.fun)) {}-- // default assignment operators- TransformIterator& operator=(const TransformIterator& other) {- if (this != &other) {- iter = other.iter;- }- return *this;- }-- TransformIterator& operator=(TransformIterator&& other) {- if (this != &other) {- iter = std::move(other.iter);- }- return *this;- }- /* The equality operator as required by the iterator concept. */ bool operator==(const TransformIterator& other) const { return iter == other.iter;@@ -114,7 +101,7 @@ } /* Support for the pointer operator. */- auto operator->() const {+ auto operator-> () const { return &**this; } @@ -194,11 +181,26 @@ * dereferencing values before forwarding them to the consumer. */ namespace detail {-inline auto iterDeref = [](auto& p) -> decltype(*p) { return *p; };-}+// HACK: Use explicit structure w/ `operator()` b/c pre-C++20 lambdas do not have copy-assign operators+struct IterTransformDeref {+ template <typename A>+ auto operator()(A&& x) const -> decltype(*x) {+ return *x;+ }+}; +// HACK: Use explicit structure w/ `operator()` b/c pre-C++20 lambdas do not have copy-assign operators+struct IterTransformToPtr {+ template <typename A>+ A* operator()(Own<A> const& x) const {+ return x.get();+ }+};++} // namespace detail+ template <typename Iter>-using IterDerefWrapper = TransformIterator<Iter, decltype(detail::iterDeref)>;+using IterDerefWrapper = TransformIterator<Iter, detail::IterTransformDeref>; /** * A factory function enabling the construction of a dereferencing@@ -206,9 +208,17 @@ */ template <typename Iter> auto derefIter(Iter&& iter) {- return transformIter(std::forward<Iter>(iter), detail::iterDeref);+ return transformIter(std::forward<Iter>(iter), detail::IterTransformDeref{}); } +/**+ * A factory function that transforms an smart-ptr iter to dumb-ptr iter.+ */+template <typename Iter>+auto ptrIter(Iter&& iter) {+ return transformIter(std::forward<Iter>(iter), detail::IterTransformToPtr{});+}+ // ------------------------------------------------------------- // Ranges // -------------------------------------------------------------@@ -219,6 +229,9 @@ */ template <typename Iter> struct range {+ using iterator = Iter;+ using const_iterator = Iter;+ // the lower and upper boundary Iter a, b; @@ -313,12 +326,21 @@ return make_range(derefIter(std::forward<Iter>(begin)), derefIter(std::forward<Iter>(end))); } +template <typename R>+auto makePtrRange(R const& xs) {+ return make_range(ptrIter(std::begin(xs)), ptrIter(std::end(xs)));+}+ /** * This wraps the Range container, and const_casts in place. */ template <typename Range, typename F> class OwningTransformRange { public:+ using iterator = decltype(transformIter(std::begin(std::declval<Range>()), std::declval<F>()));+ using const_iterator =+ decltype(transformIter(std::begin(std::declval<const Range>()), std::declval<const F>()));+ OwningTransformRange(Range&& range, F f) : range(std::move(range)), f(std::move(f)) {} auto begin() {@@ -338,7 +360,7 @@ } auto end() const {- return transformIter(std::begin(range), f);+ return transformIter(std::end(range), f); } auto cend() const {@@ -361,14 +383,5 @@ Range range; F f; };--/**- * Convert a range of any ptr-like to a range- * of pointers- */-template <typename R>-auto makePtrRange(R const& range) {- return makeTransformRange(range, [](auto const& ptrLike) { return &*ptrLike; });-} } // namespace souffle
cbits/souffle/utility/MiscUtil.h view
@@ -16,13 +16,17 @@ #pragma once +#include "souffle/utility/General.h" #include "souffle/utility/Iteration.h" #include "souffle/utility/Types.h" #include "tinyformat.h" #include <cassert> #include <chrono> #include <iostream>+#include <map> #include <memory>+#include <optional>+#include <type_traits> #include <utility> #ifdef _WIN32@@ -135,6 +139,14 @@ return clone(node.get()); } +template <typename K, typename V>+auto clone(const std::map<K, V>& xs) {+ std::map<K, decltype(clone(std::declval<const V&>()))> ys;+ for (auto&& [k, v] : xs)+ ys.insert({k, clone(v)});+ return ys;+}+ /** * Clone a range */@@ -186,75 +198,6 @@ return equal_ptr(a.get(), b.get()); } -/**- * This class is used to tell as<> that cross-casting is allowed.- * I use a named type rather than just a bool to make the code stand out.- */-class AllowCrossCast {};--/**- * Helpers for `dynamic_cast`ing without having to specify redundant type qualifiers.- * e.g. `as<AstLiteral>(p)` instead of `as<AstLiteral>(p)`.- */-template <typename B, typename CastType = void, typename A>-auto as(A* x) {- if constexpr (!std::is_same_v<CastType, AllowCrossCast>) {- static_assert(std::is_base_of_v<std::remove_const_t<A>, std::remove_const_t<B>>,- "`as<B, A>` does not allow cross-type dyn casts. "- "(i.e. `as<B, A>` where `B <: A` is not true.) "- "Such a cast is likely a mistake or typo.");- }- return dynamic_cast<copy_const_t<A, B>*>(x);-}--template <typename B, typename CastType = void, typename A>-auto as(A& x) {- return as<B, CastType>(&x);-}--template <typename B, typename CastType = void, typename A>-auto as(Own<A>& x) {- return as<B, CastType>(x.get());-}--template <typename B, typename CastType = void, typename A>-auto as(const Own<A>& x) {- return as<B, CastType>(x.get());-}--/**- * Down-casts and checks the cast has succeeded- */-template <typename B, typename CastType = void, typename A>-auto& asAssert(A&& a) {- auto* cast = as<B, CastType>(std::forward<A>(a));- assert(cast && "Invalid cast");- return *cast;-}--/**- * Checks if the object of type Source can be casted to type Destination.- */-template <typename B, typename A>-bool isA(A* x) {- // Dont't forward onto as<> - need to check cross-casting- return dynamic_cast<copy_const_t<A, B>*>(x) != nullptr;-}--template <typename B, typename A>-auto isA(A& x) {- return isA<B>(&x);-}--template <typename B, typename A>-bool isA(const Own<A>& x) {- return isA<B>(x.get());-}--template <typename B, typename A>-bool isA(Own<A>& x) {- return isA<B>(x.get());-} // ------------------------------------------------------------------------------- // Error Utilities // -------------------------------------------------------------------------------@@ -269,4 +212,18 @@ // HACK: Workaround to suppress spurious reachability warnings. #define UNREACHABLE_BAD_CASE_ANALYSIS fatal("unhandled switch branch");++// -------------------------------------------------------------------------------+// Other Utilities+// -------------------------------------------------------------------------------++template <typename F>+auto lazy(F f) {+ using A = decltype(f());+ return [cache = std::optional<A>{}, f = std::move(f)]() mutable -> A& {+ if (!cache) cache = f();+ return *cache;+ };+}+ } // namespace souffle
cbits/souffle/utility/ParallelUtil.h view
@@ -23,8 +23,8 @@ #include <memory> #include <new> -#if defined(__cpp_lib_hardware_interference_size) && \- (!defined(__APPLE__)) // https://bugs.llvm.org/show_bug.cgi?id=41423+// https://bugs.llvm.org/show_bug.cgi?id=41423+#if defined(__cpp_lib_hardware_interference_size) && (__cpp_lib_hardware_interference_size != 201703L) using std::hardware_constructive_interference_size; using std::hardware_destructive_interference_size; #else@@ -44,6 +44,10 @@ #ifdef __APPLE__ #define pthread_yield pthread_yield_np+#elif !defined(_MSC_VER)+#include <sched.h>+// pthread_yield is deprecated and should be replaced by sched_yield+#define pthread_yield sched_yield #endif // support for a parallel region@@ -521,7 +525,7 @@ } }; -/** Concurrent tracks locking mechanism. */+/** Concurrent lanes locking mechanism. */ struct MutexConcurrentLanes { using lane_id = std::size_t; using unique_lock_type = std::unique_lock<std::mutex>;@@ -561,29 +565,27 @@ return unique_lock_type(Lanes[Lane].Access); } - // Lock the given track.+ // Lock the given lane. // Must eventually be followed by unlock(Lane). void lock(const lane_id Lane) const {- assert(Lane < Size); Lanes[Lane].Access.lock(); } - // Unlock the given track.- // Must already be the owner of the track's lock.+ // Unlock the given lane.+ // Must already be the owner of the lane's lock. void unlock(const lane_id Lane) const {- assert(Lane < Size); Lanes[Lane].Access.unlock(); } - // Acquire the capability to lock all other tracks than the given one.+ // Acquire the capability to lock all other lanes than the given one. // // Must eventually be followed by beforeUnlockAllBut(Lane). void beforeLockAllBut(const lane_id Lane) const { if (!BeforeLockAll.try_lock()) { // If we cannot get the lock immediately, it means it was acquired- // concurrently by another track that will also try to acquire our- // track lock.- // So we release our track lock to let the concurrent operation+ // concurrently by another lane that will also try to acquire our+ // lane lock.+ // So we release our lane lock to let the concurrent operation // progress. unlock(Lane); BeforeLockAll.lock();@@ -591,16 +593,16 @@ } } - // Release the capability to lock all other tracks than the given one.+ // Release the capability to lock all other lanes than the given one. // // Must already be the owner of that capability. void beforeUnlockAllBut(const lane_id) const { BeforeLockAll.unlock(); } - // Lock all tracks but the given one.+ // Lock all lanes but the given one. //- // Must already have acquired the capability to lock all other tracks+ // Must already have acquired the capability to lock all other lanes // by calling beforeLockAllBut(Lane). // // Must eventually be followed by unlockAllBut(Lane).@@ -612,8 +614,8 @@ } } - // Unlock all tracks but the given one.- // Must already be the owner of all the tracks' locks.+ // Unlock all lanes but the given one.+ // Must already be the owner of all the lanes' locks. void unlockAllBut(const lane_id Lane) const { for (std::size_t I = 0; I < Size; ++I) { if (I != Lane) {
cbits/souffle/utility/StreamUtil.h view
@@ -166,9 +166,8 @@ * For use cases see the test case {util_test.cpp}. */ template <typename Iter, typename Printer>-detail::joined_sequence<Iter, Printer> join(- const Iter& a, const Iter& b, const std::string& sep, const Printer& p) {- return souffle::detail::joined_sequence<Iter, Printer>(a, b, sep, p);+detail::joined_sequence<Iter, Printer> join(const Iter& a, const Iter& b, std::string sep, const Printer& p) {+ return souffle::detail::joined_sequence<Iter, Printer>(a, b, std::move(sep), p); } /**@@ -190,8 +189,8 @@ * For use cases see the test case {util_test.cpp}. */ template <typename Container, typename Printer, typename Iter = typename Container::const_iterator>-detail::joined_sequence<Iter, Printer> join(const Container& c, const std::string& sep, const Printer& p) {- return join(c.begin(), c.end(), sep, p);+detail::joined_sequence<Iter, Printer> join(const Container& c, std::string sep, const Printer& p) {+ return join(c.begin(), c.end(), std::move(sep), p); } // Decide if the sane default is to deref-then-print or just print.@@ -208,15 +207,25 @@ template <typename Container, typename Iter = typename Container::const_iterator, typename T = typename std::iterator_traits<Iter>::value_type> std::enable_if_t<!JoinShouldDeref<T>, detail::joined_sequence<Iter, detail::print<id<T>>>> join(- const Container& c, const std::string& sep = ",") {- return join(c.begin(), c.end(), sep, detail::print<id<T>>());+ const Container& c, std::string sep = ",") {+ return join(c.begin(), c.end(), std::move(sep), detail::print<id<T>>()); } template <typename Container, typename Iter = typename Container::const_iterator, typename T = typename std::iterator_traits<Iter>::value_type> std::enable_if_t<JoinShouldDeref<T>, detail::joined_sequence<Iter, detail::print<deref<T>>>> join(- const Container& c, const std::string& sep = ",") {- return join(c.begin(), c.end(), sep, detail::print<deref<T>>());+ const Container& c, std::string sep = ",") {+ return join(c.begin(), c.end(), std::move(sep), detail::print<deref<T>>());+}++template <typename C, typename F>+auto joinMap(const C& c, F&& map) {+ return join(c.begin(), c.end(), ",", [&](auto&& os, auto&& x) { return os << map(x); });+}++template <typename C, typename F>+auto joinMap(const C& c, std::string sep, F&& map) {+ return join(c.begin(), c.end(), std::move(sep), [&](auto&& os, auto&& x) { return os << map(x); }); } } // end namespace souffle
cbits/souffle/utility/StringUtil.h view
@@ -22,6 +22,7 @@ #include <cstdlib> #include <fstream> #include <limits>+#include <set> #include <sstream> #include <stdexcept> #include <string>@@ -312,17 +313,34 @@ /** * Splits a string given a delimiter */-inline std::vector<std::string> splitString(const std::string& str, char delimiter) {- std::vector<std::string> parts;- std::stringstream strstr(str);- std::string token;- while (std::getline(strstr, token, delimiter)) {- parts.push_back(token);+inline std::vector<std::string_view> splitView(std::string_view toSplit, std::string_view delimiter) {+ if (toSplit.empty()) return {toSplit};++ auto delimLen = std::max<size_t>(1, delimiter.size()); // ensure we advance even w/ an empty needle++ std::vector<std::string_view> parts;+ for (auto tail = toSplit;;) {+ auto pos = tail.find(delimiter);+ parts.push_back(tail.substr(0, pos));+ if (pos == tail.npos) break;++ tail = tail.substr(pos + delimLen); }+ return parts; } /**+ * Splits a string given a delimiter+ */+inline std::vector<std::string> splitString(std::string_view str, char delimiter) {+ std::vector<std::string> xs;+ for (auto&& x : splitView(str, std::string_view{&delimiter, 1}))+ xs.push_back(std::string(x));+ return xs;+}++/** * Strips the prefix of a given string if it exists. No change otherwise. */ inline std::string stripPrefix(const std::string& prefix, const std::string& element) {@@ -432,6 +450,22 @@ escaped = escape(escaped, "\r", "\\r"); escaped = escape(escaped, "\n", "\\n"); return escaped;+}++template <typename C>+auto escape(C&& os, std::string_view str, std::set<char> const& needs_escape, std::string_view esc) {+ for (auto&& x : str) {+ if (needs_escape.find(x) != needs_escape.end()) {+ os << esc;+ }+ os << x;+ }++ return std::forward<C>(os);+}++inline std::string escape(std::string_view str, std::set<char> const& needs_escape, std::string_view esc) {+ return escape(std::stringstream{}, str, needs_escape, esc).str(); } } // end namespace souffle
cbits/souffle/utility/Types.h view
@@ -16,11 +16,40 @@ #pragma once +#include <iterator> #include <memory> #include <type_traits> #include <vector> namespace souffle {++// TODO: replace with C++20 concepts+template <typename CC, typename A>+constexpr bool is_iterable_of = std::is_constructible_v<A&,+ typename std::iterator_traits<decltype(std::begin(std::declval<CC>()))>::value_type&>;++// basically std::monostate, but doesn't require importing all of `<variant>`+struct Unit {};++constexpr bool operator==(Unit, Unit) noexcept {+ return true;+}+constexpr bool operator<=(Unit, Unit) noexcept {+ return true;+}+constexpr bool operator>=(Unit, Unit) noexcept {+ return true;+}+constexpr bool operator!=(Unit, Unit) noexcept {+ return false;+}+constexpr bool operator<(Unit, Unit) noexcept {+ return false;+}+constexpr bool operator>(Unit, Unit) noexcept {+ return false;+}+ template <typename A> using Own = std::unique_ptr<A>; @@ -36,29 +65,52 @@ * Copy the const qualifier of type T onto type U */ template <typename A, typename B>-using copy_const = std::conditional<std::is_const_v<A>, const B, B>;--template <typename A, typename B>-using copy_const_t = typename copy_const<A, B>::type;+using copy_const = std::conditional_t<std::is_const_v<A>, const B, B>; namespace detail {++template <typename A>+struct is_own_ptr_t : std::false_type {};++template <typename A>+struct is_own_ptr_t<Own<A>> : std::true_type {};+ template <typename T, typename U = void> struct is_range_impl : std::false_type {}; template <typename T> struct is_range_impl<T, std::void_t<decltype(*std::begin(std::declval<T&>()))>> : std::true_type {}; +template <typename A, typename = void>+struct is_associative : std::false_type {};++template <typename A>+struct is_associative<A, std::void_t<typename A::key_type>> : std::true_type {};++template <typename A, typename = void, typename = void>+struct is_set : std::false_type {};++template <typename A>+struct is_set<A, std::void_t<typename A::key_type>, std::void_t<typename A::value_type>>+ : std::is_same<typename A::key_type, typename A::value_type> {};+ } // namespace detail +template <typename A>+constexpr bool is_own_ptr = detail::is_own_ptr_t<std::decay_t<A>>::value;+ /** * A simple test to check if T is a range (i.e. has std::begin()) */ template <typename T> struct is_range : detail::is_range_impl<T> {}; -template <typename T>-inline constexpr bool is_range_v = is_range<T>::value;+template <typename A>+constexpr bool is_range_v = is_range<A>::value; +template <typename A>+constexpr bool is_remove_ref_const = std::is_const_v<std::remove_reference_t<A>>;+ /** * Type identity, remove once we have C++20 */@@ -76,13 +128,28 @@ template <class T> using remove_cvref_t = typename remove_cvref<T>::type; +namespace detail { template <typename T> struct is_pointer_like : std::is_pointer<T> {}; template <typename T> struct is_pointer_like<Own<T>> : std::true_type {}; +} // namespace detail+ template <typename T>-inline constexpr bool is_pointer_like_v = is_pointer_like<T>::value;+constexpr bool is_pointer_like = detail::is_pointer_like<remove_cvref_t<T>>::value;++// TODO: complete these or move to C++20+template <typename A>+constexpr bool is_associative = detail::is_associative<A>::value;++template <typename A>+constexpr bool is_set = detail::is_set<A>::value;++// Useful for `static_assert`ing in unhandled cases with `constexpr` static dispatching+// Gives nicer error messages. (e.g. "failed due to req' unhandled_dispatch_type<...>")+template <typename A>+constexpr bool unhandled_dispatch_type = !std::is_same_v<A, A>; } // namespace souffle
cbits/souffle/utility/span.h view
@@ -282,9 +282,13 @@ !std::is_same<typename std::remove_cv<decltype( detail::data(std::declval<T>()))>::type, void>::value>::type>+ // HACK: WORKAROUND - GCC 9.2.1 claims `A* (*)[]` is not compatible w/ `A const* (*)[]`.+ // This seems BS and Clang 10.0 is perfectly happy.+ // GCC 9.2.1 does, however, agree that `A**` is compatible w/ `A const**`.+ // Use the `*` test instead of `(*)[]`. : std::is_convertible<- remove_pointer_t<decltype(detail::data(std::declval<T>()))> (*)[],- E (*)[]> {};+ remove_pointer_t<decltype(detail::data(std::declval<T>()))>*,+ E*> {}; template <typename, typename = std::size_t> struct is_complete : std::false_type {};
+ lib/Language/Souffle/Analysis.hs view
@@ -0,0 +1,134 @@+{-# LANGUAGE UndecidableInstances, TupleSections #-}++{- | This module provides an 'Analysis' type for combining multiple Datalog+ analyses together. Composition of analyses is done via the various+ type-classes that are implemented for this type. For a longer explanation+ of how the 'Analysis' type works, see this+ <https://luctielen.com/posts/analyses_are_arrows/ blogpost>.++ If you are just starting out using this library, you are probably better+ of taking a look at the "Language.Souffle.Interpreted" module instead to+ start interacting with a single Datalog program.+-}+module Language.Souffle.Analysis+ ( Analysis+ , mkAnalysis+ , execAnalysis+ ) where++import Prelude hiding (id, (.))+import Control.Category+import Control.Monad+import Control.Arrow+import Data.Profunctor++-- | Data type used to compose multiple Datalog programs. Composition is mainly+-- done via the various type-classes implemented for this type.+-- Values of this type can be created using 'mkAnalysis'.+--+-- The @m@ type-variable represents the monad the analysis will run in. In+-- most cases, this will be the @SouffleM@ monad from either+-- "Language.Souffle.Compiled" or "Language.Souffle.Interpreted".+-- The @a@ and @b@ type-variables represent respectively the input and output+-- types of the analysis.+data Analysis m a b+ = Analysis (a -> m ()) (m ()) (a -> m b)++-- | Creates an 'Analysis' value.+mkAnalysis :: (a -> m ()) -- ^ Function for finding facts used by the 'Analysis'.+ -> m () -- ^ Function for actually running the 'Analysis'.+ -> m b -- ^ Function for retrieving the 'Analysis' results from Souffle.+ -> Analysis m a b+mkAnalysis f r g = Analysis f r (const g)++-- | Converts an 'Analysis' into an effectful function, so it can be executed.+execAnalysis :: Applicative m => Analysis m a b -> (a -> m b)+execAnalysis (Analysis f r g) a = f a *> r *> g a++instance Functor m => Functor (Analysis m a) where+ fmap func (Analysis f r g) =+ Analysis f r (fmap func <$> g)++instance Functor m => Profunctor (Analysis m) where+ lmap fn (Analysis f r g) =+ Analysis (lmap fn f) r (lmap fn g)+ rmap = fmap++instance (Monoid (m ()), Applicative m) => Applicative (Analysis m a) where+ pure a = Analysis mempty mempty (const $ pure a)++ Analysis f1 r1 g1 <*> Analysis f2 r2 g2 =+ Analysis (f1 <> f2) (r1 <> r2) (\a -> g1 a <*> g2 a)++instance (Semigroup (m ()), Semigroup (m b)) => Semigroup (Analysis m a b) where+ Analysis f1 r1 g1 <> Analysis f2 r2 g2 =+ Analysis (f1 <> f2) (r1 <> r2) (g1 <> g2)++instance (Monoid (m ()), Monoid (m b)) => Monoid (Analysis m a b) where+ mempty = Analysis mempty mempty mempty++instance (Monoid (m ()), Monad m) => Category (Analysis m) where+ id = Analysis mempty mempty pure++ Analysis f1 r1 g1 . Analysis f2 r2 g2 = Analysis f r1 g+ where+ f = execAnalysis (Analysis f2 r2 g2) >=> f1+ -- NOTE: lazyness avoids work here in g2 in cases where "const" is used+ g = g2 >=> g1++instance Functor m => Strong (Analysis m) where+ first' (Analysis f r g) =+ Analysis (f . fst) r $ \(b, d) -> (,d) <$> g b++ second' (Analysis f r g) =+ Analysis (f . snd) r $ \(d, b) -> (d,) <$> g b++instance Applicative m => Choice (Analysis m) where+ left' (Analysis f r g) = Analysis f' r g'+ where+ f' = \case+ Left b -> f b+ Right _ -> pure ()+ g' = \case+ Left b -> Left <$> g b+ Right d -> pure $ Right d++ right' (Analysis f r g) = Analysis f' r g'+ where+ f' = \case+ Left _ -> pure ()+ Right b -> f b+ g' = \case+ Left d -> pure $ Left d+ Right b -> Right <$> g b++instance (Monad m, Monoid (m ()), Category (Analysis m)) => Arrow (Analysis m) where+ arr f = Analysis mempty mempty (pure . f)++ first = first'++ second = second'++ Analysis f1 r1 g1 *** Analysis f2 r2 g2 =+ Analysis (\(b, b') -> f1 b *> f2 b') (r1 <> r2) $ \(b, b') -> do+ c <- g1 b+ c' <- g2 b'+ pure (c, c')++ Analysis f1 r1 g1 &&& Analysis f2 r2 g2 =+ Analysis (f1 <> f2) (r1 <> r2) $ \b -> (,) <$> g1 b <*> g2 b++instance (Monad m, Monoid (m ())) => ArrowChoice (Analysis m) where+ left = left'++ right = right'++ Analysis f1 r1 g1 +++ Analysis f2 r2 g2 = Analysis f' (r1 <> r2) g'+ where+ f' = \case+ Left b -> f1 b+ Right b' -> f2 b'+ g' = \case+ Left b -> Left <$> g1 b+ Right b' -> Right <$> g2 b'+
lib/Language/Souffle/Interpreted.hs view
@@ -35,7 +35,7 @@ import Control.Monad.State.Strict import Data.IORef import Data.Foldable (traverse_)-import Data.List hiding (init)+import qualified Data.List as List hiding (init) import Data.Semigroup (Last(..)) import Data.Maybe (fromMaybe) import Data.Proxy@@ -334,7 +334,7 @@ => Handle prog -> a -> SouffleM (Maybe a) findFact prog fact = do facts :: [a] <- getFacts prog- pure $ find (== fact) facts+ pure $ List.find (== fact) facts {-# INLINABLE findFact #-} addFact :: forall a prog. (Fact a, ContainsInputFact prog a, Marshal a)@@ -344,7 +344,7 @@ let relationName = factName (Proxy :: Proxy a) let factFile = factPath handle </> relationName <.> "facts" let line = pushMarshalT (push fact)- appendFile factFile $ intercalate "\t" line ++ "\n"+ appendFile factFile $ List.intercalate "\t" line ++ "\n" {-# INLINABLE addFact #-} addFacts :: forall a prog f. (Fact a, ContainsInputFact prog a, Marshal a, Foldable f)@@ -354,7 +354,7 @@ let relationName = factName (Proxy :: Proxy a) let factFile = factPath handle </> relationName <.> "facts" let factLines = map (pushMarshalT . push) (foldMap pure facts)- traverse_ (\line -> appendFile factFile (intercalate "\t" line ++ "\n")) factLines+ traverse_ (\line -> appendFile factFile (List.intercalate "\t" line ++ "\n")) factLines {-# INLINABLE addFacts #-} datalogProgramFile :: forall prog. Program prog => prog -> FilePath -> IO (Maybe FilePath)
souffle-haskell.cabal view
@@ -5,7 +5,7 @@ -- see: https://github.com/sol/hpack name: souffle-haskell-version: 3.1.0+version: 3.2.0 synopsis: Souffle Datalog bindings for Haskell description: Souffle Datalog bindings for Haskell. category: Logic Programming, Foreign Binding, Bindings@@ -25,6 +25,8 @@ cbits/souffle/CompiledSouffle.h cbits/souffle/datastructure/Brie.h cbits/souffle/datastructure/BTree.h+ cbits/souffle/datastructure/BTreeDelete.h+ cbits/souffle/datastructure/BTreeUtil.h cbits/souffle/datastructure/ConcurrentFlyweight.h cbits/souffle/datastructure/ConcurrentInsertOnlyHashMap.h cbits/souffle/datastructure/EquivalenceRelation.h@@ -50,9 +52,10 @@ cbits/souffle/SymbolTable.h cbits/souffle/utility/CacheUtil.h cbits/souffle/utility/ContainerUtil.h+ cbits/souffle/utility/DynamicCasting.h cbits/souffle/utility/EvaluatorUtil.h cbits/souffle/utility/FileUtil.h- cbits/souffle/utility/FunctionalUtil.h+ cbits/souffle/utility/General.h cbits/souffle/utility/Iteration.h cbits/souffle/utility/json11.h cbits/souffle/utility/MiscUtil.h@@ -71,6 +74,7 @@ library exposed-modules:+ Language.Souffle.Analysis Language.Souffle.Class Language.Souffle.Compiled Language.Souffle.Internal@@ -102,13 +106,17 @@ souffle/SouffleInterface.h souffle/SymbolTable.h souffle/utility/MiscUtil.h+ souffle/utility/General.h souffle/utility/Iteration.h souffle/utility/Types.h souffle/utility/tinyformat.h souffle/utility/StreamUtil.h souffle/utility/ContainerUtil.h- souffle/datastructure/Brie.h+ souffle/utility/DynamicCasting.h+ souffle/datastructure/BTreeDelete.h+ souffle/datastructure/BTreeUtil.h souffle/utility/CacheUtil.h+ souffle/datastructure/Brie.h souffle/datastructure/EquivalenceRelation.h souffle/datastructure/LambdaBTree.h souffle/datastructure/BTree.h@@ -130,19 +138,20 @@ souffle/io/ReadStreamSQLite.h souffle/io/WriteStreamSQLite.h souffle/utility/EvaluatorUtil.h- souffle/utility/FunctionalUtil.h+ souffle/utility/EvaluatorUtil.h cxx-sources: cbits/souffle.cpp build-depends: array <=1.0 , base >=4.12 && <5- , bytestring+ , bytestring >=0.10.10 && <1 , containers >=0.6.2.1 && <1 , deepseq >=1.4.4 && <2 , directory >=1.3.3 && <2 , filepath >=1.4.2 && <2 , mtl >=2.0 && <3 , process >=1.6 && <2+ , profunctors >=5.6.2 && <6 , template-haskell >=2 && <3 , temporary >=1.3 && <2 , text >=1.0 && <2@@ -158,6 +167,7 @@ type: exitcode-stdio-1.0 main-is: test.hs other-modules:+ Test.Language.Souffle.AnalysisSpec Test.Language.Souffle.CompiledSpec Test.Language.Souffle.InterpretedSpec Test.Language.Souffle.MarshalSpec@@ -182,13 +192,17 @@ souffle/SouffleInterface.h souffle/SymbolTable.h souffle/utility/MiscUtil.h+ souffle/utility/General.h souffle/utility/Iteration.h souffle/utility/Types.h souffle/utility/tinyformat.h souffle/utility/StreamUtil.h souffle/utility/ContainerUtil.h- souffle/datastructure/Brie.h+ souffle/utility/DynamicCasting.h+ souffle/datastructure/BTreeDelete.h+ souffle/datastructure/BTreeUtil.h souffle/utility/CacheUtil.h+ souffle/datastructure/Brie.h souffle/datastructure/EquivalenceRelation.h souffle/datastructure/LambdaBTree.h souffle/datastructure/BTree.h@@ -210,7 +224,7 @@ souffle/io/ReadStreamSQLite.h souffle/io/WriteStreamSQLite.h souffle/utility/EvaluatorUtil.h- souffle/utility/FunctionalUtil.h+ souffle/utility/EvaluatorUtil.h cxx-sources: tests/fixtures/edge_cases.cpp tests/fixtures/path.cpp@@ -218,7 +232,7 @@ build-depends: array <=1.0 , base >=4.12 && <5- , bytestring+ , bytestring >=0.10.10 && <1 , containers >=0.6.2.1 && <1 , deepseq >=1.4.4 && <2 , directory >=1.3.3 && <2@@ -229,6 +243,7 @@ , mtl >=2.0 && <3 , neat-interpolation ==0.* , process >=1.6 && <2+ , profunctors >=5.6.2 && <6 , souffle-haskell , template-haskell >=2 && <3 , temporary >=1.3 && <2@@ -266,13 +281,17 @@ souffle/SouffleInterface.h souffle/SymbolTable.h souffle/utility/MiscUtil.h+ souffle/utility/General.h souffle/utility/Iteration.h souffle/utility/Types.h souffle/utility/tinyformat.h souffle/utility/StreamUtil.h souffle/utility/ContainerUtil.h- souffle/datastructure/Brie.h+ souffle/utility/DynamicCasting.h+ souffle/datastructure/BTreeDelete.h+ souffle/datastructure/BTreeUtil.h souffle/utility/CacheUtil.h+ souffle/datastructure/Brie.h souffle/datastructure/EquivalenceRelation.h souffle/datastructure/LambdaBTree.h souffle/datastructure/BTree.h@@ -294,13 +313,13 @@ souffle/io/ReadStreamSQLite.h souffle/io/WriteStreamSQLite.h souffle/utility/EvaluatorUtil.h- souffle/utility/FunctionalUtil.h+ souffle/utility/EvaluatorUtil.h cxx-sources: benchmarks/fixtures/bench.cpp build-depends: array <=1.0 , base >=4.12 && <5- , bytestring+ , bytestring >=0.10.10 && <1 , containers >=0.6.2.1 && <1 , criterion , deepseq >=1.4.4 && <2@@ -308,6 +327,7 @@ , filepath >=1.4.2 && <2 , mtl >=2.0 && <3 , process >=1.6 && <2+ , profunctors >=5.6.2 && <6 , souffle-haskell , template-haskell >=2 && <3 , temporary >=1.3 && <2
+ tests/Test/Language/Souffle/AnalysisSpec.hs view
@@ -0,0 +1,249 @@+{-# LANGUAGE DataKinds, TypeFamilies, DeriveGeneric, Arrows #-}++module Test.Language.Souffle.AnalysisSpec+ ( module Test.Language.Souffle.AnalysisSpec+ ) where++import Prelude hiding ((.), id)+import Control.Arrow+import Control.Category+import Test.Hspec+import Data.Profunctor+import GHC.Generics+import Control.Monad.IO.Class+import Language.Souffle.Analysis+import qualified Language.Souffle.Interpreted as Souffle++data Path = Path++data Edge = Edge String String+ deriving (Eq, Show, Generic)++data Reachable = Reachable String String+ deriving (Eq, Show, Generic)++instance Souffle.Program Path where+ type ProgramFacts Path = [Edge, Reachable]+ programName = const "path"++instance Souffle.Fact Edge where+ type FactDirection Edge = 'Souffle.InputOutput+ factName = const "edge"++instance Souffle.Fact Reachable where+ type FactDirection Reachable = 'Souffle.Output+ factName = const "reachable"++instance Souffle.Marshal Edge+instance Souffle.Marshal Reachable++data Results = Results [Reachable] [Edge]+ deriving (Eq, Show)++pathAnalysis :: Souffle.Handle Path+ -> Analysis Souffle.SouffleM [Edge] [Reachable]+pathAnalysis h =+ mkAnalysis (Souffle.addFacts h) (Souffle.run h) (Souffle.getFacts h)++-- A little bit silly, but good enough to test different forms of application with+pathAnalysis' :: Souffle.Handle Path+ -> Analysis Souffle.SouffleM [Edge] [Edge]+pathAnalysis' h =+ mkAnalysis (Souffle.addFacts h) (Souffle.run h) (Souffle.getFacts h)++data RoundTrip = RoundTrip++newtype StringFact = StringFact String+ deriving (Eq, Show, Generic)++instance Souffle.Program RoundTrip where+ type ProgramFacts RoundTrip = '[StringFact]++ programName = const "round_trip"++instance Souffle.Fact StringFact where+ type FactDirection StringFact = 'Souffle.InputOutput++ factName = const "string_fact"++instance Souffle.Marshal StringFact+++roundTripAnalysis :: Souffle.Handle RoundTrip+ -> Analysis Souffle.SouffleM [Reachable] [StringFact]+roundTripAnalysis h =+ mkAnalysis addFacts (Souffle.run h) (Souffle.getFacts h)+ where+ addFacts rs = do+ Souffle.addFacts h $ map (\(Reachable a _) -> StringFact a) rs++withSouffle :: Souffle.Program a => a -> (Souffle.Handle a -> Souffle.SouffleM ()) -> IO ()+withSouffle prog f = Souffle.runSouffle prog $ \case+ Nothing -> error "Failed to load program"+ Just h -> f h++edges :: [Edge]+edges = [Edge "a" "b", Edge "b" "c", Edge "b" "d", Edge "d" "e"]++spec :: Spec+spec = describe "composing analyses" $ parallel $ do+ it "supports fmap" $ do+ withSouffle Path $ \h -> do+ let analysis = pathAnalysis h+ analysis' = fmap length analysis+ count <- execAnalysis analysis' edges+ liftIO $ count `shouldBe` 8++ describe "analysis used as a profunctor" $ parallel $ do+ it "supports lmap" $ do+ withSouffle Path $ \h -> do+ let inputs = [("a", "b"), ("b", "c")]+ analysis = pathAnalysis h+ analysis' = lmap (map (uncurry Edge)) analysis+ rs <- execAnalysis analysis' inputs+ liftIO $ rs `shouldBe` [ Reachable "a" "b"+ , Reachable "a" "c"+ , Reachable "b" "c"+ ]++ it "supports rmap" $ do+ withSouffle Path $ \h -> do+ let analysis = pathAnalysis h+ analysis' = rmap length analysis+ count <- execAnalysis analysis' edges+ liftIO $ count `shouldBe` 8++ it "supports applicative composition" $+ withSouffle Path $ \hPath -> do+ let analysis1 = pathAnalysis hPath+ analysis2 = pathAnalysis' hPath+ analysis = Results <$> analysis1 <*> analysis2+ inputs = [Edge "a" "b", Edge "b" "c"]+ reachables = [ Reachable "a" "b"+ , Reachable "a" "c"+ , Reachable "b" "c"+ ]+ results <- execAnalysis analysis inputs+ liftIO $ results `shouldBe` Results reachables inputs++ it "supports semigroupal composition" $ do+ withSouffle Path $ \h -> do+ let analysis = pathAnalysis h+ analysis' = analysis <> analysis+ rs <- execAnalysis analysis' [Edge "a" "b", Edge "b" "c"]+ let results = [ Reachable "a" "b"+ , Reachable "a" "c"+ , Reachable "b" "c"+ ]+ results' = mconcat $ replicate 2 results+ liftIO $ rs `shouldBe` results'++ it "supports mempty" $ do+ withSouffle Path $ \_ -> do+ let analysis :: Analysis Souffle.SouffleM [Edge] [Reachable]+ analysis = mempty+ rs <- execAnalysis analysis [Edge "a" "b", Edge "b" "c"]+ liftIO $ rs `shouldBe` []++ it "supports converting an analysis to a monadic function" $ do+ withSouffle Path $ \h -> do+ let analysis = pathAnalysis h+ rs <- execAnalysis analysis [Edge "a" "b", Edge "b" "c"]+ let results = [ Reachable "a" "b"+ , Reachable "a" "c"+ , Reachable "b" "c"+ ]+ liftIO $ rs `shouldBe` results++ describe "analysis used as a category" $ parallel $ do+ it "supports 'id'" $ do+ withSouffle Path $ \_ -> do+ let analysis :: Analysis Souffle.SouffleM [Edge] [Edge]+ analysis = id+ edges' <- execAnalysis analysis edges+ liftIO $ edges' `shouldBe` edges++ it "supports sequential composition using (.)" $ do+ withSouffle Path $ \h -> do+ let reachableToFlippedEdge (Reachable a b) = Edge b a+ analysis1 = pathAnalysis h+ analysis2 = lmap (map reachableToFlippedEdge) $ pathAnalysis h+ rs <- execAnalysis (analysis2 . analysis1) [Edge "a" "b", Edge "b" "c"]+ let results = [ Reachable "a" "a"+ , Reachable "a" "b"+ , Reachable "a" "c"+ , Reachable "b" "a"+ , Reachable "b" "b"+ , Reachable "b" "c"+ , Reachable "c" "a"+ , Reachable "c" "b"+ , Reachable "c" "c"+ ]+ liftIO $ rs `shouldBe` results++ describe "analysis used as an arrow" $ parallel $ do+ it "supports 'arr'" $ do+ withSouffle Path $ \_ -> do+ let analysis :: Analysis Souffle.SouffleM Int Int+ analysis = arr (+1)+ result1 <- execAnalysis analysis 41+ result2 <- execAnalysis (arr id) 41+ liftIO $ result1 `shouldBe` 42+ liftIO $ result2 `shouldBe` 41++ it "supports 'first'" $ do+ withSouffle Path $ \_ -> do+ let analysis :: Analysis Souffle.SouffleM (Int, Bool) (Int, Bool)+ analysis = first (arr (+1))+ input = (41, True)+ result <- execAnalysis analysis input+ liftIO $ result `shouldBe` (42, True)++ it "supports 'second'" $ do+ withSouffle Path $ \_ -> do+ let analysis :: Analysis Souffle.SouffleM (Bool, Int) (Bool, Int)+ analysis = second (arr (+1))+ input = (True, 41)+ result <- execAnalysis analysis input+ liftIO $ result `shouldBe` (True, 42)++ it "supports (***)" $ do+ withSouffle Path $ \_ -> do+ let analysis :: Analysis Souffle.SouffleM (Bool, Int) (Bool, Int)+ analysis = arr not *** arr (+1)+ input = (True, 41)+ result <- execAnalysis analysis input+ liftIO $ result `shouldBe` (False, 42)++ it "supports (&&&)" $ do+ withSouffle Path $ \_ -> do+ let analysis :: Analysis Souffle.SouffleM Int (Bool, Int)+ analysis = arr (== 1000) &&& arr (+1)+ input = 41+ result <- execAnalysis analysis input+ liftIO $ result `shouldBe` (False, 42)++ it "supports arrow notation" $ do+ withSouffle Path $ \h -> do+ liftIO $ withSouffle RoundTrip $ \h' -> do+ let arrowAnalysis = proc es -> do+ rs <- pathAnalysis h -< es+ strs <- roundTripAnalysis h' -< rs+ returnA -< strs+ result <- execAnalysis arrowAnalysis edges+ liftIO $ result `shouldBe` [ StringFact "a"+ , StringFact "b"+ , StringFact "d"+ ]++ it "supports case expressions in arrow notation" $ do+ withSouffle Path $ \h -> do+ let analysis = proc es -> do+ rs <- pathAnalysis h -< es+ case rs of+ [] -> returnA -< []+ rs' -> returnA -< take 2 rs'+ result <- execAnalysis analysis edges+ let expected = [ Reachable "a" "b", Reachable "a" "c" ]+ liftIO $ result `shouldBe` expected+
tests/fixtures/edge_cases.cpp view
@@ -318,14 +318,6 @@ class Sf_edge_cases : public SouffleProgram { private:-static inline bool regex_wrapper(const std::string& pattern, const std::string& text) {- bool result = false; - try { result = std::regex_match(text, std::regex(pattern)); } catch(...) { - std::cerr << "warning: wrong pattern provided for match(\"" << pattern << "\",\"" << text << "\").\n";-}- return result;-}-private: static inline std::string substr_wrapper(const std::string& str, std::size_t idx, std::size_t len) { std::string result; try { result = str.substr(idx,len); } catch(...) { @@ -342,30 +334,30 @@ R"_(∀)_", R"_(∀∀)_", };// -- initialize record table ---RecordTable recordTable;+SpecializedRecordTable<0> recordTable{}; // -- Table: empty_strings Own<t_btree_iii__0_1_2__111> rel_1_empty_strings = mk<t_btree_iii__0_1_2__111>(); souffle::RelationWrapper<t_btree_iii__0_1_2__111> wrapper_rel_1_empty_strings; // -- Table: long_strings Own<t_btree_i__0__1> rel_2_long_strings = mk<t_btree_i__0__1>(); souffle::RelationWrapper<t_btree_i__0__1> wrapper_rel_2_long_strings;-// -- Table: unicode-Own<t_btree_i__0__1> rel_3_unicode = mk<t_btree_i__0__1>();-souffle::RelationWrapper<t_btree_i__0__1> wrapper_rel_3_unicode; // -- Table: no_strings-Own<t_btree_uif__0_1_2__111> rel_4_no_strings = mk<t_btree_uif__0_1_2__111>();-souffle::RelationWrapper<t_btree_uif__0_1_2__111> wrapper_rel_4_no_strings;+Own<t_btree_uif__0_1_2__111> rel_3_no_strings = mk<t_btree_uif__0_1_2__111>();+souffle::RelationWrapper<t_btree_uif__0_1_2__111> wrapper_rel_3_no_strings;+// -- Table: unicode+Own<t_btree_i__0__1> rel_4_unicode = mk<t_btree_i__0__1>();+souffle::RelationWrapper<t_btree_i__0__1> wrapper_rel_4_unicode; public: Sf_edge_cases() : wrapper_rel_1_empty_strings(0, *rel_1_empty_strings, *this, "empty_strings", std::array<const char *,3>{{"s:symbol","s:symbol","i:number"}}, std::array<const char *,3>{{"s","s2","n"}}, 0) , wrapper_rel_2_long_strings(1, *rel_2_long_strings, *this, "long_strings", std::array<const char *,1>{{"s:symbol"}}, std::array<const char *,1>{{"s"}}, 0)-, wrapper_rel_3_unicode(2, *rel_3_unicode, *this, "unicode", std::array<const char *,1>{{"s:symbol"}}, std::array<const char *,1>{{"s"}}, 0)-, wrapper_rel_4_no_strings(3, *rel_4_no_strings, *this, "no_strings", std::array<const char *,3>{{"u:unsigned","i:number","f:float"}}, std::array<const char *,3>{{"u","n","f"}}, 0)+, wrapper_rel_3_no_strings(2, *rel_3_no_strings, *this, "no_strings", std::array<const char *,3>{{"u:unsigned","i:number","f:float"}}, std::array<const char *,3>{{"u","n","f"}}, 0)+, wrapper_rel_4_unicode(3, *rel_4_unicode, *this, "unicode", std::array<const char *,1>{{"s:symbol"}}, std::array<const char *,1>{{"s"}}, 0) { addRelation("empty_strings", wrapper_rel_1_empty_strings, true, true); addRelation("long_strings", wrapper_rel_2_long_strings, true, true);-addRelation("unicode", wrapper_rel_3_unicode, true, true);-addRelation("no_strings", wrapper_rel_4_no_strings, true, true);+addRelation("no_strings", wrapper_rel_3_no_strings, true, true);+addRelation("unicode", wrapper_rel_4_unicode, true, true); } ~Sf_edge_cases() { }@@ -376,14 +368,15 @@ SignalHandler* signalHandler {SignalHandler::instance()}; std::atomic<RamDomain> ctr {}; std::atomic<std::size_t> iter {};-bool performIO = false; -void runFunction(std::string inputDirectoryArg = "",- std::string outputDirectoryArg = "",- bool performIOArg = false) {+void runFunction(std::string inputDirectoryArg,+ std::string outputDirectoryArg,+ bool performIOArg,+ bool pruneImdtRelsArg) { this->inputDirectory = std::move(inputDirectoryArg); this->outputDirectory = std::move(outputDirectoryArg); this->performIO = performIOArg;+ this->pruneImdtRels = pruneImdtRelsArg; // set default threads (in embedded mode) // if this is not set, and omp is used, the default omp setting of number of cores is used.@@ -414,9 +407,9 @@ signalHandler->reset(); } public:-void run() override { runFunction("", "", false); }+void run() override { runFunction("", "", false, false); } public:-void runAll(std::string inputDirectoryArg = "", std::string outputDirectoryArg = "") override { runFunction(inputDirectoryArg, outputDirectoryArg, true);+void runAll(std::string inputDirectoryArg = "", std::string outputDirectoryArg = "", bool performIOArg=true, bool pruneImdtRelsArg=true) override { runFunction(inputDirectoryArg, outputDirectoryArg, performIOArg, pruneImdtRelsArg); } public: void printAll(std::string outputDirectoryArg = "") override {@@ -428,13 +421,13 @@ if (!outputDirectoryArg.empty()) {directiveMap["output-dir"] = outputDirectoryArg;} IOSystem::getInstance().getWriter(directiveMap, symTable, recordTable)->writeAll(*rel_2_long_strings); } catch (std::exception& e) {std::cerr << e.what();exit(1);}-try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","s"},{"auxArity","0"},{"name","unicode"},{"operation","output"},{"output-dir","."},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"s\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"s:symbol\"]}}"}});+try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","u\tn\tf"},{"auxArity","0"},{"name","no_strings"},{"operation","output"},{"output-dir","."},{"params","{\"records\": {}, \"relation\": {\"arity\": 3, \"params\": [\"u\", \"n\", \"f\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 3, \"types\": [\"u:unsigned\", \"i:number\", \"f:float\"]}}"}}); if (!outputDirectoryArg.empty()) {directiveMap["output-dir"] = outputDirectoryArg;}-IOSystem::getInstance().getWriter(directiveMap, symTable, recordTable)->writeAll(*rel_3_unicode);+IOSystem::getInstance().getWriter(directiveMap, symTable, recordTable)->writeAll(*rel_3_no_strings); } catch (std::exception& e) {std::cerr << e.what();exit(1);}-try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","u\tn\tf"},{"auxArity","0"},{"name","no_strings"},{"operation","output"},{"output-dir","."},{"params","{\"records\": {}, \"relation\": {\"arity\": 3, \"params\": [\"u\", \"n\", \"f\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 3, \"types\": [\"u:unsigned\", \"i:number\", \"f:float\"]}}"}});+try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","s"},{"auxArity","0"},{"name","unicode"},{"operation","output"},{"output-dir","."},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"s\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"s:symbol\"]}}"}}); if (!outputDirectoryArg.empty()) {directiveMap["output-dir"] = outputDirectoryArg;}-IOSystem::getInstance().getWriter(directiveMap, symTable, recordTable)->writeAll(*rel_4_no_strings);+IOSystem::getInstance().getWriter(directiveMap, symTable, recordTable)->writeAll(*rel_4_unicode); } catch (std::exception& e) {std::cerr << e.what();exit(1);} } public:@@ -442,19 +435,19 @@ try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","s"},{"auxArity","0"},{"fact-dir","."},{"name","long_strings"},{"operation","input"},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"s\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"s:symbol\"]}}"}}); if (!inputDirectoryArg.empty()) {directiveMap["fact-dir"] = inputDirectoryArg;} IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_2_long_strings);-} catch (std::exception& e) {std::cerr << "Error loading data: " << e.what() << '\n';}+} catch (std::exception& e) {std::cerr << "Error loading long_strings data: " << e.what() << '\n';}+try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","u\tn\tf"},{"auxArity","0"},{"fact-dir","."},{"name","no_strings"},{"operation","input"},{"params","{\"records\": {}, \"relation\": {\"arity\": 3, \"params\": [\"u\", \"n\", \"f\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 3, \"types\": [\"u:unsigned\", \"i:number\", \"f:float\"]}}"}});+if (!inputDirectoryArg.empty()) {directiveMap["fact-dir"] = inputDirectoryArg;}+IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_3_no_strings);+} catch (std::exception& e) {std::cerr << "Error loading no_strings data: " << e.what() << '\n';} try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","s\ts2\tn"},{"auxArity","0"},{"fact-dir","."},{"name","empty_strings"},{"operation","input"},{"params","{\"records\": {}, \"relation\": {\"arity\": 3, \"params\": [\"s\", \"s2\", \"n\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 3, \"types\": [\"s:symbol\", \"s:symbol\", \"i:number\"]}}"}}); if (!inputDirectoryArg.empty()) {directiveMap["fact-dir"] = inputDirectoryArg;} IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_1_empty_strings);-} catch (std::exception& e) {std::cerr << "Error loading data: " << e.what() << '\n';}+} catch (std::exception& e) {std::cerr << "Error loading empty_strings data: " << e.what() << '\n';} try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","s"},{"auxArity","0"},{"fact-dir","."},{"name","unicode"},{"operation","input"},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"s\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"s:symbol\"]}}"}}); if (!inputDirectoryArg.empty()) {directiveMap["fact-dir"] = inputDirectoryArg;}-IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_3_unicode);-} catch (std::exception& e) {std::cerr << "Error loading data: " << e.what() << '\n';}-try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","u\tn\tf"},{"auxArity","0"},{"fact-dir","."},{"name","no_strings"},{"operation","input"},{"params","{\"records\": {}, \"relation\": {\"arity\": 3, \"params\": [\"u\", \"n\", \"f\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 3, \"types\": [\"u:unsigned\", \"i:number\", \"f:float\"]}}"}});-if (!inputDirectoryArg.empty()) {directiveMap["fact-dir"] = inputDirectoryArg;}-IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_4_no_strings);-} catch (std::exception& e) {std::cerr << "Error loading data: " << e.what() << '\n';}+IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_4_unicode);+} catch (std::exception& e) {std::cerr << "Error loading unicode data: " << e.what() << '\n';} } public: void dumpInputs() override {@@ -466,6 +459,12 @@ } catch (std::exception& e) {std::cerr << e.what();exit(1);} try {std::map<std::string, std::string> rwOperation; rwOperation["IO"] = "stdout";+rwOperation["name"] = "no_strings";+rwOperation["types"] = "{\"relation\": {\"arity\": 3, \"auxArity\": 0, \"types\": [\"u:unsigned\", \"i:number\", \"f:float\"]}}";+IOSystem::getInstance().getWriter(rwOperation, symTable, recordTable)->writeAll(*rel_3_no_strings);+} catch (std::exception& e) {std::cerr << e.what();exit(1);}+try {std::map<std::string, std::string> rwOperation;+rwOperation["IO"] = "stdout"; rwOperation["name"] = "empty_strings"; rwOperation["types"] = "{\"relation\": {\"arity\": 3, \"auxArity\": 0, \"types\": [\"s:symbol\", \"s:symbol\", \"i:number\"]}}"; IOSystem::getInstance().getWriter(rwOperation, symTable, recordTable)->writeAll(*rel_1_empty_strings);@@ -474,13 +473,7 @@ rwOperation["IO"] = "stdout"; rwOperation["name"] = "unicode"; rwOperation["types"] = "{\"relation\": {\"arity\": 1, \"auxArity\": 0, \"types\": [\"s:symbol\"]}}";-IOSystem::getInstance().getWriter(rwOperation, symTable, recordTable)->writeAll(*rel_3_unicode);-} catch (std::exception& e) {std::cerr << e.what();exit(1);}-try {std::map<std::string, std::string> rwOperation;-rwOperation["IO"] = "stdout";-rwOperation["name"] = "no_strings";-rwOperation["types"] = "{\"relation\": {\"arity\": 3, \"auxArity\": 0, \"types\": [\"u:unsigned\", \"i:number\", \"f:float\"]}}";-IOSystem::getInstance().getWriter(rwOperation, symTable, recordTable)->writeAll(*rel_4_no_strings);+IOSystem::getInstance().getWriter(rwOperation, symTable, recordTable)->writeAll(*rel_4_unicode); } catch (std::exception& e) {std::cerr << e.what();exit(1);} } public:@@ -499,15 +492,15 @@ } catch (std::exception& e) {std::cerr << e.what();exit(1);} try {std::map<std::string, std::string> rwOperation; rwOperation["IO"] = "stdout";-rwOperation["name"] = "unicode";-rwOperation["types"] = "{\"relation\": {\"arity\": 1, \"auxArity\": 0, \"types\": [\"s:symbol\"]}}";-IOSystem::getInstance().getWriter(rwOperation, symTable, recordTable)->writeAll(*rel_3_unicode);+rwOperation["name"] = "no_strings";+rwOperation["types"] = "{\"relation\": {\"arity\": 3, \"auxArity\": 0, \"types\": [\"u:unsigned\", \"i:number\", \"f:float\"]}}";+IOSystem::getInstance().getWriter(rwOperation, symTable, recordTable)->writeAll(*rel_3_no_strings); } catch (std::exception& e) {std::cerr << e.what();exit(1);} try {std::map<std::string, std::string> rwOperation; rwOperation["IO"] = "stdout";-rwOperation["name"] = "no_strings";-rwOperation["types"] = "{\"relation\": {\"arity\": 3, \"auxArity\": 0, \"types\": [\"u:unsigned\", \"i:number\", \"f:float\"]}}";-IOSystem::getInstance().getWriter(rwOperation, symTable, recordTable)->writeAll(*rel_4_no_strings);+rwOperation["name"] = "unicode";+rwOperation["types"] = "{\"relation\": {\"arity\": 1, \"auxArity\": 0, \"types\": [\"s:symbol\"]}}";+IOSystem::getInstance().getWriter(rwOperation, symTable, recordTable)->writeAll(*rel_4_unicode); } catch (std::exception& e) {std::cerr << e.what();exit(1);} } public:@@ -545,7 +538,7 @@ try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","s\ts2\tn"},{"auxArity","0"},{"fact-dir","."},{"name","empty_strings"},{"operation","input"},{"params","{\"records\": {}, \"relation\": {\"arity\": 3, \"params\": [\"s\", \"s2\", \"n\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 3, \"types\": [\"s:symbol\", \"s:symbol\", \"i:number\"]}}"}}); if (!inputDirectory.empty()) {directiveMap["fact-dir"] = inputDirectory;} IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_1_empty_strings);-} catch (std::exception& e) {std::cerr << "Error loading data: " << e.what() << '\n';}+} catch (std::exception& e) {std::cerr << "Error loading empty_strings data: " << e.what() << '\n';} } signalHandler->setMsg(R"_(empty_strings("","",42). in file /home/luc/personal/souffle-haskell/tests/fixtures/edge_cases.dl [20:1-20:27])_");@@ -586,7 +579,7 @@ try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","s"},{"auxArity","0"},{"fact-dir","."},{"name","long_strings"},{"operation","input"},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"s\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"s:symbol\"]}}"}}); if (!inputDirectory.empty()) {directiveMap["fact-dir"] = inputDirectory;} IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_2_long_strings);-} catch (std::exception& e) {std::cerr << "Error loading data: " << e.what() << '\n';}+} catch (std::exception& e) {std::cerr << "Error loading long_strings data: " << e.what() << '\n';} } signalHandler->setMsg(R"_(long_strings("long_string_from_DL:...............................................................................................................................................................................................................................................................................................end"). in file /home/luc/personal/souffle-haskell/tests/fixtures/edge_cases.dl [25:1-25:328])_");@@ -610,29 +603,29 @@ #endif // _MSC_VER void subroutine_2(const std::vector<RamDomain>& args, std::vector<RamDomain>& ret) { if (performIO) {-try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","s"},{"auxArity","0"},{"fact-dir","."},{"name","unicode"},{"operation","input"},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"s\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"s:symbol\"]}}"}});+try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","u\tn\tf"},{"auxArity","0"},{"fact-dir","."},{"name","no_strings"},{"operation","input"},{"params","{\"records\": {}, \"relation\": {\"arity\": 3, \"params\": [\"u\", \"n\", \"f\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 3, \"types\": [\"u:unsigned\", \"i:number\", \"f:float\"]}}"}}); if (!inputDirectory.empty()) {directiveMap["fact-dir"] = inputDirectory;}-IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_3_unicode);-} catch (std::exception& e) {std::cerr << "Error loading data: " << e.what() << '\n';}+IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_3_no_strings);+} catch (std::exception& e) {std::cerr << "Error loading no_strings data: " << e.what() << '\n';} }-signalHandler->setMsg(R"_(unicode("∀").-in file /home/luc/personal/souffle-haskell/tests/fixtures/edge_cases.dl [30:1-30:16])_");+signalHandler->setMsg(R"_(no_strings(42,-100,1.5).+in file /home/luc/personal/souffle-haskell/tests/fixtures/edge_cases.dl [33:1-33:27])_"); [&](){-CREATE_OP_CONTEXT(rel_3_unicode_op_ctxt,rel_3_unicode->createContext());-Tuple<RamDomain,1> tuple{{ramBitCast(RamSigned(3))}};-rel_3_unicode->insert(tuple,READ_OP_CONTEXT(rel_3_unicode_op_ctxt));+CREATE_OP_CONTEXT(rel_3_no_strings_op_ctxt,rel_3_no_strings->createContext());+Tuple<RamDomain,3> tuple{{ramBitCast(RamUnsigned(42)),ramBitCast(RamSigned(-100)),ramBitCast(RamFloat(1.5))}};+rel_3_no_strings->insert(tuple,READ_OP_CONTEXT(rel_3_no_strings_op_ctxt)); }-();signalHandler->setMsg(R"_(unicode("∀∀").-in file /home/luc/personal/souffle-haskell/tests/fixtures/edge_cases.dl [31:1-31:19])_");+();signalHandler->setMsg(R"_(no_strings(123,-456,3.14).+in file /home/luc/personal/souffle-haskell/tests/fixtures/edge_cases.dl [34:1-34:29])_"); [&](){-CREATE_OP_CONTEXT(rel_3_unicode_op_ctxt,rel_3_unicode->createContext());-Tuple<RamDomain,1> tuple{{ramBitCast(RamSigned(4))}};-rel_3_unicode->insert(tuple,READ_OP_CONTEXT(rel_3_unicode_op_ctxt));+CREATE_OP_CONTEXT(rel_3_no_strings_op_ctxt,rel_3_no_strings->createContext());+Tuple<RamDomain,3> tuple{{ramBitCast(RamUnsigned(123)),ramBitCast(RamSigned(-456)),ramBitCast(RamFloat(3.1400001))}};+rel_3_no_strings->insert(tuple,READ_OP_CONTEXT(rel_3_no_strings_op_ctxt)); } ();if (performIO) {-try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","s"},{"auxArity","0"},{"name","unicode"},{"operation","output"},{"output-dir","."},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"s\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"s:symbol\"]}}"}});+try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","u\tn\tf"},{"auxArity","0"},{"name","no_strings"},{"operation","output"},{"output-dir","."},{"params","{\"records\": {}, \"relation\": {\"arity\": 3, \"params\": [\"u\", \"n\", \"f\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 3, \"types\": [\"u:unsigned\", \"i:number\", \"f:float\"]}}"}}); if (!outputDirectory.empty()) {directiveMap["output-dir"] = outputDirectory;}-IOSystem::getInstance().getWriter(directiveMap, symTable, recordTable)->writeAll(*rel_3_unicode);+IOSystem::getInstance().getWriter(directiveMap, symTable, recordTable)->writeAll(*rel_3_no_strings); } catch (std::exception& e) {std::cerr << e.what();exit(1);} } }@@ -644,29 +637,29 @@ #endif // _MSC_VER void subroutine_3(const std::vector<RamDomain>& args, std::vector<RamDomain>& ret) { if (performIO) {-try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","u\tn\tf"},{"auxArity","0"},{"fact-dir","."},{"name","no_strings"},{"operation","input"},{"params","{\"records\": {}, \"relation\": {\"arity\": 3, \"params\": [\"u\", \"n\", \"f\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 3, \"types\": [\"u:unsigned\", \"i:number\", \"f:float\"]}}"}});+try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","s"},{"auxArity","0"},{"fact-dir","."},{"name","unicode"},{"operation","input"},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"s\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"s:symbol\"]}}"}}); if (!inputDirectory.empty()) {directiveMap["fact-dir"] = inputDirectory;}-IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_4_no_strings);-} catch (std::exception& e) {std::cerr << "Error loading data: " << e.what() << '\n';}+IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_4_unicode);+} catch (std::exception& e) {std::cerr << "Error loading unicode data: " << e.what() << '\n';} }-signalHandler->setMsg(R"_(no_strings(42,-100,1.5).-in file /home/luc/personal/souffle-haskell/tests/fixtures/edge_cases.dl [33:1-33:27])_");+signalHandler->setMsg(R"_(unicode("∀").+in file /home/luc/personal/souffle-haskell/tests/fixtures/edge_cases.dl [30:1-30:16])_"); [&](){-CREATE_OP_CONTEXT(rel_4_no_strings_op_ctxt,rel_4_no_strings->createContext());-Tuple<RamDomain,3> tuple{{ramBitCast(RamUnsigned(42)),ramBitCast(RamSigned(-100)),ramBitCast(RamFloat(1.5))}};-rel_4_no_strings->insert(tuple,READ_OP_CONTEXT(rel_4_no_strings_op_ctxt));+CREATE_OP_CONTEXT(rel_4_unicode_op_ctxt,rel_4_unicode->createContext());+Tuple<RamDomain,1> tuple{{ramBitCast(RamSigned(3))}};+rel_4_unicode->insert(tuple,READ_OP_CONTEXT(rel_4_unicode_op_ctxt)); }-();signalHandler->setMsg(R"_(no_strings(123,-456,3.14).-in file /home/luc/personal/souffle-haskell/tests/fixtures/edge_cases.dl [34:1-34:29])_");+();signalHandler->setMsg(R"_(unicode("∀∀").+in file /home/luc/personal/souffle-haskell/tests/fixtures/edge_cases.dl [31:1-31:19])_"); [&](){-CREATE_OP_CONTEXT(rel_4_no_strings_op_ctxt,rel_4_no_strings->createContext());-Tuple<RamDomain,3> tuple{{ramBitCast(RamUnsigned(123)),ramBitCast(RamSigned(-456)),ramBitCast(RamFloat(3.1400001))}};-rel_4_no_strings->insert(tuple,READ_OP_CONTEXT(rel_4_no_strings_op_ctxt));+CREATE_OP_CONTEXT(rel_4_unicode_op_ctxt,rel_4_unicode->createContext());+Tuple<RamDomain,1> tuple{{ramBitCast(RamSigned(4))}};+rel_4_unicode->insert(tuple,READ_OP_CONTEXT(rel_4_unicode_op_ctxt)); } ();if (performIO) {-try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","u\tn\tf"},{"auxArity","0"},{"name","no_strings"},{"operation","output"},{"output-dir","."},{"params","{\"records\": {}, \"relation\": {\"arity\": 3, \"params\": [\"u\", \"n\", \"f\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 3, \"types\": [\"u:unsigned\", \"i:number\", \"f:float\"]}}"}});+try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","s"},{"auxArity","0"},{"name","unicode"},{"operation","output"},{"output-dir","."},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"s\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"s:symbol\"]}}"}}); if (!outputDirectory.empty()) {directiveMap["output-dir"] = outputDirectory;}-IOSystem::getInstance().getWriter(directiveMap, symTable, recordTable)->writeAll(*rel_4_no_strings);+IOSystem::getInstance().getWriter(directiveMap, symTable, recordTable)->writeAll(*rel_4_unicode); } catch (std::exception& e) {std::cerr << e.what();exit(1);} } }
tests/fixtures/path.cpp view
@@ -227,14 +227,6 @@ class Sf_path : public SouffleProgram { private:-static inline bool regex_wrapper(const std::string& pattern, const std::string& text) {- bool result = false; - try { result = std::regex_match(text, std::regex(pattern)); } catch(...) { - std::cerr << "warning: wrong pattern provided for match(\"" << pattern << "\",\"" << text << "\").\n";-}- return result;-}-private: static inline std::string substr_wrapper(const std::string& str, std::size_t idx, std::size_t len) { std::string result; try { result = str.substr(idx,len); } catch(...) { @@ -249,7 +241,7 @@ R"_(b)_", R"_(c)_", };// -- initialize record table ---RecordTable recordTable;+SpecializedRecordTable<0> recordTable{}; // -- Table: edge Own<t_btree_ii__0_1__11> rel_1_edge = mk<t_btree_ii__0_1__11>(); souffle::RelationWrapper<t_btree_ii__0_1__11> wrapper_rel_1_edge;@@ -277,14 +269,15 @@ SignalHandler* signalHandler {SignalHandler::instance()}; std::atomic<RamDomain> ctr {}; std::atomic<std::size_t> iter {};-bool performIO = false; -void runFunction(std::string inputDirectoryArg = "",- std::string outputDirectoryArg = "",- bool performIOArg = false) {+void runFunction(std::string inputDirectoryArg,+ std::string outputDirectoryArg,+ bool performIOArg,+ bool pruneImdtRelsArg) { this->inputDirectory = std::move(inputDirectoryArg); this->outputDirectory = std::move(outputDirectoryArg); this->performIO = performIOArg;+ this->pruneImdtRels = pruneImdtRelsArg; // set default threads (in embedded mode) // if this is not set, and omp is used, the default omp setting of number of cores is used.@@ -307,27 +300,27 @@ signalHandler->reset(); } public:-void run() override { runFunction("", "", false); }+void run() override { runFunction("", "", false, false); } public:-void runAll(std::string inputDirectoryArg = "", std::string outputDirectoryArg = "") override { runFunction(inputDirectoryArg, outputDirectoryArg, true);+void runAll(std::string inputDirectoryArg = "", std::string outputDirectoryArg = "", bool performIOArg=true, bool pruneImdtRelsArg=true) override { runFunction(inputDirectoryArg, outputDirectoryArg, performIOArg, pruneImdtRelsArg); } public: void printAll(std::string outputDirectoryArg = "") override {-try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","n\tm"},{"auxArity","0"},{"name","edge"},{"operation","output"},{"output-dir","."},{"params","{\"records\": {}, \"relation\": {\"arity\": 2, \"params\": [\"n\", \"m\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 2, \"types\": [\"s:symbol\", \"s:symbol\"]}}"}});-if (!outputDirectoryArg.empty()) {directiveMap["output-dir"] = outputDirectoryArg;}-IOSystem::getInstance().getWriter(directiveMap, symTable, recordTable)->writeAll(*rel_1_edge);-} catch (std::exception& e) {std::cerr << e.what();exit(1);} try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","n\tm"},{"auxArity","0"},{"name","reachable"},{"operation","output"},{"output-dir","."},{"params","{\"records\": {}, \"relation\": {\"arity\": 2, \"params\": [\"n\", \"m\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 2, \"types\": [\"s:symbol\", \"s:symbol\"]}}"}}); if (!outputDirectoryArg.empty()) {directiveMap["output-dir"] = outputDirectoryArg;} IOSystem::getInstance().getWriter(directiveMap, symTable, recordTable)->writeAll(*rel_2_reachable); } catch (std::exception& e) {std::cerr << e.what();exit(1);}+try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","n\tm"},{"auxArity","0"},{"name","edge"},{"operation","output"},{"output-dir","."},{"params","{\"records\": {}, \"relation\": {\"arity\": 2, \"params\": [\"n\", \"m\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 2, \"types\": [\"s:symbol\", \"s:symbol\"]}}"}});+if (!outputDirectoryArg.empty()) {directiveMap["output-dir"] = outputDirectoryArg;}+IOSystem::getInstance().getWriter(directiveMap, symTable, recordTable)->writeAll(*rel_1_edge);+} catch (std::exception& e) {std::cerr << e.what();exit(1);} } public: void loadAll(std::string inputDirectoryArg = "") override { try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","n\tm"},{"auxArity","0"},{"fact-dir","."},{"name","edge"},{"operation","input"},{"params","{\"records\": {}, \"relation\": {\"arity\": 2, \"params\": [\"n\", \"m\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 2, \"types\": [\"s:symbol\", \"s:symbol\"]}}"}}); if (!inputDirectoryArg.empty()) {directiveMap["fact-dir"] = inputDirectoryArg;} IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_1_edge);-} catch (std::exception& e) {std::cerr << "Error loading data: " << e.what() << '\n';}+} catch (std::exception& e) {std::cerr << "Error loading edge data: " << e.what() << '\n';} } public: void dumpInputs() override {@@ -342,15 +335,15 @@ void dumpOutputs() override { try {std::map<std::string, std::string> rwOperation; rwOperation["IO"] = "stdout";-rwOperation["name"] = "edge";+rwOperation["name"] = "reachable"; rwOperation["types"] = "{\"relation\": {\"arity\": 2, \"auxArity\": 0, \"types\": [\"s:symbol\", \"s:symbol\"]}}";-IOSystem::getInstance().getWriter(rwOperation, symTable, recordTable)->writeAll(*rel_1_edge);+IOSystem::getInstance().getWriter(rwOperation, symTable, recordTable)->writeAll(*rel_2_reachable); } catch (std::exception& e) {std::cerr << e.what();exit(1);} try {std::map<std::string, std::string> rwOperation; rwOperation["IO"] = "stdout";-rwOperation["name"] = "reachable";+rwOperation["name"] = "edge"; rwOperation["types"] = "{\"relation\": {\"arity\": 2, \"auxArity\": 0, \"types\": [\"s:symbol\", \"s:symbol\"]}}";-IOSystem::getInstance().getWriter(rwOperation, symTable, recordTable)->writeAll(*rel_2_reachable);+IOSystem::getInstance().getWriter(rwOperation, symTable, recordTable)->writeAll(*rel_1_edge); } catch (std::exception& e) {std::cerr << e.what();exit(1);} } public:@@ -382,7 +375,7 @@ try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","n\tm"},{"auxArity","0"},{"fact-dir","."},{"name","edge"},{"operation","input"},{"params","{\"records\": {}, \"relation\": {\"arity\": 2, \"params\": [\"n\", \"m\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 2, \"types\": [\"s:symbol\", \"s:symbol\"]}}"}}); if (!inputDirectory.empty()) {directiveMap["fact-dir"] = inputDirectory;} IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_1_edge);-} catch (std::exception& e) {std::cerr << "Error loading data: " << e.what() << '\n';}+} catch (std::exception& e) {std::cerr << "Error loading edge data: " << e.what() << '\n';} } signalHandler->setMsg(R"_(edge("a","b"). in file /home/luc/personal/souffle-haskell/tests/fixtures/path.dl [11:1-11:16])_");@@ -426,8 +419,8 @@ } ();} [&](){-CREATE_OP_CONTEXT(rel_3_delta_reachable_op_ctxt,rel_3_delta_reachable->createContext()); CREATE_OP_CONTEXT(rel_2_reachable_op_ctxt,rel_2_reachable->createContext());+CREATE_OP_CONTEXT(rel_3_delta_reachable_op_ctxt,rel_3_delta_reachable->createContext()); for(const auto& env0 : *rel_2_reachable) { Tuple<RamDomain,2> tuple{{ramBitCast(env0[0]),ramBitCast(env0[1])}}; rel_3_delta_reachable->insert(tuple,READ_OP_CONTEXT(rel_3_delta_reachable_op_ctxt));@@ -441,10 +434,10 @@ in file /home/luc/personal/souffle-haskell/tests/fixtures/path.dl [15:1-15:48])_"); if(!(rel_1_edge->empty()) && !(rel_3_delta_reachable->empty())) { [&](){-CREATE_OP_CONTEXT(rel_3_delta_reachable_op_ctxt,rel_3_delta_reachable->createContext()); CREATE_OP_CONTEXT(rel_2_reachable_op_ctxt,rel_2_reachable->createContext());-CREATE_OP_CONTEXT(rel_1_edge_op_ctxt,rel_1_edge->createContext()); CREATE_OP_CONTEXT(rel_4_new_reachable_op_ctxt,rel_4_new_reachable->createContext());+CREATE_OP_CONTEXT(rel_1_edge_op_ctxt,rel_1_edge->createContext());+CREATE_OP_CONTEXT(rel_3_delta_reachable_op_ctxt,rel_3_delta_reachable->createContext()); for(const auto& env0 : *rel_1_edge) { auto range = rel_3_delta_reachable->lowerUpperRange_10(Tuple<RamDomain,2>{{ramBitCast(env0[1]), ramBitCast<RamDomain>(MIN_RAM_SIGNED)}},Tuple<RamDomain,2>{{ramBitCast(env0[1]), ramBitCast<RamDomain>(MAX_RAM_SIGNED)}},READ_OP_CONTEXT(rel_3_delta_reachable_op_ctxt)); for(const auto& env1 : range) {@@ -478,8 +471,8 @@ IOSystem::getInstance().getWriter(directiveMap, symTable, recordTable)->writeAll(*rel_2_reachable); } catch (std::exception& e) {std::cerr << e.what();exit(1);} }-if (performIO) rel_2_reachable->purge();-if (performIO) rel_1_edge->purge();+if (pruneImdtRels) rel_1_edge->purge();+if (pruneImdtRels) rel_2_reachable->purge(); } #ifdef _MSC_VER #pragma warning(default: 4100)
tests/fixtures/round_trip.cpp view
@@ -6,18 +6,18 @@ namespace souffle { static const RamDomain RAM_BIT_SHIFT_MASK = RAM_DOMAIN_SIZE - 1;-struct t_btree_i__0__1 {+struct t_btree_f__0__1 { static constexpr Relation::arity_type Arity = 1; using t_tuple = Tuple<RamDomain, 1>; struct t_comparator_0{ int operator()(const t_tuple& a, const t_tuple& b) const {- return (ramBitCast<RamSigned>(a[0]) < ramBitCast<RamSigned>(b[0])) ? -1 : (ramBitCast<RamSigned>(a[0]) > ramBitCast<RamSigned>(b[0])) ? 1 :(0);+ return (ramBitCast<RamFloat>(a[0]) < ramBitCast<RamFloat>(b[0])) ? -1 : (ramBitCast<RamFloat>(a[0]) > ramBitCast<RamFloat>(b[0])) ? 1 :(0); } bool less(const t_tuple& a, const t_tuple& b) const {- return (ramBitCast<RamSigned>(a[0]) < ramBitCast<RamSigned>(b[0]));+ return (ramBitCast<RamFloat>(a[0]) < ramBitCast<RamFloat>(b[0])); } bool equal(const t_tuple& a, const t_tuple& b) const {-return (ramBitCast<RamSigned>(a[0]) == ramBitCast<RamSigned>(b[0]));+return (ramBitCast<RamFloat>(a[0]) == ramBitCast<RamFloat>(b[0])); } }; using t_ind_0 = btree_set<t_tuple,t_comparator_0>;@@ -109,18 +109,18 @@ ind_0.printStats(o); } };-struct t_btree_u__0__1 {+struct t_btree_i__0__1 { static constexpr Relation::arity_type Arity = 1; using t_tuple = Tuple<RamDomain, 1>; struct t_comparator_0{ int operator()(const t_tuple& a, const t_tuple& b) const {- return (ramBitCast<RamUnsigned>(a[0]) < ramBitCast<RamUnsigned>(b[0])) ? -1 : (ramBitCast<RamUnsigned>(a[0]) > ramBitCast<RamUnsigned>(b[0])) ? 1 :(0);+ return (ramBitCast<RamSigned>(a[0]) < ramBitCast<RamSigned>(b[0])) ? -1 : (ramBitCast<RamSigned>(a[0]) > ramBitCast<RamSigned>(b[0])) ? 1 :(0); } bool less(const t_tuple& a, const t_tuple& b) const {- return (ramBitCast<RamUnsigned>(a[0]) < ramBitCast<RamUnsigned>(b[0]));+ return (ramBitCast<RamSigned>(a[0]) < ramBitCast<RamSigned>(b[0])); } bool equal(const t_tuple& a, const t_tuple& b) const {-return (ramBitCast<RamUnsigned>(a[0]) == ramBitCast<RamUnsigned>(b[0]));+return (ramBitCast<RamSigned>(a[0]) == ramBitCast<RamSigned>(b[0])); } }; using t_ind_0 = btree_set<t_tuple,t_comparator_0>;@@ -212,18 +212,18 @@ ind_0.printStats(o); } };-struct t_btree_f__0__1 {+struct t_btree_u__0__1 { static constexpr Relation::arity_type Arity = 1; using t_tuple = Tuple<RamDomain, 1>; struct t_comparator_0{ int operator()(const t_tuple& a, const t_tuple& b) const {- return (ramBitCast<RamFloat>(a[0]) < ramBitCast<RamFloat>(b[0])) ? -1 : (ramBitCast<RamFloat>(a[0]) > ramBitCast<RamFloat>(b[0])) ? 1 :(0);+ return (ramBitCast<RamUnsigned>(a[0]) < ramBitCast<RamUnsigned>(b[0])) ? -1 : (ramBitCast<RamUnsigned>(a[0]) > ramBitCast<RamUnsigned>(b[0])) ? 1 :(0); } bool less(const t_tuple& a, const t_tuple& b) const {- return (ramBitCast<RamFloat>(a[0]) < ramBitCast<RamFloat>(b[0]));+ return (ramBitCast<RamUnsigned>(a[0]) < ramBitCast<RamUnsigned>(b[0])); } bool equal(const t_tuple& a, const t_tuple& b) const {-return (ramBitCast<RamFloat>(a[0]) == ramBitCast<RamFloat>(b[0]));+return (ramBitCast<RamUnsigned>(a[0]) == ramBitCast<RamUnsigned>(b[0])); } }; using t_ind_0 = btree_set<t_tuple,t_comparator_0>;@@ -318,14 +318,6 @@ class Sf_round_trip : public SouffleProgram { private:-static inline bool regex_wrapper(const std::string& pattern, const std::string& text) {- bool result = false; - try { result = std::regex_match(text, std::regex(pattern)); } catch(...) { - std::cerr << "warning: wrong pattern provided for match(\"" << pattern << "\",\"" << text << "\").\n";-}- return result;-}-private: static inline std::string substr_wrapper(const std::string& str, std::size_t idx, std::size_t len) { std::string result; try { result = str.substr(idx,len); } catch(...) { @@ -336,30 +328,30 @@ public: // -- initialize symbol table -- SymbolTable symTable;// -- initialize record table ---RecordTable recordTable;-// -- Table: string_fact-Own<t_btree_i__0__1> rel_1_string_fact = mk<t_btree_i__0__1>();-souffle::RelationWrapper<t_btree_i__0__1> wrapper_rel_1_string_fact;+SpecializedRecordTable<0> recordTable{};+// -- Table: float_fact+Own<t_btree_f__0__1> rel_1_float_fact = mk<t_btree_f__0__1>();+souffle::RelationWrapper<t_btree_f__0__1> wrapper_rel_1_float_fact; // -- Table: number_fact Own<t_btree_i__0__1> rel_2_number_fact = mk<t_btree_i__0__1>(); souffle::RelationWrapper<t_btree_i__0__1> wrapper_rel_2_number_fact;+// -- Table: string_fact+Own<t_btree_i__0__1> rel_3_string_fact = mk<t_btree_i__0__1>();+souffle::RelationWrapper<t_btree_i__0__1> wrapper_rel_3_string_fact; // -- Table: unsigned_fact-Own<t_btree_u__0__1> rel_3_unsigned_fact = mk<t_btree_u__0__1>();-souffle::RelationWrapper<t_btree_u__0__1> wrapper_rel_3_unsigned_fact;-// -- Table: float_fact-Own<t_btree_f__0__1> rel_4_float_fact = mk<t_btree_f__0__1>();-souffle::RelationWrapper<t_btree_f__0__1> wrapper_rel_4_float_fact;+Own<t_btree_u__0__1> rel_4_unsigned_fact = mk<t_btree_u__0__1>();+souffle::RelationWrapper<t_btree_u__0__1> wrapper_rel_4_unsigned_fact; public: Sf_round_trip()-: wrapper_rel_1_string_fact(0, *rel_1_string_fact, *this, "string_fact", std::array<const char *,1>{{"s:symbol"}}, std::array<const char *,1>{{"x"}}, 0)+: wrapper_rel_1_float_fact(0, *rel_1_float_fact, *this, "float_fact", std::array<const char *,1>{{"f:float"}}, std::array<const char *,1>{{"x"}}, 0) , wrapper_rel_2_number_fact(1, *rel_2_number_fact, *this, "number_fact", std::array<const char *,1>{{"i:number"}}, std::array<const char *,1>{{"x"}}, 0)-, wrapper_rel_3_unsigned_fact(2, *rel_3_unsigned_fact, *this, "unsigned_fact", std::array<const char *,1>{{"u:unsigned"}}, std::array<const char *,1>{{"x"}}, 0)-, wrapper_rel_4_float_fact(3, *rel_4_float_fact, *this, "float_fact", std::array<const char *,1>{{"f:float"}}, std::array<const char *,1>{{"x"}}, 0)+, wrapper_rel_3_string_fact(2, *rel_3_string_fact, *this, "string_fact", std::array<const char *,1>{{"s:symbol"}}, std::array<const char *,1>{{"x"}}, 0)+, wrapper_rel_4_unsigned_fact(3, *rel_4_unsigned_fact, *this, "unsigned_fact", std::array<const char *,1>{{"u:unsigned"}}, std::array<const char *,1>{{"x"}}, 0) {-addRelation("string_fact", wrapper_rel_1_string_fact, true, true);+addRelation("float_fact", wrapper_rel_1_float_fact, true, true); addRelation("number_fact", wrapper_rel_2_number_fact, true, true);-addRelation("unsigned_fact", wrapper_rel_3_unsigned_fact, true, true);-addRelation("float_fact", wrapper_rel_4_float_fact, true, true);+addRelation("string_fact", wrapper_rel_3_string_fact, true, true);+addRelation("unsigned_fact", wrapper_rel_4_unsigned_fact, true, true); } ~Sf_round_trip() { }@@ -370,14 +362,15 @@ SignalHandler* signalHandler {SignalHandler::instance()}; std::atomic<RamDomain> ctr {}; std::atomic<std::size_t> iter {};-bool performIO = false; -void runFunction(std::string inputDirectoryArg = "",- std::string outputDirectoryArg = "",- bool performIOArg = false) {+void runFunction(std::string inputDirectoryArg,+ std::string outputDirectoryArg,+ bool performIOArg,+ bool pruneImdtRelsArg) { this->inputDirectory = std::move(inputDirectoryArg); this->outputDirectory = std::move(outputDirectoryArg); this->performIO = performIOArg;+ this->pruneImdtRels = pruneImdtRelsArg; // set default threads (in embedded mode) // if this is not set, and omp is used, the default omp setting of number of cores is used.@@ -408,55 +401,55 @@ signalHandler->reset(); } public:-void run() override { runFunction("", "", false); }+void run() override { runFunction("", "", false, false); } public:-void runAll(std::string inputDirectoryArg = "", std::string outputDirectoryArg = "") override { runFunction(inputDirectoryArg, outputDirectoryArg, true);+void runAll(std::string inputDirectoryArg = "", std::string outputDirectoryArg = "", bool performIOArg=true, bool pruneImdtRelsArg=true) override { runFunction(inputDirectoryArg, outputDirectoryArg, performIOArg, pruneImdtRelsArg); } public: void printAll(std::string outputDirectoryArg = "") override {-try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"name","string_fact"},{"operation","output"},{"output-dir","."},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"s:symbol\"]}}"}});+try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"name","float_fact"},{"operation","output"},{"output-dir","."},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"f:float\"]}}"}}); if (!outputDirectoryArg.empty()) {directiveMap["output-dir"] = outputDirectoryArg;}-IOSystem::getInstance().getWriter(directiveMap, symTable, recordTable)->writeAll(*rel_1_string_fact);+IOSystem::getInstance().getWriter(directiveMap, symTable, recordTable)->writeAll(*rel_1_float_fact); } catch (std::exception& e) {std::cerr << e.what();exit(1);} try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"name","number_fact"},{"operation","output"},{"output-dir","."},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"i:number\"]}}"}}); if (!outputDirectoryArg.empty()) {directiveMap["output-dir"] = outputDirectoryArg;} IOSystem::getInstance().getWriter(directiveMap, symTable, recordTable)->writeAll(*rel_2_number_fact); } catch (std::exception& e) {std::cerr << e.what();exit(1);}-try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"name","unsigned_fact"},{"operation","output"},{"output-dir","."},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"u:unsigned\"]}}"}});+try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"name","string_fact"},{"operation","output"},{"output-dir","."},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"s:symbol\"]}}"}}); if (!outputDirectoryArg.empty()) {directiveMap["output-dir"] = outputDirectoryArg;}-IOSystem::getInstance().getWriter(directiveMap, symTable, recordTable)->writeAll(*rel_3_unsigned_fact);+IOSystem::getInstance().getWriter(directiveMap, symTable, recordTable)->writeAll(*rel_3_string_fact); } catch (std::exception& e) {std::cerr << e.what();exit(1);}-try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"name","float_fact"},{"operation","output"},{"output-dir","."},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"f:float\"]}}"}});+try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"name","unsigned_fact"},{"operation","output"},{"output-dir","."},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"u:unsigned\"]}}"}}); if (!outputDirectoryArg.empty()) {directiveMap["output-dir"] = outputDirectoryArg;}-IOSystem::getInstance().getWriter(directiveMap, symTable, recordTable)->writeAll(*rel_4_float_fact);+IOSystem::getInstance().getWriter(directiveMap, symTable, recordTable)->writeAll(*rel_4_unsigned_fact); } catch (std::exception& e) {std::cerr << e.what();exit(1);} } public: void loadAll(std::string inputDirectoryArg = "") override {-try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"fact-dir","."},{"name","string_fact"},{"operation","input"},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"s:symbol\"]}}"}});+try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"fact-dir","."},{"name","float_fact"},{"operation","input"},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"f:float\"]}}"}}); if (!inputDirectoryArg.empty()) {directiveMap["fact-dir"] = inputDirectoryArg;}-IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_1_string_fact);-} catch (std::exception& e) {std::cerr << "Error loading data: " << e.what() << '\n';}+IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_1_float_fact);+} catch (std::exception& e) {std::cerr << "Error loading float_fact data: " << e.what() << '\n';} try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"fact-dir","."},{"name","number_fact"},{"operation","input"},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"i:number\"]}}"}}); if (!inputDirectoryArg.empty()) {directiveMap["fact-dir"] = inputDirectoryArg;} IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_2_number_fact);-} catch (std::exception& e) {std::cerr << "Error loading data: " << e.what() << '\n';}-try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"fact-dir","."},{"name","unsigned_fact"},{"operation","input"},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"u:unsigned\"]}}"}});+} catch (std::exception& e) {std::cerr << "Error loading number_fact data: " << e.what() << '\n';}+try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"fact-dir","."},{"name","string_fact"},{"operation","input"},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"s:symbol\"]}}"}}); if (!inputDirectoryArg.empty()) {directiveMap["fact-dir"] = inputDirectoryArg;}-IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_3_unsigned_fact);-} catch (std::exception& e) {std::cerr << "Error loading data: " << e.what() << '\n';}-try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"fact-dir","."},{"name","float_fact"},{"operation","input"},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"f:float\"]}}"}});+IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_3_string_fact);+} catch (std::exception& e) {std::cerr << "Error loading string_fact data: " << e.what() << '\n';}+try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"fact-dir","."},{"name","unsigned_fact"},{"operation","input"},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"u:unsigned\"]}}"}}); if (!inputDirectoryArg.empty()) {directiveMap["fact-dir"] = inputDirectoryArg;}-IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_4_float_fact);-} catch (std::exception& e) {std::cerr << "Error loading data: " << e.what() << '\n';}+IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_4_unsigned_fact);+} catch (std::exception& e) {std::cerr << "Error loading unsigned_fact data: " << e.what() << '\n';} } public: void dumpInputs() override { try {std::map<std::string, std::string> rwOperation; rwOperation["IO"] = "stdout";-rwOperation["name"] = "string_fact";-rwOperation["types"] = "{\"relation\": {\"arity\": 1, \"auxArity\": 0, \"types\": [\"s:symbol\"]}}";-IOSystem::getInstance().getWriter(rwOperation, symTable, recordTable)->writeAll(*rel_1_string_fact);+rwOperation["name"] = "float_fact";+rwOperation["types"] = "{\"relation\": {\"arity\": 1, \"auxArity\": 0, \"types\": [\"f:float\"]}}";+IOSystem::getInstance().getWriter(rwOperation, symTable, recordTable)->writeAll(*rel_1_float_fact); } catch (std::exception& e) {std::cerr << e.what();exit(1);} try {std::map<std::string, std::string> rwOperation; rwOperation["IO"] = "stdout";@@ -466,24 +459,24 @@ } catch (std::exception& e) {std::cerr << e.what();exit(1);} try {std::map<std::string, std::string> rwOperation; rwOperation["IO"] = "stdout";-rwOperation["name"] = "unsigned_fact";-rwOperation["types"] = "{\"relation\": {\"arity\": 1, \"auxArity\": 0, \"types\": [\"u:unsigned\"]}}";-IOSystem::getInstance().getWriter(rwOperation, symTable, recordTable)->writeAll(*rel_3_unsigned_fact);+rwOperation["name"] = "string_fact";+rwOperation["types"] = "{\"relation\": {\"arity\": 1, \"auxArity\": 0, \"types\": [\"s:symbol\"]}}";+IOSystem::getInstance().getWriter(rwOperation, symTable, recordTable)->writeAll(*rel_3_string_fact); } catch (std::exception& e) {std::cerr << e.what();exit(1);} try {std::map<std::string, std::string> rwOperation; rwOperation["IO"] = "stdout";-rwOperation["name"] = "float_fact";-rwOperation["types"] = "{\"relation\": {\"arity\": 1, \"auxArity\": 0, \"types\": [\"f:float\"]}}";-IOSystem::getInstance().getWriter(rwOperation, symTable, recordTable)->writeAll(*rel_4_float_fact);+rwOperation["name"] = "unsigned_fact";+rwOperation["types"] = "{\"relation\": {\"arity\": 1, \"auxArity\": 0, \"types\": [\"u:unsigned\"]}}";+IOSystem::getInstance().getWriter(rwOperation, symTable, recordTable)->writeAll(*rel_4_unsigned_fact); } catch (std::exception& e) {std::cerr << e.what();exit(1);} } public: void dumpOutputs() override { try {std::map<std::string, std::string> rwOperation; rwOperation["IO"] = "stdout";-rwOperation["name"] = "string_fact";-rwOperation["types"] = "{\"relation\": {\"arity\": 1, \"auxArity\": 0, \"types\": [\"s:symbol\"]}}";-IOSystem::getInstance().getWriter(rwOperation, symTable, recordTable)->writeAll(*rel_1_string_fact);+rwOperation["name"] = "float_fact";+rwOperation["types"] = "{\"relation\": {\"arity\": 1, \"auxArity\": 0, \"types\": [\"f:float\"]}}";+IOSystem::getInstance().getWriter(rwOperation, symTable, recordTable)->writeAll(*rel_1_float_fact); } catch (std::exception& e) {std::cerr << e.what();exit(1);} try {std::map<std::string, std::string> rwOperation; rwOperation["IO"] = "stdout";@@ -493,15 +486,15 @@ } catch (std::exception& e) {std::cerr << e.what();exit(1);} try {std::map<std::string, std::string> rwOperation; rwOperation["IO"] = "stdout";-rwOperation["name"] = "unsigned_fact";-rwOperation["types"] = "{\"relation\": {\"arity\": 1, \"auxArity\": 0, \"types\": [\"u:unsigned\"]}}";-IOSystem::getInstance().getWriter(rwOperation, symTable, recordTable)->writeAll(*rel_3_unsigned_fact);+rwOperation["name"] = "string_fact";+rwOperation["types"] = "{\"relation\": {\"arity\": 1, \"auxArity\": 0, \"types\": [\"s:symbol\"]}}";+IOSystem::getInstance().getWriter(rwOperation, symTable, recordTable)->writeAll(*rel_3_string_fact); } catch (std::exception& e) {std::cerr << e.what();exit(1);} try {std::map<std::string, std::string> rwOperation; rwOperation["IO"] = "stdout";-rwOperation["name"] = "float_fact";-rwOperation["types"] = "{\"relation\": {\"arity\": 1, \"auxArity\": 0, \"types\": [\"f:float\"]}}";-IOSystem::getInstance().getWriter(rwOperation, symTable, recordTable)->writeAll(*rel_4_float_fact);+rwOperation["name"] = "unsigned_fact";+rwOperation["types"] = "{\"relation\": {\"arity\": 1, \"auxArity\": 0, \"types\": [\"u:unsigned\"]}}";+IOSystem::getInstance().getWriter(rwOperation, symTable, recordTable)->writeAll(*rel_4_unsigned_fact); } catch (std::exception& e) {std::cerr << e.what();exit(1);} } public:@@ -536,15 +529,15 @@ #endif // _MSC_VER void subroutine_0(const std::vector<RamDomain>& args, std::vector<RamDomain>& ret) { if (performIO) {-try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"fact-dir","."},{"name","string_fact"},{"operation","input"},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"s:symbol\"]}}"}});+try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"fact-dir","."},{"name","float_fact"},{"operation","input"},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"f:float\"]}}"}}); if (!inputDirectory.empty()) {directiveMap["fact-dir"] = inputDirectory;}-IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_1_string_fact);-} catch (std::exception& e) {std::cerr << "Error loading data: " << e.what() << '\n';}+IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_1_float_fact);+} catch (std::exception& e) {std::cerr << "Error loading float_fact data: " << e.what() << '\n';} } if (performIO) {-try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"name","string_fact"},{"operation","output"},{"output-dir","."},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"s:symbol\"]}}"}});+try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"name","float_fact"},{"operation","output"},{"output-dir","."},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"f:float\"]}}"}}); if (!outputDirectory.empty()) {directiveMap["output-dir"] = outputDirectory;}-IOSystem::getInstance().getWriter(directiveMap, symTable, recordTable)->writeAll(*rel_1_string_fact);+IOSystem::getInstance().getWriter(directiveMap, symTable, recordTable)->writeAll(*rel_1_float_fact); } catch (std::exception& e) {std::cerr << e.what();exit(1);} } }@@ -559,7 +552,7 @@ try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"fact-dir","."},{"name","number_fact"},{"operation","input"},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"i:number\"]}}"}}); if (!inputDirectory.empty()) {directiveMap["fact-dir"] = inputDirectory;} IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_2_number_fact);-} catch (std::exception& e) {std::cerr << "Error loading data: " << e.what() << '\n';}+} catch (std::exception& e) {std::cerr << "Error loading number_fact data: " << e.what() << '\n';} } if (performIO) { try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"name","number_fact"},{"operation","output"},{"output-dir","."},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"i:number\"]}}"}});@@ -576,15 +569,15 @@ #endif // _MSC_VER void subroutine_2(const std::vector<RamDomain>& args, std::vector<RamDomain>& ret) { if (performIO) {-try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"fact-dir","."},{"name","unsigned_fact"},{"operation","input"},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"u:unsigned\"]}}"}});+try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"fact-dir","."},{"name","string_fact"},{"operation","input"},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"s:symbol\"]}}"}}); if (!inputDirectory.empty()) {directiveMap["fact-dir"] = inputDirectory;}-IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_3_unsigned_fact);-} catch (std::exception& e) {std::cerr << "Error loading data: " << e.what() << '\n';}+IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_3_string_fact);+} catch (std::exception& e) {std::cerr << "Error loading string_fact data: " << e.what() << '\n';} } if (performIO) {-try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"name","unsigned_fact"},{"operation","output"},{"output-dir","."},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"u:unsigned\"]}}"}});+try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"name","string_fact"},{"operation","output"},{"output-dir","."},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"s:symbol\"]}}"}}); if (!outputDirectory.empty()) {directiveMap["output-dir"] = outputDirectory;}-IOSystem::getInstance().getWriter(directiveMap, symTable, recordTable)->writeAll(*rel_3_unsigned_fact);+IOSystem::getInstance().getWriter(directiveMap, symTable, recordTable)->writeAll(*rel_3_string_fact); } catch (std::exception& e) {std::cerr << e.what();exit(1);} } }@@ -596,15 +589,15 @@ #endif // _MSC_VER void subroutine_3(const std::vector<RamDomain>& args, std::vector<RamDomain>& ret) { if (performIO) {-try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"fact-dir","."},{"name","float_fact"},{"operation","input"},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"f:float\"]}}"}});+try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"fact-dir","."},{"name","unsigned_fact"},{"operation","input"},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"u:unsigned\"]}}"}}); if (!inputDirectory.empty()) {directiveMap["fact-dir"] = inputDirectory;}-IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_4_float_fact);-} catch (std::exception& e) {std::cerr << "Error loading data: " << e.what() << '\n';}+IOSystem::getInstance().getReader(directiveMap, symTable, recordTable)->readAll(*rel_4_unsigned_fact);+} catch (std::exception& e) {std::cerr << "Error loading unsigned_fact data: " << e.what() << '\n';} } if (performIO) {-try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"name","float_fact"},{"operation","output"},{"output-dir","."},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"f:float\"]}}"}});+try {std::map<std::string, std::string> directiveMap({{"IO","file"},{"attributeNames","x"},{"auxArity","0"},{"name","unsigned_fact"},{"operation","output"},{"output-dir","."},{"params","{\"records\": {}, \"relation\": {\"arity\": 1, \"params\": [\"x\"]}}"},{"types","{\"ADTs\": {}, \"records\": {}, \"relation\": {\"arity\": 1, \"types\": [\"u:unsigned\"]}}"}}); if (!outputDirectory.empty()) {directiveMap["output-dir"] = outputDirectory;}-IOSystem::getInstance().getWriter(directiveMap, symTable, recordTable)->writeAll(*rel_4_float_fact);+IOSystem::getInstance().getWriter(directiveMap, symTable, recordTable)->writeAll(*rel_4_unsigned_fact); } catch (std::exception& e) {std::cerr << e.what();exit(1);} } }