Re: Holes

[Joshua Phillips <jp.sittingduck@...>]

On Mon 13/Dec/2010, Mark Hamburg wrote:
> Here is another potential solution to the "holes" problem:

Is the holes problem that #t is not table.maxn, and table.maxn is O(n)?

> 1. Define a new value type HOLE or NIL or NULL or whatever. It doesn't
> really matter what one calls it because it's purely an implementation
> detail as we'll see below. Values of this type will only appear in the
> value fields of tables.
> 
> 2. When reading a value from a table, if the value is equal to HOLE
> then read it as nil. This would be true even with rawget.
> 
> 3. When storing a nil value to a table, if the table is specially
> marked -- e.g., an appropriate __mode value is set in the metatable
> (though that makes it hard to use the feature during table creation)
> -- then store HOLE. rawset would bypass this and store nil and would
> be what one needed to use to really remove values. (One variant would
> always do this during table construction under the theory that if you
> mention a value, you must actually care about it.)
> 
> 4. The definition of #t remains unchanged. It does not view HOLES as
> being equivalent to nil.

This will cause a large amount of complication, just to change the
behaviour of the '#' operator on tables, and some of the table
functions, without actually changing them.

You want to create a new type with a value that behaves as non-nil, and
yet is almost completely invisible. This is bound to make debugging fun!
If the HOLE type is made visible to Lua code, then it wouldn't be so
bad... but then you can use an existing type, like false, or a
particular table value (create an empty table and use it as a unique
value), depending on what is needed.

Perhaps a better idea to solve the '"holes" problem' is to store the
largest number key with each table, so that table.maxn can be O(1),
but adding new number keys would be a little slower.
This will increase the space overhead of each table though, which might
hurt performance elsewhere.