[issue13496] bisect module: Overflow at index computation

Changes by Mark Dickinson : -- resolution: -> fixed status: open -> closed ___ Python tracker ___ ___ Python-bugs-list mailing list U

[issue13496] bisect module: Overflow at index computation

Roundup Robot added the comment: New changeset 35a3a7e0d66d by Mark Dickinson in branch '3.2': Issue 13496: Fix bisect.bisect overflow bug for large collections. http://hg.python.org/cpython/rev/35a3a7e0d66d New changeset 1a9252280f07 by Mark Dickinson in branch 'default': Issue #13496: Merge f

[issue13496] bisect module: Overflow at index computation

Benjamin Peterson added the comment: LGTM -- nosy: +benjamin.peterson ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubs

[issue13496] bisect module: Overflow at index computation

Raymond Hettinger added the comment: Thanks for the updated patch. -- ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubs

[issue13496] bisect module: Overflow at index computation

Mark Dickinson added the comment: Updated patch, with comment. -- Added file: http://bugs.python.org/file24774/issue13496_v2.patch ___ Python tracker ___ ___

[issue13496] bisect module: Overflow at index computation

Antoine Pitrou added the comment: Perhaps adding a comment before those two lines would make the reason for the cast clearer. -- ___ Python tracker ___

[issue13496] bisect module: Overflow at index computation

Mark Dickinson added the comment: > Does it work with http://bugs.python.org/msg148567, in a 32 bits python? Yes. -- ___ Python tracker ___

[issue13496] bisect module: Overflow at index computation

Mark Dickinson added the comment: > I think the patch is *NOT* correct. Can you elaborate? It works fine for that example on a 64-bit build; not sure why 32-bit would be any different. The idea is just that the single cast forces the addition to be done as an addition of integers of type s

[issue13496] bisect module: Overflow at index computation

Jesús Cea Avión added the comment: I think the patch is *NOT* correct. Does it work with http://bugs.python.org/msg148567, in a 32 bits python? -- ___ Python tracker ___ __

[issue13496] bisect module: Overflow at index computation

Changes by Mark Dickinson : -- stage: -> patch review ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://m

[issue13496] bisect module: Overflow at index computation

Mark Dickinson added the comment: Here's a patch. -- keywords: +patch Added file: http://bugs.python.org/file24346/issue13496.patch ___ Python tracker ___ __

[issue13496] bisect module: Overflow at index computation

akira <4kir4...@gmail.com> added the comment: Related bug in Java: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html Do not consider any change as trivial: http://www.solipsys.co.uk/new/BinarySearchReconsidered.html (the author ran "binary search" coding cha

[issue13496] bisect module: Overflow at index computation

Changes by Jesús Cea Avión : -- nosy: +jcea ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.

[issue13496] bisect module: Overflow at index computation

Raymond Hettinger added the comment: The fix is trivial. I'll do it soonish. -- priority: low -> normal ___ Python tracker ___ ___ P

[issue13496] bisect module: Overflow at index computation

Amaury Forgeot d'Arc added the comment: [x]range is enough to trigger the bug:: bisect.bisect(range(sys.maxsize), sys.maxsize-3) -- nosy: +amaury.forgeotdarc ___ Python tracker _

[issue13496] bisect module: Overflow at index computation

Antoine Pitrou added the comment: Very good point, Mark. -- nosy: +pitrou ___ Python tracker ___ ___ Python-bugs-list mailing list Un

[issue13496] bisect module: Overflow at index computation

Mark Dickinson added the comment: Given that we typically need at least 4 bytes just for the PyObject * pointer for each item in a list, I guess real lists are safe. But how about list-like objects, implementing __len__ and __getitem__? The following appears to run forever on my machine:

[issue13496] bisect module: Overflow at index computation

Daniel Sturm added the comment: TBH I saw this more as an opportunity to get used to the whole system, how to create a patch, etc. :) Should've made it clearer at the start that this is unlikely to ever be a problem, sorry (didn't see a way to set priority to low myself). If my math isn't c

[issue13496] bisect module: Overflow at index computation

Tim Peters added the comment: FWIW, I doubt there's a real issue here. Objects in Python consume a lot more than a byte or two of memory, so the index range of a Python list is generally a lot less than ssize_t allows for. In other words, quantify "large" in "large arrays". How large can a

[issue13496] bisect module: Overflow at index computation

Raymond Hettinger added the comment: This looks like a reasonable suggestion. -- assignee: -> rhettinger priority: normal -> low ___ Python tracker ___

[issue13496] bisect module: Overflow at index computation

Changes by Antoine Pitrou : -- nosy: +mark.dickinson, rhettinger versions: +Python 2.7, Python 3.2, Python 3.3 -Python 3.4 ___ Python tracker ___

[issue13496] bisect module: Overflow at index computation

New submission from Daniel Sturm : The mid index computation in _bisectmodule.c in both internal_bisect_right and internal_bisect_left is done with: mid = (lo + hi) / 2; // all three variables Py_ssize_t which is susceptible to overflows for large arrays, which would lead to undefined behavi