slice.indices raises OverflowError

[PaulUpchurch]

BPO	14794
Nosy	@mdickinson, @ned-deily, @merwok, @hynek, @serhiy-storchaka
Files	issue14794.patch issue14794_v2.patch issue14794_v3.patch issue14794_v4.patch

^{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/mdickinson'
closed_at = <Date 2012-11-10.14:54:39.068>
created_at = <Date 2012-05-12.22:51:37.984>
labels = ['interpreter-core', 'type-feature']
title = 'slice.indices raises OverflowError'
updated_at = <Date 2012-11-17.19:23:26.519>
user = 'https://bugs.python.org/PaulUpchurch'

bugs.python.org fields:

activity = <Date 2012-11-17.19:23:26.519>
actor = 'mark.dickinson'
assignee = 'mark.dickinson'
closed = True
closed_date = <Date 2012-11-10.14:54:39.068>
closer = 'mark.dickinson'
components = ['Interpreter Core']
creation = <Date 2012-05-12.22:51:37.984>
creator = 'Paul.Upchurch'
dependencies = []
files = ['27862', '27869', '27871', '27878']
hgrepos = []
issue_num = 14794
keywords = ['patch']
message_count = 30.0
messages = ['160500', '160501', '160502', '160506', '160531', '160558', '160583', '160594', '174496', '174544', '174545', '174551', '174552', '174557', '174558', '174675', '174678', '174702', '174715', '174768', '174770', '174771', '174774', '174776', '174778', '174780', '174784', '175279', '175280', '175798']
nosy_count = 7.0
nosy_names = ['mark.dickinson', 'ned.deily', 'eric.araujo', 'python-dev', 'hynek', 'Paul.Upchurch', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'patch review'
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue14794'
versions = ['Python 3.4']

[PaulUpchurch]

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.

[hynek]

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?

[PaulUpchurch]

Sorry. I didn't realize there was a 3.2.3 out. I'll close it as fixed.

[merwok]

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.

[PaulUpchurch]

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

[hynek]

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?

[PaulUpchurch]

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.

[ned-deily]

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

[serhiy-storchaka]

This should be an issue on 64-bit too.

slice(0,1,None).indices(sys.maxsize+1)

[mdickinson]

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.

[mdickinson]

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.

[PaulUpchurch]

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__.

[serhiy-storchaka]

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.

[mdickinson]

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.

[mdickinson]

I'll look at creating a patch for 3.4

[mdickinson]

Here's a patch.

[mdickinson]

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

[mdickinson]

Updated patch (only cosmetic fixes with respect to the first patch). Thanks Ezio Melotti for comments on #python-dev.

[mdickinson]

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?

[serhiy-storchaka]

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).

[serhiy-storchaka]

The patch looks good to me. Now benchmarks and special casing for Py_ssize_t values needed.

[mdickinson]

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.

[serhiy-storchaka]

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

[mdickinson]

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.

[mdickinson]

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.

[serhiy-storchaka]

compute_slice_indices() and slice_indices() looks as partially duplicates. I think the similar code should be merged and reused.

[mdickinson]

Agreed.

[python-dev]

New changeset 9214f8440c44 by Mark Dickinson in branch 'default':
Issue bpo-14794: slice.indices no longer returns OverflowError for out-of-range start, stop, step or length.
http://hg.python.org/cpython/rev/9214f8440c44

[mdickinson]

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]

[mdickinson]

For the refactoring, see issue bpo-16451