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

[Michalis Kamburelis]

2016-03-22 8:18 GMT+01:00 Ondrej Pokorny <lazarus at kluug.net>:
>
> On 22.03.2016 8:01, Michael Van Canneyt wrote:
>>
>> 1. I change the code to raise an exception instead (as was my original plan)
>
>
> This is the way to go. False should be returned if nothing was found.
> In case there are problems with starting parameters (or string list status or whatever), an exception should be thrown instead of returning false as if nothing was found.
>

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