Mailman 3 May 2014 - Python-checkins

cpython (merge 3.4 -> default): Test correct getXXX methods in Tkinter bigmem tests.
by serhiy.storchaka May 30, 2014

May 30, 2014

http://hg.python.org/cpython/rev/71c492bfe002 changeset: 90908:71c492bfe002 parent: 90905:5b80af12ccb7 parent: 90907:8077fc82d54e user: Serhiy Storchaka <storchaka(a)gmail.com> date: Fri May 30 15:55:12 2014 +0300 summary: Test correct getXXX methods in Tkinter bigmem tests. Tk.getint is just int, true Tk wrapper is available as Tk.tk.getint. files: Lib/test/test_tcl.py | 6 +++--- 1 files changed, 3 insertions(+), 3 deletions(-) diff --git a/Lib/test/test_tcl.py b/Lib/test/test_tcl.py --- a/Lib/test/test_tcl.py +++ b/Lib/test/test_tcl.py @@ -574,9 +574,9 @@ @support.bigmemtest(size=INT_MAX + 1, memuse=9, dry_run=False) def test_huge_string_builtins(self, size): value = '1' + ' ' * size - self.assertRaises(OverflowError, self.interp.getint, value) - self.assertRaises(OverflowError, self.interp.getdouble, value) - self.assertRaises(OverflowError, self.interp.getboolean, value) + self.assertRaises(OverflowError, self.interp.tk.getint, value) + self.assertRaises(OverflowError, self.interp.tk.getdouble, value) + self.assertRaises(OverflowError, self.interp.tk.getboolean, value) self.assertRaises(OverflowError, self.interp.eval, value) self.assertRaises(OverflowError, self.interp.evalfile, value) self.assertRaises(OverflowError, self.interp.record, value) -- Repository URL: http://hg.python.org/cpython

1 0

cpython (3.4): Test correct getXXX methods in Tkinter bigmem tests.
by serhiy.storchaka May 30, 2014

May 30, 2014

http://hg.python.org/cpython/rev/8077fc82d54e changeset: 90907:8077fc82d54e branch: 3.4 parent: 90904:a90cddfd9e47 user: Serhiy Storchaka <storchaka(a)gmail.com> date: Fri May 30 15:54:35 2014 +0300 summary: Test correct getXXX methods in Tkinter bigmem tests. Tk.getint is just int, true Tk wrapper is available as Tk.tk.getint. files: Lib/test/test_tcl.py | 6 +++--- 1 files changed, 3 insertions(+), 3 deletions(-) diff --git a/Lib/test/test_tcl.py b/Lib/test/test_tcl.py --- a/Lib/test/test_tcl.py +++ b/Lib/test/test_tcl.py @@ -566,9 +566,9 @@ @support.bigmemtest(size=INT_MAX + 1, memuse=9, dry_run=False) def test_huge_string_builtins(self, size): value = '1' + ' ' * size - self.assertRaises(OverflowError, self.interp.getint, value) - self.assertRaises(OverflowError, self.interp.getdouble, value) - self.assertRaises(OverflowError, self.interp.getboolean, value) + self.assertRaises(OverflowError, self.interp.tk.getint, value) + self.assertRaises(OverflowError, self.interp.tk.getdouble, value) + self.assertRaises(OverflowError, self.interp.tk.getboolean, value) self.assertRaises(OverflowError, self.interp.eval, value) self.assertRaises(OverflowError, self.interp.evalfile, value) self.assertRaises(OverflowError, self.interp.record, value) -- Repository URL: http://hg.python.org/cpython

1 0

cpython (2.7): Fixed possible integer overflow in getint, getdouble and getboolean too (issue
by serhiy.storchaka May 30, 2014

May 30, 2014

http://hg.python.org/cpython/rev/8c96af2fba28 changeset: 90906:8c96af2fba28 branch: 2.7 parent: 90903:59468bd68789 user: Serhiy Storchaka <storchaka(a)gmail.com> date: Fri May 30 14:28:21 2014 +0300 summary: Fixed possible integer overflow in getint, getdouble and getboolean too (issue #21552). files: Modules/_tkinter.c | 3 +++ 1 files changed, 3 insertions(+), 0 deletions(-) diff --git a/Modules/_tkinter.c b/Modules/_tkinter.c --- a/Modules/_tkinter.c +++ b/Modules/_tkinter.c @@ -1894,6 +1894,7 @@ } if (!PyArg_ParseTuple(args, "s:getint", &s)) return NULL; + CHECK_STRING_LENGTH(s); if (Tcl_GetInt(Tkapp_Interp(self), s, &v) == TCL_ERROR) return Tkinter_Error(self); return Py_BuildValue("i", v); @@ -1914,6 +1915,7 @@ } if (!PyArg_ParseTuple(args, "s:getdouble", &s)) return NULL; + CHECK_STRING_LENGTH(s); if (Tcl_GetDouble(Tkapp_Interp(self), s, &v) == TCL_ERROR) return Tkinter_Error(self); return Py_BuildValue("d", v); @@ -1934,6 +1936,7 @@ } if (!PyArg_ParseTuple(args, "s:getboolean", &s)) return NULL; + CHECK_STRING_LENGTH(s); if (Tcl_GetBoolean(Tkapp_Interp(self), s, &v) == TCL_ERROR) return Tkinter_Error(self); return PyBool_FromLong(v); -- Repository URL: http://hg.python.org/cpython

1 0

cpython (merge 3.4 -> default): Issue #21552: Fixed possible integer overflow of too long string lengths in
by serhiy.storchaka May 30, 2014

May 30, 2014

http://hg.python.org/cpython/rev/5b80af12ccb7 changeset: 90905:5b80af12ccb7 parent: 90902:33c308ddfb14 parent: 90904:a90cddfd9e47 user: Serhiy Storchaka <storchaka(a)gmail.com> date: Fri May 30 14:25:22 2014 +0300 summary: Issue #21552: Fixed possible integer overflow of too long string lengths in the tkinter module on 64-bit platforms. files: Lib/test/test_tcl.py | 27 +++++++++++++++++++++++- Misc/NEWS | 3 ++ Modules/_tkinter.c | 36 +++++++++++++++++++++++++++++++- 3 files changed, 64 insertions(+), 2 deletions(-) diff --git a/Lib/test/test_tcl.py b/Lib/test/test_tcl.py --- a/Lib/test/test_tcl.py +++ b/Lib/test/test_tcl.py @@ -565,10 +565,35 @@ @support.cpython_only @unittest.skipUnless(INT_MAX < PY_SSIZE_T_MAX, "needs UINT_MAX < SIZE_MAX") @support.bigmemtest(size=INT_MAX + 1, memuse=5, dry_run=False) - def test_huge_string(self, size): + def test_huge_string_call(self, size): value = ' ' * size self.assertRaises(OverflowError, self.interp.call, 'set', '_', value) + @support.cpython_only + @unittest.skipUnless(INT_MAX < PY_SSIZE_T_MAX, "needs UINT_MAX < SIZE_MAX") + @support.bigmemtest(size=INT_MAX + 1, memuse=9, dry_run=False) + def test_huge_string_builtins(self, size): + value = '1' + ' ' * size + self.assertRaises(OverflowError, self.interp.getint, value) + self.assertRaises(OverflowError, self.interp.getdouble, value) + self.assertRaises(OverflowError, self.interp.getboolean, value) + self.assertRaises(OverflowError, self.interp.eval, value) + self.assertRaises(OverflowError, self.interp.evalfile, value) + self.assertRaises(OverflowError, self.interp.record, value) + self.assertRaises(OverflowError, self.interp.adderrorinfo, value) + self.assertRaises(OverflowError, self.interp.setvar, value, 'x', 'a') + self.assertRaises(OverflowError, self.interp.setvar, 'x', value, 'a') + self.assertRaises(OverflowError, self.interp.unsetvar, value) + self.assertRaises(OverflowError, self.interp.unsetvar, 'x', value) + self.assertRaises(OverflowError, self.interp.adderrorinfo, value) + self.assertRaises(OverflowError, self.interp.exprstring, value) + self.assertRaises(OverflowError, self.interp.exprlong, value) + self.assertRaises(OverflowError, self.interp.exprboolean, value) + self.assertRaises(OverflowError, self.interp.splitlist, value) + self.assertRaises(OverflowError, self.interp.split, value) + self.assertRaises(OverflowError, self.interp.createcommand, value, max) + self.assertRaises(OverflowError, self.interp.deletecommand, value) + def setUpModule(): if support.verbose: diff --git a/Misc/NEWS b/Misc/NEWS --- a/Misc/NEWS +++ b/Misc/NEWS @@ -89,6 +89,9 @@ Library ------- +- Issue #21552: Fixed possible integer overflow of too long string lengths in + the tkinter module on 64-bit platforms. + - Issue #14315: The zipfile module now ignores extra fields in the central directory that are too short to be parsed instead of letting a struct.unpack error bubble up as this "bad data" appears in many real world zip files in diff --git a/Modules/_tkinter.c b/Modules/_tkinter.c --- a/Modules/_tkinter.c +++ b/Modules/_tkinter.c @@ -881,6 +881,16 @@ }; +#if PY_SIZE_MAX > INT_MAX +#define CHECK_STRING_LENGTH(s) do { \ + if (s != NULL && strlen(s) >= INT_MAX) { \ + PyErr_SetString(PyExc_OverflowError, "string is too long"); \ + return NULL; \ + } } while(0) +#else +#define CHECK_STRING_LENGTH(s) +#endif + static Tcl_Obj* AsObj(PyObject *value) { @@ -1303,6 +1313,7 @@ if (!PyArg_ParseTuple(args, "s:eval", &script)) return NULL; + CHECK_STRING_LENGTH(script); CHECK_TCL_APPARTMENT; ENTER_TCL @@ -1326,6 +1337,7 @@ if (!PyArg_ParseTuple(args, "s:evalfile", &fileName)) return NULL; + CHECK_STRING_LENGTH(fileName); CHECK_TCL_APPARTMENT; ENTER_TCL @@ -1346,9 +1358,10 @@ PyObject *res = NULL; int err; - if (!PyArg_ParseTuple(args, "s", &script)) + if (!PyArg_ParseTuple(args, "s:record", &script)) return NULL; + CHECK_STRING_LENGTH(script); CHECK_TCL_APPARTMENT; ENTER_TCL @@ -1369,6 +1382,7 @@ if (!PyArg_ParseTuple(args, "s:adderrorinfo", &msg)) return NULL; + CHECK_STRING_LENGTH(msg); CHECK_TCL_APPARTMENT; ENTER_TCL @@ -1552,6 +1566,8 @@ if (!PyArg_ParseTuple(args, "ssO:setvar", &name1, &name2, &newValue)) return NULL; + CHECK_STRING_LENGTH(name1); + CHECK_STRING_LENGTH(name2); /* XXX must hold tcl lock already??? */ newval = AsObj(newValue); ENTER_TCL @@ -1597,6 +1613,7 @@ varname_converter, &name1, &name2)) return NULL; + CHECK_STRING_LENGTH(name2); ENTER_TCL tres = Tcl_GetVar2Ex(Tkapp_Interp(self), name1, name2, flags); ENTER_OVERLAP @@ -1639,6 +1656,8 @@ if (!PyArg_ParseTuple(args, "s|s:unsetvar", &name1, &name2)) return NULL; + CHECK_STRING_LENGTH(name1); + CHECK_STRING_LENGTH(name2); ENTER_TCL code = Tcl_UnsetVar2(Tkapp_Interp(self), name1, name2, flags); ENTER_OVERLAP @@ -1684,6 +1703,7 @@ } if (!PyArg_ParseTuple(args, "s:getint", &s)) return NULL; + CHECK_STRING_LENGTH(s); if (Tcl_GetInt(Tkapp_Interp(self), s, &v) == TCL_ERROR) return Tkinter_Error(self); return Py_BuildValue("i", v); @@ -1704,6 +1724,7 @@ } if (!PyArg_ParseTuple(args, "s:getdouble", &s)) return NULL; + CHECK_STRING_LENGTH(s); if (Tcl_GetDouble(Tkapp_Interp(self), s, &v) == TCL_ERROR) return Tkinter_Error(self); return Py_BuildValue("d", v); @@ -1724,6 +1745,7 @@ } if (!PyArg_ParseTuple(args, "s:getboolean", &s)) return NULL; + CHECK_STRING_LENGTH(s); if (Tcl_GetBoolean(Tkapp_Interp(self), s, &v) == TCL_ERROR) return Tkinter_Error(self); return PyBool_FromLong(v); @@ -1739,6 +1761,7 @@ if (!PyArg_ParseTuple(args, "s:exprstring", &s)) return NULL; + CHECK_STRING_LENGTH(s); CHECK_TCL_APPARTMENT; ENTER_TCL @@ -1763,6 +1786,7 @@ if (!PyArg_ParseTuple(args, "s:exprlong", &s)) return NULL; + CHECK_STRING_LENGTH(s); CHECK_TCL_APPARTMENT; ENTER_TCL @@ -1786,6 +1810,7 @@ if (!PyArg_ParseTuple(args, "s:exprdouble", &s)) return NULL; + CHECK_STRING_LENGTH(s); CHECK_TCL_APPARTMENT; PyFPE_START_PROTECT("Tkapp_ExprDouble", return 0) ENTER_TCL @@ -1810,6 +1835,7 @@ if (!PyArg_ParseTuple(args, "s:exprboolean", &s)) return NULL; + CHECK_STRING_LENGTH(s); CHECK_TCL_APPARTMENT; ENTER_TCL retval = Tcl_ExprBoolean(Tkapp_Interp(self), s, &v); @@ -1865,6 +1891,7 @@ if (!PyArg_ParseTuple(args, "et:splitlist", "utf-8", &list)) return NULL; + CHECK_STRING_LENGTH(list); if (Tcl_SplitList(Tkapp_Interp(self), list, &argc, &argv) == TCL_ERROR) { PyMem_Free(list); @@ -1926,6 +1953,7 @@ if (!PyArg_ParseTuple(args, "et:split", "utf-8", &list)) return NULL; + CHECK_STRING_LENGTH(list); v = Split(list); PyMem_Free(list); return v; @@ -2057,6 +2085,7 @@ if (!PyArg_ParseTuple(args, "sO:createcommand", &cmdName, &func)) return NULL; + CHECK_STRING_LENGTH(cmdName); if (!PyCallable_Check(func)) { PyErr_SetString(PyExc_TypeError, "command not callable"); return NULL; @@ -2118,6 +2147,7 @@ if (!PyArg_ParseTuple(args, "s:deletecommand", &cmdName)) return NULL; + CHECK_STRING_LENGTH(cmdName); #ifdef WITH_THREAD if (self->threaded && self->thread_id != Tcl_GetCurrentThread()) { @@ -2789,6 +2819,10 @@ &interactive, &wantobjects, &wantTk, &sync, &use)) return NULL; + CHECK_STRING_LENGTH(screenName); + CHECK_STRING_LENGTH(baseName); + CHECK_STRING_LENGTH(className); + CHECK_STRING_LENGTH(use); return (PyObject *) Tkapp_New(screenName, className, interactive, wantobjects, wantTk, -- Repository URL: http://hg.python.org/cpython

1 0

cpython (3.4): Issue #21552: Fixed possible integer overflow of too long string lengths in
by serhiy.storchaka May 30, 2014

May 30, 2014

http://hg.python.org/cpython/rev/a90cddfd9e47 changeset: 90904:a90cddfd9e47 branch: 3.4 parent: 90901:73ba4f1dac53 user: Serhiy Storchaka <storchaka(a)gmail.com> date: Fri May 30 14:24:03 2014 +0300 summary: Issue #21552: Fixed possible integer overflow of too long string lengths in the tkinter module on 64-bit platforms. files: Lib/test/test_tcl.py | 27 +++++++++++++++++++++++- Misc/NEWS | 3 ++ Modules/_tkinter.c | 36 +++++++++++++++++++++++++++++++- 3 files changed, 64 insertions(+), 2 deletions(-) diff --git a/Lib/test/test_tcl.py b/Lib/test/test_tcl.py --- a/Lib/test/test_tcl.py +++ b/Lib/test/test_tcl.py @@ -557,10 +557,35 @@ @support.cpython_only @unittest.skipUnless(INT_MAX < PY_SSIZE_T_MAX, "needs UINT_MAX < SIZE_MAX") @support.bigmemtest(size=INT_MAX + 1, memuse=5, dry_run=False) - def test_huge_string(self, size): + def test_huge_string_call(self, size): value = ' ' * size self.assertRaises(OverflowError, self.interp.call, 'set', '_', value) + @support.cpython_only + @unittest.skipUnless(INT_MAX < PY_SSIZE_T_MAX, "needs UINT_MAX < SIZE_MAX") + @support.bigmemtest(size=INT_MAX + 1, memuse=9, dry_run=False) + def test_huge_string_builtins(self, size): + value = '1' + ' ' * size + self.assertRaises(OverflowError, self.interp.getint, value) + self.assertRaises(OverflowError, self.interp.getdouble, value) + self.assertRaises(OverflowError, self.interp.getboolean, value) + self.assertRaises(OverflowError, self.interp.eval, value) + self.assertRaises(OverflowError, self.interp.evalfile, value) + self.assertRaises(OverflowError, self.interp.record, value) + self.assertRaises(OverflowError, self.interp.adderrorinfo, value) + self.assertRaises(OverflowError, self.interp.setvar, value, 'x', 'a') + self.assertRaises(OverflowError, self.interp.setvar, 'x', value, 'a') + self.assertRaises(OverflowError, self.interp.unsetvar, value) + self.assertRaises(OverflowError, self.interp.unsetvar, 'x', value) + self.assertRaises(OverflowError, self.interp.adderrorinfo, value) + self.assertRaises(OverflowError, self.interp.exprstring, value) + self.assertRaises(OverflowError, self.interp.exprlong, value) + self.assertRaises(OverflowError, self.interp.exprboolean, value) + self.assertRaises(OverflowError, self.interp.splitlist, value) + self.assertRaises(OverflowError, self.interp.split, value) + self.assertRaises(OverflowError, self.interp.createcommand, value, max) + self.assertRaises(OverflowError, self.interp.deletecommand, value) + def setUpModule(): if support.verbose: diff --git a/Misc/NEWS b/Misc/NEWS --- a/Misc/NEWS +++ b/Misc/NEWS @@ -18,6 +18,9 @@ Library ------- +- Issue #21552: Fixed possible integer overflow of too long string lengths in + the tkinter module on 64-bit platforms. + - Issue #14315: The zipfile module now ignores extra fields in the central directory that are too short to be parsed instead of letting a struct.unpack error bubble up as this "bad data" appears in many real world zip files in diff --git a/Modules/_tkinter.c b/Modules/_tkinter.c --- a/Modules/_tkinter.c +++ b/Modules/_tkinter.c @@ -861,6 +861,16 @@ }; +#if PY_SIZE_MAX > INT_MAX +#define CHECK_STRING_LENGTH(s) do { \ + if (s != NULL && strlen(s) >= INT_MAX) { \ + PyErr_SetString(PyExc_OverflowError, "string is too long"); \ + return NULL; \ + } } while(0) +#else +#define CHECK_STRING_LENGTH(s) +#endif + static Tcl_Obj* AsObj(PyObject *value) { @@ -1279,6 +1289,7 @@ if (!PyArg_ParseTuple(args, "s:eval", &script)) return NULL; + CHECK_STRING_LENGTH(script); CHECK_TCL_APPARTMENT; ENTER_TCL @@ -1302,6 +1313,7 @@ if (!PyArg_ParseTuple(args, "s:evalfile", &fileName)) return NULL; + CHECK_STRING_LENGTH(fileName); CHECK_TCL_APPARTMENT; ENTER_TCL @@ -1322,9 +1334,10 @@ PyObject *res = NULL; int err; - if (!PyArg_ParseTuple(args, "s", &script)) + if (!PyArg_ParseTuple(args, "s:record", &script)) return NULL; + CHECK_STRING_LENGTH(script); CHECK_TCL_APPARTMENT; ENTER_TCL @@ -1345,6 +1358,7 @@ if (!PyArg_ParseTuple(args, "s:adderrorinfo", &msg)) return NULL; + CHECK_STRING_LENGTH(msg); CHECK_TCL_APPARTMENT; ENTER_TCL @@ -1528,6 +1542,8 @@ if (!PyArg_ParseTuple(args, "ssO:setvar", &name1, &name2, &newValue)) return NULL; + CHECK_STRING_LENGTH(name1); + CHECK_STRING_LENGTH(name2); /* XXX must hold tcl lock already??? */ newval = AsObj(newValue); ENTER_TCL @@ -1573,6 +1589,7 @@ varname_converter, &name1, &name2)) return NULL; + CHECK_STRING_LENGTH(name2); ENTER_TCL tres = Tcl_GetVar2Ex(Tkapp_Interp(self), name1, name2, flags); ENTER_OVERLAP @@ -1615,6 +1632,8 @@ if (!PyArg_ParseTuple(args, "s|s:unsetvar", &name1, &name2)) return NULL; + CHECK_STRING_LENGTH(name1); + CHECK_STRING_LENGTH(name2); ENTER_TCL code = Tcl_UnsetVar2(Tkapp_Interp(self), name1, name2, flags); ENTER_OVERLAP @@ -1660,6 +1679,7 @@ } if (!PyArg_ParseTuple(args, "s:getint", &s)) return NULL; + CHECK_STRING_LENGTH(s); if (Tcl_GetInt(Tkapp_Interp(self), s, &v) == TCL_ERROR) return Tkinter_Error(self); return Py_BuildValue("i", v); @@ -1680,6 +1700,7 @@ } if (!PyArg_ParseTuple(args, "s:getdouble", &s)) return NULL; + CHECK_STRING_LENGTH(s); if (Tcl_GetDouble(Tkapp_Interp(self), s, &v) == TCL_ERROR) return Tkinter_Error(self); return Py_BuildValue("d", v); @@ -1700,6 +1721,7 @@ } if (!PyArg_ParseTuple(args, "s:getboolean", &s)) return NULL; + CHECK_STRING_LENGTH(s); if (Tcl_GetBoolean(Tkapp_Interp(self), s, &v) == TCL_ERROR) return Tkinter_Error(self); return PyBool_FromLong(v); @@ -1715,6 +1737,7 @@ if (!PyArg_ParseTuple(args, "s:exprstring", &s)) return NULL; + CHECK_STRING_LENGTH(s); CHECK_TCL_APPARTMENT; ENTER_TCL @@ -1739,6 +1762,7 @@ if (!PyArg_ParseTuple(args, "s:exprlong", &s)) return NULL; + CHECK_STRING_LENGTH(s); CHECK_TCL_APPARTMENT; ENTER_TCL @@ -1762,6 +1786,7 @@ if (!PyArg_ParseTuple(args, "s:exprdouble", &s)) return NULL; + CHECK_STRING_LENGTH(s); CHECK_TCL_APPARTMENT; PyFPE_START_PROTECT("Tkapp_ExprDouble", return 0) ENTER_TCL @@ -1786,6 +1811,7 @@ if (!PyArg_ParseTuple(args, "s:exprboolean", &s)) return NULL; + CHECK_STRING_LENGTH(s); CHECK_TCL_APPARTMENT; ENTER_TCL retval = Tcl_ExprBoolean(Tkapp_Interp(self), s, &v); @@ -1838,6 +1864,7 @@ if (!PyArg_ParseTuple(args, "et:splitlist", "utf-8", &list)) return NULL; + CHECK_STRING_LENGTH(list); if (Tcl_SplitList(Tkapp_Interp(self), list, &argc, &argv) == TCL_ERROR) { PyMem_Free(list); @@ -1899,6 +1926,7 @@ if (!PyArg_ParseTuple(args, "et:split", "utf-8", &list)) return NULL; + CHECK_STRING_LENGTH(list); v = Split(list); PyMem_Free(list); return v; @@ -2030,6 +2058,7 @@ if (!PyArg_ParseTuple(args, "sO:createcommand", &cmdName, &func)) return NULL; + CHECK_STRING_LENGTH(cmdName); if (!PyCallable_Check(func)) { PyErr_SetString(PyExc_TypeError, "command not callable"); return NULL; @@ -2091,6 +2120,7 @@ if (!PyArg_ParseTuple(args, "s:deletecommand", &cmdName)) return NULL; + CHECK_STRING_LENGTH(cmdName); #ifdef WITH_THREAD if (self->threaded && self->thread_id != Tcl_GetCurrentThread()) { @@ -2782,6 +2812,10 @@ &interactive, &wantobjects, &wantTk, &sync, &use)) return NULL; + CHECK_STRING_LENGTH(screenName); + CHECK_STRING_LENGTH(baseName); + CHECK_STRING_LENGTH(className); + CHECK_STRING_LENGTH(use); return (PyObject *) Tkapp_New(screenName, className, interactive, wantobjects, wantTk, -- Repository URL: http://hg.python.org/cpython

1 0

cpython (2.7): Issue #21552: Fixed possible integer overflow of too long string lengths in
by serhiy.storchaka May 30, 2014

May 30, 2014

http://hg.python.org/cpython/rev/59468bd68789 changeset: 90903:59468bd68789 branch: 2.7 parent: 90900:2d4648f575bd user: Serhiy Storchaka <storchaka(a)gmail.com> date: Fri May 30 14:23:52 2014 +0300 summary: Issue #21552: Fixed possible integer overflow of too long string lengths in the Tkinter module on 64-bit platforms. files: Lib/test/test_tcl.py | 52 +++++++++++++++++++++++++++++++- Misc/NEWS | 3 + Modules/_tkinter.c | 33 +++++++++++++++++++- 3 files changed, 86 insertions(+), 2 deletions(-) diff --git a/Lib/test/test_tcl.py b/Lib/test/test_tcl.py --- a/Lib/test/test_tcl.py +++ b/Lib/test/test_tcl.py @@ -569,6 +569,7 @@ for arg, res in testcases: self.assertEqual(split(arg), res) +character_size = 4 if sys.maxunicode > 0xFFFF else 2 class BigmemTclTest(unittest.TestCase): @@ -578,10 +579,59 @@ @test_support.cpython_only @unittest.skipUnless(INT_MAX < PY_SSIZE_T_MAX, "needs UINT_MAX < SIZE_MAX") @test_support.precisionbigmemtest(size=INT_MAX + 1, memuse=5, dry_run=False) - def test_huge_string(self, size): + def test_huge_string_call(self, size): value = ' ' * size self.assertRaises(OverflowError, self.interp.call, 'set', '_', value) + @test_support.cpython_only + @unittest.skipUnless(test_support.have_unicode, 'requires unicode support') + @unittest.skipUnless(INT_MAX < PY_SSIZE_T_MAX, "needs UINT_MAX < SIZE_MAX") + @test_support.precisionbigmemtest(size=INT_MAX + 1, + memuse=2*character_size + 2, + dry_run=False) + def test_huge_unicode_call(self, size): + value = unicode(' ') * size + self.assertRaises(OverflowError, self.interp.call, 'set', '_', value) + + + @test_support.cpython_only + @unittest.skipUnless(INT_MAX < PY_SSIZE_T_MAX, "needs UINT_MAX < SIZE_MAX") + @test_support.precisionbigmemtest(size=INT_MAX + 1, memuse=9, dry_run=False) + def test_huge_string_builtins(self, size): + value = '1' + ' ' * size + self.check_huge_string_builtins(value) + + @test_support.cpython_only + @unittest.skipUnless(test_support.have_unicode, 'requires unicode support') + @unittest.skipUnless(INT_MAX < PY_SSIZE_T_MAX, "needs UINT_MAX < SIZE_MAX") + @test_support.precisionbigmemtest(size=INT_MAX + 1, + memuse=2*character_size + 7, + dry_run=False) + def test_huge_unicode_builtins(self, size): + value = unicode('1' + ' ' * size) + self.check_huge_string_builtins(value) + + def check_huge_string_builtins(self, value): + self.assertRaises(OverflowError, self.interp.tk.getint, value) + self.assertRaises(OverflowError, self.interp.tk.getdouble, value) + self.assertRaises(OverflowError, self.interp.tk.getboolean, value) + self.assertRaises(OverflowError, self.interp.eval, value) + self.assertRaises(OverflowError, self.interp.evalfile, value) + self.assertRaises(OverflowError, self.interp.record, value) + self.assertRaises(OverflowError, self.interp.adderrorinfo, value) + self.assertRaises(OverflowError, self.interp.setvar, value, 'x', 'a') + self.assertRaises(OverflowError, self.interp.setvar, 'x', value, 'a') + self.assertRaises(OverflowError, self.interp.unsetvar, value) + self.assertRaises(OverflowError, self.interp.unsetvar, 'x', value) + self.assertRaises(OverflowError, self.interp.adderrorinfo, value) + self.assertRaises(OverflowError, self.interp.exprstring, value) + self.assertRaises(OverflowError, self.interp.exprlong, value) + self.assertRaises(OverflowError, self.interp.exprboolean, value) + self.assertRaises(OverflowError, self.interp.splitlist, value) + self.assertRaises(OverflowError, self.interp.split, value) + self.assertRaises(OverflowError, self.interp.createcommand, value, max) + self.assertRaises(OverflowError, self.interp.deletecommand, value) + def setUpModule(): if test_support.verbose: diff --git a/Misc/NEWS b/Misc/NEWS --- a/Misc/NEWS +++ b/Misc/NEWS @@ -18,6 +18,9 @@ Library ------- +- Issue #21552: Fixed possible integer overflow of too long string lengths in + the tkinter module on 64-bit platforms. + - Issue #14315: The zipfile module now ignores extra fields in the central directory that are too short to be parsed instead of letting a struct.unpack error bubble up as this "bad data" appears in many real world zip files in diff --git a/Modules/_tkinter.c b/Modules/_tkinter.c --- a/Modules/_tkinter.c +++ b/Modules/_tkinter.c @@ -1021,6 +1021,16 @@ 0, /*tp_is_gc*/ }; +#if PY_SIZE_MAX > INT_MAX +#define CHECK_STRING_LENGTH(s) do { \ + if (s != NULL && strlen(s) >= INT_MAX) { \ + PyErr_SetString(PyExc_OverflowError, "string is too long"); \ + return NULL; \ + } } while(0) +#else +#define CHECK_STRING_LENGTH(s) +#endif + static Tcl_Obj* AsObj(PyObject *value) { @@ -1486,6 +1496,7 @@ if (!PyArg_ParseTuple(args, "s:eval", &script)) return NULL; + CHECK_STRING_LENGTH(script); CHECK_TCL_APPARTMENT; ENTER_TCL @@ -1532,6 +1543,7 @@ if (!PyArg_ParseTuple(args, "s:evalfile", &fileName)) return NULL; + CHECK_STRING_LENGTH(fileName); CHECK_TCL_APPARTMENT; ENTER_TCL @@ -1553,9 +1565,10 @@ PyObject *res = NULL; int err; - if (!PyArg_ParseTuple(args, "s", &script)) + if (!PyArg_ParseTuple(args, "s:record", &script)) return NULL; + CHECK_STRING_LENGTH(script); CHECK_TCL_APPARTMENT; ENTER_TCL @@ -1576,6 +1589,7 @@ if (!PyArg_ParseTuple(args, "s:adderrorinfo", &msg)) return NULL; + CHECK_STRING_LENGTH(msg); CHECK_TCL_APPARTMENT; ENTER_TCL @@ -1743,6 +1757,8 @@ if (!PyArg_ParseTuple(args, "ssO:setvar", &name1, &name2, &newValue)) return NULL; + CHECK_STRING_LENGTH(name1); + CHECK_STRING_LENGTH(name2); /* XXX must hold tcl lock already??? */ newval = AsObj(newValue); ENTER_TCL @@ -1788,6 +1804,7 @@ varname_converter, &name1, &name2)) return NULL; + CHECK_STRING_LENGTH(name2); ENTER_TCL tres = Tcl_GetVar2Ex(Tkapp_Interp(self), name1, name2, flags); ENTER_OVERLAP @@ -1831,6 +1848,8 @@ if (!PyArg_ParseTuple(args, "s|s:unsetvar", &name1, &name2)) return NULL; + CHECK_STRING_LENGTH(name1); + CHECK_STRING_LENGTH(name2); ENTER_TCL code = Tcl_UnsetVar2(Tkapp_Interp(self), name1, name2, flags); ENTER_OVERLAP @@ -1930,6 +1949,7 @@ if (!PyArg_ParseTuple(args, "s:exprstring", &s)) return NULL; + CHECK_STRING_LENGTH(s); CHECK_TCL_APPARTMENT; ENTER_TCL @@ -1954,6 +1974,7 @@ if (!PyArg_ParseTuple(args, "s:exprlong", &s)) return NULL; + CHECK_STRING_LENGTH(s); CHECK_TCL_APPARTMENT; ENTER_TCL @@ -1977,6 +1998,7 @@ if (!PyArg_ParseTuple(args, "s:exprdouble", &s)) return NULL; + CHECK_STRING_LENGTH(s); CHECK_TCL_APPARTMENT; PyFPE_START_PROTECT("Tkapp_ExprDouble", return 0) ENTER_TCL @@ -2001,6 +2023,7 @@ if (!PyArg_ParseTuple(args, "s:exprboolean", &s)) return NULL; + CHECK_STRING_LENGTH(s); CHECK_TCL_APPARTMENT; ENTER_TCL retval = Tcl_ExprBoolean(Tkapp_Interp(self), s, &v); @@ -2053,6 +2076,7 @@ if (!PyArg_ParseTuple(args, "et:splitlist", "utf-8", &list)) return NULL; + CHECK_STRING_LENGTH(list); if (Tcl_SplitList(Tkapp_Interp(self), list, &argc, &argv) == TCL_ERROR) { PyMem_Free(list); @@ -2114,6 +2138,7 @@ if (!PyArg_ParseTuple(args, "et:split", "utf-8", &list)) return NULL; + CHECK_STRING_LENGTH(list); v = Split(list); PyMem_Free(list); return v; @@ -2259,6 +2284,7 @@ if (!PyArg_ParseTuple(args, "sO:createcommand", &cmdName, &func)) return NULL; + CHECK_STRING_LENGTH(cmdName); if (!PyCallable_Check(func)) { PyErr_SetString(PyExc_TypeError, "command not callable"); return NULL; @@ -2322,6 +2348,7 @@ if (!PyArg_ParseTuple(args, "s:deletecommand", &cmdName)) return NULL; + CHECK_STRING_LENGTH(cmdName); #ifdef WITH_THREAD if (self->threaded && self->thread_id != Tcl_GetCurrentThread()) { @@ -3130,6 +3157,10 @@ &interactive, &wantobjects, &wantTk, &sync, &use)) return NULL; + CHECK_STRING_LENGTH(screenName); + CHECK_STRING_LENGTH(baseName); + CHECK_STRING_LENGTH(className); + CHECK_STRING_LENGTH(use); return (PyObject *) Tkapp_New(screenName, baseName, className, interactive, wantobjects, wantTk, -- Repository URL: http://hg.python.org/cpython

1 0

cpython (merge 3.4 -> default): Add tests for getint, getdouble and getboolean methods of the tkapp object.
by serhiy.storchaka May 30, 2014

May 30, 2014

http://hg.python.org/cpython/rev/33c308ddfb14 changeset: 90902:33c308ddfb14 parent: 90899:f5521f5dec4a parent: 90901:73ba4f1dac53 user: Serhiy Storchaka <storchaka(a)gmail.com> date: Fri May 30 14:08:49 2014 +0300 summary: Add tests for getint, getdouble and getboolean methods of the tkapp object. files: Lib/test/test_tcl.py | 44 ++++++++++++++++++++++++++++++++ 1 files changed, 44 insertions(+), 0 deletions(-) diff --git a/Lib/test/test_tcl.py b/Lib/test/test_tcl.py --- a/Lib/test/test_tcl.py +++ b/Lib/test/test_tcl.py @@ -133,6 +133,50 @@ tcl = self.interp self.assertRaises(TclError,tcl.unsetvar,'a') + def test_getint(self): + tcl = self.interp.tk + self.assertEqual(tcl.getint(' 42 '), 42) + self.assertEqual(tcl.getint(42), 42) + self.assertRaises(TypeError, tcl.getint) + self.assertRaises(TypeError, tcl.getint, '42', '10') + self.assertRaises(TypeError, tcl.getint, b'42') + self.assertRaises(TypeError, tcl.getint, 42.0) + self.assertRaises(TclError, tcl.getint, 'a') + self.assertRaises((TypeError, ValueError, TclError), + tcl.getint, '42\0') + self.assertRaises((UnicodeEncodeError, ValueError, TclError), + tcl.getint, '42\ud800') + + def test_getdouble(self): + tcl = self.interp.tk + self.assertEqual(tcl.getdouble(' 42 '), 42.0) + self.assertEqual(tcl.getdouble(' 42.5 '), 42.5) + self.assertEqual(tcl.getdouble(42.5), 42.5) + self.assertRaises(TypeError, tcl.getdouble) + self.assertRaises(TypeError, tcl.getdouble, '42.5', '10') + self.assertRaises(TypeError, tcl.getdouble, b'42.5') + self.assertRaises(TypeError, tcl.getdouble, 42) + self.assertRaises(TclError, tcl.getdouble, 'a') + self.assertRaises((TypeError, ValueError, TclError), + tcl.getdouble, '42.5\0') + self.assertRaises((UnicodeEncodeError, ValueError, TclError), + tcl.getdouble, '42.5\ud800') + + def test_getboolean(self): + tcl = self.interp.tk + self.assertIs(tcl.getboolean('on'), True) + self.assertIs(tcl.getboolean('1'), True) + self.assertEqual(tcl.getboolean(42), 42) + self.assertRaises(TypeError, tcl.getboolean) + self.assertRaises(TypeError, tcl.getboolean, 'on', '1') + self.assertRaises(TypeError, tcl.getboolean, b'on') + self.assertRaises(TypeError, tcl.getboolean, 1.0) + self.assertRaises(TclError, tcl.getboolean, 'a') + self.assertRaises((TypeError, ValueError, TclError), + tcl.getboolean, 'on\0') + self.assertRaises((UnicodeEncodeError, ValueError, TclError), + tcl.getboolean, 'on\ud800') + def testEvalFile(self): tcl = self.interp with open(support.TESTFN, 'w') as f: -- Repository URL: http://hg.python.org/cpython

1 0

cpython (3.4): Add tests for getint, getdouble and getboolean methods of the tkapp object.
by serhiy.storchaka May 30, 2014

May 30, 2014

http://hg.python.org/cpython/rev/73ba4f1dac53 changeset: 90901:73ba4f1dac53 branch: 3.4 parent: 90897:33843896ce4e user: Serhiy Storchaka <storchaka(a)gmail.com> date: Fri May 30 14:07:38 2014 +0300 summary: Add tests for getint, getdouble and getboolean methods of the tkapp object. files: Lib/test/test_tcl.py | 44 ++++++++++++++++++++++++++++++++ 1 files changed, 44 insertions(+), 0 deletions(-) diff --git a/Lib/test/test_tcl.py b/Lib/test/test_tcl.py --- a/Lib/test/test_tcl.py +++ b/Lib/test/test_tcl.py @@ -133,6 +133,50 @@ tcl = self.interp self.assertRaises(TclError,tcl.unsetvar,'a') + def test_getint(self): + tcl = self.interp.tk + self.assertEqual(tcl.getint(' 42 '), 42) + self.assertEqual(tcl.getint(42), 42) + self.assertRaises(TypeError, tcl.getint) + self.assertRaises(TypeError, tcl.getint, '42', '10') + self.assertRaises(TypeError, tcl.getint, b'42') + self.assertRaises(TypeError, tcl.getint, 42.0) + self.assertRaises(TclError, tcl.getint, 'a') + self.assertRaises((TypeError, ValueError, TclError), + tcl.getint, '42\0') + self.assertRaises((UnicodeEncodeError, ValueError, TclError), + tcl.getint, '42\ud800') + + def test_getdouble(self): + tcl = self.interp.tk + self.assertEqual(tcl.getdouble(' 42 '), 42.0) + self.assertEqual(tcl.getdouble(' 42.5 '), 42.5) + self.assertEqual(tcl.getdouble(42.5), 42.5) + self.assertRaises(TypeError, tcl.getdouble) + self.assertRaises(TypeError, tcl.getdouble, '42.5', '10') + self.assertRaises(TypeError, tcl.getdouble, b'42.5') + self.assertRaises(TypeError, tcl.getdouble, 42) + self.assertRaises(TclError, tcl.getdouble, 'a') + self.assertRaises((TypeError, ValueError, TclError), + tcl.getdouble, '42.5\0') + self.assertRaises((UnicodeEncodeError, ValueError, TclError), + tcl.getdouble, '42.5\ud800') + + def test_getboolean(self): + tcl = self.interp.tk + self.assertIs(tcl.getboolean('on'), True) + self.assertIs(tcl.getboolean('1'), True) + self.assertEqual(tcl.getboolean(42), 42) + self.assertRaises(TypeError, tcl.getboolean) + self.assertRaises(TypeError, tcl.getboolean, 'on', '1') + self.assertRaises(TypeError, tcl.getboolean, b'on') + self.assertRaises(TypeError, tcl.getboolean, 1.0) + self.assertRaises(TclError, tcl.getboolean, 'a') + self.assertRaises((TypeError, ValueError, TclError), + tcl.getboolean, 'on\0') + self.assertRaises((UnicodeEncodeError, ValueError, TclError), + tcl.getboolean, 'on\ud800') + def testEvalFile(self): tcl = self.interp with open(support.TESTFN, 'w') as f: -- Repository URL: http://hg.python.org/cpython

1 0

cpython (2.7): Add tests for getint, getdouble and getboolean methods of the tkapp object.
by serhiy.storchaka May 30, 2014

May 30, 2014

http://hg.python.org/cpython/rev/2d4648f575bd changeset: 90900:2d4648f575bd branch: 2.7 parent: 90896:6dd5e9556a60 user: Serhiy Storchaka <storchaka(a)gmail.com> date: Fri May 30 14:07:20 2014 +0300 summary: Add tests for getint, getdouble and getboolean methods of the tkapp object. files: Lib/test/test_tcl.py | 47 ++++++++++++++++++++++++++++++++ 1 files changed, 47 insertions(+), 0 deletions(-) diff --git a/Lib/test/test_tcl.py b/Lib/test/test_tcl.py --- a/Lib/test/test_tcl.py +++ b/Lib/test/test_tcl.py @@ -127,6 +127,53 @@ tcl = self.interp self.assertRaises(TclError,tcl.unsetvar,'a') + def test_getint(self): + tcl = self.interp.tk + self.assertEqual(tcl.getint(' 42 '), 42) + self.assertEqual(tcl.getint(42), 42) + self.assertRaises(TypeError, tcl.getint) + self.assertRaises(TypeError, tcl.getint, '42', '10') + self.assertRaises(TypeError, tcl.getint, 42.0) + self.assertRaises(TclError, tcl.getint, 'a') + self.assertRaises((TypeError, ValueError, TclError), + tcl.getint, '42\0') + if test_support.have_unicode: + self.assertEqual(tcl.getint(unicode('42')), 42) + self.assertRaises((UnicodeEncodeError, ValueError, TclError), + tcl.getint, '42' + unichr(0xd800)) + + def test_getdouble(self): + tcl = self.interp.tk + self.assertEqual(tcl.getdouble(' 42 '), 42.0) + self.assertEqual(tcl.getdouble(' 42.5 '), 42.5) + self.assertEqual(tcl.getdouble(42.5), 42.5) + self.assertRaises(TypeError, tcl.getdouble) + self.assertRaises(TypeError, tcl.getdouble, '42.5', '10') + self.assertRaises(TypeError, tcl.getdouble, 42) + self.assertRaises(TclError, tcl.getdouble, 'a') + self.assertRaises((TypeError, ValueError, TclError), + tcl.getdouble, '42.5\0') + if test_support.have_unicode: + self.assertEqual(tcl.getdouble(unicode('42.5')), 42.5) + self.assertRaises((UnicodeEncodeError, ValueError, TclError), + tcl.getdouble, '42.5' + unichr(0xd800)) + + def test_getboolean(self): + tcl = self.interp.tk + self.assertIs(tcl.getboolean('on'), True) + self.assertIs(tcl.getboolean('1'), True) + self.assertEqual(tcl.getboolean(42), 42) + self.assertRaises(TypeError, tcl.getboolean) + self.assertRaises(TypeError, tcl.getboolean, 'on', '1') + self.assertRaises(TypeError, tcl.getboolean, 1.0) + self.assertRaises(TclError, tcl.getboolean, 'a') + self.assertRaises((TypeError, ValueError, TclError), + tcl.getboolean, 'on\0') + if test_support.have_unicode: + self.assertIs(tcl.getboolean(unicode('on')), True) + self.assertRaises((UnicodeEncodeError, ValueError, TclError), + tcl.getboolean, 'on' + unichr(0xd800)) + def testEvalFile(self): tcl = self.interp filename = "testEvalFile.tcl" -- Repository URL: http://hg.python.org/cpython

1 0

cpython: Issue #13742: Add key and reverse parameters to heapq.merge()
by raymond.hettinger May 30, 2014

May 30, 2014

http://hg.python.org/cpython/rev/f5521f5dec4a changeset: 90899:f5521f5dec4a user: Raymond Hettinger <python(a)rcn.com> date: Fri May 30 02:28:36 2014 -0700 summary: Issue #13742: Add key and reverse parameters to heapq.merge() files: Doc/glossary.rst | 7 +- Doc/library/heapq.rst | 14 +++++- Lib/heapq.py | 74 +++++++++++++++++++++++++---- Lib/test/test_heapq.py | 19 ++++++- Misc/NEWS | 3 + 5 files changed, 98 insertions(+), 19 deletions(-) diff --git a/Doc/glossary.rst b/Doc/glossary.rst --- a/Doc/glossary.rst +++ b/Doc/glossary.rst @@ -444,12 +444,13 @@ A number of tools in Python accept key functions to control how elements are ordered or grouped. They include :func:`min`, :func:`max`, - :func:`sorted`, :meth:`list.sort`, :func:`heapq.nsmallest`, - :func:`heapq.nlargest`, and :func:`itertools.groupby`. + :func:`sorted`, :meth:`list.sort`, :func:`heapq.merge`, + :func:`heapq.nsmallest`, :func:`heapq.nlargest`, and + :func:`itertools.groupby`. There are several ways to create a key function. For example. the :meth:`str.lower` method can serve as a key function for case insensitive - sorts. Alternatively, an ad-hoc key function can be built from a + sorts. Alternatively, a key function can be built from a :keyword:`lambda` expression such as ``lambda r: (r[0], r[2])``. Also, the :mod:`operator` module provides three key function constructors: :func:`~operator.attrgetter`, :func:`~operator.itemgetter`, and diff --git a/Doc/library/heapq.rst b/Doc/library/heapq.rst --- a/Doc/library/heapq.rst +++ b/Doc/library/heapq.rst @@ -81,7 +81,7 @@ The module also offers three general purpose functions based on heaps. -.. function:: merge(*iterables) +.. function:: merge(*iterables, key=None, reverse=False) Merge multiple sorted inputs into a single sorted output (for example, merge timestamped entries from multiple log files). Returns an :term:`iterator` @@ -91,6 +91,18 @@ not pull the data into memory all at once, and assumes that each of the input streams is already sorted (smallest to largest). + Has two optional arguments which must be specified as keyword arguments. + + *key* specifies a :term:`key function` of one argument that is used to + extract a comparison key from each input element. The default value is + ``None`` (compare the elements directly). + + *reverse* is a boolean value. If set to ``True``, then the input elements + are merged as if each comparison were reversed. + + .. versionchanged:: 3.5 + Added the optional *key* and *reverse* parameters. + .. function:: nlargest(n, iterable, key=None) diff --git a/Lib/heapq.py b/Lib/heapq.py --- a/Lib/heapq.py +++ b/Lib/heapq.py @@ -176,6 +176,16 @@ for i in reversed(range(n//2)): _siftup(x, i) +def _heappop_max(heap): + """Maxheap version of a heappop.""" + lastelt = heap.pop() # raises appropriate IndexError if heap is empty + if heap: + returnitem = heap[0] + heap[0] = lastelt + _siftup_max(heap, 0) + return returnitem + return lastelt + def _heapreplace_max(heap, item): """Maxheap version of a heappop followed by a heappush.""" returnitem = heap[0] # raises appropriate IndexError if heap is empty @@ -311,7 +321,7 @@ except ImportError: pass -def merge(*iterables): +def merge(*iterables, key=None, reverse=False): '''Merge multiple sorted inputs into a single sorted output. Similar to sorted(itertools.chain(*iterables)) but returns a generator, @@ -321,31 +331,73 @@ >>> list(merge([1,3,5,7], [0,2,4,8], [5,10,15,20], [], [25])) [0, 1, 2, 3, 4, 5, 5, 7, 8, 10, 15, 20, 25] + If *key* is not None, applies a key function to each element to determine + its sort order. + + >>> list(merge(['dog', 'horse'], ['cat', 'fish', 'kangaroo'], key=len)) + ['dog', 'cat', 'fish', 'horse', 'kangaroo'] + ''' h = [] h_append = h.append + + if reverse: + _heapify = _heapify_max + _heappop = _heappop_max + _heapreplace = _heapreplace_max + direction = -1 + else: + _heapify = heapify + _heappop = heappop + _heapreplace = heapreplace + direction = 1 + + if key is None: + for order, it in enumerate(map(iter, iterables)): + try: + next = it.__next__ + h_append([next(), order * direction, next]) + except StopIteration: + pass + _heapify(h) + while len(h) > 1: + try: + while True: + value, order, next = s = h[0] + yield value + s[0] = next() # raises StopIteration when exhausted + _heapreplace(h, s) # restore heap condition + except StopIteration: + _heappop(h) # remove empty iterator + if h: + # fast case when only a single iterator remains + value, order, next = h[0] + yield value + yield from next.__self__ + return + for order, it in enumerate(map(iter, iterables)): try: next = it.__next__ - h_append([next(), order, next]) + value = next() + h_append([key(value), order * direction, value, next]) except StopIteration: pass - heapify(h) - - _heapreplace = heapreplace + _heapify(h) while len(h) > 1: try: while True: - value, order, next = s = h[0] + key_value, order, value, next = s = h[0] yield value - s[0] = next() # raises StopIteration when exhausted - _heapreplace(h, s) # restore heap condition + value = next() + s[0] = key(value) + s[2] = value + _heapreplace(h, s) except StopIteration: - heappop(h) # remove empty iterator + _heappop(h) if h: - # fast case when only a single iterator remains - value, order, next = h[0] + key_value, order, value, next = h[0] yield value yield from next.__self__ diff --git a/Lib/test/test_heapq.py b/Lib/test/test_heapq.py --- a/Lib/test/test_heapq.py +++ b/Lib/test/test_heapq.py @@ -6,6 +6,7 @@ from test import support from unittest import TestCase, skipUnless +from operator import itemgetter py_heapq = support.import_fresh_module('heapq', blocked=['_heapq']) c_heapq = support.import_fresh_module('heapq', fresh=['_heapq']) @@ -152,11 +153,21 @@ def test_merge(self): inputs = [] - for i in range(random.randrange(5)): - row = sorted(random.randrange(1000) for j in range(random.randrange(10))) + for i in range(random.randrange(25)): + row = [] + for j in range(random.randrange(100)): + tup = random.choice('ABC'), random.randrange(-500, 500) + row.append(tup) inputs.append(row) - self.assertEqual(sorted(chain(*inputs)), list(self.module.merge(*inputs))) - self.assertEqual(list(self.module.merge()), []) + + for key in [None, itemgetter(0), itemgetter(1), itemgetter(1, 0)]: + for reverse in [False, True]: + seqs = [] + for seq in inputs: + seqs.append(sorted(seq, key=key, reverse=reverse)) + self.assertEqual(sorted(chain(*inputs), key=key, reverse=reverse), + list(self.module.merge(*seqs, key=key, reverse=reverse))) + self.assertEqual(list(self.module.merge()), []) def test_merge_does_not_suppress_index_error(self): # Issue 19018: Heapq.merge suppresses IndexError from user generator diff --git a/Misc/NEWS b/Misc/NEWS --- a/Misc/NEWS +++ b/Misc/NEWS @@ -94,6 +94,9 @@ error bubble up as this "bad data" appears in many real world zip files in the wild and is ignored by other zip tools. +- Issue #13742: Added "key" and "reverse" parameters to heapq.merge(). + (First draft of patch contributed by Simon Sapin.) + - Issue #21402: tkinter.ttk now works when default root window is not set. - Issue #3015: _tkinter.create() now creates tkapp object with wantobject=1 by -- Repository URL: http://hg.python.org/cpython

1 0