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

[nreid260]

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]

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]

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]

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