You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
difflib.SequenceMatcher has slightly buggy and undocumented caching behavior #54194
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')
print(list(matcher.get_matching_blocks()))
# This should print the same thing, but it does not:print(list(matcher.get_matching_blocks()))
print(matcher.get_opcodes())
print(list(matcher.get_grouped_opcodes()))
# This should print the same thing as the previous get_opcodes()# list, but it does not:print(matcher.get_opcodes())
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.
Activity
marienz commentedon Sep 29, 2010
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:
christoph commentedon Oct 1, 2010
Here's a test case and a fix for get_matching_blocks() to return the same content on subsequent calls.
christoph commentedon Oct 1, 2010
BTW, here's the commit that broke the behavior in the first place: http://svn.python.org/view/python/trunk/Lib/difflib.py?r1=54230&r2=59907
marienz commentedon Oct 1, 2010
That fixes the first problem in python 2. It should do:
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.
ned-deily commentedon Oct 1, 2010
(+nosy Raymond as committer of r59907 and removing python2.6 since this is not a security issue)
BreamoreBoy commentedon Feb 24, 2015
I believe this has been fixed by changesets f02a563ad1bf and ed73c127421c in bpo-21635.
rhettinger commentedon Aug 24, 2019
This was fixed for Python 2.7 and Python 3.4 and later.