Ordered keys patch for lua-5.1.4 (+extra junk)

[Dave Rodgers <trepanx@...>]

The Patch
---------

http://dscontracting.ca/trepan/lua/luaok_v1_lua-5.1.4.diff


TL;DR
-----

- The first 2 notes in `Changes' might be of interest to TPTB.
- I don't figure anyone will bother with this crap, so you may
 find the following remarks a little disconnected...  I gave
 up caring shortly before writing this line   ;)


Notes
-----

This is one big patch that implements the features listed in the Changes
section of this post. The main feature is LUA_ORDERED_KEYS, which allows
for deterministic table key scans using next() and pairs(). You can easily
strip out what you want by looking for the #define'd tags.

If you use lua pointer objects (tables, functions, userdata), as table
keys, the return order used by next() and pairs() depends on the memory
locations of the objects. This means that there's no guarantee on the
order between multiple runs of the same program. Here's an example that
will likely demonstrate the situation:

 t = {[{}]=1, [{}]=2, [{}]=3}; for k,v in pairs(t) do print(k,v) end

Try running that code snippet a few times, you'll probably get different
results.

In environments that demand deterministic code execution, you can either
disable pointer objects as scannable keys, or enforce an order upon them.
LUA_ORDERED_KEYS orders all of the hash keys by insertion order (array
keys are already guaranteed to be scanned in a deterministic fashion).

Because I used a doubly-linked-list overlayed on the standard lua hash
table, the prev() and rpairs() functions were easy to implement, so they
were.

I threw in LUA_READONLY_TABLES because ... well, just because. The easy
lua trick of using empty tables as proxies for the real data (via __index),
takes about 2.25 as much time as to read data as raw table reads. It also
prohibits the use of pairs (__pairs does not yet exist in standard lua).
table.readonly() allows you to simply set a table's data as read-only, no
messing around with meta-tables.



Changes
-------

* added a rule to Makefile to trigger rebuilds when the Makefile changes

* added a fix in loadlib.c for pedantic ISO-C rules about pointer casts

- added the optional `strip' boolean parameter to string.dump()

- replaced the quicksort algorithm with mergesort algorithm for table.sort()
                            
- added table.create(arraysize, hashsize) -> table
       
- added debug.getkeyinfo(table, key) -> nil | index [, hashindex, hashdepth]
   index: >0 = array index
          <0 = -(hash index)
   hashindex: -(main hash index)
   hashdepth: hash gnext() depth, starting at 1

- added the following configuration options to luaconf.h:
 - LUA_READONLY_TABLES
 - LUA_ORDERED_KEYS
 - LUA_TOSTRING_NOPOINTERS
 - LUA_PRINT_COMMON_INF_NAN



Speed Tests
-----------

http://dscontracting/trepan/lua/ok_ro/speedtests.html



LUA_ORDERED_KEYS
----------------

Lua Additions:
 prev(table [, key])  -- reverse next()
 rpairs(table)        -- reverse pairs()
 table.sortkeys(table [, 'a'] [, function | false])
 table.insertkey(table, <oldkey | nil>, newkey [, value])
 table.usearray(table [, boolean value]) -> table | value

Notes:
- Table array data is not sorted  (it is already deterministic)

- If a key is set on a table, and its old value is nil; it is appended, ex:
   local t = { a = 1, b = 2, c = 3 }
   for k,v in pairs(t) do print(k..'='..v) end  =>  a=1 b=2 c=3
   t.b = nil  t.b = 2
   for k,v in pairs(t) do print(k..'='..v) end  =>  a=1 c=3 b=2

- The 'a' parameter in table.sortkeys() tells the function to ignore the
 array part of the table. The default sortkeys() mode of operation is to
 first convert elements from the array part of the table to hash nodes.

- table.insertkey() inserts the new key before the old key, or at the end
 of the scan list if the old key is nil (similar to table.insert())

- table.usearray(t, false) forbids the use of the table's array section
 (forces the use of the hash section). If the table contains array data
 before the call is made, that data will be converted to hash nodes.  

- table.sortkeys() could be made faster, two unnecessary table copies are
 done with the code as it is. It might also be worth investigating using
 scan list pointer manipulations instead of table.sort() to sort the keys.
  
  

LUA_READONLY_TABLES
-------------------

Lua Additions:
 table.readonly(table [, state]) -> table | state | nil, error
   input state can be a boolean, or a string with the following flags:
     'o' : old keys can not be modified
     'n' : new keys can not be added  
   output state will be one of the following:
     false : no read-only protection
     'o'   : old key read-only protection
     'n'   : new key read-only protection
     'on'  : old and new key read-only protection

CAPI Additions:
 int  lua_getreadonly(lua_State *L, int tableindex)
 void lua_setreadonly(lua_State *L, int tableindex, int statebits)
 void luaH_checkreadonly(lua_State *l, int tableindex);

 #define LUA_READONLY_OLD_LUA_BIT       (1 << 0)
 #define LUA_READONLY_OLD_CAPI_BIT      (1 << 1)
 #define LUA_READONLY_OLD_INTERNAL_BIT  (1 << 2)
 #define LUA_READONLY_OLD_BITS  (LUA_READONLY_OLD_LUA_BIT  | \
                                 LUA_READONLY_OLD_CAPI_BIT | \
                                 LUA_READONLY_OLD_INTERNAL_BIT)
 #define LUA_READONLY_NEW_LUA_BIT       (1 << 3)
 #define LUA_READONLY_NEW_CAPI_BIT      (1 << 4)
 #define LUA_READONLY_NEW_INTERNAL_BIT  (1 << 5)
 #define LUA_READONLY_NEW_BITS  (LUA_READONLY_NEW_LUA_BIT  | \
                                 LUA_READONLY_NEW_CAPI_BIT | \
                                 LUA_READONLY_NEW_INTERNAL_BIT)
 #define LUA_READONLY_BITS  (LUA_READONLY_OLD_BITS | LUA_READONLY_NEW_BITS)

Notes:
- The table.readonly()  function only affects the LUA_BIT bits.

- The lua_setreadonly() function only affects the LUA_BIT and CAPI_BIT bits.

- The read-only checks do not interfere with metamethods invocations.