Re: Strong tables in Lua 5.4

[Sean Conner <sean@...>]

  The problem of "storing" nils in tables deals exclusively with sequences.
The whole notion of a sequence is a bit odd (given how it calculates the
length), especially given that Lua *does* use an array (as an optimization)
to back them up (in most cases):

typedef struct Table {
  CommonHeader;
  lu_byte flags;  /* 1<<p means tagmethod(p) is not present */
  lu_byte lsizenode;  /* log2 of size of 'node' array */
  unsigned int sizearray;  /* size of 'array' array */		// !!!!!
  TValue *array;  /* array part */				// !!!!!
  Node *node;
  Node *lastfree;  /* any free position is before this position */
  struct Table *metatable;
  GCObject *gclist;
} Table;

  One proposal could be to modify the structure slightly (only show relevant
fields):

	typedef struct Table {
	  unsigned int sizearray;  /* size of 'array' array */
	  unsigned int lenarray;  /* current length of array */
	  TValue *array;  /* array part */
	} Table;

  The intent is such that #array will simply push the value of lenarray
instead of the O(ln) search it does now.  lenarray (and sizearray if we need
to shrink or grow the array) only change when you do:

	t[#t + 1] = somevalue;
	table.insert(t,somevalue);

	table.remove(t)
	table.remove(t,<some length <= #t>)

  Creating a sequence is pretty much the same:

	t = { 1 , 2 , nil , 4 , 5 } -- #t == 5

  Although, while *this* may generate a "proper sequence":

	t = { [1] = 1 , [2] = 2 , [3] = 3 , [4] = 4 , [5] = 5 }

this *might not*:

	t = { [3] = 3 , [5] = 5 , [1] = 1 , [4] = 4 , [2] = 2 }

Currently, this *is* a valid sequence.  Under this proposal, this
construction could be problematic.  You *could* attempt to calculate the
length by falling back on the O(ln) method, but there are *always*
pathological cases to consider:

	t = { 1 , 2 , 3 , 4 , 5 }
	t[7] = 7	-- #t still 5
	t[6] = 6	-- shoult #t be 7 now?

  Would this even be a real problem?  I think this proposal would easily fix
80-90% of the issues with storing nils in sequences, but the corner cases
will probably go up.

  -spc