From 8d79e7f39df0fde9b4f0ba8e6264f2900e9024c6 Mon Sep 17 00:00:00 2001 From: Kristóf Marussy Date: Thu, 29 Jun 2023 02:08:40 +0200 Subject: 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. --- .../store/query/viatra/OrderedResultSetTest.java | 117 +++++++++++++++++++++ .../store/query/viatra/tests/QueryAssertions.java | 2 +- 2 files changed, 118 insertions(+), 1 deletion(-) create mode 100644 subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/OrderedResultSetTest.java (limited to 'subprojects/store-query-viatra/src/test') 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 + * + * 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 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.*; -- cgit v1.2.3-54-g00ecf