diff options
author | 2023-02-17 17:39:12 +0100 | |
---|---|---|
committer | 2023-02-20 17:29:20 +0100 | |
commit | 3e5a9bb7a258de77e5ca5dc46e3c730317f8b894 (patch) | |
tree | 298af498dce88566b1084f1cbf3286b323e9b9b1 /subprojects/store/src | |
parent | feat: PartialInterpretation representations (diff) | |
download | refinery-3e5a9bb7a258de77e5ca5dc46e3c730317f8b894.tar.gz refinery-3e5a9bb7a258de77e5ca5dc46e3c730317f8b894.tar.zst refinery-3e5a9bb7a258de77e5ca5dc46e3c730317f8b894.zip |
feat: type inference for class hierarchies
Diffstat (limited to 'subprojects/store/src')
11 files changed, 1011 insertions, 0 deletions
diff --git a/subprojects/store/src/main/java/tools/refinery/store/partial/translator/typehierarchy/EliminatedType.java b/subprojects/store/src/main/java/tools/refinery/store/partial/translator/typehierarchy/EliminatedType.java new file mode 100644 index 00000000..9adf6bc8 --- /dev/null +++ b/subprojects/store/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/src/main/java/tools/refinery/store/partial/translator/typehierarchy/ExtendedTypeInfo.java b/subprojects/store/src/main/java/tools/refinery/store/partial/translator/typehierarchy/ExtendedTypeInfo.java new file mode 100644 index 00000000..d3f66a4c --- /dev/null +++ b/subprojects/store/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/src/main/java/tools/refinery/store/partial/translator/typehierarchy/InferredType.java b/subprojects/store/src/main/java/tools/refinery/store/partial/translator/typehierarchy/InferredType.java new file mode 100644 index 00000000..729b1fb5 --- /dev/null +++ b/subprojects/store/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/src/main/java/tools/refinery/store/partial/translator/typehierarchy/PreservedType.java b/subprojects/store/src/main/java/tools/refinery/store/partial/translator/typehierarchy/PreservedType.java new file mode 100644 index 00000000..0299ae03 --- /dev/null +++ b/subprojects/store/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/src/main/java/tools/refinery/store/partial/translator/typehierarchy/TypeAnalysisResult.java b/subprojects/store/src/main/java/tools/refinery/store/partial/translator/typehierarchy/TypeAnalysisResult.java new file mode 100644 index 00000000..0745f84e --- /dev/null +++ b/subprojects/store/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/src/main/java/tools/refinery/store/partial/translator/typehierarchy/TypeAnalyzer.java b/subprojects/store/src/main/java/tools/refinery/store/partial/translator/typehierarchy/TypeAnalyzer.java new file mode 100644 index 00000000..062b4c49 --- /dev/null +++ b/subprojects/store/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/src/main/java/tools/refinery/store/partial/translator/typehierarchy/TypeInfo.java b/subprojects/store/src/main/java/tools/refinery/store/partial/translator/typehierarchy/TypeInfo.java new file mode 100644 index 00000000..1b0922fe --- /dev/null +++ b/subprojects/store/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 | } | ||
diff --git a/subprojects/store/src/test/java/tools/refinery/store/partial/translator/typehierarchy/InferredTypeTest.java b/subprojects/store/src/test/java/tools/refinery/store/partial/translator/typehierarchy/InferredTypeTest.java new file mode 100644 index 00000000..9efa76ef --- /dev/null +++ b/subprojects/store/src/test/java/tools/refinery/store/partial/translator/typehierarchy/InferredTypeTest.java | |||
@@ -0,0 +1,32 @@ | |||
1 | package tools.refinery.store.partial.translator.typehierarchy; | ||
2 | |||
3 | import org.junit.jupiter.api.Test; | ||
4 | import tools.refinery.store.partial.representation.PartialRelation; | ||
5 | |||
6 | import java.util.Set; | ||
7 | |||
8 | import static org.hamcrest.MatcherAssert.assertThat; | ||
9 | import static org.hamcrest.Matchers.is; | ||
10 | |||
11 | class InferredTypeTest { | ||
12 | private final PartialRelation c1 = new PartialRelation("C1", 1); | ||
13 | private final PartialRelation c2 = new PartialRelation("C2", 1); | ||
14 | |||
15 | @Test | ||
16 | void untypedIsConsistentTest() { | ||
17 | var sut = new InferredType(Set.of(), Set.of(c1, c2), null); | ||
18 | assertThat(sut.isConsistent(), is(true)); | ||
19 | } | ||
20 | |||
21 | @Test | ||
22 | void typedIsConsistentTest() { | ||
23 | var sut = new InferredType(Set.of(c1), Set.of(c1, c2), c1); | ||
24 | assertThat(sut.isConsistent(), is(true)); | ||
25 | } | ||
26 | |||
27 | @Test | ||
28 | void typedIsInconsistentTest() { | ||
29 | var sut = new InferredType(Set.of(c1), Set.of(), null); | ||
30 | assertThat(sut.isConsistent(), is(false)); | ||
31 | } | ||
32 | } | ||
diff --git a/subprojects/store/src/test/java/tools/refinery/store/partial/translator/typehierarchy/TypeAnalyzerExampleHierarchyTest.java b/subprojects/store/src/test/java/tools/refinery/store/partial/translator/typehierarchy/TypeAnalyzerExampleHierarchyTest.java new file mode 100644 index 00000000..5f528328 --- /dev/null +++ b/subprojects/store/src/test/java/tools/refinery/store/partial/translator/typehierarchy/TypeAnalyzerExampleHierarchyTest.java | |||
@@ -0,0 +1,203 @@ | |||
1 | package tools.refinery.store.partial.translator.typehierarchy; | ||
2 | |||
3 | import org.junit.jupiter.api.BeforeEach; | ||
4 | import org.junit.jupiter.api.Test; | ||
5 | import tools.refinery.store.partial.representation.PartialRelation; | ||
6 | import tools.refinery.store.representation.TruthValue; | ||
7 | |||
8 | import java.util.LinkedHashMap; | ||
9 | import java.util.Set; | ||
10 | |||
11 | import static org.hamcrest.MatcherAssert.assertThat; | ||
12 | import static org.hamcrest.Matchers.is; | ||
13 | import static org.junit.jupiter.api.Assertions.assertAll; | ||
14 | |||
15 | class TypeAnalyzerExampleHierarchyTest { | ||
16 | private final PartialRelation a1 = new PartialRelation("A1", 1); | ||
17 | private final PartialRelation a2 = new PartialRelation("A2", 1); | ||
18 | private final PartialRelation a3 = new PartialRelation("A3", 1); | ||
19 | private final PartialRelation a4 = new PartialRelation("A4", 1); | ||
20 | private final PartialRelation a5 = new PartialRelation("A5", 1); | ||
21 | private final PartialRelation c1 = new PartialRelation("C1", 1); | ||
22 | private final PartialRelation c2 = new PartialRelation("C2", 1); | ||
23 | private final PartialRelation c3 = new PartialRelation("C3", 1); | ||
24 | private final PartialRelation c4 = new PartialRelation("C4", 1); | ||
25 | |||
26 | private TypeAnalyzer sut; | ||
27 | private TypeAnalyzerTester tester; | ||
28 | |||
29 | @BeforeEach | ||
30 | void beforeEach() { | ||
31 | var typeInfoMap = new LinkedHashMap<PartialRelation, TypeInfo>(); | ||
32 | typeInfoMap.put(a1, TypeInfo.builder().abstractType().build()); | ||
33 | typeInfoMap.put(a2, TypeInfo.builder().abstractType().build()); | ||
34 | typeInfoMap.put(a3, TypeInfo.builder().abstractType().build()); | ||
35 | typeInfoMap.put(a4, TypeInfo.builder().abstractType().build()); | ||
36 | typeInfoMap.put(a5, TypeInfo.builder().abstractType().build()); | ||
37 | typeInfoMap.put(c1, TypeInfo.builder().supertypes(a1, a4).build()); | ||
38 | typeInfoMap.put(c2, TypeInfo.builder().supertypes(a1, a2, a3, a4).build()); | ||
39 | typeInfoMap.put(c3, TypeInfo.builder().supertype(a3).build()); | ||
40 | typeInfoMap.put(c4, TypeInfo.builder().supertype(a4).build()); | ||
41 | sut = new TypeAnalyzer(typeInfoMap); | ||
42 | tester = new TypeAnalyzerTester(sut); | ||
43 | } | ||
44 | |||
45 | @Test | ||
46 | void analysisResultsTest() { | ||
47 | assertAll( | ||
48 | () -> tester.assertAbstractType(a1, c1, c2), | ||
49 | () -> tester.assertEliminatedType(a2, c2), | ||
50 | () -> tester.assertAbstractType(a3, c2, c3), | ||
51 | () -> tester.assertAbstractType(a4, c1, c2, c4), | ||
52 | () -> tester.assertVacuousType(a5), | ||
53 | () -> tester.assertConcreteType(c1), | ||
54 | () -> tester.assertConcreteType(c2), | ||
55 | () -> tester.assertConcreteType(c3), | ||
56 | () -> tester.assertConcreteType(c4) | ||
57 | ); | ||
58 | } | ||
59 | |||
60 | @Test | ||
61 | void inferredTypesTest() { | ||
62 | assertAll( | ||
63 | () -> assertThat(sut.getUnknownType(), is(new InferredType(Set.of(), Set.of(c1, c2, c3, c4), null))), | ||
64 | () -> assertThat(tester.getInferredType(a1), is(new InferredType(Set.of(a1, a4), Set.of(c1, c2), c1))), | ||
65 | () -> assertThat(tester.getInferredType(a3), is(new InferredType(Set.of(a3), Set.of(c2, c3), c2))), | ||
66 | () -> assertThat(tester.getInferredType(a4), is(new InferredType(Set.of(a4), Set.of(c1, c2, c4), c1))), | ||
67 | () -> assertThat(tester.getInferredType(a5), is(new InferredType(Set.of(a5), Set.of(), null))), | ||
68 | () -> assertThat(tester.getInferredType(c1), is(new InferredType(Set.of(a1, a4, c1), Set.of(c1), c1))), | ||
69 | () -> assertThat(tester.getInferredType(c2), | ||
70 | is(new InferredType(Set.of(a1, a3, a4, c2), Set.of(c2), c2))), | ||
71 | () -> assertThat(tester.getInferredType(c3), is(new InferredType(Set.of(a3, c3), Set.of(c3), c3))), | ||
72 | () -> assertThat(tester.getInferredType(c4), is(new InferredType(Set.of(a4, c4), Set.of(c4), c4))) | ||
73 | ); | ||
74 | } | ||
75 | |||
76 | @Test | ||
77 | void consistentMustTest() { | ||
78 | var a1Result = tester.getPreservedType(a1); | ||
79 | var a3Result = tester.getPreservedType(a3); | ||
80 | var expected = new InferredType(Set.of(a1, a3, a4, c2), Set.of(c2), c2); | ||
81 | assertAll( | ||
82 | () -> assertThat(a1Result.merge(a3Result.asInferredType(), TruthValue.TRUE), is(expected)), | ||
83 | () -> assertThat(a3Result.merge(a1Result.asInferredType(), TruthValue.TRUE), is(expected)), | ||
84 | () -> assertThat(a1Result.merge(sut.getUnknownType(), TruthValue.TRUE), is(a1Result.asInferredType())), | ||
85 | () -> assertThat(a3Result.merge(sut.getUnknownType(), TruthValue.TRUE), is(a3Result.asInferredType())), | ||
86 | () -> assertThat(a1Result.merge(a1Result.asInferredType(), TruthValue.TRUE), | ||
87 | is(a1Result.asInferredType())) | ||
88 | ); | ||
89 | } | ||
90 | |||
91 | @Test | ||
92 | void consistentMayNotTest() { | ||
93 | var a1Result = tester.getPreservedType(a1); | ||
94 | var a3Result = tester.getPreservedType(a3); | ||
95 | var a4Result = tester.getPreservedType(a4); | ||
96 | assertAll( | ||
97 | () -> assertThat(a1Result.merge(a3Result.asInferredType(), TruthValue.FALSE), | ||
98 | is(new InferredType(Set.of(a3, c3), Set.of(c3), c3))), | ||
99 | () -> assertThat(a3Result.merge(a1Result.asInferredType(), TruthValue.FALSE), | ||
100 | is(new InferredType(Set.of(a1, a4, c1), Set.of(c1), c1))), | ||
101 | () -> assertThat(a4Result.merge(a3Result.asInferredType(), TruthValue.FALSE), | ||
102 | is(new InferredType(Set.of(a3, c3), Set.of(c3), c3))), | ||
103 | () -> assertThat(a3Result.merge(a4Result.asInferredType(), TruthValue.FALSE), | ||
104 | is(new InferredType(Set.of(a4), Set.of(c1, c4), c1))), | ||
105 | () -> assertThat(a1Result.merge(sut.getUnknownType(), TruthValue.FALSE), | ||
106 | is(new InferredType(Set.of(), Set.of(c3, c4), null))), | ||
107 | () -> assertThat(a3Result.merge(sut.getUnknownType(), TruthValue.FALSE), | ||
108 | is(new InferredType(Set.of(), Set.of(c1, c4), null))), | ||
109 | () -> assertThat(a4Result.merge(sut.getUnknownType(), TruthValue.FALSE), | ||
110 | is(new InferredType(Set.of(), Set.of(c3), null))) | ||
111 | ); | ||
112 | } | ||
113 | |||
114 | @Test | ||
115 | void consistentErrorTest() { | ||
116 | var c1Result = tester.getPreservedType(c1); | ||
117 | var a4Result = tester.getPreservedType(a4); | ||
118 | var expected = new InferredType(Set.of(c1, a1, a4), Set.of(), null); | ||
119 | assertAll( | ||
120 | () -> assertThat(c1Result.merge(a4Result.asInferredType(), TruthValue.ERROR), is(expected)), | ||
121 | () -> assertThat(a4Result.merge(c1Result.asInferredType(), TruthValue.ERROR), is(expected)) | ||
122 | ); | ||
123 | } | ||
124 | |||
125 | @Test | ||
126 | void consistentUnknownTest() { | ||
127 | var c1Result = tester.getPreservedType(c1); | ||
128 | var a4Result = tester.getPreservedType(a4); | ||
129 | assertAll( | ||
130 | () -> assertThat(c1Result.merge(a4Result.asInferredType(), TruthValue.UNKNOWN), | ||
131 | is(a4Result.asInferredType())), | ||
132 | () -> assertThat(a4Result.merge(c1Result.asInferredType(), TruthValue.UNKNOWN), | ||
133 | is(c1Result.asInferredType())) | ||
134 | ); | ||
135 | } | ||
136 | |||
137 | @Test | ||
138 | void inconsistentMustTest() { | ||
139 | var a1Result = tester.getPreservedType(a1); | ||
140 | var c3Result = tester.getPreservedType(c3); | ||
141 | assertAll( | ||
142 | () -> assertThat(a1Result.merge(c3Result.asInferredType(), TruthValue.TRUE), | ||
143 | is(new InferredType(Set.of(a1, a3, c3), Set.of(), null))), | ||
144 | () -> assertThat(c3Result.merge(a1Result.asInferredType(), TruthValue.TRUE), | ||
145 | is(new InferredType(Set.of(a1, a3, a4, c3), Set.of(), null))) | ||
146 | ); | ||
147 | } | ||
148 | |||
149 | @Test | ||
150 | void inconsistentMayNotTest() { | ||
151 | var a1Result = tester.getPreservedType(a1); | ||
152 | var a4Result = tester.getPreservedType(a4); | ||
153 | var c1Result = tester.getPreservedType(c1); | ||
154 | assertAll( | ||
155 | () -> assertThat(a4Result.merge(a1Result.asInferredType(), TruthValue.FALSE), | ||
156 | is(new InferredType(Set.of(a1, a4), Set.of(), null))), | ||
157 | () -> assertThat(a1Result.merge(c1Result.asInferredType(), TruthValue.FALSE), | ||
158 | is(new InferredType(Set.of(a1, a4, c1), Set.of(), null))), | ||
159 | () -> assertThat(a4Result.merge(c1Result.asInferredType(), TruthValue.FALSE), | ||
160 | is(new InferredType(Set.of(a1, a4, c1), Set.of(), null))), | ||
161 | () -> assertThat(a1Result.merge(a1Result.asInferredType(), TruthValue.FALSE), | ||
162 | is(new InferredType(Set.of(a1, a4), Set.of(), null))) | ||
163 | ); | ||
164 | } | ||
165 | |||
166 | @Test | ||
167 | void vacuousMustTest() { | ||
168 | var c1Result = tester.getPreservedType(c1); | ||
169 | var a5Result = tester.getPreservedType(a5); | ||
170 | assertAll( | ||
171 | () -> assertThat(c1Result.merge(a5Result.asInferredType(), TruthValue.TRUE), | ||
172 | is(new InferredType(Set.of(a1, a4, a5, c1), Set.of(), null))), | ||
173 | () -> assertThat(a5Result.merge(c1Result.asInferredType(), TruthValue.TRUE), | ||
174 | is(new InferredType(Set.of(a1, a4, a5, c1), Set.of(), null))) | ||
175 | ); | ||
176 | } | ||
177 | |||
178 | @Test | ||
179 | void vacuousMayNotTest() { | ||
180 | var c1Result = tester.getPreservedType(c1); | ||
181 | var a5Result = tester.getPreservedType(a5); | ||
182 | assertAll( | ||
183 | () -> assertThat(c1Result.merge(a5Result.asInferredType(), TruthValue.FALSE), | ||
184 | is(a5Result.asInferredType())), | ||
185 | () -> assertThat(a5Result.merge(c1Result.asInferredType(), TruthValue.FALSE), | ||
186 | is(c1Result.asInferredType())) | ||
187 | ); | ||
188 | } | ||
189 | |||
190 | @Test | ||
191 | void vacuousErrorTest() { | ||
192 | var c1Result = tester.getPreservedType(c1); | ||
193 | var a5Result = tester.getPreservedType(a5); | ||
194 | assertAll( | ||
195 | () -> assertThat(c1Result.merge(a5Result.asInferredType(), TruthValue.ERROR), | ||
196 | is(new InferredType(Set.of(a1, a4, a5, c1), Set.of(), null))), | ||
197 | () -> assertThat(a5Result.merge(c1Result.asInferredType(), TruthValue.ERROR), | ||
198 | is(new InferredType(Set.of(a1, a4, a5, c1), Set.of(), null))), | ||
199 | () -> assertThat(a5Result.merge(a5Result.asInferredType(), TruthValue.ERROR), | ||
200 | is(a5Result.asInferredType())) | ||
201 | ); | ||
202 | } | ||
203 | } | ||
diff --git a/subprojects/store/src/test/java/tools/refinery/store/partial/translator/typehierarchy/TypeAnalyzerTest.java b/subprojects/store/src/test/java/tools/refinery/store/partial/translator/typehierarchy/TypeAnalyzerTest.java new file mode 100644 index 00000000..02903026 --- /dev/null +++ b/subprojects/store/src/test/java/tools/refinery/store/partial/translator/typehierarchy/TypeAnalyzerTest.java | |||
@@ -0,0 +1,200 @@ | |||
1 | package tools.refinery.store.partial.translator.typehierarchy; | ||
2 | |||
3 | import org.junit.jupiter.api.Test; | ||
4 | import tools.refinery.store.partial.representation.PartialRelation; | ||
5 | import tools.refinery.store.representation.TruthValue; | ||
6 | |||
7 | import java.util.LinkedHashMap; | ||
8 | import java.util.Set; | ||
9 | |||
10 | import static org.hamcrest.MatcherAssert.assertThat; | ||
11 | import static org.hamcrest.Matchers.is; | ||
12 | import static org.junit.jupiter.api.Assertions.assertAll; | ||
13 | import static org.junit.jupiter.api.Assertions.assertThrows; | ||
14 | |||
15 | class TypeAnalyzerTest { | ||
16 | @Test | ||
17 | void directSupertypesTest() { | ||
18 | var c1 = new PartialRelation("C1", 1); | ||
19 | var c2 = new PartialRelation("C2", 1); | ||
20 | var c3 = new PartialRelation("C3", 1); | ||
21 | var typeInfoMap = new LinkedHashMap<PartialRelation, TypeInfo>(); | ||
22 | typeInfoMap.put(c1, TypeInfo.builder().supertypes(c2, c3).build()); | ||
23 | typeInfoMap.put(c2, TypeInfo.builder().supertype(c3).build()); | ||
24 | typeInfoMap.put(c3, TypeInfo.builder().build()); | ||
25 | |||
26 | var sut = new TypeAnalyzer(typeInfoMap); | ||
27 | var tester = new TypeAnalyzerTester(sut); | ||
28 | |||
29 | assertAll( | ||
30 | () -> tester.assertConcreteType(c1), | ||
31 | () -> tester.assertConcreteType(c2, c1), | ||
32 | () -> tester.assertConcreteType(c3, c2) | ||
33 | ); | ||
34 | } | ||
35 | |||
36 | @Test | ||
37 | void typeEliminationAbstractToConcreteTest() { | ||
38 | var c1 = new PartialRelation("C1", 1); | ||
39 | var c2 = new PartialRelation("C2", 1); | ||
40 | var a11 = new PartialRelation("A11", 1); | ||
41 | var a12 = new PartialRelation("A12", 1); | ||
42 | var a21 = new PartialRelation("A21", 1); | ||
43 | var a22 = new PartialRelation("A22", 1); | ||
44 | var a3 = new PartialRelation("A3", 1); | ||
45 | var typeInfoMap = new LinkedHashMap<PartialRelation, TypeInfo>(); | ||
46 | typeInfoMap.put(a3, TypeInfo.builder().abstractType().build()); | ||
47 | typeInfoMap.put(a21, TypeInfo.builder().abstractType().supertype(a3).build()); | ||
48 | typeInfoMap.put(a22, TypeInfo.builder().abstractType().supertype(a3).build()); | ||
49 | typeInfoMap.put(a11, TypeInfo.builder().abstractType().supertypes(a21, a22).build()); | ||
50 | typeInfoMap.put(a12, TypeInfo.builder().abstractType().supertypes(a21, a22).build()); | ||
51 | typeInfoMap.put(c1, TypeInfo.builder().supertypes(a11, a12).build()); | ||
52 | typeInfoMap.put(c2, TypeInfo.builder().supertype(a3).build()); | ||
53 | |||
54 | var sut = new TypeAnalyzer(typeInfoMap); | ||
55 | var tester = new TypeAnalyzerTester(sut); | ||
56 | |||
57 | assertAll( | ||
58 | () -> tester.assertConcreteType(c1), | ||
59 | () -> tester.assertConcreteType(c2), | ||
60 | () -> tester.assertEliminatedType(a11, c1), | ||
61 | () -> tester.assertEliminatedType(a12, c1), | ||
62 | () -> tester.assertEliminatedType(a21, c1), | ||
63 | () -> tester.assertEliminatedType(a22, c1), | ||
64 | () -> tester.assertAbstractType(a3, c1, c2) | ||
65 | ); | ||
66 | } | ||
67 | |||
68 | @Test | ||
69 | void typeEliminationConcreteToAbstractTest() { | ||
70 | var c1 = new PartialRelation("C1", 1); | ||
71 | var c2 = new PartialRelation("C2", 1); | ||
72 | var a11 = new PartialRelation("A11", 1); | ||
73 | var a12 = new PartialRelation("A12", 1); | ||
74 | var a21 = new PartialRelation("A21", 1); | ||
75 | var a22 = new PartialRelation("A22", 1); | ||
76 | var a3 = new PartialRelation("A3", 1); | ||
77 | var typeInfoMap = new LinkedHashMap<PartialRelation, TypeInfo>(); | ||
78 | typeInfoMap.put(c1, TypeInfo.builder().supertypes(a11, a12).build()); | ||
79 | typeInfoMap.put(c2, TypeInfo.builder().supertype(a3).build()); | ||
80 | typeInfoMap.put(a11, TypeInfo.builder().abstractType().supertypes(a21, a22).build()); | ||
81 | typeInfoMap.put(a12, TypeInfo.builder().abstractType().supertypes(a21, a22).build()); | ||
82 | typeInfoMap.put(a21, TypeInfo.builder().abstractType().supertype(a3).build()); | ||
83 | typeInfoMap.put(a22, TypeInfo.builder().abstractType().supertype(a3).build()); | ||
84 | typeInfoMap.put(a3, TypeInfo.builder().abstractType().build()); | ||
85 | |||
86 | var sut = new TypeAnalyzer(typeInfoMap); | ||
87 | var tester = new TypeAnalyzerTester(sut); | ||
88 | |||
89 | assertAll( | ||
90 | () -> tester.assertConcreteType(c1), | ||
91 | () -> tester.assertConcreteType(c2), | ||
92 | () -> tester.assertEliminatedType(a11, c1), | ||
93 | () -> tester.assertEliminatedType(a12, c1), | ||
94 | () -> tester.assertEliminatedType(a21, c1), | ||
95 | () -> tester.assertEliminatedType(a22, c1), | ||
96 | () -> tester.assertAbstractType(a3, c1, c2) | ||
97 | ); | ||
98 | } | ||
99 | |||
100 | @Test | ||
101 | void preserveConcreteTypeTest() { | ||
102 | var c1 = new PartialRelation("C1", 1); | ||
103 | var a1 = new PartialRelation("A1", 1); | ||
104 | var c2 = new PartialRelation("C2", 1); | ||
105 | var a2 = new PartialRelation("A2", 1); | ||
106 | var typeInfoMap = new LinkedHashMap<PartialRelation, TypeInfo>(); | ||
107 | typeInfoMap.put(c1, TypeInfo.builder().supertype(a1).build()); | ||
108 | typeInfoMap.put(a1, TypeInfo.builder().abstractType().supertype(c2).build()); | ||
109 | typeInfoMap.put(c2, TypeInfo.builder().supertype(a2).build()); | ||
110 | typeInfoMap.put(a2, TypeInfo.builder().abstractType().build()); | ||
111 | |||
112 | var sut = new TypeAnalyzer(typeInfoMap); | ||
113 | var tester = new TypeAnalyzerTester(sut); | ||
114 | |||
115 | assertAll( | ||
116 | () -> tester.assertConcreteType(c1), | ||
117 | () -> tester.assertEliminatedType(a1, c1), | ||
118 | () -> tester.assertConcreteType(c2, c1), | ||
119 | () -> tester.assertEliminatedType(a2, c2) | ||
120 | ); | ||
121 | } | ||
122 | |||
123 | @Test | ||
124 | void mostGeneralCurrentTypeTest() { | ||
125 | var c1 = new PartialRelation("C1", 1); | ||
126 | var c2 = new PartialRelation("C2", 1); | ||
127 | var c3 = new PartialRelation("C3", 1); | ||
128 | var typeInfoMap = new LinkedHashMap<PartialRelation, TypeInfo>(); | ||
129 | typeInfoMap.put(c1, TypeInfo.builder().supertype(c3).build()); | ||
130 | typeInfoMap.put(c2, TypeInfo.builder().supertype(c3).build()); | ||
131 | typeInfoMap.put(c3, TypeInfo.builder().build()); | ||
132 | |||
133 | var sut = new TypeAnalyzer(typeInfoMap); | ||
134 | var tester = new TypeAnalyzerTester(sut); | ||
135 | var c3Result = tester.getPreservedType(c3); | ||
136 | |||
137 | var expected = new InferredType(Set.of(c3), Set.of(c1, c2, c3), c3); | ||
138 | assertAll( | ||
139 | () -> assertThat(tester.getInferredType(c3), is(expected)), | ||
140 | () -> assertThat(c3Result.merge(sut.getUnknownType(), TruthValue.TRUE), is(expected)) | ||
141 | ); | ||
142 | } | ||
143 | |||
144 | @Test | ||
145 | void preferFirstConcreteTypeTest() { | ||
146 | var a1 = new PartialRelation("A1", 1); | ||
147 | var c1 = new PartialRelation("C1", 1); | ||
148 | var c2 = new PartialRelation("C2", 1); | ||
149 | var c3 = new PartialRelation("C3", 1); | ||
150 | var c4 = new PartialRelation("C4", 1); | ||
151 | var typeInfoMap = new LinkedHashMap<PartialRelation, TypeInfo>(); | ||
152 | typeInfoMap.put(c1, TypeInfo.builder().supertype(a1).build()); | ||
153 | typeInfoMap.put(c2, TypeInfo.builder().supertype(a1).build()); | ||
154 | typeInfoMap.put(c3, TypeInfo.builder().supertype(a1).build()); | ||
155 | typeInfoMap.put(c4, TypeInfo.builder().supertype(c3).build()); | ||
156 | typeInfoMap.put(a1, TypeInfo.builder().abstractType().build()); | ||
157 | |||
158 | var sut = new TypeAnalyzer(typeInfoMap); | ||
159 | var tester = new TypeAnalyzerTester(sut); | ||
160 | var c1Result = tester.getPreservedType(c1); | ||
161 | var a1Result = tester.getPreservedType(a1); | ||
162 | |||
163 | assertThat(c1Result.merge(a1Result.asInferredType(), TruthValue.FALSE), | ||
164 | is(new InferredType(Set.of(a1), Set.of(c2, c3, c4), c2))); | ||
165 | } | ||
166 | |||
167 | @Test | ||
168 | void preferFirstMostGeneralConcreteTypeTest() { | ||
169 | var a1 = new PartialRelation("A1", 1); | ||
170 | var c1 = new PartialRelation("C1", 1); | ||
171 | var c2 = new PartialRelation("C2", 1); | ||
172 | var c3 = new PartialRelation("C3", 1); | ||
173 | var c4 = new PartialRelation("C4", 1); | ||
174 | var typeInfoMap = new LinkedHashMap<PartialRelation, TypeInfo>(); | ||
175 | typeInfoMap.put(c4, TypeInfo.builder().supertype(c3).build()); | ||
176 | typeInfoMap.put(c3, TypeInfo.builder().supertype(a1).build()); | ||
177 | typeInfoMap.put(c2, TypeInfo.builder().supertype(a1).build()); | ||
178 | typeInfoMap.put(c1, TypeInfo.builder().supertype(a1).build()); | ||
179 | typeInfoMap.put(a1, TypeInfo.builder().abstractType().build()); | ||
180 | |||
181 | var sut = new TypeAnalyzer(typeInfoMap); | ||
182 | var tester = new TypeAnalyzerTester(sut); | ||
183 | var c1Result = tester.getPreservedType(c1); | ||
184 | var a1Result = tester.getPreservedType(a1); | ||
185 | |||
186 | assertThat(c1Result.merge(a1Result.asInferredType(), TruthValue.FALSE), | ||
187 | is(new InferredType(Set.of(a1), Set.of(c2, c3, c4), c3))); | ||
188 | } | ||
189 | |||
190 | @Test | ||
191 | void circularTypeHierarchyTest() { | ||
192 | var c1 = new PartialRelation("C1", 1); | ||
193 | var c2 = new PartialRelation("C2", 1); | ||
194 | var typeInfoMap = new LinkedHashMap<PartialRelation, TypeInfo>(); | ||
195 | typeInfoMap.put(c1, TypeInfo.builder().supertype(c2).build()); | ||
196 | typeInfoMap.put(c2, TypeInfo.builder().supertype(c1).build()); | ||
197 | |||
198 | assertThrows(IllegalArgumentException.class, () -> new TypeAnalyzer(typeInfoMap)); | ||
199 | } | ||
200 | } | ||
diff --git a/subprojects/store/src/test/java/tools/refinery/store/partial/translator/typehierarchy/TypeAnalyzerTester.java b/subprojects/store/src/test/java/tools/refinery/store/partial/translator/typehierarchy/TypeAnalyzerTester.java new file mode 100644 index 00000000..ce600ea6 --- /dev/null +++ b/subprojects/store/src/test/java/tools/refinery/store/partial/translator/typehierarchy/TypeAnalyzerTester.java | |||
@@ -0,0 +1,51 @@ | |||
1 | package tools.refinery.store.partial.translator.typehierarchy; | ||
2 | |||
3 | import tools.refinery.store.partial.representation.PartialRelation; | ||
4 | |||
5 | import static org.hamcrest.MatcherAssert.assertThat; | ||
6 | import static org.hamcrest.Matchers.*; | ||
7 | import static org.hamcrest.Matchers.is; | ||
8 | |||
9 | class TypeAnalyzerTester { | ||
10 | private final TypeAnalyzer sut; | ||
11 | |||
12 | public TypeAnalyzerTester(TypeAnalyzer sut) { | ||
13 | this.sut = sut; | ||
14 | } | ||
15 | |||
16 | public void assertAbstractType(PartialRelation partialRelation, PartialRelation... directSubtypes) { | ||
17 | assertPreservedType(partialRelation, true, false, directSubtypes); | ||
18 | } | ||
19 | |||
20 | public void assertVacuousType(PartialRelation partialRelation) { | ||
21 | assertPreservedType(partialRelation, true, true); | ||
22 | } | ||
23 | |||
24 | public void assertConcreteType(PartialRelation partialRelation, PartialRelation... directSubtypes) { | ||
25 | assertPreservedType(partialRelation, false, false, directSubtypes); | ||
26 | } | ||
27 | |||
28 | private void assertPreservedType(PartialRelation partialRelation, boolean isAbstract, boolean isVacuous, | ||
29 | PartialRelation... directSubtypes) { | ||
30 | var result = sut.getAnalysisResults().get(partialRelation); | ||
31 | assertThat(result, is(instanceOf(PreservedType.class))); | ||
32 | var preservedResult = (PreservedType) result; | ||
33 | assertThat(preservedResult.isAbstractType(), is(isAbstract)); | ||
34 | assertThat(preservedResult.isVacuous(), is(isVacuous)); | ||
35 | assertThat(preservedResult.getDirectSubtypes(), hasItems(directSubtypes)); | ||
36 | } | ||
37 | |||
38 | public void assertEliminatedType(PartialRelation partialRelation, PartialRelation replacement) { | ||
39 | var result = sut.getAnalysisResults().get(partialRelation); | ||
40 | assertThat(result, is(instanceOf(EliminatedType.class))); | ||
41 | assertThat(((EliminatedType) result).replacement(), is(replacement)); | ||
42 | } | ||
43 | |||
44 | public PreservedType getPreservedType(PartialRelation partialRelation) { | ||
45 | return (PreservedType) sut.getAnalysisResults().get(partialRelation); | ||
46 | } | ||
47 | |||
48 | public InferredType getInferredType(PartialRelation partialRelation) { | ||
49 | return getPreservedType(partialRelation).asInferredType(); | ||
50 | } | ||
51 | } | ||