[fpc-devel] New sorting routines

[Nikolay Nikolov]

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.

>
> 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)
>     at syneditmarkuphighall.pp:959
> #33 0x0000000000e8f558 in SEARCH (this=0x7fffdf5574c0, ATEXT=
>
>
> _______________________________________________
> fpc-devel maillist  -  fpc-devel at lists.freepascal.org
> http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
-------------- next part --------------
A non-text attachment was scrubbed...
Name: syneditmarkuphighall.pp.patch
Type: text/x-patch
Size: 454 bytes
Desc: not available
URL: <http://lists.freepascal.org/pipermail/fpc-devel/attachments/20190204/703767a3/attachment.bin>