table.remove behavior?

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

table.remove behavior?

Paul Chiusano-3
I don't think that table.remove works correctly for tables which have
nil at their start. Sometimes it works, sometimes it doesn't. Here's
an example I could find which fails:

> a = {}; for i=1,100 do a[i] = i end
> -- add some nils to the front
> for i=1,75 do a[i] = nil end
> table.remove(a, 97)
> print(a[97]) -- should be 98, right?
97

Okay, looking at the code for table.remove, I think I see what's happening:

static int tremove (lua_State *L) {
  int e = aux_getn(L, 1);
  int pos = luaL_optint(L, 2, e);
  if (e == 0) return 0;  /* table is `empty' */
  luaL_setn(L, 1, e - 1);  /* t.n = n-1 */
  lua_rawgeti(L, 1, pos);  /* result = t[pos] */
  for ( ;pos<e; pos++) {     /* aha! this loop may not execute,
depending on whether
                                                the getn function returns. */
    lua_rawgeti(L, 1, pos+1);
    lua_rawseti(L, 1, pos);  /* t[pos] = t[pos+1] */
  }
  lua_pushnil(L);
  lua_rawseti(L, 1, e);  /* t[e] = nil */
  return 1;
}

What about using the first encountered nil as the halting condition
for the loop? That would always work. Here it is in Lua:

function table.remove(t, ind)
  local next
  repeat
     next = t[ind+1]
     t[ind] = next
     pos = pos+1
   until next==nil
end

Even if the behavior is not changed, I'd like to see a stronger
warning that table.remove relies on the length of the table being
tracked correctly.

Here's what the ref manual says currently:
"
Removes from table the element at position pos, shifting down other
elements to close the space, if necessary. Returns the value of the
removed element. The default value for pos is n, where n is the length
of the table, so that a call table.remove(t) removes the last element
of table t.
"

What about adding something like: 'table.remove relies on the length
of the table being tracked correctly, even when an explicit index is
specified. Thus, it may not work as expected if a table contains any
nil values.'

Best,
Paul
Reply | Threaded
Open this post in threaded view
|

Re: table.remove behavior?

Paul Chiusano
Oops, that should have been:

function table.remove(t, ind)
  local next
  repeat
     next = t[ind+1]
     t[ind] = next
     ind = ind+1
   until next==nil
end

-Paul
Reply | Threaded
Open this post in threaded view
|

RE: table.remove behavior?

Jerome Vuarand-2
In reply to this post by Paul Chiusano-3
I think the problem is that you consider a table with some nil at low numeric indices to be an array. An array in lua is (a Lua guru should check this) a table with increasing contiguous integer indices starting at one (1). If you set a[1] to nil you reduce array size to 0 (as a call to #a would tell you). So there is no more position 97, and so table.remove(a, 97) should do nothing, and thus let a[97] where it is.

Considering an array stops at the first nil integer index is an important part of the lua array concept, and it can't be changed I think. Many code using both hashmap and array concept on same tables would break.

Doub.

-----Message d'origine-----
De : [hidden email] [mailto:[hidden email]] De la part de Paul Chiusano
Envoyé : 19 mars 2006 11:58
À : Lua list
Objet : table.remove behavior?

I don't think that table.remove works correctly for tables which have nil at their start. Sometimes it works, sometimes it doesn't. Here's an example I could find which fails:

> a = {}; for i=1,100 do a[i] = i end
> -- add some nils to the front
> for i=1,75 do a[i] = nil end
> table.remove(a, 97)
> print(a[97]) -- should be 98, right?
97

Okay, looking at the code for table.remove, I think I see what's happening:

static int tremove (lua_State *L) {
  int e = aux_getn(L, 1);
  int pos = luaL_optint(L, 2, e);
  if (e == 0) return 0;  /* table is `empty' */
  luaL_setn(L, 1, e - 1);  /* t.n = n-1 */
  lua_rawgeti(L, 1, pos);  /* result = t[pos] */
  for ( ;pos<e; pos++) {     /* aha! this loop may not execute,
depending on whether
                                                the getn function returns. */
    lua_rawgeti(L, 1, pos+1);
    lua_rawseti(L, 1, pos);  /* t[pos] = t[pos+1] */
  }
  lua_pushnil(L);
  lua_rawseti(L, 1, e);  /* t[e] = nil */
  return 1;
}

What about using the first encountered nil as the halting condition for the loop? That would always work. Here it is in Lua:

function table.remove(t, ind)
  local next
  repeat
     next = t[ind+1]
     t[ind] = next
     pos = pos+1
   until next==nil
end

Even if the behavior is not changed, I'd like to see a stronger warning that table.remove relies on the length of the table being tracked correctly.

Here's what the ref manual says currently:
"
Removes from table the element at position pos, shifting down other elements to close the space, if necessary. Returns the value of the removed element. The default value for pos is n, where n is the length of the table, so that a call table.remove(t) removes the last element of table t.
"

What about adding something like: 'table.remove relies on the length of the table being tracked correctly, even when an explicit index is specified. Thus, it may not work as expected if a table contains any nil values.'

Best,
Paul
Reply | Threaded
Open this post in threaded view
|

Re: table.remove behavior?

Paul Chiusano
> Considering an array stops at the first nil integer index is an important part of the lua array concept, and it can't be changed I think. Many code using both hashmap and array concept on same tables would break.

All I am saying is to change how table.remove works. I believe the
change is completely backwards compatible. Here's my proposal again:

function table.remove(t, ind)
 local next
 repeat
    next = t[ind+1]
    t[ind] = next
    ind = ind+1
  until next==nil
end

Here is my reasoning for why this proposed version is backwards compatible:

If you were using a table as a mapping, where the keys just so
happened to be integers, you would not use table.remove to remove
entries, you would just do t[ind] = nil (doing otherwise would be a
serious misuse of table.remove!). If you are using a table as both a
hashmap and an array at the same time, well, that code would not be
affected by changing how table.remove works either. There's two cases:

1) The 'map' part uses non-integer keys. This would not be affected by
changing table.remove, since table.remove (both versions) only modify
integer-keyed entries.
2) The 'map' part uses integer keys. There are two sub-cases:
2.1) There is a 'gap' between the array part and the map part: {1,2,3;
[5]='a',[6]='b'}. In this case, the table.remove behavior I propose
will not affect the map part (keys 5 and 6), which is identical to the
behavior now.
2.2) There is no gap between the array part and the map part:
t={1,2,3; [4]='a',[5]='b'}. Again this gives the same behavior as now
-- the current table.remove(t, 3) will shift [4]='a' and [5]='b' down
regardless of whether the program intended for the 'a' and 'b' to be
considered part of the 'map' part of the table. The version I am
proposing will do the same.

If table.setn were still available, then the 2.2 case could return
different results, since one could explicitly say where the array part
ended. But as far as I can tell, there is no longer any way to do that
- table.setn throws an error in 5.1, and setting t.n has no effect and
is ignored by both table.getn and the # operator.

So, unless there is some other hidden way of affecting what is
returned by table.getn that I am not aware of, this change would not
break any existing 5.1 code and has the benefit of making it easier to
work with tables as double-ended queues (see
http://www.lua.org/pil/11.4.html ).

I was using a table in this way and checked to see if table.remove
worked correctly when the table had nils at the front. It did--for the
tests I ran. Then a bizarre bug cropped up in my program and I finally
tracked it down to table.remove not working as expected!

-Paul