Storing Nils In Tables

wiki

Occasionally we find ourselves in a situation where we really do want to distinguish between table values that are nil v.s. those that are undefined. Consider this function that reverses its arguments by storing and manipulating the arguments in a table:

function reverse(...)

    local t = {...}

    for i = 1,#t/2 do

      local j = #t - i + 1

      t[i],t[j] = t[j],t[i]  -- swap

    end

    return unpack(t)

end

This usually works, but not necessarily when one of the arguments is nil:

print(reverse(10,20,30)) --> 30 20 10

print(reverse(10,nil,20,nil)) --> 10

Solution: explicit 'n' field

A solution we can use here is to store the table length as a key n in the table. In fact, this is how Lua versions prior to 5.1 implemented array length:

function reverse(...)

    local t = {n=select('#', ...), ...}

    for i = 1,t.n/2 do

      local j = t.n - i + 1

      t[i],t[j] = t[j],t[i]  -- swap

    end

    return unpack(t, 1, t.n)

end

(It's been noted by RiciLake that the extra copy of ... into a function argument list for determining its length involves needless overhead. In fact, it would also be nice to avoid the overhead of constructing a table to perform this operation, but data in ... is cumbersome to manipulate unless copied into a table, though there are some slightly awkward patterns to avoid the table--see "Vararg Saving" in VarargTheSecondClassCitizen.)

Solution: nil Placeholder

The above approach works in the special cases where a table is used as an array containing nil's. In the general case, the table might contain arbitrary (not necessarily numeric) values. The following example expresses a mathematical set by storing its elements as keys in a Lua table. However, since table keys cannot be nil, this presents a challenge to storing nil in the set. The solution is to create a placeholder object NIL that is stored in place of nil in the table:

do

  local NIL = {}

  function set_create(...)

    local t = {}

    for n=1,select('#', ...) do

      local v = select(n, ...)

      t[v == nil and NIL or v] = true

    end

    return t

  end

  function set_exists(t, v)

    return t[v == nil and NIL or v]

  end

end

local t = set_create(10, nil, false)

assert(set_exists(t, 10))

assert(set_exists(t, nil))

assert(set_exists(t, false))

assert(not set_exists(t, "hello"))

There is little possibility for conflict using NIL as a place-holder. NIL, as a table, is an object, and objects have unique identities. The table NIL is lexically scoped in the do block and is not visible anywhere else in the program--except, well, in the table. The user could grab NIL out of the table and attempt to add it to another set, and in this case NIL will be treated as nil rather than NIL, and this is probably what the user intended.

There are other alternatives to using NIL, such as using some other value that is unique to the domain of a particular table (possibly false or the table itself), but this will not work in the general case. You might alternately use a second table enumerating the defined keys:

local t = {red = 1, green = 2}

local is_key = {"red", "green", "blue"}

for _,k in ipairs(is_key) do print(k, t[k]) end

It should be noted that nil is not the only value that cannot be stored in tables. The "not-a-number" value (NAN) defined by 0/0 cannot be stored as a key (but can be stored as a value). There are some potential issues with NAN being a table key: LuaList:2005-11/msg00214.html . This limitation can be worked around in a similar way. However, note that NAN is the only value that doesn't equal itself (NAN ~= NAN), and this is the way to test for NAN.

Hack: Distinguishing UNDEF and nil via Metafunctions

One possible solution would be to define a metatable on a given table so that the table returns nil if a key exists and the value is nil but returns a new unique value UNDEF = {} if a key does not exist. However, this has some fairly serious problems. First, UNDEF logically evaluates to true, so we can't use the idiom if t[k] then ... end since it will execute the branch if k is undefined in the table. More importantly, the programmer might attempt to store these UNDEF values in a table, leading to a similar problem that UNDEF's can't be stored in tables.

That approach is implemented below by making the table be a proxy to another private table that maintains the nil v.s. UNDEF information, and the __newindex metfunction records the setting of nil. It is partly based on the "Tables with default values" example in Programming In Lua, 2nd ed., 13.4.

-- NiledTable.lua

local M = {}



-- weak table for representing nils.

local nils = setmetatable({}, {__mode = 'k'})



-- undefined value

local UNDEF = setmetatable({},

  {__tostring = function() return "undef" end})

M.UNDEF = UNDEF



-- metatable for NiledTable's.

local mt = {}

function mt.__index(t,k)

  local n = nils[t]

  return not (n and n[k]) and UNDEF or nil

end

function mt.__newindex(t,k,v)

  if v == nil then

    local u = nils[t]

    if not u then

      u = {}

      nils[t] = u

    end

    u[k] = true

  else

    rawset(t,k,v)

  end

end



-- constructor

setmetatable(M, {__call = function(class, t)

  return setmetatable(t, mt)

end})



local function exipairs_iter(t, i)

  i = i + 1

  local v = t[i]

  if v ~= UNDEF then

    return i, v

  end

end



-- ipairs replacement that handles nil values in tables.

function M.exipairs(t, i)

  return exipairs_iter, t, 0

end



-- next replacement that handles nil values in tables

function M.exnext(t, k)

  if k == nil or rawget(t,k) ~= nil then

    k = next(t,k)

    if k == nil then

      t = nils[t]

      if t then k = next(t) end

    end

  else

    t = nils[t]

    k = next(t, k)

  end

  return k

end

local exnext = M.exnext



-- pairs replacement that handles nil values in tables.

function M.expairs(t, i)

  return exnext, t, nil

end



-- Undefine key in table.  This is used since t[k] = UNDEF doesn't work

-- as is.

function M.undefine(t, k)

  rawset(t, k, nil)

end



return M

Examples/test:

-- test_nil.lua - test of NiledTable.lua



local NiledTable = require "NiledTable"



local UNDEF    = NiledTable.UNDEF

local exipairs = NiledTable.exipairs

local expairs  = NiledTable.expairs

local exnext   = NiledTable.exnext



local t = NiledTable { }



t[1] = 3

t[2] = nil

t.x = 4

t.y = nil

assert(t[1] == 3)

assert(t[2] == nil)

assert(t[3] == UNDEF)

assert(t.x == 4)

assert(t.y == nil)

assert(t.z == UNDEF)



-- UNDEF is true.  This is possible undesirable since

-- "if t[3] then ... end" syntax cannot be used as before.

assert(UNDEF)



-- nils don't count.  __len cannot be overriden in 5.1 without special

-- userdata tricks.

assert(#t == 1)



-- constructor syntax doesn't work.  The construction is done

-- before the metatable is set, so the nils are discarded before

-- NiledTable can see them.

local t2 = NiledTable {nil, nil}

assert(t2[1] == UNDEF)



-- nils don't work with standard iterators

local s = ""; local n=0

for k,v in pairs(t)  do print("pairs:", k, v); n=n+1 end

assert(n == 2)

for i,v in ipairs(t) do print("ipairs:", i, v); n=n+1 end

assert(n == 3)



-- replacement iterators that do work

for i,v in exipairs(t) do print("exipairs:", i, v); n=n+1 end

assert(n == 5)

for k,v in expairs(t) do print("expairs:", k, v); n=n+1 end

assert(n == 9)

for k,v in exnext, t do print("next:", k, v); n=n+1 end

assert(n == 13)



-- This does not do what you might expect.  The __newindex

-- metamethod is not called.  We might resolve that by making

-- the table be a proxy table to allow __newindex to handle this.

t[1] = UNDEF

assert(t[1] == UNDEF)

for k,v in expairs(t) do print("expairs2:", k, v); n=n+1 end

assert(n == 17) --opps



-- Alternative

undefine(t, 1)

for k,v in expairs(t) do print("expairs3:", k, v); n=n+1 end

assert(n == 20) --ok



-- Now that we can store nil's in tables, we might now ask

-- whether it's possible to store UNDEF in tables.  That's

-- probably not a good idea, and I don't know why you would

-- even want to do that.  It leads to a similar problem.

--

--   Here is why:  any value in Lua can potentially be used as input or

--   output to a function, and any function input or output can potentially

--   be captured as a Lua list, and Lua lists are implemented with tables...



print "done"

Solution: Existence Maintained Internally in a Table

The problems in the hack above can be solved by avoiding exposure of any new values outside the module. Instead, t[k] will return nil both if the k is not in the table or if the corresponding value is nil. We'll distinguish between those two conditions with a new function exists(t,k), which returns a Boolean indicating whether the key k exists in the table t. (This behavior is similar to that in the Perl language.)

In this way, we can still use the idiom if t[k] then ... end when appropriate or use the new idiom if exists(t, k) then ... end. Furthermore, no new values are introduced into the language, thereby avoiding the "storing UNDEF's in tables" problem above.

-- NiledTable.lua

local M = {}



-- weak table for representing proxied storage tables.

local data = setmetatable({}, {__mode = 'k'})



-- nil placeholder.

-- Note: this value is not exposed outside this module, so

-- there's typically no possibility that a user could attempt

-- to store a "nil placeholder" in a table, leading to the

-- same problem as storing nils in tables.

local NIL = {__tostring = function() return "NIL" end}

setmetatable(NIL, NIL)



-- metatable for NiledTable's.

local mt = {}

function mt.__index(t,k)

  local d = data[t]

  local v = d and d[k]

  if v == NIL then v = nil end

  return v

end

function mt.__newindex(t,k,v)

  if v == nil then v = NIL end

  local d = data[t]

  if not d then

    d = {}

    data[t] = d

  end

  d[k] = v

end

function mt.__len(t)  -- note: ignored by Lua but used by exlen below

  local d = data[t]

  return d and #d or 0

end



-- constructor

setmetatable(M, {__call = function(class, t)

  return setmetatable(t, mt)

end})



function M.exists(t, k)

  local d = data[t]

  return (d and d[k]) ~= nil

end

local exists = M.exists



function M.exlen(t)

  local mt = getmetatable(t)

  local len = mt.__len

  return len and len(t) or #t

end



local function exipairs_iter(t, i)

  i = i + 1

  if exists(t, i) then

    local v = t[i]

    return i, v

  end

end



-- ipairs replacement that handles nil values in tables.

function M.exipairs(t, i)

  return exipairs_iter, t, 0

end



-- next replacement that handles nil values in tables

function M.exnext(t, k)

  local d = data[t]

  if not d then return end

  k = next(d, k)

  return k

end

local exnext = M.exnext



-- pairs replacement that handles nil values in tables.

function M.expairs(t, i)

  return exnext, t, nil

end



-- Remove key in table.  This is used since there is no

-- value v such that t[k] = v will remove k from the table.

function M.delete(t, k)

  local d = data[t]

  if d then d[k] = nil end

end



-- array constructor replacement.  used since {...} discards nils.

function M.niledarray(...)

  local n = select('#', ...)

  local d = {...}

  local t = setmetatable({}, mt)

  for i=1,n do

    if d[i] == nil then d[i] = NIL end

  end

  data[t] = d

  return t

end



-- table constructor replacement.  used since {...} discards nils.

function M.niledtablekv(...)

  -- possibly more optimally implemented in C.

  local n = select('#', ...)

  local tmp = {...} -- it would be nice to avoid this

  local t = setmetatable({}, mt)

  for i=1,n,2 do t[tmp[i]] = tmp[i+1] end

  return t

end



return M

Examples/test:

-- test_nil.lua - test of NiledTable.lua



local NiledTable = require "NiledTable"



local exlen      = NiledTable.exlen

local exipairs   = NiledTable.exipairs

local expairs    = NiledTable.expairs

local exnext     = NiledTable.exnext

local exists     = NiledTable.exists

local delete     = NiledTable.delete

local niledarray = NiledTable.niledarray

local niledtablekv = NiledTable.niledtablekv



local t = NiledTable { }



t[1] = 3

t[2] = nil

t.x = 4

t.y = nil

assert(t[1] == 3    and exists(t, 1))

assert(t[2] == nil  and exists(t, 2))

assert(t[3] == nil  and not exists(t, 3))

assert(t.x  == 4    and exists(t, 'x'))

assert(t.y  == nil  and exists(t, 'y'))

assert(t.z  == nil  and not exists(t, 'z'))



-- non-existant and nil values are both returned as nil and

-- therefore both are logically false.

-- allows "if t[3] then ... end" usage.

assert(not t[2] and not t[3])



-- nils don't count in #t since __len cannot be overriden in

-- 5.1 without special userdata tricks.

assert(#t == 0)

assert(exlen(t) == 2) -- workaround function



-- constructor syntax doesn't work.  The construction is done

-- before the metatable is set, so the nils are discarded before

-- NiledTable can see them.

local t2 = NiledTable {nil, nil}

assert(t2[1] == nil)



-- alternate array constructor syntax (value list) that does work

local t2 = niledarray(nil,nil)

assert(t2[1] == nil and exists(t2, 1))

assert(t2[2] == nil and exists(t2, 2))

assert(t2[3] == nil and not exists(t2, 3))



--- more tests of niledarray

local t2 = niledarray(1,nil,nil)

assert(t2[1] == 1 and exists(t2, 1))

assert(t2[2] == nil and exists(t2, 2))

assert(t2[3] == nil and exists(t2, 3))

assert(t2[4] == nil and not exists(t2, 4))

t2[4]=4

assert(t2[4] == 4 and exists(t2, 4))



-- alternate table constructor syntax (key-value pair list) that does work

local t2 = niledtablekv(1,nil, 2,nil) -- {[1]=nil, [2]=nill}

assert(t2[1] == nil and exists(t2, 1))

assert(t2[2] == nil and exists(t2, 2))

assert(t2[3] == nil and not exists(t2, 3))



-- nils don't work with standard iterators

local s = ""; local n=0

for k,v in pairs(t)  do print("pairs:", k, v); n=n+1 end

assert(n == 0)

for i,v in ipairs(t) do print("ipairs:", i, v); n=n+1 end

assert(n == 0)



-- replacement iterators that do work

for i,v in exipairs(t) do print("exipairs:", i, v); n=n+1 end

n = n - 2; assert(n == 0)

for k,v in expairs(t) do print("expairs:", k, v); n=n+1 end

n = n - 4; assert(n == 0)

for k,v in exnext, t do print("next:", k, v); n=n+1 end

n = n - 4; assert(n == 0)



-- Setting an existing element to nil, makes it nil and existant

t[1] = nil

assert(t[1] == nil and exists(t, 1))

for k,v in expairs(t) do print("expairs2:", k, v); n=n+1 end

n = n - 4; assert(n == 0)



-- Calling delete makes an element non-existant

delete(t, 1)

for k,v in expairs(t) do print("expairs3:", k, v); n=n+1 end

n = n - 3; assert(n == 0)



-- nil's still can't be used as keys though (and neither can NaN)

assert(not pcall(function() t[nil] = 10 end))

assert(not pcall(function() t[0/0] = 10 end))



print "done"

Footnotes

[1] Including C, Java, Python, and Perl. In Perl, [exists and defined] differentiate these two cases: exists $v{x} v.s. defined $v{x} .

-- DavidManura

See Also

• VarargTheSecondClassCitizen - discusses the problem of nils being lost when converting ... or function multiple return values into a table.
• LuaTableSize - the change made in 5.0
• LuaList:2007-07/msg00557.html "lists with nil play nice for Lua 5.2"