diff options
Diffstat (limited to 'subprojects/language-semantics/src')
8 files changed, 715 insertions, 0 deletions
diff --git a/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/ModelInitializer.java b/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/ModelInitializer.java new file mode 100644 index 00000000..830d4a2c --- /dev/null +++ b/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/ModelInitializer.java | |||
@@ -0,0 +1,9 @@ | |||
1 | package tools.refinery.language.semantics.model; | ||
2 | |||
3 | import tools.refinery.language.utils.CollectedSymbols; | ||
4 | |||
5 | public class ModelInitializer { | ||
6 | public void createModel(CollectedSymbols symbols) { | ||
7 | |||
8 | } | ||
9 | } | ||
diff --git a/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/DecisionTree.java b/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/DecisionTree.java new file mode 100644 index 00000000..8c185509 --- /dev/null +++ b/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/DecisionTree.java | |||
@@ -0,0 +1,41 @@ | |||
1 | package tools.refinery.language.semantics.model.internal; | ||
2 | |||
3 | import org.eclipse.collections.api.factory.primitive.IntObjectMaps; | ||
4 | import tools.refinery.store.map.Cursor; | ||
5 | import tools.refinery.store.model.Tuple; | ||
6 | import tools.refinery.store.model.representation.TruthValue; | ||
7 | |||
8 | public class DecisionTree { | ||
9 | private final int levels; | ||
10 | |||
11 | private final DecisionTreeNode root; | ||
12 | |||
13 | public DecisionTree(int levels, TruthValue initialValue) { | ||
14 | this.levels = levels; | ||
15 | DecisionTreeNode node = new TerminalNode(IntObjectMaps.mutable.empty(), | ||
16 | DecisionTreeValue.fromTruthValue(initialValue)); | ||
17 | for (int level = 1; level < levels; level++) { | ||
18 | node = new IntermediateNode(IntObjectMaps.mutable.empty(), node); | ||
19 | } | ||
20 | root = node; | ||
21 | } | ||
22 | |||
23 | public TruthValue get(Tuple tuple) { | ||
24 | return root.getValue(levels - 1, tuple).getTruthValue(); | ||
25 | } | ||
26 | |||
27 | public void mergeValue(Tuple tuple, TruthValue truthValue) { | ||
28 | if (truthValue == null) { | ||
29 | return; | ||
30 | } | ||
31 | root.mergeValue(levels - 1, tuple, truthValue); | ||
32 | } | ||
33 | |||
34 | public void overwriteValues(DecisionTree values) { | ||
35 | root.overwriteValues(values.root); | ||
36 | } | ||
37 | |||
38 | public Cursor<Tuple, TruthValue> getCursor(TruthValue defaultValue, int nodeCount) { | ||
39 | return new DecisionTreeCursor(levels, defaultValue, nodeCount, root); | ||
40 | } | ||
41 | } | ||
diff --git a/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/DecisionTreeCursor.java b/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/DecisionTreeCursor.java new file mode 100644 index 00000000..8b02ba39 --- /dev/null +++ b/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/DecisionTreeCursor.java | |||
@@ -0,0 +1,94 @@ | |||
1 | package tools.refinery.language.semantics.model.internal; | ||
2 | |||
3 | import tools.refinery.store.map.Cursor; | ||
4 | import tools.refinery.store.map.VersionedMap; | ||
5 | import tools.refinery.store.model.Tuple; | ||
6 | import tools.refinery.store.model.representation.TruthValue; | ||
7 | |||
8 | import java.util.ArrayDeque; | ||
9 | import java.util.Deque; | ||
10 | import java.util.List; | ||
11 | |||
12 | class DecisionTreeCursor implements Cursor<Tuple, TruthValue> { | ||
13 | static final int STATE_FINISH = Integer.MAX_VALUE; | ||
14 | |||
15 | private final int levels; | ||
16 | |||
17 | final DecisionTreeValue defaultValue; | ||
18 | |||
19 | final int nodeCount; | ||
20 | |||
21 | private final DecisionTreeNode root; | ||
22 | |||
23 | final int[][] sortedChildren; | ||
24 | |||
25 | final int[] iterationState; | ||
26 | |||
27 | final int[] rawTuple; | ||
28 | |||
29 | final Deque<DecisionTreeNode> path = new ArrayDeque<>(); | ||
30 | |||
31 | private Tuple key; | ||
32 | |||
33 | DecisionTreeValue value = DecisionTreeValue.UNSET; | ||
34 | |||
35 | private boolean terminated; | ||
36 | |||
37 | public DecisionTreeCursor(int levels, TruthValue defaultValue, int nodeCount, DecisionTreeNode root) { | ||
38 | this.levels = levels; | ||
39 | this.defaultValue = DecisionTreeValue.fromTruthValue(defaultValue); | ||
40 | this.nodeCount = nodeCount; | ||
41 | this.root = root; | ||
42 | sortedChildren = new int[levels][]; | ||
43 | iterationState = new int[levels]; | ||
44 | for (int i = 0; i < levels; i++) { | ||
45 | iterationState[i] = STATE_FINISH; | ||
46 | } | ||
47 | rawTuple = new int[levels]; | ||
48 | } | ||
49 | |||
50 | @Override | ||
51 | public Tuple getKey() { | ||
52 | return key; | ||
53 | } | ||
54 | |||
55 | @Override | ||
56 | public TruthValue getValue() { | ||
57 | return value.getTruthValue(); | ||
58 | } | ||
59 | |||
60 | @Override | ||
61 | public boolean isTerminated() { | ||
62 | return terminated; | ||
63 | } | ||
64 | |||
65 | @Override | ||
66 | public boolean move() { | ||
67 | boolean found = false; | ||
68 | if (path.isEmpty() && !terminated) { | ||
69 | found = root.moveNext(levels - 1, this); | ||
70 | } | ||
71 | while (!found && !path.isEmpty()) { | ||
72 | int level = levels - path.size(); | ||
73 | found = path.peek().moveNext(level, this); | ||
74 | } | ||
75 | if (!found) { | ||
76 | key = null; | ||
77 | value = DecisionTreeValue.UNSET; | ||
78 | terminated = true; | ||
79 | return false; | ||
80 | } | ||
81 | key = Tuple.of(rawTuple); | ||
82 | return true; | ||
83 | } | ||
84 | |||
85 | @Override | ||
86 | public boolean isDirty() { | ||
87 | return false; | ||
88 | } | ||
89 | |||
90 | @Override | ||
91 | public List<VersionedMap<?, ?>> getDependingMaps() { | ||
92 | return List.of(); | ||
93 | } | ||
94 | } | ||
diff --git a/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/DecisionTreeNode.java b/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/DecisionTreeNode.java new file mode 100644 index 00000000..53954d62 --- /dev/null +++ b/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/DecisionTreeNode.java | |||
@@ -0,0 +1,84 @@ | |||
1 | package tools.refinery.language.semantics.model.internal; | ||
2 | |||
3 | import org.eclipse.collections.api.LazyIntIterable; | ||
4 | import tools.refinery.store.model.Tuple; | ||
5 | import tools.refinery.store.model.representation.TruthValue; | ||
6 | |||
7 | abstract class DecisionTreeNode { | ||
8 | public DecisionTreeValue getReducedValue() { | ||
9 | return getChildKeys().isEmpty() ? getOtherwiseReducedValue() : null; | ||
10 | } | ||
11 | |||
12 | public abstract DecisionTreeValue getValue(int level, Tuple tuple); | ||
13 | |||
14 | public abstract DecisionTreeNode deepCopy(); | ||
15 | |||
16 | public void mergeValue(int level, Tuple tuple, TruthValue value) { | ||
17 | int nextLevel = level - 1; | ||
18 | var key = tuple.get(level); | ||
19 | if (key < 0) { | ||
20 | mergeAllValues(nextLevel, tuple, value); | ||
21 | } else { | ||
22 | mergeSingleValue(key, nextLevel, tuple, value); | ||
23 | } | ||
24 | } | ||
25 | |||
26 | protected abstract void mergeAllValues(int nextLevel, Tuple tuple, TruthValue value); | ||
27 | |||
28 | protected abstract void mergeSingleValue(int key, int nextLevel, Tuple tuple, TruthValue value); | ||
29 | |||
30 | public DecisionTreeNode withMergedValue(int level, Tuple tuple, TruthValue value) { | ||
31 | var copy = deepCopy(); | ||
32 | copy.mergeValue(level, tuple, value); | ||
33 | return copy; | ||
34 | } | ||
35 | |||
36 | public abstract void overwriteValues(DecisionTreeNode values); | ||
37 | |||
38 | public DecisionTreeNode withOverwrittenValues(DecisionTreeNode values) { | ||
39 | var copy = deepCopy(); | ||
40 | copy.overwriteValues(values); | ||
41 | return copy; | ||
42 | } | ||
43 | |||
44 | public boolean moveNext(int level, DecisionTreeCursor cursor) { | ||
45 | var currentState = cursor.iterationState[level]; | ||
46 | boolean found; | ||
47 | if (currentState == DecisionTreeCursor.STATE_FINISH) { | ||
48 | // Entering this node for the first time. | ||
49 | cursor.path.push(this); | ||
50 | if (cursor.defaultValue == getOtherwiseReducedValue()) { | ||
51 | var sortedChildren = getChildKeys().toSortedArray(); | ||
52 | cursor.sortedChildren[level] = sortedChildren; | ||
53 | found = moveNextSparse(level, cursor, 0, sortedChildren); | ||
54 | } else { | ||
55 | found = moveNextDense(level, cursor, 0); | ||
56 | } | ||
57 | } else { | ||
58 | var sortedChildren = cursor.sortedChildren[level]; | ||
59 | if (sortedChildren == null) { | ||
60 | found = moveNextDense(level, cursor, currentState + 1); | ||
61 | } else { | ||
62 | found = moveNextSparse(level, cursor, currentState + 1, sortedChildren); | ||
63 | } | ||
64 | } | ||
65 | if (!found) { | ||
66 | cursor.sortedChildren[level] = null; | ||
67 | cursor.iterationState[level] = DecisionTreeCursor.STATE_FINISH; | ||
68 | var popped = cursor.path.pop(); | ||
69 | if (popped != this) { | ||
70 | throw new IllegalStateException("Invalid decision diagram cursor"); | ||
71 | } | ||
72 | } | ||
73 | return found; | ||
74 | } | ||
75 | |||
76 | protected abstract DecisionTreeValue getOtherwiseReducedValue(); | ||
77 | |||
78 | protected abstract LazyIntIterable getChildKeys(); | ||
79 | |||
80 | protected abstract boolean moveNextSparse(int level, DecisionTreeCursor cursor, int startIndex, | ||
81 | int[] sortedChildren); | ||
82 | |||
83 | protected abstract boolean moveNextDense(int level, DecisionTreeCursor cursor, int startIndex); | ||
84 | } | ||
diff --git a/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/DecisionTreeValue.java b/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/DecisionTreeValue.java new file mode 100644 index 00000000..1bf3c8b8 --- /dev/null +++ b/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/DecisionTreeValue.java | |||
@@ -0,0 +1,41 @@ | |||
1 | package tools.refinery.language.semantics.model.internal; | ||
2 | |||
3 | import tools.refinery.store.model.representation.TruthValue; | ||
4 | |||
5 | public enum DecisionTreeValue { | ||
6 | UNSET(null), | ||
7 | TRUE(TruthValue.TRUE), | ||
8 | FALSE(TruthValue.FALSE), | ||
9 | UNKNOWN(TruthValue.UNKNOWN), | ||
10 | ERROR(TruthValue.ERROR); | ||
11 | |||
12 | final TruthValue truthValue; | ||
13 | |||
14 | DecisionTreeValue(TruthValue truthValue) { | ||
15 | this.truthValue = truthValue; | ||
16 | } | ||
17 | |||
18 | public TruthValue getTruthValue() { | ||
19 | return truthValue; | ||
20 | } | ||
21 | |||
22 | public DecisionTreeValue merge(TruthValue other) { | ||
23 | return truthValue == null ? fromTruthValue(other) : fromTruthValue(truthValue.merge(other)); | ||
24 | } | ||
25 | |||
26 | public DecisionTreeValue overwrite(DecisionTreeValue other) { | ||
27 | return other == UNSET ? this : other; | ||
28 | } | ||
29 | |||
30 | public static DecisionTreeValue fromTruthValue(TruthValue truthValue) { | ||
31 | if (truthValue == null) { | ||
32 | return DecisionTreeValue.UNSET; | ||
33 | } | ||
34 | return switch (truthValue) { | ||
35 | case TRUE -> TRUE; | ||
36 | case FALSE -> FALSE; | ||
37 | case UNKNOWN -> UNKNOWN; | ||
38 | case ERROR -> ERROR; | ||
39 | }; | ||
40 | } | ||
41 | } | ||
diff --git a/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/IntermediateNode.java b/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/IntermediateNode.java new file mode 100644 index 00000000..acc53e73 --- /dev/null +++ b/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/IntermediateNode.java | |||
@@ -0,0 +1,130 @@ | |||
1 | package tools.refinery.language.semantics.model.internal; | ||
2 | |||
3 | import org.eclipse.collections.api.LazyIntIterable; | ||
4 | import org.eclipse.collections.api.factory.primitive.IntObjectMaps; | ||
5 | import org.eclipse.collections.api.map.primitive.MutableIntObjectMap; | ||
6 | import org.eclipse.collections.api.tuple.primitive.IntObjectPair; | ||
7 | import tools.refinery.store.model.Tuple; | ||
8 | import tools.refinery.store.model.representation.TruthValue; | ||
9 | |||
10 | final class IntermediateNode extends DecisionTreeNode { | ||
11 | private final MutableIntObjectMap<DecisionTreeNode> children; | ||
12 | |||
13 | private final DecisionTreeNode otherwise; | ||
14 | |||
15 | IntermediateNode(MutableIntObjectMap<DecisionTreeNode> children, DecisionTreeNode otherwise) { | ||
16 | this.children = children; | ||
17 | this.otherwise = otherwise; | ||
18 | } | ||
19 | |||
20 | private DecisionTreeNode getChild(int index) { | ||
21 | var child = children.get(index); | ||
22 | return child == null ? otherwise : child; | ||
23 | } | ||
24 | |||
25 | @Override | ||
26 | public DecisionTreeValue getValue(int level, Tuple tuple) { | ||
27 | return getChild(tuple.get(level)).getValue(level - 1, tuple); | ||
28 | } | ||
29 | |||
30 | @Override | ||
31 | public DecisionTreeNode deepCopy() { | ||
32 | var newChildren = IntObjectMaps.mutable.from(children.keyValuesView(), IntObjectPair::getOne, | ||
33 | pair -> pair.getTwo().deepCopy()); | ||
34 | var newOtherwise = otherwise.deepCopy(); | ||
35 | return new IntermediateNode(newChildren, newOtherwise); | ||
36 | } | ||
37 | |||
38 | @Override | ||
39 | protected void mergeAllValues(int nextLevel, Tuple tuple, TruthValue value) { | ||
40 | otherwise.mergeValue(nextLevel, tuple, value); | ||
41 | for (var child : children) { | ||
42 | child.mergeValue(nextLevel, tuple, value); | ||
43 | } | ||
44 | reduceChildren(); | ||
45 | } | ||
46 | |||
47 | @Override | ||
48 | protected void mergeSingleValue(int key, int nextLevel, Tuple tuple, TruthValue value) { | ||
49 | var otherwiseReduced = getOtherwiseReducedValue(); | ||
50 | var child = children.get(key); | ||
51 | if (child == null) { | ||
52 | var newChild = otherwise.withMergedValue(nextLevel, tuple, value); | ||
53 | if (otherwiseReduced == null || newChild.getReducedValue() != otherwiseReduced) { | ||
54 | children.put(key, newChild); | ||
55 | } | ||
56 | return; | ||
57 | } | ||
58 | child.mergeValue(nextLevel, tuple, value); | ||
59 | if (otherwiseReduced != null && child.getReducedValue() == otherwiseReduced) { | ||
60 | children.remove(key); | ||
61 | } | ||
62 | } | ||
63 | |||
64 | @Override | ||
65 | public void overwriteValues(DecisionTreeNode values) { | ||
66 | if (values instanceof IntermediateNode intermediateValues) { | ||
67 | otherwise.overwriteValues(intermediateValues.otherwise); | ||
68 | for (var pair : children.keyValuesView()) { | ||
69 | pair.getTwo().overwriteValues(intermediateValues.getChild(pair.getOne())); | ||
70 | } | ||
71 | for (var pair : intermediateValues.children.keyValuesView()) { | ||
72 | children.getIfAbsentPut(pair.getOne(), () -> otherwise.withOverwrittenValues(pair.getTwo())); | ||
73 | } | ||
74 | reduceChildren(); | ||
75 | } else { | ||
76 | throw new IllegalArgumentException("Level mismatch"); | ||
77 | } | ||
78 | } | ||
79 | |||
80 | private void reduceChildren() { | ||
81 | var otherwiseReduced = getOtherwiseReducedValue(); | ||
82 | if (otherwiseReduced == null) { | ||
83 | return; | ||
84 | } | ||
85 | var iterator = children.iterator(); | ||
86 | while (iterator.hasNext()) { | ||
87 | var child = iterator.next(); | ||
88 | if (child.getReducedValue() == otherwiseReduced) { | ||
89 | iterator.remove(); | ||
90 | } | ||
91 | } | ||
92 | } | ||
93 | |||
94 | @Override | ||
95 | protected DecisionTreeValue getOtherwiseReducedValue() { | ||
96 | return otherwise.getReducedValue(); | ||
97 | } | ||
98 | |||
99 | @Override | ||
100 | protected LazyIntIterable getChildKeys() { | ||
101 | return children.keysView(); | ||
102 | } | ||
103 | |||
104 | protected boolean moveNextSparse(int level, DecisionTreeCursor cursor, int startIndex, int[] sortedChildren) { | ||
105 | for (int i = startIndex; i < sortedChildren.length; i++) { | ||
106 | var key = sortedChildren[i]; | ||
107 | var child = getChild(key); | ||
108 | var found = child.moveNext(level - 1, cursor); | ||
109 | if (found) { | ||
110 | cursor.iterationState[level] = i; | ||
111 | cursor.rawTuple[level] = key; | ||
112 | return true; | ||
113 | } | ||
114 | } | ||
115 | return false; | ||
116 | } | ||
117 | |||
118 | protected boolean moveNextDense(int level, DecisionTreeCursor cursor, int startIndex) { | ||
119 | for (int i = startIndex; i < cursor.nodeCount; i++) { | ||
120 | var child = getChild(i); | ||
121 | var found = child.moveNext(level - 1, cursor); | ||
122 | if (found) { | ||
123 | cursor.iterationState[level] = i; | ||
124 | cursor.rawTuple[level] = i; | ||
125 | return true; | ||
126 | } | ||
127 | } | ||
128 | return false; | ||
129 | } | ||
130 | } | ||
diff --git a/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/TerminalNode.java b/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/TerminalNode.java new file mode 100644 index 00000000..20dd6b20 --- /dev/null +++ b/subprojects/language-semantics/src/main/java/tools/refinery/language/semantics/model/internal/TerminalNode.java | |||
@@ -0,0 +1,129 @@ | |||
1 | package tools.refinery.language.semantics.model.internal; | ||
2 | |||
3 | import org.eclipse.collections.api.LazyIntIterable; | ||
4 | import org.eclipse.collections.api.factory.primitive.IntObjectMaps; | ||
5 | import org.eclipse.collections.api.map.primitive.MutableIntObjectMap; | ||
6 | import org.eclipse.collections.api.tuple.primitive.IntObjectPair; | ||
7 | import tools.refinery.store.model.Tuple; | ||
8 | import tools.refinery.store.model.representation.TruthValue; | ||
9 | |||
10 | class TerminalNode extends DecisionTreeNode { | ||
11 | private MutableIntObjectMap<DecisionTreeValue> children; | ||
12 | |||
13 | private DecisionTreeValue otherwise; | ||
14 | |||
15 | TerminalNode(MutableIntObjectMap<DecisionTreeValue> children, DecisionTreeValue otherwise) { | ||
16 | this.children = children; | ||
17 | this.otherwise = otherwise; | ||
18 | } | ||
19 | |||
20 | private DecisionTreeValue getChild(int index) { | ||
21 | var child = children.get(index); | ||
22 | return child == null ? otherwise : child; | ||
23 | } | ||
24 | |||
25 | @Override | ||
26 | public DecisionTreeValue getValue(int level, Tuple tuple) { | ||
27 | assertLevel(level); | ||
28 | return getChild(tuple.get(level)); | ||
29 | } | ||
30 | |||
31 | @Override | ||
32 | public DecisionTreeNode deepCopy() { | ||
33 | return new TerminalNode(IntObjectMaps.mutable.ofAll(children), otherwise); | ||
34 | } | ||
35 | |||
36 | @Override | ||
37 | public void mergeValue(int level, Tuple tuple, TruthValue value) { | ||
38 | assertLevel(level); | ||
39 | super.mergeValue(level, tuple, value); | ||
40 | } | ||
41 | |||
42 | @Override | ||
43 | protected void mergeAllValues(int nextLevel, Tuple tuple, TruthValue value) { | ||
44 | otherwise = otherwise.merge(value); | ||
45 | children = IntObjectMaps.mutable.from(children.keyValuesView(), IntObjectPair::getOne, | ||
46 | pair -> pair.getTwo().merge(value)); | ||
47 | reduceChildren(); | ||
48 | } | ||
49 | |||
50 | @Override | ||
51 | protected void mergeSingleValue(int key, int nextLevel, Tuple tuple, TruthValue value) { | ||
52 | var newChild = getChild(key).merge(value); | ||
53 | if (newChild == otherwise) { | ||
54 | children.remove(key); | ||
55 | } else { | ||
56 | children.put(key, newChild); | ||
57 | } | ||
58 | } | ||
59 | |||
60 | @Override | ||
61 | public void overwriteValues(DecisionTreeNode values) { | ||
62 | if (values instanceof TerminalNode terminalValues) { | ||
63 | otherwise = otherwise.overwrite(terminalValues.otherwise); | ||
64 | children = IntObjectMaps.mutable.from(children.keyValuesView(), IntObjectPair::getOne, | ||
65 | pair -> pair.getTwo().overwrite(terminalValues.getChild(pair.getOne()))); | ||
66 | for (var pair : terminalValues.children.keyValuesView()) { | ||
67 | children.getIfAbsentPut(pair.getOne(), otherwise.overwrite(pair.getTwo())); | ||
68 | } | ||
69 | reduceChildren(); | ||
70 | } else { | ||
71 | throw new IllegalArgumentException("Level mismatch"); | ||
72 | } | ||
73 | } | ||
74 | |||
75 | private void reduceChildren() { | ||
76 | var iterator = children.iterator(); | ||
77 | while (iterator.hasNext()) { | ||
78 | var child = iterator.next(); | ||
79 | if (child == otherwise) { | ||
80 | iterator.remove(); | ||
81 | } | ||
82 | } | ||
83 | } | ||
84 | |||
85 | @Override | ||
86 | public boolean moveNext(int level, DecisionTreeCursor cursor) { | ||
87 | assertLevel(level); | ||
88 | return super.moveNext(level, cursor); | ||
89 | } | ||
90 | |||
91 | @Override | ||
92 | protected DecisionTreeValue getOtherwiseReducedValue() { | ||
93 | return otherwise; | ||
94 | } | ||
95 | |||
96 | @Override | ||
97 | protected LazyIntIterable getChildKeys() { | ||
98 | return children.keysView(); | ||
99 | } | ||
100 | |||
101 | @Override | ||
102 | protected boolean moveNextSparse(int level, DecisionTreeCursor cursor, int startIndex, int[] sortedChildren) { | ||
103 | if (startIndex >= sortedChildren.length) { | ||
104 | return false; | ||
105 | } | ||
106 | var key = sortedChildren[startIndex]; | ||
107 | cursor.iterationState[level] = startIndex; | ||
108 | cursor.rawTuple[level] = key; | ||
109 | cursor.value = getChild(key); | ||
110 | return true; | ||
111 | } | ||
112 | |||
113 | @Override | ||
114 | protected boolean moveNextDense(int level, DecisionTreeCursor cursor, int startIndex) { | ||
115 | if (startIndex >= cursor.nodeCount) { | ||
116 | return false; | ||
117 | } | ||
118 | cursor.iterationState[level] = startIndex; | ||
119 | cursor.rawTuple[level] = startIndex; | ||
120 | cursor.value = getChild(startIndex); | ||
121 | return true; | ||
122 | } | ||
123 | |||
124 | private static void assertLevel(int level) { | ||
125 | if (level != 0) { | ||
126 | throw new IllegalArgumentException("Invalid decision tree level: " + level); | ||
127 | } | ||
128 | } | ||
129 | } | ||
diff --git a/subprojects/language-semantics/src/test/java/tools/refinery/language/semantics/model/tests/DecisionTreeTests.java b/subprojects/language-semantics/src/test/java/tools/refinery/language/semantics/model/tests/DecisionTreeTests.java new file mode 100644 index 00000000..8fe866af --- /dev/null +++ b/subprojects/language-semantics/src/test/java/tools/refinery/language/semantics/model/tests/DecisionTreeTests.java | |||
@@ -0,0 +1,187 @@ | |||
1 | package tools.refinery.language.semantics.model.tests; | ||
2 | |||
3 | import org.junit.jupiter.api.Test; | ||
4 | import tools.refinery.language.semantics.model.internal.DecisionTree; | ||
5 | import tools.refinery.store.model.Tuple; | ||
6 | import tools.refinery.store.model.representation.TruthValue; | ||
7 | |||
8 | import java.util.LinkedHashMap; | ||
9 | import java.util.Map; | ||
10 | |||
11 | import static org.hamcrest.MatcherAssert.assertThat; | ||
12 | import static org.hamcrest.Matchers.*; | ||
13 | |||
14 | class DecisionTreeTests { | ||
15 | @Test | ||
16 | void initialValueTest() { | ||
17 | var sut = new DecisionTree(3, TruthValue.UNKNOWN); | ||
18 | assertThat(sut.get(Tuple.of(3, 4, 5)), is(TruthValue.UNKNOWN)); | ||
19 | } | ||
20 | |||
21 | @Test | ||
22 | void mergeValueTest() { | ||
23 | var sut = new DecisionTree(3, TruthValue.FALSE); | ||
24 | sut.mergeValue(Tuple.of(3, 4, 5), TruthValue.TRUE); | ||
25 | assertThat(sut.get(Tuple.of(3, 4, 5)), is(TruthValue.ERROR)); | ||
26 | assertThat(sut.get(Tuple.of(3, 4, 6)), is(TruthValue.FALSE)); | ||
27 | } | ||
28 | |||
29 | @Test | ||
30 | void mergeUnknownValueTest() { | ||
31 | var sut = new DecisionTree(3, TruthValue.FALSE); | ||
32 | sut.mergeValue(Tuple.of(3, 4, 5), TruthValue.UNKNOWN); | ||
33 | assertThat(sut.get(Tuple.of(3, 4, 5)), is(TruthValue.FALSE)); | ||
34 | } | ||
35 | |||
36 | @Test | ||
37 | void mergeWildcardTest() { | ||
38 | var sut = new DecisionTree(3, TruthValue.UNKNOWN); | ||
39 | sut.mergeValue(Tuple.of(3, -1, 5), TruthValue.TRUE); | ||
40 | sut.mergeValue(Tuple.of(-1, 4, 5), TruthValue.FALSE); | ||
41 | assertThat(sut.get(Tuple.of(2, 4, 5)), is(TruthValue.FALSE)); | ||
42 | assertThat(sut.get(Tuple.of(3, 4, 5)), is(TruthValue.ERROR)); | ||
43 | assertThat(sut.get(Tuple.of(3, 6, 5)), is(TruthValue.TRUE)); | ||
44 | assertThat(sut.get(Tuple.of(3, 4, 6)), is(TruthValue.UNKNOWN)); | ||
45 | } | ||
46 | |||
47 | @Test | ||
48 | void mergeWildcardTest2() { | ||
49 | var sut = new DecisionTree(3, TruthValue.UNKNOWN); | ||
50 | sut.mergeValue(Tuple.of(-1, 4, -1), TruthValue.FALSE); | ||
51 | sut.mergeValue(Tuple.of(3, -1, 5), TruthValue.TRUE); | ||
52 | assertThat(sut.get(Tuple.of(2, 4, 5)), is(TruthValue.FALSE)); | ||
53 | assertThat(sut.get(Tuple.of(3, 4, 5)), is(TruthValue.ERROR)); | ||
54 | assertThat(sut.get(Tuple.of(3, 6, 5)), is(TruthValue.TRUE)); | ||
55 | assertThat(sut.get(Tuple.of(3, 4, 6)), is(TruthValue.FALSE)); | ||
56 | assertThat(sut.get(Tuple.of(3, 5, 6)), is(TruthValue.UNKNOWN)); | ||
57 | } | ||
58 | |||
59 | @Test | ||
60 | void mergeWildcardTest3() { | ||
61 | var sut = new DecisionTree(3, TruthValue.UNKNOWN); | ||
62 | sut.mergeValue(Tuple.of(-1, 4, -1), TruthValue.FALSE); | ||
63 | sut.mergeValue(Tuple.of(3, -1, 5), TruthValue.TRUE); | ||
64 | sut.mergeValue(Tuple.of(-1, -1, -1), TruthValue.ERROR); | ||
65 | assertThat(sut.get(Tuple.of(2, 4, 5)), is(TruthValue.ERROR)); | ||
66 | assertThat(sut.get(Tuple.of(3, 4, 5)), is(TruthValue.ERROR)); | ||
67 | assertThat(sut.get(Tuple.of(3, 6, 5)), is(TruthValue.ERROR)); | ||
68 | assertThat(sut.get(Tuple.of(3, 4, 6)), is(TruthValue.ERROR)); | ||
69 | assertThat(sut.get(Tuple.of(3, 5, 6)), is(TruthValue.ERROR)); | ||
70 | } | ||
71 | |||
72 | @Test | ||
73 | void mergeOverUnsetTest() { | ||
74 | var sut = new DecisionTree(3, null); | ||
75 | sut.mergeValue(Tuple.of(-1, 4, 5), TruthValue.UNKNOWN); | ||
76 | sut.mergeValue(Tuple.of(3, -1, 5), TruthValue.FALSE); | ||
77 | assertThat(sut.get(Tuple.of(2, 4, 5)), is(TruthValue.UNKNOWN)); | ||
78 | assertThat(sut.get(Tuple.of(3, 4, 5)), is(TruthValue.FALSE)); | ||
79 | assertThat(sut.get(Tuple.of(3, 6, 5)), is(TruthValue.FALSE)); | ||
80 | assertThat(sut.get(Tuple.of(3, 4, 6)), is(nullValue())); | ||
81 | } | ||
82 | |||
83 | @Test | ||
84 | void emptyIterationTest() { | ||
85 | var sut = new DecisionTree(3, TruthValue.UNKNOWN); | ||
86 | var map = iterateAll(sut, TruthValue.UNKNOWN, 2); | ||
87 | assertThat(map.keySet(), hasSize(0)); | ||
88 | } | ||
89 | |||
90 | @Test | ||
91 | void completeIterationTest() { | ||
92 | var sut = new DecisionTree(3, TruthValue.UNKNOWN); | ||
93 | var map = iterateAll(sut, TruthValue.FALSE, 2); | ||
94 | assertThat(map.keySet(), hasSize(8)); | ||
95 | assertThat(map, hasEntry(Tuple.of(0, 0, 0), TruthValue.UNKNOWN)); | ||
96 | assertThat(map, hasEntry(Tuple.of(0, 0, 1), TruthValue.UNKNOWN)); | ||
97 | assertThat(map, hasEntry(Tuple.of(0, 1, 0), TruthValue.UNKNOWN)); | ||
98 | assertThat(map, hasEntry(Tuple.of(0, 1, 1), TruthValue.UNKNOWN)); | ||
99 | assertThat(map, hasEntry(Tuple.of(1, 0, 0), TruthValue.UNKNOWN)); | ||
100 | assertThat(map, hasEntry(Tuple.of(1, 0, 1), TruthValue.UNKNOWN)); | ||
101 | assertThat(map, hasEntry(Tuple.of(1, 1, 0), TruthValue.UNKNOWN)); | ||
102 | assertThat(map, hasEntry(Tuple.of(1, 1, 1), TruthValue.UNKNOWN)); | ||
103 | } | ||
104 | |||
105 | @Test | ||
106 | void mergedIterationTest() { | ||
107 | var sut = new DecisionTree(2, TruthValue.UNKNOWN); | ||
108 | sut.mergeValue(Tuple.of(1, -1), TruthValue.TRUE); | ||
109 | sut.mergeValue(Tuple.of(-1, 2), TruthValue.FALSE); | ||
110 | var map = iterateAll(sut, TruthValue.UNKNOWN, 3); | ||
111 | assertThat(map.keySet(), hasSize(5)); | ||
112 | assertThat(map, hasEntry(Tuple.of(0, 2), TruthValue.FALSE)); | ||
113 | assertThat(map, hasEntry(Tuple.of(1, 0), TruthValue.TRUE)); | ||
114 | assertThat(map, hasEntry(Tuple.of(1, 1), TruthValue.TRUE)); | ||
115 | assertThat(map, hasEntry(Tuple.of(1, 2), TruthValue.ERROR)); | ||
116 | assertThat(map, hasEntry(Tuple.of(2, 2), TruthValue.FALSE)); | ||
117 | } | ||
118 | |||
119 | @Test | ||
120 | void sparseIterationTest() { | ||
121 | var sut = new DecisionTree(2, null); | ||
122 | sut.mergeValue(Tuple.of(0, 0), TruthValue.TRUE); | ||
123 | sut.mergeValue(Tuple.of(1, 1), TruthValue.FALSE); | ||
124 | var map = iterateAll(sut, null, 10); | ||
125 | assertThat(map.keySet(), hasSize(2)); | ||
126 | assertThat(map, hasEntry(Tuple.of(0, 0), TruthValue.TRUE)); | ||
127 | assertThat(map, hasEntry(Tuple.of(1, 1), TruthValue.FALSE)); | ||
128 | } | ||
129 | |||
130 | @Test | ||
131 | void overwriteNothingTest() { | ||
132 | var sut = new DecisionTree(2, TruthValue.UNKNOWN); | ||
133 | var values = new DecisionTree(2, null); | ||
134 | sut.overwriteValues(values); | ||
135 | assertThat(sut.get(Tuple.of(0, 0)), is(TruthValue.UNKNOWN)); | ||
136 | } | ||
137 | |||
138 | @Test | ||
139 | void overwriteEverythingTest() { | ||
140 | var sut = new DecisionTree(2, TruthValue.FALSE); | ||
141 | sut.mergeValue(Tuple.of(0, 0), TruthValue.ERROR); | ||
142 | var values = new DecisionTree(2, TruthValue.TRUE); | ||
143 | sut.overwriteValues(values); | ||
144 | assertThat(sut.get(Tuple.of(0, 0)), is(TruthValue.TRUE)); | ||
145 | assertThat(sut.get(Tuple.of(0, 1)), is(TruthValue.TRUE)); | ||
146 | } | ||
147 | |||
148 | @Test | ||
149 | void overwriteWildcardTest() { | ||
150 | var sut = new DecisionTree(3, TruthValue.UNKNOWN); | ||
151 | sut.mergeValue(Tuple.of(1, 1, 1), TruthValue.FALSE); | ||
152 | sut.mergeValue(Tuple.of(-1, 4, 5), TruthValue.FALSE); | ||
153 | sut.mergeValue(Tuple.of(3, -1, 5), TruthValue.TRUE); | ||
154 | var values = new DecisionTree(3, null); | ||
155 | values.mergeValue(Tuple.of(2, 2, 2), TruthValue.TRUE); | ||
156 | values.mergeValue(Tuple.of(-1, 4, 5), TruthValue.UNKNOWN); | ||
157 | values.mergeValue(Tuple.of(3, -1, 5), TruthValue.FALSE); | ||
158 | sut.overwriteValues(values); | ||
159 | assertThat(sut.get(Tuple.of(1, 1, 1)), is(TruthValue.FALSE)); | ||
160 | assertThat(sut.get(Tuple.of(2, 2, 2)), is(TruthValue.TRUE)); | ||
161 | assertThat(sut.get(Tuple.of(2, 4, 5)), is(TruthValue.UNKNOWN)); | ||
162 | assertThat(sut.get(Tuple.of(3, 4, 5)), is(TruthValue.FALSE)); | ||
163 | assertThat(sut.get(Tuple.of(3, 6, 5)), is(TruthValue.FALSE)); | ||
164 | assertThat(sut.get(Tuple.of(3, 4, 6)), is(TruthValue.UNKNOWN)); | ||
165 | } | ||
166 | |||
167 | @Test | ||
168 | void removeIntermediateChildTest() { | ||
169 | var sut = new DecisionTree(3, TruthValue.TRUE); | ||
170 | var values = new DecisionTree(3, null); | ||
171 | values.mergeValue(Tuple.of(1, 1, 1), TruthValue.UNKNOWN); | ||
172 | sut.overwriteValues(values); | ||
173 | sut.mergeValue(Tuple.of(1, 1, 1), TruthValue.TRUE); | ||
174 | assertThat(sut.get(Tuple.of(1, 1, 1)), is(TruthValue.TRUE)); | ||
175 | } | ||
176 | |||
177 | private Map<Tuple, TruthValue> iterateAll(DecisionTree sut, TruthValue defaultValue, int nodeCount) { | ||
178 | var cursor = sut.getCursor(defaultValue, nodeCount); | ||
179 | var map = new LinkedHashMap<Tuple, TruthValue>(); | ||
180 | while (cursor.move()) { | ||
181 | map.put(cursor.getKey(), cursor.getValue()); | ||
182 | } | ||
183 | assertThat(cursor.isDirty(), is(false)); | ||
184 | assertThat(cursor.isTerminated(), is(true)); | ||
185 | return map; | ||
186 | } | ||
187 | } | ||