Sign in Join

Live chat for Free Pascal, Lazarus, Delphi and every Pascal programmer.

Mailing lists / fpc-devel / 2019-02

New sorting routines

4 messages · 3 people · –

Reply by email Subscribe to this list Your subscription

Read-only archive. Use j and k to move between messages.

C Western

I suspect the new sorting routines need some work - lazarus compiled with the latest trunk hangs on start up, and it looks like an infinite loop in sorting. Stack trace below.

Colin

#0  0x0000000000422167 in DECLOCKED (L=2) at ../x86_64/x86_64.inc:709 #1  0x000000000042c325 in fpc_ansistr_decr_ref (S=0x2)     at ../inc/astrings.inc:148
#2  0xfffffffffffffffa in  ()
#3  0x0000000000e8d67b in COMPAREBINARY (LIST=0x7fffdf4f5f00, INDEX1=6, INDEX2=
    7) at syneditmarkuphighall.pp:807
#4  0x000000000053abf6 in TSTRINGLIST_CUSTOMSORT_COMPARER (ITEM1=     0x7fffded60e88, ITEM2=0x1, CONTEXT=0x1b18e80)     at ../objpas/classes/stringl.inc:1642
#5  0x0000000001b63530 in TC_$SORTBASE_$$_QUICKSORT () #6  0x0000000000558b60 in QUICKSORT (parentfp=0x7fffffffc740, L=2, R=7)     at ../inc/sortbase.pp:182
#7  0x00007fffffffc740 in  ()
#8  0x000000000043aeb5 in SYSGETMEM (SIZE=140736931958424)     at ../inc/heap.inc:1082
#9  0x0000000000000003 in  ()
#10 0x000000000000000b in  ()
#11 0x0000000001b63530 in TC_$SORTBASE_$$_QUICKSORT () #12 0x0000000000e8d430 in
SYNEDITMARKUPHIGHALL_$$_COMPAREBINARY$TSTRINGLIST$LONGINT$LONGINT$$LONGINT ()
#13 0x000000000000000c in  ()
#14 0x0000000000558a8e in QUICKSORT_ITEMLIST_CONTEXT (ITEMS=     0x7fffdfc3c240, ITEMCOUNT=140736931958400, ITEMSIZE=16, COMPARER=     {function  (POINTER, POINTER, POINTER) : LONGINT} 0x7fffffffc750, CONTEXT=
    0x7fffffffc780) at ../inc/sortbase.pp:222
#15 0x00007fffdfc3c240 in  ()
#16 0x0000000000000010 in  ()
#17 0x000000000053abb0 in
CLASSES_$$_TSTRINGLIST_CUSTOMSORT_COMPARER$POINTER$POINTER$POINTER$$LONGINT ()
#18 0x00007fffffffc780 in  ()
#19 0x00007fffdf0017a0 in  ()
#20 0x00000000000000b0 in  ()
#21 0x00007fffdf4f5f00 in  ()
#22 0x000000000053ace2 in CUSTOMSORT (this=0x7fffded60e80, COMPAREFN=     {function  (TSTRINGLIST, LONGINT, LONGINT) : LONGINT} 0x0, SORTINGALGORITHM=0x7fffded63018) at ../objpas/classes/stringl.inc:1668 #23 0x00007fffdf4f5f00 in  ()
#24 0x00007fffdfc3c240 in  ()
#25 0x0000000000e8d430 in
SYNEDITMARKUPHIGHALL_$$_COMPAREBINARY$TSTRINGLIST$LONGINT$LONGINT$$LONGINT ()
#26 0x0000000000000003 in  ()
#27 0x0000000000e8d430 in
SYNEDITMARKUPHIGHALL_$$_COMPAREBINARY$TSTRINGLIST$LONGINT$LONGINT$$LONGINT ()
#28 0x00007fffdf4f5f00 in  ()
#29 0x0000000001b51b78 in VMT_$CLASSES_$$_TSTRINGLIST () #30 0x000000000053ab9e in CUSTOMSORT (this=0x1b18e80, COMPAREFN=     {function  (TSTRINGLIST, LONGINT, LONGINT) : LONGINT} 0x0)     at ../objpas/classes/stringl.inc:1628
#31 0x00007fffffffc890 in  ()
#32 0x0000000000e8da5e in BUILDDICTIONARY (this=0x7fffdf5574c0) :959
#33 0x0000000000e8f558 in SEARCH (this=0x7fffdf5574c0, ATEXT=

Reply by email

Nikolay Nikolov
to C Western
C Western wrote
I suspect the new sorting routines need some work - lazarus compiled with the latest trunk hangs on start up, and it looks like an infinite loop in sorting. Stack trace below.

Even though the sort routine did slightly change, I believe this exposes a bug in lazarus. The CompareBinary routine in syneditmarkuphighall.pp returns -1 when the strings are equal, while it should return 0 in this case. This is like having two elements in the array, for which (a<b) and (b<a) are both true at the same time. The Compare function, passed to the sort algorithms must satisfy the mathematical properties of comparisons, otherwise the result is undefined (whether it should results in a hang (like in this case), or in a bad sort (like in the previous variation of the algorithm) is a separate discussion).

The attached patch fixes this.

Show quoted text 66 lines
Colin #0  0x0000000000422167 in DECLOCKED (L=2) at ../x86_64/x86_64.inc:709 #1  0x000000000042c325 in fpc_ansistr_decr_ref (S=0x2)     at ../inc/astrings.inc:148 #2  0xfffffffffffffffa in  () #3  0x0000000000e8d67b in COMPAREBINARY (LIST=0x7fffdf4f5f00, INDEX1=6, INDEX2=     7) at syneditmarkuphighall.pp:807 #4  0x000000000053abf6 in TSTRINGLIST_CUSTOMSORT_COMPARER (ITEM1=     0x7fffded60e88, ITEM2=0x1, CONTEXT=0x1b18e80)     at ../objpas/classes/stringl.inc:1642 #5  0x0000000001b63530 in TC_$SORTBASE_$$_QUICKSORT () #6  0x0000000000558b60 in QUICKSORT (parentfp=0x7fffffffc740, L=2, R=7)     at ../inc/sortbase.pp:182 #7  0x00007fffffffc740 in  () #8  0x000000000043aeb5 in SYSGETMEM (SIZE=140736931958424)     at ../inc/heap.inc:1082 #9  0x0000000000000003 in  () #10 0x000000000000000b in  () #11 0x0000000001b63530 in TC_$SORTBASE_$$_QUICKSORT () #12 0x0000000000e8d430 in SYNEDITMARKUPHIGHALL_$$_COMPAREBINARY$TSTRINGLIST$LONGINT$LONGINT$$LONGINT () #13 0x000000000000000c in  () #14 0x0000000000558a8e in QUICKSORT_ITEMLIST_CONTEXT (ITEMS=     0x7fffdfc3c240, ITEMCOUNT=140736931958400, ITEMSIZE=16, COMPARER=     {function  (POINTER, POINTER, POINTER) : LONGINT} 0x7fffffffc750, CONTEXT=     0x7fffffffc780) at ../inc/sortbase.pp:222 #15 0x00007fffdfc3c240 in  () #16 0x0000000000000010 in  () #17 0x000000000053abb0 in CLASSES_$$_TSTRINGLIST_CUSTOMSORT_COMPARER$POINTER$POINTER$POINTER$$LONGINT () #18 0x00007fffffffc780 in  () #19 0x00007fffdf0017a0 in  () #20 0x00000000000000b0 in  () #21 0x00007fffdf4f5f00 in  () #22 0x000000000053ace2 in CUSTOMSORT (this=0x7fffded60e80, COMPAREFN=     {function  (TSTRINGLIST, LONGINT, LONGINT) : LONGINT} 0x0, SORTINGALGORITHM=0x7fffded63018) at ../objpas/classes/stringl.inc:1668 #23 0x00007fffdf4f5f00 in  () #24 0x00007fffdfc3c240 in  () #25 0x0000000000e8d430 in SYNEDITMARKUPHIGHALL_$$_COMPAREBINARY$TSTRINGLIST$LONGINT$LONGINT$$LONGINT () #26 0x0000000000000003 in  () #27 0x0000000000e8d430 in SYNEDITMARKUPHIGHALL_$$_COMPAREBINARY$TSTRINGLIST$LONGINT$LONGINT$$LONGINT () #28 0x00007fffdf4f5f00 in  () #29 0x0000000001b51b78 in VMT_$CLASSES_$$_TSTRINGLIST () #30 0x000000000053ab9e in CUSTOMSORT (this=0x1b18e80, COMPAREFN=     {function  (TSTRINGLIST, LONGINT, LONGINT) : LONGINT} 0x0)     at ../objpas/classes/stringl.inc:1628 #31 0x00007fffffffc890 in  () #32 0x0000000000e8da5e in BUILDDICTIONARY (this=0x7fffdf5574c0) :959 #33 0x0000000000e8f558 in SEARCH (this=0x7fffdf5574c0, ATEXT= _______________________________________________ fpc-devel maillist  -  http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel

Reply by email

C Western
to Nikolay Nikolov
Nikolay Nikolov wrote 19 lines
On 2/3/19 11:22 PM, C Western wrote: > I suspect the new sorting routines need some work - lazarus compiled > with the latest trunk hangs on start up, and it looks like an > infinite loop in sorting. Stack trace below. Even though the sort routine did slightly change, I believe this exposes a bug in lazarus. The CompareBinary routine in syneditmarkuphighall.pp returns -1 when the strings are equal, while it should return 0 in this case. This is like having two elements in the array, for which (a<b) and (b<a) are both true at the same time. The Compare function, passed to the sort algorithms must satisfy the mathematical properties of comparisons, otherwise the result is undefined (whether it should results in a hang (like in this case), or in a bad sort (like in the previous variation of the algorithm) is a separate discussion). The attached patch fixes this.

I am happy to confirm lazarus starts with the patch applied.

Many thanks

Colin

Reply by email

Mattias Gaertner
to Nikolay Nikolov: Even though the sort routine did slightly change, I believe this exposes a bug in…
Show quoted text 17 lines
On 2/3/19 11:22 PM, C Western wrote: > I suspect the new sorting routines need some work - lazarus > compiled with the latest trunk hangs on start up, and it looks like > an infinite loop in sorting. Stack trace below. Even though the sort routine did slightly change, I believe this exposes a bug in lazarus. The CompareBinary routine in syneditmarkuphighall.pp returns -1 when the strings are equal, while it should return 0 in this case. This is like having two elements in the array, for which (a<b) and (b<a) are both true at the same time. The Compare function, passed to the sort algorithms must satisfy the mathematical properties of comparisons, otherwise the result is undefined (whether it should results in a hang (like in this case), or in a bad sort (like in the previous variation of the algorithm) is a separate discussion). The attached patch fixes this.

Thanks. Applied.

Mattias

Reply by email