souffle::synthesiser::BrieRelation Class Reference

#include <Relation.h>

Inheritance diagram for souffle::synthesiser::BrieRelation:

Collaboration diagram for souffle::synthesiser::BrieRelation:

Public Member Functions
	BrieRelation (const ram::Relation &ramRel, const MinIndexSelection &indexSet, bool isProvenance)
void	computeIndices () override
	Generate index set for a brie relation. More...
void	generateTypeStruct (std::ostream &out) override
	Generate type struct of a brie relation. More...
std::string	getTypeName () override
	Generate type name of a brie relation. More...
Public Member Functions inherited from souffle::ram::Relation
Relation *	clone () const override
	Create a clone (i.e. More...
unsigned	getArity () const
	Get arity of relation. More...
const std::vector< std::string > &	getAttributeNames () const
	Get attribute names. More...
const std::vector< std::string > &	getAttributeTypes () const
	Get attribute types. More...
unsigned	getAuxiliaryArity () const
	Get number of auxiliary attributes. More...
const std::string &	getName () const
	Get name. More...
RelationRepresentation	getRepresentation () const
	Relation representation type. More...
bool	isNullary () const
	Is nullary relation. More...
bool	isTemp () const
	Is temporary relation (for semi-naive evaluation) More...
bool	operator< (const Relation &other) const
	Compare two relations via their name. More...
	Relation (std::string name, size_t arity, size_t auxiliaryArity, std::vector< std::string > attributeNames, std::vector< std::string > attributeTypes, RelationRepresentation representation)
Public Member Functions inherited from souffle::ram::Node
virtual void	apply (const NodeMapper &)
	Apply the mapper to all child nodes. More...
virtual std::vector< const Node * >	getChildNodes () const
	Obtain list of all embedded child nodes. More...
bool	operator!= (const Node &other) const
	Inequality check for two RAM nodes. More...
bool	operator== (const Node &other) const
	Equivalence check for two RAM nodes. More...
virtual void	rewrite (const Node *oldNode, Own< Node > newNode)
	Rewrite a child node. More...
virtual	~Node ()=default

Additional Inherited Members
Protected Member Functions inherited from souffle::ram::Relation
bool	equal (const Node &node) const override
	Equality check for two RAM nodes. More...
void	print (std::ostream &out) const override
	Print RAM node. More...
Protected Attributes inherited from souffle::ram::Relation
const size_t	arity
	Arity, i.e., number of attributes. More...
const std::vector< std::string >	attributeNames
	Name of attributes. More...
const std::vector< std::string >	attributeTypes
	Type of attributes. More...
const size_t	auxiliaryArity
	Number of auxiliary attributes (e.g. More...
const std::string	name
	Name of relation. More...
const RelationRepresentation	representation
	Data-structure representation. More...

Detailed Description

Definition at line 144 of file Relation.h.

Constructor & Destructor Documentation

BrieRelation()

souffle::synthesiser::BrieRelation::BrieRelation ( const ram::Relation &  ramRel, const MinIndexSelection &  indexSet, bool  isProvenance  )

inline

Definition at line 146 of file Relation.h.

            : Relation(ramRel, indexSet, isProvenance) {}

Member Function Documentation

computeIndices()

void souffle::synthesiser::BrieRelation::computeIndices ( )

override

Generate index set for a brie relation.

Definition at line 849 of file Relation.cpp.

                                  {
    assert(!isProvenance && "bries cannot be used with provenance");
 
    // Generate and set indices
    MinIndexSelection::OrderCollection inds = indices.getAllOrders();
 
    // generate a full index if no indices exist
    assert(!inds.empty() && "No full index in relation");
 
    // expand all indexes to be full
    for (auto& ind : inds) {
        if (ind.size() != getArity()) {
            // use a set as a cache for fast lookup
            std::set<int> curIndexElems(ind.begin(), ind.end());
 
            // expand index to be full
            for (size_t i = 0; i < getArity(); i++) {
                if (curIndexElems.find(i) == curIndexElems.end()) {
                    ind.push_back(i);
                }
            }
        }
 
        assert(ind.size() == getArity() && "index is not a full");
    }
    masterIndex = 0;
 
    computedIndices = inds;
}

References i.

generateTypeStruct()

void souffle::synthesiser::BrieRelation::generateTypeStruct ( std::ostream &  out )

override

Generate type struct of a brie relation.

Definition at line 904 of file Relation.cpp.

                                                     {
    size_t arity = getArity();
    const auto& inds = getIndices();
    size_t numIndexes = inds.size();
    std::map<MinIndexSelection::LexOrder, int> indexToNumMap;
 
    // struct definition
    out << "struct " << getTypeName() << " {\n";
    out << "static constexpr Relation::arity_type Arity = " << arity << ";\n";
 
    // define trie structures
    for (size_t i = 0; i < inds.size(); i++) {
        if (i < getMinIndexSelection().getAllOrders().size()) {
            indexToNumMap[getMinIndexSelection().getAllOrders()[i]] = i;
        }
        out << "using t_ind_" << i << " = Trie<" << inds[i].size() << ">;\n";
        out << "t_ind_" << i << " ind_" << i << ";\n";
    }
    out << "using t_tuple = t_ind_" << masterIndex << "::entry_type;\n";
 
    // generate auxiliary iterators that use orderOut
    for (size_t i = 0; i < numIndexes; i++) {
        // generate auxiliary iterators which orderOut
        out << "class iterator_" << i << " : public std::iterator<std::forward_iterator_tag, t_tuple> {\n";
        out << "    using nested_iterator = typename t_ind_" << i << "::iterator;\n";
        out << "    nested_iterator nested;\n";
        out << "    t_tuple value;\n";
 
        out << "public:\n";
        out << "    iterator_" << i << "() = default;\n";
        out << "    iterator_" << i << "(const nested_iterator& iter) : nested(iter), value(orderOut_" << i
            << "(*iter)) {}\n";
        out << "    iterator_" << i << "(const iterator_" << i << "& other) = default;\n";
        out << "    iterator_" << i << "& operator=(const iterator_" << i << "& other) = default;\n";
 
        out << "    bool operator==(const iterator_" << i << "& other) const {\n";
        out << "        return nested == other.nested;\n";
        out << "    }\n";
 
        out << "    bool operator!=(const iterator_" << i << "& other) const {\n";
        out << "        return !(*this == other);\n";
        out << "    }\n";
 
        out << "    const t_tuple& operator*() const {\n";
        out << "        return value;\n";
        out << "    }\n";
 
        out << "    const t_tuple* operator->() const {\n";
        out << "        return &value;\n";
        out << "    }\n";
 
        out << "    iterator_" << i << "& operator++() {\n";
        out << "        ++nested;\n";
        out << "        value = orderOut_" << i << "(*nested);\n";
        out << "        return *this;\n";
        out << "    }\n";
        out << "};\n";
    }
    out << "using iterator = iterator_" << masterIndex << ";\n";
 
    // hints struct
    out << "struct context {\n";
    for (size_t i = 0; i < numIndexes; i++) {
        out << "t_ind_" << i << "::op_context hints_" << i << ";\n";
    }
    out << "};\n";
    out << "context createContext() { return context(); }\n";
 
    // insert methods
    out << "bool insert(const t_tuple& t) {\n";
    out << "context h;\n";
    out << "return insert(t, h);\n";
    out << "}\n";
 
    out << "bool insert(const t_tuple& t, context& h) {\n";
    out << "if (ind_" << masterIndex << ".insert(orderIn_" << masterIndex << "(t), h.hints_" << masterIndex
        << ")) {\n";
    for (size_t i = 0; i < numIndexes; i++) {
        if (i != masterIndex) {
            out << "ind_" << i << ".insert(orderIn_" << i << "(t), h.hints_" << i << ");\n";
        }
    }
    out << "return true;\n";
    out << "} else return false;\n";
    out << "}\n";
 
    out << "bool insert(const RamDomain* ramDomain) {\n";
    out << "RamDomain data[" << arity << "];\n";
    out << "std::copy(ramDomain, ramDomain + " << arity << ", data);\n";
    out << "const t_tuple& tuple = reinterpret_cast<const t_tuple&>(data);\n";
    out << "context h;\n";
    out << "return insert(tuple, h);\n";
    out << "}\n";
 
    // insert method
    std::vector<std::string> decls;
    std::vector<std::string> params;
    for (size_t i = 0; i < arity; i++) {
        decls.push_back("RamDomain a" + std::to_string(i));
        params.push_back("a" + std::to_string(i));
    }
    out << "bool insert(" << join(decls, ",") << ") {\nRamDomain data[";
    out << arity << "] = {" << join(params, ",") << "};\n";
    out << "return insert(data);\n";
    out << "}\n";
 
    // contains methods
    out << "bool contains(const t_tuple& t, context& h) const {\n";
    out << "return ind_" << masterIndex << ".contains(orderIn_" << masterIndex << "(t), h.hints_"
        << masterIndex << ");\n";
    out << "}\n";
 
    out << "bool contains(const t_tuple& t) const {\n";
    out << "context h;\n";
    out << "return contains(t, h);\n";
    out << "}\n";
 
    // size method
    out << "std::size_t size() const {\n";
    out << "return ind_" << masterIndex << ".size();\n";
    out << "}\n";
 
    // find methods
    if (arity > 1) {
        out << "iterator find(const t_tuple& t, context& h) const {\n";
        out << "return ind_" << masterIndex << ".find(orderIn_" << masterIndex << "(t), h.hints_"
            << masterIndex << ");\n";
        out << "}\n";
 
        out << "iterator find(const t_tuple& t) const {\n";
        out << "context h;\n";
        out << "return find(t, h);\n";
        out << "}\n";
    }
 
    // empty lowerUpperRange method
    out << "range<iterator> lowerUpperRange_0(const t_tuple& lower, const t_tuple& upper, context& h) const "
           "{\n";
    out << "return range<iterator>(ind_" << masterIndex << ".begin(),ind_" << masterIndex << ".end());\n";
    out << "}\n";
 
    out << "range<iterator> lowerUpperRange_0(const t_tuple& lower, const t_tuple& upper) const {\n";
    out << "return range<iterator>(ind_" << masterIndex << ".begin(),ind_" << masterIndex << ".end());\n";
    out << "}\n";
 
    // loweUpperRange methods
    for (auto search : getMinIndexSelection().getSearches()) {
        auto& lexOrder = getMinIndexSelection().getLexOrder(search);
        size_t indNum = indexToNumMap[lexOrder];
 
        out << "range<iterator_" << indNum << "> lowerUpperRange_" << search;
        out << "(const t_tuple& lower, const t_tuple& upper, context& h) const {\n";
 
        // compute size of sub-index
        size_t indSize = 0;
        for (size_t i = 0; i < arity; i++) {
            if (search[i] != analysis::AttributeConstraint::None) {
                indSize++;
            }
        }
 
        out << "auto r = ind_" << indNum << ".template getBoundaries<" << indSize << ">(orderIn_" << indNum
            << "(lower), h.hints_" << indNum << ");\n";
        out << "return make_range(iterator_" << indNum << "(r.begin()), iterator_" << indNum
            << "(r.end()));\n";
        out << "}\n";
 
        out << "range<iterator_" << indNum << "> lowerUpperRange_" << search;
        out << "(const t_tuple& lower, const t_tuple& upper) const {\n";
        out << "context h; return lowerUpperRange_" << search << "(lower,upper, h);\n";
        out << "}\n";
    }
 
    // empty method
    out << "bool empty() const {\n";
    out << "return ind_" << masterIndex << ".empty();\n";
    out << "}\n";
 
    // partition method
    out << "std::vector<range<iterator>> partition() const {\n";
    out << "std::vector<range<iterator>> res;\n";
    out << "for (const auto& cur : ind_" << masterIndex << ".partition(10000)) {\n";
    out << "    res.push_back(make_range(iterator(cur.begin()), iterator(cur.end())));\n";
    out << "}\n";
    out << "return res;\n";
    out << "}\n";
 
    // purge method
    out << "void purge() {\n";
    for (size_t i = 0; i < numIndexes; i++) {
        out << "ind_" << i << ".clear();\n";
    }
    out << "}\n";
 
    // begin and end iterators
    out << "iterator begin() const {\n";
    out << "return iterator_" << masterIndex << "(ind_" << masterIndex << ".begin());\n";
    out << "}\n";
 
    out << "iterator end() const {\n";
    out << "return iterator_" << masterIndex << "(ind_" << masterIndex << ".end());\n";
    out << "}\n";
 
    // TODO: finish printStatistics method
    out << "void printStatistics(std::ostream& o) const {\n";
    for (size_t i = 0; i < numIndexes; i++) {
        out << "o << \" arity " << arity << " brie index " << i << " lex-order " << inds[i] << "\\n\";\n";
        ;
        out << "ind_" << i << ".printStats(o);\n";
    }
    out << "}\n";
 
    // orderOut and orderIn methods for reordering tuples according to index orders
    for (size_t i = 0; i < numIndexes; i++) {
        auto ind = inds[i];
        out << "static t_tuple orderIn_" << i << "(const t_tuple& t) {\n";
        out << "t_tuple res;\n";
        for (size_t j = 0; j < ind.size(); j++) {
            out << "res[" << j << "] = t[" << ind[j] << "];\n";
        }
        out << "return res;\n";
        out << "}\n";
 
        out << "static t_tuple orderOut_" << i << "(const t_tuple& t) {\n";
        out << "t_tuple res;\n";
        for (size_t j = 0; j < ind.size(); j++) {
            out << "res[" << ind[j] << "] = t[" << j << "];\n";
        }
        out << "return res;\n";
        out << "}\n";
    }
 
    // end class
    out << "};\n";
}

References i, j, souffle::join(), and TCB_SPAN_NAMESPACE_NAME::detail::size().

Here is the call graph for this function:

getTypeName()

std::string souffle::synthesiser::BrieRelation::getTypeName ( )

override

Generate type name of a brie relation.

Definition at line 880 of file Relation.cpp.

                                    {
    // collect all attributes used in the lex-order
    std::unordered_set<uint32_t> attributesUsed;
    for (auto& ind : getIndices()) {
        for (auto& attr : ind) {
            attributesUsed.insert(attr);
        }
    }
 
    std::stringstream res;
    res << "t_brie_" << getTypeAttributeString(relation.getAttributeTypes(), attributesUsed);
 
    for (auto& ind : getIndices()) {
        res << "__" << join(ind, "_");
    }
 
    for (auto& search : getMinIndexSelection().getSearches()) {
        res << "__" << search;
    }
 
    return res.str();
}

References souffle::join(), and relation.

Here is the call graph for this function:

---

The documentation for this class was generated from the following files:

• synthesiser/Relation.h
• synthesiser/Relation.cpp