Generic diff for complex hierarchical data structure

Question

I have a complex data structure consisting of case classes, maps and sets. I would like to know if there is a generic mechanism to calculate a "diff" between two structures.

As a simple example:

val s0 = Set(1,2,3)
val s1 = Set(2,3,4)
val diff = diff(s0, s1)
// this should contain the information that 1 has been removed and 4 has
// been added
assert(s1 == diff.patch(s0))

A somewhat more complex example:

case class User(name: String, roles: Set[String])
val user0 = User("Hans", Set("Developer", "Admin")
val user1 = User("Hans", Set("Admin", "Manager")
val diff = diff(user0, user1)
// this should contain the information that "Developer" has been removed
// and "Manager" has been added to the roles field

Note that I am interested in a generic solution that works for arbitrary case classes and deep hierarchies. I have a feeling that this should be possible using a typeclass-based approach and either shapeless or some boilerplate. Bonus points for an approach that allows specifying the "diff algorithm" for new collection types.

I have found https://github.com/stacycurl/delta . This seems to be pretty close to what I am looking for. But I don't really understand it.

Answer 1

There is a macro-based library s_mach.datadiff. I haven't used it, but the front-page example is generating a diff from an arbitrary case class.