Change in dart/sdk[master]: Add `Object.hash` and `Object.hashAll` static helper methods.
Lasse R.H. Nielsen (Gerrit)
There is currently an error in DDC that prevents this from building the SDK. I'll file issues.
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Lasse R.H. Nielsen (Gerrit)
Lasse R.H. Nielsen would like Leaf Petersen to review this change.
Add `Object.hash` and `Object.hashAll` static helper methods.
Bug: http://dartbug.com/11617
Change-Id: Id06fb5b3914bee24713427edbd3b9b7e86f86449
---
M CHANGELOG.md
M sdk/lib/core/object.dart
M sdk/lib/internal/internal.dart
D sdk/lib/math/jenkins_smi_hash.dart
M sdk/lib/math/math.dart
M sdk/lib/math/math_sources.gni
M sdk/lib/math/point.dart
M sdk/lib/math/rectangle.dart
A tests/corelib_2/object_hash_test.dart
9 files changed, 231 insertions(+), 45 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 76ca9f1..f4e99da 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -19,6 +19,7 @@
* Added missing methods to `UnmodifiableMapMixin`. Some maps intended to
be unmodifiable incorrectly allowed new methods added in Dart 2 to
succeed.
+* Add `hash` and `hashAll` static helper functions to `Object`.
## 2.1.0-dev.3.0
diff --git a/sdk/lib/core/object.dart b/sdk/lib/core/object.dart
index 505efdf..dde7351 100644
--- a/sdk/lib/core/object.dart
+++ b/sdk/lib/core/object.dart
@@ -112,4 +112,125 @@
* A representation of the runtime type of the object.
*/
external Type get runtimeType;
+
+ /**
+ * Creates a combined hash code for a number of objects.
+ *
+ * The hash code is computed for all arguments that are actually
+ * supplied, even if they are `null`, by numerically combining the
+ * [Object.hashCode] of each argument.
+ *
+ * The hashing algorithm is based on the [Jenkins hash function](https://en.wikipedia.org/wiki/Jenkins_hash_function)
+ *
+ * Example:
+ * ```dart
+ * class SomeObject {
+ * final Object a, b, c;
+ * SomeObject(this.a, this.b, this.c);
+ * bool operator=(Object other) =>
+ * other is SomeObject && a == other.a && b == other.b && c == other.c;
+ * int get hashCode => Object.hash(a, b, c);
+ * }
+ * ```
+ *
+ * The computed value must be consistent when the function is called
+ * with the same arguments multiple times
+ * during the execution of a single program.
+ *
+ * The hash value generated by this function is *not* guranteed to be stable
+ * over different runs of the same program.
+ * The exact algorithm used may differ between different platforms,
+ * or between different versions of the platform libraries,
+ * and it may depend on values that change per program run
+ *
+ * The [hashAll] function gives the same result as this function when
+ * called with a collection containing the actual arguments to this function.
+ */
+ static int hash(Object object1, Object object2,
+ [Object object3 = sentinelValue,
+ Object object4 = sentinelValue,
+ Object object5 = sentinelValue,
+ Object object6 = sentinelValue,
+ Object object7 = sentinelValue,
+ Object object8 = sentinelValue,
+ Object object9 = sentinelValue,
+ Object object10 = sentinelValue]) {
+ int hash = 0;
+ hash = JenkinsSmiHash.combine(hash, object1.hashCode);
+ hash = JenkinsSmiHash.combine(hash, object2.hashCode);
+ if (!identical(sentinelValue, object3)) {
+ hash = JenkinsSmiHash.combine(hash, object3.hashCode);
+ if (!identical(sentinelValue, object4)) {
+ hash = JenkinsSmiHash.combine(hash, object4.hashCode);
+ if (!identical(sentinelValue, object5)) {
+ hash = JenkinsSmiHash.combine(hash, object5.hashCode);
+ if (!identical(sentinelValue, object6)) {
+ hash = JenkinsSmiHash.combine(hash, object6.hashCode);
+ if (!identical(sentinelValue, object7)) {
+ hash = JenkinsSmiHash.combine(hash, object7.hashCode);
+ if (!identical(sentinelValue, object8)) {
+ hash = JenkinsSmiHash.combine(hash, object8.hashCode);
+ if (!identical(sentinelValue, object9)) {
+ hash = JenkinsSmiHash.combine(hash, object9.hashCode);
+ if (!identical(sentinelValue, object10)) {
+ hash = JenkinsSmiHash.combine(hash, object10.hashCode);
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ return JenkinsSmiHash.finish(hash);
+ }
+
+ /**
+ * Creates a combined hash code for a collection of objects.
+ *
+ * The hash code is computed for elements in [objects],
+ * even if they are `null`, by numerically combining the
+ * [Object.hashCode] of each element.
+ *
+ * The hashing algorithm is based on the [Jenkins hash function](https://en.wikipedia.org/wiki/Jenkins_hash_function)
+ *
+ * The result of `hashAll([o])` is not `o.hashCode`.
+ *
+ * Example:
+ * ```dart
+ * class SomeObject {
+ * final List<String> path;
+ * SomeObject(this.path);
+ * bool operator=(Object other) {
+ * if (other is SomeObject) {
+ * if (path.length != other.path.length) return false;
+ * for (int i = 0; i < path.length; i++) {
+ * if (path[i] != other.path[i]) return false;
+ * }
+ * return true;
+ * }
+ * return false;
+ * }
+ *
+ * int get hashCode => Object.hashAll(path);
+ * }
+ * ```
+ *
+ * The computed value must be consistent when the function is called
+ * with the same arguments multiple times
+ * during the execution of a single program.
+ *
+ * The hash value generated by this function is *not* guranteed to be stable
+ * over different runs of the same program.
+ * The exact algorithm used may differ between different platforms,
+ * or between different versions of the platform libraries,
+ * and it may depend on values that change per program run
+ */
+ static int hashAll(Iterable<Object> objects) {
+ int hash = 0;
+ for (var object in objects) {
+ hash = JenkinsSmiHash.combine(hash, object.hashCode);
+ }
+ return JenkinsSmiHash.finish(hash);
+ }
}
diff --git a/sdk/lib/internal/internal.dart b/sdk/lib/internal/internal.dart
index 7ffc482..5297ae4 100644
--- a/sdk/lib/internal/internal.dart
+++ b/sdk/lib/internal/internal.dart
@@ -112,6 +112,54 @@
return digit1 * 16 + digit2 - (digit2 & 256);
}
+/**
+ * This is the [Jenkins hash function][1] but using masking to keep
+ * values in SMI range.
+ *
+ * [1]: http://en.wikipedia.org/wiki/Jenkins_hash_function
+ *
+ * Use:
+ * Hash each value with the hash of the previous value, then get the final
+ * hash by calling finish.
+ * ```
+ * var hash = 0;
+ * for (var value in values) {
+ * hash = JenkinsSmiHash.combine(hash, value.hashCode);
+ * }
+ * hash = JenkinsSmiHash.finish(hash);
+ * ```
+ *
+ * TODO(lrn): Consider specializing this code per platform,
+ * so the VM can use its 64-bit integers directly.
+ */
+class JenkinsSmiHash {
+ static int combine(int hash, int value) {
+ hash = 0x1fffffff & (hash + value);
+ hash = 0x1fffffff & (hash + ((0x0007ffff & hash) << 10));
+ return hash ^ (hash >> 6);
+ }
+
+ static int finish(int hash) {
+ hash = 0x1fffffff & (hash + ((0x03ffffff & hash) << 3));
+ hash = hash ^ (hash >> 11);
+ return 0x1fffffff & (hash + ((0x00003fff & hash) << 15));
+ }
+
+ static int hash2(a, b) => finish(combine(combine(0, a), b));
+
+ static int hash4(a, b, c, d) =>
+ finish(combine(combine(combine(combine(0, a), b), c), d));
+}
+
+/// Sentinel values that should never be exposed outside of dart:core.
+class SentinelValue {
+ final int id;
+ const SentinelValue(this.id);
+}
+
+/// A default value to use when only one sentinel is needed.
+const Object sentinelValue = const SentinelValue(0);
+
/// Given an [instance] of some generic type [T], and [extract], a first-class
/// generic function that takes the same number of type parameters as [T],
/// invokes the function with the same type arguments that were passed to T
diff --git a/sdk/lib/math/jenkins_smi_hash.dart b/sdk/lib/math/jenkins_smi_hash.dart
deleted file mode 100644
index 1fc7dda..0000000
--- a/sdk/lib/math/jenkins_smi_hash.dart
+++ /dev/null
@@ -1,41 +0,0 @@
-// Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file
-// for details. All rights reserved. Use of this source code is governed by a
-// BSD-style license that can be found in the LICENSE file.
-part of dart.math;
-
-/**
- * This is the [Jenkins hash function][1] but using masking to keep
- * values in SMI range.
- *
- * [1]: http://en.wikipedia.org/wiki/Jenkins_hash_function
- *
- * Use:
- * Hash each value with the hash of the previous value, then get the final
- * hash by calling finish.
- *
- * var hash = 0;
- * for (var value in values) {
- * hash = JenkinsSmiHash.combine(hash, value.hashCode);
- * }
- * hash = JenkinsSmiHash.finish(hash);
- */
-class _JenkinsSmiHash {
- // TODO(11617): This class should be optimized and standardized elsewhere.
-
- static int combine(int hash, int value) {
- hash = 0x1fffffff & (hash + value);
- hash = 0x1fffffff & (hash + ((0x0007ffff & hash) << 10));
- return hash ^ (hash >> 6);
- }
-
- static int finish(int hash) {
- hash = 0x1fffffff & (hash + ((0x03ffffff & hash) << 3));
- hash = hash ^ (hash >> 11);
- return 0x1fffffff & (hash + ((0x00003fff & hash) << 15));
- }
-
- static int hash2(a, b) => finish(combine(combine(0, a), b));
-
- static int hash4(a, b, c, d) =>
- finish(combine(combine(combine(combine(0, a), b), c), d));
-}
diff --git a/sdk/lib/math/math.dart b/sdk/lib/math/math.dart
index 658c834..2b16493 100644
--- a/sdk/lib/math/math.dart
+++ b/sdk/lib/math/math.dart
@@ -13,7 +13,8 @@
*/
library dart.math;
-part "jenkins_smi_hash.dart";
+import "dart:_internal" show JenkinsSmiHash;
+
part "point.dart";
part "random.dart";
part "rectangle.dart";
diff --git a/sdk/lib/math/math_sources.gni b/sdk/lib/math/math_sources.gni
index ff8f3fa..c06aead 100644
--- a/sdk/lib/math/math_sources.gni
+++ b/sdk/lib/math/math_sources.gni
@@ -6,7 +6,6 @@
"math.dart",
# The above file needs to be first as it lists the parts below.
- "jenkins_smi_hash.dart",
"point.dart",
"random.dart",
"rectangle.dart",
diff --git a/sdk/lib/math/point.dart b/sdk/lib/math/point.dart
index af62968..f645fc6 100644
--- a/sdk/lib/math/point.dart
+++ b/sdk/lib/math/point.dart
@@ -28,7 +28,7 @@
return x == other.x && y == other.y;
}
- int get hashCode => _JenkinsSmiHash.hash2(x.hashCode, y.hashCode);
+ int get hashCode => JenkinsSmiHash.hash2(x.hashCode, y.hashCode);
/**
* Add [other] to `this`, as if both points were vectors.
diff --git a/sdk/lib/math/rectangle.dart b/sdk/lib/math/rectangle.dart
index 563713c..169d48f 100644
--- a/sdk/lib/math/rectangle.dart
+++ b/sdk/lib/math/rectangle.dart
@@ -46,7 +46,7 @@
bottom == other.bottom;
}
- int get hashCode => _JenkinsSmiHash.hash4(
+ int get hashCode => JenkinsSmiHash.hash4(
left.hashCode, top.hashCode, right.hashCode, bottom.hashCode);
/**
diff --git a/tests/corelib_2/object_hash_test.dart b/tests/corelib_2/object_hash_test.dart
new file mode 100644
index 0000000..db3e0d5
--- /dev/null
+++ b/tests/corelib_2/object_hash_test.dart
@@ -0,0 +1,57 @@
+// Copyright (c) 2018, the Dart project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+import "dart:typed_data";
+
+import "package:expect/expect.dart";
+
+main() {
+ const nan = double.nan;
+ const inf = double.infinity;
+
+ int hash1234 = Object.hash(1, 2, 3, 4);
+ Expect.type<int>(hash1234);
+ Expect.equals(hash1234, Object.hash(1, 2, 3, 4)); // Consistent.
+ Expect.equals(hash1234, Object.hashAll([1, 2, 3, 4]));
+ Expect.equals(hash1234, Object.hashAll(Uint8List.fromList([1, 2, 3, 4])));
+
+ Expect.notEquals(hash1234, Object.hash(1, 2, 3, 4, null));
+
+ Expect.equals(Object.hash(1, 2, 3, 4, 5, 6, 7, 8, 9),
+ Object.hashAll([1, 2, 3, 4, 5, 6, 7, 8, 9]));
+
+ // Works for all kinds of objects;
+ int varHash = Object.hash(
+ "string", 3, nan, true, null, Type, #Symbol, const Object(), function);
+ Expect.equals(
+ varHash,
+ Object.hashAll([
+ "string",
+ 3,
+ nan,
+ true,
+ null,
+ Type,
+ #Symbol,
+ const Object(),
+ function
+ ]));
+
+ // Object doesn't matter, just its hash code.
+ Expect.equals(hash1234,
+ Object.hash(Hashable(1), Hashable(2), Hashable(3), Hashable(4)));
+
+ // It's potentially possible to get a conflict, but it doesn't happen here.
+ Expect.notEquals("str".hashCode, Object.hashAll(["str"]));
+}
+
+// static function, used as constant value.
+void function() {}
+
+class Hashable {
+ final Object o;
+ Hashable(this.o);
+ bool operator ==(Object other) => other is Hashable && o == other.o;
+ int get hashCode => o.hashCode;
+}
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Stephen Adams (Gerrit)
3 comments:
File sdk/lib/core/object.dart:
Patch Set #2, Line 149:
static int hash(Object object1, Object object2,Why insist on object2?
I think all inputs should be optional so the boilerplate for SomeObject works for 0 or 1 field.
This will assist producing generated code.Presumably this function could be replaced when spread-args are available with something like:
static int hash(List<Object> ...objects) => hashAll(objects);
Patch Set #2, Line 162:
hash = JenkinsSmiHash.combine(hash, object3.hashCode);As a practical issue this is going to generate terrible code for dart2js (and probably other platforms). In dart2js each call site will pass in all the sentinel values. Each call to get:hashCode will be polymorphic (an 'interceptor' call on dart2js because of non-object types in JavaScript like null).
Calling hash(a, b, c) is going to be inefficient - the function is too big to inline to get any specialization to improve these problems.
When the feature was proposed I was concerned about Object.hash being another recommend-to-avoid feature, so I tried this experiment to generate better code for dart2js: https://dart-review.googlesource.com/c/sdk/+/15360
The key is the control of inlining to achieve
1. No arity dispatch
2. More precise receiver types on the get:hashCode calls to avoid polymorphic calls
3. Use of a shared branch-free combiner (after inlining combine/finish).The effect is to rewrite `Object.hash(a, b, c)` to `combine3(a.hashCode, b.hashCode, c.hashCode)`.
This does generate slightly larger code than simply calling `Object.hash(a, b, c)` but it is often much faster.There are a few problems with the force-inline approach (the inliner can't tell that the sentinel is not passed in as an argument, so does not do arity specialization cleanly), so I think it would be better to do the rewrite explicitly. That raises the question: should the rewrite be implemented once in Kernel for all platforms?
File sdk/lib/internal/internal.dart:
Patch Set #2, Line 133:
* so the VM can use its 64-bit integers directly.Also there are better hash functions - now that the VM arithmetic truncates, consider murmur.
In anticipation of this change, perhaps drop 'Jenkins' from he class name.
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Lasse R.H. Nielsen (Gerrit)
3 comments:
File sdk/lib/core/object.dart:
Patch Set #2, Line 149:
static int hash(Object object1, Object object2,Why insist on object2? […]
To discourage using it for one object (or none), where you can just use `object1.hashCode` directly. There is no advantage to using this function for one value, it's pure overhead.
I'd rather assist *better* generated code, not something of the form `Object.hash(o)` or `Object.hash()`.
With spread arguments, I'd probably still go for:
```
static int hash(Object object1, Object object2, [Object... objects]);
```
for the same reasons.Patch Set #2, Line 162:
if (sentinelValue == object4) {As a practical issue this is going to generate terrible code for dart2js (and probably other platfor […]
This is definitely a function that it would be interesting to make the front end "always inline" and optimize specially (I'm not absolutely sure we can guarantee that the sentinelValue doesn't leak if a user has access to mirrors: https://api.dartlang.org/stable/2.0.0/dart-mirrors/ParameterMirror/defaultValue.html).
The hashCode calls are going to be polymorphic whenever the code is not inlined, I don't see any good way around that, so it comes down to actually inlining.
I have no problem with having combine2..combine10 helper functions, or having platform specific implementations (the VM can likely be more efficient since it doesn't have to restrict itself to smis) that knows how to best inline for that platform.
For now I'm going for a default implementation, and we can definitely make the function external as soon as any platform has a better implementation.
File sdk/lib/internal/internal.dart:
Also there are better hash functions - now that the VM arithmetic truncates, consider murmur. […]
Done
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Nate Bosch (Gerrit)
3 comments:
File sdk/lib/core/object.dart:
Patch Set #3, Line 123:
* The hashing algorithm is based on the [Jenkins hash function](https://en.wikipedia.org/wiki/Jenkins_hash_function)Is this a necessary detail? Especially considering we call out that the exact algorithm may change
Patch Set #3, Line 136:
* The computed value must be consistent when the function is called[nit] change "must" to "will be"? This isn't a contract anyone else is expected to follow, it's something this follows.
I think that behavior also depends on the passed arguments having a consistent `hashCode` too - should we call that out?
Patch Set #3, Line 16:
import "dart:_internal" show JenkinsSmiHash;missed a rename?
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Leaf Petersen (Gerrit)
We're seriously considering adding rest args to the language, would we use them in this API if we had them? If so, should we consider
1 comment:
File sdk/lib/core/object.dart:
Patch Set #2, Line 149:
static int hash(Object object1, Object object2,To discourage using it for one object (or none), where you can just use `object1.hashCode` directly. […]
We're seriously considering adding rest args to the language, would we use them in this API if we had them? If so, should we consider holding off on landing this until we have rest args? We won't be able to change the API after the fact.
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Nate Bosch (Gerrit)
1 comment:
File sdk/lib/core/object.dart:
Patch Set #2, Line 149:
static int hash(Object object1, Object object2,We're seriously considering adding rest args to the language, would we use them in this API if we ha […]
Would there be negative performance implications of using rest args?
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Stephen Adams
Stephen Adams (Gerrit)
When the feature was originally proposed I was against it on the grounds that optional arguments (or rest-arguments) together with dynamic calls to hashCode would be too inefficient, and there is a risk of the feature becoming something that enters the folklore as yet another feature to be avoided.
I did some experimentation which I wrote up . here
I believe the compiler needs to understand Object.hash to generate acceptable code.
While it is reasonable to have a reference implementation using optional arguments or rest-arguments, I think we should have a plan for optimization on all platforms and resources allocated to implement them, and defer adding the feature until he full plan is in place.
I would prefer a rest-args reference implementation that takes zero or more arguments.
Lasse R.H. Nielsen (Gerrit)
4 comments:
File sdk/lib/core/object.dart:
Patch Set #2, Line 149:
static int hash(Object object1, Object object2,
Would there be negative performance implications of using rest args?
@leafp
We can change the current API to using rest parameters. It's a static function, so nobody can *implement* the API. We are free to modify it to be more permissive later, e.g., like the signature I wrote above.@nbosch
Performance implications relative to what?
There is a performance impact of anything, including calling functions. The only things that is completely "performance impact" free is a static function which is always inlined.I believe rest arguments *can* be optimized well. Whether implementations do so is obviously up to them.
With rest arguments, an implementation is free to have a calling convention where it can read values directly off the stack and know the number of parameters. That avoids checking for the sentinel. Likewise, JavaScript can use the `arguments` object directly, which is optimized by the JS engine.
(At least until someone reifies the list, then it obviously has to be allocated).So, code like:
static int hash(Object object1, Object object2, [Object... objects]) {
var hash = 0;
hash = JenkinsSmiHash.combine(hash, object1.hashCode);
hash = JenkinsSmiHash.combine(hash, object2.hashCode);
for (int i = 0; i < objects.length; i++) {
hash = JenkinsSmiHash.combine(hash, objects[i].hashCode);
}
return JenkinsSmiHash.finish(hash);
}should be pretty efficient. For JavaScript, it could be compiled to:
function hash(object1, object2) {
var hash = 0;
hash = JenkinsSmiHash.combine$2(hash, object1.hashCode$get());
hash = JenkinsSmiHash.combine$2(hash, object2.hashCode$get());
for (int i = 2; i < arguments.length; i++) {
hash = JenkinsSmiHash.combine$2(
hash, arguments[i].hashCode$get());
}
return JenkinsSmiHash.finish$1(hash);
}The JS implementation will be able to recognize that i is positive and bounded by arguments.length, so arguments[i] is a safe direct-to-stack access and `arguments` never need to be reified.
The VM should be able to do something similar.
That code is my end-goal, and why the current `hash` function is designed the away it is.
File sdk/lib/core/object.dart:
Patch Set #3, Line 123:
* The hashing algorithm is based on the [Jenkins hash function](https://en.wikipedia.org/wiki/Jenkins_hash_function)Is this a necessary detail? Especially considering we call out that the exact algorithm may change
Agree. The implementation documentation should just be on SystemHash.
Patch Set #3, Line 136:
* The computed value must be consistent when the function is called
[nit] change "must" to "will be"? This isn't a contract anyone else is expected to follow, it's some […]
Done. And done.
Patch Set #3, Line 16:
import "dart:_internal" show JenkinsSmiHash;missed a rename?
Done
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Leaf Petersen (Gerrit)
1 comment:
File sdk/lib/core/object.dart:
Patch Set #2, Line 149:
Object object4 = sentinelValue,@leafp […]
I think it's breaking to change this to rest parameters. You could be tearing it off and passing it somewhere using the current type, and when you change it to rest parameters it's no longer type compatible.
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Nate Bosch (Gerrit)
I would prefer a rest-args reference implementation that takes zero or more arguments.
You believe we could have a more optimal implementation in JS that way? From an API standpoint I agree with Lasse - I much prefer the first two arguments to not be optional to prevent misuse and confusion.
1 comment:
Patch Set #2, Line 149:
Object object4 = sentinelValue,
Performance implications relative to what?
Relative to what our pickier dart2js users would accept - mainly whatever Stephen's intuition is :)
It sounds like we should be able to be performant enough in JS either way - but if we had to choose between a feature that Google JS users would ban implemented with rest args, vs one they'd use implemented with 10 optional arguments we should choose the latter.
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Stephen Adams
Stephen Adams (Gerrit)
It would take significant effort to compile to the use of 'arguments' as you suggest. I would not make a decision that depends on being able to do that.
The Dart rest-parameter will implement some collection type, so in the general case you would need to copy arguments to an Array and tag it with a type so that it passes type checks. Reducing this to a simple use of 'arguments' would be a multi-step optimization that requires understanding indexing patterns. We probably will never get around to it, and I expect that level of cleverness would be quite fragile.
The copying to an Array is done for you with ES6 rest parameters, but we have to figure out what we are doing for IE11 before using '...'.
Most JavaScript implementations do not optimize 'arguments' well in this use case. Remember that arguments[0] is an alias to object1, so a JIT compiler would be justified in doing less optimization due to the confusing aliasing and resource constraints.
Since ES6 has rest parameters, I don't expect JavaScript implementors to spend much effort on 'arguments' when they can for the same effort do a better job on rest parameters.
I think we should allow zero or more arguments.
Disallowing one argument encourages hash-table collisions: a wrapper over, say, a single int, should probably not have the same hashCode as the int.
Irregularity always causes problems, for example, code that somehow calls Function.apply(Object.hash, items) will sometimes fail.
Lasse R.H. Nielsen (Gerrit)
1 comment:
Patch Set #2, Line 149:
Object object4 = sentinelValue,
> Performance implications relative to what? […]
If an
int Function(Object, Object, [Object..])
is not assignable to
int Function(Object, Object, [Object, Object, ... n ..., Object])
then we are doing something wrong with rest arguments. The rest-argument function can clearly be used in all the same call contexts, and then some.
The one potential break is due to something using the static type of Object.hash to infer the type of a variable, and then assign something to it.
var myHash = Object.hash;
if (useMockHash) {
myHash = (Object o1, Object o2, [ ... Object o10]) => 0;
}If we consider that breaking, then *any* change *anywhere* is breaking (like adding more optional parameters to a static function, which is something we currently consider as a completely safe change).
As for performance, I actually think rest parameters will be more performant than the optional arguments with sentinels (mainly due to the sentinels and larger code size). The optional parameters are just a stepping stone to get to the rest parameter version, one I hope we will be able to move forward from soon-ish.
I just hope they won't ban the ten-parameter function until then.
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Leaf Petersen (Gerrit)
1 comment:
Patch Set #2, Line 149:
Object object4 = sentinelValue,
If an
int Function(Object, Object, [Object..])
is not assignable to
int Function(Object, Object, [Object, Object, ... n ..., Object])
See 2.b here: https://github.com/munificent/ui-as-code/blob/master/in-progress/parameter-freedom.md#subtyping
My read is that this subtyping is not allowed.
then we are doing something wrong with rest arguments. The rest-argument function can clearly be used in all the same call contexts, and then some.
Bob's proposal does not follow the principle that any function which can be used in all of the same call contexts is a subtype, for good reason (e.g. the examples with optional parameters he discusses where the call signatures are compatible but the call sends arguments to unexpected parameters).
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Lasse R.H. Nielsen (Gerrit)
1 comment:
Patch Set #2, Line 149:
Object object4 = sentinelValue,
> If an […]
I think you are correct, and I count it as a significant argument against that design.
It believe it would accept
static int hash(Object o1, Object o2, [Object o3, ... , Object o10, Object... rest]) { ... }(Then I'd probably just intrinsify the method and let the compiler optimize it however best for the platform).
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Kevin Moore (Gerrit)
Would LOVE to see this for 2.1!
Lasse R.H. Nielsen (Gerrit)
Would LOVE to see this for 2.1!
I'm holding it back because I worry that we might not be able to generalize it with the current var-args proposal ("parameter freedom" by rnystrom).
We might be able to get away with this by documenting that the function may change signature in the future, so it should only be called, not torn off and assigned to a function type, then we might be good.
Kevin Moore
Kevin Moore (Gerrit)
We're going to have the same issue w/ print, right?
Lasse R.H. Nielsen (Gerrit)
Patch Set 8:
We're going to have the same issue w/ print, right?
We haven't actually changed print, but if we do before deciding on parameter freedom, then yes.
Kevin Moore (Gerrit)
Let's not forget about this for 2.2!
Nate Bosch (Gerrit)
Can we revisit this? I'd rather not see it sit in limbo waiting on a decision about a language feature we aren't actively pursuing...
Kevin Moore
Kevin Moore (Gerrit)
Ditto! Would love to have this.
(Don't forget @Since)
Nate Bosch (Gerrit)
If we feel stuck shipping something in the SDK, should we ship a canonical team owned `package:hash` or maybe use `package:math`?
I keep seeing hash codes get reimplemented over and over.
Dan Field (Gerrit)
Patch Set 9:
If we feel stuck shipping something in the SDK, should we ship a canonical team owned `package:hash` or maybe use `package:math`?
I keep seeing hash codes get reimplemented over and over.
This is already implemented in dart:ui - part of the idea of putting it in the SDK is so we can get rid of it there. Having it in a package won't help things.
I second moving forward on this.
Todd Volkert (Gerrit)
1 comment:
Patchset:
I'd like to move forward with this. What's the path forward here?
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Lasse R.H. Nielsen (Gerrit)
1 comment:
Patchset:
I'd like to move forward with this. […]
The block was concerns about the "10 optional parameters" API being forward compatible with a potential varargs feature.
That hasn't changed, but there is no currently active varargs proposal.
I'm still fine with landing this.
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Stephen Adams (Gerrit)
3 comments:
Patchset:
I will fix the dart2js '_validateInterceptorImplementsAllObjectMethods' failure.
File sdk/lib/core/object.dart:
Patch Set #11, Line 277:
ObjectWhy not Object?
Patch Set #11, Line 282:
hash = (hash ^ objectHash) & 0xFFFFFFFF;This is incapable of distinguishing [1,1] from [2,2].
I have found in practice one can get a good unordered hash code by sorting the individual hash codes before combining them.
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Stephen Adams (Gerrit)
1 comment:
File sdk/lib/core/object.dart:
Patch Set #12, Line 148:
static int hash(Object? object1, Object? object2,Why not have these all optional?
It makes it unnecessarily painful to add and remove a second field.
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Lasse R.H. Nielsen (Gerrit)
2 comments:
Patch Set #11, Line 277:
ObjectWhy not Object?
True, we have `?` now :)
Patch Set #11, Line 282:
hash = (hash ^ objectHash) & 0xFFFFFFFF;
This is incapable of distinguishing [1,1] from [2,2]. […]
Using `+` would probably be better than `^`. That's what Java does for set equality, but sets have the advantage that the same element doesn't occur more than once. At least it only drops the lowest bit, not all o them, for `[x, x]`. Still not great.
Sorting is also an option, but quite a lot more expensive when you need to allocate space for all the hash values before sorting. We should be able to do the computation without allocations. (On the other hand, we can probably reuse a Uint32List buffer and only grow it when necessary - probably by doubling since we are working on an iterator).
The Scala approach is to collect three order-independent results, using ^, + and * of the hash codes, then do a three-element hash combination of those three, and the element count, at the end.
For us that would be:int n = 0;
int x = 0;
int a = 0;
int m = 1;
for (var object in objects) {
var h = object.hashCode;
x ^= h;
a += h;
if (h != 0) m *= h;
n++;
}
return SystemHash.hash4(x, a, m, n);That's probably reasonably efficient. Including the count ensures that `[0, 0]` and `[0, 0, 0]` won't have the same hash (but then, I'd probably use `smear` on the object hashCode anyway.)
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Stephen Adams (Gerrit)
3 comments:
File sdk/lib/core/object.dart:
Unused
File tests/corelib_2/object_hash_test.dart:
Should this be updated for a new file?
Patch Set #16, Line 1:
// Copyright (c) 2018, the Dart project authors. Please see the AUTHORS fileIs there a corelib/ version of this test to match the corelib_2/ version?
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Lasse R.H. Nielsen (Gerrit)
3 comments:
Unused
Should this be updated for a new file?
It's technically correct. I did write it first in 2018, and it was publicly available through this CL.
I don't know what our policy is for updating copyright dates when changing a file, but we usually don't.
Patch Set #16, Line 1:
// Copyright (c) 2018, the Dart project authors. Please see the AUTHORS fileIs there a corelib/ version of this test to match the corelib_2/ version?
Working on that (just want to make the test complete first, and be sure it's correct, before I start copying it).
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Lasse R.H. Nielsen (Gerrit)
1 comment:
Patchset:
PTAL!
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Kevin Moore (Gerrit)
2 comments:
Commit Message:
Patch Set #23, Line 9:
Bug: http://dartbug.com/11617Change to
```
Fixes https://github.com/dart-lang/sdk/issues/11617
```Then GitHub will auto-close the issue for you, etc!
Patchset:
DBC
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Dan Field (Gerrit)
1 comment:
File sdk/lib/core/object.dart:
Patch Set #23, Line 157:
if (sentinelValue == object3) {Here and below: identical will produce smaller code. See https://github.com/flutter/engine/pull/19615, particularly since we know sentinelValue doesn't have to deal with any possible dynamic overloading of ==.
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Leaf Petersen (Gerrit)
7 comments:
File sdk/lib/core/object.dart:
Patch Set #23, Line 148:
static int hash(Object? object1, Object? object2,I wonder if just hashing all ten unconditionally might not be faster?
Patch Set #23, Line 271:
hash = SystemHash.combine(hash, object.hashCode);I think `0.hashCode` is `0`, right? So this will return 0 for any length list of zeros? Fixing the underlying hash is probably the right thing to do here, but if not consider at least incorporating the length?
Patch Set #23, Line 282:
* in an order independet way.independent
Patch Set #23, Line 301:
* The hash value generated by this function is *not* guranteed to be stableguaranteed
Patch Set #23, Line 311:
const int mask = 0x3FFFFFFF;Why const?
File sdk/lib/internal/internal.dart:
Patch Set #23, Line 158:
static int hash2(int v1, int v2) {If I've worked through these correctly, I think that hash(0, 0) == hash(0, 0, 0) == hash(0, 0, 0, 0, 0) etc, which doesn't seem ideal. Is there a reason we use this particular hash? Looking it up briefly on the internet, it seems to be state of the art from... 1997? :)
Patch Set #23, Line 265:
/// However, for the unordered hash based on xor, we need to improveI don't understand this comment. The unordered hash doesn't use xor that I can see (other than in the course of SystemHash.hash2).
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Lasse R.H. Nielsen (Gerrit)
6 comments:
File sdk/lib/core/object.dart:
Patch Set #23, Line 148:
static int hash(Object? object1, Object? object2,I wonder if just hashing all ten unconditionally might not be faster?
Not if the `hash` function is inlined. The implementation is optimized for dart2js inlining.
Also, `Object.hash(1, 2)` would then not give the same result as `Object.hashAll([1, 2])`, which is a goal.
Patch Set #23, Line 157:
if (sentinelValue == object3) {
Here and below: identical will produce smaller code. See https://github. […]
Is that true for both VM and dart2js?
Patch Set #23, Line 271:
hash = SystemHash.combine(hash, object.hashCode);
I think `0. […]
ACK. Another option is to not start with `0`. If the seed is non-zero, then the number of combinations will matter, even if each object hash is zero.
I'd prefer to use a *random* seed, set once per execution. Then we avoid people expecting the same hash code between different executions. (But they'd probably also be different between isolates, not sure how great that is).
Patch Set #23, Line 311:
const int mask = 0x3FFFFFFF;Why const?
It's used only once, so it could have been inlined. It's given a name just to avoid "magical constants". I tend to mark magical constants as const.
File sdk/lib/internal/internal.dart:
Patch Set #23, Line 158:
static int hash2(int v1, int v2) {
If I've worked through these correctly, I think that hash(0, 0) == hash(0, 0, 0) == hash(0, 0, 0, 0, […]
The problem with hash code algorithms is that it *might* be a breaking change to change the. You never know what people use them for
We can consider changing to a different algorithm, but we should be very careful that people won't break when the hash code of strings change, even if it's only because the iteration order of `HashSet<String>` changes.
So, for now, this is the algorithm we use, and this CL needs to keep that. For existing code, this should only be a refactoring.For the `Object.hash` functions, we can do something different because they have no existing users. We then *can't* tell people that `Object.hashAll(string.codeUnits) == string.hash`, which would otherwise be true - and yes, `("\x00"*n).hashCode` *is* zero. That's actually a good thing.
Patch Set #23, Line 265:
/// However, for the unordered hash based on xor, we need to improve
I don't understand this comment. […]
ACK. It used to, now it uses `+` instead.
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Dan Field (Gerrit)
1 comment:
File sdk/lib/core/object.dart:
Patch Set #23, Line 157:
if (sentinelValue == object3) {Is that true for both VM and dart2js?
A quick test locally with dart2js suggests that it produces the same length output, but I'm not quite as familiar with dart2js. For VM, it's definitely true, and Flutter applications use these methods a lot.
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Lasse R.H. Nielsen (Gerrit)
2 comments:
File sdk/lib/core/object.dart:
Patch Set #12, Line 148:
static int hash(Object? object1, Object? object2,Why not have these all optional? […]
This point of the function is to *combine* multiple hashes. Using it for a single value is pointless overhead.
If we allow zero or one value, we should still make sure to give the same result as `hashAll` with zero or one arguments.It's true that changing behavior between one and two elements can be annoying, or between one and zero, but it gives better code if you actually change.
File sdk/lib/core/object.dart:
Patch Set #23, Line 157:
if (sentinelValue == object3) {
A quick test locally with dart2js suggests that it produces the same length output, but I'm not quit […]
I ask because I started out using `identical`, but changed it in patch set 3 after comments from Stephen. I don't remember *why* I changed it, and can't find any comments about that in particular, so maybe it was just because it didn't seem important.
Also, why is the VM not just as efficient at `const SentinelValue(0) == x` and `identical(const SentinelValue(0), x)` when it knows statically that `SentinelValue` doesn't override `operator ==`? That seems like a low-hanging optimization fruit.
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Lasse R.H. Nielsen (Gerrit)
Lasse R.H. Nielsen uploaded patch set #24 to this change.
Add `Object.hash` and `Object.hashAll` static helper methods.
Fixes #11617.
Bug: http://dartbug.com/11617
Change-Id: Id06fb5b3914bee24713427edbd3b9b7e86f86449
---
M CHANGELOG.md
M pkg/dev_compiler/tool/dartdevc_nnbd_sdk_error_golden.txt
M sdk/lib/core/object.dart
M sdk/lib/internal/internal.dart
D sdk/lib/math/jenkins_smi_hash.dart
M sdk/lib/math/math.dart
M sdk/lib/math/math_sources.gni
M sdk/lib/math/point.dart
M sdk/lib/math/rectangle.dart
A tests/corelib/object_hash_test.dart
A tests/corelib_2/object_hash_test.dart
M tests/lib/mirrors/class_declarations_test.dart
M tests/lib_2/mirrors/class_declarations_test.dart
13 files changed, 850 insertions(+), 283 deletions(-)
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Dan Field (Gerrit)
Lasse R.H. Nielsen has uploaded this change for review.
Add `Object.hash` and `Object.hashAll` static helper methods.
Fixes #11617.
Bug: http://dartbug.com/11617
Change-Id: Id06fb5b3914bee24713427edbd3b9b7e86f86449
---
M CHANGELOG.md
M pkg/dev_compiler/tool/dartdevc_nnbd_sdk_error_golden.txt
M sdk/lib/core/object.dart
M sdk/lib/internal/internal.dart
D sdk/lib/math/jenkins_smi_hash.dart
M sdk/lib/math/math.dart
M sdk/lib/math/math_sources.gni
M sdk/lib/math/point.dart
M sdk/lib/math/rectangle.dart
A tests/corelib/object_hash_test.dart
A tests/corelib_2/object_hash_test.dart
M tests/lib/mirrors/class_declarations_test.dart
M tests/lib_2/mirrors/class_declarations_test.dart
13 files changed, 850 insertions(+), 283 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 7ecc7c3..835b6b5 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -2,6 +2,12 @@
### Core libraries
+#### `dart:core`
+
+* Adds static methods `hash`, `hashAll` and `hashAllUnordered` to the
+ `Object` class. These can be used to combine the hash codes of
+ multiple objects in a consistent way.
+
### Dart VM
### Dart2JS
diff --git a/pkg/dev_compiler/tool/dartdevc_nnbd_sdk_error_golden.txt b/pkg/dev_compiler/tool/dartdevc_nnbd_sdk_error_golden.txt
index b77ed3f..6995196 100644
--- a/pkg/dev_compiler/tool/dartdevc_nnbd_sdk_error_golden.txt
+++ b/pkg/dev_compiler/tool/dartdevc_nnbd_sdk_error_golden.txt
@@ -1,11 +1,11 @@
ERROR|COMPILE_TIME_ERROR|CONST_CONSTRUCTOR_THROWS_EXCEPTION|lib/core/core.dart|3725|5|94|Const constructors can't throw exceptions.
-ERROR|COMPILE_TIME_ERROR|CONST_CONSTRUCTOR_THROWS_EXCEPTION|lib/core/core.dart|7913|5|97|Const constructors can't throw exceptions.
+ERROR|COMPILE_TIME_ERROR|CONST_CONSTRUCTOR_THROWS_EXCEPTION|lib/core/core.dart|8117|5|97|Const constructors can't throw exceptions.
ERROR|COMPILE_TIME_ERROR|CONST_CONSTRUCTOR_THROWS_EXCEPTION|lib/core/core.dart|939|5|95|Const constructors can't throw exceptions.
ERROR|COMPILE_TIME_ERROR|CONST_CONSTRUCTOR_THROWS_EXCEPTION|lib/core/core.dart|972|5|94|Const constructors can't throw exceptions.
ERROR|COMPILE_TIME_ERROR|INVALID_ASSIGNMENT|lib/_internal/js_dev_runtime/private/interceptors.dart|1348|18|27|A value of type 'double' can't be assigned to a variable of type 'int'.
ERROR|COMPILE_TIME_ERROR|RETURN_OF_INVALID_TYPE|lib/_internal/js_dev_runtime/private/interceptors.dart|1215|14|38|A value of type 'double' can't be returned from method '%' because it has a return type of 'JSNumber'.
ERROR|COMPILE_TIME_ERROR|RETURN_OF_INVALID_TYPE|lib/_internal/js_dev_runtime/private/interceptors.dart|1217|14|38|A value of type 'double' can't be returned from method '%' because it has a return type of 'JSNumber'.
ERROR|SYNTACTIC_ERROR|CONST_FACTORY|lib/core/core.dart|3723|3|5|Only redirecting factory constructors can be declared to be 'const'.
-ERROR|SYNTACTIC_ERROR|CONST_FACTORY|lib/core/core.dart|7911|3|5|Only redirecting factory constructors can be declared to be 'const'.
+ERROR|SYNTACTIC_ERROR|CONST_FACTORY|lib/core/core.dart|8115|3|5|Only redirecting factory constructors can be declared to be 'const'.
ERROR|SYNTACTIC_ERROR|CONST_FACTORY|lib/core/core.dart|937|3|5|Only redirecting factory constructors can be declared to be 'const'.
ERROR|SYNTACTIC_ERROR|CONST_FACTORY|lib/core/core.dart|970|3|5|Only redirecting factory constructors can be declared to be 'const'.
diff --git a/sdk/lib/core/object.dart b/sdk/lib/core/object.dart
index 0f7d97b..bc2ce25 100644
--- a/sdk/lib/core/object.dart
+++ b/sdk/lib/core/object.dart
@@ -112,4 +112,208 @@
* A representation of the runtime type of the object.
*/
external Type get runtimeType;
+
+ /**
+ * Creates a combined hash code for a number of objects.
+ *
+ * The hash code is computed for all arguments that are actually
+ * supplied, even if they are `null`, by numerically combining the
+ * [Object.hashCode] of each argument.
+ *
+ * Example:
+ * ```dart
+ * class SomeObject {
+ * final Object a, b, c;
+ * SomeObject(this.a, this.b, this.c);
+ * bool operator=(Object other) =>
+ * other is SomeObject && a == other.a && b == other.b && c == other.c;
+ * int get hashCode => Object.hash(a, b, c);
+ * }
+ * ```
+ *
+ * The computed value must be consistent when the function is called
+ * with the same arguments multiple times
+ * during the execution of a single program.
+ *
+ * The hash value generated by this function is *not* guranteed to be stable
+ * over different runs of the same program.
+ * The exact algorithm used may differ between different platforms,
+ * or between different versions of the platform libraries,
+ * and it may depend on values that change per program run
+ *
+ * The [hashAll] function gives the same result as this function when
+ * called with a collection containing the actual arguments to this function.
+ */
+ @Since("2.11")
+ static int hash(Object? object1, Object? object2,
+ [Object? object3 = sentinelValue,
+ Object? object4 = sentinelValue,
+ Object? object5 = sentinelValue,
+ Object? object6 = sentinelValue,
+ Object? object7 = sentinelValue,
+ Object? object8 = sentinelValue,
+ Object? object9 = sentinelValue,
+ Object? object10 = sentinelValue]) {
+ if (sentinelValue == object3) {
+ return SystemHash.hash2(object1.hashCode, object2.hashCode);
+ }
+ if (sentinelValue == object4) {
+ return SystemHash.hash3(
+ object1.hashCode, object2.hashCode, object3.hashCode);
+ }
+ if (sentinelValue == object5) {
+ return SystemHash.hash4(object1.hashCode, object2.hashCode,
+ object3.hashCode, object4.hashCode);
+ }
+ if (sentinelValue == object6) {
+ return SystemHash.hash5(object1.hashCode, object2.hashCode,
+ object3.hashCode, object4.hashCode, object5.hashCode);
+ }
+ if (sentinelValue == object7) {
+ return SystemHash.hash6(
+ object1.hashCode,
+ object2.hashCode,
+ object3.hashCode,
+ object4.hashCode,
+ object5.hashCode,
+ object6.hashCode);
+ }
+ if (sentinelValue == object8) {
+ return SystemHash.hash7(
+ object1.hashCode,
+ object2.hashCode,
+ object3.hashCode,
+ object4.hashCode,
+ object5.hashCode,
+ object6.hashCode,
+ object7.hashCode);
+ }
+ if (sentinelValue == object9) {
+ return SystemHash.hash8(
+ object1.hashCode,
+ object2.hashCode,
+ object3.hashCode,
+ object4.hashCode,
+ object5.hashCode,
+ object6.hashCode,
+ object7.hashCode,
+ object8.hashCode);
+ }
+ if (sentinelValue == object10) {
+ return SystemHash.hash9(
+ object1.hashCode,
+ object2.hashCode,
+ object3.hashCode,
+ object4.hashCode,
+ object5.hashCode,
+ object6.hashCode,
+ object7.hashCode,
+ object8.hashCode,
+ object9.hashCode);
+ }
+ return SystemHash.hash10(
+ object1.hashCode,
+ object2.hashCode,
+ object3.hashCode,
+ object4.hashCode,
+ object5.hashCode,
+ object6.hashCode,
+ object7.hashCode,
+ object8.hashCode,
+ object9.hashCode,
+ object10.hashCode);
+ }
+
+ /**
+ * Creates a combined hash code for a sequence of objects.
+ *
+ * The hash code is computed for elements in [objects],
+ * even if they are `null`,
+ * by numerically combining the [Object.hashCode] of each element
+ * in iteration order.
+ *
+ * The result of `hashAll([o])` is not `o.hashCode`.
+ *
+ * Example:
+ * ```dart
+ * class SomeObject {
+ * final List<String> path;
+ * SomeObject(this.path);
+ * bool operator=(Object other) {
+ * if (other is SomeObject) {
+ * if (path.length != other.path.length) return false;
+ * for (int i = 0; i < path.length; i++) {
+ * if (path[i] != other.path[i]) return false;
+ * }
+ * return true;
+ * }
+ * return false;
+ * }
+ *
+ * int get hashCode => Object.hashAll(path);
+ * }
+ * ```
+ *
+ * The computed value will be be consistent when the function is called
+ * again with objects that have the same hash codes in the same order
+ * during an execution of a single program.
+ *
+ * The hash value generated by this function is *not* guranteed to be stable
+ * over different runs of the same program.
+ * The exact algorithm used may differ between different platforms,
+ * or between different versions of the platform libraries,
+ * and it may depend on values that change per program run
+ */
+ @Since("2.11")
+ static int hashAll(Iterable<Object?> objects) {
+ int hash = 0;
+ for (var object in objects) {
+ hash = SystemHash.combine(hash, object.hashCode);
+ }
+ return SystemHash.finish(hash);
+ }
+
+ /**
+ * Creates a combined hash code for a collection of objects.
+ *
+ * The hash code is computed for elements in [objects],
+ * even if they are `null`,
+ * by numerically combining the [Object.hashCode] of each element
+ * in an order independet way.
+ *
+ * The result of `unorderedHashAll({o})` is not `o.hashCode`.
+ *
+ * Example:
+ * ```dart
+ * bool setEquals<T>(Set<T> set1, Set<T> set2) {
+ * var hashCode1 = Object.unorderedHashAll(set1);
+ * var hashCode2 = Object.unorderedHashAll(set2);
+ * if (hashCode1 != hashCode2) return false;
+ * // Compare elements ...
+ * }
+ * ```
+ *
+ * The computed value will be be consistent when the function is called
+ * again with objects that have the same hash codes
+ * during an execution of a single program,
+ * even if the objects are not necessarily in the same order,
+ *
+ * The hash value generated by this function is *not* guranteed to be stable
+ * over different runs of the same program.
+ * The exact algorithm used may differ between different platforms,
+ * or between different versions of the platform libraries,
+ * and it may depend on values that change per program run
+ */
+ @Since("2.11")
+ static int hashAllUnordered(Iterable<Object?> objects) {
+ int sum = 0;
+ int count = 0;
+ const int mask = 0x3FFFFFFF;
+ for (var object in objects) {
+ int objectHash = SystemHash.smear(object.hashCode);
+ sum = (sum + objectHash) & mask;
+ count += 1;
+ }
+ return SystemHash.hash2(sum, count);
+ }
}
diff --git a/sdk/lib/internal/internal.dart b/sdk/lib/internal/internal.dart
index f86652e..2a66bd6 100644
--- a/sdk/lib/internal/internal.dart
+++ b/sdk/lib/internal/internal.dart
@@ -119,6 +119,177 @@
return digit1 * 16 + digit2 - (digit2 & 256);
}
+/**
+ * A default hash function used by the platform in various places.
+ *
+ * This is currently the [Jenkins hash function][1] but using masking to keep
+ * values in SMI range.
+ *
+ * [1]: http://en.wikipedia.org/wiki/Jenkins_hash_function
+ *
+ * Use:
+ * Hash each value with the hash of the previous value, then get the final
+ * hash by calling finish.
+ * ```
+ * var hash = 0;
+ * for (var value in values) {
+ * hash = SystemHash.combine(hash, value.hashCode);
+ * }
+ * hash = SystemHash.finish(hash);
+ * ```
+ *
+ * TODO(lrn): Consider specializing this code per platform,
+ * so the VM can use its 64-bit integers directly.
+ */
+@Since("2.11")
+class SystemHash {
+ static int combine(int hash, int value) {
+ hash = 0x1fffffff & (hash + value);
+ hash = 0x1fffffff & (hash + ((0x0007ffff & hash) << 10));
+ return hash ^ (hash >> 6);
+ }
+
+ static int finish(int hash) {
+ hash = 0x1fffffff & (hash + ((0x03ffffff & hash) << 3));
+ hash = hash ^ (hash >> 11);
+ return 0x1fffffff & (hash + ((0x00003fff & hash) << 15));
+ }
+
+ static int hash2(int v1, int v2) {
+ int hash = 0;
+ hash = combine(hash, v1);
+ hash = combine(hash, v2);
+ return finish(hash);
+ }
+
+ static int hash3(int v1, int v2, int v3) {
+ int hash = 0;
+ hash = combine(hash, v1);
+ hash = combine(hash, v2);
+ hash = combine(hash, v3);
+ return finish(hash);
+ }
+
+ static int hash4(int v1, int v2, int v3, int v4) {
+ int hash = 0;
+ hash = combine(hash, v1);
+ hash = combine(hash, v2);
+ hash = combine(hash, v3);
+ hash = combine(hash, v4);
+ return finish(hash);
+ }
+
+ static int hash5(int v1, int v2, int v3, int v4, int v5) {
+ int hash = 0;
+ hash = combine(hash, v1);
+ hash = combine(hash, v2);
+ hash = combine(hash, v3);
+ hash = combine(hash, v4);
+ hash = combine(hash, v5);
+ return finish(hash);
+ }
+
+ static int hash6(int v1, int v2, int v3, int v4, int v5, int v6) {
+ int hash = 0;
+ hash = combine(hash, v1);
+ hash = combine(hash, v2);
+ hash = combine(hash, v3);
+ hash = combine(hash, v4);
+ hash = combine(hash, v5);
+ hash = combine(hash, v6);
+ return finish(hash);
+ }
+
+ static int hash7(int v1, int v2, int v3, int v4, int v5, int v6, int v7) {
+ int hash = 0;
+ hash = combine(hash, v1);
+ hash = combine(hash, v2);
+ hash = combine(hash, v3);
+ hash = combine(hash, v4);
+ hash = combine(hash, v5);
+ hash = combine(hash, v6);
+ hash = combine(hash, v7);
+ return finish(hash);
+ }
+
+ static int hash8(
+ int v1, int v2, int v3, int v4, int v5, int v6, int v7, int v8) {
+ int hash = 0;
+ hash = combine(hash, v1);
+ hash = combine(hash, v2);
+ hash = combine(hash, v3);
+ hash = combine(hash, v4);
+ hash = combine(hash, v5);
+ hash = combine(hash, v6);
+ hash = combine(hash, v7);
+ hash = combine(hash, v8);
+ return finish(hash);
+ }
+
+ static int hash9(
+ int v1, int v2, int v3, int v4, int v5, int v6, int v7, int v8, int v9) {
+ int hash = 0;
+ hash = combine(hash, v1);
+ hash = combine(hash, v2);
+ hash = combine(hash, v3);
+ hash = combine(hash, v4);
+ hash = combine(hash, v5);
+ hash = combine(hash, v6);
+ hash = combine(hash, v7);
+ hash = combine(hash, v8);
+ hash = combine(hash, v9);
+ return finish(hash);
+ }
+
+ static int hash10(int v1, int v2, int v3, int v4, int v5, int v6, int v7,
+ int v8, int v9, int v10) {
+ int hash = 0;
+ hash = combine(hash, v1);
+ hash = combine(hash, v2);
+ hash = combine(hash, v3);
+ hash = combine(hash, v4);
+ hash = combine(hash, v5);
+ hash = combine(hash, v6);
+ hash = combine(hash, v7);
+ hash = combine(hash, v8);
+ hash = combine(hash, v9);
+ hash = combine(hash, v10);
+ return finish(hash);
+ }
+
+ /// Bit shuffling operation to improve hash codes.
+ ///
+ /// Dart integers have very simple hash codes (their value),
+ /// which is acceptable for the hash above because it smears the bits
+ /// as part of the combination.
+ /// However, for the unordered hash based on xor, we need to improve
+ /// the hash code of, e.g., integers, so a set containing the integers
+ /// from zero to 2^n won't always have a zero hashcode.
+ ///
+ /// Assumes the input hash code is an unsigned 32-bit integer.
+ /// Found by Christopher Wellons [https://github.com/skeeto/hash-prospector].
+ static int smear(int x) {
+ // TODO: Use >>> instead of >> when available.
+ x ^= x >> 16;
+ x = (x * 0x7feb352d) & 0xFFFFFFFF;
+ x ^= x >> 15;
+ x = (x * 0x846ca68b) & 0xFFFFFFFF;
+ x ^= x >> 16;
+ return x;
+ }
+}
+
+/// Sentinel values that should never be exposed outside of platform libraries.
+@Since("2.11")
+class SentinelValue {
+ final int id;
+ const SentinelValue(this.id);
+}
+
+/// A default value to use when only one sentinel is needed.
+@Since("2.11")
+const Object sentinelValue = const SentinelValue(0);
+
/// Given an [instance] of some generic type [T], and [extract], a first-class
/// generic function that takes the same number of type parameters as [T],
/// invokes the function with the same type arguments that were passed to T
diff --git a/sdk/lib/math/jenkins_smi_hash.dart b/sdk/lib/math/jenkins_smi_hash.dart
deleted file mode 100644
index deca56c..0000000
--- a/sdk/lib/math/jenkins_smi_hash.dart
+++ /dev/null
@@ -1,40 +0,0 @@
-// Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file
-// for details. All rights reserved. Use of this source code is governed by a
-// BSD-style license that can be found in the LICENSE file.
-
-part of dart.math;
-
-/// This is the [Jenkins hash function][1] but using masking to keep
-/// values in SMI range.
-///
-/// [1]: http://en.wikipedia.org/wiki/Jenkins_hash_function
-///
-/// Use:
-/// Hash each value with the hash of the previous value, then get the final
-/// hash by calling finish.
-///
-/// var hash = 0;
-/// for (var value in values) {
-/// hash = JenkinsSmiHash.combine(hash, value.hashCode);
-/// }
-/// hash = JenkinsSmiHash.finish(hash);
-class _JenkinsSmiHash {
- // TODO(11617): This class should be optimized and standardized elsewhere.
-
- static int combine(int hash, int value) {
- hash = 0x1fffffff & (hash + value);
- hash = 0x1fffffff & (hash + ((0x0007ffff & hash) << 10));
- return hash ^ (hash >> 6);
- }
-
- static int finish(int hash) {
- hash = 0x1fffffff & (hash + ((0x03ffffff & hash) << 3));
- hash = hash ^ (hash >> 11);
- return 0x1fffffff & (hash + ((0x00003fff & hash) << 15));
- }
-
- static int hash2(int a, int b) => finish(combine(combine(0, a), b));
-
- static int hash4(int a, int b, int c, int d) =>
- finish(combine(combine(combine(combine(0, a), b), c), d));
-}
diff --git a/sdk/lib/math/math.dart b/sdk/lib/math/math.dart
index b335669..8f847b1 100644
--- a/sdk/lib/math/math.dart
+++ b/sdk/lib/math/math.dart
@@ -11,7 +11,8 @@
/// {@category Core}
library dart.math;
-part "jenkins_smi_hash.dart";
+import "dart:_internal" show SystemHash;
+
part "point.dart";
part "random.dart";
part "rectangle.dart";
diff --git a/sdk/lib/math/math_sources.gni b/sdk/lib/math/math_sources.gni
index ff8f3fa..c06aead 100644
--- a/sdk/lib/math/math_sources.gni
+++ b/sdk/lib/math/math_sources.gni
@@ -6,7 +6,6 @@
"math.dart",
# The above file needs to be first as it lists the parts below.
- "jenkins_smi_hash.dart",
"point.dart",
"random.dart",
"rectangle.dart",
diff --git a/sdk/lib/math/point.dart b/sdk/lib/math/point.dart
index 4b0fed5..f092fc8 100644
--- a/sdk/lib/math/point.dart
+++ b/sdk/lib/math/point.dart
@@ -23,7 +23,7 @@
bool operator ==(Object other) =>
other is Point && x == other.x && y == other.y;
- int get hashCode => _JenkinsSmiHash.hash2(x.hashCode, y.hashCode);
+ int get hashCode => SystemHash.hash2(x.hashCode, y.hashCode);
/// Add [other] to `this`, as if both points were vectors.
///
diff --git a/sdk/lib/math/rectangle.dart b/sdk/lib/math/rectangle.dart
index 2ee86c9..e80d790 100644
--- a/sdk/lib/math/rectangle.dart
+++ b/sdk/lib/math/rectangle.dart
@@ -48,7 +48,7 @@
right == other.right &&
bottom == other.bottom;
- int get hashCode => _JenkinsSmiHash.hash4(
+ int get hashCode => SystemHash.hash4(
left.hashCode, top.hashCode, right.hashCode, bottom.hashCode);
/// Computes the intersection of `this` and [other].
diff --git a/tests/corelib/object_hash_test.dart b/tests/corelib/object_hash_test.dart
new file mode 100644
index 0000000..704d1f3
--- /dev/null
+++ b/tests/corelib/object_hash_test.dart
@@ -0,0 +1,119 @@
+// Copyright (c) 2018, the Dart project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+import "dart:typed_data";
+
+import "package:expect/expect.dart";
+
+main() {
+ const nan = double.nan;
+ const inf = double.infinity;
+
+ int hash1234 = Object.hash(1, 2, 3, 4);
+ Expect.type<int>(hash1234);
+ Expect.equals(hash1234, Object.hash(1, 2, 3, 4)); // Consistent.
+ Expect.equals(hash1234, Object.hashAll([1, 2, 3, 4]));
+ Expect.equals(hash1234, Object.hashAll(Uint8List.fromList([1, 2, 3, 4])));
+
+ Expect.notEquals(hash1234, Object.hash(1, 2, 3, 4, null));
+
+ Expect.equals(Object.hash(1, 2, 3, 4, 5, 6, 7, 8, 9),
+ Object.hashAll([1, 2, 3, 4, 5, 6, 7, 8, 9]));
+
+ // Works for all kinds of objects;
+ int varHash = Object.hash(
+ "string", 3, nan, true, null, Type, #Symbol, const Object(), function);
+ Expect.equals(
+ varHash,
+ Object.hashAll([
+ "string",
+ 3,
+ nan,
+ true,
+ null,
+ Type,
+ #Symbol,
+ const Object(),
+ function
+ ]));
+
+ // Object doesn't matter, just its hash code.
+ Expect.equals(hash1234,
+ Object.hash(Hashable(1), Hashable(2), Hashable(3), Hashable(4)));
+
+ // It's potentially possible to get a conflict, but it doesn't happen here.
+ Expect.notEquals("str".hashCode, Object.hashAll(["str"]));
+
+ var hash12345 = Object.hashAllUnordered([1, 2, 3, 4, 5]);
+ for (var p in permutations([1, 2, 3, 4, 5])) {
+ Expect.equals(hash12345, Object.hashAllUnordered(p));
+ }
+ Expect.notEquals(
+ Object.hashAllUnordered(["a", "a"]), Object.hashAllUnordered(["a"]));
+
+ Expect.notEquals(Object.hashAllUnordered(["a", "a"]),
+ Object.hashAllUnordered(["a", "a", "a", "a"]));
+
+ Expect.notEquals(Object.hashAllUnordered(["a", "b"]),
+ Object.hashAllUnordered(["a", "a", "a", "b"]));
+
+ /// Unordered hashing works for all kinds of objects.
+ var unorderHash = Object.hashAllUnordered([
+ "string",
+ 3,
+ nan,
+ true,
+ null,
+ Type,
+ #Symbol,
+ const Object(),
+ function,
+ ]);
+
+ var unorderHash2 = Object.hashAllUnordered([
+ true,
+ const Object(),
+ 3,
+ function,
+ Type,
+ "string",
+ null,
+ nan,
+ #Symbol,
+ ]);
+ Expect.equals(unorderHash, unorderHash2);
+}
+
+/// Lazily emits all permutations of [values].
+///
+/// Modifes [values] rather than create a new list.
+/// The [values] list is guaranteed to end up in its original state
+/// after all permutations have been read.
+Iterable<List<T>> permutations<T>(List<T> values) {
+ Iterable<List<T>> recPermute(int end) sync* {
+ if (end == 1) {
+ yield values;
+ return;
+ }
+ for (var i = 0; i < end; i++) {
+ yield* recPermute(end - 1);
+ // Rotate values[i:].
+ var tmp = values.first;
+ for (var k = 1; k < end; k++) values[k - 1] = values[k];
+ values[end - 1] = tmp;
+ }
+ }
+
+ return recPermute(values.length);
+}
+
+// static function, used as constant value.
+void function() {}
+
+class Hashable {
+ final Object o;
+ Hashable(this.o);
+ bool operator ==(Object other) => other is Hashable && o == other.o;
+ int get hashCode => o.hashCode;
+}
diff --git a/tests/corelib_2/object_hash_test.dart b/tests/corelib_2/object_hash_test.dart
new file mode 100644
index 0000000..704d1f3
--- /dev/null
+++ b/tests/corelib_2/object_hash_test.dart
@@ -0,0 +1,119 @@
+// Copyright (c) 2018, the Dart project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+import "dart:typed_data";
+
+import "package:expect/expect.dart";
+
+main() {
+ const nan = double.nan;
+ const inf = double.infinity;
+
+ int hash1234 = Object.hash(1, 2, 3, 4);
+ Expect.type<int>(hash1234);
+ Expect.equals(hash1234, Object.hash(1, 2, 3, 4)); // Consistent.
+ Expect.equals(hash1234, Object.hashAll([1, 2, 3, 4]));
+ Expect.equals(hash1234, Object.hashAll(Uint8List.fromList([1, 2, 3, 4])));
+
+ Expect.notEquals(hash1234, Object.hash(1, 2, 3, 4, null));
+
+ Expect.equals(Object.hash(1, 2, 3, 4, 5, 6, 7, 8, 9),
+ Object.hashAll([1, 2, 3, 4, 5, 6, 7, 8, 9]));
+
+ // Works for all kinds of objects;
+ int varHash = Object.hash(
+ "string", 3, nan, true, null, Type, #Symbol, const Object(), function);
+ Expect.equals(
+ varHash,
+ Object.hashAll([
+ "string",
+ 3,
+ nan,
+ true,
+ null,
+ Type,
+ #Symbol,
+ const Object(),
+ function
+ ]));
+
+ // Object doesn't matter, just its hash code.
+ Expect.equals(hash1234,
+ Object.hash(Hashable(1), Hashable(2), Hashable(3), Hashable(4)));
+
+ // It's potentially possible to get a conflict, but it doesn't happen here.
+ Expect.notEquals("str".hashCode, Object.hashAll(["str"]));
+
+ var hash12345 = Object.hashAllUnordered([1, 2, 3, 4, 5]);
+ for (var p in permutations([1, 2, 3, 4, 5])) {
+ Expect.equals(hash12345, Object.hashAllUnordered(p));
+ }
+ Expect.notEquals(
+ Object.hashAllUnordered(["a", "a"]), Object.hashAllUnordered(["a"]));
+
+ Expect.notEquals(Object.hashAllUnordered(["a", "a"]),
+ Object.hashAllUnordered(["a", "a", "a", "a"]));
+
+ Expect.notEquals(Object.hashAllUnordered(["a", "b"]),
+ Object.hashAllUnordered(["a", "a", "a", "b"]));
+
+ /// Unordered hashing works for all kinds of objects.
+ var unorderHash = Object.hashAllUnordered([
+ "string",
+ 3,
+ nan,
+ true,
+ null,
+ Type,
+ #Symbol,
+ const Object(),
+ function,
+ ]);
+
+ var unorderHash2 = Object.hashAllUnordered([
+ true,
+ const Object(),
+ 3,
+ function,
+ Type,
+ "string",
+ null,
+ nan,
+ #Symbol,
+ ]);
+ Expect.equals(unorderHash, unorderHash2);
+}
+
+/// Lazily emits all permutations of [values].
+///
+/// Modifes [values] rather than create a new list.
+/// The [values] list is guaranteed to end up in its original state
+/// after all permutations have been read.
+Iterable<List<T>> permutations<T>(List<T> values) {
+ Iterable<List<T>> recPermute(int end) sync* {
+ if (end == 1) {
+ yield values;
+ return;
+ }
+ for (var i = 0; i < end; i++) {
+ yield* recPermute(end - 1);
+ // Rotate values[i:].
+ var tmp = values.first;
+ for (var k = 1; k < end; k++) values[k - 1] = values[k];
+ values[end - 1] = tmp;
+ }
+ }
+
+ return recPermute(values.length);
+}
+
+// static function, used as constant value.
+void function() {}
+
+class Hashable {
+ final Object o;
+ Hashable(this.o);
+ bool operator ==(Object other) => other is Hashable && o == other.o;
+ int get hashCode => o.hashCode;
+}
diff --git a/tests/lib/mirrors/class_declarations_test.dart b/tests/lib/mirrors/class_declarations_test.dart
index 83f8964..2cbf8de 100644
--- a/tests/lib/mirrors/class_declarations_test.dart
+++ b/tests/lib/mirrors/class_declarations_test.dart
@@ -10,11 +10,18 @@
import 'stringify.dart';
import 'declarations_model.dart' as declarations_model;
-Set<DeclarationMirror> inheritedDeclarations(ClassMirror? cm) {
+/// Collects all declarations of [cm] and its super-classes except `Object`.
+///
+/// Includes static declarations of super-classes.
+///
+/// The `Object` class is omitted because this test should be stable against
+/// changes to the platform libraries, as long as the declaration model code
+/// doesn't change.
+Set<DeclarationMirror> transitiveDeclarations(ClassMirror cm) {
var decls = new Set<DeclarationMirror>();
- while (cm != null) {
+ while (cm != reflectClass(Object)) {
decls.addAll(cm.declarations.values);
- cm = cm.superclass;
+ cm = cm.superclass!;
}
return decls;
}
@@ -163,14 +170,12 @@
'Method(s(*) in s(Mixin))',
'Method(s(+) in s(Class))',
'Method(s(-) in s(Superclass))',
- 'Method(s(==) in s(Object))',
'TypeVariable(s(C) in s(Class),'
' upperBound = Class(s(Object) in s(dart.core), top-level))',
'Method(s(Class.generativeConstructor) in s(Class), constructor)',
'Method(s(Class.normalFactory) in s(Class), static, constructor)',
'Method(s(Class.redirectingConstructor) in s(Class), constructor)',
'Method(s(Class.redirectingFactory) in s(Class), static, constructor)',
- 'Method(s(Object) in s(Object), constructor)',
'TypeVariable(s(S) in s(Superclass),'
' upperBound = Class(s(Object) in s(dart.core), top-level))',
'Method(s(Superclass.inheritedGenerativeConstructor)'
@@ -182,7 +187,6 @@
'Method(s(Superclass.inheritedRedirectingFactory)'
' in s(Superclass), static, constructor)',
'Method(s(abstractMethod) in s(Class), abstract)',
- 'Method(s(hashCode) in s(Object), getter)',
'Method(s(inheritedInstanceGetter) in s(Superclass), getter)',
'Method(s(inheritedInstanceMethod) in s(Superclass))',
'Method(s(inheritedInstanceSetter=) in s(Superclass), setter)',
@@ -199,8 +203,6 @@
'Method(s(mixinInstanceMethod) in s(Mixin))',
'Method(s(mixinInstanceSetter=) in s(Mixin), setter)',
'Variable(s(mixinInstanceVariable) in s(Mixin))',
- 'Method(s(noSuchMethod) in s(Object))',
- 'Method(s(runtimeType) in s(Object), getter)',
'Method(s(staticGetter) in s(Class), static, getter)',
'Method(s(staticMethod) in s(Class), static)',
'Method(s(staticSetter=) in s(Class), static, setter)',
@@ -213,12 +215,11 @@
' with test.declarations_model.Mixin.inheritedRedirectingConstructor)'
' in s(test.declarations_model.Superclass'
' with test.declarations_model.Mixin), constructor)',
- 'Method(s(toString) in s(Object))',
'Variable(s(mixinStaticVariable) in s(Mixin), static)',
'Method(s(mixinStaticGetter) in s(Mixin), static, getter)',
'Method(s(mixinStaticSetter=) in s(Mixin), static, setter)',
'Method(s(mixinStaticMethod) in s(Mixin), static)'
- ], inheritedDeclarations(cm).where((dm) => !dm.isPrivate).map(stringify),
+ ], transitiveDeclarations(cm).where((dm) => !dm.isPrivate).map(stringify),
'transitive public');
// The public members of Object should be the same in all implementations, so
// we don't exclude Object here.
@@ -256,113 +257,106 @@
'Variable(s(staticVariable) in s(Class), static)'
], cm.declarations.values.map(stringify), 'declarations');
- Expect.setEquals(
- [
- 'Method(s(*) in s(Mixin))',
- 'Method(s(+) in s(Class))',
- 'Method(s(-) in s(Superclass))',
- 'TypeVariable(s(C) in s(Class),'
- ' upperBound = Class(s(Object) in s(dart.core), top-level))',
- 'Method(s(Class._generativeConstructor) in s(Class), private, constructor)',
- 'Method(s(Class._normalFactory) in s(Class), private, static, constructor)',
- 'Method(s(Class._redirectingConstructor)'
- ' in s(Class), private, constructor)',
- 'Method(s(Class._redirectingFactory)'
- ' in s(Class), private, static, constructor)',
- 'Method(s(Class.generativeConstructor) in s(Class), constructor)',
- 'Method(s(Class.normalFactory) in s(Class), static, constructor)',
- 'Method(s(Class.redirectingConstructor) in s(Class), constructor)',
- 'Method(s(Class.redirectingFactory) in s(Class), static, constructor)',
- 'TypeVariable(s(S) in s(Superclass),'
- ' upperBound = Class(s(Object) in s(dart.core), top-level))',
- 'Method(s(Superclass._inheritedGenerativeConstructor)'
- ' in s(Superclass), private, constructor)',
- 'Method(s(Superclass._inheritedNormalFactory)'
- ' in s(Superclass), private, static, constructor)',
- 'Method(s(Superclass._inheritedRedirectingConstructor)'
- ' in s(Superclass), private, constructor)',
- 'Method(s(Superclass._inheritedRedirectingFactory)'
- ' in s(Superclass), private, static, constructor)',
- 'Method(s(Superclass.inheritedGenerativeConstructor)'
- ' in s(Superclass), constructor)',
- 'Method(s(Superclass.inheritedNormalFactory)'
- ' in s(Superclass), static, constructor)',
- 'Method(s(Superclass.inheritedRedirectingConstructor)'
- ' in s(Superclass), constructor)',
- 'Method(s(Superclass.inheritedRedirectingFactory)'
- ' in s(Superclass), static, constructor)',
- 'Method(s(_inheritedInstanceGetter) in s(Superclass), private, getter)',
- 'Method(s(_inheritedInstanceMethod) in s(Superclass), private)',
- 'Method(s(_inheritedInstanceSetter=) in s(Superclass), private, setter)',
- 'Variable(s(_inheritedInstanceVariable) in s(Superclass), private)',
- 'Method(s(_inheritedStaticGetter)'
- ' in s(Superclass), private, static, getter)',
- 'Method(s(_inheritedStaticMethod) in s(Superclass), private, static)',
- 'Method(s(_inheritedStaticSetter=)'
- ' in s(Superclass), private, static, setter)',
- 'Variable(s(_inheritedStaticVariable) in s(Superclass), private, static)',
- 'Method(s(_instanceGetter) in s(Class), private, getter)',
- 'Method(s(_instanceMethod) in s(Class), private)',
- 'Method(s(_instanceSetter=) in s(Class), private, setter)',
- 'Variable(s(_instanceVariable) in s(Class), private)',
- 'Method(s(_mixinInstanceGetter) in s(Mixin), private, getter)',
- 'Method(s(_mixinInstanceMethod) in s(Mixin), private)',
- 'Method(s(_mixinInstanceSetter=) in s(Mixin), private, setter)',
- 'Variable(s(_mixinInstanceVariable) in s(Mixin), private)',
- 'Method(s(_staticGetter) in s(Class), private, static, getter)',
- 'Method(s(_staticMethod) in s(Class), private, static)',
- 'Method(s(_staticSetter=) in s(Class), private, static, setter)',
- 'Variable(s(_staticVariable) in s(Class), private, static)',
- 'Method(s(abstractMethod) in s(Class), abstract)',
- 'Method(s(inheritedInstanceGetter) in s(Superclass), getter)',
- 'Method(s(inheritedInstanceMethod) in s(Superclass))',
- 'Method(s(inheritedInstanceSetter=) in s(Superclass), setter)',
- 'Variable(s(inheritedInstanceVariable) in s(Superclass))',
- 'Method(s(inheritedStaticGetter) in s(Superclass), static, getter)',
- 'Method(s(inheritedStaticMethod) in s(Superclass), static)',
- 'Method(s(inheritedStaticSetter=) in s(Superclass), static, setter)',
- 'Variable(s(inheritedStaticVariable) in s(Superclass), static)',
- 'Method(s(instanceGetter) in s(Class), getter)',
- 'Method(s(instanceMethod) in s(Class))',
- 'Method(s(instanceSetter=) in s(Class), setter)',
- 'Variable(s(instanceVariable) in s(Class))',
- 'Method(s(mixinInstanceGetter) in s(Mixin), getter)',
- 'Method(s(mixinInstanceMethod) in s(Mixin))',
- 'Method(s(mixinInstanceSetter=) in s(Mixin), setter)',
- 'Variable(s(mixinInstanceVariable) in s(Mixin))',
- 'Method(s(staticGetter) in s(Class), static, getter)',
- 'Method(s(staticMethod) in s(Class), static)',
- 'Method(s(staticSetter=) in s(Class), static, setter)',
- 'Variable(s(staticVariable) in s(Class), static)',
- 'Method(s(test.declarations_model.Superclass'
- ' with test.declarations_model.Mixin._inheritedGenerativeConstructor)'
- ' in s(test.declarations_model.Superclass'
- ' with test.declarations_model.Mixin), private, constructor)',
- 'Method(s(test.declarations_model.Superclass'
- ' with test.declarations_model.Mixin._inheritedRedirectingConstructor)'
- ' in s(test.declarations_model.Superclass'
- ' with test.declarations_model.Mixin), private, constructor)',
- 'Method(s(test.declarations_model.Superclass'
- ' with test.declarations_model.Mixin.inheritedGenerativeConstructor)'
- ' in s(test.declarations_model.Superclass'
- ' with test.declarations_model.Mixin), constructor)',
- 'Method(s(test.declarations_model.Superclass'
- ' with test.declarations_model.Mixin.inheritedRedirectingConstructor)'
- ' in s(test.declarations_model.Superclass'
- ' with test.declarations_model.Mixin), constructor)',
- 'Variable(s(mixinStaticVariable) in s(Mixin), static)',
- 'Variable(s(_mixinStaticVariable) in s(Mixin), private, static)',
- 'Method(s(mixinStaticGetter) in s(Mixin), static, getter)',
- 'Method(s(mixinStaticSetter=) in s(Mixin), static, setter)',
- 'Method(s(mixinStaticMethod) in s(Mixin), static)',
- 'Method(s(_mixinStaticGetter) in s(Mixin), private, static, getter)',
- 'Method(s(_mixinStaticSetter=) in s(Mixin), private, static, setter)',
- 'Method(s(_mixinStaticMethod) in s(Mixin), private, static)'
- ],
- inheritedDeclarations(cm)
- .difference(reflectClass(Object).declarations.values.toSet())
- .map(stringify),
- 'transitive less Object');
- // The private members of Object may vary across implementations, so we
- // exclude the declarations of Object in this test case.
+ Expect.setEquals([
+ 'Method(s(*) in s(Mixin))',
+ 'Method(s(+) in s(Class))',
+ 'Method(s(-) in s(Superclass))',
+ 'TypeVariable(s(C) in s(Class),'
+ ' upperBound = Class(s(Object) in s(dart.core), top-level))',
+ 'Method(s(Class._generativeConstructor) in s(Class), private, constructor)',
+ 'Method(s(Class._normalFactory) in s(Class), private, static, constructor)',
+ 'Method(s(Class._redirectingConstructor)'
+ ' in s(Class), private, constructor)',
+ 'Method(s(Class._redirectingFactory)'
+ ' in s(Class), private, static, constructor)',
+ 'Method(s(Class.generativeConstructor) in s(Class), constructor)',
+ 'Method(s(Class.normalFactory) in s(Class), static, constructor)',
+ 'Method(s(Class.redirectingConstructor) in s(Class), constructor)',
+ 'Method(s(Class.redirectingFactory) in s(Class), static, constructor)',
+ 'TypeVariable(s(S) in s(Superclass),'
+ ' upperBound = Class(s(Object) in s(dart.core), top-level))',
+ 'Method(s(Superclass._inheritedGenerativeConstructor)'
+ ' in s(Superclass), private, constructor)',
+ 'Method(s(Superclass._inheritedNormalFactory)'
+ ' in s(Superclass), private, static, constructor)',
+ 'Method(s(Superclass._inheritedRedirectingConstructor)'
+ ' in s(Superclass), private, constructor)',
+ 'Method(s(Superclass._inheritedRedirectingFactory)'
+ ' in s(Superclass), private, static, constructor)',
+ 'Method(s(Superclass.inheritedGenerativeConstructor)'
+ ' in s(Superclass), constructor)',
+ 'Method(s(Superclass.inheritedNormalFactory)'
+ ' in s(Superclass), static, constructor)',
+ 'Method(s(Superclass.inheritedRedirectingConstructor)'
+ ' in s(Superclass), constructor)',
+ 'Method(s(Superclass.inheritedRedirectingFactory)'
+ ' in s(Superclass), static, constructor)',
+ 'Method(s(_inheritedInstanceGetter) in s(Superclass), private, getter)',
+ 'Method(s(_inheritedInstanceMethod) in s(Superclass), private)',
+ 'Method(s(_inheritedInstanceSetter=) in s(Superclass), private, setter)',
+ 'Variable(s(_inheritedInstanceVariable) in s(Superclass), private)',
+ 'Method(s(_inheritedStaticGetter)'
+ ' in s(Superclass), private, static, getter)',
+ 'Method(s(_inheritedStaticMethod) in s(Superclass), private, static)',
+ 'Method(s(_inheritedStaticSetter=)'
+ ' in s(Superclass), private, static, setter)',
+ 'Variable(s(_inheritedStaticVariable) in s(Superclass), private, static)',
+ 'Method(s(_instanceGetter) in s(Class), private, getter)',
+ 'Method(s(_instanceMethod) in s(Class), private)',
+ 'Method(s(_instanceSetter=) in s(Class), private, setter)',
+ 'Variable(s(_instanceVariable) in s(Class), private)',
+ 'Method(s(_mixinInstanceGetter) in s(Mixin), private, getter)',
+ 'Method(s(_mixinInstanceMethod) in s(Mixin), private)',
+ 'Method(s(_mixinInstanceSetter=) in s(Mixin), private, setter)',
+ 'Variable(s(_mixinInstanceVariable) in s(Mixin), private)',
+ 'Method(s(_staticGetter) in s(Class), private, static, getter)',
+ 'Method(s(_staticMethod) in s(Class), private, static)',
+ 'Method(s(_staticSetter=) in s(Class), private, static, setter)',
+ 'Variable(s(_staticVariable) in s(Class), private, static)',
+ 'Method(s(abstractMethod) in s(Class), abstract)',
+ 'Method(s(inheritedInstanceGetter) in s(Superclass), getter)',
+ 'Method(s(inheritedInstanceMethod) in s(Superclass))',
+ 'Method(s(inheritedInstanceSetter=) in s(Superclass), setter)',
+ 'Variable(s(inheritedInstanceVariable) in s(Superclass))',
+ 'Method(s(inheritedStaticGetter) in s(Superclass), static, getter)',
+ 'Method(s(inheritedStaticMethod) in s(Superclass), static)',
+ 'Method(s(inheritedStaticSetter=) in s(Superclass), static, setter)',
+ 'Variable(s(inheritedStaticVariable) in s(Superclass), static)',
+ 'Method(s(instanceGetter) in s(Class), getter)',
+ 'Method(s(instanceMethod) in s(Class))',
+ 'Method(s(instanceSetter=) in s(Class), setter)',
+ 'Variable(s(instanceVariable) in s(Class))',
+ 'Method(s(mixinInstanceGetter) in s(Mixin), getter)',
+ 'Method(s(mixinInstanceMethod) in s(Mixin))',
+ 'Method(s(mixinInstanceSetter=) in s(Mixin), setter)',
+ 'Variable(s(mixinInstanceVariable) in s(Mixin))',
+ 'Method(s(staticGetter) in s(Class), static, getter)',
+ 'Method(s(staticMethod) in s(Class), static)',
+ 'Method(s(staticSetter=) in s(Class), static, setter)',
+ 'Variable(s(staticVariable) in s(Class), static)',
+ 'Method(s(test.declarations_model.Superclass'
+ ' with test.declarations_model.Mixin._inheritedGenerativeConstructor)'
+ ' in s(test.declarations_model.Superclass'
+ ' with test.declarations_model.Mixin), private, constructor)',
+ 'Method(s(test.declarations_model.Superclass'
+ ' with test.declarations_model.Mixin._inheritedRedirectingConstructor)'
+ ' in s(test.declarations_model.Superclass'
+ ' with test.declarations_model.Mixin), private, constructor)',
+ 'Method(s(test.declarations_model.Superclass'
+ ' with test.declarations_model.Mixin.inheritedGenerativeConstructor)'
+ ' in s(test.declarations_model.Superclass'
+ ' with test.declarations_model.Mixin), constructor)',
+ 'Method(s(test.declarations_model.Superclass'
+ ' with test.declarations_model.Mixin.inheritedRedirectingConstructor)'
+ ' in s(test.declarations_model.Superclass'
+ ' with test.declarations_model.Mixin), constructor)',
+ 'Variable(s(mixinStaticVariable) in s(Mixin), static)',
+ 'Variable(s(_mixinStaticVariable) in s(Mixin), private, static)',
+ 'Method(s(mixinStaticGetter) in s(Mixin), static, getter)',
+ 'Method(s(mixinStaticSetter=) in s(Mixin), static, setter)',
+ 'Method(s(mixinStaticMethod) in s(Mixin), static)',
+ 'Method(s(_mixinStaticGetter) in s(Mixin), private, static, getter)',
+ 'Method(s(_mixinStaticSetter=) in s(Mixin), private, static, setter)',
+ 'Method(s(_mixinStaticMethod) in s(Mixin), private, static)'
+ ], transitiveDeclarations(cm).map(stringify), 'transitive all');
}
diff --git a/tests/lib_2/mirrors/class_declarations_test.dart b/tests/lib_2/mirrors/class_declarations_test.dart
index f0a121c..72619da 100644
--- a/tests/lib_2/mirrors/class_declarations_test.dart
+++ b/tests/lib_2/mirrors/class_declarations_test.dart
@@ -10,9 +10,16 @@
import 'stringify.dart';
import 'declarations_model.dart' as declarations_model;
-Set<DeclarationMirror> inheritedDeclarations(ClassMirror cm) {
+/// Collects all declarations of [cm] and its super-classes except `Object`.
+///
+/// Includes static declarations of super-classes.
+///
+/// The `Object` class is omitted because this test should be stable against
+/// changes to the platform libraries, as long as the declaration model code
+/// doesn't change.
+Set<DeclarationMirror> transitiveDeclarations(ClassMirror cm) {
var decls = new Set<DeclarationMirror>();
- while (cm != null) {
+ while (cm != reflectClass(Object)) {
decls.addAll(cm.declarations.values);
cm = cm.superclass;
}
@@ -163,14 +170,12 @@
'Method(s(*) in s(Mixin))',
'Method(s(+) in s(Class))',
'Method(s(-) in s(Superclass))',
- 'Method(s(==) in s(Object))',
'TypeVariable(s(C) in s(Class),'
' upperBound = Class(s(Object) in s(dart.core), top-level))',
'Method(s(Class.generativeConstructor) in s(Class), constructor)',
'Method(s(Class.normalFactory) in s(Class), static, constructor)',
'Method(s(Class.redirectingConstructor) in s(Class), constructor)',
'Method(s(Class.redirectingFactory) in s(Class), static, constructor)',
- 'Method(s(Object) in s(Object), constructor)',
'TypeVariable(s(S) in s(Superclass),'
' upperBound = Class(s(Object) in s(dart.core), top-level))',
'Method(s(Superclass.inheritedGenerativeConstructor)'
@@ -182,7 +187,6 @@
'Method(s(Superclass.inheritedRedirectingFactory)'
' in s(Superclass), static, constructor)',
'Method(s(abstractMethod) in s(Class), abstract)',
- 'Method(s(hashCode) in s(Object), getter)',
'Method(s(inheritedInstanceGetter) in s(Superclass), getter)',
'Method(s(inheritedInstanceMethod) in s(Superclass))',
'Method(s(inheritedInstanceSetter=) in s(Superclass), setter)',
@@ -199,8 +203,6 @@
'Method(s(mixinInstanceMethod) in s(Mixin))',
'Method(s(mixinInstanceSetter=) in s(Mixin), setter)',
'Variable(s(mixinInstanceVariable) in s(Mixin))',
- 'Method(s(noSuchMethod) in s(Object))',
- 'Method(s(runtimeType) in s(Object), getter)',
'Method(s(staticGetter) in s(Class), static, getter)',
'Method(s(staticMethod) in s(Class), static)',
'Method(s(staticSetter=) in s(Class), static, setter)',
@@ -213,12 +215,11 @@
' with test.declarations_model.Mixin.inheritedRedirectingConstructor)'
' in s(test.declarations_model.Superclass'
' with test.declarations_model.Mixin), constructor)',
- 'Method(s(toString) in s(Object))',
'Variable(s(mixinStaticVariable) in s(Mixin), static)',
'Method(s(mixinStaticGetter) in s(Mixin), static, getter)',
'Method(s(mixinStaticSetter=) in s(Mixin), static, setter)',
'Method(s(mixinStaticMethod) in s(Mixin), static)'
- ], inheritedDeclarations(cm).where((dm) => !dm.isPrivate).map(stringify),
+ ], transitiveDeclarations(cm).where((dm) => !dm.isPrivate).map(stringify),
'transitive public');
// The public members of Object should be the same in all implementations, so
// we don't exclude Object here.
@@ -256,113 +257,106 @@
'Variable(s(staticVariable) in s(Class), static)'
], cm.declarations.values.map(stringify), 'declarations');
- Expect.setEquals(
- [
- 'Method(s(*) in s(Mixin))',
- 'Method(s(+) in s(Class))',
- 'Method(s(-) in s(Superclass))',
- 'TypeVariable(s(C) in s(Class),'
- ' upperBound = Class(s(Object) in s(dart.core), top-level))',
- 'Method(s(Class._generativeConstructor) in s(Class), private, constructor)',
- 'Method(s(Class._normalFactory) in s(Class), private, static, constructor)',
- 'Method(s(Class._redirectingConstructor)'
- ' in s(Class), private, constructor)',
- 'Method(s(Class._redirectingFactory)'
- ' in s(Class), private, static, constructor)',
- 'Method(s(Class.generativeConstructor) in s(Class), constructor)',
- 'Method(s(Class.normalFactory) in s(Class), static, constructor)',
- 'Method(s(Class.redirectingConstructor) in s(Class), constructor)',
- 'Method(s(Class.redirectingFactory) in s(Class), static, constructor)',
- 'TypeVariable(s(S) in s(Superclass),'
- ' upperBound = Class(s(Object) in s(dart.core), top-level))',
- 'Method(s(Superclass._inheritedGenerativeConstructor)'
- ' in s(Superclass), private, constructor)',
- 'Method(s(Superclass._inheritedNormalFactory)'
- ' in s(Superclass), private, static, constructor)',
- 'Method(s(Superclass._inheritedRedirectingConstructor)'
- ' in s(Superclass), private, constructor)',
- 'Method(s(Superclass._inheritedRedirectingFactory)'
- ' in s(Superclass), private, static, constructor)',
- 'Method(s(Superclass.inheritedGenerativeConstructor)'
- ' in s(Superclass), constructor)',
- 'Method(s(Superclass.inheritedNormalFactory)'
- ' in s(Superclass), static, constructor)',
- 'Method(s(Superclass.inheritedRedirectingConstructor)'
- ' in s(Superclass), constructor)',
- 'Method(s(Superclass.inheritedRedirectingFactory)'
- ' in s(Superclass), static, constructor)',
- 'Method(s(_inheritedInstanceGetter) in s(Superclass), private, getter)',
- 'Method(s(_inheritedInstanceMethod) in s(Superclass), private)',
- 'Method(s(_inheritedInstanceSetter=) in s(Superclass), private, setter)',
- 'Variable(s(_inheritedInstanceVariable) in s(Superclass), private)',
- 'Method(s(_inheritedStaticGetter)'
- ' in s(Superclass), private, static, getter)',
- 'Method(s(_inheritedStaticMethod) in s(Superclass), private, static)',
- 'Method(s(_inheritedStaticSetter=)'
- ' in s(Superclass), private, static, setter)',
- 'Variable(s(_inheritedStaticVariable) in s(Superclass), private, static)',
- 'Method(s(_instanceGetter) in s(Class), private, getter)',
- 'Method(s(_instanceMethod) in s(Class), private)',
- 'Method(s(_instanceSetter=) in s(Class), private, setter)',
- 'Variable(s(_instanceVariable) in s(Class), private)',
- 'Method(s(_mixinInstanceGetter) in s(Mixin), private, getter)',
- 'Method(s(_mixinInstanceMethod) in s(Mixin), private)',
- 'Method(s(_mixinInstanceSetter=) in s(Mixin), private, setter)',
- 'Variable(s(_mixinInstanceVariable) in s(Mixin), private)',
- 'Method(s(_staticGetter) in s(Class), private, static, getter)',
- 'Method(s(_staticMethod) in s(Class), private, static)',
- 'Method(s(_staticSetter=) in s(Class), private, static, setter)',
- 'Variable(s(_staticVariable) in s(Class), private, static)',
- 'Method(s(abstractMethod) in s(Class), abstract)',
- 'Method(s(inheritedInstanceGetter) in s(Superclass), getter)',
- 'Method(s(inheritedInstanceMethod) in s(Superclass))',
- 'Method(s(inheritedInstanceSetter=) in s(Superclass), setter)',
- 'Variable(s(inheritedInstanceVariable) in s(Superclass))',
- 'Method(s(inheritedStaticGetter) in s(Superclass), static, getter)',
- 'Method(s(inheritedStaticMethod) in s(Superclass), static)',
- 'Method(s(inheritedStaticSetter=) in s(Superclass), static, setter)',
- 'Variable(s(inheritedStaticVariable) in s(Superclass), static)',
- 'Method(s(instanceGetter) in s(Class), getter)',
- 'Method(s(instanceMethod) in s(Class))',
- 'Method(s(instanceSetter=) in s(Class), setter)',
- 'Variable(s(instanceVariable) in s(Class))',
- 'Method(s(mixinInstanceGetter) in s(Mixin), getter)',
- 'Method(s(mixinInstanceMethod) in s(Mixin))',
- 'Method(s(mixinInstanceSetter=) in s(Mixin), setter)',
- 'Variable(s(mixinInstanceVariable) in s(Mixin))',
- 'Method(s(staticGetter) in s(Class), static, getter)',
- 'Method(s(staticMethod) in s(Class), static)',
- 'Method(s(staticSetter=) in s(Class), static, setter)',
- 'Variable(s(staticVariable) in s(Class), static)',
- 'Method(s(test.declarations_model.Superclass'
- ' with test.declarations_model.Mixin._inheritedGenerativeConstructor)'
- ' in s(test.declarations_model.Superclass'
- ' with test.declarations_model.Mixin), private, constructor)',
- 'Method(s(test.declarations_model.Superclass'
- ' with test.declarations_model.Mixin._inheritedRedirectingConstructor)'
- ' in s(test.declarations_model.Superclass'
- ' with test.declarations_model.Mixin), private, constructor)',
- 'Method(s(test.declarations_model.Superclass'
- ' with test.declarations_model.Mixin.inheritedGenerativeConstructor)'
- ' in s(test.declarations_model.Superclass'
- ' with test.declarations_model.Mixin), constructor)',
- 'Method(s(test.declarations_model.Superclass'
- ' with test.declarations_model.Mixin.inheritedRedirectingConstructor)'
- ' in s(test.declarations_model.Superclass'
- ' with test.declarations_model.Mixin), constructor)',
- 'Variable(s(mixinStaticVariable) in s(Mixin), static)',
- 'Variable(s(_mixinStaticVariable) in s(Mixin), private, static)',
- 'Method(s(mixinStaticGetter) in s(Mixin), static, getter)',
- 'Method(s(mixinStaticSetter=) in s(Mixin), static, setter)',
- 'Method(s(mixinStaticMethod) in s(Mixin), static)',
- 'Method(s(_mixinStaticGetter) in s(Mixin), private, static, getter)',
- 'Method(s(_mixinStaticSetter=) in s(Mixin), private, static, setter)',
- 'Method(s(_mixinStaticMethod) in s(Mixin), private, static)'
- ],
- inheritedDeclarations(cm)
- .difference(reflectClass(Object).declarations.values.toSet())
- .map(stringify),
- 'transitive less Object');
- // The private members of Object may vary across implementations, so we
- // exclude the declarations of Object in this test case.
+ Expect.setEquals([
+ 'Method(s(*) in s(Mixin))',
+ 'Method(s(+) in s(Class))',
+ 'Method(s(-) in s(Superclass))',
+ 'TypeVariable(s(C) in s(Class),'
+ ' upperBound = Class(s(Object) in s(dart.core), top-level))',
+ 'Method(s(Class._generativeConstructor) in s(Class), private, constructor)',
+ 'Method(s(Class._normalFactory) in s(Class), private, static, constructor)',
+ 'Method(s(Class._redirectingConstructor)'
+ ' in s(Class), private, constructor)',
+ 'Method(s(Class._redirectingFactory)'
+ ' in s(Class), private, static, constructor)',
+ 'Method(s(Class.generativeConstructor) in s(Class), constructor)',
+ 'Method(s(Class.normalFactory) in s(Class), static, constructor)',
+ 'Method(s(Class.redirectingConstructor) in s(Class), constructor)',
+ 'Method(s(Class.redirectingFactory) in s(Class), static, constructor)',
+ 'TypeVariable(s(S) in s(Superclass),'
+ ' upperBound = Class(s(Object) in s(dart.core), top-level))',
+ 'Method(s(Superclass._inheritedGenerativeConstructor)'
+ ' in s(Superclass), private, constructor)',
+ 'Method(s(Superclass._inheritedNormalFactory)'
+ ' in s(Superclass), private, static, constructor)',
+ 'Method(s(Superclass._inheritedRedirectingConstructor)'
+ ' in s(Superclass), private, constructor)',
+ 'Method(s(Superclass._inheritedRedirectingFactory)'
+ ' in s(Superclass), private, static, constructor)',
+ 'Method(s(Superclass.inheritedGenerativeConstructor)'
+ ' in s(Superclass), constructor)',
+ 'Method(s(Superclass.inheritedNormalFactory)'
+ ' in s(Superclass), static, constructor)',
+ 'Method(s(Superclass.inheritedRedirectingConstructor)'
+ ' in s(Superclass), constructor)',
+ 'Method(s(Superclass.inheritedRedirectingFactory)'
+ ' in s(Superclass), static, constructor)',
+ 'Method(s(_inheritedInstanceGetter) in s(Superclass), private, getter)',
+ 'Method(s(_inheritedInstanceMethod) in s(Superclass), private)',
+ 'Method(s(_inheritedInstanceSetter=) in s(Superclass), private, setter)',
+ 'Variable(s(_inheritedInstanceVariable) in s(Superclass), private)',
+ 'Method(s(_inheritedStaticGetter)'
+ ' in s(Superclass), private, static, getter)',
+ 'Method(s(_inheritedStaticMethod) in s(Superclass), private, static)',
+ 'Method(s(_inheritedStaticSetter=)'
+ ' in s(Superclass), private, static, setter)',
+ 'Variable(s(_inheritedStaticVariable) in s(Superclass), private, static)',
+ 'Method(s(_instanceGetter) in s(Class), private, getter)',
+ 'Method(s(_instanceMethod) in s(Class), private)',
+ 'Method(s(_instanceSetter=) in s(Class), private, setter)',
+ 'Variable(s(_instanceVariable) in s(Class), private)',
+ 'Method(s(_mixinInstanceGetter) in s(Mixin), private, getter)',
+ 'Method(s(_mixinInstanceMethod) in s(Mixin), private)',
+ 'Method(s(_mixinInstanceSetter=) in s(Mixin), private, setter)',
+ 'Variable(s(_mixinInstanceVariable) in s(Mixin), private)',
+ 'Method(s(_staticGetter) in s(Class), private, static, getter)',
+ 'Method(s(_staticMethod) in s(Class), private, static)',
+ 'Method(s(_staticSetter=) in s(Class), private, static, setter)',
+ 'Variable(s(_staticVariable) in s(Class), private, static)',
+ 'Method(s(abstractMethod) in s(Class), abstract)',
+ 'Method(s(inheritedInstanceGetter) in s(Superclass), getter)',
+ 'Method(s(inheritedInstanceMethod) in s(Superclass))',
+ 'Method(s(inheritedInstanceSetter=) in s(Superclass), setter)',
+ 'Variable(s(inheritedInstanceVariable) in s(Superclass))',
+ 'Method(s(inheritedStaticGetter) in s(Superclass), static, getter)',
+ 'Method(s(inheritedStaticMethod) in s(Superclass), static)',
+ 'Method(s(inheritedStaticSetter=) in s(Superclass), static, setter)',
+ 'Variable(s(inheritedStaticVariable) in s(Superclass), static)',
+ 'Method(s(instanceGetter) in s(Class), getter)',
+ 'Method(s(instanceMethod) in s(Class))',
+ 'Method(s(instanceSetter=) in s(Class), setter)',
+ 'Variable(s(instanceVariable) in s(Class))',
+ 'Method(s(mixinInstanceGetter) in s(Mixin), getter)',
+ 'Method(s(mixinInstanceMethod) in s(Mixin))',
+ 'Method(s(mixinInstanceSetter=) in s(Mixin), setter)',
+ 'Variable(s(mixinInstanceVariable) in s(Mixin))',
+ 'Method(s(staticGetter) in s(Class), static, getter)',
+ 'Method(s(staticMethod) in s(Class), static)',
+ 'Method(s(staticSetter=) in s(Class), static, setter)',
+ 'Variable(s(staticVariable) in s(Class), static)',
+ 'Method(s(test.declarations_model.Superclass'
+ ' with test.declarations_model.Mixin._inheritedGenerativeConstructor)'
+ ' in s(test.declarations_model.Superclass'
+ ' with test.declarations_model.Mixin), private, constructor)',
+ 'Method(s(test.declarations_model.Superclass'
+ ' with test.declarations_model.Mixin._inheritedRedirectingConstructor)'
+ ' in s(test.declarations_model.Superclass'
+ ' with test.declarations_model.Mixin), private, constructor)',
+ 'Method(s(test.declarations_model.Superclass'
+ ' with test.declarations_model.Mixin.inheritedGenerativeConstructor)'
+ ' in s(test.declarations_model.Superclass'
+ ' with test.declarations_model.Mixin), constructor)',
+ 'Method(s(test.declarations_model.Superclass'
+ ' with test.declarations_model.Mixin.inheritedRedirectingConstructor)'
+ ' in s(test.declarations_model.Superclass'
+ ' with test.declarations_model.Mixin), constructor)',
+ 'Variable(s(mixinStaticVariable) in s(Mixin), static)',
+ 'Variable(s(_mixinStaticVariable) in s(Mixin), private, static)',
+ 'Method(s(mixinStaticGetter) in s(Mixin), static, getter)',
+ 'Method(s(mixinStaticSetter=) in s(Mixin), static, setter)',
+ 'Method(s(mixinStaticMethod) in s(Mixin), static)',
+ 'Method(s(_mixinStaticGetter) in s(Mixin), private, static, getter)',
+ 'Method(s(_mixinStaticSetter=) in s(Mixin), private, static, setter)',
+ 'Method(s(_mixinStaticMethod) in s(Mixin), private, static)'
+ ], transitiveDeclarations(cm).map(stringify), 'transitive all');
}
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Dan Field (Gerrit)
1 comment:
File sdk/lib/core/object.dart:
Patch Set #23, Line 157:
if (sentinelValue == object3) {
I ask because I started out using `identical`, but changed it in patch set 3 after comments from Ste […]
I'm having trouble finding that comment :) I'm not sure why the VM doesn't optimize for this, perhaps Alex Markov would know.
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Alexander Markov (Gerrit)
1 comment:
File sdk/lib/core/object.dart:
Patch Set #23, Line 157:
if (sentinelValue == object3) {
I'm having trouble finding that comment :) I'm not sure why the VM doesn't optimize for this, perhap […]
VM can optimize 'sentinelValue == object3' but not 'object3 == sentinelValue' (as in https://github.com/flutter/engine/pull/19615), because in the latter case call to operator== is polymorphic if class of object3 varies. If VM can prove that operator== call will always dispatch to Object.==, then it is inlined and generated similarly to identical.
On a small example
if (obj == sentinel) {
print(1);
}
if (sentinel == obj) {
print(2);
}
if (identical(sentinel, obj)) {
print(3);
}
AOT produces the following flow graph for each of these conditions ('v2' is obj, 'v3' is sentinel):6: v22 <- LoadClassId(v2)
8: PushArgument(v2)
10: PushArgument(v3)
11: ParallelMove rcx <- rcx
12: v4 <- DispatchTableCall( cid=v22 Object.==<0>, v2, v3) T{bool?}
13: ParallelMove rax <- rax
14: Branch if StrictCompare:16(===, v4 T{bool}, v6) goto (3, 4)--------
30: Branch if StrictCompare:10(===, v3, v2 T{Object}) T{bool} goto (6, 7)--------
46: Branch if StrictCompare:52(===, v3, v2) goto (9, 10)
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Dan Field (Gerrit)
1 comment:
File sdk/lib/core/object.dart:
Patch Set #23, Line 157:
if (sentinelValue == object3) {
VM can optimize 'sentinelValue == object3' but not 'object3 == sentinelValue' (as in https://github. […]
Why can't the VM just say that `==` is commutative and pick whichever version will result in smaller/optimal code?
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Alexander Markov (Gerrit)
1 comment:
File sdk/lib/core/object.dart:
Patch Set #23, Line 157:
if (sentinelValue == object3) {
Why can't the VM just say that `==` is commutative and pick whichever version will result in smaller […]
That would violate Dart language semantics. Operator== is not guaranteed to be commutative, and 'a == b' is just a syntactic sugar for 'a.operator==(b)' call (with additional checks for null).
Here is the relevant paragraph from the Dart language specification:
Evaluation of an equality expression ee of the form e1 == e2 proceeds as
follows:
• The expression e1 is evaluated to an object o1.
• The expression e2 is evaluated to an object o2.
• If either o1 or o2 is the null object (16.4), then ee evaluates to true if both
o1 and o2 are the null object and to false otherwise. Otherwise,
• evaluation of ee is equivalent to the method invocation o1.==(o2).Here is an example of Dart program which changes behavior if arguments of operator== are swapped:
class A {
operator==(Object other) => true;
}
class B {
operator==(Object other) => false;
}main() {
print(A() == B());
print(B() == A());
}
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Ian Hickson (Gerrit)
1 comment:
File sdk/lib/core/object.dart:
Patch Set #24, Line 282:
* in an order independet way.typo in "independent"
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Lasse R.H. Nielsen (Gerrit)
1 comment:
File sdk/lib/core/object.dart:
Patch Set #23, Line 157:
if (sentinelValue == object3) {That would violate Dart language semantics. […]
This code uses `_sentinelValue == object3` (quite deliberately), so it should be fine?
The comments might have been offline, and I don't remember the details. It's quite likely that we discussed a complete rewrite, and ended up with `_sentinelValue == object3` and no reason to improve on that (because it is just as good as identical). So, not a deliberate choice to not use `identical`, just no reason to go for it when we already had the current code. (But that's guessing).
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Dan Field (Gerrit)
1 comment:
File sdk/lib/core/object.dart:
Patch Set #23, Line 157:
if (sentinelValue == object3) {
This code uses `_sentinelValue == object3` (quite deliberately), so it should be fine? […]
SGTM
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Lasse R.H. Nielsen (Gerrit)
1 comment:
Patchset:
Leaf, Stephen, any comments? (Or rubberstamps, I'm not picky 😊)
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Leaf Petersen (Gerrit)
3 comments:
File sdk/lib/core/object.dart:
Patch Set #23, Line 148:
static int hash(Object? object1, Object? object2,Not if the `hash` function is inlined. The implementation is optimized for dart2js inlining. […]
Can you say more about what you mean by this? I just tried out a program with three calls to hash, and dart2js didn't inline any of them. This seems like a fairly large function for dart2js to inline speculatively.
On the second issue, this feels like it runs into the problem that I commented on separately - I don't think that `hashAll([]) == hashAll([0]) == hashAll([0, 0]) == hashAll([0, 0, 0])` is a good thing. Resolving that seems like it will break the property you want here anyway, so maybe look to achieve it differently?
File sdk/lib/core/object.dart:
Patch Set #25, Line 138:
* The hash value generated by this function is *not* guranteed to be stableguaranteed
File sdk/lib/internal/internal.dart:
Patch Set #23, Line 158:
static int hash2(int v1, int v2) {The problem with hash code algorithms is that it *might* be a breaking change to change the. […]
This isn't just a re-factoring though, right? It's exposing new API, and thereby causing exactly the problem you're describing above: sure it's a bad hash implementation, but we can't change it because it will be breaking. This is our one chance to get a good hash function in there without it being a breaking change, so why not take it? For String and Rectangle, just hand inline the hash for them - it's non-breaking, not a lot of code, and it will probably be much faster anyway, which is important for strings. Then we can have whatever hash we want for Object.hash et al.
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Lasse R.H. Nielsen (Gerrit)
2 comments:
File sdk/lib/core/object.dart:
Patch Set #23, Line 148:
static int hash(Object? object1, Object? object2,
Can you say more about what you mean by this? I just tried out a program with three calls to hash, […]
I'll have to defer to Stephen on that. Stephen?
File sdk/lib/internal/internal.dart:
Patch Set #23, Line 158:
static int hash2(int v1, int v2) {
This isn't just a re-factoring though, right? It's exposing new API, and thereby causing exactly th […]
It's both. It's combining the four internal versions of Jenkins into one implementation, *and* exposing a new public hash code.
We could split this into two CLs, and then not necessarily use the same function for the public hash functions.
It would leave the external world still not able to reproduce `String.hashCode`, but they've survived this far without being able to do that, so not necessarily a problem.
Anyone have suggestions on a better hash code combination algorithm which can be implemented efficiently in JavaScript as well?
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Sigmund Cherem (Gerrit)
1 comment:
File sdk/lib/core/object.dart:
Patch Set #23, Line 148:
static int hash(Object? object1, Object? object2,
I'll have to defer to Stephen on that. […]
DBC - FYI Stephen is OOO until next week.
I don't have the full context of the CL, but regarding inlining: currently we cannot inline this function as it is. Basically any function with more than one `return` is not inlinable at this time.
We'd love to make inlining decisions where the parameters could be used to eliminate some branches entirely (and in this case allow inlining), but we don't have that capability at this time.
I'd have to defer to Stephen to say whether that's something we can gain in the near future. We could also special case this function directly in the compiler, which sounded like what he was hinting in Patchset #3?
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Stephen Adams (Gerrit)
Attention is currently required from: Lasse R.H. Nielsen, Leaf Petersen, Sigmund Cherem.
2 comments:
Patchset:
Would you be planning on releasing this with the "Small and useful features collection" https://github.com/dart-lang/language/issues/1077 ?
File sdk/lib/core/object.dart:
Patch Set #23, Line 148:
static int hash(Object? object1, Object? object2,
DBC - FYI Stephen is OOO until next week. […]
My plan is to special-case this in the 'compiler'.
As mentioned in my comments on patchsets #2 and #3, there are two problems that need to be solved to make Object.hash deliver on performance. (1) the arity dispatch in Object.hash needs to be removed and (2) the calls to objectN.hashCode need to be specialized on some dart2js-specific instance method dispatch criteria (i.e. 'interceptors').
dart2js won't inline the function. It also can't tell that the sentinel is never passed in, so if the function was inlined, the if-then-else chain cannot necessarily be simplified ahead of the first sentinel. AOT probably has similar limitations.
To solve the dispatch problem I would rewrite `Object.hash` to call e.g. `Object._hash3(object1, object2, object3)`:
```
int _hash3(Object? object1, Object? object2, Object? object3) {
return SystemHash.hash3(object1.hashCode, object2.hashCode, object3.hashCode);
}
```The 'compiler' could then lower `Object.hash(a, b, c)` to `Object._hash3(a, b, c)`. This solves the problem with the compilers not being willing to inline a huge function and being unable to tell that the sentinels are never passed in. Perhaps this could be a common Kernel transform.
You could add the `_hashN` methods now or later.
To solve (2) I would consider inlining `_hashN` (easy to do), or specialize `_hashN` on the tuple of dispatch criteria (harder to do).
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Stephen Adams (Gerrit)
Attention is currently required from: Lasse R.H. Nielsen, Leaf Petersen, Sigmund Cherem.
Patch set 25:Code-Review +1
1 comment:
Patchset:
The flutter function that this could replace accepts up to 20 arguments: https://api.flutter.dev/flutter/dart-ui/hashValues.html
We should aim to support deprecating the flutter version.
`Object.hash` should also accept 20 arguments to allow a simple replacement.The issue with `Object.hashAll([]) = Object.hashAll([0,0,0])` can be solved by either starting with a non-zero hashcode (e.g. `int hash = 1;`) or adding in a constant with the new element in `combine` (biasing the value make some other input have this property, but making -1 have this property by adding in +1 is less likely to cause trouble). This is a detail of SystemHash.
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Lasse R.H. Nielsen (Gerrit)
Attention is currently required from: Leaf Petersen, Sigmund Cherem.
1 comment:
Patchset:
Would you be planning on releasing this with the "Small and useful features collection" https://gith […]
No, I'll just release it when it's done. It's a library feature, not a language feature.
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Lasse R.H. Nielsen (Gerrit)
Attention is currently required from: Leaf Petersen, Sigmund Cherem.
3 comments:
Patchset:
@nbosch Should we land this?
File sdk/lib/core/object.dart:
Patch Set #25, Line 138:
* The hash value generated by this function is *not* guranteed to be stableguaranteed
Done
File sdk/lib/internal/internal.dart:
Patch Set #23, Line 158:
static int hash2(int v1, int v2) {
It's both. […]
I've looked into other hash combination algorithms, and if they are better, they are generally *byte* based, which we cannot assume here.
I think we should go with what we have here.
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Lasse R.H. Nielsen (Gerrit)
Attention is currently required from: Leaf Petersen, Sigmund Cherem, Nate Bosch.
Lasse R.H. Nielsen would like Nate Bosch to review this change.
Add `Object.hash` and `Object.hashAll` static helper methods.
Fixes #11617.
Bug: http://dartbug.com/11617
Change-Id: Id06fb5b3914bee24713427edbd3b9b7e86f86449
---
M CHANGELOG.md
M sdk/lib/core/object.dart
M sdk/lib/internal/internal.dart
A tests/corelib/object_hash_test.dart
A tests/corelib_2/object_hash_test.dart
M tests/lib/mirrors/class_declarations_test.dart
M tests/lib_2/mirrors/class_declarations_test.dart
7 files changed, 687 insertions(+), 241 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 4b4cef9..6ce8761 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -22,6 +22,10 @@
daylight saving changes that are not precisely one hour.
(No change on the Web which uses the JavaScript `Date` object.)
+* Adds static methods `hash`, `hashAll` and `hashAllUnordered` to the
+ `Object` class. These can be used to combine the hash codes of
+ multiple objects in a consistent way.
+
#### `dart:ffi`
* Adds the `DynamicLibrary.providesSymbol` function to check whether a symbol
@@ -98,7 +102,7 @@
underscore.
- fix false negative in `prefer_final_parameters` where first parameter
is final.
-- improve `directives_ordering` sorting of directives with dot paths and
+- improve `directives_ordering` sorting of directives with dot paths and
dot-separated package names.
- (internal) migrate to `SecurityLintCode` instead of deprecated
`SecurityLintCodeWithUniqueName`.
diff --git a/sdk/lib/core/object.dart b/sdk/lib/core/object.dart
index 32b52bf..8088d82 100644
--- a/sdk/lib/core/object.dart
+++ b/sdk/lib/core/object.dart
@@ -146,4 +146,208 @@
/// A representation of the runtime type of the object.
external Type get runtimeType;
+
+ /**
+ * Creates a combined hash code for a number of objects.
+ *
+ * The hash code is computed for all arguments that are actually
+ * supplied, even if they are `null`, by numerically combining the
+ * [Object.hashCode] of each argument.
+ *
+ * Example:
+ * ```dart
+ * class SomeObject {
+ * final Object a, b, c;
+ * SomeObject(this.a, this.b, this.c);
+ * bool operator=(Object other) =>
+ * other is SomeObject && a == other.a && b == other.b && c == other.c;
+ * int get hashCode => Object.hash(a, b, c);
+ * }
+ * ```
+ *
+ * The computed value must be consistent when the function is called
+ * with the same arguments multiple times
+ * during the execution of a single program.
+ *
+ * The hash value generated by this function is *not* guaranteed to be stable
+ * over different runs of the same program.
+ * The exact algorithm used may differ between different platforms,
+ * or between different versions of the platform libraries,
+ * and it may depend on values that change per program run
+ *
+ * The [hashAll] function gives the same result as this function when
+ * called with a collection containing the actual arguments to this function.
+ */
+ @Since("2.14")+ @Since("2.14")
+ static int hashAll(Iterable<Object?> objects) {
+ int hash = 0;
+ for (var object in objects) {
+ hash = SystemHash.combine(hash, object.hashCode);
+ }
+ return SystemHash.finish(hash);
+ }
+
+ /**
+ * Creates a combined hash code for a collection of objects.
+ *
+ * The hash code is computed for elements in [objects],
+ * even if they are `null`,
+ * by numerically combining the [Object.hashCode] of each element
+ * in an order independent way.
+ *
+ * The result of `unorderedHashAll({o})` is not `o.hashCode`.
+ *
+ * Example:
+ * ```dart
+ * bool setEquals<T>(Set<T> set1, Set<T> set2) {
+ * var hashCode1 = Object.unorderedHashAll(set1);
+ * var hashCode2 = Object.unorderedHashAll(set2);
+ * if (hashCode1 != hashCode2) return false;
+ * // Compare elements ...
+ * }
+ * ```
+ *
+ * The computed value will be be consistent when the function is called
+ * again with objects that have the same hash codes
+ * during an execution of a single program,
+ * even if the objects are not necessarily in the same order,
+ *
+ * The hash value generated by this function is *not* guranteed to be stable
+ * over different runs of the same program.
+ * The exact algorithm used may differ between different platforms,
+ * or between different versions of the platform libraries,
+ * and it may depend on values that change per program run
+ */
+ @Since("2.14")
+ static int hashAllUnordered(Iterable<Object?> objects) {
+ int sum = 0;
+ int count = 0;
+ const int mask = 0x3FFFFFFF;
+ for (var object in objects) {
+ int objectHash = SystemHash.smear(object.hashCode);
+ sum = (sum + objectHash) & mask;
+ count += 1;
+ }
+ return SystemHash.hash2(sum, count);
+ }
}
diff --git a/sdk/lib/internal/internal.dart b/sdk/lib/internal/internal.dart
index 858f1f5..e713630 100644
--- a/sdk/lib/internal/internal.dart
+++ b/sdk/lib/internal/internal.dart
@@ -148,7 +148,7 @@
///
/// [1]: http://en.wikipedia.org/wiki/Jenkins_hash_function
///
-/// Usage:
+/// Use:
/// Hash each value with the hash of the previous value, then get the final
/// hash by calling finish.
/// ```
@@ -158,8 +158,9 @@
/// }
/// hash = SystemHash.finish(hash);
/// ```
-// TODO(lrn): Consider specializing this code per platform,
-// so the VM can use its 64-bit integers directly.
+///
+/// TODO(lrn): Consider specializing this code per platform,
+/// so the VM can use its 64-bit integers directly.
@Since("2.11")
class SystemHash {
static int combine(int hash, int value) {
@@ -298,6 +299,17 @@
}
}
+/// Sentinel values that should never be exposed outside of platform libraries.
+@Since("2.14")
+class SentinelValue {
+ final int id;
+ const SentinelValue(this.id);
+}
+
+/// A default value to use when only one sentinel is needed.
+@Since("2.14")
+const Object sentinelValue = const SentinelValue(0);
+
/// Given an [instance] of some generic type [T], and [extract], a first-class
/// generic function that takes the same number of type parameters as [T],
/// invokes the function with the same type arguments that were passed to T
index fc43a76..29c1595 100644
--- a/tests/lib_2/mirrors/class_declarations_test.dart
+++ b/tests/lib_2/mirrors/class_declarations_test.dart
@@ -12,9 +12,16 @@
import 'stringify.dart';
import 'declarations_model.dart' as declarations_model;
-Set<DeclarationMirror> inheritedDeclarations(ClassMirror cm) {
+/// Collects all declarations of [cm] and its super-classes except `Object`.
+///
+/// Includes static declarations of super-classes.
+///
+/// The `Object` class is omitted because this test should be stable against
+/// changes to the platform libraries, as long as the declaration model code
+/// doesn't change.
+Set<DeclarationMirror> transitiveDeclarations(ClassMirror cm) {
var decls = new Set<DeclarationMirror>();
- while (cm != null) {
+ while (cm != reflectClass(Object)) {
decls.addAll(cm.declarations.values);
cm = cm.superclass;
}
@@ -165,14 +172,12 @@
'Method(s(*) in s(Mixin))',
'Method(s(+) in s(Class))',
'Method(s(-) in s(Superclass))',
- 'Method(s(==) in s(Object))',
'TypeVariable(s(C) in s(Class),'
' upperBound = Class(s(Object) in s(dart.core), top-level))',
'Method(s(Class.generativeConstructor) in s(Class), constructor)',
'Method(s(Class.normalFactory) in s(Class), static, constructor)',
'Method(s(Class.redirectingConstructor) in s(Class), constructor)',
'Method(s(Class.redirectingFactory) in s(Class), static, constructor)',
- 'Method(s(Object) in s(Object), constructor)',
'TypeVariable(s(S) in s(Superclass),'
' upperBound = Class(s(Object) in s(dart.core), top-level))',
'Method(s(Superclass.inheritedGenerativeConstructor)'
@@ -184,7 +189,6 @@
'Method(s(Superclass.inheritedRedirectingFactory)'
' in s(Superclass), static, constructor)',
'Method(s(abstractMethod) in s(Class), abstract)',
- 'Method(s(hashCode) in s(Object), getter)',
'Method(s(inheritedInstanceGetter) in s(Superclass), getter)',
'Method(s(inheritedInstanceMethod) in s(Superclass))',
'Method(s(inheritedInstanceSetter=) in s(Superclass), setter)',
@@ -201,8 +205,6 @@
'Method(s(mixinInstanceMethod) in s(Mixin))',
'Method(s(mixinInstanceSetter=) in s(Mixin), setter)',
'Variable(s(mixinInstanceVariable) in s(Mixin))',
- 'Method(s(noSuchMethod) in s(Object))',
- 'Method(s(runtimeType) in s(Object), getter)',
'Method(s(staticGetter) in s(Class), static, getter)',
'Method(s(staticMethod) in s(Class), static)',
'Method(s(staticSetter=) in s(Class), static, setter)',
@@ -215,12 +217,11 @@
' with test.declarations_model.Mixin.inheritedRedirectingConstructor)'
' in s(test.declarations_model.Superclass'
' with test.declarations_model.Mixin), constructor)',
- 'Method(s(toString) in s(Object))',
'Variable(s(mixinStaticVariable) in s(Mixin), static)',
'Method(s(mixinStaticGetter) in s(Mixin), static, getter)',
'Method(s(mixinStaticSetter=) in s(Mixin), static, setter)',
'Method(s(mixinStaticMethod) in s(Mixin), static)'
- ], inheritedDeclarations(cm).where((dm) => !dm.isPrivate).map(stringify),
+ ], transitiveDeclarations(cm).where((dm) => !dm.isPrivate).map(stringify),
'transitive public');
// The public members of Object should be the same in all implementations, so
// we don't exclude Object here.
@@ -258,113 +259,106 @@To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Lasse R.H. Nielsen (Gerrit)
Attention is currently required from: Kevin Moore, Leaf Petersen, Sigmund Cherem, Nate Bosch.
1 comment:
Commit Message:
Change to […]
The "Fixed #11617" above does that too.
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Lasse R.H. Nielsen (Gerrit)
Attention is currently required from: Kevin Moore, Ian Hickson, Leaf Petersen, Sigmund Cherem, Nate Bosch.
Patch set 27:Commit-Queue +1
14 comments:
File sdk/lib/core/object.dart:
Patch Set #2, Line 149:
static int hash(Object object1, Object object2,I think you are correct, and I count it as a significant argument against that design. […]
Done
Patch Set #2, Line 162:
hash = JenkinsSmiHash.combine(hash, object3.hashCode);This is definitely a function that it would be interesting to make the front end "always inline" and […]
Done
File sdk/lib/core/object.dart:
Patch Set #11, Line 277:
ObjectTrue, we have `?` now :)
Done
Patch Set #11, Line 282:
hash = (hash ^ objectHash) & 0xFFFFFFFF;Using `+` would probably be better than `^`. […]
Done
File sdk/lib/core/object.dart:
Patch Set #12, Line 148:
static int hash(Object? object1, Object? object2,This point of the function is to *combine* multiple hashes. […]
Done
File sdk/lib/core/object.dart:
Patch Set #23, Line 148:
static int hash(Object? object1, Object? object2,My plan is to special-case this in the 'compiler'. […]
Done
Patch Set #23, Line 282:
* in an order independet way.independent
Done
Patch Set #23, Line 301:
* The hash value generated by this function is *not* guranteed to be stableguaranteed
Done
Patch Set #23, Line 311:
const int mask = 0x3FFFFFFF;It's used only once, so it could have been inlined. […]
Done
File sdk/lib/core/object.dart:
Patch Set #24, Line 282:
* in an order independet way.typo in "independent"
Done
File sdk/lib/internal/internal.dart:
Patch Set #23, Line 158:
static int hash2(int v1, int v2) {
I've looked into other hash combination algorithms, and if they are better, they are generally *byte […]
Done
Patch Set #23, Line 265:
/// However, for the unordered hash based on xor, we need to improve
ACK. It used to, now it uses `+` instead.
Done
File tests/corelib_2/object_hash_test.dart:
It's technically correct. […]
Done
Patch Set #16, Line 1:
// Copyright (c) 2018, the Dart project authors. Please see the AUTHORS fileWorking on that (just want to make the test complete first, and be sure it's correct, before I start […]
Done
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Dart CI (Gerrit)
Attention is currently required from: Kevin Moore, Ian Hickson, Leaf Petersen, Sigmund Cherem, Nate Bosch.
go/dart-cbuild result: FAILURE (NO REGRESSIONS DETECTED)
Details: https://goto.google.com/dart-cbuild/find/31a1343158bce34110b93692ccae0475e9302bf6
Dart CI (Gerrit)
Attention is currently required from: Kevin Moore, Ian Hickson, Leaf Petersen, Sigmund Cherem, Nate Bosch.
go/dart-cbuild result: FAILURE (NO REGRESSIONS DETECTED)
Details: https://goto.google.com/dart-cbuild/find/e8381698b39c427d4044be1cbbb3c0c35cf8ec25
Stephen Adams (Gerrit)
Attention is currently required from: Kevin Moore, Lasse R.H. Nielsen, Ian Hickson, Leaf Petersen, Sigmund Cherem, Nate Bosch.
Patch set 29:Code-Review +1
1 comment:
File sdk/lib/core/object.dart:
Patch Set #29, Line 180:
static int hash(Object? object1, Object? object2,There are several libraries that have needed to implement their own hash combining, e.g. https://api.flutter.dev/flutter/dart-ui/hashValues.html
`Object.hash` should accept up to 20 arguments to allow these implementations to switch to `Object.hash`.
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Dan Field (Gerrit)
Attention is currently required from: Kevin Moore, Lasse R.H. Nielsen, Stephen Adams, Ian Hickson, Leaf Petersen, Sigmund Cherem, Nate Bosch.
1 comment:
File sdk/lib/core/object.dart:
Patch Set #29, Line 180:
static int hash(Object? object1, Object? object2,
There are several libraries that have needed to implement their own hash combining, e.g. […]
+1 on this.
We're really hoping that this becomes a drop in replacement for hashValues/hashList.
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Nate Bosch (Gerrit)
Attention is currently required from: Kevin Moore, Lasse R.H. Nielsen, Stephen Adams, Ian Hickson, Leaf Petersen, Sigmund Cherem.
Patch set 29:Code-Review +1
1 comment:
File sdk/lib/core/object.dart:
Patch Set #23, Line 271:
hash = SystemHash.combine(hash, object.hashCode);ACK. Another option is to not start with `0`. […]
+1 for starting with non-zero.
Lasse R.H. Nielsen (Gerrit)
Attention is currently required from: Kevin Moore, Stephen Adams, Ian Hickson, Leaf Petersen, Sigmund Cherem, Nate Bosch.
1 comment:
File sdk/lib/core/object.dart:
Patch Set #23, Line 271:
hash = SystemHash.combine(hash, object.hashCode);
+1 for starting with non-zero.
How'd you feel about rolling a new seed per execution (a random 32-bit integer created in a platform dependent way)?
It would mean that hash codes differ *between isolates*, which would worry me. (Unless we somehow share the seed, but that's a bigger task.)
Or we can use today's date. 😊
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Dart CI (Gerrit)
Attention is currently required from: Kevin Moore, Stephen Adams, Ian Hickson, Leaf Petersen, Sigmund Cherem, Nate Bosch.
go/dart-cbuild result: SUCCESS
Details: https://goto.google.com/dart-cbuild/find/e8c3909f22baf112e1f9da5ba785a22bb561305d
Lasse R.H. Nielsen (Gerrit)
Attention is currently required from: Kevin Moore, Dan Field, Stephen Adams, Ian Hickson, Leaf Petersen, Sigmund Cherem, Nate Bosch.
1 comment:
File sdk/lib/core/object.dart:
Patch Set #29, Line 180:
static int hash(Object? object1, Object? object2,+1 on this. […]
Added parameters up to 20.
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Nate Bosch (Gerrit)
Attention is currently required from: Kevin Moore, Lasse R.H. Nielsen, Dan Field, Stephen Adams, Ian Hickson, Leaf Petersen, Sigmund Cherem.
Patch set 31:Code-Review +1
1 comment:
File sdk/lib/core/object.dart:
Patch Set #23, Line 271:
hash = SystemHash.combine(hash, object.hashCode);How'd you feel about rolling a new seed per execution (a random 32-bit integer created in a platform […]
I don't have strong feelings on changing hash codes per execution. I could certainly be convinced that it's a good idea - I don't particularly want to support consistent hash codes across isolates as a feature.
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Stephen Adams (Gerrit)
Attention is currently required from: Kevin Moore, Lasse R.H. Nielsen, Dan Field, Ian Hickson, Leaf Petersen, Sigmund Cherem.
File sdk/lib/_internal/js_runtime/lib/js_helper.dart:
Patch Set #31, Line 957:
if (reusesPositionalArguments) {This seems to be a bug fix for an issue independent of Object.hash
I have another CL to fix this: https://dart-review.googlesource.com/c/sdk/+/204747
Dart CI (Gerrit)
Attention is currently required from: Kevin Moore, Lasse R.H. Nielsen, Dan Field, Ian Hickson, Leaf Petersen, Sigmund Cherem.
go/dart-cbuild result: SUCCESS
Details: https://goto.google.com/dart-cbuild/find/9befa7fac4827ee3e90348f56d7d8b2f4f7625af
Lasse R.H. Nielsen (Gerrit)
Attention is currently required from: Kevin Moore, Dan Field, Stephen Adams, Ian Hickson, Leaf Petersen, Sigmund Cherem.
1 comment:
File sdk/lib/_internal/js_runtime/lib/js_helper.dart:
Patch Set #31, Line 957:
if (reusesPositionalArguments) {
This seems to be a bug fix for an issue independent of Object.hash […]
Excellent, I'll just revert that fix.
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Dart CI (Gerrit)
Attention is currently required from: Kevin Moore, Dan Field, Stephen Adams, Ian Hickson, Leaf Petersen, Sigmund Cherem.
go/dart-cbuild result: SUCCESS
Details: https://goto.google.com/dart-cbuild/find/e1f98b91fc2d841a888afd0e5487ef366c674a44
Lasse R.H. Nielsen (Gerrit)
Attention is currently required from: Kevin Moore, Dan Field, Stephen Adams, Ian Hickson, Leaf Petersen, Sigmund Cherem.
Patch set 33:Commit-Queue +2
Lasse R.H. Nielsen (Gerrit)
Attention is currently required from: Kevin Moore, Dan Field, Stephen Adams, Ian Hickson, Leaf Petersen, Sigmund Cherem, Nate Bosch.
1 comment:
File sdk/lib/core/object.dart:
Patch Set #23, Line 271:
hash = SystemHash.combine(hash, object.hashCode);
I don't have strong feelings on changing hash codes per execution. […]
Let's start out doing that then, and see if anyone complains about cross-isolate discrepancies.
Dart CI (Gerrit)
Attention is currently required from: Kevin Moore, Dan Field, Stephen Adams, Ian Hickson, Leaf Petersen, Sigmund Cherem, Nate Bosch.
go/dart-cbuild result: SUCCESS
Details: https://goto.google.com/dart-cbuild/find/18fbb5dff5cab80b315e9794c7ccc2ac6f46d994
commit-bot@chromium.org (Gerrit)
commi...@chromium.org submitted this change.
Add `Object.hash` and `Object.hashAll` static helper methods.
Fixes #11617.
Bug: http://dartbug.com/11617
Change-Id: Id06fb5b3914bee24713427edbd3b9b7e86f86449
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/73360
Commit-Queue: Lasse R.H. Nielsen <l...@google.com>
Reviewed-by: Nate Bosch <nbo...@google.com>
Reviewed-by: Stephen Adams <s...@google.com>
---
M CHANGELOG.md
M sdk/lib/core/object.dart
M sdk/lib/internal/internal.dart
A tests/corelib/object_hash_test.dart
A tests/corelib_2/object_hash_test.dart
M tests/lib/mirrors/class_declarations_test.dart
M tests/lib_2/mirrors/class_declarations_test.dart
7 files changed, 1,274 insertions(+), 261 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 5119c30..f32243e 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -27,6 +27,10 @@
daylight saving changes that are not precisely one hour.
(No change on the Web which uses the JavaScript `Date` object.)
+* Adds static methods `hash`, `hashAll` and `hashAllUnordered` to the
+ `Object` class. These can be used to combine the hash codes of
+ multiple objects in a consistent way.
+
#### `dart:ffi`
* Adds the `DynamicLibrary.providesSymbol` function to check whether a symbol
diff --git a/sdk/lib/core/object.dart b/sdk/lib/core/object.dart
index 32b52bf..8d02d06 100644
--- a/sdk/lib/core/object.dart
+++ b/sdk/lib/core/object.dart
@@ -146,4 +146,418 @@
/// A representation of the runtime type of the object.
external Type get runtimeType;
+
+ /// Creates a combined hash code for a number of objects.
+ ///
+ /// The hash code is computed for all arguments that are actually
+ /// supplied, even if they are `null`, by numerically combining the
+ /// [Object.hashCode] of each argument.
+ ///
+ /// Example:
+ /// ```dart
+ /// class SomeObject {
+ /// final Object a, b, c;
+ /// SomeObject(this.a, this.b, this.c);
+ /// bool operator=(Object other) =>
+ /// other is SomeObject && a == other.a && b == other.b && c == other.c;
+ /// int get hashCode => Object.hash(a, b, c);
+ /// }
+ /// ```
+ ///
+ /// The computed value will be consistent when the function is called
+ /// with the same arguments multiple times
+ /// during the execution of a single program.
+ ///
+ /// The hash value generated by this function is *not* guaranteed to be stable
+ /// over different runs of the same program,
+ /// or between code run in different isolates of the same program.
+ /// The exact algorithm used may differ between different platforms,
+ /// or between different versions of the platform libraries,
+ /// and it may depend on values that change on each program execution.
+ ///
+ /// The [hashAll] function gives the same result as this function when
+ /// called with a collection containing the actual arguments
+ /// to this function in the same order.
+ @Since("2.14")
+ static int hash(Object? object1, Object? object2,
+ [Object? object3 = sentinelValue,
+ Object? object4 = sentinelValue,
+ Object? object5 = sentinelValue,
+ Object? object6 = sentinelValue,
+ Object? object7 = sentinelValue,
+ Object? object8 = sentinelValue,
+ Object? object9 = sentinelValue,
+ Object? object10 = sentinelValue,
+ Object? object11 = sentinelValue,
+ Object? object12 = sentinelValue,
+ Object? object13 = sentinelValue,
+ Object? object14 = sentinelValue,
+ Object? object15 = sentinelValue,
+ Object? object16 = sentinelValue,
+ Object? object17 = sentinelValue,
+ Object? object18 = sentinelValue,
+ Object? object19 = sentinelValue,
+ Object? object20 = sentinelValue]) {
+ if (sentinelValue == object3) {
+ return SystemHash.hash2(object1.hashCode, object2.hashCode, _hashSeed);
+ }
+ if (sentinelValue == object4) {
+ return SystemHash.hash3(
+ object1.hashCode, object2.hashCode, object3.hashCode, _hashSeed);
+ }
+ if (sentinelValue == object5) {
+ return SystemHash.hash4(object1.hashCode, object2.hashCode,
+ object3.hashCode, object4.hashCode, _hashSeed);
+ }
+ if (sentinelValue == object6) {
+ return SystemHash.hash5(object1.hashCode, object2.hashCode,
+ object3.hashCode, object4.hashCode, object5.hashCode, _hashSeed);
+ }
+ if (sentinelValue == object7) {
+ return SystemHash.hash6(
+ object1.hashCode,
+ object2.hashCode,
+ object3.hashCode,
+ object4.hashCode,
+ object5.hashCode,
+ object6.hashCode,
+ _hashSeed);
+ }
+ if (sentinelValue == object8) {
+ return SystemHash.hash7(
+ object1.hashCode,
+ object2.hashCode,
+ object3.hashCode,
+ object4.hashCode,
+ object5.hashCode,
+ object6.hashCode,
+ object7.hashCode,
+ _hashSeed);
+ }
+ if (sentinelValue == object9) {
+ return SystemHash.hash8(
+ object1.hashCode,
+ object2.hashCode,
+ object3.hashCode,
+ object4.hashCode,
+ object5.hashCode,
+ object6.hashCode,
+ object7.hashCode,
+ object8.hashCode,
+ _hashSeed);
+ }
+ if (sentinelValue == object10) {
+ return SystemHash.hash9(
+ object1.hashCode,
+ object2.hashCode,
+ object3.hashCode,
+ object4.hashCode,
+ object5.hashCode,
+ object6.hashCode,
+ object7.hashCode,
+ object8.hashCode,
+ object9.hashCode,
+ _hashSeed);
+ }
+ if (sentinelValue == object11) {
+ return SystemHash.hash10(
+ object1.hashCode,
+ object2.hashCode,
+ object3.hashCode,
+ object4.hashCode,
+ object5.hashCode,
+ object6.hashCode,
+ object7.hashCode,
+ object8.hashCode,
+ object9.hashCode,
+ object10.hashCode,
+ _hashSeed);
+ }
+ if (sentinelValue == object12) {
+ return SystemHash.hash11(
+ object1.hashCode,
+ object2.hashCode,
+ object3.hashCode,
+ object4.hashCode,
+ object5.hashCode,
+ object6.hashCode,
+ object7.hashCode,
+ object8.hashCode,
+ object9.hashCode,
+ object10.hashCode,
+ object11.hashCode,
+ _hashSeed);
+ }
+ if (sentinelValue == object13) {
+ return SystemHash.hash12(
+ object1.hashCode,
+ object2.hashCode,
+ object3.hashCode,
+ object4.hashCode,
+ object5.hashCode,
+ object6.hashCode,
+ object7.hashCode,
+ object8.hashCode,
+ object9.hashCode,
+ object10.hashCode,
+ object11.hashCode,
+ object12.hashCode,
+ _hashSeed);
+ }
+ if (sentinelValue == object14) {
+ return SystemHash.hash13(
+ object1.hashCode,
+ object2.hashCode,
+ object3.hashCode,
+ object4.hashCode,
+ object5.hashCode,
+ object6.hashCode,
+ object7.hashCode,
+ object8.hashCode,
+ object9.hashCode,
+ object10.hashCode,
+ object11.hashCode,
+ object12.hashCode,
+ object13.hashCode,
+ _hashSeed);
+ }
+ if (sentinelValue == object15) {
+ return SystemHash.hash14(
+ object1.hashCode,
+ object2.hashCode,
+ object3.hashCode,
+ object4.hashCode,
+ object5.hashCode,
+ object6.hashCode,
+ object7.hashCode,
+ object8.hashCode,
+ object9.hashCode,
+ object10.hashCode,
+ object11.hashCode,
+ object12.hashCode,
+ object13.hashCode,
+ object14.hashCode,
+ _hashSeed);
+ }
+ if (sentinelValue == object16) {
+ return SystemHash.hash15(
+ object1.hashCode,
+ object2.hashCode,
+ object3.hashCode,
+ object4.hashCode,
+ object5.hashCode,
+ object6.hashCode,
+ object7.hashCode,
+ object8.hashCode,
+ object9.hashCode,
+ object10.hashCode,
+ object11.hashCode,
+ object12.hashCode,
+ object13.hashCode,
+ object14.hashCode,
+ object15.hashCode,
+ _hashSeed);
+ }
+ if (sentinelValue == object17) {
+ return SystemHash.hash16(
+ object1.hashCode,
+ object2.hashCode,
+ object3.hashCode,
+ object4.hashCode,
+ object5.hashCode,
+ object6.hashCode,
+ object7.hashCode,
+ object8.hashCode,
+ object9.hashCode,
+ object10.hashCode,
+ object11.hashCode,
+ object12.hashCode,
+ object13.hashCode,
+ object14.hashCode,
+ object15.hashCode,
+ object16.hashCode,
+ _hashSeed);
+ }
+ if (sentinelValue == object18) {
+ return SystemHash.hash17(
+ object1.hashCode,
+ object2.hashCode,
+ object3.hashCode,
+ object4.hashCode,
+ object5.hashCode,
+ object6.hashCode,
+ object7.hashCode,
+ object8.hashCode,
+ object9.hashCode,
+ object10.hashCode,
+ object11.hashCode,
+ object12.hashCode,
+ object13.hashCode,
+ object14.hashCode,
+ object15.hashCode,
+ object16.hashCode,
+ object17.hashCode,
+ _hashSeed);
+ }
+ if (sentinelValue == object19) {
+ return SystemHash.hash18(
+ object1.hashCode,
+ object2.hashCode,
+ object3.hashCode,
+ object4.hashCode,
+ object5.hashCode,
+ object6.hashCode,
+ object7.hashCode,
+ object8.hashCode,
+ object9.hashCode,
+ object10.hashCode,
+ object11.hashCode,
+ object12.hashCode,
+ object13.hashCode,
+ object14.hashCode,
+ object15.hashCode,
+ object16.hashCode,
+ object17.hashCode,
+ object18.hashCode,
+ _hashSeed);
+ }
+ if (sentinelValue == object20) {
+ return SystemHash.hash19(
+ object1.hashCode,
+ object2.hashCode,
+ object3.hashCode,
+ object4.hashCode,
+ object5.hashCode,
+ object6.hashCode,
+ object7.hashCode,
+ object8.hashCode,
+ object9.hashCode,
+ object10.hashCode,
+ object11.hashCode,
+ object12.hashCode,
+ object13.hashCode,
+ object14.hashCode,
+ object15.hashCode,
+ object16.hashCode,
+ object17.hashCode,
+ object18.hashCode,
+ object19.hashCode,
+ _hashSeed);
+ }
+ return SystemHash.hash20(
+ object1.hashCode,
+ object2.hashCode,
+ object3.hashCode,
+ object4.hashCode,
+ object5.hashCode,
+ object6.hashCode,
+ object7.hashCode,
+ object8.hashCode,
+ object9.hashCode,
+ object10.hashCode,
+ object11.hashCode,
+ object12.hashCode,
+ object13.hashCode,
+ object14.hashCode,
+ object15.hashCode,
+ object16.hashCode,
+ object17.hashCode,
+ object18.hashCode,
+ object19.hashCode,
+ object20.hashCode,
+ _hashSeed);
+ }
+
+ /// Creates a combined hash code for a sequence of objects.
+ ///
+ /// The hash code is computed for elements in [objects],
+ /// even if they are `null`,
+ /// by numerically combining the [Object.hashCode] of each element
+ /// in iteration order.
+ ///
+ /// The result of `hashAll([o])` is not `o.hashCode`.
+ ///
+ /// Example:
+ /// ```dart
+ /// class SomeObject {
+ /// final List<String> path;
+ /// SomeObject(this.path);
+ /// bool operator=(Object other) {
+ /// if (other is SomeObject) {
+ /// if (path.length != other.path.length) return false;
+ /// for (int i = 0; i < path.length; i++) {
+ /// if (path[i] != other.path[i]) return false;
+ /// }
+ /// return true;
+ /// }
+ /// return false;
+ /// }
+ ///
+ /// int get hashCode => Object.hashAll(path);
+ /// }
+ /// ```
+ ///
+ /// The computed value will be be consistent when the function is called
+ /// again with objects that have the same hash codes in the same order
+ /// during an execution of a single program.
+ ///
+ /// The hash value generated by this function is *not* guranteed to be stable
+ /// over different runs of the same program,
+ /// or between code run in different isolates of the same program.
+ /// The exact algorithm used may differ between different platforms,
+ /// or between different versions of the platform libraries,
+ /// and it may depend on values that change on each program execution.
+ @Since("2.14")
+ static int hashAll(Iterable<Object?> objects) {
+ int hash = _hashSeed;
+ for (var object in objects) {
+ hash = SystemHash.combine(hash, object.hashCode);
+ }
+ return SystemHash.finish(hash);
+ }
+
+ /// Creates a combined hash code for a collection of objects.
+ ///
+ /// The hash code is computed for elements in [objects],
+ /// even if they are `null`,
+ /// by numerically combining the [Object.hashCode] of each element
+ /// in an order independent way.
+ ///
+ /// The result of `unorderedHashAll({o})` is not `o.hashCode`.
+ ///
+ /// Example:
+ /// ```dart
+ /// bool setEquals<T>(Set<T> set1, Set<T> set2) {
+ /// var hashCode1 = Object.unorderedHashAll(set1);
+ /// var hashCode2 = Object.unorderedHashAll(set2);
+ /// if (hashCode1 != hashCode2) return false;
+ /// // Compare elements ...
+ /// }
+ /// ```
+ ///
+ /// The computed value will be be consistent when the function is called
+ /// again with objects that have the same hash codes
+ /// during an execution of a single program,
+ /// even if the objects are not necessarily in the same order,
+ ///
+ /// The hash value generated by this function is *not* guranteed to be stable
+ /// over different runs of the same program.
+ /// The exact algorithm used may differ between different platforms,
+ /// or between different versions of the platform libraries,
+ /// and it may depend on values that change per program run
+ @Since("2.14")
+ static int hashAllUnordered(Iterable<Object?> objects) {
+ int sum = 0;
+ int count = 0;
+ const int mask = 0x3FFFFFFF;
+ for (var object in objects) {
+ int objectHash = SystemHash.smear(object.hashCode);
+ sum = (sum + objectHash) & mask;
+ count += 1;
+ }
+ return SystemHash.hash2(sum, count);
+ }
}
+
+// A per-isolate seed for hash code computations.
+final int _hashSeed = identityHashCode(Object);
diff --git a/sdk/lib/internal/internal.dart b/sdk/lib/internal/internal.dart
index 858f1f5..0e4c898 100644
--- a/sdk/lib/internal/internal.dart
+++ b/sdk/lib/internal/internal.dart
@@ -148,7 +148,7 @@
///
/// [1]: http://en.wikipedia.org/wiki/Jenkins_hash_function
///
-/// Usage:
+/// Use:
/// Hash each value with the hash of the previous value, then get the final
/// hash by calling finish.
/// ```
@@ -158,8 +158,9 @@
/// }
/// hash = SystemHash.finish(hash);
/// ```
-// TODO(lrn): Consider specializing this code per platform,
-// so the VM can use its 64-bit integers directly.
+///
+/// TODO(lrn): Consider specializing this code per platform,
+/// so the VM can use its 64-bit integers directly.
@Since("2.11")
class SystemHash {
static int combine(int hash, int value) {
@@ -174,23 +175,24 @@
return 0x1fffffff & (hash + ((0x00003fff & hash) << 15));
}
- static int hash2(int v1, int v2) {
- int hash = 0;
+ static int hash2(int v1, int v2, [@Since("2.14") int seed = 0]) {
+ int hash = seed;
hash = combine(hash, v1);
hash = combine(hash, v2);
return finish(hash);
}
- static int hash3(int v1, int v2, int v3) {
- int hash = 0;
+ static int hash3(int v1, int v2, int v3, [@Since("2.14") int seed = 0]) {
+ int hash = seed;
hash = combine(hash, v1);
hash = combine(hash, v2);
hash = combine(hash, v3);
return finish(hash);
}
- static int hash4(int v1, int v2, int v3, int v4) {
- int hash = 0;
+ static int hash4(int v1, int v2, int v3, int v4,
+ [@Since("2.14") int seed = 0]) {
+ int hash = seed;
hash = combine(hash, v1);
hash = combine(hash, v2);
hash = combine(hash, v3);
@@ -198,8 +200,9 @@
return finish(hash);
}
- static int hash5(int v1, int v2, int v3, int v4, int v5) {
- int hash = 0;
+ static int hash5(int v1, int v2, int v3, int v4, int v5,
+ [@Since("2.14") int seed = 0]) {
+ int hash = seed;
hash = combine(hash, v1);
hash = combine(hash, v2);
hash = combine(hash, v3);
@@ -208,8 +211,9 @@
return finish(hash);
}
- static int hash6(int v1, int v2, int v3, int v4, int v5, int v6) {
- int hash = 0;
+ static int hash6(int v1, int v2, int v3, int v4, int v5, int v6,
+ [@Since("2.14") int seed = 0]) {
+ int hash = seed;
hash = combine(hash, v1);
hash = combine(hash, v2);
hash = combine(hash, v3);
@@ -219,8 +223,9 @@
return finish(hash);
}
- static int hash7(int v1, int v2, int v3, int v4, int v5, int v6, int v7) {
- int hash = 0;
+ static int hash7(int v1, int v2, int v3, int v4, int v5, int v6, int v7,
+ [@Since("2.14") int seed = 0]) {
+ int hash = seed;
hash = combine(hash, v1);
hash = combine(hash, v2);
hash = combine(hash, v3);
@@ -232,8 +237,9 @@
}
static int hash8(
- int v1, int v2, int v3, int v4, int v5, int v6, int v7, int v8) {
- int hash = 0;
+ int v1, int v2, int v3, int v4, int v5, int v6, int v7, int v8,
+ [@Since("2.14") int seed = 0]) {
+ int hash = seed;
hash = combine(hash, v1);
hash = combine(hash, v2);
hash = combine(hash, v3);
@@ -246,8 +252,9 @@
}
static int hash9(
- int v1, int v2, int v3, int v4, int v5, int v6, int v7, int v8, int v9) {
- int hash = 0;
+ int v1, int v2, int v3, int v4, int v5, int v6, int v7, int v8, int v9,
+ [@Since("2.14") int seed = 0]) {
+ int hash = seed;
hash = combine(hash, v1);
hash = combine(hash, v2);
hash = combine(hash, v3);
@@ -261,8 +268,9 @@
}
static int hash10(int v1, int v2, int v3, int v4, int v5, int v6, int v7,
- int v8, int v9, int v10) {
- int hash = 0;
+ int v8, int v9, int v10,
+ [@Since("2.14") int seed = 0]) {
+ int hash = seed;
hash = combine(hash, v1);
hash = combine(hash, v2);
hash = combine(hash, v3);
@@ -276,14 +284,334 @@
return finish(hash);
}
+ @Since("2.14")
+ static int hash11(int v1, int v2, int v3, int v4, int v5, int v6, int v7,
+ int v8, int v9, int v10, int v11,
+ [int seed = 0]) {
+ int hash = seed;
+ hash = combine(hash, v1);
+ hash = combine(hash, v2);
+ hash = combine(hash, v3);
+ hash = combine(hash, v4);
+ hash = combine(hash, v5);
+ hash = combine(hash, v6);
+ hash = combine(hash, v7);
+ hash = combine(hash, v8);
+ hash = combine(hash, v9);
+ hash = combine(hash, v10);
+ hash = combine(hash, v11);
+ return finish(hash);
+ }
+
+ @Since("2.14")
+ static int hash12(int v1, int v2, int v3, int v4, int v5, int v6, int v7,
+ int v8, int v9, int v10, int v11, int v12,
+ [int seed = 0]) {
+ int hash = seed;
+ hash = combine(hash, v1);
+ hash = combine(hash, v2);
+ hash = combine(hash, v3);
+ hash = combine(hash, v4);
+ hash = combine(hash, v5);
+ hash = combine(hash, v6);
+ hash = combine(hash, v7);
+ hash = combine(hash, v8);
+ hash = combine(hash, v9);
+ hash = combine(hash, v10);
+ hash = combine(hash, v11);
+ hash = combine(hash, v12);
+ return finish(hash);
+ }
+
+ @Since("2.14")
+ static int hash13(int v1, int v2, int v3, int v4, int v5, int v6, int v7,
+ int v8, int v9, int v10, int v11, int v12, int v13,
+ [int seed = 0]) {
+ int hash = seed;
+ hash = combine(hash, v1);
+ hash = combine(hash, v2);
+ hash = combine(hash, v3);
+ hash = combine(hash, v4);
+ hash = combine(hash, v5);
+ hash = combine(hash, v6);
+ hash = combine(hash, v7);
+ hash = combine(hash, v8);
+ hash = combine(hash, v9);
+ hash = combine(hash, v10);
+ hash = combine(hash, v11);
+ hash = combine(hash, v12);
+ hash = combine(hash, v13);
+ return finish(hash);
+ }
+
+ @Since("2.14")
+ static int hash14(int v1, int v2, int v3, int v4, int v5, int v6, int v7,
+ int v8, int v9, int v10, int v11, int v12, int v13, int v14,
+ [int seed = 0]) {
+ int hash = seed;
+ hash = combine(hash, v1);
+ hash = combine(hash, v2);
+ hash = combine(hash, v3);
+ hash = combine(hash, v4);
+ hash = combine(hash, v5);
+ hash = combine(hash, v6);
+ hash = combine(hash, v7);
+ hash = combine(hash, v8);
+ hash = combine(hash, v9);
+ hash = combine(hash, v10);
+ hash = combine(hash, v11);
+ hash = combine(hash, v12);
+ hash = combine(hash, v13);
+ hash = combine(hash, v14);
+ return finish(hash);
+ }
+
+ @Since("2.14")
+ static int hash15(int v1, int v2, int v3, int v4, int v5, int v6, int v7,
+ int v8, int v9, int v10, int v11, int v12, int v13, int v14, int v15,
+ [int seed = 0]) {
+ int hash = seed;
+ hash = combine(hash, v1);
+ hash = combine(hash, v2);
+ hash = combine(hash, v3);
+ hash = combine(hash, v4);
+ hash = combine(hash, v5);
+ hash = combine(hash, v6);
+ hash = combine(hash, v7);
+ hash = combine(hash, v8);
+ hash = combine(hash, v9);
+ hash = combine(hash, v10);
+ hash = combine(hash, v11);
+ hash = combine(hash, v12);
+ hash = combine(hash, v13);
+ hash = combine(hash, v14);
+ hash = combine(hash, v15);
+ return finish(hash);
+ }
+
+ @Since("2.14")
+ static int hash16(
+ int v1,
+ int v2,
+ int v3,
+ int v4,
+ int v5,
+ int v6,
+ int v7,
+ int v8,
+ int v9,
+ int v10,
+ int v11,
+ int v12,
+ int v13,
+ int v14,
+ int v15,
+ int v16,
+ [int seed = 0]) {
+ int hash = seed;
+ hash = combine(hash, v1);
+ hash = combine(hash, v2);
+ hash = combine(hash, v3);
+ hash = combine(hash, v4);
+ hash = combine(hash, v5);
+ hash = combine(hash, v6);
+ hash = combine(hash, v7);
+ hash = combine(hash, v8);
+ hash = combine(hash, v9);
+ hash = combine(hash, v10);
+ hash = combine(hash, v11);
+ hash = combine(hash, v12);
+ hash = combine(hash, v13);
+ hash = combine(hash, v14);
+ hash = combine(hash, v15);
+ hash = combine(hash, v16);
+ return finish(hash);
+ }
+
+ @Since("2.14")
+ static int hash17(
+ int v1,
+ int v2,
+ int v3,
+ int v4,
+ int v5,
+ int v6,
+ int v7,
+ int v8,
+ int v9,
+ int v10,
+ int v11,
+ int v12,
+ int v13,
+ int v14,
+ int v15,
+ int v16,
+ int v17,
+ [int seed = 0]) {
+ int hash = seed;
+ hash = combine(hash, v1);
+ hash = combine(hash, v2);
+ hash = combine(hash, v3);
+ hash = combine(hash, v4);
+ hash = combine(hash, v5);
+ hash = combine(hash, v6);
+ hash = combine(hash, v7);
+ hash = combine(hash, v8);
+ hash = combine(hash, v9);
+ hash = combine(hash, v10);
+ hash = combine(hash, v11);
+ hash = combine(hash, v12);
+ hash = combine(hash, v13);
+ hash = combine(hash, v14);
+ hash = combine(hash, v15);
+ hash = combine(hash, v16);
+ hash = combine(hash, v17);
+ return finish(hash);
+ }
+
+ @Since("2.14")
+ static int hash18(
+ int v1,
+ int v2,
+ int v3,
+ int v4,
+ int v5,
+ int v6,
+ int v7,
+ int v8,
+ int v9,
+ int v10,
+ int v11,
+ int v12,
+ int v13,
+ int v14,
+ int v15,
+ int v16,
+ int v17,
+ int v18,
+ [int seed = 0]) {
+ int hash = seed;
+ hash = combine(hash, v1);
+ hash = combine(hash, v2);
+ hash = combine(hash, v3);
+ hash = combine(hash, v4);
+ hash = combine(hash, v5);
+ hash = combine(hash, v6);
+ hash = combine(hash, v7);
+ hash = combine(hash, v8);
+ hash = combine(hash, v9);
+ hash = combine(hash, v10);
+ hash = combine(hash, v11);
+ hash = combine(hash, v12);
+ hash = combine(hash, v13);
+ hash = combine(hash, v14);
+ hash = combine(hash, v15);
+ hash = combine(hash, v16);
+ hash = combine(hash, v17);
+ hash = combine(hash, v18);
+ return finish(hash);
+ }
+
+ @Since("2.14")
+ static int hash19(
+ int v1,
+ int v2,
+ int v3,
+ int v4,
+ int v5,
+ int v6,
+ int v7,
+ int v8,
+ int v9,
+ int v10,
+ int v11,
+ int v12,
+ int v13,
+ int v14,
+ int v15,
+ int v16,
+ int v17,
+ int v18,
+ int v19,
+ [int seed = 0]) {
+ int hash = seed;
+ hash = combine(hash, v1);
+ hash = combine(hash, v2);
+ hash = combine(hash, v3);
+ hash = combine(hash, v4);
+ hash = combine(hash, v5);
+ hash = combine(hash, v6);
+ hash = combine(hash, v7);
+ hash = combine(hash, v8);
+ hash = combine(hash, v9);
+ hash = combine(hash, v10);
+ hash = combine(hash, v11);
+ hash = combine(hash, v12);
+ hash = combine(hash, v13);
+ hash = combine(hash, v14);
+ hash = combine(hash, v15);
+ hash = combine(hash, v16);
+ hash = combine(hash, v17);
+ hash = combine(hash, v18);
+ hash = combine(hash, v19);
+ return finish(hash);
+ }
+
+ @Since("2.14")
+ static int hash20(
+ int v1,
+ int v2,
+ int v3,
+ int v4,
+ int v5,
+ int v6,
+ int v7,
+ int v8,
+ int v9,
+ int v10,
+ int v11,
+ int v12,
+ int v13,
+ int v14,
+ int v15,
+ int v16,
+ int v17,
+ int v18,
+ int v19,
+ int v20,
+ [int seed = 0]) {
+ int hash = seed;
+ hash = combine(hash, v1);
+ hash = combine(hash, v2);
+ hash = combine(hash, v3);
+ hash = combine(hash, v4);
+ hash = combine(hash, v5);
+ hash = combine(hash, v6);
+ hash = combine(hash, v7);
+ hash = combine(hash, v8);
+ hash = combine(hash, v9);
+ hash = combine(hash, v10);
+ hash = combine(hash, v11);
+ hash = combine(hash, v12);
+ hash = combine(hash, v13);
+ hash = combine(hash, v14);
+ hash = combine(hash, v15);
+ hash = combine(hash, v16);
+ hash = combine(hash, v17);
+ hash = combine(hash, v18);
+ hash = combine(hash, v19);
+ hash = combine(hash, v20);
+ return finish(hash);
+ }
+
/// Bit shuffling operation to improve hash codes.
///
/// Dart integers have very simple hash codes (their value),
/// which is acceptable for the hash above because it smears the bits
/// as part of the combination.
- /// However, for the unordered hash based on xor, we need to improve
- /// the hash code of, e.g., integers, so a set containing the integers
- /// from zero to 2^n won't always have a zero hashcode.
+ /// However, for the unordered hash, we need to improve
+ /// the hash code of, e.g., integers, to avoid collections of small integers
+ /// too easily having colliding hash results.
///
/// Assumes the input hash code is an unsigned 32-bit integer.
/// Found by Christopher Wellons [https://github.com/skeeto/hash-prospector].
@@ -298,6 +626,17 @@
}
}
+/// Sentinel values that should never be exposed outside of platform libraries.
+@Since("2.14")
+class SentinelValue {
+ final int id;
+ const SentinelValue(this.id);
+}
+
+/// A default value to use when only one sentinel is needed.
+@Since("2.14")
+const Object sentinelValue = const SentinelValue(0);
+
/// Given an [instance] of some generic type [T], and [extract], a first-class
/// generic function that takes the same number of type parameters as [T],
/// invokes the function with the same type arguments that were passed to T
diff --git a/tests/corelib/object_hash_test.dart b/tests/corelib/object_hash_test.dart
new file mode 100644
index 0000000..3e9e5d8
--- /dev/null
+++ b/tests/corelib/object_hash_test.dart
@@ -0,0 +1,134 @@
+// Copyright (c) 2018, the Dart project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+import "dart:math";
+import "dart:typed_data";
+
+import "package:expect/expect.dart";
+
+main() {
+ const nan = double.nan;
+ const inf = double.infinity;
+
+ int hash1234 = Object.hash(1, 2, 3, 4);
+ Expect.type<int>(hash1234);
+ Expect.equals(hash1234, Object.hash(1, 2, 3, 4)); // Consistent.
+ Expect.equals(hash1234, Object.hashAll([1, 2, 3, 4]));
+ Expect.equals(hash1234, Object.hashAll(Uint8List.fromList([1, 2, 3, 4])));
+
+ Expect.notEquals(hash1234, Object.hash(1, 2, 3, 4, null));
+
+ Expect.equals(Object.hash(1, 2, 3, 4, 5, 6, 7, 8, 9),
+ Object.hashAll([1, 2, 3, 4, 5, 6, 7, 8, 9]));
+
+ // Check that we can call `hash` with 2-20 arguments,
+ // and they all agree with `hashAll`.
+ var random = Random();
+ for (var i = 2; i <= 20; i++) {
+ var arguments = [for (var j = 0; j < i; j++) random.nextInt(256)];
+ var hashAll = Object.hashAll(arguments);
+ var hash = Function.apply(Object.hash, arguments);
+ Expect.equals(
+ hashAll,
+ hash,
+ "hashAll and hash disagrees for $i values:\n"
+ "$arguments");
+ }
index 0000000..3e9e5d8
--- /dev/null
+++ b/tests/corelib_2/object_hash_test.dart
@@ -0,0 +1,134 @@
+// Copyright (c) 2018, the Dart project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+import "dart:math";
+import "dart:typed_data";
+
+import "package:expect/expect.dart";
+
+main() {
+ const nan = double.nan;
+ const inf = double.infinity;
+
+ int hash1234 = Object.hash(1, 2, 3, 4);
+ Expect.type<int>(hash1234);
+ Expect.equals(hash1234, Object.hash(1, 2, 3, 4)); // Consistent.
+ Expect.equals(hash1234, Object.hashAll([1, 2, 3, 4]));
+ Expect.equals(hash1234, Object.hashAll(Uint8List.fromList([1, 2, 3, 4])));
+
+ Expect.notEquals(hash1234, Object.hash(1, 2, 3, 4, null));
+
+ Expect.equals(Object.hash(1, 2, 3, 4, 5, 6, 7, 8, 9),
+ Object.hashAll([1, 2, 3, 4, 5, 6, 7, 8, 9]));
+
+ // Check that we can call `hash` with 2-20 arguments,
+ // and they all agree with `hashAll`.
+ var random = Random();
+ for (var i = 2; i <= 20; i++) {
+ var arguments = [for (var j = 0; j < i; j++) random.nextInt(256)];
+ var hashAll = Object.hashAll(arguments);
+ var hash = Function.apply(Object.hash, arguments);
+ Expect.equals(
+ hashAll,
+ hash,
+ "hashAll and hash disagrees for $i values:\n"
+ "$arguments");
+ }
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Dart CI (Gerrit)
go/dart-cbuild result: SUCCESS
Details: https://goto.google.com/dart-cbuild/find/83376bf1ee81607a182f8558b242f1c9f4883246
Stephen Adams (Gerrit)
Attention is currently required from: Lasse Nielsen.
1 comment:
File sdk/lib/core/object.dart:
Patch Set #34, Line 563:
final int _hashSeed = identityHashCode(Object);Was the intention here to use the `.hashCode` of the `Type` object for the type `Object`?
I would have expected `Object()` to just use the identity hash code of an instance of `Object`.
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.
Lasse Nielsen (Gerrit)
1 comment:
File sdk/lib/core/object.dart:
Patch Set #34, Line 563:
final int _hashSeed = identityHashCode(Object);
Was the intention here to use the `.hashCode` of the `Type` object for the type `Object`? […]
The intent was to get a new seed for every run. Anything else is secondary.
A `Type` object is also an object.Looking at it again, any object which doesn't specialized the identity-hash should work (so numbers are out).
Using a constant will likely make it have the same value for isolates in the same isolate group.
Using a `new Object()` would be more likely to give a different hash seed per isolate.
I can't decide whether we want that or not. It probably doesn't matter, but since the goal is to not promise stability, using `new Object()` would be a better fit for that goal.I'm fine with changing this to practically anything that changes between runs of the same program. Using `Object()` instead of a constant is probably the choice with the most variance.
Could also just do `Random().nextInt(0x3FFFFFFF)`, if we can assume actual randomness from that.
To view, visit change 73360. To unsubscribe, or for help writing mail filters, visit settings.