feat: ordered query ResultSet

Enable deterministic state-space exploration by ordering activations in
lexicographic order.

This preliminary implementation adds oredering as a wrapper for ResultSet
instances, but more sophisticated support could be built directly into query
engine adapters if a query engine supports deterministic output by default.

* Implements Comparable for tuples with loops unrolled for small tuples by hand.
* Cleans up the contents of the (root of the) tools.refinery.query package.
* Adds ResultSetListener to notify clients about ResultSet changes.
* Adds OrderStatisticTree data structure for determinisitc ordering of keys.

8 files changed, 183 insertions, 51 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 7103a561..5f3e86b4 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
@@ -13,9 +13,9 @@ 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.model.ModelListener;
-import tools.refinery.store.query.AnyResultSet;
-import tools.refinery.store.query.EmptyResultSet;
-import tools.refinery.store.query.ResultSet;
+import tools.refinery.store.query.resultset.AnyResultSet;
+import tools.refinery.store.query.resultset.EmptyResultSet;
+import tools.refinery.store.query.resultset.ResultSet;
 import tools.refinery.store.query.dnf.AnyQuery;
 import tools.refinery.store.query.dnf.FunctionalQuery;
 import tools.refinery.store.query.dnf.Query;
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/AbstractViatraMatcher.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/AbstractViatraMatcher.java
new file mode 100644
index 00000000..99b0a3d8
--- /dev/null
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/AbstractViatraMatcher.java
@@ -0,0 +1,32 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.viatra.internal.matcher;
+
+import org.eclipse.viatra.query.runtime.matchers.backend.IQueryResultProvider;
+import org.eclipse.viatra.query.runtime.matchers.backend.IUpdateable;
+import tools.refinery.store.query.dnf.Query;
+import tools.refinery.store.query.resultset.AbstractResultSet;
+import tools.refinery.store.query.viatra.internal.ViatraModelQueryAdapterImpl;
+
+public abstract class AbstractViatraMatcher<T> extends AbstractResultSet<T> implements IUpdateable {
+        protected final IQueryResultProvider backend;
+
+        protected AbstractViatraMatcher(ViatraModelQueryAdapterImpl adapter, Query<T> query,
+                                                                        RawPatternMatcher rawPatternMatcher) {
+                super(adapter, query);
+                backend = rawPatternMatcher.getBackend();
+        }
+
+        @Override
+        protected void startListeningForChanges() {
+                backend.addUpdateListener(this, this, false);
+        }
+
+        @Override
+        protected void stopListeningForChanges() {
+                backend.removeUpdateListener(this);
+        }
+}
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/FunctionalViatraMatcher.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/FunctionalViatraMatcher.java
index f018288b..db4740cd 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/FunctionalViatraMatcher.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/FunctionalViatraMatcher.java
@@ -5,16 +5,12 @@
  */
 package tools.refinery.store.query.viatra.internal.matcher;
 
-import org.eclipse.viatra.query.runtime.matchers.backend.IQueryResultProvider;
 import org.eclipse.viatra.query.runtime.matchers.tuple.TupleMask;
 import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples;
 import org.eclipse.viatra.query.runtime.rete.index.IterableIndexer;
 import org.eclipse.viatra.query.runtime.rete.matcher.RetePatternMatcher;
 import tools.refinery.store.map.Cursor;
-import tools.refinery.store.query.ModelQueryAdapter;
-import tools.refinery.store.query.ResultSet;
 import tools.refinery.store.query.dnf.FunctionalQuery;
-import tools.refinery.store.query.dnf.Query;
 import tools.refinery.store.query.viatra.internal.ViatraModelQueryAdapterImpl;
 import tools.refinery.store.tuple.Tuple;
 
@@ -28,23 +24,18 @@ import tools.refinery.store.tuple.Tuple;
  * implementation for these methods.
  * Using this class with any other runtime context may lead to undefined behavior.
  */
-public class FunctionalViatraMatcher<T> implements ResultSet<T> {
-        private final ViatraModelQueryAdapterImpl adapter;
-        private final FunctionalQuery<T> query;
+public class FunctionalViatraMatcher<T> extends AbstractViatraMatcher<T> {
         private final TupleMask emptyMask;
         private final TupleMask omitOutputMask;
-        private final IQueryResultProvider backend;
         private final IterableIndexer omitOutputIndexer;
 
         public FunctionalViatraMatcher(ViatraModelQueryAdapterImpl adapter, FunctionalQuery<T> query,
                                                                    RawPatternMatcher rawPatternMatcher) {
-                this.adapter = adapter;
-                this.query = query;
+                super(adapter, query, rawPatternMatcher);
                 int arity = query.arity();
                 int arityWithOutput = arity + 1;
                 emptyMask = TupleMask.empty(arityWithOutput);
                 omitOutputMask = TupleMask.omit(arity, arityWithOutput);
-                backend = rawPatternMatcher.getBackend();
                 if (backend instanceof RetePatternMatcher reteBackend) {
                         var maybeIterableOmitOutputIndexer = IndexerUtils.getIndexer(reteBackend, omitOutputMask);
                         if (maybeIterableOmitOutputIndexer instanceof IterableIndexer iterableOmitOutputIndexer) {
@@ -58,16 +49,6 @@ public class FunctionalViatraMatcher<T> implements ResultSet<T> {
         }
 
         @Override
-        public ModelQueryAdapter getAdapter() {
-                return adapter;
-        }
-
-        @Override
-        public Query<T> getQuery() {
-                return query;
-        }
-
-        @Override
         public T get(Tuple parameters) {
                 var tuple = MatcherUtils.toViatraTuple(parameters);
                 if (omitOutputIndexer == null) {
@@ -93,4 +74,15 @@ public class FunctionalViatraMatcher<T> implements ResultSet<T> {
                 }
                 return omitOutputIndexer.getBucketCount();
         }
+
+        @Override
+        public void update(org.eclipse.viatra.query.runtime.matchers.tuple.Tuple updateElement, boolean isInsertion) {
+                var key = MatcherUtils.keyToRefineryTuple(updateElement);
+                var value = MatcherUtils.<T>getValue(updateElement);
+                if (isInsertion) {
+                        notifyChange(key, null, value);
+                } else {
+                        notifyChange(key, value, null);
+                }
+        }
 }
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/MatcherUtils.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/MatcherUtils.java
index 1c784492..6e24812a 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/MatcherUtils.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/MatcherUtils.java
@@ -86,6 +86,13 @@ final class MatcherUtils {
                 return getWrapper(viatraTuple, index).value0();
         }
 
+        public static <T> T getValue(ITuple match) {
+                // This is only safe if we know for sure that match came from a functional query of type {@code T}.
+                @SuppressWarnings("unchecked")
+                var result = (T) match.get(match.getSize() - 1);
+                return result;
+        }
+
         public static <T> T getSingleValue(@Nullable Iterable<? extends ITuple> viatraTuples) {
                 if (viatraTuples == null) {
                         return null;
@@ -98,8 +105,7 @@ final class MatcherUtils {
                         return null;
                 }
                 var match = iterator.next();
-                @SuppressWarnings("unchecked")
-                var result = (T) match.get(match.getSize() - 1);
+                var result = MatcherUtils.<T>getValue(match);
                 if (iterator.hasNext()) {
                         var input = keyToRefineryTuple(match);
                         throw new IllegalStateException("Query is not functional for input tuple: " + input);
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/RelationalViatraMatcher.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/RelationalViatraMatcher.java
index d1476920..ac95dcc0 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/RelationalViatraMatcher.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/RelationalViatraMatcher.java
@@ -5,16 +5,12 @@
  */
 package tools.refinery.store.query.viatra.internal.matcher;
 
-import org.eclipse.viatra.query.runtime.matchers.backend.IQueryResultProvider;
 import org.eclipse.viatra.query.runtime.matchers.tuple.TupleMask;
 import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples;
 import org.eclipse.viatra.query.runtime.rete.index.Indexer;
 import org.eclipse.viatra.query.runtime.rete.matcher.RetePatternMatcher;
 import tools.refinery.store.map.Cursor;
 import tools.refinery.store.map.Cursors;
-import tools.refinery.store.query.ModelQueryAdapter;
-import tools.refinery.store.query.ResultSet;
-import tools.refinery.store.query.dnf.Query;
 import tools.refinery.store.query.dnf.RelationalQuery;
 import tools.refinery.store.query.viatra.internal.ViatraModelQueryAdapterImpl;
 import tools.refinery.store.tuple.Tuple;
@@ -29,22 +25,17 @@ import tools.refinery.store.tuple.Tuple;
  * implementation for these methods.
  * Using this class with any other runtime context may lead to undefined behavior.
  */
-public class RelationalViatraMatcher implements ResultSet<Boolean> {
-        private final ViatraModelQueryAdapterImpl adapter;
-        private final RelationalQuery query;
+public class RelationalViatraMatcher extends AbstractViatraMatcher<Boolean> {
         private final TupleMask emptyMask;
         private final TupleMask identityMask;
-        private final IQueryResultProvider backend;
         private final Indexer emptyMaskIndexer;
 
         public RelationalViatraMatcher(ViatraModelQueryAdapterImpl adapter, RelationalQuery query,
                                                                    RawPatternMatcher rawPatternMatcher) {
-                this.adapter = adapter;
-                this.query = query;
+                super(adapter, query, rawPatternMatcher);
                 int arity = query.arity();
                 emptyMask = TupleMask.empty(arity);
                 identityMask = TupleMask.identity(arity);
-                backend = rawPatternMatcher.getBackend();
                 if (backend instanceof RetePatternMatcher reteBackend) {
                         emptyMaskIndexer = IndexerUtils.getIndexer(reteBackend, emptyMask);
                 } else {
@@ -53,16 +44,6 @@ public class RelationalViatraMatcher implements ResultSet<Boolean> {
         }
 
         @Override
-        public ModelQueryAdapter getAdapter() {
-                return adapter;
-        }
-
-        @Override
-        public Query<Boolean> getQuery() {
-                return query;
-        }
-
-        @Override
         public Boolean get(Tuple parameters) {
                 var tuple = MatcherUtils.toViatraTuple(parameters);
                 if (emptyMaskIndexer == null) {
@@ -90,4 +71,10 @@ public class RelationalViatraMatcher implements ResultSet<Boolean> {
                 var matches = emptyMaskIndexer.get(Tuples.staticArityFlatTupleOf());
                 return matches == null ? 0 : matches.size();
         }
+
+        @Override
+        public void update(org.eclipse.viatra.query.runtime.matchers.tuple.Tuple updateElement, boolean isInsertion) {
+                var key = MatcherUtils.toRefineryTuple(updateElement);
+                notifyChange(key, !isInsertion, isInsertion);
+        }
 }
diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/UnsafeFunctionalCursor.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/UnsafeFunctionalCursor.java
index 4a41d724..b0b507fe 100644
--- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/UnsafeFunctionalCursor.java
+++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/matcher/UnsafeFunctionalCursor.java
@@ -46,9 +46,7 @@ class UnsafeFunctionalCursor<T> implements Cursor<Tuple, T> {
                 if (!terminated && tuplesIterator.hasNext()) {
                         var match = tuplesIterator.next();
                         key = MatcherUtils.keyToRefineryTuple(match);
-                        @SuppressWarnings("unchecked")
-                        var typedValue = (T) match.get(match.getSize() - 1);
-                        value = typedValue;
+                        value = MatcherUtils.getValue(match);
                         return true;
                 }
                 terminated = true;
diff --git a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/OrderedResultSetTest.java b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/OrderedResultSetTest.java
new file mode 100644
index 00000000..8ede6c80
--- /dev/null
+++ b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/OrderedResultSetTest.java
@@ -0,0 +1,117 @@
+/*
+ * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.store.query.viatra;
+
+import org.junit.jupiter.api.Test;
+import tools.refinery.store.model.ModelStore;
+import tools.refinery.store.query.ModelQueryAdapter;
+import tools.refinery.store.query.dnf.Query;
+import tools.refinery.store.query.resultset.OrderedResultSet;
+import tools.refinery.store.query.term.Variable;
+import tools.refinery.store.query.view.AnySymbolView;
+import tools.refinery.store.query.view.KeyOnlyView;
+import tools.refinery.store.representation.Symbol;
+import tools.refinery.store.tuple.Tuple;
+
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.hamcrest.Matchers.is;
+
+class OrderedResultSetTest {
+        private static final Symbol<Boolean> friend = Symbol.of("friend", 2);
+        private static final AnySymbolView friendView = new KeyOnlyView<>(friend);
+
+        @Test
+        void relationalFlushTest() {
+                var query = Query.of("Relation", (builder, p1, p2) -> builder.clause(
+                                 friendView.call(p1, p2)
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(friend)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var resultSet = queryEngine.getResultSet(query);
+
+                friendInterpretation.put(Tuple.of(0, 1), true);
+                friendInterpretation.put(Tuple.of(1, 2), true);
+                friendInterpretation.put(Tuple.of(1, 1), true);
+                queryEngine.flushChanges();
+
+                try (var orderedResultSet = new OrderedResultSet<>(resultSet)) {
+                        assertThat(orderedResultSet.size(), is(3));
+                        assertThat(orderedResultSet.getKey(0), is(Tuple.of(0, 1)));
+                        assertThat(orderedResultSet.getKey(1), is(Tuple.of(1, 1)));
+                        assertThat(orderedResultSet.getKey(2), is(Tuple.of(1, 2)));
+
+                        friendInterpretation.put(Tuple.of(1, 2), false);
+                        friendInterpretation.put(Tuple.of(0, 2), true);
+                        queryEngine.flushChanges();
+
+                        assertThat(orderedResultSet.size(), is(3));
+                        assertThat(orderedResultSet.getKey(0), is(Tuple.of(0, 1)));
+                        assertThat(orderedResultSet.getKey(1), is(Tuple.of(0, 2)));
+                        assertThat(orderedResultSet.getKey(2), is(Tuple.of(1, 1)));
+                }
+        }
+
+        @Test
+        void functionalFlushTest() {
+                var query = Query.of("Function", Integer.class, (builder, p1, output) -> builder.clause(
+                                friendView.call(p1, Variable.of()),
+                                output.assign(friendView.count(p1, Variable.of()))
+                ));
+
+                var store = ModelStore.builder()
+                                .symbols(friend)
+                                .with(ViatraModelQueryAdapter.builder()
+                                                .queries(query))
+                                .build();
+
+                var model = store.createEmptyModel();
+                var friendInterpretation = model.getInterpretation(friend);
+                var queryEngine = model.getAdapter(ModelQueryAdapter.class);
+                var resultSet = queryEngine.getResultSet(query);
+
+                friendInterpretation.put(Tuple.of(0, 1), true);
+                friendInterpretation.put(Tuple.of(1, 2), true);
+                friendInterpretation.put(Tuple.of(1, 1), true);
+                queryEngine.flushChanges();
+
+                try (var orderedResultSet = new OrderedResultSet<>(resultSet)) {
+                        assertThat(orderedResultSet.size(), is(2));
+                        assertThat(orderedResultSet.getKey(0), is(Tuple.of(0)));
+                        assertThat(orderedResultSet.getKey(1), is(Tuple.of(1)));
+
+                        friendInterpretation.put(Tuple.of(0, 1), false);
+                        friendInterpretation.put(Tuple.of(2, 1), true);
+                        queryEngine.flushChanges();
+
+                        assertThat(orderedResultSet.size(), is(2));
+                        assertThat(orderedResultSet.getKey(0), is(Tuple.of(1)));
+                        assertThat(orderedResultSet.getKey(1), is(Tuple.of(2)));
+
+                        friendInterpretation.put(Tuple.of(1, 1), false);
+                        queryEngine.flushChanges();
+
+                        assertThat(orderedResultSet.size(), is(2));
+                        assertThat(orderedResultSet.getKey(0), is(Tuple.of(1)));
+                        assertThat(orderedResultSet.getKey(1), is(Tuple.of(2)));
+
+                        friendInterpretation.put(Tuple.of(1, 2), false);
+                        friendInterpretation.put(Tuple.of(1, 0), true);
+                        queryEngine.flushChanges();
+
+                        assertThat(orderedResultSet.size(), is(2));
+                        assertThat(orderedResultSet.getKey(0), is(Tuple.of(1)));
+                        assertThat(orderedResultSet.getKey(1), is(Tuple.of(2)));
+                }
+        }
+}
diff --git a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/tests/QueryAssertions.java b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/tests/QueryAssertions.java
index 7a25cfdc..ca089a9d 100644
--- a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/tests/QueryAssertions.java
+++ b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/tests/QueryAssertions.java
@@ -6,7 +6,7 @@
 package tools.refinery.store.query.viatra.tests;
 
 import org.junit.jupiter.api.function.Executable;
-import tools.refinery.store.query.ResultSet;
+import tools.refinery.store.query.resultset.ResultSet;
 import tools.refinery.store.tuple.Tuple;
 
 import java.util.*;