From 38fbd799d1a45aa60454f7cb8b951e4f2b185e91 Mon Sep 17 00:00:00 2001
From: Antoine Pitrou <solipsis@pitrou.net>
Date: Wed, 16 May 2012 15:01:40 +0200
Subject: [PATCH] Issue #14829: Fix bisect issues under 64-bit Windows.

---
 Lib/test/test_bisect.py | 47 ++++++++++++++++++++++++++++++++++++++---
 Misc/NEWS               |  2 ++
 Modules/_bisectmodule.c |  2 +-
 3 files changed, 47 insertions(+), 4 deletions(-)

diff --git a/Lib/test/test_bisect.py b/Lib/test/test_bisect.py
index f96cf442dc..60777efb66 100644
--- a/Lib/test/test_bisect.py
+++ b/Lib/test/test_bisect.py
@@ -23,6 +23,28 @@ del sys.modules['bisect']
 import bisect as c_bisect
 
 
+class Range(object):
+    """A trivial xrange()-like object without any integer width limitations."""
+    def __init__(self, start, stop):
+        self.start = start
+        self.stop = stop
+        self.last_insert = None
+
+    def __len__(self):
+        return self.stop - self.start
+
+    def __getitem__(self, idx):
+        n = self.stop - self.start
+        if idx < 0:
+            idx += n
+        if idx >= n:
+            raise IndexError(idx)
+        return self.start + idx
+
+    def insert(self, idx, item):
+        self.last_insert = idx, item
+
+
 class TestBisect(unittest.TestCase):
     module = None
 
@@ -125,12 +147,31 @@ class TestBisect(unittest.TestCase):
     def test_large_range(self):
         # Issue 13496
         mod = self.module
+        n = sys.maxsize
         try:
-            data = xrange(sys.maxsize-1)
+            data = xrange(n-1)
         except OverflowError:
             self.skipTest("can't create a xrange() object of size `sys.maxsize`")
-        self.assertEqual(mod.bisect_left(data, sys.maxsize-3), sys.maxsize-3)
-        self.assertEqual(mod.bisect_right(data, sys.maxsize-3), sys.maxsize-2)
+        self.assertEqual(mod.bisect_left(data, n-3), n-3)
+        self.assertEqual(mod.bisect_right(data, n-3), n-2)
+        self.assertEqual(mod.bisect_left(data, n-3, n-10, n), n-3)
+        self.assertEqual(mod.bisect_right(data, n-3, n-10, n), n-2)
+
+    def test_large_pyrange(self):
+        # Same as above, but without C-imposed limits on range() parameters
+        mod = self.module
+        n = sys.maxsize
+        data = Range(0, n-1)
+        self.assertEqual(mod.bisect_left(data, n-3), n-3)
+        self.assertEqual(mod.bisect_right(data, n-3), n-2)
+        self.assertEqual(mod.bisect_left(data, n-3, n-10, n), n-3)
+        self.assertEqual(mod.bisect_right(data, n-3, n-10, n), n-2)
+        x = n - 100
+        mod.insort_left(data, x, x - 50, x + 50)
+        self.assertEqual(data.last_insert, (x, x))
+        x = n - 200
+        mod.insort_right(data, x, x - 50, x + 50)
+        self.assertEqual(data.last_insert, (x + 1, x))
 
     def test_random(self, n=25):
         from random import randrange
diff --git a/Misc/NEWS b/Misc/NEWS
index a1572cda77..c2be420880 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -60,6 +60,8 @@ Core and Builtins
 Library
 -------
 
+- Issue #14829: Fix bisect issues under 64-bit Windows.
+
 - Issue #14777: tkinter may return undecoded UTF-8 bytes as a string when
   accessing the Tk clipboard.  Modify clipboad_get() to first request type
   UTF8_STRING when no specific type is requested in an X11 windowing
diff --git a/Modules/_bisectmodule.c b/Modules/_bisectmodule.c
index 25e50715ac..b6652c0ecb 100644
--- a/Modules/_bisectmodule.c
+++ b/Modules/_bisectmodule.c
@@ -195,7 +195,7 @@ insort_left(PyObject *self, PyObject *args, PyObject *kw)
         if (PyList_Insert(list, index, item) < 0)
             return NULL;
     } else {
-        result = PyObject_CallMethod(list, "insert", "iO",
+        result = PyObject_CallMethod(list, "insert", "nO",
                                      index, item);
         if (result == NULL)
             return NULL;
-- 
2.50.0