https://github.com/python/cpython/commit/1f25c333a280561e86cc0af69af307b53ddbaaac
commit: 1f25c333a280561e86cc0af69af307b53ddbaaac
branch: main
author: felix <[email protected]>
committer: encukou <[email protected]>
date: 2026-09-07T16:33:54+02:00
summary:
gh-156505: Speed up difflib.HtmlDiff for lopsided replacements (GH-156506)
files:
M Lib/difflib.py
M Lib/test/test_difflib.py
diff --git a/Lib/difflib.py b/Lib/difflib.py
index c081cd8606df5b..54fc57db975b25 100644
--- a/Lib/difflib.py
+++ b/Lib/difflib.py
@@ -31,7 +31,7 @@
'unified_diff', 'diff_bytes', 'HtmlDiff', 'Match']
from heapq import nlargest as _nlargest
-from collections import namedtuple as _namedtuple
+from collections import deque as _deque, namedtuple as _namedtuple
from types import GenericAlias
lazy from _colorize import can_colorize, get_theme
@@ -1571,7 +1571,7 @@ def _line_pair_iterator():
is defined) does not need to be of module scope.
"""
line_iterator = _line_iterator()
- fromlines,tolines=[],[]
+ fromlines, tolines = _deque(), _deque()
while True:
# Collecting lines of text until we have a from/to pair
while (len(fromlines)==0 or len(tolines)==0):
@@ -1584,8 +1584,8 @@ def _line_pair_iterator():
if to_line is not None:
tolines.append((to_line,found_diff))
# Once we have a pair, remove them from the collection and yield it
- from_line, fromDiff = fromlines.pop(0)
- to_line, to_diff = tolines.pop(0)
+ from_line, fromDiff = fromlines.popleft()
+ to_line, to_diff = tolines.popleft()
yield (from_line,to_line,fromDiff or to_diff)
# Handle case where user does not want context differencing, just yield
diff --git a/Lib/test/test_difflib.py b/Lib/test/test_difflib.py
index 5babe834e9beac..8c554d7c95b5f6 100644
--- a/Lib/test/test_difflib.py
+++ b/Lib/test/test_difflib.py
@@ -200,6 +200,26 @@ def test_mdiff_catch_stop_iteration(self):
[((1, '\x00-2\x01'), (1, '\x00+3\x01'), True)],
)
+ def test_mdiff_lopsided_replace(self):
+ self.assertEqual(
+ list(difflib._mdiff(["a\n"] * 4, ["b\n"])),
+ [
+ ((1, '\x00-a\n\x01'), (1, '\x00+b\n\x01'), True),
+ ((2, '\x00-a\n\x01'), ('', '\n'), True),
+ ((3, '\x00-a\n\x01'), ('', '\n'), True),
+ ((4, '\x00-a\n\x01'), ('', '\n'), True),
+ ],
+ )
+ self.assertEqual(
+ list(difflib._mdiff(["a\n"], ["b\n"] * 4)),
+ [
+ ((1, '\x00-a\n\x01'), (1, '\x00+b\n\x01'), True),
+ (('', '\n'), (2, '\x00+b\n\x01'), True),
+ (('', '\n'), (3, '\x00+b\n\x01'), True),
+ (('', '\n'), (4, '\x00+b\n\x01'), True),
+ ],
+ )
+
patch914575_from1 = """
1. Beautiful is beTTer than ugly.
_______________________________________________
Python-checkins mailing list -- [email protected]
To unsubscribe send an email to [email protected]
https://mail.python.org/mailman3//lists/python-checkins.python.org
Member address: [email protected]
