kpdecker / jsdiff

A javascript text differencing implementation.
BSD 3-Clause "New" or "Revised" License
8k stars 498 forks source link

Endless loop + hang with 100% CPU usage in execEditLength() when calling structuredPatch() #364

Closed xeger closed 2 years ago

xeger commented 2 years ago

I encountered a hang in Yarn 3.2.0 and have isolated the root cause as an infinite loop in diff@4.0.1. (I'm not sure it's strictly infinite -- but it certainly doesn't terminate after an hour.) When Yarn asks diff to create a structured patch in order to show the user how the lockfile has changed, diff runs forever, consuming a lot of CPU while it does so.

I have reproduced the issue in this gist for your convenience.

I also verified that the hang still happens with diff@5.0.0 -- so it's still a legitimate issue. If I make any progress on diagnosing or fixing, I will update this ticket.