Bug in range() function for large values

[robertwb]

BPO	1533
Nosy	@loewis, @rhettinger, @mdickinson, @abalkin, @tiran, @akitada
Files	bad_range.py bltinmodule2.diff: modification of bltinmodule.diff to reject floats issue1533.diff issue1533_metd.diff issue1533-py3k-tests.diff: Additional tests for py3k issue1533-release26-maint.diff: 2.6 backport

^{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 2010-05-07.13:26:30.909>
created_at = <Date 2007-12-01.00:28:10.033>
labels = ['interpreter-core', 'type-bug', 'library']
title = 'Bug in range() function for large values'
updated_at = <Date 2010-05-07.13:26:30.908>
user = 'https://bugs.python.org/robertwb'

bugs.python.org fields:

activity = <Date 2010-05-07.13:26:30.908>
actor = 'mark.dickinson'
assignee = 'mark.dickinson'
closed = True
closed_date = <Date 2010-05-07.13:26:30.909>
closer = 'mark.dickinson'
components = ['Interpreter Core', 'Library (Lib)']
creation = <Date 2007-12-01.00:28:10.033>
creator = 'robertwb'
dependencies = []
files = ['8839', '17169', '17190', '17200', '17203', '17239']
hgrepos = []
issue_num = 1533
keywords = ['patch', '26backport']
message_count = 57.0
messages = ['58034', '58039', '58040', '62617', '62631', '62898', '62937', '62938', '62943', '62945', '62947', '62950', '62989', '76623', '76624', '76630', '77509', '104680', '104681', '104682', '104687', '104695', '104719', '104720', '104728', '104737', '104741', '104742', '104743', '104744', '104745', '104747', '104758', '104771', '104772', '104775', '104811', '104812', '104813', '104923', '104928', '104929', '104930', '104931', '104948', '104953', '104956', '104957', '104960', '104970', '105107', '105109', '105110', '105129', '105152', '105199', '105200']
nosy_count = 9.0
nosy_names = ['loewis', 'rhettinger', 'mark.dickinson', 'belopolsky', 'christian.heimes', 'josm', 'robertwb', 'zanella', 'akitada']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue1533'
versions = ['Python 2.6']

[robertwb]

Range accepts arguments coerce-able into ints via __int__, but rejects
arguments coerce-able into longs but to large to fit into an int.

The problem is in handle_range_longs in bltinmodule.c:1527-1541. If they
type is not an int or long, it should try to make it so before failing
(for consistency with smaller values at least).

Attached is a file that reproduces this bug.

[josm]

Is this a bug?
print range(MyInt(2**64), MyInt(2**64+10))
produced
TypeError: range() integer start argument expected, got instance.

print range(int(MyInt(2**64)), int(MyInt(2**64+10)))
should work.

[robertwb]

Yes, that is a workaround, but

range(MyInt(n), MyInt(n+10))

should work for any valid value of n, not just some of them.

[zanella]

FWIW, using xrange() it seems to give the proper error message:

Traceback (most recent call last):
  File "bad_range.py", line 12, in <module>
    print xrange(MyInt(2**64), MyInt(2**64+10))
OverflowError: long int too large to convert to int

[robertwb]

Yes, the error for xrange is more illustrative of the problem, but just
shows that xrange has this a too. Why should xrange be invalid for
non-word sized values (especially as range works)? Incidentally, just a
week ago I had to write my own iterator for a project because xrange
couldn't handle large values.

[zanella]

According to the documentation
(http://docs.python.org/dev/library/functions.html) "The arguments must
be plain integers", so I think the wrong thing here is to run the
object's __int__() under the range()'s hood. I think the right thing to
do would be to explicitly invoke int() on passing an non-int argument as
parameter.

[abalkin]

This is related to bpo-1540617 and bpo-1546078.

bpo-1540617 contains a simple patch that extend acceptable range of
argument to +/-2**63

bpo-1546078 contains a complete long integer support implementation and
was accepted in Py3k.

It looks like all three issues can be closed by either accepting or
rejecting bpo-1540617 patch for 2.6 and marking bpo-1546078 patch as
accepted for Py3k.

[tiran]

I'm -10 on the patch in bpo-1540617 ( +/-2**63).

Reason: It's a good thing that the range of "range" is limited since it
returns a list of integers. range(2**32) allocates (2**32)*16 bytes +
small overhead for ints plus the space for the list (probably
(2**32)sizeof(ptr) which is 4 or 8 bytes). So far the memory for the
ints is *never returned to the system. I'm working on the problem.

[abalkin]

Christian,

I was probably a bit sloppy using "range" instead of "xrange," but bpo-1540617 is limited to xrange only. Are you still -10 on extending
xrange on 64-bit platforms to +/- 2**63? If so, what is your position
on backporting py3k's unlimited range implementation?

[abalkin]

So far the memory for the ints is *never* returned
to the system. I'm working on the problem.

Christian,

Are you working on the memory problem or on this issue? I think I have a
solution to OP's problem, but don't want to duplicate your effort.

[tiran]

I'm working on the memory problem. See bpo-2039 and bpo-2013.

xrange is a totally different story. I'm +0 on changing xrange. Is
Python 3.0's range function compatible with xrange? If the answer is
yes, we may reuse the code for an unlimited xrange.

[abalkin]

Attached patch addresses OP's issue:

$ ./python.exe bad_range.py
[8, 9, 10, 11, 12, 13, 14, 15, 16, 17]
here
[18446744073709551616L, 18446744073709551617L, 18446744073709551618L, 
18446744073709551619L, 18446744073709551620L, 18446744073709551621L, 
18446744073709551622L, 18446744073709551623L, 18446744073709551624L, 
18446744073709551625L]
[18446744073709551616L, 18446744073709551617L, 18446744073709551618L, 
18446744073709551619L, 18446744073709551620L, 18446744073709551621L, 
18446744073709551622L, 18446744073709551623L, 18446744073709551624L, 
18446744073709551625L]

The only existing test that fails is range(1e100, 1e101, 1e101)
producing a TypeError. It will now produce

>>> range(1e100, 1e101, 1e101)
__main__:1: DeprecationWarning: integer argument expected, got float
[10000000000000000159028911097599180468360808563945281389781327557747838
772170381060813469985856815104L]

Note that range(1e100, 1e101) would still fail:
>>> range(1e100, 1e101)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: range() result has too many items

An alternative solution would be to disallow non-ints regardless of
their value, but that is more likely to break someone's code.

[robertwb]

Alexander Belopolsky's patch looks like the right fix for range() to me.

The xrange limits still hold, but that should probably be a separate
issue/ticket.

[akitada]

I'm just curious to know which is the right behavior.

# Python 3.0
Traceback (most recent call last):
  File "bad_range.py", line 7, in <module>
    print(range(MyInt(2**3), MyInt(2**3+10)))
TypeError: 'MyInt' object cannot be interpreted as an integer

# Python 2.7a0
[8, 9, 10, 11, 12, 13, 14, 15, 16, 17]
here
[18446744073709551616L, 18446744073709551617L, 18446744073709551618L,
18446744073709551619L, 18446744073709551620L, 18446744073709551621L,
18446744073709551622L, 18446744073709551623L, 18446744073709551624L,
18446744073709551625L]
Traceback (most recent call last):
  File "bad_range.py", line 11, in <module>
    print(range(MyInt(2**64), MyInt(2**64+10)))
TypeError: range() integer start argument expected, got instance.

[robertwb]

I think *both* behaviors are wrong, the 3.0 one is backwards
incompatible, and the 2.7 one is inconsistent (accepting MyInt if it's <
32 bits, rejecting it for > 64 bits).

For our particular use case, it is very annoying to not be able to use
non-ints. It goes against the principle duck typing by simply defining
the __int__ and __index__ methods.

[akitada]

Updating versions.

[loewis]

This change is out of scope for 2.5.3 (plus, the desired behavior still
seems to be debated)

[mdickinson]

As far as I can tell there's no bug in 3.x: the 3.x range happily accepts an instance of a class that defines __index__.

[mdickinson]

Currently, in trunk, I get:

>>> range(0.0, 11.0, 1.1)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: range() integer start argument expected, got float.

But with Alexander's patch on trunk, I get:

>>> range(0.0, 11.0, 1.1)
[0L, 1L, 2L, 3L, 4L, 5L, 6L, 7L, 8L, 9L, 10L]

I'm not sure whether this is intentional or not, but IIRC it was a very deliberate choice not to allow float arguments to range (especially when, as here, the arguments are simply being truncated). I don't think this is an acceptable change for 2.7 (still less for 2.6).

Any patch for this issue should not change the behaviour for small arguments.

IMO, the *right* solution is to convert arguments via __index__ when possible (as 3.x appears to already do). However, this would be a new feature. I suggest closing this as a 'won't fix'.

[mdickinson]

IIRC, it was a very deliberate choice not to allow float arguments to range

Ignore this bit. IDRC. It was a deliberate choice not to let something range(0.0, 1.0, 0.1) work to give [0.0, 0.1, ...], since the usual floating-point difficulties give uncertainty about the endpoint.

That float arguments were allowed (and silently truncated to integers) is merely unfortunate. :) And it's no longer permitted in 2.7; I wouldn't want to go back to permitting float arguments here.

I'll set this to pending; it should be closed unless someone comes up with a simple fix in the near future.

[AlexanderBelopolsky]

I agree that this issue should be closed with no further action, but for historical accuracy the resolution should be "out of date" rather than "won't fix". The original bug was about range() behavior when it get arguments that are not ints, but "coerce-able into ints via __int__". Since range() no longer accepts such arguments, the issue is moot and there is nothing to fix or not fix here.

As a pie in the sky idea, I always wanted a range function that would work on any arguments that support addition and ordering. For example range(date(2010,1,1), date(2010, 2, 1), timedelta(7)) to return all Fridays in January, 2010. However, since advent of generator functions, this became simply

def range(start, stop, step):
   while start < stop:
      yield start
      start += step

and thus unnecessary for stdlib.

[mdickinson]

Alexander: range *does* still accept such arguments (in 2.7); just not floats:

>>> from decimal import Decimal
>>> range(Decimal(20), Decimal(20))
[]
>>> range(Decimal('1e100'), Decimal('1e100'))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: range() integer start argument expected, got Decimal.

[mdickinson]

BTW, I've changed the various "nb_int should return int object" error messages in Objects/intobject.c to the more meaningful and accurate message: "__int__ method should return an integer", in r80695.

[abalkin]

Attached patch, bpo-1533.diff, simplifies reference acrobatics at the expense of extra local variables. For the first time the first compilation did not have reference counting errors!

[abalkin]

On Sun, May 2, 2010 at 4:37 AM, Mark Dickinson <report@bugs.python.org> wrote:
..

 - Please could you also add a test for small arguments for each test
  class?

Working on it ...

[abalkin]

• Please could you also add a test for small arguments for each test
  class?

Done.

[mdickinson]

Thanks for the fixes. The latest patch looks good to me.

Alexander, is it okay for me to commit this?

[AlexanderBelopolsky]

On May 4, 2010, at 7:27 AM, Mark Dickinson <report@bugs.python.org>
wrote:

Mark Dickinson <dickinsm@gmail.com> added the comment:

Thanks for the fixes. The latest patch looks good to me.

Alexander, is it okay for me to commit this?

Sure. Why do you have to ask?

[mdickinson]

Hi Alexander,

I took the liberty of messing with your patch slightly; I didn't want to ask you to make further changes since the patch was fine, and my messing was mostly just to satisfy my own fussiness (only the first two items were really necessary):

Minor updates:

• add Misc/NEWS entry
• remove trailing whitespace and fix spaces that should have been a tab
• added some extra tests to check all possible combinations of bad
  arguments, purely to check for refcounting problems
• initialize low to NULL, to match the Py_XDECREF(low) (could change
  that Py_XDECREF to Py_DECREF instead, but the code's more resistant
  to random refactorings this way --- see next item :)
• randomly refactor: regroup blocks for ease of reading
• don't do PyLong_FromLong(1) until it's needed ('zero' is different,
  since it's always used in the non-error case)
• [micro-optimization]: don't pass a known zero value to
  get_range_long_argument

Any objections or comments? Can I apply this version of the patch?

[AlexanderBelopolsky]

I see. Let me take a look.

BTW, I tried to use tabs for indentation in the patch, but emacs was
not always happy about it. Is there some c-mode setting that I don't
know about that would take care of that?

On May 4, 2010, at 8:34 AM, Mark Dickinson <report@bugs.python.org>
wrote:

Mark Dickinson <dickinsm@gmail.com> added the comment:

Hi Alexander,

I took the liberty of messing with your patch slightly; I didn't
want to ask you to make further changes since the patch was fine,
and my messing was mostly just to satisfy my own fussiness (only the
first two items were really necessary):

Minor updates:

• add Misc/NEWS entry
• remove trailing whitespace and fix spaces that should have been a
  tab
• added some extra tests to check all possible combinations of bad
  arguments, purely to check for refcounting problems
• initialize low to NULL, to match the Py_XDECREF(low) (could change
  that Py_XDECREF to Py_DECREF instead, but the code's more resistant
  to random refactorings this way --- see next item :)
• randomly refactor: regroup blocks for ease of reading
• don't do PyLong_FromLong(1) until it's needed ('zero' is different,
  since it's always used in the non-error case)
• [micro-optimization]: don't pass a known zero value to
  get_range_long_argument

Any objections or comments? Can I apply this version of the patch?

----------
Added file: http://bugs.python.org/file17200/issue1533_metd.diff

---

Python tracker <report@bugs.python.org>
<http://bugs.python.org/issue1533\>

---

[mdickinson]

Re emacs:

C-c . python

should set a python 2.x-friendly indentation mode.

There's also a python-new style floating around somewhere on the web (not part of emacs as standard), suitable for the 4-space indent style that's supposed to be used for new code.

[abalkin]

On Tue, May 4, 2010 at 8:34 AM, Mark Dickinson <report@bugs.python.org> wrote:
..

I took the liberty of messing with your patch slightly; I didn't want
to ask you to make further changes since the patch was fine, and my
messing was mostly just to satisfy my own fussiness (only the first
two items were really necessary):

Thank you for doing it. The patch is good to go, questions and comments below are just for my education.

Minor updates:

• add Misc/NEWS entry

What is the standard practice on this? I thought Misc/NEWS entry was similar to commit message and would be written by a committer. What are the guidelines for writing such entries? I see that some entries simply repeat the title of the issues while others got into greater details.

• remove trailing whitespace and fix spaces that should have been
  a tab

I've looked at my patch through cat -et and couldn't find any tab/space issues. I did notice one empty line with a single space that you removed. Do you use an automated checking tool for this? I just did grep " $". BTW, the current trunk version (r80752) of Python/bltinmodule.c has two lines with trailing white space:

$ cat -n Python/bltinmodule.c | grep " $" | cat -et
   641^I^I^IPyErr_SetString(PyExc_TypeError, $
  2966^I        $

• added some extra tests to check all possible combinations of bad
  arguments, purely to check for refcounting problems

With arguments processing segregated in a common function, I am not sure whether additional tests actually increase coverage. This brings a question: what is the recommended way to produce coverage statistics for C modules? regrtest.py --coverage seems to be for python modules only.

• initialize low to NULL, to match the Py_XDECREF(low) (could change
  that Py_XDECREF to Py_DECREF instead, but the code's more resistant
  to random refactorings this way --- see next item :)

Good catch. Wouldn't the same argument apply to ilow? Wouldn't static code checkers complain about redundant initialization?

• randomly refactor: regroup blocks for ease of reading

I actually disagree that your regrouping makes the code clearer. In my version, all idiosyncratic argument processing is done with borrowed references first followed by common processing in three similar blocks. This, however, is purely matter of taste. Note that I considered changing i* names to raw* names, but decided not to introduce more changes than necessary. In your grouping, however, the similarity of variable names is more of an issue. This said, I don't really have any problem with your choice.

• don't do PyLong_FromLong(1) until it's needed ('zero' is different,
  since it's always used in the non-error case)

Yes, I considered that. A further micro-optimization would be to initialize a static variable in module initialization and reuse it in get_len_of_range_longs as well. I decided to put it next to zero instead to simplify the logic.

• [micro-optimization]: don't pass a known zero value to
  get_range_long_argument

Is it really worth it? Default start is probably not that common in case of long arguments.

Any objections or comments? Can I apply this version of the patch?

The above are not objections. Please apply this version of the patch.

[mdickinson]

[Some of the Alexander's questions about procedures aren't really related to this issue; I've answered those offline. Here are the answers to the others.]

> - initialize low to NULL, to match the Py_XDECREF(low) (could change
> that Py_XDECREF to Py_DECREF instead, but the code's more resistant
> to random refactorings this way --- see next item :)

Good catch. Wouldn't the same argument apply to ilow? Wouldn't static code checkers complain about redundant initialization?

ilow doesn't need to be initialized because the PyArgs_ParseTuple is
guaranteed to either fail or initialize it, and I can't see that the
PyArgs_ParseTuple call is likely to change. But I admit that the lack
of initialization here also makes me uncomfortable, especially in
combination with the assert that's there. I might add an
initialization.

Do static code checkers really complain about redundant
initializations? If anything, it seems like good defensive
programming practice to initialize variables, even
unnecessarily---later refactoring might make those initializations
necessary.

> - randomly refactor: regroup blocks for ease of reading

I actually disagree that your regrouping makes the code clearer. In my version, all idiosyncratic argument processing is done with borrowed references first followed by common processing in three similar blocks. This, however, is purely matter of taste. Note that I considered changing i* names to raw* names, but decided not to introduce more changes than necessary. In your grouping, however, the similarity of variable names is more of an issue. This said, I don't really have any problem with your choice.

Okay, fair enough. I agree it's a matter of taste. I like the three
separate blocks, one for each argument, especially since the
refcounting semantics are clear: each block adds exactly one
reference. But each to his own. :)

> - don't do PyLong_FromLong(1) until it's needed ('zero' is different,
> since it's always used in the non-error case)

Yes, I considered that. A further micro-optimization would be to initialize a static variable in module initialization and reuse it in get_len_of_range_longs as well. I decided to put it next to zero instead to simplify the logic.

Hmm. Possibly. I have an unhealthy and probably irrational aversion
to non-constant static variables, even if the only time that the
variable is changed is at module initialization.

> - [micro-optimization]: don't pass a known zero value to
> get_range_long_argument

Is it really worth it? Default start is probably not that common in case of long arguments.

Yes, possibly not. :) Partly I made this change because the
assignment 'ilow = zero;' again raises a red flag for me, because it's
not accompanied by a 'Py_INCREF(zero);' as I'd expect it to be. I
realize that in this case it works out (because ilow is already a
borrowed reference, and we're replacing it with a borrowed reference
to zero), but it's sufficiently unusual that I have to think about it.
This is personal preference again, I guess.

[mdickinson]

Applied to trunk in r80758.

Do people want this to go into 2.6 as well? The patch would need to be modified to produce a warning for floats instead of giving a TypeError (and the tests would need to be modified to test for that warning).

[AlexanderBelopolsky]

On Tue, May 4, 2010 at 12:32 PM, Mark Dickinson <report@bugs.python.org> wrote:

Mark Dickinson <dickinsm@gmail.com> added the comment:

Applied to trunk in r80758.

Do people want this to go into 2.6 as well?

Also, should additional unit tests forward ported to 3.x? If so, let
me do it as an exercise in creating a ready to commit patch. :-)

[mdickinson]

+1 for forward-porting/adapting relevant tests to py3k.

[abalkin]

I am attaching a py3k patch that adds new tests. Since there are no end user visible changes, I don't believe a Misc/NEWS entry is needed. A commit message may read:

Issue bpo-1533: Tests only. Added tests for consistency in range function argument processing.

Note that the first chunk:

-        # Reject floats when it would require PyLongs to represent.
-        # (smaller floats still accepted, but deprecated)
+        # Reject floats.
+        self.assertRaises(TypeError, range, 1., 1., 1.)

is applicable to the trunk as well.

[mdickinson]

Perfect! Committed in r80836 (py3k); fixed that one test and comment in r80842 in trunk.

Alexander, do you want to tackle the 2.6 backport?

BTW, I think in most cases it's unnecessary to add Python 3.3 to the Versions field above, since there's no corresponding svn branch for 3.3. (But it's useful if there's a task that's specifically aimed at 3.3 and not earlier versions---e.g. if something's been deprecated in 3.2 and needs to be removed in 3.3.)

[mdickinson]

That should have been r80839, not r80842.

[abalkin]

Alexander, do you want to tackle the 2.6 backport?

I've never done a maintenance branch backport, but here is my attempt:

1. Checkout release26-maint
2. Apply 80757:80758 diff, fix rejected NEWS patch
3. Ignore 80838:80839 diff - small floats are accepted in 2.6 range.
4. Replace small float with large float in bad argument tests.
5. make; make test; make patchcheck

I could probably use svn merge instead of svn diff + patch. Did I miss anything important?

BTW, I've discovered "make patchcheck", does it check C files white space issues or only python files?

Mark,

I've sent you two emails off the tracker, but it looks like they did not make it through your spam filters.

[mdickinson]

I've never done a maintenance branch backport, but here is my attempt:
[...]

Yes, that sounds about right. But after all that, you'll still need to modify the patch somewhat, since the requirements are different for 2.6: floats should give a DeprecationWarning rather than a TypeError. I think that's a straightforward change for Python/bltinmodule.c. The trickier bit is coming up with tests that work properly---i.e., check that the appropriate warnings are produced, *and* that the the appropriate values are returned. Look into the 'catch_warnings' function in the warnings module; (there's also 'check_warnings' in test_support, but I think that doesn't exist in 2.6).

'make patchcheck' only checks Python files and ReST files, as far as I can tell.

[I got your off-tracker emails; will respond anon.]

[abalkin]

the requirements are different for 2.6: floats should give a
DeprecationWarning rather than a TypeError.

I thought about it, but the comment in test_builtin.py,

\# Reject floats when it would require PyLongs to represent.                                                                                                                                          
\# (smaller floats still accepted, but deprecated)  

convinced me that raising TypeError on large floats is a feature. I don't have a strong opinion on this issue, but I think a conservative approach is not to change current behavior in the maintenance branch unless it is clearly a bug.

I did add a test checking that "smaller floats still accepted, but deprecated."

[mdickinson]

Yes, okay---that makes some sense; I'm happy to leave floats as they are (i.e., DeprecationWarning for small floats; TypeError for larger floats) and just fix use of __int__ for non-floats.

I'll look at the patch.

[mdickinson]

The backport looks fine. Applied in r80917. Thanks, Alexander.