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>

14 files changed, 161 insertions, 76 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index cadab62ce6..c83a8dd617 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -242,6 +242,17 @@ endif()
 
 message(STATUS "Using Lua interpreter: ${LUA_PRG}")
 
+# Some of the code generation still relies on stable table ordering in order to
+# produce reproducible output - specifically the msgpack'ed data in
+# funcs_metadata.generated.h and ui_events_metadata.generated.h. This should
+# ideally be fixed in the generators, but until then as a workaround you may provide
+# a specific lua implementation that provides the needed stability by setting LUA_GEN_PRG:
+if(NOT LUA_GEN_PRG)
+  set(LUA_GEN_PRG "${LUA_PRG}" CACHE FILEPATH "Path to the lua used for code generation.")
+endif()
+
+message(STATUS "Using Lua interpreter for code generation: ${LUA_GEN_PRG}")
+
 option(COMPILE_LUA "Pre-compile Lua sources into bytecode (for sources that are included in the binary)" ON)
 
 if(COMPILE_LUA AND NOT WIN32)
diff --git a/runtime/doc/lua.txt b/runtime/doc/lua.txt
index 49b5c9da70..f325c58efb 100644
--- a/runtime/doc/lua.txt
+++ b/runtime/doc/lua.txt
@@ -1694,6 +1694,18 @@ pesc({s})                                                         *vim.pesc()*
     See also: ~
         https://github.com/rxi/lume
 
+spairs({t})                                                     *vim.spairs()*
+    Enumerate a table sorted by its keys.
+
+    Parameters: ~
+      • {t}  (table) List-like table
+
+    Return: ~
+        iterator over sorted keys and their values
+
+    See also: ~
+        Based on https://github.com/premake/premake-core/blob/master/src/base/table.lua
+
 split({s}, {sep}, {kwargs})                                      *vim.split()*
     Splits a string at each instance of a separator.
 
diff --git a/runtime/doc/news.txt b/runtime/doc/news.txt
index 8a9736e1c2..83272a0d87 100644
--- a/runtime/doc/news.txt
+++ b/runtime/doc/news.txt
@@ -143,6 +143,10 @@ The following new APIs or features were added.
   instance in the background and display its UI on demand, which previously
   only was possible using an external UI implementation.
 
+• Several improvements were made to make the code generation scripts more
+  deterministic, and a `LUA_GEN_PRG` build parameter has been introduced to
+  allow for a workaround for some remaining reproducibility problems.
+
 ==============================================================================
 CHANGED FEATURES                                                 *news-changes*
 
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
diff --git a/scripts/genvimvim.lua b/scripts/genvimvim.lua
index 868084a583..3e9e7077be 100644
--- a/scripts/genvimvim.lua
+++ b/scripts/genvimvim.lua
@@ -11,6 +11,8 @@ local funcs_file = arg[3]
 
 package.path = nvimsrcdir .. '/?.lua;' .. package.path
 
+_G.vim = loadfile(nvimsrcdir..'/../../runtime/lua/vim/shared.lua')()
+
 local lld = {}
 local syn_fd = io.open(syntax_file, 'w')
 lld.line_length = 0
@@ -115,7 +117,7 @@ end
 local nvimau_start = 'syn keyword nvimAutoEvent contained '
 w('\n\n' .. nvimau_start)
 
-for au, _ in pairs(auevents.nvim_specific) do
+for au, _ in vim.spairs(auevents.nvim_specific) do
   if lld.line_length > 850 then
     w('\n' .. nvimau_start)
   end
@@ -126,7 +128,7 @@ w('\n\nsyn case match')
 local vimfun_start = 'syn keyword vimFuncName contained '
 w('\n\n' .. vimfun_start)
 local funcs = mpack.unpack(io.open(funcs_file, 'rb'):read("*all"))
-for name, _ in pairs(funcs) do
+for _, name in ipairs(funcs) do
   if name then
     if lld.line_length > 850 then
       w('\n' .. vimfun_start)
diff --git a/src/nvim/CMakeLists.txt b/src/nvim/CMakeLists.txt
index 62e4db4a5c..725d7987e7 100755
--- a/src/nvim/CMakeLists.txt
+++ b/src/nvim/CMakeLists.txt
@@ -570,11 +570,11 @@ add_custom_command(OUTPUT ${GENERATED_UNICODE_TABLES}
 add_custom_command(
   OUTPUT ${GENERATED_API_DISPATCH} ${GENERATED_FUNCS_METADATA}
          ${API_METADATA} ${LUA_API_C_BINDINGS}
-  COMMAND ${LUA_PRG} ${API_DISPATCH_GENERATOR} ${CMAKE_CURRENT_LIST_DIR}
-                     ${GENERATED_API_DISPATCH}
-                     ${GENERATED_FUNCS_METADATA} ${API_METADATA}
-                     ${LUA_API_C_BINDINGS}
-                     ${API_HEADERS}
+  COMMAND ${LUA_GEN_PRG} ${API_DISPATCH_GENERATOR} ${CMAKE_CURRENT_LIST_DIR}
+                         ${GENERATED_API_DISPATCH}
+                         ${GENERATED_FUNCS_METADATA} ${API_METADATA}
+                         ${LUA_API_C_BINDINGS}
+                         ${API_HEADERS}
   DEPENDS
     ${API_HEADERS}
     ${MSGPACK_RPC_HEADERS}
@@ -619,12 +619,12 @@ add_custom_command(
          ${GENERATED_UI_EVENTS_REMOTE}
          ${GENERATED_UI_EVENTS_METADATA}
          ${GENERATED_UI_EVENTS_CLIENT}
-  COMMAND ${LUA_PRG} ${API_UI_EVENTS_GENERATOR} ${CMAKE_CURRENT_LIST_DIR}
-                     ${CMAKE_CURRENT_LIST_DIR}/api/ui_events.in.h
-                     ${GENERATED_UI_EVENTS_CALL}
-                     ${GENERATED_UI_EVENTS_REMOTE}
-                     ${GENERATED_UI_EVENTS_METADATA}
-                     ${GENERATED_UI_EVENTS_CLIENT}
+  COMMAND ${LUA_GEN_PRG} ${API_UI_EVENTS_GENERATOR} ${CMAKE_CURRENT_LIST_DIR}
+                         ${CMAKE_CURRENT_LIST_DIR}/api/ui_events.in.h
+                         ${GENERATED_UI_EVENTS_CALL}
+                         ${GENERATED_UI_EVENTS_REMOTE}
+                         ${GENERATED_UI_EVENTS_METADATA}
+                         ${GENERATED_UI_EVENTS_CLIENT}
   DEPENDS
     ${API_UI_EVENTS_GENERATOR}
     ${GENERATOR_C_GRAMMAR}
diff --git a/src/nvim/api/keysets.lua b/src/nvim/api/keysets.lua
index 8f909e937f..bd709b7b25 100644
--- a/src/nvim/api/keysets.lua
+++ b/src/nvim/api/keysets.lua
@@ -1,8 +1,8 @@
 return {
-  context = {
+  { 'context', {
     "types";
-  };
-  set_decoration_provider = {
+  }};
+  { 'set_decoration_provider', {
     "on_start";
     "on_buf";
     "on_win";
@@ -10,8 +10,8 @@ return {
     "on_end";
     "_on_hl_def";
     "_on_spell_nav";
-  };
-  set_extmark = {
+  }};
+  { 'set_extmark', {
     "id";
     "end_line";
     "end_row";
@@ -39,8 +39,8 @@ return {
     "conceal";
     "spell";
     "ui_watched";
-  };
-  keymap = {
+  }};
+  { 'keymap', {
     "noremap";
     "nowait";
     "silent";
@@ -50,11 +50,11 @@ return {
     "callback";
     "desc";
     "replace_keycodes";
-  };
-  get_commands = {
+  }};
+  { 'get_commands', {
     "builtin";
-  };
-  user_command = {
+  }};
+  { 'user_command', {
     "addr";
     "bang";
     "bar";
@@ -67,8 +67,8 @@ return {
     "preview";
     "range";
     "register";
-  };
-  float_config = {
+  }};
+  { 'float_config', {
     "row";
     "col";
     "width";
@@ -85,25 +85,25 @@ return {
     "title_pos";
     "style";
     "noautocmd";
-  };
-  runtime = {
+  }};
+  { 'runtime', {
     "is_lua";
     "do_source";
-  };
-  eval_statusline = {
+  }};
+  { 'eval_statusline', {
     "winid";
     "maxwidth";
     "fillchar";
     "highlights";
     "use_winbar";
     "use_tabline";
-  };
-  option = {
+  }};
+  { 'option', {
     "scope";
     "win";
     "buf";
-  };
-  highlight = {
+  }};
+  { 'highlight', {
     "bold";
     "standout";
     "strikethrough";
@@ -128,8 +128,8 @@ return {
     "blend";
     "fg_indexed";
     "bg_indexed";
-  };
-  highlight_cterm = {
+  }};
+  { 'highlight_cterm', {
     "bold";
     "standout";
     "strikethrough";
@@ -141,15 +141,15 @@ return {
     "italic";
     "reverse";
     "nocombine";
-  };
+  }};
   -- Autocmds
-  clear_autocmds = {
+  { 'clear_autocmds', {
     "buffer";
     "event";
     "group";
     "pattern";
-  };
-  create_autocmd = {
+  }};
+  { 'create_autocmd', {
     "buffer";
     "callback";
     "command";
@@ -158,24 +158,24 @@ return {
     "nested";
     "once";
     "pattern";
-  };
-  exec_autocmds = {
+  }};
+  { 'exec_autocmds', {
     "buffer";
     "group";
     "modeline";
     "pattern";
     "data";
-  };
-  get_autocmds = {
+  }};
+  { 'get_autocmds', {
     "event";
     "group";
     "pattern";
     "buffer";
-  };
-  create_augroup = {
+  }};
+  { 'create_augroup', {
     "clear";
-  };
-  cmd = {
+  }};
+  { 'cmd', {
     "cmd";
     "range";
     "count";
@@ -187,12 +187,12 @@ return {
     "nargs";
     "addr";
     "nextcmd";
-  };
-  cmd_magic = {
+  }};
+  { 'cmd_magic', {
     "file";
     "bar";
-  };
-  cmd_mods = {
+  }};
+  { 'cmd_mods', {
     "silent";
     "emsg_silent";
     "unsilent";
@@ -213,16 +213,15 @@ return {
     "verbose";
     "vertical";
     "split";
-  };
-  cmd_mods_filter = {
+  }};
+  { 'cmd_mods_filter', {
     "pattern";
     "force";
-  };
-  cmd_opts = {
+  }};
+  { 'cmd_opts', {
     "output";
-  };
-  echo_opts = {
+  }};
+  { 'echo_opts', {
     "verbose";
-  };
+  }};
 }
-
diff --git a/src/nvim/auevents.lua b/src/nvim/auevents.lua
index 2c0cb771c3..a75ee3bbd5 100644
--- a/src/nvim/auevents.lua
+++ b/src/nvim/auevents.lua
@@ -127,10 +127,22 @@ return {
     'WinScrolled',            -- after a window was scrolled or resized
   },
   aliases = {
-    BufCreate = 'BufAdd',
-    BufRead = 'BufReadPost',
-    BufWrite = 'BufWritePre',
-    FileEncoding = 'EncodingChanged',
+    {
+      'BufCreate',
+      'BufAdd'
+    },
+    {
+      'BufRead',
+      'BufReadPost'
+    },
+    {
+      'BufWrite',
+      'BufWritePre'
+    },
+    {
+      'FileEncoding',
+      'EncodingChanged'
+    },
   },
   -- List of nvim-specific events or aliases for the purpose of generating
   -- syntax file
diff --git a/src/nvim/generators/gen_api_dispatch.lua b/src/nvim/generators/gen_api_dispatch.lua
index 96c9b21b8f..35f6bf8455 100644
--- a/src/nvim/generators/gen_api_dispatch.lua
+++ b/src/nvim/generators/gen_api_dispatch.lua
@@ -426,7 +426,9 @@ for _,fn in ipairs(functions) do
 end
 remote_fns.redraw = {impl_name="ui_client_redraw", fast=true}
 
-local hashorder, hashfun = hashy.hashy_hash("msgpack_rpc_get_handler_for", vim.tbl_keys(remote_fns), function (idx)
+local names = vim.tbl_keys(remote_fns)
+table.sort(names)
+local hashorder, hashfun = hashy.hashy_hash("msgpack_rpc_get_handler_for", names, function (idx)
   return "method_handlers["..idx.."].name"
 end)
 
diff --git a/src/nvim/generators/gen_eval.lua b/src/nvim/generators/gen_eval.lua
index a50e058e00..baed6a74c2 100644
--- a/src/nvim/generators/gen_eval.lua
+++ b/src/nvim/generators/gen_eval.lua
@@ -73,14 +73,13 @@ for _,fun in ipairs(metadata) do
   end
 end
 
+local func_names = vim.tbl_keys(funcs)
+table.sort(func_names)
 local funcsdata = io.open(funcs_file, 'w')
-funcsdata:write(mpack.pack(funcs))
+funcsdata:write(mpack.pack(func_names))
 funcsdata:close()
 
-
-local names = vim.tbl_keys(funcs)
-
-local neworder, hashfun = hashy.hashy_hash("find_internal_func", names, function (idx)
+local neworder, hashfun = hashy.hashy_hash("find_internal_func", func_names, function (idx)
   return "functions["..idx.."].name"
 end)
 hashpipe:write("static const EvalFuncDef functions[] = {\n")
diff --git a/src/nvim/generators/gen_events.lua b/src/nvim/generators/gen_events.lua
index 6ee45a14af..8db7f22452 100644
--- a/src/nvim/generators/gen_events.lua
+++ b/src/nvim/generators/gen_events.lua
@@ -32,7 +32,9 @@ for i, event in ipairs(events) do
   end
 end
 
-for alias, event in pairs(aliases) do
+for _, v in ipairs(aliases) do
+  local alias = v[1]
+  local event = v[2]
   names_tgt:write(('\n  {%u, "%s", EVENT_%s},'):format(#alias, alias, event:upper()))
 end
 
diff --git a/src/nvim/generators/gen_keysets.lua b/src/nvim/generators/gen_keysets.lua
index 633c5da184..b1c1f3e2d8 100644
--- a/src/nvim/generators/gen_keysets.lua
+++ b/src/nvim/generators/gen_keysets.lua
@@ -1,4 +1,3 @@
-
 local nvimsrcdir = arg[1]
 local shared_file = arg[2]
 local funcs_file = arg[3]
@@ -38,7 +37,9 @@ local function sanitize(key)
   return key
 end
 
-for name, keys in pairs(keysets) do
+for _, v in ipairs(keysets) do
+  local name = v[1]
+  local keys = v[2]
   local neworder, hashfun = hashy.hashy_hash(name, keys, function (idx)
     return name.."_table["..idx.."].str"
   end)
diff --git a/src/nvim/generators/gen_options.lua b/src/nvim/generators/gen_options.lua
index af21d44eaf..edb7dae159 100644
--- a/src/nvim/generators/gen_options.lua
+++ b/src/nvim/generators/gen_options.lua
@@ -159,7 +159,7 @@ local dump_option = function(i, o)
     if #o.scope == 2 then
       pv_name = 'OPT_BOTH(' .. pv_name .. ')'
     end
-    defines['PV_' .. varname:sub(3):upper()] = pv_name
+    table.insert(defines,  { 'PV_' .. varname:sub(3):upper() , pv_name})
     w('    .indir=' .. pv_name)
   end
   if o.enable_if then
@@ -192,7 +192,7 @@ w('  [' .. ('%u'):format(#options.options) .. ']={.fullname=NULL}')
 w('};')
 w('')
 
-for k, v in pairs(defines) do
-  w('#define ' .. k .. ' ' .. v)
+for _, v in ipairs(defines) do
+  w('#define ' .. v[1] .. ' ' .. v[2])
 end
 opt_fd:close()
diff --git a/test/functional/lua/vim_spec.lua b/test/functional/lua/vim_spec.lua
index d90a78c92a..867f366d06 100644
--- a/test/functional/lua/vim_spec.lua
+++ b/test/functional/lua/vim_spec.lua
@@ -763,6 +763,20 @@ describe('lua stdlib', function()
       pcall_err(exec_lua, code))
   end)
 
+  it('vim.spairs', function()
+    local res = ''
+    local table = {
+      ccc=1,
+      bbb=2,
+      ddd=3,
+      aaa=4
+    }
+    for key, _ in vim.spairs(table) do
+      res = res .. key
+    end
+    matches('aaabbbcccddd', res)
+  end)
+
   it('vim.call, vim.fn', function()
     eq(true, exec_lua([[return vim.call('sin', 0.0) == 0.0 ]]))
     eq(true, exec_lua([[return vim.fn.sin(0.0) == 0.0 ]]))