classification
Title: slice.indices raises OverflowError
Type: enhancement Stage: patch review
Components: Interpreter Core Versions: Python 3.4
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: mark.dickinson Nosy List: Paul.Upchurch, eric.araujo, hynek, mark.dickinson, ned.deily, python-dev, serhiy.storchaka
Priority: normal Keywords: patch

Created on 2012-05-12 22:51 by Paul.Upchurch, last changed 2012-11-17 19:23 by mark.dickinson. This issue is now closed.

Files
File name Uploaded Description Edit
issue14794.patch mark.dickinson, 2012-11-03 19:17 review
issue14794_v2.patch mark.dickinson, 2012-11-03 21:42 review
issue14794_v3.patch mark.dickinson, 2012-11-03 22:31 review
issue14794_v4.patch mark.dickinson, 2012-11-04 11:00 review
Messages (30)
msg160500 - (view) Author: Paul Upchurch (Paul.Upchurch) Date: 2012-05-12 22:51
To reproduce the error:

Python 3.2.2 (default, Sep  5 2011, 22:09:30) 
[GCC 4.6.1] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> slice(0,90000,None).indices(12600000000)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: cannot fit 'int' into an index-sized integer
>>> 

The correct behaviour is to return (0, 90000, 1).

>>> slice(0,90000,None).indices(600000000)
(0, 90000, 1)

This is related to http://bugs.python.org/issue1456470.
msg160501 - (view) Author: Hynek Schlawack (hynek) * (Python committer) Date: 2012-05-12 22:57
This seems to have been fixed as of 3.2.3 (as shipped with Ubuntu Precise):

Python 3.2.3 (default, Apr 12 2012, 19:08:59) 
[GCC 4.6.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> slice(0,90000,None).indices(12600000000)
(0, 90000, 1)

Current tip works fine too:

Python 3.3.0a3+ (default:b32baa5b7626+, May 10 2012, 14:56:20) 
[GCC 4.6.3] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> slice(0,90000,None).indices(12600000000)
(0, 90000, 1)


I'd close this bug unless I'm missing something?
msg160502 - (view) Author: Paul Upchurch (Paul.Upchurch) Date: 2012-05-12 23:13
Sorry. I didn't realize there was a 3.2.3 out. I'll close it as fixed.
msg160506 - (view) Author: Éric Araujo (eric.araujo) * (Python committer) Date: 2012-05-13 05:01
> This seems to have been fixed as of 3.2.3 (as shipped with Ubuntu Precise)

Just a note: you can’t really trust the behavior of Python shipped by Debian or derivative systems because doko (the Debian Python maintainer) backports changes to released versions, which means that Debian’s 3.2.3 may not always behave as python.org’s 3.2.3.
msg160531 - (view) Author: Paul Upchurch (Paul.Upchurch) Date: 2012-05-13 17:31
That's true; it doesn't work with today's downloads from python.org. The version I tested was win32 but I don't think that should matter. Python has always supported large numbers on 32-bit OSs.

My observations:

[1] Debian Wheezy, python3.2, 3.2.3~rc2-1: Fail
[2] Debian Wheezy, python2.7, 2.7.3~rc2-2.1: Fail
[3] python.org, python3.3, 3.3.0a3: Fail
[4] python.org, python3.2, 3.2.3: Fail

I'll compile 64-bit linux from source and try that.

[1] Python 3.2.3rc2 (default, Mar 21 2012, 06:59:51) [GCC 4.6.3] on linux2
[2] Python 2.7.3rc2 (default, Apr 22 2012, 22:35:38) [GCC 4.6.3] on linux2
[3] Python 3.3.0a3 (default, May  1 2012, 16:25:20) [MSC v.1500 32 bit (Intel)] on win32
[4] Python 3.2.3 (default, Apr 11 2012, 07:15:24) [MSC v.1500 32 bit (Intel)] on win32
msg160558 - (view) Author: Hynek Schlawack (hynek) * (Python committer) Date: 2012-05-13 19:37
I did a little compiling party with official releases and all permutations of Linux, OS X x 3.2.2, 3.2.3 worked. Both ran on 64bit (Linux in a VirtualBox).

Python 3.2.2 (default, May 13 2012, 21:24:38) 
[GCC 4.6.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> slice(0,90000,None).indices(12600000000)
(0, 90000, 1)

Python 3.2.2 (default, May 13 2012, 21:33:57) 
[GCC 4.2.1 (Based on Apple Inc. build 5658) (LLVM build 2336.1.00)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> slice(0,90000,None).indices(12600000000)
(0, 90000, 1)

Can we narrow it down to 32bit hosts/OS?
msg160583 - (view) Author: Paul Upchurch (Paul.Upchurch) Date: 2012-05-13 23:53
The pre-built 64-bit Windows binaries from python.org works.

Python 3.3.0a3 (default, May  1 2012, 16:46:00) [MSC v.1500 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> slice(0,90000,None).indices(12600000000)
(0, 90000, 1)

Python 3.2.3 (default, Apr 11 2012, 07:12:16) [MSC v.1500 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> slice(0,90000,None).indices(12600000000)
(0, 90000, 1)

I think this issue is settled. There are several possible actions for people that find this discussion through a web search.

1. Use Ubuntu 12.04 LTS
2. Compile a fresh copy of 3.2 or 3.3 from python.org.
3. Use a pre-built 3.2 or 3.3 64-bit Windows binary from python.org.
4. Wait for your Linux distribution to catch up.

Hynek, Éric: Thanks for your help.
msg160594 - (view) Author: Ned Deily (ned.deily) * (Python committer) Date: 2012-05-14 05:05
The problem you described is definitely still an issue with 32-bit builds.

$ /usr/local/bin/python3.3
Python 3.3.0a3 (v3.3.0a3:0b53b70a40a0, May  1 2012, 11:39:35) 
[GCC 4.2.1 (Apple Inc. build 5666) (dot 3)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys; sys.maxsize
9223372036854775807
>>> slice(0,90000,None).indices(12600000000)
(0, 90000, 1)
$ /usr/local/bin/python3.3-32
Python 3.3.0a3 (v3.3.0a3:0b53b70a40a0, May  1 2012, 11:39:35) 
[GCC 4.2.1 (Apple Inc. build 5666) (dot 3)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys; print(sys.maxsize)
2147483647
>>> slice(0,90000,None).indices(12600000000)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: cannot fit 'int' into an index-sized integer
msg174496 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-11-02 09:07
This should be an issue on 64-bit too.

slice(0,1,None).indices(sys.maxsize+1)
msg174544 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2012-11-02 17:27
For 2.7, I don't see any problem with raising OverflowError for a length that's > sys.maxsize, since it's hard to have sequences larger than that anyway.

For 3.x, I'd also see this behaviour as reasonable, and not a bug.  If it's raising OverflowError for lengths *smaller* than sys.maxsize, that's a bug.  Unless that's the case, I'd call this a feature request for 3.4, rather than a bug that needs fixing in all the maintenance branches.
msg174545 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2012-11-02 17:32
> If it's raising OverflowError for lengths *smaller* than sys.maxsize,
> that's a bug.

Ah, reading Ned's comment, it looks like that's exactly what it's doing.
msg174551 - (view) Author: Paul Upchurch (Paul.Upchurch) Date: 2012-11-02 18:23
For the concept of "reasonable", it should be noted that this behaviour will affect code that works with reasonably sized sequences despite the largeness of the parameter.

Consider an extremely large array. To work with such an array, one would typically break it into small segments. However, to simplify the code and reduce bugs it makes sense to use a consistent indexing method on each segment. The size of its parameter does not say anything about the size of a segment. Consider a class which implements virtual arrays.

def __getitem__(...):
  ...
  start,stop,step=slice.indices(start,stop,step).indices(12600000000)
  while True:
    if step>0 and start>=stop: break
    if step<0 and start<=stop: break
    p=pageid(start)
    make_page_resident(p)
    do work ...
    start=start+step

As you can see, slice.indices should not be limited to sys.maxsize. If Python can perform the arithmetic calculation sys.maxsize+1 then slice.indices(sys.maxsize+1) should also work. The usage of slice.indices is to ensure consistent behaviour of the slicing operator. Another workaround for this bug:

5. write your own implementation of slice.indices

I consider this a workaround. The correct way to handle the index parameter to __getitem__ and __setitem__ is to use slice.indices. That way, if the semantics of slicing changes in future versions of Python, your class will behave consistently. It seems to me that this is the main reason why slice.indices exists at all: to prevent inconsistent behaviour when people implement __getitem__ and __setitem__.
msg174552 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-11-02 18:27
I think the issue is than slice constructor accepts integer out of Py_ssize_t range. And more, it accepts any objects, not only integers or None.

>>> slice(3.4, 'a', {})
slice(3.4, 'a', {})

May be we should disallow creating of such doubtful slices and raise TypeError or OverflowError.
msg174557 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2012-11-02 18:42
Paul:  I think you make good arguments that this should be fixed for 3.4.  I do however think that for versions earlier than 3.4 this 'fix' would be bordering on a new feature;  it's also likely to require significant new code and tests, and so I'd be wary of introducing such a change in a maintenance release.  I'd propose to fix this for 3.4 only.
msg174558 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2012-11-02 18:49
I'll look at creating a patch for 3.4
msg174675 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2012-11-03 19:17
Here's a patch.
msg174678 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2012-11-03 19:28
I should note that this patch fixes/changes one other aspect of slice.indices:  namely that it used to accept a negative length, and return essentially meaningless results in that case:

    >>> slice(0, 10, 1).indices(-3)
    (-3, -3, 1)

With the patch, it now raises ValueError if given a negative length:

    >>> slice(0, 10, 1).indices(-3)
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    ValueError: length should not be negative
msg174702 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2012-11-03 21:42
Updated patch (only cosmetic fixes with respect to the first patch).  Thanks Ezio Melotti for comments on #python-dev.
msg174715 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2012-11-03 22:31
Updated for Serhiy's comments on Rietveld:

  - fix some refleaks in error cases
  - streamline the C code somewhat following Serhiy's suggestions.

Serhiy:  you made a comment on the slice_indices function in test_slice.py: "Can we use Python implementation for builtin object?".  I don't understand what you mean---can you elaborate?
msg174768 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-11-04 09:55
> I don't understand what you mean---can you elaborate?

The Python implementation of this method only 40 lines length, including blank lines, docstring and comments.  The C implementation requires over 160 lines and less clear.  Are there ways to use in Python interpreter core Python implementation for method of builtin class slice.  As already used C implementations for some Python-implemented classes.  May be add the file _builtins.py where Python version of some cumbersome methods will be implemented?  Then execute the followed code on interpreter initialization:

  from _builtins import slice_indices
  slice.indices = slice_indices
  del slice_indices

(or an analog in C).
msg174770 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-11-04 10:04
The patch looks good to me.  Now benchmarks and special casing for Py_ssize_t values needed.
msg174771 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2012-11-04 10:19
> Now benchmarks and special casing for Py_ssize_t values needed.

I thought about that, but I don't think it's worth it.  I did some quick timings, and as expected the new version of slice.indices is somewhat slower than the original.  But I think adding a special case for Py_ssize_t values would be premature optimization.
msg174774 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-11-04 10:23
Look at compute_slice_indices() in Objects/rangeobject.c.
msg174776 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2012-11-04 10:37
Hmm:  one more thing that needs to be fixed before this can be committed---the error messages for maltyped start, stop and step are less informative than they used to be.

Before the patch:

    >>> slice(0, 2.3, 4).indices(5)
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    TypeError: slice indices must be integers or None or have an __index__ method

After the patch:

    >>> slice(0, 2.3, 4).indices(5)
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    TypeError: 'float' object cannot be interpreted as an integer

I'll fix this.
msg174778 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2012-11-04 11:00
New patch that fixes the error message for badly typed slice arguments.

Also tweaks a couple of other details:

 - replace Py_GE with Py_GT, Py_LE with Py_LT in the out-of-range comparisons, as suggested by Serhiy;  this also makes it more closely match the Python reference implementation (since max(x, y) and min(x, y) both return x when x and y are equal)

 - make sure exception messages match between the Python reference implementation and the C version.

> Look at compute_slice_indices() in Objects/rangeobject.c.

Will do.  I'm not quite sure I even understand how that code's managing to work at the moment:  I see the Py_ssize_t case, but I don't see the fallback code for the case when things are too large for a Py_ssize_t.
msg174780 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-11-04 11:19
compute_slice_indices() and slice_indices() looks as partially duplicates.  I think the similar code should be merged and reused.
msg174784 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2012-11-04 11:31
Agreed.
msg175279 - (view) Author: Roundup Robot (python-dev) Date: 2012-11-10 14:52
New changeset 9214f8440c44 by Mark Dickinson in branch 'default':
Issue #14794: slice.indices no longer returns OverflowError for out-of-range start, stop, step or length.
http://hg.python.org/cpython/rev/9214f8440c44
msg175280 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2012-11-10 14:54
Committed the patch.  I'll open a new issue for the refactoring.  Many thanks to Serhiy Storchaka for the thorough reviews.

Now if only we could fix len, too... :-)

Python 3.4.0a0 (default:f02555353544, Nov  4 2012, 11:50:12) 
[GCC 4.2.1 (Apple Inc. build 5664)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> len(range(10**20))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: Python int too large to convert to C ssize_t
[68571 refs]
msg175798 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2012-11-17 19:23
For the refactoring, see issue #16451
History
Date User Action Args
2012-11-17 19:23:26mark.dickinsonsetmessages: + msg175798
2012-11-10 14:54:39mark.dickinsonsetstatus: open -> closed
resolution: fixed
messages: + msg175280
2012-11-10 14:52:26python-devsetnosy: + python-dev
messages: + msg175279
2012-11-04 11:31:14mark.dickinsonsetmessages: + msg174784
2012-11-04 11:19:53serhiy.storchakasetmessages: + msg174780
2012-11-04 11:00:46mark.dickinsonsetfiles: + issue14794_v4.patch

messages: + msg174778
2012-11-04 10:37:02mark.dickinsonsetmessages: + msg174776
2012-11-04 10:23:48serhiy.storchakasetmessages: + msg174774
2012-11-04 10:19:24mark.dickinsonsetmessages: + msg174771
2012-11-04 10:04:39serhiy.storchakasetmessages: + msg174770
2012-11-04 09:55:13serhiy.storchakasetmessages: + msg174768
2012-11-03 22:31:19mark.dickinsonsetfiles: + issue14794_v3.patch

messages: + msg174715
2012-11-03 21:42:08mark.dickinsonsetfiles: + issue14794_v2.patch

messages: + msg174702
2012-11-03 19:28:20mark.dickinsonsetmessages: + msg174678
2012-11-03 19:17:33mark.dickinsonsetfiles: + issue14794.patch
versions: - Python 2.7, Python 3.2, Python 3.3
messages: + msg174675

keywords: + patch
type: behavior -> enhancement
stage: needs patch -> patch review
2012-11-02 18:49:03mark.dickinsonsetassignee: mark.dickinson
messages: + msg174558
2012-11-02 18:42:36mark.dickinsonsetmessages: + msg174557
2012-11-02 18:27:51serhiy.storchakasetmessages: + msg174552
2012-11-02 18:23:37Paul.Upchurchsetmessages: + msg174551
2012-11-02 17:32:07mark.dickinsonsetmessages: + msg174545
2012-11-02 17:27:18mark.dickinsonsetmessages: + msg174544
2012-11-02 13:51:26mark.dickinsonsetnosy: + mark.dickinson
2012-11-02 09:07:48serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg174496
2012-11-02 07:04:30hyneksetversions: + Python 3.4
2012-05-14 05:05:58ned.deilysetstatus: closed -> open

versions: + Python 2.7, Python 3.3
nosy: + ned.deily

messages: + msg160594
resolution: out of date -> (no value)
stage: resolved -> needs patch
2012-05-13 23:53:39Paul.Upchurchsetmessages: + msg160583
2012-05-13 19:37:36hyneksetmessages: + msg160558
2012-05-13 17:31:32Paul.Upchurchsetmessages: + msg160531
2012-05-13 05:01:08eric.araujosetnosy: + eric.araujo
messages: + msg160506

resolution: fixed -> out of date
stage: resolved
2012-05-12 23:13:24Paul.Upchurchsetstatus: open -> closed
resolution: fixed
messages: + msg160502
2012-05-12 22:57:55hyneksetnosy: + hynek
messages: + msg160501
2012-05-12 22:51:37Paul.Upchurchcreate