Numeric key collision related bug in Lua 5.3

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

Numeric key collision related bug in Lua 5.3

Egor Skriptunoff-2
Hi!

An interesting bug has been found in Lua 5.3

t = {[(1<<63)-333] = 0}
key = next(t) + 0.0
t[key] = "Lua is great!"
print(t[key])          --> Lua is great!
t[0] = "Are you sure?"
print(t[key])          --> nil

Why Lua is not great anymore?

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

Re: Numeric key collision related bug in Lua 5.3

Dirk Laurie-2
2015-04-21 17:32 GMT+02:00 Egor Skriptunoff <[hidden email]>:

> Hi!
>
> An interesting bug has been found in Lua 5.3
>
> t = {[(1<<63)-333] = 0}
> key = next(t) + 0.0
> t[key] = "Lua is great!"
> print(t[key])          --> Lua is great!
> t[0] = "Are you sure?"
> print(t[key])          --> nil
>
> Why Lua is not great anymore?

The manual says:

The indexing of tables follows the definition of raw equality in the
language. The expressions a[i] and a[j] denote the same table element
if and only if i and j are raw equal (that is, equal without
metamethods). In particular, floats with integral values are equal to
their respective integers (e.g., 1.0 == 1). To avoid ambiguities, any
float with integral value used as a key is converted to its respective
integer. For instance, if you write a[2.0] = true, the actual key
inserted into the table will be the integer 2. (On the other hand, 2
and "2" are different Lua values and therefore denote different table
entries.)

Let origkey = 1<<63)-333, which  is a very large integer, but slightly
smaller than math.maxinteger.

"key" is a float with integral value, but that integral value is not
origkey, but math.maxinteger. In a floating-point comparison, it tests
equal to origkey,
though.

When t[key] is assigned, "key" is not considered to be a new index, and
the value of t[origkey] is replaced.

When t[0] is assigned, the hash part of the table is reorganized.
t[origkey] is still "Lua is great!", but is no longer found when asking
for t[key].

Reply | Threaded
Open this post in threaded view
|

Re: Numeric key collision related bug in Lua 5.3

Dirk Laurie-2
2015-04-21 18:36 GMT+02:00 Dirk Laurie <[hidden email]>:

> 2015-04-21 17:32 GMT+02:00 Egor Skriptunoff <[hidden email]>:
>> An interesting bug has been found in Lua 5.3
>>
>> t = {[(1<<63)-333] = 0}
>> key = next(t) + 0.0
>> t[key] = "Lua is great!"
>> print(t[key])          --> Lua is great!
>> t[0] = "Are you sure?"
>> print(t[key])          --> nil
>>
>> Why Lua is not great anymore?
>
> The manual says:
>
> The indexing of tables follows the definition of raw equality in the
> language. The expressions a[i] and a[j] denote the same table element
> if and only if i and j are raw equal (that is, equal without
> metamethods). In particular, floats with integral values are equal to
> their respective integers (e.g., 1.0 == 1). To avoid ambiguities, any
> float with integral value used as a key is converted to its respective
> integer. For instance, if you write a[2.0] = true, the actual key
> inserted into the table will be the integer 2. (On the other hand, 2
> and "2" are different Lua values and therefore denote different table
> entries.)
>
> Let origkey = 1<<63)-333, which  is a very large integer, but slightly
> smaller than math.maxinteger.
>
> "key" is a float with integral value, but that integral value is not
> origkey, but math.maxinteger. In a floating-point comparison, it tests
> equal to origkey,
> though.
>
> When t[key] is assigned, "key" is not considered to be a new index, and
> the value of t[origkey] is replaced.
>
> When t[0] is assigned, the hash part of the table is reorganized.
> t[origkey] is still "Lua is great!", but is no longer found when asking
> for t[key].

I've been asking myself what in all this is a bug. And the answer has
nothing to do with tables.

origkey = (1<<63)-333
maxint = math.maxinteger
key = origkey + 0.
print (maxint == key ) --> true

I.e. a float that can be represented exactly as an integer is being
compared to an integer is being compared to another integer,
and tests equal even though those integers are different.

Somewhat surprisingly, this is in fact the documented behaviour.

| If both operands are integers, they are compared as integers;
| otherwise, they are converted to floats and compared as such.

The ideal solution would be to change the semantics to:

| If both operands are integers, or if one operand is a float but
| can be represented exactly as an integer, they are compared
| as integers; otherwise, they are converted to floats and
| compared as such.

But until such time as that is done, I submit that the "numeric
key collision related bug" is not a bug, but only a gotcha.

Reply | Threaded
Open this post in threaded view
|

Re: Numeric key collision related bug in Lua 5.3

Coda Highland
On Tue, Apr 21, 2015 at 11:54 AM, Dirk Laurie <[hidden email]> wrote:

> 2015-04-21 18:36 GMT+02:00 Dirk Laurie <[hidden email]>:
>> 2015-04-21 17:32 GMT+02:00 Egor Skriptunoff <[hidden email]>:
>>> An interesting bug has been found in Lua 5.3
>>>
>>> t = {[(1<<63)-333] = 0}
>>> key = next(t) + 0.0
>>> t[key] = "Lua is great!"
>>> print(t[key])          --> Lua is great!
>>> t[0] = "Are you sure?"
>>> print(t[key])          --> nil
>>>
>>> Why Lua is not great anymore?
>>
>> The manual says:
>>
>> The indexing of tables follows the definition of raw equality in the
>> language. The expressions a[i] and a[j] denote the same table element
>> if and only if i and j are raw equal (that is, equal without
>> metamethods). In particular, floats with integral values are equal to
>> their respective integers (e.g., 1.0 == 1). To avoid ambiguities, any
>> float with integral value used as a key is converted to its respective
>> integer. For instance, if you write a[2.0] = true, the actual key
>> inserted into the table will be the integer 2. (On the other hand, 2
>> and "2" are different Lua values and therefore denote different table
>> entries.)
>>
>> Let origkey = 1<<63)-333, which  is a very large integer, but slightly
>> smaller than math.maxinteger.
>>
>> "key" is a float with integral value, but that integral value is not
>> origkey, but math.maxinteger. In a floating-point comparison, it tests
>> equal to origkey,
>> though.
>>
>> When t[key] is assigned, "key" is not considered to be a new index, and
>> the value of t[origkey] is replaced.
>>
>> When t[0] is assigned, the hash part of the table is reorganized.
>> t[origkey] is still "Lua is great!", but is no longer found when asking
>> for t[key].
>
> I've been asking myself what in all this is a bug. And the answer has
> nothing to do with tables.
>
> origkey = (1<<63)-333
> maxint = math.maxinteger
> key = origkey + 0.
> print (maxint == key ) --> true
>
> I.e. a float that can be represented exactly as an integer is being
> compared to an integer is being compared to another integer,
> and tests equal even though those integers are different.
>
> Somewhat surprisingly, this is in fact the documented behaviour.
>
> | If both operands are integers, they are compared as integers;
> | otherwise, they are converted to floats and compared as such.
>
> The ideal solution would be to change the semantics to:
>
> | If both operands are integers, or if one operand is a float but
> | can be represented exactly as an integer, they are compared
> | as integers; otherwise, they are converted to floats and
> | compared as such.
>
> But until such time as that is done, I submit that the "numeric
> key collision related bug" is not a bug, but only a gotcha.
>

It won't be done. It would add load to the computational fast path
that isn't necessary in nearly all cases.

/s/ Adam

Reply | Threaded
Open this post in threaded view
|

Re: Numeric key collision related bug in Lua 5.3

Tim Hill
In reply to this post by Dirk Laurie-2

> On Apr 21, 2015, at 9:36 AM, Dirk Laurie <[hidden email]> wrote:
>
> 2015-04-21 17:32 GMT+02:00 Egor Skriptunoff <[hidden email]>:
>> Hi!
>>
>> An interesting bug has been found in Lua 5.3
>>
>> t = {[(1<<63)-333] = 0}
>> key = next(t) + 0.0
>> t[key] = "Lua is great!"
>> print(t[key])          --> Lua is great!
>> t[0] = "Are you sure?"
>> print(t[key])          --> nil
>>
>> Why Lua is not great anymore?
>
> The manual says:
>
> The indexing of tables follows the definition of raw equality in the
> language. The expressions a[i] and a[j] denote the same table element
> if and only if i and j are raw equal (that is, equal without
> metamethods). In particular, floats with integral values are equal to
> their respective integers (e.g., 1.0 == 1). To avoid ambiguities, any
> float with integral value used as a key is converted to its respective
> integer. For instance, if you write a[2.0] = true, the actual key
> inserted into the table will be the integer 2. (On the other hand, 2
> and "2" are different Lua values and therefore denote different table
> entries.)
>
> Let origkey = 1<<63)-333, which  is a very large integer, but slightly
> smaller than math.maxinteger.
>
> "key" is a float with integral value, but that integral value is not
> origkey, but math.maxinteger. In a floating-point comparison, it tests
> equal to origkey,
> though.
>
> When t[key] is assigned, "key" is not considered to be a new index, and
> the value of t[origkey] is replaced.
>
> When t[0] is assigned, the hash part of the table is reorganized.
> t[origkey] is still "Lua is great!", but is no longer found when asking
> for t[key].
>


Hmm this still looks like a bug to me. The entire hash/non-hash parts of tables are supposed to be purely implementation detail, yet here we are seeing the insertion of t[0] causing behavior changes to unrelated key(s). I’m not even sure what Lua is doing with that key, what does “float with integral value” mean for an integer that has no exact representation as a double-precision float (i.e. is > 2^52)?

nkey = (1<<63)-333
fkey = nkey + 0.0
print(fkey == nkey) -> true

t = {}
t[nkey] = “nkey”
t[fkey] = “fkey”
print(t[nkey], t[fkey]) -> “fkey” “fkey” — Expected based on equality check above

t[0] = 0
print(t[nkey], t[fkey]) -> “fkey” nil — Unexpected

—Tim





Reply | Threaded
Open this post in threaded view
|

Re: Numeric key collision related bug in Lua 5.3

Tim Hill

> On Apr 21, 2015, at 12:20 PM, Tim Hill <[hidden email]> wrote:
>
> Hmm this still looks like a bug to me. The entire hash/non-hash parts of tables are supposed to be purely implementation detail, yet here we are seeing the insertion of t[0] causing behavior changes to unrelated key(s). I’m not even sure what Lua is doing with that key, what does “float with integral value” mean for an integer that has no exact representation as a double-precision float (i.e. is > 2^52)?
>
> nkey = (1<<63)-333
> fkey = nkey + 0.0
> print(fkey == nkey) -> true
>
> t = {}
> t[nkey] = “nkey”
> t[fkey] = “fkey”
> print(t[nkey], t[fkey]) -> “fkey” “fkey” — Expected based on equality check above
>
> t[0] = 0
> print(t[nkey], t[fkey]) -> “fkey” nil — Unexpected
>
> —Tim
>

Contrast with this…

t = {}
t[fkey] = “fkey”
t[nkey] = “nkey”
print(t[nkey], t[fkey]) -> “nkey” “fkey” — Notice difference from previous example

t[0] = 0
print(t[nkey], t[fkey]) -> “nkey” “fkey” — Notice difference from previous example

This looks like a bug in how keys are checked for integral values, and isn’t related (so far as I can see) to the way Lua handles equality between values of different types.

—Tim


Reply | Threaded
Open this post in threaded view
|

Re: Numeric key collision related bug in Lua 5.3

Liam Devine
In reply to this post by Dirk Laurie-2
On 21/04/15 17:36, Dirk Laurie wrote:

>
> 2015-04-21 17:32 GMT+02:00 Egor Skriptunoff <[hidden email]>:
>> Hi!
>>
>> An interesting bug has been found in Lua 5.3
>>
>> t = {[(1<<63)-333] = 0}
>> key = next(t) + 0.0
>> t[key] = "Lua is great!"
>> print(t[key])          --> Lua is great!
>> t[0] = "Are you sure?"
>> print(t[key])          --> nil
>>
>> Why Lua is not great anymore?
>
> The manual says:
>
> The indexing of tables follows the definition of raw equality in the
> language. The expressions a[i] and a[j] denote the same table element
> if and only if i and j are raw equal (that is, equal without
> metamethods). In particular, floats with integral values are equal to
> their respective integers (e.g., 1.0 == 1). To avoid ambiguities, any
> float with integral value used as a key is converted to its respective
> integer. For instance, if you write a[2.0] = true, the actual key
> inserted into the table will be the integer 2. (On the other hand, 2
> and "2" are different Lua values and therefore denote different table
> entries.)
>
> Let origkey = 1<<63)-333, which  is a very large integer, but slightly
> smaller than math.maxinteger.
>
> "key" is a float with integral value, but that integral value is not
> origkey, but math.maxinteger. In a floating-point comparison, it tests
> equal to origkey,
> though.
>
> When t[key] is assigned, "key" is not considered to be a new index, and
> the value of t[origkey] is replaced.
>
> When t[0] is assigned, the hash part of the table is reorganized.
> t[origkey] is still "Lua is great!", but is no longer found when asking
> for t[key].
>
For me, there is a problem here and it seems to be with rawequal. What
does it mean to compare with rawequal? Well the manual says:

"Checks whether v1 is equal to v2, without invoking any metamethod.
Returns a boolean"

I think there is a standard definition of what equal means, but what
does it mean when you do not use a metamethod:

> return rawequal(1, 1)
true

> return rawequal(2.1, 2)
false

> return rawequal(2.1, 3.0)
false

OK it may seem a little silly but let us add max integer to the last one:

> return rawequal(math.maxinteger+2.1, math.maxinteger+3.0)
true

Hmm that doesn't seem very equal to me. As a consequence of this
equality you can not store more than one floating point number, as a
key, in a table when it is larger than maxinteger.

> t = {} for i = 1, 100 do t[math.maxinteger+(i+0.1)] = i end for k,v in
pairs(t) do print(k,v) end
9.2233720368548e+18 100


This is what the manual states about conversions:
Lua provides some automatic conversions between some types and
representations at run time. Bitwise operators always convert float
operands to integers. Exponentiation and float division always convert
integer operands to floats. All other arithmetic operations applied to
mixed numbers (integers and floats) convert the integer operand to a
float; this is called the usual rule. The C API also converts both
integers to floats and floats to integers, as needed.


So the "usaal rule" is not being used in rawequal, but the C API can do
as it likes when it is needed. Shouldn't rawequal explicitly state this
happens?

I would not have guessed that two floating point numbers greater than
maxinteger would ever compare equal when they are far enough apart to
detect a difference.

--
Liam


signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Numeric key collision related bug in Lua 5.3

Tim Hill
In reply to this post by Dirk Laurie-2

On Apr 21, 2015, at 9:36 AM, Dirk Laurie <[hidden email]> wrote:

The indexing of tables follows the definition of raw equality in the
language. The expressions a[i] and a[j] denote the same table element
if and only if i and j are raw equal (that is, equal without
metamethods). In particular, floats with integral values are equal to
their respective integers (e.g., 1.0 == 1). To avoid ambiguities, any
float with integral value used as a key is converted to its respective
integer. For instance, if you write a[2.0] = true, the actual key
inserted into the table will be the integer 2. (On the other hand, 2
and "2" are different Lua values and therefore denote different table
entries.)


nkey = (1<<63)-333
fkey = nkey + 0.0

Now, of course, nkey == fkey by the Lua rules of converting both to floats before doing the comparison. But is fkey a “float with integral value”? I dont think it is, and math.tointeger() doesn’t either (it returns nil).

The reality is Lua has three number ranges:
[a] Integers with a magnitude less than 2^52 (and can be represented exactly either as float or integer)
[b] Integers with magnitude greater than 2^52 but less than 2^63 (and can only be represented exactly as integers)
[c] Floats with magnitudes greater than 2^63

It’s the [b] range that is the problem here, and I don’t see any clear guidelines in the Lua docs to indicate how this range is handled when used as table keys.

—Tim

Reply | Threaded
Open this post in threaded view
|

Re: Numeric key collision related bug in Lua 5.3

Andrew Starks
On Tue, Apr 21, 2015 at 2:45 PM, Tim Hill <[hidden email]> wrote:

>
> On Apr 21, 2015, at 9:36 AM, Dirk Laurie <[hidden email]> wrote:
>
> The indexing of tables follows the definition of raw equality in the
> language. The expressions a[i] and a[j] denote the same table element
> if and only if i and j are raw equal (that is, equal without
> metamethods). In particular, floats with integral values are equal to
> their respective integers (e.g., 1.0 == 1). To avoid ambiguities, any
> float with integral value used as a key is converted to its respective
> integer. For instance, if you write a[2.0] = true, the actual key
> inserted into the table will be the integer 2. (On the other hand, 2
> and "2" are different Lua values and therefore denote different table
> entries.)
>
>
> nkey = (1<<63)-333
> fkey = nkey + 0.0
>
> Now, of course, nkey == fkey by the Lua rules of converting both to floats
> before doing the comparison. But is fkey a "float with integral value"? I
> dont think it is, and math.tointeger() doesn't either (it returns nil).
>
> The reality is Lua has three number ranges:
> [a] Integers with a magnitude less than 2^52 (and can be represented exactly
> either as float or integer)
> [b] Integers with magnitude greater than 2^52 but less than 2^63 (and can
> only be represented exactly as integers)
> [c] Floats with magnitudes greater than 2^63
>
> It's the [b] range that is the problem here, and I don't see any clear
> guidelines in the Lua docs to indicate how this range is handled when used
> as table keys.
>
> --Tim
>
I am following along, and not remotely qualified to participate as a
peer in this discussion. With that caveat established and given that
it is important to document and to know the limitations of the tool
that you are using, what are there substantive consequences beyond
that?

It would add tremendously to my understanding if someone someone would
make up a story that includes a user in a real-world scenario hitting
this edge case. Is there a story that could be imagined that includes
how this may be exploited by a nefarious user?



-Andrew

Reply | Threaded
Open this post in threaded view
|

Re: Numeric key collision related bug in Lua 5.3

Liam Devine
On 21/04/15 21:04, Andrew Starks wrote:

> It would add tremendously to my understanding if someone someone would
> make up a story that includes a user in a real-world scenario hitting
> this edge case. ...
>
>
>
> -Andrew
>

Correction to my earlier email a this does not just effect rawequal.

> a, b = math.maxinteger + 2.1, math.maxinteger + 3.5
> print(math.type(a), math.type(b))
float float
> return a == b
true



--
Liam


signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Numeric key collision related bug in Lua 5.3

Ross Berteig
In reply to this post by Andrew Starks

On 4/21/2015 1:04 PM, Andrew Starks wrote:
> On Tue, Apr 21, 2015 at 2:45 PM, Tim Hill <[hidden email]> wrote:
>>....
>> The reality is Lua has three number ranges:
>> [a] Integers with a magnitude less than 2^52 (and can be represented
 >> exactly either as float or integer)

>> [b] Integers with magnitude greater than 2^52 but less than 2^63
>> (and canonly be represented exactly as integers)
>> [c] Floats with magnitudes greater than 2^63
>>
>> It's the [b] range that is the problem here, and I don't see any
>> clear guidelines in the Lua docs to indicate how this range is
>> handled whenused as table keys.
>>....
> .... what are the substantive consequences beyond that?
>
> It would add tremendously to my understanding if someone someone would
> make up a story that includes a user in a real-world scenario hitting
> this edge case. Is there a story that could be imagined that includes
> how this may be exploited by a nefarious user?

One of the only reasons I've personally used floats for table keys has
been for memoization, where a table is used to cache results of (a
presumably expensive) calculation. Having different input values return
the same cache slot would be wrong, and likely very hard to debug.

IMHO, I would think that integers should only get floated implicitly (or
vice-versa) when that conversion can survive a round trip. Then whether
the key is "really" the integer or the float is purely an implementation
detail. Having a range of values which plainly compare different and
which are treated as the same key seems to violate the principle of
least surprise.

--
Ross Berteig                               [hidden email]
Cheshire Engineering Corp.           http://www.CheshireEng.com/


Reply | Threaded
Open this post in threaded view
|

Re: Numeric key collision related bug in Lua 5.3

Tim Hill
In reply to this post by Liam Devine

> On Apr 21, 2015, at 1:23 PM, Liam Devine <[hidden email]> wrote:
>
> On 21/04/15 21:04, Andrew Starks wrote:
>
>> It would add tremendously to my understanding if someone someone would
>> make up a story that includes a user in a real-world scenario hitting
>> this edge case. ...
>>
>>
>>
>> -Andrew
>>
>
> Correction to my earlier email a this does not just effect rawequal.
>
>> a, b = math.maxinteger + 2.1, math.maxinteger + 3.5
>> print(math.type(a), math.type(b))
> float float
>> return a == b
> true
>
>

This is expected behavior. math.maxinteger is 2^63-1. An IEEE754 double-precision float has 53 bits for the mantissa. Since your integer has a magnitude of approx 2^63, only the most significant 53 bits are stored (along with an appropriate exponent) and the lower 10 bits are lost to rounding errors (again, as expected). So the smallest delta that will actually generate a different float value is approx 2^10, or 1024..

mi = math.maxinteger
a, b = mi + 1024, mi + 2048
print(a==b) -> false

—Tim


Reply | Threaded
Open this post in threaded view
|

Re: Numeric key collision related bug in Lua 5.3

Andrew Starks
In reply to this post by Ross Berteig
On Tue, Apr 21, 2015 at 3:29 PM, Ross Berteig <[hidden email]> wrote:

>
> On 4/21/2015 1:04 PM, Andrew Starks wrote:
>>
>> On Tue, Apr 21, 2015 at 2:45 PM, Tim Hill <[hidden email]> wrote:
>>>
>>> ....
>>> The reality is Lua has three number ranges:
>>> [a] Integers with a magnitude less than 2^52 (and can be represented
>
>>> exactly either as float or integer)
>>>
>>> [b] Integers with magnitude greater than 2^52 but less than 2^63
>>> (and canonly be represented exactly as integers)
>>> [c] Floats with magnitudes greater than 2^63
>>>
>>> It's the [b] range that is the problem here, and I don't see any
>>> clear guidelines in the Lua docs to indicate how this range is
>>> handled whenused as table keys.
>>> ....
>>
>> .... what are the substantive consequences beyond that?
>>
>> It would add tremendously to my understanding if someone someone would
>> make up a story that includes a user in a real-world scenario hitting
>> this edge case. Is there a story that could be imagined that includes
>> how this may be exploited by a nefarious user?
>
>
> One of the only reasons I've personally used floats for table keys has
> been for memoization, where a table is used to cache results of (a
> presumably expensive) calculation. Having different input values return
> the same cache slot would be wrong, and likely very hard to debug.
>
> IMHO, I would think that integers should only get floated implicitly (or
> vice-versa) when that conversion can survive a round trip. Then whether
> the key is "really" the integer or the float is purely an implementation
> detail. Having a range of values which plainly compare different and
> which are treated as the same key seems to violate the principle of
> least surprise.
>
> --
> Ross Berteig                               [hidden email]
> Cheshire Engineering Corp.           http://www.CheshireEng.com/
>
>

Floats have  precision ceiling and floor. It's something that I have
spent a bit of time being frustrated over, as well (in a context that
is not related to table keys) and I think that it's established that
the issues are not related to Lua, specifically.

Is there an assertion that table keys represent a special case that
deserves a guard in the implementation? The motivation for my question
hopefully illustrated by a modification of Liam's example:

> mi = math.maxinteger
> a, b = mi +2.1, mi +3.5
> print(a,b)
9.2233720368548e+018    9.2233720368548e+018
> print(tostring(a), tostring(b))
9.2233720368548e+018    9.2233720368548e+018
> print(tostring(a) == tostring(b))
true


How could (or "Why should") Lua be made to treat a and be as two separate keys?

-- Andrew

Reply | Threaded
Open this post in threaded view
|

Re: Numeric key collision related bug in Lua 5.3

Coda Highland
In reply to this post by Liam Devine
On Tue, Apr 21, 2015 at 1:23 PM, Liam Devine <[hidden email]> wrote:

> On 21/04/15 21:04, Andrew Starks wrote:
>
>> It would add tremendously to my understanding if someone someone would
>> make up a story that includes a user in a real-world scenario hitting
>> this edge case. ...
>>
>>
>>
>> -Andrew
>>
>
> Correction to my earlier email a this does not just effect rawequal.
>
>> a, b = math.maxinteger + 2.1, math.maxinteger + 3.5
>> print(math.type(a), math.type(b))
> float   float
>> return a == b
> true
>
>
>
> --
> Liam
>

THIS isn't a bug. It's only tangentially related to the behaviors
under discussion. rawequal or not rawequal, this example is working as
intended.

/s/ Adam

Reply | Threaded
Open this post in threaded view
|

Re: Numeric key collision related bug in Lua 5.3

Tim Hill
In reply to this post by Tim Hill

On Apr 21, 2015, at 1:35 PM, Tim Hill <[hidden email]> wrote:


On Apr 21, 2015, at 1:23 PM, Liam Devine <[hidden email]> wrote:

On 21/04/15 21:04, Andrew Starks wrote:

It would add tremendously to my understanding if someone someone would
make up a story that includes a user in a real-world scenario hitting
this edge case. ...



-Andrew


Correction to my earlier email a this does not just effect rawequal.

a, b = math.maxinteger + 2.1, math.maxinteger + 3.5
print(math.type(a), math.type(b))
float float
return a == b
true



This is expected behavior. math.maxinteger is 2^63-1. An IEEE754 double-precision float has 53 bits for the mantissa. Since your integer has a magnitude of approx 2^63, only the most significant 53 bits are stored (along with an appropriate exponent) and the lower 10 bits are lost to rounding errors (again, as expected). So the smallest delta that will actually generate a different float value is approx 2^10, or 1024..

mi = math.maxinteger
a, b = mi + 1024, mi + 2048
print(a==b) -> false

—Tim

(Sorry, missed the “.0” in the two constants above, but you get my meaning I’m sure.)

In fact, consider the following:

c = 10.0e18
d = c
for i = 1,10000 do c = c + 100.0 end
print(c == d)

You can add 100.0 to c forever and it’s value will never change. Welcome to the world of limited precision floating point :)

—Tim

Reply | Threaded
Open this post in threaded view
|

Re: Numeric key collision related bug in Lua 5.3

Coda Highland
In reply to this post by Andrew Starks
On Tue, Apr 21, 2015 at 1:36 PM, Andrew Starks <[hidden email]> wrote:

> Is there an assertion that table keys represent a special case that
> deserves a guard in the implementation? The motivation for my question
> hopefully illustrated by a modification of Liam's example:
>
>> mi = math.maxinteger
>> a, b = mi +2.1, mi +3.5
>> print(a,b)
> 9.2233720368548e+018    9.2233720368548e+018
>> print(tostring(a), tostring(b))
> 9.2233720368548e+018    9.2233720368548e+018
>> print(tostring(a) == tostring(b))
> true
>
>
> How could (or "Why should") Lua be made to treat a and be as two separate keys?
>
> -- Andrew
>

This is a bit of a red herring.

Bringing the discussion back around to the actual issue: Remember that
what we're looking at is a case where they DO resolve as equal, yet DO
NOT yield the same table key.

Look back at Tim Hill's post earlier:

nkey = (1<<63)-333
fkey = nkey + 0.0
print(fkey == nkey)             -> true

t = {}
t[nkey] = “nkey”
t[fkey] = “fkey”
print(t[nkey], t[fkey]) -> “fkey” “fkey”                — Expected
based on equality check above

t[0] = 0
print(t[nkey], t[fkey]) -> “fkey” nil           — Unexpected

/s/ Adam

Reply | Threaded
Open this post in threaded view
|

Re: Numeric key collision related bug in Lua 5.3

Andrew Starks
On Tue, Apr 21, 2015 at 3:46 PM, Coda Highland <[hidden email]> wrote:

> nkey = (1<<63)-333
> fkey = nkey + 0.0
> print(fkey == nkey)             -> true
>
> t = {}
> t[nkey] = "nkey"
> t[fkey] = "fkey"
> print(t[nkey], t[fkey]) -> "fkey" "fkey"                -- Expected
> based on equality check above
>
> t[0] = 0
> print(t[nkey], t[fkey]) -> "fkey" nil           -- Unexpected

Thank you for your patience. What am I doing wrong here? I only get
expected behavior:

> nkey = (1<<63) - 333
> fkey = nkey + 0.0
> print(fkey == nkey)
true
> t = {[nkey] = 'nkey', [fkey] = 'fkey'}
> print(t[nkey], t[fkey])
nkey    fkey
> t[0] = 0
> print(t[nkey], t[fkey])
nkey    fkey
> t[nkey] = 'nkey'
> t[fkey] = 'fkey'
> print(t[nkey], t[fkey])
nkey    fkey
> t[0] = 0
> print(t[nkey], t[fkey])
nkey    fkey

Andrew

Reply | Threaded
Open this post in threaded view
|

Re: Numeric key collision related bug in Lua 5.3

Andrew Starks
On Tue, Apr 21, 2015 at 3:55 PM, Andrew Starks <[hidden email]> wrote:

> On Tue, Apr 21, 2015 at 3:46 PM, Coda Highland <[hidden email]> wrote:
>> nkey = (1<<63)-333
>> fkey = nkey + 0.0
>> print(fkey == nkey)             -> true
>>
>> t = {}
>> t[nkey] = "nkey"
>> t[fkey] = "fkey"
>> print(t[nkey], t[fkey]) -> "fkey" "fkey"                -- Expected
>> based on equality check above
>>
>> t[0] = 0
>> print(t[nkey], t[fkey]) -> "fkey" nil           -- Unexpected
>
> Thank you for your patience. What am I doing wrong here? I only get
> expected behavior:
>
>> nkey = (1<<63) - 333
>> fkey = nkey + 0.0
>> print(fkey == nkey)
> true
>> t = {[nkey] = 'nkey', [fkey] = 'fkey'}
>> print(t[nkey], t[fkey])
> nkey    fkey
>> t[0] = 0
>> print(t[nkey], t[fkey])
> nkey    fkey
>> t[nkey] = 'nkey'
>> t[fkey] = 'fkey'
>> print(t[nkey], t[fkey])
> nkey    fkey
>> t[0] = 0
>> print(t[nkey], t[fkey])
> nkey    fkey
>
> Andrew

ACK

sorry, i only get unexpected behavior. Okay. I'll fade back into the
background now, unless you can point out some other clue that you may
think would be helpful...

Reply | Threaded
Open this post in threaded view
|

Re: Numeric key collision related bug in Lua 5.3

Coda Highland
In reply to this post by Andrew Starks
On Tue, Apr 21, 2015 at 1:55 PM, Andrew Starks <[hidden email]> wrote:

> On Tue, Apr 21, 2015 at 3:46 PM, Coda Highland <[hidden email]> wrote:
>> nkey = (1<<63)-333
>> fkey = nkey + 0.0
>> print(fkey == nkey)             -> true
>>
>> t = {}
>> t[nkey] = "nkey"
>> t[fkey] = "fkey"
>> print(t[nkey], t[fkey]) -> "fkey" "fkey"                -- Expected
>> based on equality check above
>>
>> t[0] = 0
>> print(t[nkey], t[fkey]) -> "fkey" nil           -- Unexpected
>
> Thank you for your patience. What am I doing wrong here? I only get
> expected behavior:
>
>> nkey = (1<<63) - 333
>> fkey = nkey + 0.0
>> print(fkey == nkey)
> true
>> t = {[nkey] = 'nkey', [fkey] = 'fkey'}
>> print(t[nkey], t[fkey])
> nkey    fkey
>> t[0] = 0
>> print(t[nkey], t[fkey])
> nkey    fkey
>> t[nkey] = 'nkey'
>> t[fkey] = 'fkey'
>> print(t[nkey], t[fkey])
> nkey    fkey
>> t[0] = 0
>> print(t[nkey], t[fkey])
> nkey    fkey
>
> Andrew
>

You're getting different behavior because this misbehavior is
sensitive to the specific construction of the table. What you've
demonstrated here is that using the table constructor can result in a
different internal representation than using serial assignment -- a
fact that is already well-known, from many discussions regarding the
behavior of "array part" versus "hash part".

If you had reinitialized t to {} before the t[nkey] = 'nkey' line, you
would be more likely to see the behavior under discussion.

It may make a difference, too, if you used t = { [fkey] = 'fkey',
[nkey] = 'nkey' } as opposed to the ordering you have now.

/s/ Adam

Reply | Threaded
Open this post in threaded view
|

Re: Numeric key collision related bug in Lua 5.3

Liam Devine
In reply to this post by Tim Hill
On 21/04/15 21:42, Tim Hill wrote:

>
>> On Apr 21, 2015, at 1:35 PM, Tim Hill <[hidden email]
>> <mailto:[hidden email]>> wrote:
>>
>>>
>>> On Apr 21, 2015, at 1:23 PM, Liam Devine <[hidden email]
>>> <mailto:[hidden email]>> wrote:
>>>
>>> On 21/04/15 21:04, Andrew Starks wrote:
>>>
>>>> It would add tremendously to my understanding if someone someone would
>>>> make up a story that includes a user in a real-world scenario hitting
>>>> this edge case. ...
>>>>
>>>>
>>>>
>>>> -Andrew
>>>>
>>>
>>> Correction to my earlier email a this does not just effect rawequal.
>>>
>>>> a, b = math.maxinteger + 2.1, math.maxinteger + 3.5
>>>> print(math.type(a), math.type(b))
>>> floatfloat
>>>> return a == b
>>> true
>>>
>>>
>>
>> This is expected behavior. math.maxinteger is 2^63-1. An IEEE754
>> double-precision float has 53 bits for the mantissa. Since your
>> integer has a magnitude of approx 2^63, only the most significant 53
>> bits are stored (along with an appropriate exponent) and the lower 10
>> bits are lost to rounding errors (again, as expected). So the smallest
>> delta that will actually generate a different float value is approx
>> 2^10, or 1024..
>>
>> mi = math.maxinteger
>> a, b = mi + 1024, mi + 2048
>> print(a==b)-> false
>>
>> —Tim
>
> (Sorry, missed the “.0” in the two constants above, but you get my
> meaning I’m sure.)
>
> In fact, consider the following:
>
> c = 10.0e18
> d = c
> for i = 1,10000 do c = c + 100.0 end
> print(c == d)
>
> You can add 100.0 to c forever and it’s value will never change. Welcome
> to the world of limited precision floating point :)
>
> —Tim
>
I do get your point and it was silly of me to write such emails (I do
actually know how floating point numbers are stored, honest gov :p).
Sorry for the noise, I was not thinking straight.

--
Liam


signature.asc (836 bytes) Download Attachment
12