collection 1.19.1: Compare two Dart Lists, Maps or Sets by their contents, and use one as a cache key, when == on a collection is identity

{"case":{"caseId":"case:sha256:90d68b57163c842f048698a450137efade218e3143020d06753139ece8b2cf1f","constraints":{"runtime":"dart"},"contract":["assert two Lists with the same contents are not ==, and neither are two Maps nor two Sets, while package:test's equals matcher deep-compares the same values, nested ones included, and passes","assert a const collection is canonicalized, so const [1, 2] is identical to const [1, 2], that canonicalization is per type argument, and that copying the list loses the equality again","assert ListEquality compares in order while MapEquality and SetEquality do not, their hashes agree where their equals does, and IterableEquality compares a List against a Set","assert ListEquality and MapEquality go exactly one level deep, so nested collections are compared with == and only match when the inner values are const-canonicalized","assert DeepCollectionEquality recurses through nested maps, lists and sets, is already order-insensitive for Sets but not for Lists, that unordered() extends that to Lists as a multiset, and that non-collections fall through to the base equality","assert a Map used as a key in a plain Map only matches the instance it was stored under, so the cache grows and never hits, while a HashMap given DeepCollectionEquality's equals and hash matches a rebuilt key whatever order its literal was written in","assert equal structures produce equal DeepCollectionEquality hashes, that the ordered and unordered hashes track their own equalities, and that a HashMap given equals without hashCode misses 2000 freshly built keys without calling the equals it was given even once","assert groupBy returns exact groups keyed in first-occurrence order, firstWhereOrNull returns null where the SDK's firstWhere throws StateError, and whereNotNull yields the same List\u003cint\u003e as the SDK's nonNulls that deprecates it","assert Dart records compare by value and work as Map keys, but a record holding a List is back to identity"],"goal":"Compare two Dart Lists, Maps or Sets by their contents, and use one as a cache key, when == on a collection is identity","kind":"HOW","packages":["pkg:pub/collection@1.19.1"],"schemaVersion":1,"symbols":["ListEquality","MapEquality","SetEquality","IterableEquality","DeepCollectionEquality","DeepCollectionEquality.unordered","DeepCollectionEquality.hash","groupBy","firstWhereOrNull","whereNotNull","HashMap"]},"contractCommand":["dart","test","--reporter=expanded"],"environment":{"arch":"x64","ecosystem":"pub","executionContext":"dart","language":"dart","os":"linux","packageManager":"pub","runtime":"dart","runtimeVersion":"3","schemaVersion":1},"license":"MIT-0","packages":["pkg:pub/collection@1.19.1"],"schemaVersion":1,"symbols":["ListEquality","MapEquality","SetEquality","IterableEquality","DeepCollectionEquality","DeepCollectionEquality.unordered","DeepCollectionEquality.hash","groupBy","firstWhereOrNull","whereNotNull","HashMap"],"verifierAdapter":"pub@1"}

import 'dart:collection';

import 'package:collection/collection.dart';

/// Two Dart collections with the same contents are not equal. `[1, 2] == [1, 2]`
/// is false, `{'a': 1} == {'a': 1}` is false, `{1, 2} == {1, 2}` is false. List,
/// Map and Set inherit `==` and `hashCode` from Object, and Object compares by
/// identity, so the only question those operators answer is "is this the same
/// object". Nothing in the language gives an SDK collection value semantics, and
/// nothing warns you: the code type-checks, reads correctly, and quietly means
/// something else.
///
/// The reason people believe it works sometimes is `const`. A const collection
/// is canonicalized at compile time, so every `const [1, 2]` in the program is
/// one shared instance and `identical` is true — which makes `==` true as well.
/// Same literal text, opposite answer, decided by a keyword that is usually
/// somewhere else in the file. Canonicalization is per type argument too, so
/// `const <int>[1, 2]` and `const <num>[1, 2]` are two different canonical
/// objects and compare false.
///
/// package:collection is the answer: Equality objects that compare contents
/// instead of identity. They come in one-level and deep flavours, and picking
/// the wrong one is the second trap. ListEquality, MapEquality and SetEquality
/// compare the collection itself by content but compare its *elements* with
/// their own `==`, so a List of Lists is back to identity one level down.
/// DeepCollectionEquality recurses, dispatching per collection type on the way:
/// SetEquality for sets, MapEquality for maps, ListEquality for lists. That
/// means Sets and Map keys are already order-insensitive under the plain
/// DeepCollectionEquality; `.unordered()` is what extends that to Lists.
///
/// The consequence that costs real money is caching. A Map or a List used as a
/// key in another Map never matches a rebuilt key, so the lookup misses, the
/// work is redone, and the cache grows one entry per call until the process
/// dies. Supplying only `equals` does not fix it, and the mechanism is sharper
/// than the usual "the probe lands in the wrong bucket": the table records the
/// hash each key was filed under and compares that recorded hash before it will
/// call `equals` at all. An identity hash never repeats, so the `equals` you
/// supplied is not outvoted, it is never invoked — the contract measures 2000
/// fresh pairs and counts zero hits and zero calls into it. Both hooks, or
/// nothing — `HashMap(equals: deep.equals, hashCode: deep.hash)`.
///
/// Tests hide all of this. package:test's `equals` matcher runs its own deep
/// comparison, so `expect(list, equals([1, 2]))` passes while the `==` the
/// production code uses is false. A green suite is not evidence that your
/// equality works.
///
/// If you control the shape, a Dart 3 record is the built-in fix: records have
/// structural equality, so `(1, 2) == (1, 2)`. The escape hatch is only as deep
/// as its fields — a record holding a List compares that field with `==` and is
/// back where it started.

/// A cache keyed by the query itself. The keys here are Maps, which is exactly
/// where the identity default hurts.
typedef Query = Map<String, Object?>;

/// The cache everyone writes first. It compiles, it type-checks, and every
/// lookup with a freshly built query misses.
class IdentityQueryCache {
  final Map<Query, List<String>> _entries = {};

  void store(Query query, List<String> rows) => _entries[query] = rows;

  List<String>? lookup(Query query) => _entries[query];

  int get size => _entries.length;
}

/// The half-fix, and the reason the whole thing is worth a sample: `equals` is
/// supplied and `hashCode` is left at the identity default. It reads as done and
/// it never hits. The miss is structural rather than a matter of collision luck:
/// over 2000 freshly built key pairs on Dart 3.13 the contract counts zero hits
/// and zero calls into the supplied `equals`, because the recorded hash is
/// compared first.
class EqualsOnlyQueryCache {
  static const _deep = DeepCollectionEquality();

  final Map<Query, List<String>> _entries = HashMap(equals: _deep.equals);

  void store(Query query, List<String> rows) => _entries[query] = rows;

  List<String>? lookup(Query query) => _entries[query];

  int get size => _entries.length;
}

/// The same cache with both hooks supplied. `equals` alone would still miss,
/// because the bucket is chosen by the hash before `equals` is ever called.
class DeepQueryCache {
  static const _deep = DeepCollectionEquality();

  final Map<Query, List<String>> _entries = HashMap(
    equals: _deep.equals,
    hashCode: _deep.hash,
  );

  void store(Query query, List<String> rows) => _entries[query] = rows;

  List<String>? lookup(Query query) => _entries[query];

  int get size => _entries.length;
}

/// groupBy keeps the first-occurrence order of the keys, because the Map it
/// returns is a plain insertion-ordered LinkedHashMap.
Map<int, List<String>> wordsByLength(Iterable<String> words) =>
    groupBy(words, (word) => word.length);

/// firstWhere throws StateError when nothing matches, so "not found" arrives as
/// an exception on an ordinary path. firstWhereOrNull returns null instead.
String? firstStartingWith(Iterable<String> words, String prefix) =>
    words.firstWhereOrNull((word) => word.startsWith(prefix));

/// whereNotNull narrows `Iterable<int?>` to `Iterable<int>`. Measured: it is
/// deprecated as of collection 1.19.1 in favour of the SDK's own
/// `Iterable.nonNulls`, which has been in dart:core since Dart 3.0 and does the
/// same job with no dependency. It still runs, so existing code is not broken,
/// but new code should use nonNulls.
// ignore: deprecated_member_use
List<int> presentScores(Iterable<int?> scores) => scores.whereNotNull().toList();

/// The replacement, for comparison in the contract.
List<int> presentScoresFromSdk(Iterable<int?> scores) => scores.nonNulls.toList();

# Generated by pub
# See https://dart.dev/tools/pub/glossary#lockfile
packages:
  _fe_analyzer_shared:
    dependency: transitive
    description:
      name: _fe_analyzer_shared
      sha256: "9a3386eea899815698dd55995277cf7cb8572ee52b399a6edfb7ae2b50e5fc19"
      url: "https://pub.dev"
    source: hosted
    version: "105.0.0"
  analyzer:
    dependency: transitive
    description:
      name: analyzer
      sha256: "62993bed6eadbe9596c5c20d5c167e7bc563c5fe266657a04ddeb93bdb84f4c9"
      url: "https://pub.dev"
    source: hosted
    version: "14.1.0"
  args:
    dependency: transitive
    description:
      name: args
      sha256: d0481093c50b1da8910eb0bb301626d4d8eb7284aa739614d2b394ee09e3ea04
      url: "https://pub.dev"
    source: hosted
    version: "2.7.0"
  async:
    dependency: transitive
    description:
      name: async
      sha256: e2eb0491ba5ddb6177742d2da23904574082139b07c1e33b8503b9f46f3e1a37
      url: "https://pub.dev"
    source: hosted
    version: "2.13.1"
  boolean_selector:
    dependency: transitive
    description:
      name: boolean_selector
      sha256: "8aab1771e1243a5063b8b0ff68042d67334e3feab9e95b9490f9a6ebf73b42ea"
      url: "https://pub.dev"
    source: hosted
    version: "2.1.2"
  cli_config:
    dependency: transitive
    description:
      name: cli_config
      sha256: ac20a183a07002b700f0c25e61b7ee46b23c309d76ab7b7640a028f18e4d99ec
      url: "https://pub.dev"
    source: hosted
    version: "0.2.0"
  collection:
    dependency: "direct main"
    description:
      name: collection
      sha256: "2f5709ae4d3d59dd8f7cd309b4e023046b57d8a6c82130785d2b0e5868084e76"
      url: "https://pub.dev"
    source: hosted
    version: "1.19.1"
  convert:
    dependency: transitive
    description:
      name: convert
      sha256: b30acd5944035672bc15c6b7a8b47d773e41e2f17de064350988c5d02adb1c68
      url: "https://pub.dev"
    source: hosted
    version: "3.1.2"
  coverage:
    dependency: transitive
    description:
      name: coverage
      sha256: "956a3de0725ca232ad353565a8290d3357592bf4250f6f298a185e2d949c5d3d"
      url: "https://pub.dev"
    source: hosted
    version: "1.15.1"
  crypto:
    dependency: transitive
    description:
      name: crypto
      sha256: c8ea0233063ba03258fbcf2ca4d6dadfefe14f02fab57702265467a19f27fadf
      url: "https://pub.dev"
    source: hosted
    version: "3.0.7"
  file:
    dependency: transitive
    description:
      name: file
      sha256: a3b4f84adafef897088c160faf7dfffb7696046cb13ae90b508c2cbc95d3b8d4
      url: "https://pub.dev"
    source: hosted
    version: "7.0.1"
  frontend_server_client:
    dependency: transitive
    description:
      name: frontend_server_client
      sha256: f64a0333a82f30b0cca061bc3d143813a486dc086b574bfb233b7c1372427694
      url: "https://pub.dev"
    source: hosted
    version: "4.0.0"
  glob:
    dependency: transitive
    description:
      name: glob
      sha256: c3f1ee72c96f8f78935e18aa8cecced9ab132419e8625dc187e1c2408efc20de
      url: "https://pub.dev"
    source: hosted
    version: "2.1.3"
  http_multi_server:
    dependency: transitive
    description:
      name: http_multi_server
      sha256: aa6199f908078bb1c5efb8d8638d4ae191aac11b311132c3ef48ce352fb52ef8
      url: "https://pub.dev"
    source: hosted
    version: "3.2.2"
  http_parser:
    dependency: transitive
    description:
      name: http_parser
      sha256: "178d74305e7866013777bab2c3d8726205dc5a4dd935297175b19a23a2e66571"
      url: "https://pub.dev"
    source: hosted
    version: "4.1.2"
  io:
    dependency: transitive
    description:
      name: io
      sha256: dfd5a80599cf0165756e3181807ed3e77daf6dd4137caaad72d0b7931597650b
      url: "https://pub.dev"
    source: hosted
    version: "1.0.5"
  logging:
    dependency: transitive
    description:
      name: logging
      sha256: c8245ada5f1717ed44271ed1c26b8ce85ca3228fd2ffdb75468ab01979309d61
      url: "https://pub.dev"
    source: hosted
    version: "1.3.0"
  matcher:
    dependency: transitive
    description:
      name: matcher
      sha256: "31bd099b47c10cd1aeb55146a2d46ce0277630ecef3f7dae54ad7873f36696cd"
      url: "https://pub.dev"
    source: hosted
    version: "0.12.20"
  meta:
    dependency: transitive
    description:
      name: meta
      sha256: "307249ce4ff29d58a18e97f6345f539382eb9c9c29ecda628900f31de0443dd9"
      url: "https://pub.dev"
    source: hosted
    version: "1.19.0"
  mime:
    dependency: transitive
    description:
      name: mime
      sha256: "41a20518f0cb1256669420fdba0cd90d21561e560ac240f26ef8322e45bb7ed6"
      url: "https://pub.dev"
    source: hosted
    version: "2.0.0"
  node_preamble:
    dependency: transitive
    description:
      name: node_preamble
      sha256: "6e7eac89047ab8a8d26cf16127b5ed26de65209847630400f9aefd7cd5c730db"
      url: "https://pub.dev"
    source: hosted
    version: "2.0.2"
  package_config:
    dependency: transitive
    description:
      name: package_config
      sha256: ffcf4cf3d6c0b74ac43708d9f56625506e8a68aa935abe9d267a7330f320eb5d
      url: "https://pub.dev"
    source: hosted
    version: "3.0.0"
  path:
    dependency: transitive
    description:
      name: path
      sha256: "75cca69d1490965be98c73ceaea117e8a04dd21217b37b292c9ddbec0d955bc5"
      url: "https://pub.dev"
    source: hosted
    version: "1.9.1"
  pool:
    dependency: transitive
    description:
      name: pool
      sha256: "978783255c543aa3586a1b3c21f6e9d720eb315376a915872c61ef8b5c20177d"
      url: "https://pub.dev"
    source: hosted
    version: "1.5.2"
  pub_semver:
    dependency: transitive
    description:
      name: pub_semver
      sha256: "5bfcf68ca79ef689f8990d1160781b4bad40a3bd5e5218ad4076ddb7f4081585"
      url: "https://pub.dev"
    source: hosted
    version: "2.2.0"
  shelf:
    dependency: transitive
    description:
      name: shelf
      sha256: e7dd780a7ffb623c57850b33f43309312fc863fb6aa3d276a754bb299839ef12
      url: "https://pub.dev"
    source: hosted
    version: "1.4.2"
  shelf_packages_handler:
    dependency: transitive
    description:
      name: shelf_packages_handler
      sha256: "89f967eca29607c933ba9571d838be31d67f53f6e4ee15147d5dc2934fee1b1e"
      url: "https://pub.dev"
    source: hosted
    version: "3.0.2"
  shelf_static:
    dependency: transitive
    description:
      name: shelf_static
      sha256: c87c3875f91262785dade62d135760c2c69cb217ac759485334c5857ad89f6e3
      url: "https://pub.dev"
    source: hosted
    version: "1.1.3"
  shelf_web_socket:
    dependency: transitive
    description:
      name: shelf_web_socket
      sha256: "3632775c8e90d6c9712f883e633716432a27758216dfb61bd86a8321c0580925"
      url: "https://pub.dev"
    source: hosted
    version: "3.0.0"
  source_map_stack_trace:
    dependency: transitive
    description:
      name: source_map_stack_trace
      sha256: c0713a43e323c3302c2abe2a1cc89aa057a387101ebd280371d6a6c9fa68516b
      url: "https://pub.dev"
    source: hosted
    version: "2.1.2"
  source_maps:
    dependency: transitive
    description:
      name: source_maps
      sha256: "190222579a448b03896e0ca6eca5998fa810fda630c1d65e2f78b3f638f54812"
      url: "https://pub.dev"
    source: hosted
    version: "0.10.13"
  source_span:
    dependency: transitive
    description:
      name: source_span
      sha256: "56a02f1f4cd1a2d96303c0144c93bd6d909eea6bee6bf5a0e0b685edbd4c47ab"
      url: "https://pub.dev"
    source: hosted
    version: "1.10.2"
  stack_trace:
    dependency: transitive
    description:
      name: stack_trace
      sha256: "8b27215b45d22309b5cddda1aa2b19bdfec9df0e765f2de506401c071d38d1b1"
      url: "https://pub.dev"
    source: hosted
    version: "1.12.1"
  stream_channel:
    dependency: transitive
    description:
      name: stream_channel
      sha256: "969e04c80b8bcdf826f8f16579c7b14d780458bd97f56d107d3950fdbeef059d"
      url: "https://pub.dev"
    source: hosted
    version: "2.1.4"
  string_scanner:
    dependency: transitive
    description:
      name: string_scanner
      sha256: "921cd31725b72fe181906c6a94d987c78e3b98c2e205b397ea399d4054872b43"
      url: "https://pub.dev"
    source: hosted
    version: "1.4.1"
  term_glyph:
    dependency: transitive
    description:
      name: term_glyph
      sha256: "7f554798625ea768a7518313e58f83891c7f5024f88e46e7182a4558850a4b8e"
      url: "https://pub.dev"
    source: hosted
    version: "1.2.2"
  test:
    dependency: "direct dev"
    description:
      name: test
      sha256: "0d5ba5602ec3baa28c8ce365e1efc5575969c765f45c554a3e167dc7945b9c30"
      url: "https://pub.dev"
    source: hosted
    version: "1.31.2"
  test_api:
    dependency: transitive
    description:
      name: test_api
      sha256: "475610b2aa23c19687cce2961e44b0cc57cafe220f67c2b80201231b2a07fbe7"
      url: "https://pub.dev"
    source: hosted
    version: "0.7.13"
  test_core:
    dependency: transitive
    description:
      name: test_core
      sha256: a39c204a4fc7a7ccb04a2b985e359fda3cc37e45e0b8ac61c3fb1a05aa832132
      url: "https://pub.dev"
    source: hosted
    version: "0.6.19"
  typed_data:
    dependency: transitive
    description:
      name: typed_data
      sha256: f9049c039ebfeb4cf7a7104a675823cd72dba8297f264b6637062516699fa006
      url: "https://pub.dev"
    source: hosted
    version: "1.4.0"
  vm_service:
    dependency: transitive
    description:
      name: vm_service
      sha256: "0016aef94fc66495ac78af5859181e3f3bf2026bd8eecc72b9565601e19ab360"
      url: "https://pub.dev"
    source: hosted
    version: "15.2.0"
  watcher:
    dependency: transitive
    description:
      name: watcher
      sha256: "1398c9f081a753f9226febe8900fce8f7d0a67163334e1c94a2438339d79d635"
      url: "https://pub.dev"
    source: hosted
    version: "1.2.1"
  web:
    dependency: transitive
    description:
      name: web
      sha256: "868d88a33d8a87b18ffc05f9f030ba328ffefba92d6c127917a2ba740f9cfe4a"
      url: "https://pub.dev"
    source: hosted
    version: "1.1.1"
  web_socket:
    dependency: transitive
    description:
      name: web_socket
      sha256: "34d64019aa8e36bf9842ac014bb5d2f5586ca73df5e4d9bf5c936975cae6982c"
      url: "https://pub.dev"
    source: hosted
    version: "1.0.1"
  web_socket_channel:
    dependency: transitive
    description:
      name: web_socket_channel
      sha256: d645757fb0f4773d602444000a8131ff5d48c9e47adfe9772652dd1a4f2d45c8
      url: "https://pub.dev"
    source: hosted
    version: "3.0.3"
  webkit_inspection_protocol:
    dependency: transitive
    description:
      name: webkit_inspection_protocol
      sha256: "87d3f2333bb240704cd3f1c6b5b7acd8a10e7f0bc28c28dcf14e782014f4a572"
      url: "https://pub.dev"
    source: hosted
    version: "1.2.1"
  yaml:
    dependency: transitive
    description:
      name: yaml
      sha256: b9da305ac7c39faa3f030eccd175340f968459dae4af175130b3fc47e40d76ce
      url: "https://pub.dev"
    source: hosted
    version: "3.1.3"
sdks:
  dart: ">=3.11.0 <4.0.0"

name: csx_collection_equality
description: Why two Dart Lists with the same contents are not ==, and what package:collection does about it.
publish_to: none
environment:
  sdk: ^3.11.0
dependencies:
  collection: 1.19.1
dev_dependencies:
  test: 1.31.2

import 'dart:collection';

import 'package:collection/collection.dart';
import 'package:csx_collection_equality/equality.dart';
import 'package:test/test.dart';

void main() {
  test('same contents, different objects: == on SDK collections is identity',
      () {
    final left = [1, 2];
    final right = [1, 2];

    expect(identical(left, right), isFalse);
    expect(left == right, isFalse);
    expect({'a': 1} == {'a': 1}, isFalse);
    expect({1, 2} == {1, 2}, isFalse);
    // Copying is not a rescue: every constructor produces a new object.
    expect(left == [...left], isFalse);
    expect(left == List<int>.of(left), isFalse);

    // And this is why the bug survives review: package:test's equals matcher
    // does its own deep comparison, so the assertion passes on exactly the
    // values the production `==` calls unequal.
    expect(left, equals(right));
    expect({'a': 1}, equals({'a': 1}));
    // The matcher recurses, so even the nested shape that defeats the one-level
    // Equality objects below is green here.
    expect([
      [1],
      [2]
    ], equals([
      [1],
      [2]
    ]));
    expect(left, isNot(same(right)));
  });

  test('const collections are canonicalized, which is what makes it confusing',
      () {
    // Same literal as above, opposite answer. A const collection is one shared
    // instance for the whole program, so identity happens to be right.
    expect(identical(const [1, 2], const [1, 2]), isTrue);
    expect(const [1, 2] == const [1, 2], isTrue);
    expect(const {'a': 1} == const {'a': 1}, isTrue);
    expect(const {1, 2} == const {1, 2}, isTrue);

    // Canonicalization is per type argument: these two hold the same numbers
    // and are still two objects.
    expect(identical(const <int>[1, 2], const <num>[1, 2]), isFalse);
    expect(const <int>[1, 2] == const <num>[1, 2], isFalse);

    // It also does not survive being copied, so the moment a const list is
    // spread into a builder the equality quietly reverts.
    expect(const [1, 2] == [...const [1, 2]], isFalse);
  });

  test('the Equality objects compare contents, exactly one level deep', () {
    const listEq = ListEquality<int>();
    expect(listEq.equals([1, 2], [1, 2]), isTrue);
    expect(listEq.hash([1, 2]), equals(listEq.hash([1, 2])));
    // A List is ordered, so this is an inequality and not a set comparison.
    expect(listEq.equals([1, 2], [2, 1]), isFalse);
    expect(listEq.equals([1, 2], [1, 2, 3]), isFalse);

    // A Map is not ordered for equality purposes: same pairs, written in the
    // other order, is equal.
    const mapEq = MapEquality<String, int>();
    expect(mapEq.equals({'a': 1, 'b': 2}, {'b': 2, 'a': 1}), isTrue);
    expect(mapEq.equals({'a': 1}, {'a': 1, 'b': 2}), isFalse);

    // Set equality has the same identity default as List (`{1, 2} == {1, 2}`
    // is false above) and SetEquality is the fix, order-insensitive by nature.
    const setEq = SetEquality<int>();
    expect(setEq.equals({1, 2}, {2, 1}), isTrue);
    expect(setEq.hash({1, 2}), equals(setEq.hash({2, 1})));
    expect(setEq.equals({1, 2}, {1, 2, 3}), isFalse);

    // IterableEquality compares in order without caring what the container is,
    // which is the one to reach for when you hold an Iterable you did not build.
    expect(const IterableEquality<int>().equals([1, 2], {1, 2}), isTrue);
  });

  test('one level is not enough: nested elements are compared with ==', () {
    const listOfLists = ListEquality<List<int>>();
    // The outer List is compared by content, the inner ones by `==`, which is
    // identity again. This is the failure that sends people to the docs.
    expect(listOfLists.equals([
      [1],
      [2]
    ], [
      [1],
      [2]
    ]), isFalse);

    // Make the inner lists const and the identical call answers true, because
    // the canonical instances really are identical. Same equality object, same
    // shape, different answer, decided by a keyword on the elements.
    expect(listOfLists.equals([const [1], const [2]], [const [1], const [2]]),
        isTrue);

    // Map values go the same way.
    expect(
        const MapEquality<String, List<int>>().equals({
          'a': [1]
        }, {
          'a': [1]
        }),
        isFalse);
  });

  test('DeepCollectionEquality recurses, and unordered() extends it to Lists',
      () {
    const deep = DeepCollectionEquality();
    final left = {
      'ids': [1, 2],
      'meta': {
        'tags': {'a', 'b'},
        'nested': [
          [3]
        ],
      },
    };
    final right = {
      'meta': {
        'nested': [
          [3]
        ],
        'tags': {'b', 'a'},
      },
      'ids': [1, 2],
    };

    expect(left == right, isFalse);
    expect(deep.equals(left, right), isTrue);

    // The plain DeepCollectionEquality is already order-insensitive for Sets
    // and Map keys, because it dispatches per collection type on the way down.
    // Only Lists stay ordered, which is the distinction the name hides.
    expect(deep.equals({1, 2}, {2, 1}), isTrue);
    expect(deep.equals([1, 2], [2, 1]), isFalse);
    expect(const DeepCollectionEquality.unordered().equals([1, 2], [2, 1]),
        isTrue);
    // Unordered still counts, so it is a multiset and not a set.
    expect(const DeepCollectionEquality.unordered().equals([1, 2], [1, 2, 2]),
        isFalse);

    // Non-collections fall through to the base equality, so it is safe to hand
    // it a value of unknown shape.
    expect(deep.equals('ab', 'ab'), isTrue);
    expect(deep.equals(1, 2), isFalse);
  });

  test('a Map used as a key needs both equals and hash, or it never matches',
      () {
    final query = {'status': 'open', 'limit': 10};
    final rebuilt = {'status': 'open', 'limit': 10};

    final plain = IdentityQueryCache()..store(query, ['a-1', 'a-2']);
    // The instance you stored under works, which is how this ships: the first
    // test written is usually the one that reuses the variable.
    expect(plain.lookup(query), equals(['a-1', 'a-2']));
    // An equal query built anywhere else misses.
    expect(plain.lookup(rebuilt), isNull);
    // So the cache is not a cache. It is a leak with a lookup method: every
    // call adds an entry and none of them are ever found again.
    plain.store(rebuilt, ['a-1', 'a-2']);
    expect(plain.size, equals(2));

    final deep = DeepQueryCache()..store(query, ['a-1', 'a-2']);
    expect(deep.lookup(rebuilt), equals(['a-1', 'a-2']));
    // Writing under an equal key replaces rather than adds.
    deep.store(rebuilt, ['a-1']);
    expect(deep.size, equals(1));
    expect(deep.lookup(query), equals(['a-1']));
    // Key order in the literal is irrelevant, because Map equality is not
    // ordered — the cache does not care how the caller spelled the query.
    expect(deep.lookup({'limit': 10, 'status': 'open'}), equals(['a-1']));
    // A key holding a nested collection still matches, which is the part that
    // needs the deep equality rather than MapEquality.
    final nested = DeepQueryCache()
      ..store({
        'ids': [1, 2]
      }, [
        'a-1'
      ]);
    expect(
        nested.lookup({
          'ids': [1, 2]
        }),
        equals(['a-1']));
  });

  test('the hash is the half people forget', () {
    const deep = DeepCollectionEquality();
    final left = {
      'ids': [1, 2]
    };
    final right = {
      'ids': [1, 2]
    };

    expect(identical(left, right), isFalse);
    expect(deep.equals(left, right), isTrue);
    // Equal structures hash the same, which is the contract a hash table needs
    // and the thing Object.hashCode cannot give you: it is an identity hash, so
    // these two are filed under different hashes and `equals` is never consulted.
    expect(deep.hash(left), equals(deep.hash(right)));

    // Which makes the half-fix worse than no fix: a HashMap given `equals` and
    // not `hashCode` still misses, so the equality you supplied is dead code.
    final half = EqualsOnlyQueryCache()
      ..store({'status': 'open'}, ['a-1']);
    expect(half.lookup({'status': 'open'}), isNull);
    final both = DeepQueryCache()..store({'status': 'open'}, ['a-1']);
    expect(both.lookup({'status': 'open'}), equals(['a-1']));

    // And it is not collision luck. Over 2000 freshly built pairs nothing hits,
    // and the supplied `equals` is not called once: the table compares the hash
    // each key was filed under before it consults equality, and an identity hash
    // never repeats. So the tempting story — that an equal-but-distinct key gets
    // found whenever the two keys happen to share a bucket — is wrong; the
    // equality never gets a vote.
    var equalsCalls = 0;
    var hits = 0;
    for (var i = 0; i < 2000; i++) {
      final table = HashMap<Query, String>(equals: (a, b) {
        equalsCalls++;
        return deep.equals(a, b);
      });
      table[{'status': 'open', 'limit': i}] = 'row';
      if (table[{'status': 'open', 'limit': i}] != null) hits++;
    }
    expect(hits, isZero);
    expect(equalsCalls, isZero);

    // The hash tracks its equality. Order changes the ordered hash and not the
    // unordered one, so the pairs stay consistent whichever you pick.
    expect(deep.hash([1, 2]), isNot(equals(deep.hash([2, 1]))));
    expect(const DeepCollectionEquality.unordered().hash([1, 2]),
        equals(const DeepCollectionEquality.unordered().hash([2, 1])));
  });

  test('groupBy, firstWhereOrNull and whereNotNull', () {
    const words = ['ada', 'grace', 'alan', 'edsger', 'ken'];

    expect(
        wordsByLength(words),
        equals({
          3: ['ada', 'ken'],
          5: ['grace'],
          4: ['alan'],
          6: ['edsger'],
        }));
    // The keys come out in first-occurrence order, not sorted, and the values
    // keep the input order — worth pinning, because it is what makes groupBy
    // usable for rendering without a second sort.
    expect(wordsByLength(words).keys.toList(), equals([3, 5, 4, 6]));

    expect(firstStartingWith(words, 'e'), equals('edsger'));
    expect(firstStartingWith(words, 'z'), isNull);
    // The SDK method it replaces throws instead of returning null.
    expect(() => words.firstWhere((word) => word.startsWith('z')),
        throwsStateError);

    const scores = <int?>[10, null, 7, null, 3];
    expect(presentScores(scores), equals([10, 7, 3]));
    // The point of it is the type: Iterable<int?> in, List<int> out, no `!`.
    expect(presentScores(scores), isA<List<int>>());
    // Measured: whereNotNull is deprecated in collection 1.19.1 and the SDK's
    // nonNulls is the replacement. Same elements, same order, no dependency.
    expect(presentScores(scores), equals(presentScoresFromSdk(scores)));
  });

  test('records have value equality; a record holding a List does not', () {
    // The built-in fix when you control the shape. No package, no Equality
    // object, and it works as a Map key because the hashCode is structural too.
    expect((1, 2) == (1, 2), isTrue);
    expect((id: 'a-1', qty: 2) == (id: 'a-1', qty: 2), isTrue);
    expect({(1, 2): 'hit'}[(1, 2)], equals('hit'));

    // Only as deep as its fields: the record compares each field with `==`, so
    // a List field is identity again and the whole record is unequal.
    expect(([1, 2],) == ([1, 2],), isFalse);
    final shared = [1, 2];
    expect((shared,) == (shared,), isTrue);
  });
}