Re: Bug report in length of simple table

[Miroslav Janíček <mira.janicek@...>]

> On 15 Sep 2016, at 0:15, Ross Berteig <Ross@CheshireEng.com> wrote:
> 
> On 9/14/2016 2:16 PM, Miroslav Janíček wrote:
>>> On 14 Sep 2016, at 16:04, Roberto Ierusalimschy <roberto@inf.puc-rio.br> wrote:
>>> ...
>>> Note that any table has at least one border.
>>> Note also that keys that are not a non-negative integer
>>> do not interfere with the notion of borders.
>> 
>> Are these two notes correct?
>> 
>> It seems to me that a table with non-nil values for all positive
>> integer keys {1 … math.maxinteger}, *and* a non-nil value for the key
>> (math.maxinteger + 1) would not have a border.
> 
> I'm not sure there are practical versions of Lua where that table could actually exist. It would have to be built with a small enough integer type that a table with half of all possible integral keys could fit within (virtual) memory.

Bah, that’s an implementation detail ;)

But you’re of course right — we probably won’t see systems that could handle such tables for 64-bit integers in our lifetimes. However, I think it’s perfectly possible to have such a table with 32-bit integers, even today.

 (As a side note: in my reading of the Lua Reference
  Manual I haven’t been able to conclusively discard the
  possibility that computing sequence length involves
  invoking the __index metamethod. I know it sounds silly,
  but I think that a Lua implementation that would do that
  would still be “legal” according to the manual. Now, in
  such an implementation, the __index metamethod

  function (t, k) if k > 0 then return k; else return nil; end end

  would do the trick for any integer width.)

But anyway, that wasn’t really the point. The point is that under this definition, it seems that there exists a sequence that does not have a length.

I think the fix could be quite simple, along the following lines:

 * if t[1] == nil, then 0 is a border;
 * let MAX be the maximum value for an integer, then MAX
   is a border if t[MAX] ~= nil;
 * for all positive integers i, if t[i] ~= nil and t[i+1] == nil,
   then i is a border.

Plus: a table is a sequence if and only if it has exactly one border.

> That said, I'm not certain that the definition of sequence cares about whether the keys are specifically integer type numbers. So the number math.maxinteger will be 2^63-1, and 2^63 can be exactly represented in 64-bit float. 2^63+1 cannot, and that is probably where the fuzzy non-border happens.

I must admit I’m not exactly sure what you mean. Suppose the table contains a non-nil value for the key with the mathematical value of 2^63 (a float), and a non-nil value for (2^63 - 1). Should (2^63 - 1) be a border?

  M.