From 8564cba1883aa4100d0ce614f44af26adde12f41 Mon Sep 17 00:00:00 2001 From: Michael Williamson Date: Fri, 5 Jan 2024 21:11:11 +0000 Subject: Handle simple subtyping for constructed types --- .../shedlang/compiler/typechecker/TypeChecker.java | 2 +- .../compiler/typechecker/TypeCheckerSubTyping.java | 79 ++++++++++++++++++++-- .../org/shedlang/compiler/types/TypeParam.java | 8 +++ 3 files changed, 81 insertions(+), 8 deletions(-) (limited to 'src/main/java') diff --git a/src/main/java/org/shedlang/compiler/typechecker/TypeChecker.java b/src/main/java/org/shedlang/compiler/typechecker/TypeChecker.java index 1aefd526..a5877a8e 100644 --- a/src/main/java/org/shedlang/compiler/typechecker/TypeChecker.java +++ b/src/main/java/org/shedlang/compiler/typechecker/TypeChecker.java @@ -148,7 +148,7 @@ public class TypeChecker { } var typedArgsNode = new TypedArgsNode(typedPositionalArgs, typedNamedArgs, args.source()); - return context.toResult(new TypeCheckArgsValues(typedArgsNode, constraints.solve())); + return context.toResult(new TypeCheckArgsValues(typedArgsNode, constraints.solve(args.source()))); } private static TypeCheckSteps typeCheckStepsAssign( diff --git a/src/main/java/org/shedlang/compiler/typechecker/TypeCheckerSubTyping.java b/src/main/java/org/shedlang/compiler/typechecker/TypeCheckerSubTyping.java index 4f1a283e..f36626e9 100644 --- a/src/main/java/org/shedlang/compiler/typechecker/TypeCheckerSubTyping.java +++ b/src/main/java/org/shedlang/compiler/typechecker/TypeCheckerSubTyping.java @@ -11,6 +11,7 @@ import org.shedlang.compiler.util.P; import java.util.List; import java.util.Map; import java.util.Optional; +import java.util.function.Function; import java.util.stream.Collectors; public class TypeCheckerSubTyping { @@ -31,6 +32,13 @@ public class TypeCheckerSubTyping { this.upper ); } + + public TypeBounds addUpperBound(Type upperBound) { + return new TypeBounds( + this.lower, + this.upper.plus(upperBound) + ); + } } static Constraints constraints(List typeLevelParams, TypeInfos typeInfos) { @@ -44,8 +52,18 @@ public class TypeCheckerSubTyping { TypeInfos typeInfos ) { public Constraints addLowerBound(TypeParam typeParam, Type lowerBound) { - var bounds = this.typeBounds.getOrDefault(typeParam, TypeBounds.EMPTY) - .addLowerBound(lowerBound); + return updateBounds(typeParam, bounds -> bounds.addLowerBound(lowerBound)); + } + + public Constraints addUpperBound(TypeParam typeParam, Type upperBound) { + return updateBounds(typeParam, bounds -> bounds.addUpperBound(upperBound)); + } + + private Constraints updateBounds( + TypeParam typeParam, + Function update + ) { + var bounds = update.apply(this.typeBounds.getOrDefault(typeParam, TypeBounds.EMPTY)); return new Constraints( this.typeLevelParams, this.typeBounds.plus(typeParam, bounds), @@ -53,8 +71,7 @@ public class TypeCheckerSubTyping { ); } - public TypeSubstitutionMap solve() { - // TODO: handle upper bounds + public TypeSubstitutionMap solve(Source source) { // TODO: handle type params that are constrained by other type params // TODO: handle unconstrained types // TODO: do we need any special handling for mutual recursion (i.e. do we need separate type params for the parent call and the child call?) @@ -62,13 +79,23 @@ public class TypeCheckerSubTyping { var map = this.typeLevelParams.stream() .map(typeParam -> { var typeParamBounds = this.typeBounds.getOrDefault(typeParam, TypeBounds.EMPTY); - var bound = Types.BOTTOM; + var lowerBound = Types.BOTTOM; for (var lower : typeParamBounds.lower) { - bound = Types.commonSupertype(List.of(bound, lower)); + lowerBound = Types.commonSupertype(List.of(lowerBound, lower)); + } + + var upperBound = Types.TOP; + for (var upper : typeParamBounds.upper) { + upperBound = Types.commonSubtype(List.of(upperBound, upper)); } - return Map.entry(typeParam, bound); + if (!isSubType(lowerBound, upperBound, typeInfos)) { + // TODO: proper error (or return empty and let caller throw?) + throw new IllegalStateException("Incompatible type bounds"); + } + + return Map.entry(typeParam, lowerBound); }) .collect(Collectors.toMap(x -> x.getKey(), x -> x.getValue())); @@ -120,6 +147,15 @@ public class TypeCheckerSubTyping { return Optional.of(constraints); } + if ( + subtype instanceof TypeParam subtypeTypeParam && + constraints.typeLevelParams.contains(subtypeTypeParam) + ) { + constraints = constraints.addUpperBound(subtypeTypeParam, supertype); + + return Optional.of(constraints); + } + if (subtype instanceof SumType subtypeSum) { var subtypeInfo = constraints.typeInfos .sumTypeInfo(subtypeSum) @@ -143,6 +179,35 @@ public class TypeCheckerSubTyping { return tryAddVariantSubtypeConstraint(subtype, superTypeInfo, constraints); } + if ( + supertype instanceof ConstructedType supertypeConstructed && + subtype instanceof ConstructedType subtypeConstructed && + supertypeConstructed.constructor().equals(subtypeConstructed.constructor()) + ) { + var failed = false; + for (var i = 0; i < subtypeConstructed.constructor().params().size(); i++) { + var subtypeArg = subtypeConstructed.args().get(i); + var supertypeArg = supertypeConstructed.args().get(i); + + var result1 = tryAddSubtypeConstraint(subtypeArg, supertypeArg, constraints); + if (result1.isEmpty()) { + failed = true; + break; + } + constraints = result1.get(); + + var result2 = tryAddSubtypeConstraint(supertypeArg, subtypeArg, constraints); + if (result2.isEmpty()) { + failed = true; + break; + } + constraints = result2.get(); + } + if (!failed) { + return Optional.of(constraints); + } + } + if ( supertype instanceof FunctionType supertypeFunction && subtype instanceof FunctionType subtypeFunction diff --git a/src/main/java/org/shedlang/compiler/types/TypeParam.java b/src/main/java/org/shedlang/compiler/types/TypeParam.java index 4d0fd70d..c7d0c88d 100644 --- a/src/main/java/org/shedlang/compiler/types/TypeParam.java +++ b/src/main/java/org/shedlang/compiler/types/TypeParam.java @@ -1,6 +1,14 @@ package org.shedlang.compiler.types; public record TypeParam(Scope scope, String name) implements Type { + public static TypeParam forFunction( + NamespaceName namespaceName, + String functionName, + String name + ) { + return new TypeParam(new Scope.Function(namespaceName, functionName), name); + } + public static TypeParam forStructType(SimpleStructType structType, String name) { return new TypeParam(new Scope.Struct(structType), name); } -- cgit v1.2.3