Generalized Pairs And Ipairs

Lua 5.2+ __pairs and __ipairs

Lua 5.2 introduced the `__pairs` and `__ipairs` methods for controlling the behavior of `pairs` and `ipairs` for a table in `for` loops. The `__pairs` and `__ipairs` method work like standard iterator methods. Below is an example of a stateless iterator that behaves like the default `pairs` and `ipairs` iterators, but can be overridden to get loop behavior, such as filtering out values or looping through items in a different order.

```local M = {}

function M.__pairs(tbl)

-- Iterator function takes the table and an index and returns the next index and associated value
-- or nil to end iteration

local function stateless_iter(tbl, k)
local v
-- Implement your own key,value selection logic in place of next
k, v = next(tbl, k)
if nil~=v then return k,v end
end

-- Return an iterator function, the table, starting point
return stateless_iter, tbl, nil
end

function M.__ipairs(tbl)
-- Iterator function
local function stateless_iter(tbl, i)
-- Implement your own index, value selection logic
i = i + 1
local v = tbl[i]
if nil~=v then return i, v end
end

-- return iterator function, table, and starting point
return stateless_iter, tbl, 0
end

t = setmetatable({5, 6, a=1}, M)

for k,v in ipairs(t) do
print(string.format("%s: %s", k, v))
end
-- Prints the following:
-- 1: 5
-- 2: 6

for k,v in pairs(t) do
print(string.format("%s: %s", k, v))
end
-- Prints the following:
-- 1: 5
-- 2: 6
-- a: 1
```

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       !
```

Implementing custom looping behavior in Lua 5.1

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. Before Lua 5.2, 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
```

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
```
The problem with this is that the iterator appropriate to each type of table varies i.e. ipairs for array-like tables or pairs for dictionary-like tables. But if there was an `__iter` metamethod which was used directly by the generic `for` structure, then the appropriate iterator could be set for each table (or inherited in the class metatable for object oriented programming). In the simple cases the `__iter` metamethod would simply be set to the existing pairs or ipairs functions, but custom iterator factories could also be used were appropriate. Of course, this would involve a change to the language definition rather than just the standard libraries. However, this implementation would be backward compatible since if generic `for` saw a function in this site, it would use this as at present and ignore the metamethod. If it saw a table or a userdata, it would look for the `__iter` metamethod.

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?

-- 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