I just ran across the change that checks Sorted at beginning of find and exits if Sorted = False. This has caused some problems for us

a) We have lists that are sorted manually and we'd like to continue keeping them sorted manually (and be able to call .insert()). This means not setting the sorted flag. But without setting 'sorted' we can no longer use find. We are sharing code between VCL and FPC - delphi compatibility has been broken.

b) The change, in my opinion, hasn't solved the unpredictable response problem. There is still nothing to indicate to a caller that they have called the function inappropriately i.e. they do not know why find has returned false.

Furthermore the documentation also indicates that if false is returned then 'Index' will contain the position where the string should be inserted. Index used to at least be within the range of FCount or 0. Now the value 'Index' is even more indeterminte as the code exits before Index has been set to anything. It has gone from possibly placing a string at a wrong location to possibly causing a crash with index out of range.

It could be argued whether this is worse but it certainly doesn't seem to have made the situation any better for people blindly misusing Find an unsorted list - while at the same time breaking Delphi compatibility and the option to manually keep lists sorted.

Thoughts?

David Jenkins

We can introduce a property which disables the check, if you want.

Michael.

That would work for us. Our other option is to pull the check out in our local version of stringl.inc. But we prefer to maintain as few local patches as possible.

However.......... now that I've thought about it some more. That change would be nice and all for us but doesn't it just muddle the picture even more for anyone else using the code?

I'm feeling tempted to argue against my side a little. If the change is correct i.e. makes for better code or behavior then it should stay and we'll go ahead and take it out in our local files if we don't like it (we'll grumble at having to maintain a local patch be we already have a few of those).

My thought is that it doesn't make for better code or behavior while at the same time breaking Delphi compatibility. Delphi compatibility isn't the golden standard but it seems any breakage should be for a good reason.

David

The reason for this behaviour is that find needs to be sure that the list is sorted. If it thinks the list is not sorted, the result cannot be guaranteed to be correct, and this is an error condition.

What I don't understand about these discussions is:

TStringList is just one possible implementation of TStrings. It is only there for your ease of use.

If you don't like it, you can use another one. You can find several. There is one in inifiles, the LCL probably also contains a couple.

If all APIs work with TStrings, then they don't care what TStrings descendent you use. So you are free to use one that does whatever you want.

Anyone declaring an API that explicitly expects TStringList, is simply doing something wrong, in my view.

This is Object Pascal for a reason, after all.

Michael.

Michael Van Canneyt wrote

The reason for this behaviour is that find needs to be sure that the list is sorted. If it thinks the list is not sorted, the result cannot be guaranteed to be correct, and this is an error condition.

Then it should raise an exception, not silently exit.

IMO, it's a bad change because it forces us to set Sorted to true and deal with the extra overhead that that introduces even for lists that we know are sorted externally. The fact that it breaks Delphi compatibility for little gain is another knock against it.

TStringList is just one possible implementation of TStrings. It is only there for your ease of use. If you don't like it, you can use another one. You can find several. There is one in inifiles, the LCL probably also contains a couple.

Why would you possibly think that it's better for us to use a TStrings implementation from IniFiles rather than the one in Classes when we want to store a specific list of strings? That's what the core RTL classes are for.

If all APIs work with TStrings, then they don't care what TStrings descendent you use. So you are free to use one that does whatever you want.

Nobody said anything about declaring APIs. We have concrete instances of TStringList that we're creating and encapsulating in our classes. We're not passing in random TStrings/TStringList instances to these things.

Regardless, Find is introduced in TStringList, not TStrings.

I understand the need for the list to be sorted and agree that calling find on an unsorted list is an error condition.

I am not convinced that current change deals with that well.

For one, the Sorted flag and actual state of the list are not directly linked. I can manually sort the list so that Find binary search will work just fine. But Find will exit before the binary search can occur - without any indication why.

Ff the list is not sorted, I don't think the current change creates a true error response to the error condition. Returning False indicates string not found - not an error. Furthermore I think the change makes the error condition worse by leaving values in Index that can cause crashes beyond just the error condition of not finding the right string.

Raising an exception if not Sorted would be an error response. Or providing some feedback to the user to indicate the difference between not found and error condition.

We can use our own descendant of TStrings or we could apply a local patch to TStringList as already mentioned. So we can actually create a work around. Our interest was in pointing out a change in fpc code that we thought was a regression rather than an improvement.

But you agree that if Find is called on an unsorted list, bogus data will be returned ? Or, worse, an never-ending loop may occur ? In short, as you say, an "error condition" can ensue without you knowing it.

That is a bug.
So, in my opinion (and of some others), Find is implemented buggy in Delphi.

Consider the buggyness a given in what follows.

If we consider something a bug in Delphi, we do not copy the bug.

You happen to rely on this buggy behaviour. This is of course unfortunate.

I attempted to fix this bug using a not too invasive method. Originally I simply wanted to raise an exception, but that was deemed too invasive.

There are now several options:
1. I change the code to raise an exception instead (as was my original plan)
2. I change the code to resort to a linear search if sorted is false.
3. I introduce a boolean property that determines whether Find does any check. By default the check will be done, to warn people they're doing something stupid. If they override the check, we can assume they know what they are doing.
4. Combine 1 and 3.

Or,

5. You override sort so it does nothing. It is virtual. You can then set sorted to True, no sort will occur, and find will do it's job.

6. You use another TStringList where you change find to suit your needs. All it takes for you is to copy the implementation, you can keep the same name, and insert the unit after the classes unit in places where you need it.

It's your call which of the 5 methods is used.

But one thing is sure: we're not reverting the behaviour back to the buggy behaviour.

Michael.

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.

Ondrej

2016-03-22 8:18 GMT+01:00 Ondrej Pokorny :

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

#1 is what Zoe Peterson (my coworker) has suggested as well. Without that exception (as the code now is) there is no warning issued just an ambiguous return of False. Which means that the code is still buggy as the user could assume that the Index value points to next insert spot and instead it is out of range and causes a crash. Setting Index value to -1 would be a better indicator of bad usage than just returning False (with raising an exception still being the best warning).

Keep in mind though that being able to call find on a manually sorted list (Sorted true) is not buggy behavior (this is the Delphi compatibility that we are interested in maintaining). In which case adding in #3 would be necessary. So I guess I am for #4.

I would suggest that the added boolean flag be named to indicate that the list is manually sorted (ManualSorted ?) rather than the flag being just a 'bypass check' indicator. The check in Find would be "if not Sorted or not ManualSorted then raise exception'. But that's just a personal preference and not something that I feel extra committed to.

My second choice would be #1 by itself.

David

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

Find method must find an item in the list. Whether the list is sorted or not, whether the binary search optimization can be applied or not - are implementation details.

Find method should either:
1) Raise exception if list is not sorted,
2) Use IndexOf method if the list is not sorted (preferable).

Adding optional parameters is hardly a good solution. Instead, add a FindSorted method.

To summarise:

procedure Find(const S: string; out Index: Integer):Boolean;
begin
  if Sorted then
    Result := FindSorted(S, Index);
  else
  begin
    Index := IndexOf(S);
    Result := (Index >= 0);
  end;
end;
procedure FindSorted(const S: string; out Index: Integer):Boolean;
begin
  if not Sorted then
    raise Exception.Create('List must be sorted');
  // search logic here...
end;

Denis

Here we disagree.
It IS buggy behavior. Delphi is not sacrosanct, it does contain bugs like any software. This is one of them.

(*
This is not idle talk:
I'm trying to report 2 serious bugs in Delphi Seattle, only to find that the bugtracker (ironically called quality :) ) is not working :/

Well, it can happen to anyone, I guess.
*)

That aside: I will probably go for 1 or 4.

Michael.

PS. And if you allow me to express wonder:
Given that you are apparently the maker of beyond compare, I'm doubly surprised to see you use an all-purpose container class as TStringlist, instead of writing your own...

Please consider the following implementation logic, I think it covers all angles:

procedure Find(const S: string; out Index: Integer):Boolean;
begin
  if Sorted then
    Result := FindSorted(S, Index);
  else
  begin
    Index := IndexOf(S);
    Result := (Index >= 0);
  end;
end;
procedure FindSorted(const S: string; out Index: Integer; CheckSorted:
Boolean = True):Boolean;
begin
  if CheckSorted and not Sorted then
    raise Exception.Create('List must be sorted');
  // search logic here...
end;

Denis

No one here holds Delphi up on a pedestal - least of all me. My viewpoint is completely practical/funcitonal - I have to make our code base work with FPC/LCL and VCL. Given the way we use find functionality (with a mixture of naturally sorted and automatically sorted lists) it has ceased to work with both (it did previously). I want to fix that as elegantly and as effectively as possible. Making suggestions for FPC improvement is a side effect - and as we both agree TStringList.Find can use some improvement.

And I am fine disagreeing. My definition of 'bug' is again completely functional. If I knowingly stick in a naturally sorted list into Find(), the code operates as expected without error, and I get the desired result. Both user and producer operated as expected - by intention not by accident. I do not see a bug there.

If I stick in a non-sorted list (knowingly or unknowingly) then results are undefined. Is that user error or buggy code? It certainly isn't robust code and can be improved. Label it as you like I am only interested it seeing it improved.

As we have all pointed out there is some inherent issues with a function traditionally named 'find' that essentially hides input requirements (again label that as you like). Michalis has pointed out that TFSMap.Find has a similar issue.

The other weakness I see in the current traditional implementation (Delphi and FPC) is that the 'Sorted' flag is somewhat loosely coupled to the actual state of the list i.e. it can be in a sorted state and the flag does not reflect me it seems that the flag really means 'auto sort this please'. Once it is enabled the code will sort and maintain sort. But the code is also intended to support naturally sorted lists and not induce the overhead of auto sort. In that situation the sorted property has nothing to do with the actual state of the list. IMO better designed code would account for this.

Perhaps it should have been called TStringSortedList and enforced auto sort all the way through instead of purposely handling both sorted and unsorted lists.

As to our decision to use TStringList directly. Whether we use it directly or create our own doesn't fix the code that we all agree is insufficiently robust, 'buggy', 'prone to allow bad use', or whatever label you want to use. So I find your concern touching but not applicable to the TStringList has provided exactly what we needed (and we have been careful to only pass sorted - natural or automatic - to it). Why would we purposely rebuild the wheel. Libraries exist for just this.

And that's all I have to say about that (as Forrest Gump said). Thanks for the discussion.

David

Yes.

"by intention not by accident."
Clearly this is not the case, given the warning in Delphi's help.

And as a component developer I have a different point of view. A component should enforce correct behaviour and conditions.

No argument there.

Perhaps it should have been called TStringSortedList and enforced auto sort all the way through instead of purposely handling both sorted and unsorted lists.

That's not very handy, I switch sort on and off regularly. This approach would require me to re-create classes and copy data.

Yes and no, they are general purpose classes:
In general, I don't believe in the 'one size fits all' approach, and think an argument can be made for custom classes in case of specialized needs. (which is not to say that general purpose classes should not strive for the best possible implementation)

In each case, there is no argument that the code can be improved.

We'll sort something out in the end.

Is your preference for an extra argument to Find() or an additional property ?

Michael.

Denis,

I like how this solves the issue of calling find on truly unsorted lists. My only quibble with this is that 'Sorted' still does not reflect the actual state of the list. For a naturally sorted list there is still unnecessary calls to sort both in your suggested code above and in the existing code (if sorted is set). Can that be handled as well? 'Sorted' right now is a request and an expression of state. As an expression of state it is only valid if the request has been first made.

David

I do not see it as a warning. It is a statement of requirement on the input. By passing in a naturally sorted list I am complying with that requirement (the requirement is only that it be sorted not how it is sorted). So the code works not by accident but because I have complied with the requirement and the code functions properly. Adding a check to make sure I comply with the requirement makes the code more robust and is a great thing to do. Checking for 'Sorted' actually doesn't always do this.

The problem is that the Sorted flag is both a request and a loose statement of state. My list can be sorted without me requesting (through the flag) that the code sort and maintain the list. But throughout the code (Delphi and FPC) 'Sorted' is treated as an accurate mirror of list state whether the list is automatically sorted, naturally sorted, or not sorted at all (it can't tell the difference between the latter two). In the case of naturally sorted this state can be inaccurate (Sorted not set) and so some code won't run or accurate (Sorted set) but requesting unneeded actions.

To me, after spending this amount of time thinking about it, this calls out for improvement as much as the concern about an accidental call to Find with an unsorted list. Though I understand that getting an erroneous result, unknowingly, is far more critical than inefficient code. However, for us we are parsing a whole lot of text strings - running through unneeded calls to sort (no matter how fast it might be on an already sorted list) adds up. And not running at all is a failure of function.

I do not have a preference.

I like the auto param because 1) it is simple 2) doesn't change the interface for code that doesn't care and 3) solves the base problem. However, it doesn't decouple "Sorted" request from sorted state.

An additional property could solve the base problem and clarify what the list state actually is. Though additional code would need to change to take advantage of the clarity.

Maybe something (not extensibly thought on) like

Sorted: boolean read GetSorted write SetSorted
NaturalSorted: boolean read FNaturalSorted write FNaturalSorted

SetSorted(AValue: Boolean)
begin
FAutoSorted := AValue;  // This is the request to auto sort or not
end
GetSorted: Boolean
begin
Result := FAutoSorted or FNaturalSorted  // This gets the state right
for both Auto and Natural (as long is Natural truly is :D)
end

or have a ListType property that is ltAutoSort, ltNaturalSort, ltNone

and GetSorted = ListType in [ltAutoSort, ltNaturalSort]

The additional properties (not necessarily implemented as above) is attractive as it seems like a more complete solution. There is still the chance of an unsorted list getting by.

Adding Denis' solution in .Find along with the new properties would narrow the window of unsorted lists coming through while still allowing bypass of sorting code for explicitly set Naturally sorted lists (lists with NaturallySorted=True but not actually sorted could still sneak through).

All the above are fine with me.

David

David Jenkins wrote

or have a ListType property that is ltAutoSort, ltNaturalSort, ltNone

I think this idea is probably the best alternative.

Michael.

I don't think "natural sort" is a good name, because it has a specific meaning (https://en.wikipedia.org/wiki/Natural_sort_order ). ltAssumeSorted or so seems better.

Jonas

I had the same thought, and was thinking of ltUserSorted.

Michael.

or better something concise like ltAuto,ltUser,ltNone.

Michael.

Michael Van Canneyt wrote

or better something concise like ltAuto,ltUser,ltNone.

It may make more sense to call it ListSortType (as opposed to ListType):
   TListSortType = (lstNone, lstAuto, lstManual);

Something like this could work (prototype code):

=======================================================
function TStringList.GetSorted: Boolean;
begin
   Result := (FSortType = lstAuto);
end;
procedure TStringList.SetSorted(Value: Boolean);
begin
   if Value xor (FSortType= lstAuto)then
   begin
     if Value then
begin
       Sort;
       FSortType:= lstAuto;
     end
     else
FSortType:= lstNone;
   end;
end;
procedure TStringList.SetSortType(Value: TListSortType);
begin
   if FSortType Value then
   begin
     if Value = lstAutothen
Sort;
     FSorted := Value;
   end;
end;
procedure TStringList.Find(const S: string; out Index: Integer):Boolean;
begin
   if FSortType  lstNonethen
     Result := FindSorted(S, Index);
   else
   begin
     Index := IndexOf(S);
     Result := (Index >= 0);
   end;
end;
procedure TStringList.FindSorted(const S: string; out Index:
Integer):Boolean;
begin
   ifFSortType= lstNonethen
     raise Exception.Create('List must be sorted');
   // sorted search logic here...
end;
=======================================================

An alternative solution, without adding TListSortType:

=======================================================
procedure Find(const S: string; out Index: Integer; *AssumeSorted:
Boolean = False*):Boolean;
begin
   if *AssumeSorted* or Sorted then
     Result := FindSorted(S, Index, False);
   else
   begin
     Index := IndexOf(S);
     Result := (Index >= 0);
   end;
end;
procedure FindSorted(const S: string; out Index: Integer; *CheckSorted:
Boolean = True*):Boolean;
begin
   if *CheckSorted* and not Sorted then
     raise Exception.Create('List must be sorted');
   // search logic here...
end;
=======================================================

Denis

I went for TStringsSortStyle

This should be
   Result in [lstAuto, lstManual];
I am in agreement with David Jenkins that Sorted should reflect the actual state;
no matter how this state was reached.

I raise an exception here. Find is for sorted lists.

I have an implementation ready, as soon as all tests are done I will commit it.

Michael.

I have implemented a new property

  TStringsSortStyle = (sslNone,sslUser,sslAuto);
  Property SortStyle : TStringsSortStyle Read FSortStyle Write SetSortStyle;

I assume the meaning is clear.

- Sorted is true if SortStyle is in [sslUser,sslAuto], so it reflects actual state.

- Setting sorted to True is equivalent to setting SortStyle = sslAuto

- Setting sorted to false is equivalent to setting SortStyle = sslNone

- Find will work on one of those values, but it will raise an exception if sortstyle = sslnone

- Add will put a new string on the 'correct' place if SortStyle=sslAuto

- Insert will raise an error (as it was) if SortStyle=sslAuto.

Michael.

I think you might have missed updating a file:

bootstrap/ppcx64 -Ur -gl -Ur -Xs -O2 -n -Fi../inc -Fi../x86_64 -Fi../unix -Fix86_64 -FE.
-FU/home/ctcmw/fpc/trunk.w/fpcsrc/rtl/units/x86_64-linux -Cg -dx86_64 -dDEBUG -dRELEASE -Fi../objpas/classes ../unix/classes.pp stringl.inc(1447,29) Error: Identifier not found "SErrFindNeedsSortedList"

On a related matter - is this insensitive to changes in the system/rtl sort order? I had a difficult to find problem recently where I had some code in an initialization section that prepared a sorted string list (or something like it). The use of this in the main program then broke when I added another package to the program (in fact fpSpreadsheet) that forced inclusion of cwstrings to the program, but implicitly after the initialization discussed. This was easily fixed by adding cwstrings at the top of the lpr file. I am not sure if this is something that can be more generally fixed, but if there is anything that can reduce the possibilities for confusion that would be good.

Colin

Correct. Committed the file.

This is unrelated, and has to do with the fact that the stringlist by default is sorted case-insensitively.

Michael.

Michael,

I have checked out this code and imported it into our code base. It works great. Thank you very much. In addition the work of searching through our code and making sure we are setting SortStyle correctly has uncovered a bug in our usage. So additional thanks :D

David Jenkins