preact@10.22.0 unexpected child ordering with skew based diff

[hzy]

• Check if updating to the latest Preact version resolves the issue (Checked, the issue still reproduce)

Describe the bug
With preact version from 10.16.0 to 10.22.0, and code below:

<div>
  {items.map((key) => (
    <div key={key}>{key}</div>
  ))}
</div>

Updating array items (shuffle it) leads to unexpected ordering.

preact version 10.15.0 and below will not reproduce this issue.

To Reproduce (with Stackblitz)

Steps to reproduce the behavior:

1. Open project at https://stackblitz.com/edit/create-preact-starter-ckjsze?file=src%2Findex.jsx
2. You can see numbers in order:

   1
   3
   4
   0
   5
   2
   6
   

Expected behavior
Numbers should be in order:

1
3
5
2
6
4
0

To Reproduce (in preact unit test)

1. Put code below inside file test/browser/render.test.js,

   it("shuffle", function () {
       const jsx = (items) => (
   	    <div>
   		    {items.map((key) => (
   			    <div key={key}>{key}</div>
   		    ))}
   	    </div>
       );
       const a = ["0", "1", "2", "3", "4", "5", "6"];
       const b = ["1", "3", "5", "2", "6", "4", "0"];
       render(jsx(a), scratch);
       render(jsx(b), scratch);
   
       expect(scratch.innerHTML).to.equal(
   	    `<div>${b.map(n => `<div>${n}</div>`).join("")}</div>`
       );
   });

2. run test, the test above will FAIL

Expected behavior
Test should pass.

[hzy]

@JoviDeCroock Thank you for your timely fix.
But I think this problem has not been completely solved, if runs on highly randomized input.

To Reproduce (in preact unit test)

1. Put code below inside file test/browser/render.test.js,

it('handle shuffled', () => {
	function randomize(arr) {
		for (let i = arr.length - 1; i > 0; i--) {
			let j = Math.floor(Math.random() * (i + 1));
			[arr[i], arr[j]] = [arr[j], arr[i]];
		}
		return arr;
	}

	const App = ({items}) => (
		<div>
			{items.map(key => (
			<div key={key}>
				{key}
			</div>
			))}
		</div>
	);

	const a = Array.from({ length: 8 }).map((_, i) => `${i}`);

	for (let i = 0; i < 10000; i++) {
		const aa = randomize(a);
		render(<App items={aa}/>, scratch);
		expect(scratch.innerHTML).to.equal(
			`<div>${aa.map(n => `<div>${n}</div>`).join('')}</div>`
		);
	}
});

2. run test, the test above will FAIL

Expected behavior
Test should pass.

[JoviDeCroock]

@hzy Thank you so much for reporting these, added a log here

	for (let i = 0; i < 10000; i++) {
		const aa = randomize(a);
                console.log(aa)
		render(<App items={aa}/>, scratch);
		expect(scratch.innerHTML).to.equal(
			`<div>${aa.map(n => `<div>${n}</div>`).join('')}</div>`
		);
	}

To find the exact sequence that makes it fail and made #4472 to fix it. Thank you for bearing with me to find this fix. In the future you would be better off creating a new issue, I came across this by accident 😅 closed issues are often unsubscribed from