souffle::ast::transform::MagicSetTransformer::NormaliseDatabaseTransformer Class Reference

Database normaliser for MST. More...

#include <MagicSet.h>

Inheritance diagram for souffle::ast::transform::MagicSetTransformer::NormaliseDatabaseTransformer:

Collaboration diagram for souffle::ast::transform::MagicSetTransformer::NormaliseDatabaseTransformer:

Public Member Functions
NormaliseDatabaseTransformer *	clone () const override
std::string	getName () const override
Public Member Functions inherited from souffle::ast::transform::Transformer
bool	apply (TranslationUnit &translationUnit)
virtual	~Transformer ()=default

Private Member Functions
bool	transform (TranslationUnit &translationUnit) override

Static Private Member Functions
static bool	extractIDB (TranslationUnit &translationUnit)
	Separates the IDB from the EDB, so that they are disjoint. More...
static bool	normaliseArguments (TranslationUnit &translationUnit)
	Normalise all arguments within each clause. More...
static bool	partitionIO (TranslationUnit &translationUnit)
	Partitions the input and output relations. More...
static bool	querifyOutputRelations (TranslationUnit &translationUnit)
	Extracts output relations into separate simple query relations, so that they are unused in any other rules. More...

Detailed Description

Database normaliser for MST.

Effects:

• Partitions database into [input|intermediate|queries]
• Normalises all arguments and constraints Prerequisite for adornment.

Definition at line 112 of file MagicSet.h.

Member Function Documentation

clone()

NormaliseDatabaseTransformer* souffle::ast::transform::MagicSetTransformer::NormaliseDatabaseTransformer::clone ( ) const

inlineoverridevirtual

Implements souffle::ast::transform::Transformer.

Definition at line 118 of file MagicSet.h.

                                                         {
        return new NormaliseDatabaseTransformer();
    }

extractIDB()

bool souffle::ast::transform::NormaliseDatabaseTransformer::extractIDB ( TranslationUnit &  translationUnit )

staticprivate

Separates the IDB from the EDB, so that they are disjoint.

Program will no longer have input relations that appear as the head of clauses.

Definition at line 380 of file MagicSet.cpp.

                                : getClauses(program, rel->getQualifiedName())) {
            visitDepthFirst(clause->getBodyLiterals(), [&](const Atom& /* atom */) { hasRules = true; });
        }
        return !hasRules;
    };
 
    // Get all input relations that also have IDB rules attached
    std::set<QualifiedName> inputRelationNames;
    for (auto* rel : program.getRelations()) {
        if (ioTypes.isInput(rel) && !isStrictlyEDB(rel)) {
            assert(!ioTypes.isOutput(rel) && !ioTypes.isPrintSize(rel) &&
                    "input relations should not be output at this stage");
            inputRelationNames.insert(rel->getQualifiedName());
        }
    }
 
    // Add a new intermediate non-input relation for each
    // These will cover relation appearances in IDB rules
    std::map<QualifiedName, QualifiedName> inputToIntermediate;
    for (const auto& inputRelationName : inputRelationNames) {
        // Give it a unique name
        QualifiedName intermediateName(inputRelationName);
        intermediateName.prepend("@interm_in");
        inputToIntermediate[inputRelationName] = intermediateName;
 
        // Add the relation
        auto intermediateRelation = souffle::clone(getRelation(program, inputRelationName));
        intermediateRelation->setQualifiedName(intermediateName);
        program.addRelation(std::move(intermediateRelation));
    }
 
    // Rename them systematically
    renameAtoms(program, inputToIntermediate);
 
    // Add the rule I' <- I
    for (const auto& inputRelationName : inputRelationNames) {
        auto queryHead = mk<Atom>(inputToIntermediate.at(inputRelationName));
        auto queryLiteral = mk<Atom>(inputRelationName);
 
        // Give them identical arguments
        const auto* inputRelation = getRelation(program, inputRelationName);
        for (size_t i = 0; i < inputRelation->getArity(); i++) {
            std::stringstream var;
            var << "@query_x" << i;
            queryHead->addArgument(mk<ast::Variable>(var.str()));
            queryLiteral->addArgument(mk<ast::Variable>(var.str()));
        }
 
        auto query = mk<Clause>(std::move(queryHead));
        query->addToBody(std::move(queryLiteral));
        program.addClause(std::move(query));
    }
 
    return !inputRelationNames.empty();
}
 
bool NormaliseDatabaseTransformer::querifyOutputRelations(TranslationUnit& translationUnit) {
    Program& program = translationUnit.getProgram();
 
    // Helper method to check if a relation is a single-rule output query
    auto isStrictlyOutput = [&](const Relation* rel) {

References souffle::ast::visitDepthFirst().

Here is the call graph for this function:

getName()

std::string souffle::ast::transform::MagicSetTransformer::NormaliseDatabaseTransformer::getName ( ) const

inlineoverridevirtual

Implements souffle::ast::transform::Transformer.

Definition at line 114 of file MagicSet.h.

                                       {
        return "NormaliseDatabaseTransformer";
    }

normaliseArguments()

bool souffle::ast::transform::NormaliseDatabaseTransformer::normaliseArguments ( TranslationUnit &  translationUnit )

staticprivate

Normalise all arguments within each clause.

All arguments in all clauses will now be either: (1) a variable, or (2) the RHS of a <var> = <arg> constraint

Definition at line 517 of file MagicSet.cpp.

                : constraints(constraints), changeCount(changeCount) {}
 
        Own<Node> operator()(Own<Node> node) const override {
            if (auto* aggr = dynamic_cast<Aggregator*>(node.get())) {
                // Aggregator variable scopes should be maintained, so changes shouldn't propagate
                // above this level.
                std::set<Own<BinaryConstraint>> subConstraints;
                argument_normaliser aggrUpdate(subConstraints, changeCount);
                aggr->apply(aggrUpdate);
 
                // Add the constraints to this level
                std::vector<Own<Literal>> newBodyLiterals;
                for (const auto* lit : aggr->getBodyLiterals()) {
                    newBodyLiterals.push_back(souffle::clone(lit));
                }
                for (auto& constr : subConstraints) {
                    newBodyLiterals.push_back(souffle::clone(constr));
                }
 
                // Update the node to reflect normalised aggregator
                node = aggr->getTargetExpression() != nullptr
                               ? mk<Aggregator>(aggr->getBaseOperator(),
                                         souffle::clone(aggr->getTargetExpression()),
                                         std::move(newBodyLiterals))
                               : mk<Aggregator>(aggr->getBaseOperator(), nullptr, std::move(newBodyLiterals));
            } else {
                // Otherwise, just normalise children as usual.
                node->apply(*this);
            }
 
            // All non-variables should be normalised
            if (auto* arg = dynamic_cast<Argument*>(node.get())) {
                if (!isA<ast::Variable>(arg)) {
                    std::stringstream name;
                    name << "@abdul" << changeCount++;
 
                    // Unnamed variables don't need a new constraint, just give them a name
                    if (isA<UnnamedVariable>(arg)) {
                        return mk<ast::Variable>(name.str());
                    }
 
                    // Link other variables back to their original value with a `<var> = <arg>` constraint
                    constraints.insert(mk<BinaryConstraint>(
                            BinaryConstraintOp::EQ, mk<ast::Variable>(name.str()), souffle::clone(arg)));
                    return mk<ast::Variable>(name.str());
                }
            }
            return node;
        }
    };
 
    // Transform each clause so that all arguments are:
    //      1) a variable, or
    //      2) the RHS of a `<var> = <arg>` constraint
    bool changed = false;
    for (auto* clause : program.getClauses()) {
        int changeCount = 0;
        std::set<Own<BinaryConstraint>> constraintsToAdd;
        argument_normaliser update(constraintsToAdd, changeCount);
 
        // Apply to each clause head
        clause->getHead()->apply(update);
 
        // Apply to each body literal that isn't already a `<var> = <arg>` constraint
        for (Literal* lit : clause->getBodyLiterals()) {
            if (auto* bc = dynamic_cast<BinaryConstraint*>(lit)) {
                if (isEqConstraint(bc->getBaseOperator()) && isA<ast::Variable>(bc->getLHS())) {
                    continue;
                }
            }
            lit->apply(update);
        }
 
        // Also apply to each record
        visitDepthFirst(*clause, [&](const RecordInit& rec) {
            for (Argument* arg : rec.getArguments()) {
                arg->apply(update);
            }
        });
 
        // Add each necessary new constraint to the clause
        for (auto& constraint : constraintsToAdd) {
            clause->addToBody(souffle::clone(constraint));
        }
 
        changed |= changeCount != 0;
    }
 
    return changed;
}
 
QualifiedName AdornDatabaseTransformer::getAdornmentID(
        const QualifiedName& relName, const std::string& adornmentMarker) {
    if (adornmentMarker == "") return relName;
    QualifiedName adornmentID(relName);
    std::stringstream adornmentMarkerRepr;

partitionIO()

bool souffle::ast::transform::NormaliseDatabaseTransformer::partitionIO ( TranslationUnit &  translationUnit )

staticprivate

Partitions the input and output relations.

Program will no longer have relations that are both input and output.

Definition at line 312 of file MagicSet.cpp.

                   : program.getRelations()) {
        if (ioTypes.isInput(rel) && (ioTypes.isOutput(rel) || ioTypes.isPrintSize(rel))) {
            relationsToSplit.insert(rel->getQualifiedName());
        }
    }
 
    // For each of these relations I, add a new relation I' that's input instead.
    // The old relation I is no longer input, but copies over the data from I'.
    for (auto relName : relationsToSplit) {
        const auto* rel = getRelation(program, relName);
        assert(rel != nullptr && "relation does not exist");
        auto newRelName = QualifiedName(relName);
        newRelName.prepend("@split_in");
 
        // Create a new intermediate input relation, I'
        auto newRelation = mk<Relation>(newRelName);
        for (const auto* attr : rel->getAttributes()) {
            newRelation->addAttribute(souffle::clone(attr));
        }
 
        // Add the rule I <- I'
        auto newClause = mk<Clause>();
        auto newHeadAtom = mk<Atom>(relName);
        auto newBodyAtom = mk<Atom>(newRelName);
        for (size_t i = 0; i < rel->getArity(); i++) {
            std::stringstream varName;
            varName << "@var" << i;
            newHeadAtom->addArgument(mk<ast::Variable>(varName.str()));
            newBodyAtom->addArgument(mk<ast::Variable>(varName.str()));
        }
        newClause->setHead(std::move(newHeadAtom));
        newClause->addToBody(std::move(newBodyAtom));
 
        // New relation I' should be input, original should not
        std::set<const Directive*> iosToDelete;
        std::set<Own<Directive>> iosToAdd;
        for (const auto* io : program.getDirectives()) {
            if (io->getQualifiedName() == relName && io->getType() == ast::DirectiveType::input) {
                // New relation inherits the old input rules
                auto newIO = souffle::clone(io);
                newIO->setQualifiedName(newRelName);
                iosToAdd.insert(std::move(newIO));
 
                // Original no longer has them
                iosToDelete.insert(io);
            }
        }
        for (const auto* io : iosToDelete) {
            program.removeDirective(io);
        }
        for (auto& io : iosToAdd) {
            program.addDirective(souffle::clone(io));
        }
 
        // Add in the new relation and the copy clause
        program.addRelation(std::move(newRelation));
        program.addClause(std::move(newClause));
    }
 
    return !relationsToSplit.empty();
}
 
bool NormaliseDatabaseTransformer::extractIDB(TranslationUnit& translationUnit) {
    Program& program = translationUnit.getProgram();
    const auto& ioTypes = *translationUnit.getAnalysis<analysis::IOTypeAnalysis>();
 
    // Helper method to check if an input relation has no associated rules

References rel().

Here is the call graph for this function:

querifyOutputRelations()

bool souffle::ast::transform::NormaliseDatabaseTransformer::querifyOutputRelations ( TranslationUnit &  translationUnit )

staticprivate

Extracts output relations into separate simple query relations, so that they are unused in any other rules.

Programs will only contain output relations which: (1) have exactly one rule defining them (2) do not appear in other rules

Definition at line 443 of file MagicSet.cpp.

                                : program.getClauses()) {
            // Check if the relation is used in the body of any rules
            visitDepthFirst(clause->getBodyLiterals(), [&](const Atom& atom) {
                if (atom.getQualifiedName() == rel->getQualifiedName()) {
                    strictlyOutput = false;
                }
            });
 
            // Keep track of number of rules defining the relation
            if (clause->getHead()->getQualifiedName() == rel->getQualifiedName()) {
                ruleCount++;
            }
        }
 
        return strictlyOutput && ruleCount <= 1;
    };
 
    // Get all output relations that need to be normalised
    const auto& ioTypes = *translationUnit.getAnalysis<analysis::IOTypeAnalysis>();
    std::set<QualifiedName> outputRelationNames;
    for (auto* rel : program.getRelations()) {
        if ((ioTypes.isOutput(rel) || ioTypes.isPrintSize(rel)) && !isStrictlyOutput(rel)) {
            assert(!ioTypes.isInput(rel) && "output relations should not be input at this stage");
            outputRelationNames.insert(rel->getQualifiedName());
        }
    }
 
    // Add a new intermediate non-output relation for each
    // These will cover relation appearances in intermediate rules
    std::map<QualifiedName, QualifiedName> outputToIntermediate;
    for (const auto& outputRelationName : outputRelationNames) {
        // Give it a unique name
        QualifiedName intermediateName(outputRelationName);
        intermediateName.prepend("@interm_out");
        outputToIntermediate[outputRelationName] = intermediateName;
 
        // Add the relation
        auto intermediateRelation = souffle::clone(getRelation(program, outputRelationName));
        intermediateRelation->setQualifiedName(intermediateName);
        program.addRelation(std::move(intermediateRelation));
    }
 
    // Rename them systematically
    renameAtoms(program, outputToIntermediate);
 
    // Add the rule I <- I'
    for (const auto& outputRelationName : outputRelationNames) {
        auto queryHead = mk<Atom>(outputRelationName);
        auto queryLiteral = mk<Atom>(outputToIntermediate.at(outputRelationName));
 
        // Give them identical arguments
        const auto* outputRelation = getRelation(program, outputRelationName);
        for (size_t i = 0; i < outputRelation->getArity(); i++) {
            std::stringstream var;
            var << "@query_x" << i;
            queryHead->addArgument(mk<ast::Variable>(var.str()));
            queryLiteral->addArgument(mk<ast::Variable>(var.str()));
        }
        auto query = mk<Clause>(std::move(queryHead));
        query->addToBody(std::move(queryLiteral));
        program.addClause(std::move(query));
    }
 
    return !outputRelationNames.empty();
}
 
bool NormaliseDatabaseTransformer::normaliseArguments(TranslationUnit& translationUnit) {
    Program& program = translationUnit.getProgram();
 
    // Replace all non-variable-arguments nested inside the node with named variables
    // Also, keeps track of constraints to add to keep the clause semantically equivalent

References souffle::ast::visitDepthFirst().

Here is the call graph for this function:

transform()

bool souffle::ast::transform::NormaliseDatabaseTransformer::transform ( TranslationUnit &  translationUnit )

overrideprivatevirtual

(1) Partition input and output relations

(2) Separate the IDB from the EDB

(3) Normalise arguments within each clause

(4) Querify output relations

Implements souffle::ast::transform::Transformer.

Definition at line 290 of file MagicSet.cpp.

                                                                               {
    Program& program = translationUnit.getProgram();
    const auto& ioTypes = *translationUnit.getAnalysis<analysis::IOTypeAnalysis>();
 
    // Get all relations that are both input and output

---

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

• ast/transform/MagicSet.h
• ast/transform/MagicSet.cpp