Lazarus

Free Pascal => General => Topic started by: Pasqualish on August 13, 2016, 07:38:36 am

Title: TFPList
Post by: Pasqualish on August 13, 2016, 07:38:36 am
I am looking at the code defined in ../rtl/objpas/classes/classesh.inc  for an TFPList class, in the situation when FPC_TESTGENERICS is false.  I don't understand how it works as it has a private member - FList: PPointerList - which is a pointer to a static array - array[0..MaxListSize - 1] of Pointer;   However, there is no constructor for this class. I don't see how FList gets a valid value or what it points to would be created.

Code: Pascal  [Select][+][-]
  1. Type
  2. PPointerList = ^TPointerList;
  3. TPointerList = array[0..MaxListSize - 1] of Pointer;
  4.  
  5. TFPList = class(TObject)
  6.   private
  7.     FList: PPointerList;
  8.     FCount: Integer;
  9.     FCapacity: Integer;
  10.     procedure CopyMove (aList : TFPList);
  11.     procedure MergeMove (aList : TFPList);
  12.     procedure DoCopy(ListA, ListB : TFPList);
  13.     procedure DoSrcUnique(ListA, ListB : TFPList);
  14.     procedure DoAnd(ListA, ListB : TFPList);
  15.     procedure DoDestUnique(ListA, ListB : TFPList);
  16.     procedure DoOr(ListA, ListB : TFPList);
  17.     procedure DoXOr(ListA, ListB : TFPList);
  18.   protected
  19.     function Get(Index: Integer): Pointer; {$ifdef CLASSESINLINE} inline; {$endif CLASSESINLINE}
  20.     procedure Put(Index: Integer; Item: Pointer); {$ifdef CLASSESINLINE} inline; {$endif CLASSESINLINE}
  21.     procedure SetCapacity(NewCapacity: Integer);
  22.     procedure SetCount(NewCount: Integer);
  23.     Procedure RaiseIndexError(Index: Integer);
  24.   public
  25.     Type
  26.       TDirection = (FromBeginning, FromEnd);
  27.     destructor Destroy; override;
  28.     Procedure AddList(AList : TFPList);
  29.     function Add(Item: Pointer): Integer; {$ifdef CLASSESINLINE} inline; {$endif CLASSESINLINE}
  30.     procedure Clear;
  31.     procedure Delete(Index: Integer); {$ifdef CLASSESINLINE} inline; {$endif CLASSESINLINE}
  32.     class procedure Error(const Msg: string; Data: PtrInt);
  33.     procedure Exchange(Index1, Index2: Integer);
  34.     function Expand: TFPList; {$ifdef CLASSESINLINE} inline; {$endif CLASSESINLINE}
  35.     function Extract(Item: Pointer): Pointer;
  36.     function First: Pointer;
  37.     function GetEnumerator: TFPListEnumerator;
  38.     function IndexOf(Item: Pointer): Integer;
  39.     function IndexOfItem(Item: Pointer; Direction: TDirection): Integer;
  40.     procedure Insert(Index: Integer; Item: Pointer); {$ifdef CLASSESINLINE} inline; {$endif CLASSESINLINE}
  41.     function Last: Pointer;
  42.     procedure Move(CurIndex, NewIndex: Integer);
  43.     procedure Assign (ListA: TFPList; AOperator: TListAssignOp=laCopy; ListB: TFPList=nil);
  44.     function Remove(Item: Pointer): Integer;
  45.     procedure Pack;
  46.     procedure Sort(Compare: TListSortCompare);
  47.     procedure ForEachCall(proc2call:TListCallback;arg:pointer);
  48.     procedure ForEachCall(proc2call:TListStaticCallback;arg:pointer);
  49.     property Capacity: Integer read FCapacity write SetCapacity;
  50.     property Count: Integer read FCount write SetCount;
  51.     property Items[Index: Integer]: Pointer read Get write Put; default;
  52.     property List: PPointerList read FList;
  53.   end;
Title: Re: TFPList
Post by: Thaddy on August 13, 2016, 08:28:00 am
The constructor is the default constructor for TObject which will initialize the structure.
Ultimately the ppointerlist is expanded on demand through ultimately setcapacity.
The capacity is checked and expanded/initialized when you add an Item to the list.
Hence the code is always valid.
Title: Re: TFPList
Post by: Pasqualish on August 13, 2016, 09:45:11 am
Thanks! 

I don't understand why the pointer type is defined to point to a static array as it doesn't appear that there is any limitation with regard to going past a static array bound. Although it does indirectly show what the allocation/re-allocation checks for as far as a size limit before raising an exception, so maybe it is for documentation.

Code: Pascal  [Select][+][-]
  1. {$R+}
  2.  
  3. type
  4.    SomeArrayType  = array [0 .. 1000] of Pointer;
  5.    PSomeArrayType = ^SomeArrayType;                                
  6.  
  7. var
  8.    myPointer : PSomeArrayType;
  9.    i : Cardinal;
  10. begin
  11.    New(myPointer);
  12.    for i := 0 to 2000 do
  13.       Inc(myPointer);
  14.    WriteLn('program ended normally');
  15. end.

outputs:
Quote
program ended normally
Title: Re: TFPList
Post by: Thaddy on August 13, 2016, 11:06:59 am
There are TWO big limitations: memory and stackspace.
If you would allocate a full array as TArray you either run out of memory or you blow up the stack. That's why they are PArray's or even PPArrays. The full size never gets used because you will probably run out of memory or blow up the stack long before hand. If you look in the implementation in Lists.inc you see what I mean.
This is normal and prudent programming procedure and this is also how it works in e.g. C and C++.
Code: Pascal  [Select][+][-]
  1. procedure BlowStack;
  2. var
  3.   Arr:array[0.maxint-1] of pointer;
  4. begin
  5.   Result :=0;
  6. end;
  7.  
  8. type
  9.   TMaxArray = array[0..maxint-1] of pointer;
  10.   PMaxArray = ^TMaxArray;
  11. procedure DontBlowStack;
  12. var
  13.   arr: PMaxArray;
  14. begin
  15.   result := 0;
  16. end;
  17.  
Title: Re: TFPList
Post by: Thaddy on August 13, 2016, 11:30:59 am
Quote
it doesn't appear that there is any limitation with regard to going past a static array bound
Of course there is: Its called Range checking and Stack checking. What you want can only work if range checks are off and inside a method when stack checking is also off.
But this is an often used programming technique (good or bad!)
Code: Pascal  [Select][+][-]
  1. {$RANGECHECKS OFF}
  2. TMyArray = array[0..0] of integer;// works only with range checks off in any meaningful way
  3. PMyArray = ^TMyArray;// Now try any index other than 0 with {$R+} or {$RANGECHECKS ON}
http://www.freepascal.org/docs-html/current/prog/progsu65.html#x72-710001.2.65
http://www.freepascal.org/docs-html/current/prog/progsu115.html#x123-1240001.3.32
Title: Re: TFPList
Post by: Pasqualish on August 13, 2016, 11:38:08 am
My question is with regard to the fact that the "pointed to" type - a static array -  does not appear to have any limitation or effect on the usage of the pointer -  which is defined to point only to that static array. Not only does the pointer not get used to point to a static array, but you can increment the pointer past where the static array of  the type it allegedly only points to, ends.

In my example code I had {$R+} and it let me increment the pointer past 1000 even though that was the High() of my static array.
Title: Re: TFPList
Post by: Thaddy on August 13, 2016, 11:43:05 am
Read my comments that I editted.
{$RANGECHECKS ON} or {$R+}
The default is OFF that's why it appears to be allowed, but it isn't.  You can catch such errors. But you can also mis-use it like in my example.
In the case of the TFPList, there is no mis-use (and no range error) because there the are declared in a static range for the maximum possible for the type.
But for that to work it needs to be a pointertype to a pointer type to an array.

No range error but an EOutOfMemory, that is ;)
Same problem in C and C++. Same solutions.

Basic (very basic) programming klnowledge.
Title: Re: TFPList
Post by: Pasqualish on August 13, 2016, 11:45:38 am
Quote from: Thaddy on August 13, 2016, 11:43:05 am
Read my comments that I editted.
{$RANGECHECKS ON} or {$R+}
The default is OFF that's why it appears to be allowed, but it isn't.  You can catch such errors. But you can also mis-use it like in my example.
In the case of the TFPList, there is no mis-use (and no range error) because there the are declared in a static range for the maximum possible for the type.
But for that to work it needs to be a pointertype to a pointer type to an array.

No range error but an EOutOfMemory, that is ;)

I must be missing something. I used {$R+} in my example code and it still let me increment a pointer to a static array [0..1000] of Pointer, 2000 times.  It appears that range checks don't have an effect on "pointers to static arrays", which would seem to make a pointer declared as a "pointer to a static array [n1..n2] of Pointer, the same as "Type PPointer = ^Pointer".
Title: Re: TFPList
Post by: Thaddy on August 13, 2016, 11:55:00 am
Code: Pascal  [Select][+][-]
  1. program untitled;
  2. {$RANGECHECKS ON}
  3. type
  4.   TArr = array[0..9] of integer;
  5.   PArr = ^TArr;
  6. var T:PArr;
  7. begin
  8.   T := New(PArr);
  9.   T^[11] := 100;
  10.   Dispose(T);
  11. end.

Sigh ;). Compile...

Code: [Select]
fpc -CX -XXs -CaEABIHF -CpARMV7A -CfVFPV4 -O4 -OpARMV7A -O- -Fu/usr/local/lib/fpc/3.1.1/units/arm-linux/* "arrtest.pas" (in directory: /home/pi)
arrtest.pas(9,6) Error: range check error while evaluating constants (11 must be between 0 and 9)
arrtest.pas(11) Fatal: There were 1 errors compiling module, stopping
Fatal: Compilation aborted
Error: /usr/local/bin/ppcarm returned an error exitcode
Compilation failed.
Title: Re: TFPList
Post by: Thaddy on August 13, 2016, 12:03:09 pm
Note that rangechecks are local to a piece of code or unit scope unless specified from the command line with -Cr while compiling. Maybe there is your error.

E.G.: this will compile without the error:
Code: Pascal  [Select][+][-]
  1. program untitled;
  2. {$RANGECHECKS ON}
  3. type
  4.   TArr = array[0..11] of integer;
  5.   PArr = ^TArr;
  6. var T:PArr;
  7. begin
  8.   T := New(PArr);
  9.   {$push}
  10.   {$R-}  // or {$RANGECHECKS OFF}
  11.   T^[11] := 100;  // will now be allowed, even regardless of compiling with -Cr
  12.   {$pop}
  13.   Dispose(T);
  14. end.
TinyPortal © 2005-2018