souffle  2.0.2-371-g6315b36
HoistConditions.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 HoistConditions.cpp
12  *
13  ***********************************************************************/
14 
16 #include "ram/Condition.h"
17 #include "ram/Node.h"
18 #include "ram/Operation.h"
19 #include "ram/Program.h"
20 #include "ram/Statement.h"
21 #include "ram/utility/Visitor.h"
23 #include <functional>
24 #include <memory>
25 #include <utility>
26 #include <vector>
27 
28 namespace souffle::ram::transform {
29 
30 bool HoistConditionsTransformer::hoistConditions(Program& program) {
31  bool changed = false;
32 
33  // helper for collecting conditions from filter operations
34  auto addCondition = [](Own<Condition> condition, Own<Condition> c) -> Own<Condition> {
35  if (condition == nullptr) {
36  return c;
37  } else {
38  return mk<Conjunction>(std::move(condition), std::move(c));
39  }
40  };
41 
42  // hoist conditions to the most outer scope if they
43  // don't depend on TupleOperations
44  visitDepthFirst(program, [&](const Query& query) {
45  Own<Condition> newCondition;
46  std::function<Own<Node>(Own<Node>)> filterRewriter = [&](Own<Node> node) -> Own<Node> {
47  if (auto* filter = dynamic_cast<Filter*>(node.get())) {
48  const Condition& condition = filter->getCondition();
49  // if filter condition is independent of any TupleOperation,
50  // delete the filter operation and collect condition
51  if (rla->getLevel(&condition) == -1) {
52  changed = true;
53  newCondition = addCondition(std::move(newCondition), souffle::clone(&condition));
54  node->apply(makeLambdaRamMapper(filterRewriter));
55  return souffle::clone(&filter->getOperation());
56  }
57  }
58  node->apply(makeLambdaRamMapper(filterRewriter));
59  return node;
60  };
61  auto* mQuery = const_cast<Query*>(&query);
62  mQuery->apply(makeLambdaRamMapper(filterRewriter));
63  if (newCondition != nullptr) {
64  // insert new filter operation at outer-most level of the query
65  changed = true;
66  auto* nestedOp = const_cast<Operation*>(&mQuery->getOperation());
67  mQuery->rewrite(nestedOp, mk<Filter>(std::move(newCondition), souffle::clone(nestedOp)));
68  }
69  });
70 
71  // hoist conditions for each TupleOperation operation
72  visitDepthFirst(program, [&](const TupleOperation& search) {
73  Own<Condition> newCondition;
74  std::function<Own<Node>(Own<Node>)> filterRewriter = [&](Own<Node> node) -> Own<Node> {
75  if (auto* filter = dynamic_cast<Filter*>(node.get())) {
76  const Condition& condition = filter->getCondition();
77  // if filter condition matches level of TupleOperation,
78  // delete the filter operation and collect condition
79  if (rla->getLevel(&condition) == search.getTupleId()) {
80  changed = true;
81  newCondition = addCondition(std::move(newCondition), souffle::clone(&condition));
82  node->apply(makeLambdaRamMapper(filterRewriter));
83  return souffle::clone(&filter->getOperation());
84  }
85  }
86  node->apply(makeLambdaRamMapper(filterRewriter));
87  return node;
88  };
89  auto* tupleOp = const_cast<TupleOperation*>(&search);
90  tupleOp->apply(makeLambdaRamMapper(filterRewriter));
91  if (newCondition != nullptr) {
92  // insert new filter operation after the search operation
93  changed = true;
94  tupleOp->rewrite(&tupleOp->getOperation(),
95  mk<Filter>(std::move(newCondition), souffle::clone(&tupleOp->getOperation())));
96  }
97  });
98  return changed;
99 }
100 
101 } // namespace souffle::ram::transform
souffle::ram::transform
Definition: ChoiceConversion.cpp:30
souffle::ram::analysis::LevelAnalysis::getLevel
int getLevel(const Node *value) const
Get level of a RAM expression/condition.
Definition: Level.cpp:64
souffle::ram::transform::HoistConditionsTransformer::rla
analysis::LevelAnalysis * rla
Definition: HoistConditions.h:88
souffle::ram::Query
A relational algebra query.
Definition: Query.h:50
souffle::Own
std::unique_ptr< A > Own
Definition: ContainerUtil.h:42
MiscUtil.h
souffle::ram::Condition
Abstract class for conditions and boolean values in RAM.
Definition: Condition.h:35
Program.h
souffle::ram::Filter
Checks whether a given condition holds.
Definition: Filter.h:49
Visitor.h
souffle::clone
auto clone(const std::vector< A * > &xs)
Definition: ContainerUtil.h:172
souffle::filter
std::vector< A > filter(std::vector< A > xs, F &&f)
Filter a vector to include certain elements.
Definition: FunctionalUtil.h:155
Condition.h
HoistConditions.h
souffle::ram::transform::HoistConditionsTransformer::hoistConditions
bool hoistConditions(Program &program)
Hoist filter operations.
Definition: HoistConditions.cpp:34
Node.h
Operation.h
Statement.h
souffle::ram::visitDepthFirst
void visitDepthFirst(const Node &root, Visitor< R, Ps... > &visitor, Args &... args)
A utility function visiting all nodes within the RAM fragments rooted by the given node recursively i...
Definition: Visitor.h:357
souffle::ram::makeLambdaRamMapper
LambdaNodeMapper< Lambda > makeLambdaRamMapper(const Lambda &lambda)
Creates a node mapper based on a corresponding lambda expression.
Definition: LambdaNodeMapper.h:67