classification
Title: Heapq.merge suppreses IndexError from user generator
Type: behavior Stage:
Components: Library (Lib) Versions: Python 3.3, Python 2.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: afn, python-dev, r.david.murray, rhettinger, stutzbach
Priority: normal Keywords: patch

Created on 2013-09-14 19:16 by afn, last changed 2013-09-15 05:30 by rhettinger. This issue is now closed.

Files
File name Uploaded Description Edit
unittest_patch.diff afn, 2013-09-14 21:14 add a unittest to check that indexerror is raised in heapq.merge review
Messages (7)
msg197726 - (view) Author: Artem Fokin (afn) Date: 2013-09-14 19:16
Suppose we have the following code:

    from heapq import merge

    def iterable():
        lst = range(10)
        for i in xrange(20):
            yield lst[i]
        
    it1, it2= iterable(), iterable()

    print list(merge(it1, it2)) # no IndexError
    #output is: [0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9]


The reason is that in heapq.merge http://hg.python.org/cpython/file/7c18b799841e/Lib/heapq.py#l372 try-catch clause for IndexError is too broad

    while 1:
        try:
            while 1:
                v, itnum, next = s = h[0]   # raises IndexError when h is empty
                yield v
                s[0] = next()               # raises StopIteration when exhausted, 
                _heapreplace(h, s)          # restore heap condition
        except _StopIteration:
            _heappop(h)                     # remove empty iterator
        except IndexError:
            return

s[0] = next() also may raise different kinds of exceptions including IndexError which will be silently suppressed. 
For example, this loop can be rewritten as

    while 1:
        try:
            while 1:
                try:
                    v, itnum, next = s = h[0]   # raises IndexError when h is empty
                except IndexError:
                    return
                yield v
                s[0] = next()               # raises StopIteration when exhausted, 
                _heapreplace(h, s)          # restore heap condition
        except _StopIteration:
            _heappop(h)                     # remove empty iterator
msg197728 - (view) Author: Artem Fokin (afn) Date: 2013-09-14 19:36
Oh, it seems that in current cpython branch this problem is fixed by checking condition _len(h) > 1:
http://hg.python.org/cpython/file/1dc925ee441a/Lib/heapq.py#l373
But is it possible to fix it for the previous branches?
msg197730 - (view) Author: R. David Murray (r.david.murray) * (Python committer) Date: 2013-09-14 20:41
It was checked in as an optimization, but if it fixes a bug I don't see why it couldn't be backported.  A unit test would be helpful, if you feel like writing one.
msg197731 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2013-09-14 20:47
This seems like a good reason for a backport.

Add a unittest and I'll take care of the rest.
msg197732 - (view) Author: Artem Fokin (afn) Date: 2013-09-14 21:14
Which branch should I add a unit-test to?
Here is a patch that adds a unit-test to the current one.
msg197744 - (view) Author: Roundup Robot (python-dev) Date: 2013-09-15 03:53
New changeset 0ff5bb61c6a1 by Raymond Hettinger in branch '3.3':
Issue #19018: The heapq.merge() function no longer suppresses IndexError
http://hg.python.org/cpython/rev/0ff5bb61c6a1
msg197747 - (view) Author: Roundup Robot (python-dev) Date: 2013-09-15 05:17
New changeset 56a3c0bc4634 by Raymond Hettinger in branch '2.7':
Issue #19018: The heapq.merge() function no longer suppresses IndexError
http://hg.python.org/cpython/rev/56a3c0bc4634
History
Date User Action Args
2013-09-15 05:30:36rhettingersetstatus: open -> closed
resolution: fixed
2013-09-15 05:17:50python-devsetmessages: + msg197747
2013-09-15 03:53:11python-devsetnosy: + python-dev
messages: + msg197744
2013-09-14 21:14:52afnsetfiles: + unittest_patch.diff
keywords: + patch
messages: + msg197732
2013-09-14 20:47:44rhettingersetassignee: rhettinger
messages: + msg197731
2013-09-14 20:41:19r.david.murraysetnosy: + r.david.murray

messages: + msg197730
versions: - Python 3.1, Python 3.2
2013-09-14 20:05:16pitrousetnosy: + rhettinger, stutzbach
2013-09-14 19:36:40afnsetmessages: + msg197728
2013-09-14 19:31:53afnsetversions: - Python 2.6, 3rd party, Python 3.4, Python 3.5
2013-09-14 19:16:38afncreate