Swarm Testing Data Structures

8 Likes

This mostly about testing, rather than Zig per-se (although comptime is pretty instrumental), but I do think that this is an important testing pattern which deserves to be better known!

2 Likes

Along with property-based testing, are you guys also looking into metamorphic testing? I know cockroachdb had success with that in their database.

1 Like

Very cool, exhaustive testing primitives are game-changing. Maybe there’s a place for them in the std as well.

Also, I’ll remember to use std.testing.random_seed next time I need randomness in tests.

Thanks for the write-up!

1 Like

TBH, I never “got” metamorphic testing. Is there really anything more to it than testing “commutativity diagram” of two paths through the code base? Which I’d personally call property-testing 101 :stuck_out_tongue:

We generally don’t need that because, due to strict serializability and relative simplicity of our domain model, we actually always know the precise answer that our database should return. We do have a full model of our database here:

That being said, yeah, we do use metamorphic testing in the small. E.g, to test that our PRNG implements biased coin correctly, we use two coins, one with P(heads) = p and another with P(heads) = 1-p:

Although now that I think about this, we might still want to do this to double-check our model…

Thanks for raising this!

1 Like

My understanding of it when attempting to implement the idea, is that you have a set of inputs, then a bunch of transformations, along with a set of invariants/relations that must hold while running through all combination of the transformations. I.e it’s another test methodology where you don’t need an oracle.

Here’s one example

That said, I find it rather hard to come up with these relations in practice :sweat_smile:

Yeah, I wouldn’t call it “testing methodology”, just one of the properties in property based testing:

1 Like

I guess that’s fair, the original paper invoked “methodology” only as a goal :slight_smile: