Skip to content

difflib.SequenceMatcher has slightly buggy and undocumented caching behavior #54194

Closed

Description

@marienz
mannequin
BPO 9985
Nosy @rhettinger, @marienz, @ned-deily
Files
  • get_matching_blocks.diff: Patch & test case fixing get_matching_blocks()
  • Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.

    Show more details

    GitHub fields:

    assignee = 'https://github.com/rhettinger'
    closed_at = <Date 2019-08-24.00:20:45.485>
    created_at = <Date 2010-09-29.14:32:17.922>
    labels = ['type-bug', 'library']
    title = 'difflib.SequenceMatcher has slightly buggy and undocumented caching behavior'
    updated_at = <Date 2019-08-24.00:20:45.481>
    user = 'https://github.com/marienz'

    bugs.python.org fields:

    activity = <Date 2019-08-24.00:20:45.481>
    actor = 'rhettinger'
    assignee = 'rhettinger'
    closed = True
    closed_date = <Date 2019-08-24.00:20:45.485>
    closer = 'rhettinger'
    components = ['Library (Lib)']
    creation = <Date 2010-09-29.14:32:17.922>
    creator = 'marienz'
    dependencies = []
    files = ['19084']
    hgrepos = []
    issue_num = 9985
    keywords = ['patch']
    message_count = 7.0
    messages = ['117612', '117800', '117801', '117819', '117830', '236538', '350339']
    nosy_count = 4.0
    nosy_names = ['rhettinger', 'marienz', 'ned.deily', 'christoph']
    pr_nums = []
    priority = 'normal'
    resolution = 'out of date'
    stage = 'resolved'
    status = 'closed'
    superseder = None
    type = 'behavior'
    url = 'https://bugs.python.org/issue9985'
    versions = ['Python 3.1', 'Python 2.7', 'Python 3.2']

    Activity

    1. marienz commented on Sep 29, 2010

      marienzmannequin
      MannequinAuthor

      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())
    2. added
      stdlibStandard Library Python modules in the Lib/ directory
      type-bugAn unexpected behavior, bug, or error
      on Sep 29, 2010
    3. christoph commented on Oct 1, 2010

      christophmannequin
      Mannequin

      Here's a test case and a fix for get_matching_blocks() to return the same content on subsequent calls.

    4. christoph commented on Oct 1, 2010

      christophmannequin
      Mannequin

      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

    5. marienz commented on Oct 1, 2010

      marienzmannequin
      MannequinAuthor

      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.

    6. ned-deily commented on Oct 1, 2010

      @ned-deily
      Member

      (+nosy Raymond as committer of r59907 and removing python2.6 since this is not a security issue)

    7. BreamoreBoy commented on Feb 24, 2015

      BreamoreBoymannequin
      Mannequin

      I believe this has been fixed by changesets f02a563ad1bf and ed73c127421c in bpo-21635.

    8. self-assigned this
      on Feb 26, 2015
    9. rhettinger commented on Aug 24, 2019

      @rhettinger
      Contributor

      This was fixed for Python 2.7 and Python 3.4 and later.

    10. transferred this issue fromon Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

    Metadata

    Metadata

    Assignees

    Labels

    stdlibStandard Library Python modules in the Lib/ directorytype-bugAn unexpected behavior, bug, or error

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions