lib.hash shortcomings (edge-cases)

[tmillr]

Note

This is a low-priority issue as these are edge-cases. I just want to report this here so that this is known (and before I forget).

1. lib.hash does not sort table keys, which can lead to false cache-misses. The reason for this is that (to the best of my current knowledge) table key iteration order is not well-defined (or, in other words, is unspecified) in Lua. The effect is that two different tables (instances) with the same exact content can produce different hashes:

-- Here's just one example
local hash = require 'github-theme.lib.hash'
local function same() return { a = 1, b = 2, c = 3 } end
assert(hash({ a = 1, b = 2, c = 3 }) == hash(same())) -- fails!

local t = { b = 2 }
t.a = 1
rawset(t, 'c', 3)
assert(hash(same()) == hash(t))
assert(hash({ a = 1, b = 2, c = 3 }) == hash(t))

Edit: never-mind, the example above seems to be working for me now?

---

2. lib.hash is not prefix-free, and suffers from prefix collisions (although in practice, given the expected content that we are hashing, these collisions are probably very unlikely). This can result in false cache-hits:

local hash = require 'github-theme.lib.hash'
assert(hash({ a = 'bc' }) ~= hash({ ab = 'c' })) -- fails!