diff options
Diffstat (limited to 'subprojects/store-partial/src/main')
42 files changed, 1674 insertions, 0 deletions
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/AnyPartialSymbolInterpretation.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/AnyPartialSymbolInterpretation.java new file mode 100644 index 00000000..b6b1f2be --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/AnyPartialSymbolInterpretation.java | |||
@@ -0,0 +1,13 @@ | |||
1 | package tools.refinery.store.partial; | ||
2 | |||
3 | import tools.refinery.store.partial.representation.AnyPartialSymbol; | ||
4 | |||
5 | public sealed interface AnyPartialSymbolInterpretation permits PartialSymbolInterpretation { | ||
6 | PartialInterpretationAdapter getAdapter(); | ||
7 | |||
8 | AnyPartialSymbol getPartialSymbol(); | ||
9 | |||
10 | int countUnfinished(); | ||
11 | |||
12 | int countErrors(); | ||
13 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/MergeResult.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/MergeResult.java new file mode 100644 index 00000000..82414d87 --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/MergeResult.java | |||
@@ -0,0 +1,15 @@ | |||
1 | package tools.refinery.store.partial; | ||
2 | |||
3 | public enum MergeResult { | ||
4 | UNCHANGED, | ||
5 | REFINED, | ||
6 | REJECTED; | ||
7 | |||
8 | public MergeResult andAlso(MergeResult other) { | ||
9 | return switch (this) { | ||
10 | case UNCHANGED -> other; | ||
11 | case REFINED -> other == REJECTED ? REJECTED : REFINED; | ||
12 | case REJECTED -> REJECTED; | ||
13 | }; | ||
14 | } | ||
15 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/PartialInterpretation.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/PartialInterpretation.java new file mode 100644 index 00000000..d76f8728 --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/PartialInterpretation.java | |||
@@ -0,0 +1,24 @@ | |||
1 | package tools.refinery.store.partial; | ||
2 | |||
3 | import tools.refinery.store.partial.internal.PartialInterpretationBuilderImpl; | ||
4 | import tools.refinery.store.adapter.ModelAdapterBuilderFactory; | ||
5 | import tools.refinery.store.model.ModelStoreBuilder; | ||
6 | import tools.refinery.store.partial.representation.PartialRelation; | ||
7 | |||
8 | public final class PartialInterpretation extends ModelAdapterBuilderFactory<PartialInterpretationAdapter, | ||
9 | PartialInterpretationStoreAdapter, PartialInterpretationBuilder> { | ||
10 | public static final PartialInterpretation ADAPTER = new PartialInterpretation(); | ||
11 | |||
12 | public static final PartialRelation EXISTS = new PartialRelation("exists", 1); | ||
13 | |||
14 | public static final PartialRelation EQUALS = new PartialRelation("equals", 1); | ||
15 | |||
16 | private PartialInterpretation() { | ||
17 | super(PartialInterpretationAdapter.class, PartialInterpretationStoreAdapter.class, PartialInterpretationBuilder.class); | ||
18 | } | ||
19 | |||
20 | @Override | ||
21 | public PartialInterpretationBuilder createBuilder(ModelStoreBuilder storeBuilder) { | ||
22 | return new PartialInterpretationBuilderImpl(storeBuilder); | ||
23 | } | ||
24 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/PartialInterpretationAdapter.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/PartialInterpretationAdapter.java new file mode 100644 index 00000000..b811ae7a --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/PartialInterpretationAdapter.java | |||
@@ -0,0 +1,20 @@ | |||
1 | package tools.refinery.store.partial; | ||
2 | |||
3 | import tools.refinery.store.adapter.ModelAdapter; | ||
4 | import tools.refinery.store.partial.representation.AnyPartialSymbol; | ||
5 | import tools.refinery.store.partial.representation.PartialSymbol; | ||
6 | import tools.refinery.store.query.Dnf; | ||
7 | import tools.refinery.store.query.ResultSet; | ||
8 | |||
9 | public interface PartialInterpretationAdapter extends ModelAdapter { | ||
10 | @Override | ||
11 | PartialInterpretationStoreAdapter getStoreAdapter(); | ||
12 | |||
13 | default AnyPartialSymbolInterpretation getPartialInterpretation(AnyPartialSymbol partialSymbol) { | ||
14 | return getPartialInterpretation((PartialSymbol<?, ?>) partialSymbol); | ||
15 | } | ||
16 | |||
17 | <A, C> PartialSymbolInterpretation<A, C> getPartialInterpretation(PartialSymbol<A, C> partialSymbol); | ||
18 | |||
19 | ResultSet getLiftedResultSet(Dnf query); | ||
20 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/PartialInterpretationBuilder.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/PartialInterpretationBuilder.java new file mode 100644 index 00000000..db042466 --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/PartialInterpretationBuilder.java | |||
@@ -0,0 +1,28 @@ | |||
1 | package tools.refinery.store.partial; | ||
2 | |||
3 | import tools.refinery.store.adapter.ModelAdapterBuilder; | ||
4 | import tools.refinery.store.model.ModelStore; | ||
5 | import tools.refinery.store.query.Dnf; | ||
6 | import tools.refinery.store.partial.literal.Modality; | ||
7 | |||
8 | import java.util.Collection; | ||
9 | import java.util.List; | ||
10 | |||
11 | @SuppressWarnings("UnusedReturnValue") | ||
12 | public interface PartialInterpretationBuilder extends ModelAdapterBuilder { | ||
13 | default PartialInterpretationBuilder liftedQueries(Dnf... liftedQueries) { | ||
14 | return liftedQueries(List.of(liftedQueries)); | ||
15 | } | ||
16 | |||
17 | default PartialInterpretationBuilder liftedQueries(Collection<Dnf> liftedQueries) { | ||
18 | liftedQueries.forEach(this::liftedQuery); | ||
19 | return this; | ||
20 | } | ||
21 | |||
22 | PartialInterpretationBuilder liftedQuery(Dnf liftedQuery); | ||
23 | |||
24 | Dnf lift(Modality modality, Dnf query); | ||
25 | |||
26 | @Override | ||
27 | PartialInterpretationStoreAdapter createStoreAdapter(ModelStore store); | ||
28 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/PartialInterpretationStoreAdapter.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/PartialInterpretationStoreAdapter.java new file mode 100644 index 00000000..a1813671 --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/PartialInterpretationStoreAdapter.java | |||
@@ -0,0 +1,17 @@ | |||
1 | package tools.refinery.store.partial; | ||
2 | |||
3 | import tools.refinery.store.adapter.ModelStoreAdapter; | ||
4 | import tools.refinery.store.model.Model; | ||
5 | import tools.refinery.store.partial.representation.AnyPartialSymbol; | ||
6 | import tools.refinery.store.query.Dnf; | ||
7 | |||
8 | import java.util.Collection; | ||
9 | |||
10 | public interface PartialInterpretationStoreAdapter extends ModelStoreAdapter { | ||
11 | Collection<AnyPartialSymbol> getPartialSymbols(); | ||
12 | |||
13 | Collection<Dnf> getLiftedQueries(); | ||
14 | |||
15 | @Override | ||
16 | PartialInterpretationAdapter createModelAdapter(Model model); | ||
17 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/PartialSymbolInterpretation.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/PartialSymbolInterpretation.java new file mode 100644 index 00000000..fa9e9216 --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/PartialSymbolInterpretation.java | |||
@@ -0,0 +1,22 @@ | |||
1 | package tools.refinery.store.partial; | ||
2 | |||
3 | import tools.refinery.store.partial.representation.PartialSymbol; | ||
4 | import tools.refinery.store.map.Cursor; | ||
5 | import tools.refinery.store.tuple.Tuple; | ||
6 | |||
7 | public non-sealed interface PartialSymbolInterpretation<A, C> extends AnyPartialSymbolInterpretation { | ||
8 | @Override | ||
9 | PartialSymbol<A, C> getPartialSymbol(); | ||
10 | |||
11 | A get(Tuple key); | ||
12 | |||
13 | Cursor<Tuple, A> getAll(); | ||
14 | |||
15 | Cursor<Tuple, A> getAllErrors(); | ||
16 | |||
17 | MergeResult merge(Tuple key, A value); | ||
18 | |||
19 | C getConcrete(Tuple key); | ||
20 | |||
21 | Cursor<Tuple, C> getAllConcrete(); | ||
22 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/internal/PartialInterpretationAdapterImpl.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/internal/PartialInterpretationAdapterImpl.java new file mode 100644 index 00000000..c482d8a2 --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/internal/PartialInterpretationAdapterImpl.java | |||
@@ -0,0 +1,38 @@ | |||
1 | package tools.refinery.store.partial.internal; | ||
2 | |||
3 | import tools.refinery.store.model.Model; | ||
4 | import tools.refinery.store.partial.PartialInterpretationAdapter; | ||
5 | import tools.refinery.store.partial.PartialSymbolInterpretation; | ||
6 | import tools.refinery.store.partial.representation.PartialSymbol; | ||
7 | import tools.refinery.store.query.Dnf; | ||
8 | import tools.refinery.store.query.ResultSet; | ||
9 | |||
10 | public class PartialInterpretationAdapterImpl implements PartialInterpretationAdapter { | ||
11 | private final Model model; | ||
12 | private final PartialInterpretationStoreAdapterImpl storeAdapter; | ||
13 | |||
14 | PartialInterpretationAdapterImpl(Model model, PartialInterpretationStoreAdapterImpl storeAdapter) { | ||
15 | this.model = model; | ||
16 | this.storeAdapter = storeAdapter; | ||
17 | } | ||
18 | |||
19 | @Override | ||
20 | public Model getModel() { | ||
21 | return model; | ||
22 | } | ||
23 | |||
24 | @Override | ||
25 | public PartialInterpretationStoreAdapterImpl getStoreAdapter() { | ||
26 | return storeAdapter; | ||
27 | } | ||
28 | |||
29 | @Override | ||
30 | public <A, C> PartialSymbolInterpretation<A, C> getPartialInterpretation(PartialSymbol<A, C> partialSymbol) { | ||
31 | return null; | ||
32 | } | ||
33 | |||
34 | @Override | ||
35 | public ResultSet getLiftedResultSet(Dnf query) { | ||
36 | return null; | ||
37 | } | ||
38 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/internal/PartialInterpretationBuilderImpl.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/internal/PartialInterpretationBuilderImpl.java new file mode 100644 index 00000000..5853aeaf --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/internal/PartialInterpretationBuilderImpl.java | |||
@@ -0,0 +1,29 @@ | |||
1 | package tools.refinery.store.partial.internal; | ||
2 | |||
3 | import tools.refinery.store.adapter.AbstractModelAdapterBuilder; | ||
4 | import tools.refinery.store.model.ModelStore; | ||
5 | import tools.refinery.store.model.ModelStoreBuilder; | ||
6 | import tools.refinery.store.partial.PartialInterpretationBuilder; | ||
7 | import tools.refinery.store.partial.literal.Modality; | ||
8 | import tools.refinery.store.query.Dnf; | ||
9 | |||
10 | public class PartialInterpretationBuilderImpl extends AbstractModelAdapterBuilder implements PartialInterpretationBuilder { | ||
11 | public PartialInterpretationBuilderImpl(ModelStoreBuilder storeBuilder) { | ||
12 | super(storeBuilder); | ||
13 | } | ||
14 | |||
15 | @Override | ||
16 | public PartialInterpretationBuilder liftedQuery(Dnf liftedQuery) { | ||
17 | return null; | ||
18 | } | ||
19 | |||
20 | @Override | ||
21 | public Dnf lift(Modality modality, Dnf query) { | ||
22 | return null; | ||
23 | } | ||
24 | |||
25 | @Override | ||
26 | public PartialInterpretationStoreAdapterImpl createStoreAdapter(ModelStore store) { | ||
27 | return null; | ||
28 | } | ||
29 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/internal/PartialInterpretationStoreAdapterImpl.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/internal/PartialInterpretationStoreAdapterImpl.java new file mode 100644 index 00000000..0486af6e --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/internal/PartialInterpretationStoreAdapterImpl.java | |||
@@ -0,0 +1,37 @@ | |||
1 | package tools.refinery.store.partial.internal; | ||
2 | |||
3 | import tools.refinery.store.partial.PartialInterpretationStoreAdapter; | ||
4 | import tools.refinery.store.model.Model; | ||
5 | import tools.refinery.store.model.ModelStore; | ||
6 | import tools.refinery.store.partial.representation.AnyPartialSymbol; | ||
7 | import tools.refinery.store.query.Dnf; | ||
8 | |||
9 | import java.util.Collection; | ||
10 | |||
11 | public class PartialInterpretationStoreAdapterImpl implements PartialInterpretationStoreAdapter { | ||
12 | private final ModelStore store; | ||
13 | |||
14 | PartialInterpretationStoreAdapterImpl(ModelStore store) { | ||
15 | this.store = store; | ||
16 | } | ||
17 | |||
18 | @Override | ||
19 | public ModelStore getStore() { | ||
20 | return store; | ||
21 | } | ||
22 | |||
23 | @Override | ||
24 | public Collection<AnyPartialSymbol> getPartialSymbols() { | ||
25 | return null; | ||
26 | } | ||
27 | |||
28 | @Override | ||
29 | public Collection<Dnf> getLiftedQueries() { | ||
30 | return null; | ||
31 | } | ||
32 | |||
33 | @Override | ||
34 | public PartialInterpretationAdapterImpl createModelAdapter(Model model) { | ||
35 | return new PartialInterpretationAdapterImpl(model, this); | ||
36 | } | ||
37 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/lifting/DnfLifter.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/lifting/DnfLifter.java new file mode 100644 index 00000000..1c35b925 --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/lifting/DnfLifter.java | |||
@@ -0,0 +1,107 @@ | |||
1 | package tools.refinery.store.partial.lifting; | ||
2 | |||
3 | import org.jetbrains.annotations.Nullable; | ||
4 | import tools.refinery.store.partial.literal.ModalDnfCallLiteral; | ||
5 | import tools.refinery.store.partial.PartialInterpretation; | ||
6 | import tools.refinery.store.partial.literal.ModalRelationLiteral; | ||
7 | import tools.refinery.store.partial.literal.PartialRelationLiteral; | ||
8 | import tools.refinery.store.query.Dnf; | ||
9 | import tools.refinery.store.query.DnfBuilder; | ||
10 | import tools.refinery.store.query.DnfClause; | ||
11 | import tools.refinery.store.query.Variable; | ||
12 | import tools.refinery.store.query.literal.CallPolarity; | ||
13 | import tools.refinery.store.query.literal.DnfCallLiteral; | ||
14 | import tools.refinery.store.query.literal.Literal; | ||
15 | import tools.refinery.store.partial.literal.Modality; | ||
16 | import tools.refinery.store.util.CycleDetectingMapper; | ||
17 | |||
18 | import java.util.ArrayList; | ||
19 | import java.util.HashSet; | ||
20 | import java.util.List; | ||
21 | |||
22 | public class DnfLifter { | ||
23 | private final CycleDetectingMapper<ModalDnf, Dnf> mapper = new CycleDetectingMapper<>(ModalDnf::toString, | ||
24 | this::doLift); | ||
25 | |||
26 | public Dnf lift(Modality modality, Dnf query) { | ||
27 | return mapper.map(new ModalDnf(modality, query)); | ||
28 | } | ||
29 | |||
30 | private Dnf doLift(ModalDnf modalDnf) { | ||
31 | var modality = modalDnf.modality(); | ||
32 | var dnf = modalDnf.dnf(); | ||
33 | var builder = Dnf.builder(); | ||
34 | builder.parameters(dnf.getParameters()); | ||
35 | boolean changed = false; | ||
36 | for (var clause : dnf.getClauses()) { | ||
37 | if (liftClause(modality, clause, builder)) { | ||
38 | changed = true; | ||
39 | } | ||
40 | } | ||
41 | if (changed) { | ||
42 | return builder.build(); | ||
43 | } | ||
44 | return dnf; | ||
45 | } | ||
46 | |||
47 | private boolean liftClause(Modality modality, DnfClause clause, DnfBuilder builder) { | ||
48 | boolean changed = false; | ||
49 | var quantifiedVariables = new HashSet<>(clause.quantifiedVariables()); | ||
50 | var literals = clause.literals(); | ||
51 | var liftedLiterals = new ArrayList<Literal>(literals.size()); | ||
52 | for (var literal : literals) { | ||
53 | Literal liftedLiteral = liftLiteral(modality, literal); | ||
54 | if (liftedLiteral == null) { | ||
55 | liftedLiteral = literal; | ||
56 | } else { | ||
57 | changed = true; | ||
58 | } | ||
59 | liftedLiterals.add(liftedLiteral); | ||
60 | var variable = isExistsLiteralForVariable(modality, liftedLiteral); | ||
61 | if (variable != null) { | ||
62 | // If we already quantify over the existence of the variable with the expected modality, | ||
63 | // we don't need to insert quantification manually. | ||
64 | quantifiedVariables.remove(variable); | ||
65 | } | ||
66 | } | ||
67 | for (var quantifiedVariable : quantifiedVariables) { | ||
68 | // Quantify over variables that are not already quantified with the expected modality. | ||
69 | liftedLiterals.add(PartialInterpretation.EXISTS.call(CallPolarity.POSITIVE, modality, | ||
70 | List.of(quantifiedVariable))); | ||
71 | } | ||
72 | builder.clause(liftedLiterals); | ||
73 | return changed || !quantifiedVariables.isEmpty(); | ||
74 | } | ||
75 | |||
76 | @Nullable | ||
77 | private Variable isExistsLiteralForVariable(Modality modality, Literal literal) { | ||
78 | if (literal instanceof ModalRelationLiteral modalRelationLiteral && | ||
79 | modalRelationLiteral.getPolarity() == CallPolarity.POSITIVE && | ||
80 | modalRelationLiteral.getModality() == modality && | ||
81 | modalRelationLiteral.getTarget().equals(PartialInterpretation.EXISTS)) { | ||
82 | return modalRelationLiteral.getArguments().get(0); | ||
83 | } | ||
84 | return null; | ||
85 | } | ||
86 | |||
87 | @Nullable | ||
88 | private Literal liftLiteral(Modality modality, Literal literal) { | ||
89 | if (literal instanceof PartialRelationLiteral partialRelationLiteral) { | ||
90 | return new ModalRelationLiteral(modality, partialRelationLiteral); | ||
91 | } else if (literal instanceof DnfCallLiteral dnfCallLiteral) { | ||
92 | var polarity = dnfCallLiteral.getPolarity(); | ||
93 | var target = dnfCallLiteral.getTarget(); | ||
94 | var liftedTarget = lift(modality.commute(polarity), target); | ||
95 | if (target.equals(liftedTarget)) { | ||
96 | return null; | ||
97 | } | ||
98 | return new DnfCallLiteral(polarity, liftedTarget, dnfCallLiteral.getArguments()); | ||
99 | } else if (literal instanceof ModalDnfCallLiteral modalDnfCallLiteral) { | ||
100 | var liftedTarget = lift(modalDnfCallLiteral.getModality(), modalDnfCallLiteral.getTarget()); | ||
101 | return new DnfCallLiteral(modalDnfCallLiteral.getPolarity(), liftedTarget, | ||
102 | modalDnfCallLiteral.getArguments()); | ||
103 | } else { | ||
104 | return null; | ||
105 | } | ||
106 | } | ||
107 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/lifting/ModalDnf.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/lifting/ModalDnf.java new file mode 100644 index 00000000..6fe54ad9 --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/lifting/ModalDnf.java | |||
@@ -0,0 +1,11 @@ | |||
1 | package tools.refinery.store.partial.lifting; | ||
2 | |||
3 | import tools.refinery.store.query.Dnf; | ||
4 | import tools.refinery.store.partial.literal.Modality; | ||
5 | |||
6 | public record ModalDnf(Modality modality, Dnf dnf) { | ||
7 | @Override | ||
8 | public String toString() { | ||
9 | return "%s %s".formatted(modality, dnf.name()); | ||
10 | } | ||
11 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/literal/ModalDnfCallLiteral.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/literal/ModalDnfCallLiteral.java new file mode 100644 index 00000000..a49e0625 --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/literal/ModalDnfCallLiteral.java | |||
@@ -0,0 +1,37 @@ | |||
1 | package tools.refinery.store.partial.literal; | ||
2 | |||
3 | import tools.refinery.store.query.Dnf; | ||
4 | import tools.refinery.store.query.Variable; | ||
5 | import tools.refinery.store.query.literal.CallPolarity; | ||
6 | import tools.refinery.store.query.literal.DnfCallLiteral; | ||
7 | import tools.refinery.store.query.literal.LiteralReduction; | ||
8 | import tools.refinery.store.query.literal.PolarLiteral; | ||
9 | |||
10 | import java.util.List; | ||
11 | import java.util.Map; | ||
12 | |||
13 | public class ModalDnfCallLiteral extends ModalLiteral<Dnf> implements PolarLiteral<ModalDnfCallLiteral> { | ||
14 | public ModalDnfCallLiteral(CallPolarity polarity, Modality modality, Dnf target, List<Variable> arguments) { | ||
15 | super(polarity, modality, target, arguments); | ||
16 | } | ||
17 | |||
18 | public ModalDnfCallLiteral(Modality modality, DnfCallLiteral baseLiteral) { | ||
19 | super(modality.commute(baseLiteral.getPolarity()), baseLiteral); | ||
20 | } | ||
21 | |||
22 | @Override | ||
23 | public ModalDnfCallLiteral substitute(Map<Variable, Variable> substitution) { | ||
24 | return new ModalDnfCallLiteral(getPolarity(), getModality(), getTarget(), substituteArguments(substitution)); | ||
25 | } | ||
26 | |||
27 | @Override | ||
28 | public ModalDnfCallLiteral negate() { | ||
29 | return new ModalDnfCallLiteral(getPolarity().negate(), getModality(), getTarget(), getArguments()); | ||
30 | } | ||
31 | |||
32 | @Override | ||
33 | public LiteralReduction getReduction() { | ||
34 | var dnfReduction = getTarget().getReduction(); | ||
35 | return getPolarity().isPositive() ? dnfReduction : dnfReduction.negate(); | ||
36 | } | ||
37 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/literal/ModalLiteral.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/literal/ModalLiteral.java new file mode 100644 index 00000000..a1b6c83e --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/literal/ModalLiteral.java | |||
@@ -0,0 +1,45 @@ | |||
1 | package tools.refinery.store.partial.literal; | ||
2 | |||
3 | import tools.refinery.store.query.RelationLike; | ||
4 | import tools.refinery.store.query.Variable; | ||
5 | import tools.refinery.store.query.literal.CallLiteral; | ||
6 | import tools.refinery.store.query.literal.CallPolarity; | ||
7 | |||
8 | import java.util.List; | ||
9 | import java.util.Objects; | ||
10 | |||
11 | public abstract class ModalLiteral<T extends RelationLike> extends CallLiteral<T> { | ||
12 | private final Modality modality; | ||
13 | |||
14 | protected ModalLiteral(CallPolarity polarity, Modality modality, T target, List<Variable> arguments) { | ||
15 | super(polarity, target, arguments); | ||
16 | this.modality = modality; | ||
17 | } | ||
18 | |||
19 | protected ModalLiteral(Modality modality, CallLiteral<? extends T> baseLiteral) { | ||
20 | this(baseLiteral.getPolarity(), commute(modality, baseLiteral.getPolarity()), baseLiteral.getTarget(), | ||
21 | baseLiteral.getArguments()); | ||
22 | } | ||
23 | |||
24 | public Modality getModality() { | ||
25 | return modality; | ||
26 | } | ||
27 | |||
28 | @Override | ||
29 | public boolean equals(Object o) { | ||
30 | if (this == o) return true; | ||
31 | if (o == null || getClass() != o.getClass()) return false; | ||
32 | if (!super.equals(o)) return false; | ||
33 | ModalLiteral<?> that = (ModalLiteral<?>) o; | ||
34 | return modality == that.modality; | ||
35 | } | ||
36 | |||
37 | @Override | ||
38 | public int hashCode() { | ||
39 | return Objects.hash(super.hashCode(), modality); | ||
40 | } | ||
41 | |||
42 | private static Modality commute(Modality modality, CallPolarity polarity) { | ||
43 | return polarity.isPositive() ? modality : modality.negate(); | ||
44 | } | ||
45 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/literal/ModalRelationLiteral.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/literal/ModalRelationLiteral.java new file mode 100644 index 00000000..dbaa524f --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/literal/ModalRelationLiteral.java | |||
@@ -0,0 +1,31 @@ | |||
1 | package tools.refinery.store.partial.literal; | ||
2 | |||
3 | import tools.refinery.store.partial.representation.PartialRelation; | ||
4 | import tools.refinery.store.query.Variable; | ||
5 | import tools.refinery.store.query.literal.CallPolarity; | ||
6 | import tools.refinery.store.query.literal.PolarLiteral; | ||
7 | |||
8 | import java.util.List; | ||
9 | import java.util.Map; | ||
10 | |||
11 | public final class ModalRelationLiteral extends ModalLiteral<PartialRelation> | ||
12 | implements PolarLiteral<ModalRelationLiteral> { | ||
13 | public ModalRelationLiteral(CallPolarity polarity, Modality modality, PartialRelation target, | ||
14 | List<Variable> arguments) { | ||
15 | super(polarity, modality, target, arguments); | ||
16 | } | ||
17 | |||
18 | public ModalRelationLiteral(Modality modality, PartialRelationLiteral baseLiteral) { | ||
19 | super(modality, baseLiteral); | ||
20 | } | ||
21 | |||
22 | @Override | ||
23 | public ModalRelationLiteral substitute(Map<Variable, Variable> substitution) { | ||
24 | return new ModalRelationLiteral(getPolarity(), getModality(), getTarget(), substituteArguments(substitution)); | ||
25 | } | ||
26 | |||
27 | @Override | ||
28 | public ModalRelationLiteral negate() { | ||
29 | return new ModalRelationLiteral(getPolarity().negate(), getModality(), getTarget(), getArguments()); | ||
30 | } | ||
31 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/literal/Modality.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/literal/Modality.java new file mode 100644 index 00000000..d647ef0a --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/literal/Modality.java | |||
@@ -0,0 +1,31 @@ | |||
1 | package tools.refinery.store.partial.literal; | ||
2 | |||
3 | import tools.refinery.store.query.literal.CallPolarity; | ||
4 | |||
5 | import java.util.Locale; | ||
6 | |||
7 | public enum Modality { | ||
8 | MUST, | ||
9 | MAY, | ||
10 | CURRENT; | ||
11 | |||
12 | public Modality negate() { | ||
13 | return switch(this) { | ||
14 | case MUST -> MAY; | ||
15 | case MAY -> MUST; | ||
16 | case CURRENT -> CURRENT; | ||
17 | }; | ||
18 | } | ||
19 | |||
20 | public Modality commute(CallPolarity polarity) { | ||
21 | if (polarity.isPositive()) { | ||
22 | return this; | ||
23 | } | ||
24 | return this.negate(); | ||
25 | } | ||
26 | |||
27 | @Override | ||
28 | public String toString() { | ||
29 | return name().toLowerCase(Locale.ROOT); | ||
30 | } | ||
31 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/literal/PartialLiterals.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/literal/PartialLiterals.java new file mode 100644 index 00000000..51d388d3 --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/literal/PartialLiterals.java | |||
@@ -0,0 +1,33 @@ | |||
1 | package tools.refinery.store.partial.literal; | ||
2 | |||
3 | import tools.refinery.store.query.literal.DnfCallLiteral; | ||
4 | |||
5 | public final class PartialLiterals { | ||
6 | private PartialLiterals() { | ||
7 | throw new IllegalStateException("This is a static utility class and should not be instantiated directly"); | ||
8 | } | ||
9 | |||
10 | public ModalRelationLiteral may(PartialRelationLiteral literal) { | ||
11 | return new ModalRelationLiteral(Modality.MAY, literal); | ||
12 | } | ||
13 | |||
14 | public ModalRelationLiteral must(PartialRelationLiteral literal) { | ||
15 | return new ModalRelationLiteral(Modality.MUST, literal); | ||
16 | } | ||
17 | |||
18 | public ModalRelationLiteral current(PartialRelationLiteral literal) { | ||
19 | return new ModalRelationLiteral(Modality.CURRENT, literal); | ||
20 | } | ||
21 | |||
22 | public ModalDnfCallLiteral may(DnfCallLiteral literal) { | ||
23 | return new ModalDnfCallLiteral(Modality.MAY, literal); | ||
24 | } | ||
25 | |||
26 | public ModalDnfCallLiteral must(DnfCallLiteral literal) { | ||
27 | return new ModalDnfCallLiteral(Modality.MUST, literal); | ||
28 | } | ||
29 | |||
30 | public ModalDnfCallLiteral current(DnfCallLiteral literal) { | ||
31 | return new ModalDnfCallLiteral(Modality.CURRENT, literal); | ||
32 | } | ||
33 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/literal/PartialRelationLiteral.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/literal/PartialRelationLiteral.java new file mode 100644 index 00000000..dc1a1da3 --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/literal/PartialRelationLiteral.java | |||
@@ -0,0 +1,27 @@ | |||
1 | package tools.refinery.store.partial.literal; | ||
2 | |||
3 | import tools.refinery.store.partial.representation.PartialRelation; | ||
4 | import tools.refinery.store.query.Variable; | ||
5 | import tools.refinery.store.query.literal.CallLiteral; | ||
6 | import tools.refinery.store.query.literal.CallPolarity; | ||
7 | import tools.refinery.store.query.literal.PolarLiteral; | ||
8 | |||
9 | import java.util.List; | ||
10 | import java.util.Map; | ||
11 | |||
12 | public final class PartialRelationLiteral extends CallLiteral<PartialRelation> | ||
13 | implements PolarLiteral<PartialRelationLiteral> { | ||
14 | public PartialRelationLiteral(CallPolarity polarity, PartialRelation target, List<Variable> substitution) { | ||
15 | super(polarity, target, substitution); | ||
16 | } | ||
17 | |||
18 | @Override | ||
19 | public PartialRelationLiteral substitute(Map<Variable, Variable> substitution) { | ||
20 | return new PartialRelationLiteral(getPolarity(), getTarget(), substituteArguments(substitution)); | ||
21 | } | ||
22 | |||
23 | @Override | ||
24 | public PartialRelationLiteral negate() { | ||
25 | return new PartialRelationLiteral(getPolarity().negate(), getTarget(), getArguments()); | ||
26 | } | ||
27 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/representation/AnyPartialFunction.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/representation/AnyPartialFunction.java new file mode 100644 index 00000000..1113245e --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/representation/AnyPartialFunction.java | |||
@@ -0,0 +1,4 @@ | |||
1 | package tools.refinery.store.partial.representation; | ||
2 | |||
3 | public sealed interface AnyPartialFunction extends AnyPartialSymbol permits PartialFunction { | ||
4 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/representation/AnyPartialSymbol.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/representation/AnyPartialSymbol.java new file mode 100644 index 00000000..25096e74 --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/representation/AnyPartialSymbol.java | |||
@@ -0,0 +1,11 @@ | |||
1 | package tools.refinery.store.partial.representation; | ||
2 | |||
3 | import tools.refinery.store.representation.AnyAbstractDomain; | ||
4 | |||
5 | public sealed interface AnyPartialSymbol permits AnyPartialFunction, PartialSymbol { | ||
6 | String name(); | ||
7 | |||
8 | int arity(); | ||
9 | |||
10 | AnyAbstractDomain abstractDomain(); | ||
11 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/representation/PartialFunction.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/representation/PartialFunction.java new file mode 100644 index 00000000..3c186f6f --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/representation/PartialFunction.java | |||
@@ -0,0 +1,32 @@ | |||
1 | package tools.refinery.store.partial.representation; | ||
2 | |||
3 | import tools.refinery.store.representation.AbstractDomain; | ||
4 | |||
5 | public record PartialFunction<A, C>(String name, int arity, AbstractDomain<A, C> abstractDomain) | ||
6 | implements AnyPartialFunction, PartialSymbol<A, C> { | ||
7 | @Override | ||
8 | public A defaultValue() { | ||
9 | return null; | ||
10 | } | ||
11 | |||
12 | @Override | ||
13 | public C defaultConcreteValue() { | ||
14 | return null; | ||
15 | } | ||
16 | |||
17 | @Override | ||
18 | public boolean equals(Object o) { | ||
19 | return this == o; | ||
20 | } | ||
21 | |||
22 | @Override | ||
23 | public int hashCode() { | ||
24 | // Compare by identity to make hash table lookups more efficient. | ||
25 | return System.identityHashCode(this); | ||
26 | } | ||
27 | |||
28 | @Override | ||
29 | public String toString() { | ||
30 | return "%s/%d".formatted(name, arity); | ||
31 | } | ||
32 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/representation/PartialRelation.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/representation/PartialRelation.java new file mode 100644 index 00000000..51c2f28d --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/representation/PartialRelation.java | |||
@@ -0,0 +1,66 @@ | |||
1 | package tools.refinery.store.partial.representation; | ||
2 | |||
3 | import tools.refinery.store.partial.literal.Modality; | ||
4 | import tools.refinery.store.partial.literal.PartialRelationLiteral; | ||
5 | import tools.refinery.store.partial.literal.ModalRelationLiteral; | ||
6 | import tools.refinery.store.query.RelationLike; | ||
7 | import tools.refinery.store.query.Variable; | ||
8 | import tools.refinery.store.query.literal.CallPolarity; | ||
9 | import tools.refinery.store.representation.AbstractDomain; | ||
10 | import tools.refinery.store.representation.TruthValue; | ||
11 | import tools.refinery.store.representation.TruthValueDomain; | ||
12 | |||
13 | import java.util.List; | ||
14 | |||
15 | public record PartialRelation(String name, int arity) implements PartialSymbol<TruthValue, Boolean>, RelationLike { | ||
16 | @Override | ||
17 | public AbstractDomain<TruthValue, Boolean> abstractDomain() { | ||
18 | return TruthValueDomain.INSTANCE; | ||
19 | } | ||
20 | |||
21 | @Override | ||
22 | public TruthValue defaultValue() { | ||
23 | return TruthValue.FALSE; | ||
24 | } | ||
25 | |||
26 | @Override | ||
27 | public Boolean defaultConcreteValue() { | ||
28 | return false; | ||
29 | } | ||
30 | |||
31 | public ModalRelationLiteral call(CallPolarity polarity, Modality modality, List<Variable> arguments) { | ||
32 | return new ModalRelationLiteral(polarity, modality, this, arguments); | ||
33 | } | ||
34 | |||
35 | public PartialRelationLiteral call(CallPolarity polarity, List<Variable> arguments) { | ||
36 | return new PartialRelationLiteral(polarity, this, arguments); | ||
37 | } | ||
38 | |||
39 | public PartialRelationLiteral call(CallPolarity polarity, Variable... arguments) { | ||
40 | return call(polarity, List.of(arguments)); | ||
41 | } | ||
42 | |||
43 | public PartialRelationLiteral call(Variable... arguments) { | ||
44 | return call(CallPolarity.POSITIVE, arguments); | ||
45 | } | ||
46 | |||
47 | public PartialRelationLiteral callTransitive(Variable left, Variable right) { | ||
48 | return call(CallPolarity.TRANSITIVE, List.of(left, right)); | ||
49 | } | ||
50 | |||
51 | @Override | ||
52 | public boolean equals(Object o) { | ||
53 | return this == o; | ||
54 | } | ||
55 | |||
56 | @Override | ||
57 | public int hashCode() { | ||
58 | // Compare by identity to make hash table lookups more efficient. | ||
59 | return System.identityHashCode(this); | ||
60 | } | ||
61 | |||
62 | @Override | ||
63 | public String toString() { | ||
64 | return "%s/%d".formatted(name, arity); | ||
65 | } | ||
66 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/representation/PartialSymbol.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/representation/PartialSymbol.java new file mode 100644 index 00000000..38533fa9 --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/representation/PartialSymbol.java | |||
@@ -0,0 +1,12 @@ | |||
1 | package tools.refinery.store.partial.representation; | ||
2 | |||
3 | import tools.refinery.store.representation.AbstractDomain; | ||
4 | |||
5 | public sealed interface PartialSymbol<A, C> extends AnyPartialSymbol permits PartialFunction, PartialRelation { | ||
6 | @Override | ||
7 | AbstractDomain<A, C> abstractDomain(); | ||
8 | |||
9 | A defaultValue(); | ||
10 | |||
11 | C defaultConcreteValue(); | ||
12 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/rule/RelationRefinementAction.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/rule/RelationRefinementAction.java new file mode 100644 index 00000000..6c89653d --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/rule/RelationRefinementAction.java | |||
@@ -0,0 +1,36 @@ | |||
1 | package tools.refinery.store.partial.rule; | ||
2 | |||
3 | import tools.refinery.store.partial.PartialInterpretation; | ||
4 | import tools.refinery.store.partial.representation.PartialRelation; | ||
5 | import tools.refinery.store.model.Model; | ||
6 | import tools.refinery.store.query.Variable; | ||
7 | import tools.refinery.store.representation.TruthValue; | ||
8 | import tools.refinery.store.tuple.Tuple; | ||
9 | |||
10 | import java.util.List; | ||
11 | |||
12 | public record RelationRefinementAction(PartialRelation target, List<Variable> arguments, TruthValue value) | ||
13 | implements RuleAction { | ||
14 | public RelationRefinementAction { | ||
15 | if (arguments.size() != target.arity()) { | ||
16 | throw new IllegalArgumentException("%s needs %d parameters, but got %s".formatted(target.name(), | ||
17 | target.arity(), arguments.size())); | ||
18 | } | ||
19 | if (value == TruthValue.UNKNOWN) { | ||
20 | throw new IllegalArgumentException("Refining with UNKNOWN has no effect"); | ||
21 | } | ||
22 | } | ||
23 | |||
24 | @Override | ||
25 | public RuleActionExecutor createExecutor(int[] argumentIndices, Model model) { | ||
26 | var targetInterpretation = model.getAdapter(PartialInterpretation.ADAPTER).getPartialInterpretation(target); | ||
27 | return activationTuple -> { | ||
28 | int arity = argumentIndices.length; | ||
29 | var arguments = new int[arity]; | ||
30 | for (int i = 0; i < arity; i++) { | ||
31 | arguments[i] = activationTuple.get(argumentIndices[i]); | ||
32 | } | ||
33 | return targetInterpretation.merge(Tuple.of(arguments), value); | ||
34 | }; | ||
35 | } | ||
36 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/rule/Rule.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/rule/Rule.java new file mode 100644 index 00000000..c114b8cf --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/rule/Rule.java | |||
@@ -0,0 +1,38 @@ | |||
1 | package tools.refinery.store.partial.rule; | ||
2 | |||
3 | import tools.refinery.store.model.Model; | ||
4 | import tools.refinery.store.query.Dnf; | ||
5 | |||
6 | import java.util.ArrayList; | ||
7 | import java.util.HashSet; | ||
8 | import java.util.List; | ||
9 | |||
10 | public record Rule(Dnf precondition, List<RuleAction> actions) { | ||
11 | public Rule { | ||
12 | var parameterSet = new HashSet<>(precondition.getParameters()); | ||
13 | for (var action : actions) { | ||
14 | for (var argument : action.arguments()) { | ||
15 | if (!parameterSet.contains(argument)) { | ||
16 | throw new IllegalArgumentException( | ||
17 | "Argument %s of action %s does not appear in the parameter list %s of %s" | ||
18 | .formatted(argument, action, precondition.getParameters(), precondition.name())); | ||
19 | } | ||
20 | } | ||
21 | } | ||
22 | } | ||
23 | |||
24 | public RuleExecutor createExecutor(Model model) { | ||
25 | var parameters = precondition.getParameters(); | ||
26 | var actionExecutors = new ArrayList<RuleActionExecutor>(actions.size()); | ||
27 | for (var action : actions) { | ||
28 | var arguments = action.arguments(); | ||
29 | int arity = arguments.size(); | ||
30 | var argumentIndices = new int[arity]; | ||
31 | for (int i = 0; i < arity; i++) { | ||
32 | argumentIndices[i] = parameters.indexOf(arguments.get(i)); | ||
33 | } | ||
34 | actionExecutors.add(action.createExecutor(argumentIndices, model)); | ||
35 | } | ||
36 | return new RuleExecutor(this, model, actionExecutors); | ||
37 | } | ||
38 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/rule/RuleAction.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/rule/RuleAction.java new file mode 100644 index 00000000..7a8ede40 --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/rule/RuleAction.java | |||
@@ -0,0 +1,12 @@ | |||
1 | package tools.refinery.store.partial.rule; | ||
2 | |||
3 | import tools.refinery.store.model.Model; | ||
4 | import tools.refinery.store.query.Variable; | ||
5 | |||
6 | import java.util.List; | ||
7 | |||
8 | public interface RuleAction { | ||
9 | List<Variable> arguments(); | ||
10 | |||
11 | RuleActionExecutor createExecutor(int[] argumentIndices, Model model); | ||
12 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/rule/RuleActionExecutor.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/rule/RuleActionExecutor.java new file mode 100644 index 00000000..1c2db5f1 --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/rule/RuleActionExecutor.java | |||
@@ -0,0 +1,9 @@ | |||
1 | package tools.refinery.store.partial.rule; | ||
2 | |||
3 | import tools.refinery.store.partial.MergeResult; | ||
4 | import tools.refinery.store.tuple.TupleLike; | ||
5 | |||
6 | @FunctionalInterface | ||
7 | public interface RuleActionExecutor { | ||
8 | MergeResult execute(TupleLike activationTuple); | ||
9 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/rule/RuleExecutor.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/rule/RuleExecutor.java new file mode 100644 index 00000000..41d79306 --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/rule/RuleExecutor.java | |||
@@ -0,0 +1,34 @@ | |||
1 | package tools.refinery.store.partial.rule; | ||
2 | |||
3 | import tools.refinery.store.partial.MergeResult; | ||
4 | import tools.refinery.store.model.Model; | ||
5 | import tools.refinery.store.tuple.TupleLike; | ||
6 | |||
7 | import java.util.List; | ||
8 | |||
9 | public final class RuleExecutor { | ||
10 | private final Rule rule; | ||
11 | private final Model model; | ||
12 | private final List<RuleActionExecutor> actionExecutors; | ||
13 | |||
14 | RuleExecutor(Rule rule, Model model, List<RuleActionExecutor> actionExecutors) { | ||
15 | this.rule = rule; | ||
16 | this.model = model; | ||
17 | this.actionExecutors = actionExecutors; | ||
18 | } | ||
19 | |||
20 | public Rule getRule() { | ||
21 | return rule; | ||
22 | } | ||
23 | |||
24 | public Model getModel() { | ||
25 | return model; | ||
26 | } | ||
27 | public MergeResult execute(TupleLike activationTuple) { | ||
28 | MergeResult mergeResult = MergeResult.UNCHANGED; | ||
29 | for (var actionExecutor : actionExecutors) { | ||
30 | mergeResult = mergeResult.andAlso(actionExecutor.execute(activationTuple)); | ||
31 | } | ||
32 | return mergeResult; | ||
33 | } | ||
34 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/Advice.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/Advice.java new file mode 100644 index 00000000..65040a8e --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/Advice.java | |||
@@ -0,0 +1,155 @@ | |||
1 | package tools.refinery.store.partial.translator; | ||
2 | |||
3 | import tools.refinery.store.partial.representation.AnyPartialSymbol; | ||
4 | import tools.refinery.store.partial.representation.PartialRelation; | ||
5 | import tools.refinery.store.query.Variable; | ||
6 | import tools.refinery.store.query.literal.Literal; | ||
7 | |||
8 | import java.util.*; | ||
9 | |||
10 | public final class Advice { | ||
11 | private final AnyPartialSymbol source; | ||
12 | private final PartialRelation target; | ||
13 | private final AdviceSlot slot; | ||
14 | private final boolean mandatory; | ||
15 | private final List<Variable> parameters; | ||
16 | private final List<Literal> literals; | ||
17 | private boolean processed; | ||
18 | |||
19 | public Advice(AnyPartialSymbol source, PartialRelation target, AdviceSlot slot, boolean mandatory, List<Variable> parameters, List<Literal> literals) { | ||
20 | if (mandatory && !slot.isMonotonic()) { | ||
21 | throw new IllegalArgumentException("Only monotonic advice can be mandatory"); | ||
22 | } | ||
23 | this.source = source; | ||
24 | this.target = target; | ||
25 | this.slot = slot; | ||
26 | this.mandatory = mandatory; | ||
27 | checkArity(parameters); | ||
28 | this.parameters = parameters; | ||
29 | this.literals = literals; | ||
30 | } | ||
31 | |||
32 | public AnyPartialSymbol source() { | ||
33 | return source; | ||
34 | } | ||
35 | |||
36 | public PartialRelation target() { | ||
37 | return target; | ||
38 | } | ||
39 | |||
40 | public AdviceSlot slot() { | ||
41 | return slot; | ||
42 | } | ||
43 | |||
44 | public boolean mandatory() { | ||
45 | return mandatory; | ||
46 | } | ||
47 | |||
48 | public List<Variable> parameters() { | ||
49 | return parameters; | ||
50 | } | ||
51 | |||
52 | public List<Literal> literals() { | ||
53 | return literals; | ||
54 | } | ||
55 | |||
56 | public boolean processed() { | ||
57 | return processed; | ||
58 | } | ||
59 | |||
60 | public List<Literal> substitute(List<Variable> substituteParameters) { | ||
61 | checkArity(substituteParameters); | ||
62 | markProcessed(); | ||
63 | int arity = parameters.size(); | ||
64 | var substitution = new HashMap<Variable, Variable>(arity); | ||
65 | for (int i = 0; i < arity; i++) { | ||
66 | substitution.put(parameters.get(i), substituteParameters.get(i)); | ||
67 | } | ||
68 | return literals.stream().map(literal -> literal.substitute(substitution)).toList(); | ||
69 | } | ||
70 | |||
71 | private void markProcessed() { | ||
72 | processed = true; | ||
73 | } | ||
74 | |||
75 | public void checkProcessed() { | ||
76 | if (mandatory && !processed) { | ||
77 | throw new IllegalStateException("Mandatory advice %s was not processed".formatted(this)); | ||
78 | } | ||
79 | } | ||
80 | |||
81 | private void checkArity(List<Variable> toCheck) { | ||
82 | if (toCheck.size() != target.arity()) { | ||
83 | throw new IllegalArgumentException("%s needs %d parameters, but got %s".formatted(target.name(), | ||
84 | target.arity(), parameters.size())); | ||
85 | } | ||
86 | } | ||
87 | |||
88 | public static Builder builderFor(AnyPartialSymbol source, PartialRelation target, AdviceSlot slot) { | ||
89 | return new Builder(source, target, slot); | ||
90 | } | ||
91 | |||
92 | |||
93 | @Override | ||
94 | public String toString() { | ||
95 | return "Advice[source=%s, target=%s, slot=%s, mandatory=%s, parameters=%s, literals=%s]".formatted(source, | ||
96 | target, slot, mandatory, parameters, literals); | ||
97 | } | ||
98 | |||
99 | public static class Builder { | ||
100 | private final AnyPartialSymbol source; | ||
101 | private final PartialRelation target; | ||
102 | private final AdviceSlot slot; | ||
103 | private boolean mandatory; | ||
104 | private final List<Variable> parameters = new ArrayList<>(); | ||
105 | private final List<Literal> literals = new ArrayList<>(); | ||
106 | |||
107 | private Builder(AnyPartialSymbol source, PartialRelation target, AdviceSlot slot) { | ||
108 | this.source = source; | ||
109 | this.target = target; | ||
110 | this.slot = slot; | ||
111 | } | ||
112 | |||
113 | public Builder mandatory(boolean mandatory) { | ||
114 | this.mandatory = mandatory; | ||
115 | return this; | ||
116 | } | ||
117 | |||
118 | public Builder mandatory() { | ||
119 | return mandatory(false); | ||
120 | } | ||
121 | |||
122 | public Builder parameters(List<Variable> variables) { | ||
123 | parameters.addAll(variables); | ||
124 | return this; | ||
125 | } | ||
126 | |||
127 | public Builder parameters(Variable... variables) { | ||
128 | return parameters(List.of(variables)); | ||
129 | } | ||
130 | |||
131 | public Builder parameter(Variable variable) { | ||
132 | parameters.add(variable); | ||
133 | return this; | ||
134 | } | ||
135 | |||
136 | public Builder literals(Collection<Literal> literals) { | ||
137 | this.literals.addAll(literals); | ||
138 | return this; | ||
139 | } | ||
140 | |||
141 | public Builder literals(Literal... literals) { | ||
142 | return literals(List.of(literals)); | ||
143 | } | ||
144 | |||
145 | public Builder literal(Literal literal) { | ||
146 | literals.add(literal); | ||
147 | return this; | ||
148 | } | ||
149 | |||
150 | public Advice build() { | ||
151 | return new Advice(source, target, slot, mandatory, Collections.unmodifiableList(parameters), | ||
152 | Collections.unmodifiableList(literals)); | ||
153 | } | ||
154 | } | ||
155 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/AdviceSlot.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/AdviceSlot.java new file mode 100644 index 00000000..3702a8ac --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/AdviceSlot.java | |||
@@ -0,0 +1,25 @@ | |||
1 | package tools.refinery.store.partial.translator; | ||
2 | |||
3 | import tools.refinery.store.representation.TruthValue; | ||
4 | |||
5 | public enum AdviceSlot { | ||
6 | EXTEND_MUST(true), | ||
7 | |||
8 | RESTRICT_MAY(true), | ||
9 | |||
10 | /** | ||
11 | * Same as {@link #RESTRICT_MAY}, but only active if the value of the relation is not {@link TruthValue#TRUE} or | ||
12 | * {@link TruthValue#ERROR}. | ||
13 | */ | ||
14 | RESTRICT_NEW(false); | ||
15 | |||
16 | private final boolean monotonic; | ||
17 | |||
18 | AdviceSlot(boolean monotonic) { | ||
19 | this.monotonic = monotonic; | ||
20 | } | ||
21 | |||
22 | public boolean isMonotonic() { | ||
23 | return monotonic; | ||
24 | } | ||
25 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/Seed.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/Seed.java new file mode 100644 index 00000000..c56b06ed --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/Seed.java | |||
@@ -0,0 +1,12 @@ | |||
1 | package tools.refinery.store.partial.translator; | ||
2 | |||
3 | import tools.refinery.store.map.Cursor; | ||
4 | import tools.refinery.store.tuple.Tuple; | ||
5 | |||
6 | public interface Seed<T> { | ||
7 | int arity(); | ||
8 | |||
9 | T get(Tuple key); | ||
10 | |||
11 | Cursor<Tuple, T> getCursor(T defaultValue, int nodeCount); | ||
12 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/TranslationUnit.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/TranslationUnit.java new file mode 100644 index 00000000..26bd909b --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/TranslationUnit.java | |||
@@ -0,0 +1,48 @@ | |||
1 | package tools.refinery.store.partial.translator; | ||
2 | |||
3 | import tools.refinery.store.partial.PartialInterpretationBuilder; | ||
4 | import tools.refinery.store.model.Model; | ||
5 | import tools.refinery.store.model.ModelStoreBuilder; | ||
6 | import tools.refinery.store.partial.AnyPartialSymbolInterpretation; | ||
7 | import tools.refinery.store.partial.literal.Modality; | ||
8 | import tools.refinery.store.partial.representation.AnyPartialSymbol; | ||
9 | import tools.refinery.store.partial.representation.PartialRelation; | ||
10 | import tools.refinery.store.query.Variable; | ||
11 | import tools.refinery.store.query.literal.CallPolarity; | ||
12 | import tools.refinery.store.query.literal.Literal; | ||
13 | |||
14 | import java.util.Collection; | ||
15 | import java.util.List; | ||
16 | import java.util.Map; | ||
17 | |||
18 | public abstract class TranslationUnit { | ||
19 | private PartialInterpretationBuilder partialInterpretationBuilder; | ||
20 | |||
21 | protected PartialInterpretationBuilder getPartialInterpretationBuilder() { | ||
22 | return partialInterpretationBuilder; | ||
23 | } | ||
24 | |||
25 | public void setPartialInterpretationBuilder(PartialInterpretationBuilder partialInterpretationBuilder) { | ||
26 | this.partialInterpretationBuilder = partialInterpretationBuilder; | ||
27 | } | ||
28 | |||
29 | protected ModelStoreBuilder getModelStoreBuilder() { | ||
30 | return partialInterpretationBuilder.getStoreBuilder(); | ||
31 | } | ||
32 | |||
33 | public abstract Collection<AnyPartialSymbol> getTranslatedPartialSymbols(); | ||
34 | |||
35 | public Collection<Advice> computeAdvices() { | ||
36 | // No advices to give by default. | ||
37 | return List.of(); | ||
38 | } | ||
39 | |||
40 | public abstract void configure(Collection<Advice> advices); | ||
41 | |||
42 | public abstract List<Literal> call(CallPolarity polarity, Modality modality, PartialRelation target, | ||
43 | List<Variable> arguments); | ||
44 | |||
45 | public abstract Map<AnyPartialSymbol, AnyPartialSymbolInterpretation> createPartialInterpretations(Model model); | ||
46 | |||
47 | public abstract void initializeModel(Model model, int nodeCount); | ||
48 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/EliminatedType.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/EliminatedType.java new file mode 100644 index 00000000..9adf6bc8 --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/EliminatedType.java | |||
@@ -0,0 +1,6 @@ | |||
1 | package tools.refinery.store.partial.translator.typehierarchy; | ||
2 | |||
3 | import tools.refinery.store.partial.representation.PartialRelation; | ||
4 | |||
5 | record EliminatedType(PartialRelation replacement) implements TypeAnalysisResult { | ||
6 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/ExtendedTypeInfo.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/ExtendedTypeInfo.java new file mode 100644 index 00000000..d3f66a4c --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/ExtendedTypeInfo.java | |||
@@ -0,0 +1,101 @@ | |||
1 | package tools.refinery.store.partial.translator.typehierarchy; | ||
2 | |||
3 | import org.jetbrains.annotations.NotNull; | ||
4 | import tools.refinery.store.partial.representation.PartialRelation; | ||
5 | |||
6 | import java.util.HashSet; | ||
7 | import java.util.LinkedHashSet; | ||
8 | import java.util.Objects; | ||
9 | import java.util.Set; | ||
10 | |||
11 | final class ExtendedTypeInfo implements Comparable<ExtendedTypeInfo> { | ||
12 | private final int index; | ||
13 | private final PartialRelation type; | ||
14 | private final TypeInfo typeInfo; | ||
15 | private final Set<PartialRelation> allSubtypes = new LinkedHashSet<>(); | ||
16 | private final Set<PartialRelation> allSupertypes; | ||
17 | private final Set<PartialRelation> concreteSubtypesAndSelf = new LinkedHashSet<>(); | ||
18 | private Set<PartialRelation> directSubtypes; | ||
19 | private final Set<PartialRelation> unsortedDirectSupertypes = new HashSet<>(); | ||
20 | |||
21 | public ExtendedTypeInfo(int index, PartialRelation type, TypeInfo typeInfo) { | ||
22 | this.index = index; | ||
23 | this.type = type; | ||
24 | this.typeInfo = typeInfo; | ||
25 | this.allSupertypes = new LinkedHashSet<>(typeInfo.supertypes()); | ||
26 | } | ||
27 | |||
28 | public PartialRelation getType() { | ||
29 | return type; | ||
30 | } | ||
31 | |||
32 | public TypeInfo getTypeInfo() { | ||
33 | return typeInfo; | ||
34 | } | ||
35 | |||
36 | public boolean isAbstractType() { | ||
37 | return getTypeInfo().abstractType(); | ||
38 | } | ||
39 | |||
40 | public Set<PartialRelation> getAllSubtypes() { | ||
41 | return allSubtypes; | ||
42 | } | ||
43 | |||
44 | public Set<PartialRelation> getAllSupertypes() { | ||
45 | return allSupertypes; | ||
46 | } | ||
47 | |||
48 | public Set<PartialRelation> getAllSupertypesAndSelf() { | ||
49 | var allSubtypesAndSelf = new HashSet<PartialRelation>(allSupertypes.size() + 1); | ||
50 | addMust(allSubtypesAndSelf); | ||
51 | return allSubtypesAndSelf; | ||
52 | } | ||
53 | |||
54 | public Set<PartialRelation> getConcreteSubtypesAndSelf() { | ||
55 | return concreteSubtypesAndSelf; | ||
56 | } | ||
57 | |||
58 | public Set<PartialRelation> getDirectSubtypes() { | ||
59 | return directSubtypes; | ||
60 | } | ||
61 | |||
62 | public Set<PartialRelation> getUnsortedDirectSupertypes() { | ||
63 | return unsortedDirectSupertypes; | ||
64 | } | ||
65 | |||
66 | public void setDirectSubtypes(Set<PartialRelation> directSubtypes) { | ||
67 | this.directSubtypes = directSubtypes; | ||
68 | } | ||
69 | |||
70 | public boolean allowsAllConcreteTypes(Set<PartialRelation> concreteTypes) { | ||
71 | for (var concreteType : concreteTypes) { | ||
72 | if (!concreteSubtypesAndSelf.contains(concreteType)) { | ||
73 | return false; | ||
74 | } | ||
75 | } | ||
76 | return true; | ||
77 | } | ||
78 | |||
79 | public void addMust(Set<PartialRelation> mustTypes) { | ||
80 | mustTypes.add(type); | ||
81 | mustTypes.addAll(allSupertypes); | ||
82 | } | ||
83 | |||
84 | @Override | ||
85 | public int compareTo(@NotNull ExtendedTypeInfo extendedTypeInfo) { | ||
86 | return Integer.compare(index, extendedTypeInfo.index); | ||
87 | } | ||
88 | |||
89 | @Override | ||
90 | public boolean equals(Object o) { | ||
91 | if (this == o) return true; | ||
92 | if (o == null || getClass() != o.getClass()) return false; | ||
93 | ExtendedTypeInfo that = (ExtendedTypeInfo) o; | ||
94 | return index == that.index; | ||
95 | } | ||
96 | |||
97 | @Override | ||
98 | public int hashCode() { | ||
99 | return Objects.hash(index); | ||
100 | } | ||
101 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/InferredMayTypeRelationView.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/InferredMayTypeRelationView.java new file mode 100644 index 00000000..ff761936 --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/InferredMayTypeRelationView.java | |||
@@ -0,0 +1,19 @@ | |||
1 | package tools.refinery.store.partial.translator.typehierarchy; | ||
2 | |||
3 | import tools.refinery.store.partial.representation.PartialRelation; | ||
4 | import tools.refinery.store.query.view.TuplePreservingRelationView; | ||
5 | import tools.refinery.store.tuple.Tuple; | ||
6 | |||
7 | class InferredMayTypeRelationView extends TuplePreservingRelationView<InferredType> { | ||
8 | private final PartialRelation type; | ||
9 | |||
10 | InferredMayTypeRelationView(PartialRelation type) { | ||
11 | super(TypeHierarchyTranslationUnit.INFERRED_TYPE_SYMBOL, "%s#may".formatted(type)); | ||
12 | this.type = type; | ||
13 | } | ||
14 | |||
15 | @Override | ||
16 | public boolean filter(Tuple key, InferredType value) { | ||
17 | return value.mayConcreteTypes().contains(type); | ||
18 | } | ||
19 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/InferredMustTypeRelationView.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/InferredMustTypeRelationView.java new file mode 100644 index 00000000..4eca0a1c --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/InferredMustTypeRelationView.java | |||
@@ -0,0 +1,19 @@ | |||
1 | package tools.refinery.store.partial.translator.typehierarchy; | ||
2 | |||
3 | import tools.refinery.store.partial.representation.PartialRelation; | ||
4 | import tools.refinery.store.query.view.TuplePreservingRelationView; | ||
5 | import tools.refinery.store.tuple.Tuple; | ||
6 | |||
7 | class InferredMustTypeRelationView extends TuplePreservingRelationView<InferredType> { | ||
8 | private final PartialRelation type; | ||
9 | |||
10 | InferredMustTypeRelationView(PartialRelation type) { | ||
11 | super(TypeHierarchyTranslationUnit.INFERRED_TYPE_SYMBOL, "%s#must".formatted(type)); | ||
12 | this.type = type; | ||
13 | } | ||
14 | |||
15 | @Override | ||
16 | public boolean filter(Tuple key, InferredType value) { | ||
17 | return value.mustTypes().contains(type); | ||
18 | } | ||
19 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/InferredType.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/InferredType.java new file mode 100644 index 00000000..729b1fb5 --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/InferredType.java | |||
@@ -0,0 +1,30 @@ | |||
1 | package tools.refinery.store.partial.translator.typehierarchy; | ||
2 | |||
3 | import tools.refinery.store.partial.representation.PartialRelation; | ||
4 | |||
5 | import java.util.Collections; | ||
6 | import java.util.Set; | ||
7 | |||
8 | record InferredType(Set<PartialRelation> mustTypes, Set<PartialRelation> mayConcreteTypes, | ||
9 | PartialRelation currentType) { | ||
10 | public static final InferredType UNTYPED = new InferredType(Set.of(), Set.of(), null); | ||
11 | |||
12 | public InferredType(Set<PartialRelation> mustTypes, Set<PartialRelation> mayConcreteTypes, | ||
13 | PartialRelation currentType) { | ||
14 | this.mustTypes = Collections.unmodifiableSet(mustTypes); | ||
15 | this.mayConcreteTypes = Collections.unmodifiableSet(mayConcreteTypes); | ||
16 | this.currentType = currentType; | ||
17 | } | ||
18 | |||
19 | public boolean isConsistent() { | ||
20 | return currentType != null || mustTypes.isEmpty(); | ||
21 | } | ||
22 | |||
23 | public boolean isMust(PartialRelation partialRelation) { | ||
24 | return mustTypes.contains(partialRelation); | ||
25 | } | ||
26 | |||
27 | public boolean isMayConcrete(PartialRelation partialRelation) { | ||
28 | return mayConcreteTypes.contains(partialRelation); | ||
29 | } | ||
30 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/PreservedType.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/PreservedType.java new file mode 100644 index 00000000..0299ae03 --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/PreservedType.java | |||
@@ -0,0 +1,136 @@ | |||
1 | package tools.refinery.store.partial.translator.typehierarchy; | ||
2 | |||
3 | import tools.refinery.store.partial.representation.PartialRelation; | ||
4 | import tools.refinery.store.representation.TruthValue; | ||
5 | |||
6 | import java.util.*; | ||
7 | |||
8 | final class PreservedType implements TypeAnalysisResult { | ||
9 | private final ExtendedTypeInfo extendedTypeInfo; | ||
10 | private final List<PartialRelation> directSubtypes; | ||
11 | private final List<ExtendedTypeInfo> allExternalTypeInfoList; | ||
12 | private final InferredType inferredType; | ||
13 | |||
14 | public PreservedType(ExtendedTypeInfo extendedTypeInfo, List<ExtendedTypeInfo> allExternalTypeInfoList) { | ||
15 | this.extendedTypeInfo = extendedTypeInfo; | ||
16 | directSubtypes = List.copyOf(extendedTypeInfo.getDirectSubtypes()); | ||
17 | this.allExternalTypeInfoList = allExternalTypeInfoList; | ||
18 | inferredType = propagateMust(extendedTypeInfo.getAllSupertypesAndSelf(), | ||
19 | extendedTypeInfo.getConcreteSubtypesAndSelf()); | ||
20 | } | ||
21 | |||
22 | public PartialRelation type() { | ||
23 | return extendedTypeInfo.getType(); | ||
24 | } | ||
25 | |||
26 | public List<PartialRelation> getDirectSubtypes() { | ||
27 | return directSubtypes; | ||
28 | } | ||
29 | |||
30 | public boolean isAbstractType() { | ||
31 | return extendedTypeInfo.isAbstractType(); | ||
32 | } | ||
33 | |||
34 | public boolean isVacuous() { | ||
35 | return isAbstractType() && directSubtypes.isEmpty(); | ||
36 | } | ||
37 | |||
38 | public InferredType asInferredType() { | ||
39 | return inferredType; | ||
40 | } | ||
41 | |||
42 | public InferredType merge(InferredType inferredType, TruthValue value) { | ||
43 | return switch (value) { | ||
44 | case UNKNOWN -> inferredType; | ||
45 | case TRUE -> addMust(inferredType); | ||
46 | case FALSE -> removeMay(inferredType); | ||
47 | case ERROR -> addError(inferredType); | ||
48 | }; | ||
49 | } | ||
50 | |||
51 | private InferredType addMust(InferredType inferredType) { | ||
52 | var originalMustTypes = inferredType.mustTypes(); | ||
53 | if (originalMustTypes.contains(type())) { | ||
54 | return inferredType; | ||
55 | } | ||
56 | var mustTypes = new HashSet<>(originalMustTypes); | ||
57 | extendedTypeInfo.addMust(mustTypes); | ||
58 | var originalMayConcreteTypes = inferredType.mayConcreteTypes(); | ||
59 | var mayConcreteTypes = new LinkedHashSet<>(originalMayConcreteTypes); | ||
60 | Set<PartialRelation> mayConcreteTypesResult; | ||
61 | if (mayConcreteTypes.retainAll(extendedTypeInfo.getConcreteSubtypesAndSelf())) { | ||
62 | mayConcreteTypesResult = mayConcreteTypes; | ||
63 | } else { | ||
64 | mayConcreteTypesResult = originalMayConcreteTypes; | ||
65 | } | ||
66 | return propagateMust(mustTypes, mayConcreteTypesResult); | ||
67 | } | ||
68 | |||
69 | private InferredType removeMay(InferredType inferredType) { | ||
70 | var originalMayConcreteTypes = inferredType.mayConcreteTypes(); | ||
71 | var mayConcreteTypes = new LinkedHashSet<>(originalMayConcreteTypes); | ||
72 | if (!mayConcreteTypes.removeAll(extendedTypeInfo.getConcreteSubtypesAndSelf())) { | ||
73 | return inferredType; | ||
74 | } | ||
75 | return propagateMust(inferredType.mustTypes(), mayConcreteTypes); | ||
76 | } | ||
77 | |||
78 | private InferredType addError(InferredType inferredType) { | ||
79 | var originalMustTypes = inferredType.mustTypes(); | ||
80 | if (originalMustTypes.contains(type())) { | ||
81 | if (inferredType.mayConcreteTypes().isEmpty()) { | ||
82 | return inferredType; | ||
83 | } | ||
84 | return new InferredType(originalMustTypes, Set.of(), null); | ||
85 | } | ||
86 | var mustTypes = new HashSet<>(originalMustTypes); | ||
87 | extendedTypeInfo.addMust(mustTypes); | ||
88 | return new InferredType(mustTypes, Set.of(), null); | ||
89 | } | ||
90 | |||
91 | private InferredType propagateMust(Set<PartialRelation> originalMustTypes, | ||
92 | Set<PartialRelation> mayConcreteTypes) { | ||
93 | // It is possible that there is not type at all, do not force one by propagation. | ||
94 | var maybeUntyped = originalMustTypes.isEmpty(); | ||
95 | // Para-consistent case, do not propagate must types to avoid logical explosion. | ||
96 | var paraConsistentOrSurelyUntyped = mayConcreteTypes.isEmpty(); | ||
97 | if (maybeUntyped || paraConsistentOrSurelyUntyped) { | ||
98 | return new InferredType(originalMustTypes, mayConcreteTypes, null); | ||
99 | } | ||
100 | var currentType = computeCurrentType(mayConcreteTypes); | ||
101 | var mustTypes = new HashSet<>(originalMustTypes); | ||
102 | boolean changed = false; | ||
103 | for (var newMustExtendedTypeInfo : allExternalTypeInfoList) { | ||
104 | var newMustType = newMustExtendedTypeInfo.getType(); | ||
105 | if (mustTypes.contains(newMustType)) { | ||
106 | continue; | ||
107 | } | ||
108 | if (newMustExtendedTypeInfo.allowsAllConcreteTypes(mayConcreteTypes)) { | ||
109 | newMustExtendedTypeInfo.addMust(mustTypes); | ||
110 | changed = true; | ||
111 | } | ||
112 | } | ||
113 | if (!changed) { | ||
114 | return new InferredType(originalMustTypes, mayConcreteTypes, currentType); | ||
115 | } | ||
116 | return new InferredType(mustTypes, mayConcreteTypes, currentType); | ||
117 | } | ||
118 | |||
119 | /** | ||
120 | * Returns a concrete type that is allowed by a (consistent, i.e., nonempty) set of <b>may</b> concrete types. | ||
121 | * | ||
122 | * @param mayConcreteTypes The set of allowed concrete types. Must not be empty. | ||
123 | * @return The first concrete type that is allowed by {@code matConcreteTypes}. | ||
124 | */ | ||
125 | private PartialRelation computeCurrentType(Set<PartialRelation> mayConcreteTypes) { | ||
126 | for (var concreteExtendedTypeInfo : allExternalTypeInfoList) { | ||
127 | var concreteType = concreteExtendedTypeInfo.getType(); | ||
128 | if (!concreteExtendedTypeInfo.isAbstractType() && mayConcreteTypes.contains(concreteType)) { | ||
129 | return concreteType; | ||
130 | } | ||
131 | } | ||
132 | // We have already filtered out the para-consistent case in {@link #propagateMust(Set<PartialRelation>, | ||
133 | // Set<PartialRelation>}. | ||
134 | throw new AssertionError("No concrete type in %s".formatted(mayConcreteTypes)); | ||
135 | } | ||
136 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/TypeAnalysisResult.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/TypeAnalysisResult.java new file mode 100644 index 00000000..0745f84e --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/TypeAnalysisResult.java | |||
@@ -0,0 +1,4 @@ | |||
1 | package tools.refinery.store.partial.translator.typehierarchy; | ||
2 | |||
3 | sealed interface TypeAnalysisResult permits EliminatedType, PreservedType { | ||
4 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/TypeAnalyzer.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/TypeAnalyzer.java new file mode 100644 index 00000000..062b4c49 --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/TypeAnalyzer.java | |||
@@ -0,0 +1,202 @@ | |||
1 | package tools.refinery.store.partial.translator.typehierarchy; | ||
2 | |||
3 | import tools.refinery.store.partial.representation.PartialRelation; | ||
4 | |||
5 | import java.util.*; | ||
6 | |||
7 | class TypeAnalyzer { | ||
8 | private final Map<PartialRelation, ExtendedTypeInfo> extendedTypeInfoMap; | ||
9 | private final Map<PartialRelation, PartialRelation> replacements = new LinkedHashMap<>(); | ||
10 | private final InferredType unknownType; | ||
11 | private final Map<PartialRelation, TypeAnalysisResult> analysisResults; | ||
12 | |||
13 | public TypeAnalyzer(Map<PartialRelation, TypeInfo> typeInfoMap) { | ||
14 | int size = typeInfoMap.size(); | ||
15 | extendedTypeInfoMap = new LinkedHashMap<>(size); | ||
16 | var concreteTypes = new LinkedHashSet<PartialRelation>(); | ||
17 | int index = 0; | ||
18 | for (var entry : typeInfoMap.entrySet()) { | ||
19 | var type = entry.getKey(); | ||
20 | var typeInfo = entry.getValue(); | ||
21 | extendedTypeInfoMap.put(type, new ExtendedTypeInfo(index, type, typeInfo)); | ||
22 | if (!typeInfo.abstractType()) { | ||
23 | concreteTypes.add(type); | ||
24 | } | ||
25 | index++; | ||
26 | } | ||
27 | unknownType = new InferredType(Set.of(), concreteTypes, null); | ||
28 | computeAllSupertypes(); | ||
29 | computeAllAndConcreteSubtypes(); | ||
30 | computeDirectSubtypes(); | ||
31 | eliminateTrivialSupertypes(); | ||
32 | analysisResults = computeAnalysisResults(); | ||
33 | } | ||
34 | |||
35 | public InferredType getUnknownType() { | ||
36 | return unknownType; | ||
37 | } | ||
38 | |||
39 | public Map<PartialRelation, TypeAnalysisResult> getAnalysisResults() { | ||
40 | return analysisResults; | ||
41 | } | ||
42 | |||
43 | private void computeAllSupertypes() { | ||
44 | boolean changed; | ||
45 | do { | ||
46 | changed = false; | ||
47 | for (var extendedTypeInfo : extendedTypeInfoMap.values()) { | ||
48 | var found = new HashSet<PartialRelation>(); | ||
49 | var allSupertypes = extendedTypeInfo.getAllSupertypes(); | ||
50 | for (var supertype : allSupertypes) { | ||
51 | found.addAll(extendedTypeInfoMap.get(supertype).getAllSupertypes()); | ||
52 | } | ||
53 | if (allSupertypes.addAll(found)) { | ||
54 | changed = true; | ||
55 | } | ||
56 | } | ||
57 | } while (changed); | ||
58 | } | ||
59 | |||
60 | private void computeAllAndConcreteSubtypes() { | ||
61 | for (var extendedTypeInfo : extendedTypeInfoMap.values()) { | ||
62 | var type = extendedTypeInfo.getType(); | ||
63 | if (!extendedTypeInfo.isAbstractType()) { | ||
64 | extendedTypeInfo.getConcreteSubtypesAndSelf().add(type); | ||
65 | } | ||
66 | for (var supertype : extendedTypeInfo.getAllSupertypes()) { | ||
67 | if (type.equals(supertype)) { | ||
68 | throw new IllegalArgumentException("%s cannot be a supertype of itself".formatted(type)); | ||
69 | } | ||
70 | var supertypeInfo = extendedTypeInfoMap.get(supertype); | ||
71 | supertypeInfo.getAllSubtypes().add(type); | ||
72 | if (!extendedTypeInfo.isAbstractType()) { | ||
73 | supertypeInfo.getConcreteSubtypesAndSelf().add(type); | ||
74 | } | ||
75 | } | ||
76 | } | ||
77 | } | ||
78 | |||
79 | private void computeDirectSubtypes() { | ||
80 | for (var extendedTypeInfo : extendedTypeInfoMap.values()) { | ||
81 | var allSubtypes = extendedTypeInfo.getAllSubtypes(); | ||
82 | var directSubtypes = new LinkedHashSet<>(allSubtypes); | ||
83 | var indirectSubtypes = new LinkedHashSet<PartialRelation>(allSubtypes.size()); | ||
84 | for (var subtype : allSubtypes) { | ||
85 | indirectSubtypes.addAll(extendedTypeInfoMap.get(subtype).getAllSubtypes()); | ||
86 | } | ||
87 | directSubtypes.removeAll(indirectSubtypes); | ||
88 | extendedTypeInfo.setDirectSubtypes(directSubtypes); | ||
89 | } | ||
90 | } | ||
91 | |||
92 | private void eliminateTrivialSupertypes() { | ||
93 | boolean changed; | ||
94 | do { | ||
95 | var toRemove = new ArrayList<PartialRelation>(); | ||
96 | for (var entry : extendedTypeInfoMap.entrySet()) { | ||
97 | var extendedTypeInfo = entry.getValue(); | ||
98 | boolean isAbstract = extendedTypeInfo.isAbstractType(); | ||
99 | // Do not eliminate abstract types with 0 subtypes, because they can be used para-consistently, i.e., | ||
100 | // an object determined to <b>must</b> have an abstract type with 0 subtypes <b>may not</b> ever exist. | ||
101 | boolean hasSingleDirectSubtype = extendedTypeInfo.getDirectSubtypes().size() == 1; | ||
102 | if (isAbstract && hasSingleDirectSubtype) { | ||
103 | toRemove.add(entry.getKey()); | ||
104 | } | ||
105 | } | ||
106 | toRemove.forEach(this::removeTrivialType); | ||
107 | changed = !toRemove.isEmpty(); | ||
108 | } while (changed); | ||
109 | } | ||
110 | |||
111 | private void removeTrivialType(PartialRelation trivialType) { | ||
112 | var extendedTypeInfo = extendedTypeInfoMap.get(trivialType); | ||
113 | var iterator = extendedTypeInfo.getDirectSubtypes().iterator(); | ||
114 | if (!iterator.hasNext()) { | ||
115 | throw new AssertionError("Expected trivial supertype %s to have a direct subtype" | ||
116 | .formatted(trivialType)); | ||
117 | } | ||
118 | PartialRelation replacement = setReplacement(trivialType, iterator.next()); | ||
119 | if (iterator.hasNext()) { | ||
120 | throw new AssertionError("Expected trivial supertype %s to have at most 1 direct subtype" | ||
121 | .formatted(trivialType)); | ||
122 | } | ||
123 | replacements.put(trivialType, replacement); | ||
124 | for (var supertype : extendedTypeInfo.getAllSupertypes()) { | ||
125 | var extendedSupertypeInfo = extendedTypeInfoMap.get(supertype); | ||
126 | if (!extendedSupertypeInfo.getAllSubtypes().remove(trivialType)) { | ||
127 | throw new AssertionError("Expected %s to be subtype of %s".formatted(trivialType, supertype)); | ||
128 | } | ||
129 | var directSubtypes = extendedSupertypeInfo.getDirectSubtypes(); | ||
130 | if (directSubtypes.remove(trivialType)) { | ||
131 | directSubtypes.add(replacement); | ||
132 | } | ||
133 | } | ||
134 | for (var subtype : extendedTypeInfo.getAllSubtypes()) { | ||
135 | var extendedSubtypeInfo = extendedTypeInfoMap.get(subtype); | ||
136 | if (!extendedSubtypeInfo.getAllSupertypes().remove(trivialType)) { | ||
137 | throw new AssertionError("Expected %s to be supertype of %s".formatted(trivialType, subtype)); | ||
138 | } | ||
139 | } | ||
140 | extendedTypeInfoMap.remove(trivialType); | ||
141 | } | ||
142 | |||
143 | private PartialRelation setReplacement(PartialRelation trivialRelation, PartialRelation replacement) { | ||
144 | if (replacement == null) { | ||
145 | return trivialRelation; | ||
146 | } | ||
147 | var resolved = setReplacement(replacement, replacements.get(replacement)); | ||
148 | replacements.put(trivialRelation, resolved); | ||
149 | return resolved; | ||
150 | } | ||
151 | |||
152 | private Map<PartialRelation, TypeAnalysisResult> computeAnalysisResults() { | ||
153 | var allExtendedTypeInfoList = sortTypes(); | ||
154 | var results = new LinkedHashMap<PartialRelation, TypeAnalysisResult>( | ||
155 | allExtendedTypeInfoList.size() + replacements.size()); | ||
156 | for (var extendedTypeInfo : allExtendedTypeInfoList) { | ||
157 | var type = extendedTypeInfo.getType(); | ||
158 | results.put(type, new PreservedType(extendedTypeInfo, allExtendedTypeInfoList)); | ||
159 | } | ||
160 | for (var entry : replacements.entrySet()) { | ||
161 | var type = entry.getKey(); | ||
162 | results.put(type, new EliminatedType(entry.getValue())); | ||
163 | } | ||
164 | return Collections.unmodifiableMap(results); | ||
165 | } | ||
166 | |||
167 | private List<ExtendedTypeInfo> sortTypes() { | ||
168 | // Invert {@code directSubtypes} to keep track of the out-degree of types. | ||
169 | for (var extendedTypeInfo : extendedTypeInfoMap.values()) { | ||
170 | for (var directSubtype : extendedTypeInfo.getDirectSubtypes()) { | ||
171 | var extendedDirectSubtypeInfo = extendedTypeInfoMap.get(directSubtype); | ||
172 | extendedDirectSubtypeInfo.getUnsortedDirectSupertypes().add(extendedTypeInfo.getType()); | ||
173 | } | ||
174 | } | ||
175 | // Build a <i>inverse</i> topological order ({@code extends} edges always points to earlier nodes in the order, | ||
176 | // breaking ties according to the original order ({@link ExtendedTypeInfo#index}) to form a 'stable' sort. | ||
177 | // See, e.g., https://stackoverflow.com/a/11236027. | ||
178 | var priorityQueue = new PriorityQueue<ExtendedTypeInfo>(); | ||
179 | for (var extendedTypeInfo : extendedTypeInfoMap.values()) { | ||
180 | if (extendedTypeInfo.getUnsortedDirectSupertypes().isEmpty()) { | ||
181 | priorityQueue.add(extendedTypeInfo); | ||
182 | } | ||
183 | } | ||
184 | var sorted = new ArrayList<ExtendedTypeInfo>(extendedTypeInfoMap.size()); | ||
185 | while (!priorityQueue.isEmpty()) { | ||
186 | var extendedTypeInfo = priorityQueue.remove(); | ||
187 | sorted.add(extendedTypeInfo); | ||
188 | for (var directSubtype : extendedTypeInfo.getDirectSubtypes()) { | ||
189 | var extendedDirectSubtypeInfo = extendedTypeInfoMap.get(directSubtype); | ||
190 | var unsortedDirectSupertypes = extendedDirectSubtypeInfo.getUnsortedDirectSupertypes(); | ||
191 | if (!unsortedDirectSupertypes.remove(extendedTypeInfo.getType())) { | ||
192 | throw new AssertionError("Expected %s to be a direct supertype of %s" | ||
193 | .formatted(extendedTypeInfo.getType(), directSubtype)); | ||
194 | } | ||
195 | if (unsortedDirectSupertypes.isEmpty()) { | ||
196 | priorityQueue.add(extendedDirectSubtypeInfo); | ||
197 | } | ||
198 | } | ||
199 | } | ||
200 | return Collections.unmodifiableList(sorted); | ||
201 | } | ||
202 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/TypeHierarchyTranslationUnit.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/TypeHierarchyTranslationUnit.java new file mode 100644 index 00000000..7f438f71 --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/TypeHierarchyTranslationUnit.java | |||
@@ -0,0 +1,52 @@ | |||
1 | package tools.refinery.store.partial.translator.typehierarchy; | ||
2 | |||
3 | import tools.refinery.store.partial.AnyPartialSymbolInterpretation; | ||
4 | import tools.refinery.store.partial.literal.Modality; | ||
5 | import tools.refinery.store.partial.representation.AnyPartialSymbol; | ||
6 | import tools.refinery.store.partial.representation.PartialRelation; | ||
7 | import tools.refinery.store.partial.translator.Advice; | ||
8 | import tools.refinery.store.partial.translator.TranslationUnit; | ||
9 | import tools.refinery.store.model.Model; | ||
10 | import tools.refinery.store.query.Variable; | ||
11 | import tools.refinery.store.query.literal.CallPolarity; | ||
12 | import tools.refinery.store.query.literal.Literal; | ||
13 | import tools.refinery.store.representation.Symbol; | ||
14 | |||
15 | import java.util.*; | ||
16 | |||
17 | public class TypeHierarchyTranslationUnit extends TranslationUnit { | ||
18 | static final Symbol<InferredType> INFERRED_TYPE_SYMBOL = new Symbol<>("inferredType", 1, | ||
19 | InferredType.class, InferredType.UNTYPED); | ||
20 | |||
21 | private final Map<PartialRelation, TypeInfo> typeInfoMap; | ||
22 | |||
23 | public TypeHierarchyTranslationUnit(Map<PartialRelation, TypeInfo> typeInfoMap) { | ||
24 | this.typeInfoMap = new LinkedHashMap<>(typeInfoMap); | ||
25 | } | ||
26 | |||
27 | @Override | ||
28 | public Collection<AnyPartialSymbol> getTranslatedPartialSymbols() { | ||
29 | return null; | ||
30 | } | ||
31 | |||
32 | @Override | ||
33 | public void configure(Collection<Advice> advices) { | ||
34 | |||
35 | } | ||
36 | |||
37 | @Override | ||
38 | public List<Literal> call(CallPolarity polarity, Modality modality, PartialRelation target, | ||
39 | List<Variable> arguments) { | ||
40 | return null; | ||
41 | } | ||
42 | |||
43 | @Override | ||
44 | public Map<AnyPartialSymbol, AnyPartialSymbolInterpretation> createPartialInterpretations(Model model) { | ||
45 | return null; | ||
46 | } | ||
47 | |||
48 | @Override | ||
49 | public void initializeModel(Model model, int nodeCount) { | ||
50 | |||
51 | } | ||
52 | } | ||
diff --git a/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/TypeInfo.java b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/TypeInfo.java new file mode 100644 index 00000000..1b0922fe --- /dev/null +++ b/subprojects/store-partial/src/main/java/tools/refinery/store/partial/translator/typehierarchy/TypeInfo.java | |||
@@ -0,0 +1,46 @@ | |||
1 | package tools.refinery.store.partial.translator.typehierarchy; | ||
2 | |||
3 | import tools.refinery.store.partial.representation.PartialRelation; | ||
4 | |||
5 | import java.util.*; | ||
6 | |||
7 | public record TypeInfo(Collection<PartialRelation> supertypes, boolean abstractType) { | ||
8 | public static Builder builder() { | ||
9 | return new Builder(); | ||
10 | } | ||
11 | |||
12 | public static class Builder { | ||
13 | private final Set<PartialRelation> supertypes = new LinkedHashSet<>(); | ||
14 | private boolean abstractType; | ||
15 | |||
16 | private Builder() { | ||
17 | } | ||
18 | |||
19 | public Builder supertypes(Collection<PartialRelation> supertypes) { | ||
20 | this.supertypes.addAll(supertypes); | ||
21 | return this; | ||
22 | } | ||
23 | |||
24 | public Builder supertypes(PartialRelation... supertypes) { | ||
25 | return supertypes(List.of(supertypes)); | ||
26 | } | ||
27 | |||
28 | public Builder supertype(PartialRelation supertype) { | ||
29 | supertypes.add(supertype); | ||
30 | return this; | ||
31 | } | ||
32 | |||
33 | public Builder abstractType(boolean abstractType) { | ||
34 | this.abstractType = abstractType; | ||
35 | return this; | ||
36 | } | ||
37 | |||
38 | public Builder abstractType() { | ||
39 | return abstractType(true); | ||
40 | } | ||
41 | |||
42 | public TypeInfo build() { | ||
43 | return new TypeInfo(Collections.unmodifiableSet(supertypes), abstractType); | ||
44 | } | ||
45 | } | ||
46 | } | ||