Skip to content

bpo-36218: Fix handling of heterogeneous values in list.sort #12209

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
rhettinger merged 9 commits into from
Mar 25, 2019
Merged

bpo-36218: Fix handling of heterogeneous values in list.sort #12209

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
9 commits
Select commit Hold shift + click to select a range
e75d9fb
Fix sorting of heterogeneous values in list.sort
Mar 7, 2019
8498a21
Add blurb
Mar 7, 2019
60aca1e
Remove early exit when keys are tuples
Mar 12, 2019
eaa7c50
Fix bug found by test_json
Mar 12, 2019
3b02a05
Remove empty line
Mar 12, 2019
47a0688
Simplify logic in pre-sort check
Mar 21, 2019
467cd16
Add test
Mar 21, 2019
8b2224f
Fix coding style
serhiy-storchaka Mar 21, 2019
6286a4b
Fix indentation
Mar 22, 2019
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Next Next commit
Fix sorting of heterogeneous values in list.sort
  • Loading branch information
Rémi Lapeyre committed Mar 7, 2019
commit e75d9fb94b2c61e88f6fb97d6b1541c818e62728
3 changes: 3 additions & 0 deletions Lib/test/test_sort.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -373,6 +373,9 @@ def test_unsafe_tuple_compare(self):
check_against_PyObject_RichCompareBool(self, [float('nan')]*100)
check_against_PyObject_RichCompareBool(self, [float('nan') for
_ in range(100)])

def test_not_all_tuples(self):
self.assertRaises(TypeError, [(1.0, 1.0), (False, "A"), 6].sort)
#==============================================================================

if __name__ == "__main__":
Expand Down
24 changes: 14 additions & 10 deletions Objects/listobject.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -2305,6 +2305,7 @@ list_sort_impl(PyListObject *self, PyObject *keyfunc, int reverse)
lo.keys[i]);

if (key->ob_type != key_type) {
keys_are_in_tuples = 0;
Copy link
Copy Markdown
Contributor

@embg embg Mar 11, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
keys_are_in_tuples = 0;

Copy link
Copy Markdown
Contributor

@embg embg Mar 11, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

We remove this line, which over-compensates in the case you mentioned.

keys_are_all_same_type = 0;
break;
}
Expand Down Expand Up @@ -2338,21 +2339,24 @@ list_sort_impl(PyListObject *self, PyObject *keyfunc, int reverse)
else {
ms.key_compare = safe_object_compare;
}

if (keys_are_in_tuples) {
/* Make sure we're not dealing with tuples of tuples
* (remember: here, key_type refers list [key[0] for key in keys]) */
if (key_type == &PyTuple_Type) {
Copy link
Copy Markdown
Contributor

@embg embg Mar 11, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
if (key_type == &PyTuple_Type) {
if ( (keys_are_all_same_type == 0) || (key_type == &PyTuple_Type) ) {

Copy link
Copy Markdown
Contributor

@embg embg Mar 11, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

And instead modify this check, which sets tuple_elem_compare to safe_object_compare in the case of nested tuples, to also fall back when the tuple first-elements are heterogeneous.

Copy link
Copy Markdown
Author

@remilapeyre remilapeyre Mar 11, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I don't think that's going to work because of the early exit at https://github.com/python/cpython/pull/12209/files#diff-5037da2a492e5903f100107e0506f818R2310 you can't be sure that all keys are tuples anyway.

I think the simplest way forward would be to use two variables key_type and inner_key_type to know if it's item[0] or item that changed type.

Does this make sense?

ms.tuple_elem_compare = safe_object_compare;
}
else {
ms.tuple_elem_compare = ms.key_compare;
}

ms.key_compare = unsafe_tuple_compare;
}
}
else {
ms.key_compare = safe_object_compare;
}

if (keys_are_in_tuples) {
/* Make sure we're not dealing with tuples of tuples
* (remember: here, key_type refers list [key[0] for key in keys]) */
if (key_type == &PyTuple_Type)
ms.tuple_elem_compare = safe_object_compare;
else
ms.tuple_elem_compare = ms.key_compare;

ms.key_compare = unsafe_tuple_compare;
}
}
/* End of pre-sort check: ms is now set properly! */

Expand Down