Transformation pass to replaces copy of relations by their origin. More...

#include <RemoveRelationCopies.h>

Inheritance diagram for souffle::ast::transform::RemoveRelationCopiesTransformer:

Collaboration diagram for souffle::ast::transform::RemoveRelationCopiesTransformer:

Public Member Functions
RemoveRelationCopiesTransformer *	clone () const override

std::string	getName () const override

Public Member Functions inherited from souffle::ast::transform::Transformer
bool	apply (TranslationUnit &translationUnit)

virtual	~Transformer ()=default

Static Public Member Functions
static bool	removeRelationCopies (TranslationUnit &translationUnit)
	Replaces copies of relations by their origin in the given program. More...

Private Member Functions
bool	transform (TranslationUnit &translationUnit) override

Detailed Description

Transformation pass to replaces copy of relations by their origin.

For instance, if a relation r is defined by

 r(X,Y) :- s(X,Y)

and no other clause, all occurrences of r will be replaced by s.

Definition at line 35 of file RemoveRelationCopies.h.

Member Function Documentation

◆ clone()

RemoveRelationCopiesTransformer* souffle::ast::transform::RemoveRelationCopiesTransformer::clone ( ) const

inlineoverridevirtual

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

Definition at line 53 of file RemoveRelationCopies.h.

◆ getName()

std::string souffle::ast::transform::RemoveRelationCopiesTransformer::getName ( ) const

inlineoverridevirtual

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

Definition at line 41 of file RemoveRelationCopies.h.

45 {

◆ removeRelationCopies()

bool souffle::ast::transform::RemoveRelationCopiesTransformer::removeRelationCopies ( TranslationUnit & translationUnit )

static

Replaces copies of relations by their origin in the given program.

Parameters

program the program to be processed

Returns: whether the program was modified

Definition at line 42 of file RemoveRelationCopies.cpp.

                        : program.getRelations()) {
         const auto& clauses = getClauses(program, *rel);
         if (!ioType->isIO(rel) && clauses.size() == 1u) {
             // .. of shape r(x,y,..) :- s(x,y,..)
             Clause* cl = clauses[0];
             std::vector<Atom*> bodyAtoms = getBodyLiterals<Atom>(*cl);
             if (!isFact(*cl) && cl->getBodyLiterals().size() == 1u && bodyAtoms.size() == 1u) {
                 Atom* atom = bodyAtoms[0];
                 if (equal_targets(cl->getHead()->getArguments(), atom->getArguments())) {
                     // Requirements:
                     // 1) (checked) It is a rule with exactly one body.
                     // 3) (checked) The body consists of an atom.
                     // 4) (checked) The atom's arguments must be identical to the rule's head.
                     // 5) (pending) The rules's head must consist only of either:
                     //  5a) Variables
                     //  5b) Records unpacked into variables
                     // 6) (pending) Each variable must have a distinct name.
                     bool onlyDistinctHeadVars = true;
                     std::set<std::string> headVars;
  
                     auto args = cl->getHead()->getArguments();
                     while (onlyDistinctHeadVars && !args.empty()) {
                         const auto cur = args.back();
                         args.pop_back();
  
                         if (auto var = dynamic_cast<const ast::Variable*>(cur)) {
                             onlyDistinctHeadVars &= headVars.insert(var->getName()).second;
                         } else if (auto init = dynamic_cast<const RecordInit*>(cur)) {
                             // records are decomposed and their arguments are checked
                             for (auto rec_arg : init->getArguments()) {
                                 args.push_back(rec_arg);
                             }
                         } else {
                             onlyDistinctHeadVars = false;
                         }
                     }
  
                     if (onlyDistinctHeadVars) {
                         // all arguments are either distinct variables or records unpacked into distinct
                         // variables
                         isDirectAliasOf[cl->getHead()->getQualifiedName()] = atom->getQualifiedName();
                     }
                 }
             }
         }
     }
  
     // map each relation to its ultimate alias (could be transitive)
     alias_map isAliasOf;
  
     // track any copy cycles; cyclic rules are effectively empty
     std::set<QualifiedName> cycle_reps;
  
     for (std::pair<QualifiedName, QualifiedName> cur : isDirectAliasOf) {
         // compute replacement
  
         std::set<QualifiedName> visited;
         visited.insert(cur.first);
         visited.insert(cur.second);
  
         auto pos = isDirectAliasOf.find(cur.second);
         while (pos != isDirectAliasOf.end()) {
             if (visited.count(pos->second) != 0u) {
                 cycle_reps.insert(cur.second);
                 break;
             }
             cur.second = pos->second;
             pos = isDirectAliasOf.find(cur.second);
         }
         isAliasOf[cur.first] = cur.second;
     }
  
     if (isAliasOf.empty()) {
         return false;
     }
  
     // replace usage of relations according to alias map
     visitDepthFirst(program, [&](const Atom& atom) {
         auto pos = isAliasOf.find(atom.getQualifiedName());
         if (pos != isAliasOf.end()) {
             const_cast<Atom&>(atom).setQualifiedName(pos->second);
         }
     });
  
     // break remaining cycles
     for (const auto& rep : cycle_reps) {
         const auto& rel = *getRelation(program, rep);
         const auto& clauses = getClauses(program, rel);
         assert(clauses.size() == 1u && "unexpected number of clauses in relation");
         program.removeClause(clauses[0]);
     }
  
     // remove unused relations
     for (const auto& cur : isAliasOf) {
         if (cycle_reps.count(cur.first) == 0u) {
             removeRelation(translationUnit, getRelation(program, cur.first)->getQualifiedName());
         }
     }
  
     return true;
 }
  
 }  // namespace souffle::ast::transform