This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Title: difflib.SequenceMatcher has slightly buggy and undocumented caching behavior
Type: behavior Stage: resolved
Components: Library (Lib) Versions: Python 3.1, Python 3.2, Python 2.7
Status: closed Resolution: out of date
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: christoph, marienz, ned.deily, rhettinger
Priority: normal Keywords: patch

Created on 2010-09-29 14:32 by marienz, last changed 2022-04-11 14:57 by admin. This issue is now closed.

File name Uploaded Description Edit
get_matching_blocks.diff christoph, 2010-10-01 14:06 Patch & test case fixing get_matching_blocks() review
Messages (7)
msg117612 - (view) Author: Marien Zwart (marienz) * Date: 2010-09-29 14:32
SequenceMatcher caches the result of get_matching_blocks and get_opcodes. There are some problems with this:

What get_matching_blocks caches is a list of tuples. The first call does not return that list: it returns map(Match._make, self.matching_blocks) (converting the tuples to namedtuples). Subsequent calls just return self.matching_blocks directly. Especially in python 3 and up this is weird, since the first call returns a map object while later calls return a list.

This caching behavior is not documented, so calling code may mutate the returned list. One example of calling code is difflib itself: get_grouped_opcodes mutates the result of get_opcodes (a cached list). I am not sure if the right fix is to have get_grouped_opcodes copy before it mutates or to have get_opcodes return a copy.

Snippet demonstrating both bugs:

matcher = difflib.SequenceMatcher(a='aaaaaaaabc', b='aaaaaaaadc')
# This should print the same thing, but it does not:

# This should print the same thing as the previous get_opcodes()
# list, but it does not:
msg117800 - (view) Author: Christoph Burgmer (christoph) Date: 2010-10-01 14:06
Here's a test case and a fix for get_matching_blocks() to return the same content on subsequent calls.
msg117801 - (view) Author: Christoph Burgmer (christoph) Date: 2010-10-01 14:07
BTW, here's the commit that broke the behavior in the first place:
msg117819 - (view) Author: Marien Zwart (marienz) * Date: 2010-10-01 17:41
That fixes the first problem in python 2. It should do:

self.matching_blocks = [Match._make(t) for t in non_adjacent]

in python 3 though, or it will return an already-exhausted map object if it is called again.

This leaves the problem of other code mutating the cached list (not realizing it is cached). I think it would make sense for these functions to just return a shallow copy of their cached list, but I have not thought that through much.
msg117830 - (view) Author: Ned Deily (ned.deily) * (Python committer) Date: 2010-10-01 20:09
(+nosy Raymond as committer of r59907 and removing python2.6 since this is not a security issue)
msg236538 - (view) Author: Mark Lawrence (BreamoreBoy) * Date: 2015-02-24 19:59
I believe this has been fixed by changesets f02a563ad1bf and ed73c127421c in #21635.
msg350339 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2019-08-24 00:20
This was fixed for Python 2.7 and Python 3.4 and later.
Date User Action Args
2022-04-11 14:57:07adminsetgithub: 54194
2019-08-24 00:20:45rhettingersetstatus: open -> closed
resolution: out of date
messages: + msg350339

stage: needs patch -> resolved
2019-03-15 22:42:57BreamoreBoysetnosy: - BreamoreBoy
2015-02-26 08:20:06rhettingersetassignee: rhettinger
2015-02-24 20:00:00BreamoreBoysetnosy: + BreamoreBoy
messages: + msg236538
2010-10-01 20:09:30ned.deilysetversions: - Python 2.6
nosy: + rhettinger, ned.deily

messages: + msg117830

stage: needs patch
2010-10-01 17:41:26marienzsetmessages: + msg117819
2010-10-01 14:07:44christophsetmessages: + msg117801
2010-10-01 14:06:41christophsetfiles: + get_matching_blocks.diff

nosy: + christoph
messages: + msg117800

keywords: + patch
2010-09-29 14:32:17marienzcreate