Recent

Author Topic: Iterator on non-existing structure  (Read 1850 times)

jollytall

  • Sr. Member
  • ****
  • Posts: 376
Iterator on non-existing structure
« on: January 14, 2025, 07:19:02 pm »
Today I had a very unfortunate error (i.e. very expensive). I know it was my error, but my question if it would be possible to avoid next time?

If I have a dynamic array and it's nil (what I think is equal to when the length is zero), I can iterate through it, no error:
Code: Pascal  [Select][+][-]
  1. type
  2.   tC = class
  3.     end;
  4.   tCs = array of tC;
  5. var
  6.   C : tC;
  7.   Cs : tCs;
  8. begin
  9. Cs := nil;
  10. for C in Cs do
  11.   ;
  12. end.
works fine. However if I use tFPGObjectList, like
Code: Pascal  [Select][+][-]
  1. type
  2.   tC = class
  3.     end;
  4.   tCs = specialize tFPGObjectList<tC>;
  5. var
  6.   C : tC;
  7.   Cs : tCs;
  8. begin
  9. Cs := nil;
  10. for C in Cs do
  11.   ;
  12. end.
then it crashes. I know an array is not the same as an object list, but if the iterator of an array can first check if it exists, would it be possible to do the same for the object list? Is it a difficult change request?

Btw. I know I can easily do
Code: Pascal  [Select][+][-]
  1. if assigned(Cs) then
  2.   for C in Cs do
  3.     ;
  4.  
but it would be more elegant not to do that.

TRon

  • Hero Member
  • *****
  • Posts: 3946
Re: Iterator on non-existing structure
« Reply #1 on: January 14, 2025, 07:25:56 pm »
then it crashes. I know an array is not the same as an object list, but if the iterator of an array can first check if it exists, would it be possible to do the same for the object list? Is it a difficult change request?
Quick question. Where do you think the iterator (enumerator)  for the objectlist comes from, e.g. where is that iterator defined ? Exactly, in the object list so a chicken-egg situation.
I do not have to remember anything anymore thanks to total-recall.

Warfley

  • Hero Member
  • *****
  • Posts: 1864
Re: Iterator on non-existing structure
« Reply #2 on: January 14, 2025, 07:47:07 pm »
Well the fix would actually be quite trivial:
Code: Pascal  [Select][+][-]
  1. function TFPGListEnumerator.MoveNext: Boolean;
  2. begin
  3.   if not assigned(FList) then
  4.     Exit(False);
  5.   inc(FPosition);
  6.   Result := FPosition < FList.Count;
  7. end;  
In fgl.pas line 902. The question is if thats actually desireable, as it may hide errors (use after free, use of uninitialized variable, etc.).

Because crashes are actually a good thing, they are a very visible and easy to debug error. Whats way worse is having an error that the program is just spitting out wrong stuff but does so completely silently because it tries to be "smart" and just swallow errors silently

TRon

  • Hero Member
  • *****
  • Posts: 3946
Re: Iterator on non-existing structure
« Reply #3 on: January 14, 2025, 07:55:00 pm »
Well the fix would actually be quite trivial:
Oh, IC. The other way around. I did not consider that. Nice.

Quote
The question is if thats actually desireable, as it may hide errors (use after free, use of uninitialized variable, etc.).
...
That is actually a very good point. No idea how to answer for this case.
I do not have to remember anything anymore thanks to total-recall.

jollytall

  • Sr. Member
  • ****
  • Posts: 376
Re: Iterator on non-existing structure
« Reply #4 on: January 15, 2025, 10:04:53 am »
The question is if thats actually desireable, as it may hide errors (use after free, use of uninitialized variable, etc.).
I see you point, but I have two reasons why it would be a good solution:

First, as in my example, if I have a bunch of variable number of items (can be anything from class instances to simple integers), I need to store them somewhere. The simple way is to put them into a dynamic array. There, if the array does not exist, it is equivalent to having zero elements in it, so, as in the example, the iterator works. If the items are regularly deleted, added and the number of them is large, then it is not too economic to move all items in the array when one is removed. So then a linked list is better, like tFPGObjectList. It seems logic that it works the same way. (When I changed from the array kind of implementation to the object list, I - incorrectly - also assumed it.)

Second, from a human point of view, what does it mean to have a code like
Code: Pascal  [Select][+][-]
  1. for C in Cs do
  2.   DoSomething(C);
?
For me it means that for all the elements that are stored in Cs we should do something. If Cs does not exist at all then obviously there are no elements in it, so there is no item to do something with. It is not necessarily an error. It is more a question of implementation.

Actually in my example Cs is a member of a class instance, where the class instance also has many siblings (other instances of the same class) also stored in an object list. Similarly to Cs for every instance I have Ds, Es, etc. When I create the instance X, it has got no C, D, or E items. There are three ways to handle it:
- Create Cs, Ds, Es, like
Code: Pascal  [Select][+][-]
  1. Cs := tCs.Create
and then the iterator would not fail, but I feel it an overkill, when most of the time X has no Cs, Ds, or Es, so why to create class instances in the heap for nothing.

- Set Cs, Ds, Es := nil and when I want to go through all elements, before using the iterator, I do the
Code: Pascal  [Select][+][-]
  1. if assigned(Cs) then
check. It works but seems an unnecessary extra step that could be included in the original class.

- Set them to nil (as above) and check it in the iterator. It can be done by the developer (this is why I raised it here), or it could be done somewhere during the specialization, but as I see from Warfley's elegant solution it is not even in tFPGObjectList, but in tFPGListEnumerator, what would not be that easy to do.

Warfley

  • Hero Member
  • *****
  • Posts: 1864
Re: Iterator on non-existing structure
« Reply #5 on: January 15, 2025, 01:44:17 pm »
The difference with arrays are, arrays are managed, they should never contain an undefined value. Nil is per Definition an empty array.

But lists are classes which are not managed, first an empty list is a list that is empty, the following works for arrays but not lists:
Code: Pascal  [Select][+][-]
  1. if length(TIntArray(nil)) > 0 then // works because nil is a defined value of array
  2. // But
  3. if TIntList(nil).Count > 0 then // crashes because nil is not a valid list
Your list being nil is not equivalent to the list being empty, there is no list.

Second, because lists are not managed, they can be in an undefined state, so you must always actively manage them:
Code: Pascal  [Select][+][-]
  1. var
  2.   sl1, sl2: TStringList;
  3. begin
  4.   sl1 := TStringList.Create;
  5.   sl1.Add('Hello SL1');
  6.   sl1.Free;
  7.  
  8.   sl2 := TStringList.Create;
  9.   sl2.Add('Hello SL2');
  10.   WriteLn(sl1.Text); // Use of sl1 after it has been freed above
  11.   sl2.Free;
  12. end;
This prints out Hello SL2, because after free it's in an undefined state. Even when initializing there is no guarantee it's nil:
Code: Pascal  [Select][+][-]
  1. procedure Uninitialized;
  2. var
  3.   sl: TStringList;
  4. begin
  5.   WriteLn(sl <> nil); // Prints true, sl seems assigned
  6. end;
  7.  
  8. procedure Smack;
  9. var
  10.   x: IntPtr;
  11. begin
  12.   x := -1;
  13.   WriteLn('X: ', x);
  14. end;
  15.  
  16. begin
  17.   Smack;
  18.   Uninitialized;
  19. end.
So you always need to initialize your lists. So why do you use nil at all? Just create them once, and if want to clear a list use the Clear method.
Once you never use them again, free them. By introducing nil as third state you make your program much more complex and it just results in more bugs (like the one you encountered).

That's exactly why C.A.R. Hoare called the invention of nil his billion dollar mistake, nil usually introduces more errors than it solves

Martin_fr

  • Administrator
  • Hero Member
  • *
  • Posts: 10799
  • Debugger - SynEdit - and more
    • wiki
Re: Iterator on non-existing structure
« Reply #6 on: January 15, 2025, 01:57:10 pm »
If you need nil (initialized to nil) to be iterate able, then you can write your own (sub-) classes, and add checks like
Code: Pascal  [Select][+][-]
  1. if self = nil then exit(NilToEmptyIterator);

Similar for count...

jollytall

  • Sr. Member
  • ****
  • Posts: 376
Re: Iterator on non-existing structure
« Reply #7 on: January 15, 2025, 02:04:53 pm »
@Warfley
Sure, I know arrays are different from lists.
Yes, I can also always make an instance of the list, but it is an overhead.

Imagine, my objects are companies and there are many lists within for employees, like engineers, cleaners, doctors, etc. All companies will have some employees in some of the lists, but most of the lists will be empty (an engineering company has no doctors, etc.). So, why to create all possible lists? It is enough to create the list when the company hires the first of that employee.
(I know this example could be solved other ways, but that is not the point.)

@Martin_fr
Where do you mean? My problem is that I have a descendant (specialized) class type from tFPGObjectList, but the iterator is from tFPGListEnumerator, but then it is extrawork to redefine tFPGObjectList descendant to use that.

Martin_fr

  • Administrator
  • Hero Member
  • *
  • Posts: 10799
  • Debugger - SynEdit - and more
    • wiki
Re: Iterator on non-existing structure
« Reply #8 on: January 15, 2025, 03:34:41 pm »
There are different locations that you can use.

Most generic: In "GetEnumerator" => and then instantiate a special enumerator class, that always returns false for "MoveNext".

Or in the enumerator, in MoveNext. (and anywhere else where the list is accessed, if such other places exist / and are called with MoveNext = False).

Full example:
Code: Pascal  [Select][+][-]
  1. program Project1;
  2.  
  3. uses fgl;
  4.  
  5. type
  6.  
  7.   { tMyFPGObjectList }
  8.  
  9.   generic tMyFPGObjectList<T: TObject> = class(specialize TFPGObjectList<T>)
  10.   private type
  11.     TMyFPGListEnumeratorSpec = class(specialize TFPGListEnumerator<T>)
  12.       function MoveNext: Boolean;
  13.     end;
  14.   public
  15.     function GetEnumerator: TMyFPGListEnumeratorSpec; inline;
  16.   end;
  17.  
  18. { tMyFPGObjectList.TMyFPGListEnumeratorSpec }
  19.  
  20. function tMyFPGObjectList.TMyFPGListEnumeratorSpec.MoveNext: Boolean;
  21. begin
  22.   Result := FList <> nil;
  23.   if Result then
  24.     Result := inherited MoveNext;
  25. end;
  26.  
  27. { tMyFPGObjectList }
  28.  
  29. function tMyFPGObjectList.GetEnumerator: TMyFPGListEnumeratorSpec;
  30. begin
  31.    Result := TMyFPGListEnumeratorSpec.Create(Self);
  32. end;
  33.  
  34. var
  35.   x: specialize tMyFPGObjectList<TObject>;
  36.   i: TObject;
  37.  
  38.  
  39. begin
  40.   x := nil;
  41.   for i in x do writeln('in loop');
  42.   readln;
  43. end.
  44.  

Of course you need all your lists to be changed to the new generic.

Also, any variable needs to be declared as the correct specialized type.
If you have variables like
Code: Pascal  [Select][+][-]
  1. var L: TFPSList;
  2. begin
  3.   L := TMySecializedFPGObjectList.create;

Then that wont work. Because GetEnumerator is not virtual.
However that already will not work, because TFPSList does not have a GetEnumerator.

Warfley

  • Hero Member
  • *****
  • Posts: 1864
Re: Iterator on non-existing structure
« Reply #9 on: January 15, 2025, 03:37:11 pm »
@Warfley
Sure, I know arrays are different from lists.
Yes, I can also always make an instance of the list, but it is an overhead.

The overhead of TFPGList is 40 bytes (+heap info). How many lists do you have 1000? Still just 40KB. The average low end cheap laptop has 8 gigabytes of RAM, 40kb is 0.0005% of total memory. If your program comes down to this level of optimizations, something went really wrong.

There is this very famous quote from Donald E. Knuth:
Quote
Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.

You already ran into a bug because you tried to optimize something that does not need to be optimized. Memory is cheap, bugs are expensive. Better have a tiny inefficiency but keep easier to maintain code

Martin_fr

  • Administrator
  • Hero Member
  • *
  • Posts: 10799
  • Debugger - SynEdit - and more
    • wiki
Re: Iterator on non-existing structure
« Reply #10 on: January 15, 2025, 03:41:20 pm »
Here is an alternative. It saves on creating the enumerator.
Code: Pascal  [Select][+][-]
  1. program Project1;
  2.  
  3. uses fgl;
  4.  
  5. type
  6.  
  7.   { tMyFPGObjectList }
  8.  
  9.   generic tMyFPGObjectList<T: TObject> = class(specialize TFPGObjectList<T>)
  10.   private type
  11.     TMyFPGListEnumeratorSpec = class(specialize TFPGListEnumerator<T>)
  12.       function MoveNext: Boolean;
  13.     end;
  14.   public
  15.     function GetEnumerator: TMyFPGListEnumeratorSpec; inline;
  16.   end;
  17.  
  18. { tMyFPGObjectList.TMyFPGListEnumeratorSpec }
  19.  
  20. function tMyFPGObjectList.TMyFPGListEnumeratorSpec.MoveNext: Boolean;
  21. begin
  22.   Result := Self <> nil;
  23.   if Result then
  24.     Result := inherited MoveNext;
  25. end;
  26.  
  27. { tMyFPGObjectList }
  28.  
  29. function tMyFPGObjectList.GetEnumerator: TMyFPGListEnumeratorSpec;
  30. begin
  31.   if Self = nil then exit(nil);
  32.   Result := TMyFPGListEnumeratorSpec.Create(Self);
  33. end;
  34.  
  35. var
  36.   x: specialize tMyFPGObjectList<TObject>;
  37.   i: TObject;
  38.  
  39.  
  40. begin
  41.   x := nil;
  42.   for i in x do writeln('in loop');
  43.   readln;
  44. end.
  45.  

Martin_fr

  • Administrator
  • Hero Member
  • *
  • Posts: 10799
  • Debugger - SynEdit - and more
    • wiki
Re: Iterator on non-existing structure
« Reply #11 on: January 15, 2025, 03:51:46 pm »
It appears that FPC may even test for GetEnumerator returning nil. In that case you don't need the custom MoveNext.

However I have not checked if that is documented or just happening in the example. So go and check the docs. And maybe it will be just the GetEnumerator to return nil.


@Warfley

Using nil as a value is not exactly uncommon.

The only thing is that normally you would do
Code: Pascal  [Select][+][-]
  1. If foo <> nil then for f in foo do ...;

Of course if you expect a lot of nil values then moving the nil check inside the method is fine too. There is a prominent example for that.
Code: Pascal  [Select][+][-]
  1. Foo.Free; // works for nil values too

Warfley

  • Hero Member
  • *****
  • Posts: 1864
Re: Iterator on non-existing structure
« Reply #12 on: January 15, 2025, 04:08:43 pm »
Using nil as a value is not exactly uncommon.

Doesn't make it necessarily a good thing. I highly recommend this talk by Tony Hoare: https://www.infoq.com/presentations/Null-References-The-Billion-Dollar-Mistake-Tony-Hoare/

Specifically from the 27 minute mark on null and why so many languages today move away from nullable types.

Null was just easy to implement but having an implicit bottom value as additional state makes programs much more complicated as it circumvents compiletime checking.

Martin_fr

  • Administrator
  • Hero Member
  • *
  • Posts: 10799
  • Debugger - SynEdit - and more
    • wiki
Re: Iterator on non-existing structure
« Reply #13 on: January 15, 2025, 04:52:01 pm »
Doesn't make it necessarily a good thing. I highly recommend this talk by Tony Hoare: https://www.infoq.com/presentations/Null-References-The-Billion-Dollar-Mistake-Tony-Hoare/

Specifically from the 27 minute mark on null and why so many languages today move away from nullable types.

Null was just easy to implement but having an implicit bottom value as additional state makes programs much more complicated as it circumvents compiletime checking.
Way to long a talk...

But minute 27, makes the point of "every ... null-able is a bad idea". With noticeable stress on every.

And well, any "one shoe fits all" tends to be bad. So having objects of which by the desired design do not need nil-ability and having those forcefully nil-able => that is a bad idea. Having the option of fine tuning what should and shouldn't => better. Matter of cost (as stated in the presentation: cheapness was the factor back then).


Also the question of: nil-ability being good or bad, surely depends on the handling of nil. If nil values are handled save (as FPC does for the implicit nil in ansistring and dyn array) then the judgement may differ (don't know if that is addressed in the video?).

As demonstrated => classes can be made nil save.
Compilers could check that nil is handled in every code path, if that was the desired solution. Matter of cost vs cheapness.



Further, the parts of the video I watched stated that the (or one of the?) problem was initialization. (i.e. to non nil). Of course completely uninitialized values are a bad idea. IMHO worse than nil.
Because you can handle nil. But you can't really handle $1ABC123 => which has no indicator if it is a valid value or random uninitialized value. Or dangling pointer.

Forbidding nil, seems (don't know / didn't watch enough of the video) just the extension of forbidding invalid pointer value => by completely taking the access to the pointer away.
But then removing pointers from the equation is a different discussion (it affects the availability of nil, but it is much more).

As long as you have pointer access, nil is likely the least issue.

Warfley

  • Hero Member
  • *****
  • Posts: 1864
Re: Iterator on non-existing structure
« Reply #14 on: January 15, 2025, 05:45:03 pm »
The solution that is currently pursued in most languages is requiring explicit nil checks. In ktolin for example, which is based on the jvm and therefore uses pointers implicitly everywhere, you must define a variable explicitly nullable, and then the type checker enforces that each access to the variable must first check that it is not null.

With such a provision the bug that started this thread could not have happened, while also not restricting the expressive power of the language.
The problem is not the existence of nil, it's that any class can be nil at any time and the Compiler/the type system cannot enforce checks against nil.

 

TinyPortal © 2005-2018