]> git.ipfire.org Git - thirdparty/Python/cpython.git/commit
gh-119105: Differ.compare is too slow [for degenerate cases] (#119492)
authorTim Peters <tim.peters@gmail.com>
Sat, 25 May 2024 03:08:21 +0000 (22:08 -0500)
committerGitHub <noreply@github.com>
Sat, 25 May 2024 03:08:21 +0000 (22:08 -0500)
commitde19694cfbcaa1c85c3a4b7184a24ff21b1c0919
treee89934fb91ec8b089f7a088ac313275ee3f4a8b0
parent84be5244de75c92904fb41326c9a69f19051e7ab
gh-119105: Differ.compare is too slow [for degenerate cases] (#119492)

``_fancy_replace()`` is no longer recursive. and a single call does a worst-case linear number of ratio() computations instead of quadratic. This renders toothless a universe of pathological cases. Some inputs may produce different output, but that's rare, and I didn't find a case where the final diff appeared to be of materially worse quality. To the contrary, by refusing to even consider synching on lines "far apart", there was more easy-to-digest locality in the output.
Lib/difflib.py
Misc/NEWS.d/next/Library/2024-05-24-04-05-37.gh-issue-119105.aDSRFn.rst [new file with mode: 0644]