From 870aa25e96683a6686b019e40e1fe611fd36c69f Mon Sep 17 00:00:00 2001 From: Michael Williamson Date: Sun, 7 Jan 2024 17:50:25 +0000 Subject: Update commonSupertype to consider sum types --- .../compiler/typechecker/TypeCheckerSubTyping.java | 2 +- .../shedlang/compiler/typechecker/TypeInfos.java | 36 +++++++++++++++++++--- .../java/org/shedlang/compiler/types/Types.java | 12 ++++++-- src/main/java/org/shedlang/compiler/util/P.java | 5 +++ 4 files changed, 48 insertions(+), 7 deletions(-) (limited to 'src/main/java') diff --git a/src/main/java/org/shedlang/compiler/typechecker/TypeCheckerSubTyping.java b/src/main/java/org/shedlang/compiler/typechecker/TypeCheckerSubTyping.java index fd4ea432..dd12d06b 100644 --- a/src/main/java/org/shedlang/compiler/typechecker/TypeCheckerSubTyping.java +++ b/src/main/java/org/shedlang/compiler/typechecker/TypeCheckerSubTyping.java @@ -17,7 +17,7 @@ import java.util.stream.Collectors; public class TypeCheckerSubTyping { private TypeCheckerSubTyping() {} - static boolean isSubType(Type subtype, Type supertype, TypeInfos typeInfos) { + public static boolean isSubType(Type subtype, Type supertype, TypeInfos typeInfos) { var constraints = new Constraints(List.of(), P.map(), typeInfos); return tryAddSubtypeConstraint(subtype, supertype, constraints) .isPresent(); diff --git a/src/main/java/org/shedlang/compiler/typechecker/TypeInfos.java b/src/main/java/org/shedlang/compiler/typechecker/TypeInfos.java index 7812614f..ff2e0aad 100644 --- a/src/main/java/org/shedlang/compiler/typechecker/TypeInfos.java +++ b/src/main/java/org/shedlang/compiler/typechecker/TypeInfos.java @@ -1,8 +1,6 @@ package org.shedlang.compiler.typechecker; -import org.pcollections.Empty; -import org.pcollections.OrderedPMap; -import org.pcollections.PMap; +import org.pcollections.*; import org.shedlang.compiler.types.*; import org.shedlang.compiler.util.P; import org.shedlang.compiler.util.PCollectors; @@ -11,22 +9,31 @@ import java.util.Optional; import java.util.Set; public class TypeInfos { - public static final TypeInfos EMPTY = new TypeInfos(Empty.map(), P.orderedPMap(), Empty.map(), Empty.map()); + public static final TypeInfos EMPTY = new TypeInfos( + Empty.map(), + P.orderedPMap(), + Empty.map(), + Empty.map(), + Empty.map() + ); private final PMap namespaceTypeInfos; private final OrderedPMap structTypeInfos; private final PMap sumTypeInfos; + private final PMap> structSupertypes; private final PMap userDefinedEffectInfos; public TypeInfos( PMap namespaceTypeInfos, OrderedPMap structTypeInfos, PMap sumTypeInfos, + PMap> structSupertypes, PMap userDefinedEffectInfos ) { this.namespaceTypeInfos = namespaceTypeInfos; this.structTypeInfos = structTypeInfos; this.sumTypeInfos = sumTypeInfos; + this.structSupertypes = structSupertypes; this.userDefinedEffectInfos = userDefinedEffectInfos; } @@ -38,6 +45,7 @@ public class TypeInfos { this.namespaceTypeInfos.plus(namespaceName, namespaceTypeInfo), this.structTypeInfos, this.sumTypeInfos, + this.structSupertypes, this.userDefinedEffectInfos ); } @@ -54,6 +62,7 @@ public class TypeInfos { this.namespaceTypeInfos, this.structTypeInfos.plus(type, structTypeInfo), this.sumTypeInfos, + this.structSupertypes, this.userDefinedEffectInfos ); } @@ -94,10 +103,20 @@ public class TypeInfos { } public TypeInfos addSumTypeInfo(SimpleSumType sumType, SumTypeInfo sumTypeInfo) { + var structSupertypes = this.structSupertypes; + + for (var variant : sumTypeInfo.variants()) { + structSupertypes = structSupertypes.plus( + variant, + structSupertypes.getOrDefault(variant, P.orderedSet()).plus(sumType) + ); + } + return new TypeInfos( this.namespaceTypeInfos, this.structTypeInfos, this.sumTypeInfos.plus(sumType, sumTypeInfo), + structSupertypes, this.userDefinedEffectInfos ); } @@ -112,6 +131,14 @@ public class TypeInfos { }; } + public Set supertypes(Type type) { + if (type instanceof StructType structType) { + return this.structSupertypes.getOrDefault(structType, P.orderedSet()); + } else { + return P.set(); + } + } + private Optional simpleSumTypeInfo(SimpleSumType type) { return Optional.ofNullable(sumTypeInfos.get(type)); } @@ -136,6 +163,7 @@ public class TypeInfos { this.namespaceTypeInfos, this.structTypeInfos, this.sumTypeInfos, + this.structSupertypes, this.userDefinedEffectInfos.plus(effect, effectInfo) ); } diff --git a/src/main/java/org/shedlang/compiler/types/Types.java b/src/main/java/org/shedlang/compiler/types/Types.java index 474d3a26..2e5f2562 100644 --- a/src/main/java/org/shedlang/compiler/types/Types.java +++ b/src/main/java/org/shedlang/compiler/types/Types.java @@ -5,6 +5,8 @@ import org.shedlang.compiler.typechecker.TypeInfos; import java.util.List; import java.util.stream.Collectors; +import static org.shedlang.compiler.typechecker.TypeCheckerSubTyping.isSubType; + public class Types { private Types() { } @@ -87,9 +89,15 @@ public class Types { return BOTTOM; } else if (uniqueSubtypes.size() == 1) { return uniqueSubtypes.iterator().next(); - } else { - return TOP; } + + for (var supertype : typeInfos.supertypes(uniqueSubtypes.iterator().next())) { + if (uniqueSubtypes.stream().allMatch(subtype -> isSubType(subtype, supertype, typeInfos))) { + return supertype; + } + } + + return TOP; } public static Type commonSubtype(List supertypes) { diff --git a/src/main/java/org/shedlang/compiler/util/P.java b/src/main/java/org/shedlang/compiler/util/P.java index 5d40d596..deff0c9a 100644 --- a/src/main/java/org/shedlang/compiler/util/P.java +++ b/src/main/java/org/shedlang/compiler/util/P.java @@ -42,6 +42,11 @@ public class P { return OrderedPSet.from(Arrays.asList(values)); } + @SafeVarargs + public static PSet set(T... values) { + return HashTreePSet.from(Arrays.asList(values)); + } + @SafeVarargs public static PStack stack(T... values) { return ConsPStack.from(Arrays.asList(values)); -- cgit v1.2.3