search

square / kotlinpoet

A Kotlin API for generating .kt source files.
https://square.github.io/kotlinpoet/
Apache License 2.0
3.9k stars 288 forks source link

TypeName subclasses can cause StackOverflowError in hashCode/equals in cyclic types #1737

Open nreid260 opened 11 months ago

nreid260 commented 11 months ago

Describe the bug When calling hashCode/equals on a TypeName with a cyclic definition, there can be a StackOverflowError

To Reproduce I'm not 100% what type is causing the issue. However, reading the implementations of these functions, it's clear that they call into on another, with no guards for the cyclic case.

Expected behavior These functions should not throw.

Additional context hashCode is relatively easy to fix by ignoring potentially cyclic fields. However, equals is trickier.

Having solved a very similar problem in the JSCompiler typesystem, the solution was to implement equals as a visitor that traversed over the type-graph, accumulating state to detect cycles.

Here are the top few loops in the stacktrace for equals:

Exception in thread "main" java.lang.StackOverflowError
        at java.base/java.util.Collections$UnmodifiableCollection$1.<init>(Collections.java:1074)
        at java.base/java.util.Collections$UnmodifiableCollection.iterator(Collections.java:1074)
        at java.base/java.util.ArrayList.equalsRange(ArrayList.java:623)
        at java.base/java.util.ArrayList.equals(ArrayList.java:612)
        at java.base/java.util.Collections$UnmodifiableList.equals(Collections.java:1498)
        at kotlin.jvm.internal.Intrinsics.areEqual(Intrinsics.java:169)
        at com.squareup.kotlinpoet.TypeName.equals(TypeName.kt:103)
        at com.squareup.kotlinpoet.WildcardTypeName.equals(WildcardTypeName.kt:58)
        at java.base/java.util.Objects.equals(Objects.java:64)
        at java.base/java.util.ArrayList.equalsRange(ArrayList.java:625)
        at java.base/java.util.ArrayList.equals(ArrayList.java:612)
        at java.base/java.util.Collections$UnmodifiableList.equals(Collections.java:1498)
        at kotlin.jvm.internal.Intrinsics.areEqual(Intrinsics.java:169)
        at com.squareup.kotlinpoet.ParameterizedTypeName.equals(ParameterizedTypeName.kt:115)
        at java.base/java.util.Objects.equals(Objects.java:64)
        at java.base/java.util.ArrayList.equalsRange(ArrayList.java:625)
        at java.base/java.util.ArrayList.equals(ArrayList.java:612)
        at java.base/java.util.Collections$UnmodifiableList.equals(Collections.java:1498)
        at kotlin.jvm.internal.Intrinsics.areEqual(Intrinsics.java:169)
        at com.squareup.kotlinpoet.TypeVariableName.equals(TypeVariableName.kt:82)
        at java.base/java.util.Objects.equals(Objects.java:64)
        at java.base/java.util.ArrayList.equalsRange(ArrayList.java:625)
        at java.base/java.util.ArrayList.equals(ArrayList.java:612)
        at java.base/java.util.Collections$UnmodifiableList.equals(Collections.java:1498)
        at kotlin.jvm.internal.Intrinsics.areEqual(Intrinsics.java:169)
        at com.squareup.kotlinpoet.WildcardTypeName.equals(WildcardTypeName.kt:63)
        at java.base/java.util.Objects.equals(Objects.java:64)
        at java.base/java.util.ArrayList.equalsRange(ArrayList.java:625)
        at java.base/java.util.ArrayList.equals(ArrayList.java:612)
        at java.base/java.util.Collections$UnmodifiableList.equals(Collections.java:1498)
        at kotlin.jvm.internal.Intrinsics.areEqual(Intrinsics.java:169)
        at com.squareup.kotlinpoet.ParameterizedTypeName.equals(ParameterizedTypeName.kt:115)
        at java.base/java.util.Objects.equals(Objects.java:64)
        at java.base/java.util.ArrayList.equalsRange(ArrayList.java:625)
        at java.base/java.util.ArrayList.equals(ArrayList.java:612)
        at java.base/java.util.Collections$UnmodifiableList.equals(Collections.java:1498)
        at kotlin.jvm.internal.Intrinsics.areEqual(Intrinsics.java:169)
        at com.squareup.kotlinpoet.TypeVariableName.equals(TypeVariableName.kt:82)
        at java.base/java.util.Objects.equals(Objects.java:64)
        at java.base/java.util.ArrayList.equalsRange(ArrayList.java:625)
        at java.base/java.util.ArrayList.equals(ArrayList.java:612)
        at java.base/java.util.Collections$UnmodifiableList.equals(Collections.java:1498)
        at kotlin.jvm.internal.Intrinsics.areEqual(Intrinsics.java:169)
        at com.squareup.kotlinpoet.WildcardTypeName.equals(WildcardTypeName.kt:63)
        at java.base/java.util.Objects.equals(Objects.java:64)
        at java.base/java.util.ArrayList.equalsRange(ArrayList.java:625)
        at java.base/java.util.ArrayList.equals(ArrayList.java:612)
        at java.base/java.util.Collections$UnmodifiableList.equals(Collections.java:1498)
        at kotlin.jvm.internal.Intrinsics.areEqual(Intrinsics.java:169)
        at com.squareup.kotlinpoet.ParameterizedTypeName.equals(ParameterizedTypeName.kt:115)
nreid260 commented 11 months ago

As another idea for a potential fix, it seem incorrect that TypeVariableName needs to hold reference to TypeNames for its bounds; the bounds are not part of the name. Eliminating these references would eliminate most (all?) possible cycles.

I see that the bounds are being used when the name is part of a class declarations, but conceptually, the declaration is using more than the classname. It is also the declaration of the type variables. Presumably there could/should be a different API for this purpose. That is, TypeNames would only be used for references to types declared elsewhere.

JakeWharton commented 11 months ago

Thanks for the report. Did you want to try and send a PR with a fix? If not, someone will get to it when we have free time.

nreid260 commented 11 months ago

I have hacked around this locally by adding a depth counter to equals. It's not exactly a problem I'm looking to revisit 😁