Implement hashCode on objects stored in a set or used as map keys.

Implement hashCode on objects stored in a set or used as map keys.

R=johnniwinther@google.com, ngeoffray@google.com

Committed: https://code.google.com/p/dart/source/detail?r=24464

[ahe, 2013-06-23 09:38:16]

Makes dart2js 5% faster at compiling itself.

[Johnni Winther, 2013-06-23 19:07:42]

lgtm

https://codereview.chromium.org/17569004/diff/1/dart/sdk/lib/_internal/compil...
File dart/sdk/lib/_internal/compiler/implementation/util/util.dart (right):

https://codereview.chromium.org/17569004/diff/1/dart/sdk/lib/_internal/compil...
dart/sdk/lib/_internal/compiler/implementation/util/util.dart:112: int
computeHashCode(part1, [part2, part3, part4]) {
Wouldn't it be faster to have functions [computeHashCode2],..,
[computeHashCode4] to avoid the implicit [: ^ null.hashCode :] for the optional
arguments?

[kasperl, 2013-06-24 06:32:43]

https://codereview.chromium.org/17569004/diff/1/dart/sdk/lib/_internal/compil...
File dart/sdk/lib/_internal/compiler/implementation/util/util.dart (right):

https://codereview.chromium.org/17569004/diff/1/dart/sdk/lib/_internal/compil...
dart/sdk/lib/_internal/compiler/implementation/util/util.dart:112: int
computeHashCode(part1, [part2, part3, part4]) {
At some point we should probably figure out if using something heavier like
Selector.mixHashCodeBits would be better.

[ngeoffray, 2013-06-24 10:12:07]

LGTM

[ngeoffray, 2013-06-24 10:12:07]

LGTM

[ahe, 2013-06-24 19:25:59]

PTAL

[ngeoffray, 2013-06-24 19:43:10]

LGTM

https://codereview.chromium.org/17569004/diff/8001/dart/sdk/lib/_internal/com...
File dart/sdk/lib/_internal/compiler/implementation/dart_types.dart (right):

https://codereview.chromium.org/17569004/diff/8001/dart/sdk/lib/_internal/com...
dart/sdk/lib/_internal/compiler/implementation/dart_types.dart:98: // of
duplicating it here?
Not my code, but I can understand why someone would like to have it in the root
of a class hierarchy. It kind of says to the subclasses that they should
implement it, because some code will request it.

https://codereview.chromium.org/17569004/diff/8001/dart/sdk/lib/_internal/com...
File
dart/sdk/lib/_internal/compiler/implementation/ssa/value_range_analyzer.dart
(right):

https://codereview.chromium.org/17569004/diff/8001/dart/sdk/lib/_internal/com...
dart/sdk/lib/_internal/compiler/implementation/ssa/value_range_analyzer.dart:151:
int get hashCode => throw new UnsupportedError('IntValue.hashCode');
Changes in this file tend to show that it's not so nice to have a warning that
you haven't implemented hashCode..... In this file, operator== is like any other
relational operator. The intent is not to put them in data structure that rely
on hashCode. I agree it's defensive programming then, but maybe just add it to
the root of this class hierarchy, to avoid seeing these duplicated
UnsupportedError.

https://codereview.chromium.org/17569004/diff/8001/dart/sdk/lib/_internal/com...
File dart/sdk/lib/_internal/compiler/implementation/tree/dartstring.dart
(right):

https://codereview.chromium.org/17569004/diff/8001/dart/sdk/lib/_internal/com...
dart/sdk/lib/_internal/compiler/implementation/tree/dartstring.dart:47: int get
hashCode => throw new UnsupportedError('ArgumentsTypes.hashCode');
ArgumentsTypes => DartString.

[ahe, 2013-06-24 20:18:54]

Thank you!

https://codereview.chromium.org/17569004/diff/8001/dart/sdk/lib/_internal/com...
File dart/sdk/lib/_internal/compiler/implementation/dart_types.dart (right):

https://codereview.chromium.org/17569004/diff/8001/dart/sdk/lib/_internal/com...
dart/sdk/lib/_internal/compiler/implementation/dart_types.dart:98: // of
duplicating it here?
On 2013/06/24 19:43:10, ngeoffray wrote:
> Not my code, but I can understand why someone would like to have it in the
root
> of a class hierarchy. It kind of says to the subclasses that they should
> implement it, because some code will request it.

One of my concerns is that Dart is a dynamic language that doesn't benefit from
AOT compilation, and the more hoops the JIT compiler has to jump through, the
less time it has to compile your program. At least one of the subclasses of this
class would like to use Object.operator==, but it has to re-implement it. 
That's just more work for the JIT compiler.

Also, I don't like the principle of removing an implementation from a superclass
and then re-implement it in a subclass.  It certainly doesn't scale[1], and I
don't see what is special with operator==.

Finally, I don't think it is "darty" to be so verbose.  It smells like another
programming language that Dart shouldn't smell like ;-)

[1] I assume everyone agree that you shouldn't create a class like this:

abstract class MyObject {
  bool operator ==(other);
  int get hashCode;
  String toString();
  noSuchMethod(Invocation invocation);
  Type get runtimeType;
}

https://codereview.chromium.org/17569004/diff/8001/dart/sdk/lib/_internal/com...
File
dart/sdk/lib/_internal/compiler/implementation/ssa/value_range_analyzer.dart
(right):

https://codereview.chromium.org/17569004/diff/8001/dart/sdk/lib/_internal/com...
dart/sdk/lib/_internal/compiler/implementation/ssa/value_range_analyzer.dart:151:
int get hashCode => throw new UnsupportedError('IntValue.hashCode');
On 2013/06/24 19:43:10, ngeoffray wrote:
> Changes in this file tend to show that it's not so nice to have a warning that
> you haven't implemented hashCode..... In this file, operator== is like any
other
> relational operator. The intent is not to put them in data structure that rely
> on hashCode. I agree it's defensive programming then, but maybe just add it to
> the root of this class hierarchy, to avoid seeing these duplicated
> UnsupportedError.

You'd still get a warning.  The rule is simple because it is the only rule that
works in general: when you override operator==, you have to override hashCode. 
It is actually quite hard to implement operator== and hashCode, and if you don't
keep it simple you quickly get in trouble.  I look forward to discussing
operator==/hashCode with rest of you tomorrow, I have a bunch of concrete
suggestions and some general advice.  I should also try to to write it up for
dartlang.org.

[ahe, 2013-06-24 20:43:50]

https://codereview.chromium.org/17569004/diff/8001/dart/sdk/lib/_internal/com...
File dart/sdk/lib/_internal/compiler/implementation/tree/dartstring.dart
(right):

https://codereview.chromium.org/17569004/diff/8001/dart/sdk/lib/_internal/com...
dart/sdk/lib/_internal/compiler/implementation/tree/dartstring.dart:47: int get
hashCode => throw new UnsupportedError('ArgumentsTypes.hashCode');
On 2013/06/24 19:43:10, ngeoffray wrote:
> ArgumentsTypes => DartString.

Done.

[sra1, 2013-06-25 03:33:38]

https://codereview.chromium.org/17569004/diff/8001/dart/sdk/lib/_internal/com...
File
dart/sdk/lib/_internal/compiler/implementation/ssa/value_range_analyzer.dart
(right):

https://codereview.chromium.org/17569004/diff/8001/dart/sdk/lib/_internal/com...
dart/sdk/lib/_internal/compiler/implementation/ssa/value_range_analyzer.dart:151:
int get hashCode => throw new UnsupportedError('IntValue.hashCode');
On 2013/06/24 20:18:54, ahe wrote:
> On 2013/06/24 19:43:10, ngeoffray wrote:
> > Changes in this file tend to show that it's not so nice to have a warning
that
> > you haven't implemented hashCode..... In this file, operator== is like any
> other
> > relational operator. The intent is not to put them in data structure that
rely
> > on hashCode. I agree it's defensive programming then, but maybe just add it
to
> > the root of this class hierarchy, to avoid seeing these duplicated
> > UnsupportedError.
> 
> You'd still get a warning.  The rule is simple because it is the only rule
that
> works in general: when you override operator==, you have to override hashCode.

> It is actually quite hard to implement operator== and hashCode, and if you
don't
> keep it simple you quickly get in trouble.  I look forward to discussing
> operator==/hashCode with rest of you tomorrow, I have a bunch of concrete
> suggestions and some general advice.  I should also try to to write it up for
> http://dartlang.org.

I don't like the changes in this file.  There is no simple rule for this problem
that is both accurate and comfortable for the working programmer.  This kind of
invariant should be checked by a static analysis tool that has some
intelligence.

Tools I have worked with can take a pattern like the following and construct an
example if the exception can be reached.

checkHashCode(a, b) {
  if (a == b) {
    if (a.hashCode != b.hashCode) {
      throw ValidationError('hashCode different for equal objects', a, b);
    }
  }
}

A hashCode implementation, inherited or not, that throws an exception or returns
a constant will always be trivially validated.

My high level point is that we don't have to solve all problems with simple
rules.  The platform will be better if we use the hammer for nails and wait
until we have a scalpel before trying to solve more delicate problems.

[ahe, 2013-06-25 05:24:58]

https://codereview.chromium.org/17569004/diff/8001/dart/sdk/lib/_internal/com...
File
dart/sdk/lib/_internal/compiler/implementation/ssa/value_range_analyzer.dart
(right):

https://codereview.chromium.org/17569004/diff/8001/dart/sdk/lib/_internal/com...
dart/sdk/lib/_internal/compiler/implementation/ssa/value_range_analyzer.dart:151:
int get hashCode => throw new UnsupportedError('IntValue.hashCode');
I find it peculiar that you would use this particular file as an example of a
valid use: all the classes here are broken as they don't override hashCode.  The
only reason that dart2js isn't broken as well is that these objects are not put
in a set or used as keys in a hashMap.

It is possible that you can come up with a smarter tool, but I highly doubt it
would be worth the effort. It is not the case that throwing an exception is a
valid hashCode implementation, it just prevents us from accidentally using these
objects as keys. In the end, the result is going to be the same: in virtually
all real situations, you have to implement hashCode when you override
operator==.

On 2013/06/25 03:33:38, sra1 wrote:
> On 2013/06/24 20:18:54, ahe wrote:
> > On 2013/06/24 19:43:10, ngeoffray wrote:
> > > Changes in this file tend to show that it's not so nice to have a warning
> that
> > > you haven't implemented hashCode..... In this file, operator== is like any
> > other
> > > relational operator. The intent is not to put them in data structure that
> rely
> > > on hashCode. I agree it's defensive programming then, but maybe just add
it
> to
> > > the root of this class hierarchy, to avoid seeing these duplicated
> > > UnsupportedError.
> > 
> > You'd still get a warning.  The rule is simple because it is the only rule
> that
> > works in general: when you override operator==, you have to override
hashCode.
> 
> > It is actually quite hard to implement operator== and hashCode, and if you
> don't
> > keep it simple you quickly get in trouble.  I look forward to discussing
> > operator==/hashCode with rest of you tomorrow, I have a bunch of concrete
> > suggestions and some general advice.  I should also try to to write it up
for
> > http://dartlang.org.
> 
> I don't like the changes in this file.  There is no simple rule for this
problem
> that is both accurate and comfortable for the working programmer.  This kind
of
> invariant should be checked by a static analysis tool that has some
> intelligence.
> 
> Tools I have worked with can take a pattern like the following and construct
an
> example if the exception can be reached.
> 
> checkHashCode(a, b) {
>   if (a == b) {
>     if (a.hashCode != b.hashCode) {
>       throw ValidationError('hashCode different for equal objects', a, b);
>     }
>   }
> }
> 
> A hashCode implementation, inherited or not, that throws an exception or
returns
> a constant will always be trivially validated.
> 
> My high level point is that we don't have to solve all problems with simple
> rules.  The platform will be better if we use the hammer for nails and wait
> until we have a scalpel before trying to solve more delicate problems.
>

[ahe, 2013-06-26 11:50:01]

Committed patchset #5 manually as r24464 (presubmit successful).

[Johnni Winther, 2013-06-28 14:24:20]

https://codereview.chromium.org/17569004/diff/24001/dart/sdk/lib/_internal/co...
File dart/sdk/lib/_internal/compiler/implementation/dart_types.dart (right):

https://codereview.chromium.org/17569004/diff/24001/dart/sdk/lib/_internal/co...
dart/sdk/lib/_internal/compiler/implementation/dart_types.dart:98: // of
duplicating it here?
I think its archaic. Just remove it.

https://codereview.chromium.org/17569004/diff/24001/dart/sdk/lib/_internal/co...
dart/sdk/lib/_internal/compiler/implementation/dart_types.dart:562: // for
concrete suggestions.
If you have a good solution, put it in. The idea in the implementation was that
all subclasses of GenericType should require that [other] is an instance of
their own type. Maybe we can now use [: runtimeType == other.runtimeType :] in
GenericType as one would use .getClass() in Java?

[ahe, 2013-06-28 17:55:44]

Thanks, Johnni.  I'll send you a separate CL.

https://codereview.chromium.org/17569004/diff/24001/dart/sdk/lib/_internal/co...
File dart/sdk/lib/_internal/compiler/implementation/dart_types.dart (right):

https://codereview.chromium.org/17569004/diff/24001/dart/sdk/lib/_internal/co...
dart/sdk/lib/_internal/compiler/implementation/dart_types.dart:98: // of
duplicating it here?
On 2013/06/28 14:24:21, Johnni Winther wrote:
> I think its archaic. Just remove it.

Done.

https://codereview.chromium.org/17569004/diff/24001/dart/sdk/lib/_internal/co...
dart/sdk/lib/_internal/compiler/implementation/dart_types.dart:562: // for
concrete suggestions.
On 2013/06/28 14:24:21, Johnni Winther wrote:
> If you have a good solution, put it in. The idea in the implementation was
that
> all subclasses of GenericType should require that [other] is an instance of
> their own type. Maybe we can now use [: runtimeType == other.runtimeType :] in
> GenericType as one would use .getClass() in Java?

Done.