https://issues.dlang.org/show_bug.cgi?id=13420

Marc Schütz <schuetzm@gmx.net> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |schuetzm@gmx.net

--- Comment #1 from Marc Schütz <schuetzm@gmx.net> ---
Is that really supposed to work, given that NaN is defined not to be equal to anything, including itself?

--

https://issues.dlang.org/show_bug.cgi?id=13420

yebblies <yebblies@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |yebblies@gmail.com

--- Comment #2 from yebblies <yebblies@gmail.com> ---
Lol what exactly would this do, since NaN is not equal to itself?  I'd say the default equality function is not sufficient for AAs with floating point keys if NaN may be present.

--

https://issues.dlang.org/show_bug.cgi?id=13420

hsteoh@quickfur.ath.cx changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |hsteoh@quickfur.ath.cx

--- Comment #3 from hsteoh@quickfur.ath.cx ---
What *should* be the behaviour of an AA with a key type that can take on values that don't equal themselves?

Suppose you're given an opaque type K, and for all instances k1, k2 of K, k1 != k2 (even when k1 and k2 have the same binary representation)? Basically, the only sane way to store such keys in an AA would be to use its binary representation... but that breaks down as soon as K contains indirections. Should such key types even be valid AA keys??

Also, an AA with floating-point key also suffers from the problem that, unless you're expecting to look up the exact binary representation, it's effectively worthless (e.g., if 10.0 is a key in an AA, then I try to look up the result of some arbitrary computation that I expect to be equal to 10.0, then it may fail due to roundoff error during said computation). There is currently no such thing as approxEqual lookup of a floating-point AA key, so there is no way around this. (You'd have to use an interval tree or something like that instead.) So it would seem that when it comes to floating-point AA keys, we're really looking at dealing with the binary representation of the values, not the logical semantics of the values.

In this sense, I argue that existing code that uses floating-point AA keys is already broken -- recently, for example, there was a PR to make aa[0.0] the same thing as aa[-0.0]. Logically this may make sense, but then you have to deal with NaN being never equal to itself, and there's no way a generic AA implementation can deal with this satisfactorily (at least, not without breaking the IEEE floating-point semantics).

The only sensible solution I can see is to treat floating-point keys as their binary representations instead of their logical meaning, which means that aa[0.0] and aa[-0.0] should be distinct. Which would mean reopening the bug associated with the PR that treated 0.0 as equal to -0.0.

--

https://issues.dlang.org/show_bug.cgi?id=13420

--- Comment #4 from yebblies <yebblies@gmail.com> ---
(In reply to hsteoh from comment #3)
> What *should* be the behaviour of an AA with a key type that can take on values that don't equal themselves?

Exception.  Or assertion failure, depending on if we decide it's an input error or a program error.

> Suppose you're given an opaque type K, and for all instances k1, k2 of K, k1 != k2 (even when k1 and k2 have the same binary representation)? Basically, the only sane way to store such keys in an AA would be to use its binary representation... but that breaks down as soon as K contains indirections. Should such key types even be valid AA keys??

No.

> In this sense, I argue that existing code that uses floating-point AA keys is already broken -- recently, for example, there was a PR to make aa[0.0] the same thing as aa[-0.0]. Logically this may make sense, but then you have to deal with NaN being never equal to itself, and there's no way a generic AA implementation can deal with this satisfactorily (at least, not without breaking the IEEE floating-point semantics).

Having multiple keys compare as equal is fine, so long as the hash and comparison match.

> The only sensible solution I can see is to treat floating-point keys as their binary representations instead of their logical meaning, which means that aa[0.0] and aa[-0.0] should be distinct. Which would mean reopening the bug associated with the PR that treated 0.0 as equal to -0.0.

No, if somebody wants to use the binary rep of a floating point type as a key they should a) wrap it in a struct that explicitly overrides the hash and comparison or b) reinterpret cast it to a type that works that way.

--

https://issues.dlang.org/show_bug.cgi?id=13420

--- Comment #5 from Vladimir Panteleev <thecybershadow@gmail.com> ---
(In reply to hsteoh from comment #3)
> In this sense, I argue that existing code that uses floating-point AA keys is already broken -- recently, for example, there was a PR to make aa[0.0] the same thing as aa[-0.0]. Logically this may make sense, but then you have to deal with NaN being never equal to itself, and there's no way a generic AA implementation can deal with this satisfactorily (at least, not without breaking the IEEE floating-point semantics).
> 
> The only sensible solution I can see is to treat floating-point keys as their binary representations instead of their logical meaning, which means that aa[0.0] and aa[-0.0] should be distinct. Which would mean reopening the bug associated with the PR that treated 0.0 as equal to -0.0.

This is the behavior that my code was relying on. My project[1] was building a constant pool, and was relying on AAs doing bitwise hashing/comparison for doubles.

Of course, the work around was simple, but that doesn't change that this regression broke code that's out there.

I'm not going to argue which behavior is more correct or more useful, just pointing out that the old behavior did have a valid use case, and certainly wasn't broken.

  [1]: https://github.com/CyberShadow/RABCDAsm

--

https://issues.dlang.org/show_bug.cgi?id=13420

--- Comment #6 from Vladimir Panteleev <thecybershadow@gmail.com> ---
Maybe the AA implementation should assert that keys added to it should be equal to themselves. That would make the problem easier to spot, at least (in my case it caused the output to be incorrect).

--

https://issues.dlang.org/show_bug.cgi?id=13420

Steven Schveighoffer <schveiguy@yahoo.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |schveiguy@yahoo.com

--- Comment #7 from Steven Schveighoffer <schveiguy@yahoo.com> ---
(In reply to Vladimir Panteleev from comment #6)
> Maybe the AA implementation should assert that keys added to it should be equal to themselves. That would make the problem easier to spot, at least (in my case it caused the output to be incorrect).

Yeah, possibly a good solution. But I think we should not pay the runtime penalty for this rare situation (every access using every key type must be checked). I actually think the current breakage of code is warranted, and this is not going to cause a lot of problems (I would guess not many use nan keys).

Incidentally, typeid(float).compare is broken.

Observe:

    float a, b=1;                              // a = nan
    assert(!(a < b));                          // test 1
    assert(typeid(float).compare(&a, &b) < 0); // test 2

>From the definition of opCmp, this implies that from the result of test 1, test
2 should fail (compare(&a, &b) should be >= 0). In fact, I fully expected
compare(&a, &b) to be 0.

So your code only worked because:
a) the old AA implementation assumed compare(a, b) == 0 means equality (and as
has been discussed in the NG, this is not the case)
b) float.compare(x, y) can return -1 or 1 even when x or y is inf or nan!

I think we need another bug report for b)... (will add)

--

https://issues.dlang.org/show_bug.cgi?id=13420

--- Comment #8 from Vladimir Panteleev <thecybershadow@gmail.com> ---
(In reply to Steven Schveighoffer from comment #7)
> every access using every key type must be checked

Only insertion, and only in non-release mode.

--

https://issues.dlang.org/show_bug.cgi?id=13420

--- Comment #9 from Steven Schveighoffer <schveiguy@yahoo.com> ---
(In reply to Vladimir Panteleev from comment #8)
> (In reply to Steven Schveighoffer from comment #7)
> > every access using every key type must be checked
> 
> Only insertion, and only in non-release mode.

Well, if we do it only on insertion, that may work. Actually that's a pretty good idea, because you are already incurring the cost of adding a node, potentially rehashing, doing a quick comparison of a key to itself isn't going to be significant. And you only pay once per element in the AA, not once per access. But I think "only in non-release mode" is not possible -- AA's are (at least currently) runtime based, so you would need a non-release version of druntime to get it to catch your error.

Even if they were switched to a library template, you would potentially have already-compiled AA inside phobos which would be release mode. We could potentially just ensure that X[float] never occurs in phobos.

But are we fixing a problem that is not widespread or significant? I still am skeptical that there are many AAs that depend on nan for a key, and any which did so is fundamentally flawed and depending on incorrect compare implementation.

--

https://issues.dlang.org/show_bug.cgi?id=13420

Martin Nowak <code@dawg.eu> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |code@dawg.eu
         Resolution|---                         |WONTFIX

--- Comment #10 from Martin Nowak <code@dawg.eu> ---
> Maybe the AA implementation should assert that keys added to it should be equal to themselves.

Sorry for breaking your code, but this check seems exaggerated.
An AA implementation has to rely on a working equality comparison and hash.

As floats are builtin types we should special case the AA implementation to
perform some extra checks, e.g. disallow NaN as key value.
See bug 13581 for an enhancement request.

> b) float.compare(x, y) can return -1 or 1 even when x or y is inf or nan!
> 
> I think we need another bug report for b)... (will add)

Reference?

--