feat: type inference for class hierarchies

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 @@
+package tools.refinery.store.partial.translator.typehierarchy;
+
+import tools.refinery.store.partial.representation.PartialRelation;
+
+record EliminatedType(PartialRelation replacement) implements TypeAnalysisResult {
+}
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 @@
+package tools.refinery.store.partial.translator.typehierarchy;
+
+import org.jetbrains.annotations.NotNull;
+import tools.refinery.store.partial.representation.PartialRelation;
+
+import java.util.HashSet;
+import java.util.LinkedHashSet;
+import java.util.Objects;
+import java.util.Set;
+
+final class ExtendedTypeInfo implements Comparable<ExtendedTypeInfo> {
+        private final int index;
+        private final PartialRelation type;
+        private final TypeInfo typeInfo;
+        private final Set<PartialRelation> allSubtypes = new LinkedHashSet<>();
+        private final Set<PartialRelation> allSupertypes;
+        private final Set<PartialRelation> concreteSubtypesAndSelf = new LinkedHashSet<>();
+        private Set<PartialRelation> directSubtypes;
+        private final Set<PartialRelation> unsortedDirectSupertypes = new HashSet<>();
+
+        public ExtendedTypeInfo(int index, PartialRelation type, TypeInfo typeInfo) {
+                this.index = index;
+                this.type = type;
+                this.typeInfo = typeInfo;
+                this.allSupertypes = new LinkedHashSet<>(typeInfo.supertypes());
+        }
+
+        public PartialRelation getType() {
+                return type;
+        }
+
+        public TypeInfo getTypeInfo() {
+                return typeInfo;
+        }
+
+        public boolean isAbstractType() {
+                return getTypeInfo().abstractType();
+        }
+
+        public Set<PartialRelation> getAllSubtypes() {
+                return allSubtypes;
+        }
+
+        public Set<PartialRelation> getAllSupertypes() {
+                return allSupertypes;
+        }
+
+        public Set<PartialRelation> getAllSupertypesAndSelf() {
+                var allSubtypesAndSelf = new HashSet<PartialRelation>(allSupertypes.size() + 1);
+                addMust(allSubtypesAndSelf);
+                return allSubtypesAndSelf;
+        }
+
+        public Set<PartialRelation> getConcreteSubtypesAndSelf() {
+                return concreteSubtypesAndSelf;
+        }
+
+        public Set<PartialRelation> getDirectSubtypes() {
+                return directSubtypes;
+        }
+
+        public Set<PartialRelation> getUnsortedDirectSupertypes() {
+                return unsortedDirectSupertypes;
+        }
+
+        public void setDirectSubtypes(Set<PartialRelation> directSubtypes) {
+                this.directSubtypes = directSubtypes;
+        }
+
+        public boolean allowsAllConcreteTypes(Set<PartialRelation> concreteTypes) {
+                for (var concreteType : concreteTypes) {
+                        if (!concreteSubtypesAndSelf.contains(concreteType)) {
+                                return false;
+                        }
+                }
+                return true;
+        }
+
+        public void addMust(Set<PartialRelation> mustTypes) {
+                mustTypes.add(type);
+                mustTypes.addAll(allSupertypes);
+        }
+
+        @Override
+        public int compareTo(@NotNull ExtendedTypeInfo extendedTypeInfo) {
+                return Integer.compare(index, extendedTypeInfo.index);
+        }
+
+        @Override
+        public boolean equals(Object o) {
+                if (this == o) return true;
+                if (o == null || getClass() != o.getClass()) return false;
+                ExtendedTypeInfo that = (ExtendedTypeInfo) o;
+                return index == that.index;
+        }
+
+        @Override
+        public int hashCode() {
+                return Objects.hash(index);
+        }
+}
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 @@
+package tools.refinery.store.partial.translator.typehierarchy;
+
+import tools.refinery.store.partial.representation.PartialRelation;
+
+import java.util.Collections;
+import java.util.Set;
+
+record InferredType(Set<PartialRelation> mustTypes, Set<PartialRelation> mayConcreteTypes,
+                                        PartialRelation currentType) {
+        public static final InferredType UNTYPED = new InferredType(Set.of(), Set.of(), null);
+
+        public InferredType(Set<PartialRelation> mustTypes, Set<PartialRelation> mayConcreteTypes,
+                                                PartialRelation currentType) {
+                this.mustTypes = Collections.unmodifiableSet(mustTypes);
+                this.mayConcreteTypes = Collections.unmodifiableSet(mayConcreteTypes);
+                this.currentType = currentType;
+        }
+
+        public boolean isConsistent() {
+                return currentType != null || mustTypes.isEmpty();
+        }
+
+        public boolean isMust(PartialRelation partialRelation) {
+                return mustTypes.contains(partialRelation);
+        }
+
+        public boolean isMayConcrete(PartialRelation partialRelation) {
+                return mayConcreteTypes.contains(partialRelation);
+        }
+}
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 @@
+package tools.refinery.store.partial.translator.typehierarchy;
+
+import tools.refinery.store.partial.representation.PartialRelation;
+import tools.refinery.store.representation.TruthValue;
+
+import java.util.*;
+
+final class PreservedType implements TypeAnalysisResult {
+        private final ExtendedTypeInfo extendedTypeInfo;
+        private final List<PartialRelation> directSubtypes;
+        private final List<ExtendedTypeInfo> allExternalTypeInfoList;
+        private final InferredType inferredType;
+
+        public PreservedType(ExtendedTypeInfo extendedTypeInfo, List<ExtendedTypeInfo> allExternalTypeInfoList) {
+                this.extendedTypeInfo = extendedTypeInfo;
+                directSubtypes = List.copyOf(extendedTypeInfo.getDirectSubtypes());
+                this.allExternalTypeInfoList = allExternalTypeInfoList;
+                inferredType = propagateMust(extendedTypeInfo.getAllSupertypesAndSelf(),
+                                extendedTypeInfo.getConcreteSubtypesAndSelf());
+        }
+
+        public PartialRelation type() {
+                return extendedTypeInfo.getType();
+        }
+
+        public List<PartialRelation> getDirectSubtypes() {
+                return directSubtypes;
+        }
+
+        public boolean isAbstractType() {
+                return extendedTypeInfo.isAbstractType();
+        }
+
+        public boolean isVacuous() {
+                return isAbstractType() && directSubtypes.isEmpty();
+        }
+
+        public InferredType asInferredType() {
+                return inferredType;
+        }
+
+        public InferredType merge(InferredType inferredType, TruthValue value) {
+                return switch (value) {
+                        case UNKNOWN -> inferredType;
+                        case TRUE -> addMust(inferredType);
+                        case FALSE -> removeMay(inferredType);
+                        case ERROR -> addError(inferredType);
+                };
+        }
+
+        private InferredType addMust(InferredType inferredType) {
+                var originalMustTypes = inferredType.mustTypes();
+                if (originalMustTypes.contains(type())) {
+                        return inferredType;
+                }
+                var mustTypes = new HashSet<>(originalMustTypes);
+                extendedTypeInfo.addMust(mustTypes);
+                var originalMayConcreteTypes = inferredType.mayConcreteTypes();
+                var mayConcreteTypes = new LinkedHashSet<>(originalMayConcreteTypes);
+                Set<PartialRelation> mayConcreteTypesResult;
+                if (mayConcreteTypes.retainAll(extendedTypeInfo.getConcreteSubtypesAndSelf())) {
+                        mayConcreteTypesResult = mayConcreteTypes;
+                } else {
+                        mayConcreteTypesResult = originalMayConcreteTypes;
+                }
+                return propagateMust(mustTypes, mayConcreteTypesResult);
+        }
+
+        private InferredType removeMay(InferredType inferredType) {
+                var originalMayConcreteTypes = inferredType.mayConcreteTypes();
+                var mayConcreteTypes = new LinkedHashSet<>(originalMayConcreteTypes);
+                if (!mayConcreteTypes.removeAll(extendedTypeInfo.getConcreteSubtypesAndSelf())) {
+                        return inferredType;
+                }
+                return propagateMust(inferredType.mustTypes(), mayConcreteTypes);
+        }
+
+        private InferredType addError(InferredType inferredType) {
+                var originalMustTypes = inferredType.mustTypes();
+                if (originalMustTypes.contains(type())) {
+                        if (inferredType.mayConcreteTypes().isEmpty()) {
+                                return inferredType;
+                        }
+                        return new InferredType(originalMustTypes, Set.of(), null);
+                }
+                var mustTypes = new HashSet<>(originalMustTypes);
+                extendedTypeInfo.addMust(mustTypes);
+                return new InferredType(mustTypes, Set.of(), null);
+        }
+
+        private InferredType propagateMust(Set<PartialRelation> originalMustTypes,
+                                                                           Set<PartialRelation> mayConcreteTypes) {
+                // It is possible that there is not type at all, do not force one by propagation.
+                var maybeUntyped = originalMustTypes.isEmpty();
+                // Para-consistent case, do not propagate must types to avoid logical explosion.
+                var paraConsistentOrSurelyUntyped = mayConcreteTypes.isEmpty();
+                if (maybeUntyped || paraConsistentOrSurelyUntyped) {
+                        return new InferredType(originalMustTypes, mayConcreteTypes, null);
+                }
+                var currentType = computeCurrentType(mayConcreteTypes);
+                var mustTypes = new HashSet<>(originalMustTypes);
+                boolean changed = false;
+                for (var newMustExtendedTypeInfo : allExternalTypeInfoList) {
+                        var newMustType = newMustExtendedTypeInfo.getType();
+                        if (mustTypes.contains(newMustType)) {
+                                continue;
+                        }
+                        if (newMustExtendedTypeInfo.allowsAllConcreteTypes(mayConcreteTypes)) {
+                                newMustExtendedTypeInfo.addMust(mustTypes);
+                                changed = true;
+                        }
+                }
+                if (!changed) {
+                        return new InferredType(originalMustTypes, mayConcreteTypes, currentType);
+                }
+                return new InferredType(mustTypes, mayConcreteTypes, currentType);
+        }
+
+        /**
+         * Returns a concrete type that is allowed by a (consistent, i.e., nonempty) set of <b>may</b> concrete types.
+         *
+         * @param mayConcreteTypes The set of allowed concrete types. Must not be empty.
+         * @return The first concrete type that is allowed by {@code matConcreteTypes}.
+         */
+        private PartialRelation computeCurrentType(Set<PartialRelation> mayConcreteTypes) {
+                for (var concreteExtendedTypeInfo : allExternalTypeInfoList) {
+                        var concreteType = concreteExtendedTypeInfo.getType();
+                        if (!concreteExtendedTypeInfo.isAbstractType() && mayConcreteTypes.contains(concreteType)) {
+                                return concreteType;
+                        }
+                }
+                // We have already filtered out the para-consistent case in {@link #propagateMust(Set<PartialRelation>,
+                // Set<PartialRelation>}.
+                throw new AssertionError("No concrete type in %s".formatted(mayConcreteTypes));
+        }
+}
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 @@
+package tools.refinery.store.partial.translator.typehierarchy;
+
+sealed interface TypeAnalysisResult permits EliminatedType, PreservedType {
+}
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 @@
+package tools.refinery.store.partial.translator.typehierarchy;
+
+import tools.refinery.store.partial.representation.PartialRelation;
+
+import java.util.*;
+
+class TypeAnalyzer {
+        private final Map<PartialRelation, ExtendedTypeInfo> extendedTypeInfoMap;
+        private final Map<PartialRelation, PartialRelation> replacements = new LinkedHashMap<>();
+        private final InferredType unknownType;
+        private final Map<PartialRelation, TypeAnalysisResult> analysisResults;
+
+        public TypeAnalyzer(Map<PartialRelation, TypeInfo> typeInfoMap) {
+                int size = typeInfoMap.size();
+                extendedTypeInfoMap = new LinkedHashMap<>(size);
+                var concreteTypes = new LinkedHashSet<PartialRelation>();
+                int index = 0;
+                for (var entry : typeInfoMap.entrySet()) {
+                        var type = entry.getKey();
+                        var typeInfo = entry.getValue();
+                        extendedTypeInfoMap.put(type, new ExtendedTypeInfo(index, type, typeInfo));
+                        if (!typeInfo.abstractType()) {
+                                concreteTypes.add(type);
+                        }
+                        index++;
+                }
+                unknownType = new InferredType(Set.of(), concreteTypes, null);
+                computeAllSupertypes();
+                computeAllAndConcreteSubtypes();
+                computeDirectSubtypes();
+                eliminateTrivialSupertypes();
+                analysisResults = computeAnalysisResults();
+        }
+
+        public InferredType getUnknownType() {
+                return unknownType;
+        }
+
+        public Map<PartialRelation, TypeAnalysisResult> getAnalysisResults() {
+                return analysisResults;
+        }
+
+        private void computeAllSupertypes() {
+                boolean changed;
+                do {
+                        changed = false;
+                        for (var extendedTypeInfo : extendedTypeInfoMap.values()) {
+                                var found = new HashSet<PartialRelation>();
+                                var allSupertypes = extendedTypeInfo.getAllSupertypes();
+                                for (var supertype : allSupertypes) {
+                                        found.addAll(extendedTypeInfoMap.get(supertype).getAllSupertypes());
+                                }
+                                if (allSupertypes.addAll(found)) {
+                                        changed = true;
+                                }
+                        }
+                } while (changed);
+        }
+
+        private void computeAllAndConcreteSubtypes() {
+                for (var extendedTypeInfo : extendedTypeInfoMap.values()) {
+                        var type = extendedTypeInfo.getType();
+                        if (!extendedTypeInfo.isAbstractType()) {
+                                extendedTypeInfo.getConcreteSubtypesAndSelf().add(type);
+                        }
+                        for (var supertype : extendedTypeInfo.getAllSupertypes()) {
+                                if (type.equals(supertype)) {
+                                        throw new IllegalArgumentException("%s cannot be a supertype of itself".formatted(type));
+                                }
+                                var supertypeInfo = extendedTypeInfoMap.get(supertype);
+                                supertypeInfo.getAllSubtypes().add(type);
+                                if (!extendedTypeInfo.isAbstractType()) {
+                                        supertypeInfo.getConcreteSubtypesAndSelf().add(type);
+                                }
+                        }
+                }
+        }
+
+        private void computeDirectSubtypes() {
+                for (var extendedTypeInfo : extendedTypeInfoMap.values()) {
+                        var allSubtypes = extendedTypeInfo.getAllSubtypes();
+                        var directSubtypes = new LinkedHashSet<>(allSubtypes);
+                        var indirectSubtypes = new LinkedHashSet<PartialRelation>(allSubtypes.size());
+                        for (var subtype : allSubtypes) {
+                                indirectSubtypes.addAll(extendedTypeInfoMap.get(subtype).getAllSubtypes());
+                        }
+                        directSubtypes.removeAll(indirectSubtypes);
+                        extendedTypeInfo.setDirectSubtypes(directSubtypes);
+                }
+        }
+
+        private void eliminateTrivialSupertypes() {
+                boolean changed;
+                do {
+                        var toRemove = new ArrayList<PartialRelation>();
+                        for (var entry : extendedTypeInfoMap.entrySet()) {
+                                var extendedTypeInfo = entry.getValue();
+                                boolean isAbstract = extendedTypeInfo.isAbstractType();
+                                // Do not eliminate abstract types with 0 subtypes, because they can be used para-consistently, i.e.,
+                                // an object determined to <b>must</b> have an abstract type with 0 subtypes <b>may not</b> ever exist.
+                                boolean hasSingleDirectSubtype = extendedTypeInfo.getDirectSubtypes().size() == 1;
+                                if (isAbstract && hasSingleDirectSubtype) {
+                                        toRemove.add(entry.getKey());
+                                }
+                        }
+                        toRemove.forEach(this::removeTrivialType);
+                        changed = !toRemove.isEmpty();
+                } while (changed);
+        }
+
+        private void removeTrivialType(PartialRelation trivialType) {
+                var extendedTypeInfo = extendedTypeInfoMap.get(trivialType);
+                var iterator = extendedTypeInfo.getDirectSubtypes().iterator();
+                if (!iterator.hasNext()) {
+                        throw new AssertionError("Expected trivial supertype %s to have a direct subtype"
+                                        .formatted(trivialType));
+                }
+                PartialRelation replacement = setReplacement(trivialType, iterator.next());
+                if (iterator.hasNext()) {
+                        throw new AssertionError("Expected trivial supertype %s to have at most 1 direct subtype"
+                                        .formatted(trivialType));
+                }
+                replacements.put(trivialType, replacement);
+                for (var supertype : extendedTypeInfo.getAllSupertypes()) {
+                        var extendedSupertypeInfo = extendedTypeInfoMap.get(supertype);
+                        if (!extendedSupertypeInfo.getAllSubtypes().remove(trivialType)) {
+                                throw new AssertionError("Expected %s to be subtype of %s".formatted(trivialType, supertype));
+                        }
+                        var directSubtypes = extendedSupertypeInfo.getDirectSubtypes();
+                        if (directSubtypes.remove(trivialType)) {
+                                directSubtypes.add(replacement);
+                        }
+                }
+                for (var subtype : extendedTypeInfo.getAllSubtypes()) {
+                        var extendedSubtypeInfo = extendedTypeInfoMap.get(subtype);
+                        if (!extendedSubtypeInfo.getAllSupertypes().remove(trivialType)) {
+                                throw new AssertionError("Expected %s to be supertype of %s".formatted(trivialType, subtype));
+                        }
+                }
+                extendedTypeInfoMap.remove(trivialType);
+        }
+
+        private PartialRelation setReplacement(PartialRelation trivialRelation, PartialRelation replacement) {
+                if (replacement == null) {
+                        return trivialRelation;
+                }
+                var resolved = setReplacement(replacement, replacements.get(replacement));
+                replacements.put(trivialRelation, resolved);
+                return resolved;
+        }
+
+        private Map<PartialRelation, TypeAnalysisResult> computeAnalysisResults() {
+                var allExtendedTypeInfoList = sortTypes();
+                var results = new LinkedHashMap<PartialRelation, TypeAnalysisResult>(
+                                allExtendedTypeInfoList.size() + replacements.size());
+                for (var extendedTypeInfo : allExtendedTypeInfoList) {
+                        var type = extendedTypeInfo.getType();
+                        results.put(type, new PreservedType(extendedTypeInfo, allExtendedTypeInfoList));
+                }
+                for (var entry : replacements.entrySet()) {
+                        var type = entry.getKey();
+                        results.put(type, new EliminatedType(entry.getValue()));
+                }
+                return Collections.unmodifiableMap(results);
+        }
+
+        private List<ExtendedTypeInfo> sortTypes() {
+                // Invert {@code directSubtypes} to keep track of the out-degree of types.
+                for (var extendedTypeInfo : extendedTypeInfoMap.values()) {
+                        for (var directSubtype : extendedTypeInfo.getDirectSubtypes()) {
+                                var extendedDirectSubtypeInfo = extendedTypeInfoMap.get(directSubtype);
+                                extendedDirectSubtypeInfo.getUnsortedDirectSupertypes().add(extendedTypeInfo.getType());
+                        }
+                }
+                // Build a <i>inverse</i> topological order ({@code extends} edges always points to earlier nodes in the order,
+                // breaking ties according to the original order ({@link ExtendedTypeInfo#index}) to form a 'stable' sort.
+                // See, e.g., https://stackoverflow.com/a/11236027.
+                var priorityQueue = new PriorityQueue<ExtendedTypeInfo>();
+                for (var extendedTypeInfo : extendedTypeInfoMap.values()) {
+                        if (extendedTypeInfo.getUnsortedDirectSupertypes().isEmpty()) {
+                                priorityQueue.add(extendedTypeInfo);
+                        }
+                }
+                var sorted = new ArrayList<ExtendedTypeInfo>(extendedTypeInfoMap.size());
+                while (!priorityQueue.isEmpty()) {
+                        var extendedTypeInfo = priorityQueue.remove();
+                        sorted.add(extendedTypeInfo);
+                        for (var directSubtype : extendedTypeInfo.getDirectSubtypes()) {
+                                var extendedDirectSubtypeInfo = extendedTypeInfoMap.get(directSubtype);
+                                var unsortedDirectSupertypes = extendedDirectSubtypeInfo.getUnsortedDirectSupertypes();
+                                if (!unsortedDirectSupertypes.remove(extendedTypeInfo.getType())) {
+                                        throw new AssertionError("Expected %s to be a direct supertype of %s"
+                                                        .formatted(extendedTypeInfo.getType(), directSubtype));
+                                }
+                                if (unsortedDirectSupertypes.isEmpty()) {
+                                        priorityQueue.add(extendedDirectSubtypeInfo);
+                                }
+                        }
+                }
+                return Collections.unmodifiableList(sorted);
+        }
+}
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 @@
+package tools.refinery.store.partial.translator.typehierarchy;
+
+import tools.refinery.store.partial.representation.PartialRelation;
+
+import java.util.*;
+
+public record TypeInfo(Collection<PartialRelation> supertypes, boolean abstractType) {
+        public static Builder builder() {
+                return new Builder();
+        }
+
+        public static class Builder {
+                private final Set<PartialRelation> supertypes = new LinkedHashSet<>();
+                private boolean abstractType;
+
+                private Builder() {
+                }
+
+                public Builder supertypes(Collection<PartialRelation> supertypes) {
+                        this.supertypes.addAll(supertypes);
+                        return this;
+                }
+
+                public Builder supertypes(PartialRelation... supertypes) {
+                        return supertypes(List.of(supertypes));
+                }
+
+                public Builder supertype(PartialRelation supertype) {
+                        supertypes.add(supertype);
+                        return this;
+                }
+
+                public Builder abstractType(boolean abstractType) {
+                        this.abstractType = abstractType;
+                        return this;
+                }
+
+                public Builder abstractType() {
+                        return abstractType(true);
+                }
+
+                public TypeInfo build() {
+                        return new TypeInfo(Collections.unmodifiableSet(supertypes), abstractType);
+                }
+        }
+}
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 @@
+package tools.refinery.store.partial.translator.typehierarchy;
+
+import org.junit.jupiter.api.Test;
+import tools.refinery.store.partial.representation.PartialRelation;
+
+import java.util.Set;
+
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.hamcrest.Matchers.is;
+
+class InferredTypeTest {
+        private final PartialRelation c1 = new PartialRelation("C1", 1);
+        private final PartialRelation c2 = new PartialRelation("C2", 1);
+
+        @Test
+        void untypedIsConsistentTest() {
+                var sut = new InferredType(Set.of(), Set.of(c1, c2), null);
+                assertThat(sut.isConsistent(), is(true));
+        }
+
+        @Test
+        void typedIsConsistentTest() {
+                var sut = new InferredType(Set.of(c1), Set.of(c1, c2), c1);
+                assertThat(sut.isConsistent(), is(true));
+        }
+
+        @Test
+        void typedIsInconsistentTest() {
+                var sut = new InferredType(Set.of(c1), Set.of(), null);
+                assertThat(sut.isConsistent(), is(false));
+        }
+}
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 @@
+package tools.refinery.store.partial.translator.typehierarchy;
+
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
+import tools.refinery.store.partial.representation.PartialRelation;
+import tools.refinery.store.representation.TruthValue;
+
+import java.util.LinkedHashMap;
+import java.util.Set;
+
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.hamcrest.Matchers.is;
+import static org.junit.jupiter.api.Assertions.assertAll;
+
+class TypeAnalyzerExampleHierarchyTest {
+        private final PartialRelation a1 = new PartialRelation("A1", 1);
+        private final PartialRelation a2 = new PartialRelation("A2", 1);
+        private final PartialRelation a3 = new PartialRelation("A3", 1);
+        private final PartialRelation a4 = new PartialRelation("A4", 1);
+        private final PartialRelation a5 = new PartialRelation("A5", 1);
+        private final PartialRelation c1 = new PartialRelation("C1", 1);
+        private final PartialRelation c2 = new PartialRelation("C2", 1);
+        private final PartialRelation c3 = new PartialRelation("C3", 1);
+        private final PartialRelation c4 = new PartialRelation("C4", 1);
+
+        private TypeAnalyzer sut;
+        private TypeAnalyzerTester tester;
+
+        @BeforeEach
+        void beforeEach() {
+                var typeInfoMap = new LinkedHashMap<PartialRelation, TypeInfo>();
+                typeInfoMap.put(a1, TypeInfo.builder().abstractType().build());
+                typeInfoMap.put(a2, TypeInfo.builder().abstractType().build());
+                typeInfoMap.put(a3, TypeInfo.builder().abstractType().build());
+                typeInfoMap.put(a4, TypeInfo.builder().abstractType().build());
+                typeInfoMap.put(a5, TypeInfo.builder().abstractType().build());
+                typeInfoMap.put(c1, TypeInfo.builder().supertypes(a1, a4).build());
+                typeInfoMap.put(c2, TypeInfo.builder().supertypes(a1, a2, a3, a4).build());
+                typeInfoMap.put(c3, TypeInfo.builder().supertype(a3).build());
+                typeInfoMap.put(c4, TypeInfo.builder().supertype(a4).build());
+                sut = new TypeAnalyzer(typeInfoMap);
+                tester = new TypeAnalyzerTester(sut);
+        }
+
+        @Test
+        void analysisResultsTest() {
+                assertAll(
+                                () -> tester.assertAbstractType(a1, c1, c2),
+                                () -> tester.assertEliminatedType(a2, c2),
+                                () -> tester.assertAbstractType(a3, c2, c3),
+                                () -> tester.assertAbstractType(a4, c1, c2, c4),
+                                () -> tester.assertVacuousType(a5),
+                                () -> tester.assertConcreteType(c1),
+                                () -> tester.assertConcreteType(c2),
+                                () -> tester.assertConcreteType(c3),
+                                () -> tester.assertConcreteType(c4)
+                );
+        }
+
+        @Test
+        void inferredTypesTest() {
+                assertAll(
+                                () -> assertThat(sut.getUnknownType(), is(new InferredType(Set.of(), Set.of(c1, c2, c3, c4), null))),
+                                () -> assertThat(tester.getInferredType(a1), is(new InferredType(Set.of(a1, a4), Set.of(c1, c2), c1))),
+                                () -> assertThat(tester.getInferredType(a3), is(new InferredType(Set.of(a3), Set.of(c2, c3), c2))),
+                                () -> assertThat(tester.getInferredType(a4), is(new InferredType(Set.of(a4), Set.of(c1, c2, c4), c1))),
+                                () -> assertThat(tester.getInferredType(a5), is(new InferredType(Set.of(a5), Set.of(), null))),
+                                () -> assertThat(tester.getInferredType(c1), is(new InferredType(Set.of(a1, a4, c1), Set.of(c1), c1))),
+                                () -> assertThat(tester.getInferredType(c2),
+                                                is(new InferredType(Set.of(a1, a3, a4, c2), Set.of(c2), c2))),
+                                () -> assertThat(tester.getInferredType(c3), is(new InferredType(Set.of(a3, c3), Set.of(c3), c3))),
+                                () -> assertThat(tester.getInferredType(c4), is(new InferredType(Set.of(a4, c4), Set.of(c4), c4)))
+                );
+        }
+
+        @Test
+        void consistentMustTest() {
+                var a1Result = tester.getPreservedType(a1);
+                var a3Result = tester.getPreservedType(a3);
+                var expected = new InferredType(Set.of(a1, a3, a4, c2), Set.of(c2), c2);
+                assertAll(
+                                () -> assertThat(a1Result.merge(a3Result.asInferredType(), TruthValue.TRUE), is(expected)),
+                                () -> assertThat(a3Result.merge(a1Result.asInferredType(), TruthValue.TRUE), is(expected)),
+                                () -> assertThat(a1Result.merge(sut.getUnknownType(), TruthValue.TRUE), is(a1Result.asInferredType())),
+                                () -> assertThat(a3Result.merge(sut.getUnknownType(), TruthValue.TRUE), is(a3Result.asInferredType())),
+                                () -> assertThat(a1Result.merge(a1Result.asInferredType(), TruthValue.TRUE),
+                                                is(a1Result.asInferredType()))
+                );
+        }
+
+        @Test
+        void consistentMayNotTest() {
+                var a1Result = tester.getPreservedType(a1);
+                var a3Result = tester.getPreservedType(a3);
+                var a4Result = tester.getPreservedType(a4);
+                assertAll(
+                                () -> assertThat(a1Result.merge(a3Result.asInferredType(), TruthValue.FALSE),
+                                                is(new InferredType(Set.of(a3, c3), Set.of(c3), c3))),
+                                () -> assertThat(a3Result.merge(a1Result.asInferredType(), TruthValue.FALSE),
+                                                is(new InferredType(Set.of(a1, a4, c1), Set.of(c1), c1))),
+                                () -> assertThat(a4Result.merge(a3Result.asInferredType(), TruthValue.FALSE),
+                                                is(new InferredType(Set.of(a3, c3), Set.of(c3), c3))),
+                                () -> assertThat(a3Result.merge(a4Result.asInferredType(), TruthValue.FALSE),
+                                                is(new InferredType(Set.of(a4), Set.of(c1, c4), c1))),
+                                () -> assertThat(a1Result.merge(sut.getUnknownType(), TruthValue.FALSE),
+                                                is(new InferredType(Set.of(), Set.of(c3, c4), null))),
+                                () -> assertThat(a3Result.merge(sut.getUnknownType(), TruthValue.FALSE),
+                                                is(new InferredType(Set.of(), Set.of(c1, c4), null))),
+                                () -> assertThat(a4Result.merge(sut.getUnknownType(), TruthValue.FALSE),
+                                                is(new InferredType(Set.of(), Set.of(c3), null)))
+                );
+        }
+
+        @Test
+        void consistentErrorTest() {
+                var c1Result = tester.getPreservedType(c1);
+                var a4Result = tester.getPreservedType(a4);
+                var expected = new InferredType(Set.of(c1, a1, a4), Set.of(), null);
+                assertAll(
+                                () -> assertThat(c1Result.merge(a4Result.asInferredType(), TruthValue.ERROR), is(expected)),
+                                () -> assertThat(a4Result.merge(c1Result.asInferredType(), TruthValue.ERROR), is(expected))
+                );
+        }
+
+        @Test
+        void consistentUnknownTest() {
+                var c1Result = tester.getPreservedType(c1);
+                var a4Result = tester.getPreservedType(a4);
+                assertAll(
+                                () -> assertThat(c1Result.merge(a4Result.asInferredType(), TruthValue.UNKNOWN),
+                                                is(a4Result.asInferredType())),
+                                () -> assertThat(a4Result.merge(c1Result.asInferredType(), TruthValue.UNKNOWN),
+                                                is(c1Result.asInferredType()))
+                );
+        }
+
+        @Test
+        void inconsistentMustTest() {
+                var a1Result = tester.getPreservedType(a1);
+                var c3Result = tester.getPreservedType(c3);
+                assertAll(
+                                () -> assertThat(a1Result.merge(c3Result.asInferredType(), TruthValue.TRUE),
+                                                is(new InferredType(Set.of(a1, a3, c3), Set.of(), null))),
+                                () -> assertThat(c3Result.merge(a1Result.asInferredType(), TruthValue.TRUE),
+                                                is(new InferredType(Set.of(a1, a3, a4, c3), Set.of(), null)))
+                );
+        }
+
+        @Test
+        void inconsistentMayNotTest() {
+                var a1Result = tester.getPreservedType(a1);
+                var a4Result = tester.getPreservedType(a4);
+                var c1Result = tester.getPreservedType(c1);
+                assertAll(
+                                () -> assertThat(a4Result.merge(a1Result.asInferredType(), TruthValue.FALSE),
+                                                is(new InferredType(Set.of(a1, a4), Set.of(), null))),
+                                () -> assertThat(a1Result.merge(c1Result.asInferredType(), TruthValue.FALSE),
+                                                is(new InferredType(Set.of(a1, a4, c1), Set.of(), null))),
+                                () -> assertThat(a4Result.merge(c1Result.asInferredType(), TruthValue.FALSE),
+                                                is(new InferredType(Set.of(a1, a4, c1), Set.of(), null))),
+                                () -> assertThat(a1Result.merge(a1Result.asInferredType(), TruthValue.FALSE),
+                                                is(new InferredType(Set.of(a1, a4), Set.of(), null)))
+                );
+        }
+
+        @Test
+        void vacuousMustTest() {
+                var c1Result = tester.getPreservedType(c1);
+                var a5Result = tester.getPreservedType(a5);
+                assertAll(
+                                () -> assertThat(c1Result.merge(a5Result.asInferredType(), TruthValue.TRUE),
+                                                is(new InferredType(Set.of(a1, a4, a5, c1), Set.of(), null))),
+                                () -> assertThat(a5Result.merge(c1Result.asInferredType(), TruthValue.TRUE),
+                                                is(new InferredType(Set.of(a1, a4, a5, c1), Set.of(), null)))
+                );
+        }
+
+        @Test
+        void vacuousMayNotTest() {
+                var c1Result = tester.getPreservedType(c1);
+                var a5Result = tester.getPreservedType(a5);
+                assertAll(
+                                () -> assertThat(c1Result.merge(a5Result.asInferredType(), TruthValue.FALSE),
+                                                is(a5Result.asInferredType())),
+                                () -> assertThat(a5Result.merge(c1Result.asInferredType(), TruthValue.FALSE),
+                                                is(c1Result.asInferredType()))
+                );
+        }
+
+        @Test
+        void vacuousErrorTest() {
+                var c1Result = tester.getPreservedType(c1);
+                var a5Result = tester.getPreservedType(a5);
+                assertAll(
+                                () -> assertThat(c1Result.merge(a5Result.asInferredType(), TruthValue.ERROR),
+                                                is(new InferredType(Set.of(a1, a4, a5, c1), Set.of(), null))),
+                                () -> assertThat(a5Result.merge(c1Result.asInferredType(), TruthValue.ERROR),
+                                                is(new InferredType(Set.of(a1, a4, a5, c1), Set.of(), null))),
+                                () -> assertThat(a5Result.merge(a5Result.asInferredType(), TruthValue.ERROR),
+                                                is(a5Result.asInferredType()))
+                );
+        }
+}
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 @@
+package tools.refinery.store.partial.translator.typehierarchy;
+
+import org.junit.jupiter.api.Test;
+import tools.refinery.store.partial.representation.PartialRelation;
+import tools.refinery.store.representation.TruthValue;
+
+import java.util.LinkedHashMap;
+import java.util.Set;
+
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.hamcrest.Matchers.is;
+import static org.junit.jupiter.api.Assertions.assertAll;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+class TypeAnalyzerTest {
+        @Test
+        void directSupertypesTest() {
+                var c1 = new PartialRelation("C1", 1);
+                var c2 = new PartialRelation("C2", 1);
+                var c3 = new PartialRelation("C3", 1);
+                var typeInfoMap = new LinkedHashMap<PartialRelation, TypeInfo>();
+                typeInfoMap.put(c1, TypeInfo.builder().supertypes(c2, c3).build());
+                typeInfoMap.put(c2, TypeInfo.builder().supertype(c3).build());
+                typeInfoMap.put(c3, TypeInfo.builder().build());
+
+                var sut = new TypeAnalyzer(typeInfoMap);
+                var tester = new TypeAnalyzerTester(sut);
+
+                assertAll(
+                                () -> tester.assertConcreteType(c1),
+                                () -> tester.assertConcreteType(c2, c1),
+                                () -> tester.assertConcreteType(c3, c2)
+                );
+        }
+
+        @Test
+        void typeEliminationAbstractToConcreteTest() {
+                var c1 = new PartialRelation("C1", 1);
+                var c2 = new PartialRelation("C2", 1);
+                var a11 = new PartialRelation("A11", 1);
+                var a12 = new PartialRelation("A12", 1);
+                var a21 = new PartialRelation("A21", 1);
+                var a22 = new PartialRelation("A22", 1);
+                var a3 = new PartialRelation("A3", 1);
+                var typeInfoMap = new LinkedHashMap<PartialRelation, TypeInfo>();
+                typeInfoMap.put(a3, TypeInfo.builder().abstractType().build());
+                typeInfoMap.put(a21, TypeInfo.builder().abstractType().supertype(a3).build());
+                typeInfoMap.put(a22, TypeInfo.builder().abstractType().supertype(a3).build());
+                typeInfoMap.put(a11, TypeInfo.builder().abstractType().supertypes(a21, a22).build());
+                typeInfoMap.put(a12, TypeInfo.builder().abstractType().supertypes(a21, a22).build());
+                typeInfoMap.put(c1, TypeInfo.builder().supertypes(a11, a12).build());
+                typeInfoMap.put(c2, TypeInfo.builder().supertype(a3).build());
+
+                var sut = new TypeAnalyzer(typeInfoMap);
+                var tester = new TypeAnalyzerTester(sut);
+
+                assertAll(
+                                () -> tester.assertConcreteType(c1),
+                                () -> tester.assertConcreteType(c2),
+                                () -> tester.assertEliminatedType(a11, c1),
+                                () -> tester.assertEliminatedType(a12, c1),
+                                () -> tester.assertEliminatedType(a21, c1),
+                                () -> tester.assertEliminatedType(a22, c1),
+                                () -> tester.assertAbstractType(a3, c1, c2)
+                );
+        }
+
+        @Test
+        void typeEliminationConcreteToAbstractTest() {
+                var c1 = new PartialRelation("C1", 1);
+                var c2 = new PartialRelation("C2", 1);
+                var a11 = new PartialRelation("A11", 1);
+                var a12 = new PartialRelation("A12", 1);
+                var a21 = new PartialRelation("A21", 1);
+                var a22 = new PartialRelation("A22", 1);
+                var a3 = new PartialRelation("A3", 1);
+                var typeInfoMap = new LinkedHashMap<PartialRelation, TypeInfo>();
+                typeInfoMap.put(c1, TypeInfo.builder().supertypes(a11, a12).build());
+                typeInfoMap.put(c2, TypeInfo.builder().supertype(a3).build());
+                typeInfoMap.put(a11, TypeInfo.builder().abstractType().supertypes(a21, a22).build());
+                typeInfoMap.put(a12, TypeInfo.builder().abstractType().supertypes(a21, a22).build());
+                typeInfoMap.put(a21, TypeInfo.builder().abstractType().supertype(a3).build());
+                typeInfoMap.put(a22, TypeInfo.builder().abstractType().supertype(a3).build());
+                typeInfoMap.put(a3, TypeInfo.builder().abstractType().build());
+
+                var sut = new TypeAnalyzer(typeInfoMap);
+                var tester = new TypeAnalyzerTester(sut);
+
+                assertAll(
+                                () -> tester.assertConcreteType(c1),
+                                () -> tester.assertConcreteType(c2),
+                                () -> tester.assertEliminatedType(a11, c1),
+                                () -> tester.assertEliminatedType(a12, c1),
+                                () -> tester.assertEliminatedType(a21, c1),
+                                () -> tester.assertEliminatedType(a22, c1),
+                                () -> tester.assertAbstractType(a3, c1, c2)
+                );
+        }
+
+        @Test
+        void preserveConcreteTypeTest() {
+                var c1 = new PartialRelation("C1", 1);
+                var a1 = new PartialRelation("A1", 1);
+                var c2 = new PartialRelation("C2", 1);
+                var a2 = new PartialRelation("A2", 1);
+                var typeInfoMap = new LinkedHashMap<PartialRelation, TypeInfo>();
+                typeInfoMap.put(c1, TypeInfo.builder().supertype(a1).build());
+                typeInfoMap.put(a1, TypeInfo.builder().abstractType().supertype(c2).build());
+                typeInfoMap.put(c2, TypeInfo.builder().supertype(a2).build());
+                typeInfoMap.put(a2, TypeInfo.builder().abstractType().build());
+
+                var sut = new TypeAnalyzer(typeInfoMap);
+                var tester = new TypeAnalyzerTester(sut);
+
+                assertAll(
+                                () -> tester.assertConcreteType(c1),
+                                () -> tester.assertEliminatedType(a1, c1),
+                                () -> tester.assertConcreteType(c2, c1),
+                                () -> tester.assertEliminatedType(a2, c2)
+                );
+        }
+
+        @Test
+        void mostGeneralCurrentTypeTest() {
+                var c1 = new PartialRelation("C1", 1);
+                var c2 = new PartialRelation("C2", 1);
+                var c3 = new PartialRelation("C3", 1);
+                var typeInfoMap = new LinkedHashMap<PartialRelation, TypeInfo>();
+                typeInfoMap.put(c1, TypeInfo.builder().supertype(c3).build());
+                typeInfoMap.put(c2, TypeInfo.builder().supertype(c3).build());
+                typeInfoMap.put(c3, TypeInfo.builder().build());
+
+                var sut = new TypeAnalyzer(typeInfoMap);
+                var tester = new TypeAnalyzerTester(sut);
+                var c3Result = tester.getPreservedType(c3);
+
+                var expected = new InferredType(Set.of(c3), Set.of(c1, c2, c3), c3);
+                assertAll(
+                                () -> assertThat(tester.getInferredType(c3), is(expected)),
+                                () -> assertThat(c3Result.merge(sut.getUnknownType(), TruthValue.TRUE), is(expected))
+                );
+        }
+
+        @Test
+        void preferFirstConcreteTypeTest() {
+                var a1 = new PartialRelation("A1", 1);
+                var c1 = new PartialRelation("C1", 1);
+                var c2 = new PartialRelation("C2", 1);
+                var c3 = new PartialRelation("C3", 1);
+                var c4 = new PartialRelation("C4", 1);
+                var typeInfoMap = new LinkedHashMap<PartialRelation, TypeInfo>();
+                typeInfoMap.put(c1, TypeInfo.builder().supertype(a1).build());
+                typeInfoMap.put(c2, TypeInfo.builder().supertype(a1).build());
+                typeInfoMap.put(c3, TypeInfo.builder().supertype(a1).build());
+                typeInfoMap.put(c4, TypeInfo.builder().supertype(c3).build());
+                typeInfoMap.put(a1, TypeInfo.builder().abstractType().build());
+
+                var sut = new TypeAnalyzer(typeInfoMap);
+                var tester = new TypeAnalyzerTester(sut);
+                var c1Result = tester.getPreservedType(c1);
+                var a1Result = tester.getPreservedType(a1);
+
+                assertThat(c1Result.merge(a1Result.asInferredType(), TruthValue.FALSE),
+                                is(new InferredType(Set.of(a1), Set.of(c2, c3, c4), c2)));
+        }
+
+        @Test
+        void preferFirstMostGeneralConcreteTypeTest() {
+                var a1 = new PartialRelation("A1", 1);
+                var c1 = new PartialRelation("C1", 1);
+                var c2 = new PartialRelation("C2", 1);
+                var c3 = new PartialRelation("C3", 1);
+                var c4 = new PartialRelation("C4", 1);
+                var typeInfoMap = new LinkedHashMap<PartialRelation, TypeInfo>();
+                typeInfoMap.put(c4, TypeInfo.builder().supertype(c3).build());
+                typeInfoMap.put(c3, TypeInfo.builder().supertype(a1).build());
+                typeInfoMap.put(c2, TypeInfo.builder().supertype(a1).build());
+                typeInfoMap.put(c1, TypeInfo.builder().supertype(a1).build());
+                typeInfoMap.put(a1, TypeInfo.builder().abstractType().build());
+
+                var sut = new TypeAnalyzer(typeInfoMap);
+                var tester = new TypeAnalyzerTester(sut);
+                var c1Result = tester.getPreservedType(c1);
+                var a1Result = tester.getPreservedType(a1);
+
+                assertThat(c1Result.merge(a1Result.asInferredType(), TruthValue.FALSE),
+                                is(new InferredType(Set.of(a1), Set.of(c2, c3, c4), c3)));
+        }
+
+        @Test
+        void circularTypeHierarchyTest() {
+                var c1 = new PartialRelation("C1", 1);
+                var c2 = new PartialRelation("C2", 1);
+                var typeInfoMap = new LinkedHashMap<PartialRelation, TypeInfo>();
+                typeInfoMap.put(c1, TypeInfo.builder().supertype(c2).build());
+                typeInfoMap.put(c2, TypeInfo.builder().supertype(c1).build());
+
+                assertThrows(IllegalArgumentException.class, () -> new TypeAnalyzer(typeInfoMap));
+        }
+}
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 @@
+package tools.refinery.store.partial.translator.typehierarchy;
+
+import tools.refinery.store.partial.representation.PartialRelation;
+
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.hamcrest.Matchers.*;
+import static org.hamcrest.Matchers.is;
+
+class TypeAnalyzerTester {
+        private final TypeAnalyzer sut;
+
+        public TypeAnalyzerTester(TypeAnalyzer sut) {
+                this.sut = sut;
+        }
+
+        public void assertAbstractType(PartialRelation partialRelation, PartialRelation... directSubtypes) {
+                assertPreservedType(partialRelation, true, false, directSubtypes);
+        }
+
+        public void assertVacuousType(PartialRelation partialRelation) {
+                assertPreservedType(partialRelation, true, true);
+        }
+
+        public void assertConcreteType(PartialRelation partialRelation, PartialRelation... directSubtypes) {
+                assertPreservedType(partialRelation, false, false, directSubtypes);
+        }
+
+        private void assertPreservedType(PartialRelation partialRelation, boolean isAbstract, boolean isVacuous,
+                                                                         PartialRelation... directSubtypes) {
+                var result = sut.getAnalysisResults().get(partialRelation);
+                assertThat(result, is(instanceOf(PreservedType.class)));
+                var preservedResult = (PreservedType) result;
+                assertThat(preservedResult.isAbstractType(), is(isAbstract));
+                assertThat(preservedResult.isVacuous(), is(isVacuous));
+                assertThat(preservedResult.getDirectSubtypes(), hasItems(directSubtypes));
+        }
+
+        public void assertEliminatedType(PartialRelation partialRelation, PartialRelation replacement) {
+                var result = sut.getAnalysisResults().get(partialRelation);
+                assertThat(result, is(instanceOf(EliminatedType.class)));
+                assertThat(((EliminatedType) result).replacement(), is(replacement));
+        }
+
+        public PreservedType getPreservedType(PartialRelation partialRelation) {
+                return (PreservedType) sut.getAnalysisResults().get(partialRelation);
+        }
+
+        public InferredType getInferredType(PartialRelation partialRelation) {
+                return getPreservedType(partialRelation).asInferredType();
+        }
+}