Issue1835099

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.

Had the same error and managed to reproduce. Seems like the standard
sorting algorithm has an error.

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

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.

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)

Yes, and the new patch works with test_sort() as well as my own testcase

Fixed in r4527. Thanks.

closing out

A patch against the sources delivered with the stable Jython 2.2.1 
release, that solved my issues.

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.

This bug may be relevant for PyDev 2.3.0 that uses now Jython 2.2.1.