diff options
author | Kristóf Marussy <kristof@marussy.com> | 2023-02-17 17:39:12 +0100 |
---|---|---|
committer | Kristóf Marussy <kristof@marussy.com> | 2023-02-20 17:29:20 +0100 |
commit | 3e5a9bb7a258de77e5ca5dc46e3c730317f8b894 (patch) | |
tree | 298af498dce88566b1084f1cbf3286b323e9b9b1 /subprojects/store/src/main/java/tools | |
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/main/java/tools')
7 files changed, 525 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 | } | ||