Title: Bug in list.sort()
Type: behaviour Severity: major
Components: Core Versions: 2.2.2
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: arnebef, nriley, pjenvey, r_walter
Priority: normal Keywords:

Created on 2007-11-20.11:55:26 by r_walter, last changed 2011-12-16.13:20:40 by r_walter.

File name Uploaded Description Edit Remove arnebef, 2008-06-03.11:07:05 Reproduced sorting bug
sorterror.patch arnebef, 2008-06-03.13:18:39 Mergestate patch
sorterror_updated.patch arnebef, 2008-06-03.21:56:44
sorterror_updated.patch arnebef, 2008-06-03.22:29:14
MergeState_2_2_1.patch r_walter, 2008-06-14.11:33:42 Patch of org.python.core.MergeState
msg2012 (view) Author: Roland Walter (r_walter) Date: 2007-11-20.11:55:26

I discovered a bug in the sort()-method for sequences.

I run the following skript on Jython 2.2.1 and Python 2.5:


f = open(filename1, "r")

lines = f.readlines()



f = open("bug_jy_sort_test.txt", "w")



I compared the written file with diff and get that line 903 has a difference. The file written with Jython contains a line a second time and has dropped the line that should be in that position. 

The output of the diff-command is:

$ diff bug_jy_sort_test.txt_2_2_1 bug_jy_sort_test.txt
< 200;73E;4047700000004;4314125000002;0000099;4314122749881;;4047700002756;;0257158;;;;ALP. COLA-WEIZEN  4X6X0,3;;;;;;;;;;;;;;;;;1;STK;;;;;;;;;;;;;;01.06.2007;;30.06.2007;;;;;;;;
> 200;73E;4047700000004;4314125000002;0000099;4314122749881;;4047700002954;;0021960;;;;ALP. KLEINER MOENCH 4X6X0;;;;;;;;;;;;;;;;;1;STK;;;;;;;;;;;;;;01.06.2007;;30.06.2007;;;;;;;;

The problem is, I cannot provide the whole file as it contains confidential data. It has 1148 lines and its size is 202654 bytes.

The bug is not in jython 2.1.
msg3217 (view) Author: Arne Fossaa (arnebef) Date: 2008-06-03.11:07:05
Had the same error and managed to reproduce. Seems like the standard
sorting algorithm has an error.
msg3218 (view) Author: Arne Fossaa (arnebef) Date: 2008-06-03.13:18:37
Found the problem (in MergeState). Made a small bugfix that fixed the
problem with the problematic set (see, but have not
checked this against other datasets.

The patch is against rev 2624 of MergeState
msg3220 (view) Author: Arne Fossaa (arnebef) Date: 2008-06-03.19:52:35
The problem with my testset is in merge_lo, but since the function is
similar in merge_hi, I think that should be fixed too.
msg3222 (view) Author: Arne Fossaa (arnebef) Date: 2008-06-03.21:56:43
Ok, this should be a better patch (not beautiful, but should work).

The problem is in merge_lo/merge_hi in mergestate. These have been
copied from listobject.c

In listobject.c there are these lines:
static Py_ssize_t merge_lo(... {
  if (na == 0)
    goto Succeed;
    result = 0;
    if (nb)
      memcpy(dest-(nb-1), baseb, nb * sizeof(PyObject*));
    return result;

Because of gotos fall through, when Succeed is jumped, Fail is also

In MergeState it has been convert to these lines:
void merge_lo(...) {
  if (nb == 0)
  try { ... }
  finally {
    if (na != 0)
      System.arraycopy(this.a, pa, this.kvdata, dest, na);

Basically, in the C implementation, Fail will also be performed when
Succeed is performed, while in the Java implementation, the finally tag
will never be entered if nb == 1 when starting. This means that
this.kvdata[pa] = this.kvdata[pb], and the sort is not a sort anymore ;)

Patch attached (sorterror_updated)
msg3223 (view) Author: Arne Fossaa (arnebef) Date: 2008-06-03.22:00:37
Yes, and the new patch works with test_sort() as well as my own testcase
msg3224 (view) Author: Nicholas Riley (nriley) Date: 2008-06-04.04:34:41
Fixed in r4527. Thanks.
msg3253 (view) Author: Philip Jenvey (pjenvey) Date: 2008-06-08.22:03:39
closing out
msg3285 (view) Author: Roland Walter (r_walter) Date: 2008-06-14.11:33:37
A patch against the sources delivered with the stable Jython 2.2.1 
release, that solved my issues.
msg3789 (view) Author: Roland Walter (r_walter) Date: 2008-11-19.22:25:26
This has not been fixed in the branch /branches/Release_2_2maint yet. 
It is only fixed in the trunk. Consider to reopen this bug when you 
plan to release a 2.2.2.
msg6746 (view) Author: Roland Walter (r_walter) Date: 2011-12-16.13:20:40
This bug may be relevant for PyDev 2.3.0 that uses now Jython 2.2.1.
Date User Action Args
2011-12-16 13:20:40r_waltersetmessages: + msg6746
2008-11-19 22:25:27r_waltersetmessages: + msg3789
versions: + 2.2.2, - 2.2.1rc1
2008-06-14 11:33:43r_waltersetfiles: + MergeState_2_2_1.patch
messages: + msg3285
2008-06-08 22:03:41pjenveysetstatus: open -> closed
resolution: fixed
messages: + msg3253
nosy: + pjenvey
2008-06-04 04:34:42nrileysetnosy: + nriley
messages: + msg3224
2008-06-03 22:29:15arnebefsetfiles: + sorterror_updated.patch
2008-06-03 22:00:37arnebefsetmessages: + msg3223
2008-06-03 21:56:44arnebefsetfiles: + sorterror_updated.patch
messages: + msg3222
2008-06-03 19:52:36arnebefsetmessages: + msg3220
2008-06-03 13:20:38arnebefsettitle: Bug in sort()-method -> Bug in list.sort()
2008-06-03 13:18:39arnebefsetfiles: + sorterror.patch
messages: + msg3218
2008-06-03 11:07:06arnebefsetfiles: +
severity: normal -> major
versions: + 2.2.1rc1
nosy: + arnebef
messages: + msg3217
type: behaviour
2007-11-20 11:55:26r_waltercreate