How to create a deeply nested data model that supports deep copying?

Support
1

I’m porting a 2D graphics engine from Swift to Kotlin. Large parts of the data model are nested structs in Swift. As a simple example:

struct Point {
  var x: Float
  var y: Float
}

struct Size {
  var width: Float
  var height: Float
}

struct Rect {
  var origin: Point
  var size: Size
}

Many model structures are deeply nested, with way more levels than here. Also, as we use structs instead of classes for most types, which are value typed in Swift, we can easily use pure functions for 2D operations, like in this small, contrived example:

func translate(rect1: Rect, dx: Float) -> Rect {
  var rect2 = rect1 // Creates a mutable deep copy
  rect2.origin.x += dx
  return rect2
}

This approach gives us a high performance, no memory handling issues (everything lives on the stack), and great testability. As the structs are value typed, we cannot accidentally create shallow copies and modify the wrong objects.

What’s the idiomatic way to create such a model in Kotlin?

It looks like Kotlin’s data classes are a solution, but I don’t know how copying deeply nested data classes is usually done. Do you create custom deepCopy() methods everywhere?

Should I be worried about the performance if the call of a copy()/deepCopy() method triggers a torrent of other copy()/deepCopy() calls down the model? (From a C programmer’s perspective, I see thousands of small, short lived allocations on the heap)

2

AFAIK there is no idiomatic way for deep copy in Kotlin. Data classes do offer a compiler generated deep copy method but it will not iterate trough all nested data classes, just the first layer.

I believe deep copying requires the entire compilation stack to be aware of the operation and since Kotlin targets the JDK and JS engines that do not support that feature the Kotlin team just decided not to implement it “externally” (aside from the first copy layer of data classes).

Still, if there is a way Iàd like to know as well!

3

Maybe arrow-optics can help?

https://arrow-kt.io/docs/0.10/optics/dsl/

1 Like
4

Thanks for the suggestion. I haven’t used any Optics framework so far, so it’s a bit difficult to understand what Arrow actually does. Do you know how it works, and what happens on a conceptual level? Does it generate the boilerplate to recursively create deep copies?

1 Like
5

tbh, I’m at the same level.
I know it exists, but I would love to see a koans which teaches arrow-kt.

6

It might be possible to create something using kotlinx.serialization. All the machinery is there for accessing fields and creating objects without reflection.

The naïve approach would be serializing then deserializing, but I bet it’s possible to copy without that.

1 Like
7

It shouldn’t be to hard to solve this using kapt, either. That way you could generate the proper deepCopy methods as extension functions. This won’t work for private or protected properties, but should be quite simple for data classes.

1 Like
8

Instead of deep copying, have you considered shallow copying with everything as an immutable (val) type? We have an app with a rendering engine that’s ported to both iOS and Android, so we have both Swift and Kotlin versions. For Swift, we use value type semantics. For Kotlin, we made everything immutable, and have been quite happy with the results.

The drawback is if you want to change something in a deeply nested class, you end up with some long copy chains. For example…

a = a.copy( b=a.b.copy( c=a.b.c.copy( d=newValue )))

To solve this problem, we created a lens library for Kotlin (which I’m unfortunately not able to share at the moment, but it wasn’t terribly difficult, and I think there are now some open source lens libraries for Kotlin). We overloaded the range operator (because it looks kind of like the member operator) and use it to reference deeply into an immutable structure.

For example…

val lens = A::b .. B::c .. C::d
a = a.copySetting( lens, newValue )
println( "updated value: ${a.get(lens)}" )

Working like this with everything immutable takes some getting used to, but depending on your use case, there can be some really big benefits to it. For example, we use it to support our near-infinite undo…

fun DocumentHolder.edit( action: (Document)->Document ) {
    undoStack.add( document )
    document = action(document)
}

// When user edits something...
holder.edit { it.copyWith(lens, newValue) }

This means that the undoStack is a list of all previous document states, but because each was an immutable copy only changing the chain of object instances between the root and the revision, nearly all of the data is shared with other revisions on the undo stack, so we get an extremely high performance, lightweight near-infinite (as far as the user is concerned) undo history with a small memory footprint.

This may not fit your use case, but we’ve found for many situations, where we would use a value type in swift, a good solution in Kotlin has often been to use immutable data classes with a lens library for making copies with a modification.

I think Arrow includes lens support, which may be worth looking into (at the time we rolled our own, that wasn’t an option). If you’ve ever used key paths in Swift, lenses in functional programming are basically the same thing. A little hard to wrap your brain around at first, but incredibly useful if you get the hang of them.

3 Likes
9

You pretty much summed up functional programming as well as the arrow library :wink:

3 Likes