diff options
author | Kristóf Marussy <kristof@marussy.com> | 2023-07-10 18:38:11 +0200 |
---|---|---|
committer | Kristóf Marussy <kristof@marussy.com> | 2023-07-10 20:21:01 +0200 |
commit | 9666818c58bb4c30ef6b0c88cc680bc559b123c6 (patch) | |
tree | e49a67fd85fcf8a8ac679553e47aeeec9b729f0b /subprojects/store-query | |
parent | refactor: enable data variable unification (diff) | |
download | refinery-9666818c58bb4c30ef6b0c88cc680bc559b123c6.tar.gz refinery-9666818c58bb4c30ef6b0c88cc680bc559b123c6.tar.zst refinery-9666818c58bb4c30ef6b0c88cc680bc559b123c6.zip |
feat: DNF rewriting
* DuplicateDnfRewriter replaces DNF with their canonical
representatives
* ClauseInputParameterResolver removes input parameters by demand set
transformation
* CompositeRewriter for rewriter stacks
Diffstat (limited to 'subprojects/store-query')
19 files changed, 875 insertions, 4 deletions
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/Dnf.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/Dnf.java index e3c8924b..55f1aae5 100644 --- a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/Dnf.java +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/Dnf.java | |||
@@ -215,6 +215,13 @@ public final class Dnf implements Constraint { | |||
215 | return new DnfBuilder(name); | 215 | return new DnfBuilder(name); |
216 | } | 216 | } |
217 | 217 | ||
218 | public static DnfBuilder builderFrom(Dnf original) { | ||
219 | var builder = builder(original.name()); | ||
220 | builder.symbolicParameters(original.getSymbolicParameters()); | ||
221 | builder.functionalDependencies(original.getFunctionalDependencies()); | ||
222 | return builder; | ||
223 | } | ||
224 | |||
218 | public static Dnf of(Consumer<DnfBuilder> callback) { | 225 | public static Dnf of(Consumer<DnfBuilder> callback) { |
219 | return of(null, callback); | 226 | return of(null, callback); |
220 | } | 227 | } |
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/DnfBuilder.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/DnfBuilder.java index 3d3b5198..0538427f 100644 --- a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/DnfBuilder.java +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/DnfBuilder.java | |||
@@ -6,6 +6,9 @@ | |||
6 | package tools.refinery.store.query.dnf; | 6 | package tools.refinery.store.query.dnf; |
7 | 7 | ||
8 | import tools.refinery.store.query.dnf.callback.*; | 8 | import tools.refinery.store.query.dnf.callback.*; |
9 | import tools.refinery.store.query.equality.DnfEqualityChecker; | ||
10 | import tools.refinery.store.query.equality.SubstitutingLiteralEqualityHelper; | ||
11 | import tools.refinery.store.query.equality.SubstitutingLiteralHashCodeHelper; | ||
9 | import tools.refinery.store.query.literal.Literal; | 12 | import tools.refinery.store.query.literal.Literal; |
10 | import tools.refinery.store.query.term.*; | 13 | import tools.refinery.store.query.term.*; |
11 | 14 | ||
@@ -223,12 +226,12 @@ public final class DnfBuilder { | |||
223 | 226 | ||
224 | private List<DnfClause> postProcessClauses() { | 227 | private List<DnfClause> postProcessClauses() { |
225 | var parameterInfoMap = getParameterInfoMap(); | 228 | var parameterInfoMap = getParameterInfoMap(); |
226 | var postProcessedClauses = new ArrayList<DnfClause>(clauses.size()); | 229 | var postProcessedClauses = new LinkedHashSet<CanonicalClause>(clauses.size()); |
227 | for (var literals : clauses) { | 230 | for (var literals : clauses) { |
228 | var postProcessor = new ClausePostProcessor(parameterInfoMap, literals); | 231 | var postProcessor = new ClausePostProcessor(parameterInfoMap, literals); |
229 | var result = postProcessor.postProcessClause(); | 232 | var result = postProcessor.postProcessClause(); |
230 | if (result instanceof ClausePostProcessor.ClauseResult clauseResult) { | 233 | if (result instanceof ClausePostProcessor.ClauseResult clauseResult) { |
231 | postProcessedClauses.add(clauseResult.clause()); | 234 | postProcessedClauses.add(new CanonicalClause(clauseResult.clause())); |
232 | } else if (result instanceof ClausePostProcessor.ConstantResult constantResult) { | 235 | } else if (result instanceof ClausePostProcessor.ConstantResult constantResult) { |
233 | switch (constantResult) { | 236 | switch (constantResult) { |
234 | case ALWAYS_TRUE -> { | 237 | case ALWAYS_TRUE -> { |
@@ -245,7 +248,7 @@ public final class DnfBuilder { | |||
245 | throw new IllegalStateException("Unexpected ClausePostProcessor.Result: " + result); | 248 | throw new IllegalStateException("Unexpected ClausePostProcessor.Result: " + result); |
246 | } | 249 | } |
247 | } | 250 | } |
248 | return postProcessedClauses; | 251 | return postProcessedClauses.stream().map(CanonicalClause::getDnfClause).toList(); |
249 | } | 252 | } |
250 | 253 | ||
251 | private Map<Variable, ClausePostProcessor.ParameterInfo> getParameterInfoMap() { | 254 | private Map<Variable, ClausePostProcessor.ParameterInfo> getParameterInfoMap() { |
@@ -268,4 +271,35 @@ public final class DnfBuilder { | |||
268 | } | 271 | } |
269 | return Collections.unmodifiableSet(inputParameters); | 272 | return Collections.unmodifiableSet(inputParameters); |
270 | } | 273 | } |
274 | |||
275 | private class CanonicalClause { | ||
276 | private final DnfClause dnfClause; | ||
277 | |||
278 | public CanonicalClause(DnfClause dnfClause) { | ||
279 | this.dnfClause = dnfClause; | ||
280 | } | ||
281 | |||
282 | public DnfClause getDnfClause() { | ||
283 | return dnfClause; | ||
284 | } | ||
285 | |||
286 | @Override | ||
287 | public boolean equals(Object obj) { | ||
288 | if (this == obj) { | ||
289 | return true; | ||
290 | } | ||
291 | if (obj == null || getClass() != obj.getClass()) { | ||
292 | return false; | ||
293 | } | ||
294 | var otherCanonicalClause = (CanonicalClause) obj; | ||
295 | var helper = new SubstitutingLiteralEqualityHelper(DnfEqualityChecker.DEFAULT, parameters, parameters); | ||
296 | return dnfClause.equalsWithSubstitution(helper, otherCanonicalClause.dnfClause); | ||
297 | } | ||
298 | |||
299 | @Override | ||
300 | public int hashCode() { | ||
301 | var helper = new SubstitutingLiteralHashCodeHelper(parameters); | ||
302 | return dnfClause.hashCodeWithSubstitution(helper); | ||
303 | } | ||
304 | } | ||
271 | } | 305 | } |
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/FunctionalQuery.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/FunctionalQuery.java index 5a32b1ba..aaebfcc2 100644 --- a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/FunctionalQuery.java +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/FunctionalQuery.java | |||
@@ -54,6 +54,11 @@ public final class FunctionalQuery<T> extends Query<T> { | |||
54 | return null; | 54 | return null; |
55 | } | 55 | } |
56 | 56 | ||
57 | @Override | ||
58 | protected Query<T> withDnfInternal(Dnf newDnf) { | ||
59 | return newDnf.asFunction(type); | ||
60 | } | ||
61 | |||
57 | public AssignedValue<T> call(List<NodeVariable> arguments) { | 62 | public AssignedValue<T> call(List<NodeVariable> arguments) { |
58 | return targetVariable -> { | 63 | return targetVariable -> { |
59 | var argumentsWithTarget = new ArrayList<Variable>(arguments.size() + 1); | 64 | var argumentsWithTarget = new ArrayList<Variable>(arguments.size() + 1); |
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/Query.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/Query.java index aaa52ce6..55f748da 100644 --- a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/Query.java +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/Query.java | |||
@@ -43,6 +43,26 @@ public abstract sealed class Query<T> implements AnyQuery permits FunctionalQuer | |||
43 | 43 | ||
44 | public abstract T defaultValue(); | 44 | public abstract T defaultValue(); |
45 | 45 | ||
46 | public Query<T> withDnf(Dnf newDnf) { | ||
47 | int arity = dnf.arity(); | ||
48 | if (newDnf.arity() != arity) { | ||
49 | throw new IllegalArgumentException("Arity of %s and %s do not match".formatted(dnf, newDnf)); | ||
50 | } | ||
51 | var parameters = dnf.getParameters(); | ||
52 | var newParameters = newDnf.getParameters(); | ||
53 | for (int i = 0; i < arity; i++) { | ||
54 | var parameter = parameters.get(i); | ||
55 | var newParameter = newParameters.get(i); | ||
56 | if (!parameter.matches(newParameter)) { | ||
57 | throw new IllegalArgumentException("Parameter #%d mismatch: %s does not match %s" | ||
58 | .formatted(i, parameter, newParameter)); | ||
59 | } | ||
60 | } | ||
61 | return withDnfInternal(newDnf); | ||
62 | } | ||
63 | |||
64 | protected abstract Query<T> withDnfInternal(Dnf newDnf); | ||
65 | |||
46 | @Override | 66 | @Override |
47 | public boolean equals(Object o) { | 67 | public boolean equals(Object o) { |
48 | if (this == o) return true; | 68 | if (this == o) return true; |
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/RelationalQuery.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/RelationalQuery.java index d34a7ace..c1892ee1 100644 --- a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/RelationalQuery.java +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/RelationalQuery.java | |||
@@ -40,6 +40,11 @@ public final class RelationalQuery extends Query<Boolean> { | |||
40 | return false; | 40 | return false; |
41 | } | 41 | } |
42 | 42 | ||
43 | @Override | ||
44 | protected Query<Boolean> withDnfInternal(Dnf newDnf) { | ||
45 | return newDnf.asRelation(); | ||
46 | } | ||
47 | |||
43 | public CallLiteral call(CallPolarity polarity, List<NodeVariable> arguments) { | 48 | public CallLiteral call(CallPolarity polarity, List<NodeVariable> arguments) { |
44 | return getDnf().call(polarity, Collections.unmodifiableList(arguments)); | 49 | return getDnf().call(polarity, Collections.unmodifiableList(arguments)); |
45 | } | 50 | } |
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/equality/SubstitutingLiteralHashCodeHelper.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/equality/SubstitutingLiteralHashCodeHelper.java index a40ecd58..754f6976 100644 --- a/subprojects/store-query/src/main/java/tools/refinery/store/query/equality/SubstitutingLiteralHashCodeHelper.java +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/equality/SubstitutingLiteralHashCodeHelper.java | |||
@@ -5,9 +5,11 @@ | |||
5 | */ | 5 | */ |
6 | package tools.refinery.store.query.equality; | 6 | package tools.refinery.store.query.equality; |
7 | 7 | ||
8 | import tools.refinery.store.query.dnf.SymbolicParameter; | ||
8 | import tools.refinery.store.query.term.Variable; | 9 | import tools.refinery.store.query.term.Variable; |
9 | 10 | ||
10 | import java.util.LinkedHashMap; | 11 | import java.util.LinkedHashMap; |
12 | import java.util.List; | ||
11 | import java.util.Map; | 13 | import java.util.Map; |
12 | 14 | ||
13 | public class SubstitutingLiteralHashCodeHelper implements LiteralHashCodeHelper { | 15 | public class SubstitutingLiteralHashCodeHelper implements LiteralHashCodeHelper { |
@@ -16,6 +18,16 @@ public class SubstitutingLiteralHashCodeHelper implements LiteralHashCodeHelper | |||
16 | // 0 is for {@code null}, so we start with 1. | 18 | // 0 is for {@code null}, so we start with 1. |
17 | private int next = 1; | 19 | private int next = 1; |
18 | 20 | ||
21 | public SubstitutingLiteralHashCodeHelper() { | ||
22 | this(List.of()); | ||
23 | } | ||
24 | |||
25 | public SubstitutingLiteralHashCodeHelper(List<SymbolicParameter> parameters) { | ||
26 | for (var parameter : parameters) { | ||
27 | getVariableHashCode(parameter.getVariable()); | ||
28 | } | ||
29 | } | ||
30 | |||
19 | @Override | 31 | @Override |
20 | public int getVariableHashCode(Variable variable) { | 32 | public int getVariableHashCode(Variable variable) { |
21 | if (variable == null) { | 33 | if (variable == null) { |
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AbstractCallLiteral.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AbstractCallLiteral.java index 263c2e20..b309f24b 100644 --- a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AbstractCallLiteral.java +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AbstractCallLiteral.java | |||
@@ -96,6 +96,15 @@ public abstract class AbstractCallLiteral extends AbstractLiteral { | |||
96 | 96 | ||
97 | protected abstract Literal doSubstitute(Substitution substitution, List<Variable> substitutedArguments); | 97 | protected abstract Literal doSubstitute(Substitution substitution, List<Variable> substitutedArguments); |
98 | 98 | ||
99 | public AbstractCallLiteral withTarget(Constraint newTarget) { | ||
100 | if (Objects.equals(target, newTarget)) { | ||
101 | return this; | ||
102 | } | ||
103 | return internalWithTarget(newTarget); | ||
104 | } | ||
105 | |||
106 | protected abstract AbstractCallLiteral internalWithTarget(Constraint newTarget); | ||
107 | |||
99 | @Override | 108 | @Override |
100 | public boolean equalsWithSubstitution(LiteralEqualityHelper helper, Literal other) { | 109 | public boolean equalsWithSubstitution(LiteralEqualityHelper helper, Literal other) { |
101 | if (!super.equalsWithSubstitution(helper, other)) { | 110 | if (!super.equalsWithSubstitution(helper, other)) { |
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AggregationLiteral.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AggregationLiteral.java index 615fd493..dac34332 100644 --- a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AggregationLiteral.java +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AggregationLiteral.java | |||
@@ -92,6 +92,11 @@ public class AggregationLiteral<R, T> extends AbstractCallLiteral { | |||
92 | } | 92 | } |
93 | 93 | ||
94 | @Override | 94 | @Override |
95 | protected AbstractCallLiteral internalWithTarget(Constraint newTarget) { | ||
96 | return new AggregationLiteral<>(resultVariable, aggregator, inputVariable, newTarget, getArguments()); | ||
97 | } | ||
98 | |||
99 | @Override | ||
95 | public boolean equalsWithSubstitution(LiteralEqualityHelper helper, Literal other) { | 100 | public boolean equalsWithSubstitution(LiteralEqualityHelper helper, Literal other) { |
96 | if (!super.equalsWithSubstitution(helper, other)) { | 101 | if (!super.equalsWithSubstitution(helper, other)) { |
97 | return false; | 102 | return false; |
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CallLiteral.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CallLiteral.java index a311dada..b1585c77 100644 --- a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CallLiteral.java +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CallLiteral.java | |||
@@ -98,6 +98,11 @@ public final class CallLiteral extends AbstractCallLiteral implements CanNegate< | |||
98 | } | 98 | } |
99 | 99 | ||
100 | @Override | 100 | @Override |
101 | protected AbstractCallLiteral internalWithTarget(Constraint newTarget) { | ||
102 | return new CallLiteral(polarity, newTarget, getArguments()); | ||
103 | } | ||
104 | |||
105 | @Override | ||
101 | public String toString() { | 106 | public String toString() { |
102 | var builder = new StringBuilder(); | 107 | var builder = new StringBuilder(); |
103 | if (!polarity.isPositive()) { | 108 | if (!polarity.isPositive()) { |
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CountLiteral.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CountLiteral.java index ac4b8788..77b77389 100644 --- a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CountLiteral.java +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CountLiteral.java | |||
@@ -62,6 +62,11 @@ public class CountLiteral extends AbstractCallLiteral { | |||
62 | } | 62 | } |
63 | 63 | ||
64 | @Override | 64 | @Override |
65 | protected AbstractCallLiteral internalWithTarget(Constraint newTarget) { | ||
66 | return new CountLiteral(resultVariable, newTarget, getArguments()); | ||
67 | } | ||
68 | |||
69 | @Override | ||
65 | public boolean equalsWithSubstitution(LiteralEqualityHelper helper, Literal other) { | 70 | public boolean equalsWithSubstitution(LiteralEqualityHelper helper, Literal other) { |
66 | if (!super.equalsWithSubstitution(helper, other)) { | 71 | if (!super.equalsWithSubstitution(helper, other)) { |
67 | return false; | 72 | return false; |
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/AbstractRecursiveRewriter.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/AbstractRecursiveRewriter.java new file mode 100644 index 00000000..fb4c14a7 --- /dev/null +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/AbstractRecursiveRewriter.java | |||
@@ -0,0 +1,26 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.query.rewriter; | ||
7 | |||
8 | import tools.refinery.store.query.dnf.Dnf; | ||
9 | import tools.refinery.store.query.equality.DnfEqualityChecker; | ||
10 | import tools.refinery.store.util.CycleDetectingMapper; | ||
11 | |||
12 | public abstract class AbstractRecursiveRewriter implements DnfRewriter { | ||
13 | private final CycleDetectingMapper<Dnf, Dnf> mapper = new CycleDetectingMapper<>(Dnf::name, this::map); | ||
14 | |||
15 | @Override | ||
16 | public Dnf rewrite(Dnf dnf) { | ||
17 | return mapper.map(dnf); | ||
18 | } | ||
19 | |||
20 | protected Dnf map(Dnf dnf) { | ||
21 | var result = doRewrite(dnf); | ||
22 | return dnf.equalsWithSubstitution(DnfEqualityChecker.DEFAULT, result) ? dnf : result; | ||
23 | } | ||
24 | |||
25 | protected abstract Dnf doRewrite(Dnf dnf); | ||
26 | } | ||
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/ClauseInputParameterResolver.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/ClauseInputParameterResolver.java new file mode 100644 index 00000000..bdd07f19 --- /dev/null +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/ClauseInputParameterResolver.java | |||
@@ -0,0 +1,160 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.query.rewriter; | ||
7 | |||
8 | import tools.refinery.store.query.dnf.Dnf; | ||
9 | import tools.refinery.store.query.dnf.DnfClause; | ||
10 | import tools.refinery.store.query.literal.*; | ||
11 | import tools.refinery.store.query.substitution.Substitution; | ||
12 | import tools.refinery.store.query.term.ParameterDirection; | ||
13 | import tools.refinery.store.query.term.Variable; | ||
14 | |||
15 | import java.util.*; | ||
16 | |||
17 | class ClauseInputParameterResolver { | ||
18 | private final InputParameterResolver rewriter; | ||
19 | private final String dnfName; | ||
20 | private final int clauseIndex; | ||
21 | private final Set<Variable> positiveVariables = new LinkedHashSet<>(); | ||
22 | private final List<Literal> inlinedLiterals = new ArrayList<>(); | ||
23 | private final Deque<Literal> workList; | ||
24 | private int helperIndex = 0; | ||
25 | |||
26 | public ClauseInputParameterResolver(InputParameterResolver rewriter, List<Literal> context, DnfClause clause, | ||
27 | String dnfName, int clauseIndex) { | ||
28 | this.rewriter = rewriter; | ||
29 | this.dnfName = dnfName; | ||
30 | this.clauseIndex = clauseIndex; | ||
31 | workList = new ArrayDeque<>(clause.literals().size() + context.size()); | ||
32 | for (var literal : context) { | ||
33 | workList.addLast(literal); | ||
34 | } | ||
35 | for (var literal : clause.literals()) { | ||
36 | workList.addLast(literal); | ||
37 | } | ||
38 | } | ||
39 | |||
40 | public List<Literal> rewriteClause() { | ||
41 | while (!workList.isEmpty()) { | ||
42 | var literal = workList.removeFirst(); | ||
43 | processLiteral(literal); | ||
44 | } | ||
45 | return inlinedLiterals; | ||
46 | } | ||
47 | |||
48 | private void processLiteral(Literal literal) { | ||
49 | if (!(literal instanceof AbstractCallLiteral abstractCallLiteral) || | ||
50 | !(abstractCallLiteral.getTarget() instanceof Dnf targetDnf)) { | ||
51 | markAsDone(literal); | ||
52 | return; | ||
53 | } | ||
54 | boolean hasInputParameter = hasInputParameter(targetDnf); | ||
55 | if (!hasInputParameter) { | ||
56 | targetDnf = rewriter.doRewrite(targetDnf); | ||
57 | } | ||
58 | if (inlinePositiveClause(abstractCallLiteral, targetDnf)) { | ||
59 | return; | ||
60 | } | ||
61 | if (eliminateDoubleNegation(abstractCallLiteral, targetDnf)) { | ||
62 | return; | ||
63 | } | ||
64 | if (hasInputParameter) { | ||
65 | rewriteWithCurrentContext(abstractCallLiteral, targetDnf); | ||
66 | return; | ||
67 | } | ||
68 | markAsDone(abstractCallLiteral.withTarget(targetDnf)); | ||
69 | } | ||
70 | |||
71 | private void markAsDone(Literal literal) { | ||
72 | positiveVariables.addAll(literal.getOutputVariables()); | ||
73 | inlinedLiterals.add(literal); | ||
74 | } | ||
75 | |||
76 | private boolean inlinePositiveClause(AbstractCallLiteral abstractCallLiteral, Dnf targetDnf) { | ||
77 | var targetLiteral = getSingleLiteral(abstractCallLiteral, targetDnf, CallPolarity.POSITIVE); | ||
78 | if (targetLiteral == null) { | ||
79 | return false; | ||
80 | } | ||
81 | var substitution = asSubstitution(abstractCallLiteral, targetDnf); | ||
82 | var substitutedLiteral = targetLiteral.substitute(substitution); | ||
83 | workList.addFirst(substitutedLiteral); | ||
84 | return true; | ||
85 | } | ||
86 | |||
87 | private boolean eliminateDoubleNegation(AbstractCallLiteral abstractCallLiteral, Dnf targetDnf) { | ||
88 | var targetLiteral = getSingleLiteral(abstractCallLiteral, targetDnf, CallPolarity.NEGATIVE); | ||
89 | if (!(targetLiteral instanceof CallLiteral targetCallLiteral) || | ||
90 | targetCallLiteral.getPolarity() != CallPolarity.NEGATIVE) { | ||
91 | return false; | ||
92 | } | ||
93 | var substitution = asSubstitution(abstractCallLiteral, targetDnf); | ||
94 | var substitutedLiteral = (CallLiteral) targetCallLiteral.substitute(substitution); | ||
95 | workList.addFirst(substitutedLiteral.negate()); | ||
96 | return true; | ||
97 | } | ||
98 | |||
99 | private void rewriteWithCurrentContext(AbstractCallLiteral abstractCallLiteral, Dnf targetDnf) { | ||
100 | var contextBuilder = Dnf.builder("%s#clause%d#helper%d".formatted(dnfName, clauseIndex, helperIndex)); | ||
101 | helperIndex++; | ||
102 | contextBuilder.parameters(positiveVariables, ParameterDirection.OUT); | ||
103 | contextBuilder.clause(inlinedLiterals); | ||
104 | var contextDnf = contextBuilder.build(); | ||
105 | var contextCall = new CallLiteral(CallPolarity.POSITIVE, contextDnf, List.copyOf(positiveVariables)); | ||
106 | inlinedLiterals.clear(); | ||
107 | var substitution = Substitution.builder().renewing().build(); | ||
108 | var context = new ArrayList<Literal>(); | ||
109 | context.add(contextCall.substitute(substitution)); | ||
110 | int arity = targetDnf.arity(); | ||
111 | for (int i = 0; i < arity; i++) { | ||
112 | var parameter = targetDnf.getSymbolicParameters().get(i).getVariable(); | ||
113 | var argument = abstractCallLiteral.getArguments().get(i); | ||
114 | context.add(new EquivalenceLiteral(true, parameter, substitution.getSubstitute(argument))); | ||
115 | } | ||
116 | var rewrittenDnf = rewriter.rewriteWithContext(context, targetDnf); | ||
117 | workList.addFirst(abstractCallLiteral.withTarget(rewrittenDnf)); | ||
118 | workList.addFirst(contextCall); | ||
119 | } | ||
120 | |||
121 | private static boolean hasInputParameter(Dnf targetDnf) { | ||
122 | for (var parameter : targetDnf.getParameters()) { | ||
123 | if (parameter.getDirection() != ParameterDirection.OUT) { | ||
124 | return true; | ||
125 | } | ||
126 | } | ||
127 | return false; | ||
128 | } | ||
129 | |||
130 | private static Literal getSingleLiteral(AbstractCallLiteral abstractCallLiteral, Dnf targetDnf, | ||
131 | CallPolarity polarity) { | ||
132 | if (!(abstractCallLiteral instanceof CallLiteral callLiteral) || | ||
133 | callLiteral.getPolarity() != polarity) { | ||
134 | return null; | ||
135 | } | ||
136 | var clauses = targetDnf.getClauses(); | ||
137 | if (clauses.size() != 1) { | ||
138 | return null; | ||
139 | } | ||
140 | var targetLiterals = clauses.get(0).literals(); | ||
141 | if (targetLiterals.size() != 1) { | ||
142 | return null; | ||
143 | } | ||
144 | return targetLiterals.get(0); | ||
145 | } | ||
146 | |||
147 | private static Substitution asSubstitution(AbstractCallLiteral callLiteral, Dnf targetDnf) { | ||
148 | var builder = Substitution.builder().renewing(); | ||
149 | var arguments = callLiteral.getArguments(); | ||
150 | var parameters = targetDnf.getSymbolicParameters(); | ||
151 | int arity = arguments.size(); | ||
152 | if (parameters.size() != arity) { | ||
153 | throw new IllegalArgumentException("Call %s of %s arity mismatch".formatted(callLiteral, targetDnf)); | ||
154 | } | ||
155 | for (int i = 0; i < arity; i++) { | ||
156 | builder.putChecked(parameters.get(i).getVariable(), arguments.get(i)); | ||
157 | } | ||
158 | return builder.build(); | ||
159 | } | ||
160 | } | ||
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/CompositeRewriter.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/CompositeRewriter.java new file mode 100644 index 00000000..5b4f65e5 --- /dev/null +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/CompositeRewriter.java | |||
@@ -0,0 +1,29 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.query.rewriter; | ||
7 | |||
8 | import tools.refinery.store.query.dnf.Dnf; | ||
9 | |||
10 | import java.util.ArrayList; | ||
11 | import java.util.List; | ||
12 | |||
13 | public class CompositeRewriter implements DnfRewriter { | ||
14 | private final List<DnfRewriter> rewriterList = new ArrayList<>(); | ||
15 | |||
16 | public void addFirst(DnfRewriter rewriter) { | ||
17 | rewriterList.add(rewriter); | ||
18 | } | ||
19 | |||
20 | @Override | ||
21 | public Dnf rewrite(Dnf dnf) { | ||
22 | Dnf rewrittenDnf = dnf; | ||
23 | for (int i = rewriterList.size() - 1; i >= 0; i--) { | ||
24 | var rewriter = rewriterList.get(i); | ||
25 | rewrittenDnf = rewriter.rewrite(rewrittenDnf); | ||
26 | } | ||
27 | return rewrittenDnf; | ||
28 | } | ||
29 | } | ||
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/DnfRewriter.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/DnfRewriter.java new file mode 100644 index 00000000..5d8359d1 --- /dev/null +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/DnfRewriter.java | |||
@@ -0,0 +1,24 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.query.rewriter; | ||
7 | |||
8 | import tools.refinery.store.query.dnf.AnyQuery; | ||
9 | import tools.refinery.store.query.dnf.Dnf; | ||
10 | import tools.refinery.store.query.dnf.Query; | ||
11 | |||
12 | @FunctionalInterface | ||
13 | public interface DnfRewriter { | ||
14 | Dnf rewrite(Dnf dnf); | ||
15 | |||
16 | default AnyQuery rewrite(AnyQuery query) { | ||
17 | return rewrite((Query<?>) query); | ||
18 | } | ||
19 | |||
20 | default <T> Query<T> rewrite(Query<T> query) { | ||
21 | var rewrittenDnf = rewrite(query.getDnf()); | ||
22 | return query.withDnf(rewrittenDnf); | ||
23 | } | ||
24 | } | ||
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/DuplicateDnfRemover.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/DuplicateDnfRemover.java new file mode 100644 index 00000000..0c786470 --- /dev/null +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/DuplicateDnfRemover.java | |||
@@ -0,0 +1,98 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.query.rewriter; | ||
7 | |||
8 | import tools.refinery.store.query.dnf.Dnf; | ||
9 | import tools.refinery.store.query.dnf.DnfClause; | ||
10 | import tools.refinery.store.query.dnf.Query; | ||
11 | import tools.refinery.store.query.equality.DnfEqualityChecker; | ||
12 | import tools.refinery.store.query.literal.AbstractCallLiteral; | ||
13 | import tools.refinery.store.query.literal.Literal; | ||
14 | |||
15 | import java.util.ArrayList; | ||
16 | import java.util.HashMap; | ||
17 | import java.util.List; | ||
18 | import java.util.Map; | ||
19 | |||
20 | public class DuplicateDnfRemover extends AbstractRecursiveRewriter { | ||
21 | private final Map<CanonicalDnf, Dnf> dnfCache = new HashMap<>(); | ||
22 | private final Map<Dnf, Query<?>> queryCache = new HashMap<>(); | ||
23 | |||
24 | @Override | ||
25 | protected Dnf map(Dnf dnf) { | ||
26 | var result = super.map(dnf); | ||
27 | return dnfCache.computeIfAbsent(new CanonicalDnf(result), CanonicalDnf::getDnf); | ||
28 | } | ||
29 | |||
30 | @Override | ||
31 | protected Dnf doRewrite(Dnf dnf) { | ||
32 | var builder = Dnf.builderFrom(dnf); | ||
33 | for (var clause : dnf.getClauses()) { | ||
34 | builder.clause(rewriteClause(clause)); | ||
35 | } | ||
36 | return builder.build(); | ||
37 | } | ||
38 | |||
39 | private List<Literal> rewriteClause(DnfClause clause) { | ||
40 | var originalLiterals = clause.literals(); | ||
41 | var literals = new ArrayList<Literal>(originalLiterals.size()); | ||
42 | for (var literal : originalLiterals) { | ||
43 | var rewrittenLiteral = literal; | ||
44 | if (literal instanceof AbstractCallLiteral abstractCallLiteral && | ||
45 | abstractCallLiteral.getTarget() instanceof Dnf targetDnf) { | ||
46 | var rewrittenTarget = rewrite(targetDnf); | ||
47 | rewrittenLiteral = abstractCallLiteral.withTarget(rewrittenTarget); | ||
48 | } | ||
49 | literals.add(rewrittenLiteral); | ||
50 | } | ||
51 | return literals; | ||
52 | } | ||
53 | |||
54 | @Override | ||
55 | public <T> Query<T> rewrite(Query<T> query) { | ||
56 | var rewrittenDnf = rewrite(query.getDnf()); | ||
57 | // {@code withDnf} will always return the appropriate type. | ||
58 | @SuppressWarnings("unchecked") | ||
59 | var rewrittenQuery = (Query<T>) queryCache.computeIfAbsent(rewrittenDnf, query::withDnf); | ||
60 | return rewrittenQuery; | ||
61 | } | ||
62 | |||
63 | private static class CanonicalDnf { | ||
64 | private final Dnf dnf; | ||
65 | private final int hash; | ||
66 | |||
67 | public CanonicalDnf(Dnf dnf) { | ||
68 | this.dnf = dnf; | ||
69 | hash = dnf.hashCodeWithSubstitution(); | ||
70 | } | ||
71 | |||
72 | public Dnf getDnf() { | ||
73 | return dnf; | ||
74 | } | ||
75 | |||
76 | @Override | ||
77 | public boolean equals(Object obj) { | ||
78 | if (this == obj) { | ||
79 | return true; | ||
80 | } | ||
81 | if (obj == null || getClass() != obj.getClass()) { | ||
82 | return false; | ||
83 | } | ||
84 | var otherCanonicalDnf = (CanonicalDnf) obj; | ||
85 | return dnf.equalsWithSubstitution(DnfEqualityChecker.DEFAULT, otherCanonicalDnf.dnf); | ||
86 | } | ||
87 | |||
88 | @Override | ||
89 | public int hashCode() { | ||
90 | return hash; | ||
91 | } | ||
92 | |||
93 | @Override | ||
94 | public String toString() { | ||
95 | return dnf.name(); | ||
96 | } | ||
97 | } | ||
98 | } | ||
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/InputParameterResolver.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/InputParameterResolver.java new file mode 100644 index 00000000..cd8a2e7d --- /dev/null +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/rewriter/InputParameterResolver.java | |||
@@ -0,0 +1,51 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.query.rewriter; | ||
7 | |||
8 | import tools.refinery.store.query.dnf.Dnf; | ||
9 | import tools.refinery.store.query.dnf.DnfBuilder; | ||
10 | import tools.refinery.store.query.literal.Literal; | ||
11 | import tools.refinery.store.query.term.ParameterDirection; | ||
12 | import tools.refinery.store.query.term.Variable; | ||
13 | |||
14 | import java.util.HashSet; | ||
15 | import java.util.List; | ||
16 | |||
17 | public class InputParameterResolver extends AbstractRecursiveRewriter { | ||
18 | @Override | ||
19 | protected Dnf doRewrite(Dnf dnf) { | ||
20 | return rewriteWithContext(List.of(), dnf); | ||
21 | } | ||
22 | |||
23 | Dnf rewriteWithContext(List<Literal> context, Dnf dnf) { | ||
24 | var dnfName = dnf.name(); | ||
25 | var builder = Dnf.builder(dnfName); | ||
26 | createSymbolicParameters(context, dnf, builder); | ||
27 | builder.functionalDependencies(dnf.getFunctionalDependencies()); | ||
28 | var clauses = dnf.getClauses(); | ||
29 | int clauseCount = clauses.size(); | ||
30 | for (int i = 0; i < clauseCount; i++) { | ||
31 | var clause = clauses.get(i); | ||
32 | var clauseRewriter = new ClauseInputParameterResolver(this, context, clause, dnfName, i); | ||
33 | builder.clause(clauseRewriter.rewriteClause()); | ||
34 | } | ||
35 | return builder.build(); | ||
36 | } | ||
37 | |||
38 | private static void createSymbolicParameters(List<Literal> context, Dnf dnf, DnfBuilder builder) { | ||
39 | var positiveInContext = new HashSet<Variable>(); | ||
40 | for (var literal : context) { | ||
41 | positiveInContext.addAll(literal.getOutputVariables()); | ||
42 | } | ||
43 | for (var symbolicParameter : dnf.getSymbolicParameters()) { | ||
44 | var variable = symbolicParameter.getVariable(); | ||
45 | var isOutput = symbolicParameter.getDirection() == ParameterDirection.OUT || | ||
46 | positiveInContext.contains(variable); | ||
47 | var direction = isOutput ? ParameterDirection.OUT : ParameterDirection.IN; | ||
48 | builder.parameter(variable, direction); | ||
49 | } | ||
50 | } | ||
51 | } | ||
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/term/Parameter.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/term/Parameter.java index e5a0cdf1..dbb76177 100644 --- a/subprojects/store-query/src/main/java/tools/refinery/store/query/term/Parameter.java +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/term/Parameter.java | |||
@@ -35,6 +35,10 @@ public class Parameter { | |||
35 | return direction; | 35 | return direction; |
36 | } | 36 | } |
37 | 37 | ||
38 | public boolean matches(Parameter other) { | ||
39 | return Objects.equals(dataType, other.dataType) && direction == other.direction; | ||
40 | } | ||
41 | |||
38 | public boolean isAssignable(Variable variable) { | 42 | public boolean isAssignable(Variable variable) { |
39 | if (variable instanceof AnyDataVariable dataVariable) { | 43 | if (variable instanceof AnyDataVariable dataVariable) { |
40 | return dataVariable.getType().equals(dataType); | 44 | return dataVariable.getType().equals(dataType); |
@@ -50,7 +54,7 @@ public class Parameter { | |||
50 | if (this == o) return true; | 54 | if (this == o) return true; |
51 | if (o == null || getClass() != o.getClass()) return false; | 55 | if (o == null || getClass() != o.getClass()) return false; |
52 | Parameter parameter = (Parameter) o; | 56 | Parameter parameter = (Parameter) o; |
53 | return Objects.equals(dataType, parameter.dataType) && direction == parameter.direction; | 57 | return matches(parameter); |
54 | } | 58 | } |
55 | 59 | ||
56 | @Override | 60 | @Override |
diff --git a/subprojects/store-query/src/test/java/tools/refinery/store/query/rewriter/DuplicateDnfRemoverTest.java b/subprojects/store-query/src/test/java/tools/refinery/store/query/rewriter/DuplicateDnfRemoverTest.java new file mode 100644 index 00000000..ebb24ab5 --- /dev/null +++ b/subprojects/store-query/src/test/java/tools/refinery/store/query/rewriter/DuplicateDnfRemoverTest.java | |||
@@ -0,0 +1,164 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.query.rewriter; | ||
7 | |||
8 | import org.junit.jupiter.api.BeforeEach; | ||
9 | import org.junit.jupiter.api.Test; | ||
10 | import tools.refinery.store.query.dnf.Query; | ||
11 | import tools.refinery.store.query.literal.AbstractCallLiteral; | ||
12 | import tools.refinery.store.query.literal.Reduction; | ||
13 | import tools.refinery.store.query.term.Variable; | ||
14 | import tools.refinery.store.query.view.AnySymbolView; | ||
15 | import tools.refinery.store.query.view.KeyOnlyView; | ||
16 | import tools.refinery.store.representation.Symbol; | ||
17 | |||
18 | import java.util.List; | ||
19 | |||
20 | import static org.hamcrest.MatcherAssert.assertThat; | ||
21 | import static org.hamcrest.Matchers.is; | ||
22 | import static org.hamcrest.Matchers.not; | ||
23 | import static tools.refinery.store.query.literal.Literals.not; | ||
24 | |||
25 | class DuplicateDnfRemoverTest { | ||
26 | private final static Symbol<Boolean> friend = Symbol.of("friend", 2); | ||
27 | private final static AnySymbolView friendView = new KeyOnlyView<>(friend); | ||
28 | |||
29 | private DuplicateDnfRemover sut; | ||
30 | |||
31 | @BeforeEach | ||
32 | void beforeEach() { | ||
33 | sut = new DuplicateDnfRemover(); | ||
34 | } | ||
35 | |||
36 | @Test | ||
37 | void removeDuplicateSimpleTest() { | ||
38 | var one = Query.of("One", (builder, x, y) -> builder.clause( | ||
39 | friendView.call(x, y), | ||
40 | friendView.call(y, x) | ||
41 | )); | ||
42 | var two = Query.of("Two", (builder, x, y) -> builder.clause( | ||
43 | friendView.call(x, y), | ||
44 | friendView.call(y, x) | ||
45 | )); | ||
46 | |||
47 | var oneResult = sut.rewrite(one); | ||
48 | var twoResult = sut.rewrite(two); | ||
49 | |||
50 | assertThat(oneResult, is(twoResult)); | ||
51 | assertThat(one, is(oneResult)); | ||
52 | } | ||
53 | |||
54 | @Test | ||
55 | void notDuplicateSimpleTest() { | ||
56 | var one = Query.of("One", (builder, x, y) -> builder.clause( | ||
57 | friendView.call(x, y), | ||
58 | friendView.call(y, x) | ||
59 | )); | ||
60 | var two = Query.of("Two", (builder, x, y) -> builder.clause((z) -> List.of( | ||
61 | friendView.call(x, y), | ||
62 | friendView.call(y, z) | ||
63 | ))); | ||
64 | |||
65 | var oneResult = sut.rewrite(one); | ||
66 | var twoResult = sut.rewrite(two); | ||
67 | |||
68 | assertThat(one, is(oneResult)); | ||
69 | assertThat(two, is(twoResult)); | ||
70 | } | ||
71 | |||
72 | @Test | ||
73 | void removeDuplicateRecursiveTest() { | ||
74 | var oneSubQuery = Query.of("OneSubQuery", (builder, x, y) -> builder.clause( | ||
75 | friendView.call(x, y), | ||
76 | friendView.call(y, x) | ||
77 | )); | ||
78 | var one = Query.of("One", (builder, x) -> builder.clause( | ||
79 | oneSubQuery.call(x, Variable.of()) | ||
80 | )); | ||
81 | var twoSubQuery = Query.of("TwoSubQuery", (builder, x, y) -> builder.clause( | ||
82 | friendView.call(x, y), | ||
83 | friendView.call(y, x) | ||
84 | )); | ||
85 | var two = Query.of("Two", (builder, x) -> builder.clause( | ||
86 | twoSubQuery.call(x, Variable.of()) | ||
87 | )); | ||
88 | |||
89 | var oneResult = sut.rewrite(one); | ||
90 | var twoResult = sut.rewrite(two); | ||
91 | |||
92 | assertThat(oneResult, is(twoResult)); | ||
93 | assertThat(one, is(oneResult)); | ||
94 | } | ||
95 | |||
96 | @Test | ||
97 | void notDuplicateRecursiveTest() { | ||
98 | var oneSubQuery = Query.of("OneSubQuery", (builder, x, y) -> builder.clause( | ||
99 | friendView.call(x, y), | ||
100 | friendView.call(y, x) | ||
101 | )); | ||
102 | var one = Query.of("One", (builder, x) -> builder.clause( | ||
103 | oneSubQuery.call(x, Variable.of()) | ||
104 | )); | ||
105 | var twoSubQuery = Query.of("TwoSubQuery", (builder, x, y) -> builder.clause( | ||
106 | friendView.call(x, y), | ||
107 | friendView.call(y, x) | ||
108 | )); | ||
109 | var two = Query.of("Two", (builder, x) -> builder.clause( | ||
110 | twoSubQuery.call(Variable.of(), x) | ||
111 | )); | ||
112 | |||
113 | var oneResult = sut.rewrite(one); | ||
114 | var twoResult = sut.rewrite(two); | ||
115 | |||
116 | assertThat(one, is(oneResult)); | ||
117 | assertThat(oneResult, is(not(twoResult))); | ||
118 | |||
119 | var oneCall = (AbstractCallLiteral) oneResult.getDnf().getClauses().get(0).literals().get(0); | ||
120 | var twoCall = (AbstractCallLiteral) twoResult.getDnf().getClauses().get(0).literals().get(0); | ||
121 | |||
122 | assertThat(oneCall.getTarget(), is(twoCall.getTarget())); | ||
123 | } | ||
124 | |||
125 | @Test | ||
126 | void removeContradictionTest() { | ||
127 | var oneSubQuery = Query.of("OneSubQuery", (builder, x, y) -> builder.clause( | ||
128 | friendView.call(x, y), | ||
129 | friendView.call(y, x) | ||
130 | )); | ||
131 | var twoSubQuery = Query.of("TwoSubQuery", (builder, x, y) -> builder.clause( | ||
132 | friendView.call(x, y), | ||
133 | friendView.call(y, x) | ||
134 | )); | ||
135 | var query = Query.of("Contradiction", (builder, x, y) -> builder.clause( | ||
136 | oneSubQuery.call(x, y), | ||
137 | not(twoSubQuery.call(x, y)) | ||
138 | )); | ||
139 | |||
140 | var result = sut.rewrite(query); | ||
141 | |||
142 | assertThat(result.getDnf().getReduction(), is(Reduction.ALWAYS_FALSE)); | ||
143 | } | ||
144 | |||
145 | @Test | ||
146 | void removeQuantifiedContradictionTest() { | ||
147 | var oneSubQuery = Query.of("OneSubQuery", (builder, x, y) -> builder.clause( | ||
148 | friendView.call(x, y), | ||
149 | friendView.call(y, x) | ||
150 | )); | ||
151 | var twoSubQuery = Query.of("TwoSubQuery", (builder, x, y) -> builder.clause( | ||
152 | friendView.call(x, y), | ||
153 | friendView.call(y, x) | ||
154 | )); | ||
155 | var query = Query.of("Contradiction", (builder, x) -> builder.clause( | ||
156 | oneSubQuery.call(x, Variable.of()), | ||
157 | not(twoSubQuery.call(x, Variable.of())) | ||
158 | )); | ||
159 | |||
160 | var result = sut.rewrite(query); | ||
161 | |||
162 | assertThat(result.getDnf().getReduction(), is(Reduction.ALWAYS_FALSE)); | ||
163 | } | ||
164 | } | ||
diff --git a/subprojects/store-query/src/test/java/tools/refinery/store/query/rewriter/InputParameterResolverTest.java b/subprojects/store-query/src/test/java/tools/refinery/store/query/rewriter/InputParameterResolverTest.java new file mode 100644 index 00000000..ddb2a069 --- /dev/null +++ b/subprojects/store-query/src/test/java/tools/refinery/store/query/rewriter/InputParameterResolverTest.java | |||
@@ -0,0 +1,208 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.query.rewriter; | ||
7 | |||
8 | import org.junit.jupiter.api.BeforeEach; | ||
9 | import org.junit.jupiter.api.Test; | ||
10 | import tools.refinery.store.query.dnf.Dnf; | ||
11 | import tools.refinery.store.query.dnf.Query; | ||
12 | import tools.refinery.store.query.term.ParameterDirection; | ||
13 | import tools.refinery.store.query.term.Variable; | ||
14 | import tools.refinery.store.query.view.AnySymbolView; | ||
15 | import tools.refinery.store.query.view.KeyOnlyView; | ||
16 | import tools.refinery.store.representation.Symbol; | ||
17 | |||
18 | import java.util.List; | ||
19 | |||
20 | import static org.hamcrest.MatcherAssert.assertThat; | ||
21 | import static tools.refinery.store.query.literal.Literals.not; | ||
22 | import static tools.refinery.store.query.tests.QueryMatchers.structurallyEqualTo; | ||
23 | |||
24 | class InputParameterResolverTest { | ||
25 | private final static Symbol<Boolean> person = Symbol.of("Person", 1); | ||
26 | private final static Symbol<Boolean> friend = Symbol.of("friend", 2); | ||
27 | private final static AnySymbolView personView = new KeyOnlyView<>(person); | ||
28 | private final static AnySymbolView friendView = new KeyOnlyView<>(friend); | ||
29 | |||
30 | private InputParameterResolver sut; | ||
31 | |||
32 | @BeforeEach | ||
33 | void beforeEach() { | ||
34 | sut = new InputParameterResolver(); | ||
35 | } | ||
36 | |||
37 | @Test | ||
38 | void inlineSingleClauseTest() { | ||
39 | var dnf = Dnf.of("SubQuery", builder -> { | ||
40 | var x = builder.parameter("x", ParameterDirection.OUT); | ||
41 | builder.clause(friendView.call(x, Variable.of())); | ||
42 | }); | ||
43 | var query = Query.of("Actual", (builder, x) -> builder.clause( | ||
44 | dnf.call(x), | ||
45 | personView.call(x) | ||
46 | )); | ||
47 | |||
48 | var actual = sut.rewrite(query); | ||
49 | |||
50 | var expected = Query.of("Expected", (builder, x) -> builder.clause( | ||
51 | friendView.call(x, Variable.of()), | ||
52 | personView.call(x) | ||
53 | )); | ||
54 | |||
55 | assertThat(actual.getDnf(), structurallyEqualTo(expected.getDnf())); | ||
56 | } | ||
57 | |||
58 | @Test | ||
59 | void inlineSingleClauseWIthInputTest() { | ||
60 | var dnf = Dnf.of("SubQuery", builder -> { | ||
61 | var x = builder.parameter("x", ParameterDirection.IN); | ||
62 | builder.clause(not(friendView.call(x, Variable.of()))); | ||
63 | }); | ||
64 | var query = Query.of("Actual", (builder, x) -> builder.clause( | ||
65 | dnf.call(x), | ||
66 | personView.call(x) | ||
67 | )); | ||
68 | |||
69 | var actual = sut.rewrite(query); | ||
70 | |||
71 | var expected = Query.of("Expected", (builder, x) -> builder.clause( | ||
72 | personView.call(x), | ||
73 | not(friendView.call(x, Variable.of())) | ||
74 | )); | ||
75 | |||
76 | assertThat(actual.getDnf(), structurallyEqualTo(expected.getDnf())); | ||
77 | } | ||
78 | |||
79 | @Test | ||
80 | void singleLiteralDemandSetTest() { | ||
81 | var dnf = Dnf.of("SubQuery", builder -> { | ||
82 | var x = builder.parameter("x", ParameterDirection.IN); | ||
83 | builder.clause(not(friendView.call(x, Variable.of()))); | ||
84 | builder.clause(not(friendView.call(Variable.of(), x))); | ||
85 | }); | ||
86 | var query = Query.of("Actual", (builder, x) -> builder.clause( | ||
87 | dnf.call(x), | ||
88 | personView.call(x) | ||
89 | )); | ||
90 | |||
91 | var actual = sut.rewrite(query); | ||
92 | |||
93 | var expectedSubQuery = Dnf.of("ExpectedSubQuery", builder -> { | ||
94 | var x = builder.parameter("x", ParameterDirection.OUT); | ||
95 | builder.clause( | ||
96 | personView.call(x), | ||
97 | not(friendView.call(x, Variable.of())) | ||
98 | ); | ||
99 | builder.clause( | ||
100 | personView.call(x), | ||
101 | not(friendView.call(Variable.of(), x)) | ||
102 | ); | ||
103 | }); | ||
104 | var expected = Query.of("Expected", (builder, x) -> builder.clause( | ||
105 | personView.call(x), | ||
106 | expectedSubQuery.call(x) | ||
107 | )); | ||
108 | |||
109 | assertThat(actual.getDnf(), structurallyEqualTo(expected.getDnf())); | ||
110 | } | ||
111 | |||
112 | @Test | ||
113 | void multipleLiteralDemandSetTest() { | ||
114 | var dnf = Dnf.of("SubQuery", builder -> { | ||
115 | var x = builder.parameter("x", ParameterDirection.IN); | ||
116 | var y = builder.parameter("y", ParameterDirection.IN); | ||
117 | builder.clause(not(friendView.call(x, y))); | ||
118 | builder.clause(not(friendView.call(y, x))); | ||
119 | }); | ||
120 | var query = Query.of("Actual", (builder, p1) -> builder.clause(p2 -> List.of( | ||
121 | not(dnf.call(p1, p2)), | ||
122 | personView.call(p1), | ||
123 | personView.call(p2) | ||
124 | ))); | ||
125 | |||
126 | var actual = sut.rewrite(query); | ||
127 | |||
128 | var context = Dnf.of("Context", builder -> { | ||
129 | var x = builder.parameter("x", ParameterDirection.OUT); | ||
130 | var y = builder.parameter("y", ParameterDirection.OUT); | ||
131 | builder.clause( | ||
132 | personView.call(x), | ||
133 | personView.call(y) | ||
134 | ); | ||
135 | }); | ||
136 | var expectedSubQuery = Dnf.of("ExpectedSubQuery", builder -> { | ||
137 | var x = builder.parameter("x", ParameterDirection.OUT); | ||
138 | var y = builder.parameter("x", ParameterDirection.OUT); | ||
139 | builder.clause( | ||
140 | context.call(x, y), | ||
141 | not(friendView.call(x, y)) | ||
142 | ); | ||
143 | builder.clause( | ||
144 | context.call(x, y), | ||
145 | not(friendView.call(y, x)) | ||
146 | ); | ||
147 | }); | ||
148 | var expected = Query.of("Expected", (builder, p1) -> builder.clause(p2 -> List.of( | ||
149 | context.call(p1, p2), | ||
150 | not(expectedSubQuery.call(p1, p2)) | ||
151 | ))); | ||
152 | |||
153 | assertThat(actual.getDnf(), structurallyEqualTo(expected.getDnf())); | ||
154 | } | ||
155 | |||
156 | @Test | ||
157 | void multipleParameterDemandSetTest() { | ||
158 | var dnf = Dnf.of("SubQuery", builder -> { | ||
159 | var x = builder.parameter("x", ParameterDirection.IN); | ||
160 | var y = builder.parameter("y", ParameterDirection.IN); | ||
161 | builder.clause(not(friendView.call(x, y))); | ||
162 | builder.clause(not(friendView.call(y, x))); | ||
163 | }); | ||
164 | var query = Query.of("Actual", (builder, p1) -> builder.clause( | ||
165 | not(dnf.call(p1, p1)), | ||
166 | personView.call(p1) | ||
167 | )); | ||
168 | |||
169 | var actual = sut.rewrite(query); | ||
170 | |||
171 | var expectedSubQuery = Dnf.of("ExpectedSubQuery", builder -> { | ||
172 | var x = builder.parameter("x", ParameterDirection.OUT); | ||
173 | var y = builder.parameter("y", ParameterDirection.OUT); | ||
174 | builder.clause( | ||
175 | y.isEquivalent(x), | ||
176 | personView.call(x), | ||
177 | not(friendView.call(x, x)) | ||
178 | ); | ||
179 | }); | ||
180 | var expected = Query.of("Expected", (builder, p1) -> builder.clause( | ||
181 | personView.call(p1), | ||
182 | not(expectedSubQuery.call(p1, p1)) | ||
183 | )); | ||
184 | |||
185 | assertThat(actual.getDnf(), structurallyEqualTo(expected.getDnf())); | ||
186 | } | ||
187 | |||
188 | @Test | ||
189 | void eliminateDoubleNegationTest() { | ||
190 | var dnf = Dnf.of("SubQuery", builder -> { | ||
191 | var x = builder.parameter("x", ParameterDirection.IN); | ||
192 | builder.clause(not(friendView.call(x, Variable.of()))); | ||
193 | }); | ||
194 | var query = Query.of("Actual", (builder, p1) -> builder.clause( | ||
195 | personView.call(p1), | ||
196 | not(dnf.call(p1)) | ||
197 | )); | ||
198 | |||
199 | var actual = sut.rewrite(query); | ||
200 | |||
201 | var expected = Query.of("Actual", (builder, p1) -> builder.clause( | ||
202 | personView.call(p1), | ||
203 | friendView.call(p1, Variable.of()) | ||
204 | )); | ||
205 | |||
206 | assertThat(actual.getDnf(), structurallyEqualTo(expected.getDnf())); | ||
207 | } | ||
208 | } | ||