Issue1835099

classification
Title: Bug in list.sort()
Type: behaviour Severity: major
Components: Core Versions: 2.2.2
process
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.

Files
File name Uploaded Description Edit Remove
jythonerror.py 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
Messages
msg2012 (view) Author: Roland Walter (r_walter) Date: 2007-11-20.11:55:26
Hello,

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

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

filename1="e:\\daten\\slsrpt\\OUT\\asciitest_slsrpt\\slsrpt4562.txt"

f = open(filename1, "r")

lines = f.readlines()

f.close()

lines.sort()

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

f.writelines(lines)

f.close()

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
903c903
< 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 jythonerror.py), 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
(http://svn.python.org/projects/python/trunk/Objects/listobject.c). 

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

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

In MergeState it has been convert to these lines:
void merge_lo(...) {
  <snip>
  --nb;
  if (nb == 0)
    return;
  <snip>
  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.
History
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: + jythonerror.py
severity: normal -> major
versions: + 2.2.1rc1
nosy: + arnebef
messages: + msg3217
type: behaviour
2007-11-20 11:55:26r_waltercreate