souffle  2.0.2-371-g6315b36
ResolveAliases.cpp
Go to the documentation of this file.
1 /*
2  * Souffle - A Datalog Compiler
3  * Copyright (c) 2018, The Souffle Developers. All rights reserved.
4  * Licensed under the Universal Permissive License v 1.0 as shown at:
5  * - https://opensource.org/licenses/UPL
6  * - <souffle root>/licenses/SOUFFLE-UPL.txt
7  */
8 
9 /************************************************************************
10  *
11  * @file ResolveAliases.cpp
12  *
13  * Define classes and functionality related to the ResolveAliases
14  * transformer.
15  *
16  ***********************************************************************/
17 
19 #include "ast/Argument.h"
20 #include "ast/Atom.h"
21 #include "ast/BinaryConstraint.h"
22 #include "ast/Clause.h"
23 #include "ast/Functor.h"
24 #include "ast/Literal.h"
25 #include "ast/Node.h"
26 #include "ast/Program.h"
27 #include "ast/RecordInit.h"
28 #include "ast/Relation.h"
29 #include "ast/TranslationUnit.h"
30 #include "ast/Variable.h"
31 #include "ast/analysis/Functor.h"
32 #include "ast/utility/NodeMapper.h"
33 #include "ast/utility/Utils.h"
34 #include "ast/utility/Visitor.h"
40 #include <algorithm>
41 #include <cassert>
42 #include <cstddef>
43 #include <map>
44 #include <memory>
45 #include <ostream>
46 #include <set>
47 #include <string>
48 #include <type_traits>
49 #include <utility>
50 #include <vector>
51 
52 namespace souffle::ast::transform {
53 
54 namespace {
55 
56 /**
57  * A utility class for the unification process required to eliminate aliases.
58  * A substitution maps variables to terms and can be applied as a transformation
59  * to Arguments.
60  */
61 class Substitution {
62  // map type used for internally storing var->term mappings
63  // - note: variables are identified by their names
64  using map_t = std::map<std::string, Own<Argument>>;
65 
66  // the mapping of variables to terms
67  map_t varToTerm;
68 
69 public:
70  // -- Constructors/Destructors --
71 
72  Substitution() = default;
73 
74  Substitution(const std::string& var, const Argument* arg) {
75  varToTerm.insert(std::make_pair(var, souffle::clone(arg)));
76  }
77 
78  ~Substitution() = default;
79 
80  /**
81  * Applies this substitution to the given argument and returns a pointer
82  * to the modified argument.
83  *
84  * @param node the node to be transformed
85  * @return a pointer to the modified or replaced node
86  */
87  Own<Node> operator()(Own<Node> node) const {
88  // create a substitution mapper
89  struct M : public NodeMapper {
90  const map_t& map;
91 
92  M(const map_t& map) : map(map) {}
93 
94  using NodeMapper::operator();
95 
96  Own<Node> operator()(Own<Node> node) const override {
97  // see whether it is a variable to be substituted
98  if (auto var = dynamic_cast<ast::Variable*>(node.get())) {
99  auto pos = map.find(var->getName());
100  if (pos != map.end()) {
101  return souffle::clone(pos->second);
102  }
103  }
104 
105  // otherwise, apply the mapper recursively
106  node->apply(*this);
107  return node;
108  }
109  };
110 
111  // apply the mapper
112  return M(varToTerm)(std::move(node));
113  }
114 
115  /**
116  * A generic, type consistent wrapper of the transformation operation above.
117  */
118  template <typename T>
119  Own<T> operator()(Own<T> node) const {
120  Own<Node> resPtr = (*this)(Own<Node>(node.release()));
121  assert(isA<T>(resPtr.get()) && "Invalid node type mapping.");
122  return Own<T>(dynamic_cast<T*>(resPtr.release()));
123  }
124 
125  /**
126  * Appends the given substitution s to this substitution t such that the
127  * result t' is s composed with t (s o t).
128  * i.e.,
129  * - if t(x) = y, then t'(x) = s(y)
130  * - if s(x) = y, and x is not mapped by t, then t'(x) = y
131  */
132  void append(const Substitution& sub) {
133  // apply substitution on the rhs of all current mappings
134  for (auto& pair : varToTerm) {
135  pair.second = sub(std::move(pair.second));
136  }
137 
138  // append unseen variables to the end
139  for (const auto& pair : sub.varToTerm) {
140  if (varToTerm.find(pair.first) == varToTerm.end()) {
141  // not seen yet, add it in
142  varToTerm.insert(std::make_pair(pair.first, souffle::clone(pair.second)));
143  }
144  }
145  }
146 
147  /** A print function (for debugging) */
148  void print(std::ostream& out) const {
149  out << "{"
150  << join(varToTerm, ",",
151  [](std::ostream& out, const std::pair<const std::string, Own<Argument>>& cur) {
152  out << cur.first << " -> " << *cur.second;
153  })
154  << "}";
155  }
156 
157  friend std::ostream& operator<<(std::ostream& out, const Substitution& s) __attribute__((unused)) {
158  s.print(out);
159  return out;
160  }
161 };
162 
163 /**
164  * An equality constraint between two Arguments utilised by the unification
165  * algorithm required by the alias resolution.
166  */
167 class Equation {
168 public:
169  // the two terms to be equivalent
170  Own<Argument> lhs;
171  Own<Argument> rhs;
172 
173  Equation(const Argument& lhs, const Argument& rhs)
174  : lhs(souffle::clone(&lhs)), rhs(souffle::clone(&rhs)) {}
175 
176  Equation(const Argument* lhs, const Argument* rhs) : lhs(souffle::clone(lhs)), rhs(souffle::clone(rhs)) {}
177 
178  Equation(const Equation& other) : lhs(souffle::clone(other.lhs)), rhs(souffle::clone(other.rhs)) {}
179 
180  Equation(Equation&& other) = default;
181 
182  ~Equation() = default;
183 
184  /**
185  * Applies the given substitution to both sides of the equation.
186  */
187  void apply(const Substitution& sub) {
188  lhs = sub(std::move(lhs));
189  rhs = sub(std::move(rhs));
190  }
191 
192  /**
193  * Enables equations to be printed (for debugging)
194  */
195  void print(std::ostream& out) const {
196  out << *lhs << " = " << *rhs;
197  }
198 
199  friend std::ostream& operator<<(std::ostream& out, const Equation& e) __attribute__((unused)) {
200  e.print(out);
201  return out;
202  }
203 };
204 
205 } // namespace
206 
207 Own<Clause> ResolveAliasesTransformer::resolveAliases(const Clause& clause) {
208  // -- utilities --
209 
210  // tests whether something is a variable
211  auto isVar = [&](const Argument& arg) { return isA<ast::Variable>(&arg); };
212 
213  // tests whether something is a record
214  auto isRec = [&](const Argument& arg) { return isA<RecordInit>(&arg); };
215 
216  // tests whether something is a multi-result functor
217  auto isMultiResultFunctor = [&](const Argument& arg) {
218  const auto* inf = dynamic_cast<const IntrinsicFunctor*>(&arg);
219  if (inf == nullptr) return false;
221  };
222 
223  // tests whether a value `a` occurs in a term `b`
224  auto occurs = [](const Argument& a, const Argument& b) {
225  bool res = false;
226  visitDepthFirst(b, [&](const Argument& arg) { res = (res || (arg == a)); });
227  return res;
228  };
229 
230  // variables appearing as functorless arguments in atoms or records should not
231  // be resolved
232  std::set<std::string> baseGroundedVariables;
233  for (const auto* atom : getBodyLiterals<Atom>(clause)) {
234  for (const Argument* arg : atom->getArguments()) {
235  if (const auto* var = dynamic_cast<const ast::Variable*>(arg)) {
236  baseGroundedVariables.insert(var->getName());
237  }
238  }
239  visitDepthFirst(*atom, [&](const RecordInit& rec) {
240  for (const Argument* arg : rec.getArguments()) {
241  if (const auto* var = dynamic_cast<const ast::Variable*>(arg)) {
242  baseGroundedVariables.insert(var->getName());
243  }
244  }
245  });
246  }
247 
248  // I) extract equations
249  std::vector<Equation> equations;
250  visitDepthFirst(clause, [&](const BinaryConstraint& constraint) {
251  if (isEqConstraint(constraint.getBaseOperator())) {
252  equations.push_back(Equation(constraint.getLHS(), constraint.getRHS()));
253  }
254  });
255 
256  // II) compute unifying substitution
257  Substitution substitution;
258 
259  // a utility for processing newly identified mappings
260  auto newMapping = [&](const std::string& var, const Argument* term) {
261  // found a new substitution
262  Substitution newMapping(var, term);
263 
264  // apply substitution to all remaining equations
265  for (auto& equation : equations) {
266  equation.apply(newMapping);
267  }
268 
269  // add mapping v -> t to substitution
270  substitution.append(newMapping);
271  };
272 
273  while (!equations.empty()) {
274  // get next equation to compute
275  Equation equation = equations.back();
276  equations.pop_back();
277 
278  // shortcuts for left/right
279  const Argument& lhs = *equation.lhs;
280  const Argument& rhs = *equation.rhs;
281 
282  // #1: t = t => skip
283  if (lhs == rhs) {
284  continue;
285  }
286 
287  // #2: [..] = [..] => decompose
288  if (isRec(lhs) && isRec(rhs)) {
289  // get arguments
290  const auto& lhs_args = static_cast<const RecordInit&>(lhs).getArguments();
291  const auto& rhs_args = static_cast<const RecordInit&>(rhs).getArguments();
292 
293  // make sure sizes are identical
294  assert(lhs_args.size() == rhs_args.size() && "Record lengths not equal");
295 
296  // create new equalities
297  for (size_t i = 0; i < lhs_args.size(); i++) {
298  equations.push_back(Equation(lhs_args[i], rhs_args[i]));
299  }
300 
301  continue;
302  }
303 
304  // #3: neither is a variable => skip
305  if (!isVar(lhs) && !isVar(rhs)) {
306  continue;
307  }
308 
309  // #4: v = w => add mapping
310  if (isVar(lhs) && isVar(rhs)) {
311  auto& var = static_cast<const ast::Variable&>(lhs);
312  newMapping(var.getName(), &rhs);
313  continue;
314  }
315 
316  // #5: t = v => swap
317  if (!isVar(lhs)) {
318  equations.push_back(Equation(rhs, lhs));
319  continue;
320  }
321 
322  // now we know lhs is a variable
323  assert(isVar(lhs));
324 
325  // therefore, we have v = t
326  const auto& v = static_cast<const ast::Variable&>(lhs);
327  const Argument& t = rhs;
328 
329  // #6: t is a multi-result functor => skip
330  if (isMultiResultFunctor(t)) {
331  continue;
332  }
333 
334  // #7: v occurs in t => skip
335  if (occurs(v, t)) {
336  continue;
337  }
338 
339  assert(!occurs(v, t));
340 
341  // #8: t is a record => add mapping
342  if (isRec(t)) {
343  newMapping(v.getName(), &t);
344  continue;
345  }
346 
347  // #9: v is already grounded => skip
348  auto pos = baseGroundedVariables.find(v.getName());
349  if (pos != baseGroundedVariables.end()) {
350  continue;
351  }
352 
353  // add new mapping
354  newMapping(v.getName(), &t);
355  }
356 
357  // III) compute resulting clause
358  return substitution(souffle::clone(&clause));
359 }
360 
361 Own<Clause> ResolveAliasesTransformer::removeTrivialEquality(const Clause& clause) {
362  Own<Clause> res(cloneHead(&clause));
363 
364  // add all literals, except filtering out t = t constraints
365  for (Literal* literal : clause.getBodyLiterals()) {
366  if (auto* constraint = dynamic_cast<BinaryConstraint*>(literal)) {
367  // TODO: don't filter out `FEQ` constraints, since `x = x` can fail when `x` is a NaN
368  if (isEqConstraint(constraint->getBaseOperator())) {
369  if (*constraint->getLHS() == *constraint->getRHS()) {
370  continue; // skip this one
371  }
372  }
373  }
374 
375  res->addToBody(souffle::clone(literal));
376  }
377 
378  // done
379  return res;
380 }
381 
382 Own<Clause> ResolveAliasesTransformer::removeComplexTermsInAtoms(const Clause& clause) {
383  Own<Clause> res(clause.clone());
384 
385  // get list of atoms
386  std::vector<Atom*> atoms = getBodyLiterals<Atom>(*res);
387 
388  // find all functors in atoms
389  std::vector<const Argument*> terms;
390  for (const Atom* atom : atoms) {
391  for (const Argument* arg : atom->getArguments()) {
392  // ignore if not a functor
393  if (!isA<Functor>(arg)) {
394  continue;
395  }
396 
397  // add this functor if not seen yet
398  if (!any_of(terms, [&](const Argument* cur) { return *cur == *arg; })) {
399  terms.push_back(arg);
400  }
401  }
402  }
403 
404  // find all functors in records too
405  visitDepthFirst(atoms, [&](const RecordInit& rec) {
406  for (const Argument* arg : rec.getArguments()) {
407  // ignore if not a functor
408  if (!isA<Functor>(arg)) {
409  continue;
410  }
411 
412  // add this functor if not seen yet
413  if (!any_of(terms, [&](const Argument* cur) { return *cur == *arg; })) {
414  terms.push_back(arg);
415  }
416  }
417  });
418 
419  // substitute them with new variables (a real map would compare pointers)
420  using substitution_map = std::vector<std::pair<Own<Argument>, Own<ast::Variable>>>;
421  substitution_map termToVar;
422 
423  static int varCounter = 0;
424  for (const Argument* arg : terms) {
425  // create a new mapping for this term
426  auto term = souffle::clone(arg);
427  auto newVariable = mk<ast::Variable>(" _tmp_" + toString(varCounter++));
428  termToVar.push_back(std::make_pair(std::move(term), std::move(newVariable)));
429  }
430 
431  // apply mapping to replace the terms with the variables
432  struct Update : public NodeMapper {
433  const substitution_map& map;
434 
435  Update(const substitution_map& map) : map(map) {}
436 
437  Own<Node> operator()(Own<Node> node) const override {
438  // check whether node needs to be replaced
439  for (const auto& pair : map) {
440  auto& term = pair.first;
441  auto& variable = pair.second;
442 
443  if (*term == *node) {
444  return souffle::clone(variable);
445  }
446  }
447 
448  // continue recursively
449  node->apply(*this);
450  return node;
451  }
452  };
453 
454  // update atoms
455  Update update(termToVar);
456  for (Atom* atom : atoms) {
457  atom->apply(update);
458  }
459 
460  // add the necessary variable constraints to the clause
461  for (const auto& pair : termToVar) {
462  auto& term = pair.first;
463  auto& variable = pair.second;
464 
465  res->addToBody(
466  mk<BinaryConstraint>(BinaryConstraintOp::EQ, souffle::clone(variable), souffle::clone(term)));
467  }
468 
469  return res;
470 }
471 
472 bool ResolveAliasesTransformer::transform(TranslationUnit& translationUnit) {
473  bool changed = false;
474  Program& program = translationUnit.getProgram();
475 
476  // get all clauses
477  std::vector<const Clause*> clauses;
478  visitDepthFirst(program, [&](const Relation& rel) {
479  for (const auto& clause : getClauses(program, rel)) {
480  clauses.push_back(clause);
481  }
482  });
483 
484  // clean all clauses
485  for (const Clause* clause : clauses) {
486  // -- Step 1 --
487  // get rid of aliases
488  Own<Clause> noAlias = resolveAliases(*clause);
489 
490  // clean up equalities
491  Own<Clause> cleaned = removeTrivialEquality(*noAlias);
492 
493  // -- Step 2 --
494  // restore simple terms in atoms
495  Own<Clause> normalised = removeComplexTermsInAtoms(*cleaned);
496 
497  // swap if changed
498  if (*normalised != *clause) {
499  changed = true;
500  program.removeClause(clause);
501  program.addClause(std::move(normalised));
502  }
503  }
504 
505  return changed;
506 }
507 
508 } // namespace souffle::ast::transform
souffle::ast::cloneHead
Clause * cloneHead(const Clause *clause)
Returns a clause which contains head of the given clause.
Definition: Utils.cpp:254
BinaryConstraintOps.h
souffle::ast::analysis::FunctorAnalysis::isMultiResult
static bool isMultiResult(const Functor &functor)
Definition: Functor.cpp:53
TranslationUnit.h
Functor.h
souffle::ast::analysis::sub
std::shared_ptr< Constraint< Var > > sub(const Var &a, const Var &b, const std::string &symbol="⊑")
A generic factory for constraints of the form.
Definition: ConstraintSystem.h:228
e
l j a showGridBackground &&c b raw series this eventEmitter e
Definition: htmlJsChartistMin.h:15
souffle::Own
std::unique_ptr< A > Own
Definition: ContainerUtil.h:42
souffle::BinaryConstraintOp::EQ
@ EQ
souffle::map
auto map(const std::vector< A > &xs, F &&f)
Applies a function to each element of a vector and returns the results.
Definition: ContainerUtil.h:158
MiscUtil.h
souffle::ast::Clause
Intermediate representation of a horn clause.
Definition: Clause.h:51
Relation.h
rhs
Own< Argument > rhs
Definition: ResolveAliases.cpp:185
souffle::ast::Atom
An atom class.
Definition: Atom.h:51
Utils.h
NodeMapper.h
souffle::ast::Argument
An abstract class for arguments.
Definition: Argument.h:33
lhs
Own< Argument > lhs
Definition: ResolveAliases.cpp:184
souffle::toString
const std::string & toString(const std::string &str)
A generic function converting strings into strings (trivial case).
Definition: StringUtil.h:234
Argument.h
souffle::clone
auto clone(const std::vector< A * > &xs)
Definition: ContainerUtil.h:172
i
size_t i
Definition: json11.h:663
souffle::join
detail::joined_sequence< Iter, Printer > join(const Iter &a, const Iter &b, const std::string &sep, const Printer &p)
Creates an object to be forwarded to some output stream for printing sequences of elements interspers...
Definition: StreamUtil.h:175
clauses
std::vector< Own< Clause > > clauses
Definition: ComponentInstantiation.cpp:67
StringUtil.h
souffle::ast::IntrinsicFunctor
Intrinsic Functor class for functors are in-built.
Definition: IntrinsicFunctor.h:47
Atom.h
souffle::any_of
bool any_of(const Container &c, UnaryPredicate p)
A generic test checking whether any elements within a container satisfy a certain predicate.
Definition: FunctionalUtil.h:124
Literal.h
souffle::ast::operator<<
std::ostream & operator<<(std::ostream &os, DirectiveType e)
Definition: Directive.h:40
souffle::ast::transform
Definition: Program.h:45
souffle::ast::Term::getArguments
std::vector< Argument * > getArguments() const
Get arguments.
Definition: Term.h:56
souffle::ast::getClauses
std::vector< Clause * > getClauses(const Program &program, const QualifiedName &relationName)
Returns a vector of clauses in the program describing the relation with the given name.
Definition: Utils.cpp:77
souffle::isEqConstraint
bool isEqConstraint(const BinaryConstraintOp constraintOp)
Definition: BinaryConstraintOps.h:124
Node.h
Functor.h
b
l j a showGridBackground &&c b raw series this eventEmitter b
Definition: htmlJsChartistMin.h:15
Program.h
StreamUtil.h
Visitor.h
Clause.h
souffle
Definition: AggregateOp.h:25
souffle::ast::transform::ResolveAliasesTransformer::resolveAliases
static Own< Clause > resolveAliases(const Clause &clause)
Converts the given clause into a version without variables aliasing grounded variables.
Definition: ResolveAliases.cpp:214
BinaryConstraint.h
souffle::ast::visitDepthFirst
void visitDepthFirst(const Node &root, Visitor< R, Ps... > &visitor, Args &... args)
A utility function visiting all nodes within the ast rooted by the given node recursively in a depth-...
Definition: Visitor.h:273
FunctionalUtil.h
rel
void rel(size_t limit, bool showLimit=true)
Definition: Tui.h:1086
RecordInit.h
souffle::ast::RecordInit
Defines a record initialization class.
Definition: RecordInit.h:42
varToTerm
map_t varToTerm
Definition: ResolveAliases.cpp:88
Variable.h
ResolveAliases.h