Generalized Pairs And Ipairs

wiki

Warning

A Table in Lua has these essential properties (and others):

• Indexed read b=a[x] and write a[x]=b.
• Table iteration using k,v=next(t,k) (as well as the more readable for statement with pairs, ipairs, and others).
• Length (#) operator.

The first property can be customized via __index and __newindex metamethods for tables and userdata. There is no direct way to customize the second and third properties (LuaVirtualization). We examine ways to customize these properties here.

Defining __next and __index metamethods

If you are happy with just rewriting the next() function, then you can use the code snippet below...

rawnext = next

function next(t,k)

  local m = getmetatable(t)

  local n = m and m.__next or rawnext

  return n(t,k)

end

Example usage:

local priv = {a = 1, b = 2, c = 3}

local mt = {

  __next = function(t, k) return next(priv, k) end

}

local t = setmetatable({}, mt)



for k,v in next, t do print(k,v) end

-- prints a 1 c 3 b 2

Note that this has no effect on the pairs function:

for k,v in pairs(t) do print(k,v) end

-- prints nothing.

The pairs function may be redefined in terms of next:

function pairs(t) return next, t, nil end

Example usage:

for k,v in pairs(t) do print(k,v) end

-- prints a 1 c 3 b 2

ipairs may also be extended to reference the __index metamethod:

local function _ipairs(t, var)

  var = var + 1

  local value = t[var]

  if value == nil then return end

  return var, value

end

function ipairs(t) return _ipairs, t, 0 end

Example usage:

local priv = {a = 1, b = 2, c = 3, 7, 8, 9}

local mt = {__index = priv}

local t = setmetatable({}, mt)



for k,v in ipairs(t) do print(k,v) end

-- prints 1 7 2 8 3 9

-- PeterHill, DavidManura

Defining __pairs and __index metamethods

The following C implementation provides similar behavior but using __pairs and __index metamethods. This approach using a __pairs metamethod is likely faster than the alternate approach above using a __next metamethod.

This code redefines pairs and ipairs so that:

• pairs consults the __pairs metamethod
• ipairs uses lua_gettable instead of lua_rawgeti so that it will respect __index metamethods

It should install a __pairs method for strings, but it doesn't yet. Feel free to add it, all the bits and pieces are there.

It expects to be loaded with require "xt" and will produce an "xt" table with the various functions. However, it also overwrites pairs and ipairs in the globals table. If you find that offensive, take out the relevant lines in luaopen_xt.

In short, take it and do as you will. Feel free to post patches.

#include "lua.h"

#include "lauxlib.h"



/* This simple replacement for the standard ipairs is probably

 * almost as efficient, and will work on anything which implements

 * integer keys. The prototype is ipairs(obj, [start]); if start

 * is omitted, it defaults to 1.

 *

 * Semantic differences from ipairs:

 *   1) metamethods are respected, so it will work on pseudo-arrays

 *   2) You can specify a starting point

 *   3) ipairs does not throw an error if applied to a non-table;

 *      the error will be thrown by the inext auxiliary function

 *      (if the object has no __index meta). In practice, this

 *      shouldn't make much difference except that the debug library

 *      won't figure out the name of the object.

 *   4) The auxiliary function does no explicit error checking

 *      (although it calls lua_gettable which can throw an error).

 *      If you call the auxiliary function with a non-numeric key, it

 *      will just start at 1.

 */



static int luaXT_inext (lua_State *L) {

  lua_Number n = lua_tonumber(L, 2) + 1;

  lua_pushnumber(L, n);

  lua_pushnumber(L, n);

  lua_gettable(L, 1);

  return lua_isnil(L, -1) ? 0 : 2;

}



/* Requires luaXT_inext as upvalue 1 */

static int luaXT_ipairs (lua_State *L) {

  int n = luaL_optinteger(L, 2, 1) - 1;

  luaL_checkany(L, 1);

  lua_pushvalue(L, lua_upvalueindex(1));

  lua_pushvalue(L, 1);

  lua_pushinteger(L, n);

  return 3;

}  

  

/* This could have been done with an __index metamethod for

 * strings, but that's already been used up by the string library.

 * Anyway, this is probably cleaner.

 */

static int luaXT_strnext (lua_State *L) {

  size_t len;

  const char *s = lua_tolstring(L, 1, &len);

  int i = lua_tointeger(L, 2) + 1;

  if (i <= len && i > 0) {

    lua_pushinteger(L, i);

    lua_pushlstring(L, s + i - 1, 1);

    return 2;

  }

  return 0;

}



/* And finally a version of pairs that respects a __pairs metamethod.

 * It knows about two default iterators: tables and strings. 

 * (This could also have been done with a __pairs metamethod for

 * strings, but there was no real point.)

 */



/* requires next and strnext as upvalues 1 and 2 */

static int luaXT_pairs (lua_State *L) {

  luaL_checkany(L, 1);

  if (luaL_getmetafield(L, 1, "__pairs")) {

    lua_insert(L, 1);

    lua_call(L, lua_gettop(L) - 1, LUA_MULTRET);

    return lua_gettop(L);

  }

  else {

    switch (lua_type(L, 1)) {

      case LUA_TTABLE: lua_pushvalue(L, lua_upvalueindex(1)); break;

      case LUA_TSTRING: lua_pushvalue(L, lua_upvalueindex(2)); break;

      default: luaL_typerror(L, 1, "iterable"); break;

    }

  }

  lua_pushvalue(L, 1);

  return 2;

}





static const luaL_reg luaXT_reg[] = {

  {"inext", luaXT_inext},

  {"strnext", luaXT_strnext},

  {NULL, NULL}

};



int luaopen_xt (lua_State *L) {

  luaL_openlib(L, "xt", luaXT_reg, 0);

  lua_getfield(L, -1, "inext");

  lua_pushcclosure(L, luaXT_ipairs, 1);

  lua_pushvalue(L, -1); lua_setglobal(L, "ipairs");

  lua_setfield(L, -2, "ipairs");

  lua_getglobal(L, "next");

  lua_getfield(L, -2, "strnext");

  lua_pushcclosure(L, luaXT_pairs, 2);

  lua_pushvalue(L, -1); lua_setglobal(L, "pairs");

  lua_setfield(L, -2, "pairs");

  return 1;

}

Here's an alternate Lua implementation of the pairs replacement. Note: unlike the C implementation, this Lua implementation won't work if the metatable is protected.

local _p = pairs; function pairs(t, ...)

  return (getmetatable(t).__pairs or _p)(t, ...) end

-- RiciLake

Defining __next and __ipairs metamethods

p. 262 of Beginning Lua Programming follows a similar method but instead uses __next and __ipairs metamethods. The code is online via the download link at [1] (see Chapter 08/orderedtbl.lua). Note, however, that this code requires a correction (noted on p. 306) to make {__mode = "k"} the metatable for the RealTbls, NumToKeys, and KeyToNums tables.

Here is an alternative OrderedTable implementation by RiciLake.

More Notes

If you want to truly emulate such behaviour you will need to modify the Lua source to add lua_rawnext() and to update lua_next(), in which case see the ExtendingForAndNext entry by RiciLake.

Historical Note: I (RiciLake) wrote ExtendingForAndNext in September, 2001, when Lua did not yet have a generalized for statement. The design was based on the existing code in Lua 4, and I'd like to think that it influenced the design of the generalized for statement, which appeared a few months later. At the time, Lua had "tag methods" rather than metamethods; tag method access was somewhat faster than metamethod access (except where optimized), but metamethods are clearly better. I mention that only to put the ExtendingForAndNext patch in context.

ExtendingForAndNext contemplates the use of both functions and iterable objects as the target of the for statement; however, Roberto's design is quite a bit nicer in that it only uses functions. Instead of looking up the appropriate next method on every loop iteration, an appropriate iterator-factory, such as pairs, is invoked just once on loop setup. That's certainly faster, unless the next method lookup is trivial (which it normally isn't). Since the object being iterated is constant through the loop, the next lookup will always be the same. But, more importantly, it's also more general, because it does not restrict an iterable object to having just one iteration mechanism.

The one thing which my original proposal addressed, and which is not satisfactorily solved in the current (5.1) Lua implementation, is that while it is convenient to have multiple iteration mechanisms for the same object (string.gmatch is probably the best example of this), it is inconvenient to have to know the type of an iterable object in order to code the correct default iteration mechanism. That is, one (or at least I) would like to be able to just write for k, v in pairs(t) do without having to know what the precise object type of t is, in the case where the object type has a default key/value type iteration method.

The code above, which generalizes the implementation of pairs to consult a __pairs metamethod, is an attempt to solve that problem in the simplest possible way.

The generalized version of ipairs is, unfortunately, probably incorrect, although I've left it in the code for historical integrity. Normally, one would want to override ipairs in precisely the circumstance that the object's default iteration mechanism should be increasing integer keys. In fact, in many cases the correct default iterator for a given table is the iterator returned by ipairs rather than the iterator returned by pairs, and it would be more appropriate to make ipairs (or a customized version) the __pairs metamethod, rather than leaving it to the object's client to know that the default iterator is ipairs.

That design almost eliminates the need for a __next metamethod, and personally I now feel that __next is poor style. (In fact, I feel strongly enough about it to write this longish note.) It might be argued that, just as there is a need to be able to get the default iterator using pairs, that one should have access to the default step function using next. However, that would limit the possible implementations of pairs since it would force them to return an iterator which used the target object itself, as opposed to some delegate or proxy, as the iteration object. In my opinion, better style is to use the pairs (or other iterator factory) to return a triple stepfunc, obj, initial_state and then use that to manually step through an iterable object, in the case that the for statement's rigidity is inapplicable. For example, one might use that style to create a tail-recursive loop:

-- This simple example is for parsing escaped strings from an input sequence; the

-- iterator might have been returned by string.gmatch



function find_end(accum, f, o, s, v)

  if v == nil then                                          

    error "Undelimited string"

  elseif v == accum[1] then

    return table.concat(accum, "", 2), f(o, s)

  elseif v == '\\' then

    s, v = f(o, s) -- skip next char

  end

  accum[#accum+1] = v

  return find_end(accum, f, o, f(o, s)) -- tail recursive loop

end



function get_string(f, o, s, v)

  local accum = {v}                                         

  return find_end(accum, f, o, f(o, s))

end



function skip_space(f, o, s, v)

  repeat s, v = f(o, s) until not v:match"%s"

  return s, v

end



function get_word(f, o, s, v)

  local w = {v}                  

  for ss, vv in f, o, s do

    if vv:match"%w" then w[#w+1] = vv

    else return table.concat(w), ss, vv

    end

  end

  return table.concat(w)

end



function nextchar(str, i)

  i = i + 1

  local v = str:sub(i, i)

  if v ~= "" then return i, v end

end

function chars(str) return nextchar, str, 0 end



function aux_parse(f, o, s, v)

  while v do

    local ttype, token

    if v:match"%s" then

      s, v = skip_space(f, o, s, v)

    elseif v:match"%w" then

      ttype, token, s, v = "id", get_word(f, o, s, v)

    elseif v:match"['\"]" then

      ttype, token, s, v = "string", get_string(f, o, s, v)

    else error("Unexpected character: "..v)

    end

    if ttype then print(ttype, token) end

  end

end



function parse(str)           

  local f, o, s = chars(str)

  return aux_parse(f, o, f(o, s))

end



parse[[word word2 'str\\ing\'' word3]]

Self-iterating tables - the __iter metamethod

It would surely be more natural to be able to write a generic for over a table as follows:

for item1 in table1 do

...

end

An idiom for achieving this with the Lua 5.1 language definition is to use the __call metamethod as an iterator factory. Then one can write:

for item1 in table1() do

...

end

This is slightly less natural than the __iter approach, but can be implemented without changing the language definition. A side advantage is that parameters can be passed into the iterator factory to modify the iteration. For example a version of ipairs with optional minimum and maximum indices:

for item1 in table1(3, 10) do

...

end

If __pairs and __ipairs metamethods are being considered for a future language implementation, could this __iter alternative be considered too?

(15 Jan 2010) Got fed up with arguing about this and implemented it myself! See LuaPowerPatches.

-- JohnHind

The __len metamethod

#t does not invoke the __len metamethod when t is a table. See LuaList:2006-01/msg00158.html. This prevents simple implementations of some obvious things like ReadOnlyTables .

The __len metamethod for tables is reported to be implemented in Lua 5.2 (LuaFiveTwo).

There seems to be a general policy in Lua that metamethods do not override built-in functionality but rather only supply functionality in cases that would otherwise generate an error message (or at least return a nil). But __len for tables has to be a good case to be the 'exception which proves the rule', since the default behaviour only makes sense in the special case of contiguous arrays and other behaviours could reasonably be expected in other cases. -- JohnHind

__pairs and __ipairs in Lua 5.2

Note that you can override __ipairs for strings, although of course this is a global change:

getmetatable('').__ipairs = function(s)

    local i,n = 0,#s

    return function()

        i = i + 1

        if i <= n then

            return i,s:sub(i,i)

        end

    end

end



for i,ch in ipairs "he!" do print(i,ch) end

=>

1       h

2       e

3       !

SteveDonovan

See Also

• NextMetamethodForIndexTable - Rewriting next() for when __index is a table
• LuaVirtualization - notes limitations of objects acting as values of other types
• LuaPowerPatches - patch to implement the '__iter' metamethod.