Circular reference in Kotlin data class could generate stack overflow error

user_12904585 0
Viewed 492

I have a question regarding data classes in Kotlin.
Say we have two classes with a circular reference:

data class Foo(
    var bar: Bar? = null
)

data class Bar (
    var foo: Foo? = null
)

and the main function:

fun main() {
    val f = Foo()
    val b = Bar()
    f.bar = b
    b.foo = f
    f.hashCode()
    b.hashCode()
    //println(f)
    //println(b)
}

the code that Kotlin auto generates will make the main function go in stack overflow. You can try this in Kotlin Playground.
Is this an expected behaviour? Note that this is a basic example, but this will happen in real life situation where, for example, instead of a reference of Foo in Bar we can have a List, a Set or a generic collection of Foo.
Shouldn't Kotlin generate some sort of compiler error or this happens even in other languages?
same thing but in Java

kotlin
2 Answers

This might be considered a bug. Here is a correspondence with a Kotlin developer, discussing something that may be another bug, but the important bit is:

By default, no specific equals and hashCode are generated (thus, they check object identity).

For data classes, hashCode and equals are based on property values. I’ll write algorithm steps in words instead of pseudocode:

hashCode:

  1. Calculate hashCode for each property declared as constructor parameter in current class
  2. Return h1 × 31n−1 + h2 × 31n−2 + … + hn

This is then the expected behavior, and obviously breaks on your example with step 1. In your "real" world example using the Array.hashCode might be the solution, but it seems like in this contrived one (though I have seen constructs such as these, that's why forward declarations exist in C/++...). I would file it at https://youtrack.jetbrains.com/issues. They may just tell you to set the hashCode to the default one for regular classes using object ID.

poipoi found this was in fact reported years ago, which I missed at: https://youtrack.jetbrains.com/issue/KT-16244

so data classes with circular references must provide their own toString and hashCode. Too bad this is not documented behavior.

user_68812400

Yes, this will smash the stack; and no, I'm not aware of any language compilers which protect against this.

In the general case, I don't think problematic circular references could be spotted by a compiler, without also picking up perfectly valid circular references.  (For example, any doubly-linked list structure contains circular references; but because none of the usual things you'd want to do would follow them in a circle, it's extremely unlikely to be a problem.)

It's only a problem here because these are data classes, which in some sense ‘contains’ their members, at least as far as some of the autogenerated methods go.

In the Java standard library, some of the collection classes explicitly give undefined behaviour if a collection contains itself, either directly or indirectly.  For example, the Collection.addAll() function:

The behavior of this operation is undefined if the specified collection is modified while the operation is in progress. (This implies that the behavior of this call is undefined if the specified collection is this collection, and this collection is nonempty.)

While an implementation could check for that and thrown an exception, doing so in a way which works for arbitrary levels of nesting would probably have a very significant impact on performance, so it's not required by all implementations — and I don't know any that do.

Even for the specific case of data classes in Kotlin, there's no obvious way — especially if you allow the two classes to be compiled at different times.  You could disallow data class members which were themselves data classes — but that wouldn't stop members being non-data classes which themselves contained data classes (and had hand-written methods delegating to them).  (And it would prevent a lot of non-circular references too.)

user_101342090
Related