Bug 13179 – AA key type TagIndex now requires equality rather than comparison

Building Tango with 2.066.0-b5 results in the following error: tango/text/Regex.d(2532): Error: AA key type TagIndex now requires equality rather than comparison tango/text/Regex.d(2532): Please define opEquals, or remove opCmp to also rely on default memberwise comparison. I can see that opEquals should be used and not opCmp for AA keys, but if opCmp is defined, why doesn't the compiler automatically generate opEquals that calls opCmp?

Reduced test case: struct TagIndex { uint tag, index; const int opCmp(ref const TagIndex o) { if (tag == o.tag && index == o.index) return 0; if (tag > o.tag) return 1; if (tag < o.tag) return -1; if (index > o.index) return 1; if (index < o.index) return -1; assert(0); } } int[TagIndex] a;

(In reply to Jacob Carlborg from comment #0) > Building Tango with 2.066.0-b5 results in the following error: > > tango/text/Regex.d(2532): Error: AA key type TagIndex now requires equality > rather than comparison > tango/text/Regex.d(2532): Please define opEquals, or remove opCmp to > also rely on default memberwise comparison. > > I can see that opEquals should be used and not opCmp for AA keys, but if > opCmp is defined, why doesn't the compiler automatically generate opEquals > that calls opCmp? It's intended behavior, because compiler cannot know whether the generated opEquals is what programmer is expecting. (In reply to Jacob Carlborg from comment #1) > Reduced test case: > > struct TagIndex > { > uint tag, index; > > const int opCmp(ref const TagIndex o) > { [snip] > } > } > > int[TagIndex] a; In D, all struct define default member-wise equality for == operator. TagIndex t1, t2; // t1 == t2 will be rewritten as: // t1.tupleof == t2.tupleof // and then it will mean: // t1.tag == t2.tag && t1.index == t2.index If TagIndex is used for AA keys, compiler cannot determine which is the intended 'equality', t1 == t2 or t1.opCmp(t2) == 0. So compiler requests you to resolve the ambiguity by defining opEquals or removing opCmp.

(In reply to Kenji Hara from comment #2) > If TagIndex is used for AA keys, compiler cannot determine which is the > intended 'equality', t1 == t2 or t1.opCmp(t2) == 0. opCmp includes an equality, this means the programmer has defined an equality too. So can't we assume that the equality is "t1.opCmp(t2) == 0" when the user defines just opCmp?

(In reply to Kenji Hara from comment #2) [...] > It's intended behavior, because compiler cannot know whether the generated > opEquals is what programmer is expecting. [...] That doesn't make sense. The programmer has already defined opCmp, which means "a == b" is already compiled to be "a.opCmp(b)==0". Therefore, if the programmer didn't define opEquals, it should simply default to: ---- bool opEquals(T b) { return a.opCmp(b)==0; } ---- By your logic, the compiler should reject "a == b" when the programmer hasn't defined opEquals, because the compiler cannot know whether a.opCmp(b)==0 is what the programmer is expecting. I don't understand how this could make any sense.

(In reply to Kenji Hara from comment #2) > It's intended behavior, because compiler cannot know whether the generated > opEquals is what programmer is expecting. As others have already said, if opCmp is defined then the compiler can generate opEquals that calls opCmp. > In D, all struct define default member-wise equality for == operator. > > TagIndex t1, t2; > // t1 == t2 will be rewritten as: > // t1.tupleof == t2.tupleof > // and then it will mean: > // t1.tag == t2.tag && t1.index == t2.index > > If TagIndex is used for AA keys, compiler cannot determine which is the > intended 'equality', t1 == t2 or t1.opCmp(t2) == 0. > > So compiler requests you to resolve the ambiguity by defining opEquals or > removing opCmp. opCmp was added because of a regression in 2.065.0 and now it's changed again.

(In reply to Jacob Carlborg from comment #5) > opCmp was added because of a regression in 2.065.0 and now it's changed > again. So you can just remove opCmp completely. For the struct struct TagIndex { uint tag, index; } In 2.066 AA will use default member-wise equality and hasing.

(In reply to bearophile_hugs from comment #3) > opCmp includes an equality, this means the programmer has defined an > equality too. So can't we assume that the equality is "t1.opCmp(t2) == 0" > when the user defines just opCmp? But currently `a == b` is never rewritten to `a.opCmp(b) == 0`. It's in a domain of enhancement request that requires more discussion. (In reply to hsteoh from comment #4) > By your logic, the compiler should reject "a == b" when the programmer > hasn't defined opEquals, because the compiler cannot know whether > a.opCmp(b)==0 is what the programmer is expecting. I don't understand how > this could make any sense. It's not a logic issue. If opCmp is defined and `a == b` will be automatically rewritten to `a.opCmp(b) == 0`, the code behavior will be _silently_ changed. So compiler reports a diagnostic error. It's far better than silent changing.

(In reply to Kenji Hara from comment #7) [...] > But currently `a == b` is never rewritten to `a.opCmp(b) == 0`. It's in a > domain of enhancement request that requires more discussion. Wait, wat?? That's ridiculous... I think this is a bug. If I define opCmp, then a==b should work even if I don't define opEquals. Otherwise this leads to the current ridiculous situation: ------ struct S { int x; int y; int opCmp(S s) { return x - s.x; } } void main() { auto s1 = S(1,2); auto s2 = S(1,3); auto s3 = S(2,1); assert(s1 < s3); // OK assert(s2 < s3); // OK assert(s3 > s1); // OK assert(s3 > s2); // OK assert(s1 <= s2 && s2 >= s1); // OK assert(s1 == s2); // FAIL } ------ The last two lines show that s1<=s2 && s1>=s2 does not imply s1==s2. I find that difficult to accept. I think this needs to be fixed. > (In reply to hsteoh from comment #4) > > By your logic, the compiler should reject "a == b" when the programmer > > hasn't defined opEquals, because the compiler cannot know whether > > a.opCmp(b)==0 is what the programmer is expecting. I don't understand how > > this could make any sense. > > It's not a logic issue. If opCmp is defined and `a == b` will be > automatically rewritten to `a.opCmp(b) == 0`, the code behavior will be > _silently_ changed. > > So compiler reports a diagnostic error. It's far better than silent changing. I think that any code depends on the fact that s1<=s2 && s1>=s2 doesn't imply s1==s2, is already horribly broken.

I would not expect `a == b` to _ever_ be converted to `a.opCmp(b) == 0`. That's what opEquals is for. However, I also wouldn't expect declaring opCmp to make it so that the compiler no longer generates an opEquals for the struct. The compiler should either continue to declare the opEquals or make it an error if you define opCmp but not opEquals. It makes no sense whatsoever to have a type which is comparable with <, <=, >=, and > but not ==. And it should _always_ be considered a bug if `a.opCmp(b) == 0` is not equivalent to `a == b` or if `a <= b && a >= b` is not equivalent to `a == b`.

(In reply to Jonathan M Davis from comment #9) > I would not expect `a == b` to _ever_ be converted to `a.opCmp(b) == 0`. > That's what opEquals is for. Why? When opCmp returns zero it means ==. What's wrong about using that possible return value to test for equality?

(In reply to bearophile_hugs from comment #10) > (In reply to Jonathan M Davis from comment #9) > > I would not expect `a == b` to _ever_ be converted to `a.opCmp(b) == 0`. > > That's what opEquals is for. > > Why? When opCmp returns zero it means ==. What's wrong about using that > possible return value to test for equality? It's an unnecessary efficiency hit. The language has opEquals for a reason, and it's defined by the language to be ==, whereas opCmp is for <, <=, >=, and >. And code really shouldn't be calling opEquals or opCmp directly except under very rare circumstances. They're for generating overloaded operators, not for calling as normal functions. I can see an argument for just continuing to have the compiler define == when opCmp is defined in order to avoid having to declare opEquals as well when the default would be fine, and I can see an argument that opEquals should be explicitly defined in that case in order to reduce the odds of there being a bug when someone defined opCmp in a way that was inconsistent with the built in opEquals. But opEquals is what's supposed to be defining equality. That's what it's _for_. That's not opCmp's job.

(In reply to Jonathan M Davis from comment #11) [...] > And code really shouldn't be calling opEquals or opCmp directly > except under very rare circumstances. They're for generating overloaded > operators, not for calling as normal functions. Nobody is talking about calling opCmp or opEquals directly here. The issue here is that == does not behave consistently with <, <=, >=, > when the user defines opCmp (but not opEquals). Either we should *reject* such code (i.e., the user must always explicitly define opEquals if opCmp is defined), or we should do the Right Thing, that is, make opEquals the same as opCmp()==0.

(In reply to hsteoh from comment #12) > Nobody is talking about calling opCmp or opEquals directly here. The issue > here is that == does not behave consistently with <, <=, >=, > when the user > defines opCmp (but not opEquals). Either we should *reject* such code (i.e., > the user must always explicitly define opEquals if opCmp is defined), or we > should do the Right Thing, that is, make opEquals the same as opCmp()==0. I'd be in favor of either making it an error to define opCmp but not opEquals, letting the programmer just screws themselves if they define opCmp so that it doesn't match the compiler-generated opEquals, and they don't define opEquals themselves (which would basically be the same as if they defined both but didn't make them consistent). The advantage of not requiring that opEquals be defined and still using the default one is that you wouldn't have to define opEquals just because you defined opCmp when the default opEquals did what you wanted (which it probably does in the majority of cases). The advantage of requiring opEquals is that it makes it clear that the programmer needs to make sure that opCmp is consistent with opEquals, but it doesn't necessarily make it less error-prone, because the programmer then needs to define opEquals to be equivalent to a.opCmp(b) == 0, and they can screw that up, so there's no guarantee that a.opCmp(b) == 0 is equivalent to opEquals, even if it's supposed to be. And they're probably _more_ likely to define opEquals incorrectly than the default one if what they want is what the default one does (also, they'd generally lose out on whatever efficiency gains the default one might have if they define it themselves). Using a.opCmp(b) == 0 for opEquals if opEquals isn't defined would guarantee correctness, but it would incur a performance hit, and I'm willing to bet that a lot of folks would expect the normal, compiler-generated opEquals to still be generated even when opCmp is declared (I certainly would have), so they wouldn't realize that they were getting a performance hit. And those that didn't think it through even that far wouldn't know about the performance hit either. And there's toHash to consider as well. It needs to be consistent with opEquals, and it won't be if opEquals is defined by the user but not toHash - making it so that toHash should probably be required by the AA to be explicitly defined by the type if opEquals has been declared and so that if toHash is declared, opEquals should be required. Regardless, there is no option in that case to use another function to guarantee correctness (as you can do by using opCmp for opEquals). So, we _still_ require correctness of the user. Also, if the compiler-generate opEquals is used when opCmp is declared, then the compiler-generated toHash can still be used, whereas if a.opCmp(b) == 0 were used for opEquals, then toHash would have to be defined. So, I think that we really should just use the compiler-generate opEquals unless the programmer defines opEquals themselves, even if opCmp is declared, and the compiler-generate toHash should be used if the compiler-generated opEquals is used, whereas it can't be otherwise. The programmer will just have to make sure that a.opCmp(b) == 0 is equivalent to opEquals if they don't want bugs. They should be unit testing that anyway.

I think the toHash issue is really only applicable if you try to use your type as an AA key. If you never use it as an AA key, there's no reason to require the user to define toHash just because they defined their own opEquals. AFAIK the latest dmd git HEAD will reject using types as AA keys if they define one of toHash/opEquals but not both. So either you don't define either and get the default implementations, or you define both and the onus is on you to make them consistent with each other. The compiler rejects the code if you define one but not the other, which makes sense. But there's no reason to require toHash to be defined if the user never tries to use it as an AA key, even if they define opEquals.

(In reply to hsteoh from comment #14) > But there's no reason to require toHash to be defined if the user never > tries to use it as an AA key, even if they define opEquals. Agreed. I don't think that I said otherwise. What I was trying to point out that is if you define opEquals, then if you use the type with an AA, then you're going to need to define toHash as well. So, forcing the user to define opEquals simply because they defined opCmp potentially forces them to define toHash. And if the compiler-generate opEquals and toHash would have been consistent with opCmp, then having to define them just increases the risk that you're going to screw up defining them (particular toHash). What it would mean would be that any type that you wanted to use as an AA key that defined opCmp (as was previously required) would then have to define opEquals and toHash as well even if it shouldn't be necessary. So, I favor just having the compiler continue to generate opEquals and toHash even if opCmp is defined. If opCmp is not consistent with opEquals, then that's a bug, and the programmer will need to either fix opCmp or define opEquals (and toHash if using AAs) so that it's consistent with opCmp. Requiring that the user define opEquals won't necessarily make it less likely to be inconsistent with opCmp, because then instead of relying on the built-in opEquals in the cases where it would have been fine, you'd then have to define it and would potentially screw it up. And if they both need to be defined in order to be consistent, then it's always up to the programmer to get it right anyway. But I think that making it so that defining opCmp results in opEquals being generated as a.opCmp(b) == 0 is pernicious, because it's a hidden performance hit.

How about this, the programmer has to declare opEquals if they define opCmp (in order to force the programmer to be aware of the problem and choose how opEquals should work), but we provide a way to tell the compiler to use the default opEquals rather than forcing the programmer to define their own. e.g. something like struct S { bool opEquals(S s) = default; int opCmp()(auto ref S s) {...} } The same with toHash so that the programmer doesn't have to define that just because they defined opEquals in the cases where the default would work. I believe that C++11 did something like this. By doing this, we force the programmer to consider it but don't force them to define opEquals or toHash themselves when the defaults should work. Regardless, if the programmer wants opEquals to just call opCmp, I think that they should have to define that themselves, since having the compiler do it would incur a silent performance hit. At least the definition is short and easy: bool opEquals()(auto ref S s) { return opCmp(s) == 0; }

(In reply to Kenji Hara from comment #6) > So you can just remove opCmp completely. For the struct > > struct TagIndex > { > uint tag, index; > } > > In 2.066 AA will use default member-wise equality and hasing. My point was that it was a regression _again_. This time DMD changes back and forwards between different versions. Add a function to workaround a regression, then remove it in the next release because of regression again. Walter keeps talking about we should not make regressions and then someone goes and does this.

(In reply to Jonathan M Davis from comment #15) > Agreed. I don't think that I said otherwise. What I was trying to point out > that is if you define opEquals, then if you use the type with an AA, then > you're going to need to define toHash as well. So, forcing the user to > define opEquals simply because they defined opCmp potentially forces them to > define toHash. And if the compiler-generate opEquals and toHash would have > been consistent with opCmp, then having to define them just increases the > risk that you're going to screw up defining them (particular toHash). What > it would mean would be that any type that you wanted to use as an AA key > that defined opCmp (as was previously required) would then have to define > opEquals and toHash as well even if it shouldn't be necessary. That's how the current behavior in 2.066.0-b5 is. If opCmp is defined and the type is used as an AA key the compiler will force you to defined opEquals as well. And if opEquals is defined the compiler will require you to define toHash as well. I'm guessing this is to ease the transition from opCmp being used for AA keys to opEquals.

Okay. Clearly, I was not paying enough attention to what was going on here. It always has been the case that opEquals is generated for for structs, if you don't define it. That hasn't changed for 2.066. Rather, in the case where you try and use it as an AA key, it now screams at you for not having defined opEquals, even though the default opEquals was almost certainly fine, because that's what was being used. It's a major bug IMHO if lhs.opCmp(rhs) == 0 is not equivalent to lhs == rhs, so if we change the AAs to use opEquals but do not give the error that we're currently giving, then all we'd be doing is exposing an existing bug in someone's code, and that bug probably exists elsewhere in their code, since they probably use opEquals with their keys _somewhere_. And it seems kind of messed up to me to require that opEquals be defined just because you're using an AA when the default opEquals already does the right thing. IMHO, we should either require that opEquals be defined in general if opCmp is defined (which I think is a bad idea), or we should just use the default opEquals with AAs without complaining about it (much better idea IMHO). The only code that would be negatively affected is already broken anyway. But requiring folks to define opEquals instead of using the perfectly good default just because they're using an AA seems very wrong to me.

(In reply to Jonathan M Davis from comment #19) > Okay. Clearly, I was not paying enough attention to what was going on here. > It always has been the case that opEquals is generated for for structs, if > you don't define it. That hasn't changed for 2.066. Rather, in the case > where you try and use it as an AA key, it now screams at you for not having > defined opEquals, even though the default opEquals was almost certainly > fine, because that's what was being used. > > It's a major bug IMHO if lhs.opCmp(rhs) == 0 is not equivalent to lhs == > rhs, so if we change the AAs to use opEquals but do not give the error that > we're currently giving, then all we'd be doing is exposing an existing bug > in someone's code, and that bug probably exists elsewhere in their code, > since they probably use opEquals with their keys _somewhere_. > > And it seems kind of messed up to me to require that opEquals be defined > just because you're using an AA when the default opEquals already does the > right thing. > > IMHO, we should either require that opEquals be defined in general if opCmp > is defined (which I think is a bad idea), or we should just use the default > opEquals with AAs without complaining about it (much better idea IMHO). The > only code that would be negatively affected is already broken anyway. But > requiring folks to define opEquals instead of using the perfectly good > default just because they're using an AA seems very wrong to me. If you define opCmp it means that the default generated isn't correct for you. If the default opCmp isn't correct, how often will the default opEquals be correct then. I mean, will there be uses where the default opEquals is correct but not the default opCmp. Generating opEquals to call opCmp == 0 if opCmp is defined will be a breaking change but it will only change the behavior if previously lhs.opCmp(rhs) == 0 was _not_ the same as lhs == rhs, which you defined as a bug. So to me this looks like it will fix bugs.

(In reply to Jacob Carlborg from comment #20) > If you define opCmp it means that the default generated isn't correct for > you. If the default opCmp isn't correct, how often will the default opEquals > be correct then. I mean, will there be uses where the default opEquals is > correct but not the default opCmp. > > Generating opEquals to call opCmp == 0 if opCmp is defined will be a > breaking change but it will only change the behavior if previously > lhs.opCmp(rhs) == 0 was _not_ the same as lhs == rhs, which you defined as a > bug. So to me this looks like it will fix bugs. The compiler does not define opCmp for you. If you don't define it, none of the other comparison operators work. You define opCmp, because you want your struct to work with <, <=, >=, and >. == has nothing to do with it. And if you define opCmp so that lhs.opCmp(rhs) == 0 is not equivalent to opEquals, then one of the two needs to be fixed so that they _are_ equivalent; otherwise it's a bug. If that means having to define opEquals instead of the built-in one, then you have to define it, but in many cases, the built-in one is correct, and you simply added opCmp in order to get the other comparison operators. So, if we make opEquals be generated as lhs.opCmp(rhs) == 0 when opCmp is defined, then that will incur a performance hit, and it will only be more correct if the struct was broken in the first place. So, we'd be penalizing code that was written correctly just to fix bugs in code that didn't define opEquals like when should have. And that still wouldn't fix code where opEquals _was_ defined but it was defined incorrectly. So, as far as I can see, changing the default opEquals implementation to use opCmp just penalizes the folks who made sure that opCmp was correctly implemented. I don't see any reason to try and fix broken code by changing the language, especially when that penalizes correct code. And FWIW, Walter agrees with me: http://forum.dlang.org/post/[email protected]

Alright. I think the forum discussion has convinced me that having opEquals = (opCmp()==0) is a bad idea. Instead, Jonathan's solution is the best: get rid of the compile error that forces you to declare opEquals just because you declared opCmp. Code that defines opCmp that's inconsistent with opEquals is already broken, and we aren't making things worse. Assuming that the user-defined opCmp is consistent with opEquals, then the AA code change that switched from using typeinfo.compare to typeinfo.equals should still work correctly on existing code. So this sounds like the best way to go.

Anyone know which pull request introduced this regression?

Found it with git bisect: it's caused by dmd commit 11a29600c94a599ea670c8ba1a134a6ea5bcf491, which was merged by PR 3731.

Said PR appears to be a fix of issue #13074.

Ah, I see. 13179 and 13074 are mirror images of each other!

Commits pushed to master at https://github.com/D-Programming-Language/dmd https://github.com/D-Programming-Language/dmd/commit/97045eae39d6c10eab020b95f9ee8bcfc01d8fb3 fix Issue 13179 - AA key type TagIndex now requires equality rather than comparison https://github.com/D-Programming-Language/dmd/commit/6363a7f8e20aacb3271d5607c6f024c9b54b21e1 Merge pull request #3813 from WalterBright/revert3731 [reg] fix Issue 13179 - AA key type TagIndex now requires equality rather than...

Commit pushed to 2.066 at https://github.com/D-Programming-Language/dmd https://github.com/D-Programming-Language/dmd/commit/1b244ba48a50fa0cb0961b08cfc3c3cb4bba2f35 Merge pull request #3813 from WalterBright/revert3731 [reg] fix Issue 13179 - AA key type TagIndex now requires equality rather than...

Commit pushed to master at https://github.com/D-Programming-Language/dmd https://github.com/D-Programming-Language/dmd/commit/1b244ba48a50fa0cb0961b08cfc3c3cb4bba2f35 Merge pull request #3813 from WalterBright/revert3731

You realize this now SILENTLY breaks such code? Anyone who defined opCmp and toHash to be other than the default, left opEquals alone, will have their AA keys compile silently, and then do the completely wrong thing? This was not a regression. It is an unfortunate step REQUIRED because of the state of D before this change. Before the change, regardless of what the spec said, only opCmp was used. opEquals was not used. If one defined opCmp, but not opEquals, no error was raised, and it worked as expected. Now that we switched to using opEquals instead of opCmp, even though the spec has warned such users not to depend on implementation details such as this, it will break code. In reverting this change, we have introduced a silent breaking regression. I'll also note that the equivalent class requirements are still in there. In other words, change TagIndex to a class, and you still get the error. There was a lot of work and thought put into this before the release, I'm surprised it was killed so quickly. I respectfully ask that it be reinstated. If we all decide that such users should just be screwed for not reading the fine print of the spec, then I guess that's what's been decided. At least, remove the class error as well.

> opCmp was added because of a regression in 2.065.0 and now it's changed > again. What are you referring to here?

(In reply to hsteoh from comment #22) > Instead, Jonathan's solution is the best: get rid of the compile error that > forces you to declare opEquals just because you declared opCmp. Code that > defines opCmp that's inconsistent with opEquals is already broken, and we > aren't making things worse. Assuming that the user-defined opCmp is > consistent with opEquals, then the AA code change that switched from using > typeinfo.compare to typeinfo.equals should still work correctly on existing > code. So this sounds like the best way to go. So is this the bottom line of the discussion? And are we OK that this change might silently break code that was previously incorrect but did work?

See: http://forum.dlang.org/post/[email protected]

> See: http://forum.dlang.org/post/[email protected] OK, problem solved. I'd also like to amend that if a struct defines opCmp we'll still use the compiler generated xToHash, i.e. compute the hash over all fields. So it's even more unlikely that anyone successfully used a struct with only opCmp as hash key.