diff options
author | Kristóf Marussy <kristof@marussy.com> | 2023-06-29 02:08:40 +0200 |
---|---|---|
committer | Kristóf Marussy <kristof@marussy.com> | 2023-06-29 02:22:13 +0200 |
commit | 8d79e7f39df0fde9b4f0ba8e6264f2900e9024c6 (patch) | |
tree | 9cc6850dba18ed526eb27a911bc3f73b28752a14 /subprojects/store-query-viatra/src/main | |
parent | fix: FilteredView default value (diff) | |
download | refinery-8d79e7f39df0fde9b4f0ba8e6264f2900e9024c6.tar.gz refinery-8d79e7f39df0fde9b4f0ba8e6264f2900e9024c6.tar.zst refinery-8d79e7f39df0fde9b4f0ba8e6264f2900e9024c6.zip |
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.
Diffstat (limited to 'subprojects/store-query-viatra/src/main')
6 files changed, 65 insertions, 50 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; | |||
13 | import org.eclipse.viatra.query.runtime.matchers.backend.IQueryBackendFactory; | 13 | import org.eclipse.viatra.query.runtime.matchers.backend.IQueryBackendFactory; |
14 | import tools.refinery.store.model.Model; | 14 | import tools.refinery.store.model.Model; |
15 | import tools.refinery.store.model.ModelListener; | 15 | import tools.refinery.store.model.ModelListener; |
16 | import tools.refinery.store.query.AnyResultSet; | 16 | import tools.refinery.store.query.resultset.AnyResultSet; |
17 | import tools.refinery.store.query.EmptyResultSet; | 17 | import tools.refinery.store.query.resultset.EmptyResultSet; |
18 | import tools.refinery.store.query.ResultSet; | 18 | import tools.refinery.store.query.resultset.ResultSet; |
19 | import tools.refinery.store.query.dnf.AnyQuery; | 19 | import tools.refinery.store.query.dnf.AnyQuery; |
20 | import tools.refinery.store.query.dnf.FunctionalQuery; | 20 | import tools.refinery.store.query.dnf.FunctionalQuery; |
21 | import tools.refinery.store.query.dnf.Query; | 21 | 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 @@ | |||
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.viatra.internal.matcher; | ||
7 | |||
8 | import org.eclipse.viatra.query.runtime.matchers.backend.IQueryResultProvider; | ||
9 | import org.eclipse.viatra.query.runtime.matchers.backend.IUpdateable; | ||
10 | import tools.refinery.store.query.dnf.Query; | ||
11 | import tools.refinery.store.query.resultset.AbstractResultSet; | ||
12 | import tools.refinery.store.query.viatra.internal.ViatraModelQueryAdapterImpl; | ||
13 | |||
14 | public abstract class AbstractViatraMatcher<T> extends AbstractResultSet<T> implements IUpdateable { | ||
15 | protected final IQueryResultProvider backend; | ||
16 | |||
17 | protected AbstractViatraMatcher(ViatraModelQueryAdapterImpl adapter, Query<T> query, | ||
18 | RawPatternMatcher rawPatternMatcher) { | ||
19 | super(adapter, query); | ||
20 | backend = rawPatternMatcher.getBackend(); | ||
21 | } | ||
22 | |||
23 | @Override | ||
24 | protected void startListeningForChanges() { | ||
25 | backend.addUpdateListener(this, this, false); | ||
26 | } | ||
27 | |||
28 | @Override | ||
29 | protected void stopListeningForChanges() { | ||
30 | backend.removeUpdateListener(this); | ||
31 | } | ||
32 | } | ||
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 @@ | |||
5 | */ | 5 | */ |
6 | package tools.refinery.store.query.viatra.internal.matcher; | 6 | package tools.refinery.store.query.viatra.internal.matcher; |
7 | 7 | ||
8 | import org.eclipse.viatra.query.runtime.matchers.backend.IQueryResultProvider; | ||
9 | import org.eclipse.viatra.query.runtime.matchers.tuple.TupleMask; | 8 | import org.eclipse.viatra.query.runtime.matchers.tuple.TupleMask; |
10 | import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples; | 9 | import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples; |
11 | import org.eclipse.viatra.query.runtime.rete.index.IterableIndexer; | 10 | import org.eclipse.viatra.query.runtime.rete.index.IterableIndexer; |
12 | import org.eclipse.viatra.query.runtime.rete.matcher.RetePatternMatcher; | 11 | import org.eclipse.viatra.query.runtime.rete.matcher.RetePatternMatcher; |
13 | import tools.refinery.store.map.Cursor; | 12 | import tools.refinery.store.map.Cursor; |
14 | import tools.refinery.store.query.ModelQueryAdapter; | ||
15 | import tools.refinery.store.query.ResultSet; | ||
16 | import tools.refinery.store.query.dnf.FunctionalQuery; | 13 | import tools.refinery.store.query.dnf.FunctionalQuery; |
17 | import tools.refinery.store.query.dnf.Query; | ||
18 | import tools.refinery.store.query.viatra.internal.ViatraModelQueryAdapterImpl; | 14 | import tools.refinery.store.query.viatra.internal.ViatraModelQueryAdapterImpl; |
19 | import tools.refinery.store.tuple.Tuple; | 15 | import tools.refinery.store.tuple.Tuple; |
20 | 16 | ||
@@ -28,23 +24,18 @@ import tools.refinery.store.tuple.Tuple; | |||
28 | * implementation for these methods. | 24 | * implementation for these methods. |
29 | * Using this class with any other runtime context may lead to undefined behavior. | 25 | * Using this class with any other runtime context may lead to undefined behavior. |
30 | */ | 26 | */ |
31 | public class FunctionalViatraMatcher<T> implements ResultSet<T> { | 27 | public class FunctionalViatraMatcher<T> extends AbstractViatraMatcher<T> { |
32 | private final ViatraModelQueryAdapterImpl adapter; | ||
33 | private final FunctionalQuery<T> query; | ||
34 | private final TupleMask emptyMask; | 28 | private final TupleMask emptyMask; |
35 | private final TupleMask omitOutputMask; | 29 | private final TupleMask omitOutputMask; |
36 | private final IQueryResultProvider backend; | ||
37 | private final IterableIndexer omitOutputIndexer; | 30 | private final IterableIndexer omitOutputIndexer; |
38 | 31 | ||
39 | public FunctionalViatraMatcher(ViatraModelQueryAdapterImpl adapter, FunctionalQuery<T> query, | 32 | public FunctionalViatraMatcher(ViatraModelQueryAdapterImpl adapter, FunctionalQuery<T> query, |
40 | RawPatternMatcher rawPatternMatcher) { | 33 | RawPatternMatcher rawPatternMatcher) { |
41 | this.adapter = adapter; | 34 | super(adapter, query, rawPatternMatcher); |
42 | this.query = query; | ||
43 | int arity = query.arity(); | 35 | int arity = query.arity(); |
44 | int arityWithOutput = arity + 1; | 36 | int arityWithOutput = arity + 1; |
45 | emptyMask = TupleMask.empty(arityWithOutput); | 37 | emptyMask = TupleMask.empty(arityWithOutput); |
46 | omitOutputMask = TupleMask.omit(arity, arityWithOutput); | 38 | omitOutputMask = TupleMask.omit(arity, arityWithOutput); |
47 | backend = rawPatternMatcher.getBackend(); | ||
48 | if (backend instanceof RetePatternMatcher reteBackend) { | 39 | if (backend instanceof RetePatternMatcher reteBackend) { |
49 | var maybeIterableOmitOutputIndexer = IndexerUtils.getIndexer(reteBackend, omitOutputMask); | 40 | var maybeIterableOmitOutputIndexer = IndexerUtils.getIndexer(reteBackend, omitOutputMask); |
50 | if (maybeIterableOmitOutputIndexer instanceof IterableIndexer iterableOmitOutputIndexer) { | 41 | if (maybeIterableOmitOutputIndexer instanceof IterableIndexer iterableOmitOutputIndexer) { |
@@ -58,16 +49,6 @@ public class FunctionalViatraMatcher<T> implements ResultSet<T> { | |||
58 | } | 49 | } |
59 | 50 | ||
60 | @Override | 51 | @Override |
61 | public ModelQueryAdapter getAdapter() { | ||
62 | return adapter; | ||
63 | } | ||
64 | |||
65 | @Override | ||
66 | public Query<T> getQuery() { | ||
67 | return query; | ||
68 | } | ||
69 | |||
70 | @Override | ||
71 | public T get(Tuple parameters) { | 52 | public T get(Tuple parameters) { |
72 | var tuple = MatcherUtils.toViatraTuple(parameters); | 53 | var tuple = MatcherUtils.toViatraTuple(parameters); |
73 | if (omitOutputIndexer == null) { | 54 | if (omitOutputIndexer == null) { |
@@ -93,4 +74,15 @@ public class FunctionalViatraMatcher<T> implements ResultSet<T> { | |||
93 | } | 74 | } |
94 | return omitOutputIndexer.getBucketCount(); | 75 | return omitOutputIndexer.getBucketCount(); |
95 | } | 76 | } |
77 | |||
78 | @Override | ||
79 | public void update(org.eclipse.viatra.query.runtime.matchers.tuple.Tuple updateElement, boolean isInsertion) { | ||
80 | var key = MatcherUtils.keyToRefineryTuple(updateElement); | ||
81 | var value = MatcherUtils.<T>getValue(updateElement); | ||
82 | if (isInsertion) { | ||
83 | notifyChange(key, null, value); | ||
84 | } else { | ||
85 | notifyChange(key, value, null); | ||
86 | } | ||
87 | } | ||
96 | } | 88 | } |
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 { | |||
86 | return getWrapper(viatraTuple, index).value0(); | 86 | return getWrapper(viatraTuple, index).value0(); |
87 | } | 87 | } |
88 | 88 | ||
89 | public static <T> T getValue(ITuple match) { | ||
90 | // This is only safe if we know for sure that match came from a functional query of type {@code T}. | ||
91 | @SuppressWarnings("unchecked") | ||
92 | var result = (T) match.get(match.getSize() - 1); | ||
93 | return result; | ||
94 | } | ||
95 | |||
89 | public static <T> T getSingleValue(@Nullable Iterable<? extends ITuple> viatraTuples) { | 96 | public static <T> T getSingleValue(@Nullable Iterable<? extends ITuple> viatraTuples) { |
90 | if (viatraTuples == null) { | 97 | if (viatraTuples == null) { |
91 | return null; | 98 | return null; |
@@ -98,8 +105,7 @@ final class MatcherUtils { | |||
98 | return null; | 105 | return null; |
99 | } | 106 | } |
100 | var match = iterator.next(); | 107 | var match = iterator.next(); |
101 | @SuppressWarnings("unchecked") | 108 | var result = MatcherUtils.<T>getValue(match); |
102 | var result = (T) match.get(match.getSize() - 1); | ||
103 | if (iterator.hasNext()) { | 109 | if (iterator.hasNext()) { |
104 | var input = keyToRefineryTuple(match); | 110 | var input = keyToRefineryTuple(match); |
105 | throw new IllegalStateException("Query is not functional for input tuple: " + input); | 111 | 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 @@ | |||
5 | */ | 5 | */ |
6 | package tools.refinery.store.query.viatra.internal.matcher; | 6 | package tools.refinery.store.query.viatra.internal.matcher; |
7 | 7 | ||
8 | import org.eclipse.viatra.query.runtime.matchers.backend.IQueryResultProvider; | ||
9 | import org.eclipse.viatra.query.runtime.matchers.tuple.TupleMask; | 8 | import org.eclipse.viatra.query.runtime.matchers.tuple.TupleMask; |
10 | import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples; | 9 | import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples; |
11 | import org.eclipse.viatra.query.runtime.rete.index.Indexer; | 10 | import org.eclipse.viatra.query.runtime.rete.index.Indexer; |
12 | import org.eclipse.viatra.query.runtime.rete.matcher.RetePatternMatcher; | 11 | import org.eclipse.viatra.query.runtime.rete.matcher.RetePatternMatcher; |
13 | import tools.refinery.store.map.Cursor; | 12 | import tools.refinery.store.map.Cursor; |
14 | import tools.refinery.store.map.Cursors; | 13 | import tools.refinery.store.map.Cursors; |
15 | import tools.refinery.store.query.ModelQueryAdapter; | ||
16 | import tools.refinery.store.query.ResultSet; | ||
17 | import tools.refinery.store.query.dnf.Query; | ||
18 | import tools.refinery.store.query.dnf.RelationalQuery; | 14 | import tools.refinery.store.query.dnf.RelationalQuery; |
19 | import tools.refinery.store.query.viatra.internal.ViatraModelQueryAdapterImpl; | 15 | import tools.refinery.store.query.viatra.internal.ViatraModelQueryAdapterImpl; |
20 | import tools.refinery.store.tuple.Tuple; | 16 | import tools.refinery.store.tuple.Tuple; |
@@ -29,22 +25,17 @@ import tools.refinery.store.tuple.Tuple; | |||
29 | * implementation for these methods. | 25 | * implementation for these methods. |
30 | * Using this class with any other runtime context may lead to undefined behavior. | 26 | * Using this class with any other runtime context may lead to undefined behavior. |
31 | */ | 27 | */ |
32 | public class RelationalViatraMatcher implements ResultSet<Boolean> { | 28 | public class RelationalViatraMatcher extends AbstractViatraMatcher<Boolean> { |
33 | private final ViatraModelQueryAdapterImpl adapter; | ||
34 | private final RelationalQuery query; | ||
35 | private final TupleMask emptyMask; | 29 | private final TupleMask emptyMask; |
36 | private final TupleMask identityMask; | 30 | private final TupleMask identityMask; |
37 | private final IQueryResultProvider backend; | ||
38 | private final Indexer emptyMaskIndexer; | 31 | private final Indexer emptyMaskIndexer; |
39 | 32 | ||
40 | public RelationalViatraMatcher(ViatraModelQueryAdapterImpl adapter, RelationalQuery query, | 33 | public RelationalViatraMatcher(ViatraModelQueryAdapterImpl adapter, RelationalQuery query, |
41 | RawPatternMatcher rawPatternMatcher) { | 34 | RawPatternMatcher rawPatternMatcher) { |
42 | this.adapter = adapter; | 35 | super(adapter, query, rawPatternMatcher); |
43 | this.query = query; | ||
44 | int arity = query.arity(); | 36 | int arity = query.arity(); |
45 | emptyMask = TupleMask.empty(arity); | 37 | emptyMask = TupleMask.empty(arity); |
46 | identityMask = TupleMask.identity(arity); | 38 | identityMask = TupleMask.identity(arity); |
47 | backend = rawPatternMatcher.getBackend(); | ||
48 | if (backend instanceof RetePatternMatcher reteBackend) { | 39 | if (backend instanceof RetePatternMatcher reteBackend) { |
49 | emptyMaskIndexer = IndexerUtils.getIndexer(reteBackend, emptyMask); | 40 | emptyMaskIndexer = IndexerUtils.getIndexer(reteBackend, emptyMask); |
50 | } else { | 41 | } else { |
@@ -53,16 +44,6 @@ public class RelationalViatraMatcher implements ResultSet<Boolean> { | |||
53 | } | 44 | } |
54 | 45 | ||
55 | @Override | 46 | @Override |
56 | public ModelQueryAdapter getAdapter() { | ||
57 | return adapter; | ||
58 | } | ||
59 | |||
60 | @Override | ||
61 | public Query<Boolean> getQuery() { | ||
62 | return query; | ||
63 | } | ||
64 | |||
65 | @Override | ||
66 | public Boolean get(Tuple parameters) { | 47 | public Boolean get(Tuple parameters) { |
67 | var tuple = MatcherUtils.toViatraTuple(parameters); | 48 | var tuple = MatcherUtils.toViatraTuple(parameters); |
68 | if (emptyMaskIndexer == null) { | 49 | if (emptyMaskIndexer == null) { |
@@ -90,4 +71,10 @@ public class RelationalViatraMatcher implements ResultSet<Boolean> { | |||
90 | var matches = emptyMaskIndexer.get(Tuples.staticArityFlatTupleOf()); | 71 | var matches = emptyMaskIndexer.get(Tuples.staticArityFlatTupleOf()); |
91 | return matches == null ? 0 : matches.size(); | 72 | return matches == null ? 0 : matches.size(); |
92 | } | 73 | } |
74 | |||
75 | @Override | ||
76 | public void update(org.eclipse.viatra.query.runtime.matchers.tuple.Tuple updateElement, boolean isInsertion) { | ||
77 | var key = MatcherUtils.toRefineryTuple(updateElement); | ||
78 | notifyChange(key, !isInsertion, isInsertion); | ||
79 | } | ||
93 | } | 80 | } |
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> { | |||
46 | if (!terminated && tuplesIterator.hasNext()) { | 46 | if (!terminated && tuplesIterator.hasNext()) { |
47 | var match = tuplesIterator.next(); | 47 | var match = tuplesIterator.next(); |
48 | key = MatcherUtils.keyToRefineryTuple(match); | 48 | key = MatcherUtils.keyToRefineryTuple(match); |
49 | @SuppressWarnings("unchecked") | 49 | value = MatcherUtils.getValue(match); |
50 | var typedValue = (T) match.get(match.getSize() - 1); | ||
51 | value = typedValue; | ||
52 | return true; | 50 | return true; |
53 | } | 51 | } |
54 | terminated = true; | 52 | terminated = true; |