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/src | |
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/src')
6 files changed, 90 insertions, 1 deletions
diff --git a/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple.java b/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple.java index 6700417a..aae7b344 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple.java +++ b/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple.java | |||
@@ -5,11 +5,29 @@ | |||
5 | */ | 5 | */ |
6 | package tools.refinery.store.tuple; | 6 | package tools.refinery.store.tuple; |
7 | 7 | ||
8 | public sealed interface Tuple permits Tuple0, Tuple1, Tuple2, Tuple3, Tuple4, TupleN { | 8 | import org.jetbrains.annotations.NotNull; |
9 | |||
10 | public sealed interface Tuple extends Comparable<Tuple> permits Tuple0, Tuple1, Tuple2, Tuple3, Tuple4, TupleN { | ||
9 | int getSize(); | 11 | int getSize(); |
10 | 12 | ||
11 | int get(int element); | 13 | int get(int element); |
12 | 14 | ||
15 | @Override | ||
16 | default int compareTo(@NotNull Tuple other) { | ||
17 | int size = getSize(); | ||
18 | int compareSize = Integer.compare(size, other.getSize()); | ||
19 | if (compareSize != 0) { | ||
20 | return compareSize; | ||
21 | } | ||
22 | for (int i = 0; i < size; i++) { | ||
23 | int compareElement = Integer.compare(get(i), other.get(i)); | ||
24 | if (compareElement != 0) { | ||
25 | return compareElement; | ||
26 | } | ||
27 | } | ||
28 | return 0; | ||
29 | } | ||
30 | |||
13 | static Tuple0 of() { | 31 | static Tuple0 of() { |
14 | return Tuple0.INSTANCE; | 32 | return Tuple0.INSTANCE; |
15 | } | 33 | } |
diff --git a/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple0.java b/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple0.java index 1451099c..a9aa9bf2 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple0.java +++ b/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple0.java | |||
@@ -8,6 +8,10 @@ package tools.refinery.store.tuple; | |||
8 | import static tools.refinery.store.tuple.TupleConstants.TUPLE_BEGIN; | 8 | import static tools.refinery.store.tuple.TupleConstants.TUPLE_BEGIN; |
9 | import static tools.refinery.store.tuple.TupleConstants.TUPLE_END; | 9 | import static tools.refinery.store.tuple.TupleConstants.TUPLE_END; |
10 | 10 | ||
11 | /** | ||
12 | * Singleton implementation to ensure only a single empty tuple exists. | ||
13 | */ | ||
14 | @SuppressWarnings("squid:S6548") | ||
11 | public final class Tuple0 implements Tuple { | 15 | public final class Tuple0 implements Tuple { |
12 | public static final Tuple0 INSTANCE = new Tuple0(); | 16 | public static final Tuple0 INSTANCE = new Tuple0(); |
13 | 17 | ||
diff --git a/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple1.java b/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple1.java index cda145d7..388ee3a9 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple1.java +++ b/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple1.java | |||
@@ -5,6 +5,7 @@ | |||
5 | */ | 5 | */ |
6 | package tools.refinery.store.tuple; | 6 | package tools.refinery.store.tuple; |
7 | 7 | ||
8 | import org.jetbrains.annotations.NotNull; | ||
8 | import tools.refinery.store.model.TupleHashProvider; | 9 | import tools.refinery.store.model.TupleHashProvider; |
9 | 10 | ||
10 | import java.util.Arrays; | 11 | import java.util.Arrays; |
@@ -54,11 +55,23 @@ public final class Tuple1 implements Tuple { | |||
54 | return 31 + value0; | 55 | return 31 + value0; |
55 | } | 56 | } |
56 | 57 | ||
58 | @Override | ||
59 | public int compareTo(@NotNull Tuple other) { | ||
60 | if (other instanceof Tuple1 other1) { | ||
61 | return Integer.compare(value0, other1.value0); | ||
62 | } | ||
63 | return Tuple.super.compareTo(other); | ||
64 | } | ||
65 | |||
57 | /** | 66 | /** |
58 | * This class uses safe double-checked locking, see | 67 | * This class uses safe double-checked locking, see |
59 | * <a href="https://shipilev.net/blog/2014/safe-public-construction/">Safe Publication and Safe Initialization in | 68 | * <a href="https://shipilev.net/blog/2014/safe-public-construction/">Safe Publication and Safe Initialization in |
60 | * Java</a> for details. | 69 | * Java</a> for details. |
70 | * <p> | ||
71 | * This class implements the singleton pattern to ensure only a single cache exists. This is thread-safe because | ||
72 | * of the locking of the cache. | ||
61 | */ | 73 | */ |
74 | @SuppressWarnings("squid:S6548") | ||
62 | public static class Cache { | 75 | public static class Cache { |
63 | private static final int MIN_CACHE_SIZE = 256; | 76 | private static final int MIN_CACHE_SIZE = 256; |
64 | 77 | ||
diff --git a/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple2.java b/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple2.java index b669674b..6d886fd3 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple2.java +++ b/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple2.java | |||
@@ -5,6 +5,8 @@ | |||
5 | */ | 5 | */ |
6 | package tools.refinery.store.tuple; | 6 | package tools.refinery.store.tuple; |
7 | 7 | ||
8 | import org.jetbrains.annotations.NotNull; | ||
9 | |||
8 | import static tools.refinery.store.tuple.TupleConstants.*; | 10 | import static tools.refinery.store.tuple.TupleConstants.*; |
9 | 11 | ||
10 | public record Tuple2(int value0, int value1) implements Tuple { | 12 | public record Tuple2(int value0, int value1) implements Tuple { |
@@ -41,4 +43,16 @@ public record Tuple2(int value0, int value1) implements Tuple { | |||
41 | hash = 31 * hash + value1; | 43 | hash = 31 * hash + value1; |
42 | return hash; | 44 | return hash; |
43 | } | 45 | } |
46 | |||
47 | @Override | ||
48 | public int compareTo(@NotNull Tuple other) { | ||
49 | if (other instanceof Tuple2 other2) { | ||
50 | int compare0 = Integer.compare(value0, other2.value0); | ||
51 | if (compare0 != 0) { | ||
52 | return compare0; | ||
53 | } | ||
54 | return Integer.compare(value1, other2.value1); | ||
55 | } | ||
56 | return Tuple.super.compareTo(other); | ||
57 | } | ||
44 | } | 58 | } |
diff --git a/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple3.java b/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple3.java index 542ed328..734e45c2 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple3.java +++ b/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple3.java | |||
@@ -5,6 +5,8 @@ | |||
5 | */ | 5 | */ |
6 | package tools.refinery.store.tuple; | 6 | package tools.refinery.store.tuple; |
7 | 7 | ||
8 | import org.jetbrains.annotations.NotNull; | ||
9 | |||
8 | import static tools.refinery.store.tuple.TupleConstants.*; | 10 | import static tools.refinery.store.tuple.TupleConstants.*; |
9 | 11 | ||
10 | public record Tuple3(int value0, int value1, int value2) implements Tuple { | 12 | public record Tuple3(int value0, int value1, int value2) implements Tuple { |
@@ -43,4 +45,20 @@ public record Tuple3(int value0, int value1, int value2) implements Tuple { | |||
43 | hash = 31 * hash + value2; | 45 | hash = 31 * hash + value2; |
44 | return hash; | 46 | return hash; |
45 | } | 47 | } |
48 | |||
49 | @Override | ||
50 | public int compareTo(@NotNull Tuple other) { | ||
51 | if (other instanceof Tuple3 other3) { | ||
52 | int compare0 = Integer.compare(value0, other3.value0); | ||
53 | if (compare0 != 0) { | ||
54 | return compare0; | ||
55 | } | ||
56 | int compare1 = Integer.compare(value1, other3.value1); | ||
57 | if (compare1 != 0) { | ||
58 | return compare1; | ||
59 | } | ||
60 | return Integer.compare(value2, other3.value2); | ||
61 | } | ||
62 | return Tuple.super.compareTo(other); | ||
63 | } | ||
46 | } | 64 | } |
diff --git a/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple4.java b/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple4.java index 121a15f6..e1b93e7b 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple4.java +++ b/subprojects/store/src/main/java/tools/refinery/store/tuple/Tuple4.java | |||
@@ -5,6 +5,8 @@ | |||
5 | */ | 5 | */ |
6 | package tools.refinery.store.tuple; | 6 | package tools.refinery.store.tuple; |
7 | 7 | ||
8 | import org.jetbrains.annotations.NotNull; | ||
9 | |||
8 | import static tools.refinery.store.tuple.TupleConstants.*; | 10 | import static tools.refinery.store.tuple.TupleConstants.*; |
9 | 11 | ||
10 | public record Tuple4(int value0, int value1, int value2, int value3) implements Tuple { | 12 | public record Tuple4(int value0, int value1, int value2, int value3) implements Tuple { |
@@ -46,4 +48,24 @@ public record Tuple4(int value0, int value1, int value2, int value3) implements | |||
46 | hash = 31 * hash + value3; | 48 | hash = 31 * hash + value3; |
47 | return hash; | 49 | return hash; |
48 | } | 50 | } |
51 | |||
52 | @Override | ||
53 | public int compareTo(@NotNull Tuple other) { | ||
54 | if (other instanceof Tuple4 other4) { | ||
55 | int compare0 = Integer.compare(value0, other4.value0); | ||
56 | if (compare0 != 0) { | ||
57 | return compare0; | ||
58 | } | ||
59 | int compare1 = Integer.compare(value1, other4.value1); | ||
60 | if (compare1 != 0) { | ||
61 | return compare1; | ||
62 | } | ||
63 | int compare2 = Integer.compare(value2, other4.value2); | ||
64 | if (compare2 != 0) { | ||
65 | return compare2; | ||
66 | } | ||
67 | return Integer.compare(value3, other4.value3); | ||
68 | } | ||
69 | return Tuple.super.compareTo(other); | ||
70 | } | ||
49 | } | 71 | } |