Berry: [Bug] patch protocol can result in infinite loop

[andreialecu]

• [ ] I'd be willing to implement a fix

Describe the bug

I noticed a certain patch resulting in yarn being stuck in an infinite loop while trying to apply it.

To Reproduce

Reproduction

```js repro
await yarn("init", "-y");
const { execSync } = require('child_process');

execSync("yarn add git-file-downloader");
execSync("yarn git-file-downloader andreialecu/yarn-patch-bug types-mongoose.patch");

execSync("yarn policies set-version berry");
try {
execSync("yarn add @types/mongoose@patch:@types/[email protected]#types-mongoose.patch", { timeout: 30000 });
} catch (err) {
expect(err).toBeFalsy();
}
expect(true).toBeTruthy();

</details>

Full repro at: https://github.com/andreialecu/yarn-patch-bug

**Additional context**

The repro isn't great because of the lack of `setTimeout/clearTimeout` in Sherlock. Ref:

ReferenceError: setTimeout is not defined
at module.exports (evalmachine.:7:17)
at process._tickCallback (internal/process/next_tick.js:68:7)
`` https://github.com/arcanis/sherlock/blob/master/sources/executeRepro.ts#L23-L26 perhapssetTimeout/clearTimeout` could be added here so they can be used in reproductions.

[yarnbot]

The reproduction case in your issue seems broken (ie it neither pass nor fail due to throwing an unmanaged exception):

Error: Command failed: curl https://raw.githubusercontent.com/andreialecu/yarn-patch-bug/master/types-mongoose.patch > foo.patch
/bin/sh: curl: not found

    at checkExecSyncError (child_process.js:630:11)
    at execSync (child_process.js:666:15)
    at module.exports (evalmachine.<anonymous>:5:1)
    at processTicksAndRejections (internal/process/task_queues.js:97:5)
    at async /github/workspace/.yarn/cache/@arcanis-sherlock-npm-1.0.38-d4f5e2dbf3-63f998598d.zip/node_modules/@arcanis/sherlock/lib/executeRepro.js:56:13
    at async executeInTempDirectory (/github/workspace/.yarn/cache/@arcanis-sherlock-npm-1.0.38-d4f5e2dbf3-63f998598d.zip/node_modules/@arcanis/sherlock/lib/executeRepro.js:17:16)
    at async Object.executeRepro (/github/workspace/.yarn/cache/@arcanis-sherlock-npm-1.0.38-d4f5e2dbf3-63f998598d.zip/node_modules/@arcanis/sherlock/lib/executeRepro.js:24:12)
    at async ExecCommand.execute (/github/workspace/.yarn/cache/@arcanis-sherlock-npm-1.0.38-d4f5e2dbf3-63f998598d.zip/node_modules/@arcanis/sherlock/lib/commands/exec.js:25:38)
    at async ExecCommand.validateAndExecute (/github/workspace/.yarn/cache/clipanion-npm-2.0.0-rc.16-b9444aaf89-a57989414f.zip/node_modules/clipanion/lib/advanced/Command.js:161:26)
    at async Cli.run (/github/workspace/.yarn/cache/clipanion-npm-2.0.0-rc.16-b9444aaf89-a57989414f.zip/node_modules/clipanion/lib/advanced/Cli.js:74:24)

Remember: any non-Jest exceptions will cause the test to be reported as broken. If you expect something to pass without throwing, you must wrap it into something like await expect(...).resolves.toBeTruthy(). If you instead expect something to throw, you need to wrap it into await expect(...).rejects.toThrow().

[yarnbot]

The reproduction case in your issue seems broken (ie it neither pass nor fail due to throwing an unmanaged exception):

Error: Command failed: npx git-file-downloader andreialecu/yarn-patch-bug types-mongoose.patch
/bin/sh: npx: not found

    at checkExecSyncError (child_process.js:630:11)
    at execSync (child_process.js:666:15)
    at module.exports (evalmachine.<anonymous>:5:1)
    at processTicksAndRejections (internal/process/task_queues.js:97:5)
    at async /github/workspace/.yarn/cache/@arcanis-sherlock-npm-1.0.38-d4f5e2dbf3-63f998598d.zip/node_modules/@arcanis/sherlock/lib/executeRepro.js:56:13
    at async executeInTempDirectory (/github/workspace/.yarn/cache/@arcanis-sherlock-npm-1.0.38-d4f5e2dbf3-63f998598d.zip/node_modules/@arcanis/sherlock/lib/executeRepro.js:17:16)
    at async Object.executeRepro (/github/workspace/.yarn/cache/@arcanis-sherlock-npm-1.0.38-d4f5e2dbf3-63f998598d.zip/node_modules/@arcanis/sherlock/lib/executeRepro.js:24:12)
    at async ExecCommand.execute (/github/workspace/.yarn/cache/@arcanis-sherlock-npm-1.0.38-d4f5e2dbf3-63f998598d.zip/node_modules/@arcanis/sherlock/lib/commands/exec.js:25:38)
    at async ExecCommand.validateAndExecute (/github/workspace/.yarn/cache/clipanion-npm-2.0.0-rc.16-b9444aaf89-a57989414f.zip/node_modules/clipanion/lib/advanced/Command.js:161:26)
    at async Cli.run (/github/workspace/.yarn/cache/clipanion-npm-2.0.0-rc.16-b9444aaf89-a57989414f.zip/node_modules/clipanion/lib/advanced/Cli.js:74:24)

Remember: any non-Jest exceptions will cause the test to be reported as broken. If you expect something to pass without throwing, you must wrap it into something like await expect(...).resolves.toBeTruthy(). If you instead expect something to throw, you need to wrap it into await expect(...).rejects.toThrow().

[yarnbot]

This issue reproduces on master:

Error: expect(received).toBeFalsy()

Received: [Error: spawnSync /bin/sh ETIMEDOUT]
    at module.exports (evalmachine.<anonymous>:12:15)
    at processTicksAndRejections (internal/process/task_queues.js:97:5)
    at async /github/workspace/.yarn/cache/@arcanis-sherlock-npm-1.0.38-d4f5e2dbf3-63f998598d.zip/node_modules/@arcanis/sherlock/lib/executeRepro.js:56:13
    at async executeInTempDirectory (/github/workspace/.yarn/cache/@arcanis-sherlock-npm-1.0.38-d4f5e2dbf3-63f998598d.zip/node_modules/@arcanis/sherlock/lib/executeRepro.js:17:16)
    at async Object.executeRepro (/github/workspace/.yarn/cache/@arcanis-sherlock-npm-1.0.38-d4f5e2dbf3-63f998598d.zip/node_modules/@arcanis/sherlock/lib/executeRepro.js:24:12)
    at async ExecCommand.execute (/github/workspace/.yarn/cache/@arcanis-sherlock-npm-1.0.38-d4f5e2dbf3-63f998598d.zip/node_modules/@arcanis/sherlock/lib/commands/exec.js:25:38)
    at async ExecCommand.validateAndExecute (/github/workspace/.yarn/cache/clipanion-npm-2.0.0-rc.16-b9444aaf89-a57989414f.zip/node_modules/clipanion/lib/advanced/Command.js:161:26)
    at async Cli.run (/github/workspace/.yarn/cache/clipanion-npm-2.0.0-rc.16-b9444aaf89-a57989414f.zip/node_modules/clipanion/lib/advanced/Cli.js:74:24)
    at async Cli.runExit (/github/workspace/.yarn/cache/clipanion-npm-2.0.0-rc.16-b9444aaf89-a57989414f.zip/node_modules/clipanion/lib/advanced/Cli.js:83:28)

[bgotink]

Every hunk in the patch takes ± double the time the previous hunk took to apply

the first hunks apply too fast to be measured correctly with the millisecond precision of Date.now()

hunk 17 took 6 ms
hunk 18 took 11 ms
hunk 19 took 23 ms
hunk 20 took 44 ms
hunk 21 took 82 ms
hunk 22 took 156 ms
hunk 23 took 312 ms
hunk 24 took 602 ms
hunk 25 took 1195 ms
hunk 26 took 2423 ms
hunk 27 took 4607 ms
hunk 28 took 8997 ms
hunk 29 took 19053 ms
hunk 30 took 93713 ms <-- at lot more than double

The patch in the repro contains 117 hunks.
On a bright note, the patch would take ± 4x10**20 years to apply, so it'd be finished well before the heat death of the universe.

The issue lies in the fuzzy search when trying to apply a hunk of the patch. A wrong sign led the fuzzy search area to grow exponentially, which in turn led to the execution time growing exponentially.