feat: Dnf reduction and structural equality

4 files changed, 83 insertions, 14 deletions

diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryAdapterImpl.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryAdapterImpl.java
index e5d8e2f6..e0341598 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryAdapterImpl.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryAdapterImpl.java
@@ -8,6 +8,7 @@ import org.eclipse.viatra.query.runtime.matchers.backend.IQueryBackend;
 import org.eclipse.viatra.query.runtime.matchers.backend.IQueryBackendFactory;
 import tools.refinery.store.model.Model;
 import tools.refinery.store.query.Dnf;
+import tools.refinery.store.query.EmptyResultSet;
 import tools.refinery.store.query.ResultSet;
 import tools.refinery.store.query.viatra.ViatraModelQueryAdapter;
 
@@ -15,7 +16,7 @@ import java.lang.invoke.MethodHandle;
 import java.lang.invoke.MethodHandles;
 import java.util.Collection;
 import java.util.Collections;
-import java.util.HashMap;
+import java.util.LinkedHashMap;
 import java.util.Map;
 
 public class ViatraModelQueryAdapterImpl implements ViatraModelQueryAdapter {
@@ -51,11 +52,15 @@ public class ViatraModelQueryAdapterImpl implements ViatraModelQueryAdapter {
                 GenericQueryGroup.of(
                                 Collections.<IQuerySpecification<?>>unmodifiableCollection(querySpecifications.values()).stream()
                 ).prepare(queryEngine);
-                resultSets = new HashMap<>(querySpecifications.size());
+                var vacuousQueries = storeAdapter.getVacuousQueries();
+                resultSets = new LinkedHashMap<>(querySpecifications.size() + vacuousQueries.size());
                 for (var entry : querySpecifications.entrySet()) {
                         var matcher = queryEngine.getMatcher(entry.getValue());
                         resultSets.put(entry.getKey(), matcher);
                 }
+                for (var vacuousQuery : vacuousQueries) {
+                        resultSets.put(vacuousQuery, new EmptyResultSet());
+                }
 
                 setUpdatePropagationDelayed(true);
         }
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryBuilderImpl.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryBuilderImpl.java
index af20033a..13641ace 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryBuilderImpl.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryBuilderImpl.java
@@ -14,14 +14,13 @@ import tools.refinery.store.query.viatra.ViatraModelQueryBuilder;
 import tools.refinery.store.query.viatra.internal.pquery.Dnf2PQuery;
 import tools.refinery.store.query.viatra.internal.pquery.RawPatternMatcher;
 
-import java.util.Collections;
-import java.util.LinkedHashMap;
-import java.util.Map;
+import java.util.*;
 import java.util.function.Function;
 
 public class ViatraModelQueryBuilderImpl extends AbstractModelAdapterBuilder implements ViatraModelQueryBuilder {
         private ViatraQueryEngineOptions.Builder engineOptionsBuilder;
         private final Dnf2PQuery dnf2PQuery = new Dnf2PQuery();
+        private final Set<Dnf> vacuousQueries = new LinkedHashSet<>();
         private final Map<Dnf, IQuerySpecification<RawPatternMatcher>> querySpecifications = new LinkedHashMap<>();
 
         public ViatraModelQueryBuilderImpl(ModelStoreBuilder storeBuilder) {
@@ -64,11 +63,21 @@ public class ViatraModelQueryBuilderImpl extends AbstractModelAdapterBuilder imp
 
         @Override
         public ViatraModelQueryBuilder query(Dnf query) {
-                if (querySpecifications.containsKey(query)) {
-                        throw new IllegalArgumentException("%s was already added to the query engine".formatted(query.name()));
+                if (querySpecifications.containsKey(query) || vacuousQueries.contains(query)) {
+                        // Ignore duplicate queries.
+                        return this;
+                }
+                var reduction = query.getReduction();
+                switch (reduction) {
+                case NOT_REDUCIBLE -> {
+                        var pQuery = dnf2PQuery.translate(query);
+                        querySpecifications.put(query, pQuery.build());
+                }
+                case ALWAYS_FALSE -> vacuousQueries.add(query);
+                case ALWAYS_TRUE -> throw new IllegalArgumentException(
+                                "Query %s is relationally unsafe (it matches every tuple)".formatted(query.name()));
+                default -> throw new IllegalArgumentException("Unknown reduction: " + reduction);
                 }
-                var pQuery = dnf2PQuery.translate(query);
-                querySpecifications.put(query, pQuery.build());
                 return this;
         }
 
@@ -89,6 +98,10 @@ public class ViatraModelQueryBuilderImpl extends AbstractModelAdapterBuilder imp
         public ViatraModelQueryBuilder hint(Dnf dnf, QueryEvaluationHint queryEvaluationHint) {
                 var pQuery = dnf2PQuery.getAlreadyTranslated(dnf);
                 if (pQuery == null) {
+                        if (vacuousQueries.contains(dnf)) {
+                                // Ignore hits for queries that will never be executed by the query engine.
+                                return this;
+                        }
                         throw new IllegalArgumentException(
                                         "Cannot specify hint for %s, because it was not added to the query engine".formatted(dnf.name()));
                 }
@@ -100,7 +113,7 @@ public class ViatraModelQueryBuilderImpl extends AbstractModelAdapterBuilder imp
         public ViatraModelQueryStoreAdapterImpl createStoreAdapter(ModelStore store) {
                 validateSymbols(store);
                 return new ViatraModelQueryStoreAdapterImpl(store, engineOptionsBuilder.build(), dnf2PQuery.getRelationViews(),
-                                Collections.unmodifiableMap(querySpecifications));
+                                Collections.unmodifiableMap(querySpecifications), Collections.unmodifiableSet(vacuousQueries));
         }
 
         private void validateSymbols(ModelStore store) {
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryStoreAdapterImpl.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryStoreAdapterImpl.java
index 8323118b..00660d0b 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryStoreAdapterImpl.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryStoreAdapterImpl.java
@@ -10,22 +10,29 @@ import tools.refinery.store.query.viatra.ViatraModelQueryStoreAdapter;
 import tools.refinery.store.query.viatra.internal.pquery.RawPatternMatcher;
 import tools.refinery.store.query.view.AnyRelationView;
 
-import java.util.Collection;
-import java.util.Map;
+import java.util.*;
 
 public class ViatraModelQueryStoreAdapterImpl implements ViatraModelQueryStoreAdapter {
         private final ModelStore store;
         private final ViatraQueryEngineOptions engineOptions;
         private final Map<AnyRelationView, IInputKey> inputKeys;
         private final Map<Dnf, IQuerySpecification<RawPatternMatcher>> querySpecifications;
+        private final Set<Dnf> vacuousQueries;
+        private final Set<Dnf> allQueries;
 
         ViatraModelQueryStoreAdapterImpl(ModelStore store, ViatraQueryEngineOptions engineOptions,
                                                                          Map<AnyRelationView, IInputKey> inputKeys,
-                                                                         Map<Dnf, IQuerySpecification<RawPatternMatcher>> querySpecifications) {
+                                                                         Map<Dnf, IQuerySpecification<RawPatternMatcher>> querySpecifications,
+                                                                         Set<Dnf> vacuousQueries) {
                 this.store = store;
                 this.engineOptions = engineOptions;
                 this.inputKeys = inputKeys;
                 this.querySpecifications = querySpecifications;
+                this.vacuousQueries = vacuousQueries;
+                var mutableAllQueries = new LinkedHashSet<Dnf>(querySpecifications.size() + vacuousQueries.size());
+                mutableAllQueries.addAll(querySpecifications.keySet());
+                mutableAllQueries.addAll(vacuousQueries);
+                this.allQueries = Collections.unmodifiableSet(mutableAllQueries);
         }
 
         @Override
@@ -43,13 +50,17 @@ public class ViatraModelQueryStoreAdapterImpl implements ViatraModelQueryStoreAd
 
         @Override
         public Collection<Dnf> getQueries() {
-                return querySpecifications.keySet();
+                return allQueries;
         }
 
         Map<Dnf, IQuerySpecification<RawPatternMatcher>> getQuerySpecifications() {
                 return querySpecifications;
         }
 
+        Set<Dnf> getVacuousQueries() {
+                return vacuousQueries;
+        }
+
         @Override
         public ViatraQueryEngineOptions getEngineOptions() {
                 return engineOptions;
diff --git a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/QueryTest.java b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/QueryTest.java
index 6a3a62e3..54ae70c3 100644
--- a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/QueryTest.java
+++ b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/QueryTest.java
@@ -17,6 +17,7 @@ import java.util.Set;
 import java.util.stream.Stream;
 
 import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertThrows;
 import static tools.refinery.store.query.literal.Literals.not;
 
 class QueryTest {
@@ -669,6 +670,45 @@ class QueryTest {
                 assertEquals(3, predicateResultSet.countResults());
         }
 
+        @Test
+        void alwaysFalseTest() {
+                var person = new Symbol<>("Person", 1, Boolean.class, false);
+
+                var p1 = new Variable("p1");
+                var predicate = Dnf.builder("AlwaysFalse").parameters(p1).build();
+
+                var store = ModelStore.builder()
+                                .symbols(person)
+                                .with(ViatraModelQuery.ADAPTER)
+                                .queries(predicate)
+                                .build();
+
+                var model = store.createEmptyModel();
+                var personInterpretation = model.getInterpretation(person);
+                var queryEngine = model.getAdapter(ModelQuery.ADAPTER);
+                var predicateResultSet = queryEngine.getResultSet(predicate);
+
+                personInterpretation.put(Tuple.of(0), true);
+                personInterpretation.put(Tuple.of(1), true);
+                personInterpretation.put(Tuple.of(2), true);
+
+                queryEngine.flushChanges();
+                assertEquals(0, predicateResultSet.countResults());
+        }
+
+        @Test
+        void alwaysTrueTest() {
+                var person = new Symbol<>("Person", 1, Boolean.class, false);
+
+                var p1 = new Variable("p1");
+                var predicate = Dnf.builder("AlwaysTrue").parameters(p1).clause().build();
+
+                var storeBuilder = ModelStore.builder().symbols(person);
+                var queryBuilder = storeBuilder.with(ViatraModelQuery.ADAPTER);
+
+                assertThrows(IllegalArgumentException.class, () -> queryBuilder.queries(predicate));
+        }
+
         static void compareMatchSets(Stream<TupleLike> matchSet, Set<Tuple> expected) {
                 Set<Tuple> translatedMatchSet = new HashSet<>();
                 var iterator = matchSet.iterator();