It is more than a touch obscure. To be clear, this is the sort of code where if I saw it in another codebase I might not even waste my time trying to understand it. One thing I’ve learned from reading a lot of database code is that there are times when it’s easier to derive what something must be doing from first principles than to actually read the code. Reading code sucks.
In this case the salient point is that even I had no idea wtf the code was doing and I just wrote it, so it was uniquely garbage.
Anyway, I will try to explain it just for fun. That code builds the index blocks for an LSM table. Each table in an LSM is a two-level structure (like a degenerate, immutable btree) where the first level holds sorted pairs and the second level holds an index entry for every, say, 64 KiB of data. The key pairs are divided into subtables every 64 KiB (these are traditionally called “blocks” rather than “subtables” but in my case the term was overloaded) and each subtable gets an index entry.
The entries are accumulated such that they end up in a structure of [{block_i, [{key, pointer}]}]. The block_i here really is a block and is not a subtable but this is not worth explaining further. The point is, it’s a nested list. And we need a nested loop.
“Idiomatic” is a funny thing because I think the most idiomatic way to solve this would be to flatten the whole thing into one list. The problem is that, as @Schultzer will tell you, this will cause a huge number of completely wasted allocations. So we want to traverse the nested structure.
My first attempt at this was absolutely disgusting. There was, like, a function head that noticed when one level of the loop was finished and popped it out. Just really confusing to look at.
Informed by versions of this code I had to write elsewhere, I realized that this was much more readable (and indeed likely faster) when implemented as two sets of recursive functions, i.e. as the functional analog of a nested loop. In hindsight this is obvious. But that’s the funny thing about hindsight.
BTW, I am making no claims that this code is now “good” and I’m sure I’ll end up rewriting it again. I think it may not be garbage anymore, though.
I also gave the variables better names. The important takeaway if anything is that stuff like that really matters and is not bikeshedding. I was having trouble reverse-engineering my own code because the variable names were not clear enough. I even wrote a bug while refactoring because of this (and the tests quickly caught it). The minutiae really do make a big difference when it comes to not writing bugs.
WRT the fuzzers, they helped because they are tests. Any test suite would help, it’s just that fuzzers are the only viable path to test code like this. You have to generate too much data just to get the thing to work at all, let alone the edge cases. The LSM fuzzers are still very immature, but even the most basic fuzzer runs circles around unit tests.
I’m sure this code is still loaded with bugs as I haven’t fuzzed it very aggressively yet. It’s solidifying.
