search

bakpakin / Fennel

Lua Lisp Language
https://fennel-lang.org
MIT License
2.42k stars 124 forks source link

Fix unstable order bug #450

Closed jaawerth closed 1 year ago

jaawerth commented 1 year ago

Fixes #449

Description (from commit msg)

Fix Lua 5.3/5.4 edge case for stablepairs

When a :keys custom metamethod is present on a table node, stablepairs skipped sorting and only used the specified keys to determine order, adding the extras in as they occurred in pairs, which is unstable in PUC Lua > 5.2 due to a random nonce added to hash tables to prevent collission attacks.

As a result, if a macro added extra keys to a table literal, those extra keys cause non-deterministic order for table literals in the emitted Lua on affected versions of the Lua VM.

Also addressed an edge case for cases like {:1 :one 1 :also-one} and {true :TRUE "true" :ALSO-TRUE}, which would not sort reliably with the old sort comparator that simply used (< (tostring a) (tostring b))

Example:

(macro add-keys [t ...]
  (assert (table? t))
  (for [i 1 (select :# ...)]
    (let [(k v) (select i ...)] (tset t k v)))
  t)
(add-keys {:a 1 :b 2} :c 3 :d 4)

Test reliability and random nonce

I wasn't sure where the best place to put the tests for this - for now, I originally created a separate test module running compilation via the CLI so that it could run while re-instantiating the Lua VM each time so I could add a loop to re-compile and assert multiple times to check stability.

However (see second commit) since the test is failing reliably on every run from the main branch, I consolidated it into the core test suit, compiling directly, to avoid further slowing down tests with more shelling out to the CLI. The test will already run once for each Lua version (twice for those with the nonce), and the higher number of table keys means more keys that could potentially show up out of order, so I decided I was being overly cautious.

I left it in a separate commit for review purposes - we can always go the back to running via the CLI to ensure we'd hit a random edge case by throwing out the second commit.

technomancy commented 1 year ago

Cool; thanks for tracking this down! I think as long as you were able to get the tests failing normally before the fix was applied it should be fine.