[fpc-devel] Questions on TStringList.Find change (Mantis 28744)

[David Jenkins]

On 3/22/16 4:15 AM, Michalis Kamburelis wrote:
> 2016-03-22 8:18 GMT+01:00 Ondrej Pokorny <lazarus at kluug.net>:
> This would be my preference too --- just raise the exception. Or just
> fallback on linear search using IndexOf, if the list is not known to
> be sorted.
>
> In my experience, it's a common bug right now to call Find on an
> unsorted list. I stumbled on this bug, and I saw other people
> stumbling on it too. Even though it's clearly documented that "Find
> only works on sorted lists", it's still a problem --- you just don't
> check documentation for something as obvious as "Find". Just like you
> don't check documentation of "IndexOf", "Add" and other
> seemingly-obvious methods. A nice API would call the method
> "FindInSorted" if the method was assuming the list to be sorted,
> right?
>
> The case when the list is already known to be naturally sorted should
> be marked by the caller, e.g. by an optional parameter to Find (like
> AssumeAlwaysSorted=true), or by using special method to assume a
> sorted list. Also, setting "Sorted := true" on an already-sorted list
> should be rather fast (quicksort on an already-sorted list should go
> fast, in linear time; sure, it's not zero time, but still it's often
> fast enough).
>
> But the default should really be safer (IMHO), which is either
> 1. "raise exception" (predictable, and easy to catch the bug ---
> developer will either make it sorted, or use IndexOf instead), or
> 2. fallback to linear search (so it always works correctly, but with a
> speed penalty if you forgot to sort).
>
> Delphi behavior in this case (blindly trust the list is already
> sorted) is just a bug IMHO, and this case warrants breaking Delphi
> compatibility.
>
> Also: for consistency, it would be great to apply any fixes developed
> here also to FGL unit containers, as the TFPSMap.Find shares the same
> problem: it's name is simply "Find", and it assumes the contents to be
> Sorted.
>
> Regards,
> Michalis
> _______________________________________________
> fpc-devel maillist  -  fpc-devel at lists.freepascal.org
> http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
I'd also be fine with this suggestion of the optional 
AssumeAlwaysSorted=true parameter as a way of maintaining the particular 
functionality we are interested in (instead of the ManualSorted property).

David