build: make generated source files reproducible #21586

Problem:
Build is not reproducible, because generated source files (.c/.h/) are not
deterministic, mostly because Lua pairs() is unordered by design (for security).

https://github.com/LuaJIT/LuaJIT/issues/626#issuecomment-707005671
https://www.lua.org/manual/5.1/manual.html#pdf-next
> The order in which the indices are enumerated is not specified [...]
>
>> The hardening of the VM deliberately randomizes string hashes. This in
>> turn randomizes the iteration order of tables with string keys.

Solution:
- Update the code generation scripts to be deterministic.
    - That is only a partial solution: the exported function
      (funcs_metadata.generated.h) and ui event
      (ui_events_metadata.generated.h) metadata have some mpack'ed
      tables, which are not serialized deterministically.
    - As a workaround, introduce `PRG_GEN_LUA` cmake setting, so you can
      inject a modified build of luajit (with LUAJIT_SECURITY_PRN=0)
      that preserves table order.
    - Longer-term we should change the mpack'ed data structure so it no
      longer uses tables keyed by strings.

Closes #20124

Co-Authored-By: dundargoc <gocdundar@gmail.com>
Co-Authored-By: Arnout Engelen <arnout@bzzt.net>

1 files changed, 27 insertions, 0 deletions

diff --git a/runtime/lua/vim/shared.lua b/runtime/lua/vim/shared.lua
index 7967d13943..cc48e3f193 100644
--- a/runtime/lua/vim/shared.lua
+++ b/runtime/lua/vim/shared.lua
@@ -458,6 +458,33 @@ function vim.tbl_flatten(t)
   return result
 end
 
+--- Enumerate a table sorted by its keys.
+---
+---@see Based on https://github.com/premake/premake-core/blob/master/src/base/table.lua
+---
+---@param t table List-like table
+---@return iterator over sorted keys and their values
+function vim.spairs(t)
+  assert(type(t) == 'table', string.format('Expected table, got %s', type(t)))
+
+  -- collect the keys
+  local keys = {}
+  for k in pairs(t) do
+    table.insert(keys, k)
+  end
+  table.sort(keys)
+
+  -- Return the iterator function.
+  -- TODO(justinmk): Return "iterator function, table {t}, and nil", like pairs()?
+  local i = 0
+  return function()
+    i = i + 1
+    if keys[i] then
+      return keys[i], t[keys[i]]
+    end
+  end
+end
+
 --- Tests if a Lua table can be treated as an array.
 ---
 --- Empty table `{}` is assumed to be an array, unless it was created by