lukeed / lukeed/dequal

False negative: equal Maps with duplicate-shaped keys (greedy matching)

Open
#41 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
JavaScript
Stars
1.5k
Forks
36
PR merge metrics
No merged PRs in 30d

Description

Greedy key matching produces a **false negative** on genuinely equal Maps
when multiple keys are structurally equal:

```js
import { dequal } from 'dequal';

const A = new Map([[{}, 1], [{}, 2]]);
const B = new Map([[{}, 2], [{}, 1]]);

console.log(dequal(A, B)); // false — but both are the same multiset of entries ({}→1, {}→2)
```

The matcher pairs each key of `A` with the *first* structurally-equal key of
`B` and never reconsiders, so when that first pairing has the wrong value the
whole comparison fails even though a valid pairing exists. Deciding this
correctly needs backtracking (or equivalent) over equal-key groups.

Related but distinct from #31: that one is a false *positive* on Sets
(overcounting); this is a false *negative* on Maps (greedy undercounting).
Both stem from element matching without multiplicity/backtracking.

Found by an 8,000-pair differential fuzz against a brute-force matcher;
happy to share more failing cases if useful (they're all this shape:
duplicate-structural keys whose values differ per pairing).

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by locating the Map comparison path and any existing collection-equality tests. Reproduce the two Maps from the issue, then add a regression case covering structurally equal duplicate keys with different values. Done means equal Maps return true without breaking existing Map and Set comparisons.

Written by the indexing model from the issue text.

Assessment

Tech stack
javascript
Domain
tooling
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
65/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.