A quick story about discovering where Lua’s table abstraction fails to work.
In Lua, arrays should always be initialized sequentially, and should never have a
nilinserted.
(The code behind this adventure starts on line 128 in one commit, where a crazy work-around was used to get what I wanted. This was eventually fixed in commit 8b8f36b (though accidentally sorting the wrong direction at that point). I provide these links to remind myself what happened, and so that if someone more knowledgeable than me wants to figure this out, hopefully they can. I’ve also made sure those links have been archived by the Internet Archive so they remain available even if the project is gone.)
While working on a prototype, I needed to sort a list of integers so that I could count the sum of the top thousand items in an array of ~40 thousand items. This list had empty indexes (or holes) within it, so I wrote a for loop to fill them with zeros and then called table.sort. It errored from trying to compare with a nil. This was confusing because I had a well-defined length that was used to fill holes, and the way Lua works, any hole in the list should be the end of what Lua recognizes as a list. As far as I knew, standard functions don’t allow holes in lists by ending at the first hole encountered.
for i = 0, list_length do
if not list[i] then
list[i] = 0
end
endI was further confused when I added debug code to check the list for nil values by iterating over it and printing every value in it: No nil values existed. The strangest part was when I passed my own sorting function to table.sort specifically to handle nil values and it created the same error. I worked around this by brute-forcing it with an incredibly inefficient thousand traversals of the entire list, removing items as I found the maximum each time. It’s a prototype, so whatever.
It didn’t sit right with me, especially because I couldn’t figure out how this was occurring. It’s incredibly rare to find an actual bug in highly used production software like programming languages, so I doubted I’d found an actual problem. Later, I realized I had added a zeroth element to this list, and Lua starts counting at 1, unlike a lot of programming languages. Removing this changed nothing, so I double-checked my assumptions and found that now nil values were showing up – and this is after no code changes except adding a for loop to print values.
I wrote a new sorting function that checks more thoroughly for nil values (I think the previous attempts at that failed because I’d made some simple error in how I was thinking about it). It worked. But then I found the loop whose code I’ve shared above, where holes are filled with zeroes. It had been a while, so I was very surprised to find what should have fixed things right there doing nothing.. somehow. I mentioned this in a group chat, and someone suggested replacing list_length with #list (the # operator returns length). The problem is that Lua stops counting at the first nil, so that should do nothing.
There’s also the possibility of an off-by-one error, those are very common, but I had assumed this would happen at some point and made sure all of my functions and loops checked one element earlier than necessary and one element later, so that if I checked too much – just extra zeroes, but I couldn’t check too little.
I wasn’t satisfied by all the nil values being there after a loop that replaces them with zero, so I tried making a loop at the top of the code that prefills a much longer list than I actually needed with zeroes. Suddenly, I didn’t need a custom sorting function. So why does filling the list with zeroes work in one place, but not another?
How Objects Work in Lua
In Lua all objects are called tables, and can contain an array-like section and arbitrary key-value pairs in a hashmap. It doesn’t really distinguish between these except as an optimization, under the hood it tries to guess how you intend to use the object and assigns values internally differently depending on what index you’re using. I thought that in practice, this means integer indexes are handled like arrays, and non-integer indexes are in the hashmap. I thought that maybe because my code was selecting integer indexes in a completely random order, it treated these as a hashmap instead, somehow leading to ignoring attempting to fill the holes – because there weren’t any holes, or the holes persisted because only part of the indexes were treated as an array.
Lua’s tables are an abstraction meant to make writing code easier, and for my years of working with them, they do that quite well, but maybe this is where the abstraction leaks? (All abstractions leak: They have some condition(s) where you end up needing to know how they work underneath, even though the point of abstraction is to not need to know how it works underneath.) Perhaps arrays are only recognized when they’re initialized sequentially, whereas my code initialized them in a random order? Either way, the error I started with manifests as “An array of integers can’t be sorted because part of it is undefined – even though every element is defined when iterated over.” which is not supposed to be possible.
There’s also the detail that in Lua there is not supposed to be difference between something having a nil value and it not existing at all. There is a difference, but it should be impossible to tell the difference or for the difference to matter in your code. It is possible that this alone is why I had this problem. Changing a value to nil inside an array table can cause all values within it to be converted to a hashmap, or some of them, or none of them. Again, this shouldn’t matter (other than a difference in speed which is usually unnoticeable), but it might matter.
I wrote a minimum test case to see if my hunch was correct, but it works when I expect it not to. I’m lost. I have an explanation that informs how I should code so that it works – and it does work, but because that explanation fails when tested, it seems incorrect. I want to know what’s really going on, but it requires a depth of understanding that I lack, and effort that I do not have the time and energy to go into.
I also learned that Lua defines this kind of behavior as “strange and unpredictable behavior” instead of undefined behavior, because undefined behavior means that an entire program can fail to function correctly do to one element with undefined behavior (even when that element is not accessed), whereas in Lua, a table exhibiting strange and unpredictable behavior doesn’t affect the rest of the program. So, if you can work around it, it’s okay.
At this point, I’m happy enough telling myself that arrays should always be initialized sequentially, and shouldn’t have nil elements ever. If I follow that, I probably won’t run into this. But.. if you’re reading this and understand what’s really going on here, please tell me.