[fpc-devel] Library announcement: Generics.Collections

[Maciej Izak]

Hi Free Pascal community!

I'm pleased to announce the generic library, compatible with Delphi
Generics.Collections (almost ;) ).

Homepage

https://code.google.com/p/fpc-generics-collections/

SVN

http://fpc-generics-collections.googlecode.com/svn/trunk/


=== modules ===

Generics.Defaults
Generics.Collections
Generics.Helpers
Generics.Hashes

=== compatible classes ===

TEnumerator<T>
TEnumerable<T>
TList<T>
TQueue<T>
TStack<T>
TDictionary<TKey, TValue>
TObjectList<T: TObject>
TObjectStack<T: TObject>
TObjectDictionary<TKey, TValue>

=== renamed (because compiler limations/bug) ===

TArrayHelper<T> instead of TArray<T>

=== additional classes ===
************
TDictionary<TKey, TValue, TProbeSequence, THash, THashFactory>
TObjectDictionary<TKey, TValue, TProbeSequence, THash, THashFactory>

TKey - key, TValue - value, THashFactory - hash factory :)
TProbeSequence - TProbeSequence is special record for open addresing.
To choose from a predefined:
TLinearProbing, TQuadraticProbing, TDoubleHashing,
TFastLinearProbing, TFastQuadraticProbing, TFastDoubleHashing (fast
version is without "mod")
more info at http://en.wikipedia.org/wiki/Open_addressing
THash - type for hash (to reduce size of dictionary - can be UInt8,
UInt16, UInt32 etc.)

For example, Delphi TDictionary version in this library is defined as:
TDictionary<TKey, TValue> = class(TDictionary<TKey, TValue,
TFastLinearProbing, UInt32, TDelphiHashFactory>);
************
TDictionaryList<TKey, TValue, TIndex, THash, THashFactory>
class, that combines a TList and TDictionary

TKey - key, TValue - value, THashFactory - hash factory :)
TIndex - type for index (to reduce size of dictionary - can be UInt8,
UInt16, UInt32 etc.)
THash - type for hash (to reduce size of dictionary - can be UInt8,
UInt16, UInt32 etc.)
************
Similar to TList, TDictionary and TDictionaryList, but uses normal
operators instead of IEqualityComparer.

TFastList
TFastDictionary
TFastDictionaryList
************
TFastArrayHelper<T> - similar rules as above

=== not implemented ===

TThreadedQueue<T>

=== FAQ ===

1. How to use record as Key or Value in dictionary?

You need to wait for some compiler magic ( system functions
GetReferenceToValue and GetValueSize described bolow)
or add two methods to record:

TRecord = record
(* ... *)
function GetValueSize: Integer; inline;
function GetReferenceToValue: Pointer; inline;
end;

2. How to use Pointer or some custom type as Key or Value in dictionary?

You need to wait for some compiler magic ( system functions
GetReferenceToValue and GetValueSize described bolow)
or use TValueHelper:

uses
Generics.Collections, Generics.Helpers;
(* ... *)
type
TValueHelperPointer = TValueHelper<Pointer>;
var
d: TDictionary<TValueHelperPointer, string>;
begin
(* ... *)
d.Add(nil, 'foo');

=== TODO ===

Comparer from Generics.Defaults can be optimized.

I have no knowledge of FPC compiler design, so i need a little help...

First thing : To finish my work I need critical compiler magic
functions/feature. At first look mayby there is no sense for this functions
but during work on Generic library it's necessary:

function GetReferenceToValue(Value: T): Pointer; // for string types
return @s[1] or nil for empty string for Int32 return @i etc. returns a
reference to the value, as

measured by human/programmer
function GetValueSize(Value: T): Integer; // for string types return
Length(s), for Int32 returs 4 etc.

This functions should be implemented as operators (like Inc, Dec operators).

There is half-workaround/cripled solution as record/type helpers (module
Generics.Helpers). Don't work for custom strings, and for custom "basic"
types like:

type MyStr = type string;
type MyInt = type Int32;

Second thing: Bugs. Look at Critical - fix is needed to perform
compatibility with Delphi and proper work.

http://bugs.freepascal.org/view.php?id=24283 (CRITICAL! Very
Important!)
http://bugs.freepascal.org/view.php?id=24282 (CRITICAL! Very
Important!)
http://bugs.freepascal.org/view.php?id=24254 (CRITICAL! for
TArray.Sort<T>)
http://bugs.freepascal.org/view.php?id=24287 (Very Important!)
http://bugs.freepascal.org/view.php?id=24072 (Very Important!)
http://bugs.freepascal.org/view.php?id=24097 (Important!)
http://bugs.freepascal.org/view.php?id=24064 (Important!)
http://bugs.freepascal.org/view.php?id=24071 (Important!)
http://bugs.freepascal.org/view.php?id=24285 (Important!)
http://bugs.freepascal.org/view.php?id=24286 similar to 24285
http://bugs.freepascal.org/view.php?id=24458
http://bugs.freepascal.org/view.php?id=24098 (Frustrating)
http://bugs.freepascal.org/view.php?id=24073
http://bugs.freepascal.org/view.php?id=24463

[Maciej Izak]

Sorry for ugly e mail. I do not have much experience with mailing lists.
Waiting for testing and suggestions. I've added a zip to download:

https://code.google.com/p/fpc-generics-collections/downloads/list

Post by Maciej Izak
Hi Free Pascal community!
I'm pleased to announce the generic library, compatible with Delphi
Generics.Collections (almost ;) ).
Homepage
https://code.google.com/p/fpc-generics-collections/
SVN
http://fpc-generics-collections.googlecode.com/svn/trunk/

[Sven Barth]

Post by Maciej Izak
Hi Free Pascal community!
I'm pleased to announce the generic library, compatible with Delphi
Generics.Collections (almost ;) ).
Homepage
https://code.google.com/p/fpc-generics-collections/
SVN
http://fpc-generics-collections.googlecode.com/svn/trunk/

Nice. Now I know where all those bug reports come from :P

Post by Maciej Izak
I have no knowledge of FPC compiler design, so i need a little help...
First thing : To finish my work I need critical compiler magic
functions/feature. At first look mayby there is no sense for this functions

Are those available in Delphi as well? If not I see no use in them.

Post by Maciej Izak
function GetReferenceToValue(Value: T): Pointer; // for string types
a reference to the value, as

Consider this code:

=== code begin ===

procedure SomeProc(aValue: Int32);
var
p: Pointer;
begin
p := GetReferenceToValue(aValue);
end;

=== code end ===

The value stored in "p" will be of no significant use for you to be
stored in the longterm, because aValue will be located on the stack and
thus the pointer will no longer be valid once the function exits. This
will also be the case for strings, arrays, records, etc. No compiler
magic will change this.

Post by Maciej Izak
measured by human/programmer
function GetValueSize(Value: T): Integer; // for string types return
Length(s), for Int32 returs 4 etc.

You should not store the string's content, but only the reference to the
string. If you use assignment operators the RTL will take care of the rest.

Post by Maciej Izak
Second thing: Bugs. Look at Critical - fix is needed to perform
compatibility with Delphi and proper work.
http://bugs.freepascal.org/view.php?id=24283 (CRITICAL! Very Important!)

I don't consider nested specializations as critical. It's likely that I
will fix this after I've fixed other generic problems...

Post by Maciej Izak
http://bugs.freepascal.org/view.php?id=24282 (CRITICAL! Very Important!)

The underlying problem is also the source of some other bugs... I'm
happy when I've fixed this, but it's not highest priority... (keyword:
partial specialization)

Post by Maciej Izak
http://bugs.freepascal.org/view.php?id=24254 (CRITICAL! for
TArray.Sort<T>)

I don't consider this critical. It's a missing feature that needs to be
implemented and will be implemented when time permits (though I'm
looking forward to having this feature available :) )

Post by Maciej Izak
http://bugs.freepascal.org/view.php?id=24287 (Very Important!)
http://bugs.freepascal.org/view.php?id=24072 (Very Important!)

Also part of "partial specialization"

Post by Maciej Izak
http://bugs.freepascal.org/view.php?id=24097 (Important!)

Forward declarations are encountered seldomly enough so that I don't
consider this as important.

Post by Maciej Izak
http://bugs.freepascal.org/view.php?id=24064 (Important!)

Considering that your example does not compile in Delphi either and the
way generics and units work I consider it as unlikely that I'll fix that.

Post by Maciej Izak
http://bugs.freepascal.org/view.php?id=24071 (Important!)
http://bugs.freepascal.org/view.php?id=24285 (Important!)
http://bugs.freepascal.org/view.php?id=24286 similar to 24285
http://bugs.freepascal.org/view.php?id=24458
http://bugs.freepascal.org/view.php?id=24098 (Frustrating)

That comes when Borland decides to use "<...>" for generic parameters...
I could still kill them for that decision -.-
This won't be fixed for quite some time.

Post by Maciej Izak
http://bugs.freepascal.org/view.php?id=24073
http://bugs.freepascal.org/view.php?id=24463

Regards,
Sven

[Maciej Izak]

Nice. Now I know where all those bug reports come from :P
:D It's my pleasure. Aren't you happy?

Are those available in Delphi as well? If not I see no use in them.

Post by Sven Barth
=== code begin ===
procedure SomeProc(aValue: Int32);
var
p: Pointer;
begin
p := GetReferenceToValue(aValue);
end;
=== code end ===
The value stored in "p" will be of no significant use for you to be stored
in the longterm, because aValue will be located on the stack and thus the
pointer will no longer be valid once the function exits. This will also be
the case for strings, arrays, records, etc. No compiler magic will change
this.

Yes, I know that. I need this only for shortterm. In that case for safety
maybe we should remove System.Addr? ;) In Delphi they do that by special
interfaces created for each type (lost of time and memory). First, I can't
implement this by Delphi way because we have still a lot of generics bugs.
Secondly, I think that we can do much more better implementation of
Generics. This is not C#, in Pascal we have better access to pointers. Now
I'm using (I hope temporarily):

=== code begin ===

TValueAnsiStringHelper = record helper for AnsiString
function GetValueSize: Integer; inline;
function GetReferenceToValue: Pointer; inline;
end;

function TValueAnsiStringHelper.GetValueSize: Integer;
begin
Result := Length(Self) * SizeOf(AnsiChar);
end;

function TValueAnsiStringHelper.GetReferenceToValue: Pointer;
begin
if Length(Self) <> 0 then
Result := @Self[1]
else
Result := nil;
end;

=== code end ===
Etc. for other basic types.

I, really need this for custom comparers and equality comparers, for
example:

=== code begin ===
while AComparer.Compare(AValues[I].GetReferenceToValue,
P.GetReferenceToValue, AValues[I].GetValueSize, P.GetValueSize) < 0 do
// ...
if FEqualityComparer.Equals(AKey.GetReferenceToValue,
LItem.Pair.Key.GetReferenceToValue, AKey.GetValueSize,
LItem.Pair.Key.GetValueSize) then
=== code end ===

measured by human/programmer

Post by Sven Barth

Post by Maciej Izak
function GetValueSize(Value: T): Integer; // for string types return
Length(s), for Int32 returs 4 etc.

You should not store the string's content, but only the reference to the
string. If you use assignment operators the RTL will take care of the rest.

But with generics code for some types i don't have predefined operators
(for example: records), and here is the problem with Generics Dictionary.
GetValueSize and GetReferenceToValue is in the same level as System.SizeOf
and System.Addr.

I think it's a natural evolution System.SizeOf and System.Addr for Generics
(to operate on values). There is no other language as FreePascal and it
would be wrong to introduce something stupid to such an important system
functions. If my thinking is wrong, please, any hint of an
alternative. Without it, I'm completely stuck.

Post by Sven Barth
http://bugs.freepascal.org/**view.php?id=24283<http://bugs.freepascal.org/view.php?id=24283>(CRITICAL! Very Important!)
I don't consider nested specializations as critical. It's likely that I
will fix this after I've fixed other generic problems...

As critical error I mean - hardcore incompatibility with Delphi version of
Generics.Collections. With critical error you can't compile Delphi code "as
is" with this library.

[Sven Barth]

Post by Sven Barth
Nice. Now I know where all those bug reports come from :P
:D It's my pleasure. Aren't you happy?

Depends. On the one hand I'm happy that someone stresses the generics
implementation to its limits (like JC Chu does as well), but on the
other hand it means work in - in case of generics - a bunch of
headaches... ;)

Post by Sven Barth
Are those available in Delphi as well? If not I see no use in them.
=== code begin ===
procedure SomeProc(aValue: Int32);
var
p: Pointer;
begin
p := GetReferenceToValue(aValue);
end;
=== code end ===
The value stored in "p" will be of no significant use for you to
be stored in the longterm, because aValue will be located on the
stack and thus the pointer will no longer be valid once the
function exits. This will also be the case for strings, arrays,
records, etc. No compiler magic will change this.
Yes, I know that. I need this only for shortterm. In that case for
safety maybe we should remove System.Addr? ;) In Delphi they do that
by special interfaces created for each type (lost of time and memory).
First, I can't implement this by Delphi way because we have still a
lot of generics bugs. Secondly, I think that we can do much more
better implementation of Generics. This is not C#, in Pascal we have
=== code begin ===
TValueAnsiStringHelper = record helper for AnsiString
function GetValueSize: Integer; inline;
function GetReferenceToValue: Pointer; inline;
end;
function TValueAnsiStringHelper.GetValueSize: Integer;
begin
Result := Length(Self) * SizeOf(AnsiChar);
end;
function TValueAnsiStringHelper.GetReferenceToValue: Pointer;
begin
if Length(Self) <> 0 then
else
Result := nil;
end;
=== code end ===
Etc. for other basic types.
I, really need this for custom comparers and equality comparers, for
=== code begin ===
while AComparer.Compare(AValues[I].GetReferenceToValue,
P.GetReferenceToValue, AValues[I].GetValueSize, P.GetValueSize) < 0 do
// ...
if FEqualityComparer.Equals(AKey.GetReferenceToValue,
LItem.Pair.Key.GetReferenceToValue, AKey.GetValueSize,
LItem.Pair.Key.GetValueSize) then
=== code end ===

I still see no need for this. I would simply do

=== code begin ===

if FEqualityComparer.Equals(AKey, LItem.Pair.Key) then
...

=== code end ===

Why fall back to pointers for something like this if we can use static
types?! And if that means that the comparer needs to be implemented for
each type, then so be it (you could implement a default generic
comparer, which uses the normal "=" operator, maybe some others for
basic types like strings and a TObject.Equals based one and the other
comparators should be supplied by the user). You can't do things as
equality tests in a general way anyway (best example: case sensitive vs.
case insensitive comparison of strings). If your concern is performance
then you could declare the two parameters as "constref" so that they are
passed by reference and not by value.

Post by Sven Barth
measured by human/programmer
function GetValueSize(Value: T): Integer; // for string
types return Length(s), for Int32 returs 4 etc.
You should not store the string's content, but only the reference
to the string. If you use assignment operators the RTL will take
care of the rest.
But with generics code for some types i don't have predefined
operators (for example: records), and here is the problem with
Generics Dictionary.

If your implementation of Generics.Dictionary needs certain operators
than the type with which the dictionary is specialized needs to
implement these operators. If the type does not: bad luck.

Post by Sven Barth
GetValueSize and GetReferenceToValue is in the same level as
System.SizeOf and System.Addr.
I think it's a natural evolution System.SizeOf and System.Addr for
Generics (to operate on values).

I see no need for a context sensitive SizeOf and your
GetReferenceToValue is simply flawed, because you can't capture the
correct location of a parameter passed by value as this is just a copy,
no "@Self" will result in the correct value here. E.g.:

=== code begin ===

{$mode objfpc}

type
TLongIntHelper = type helper for LongInt
function GetSelfAddress: Pointer;
end;

function TLongIntHelper.GetSelfAddress: Pointer;
begin
Result := @Self;
end;

var
l: LongInt;

procedure TestProc(aValue: LongInt);
begin
Writeln(hexstr(aValue.GetSelfAddress));
Writeln(hexstr(l.GetSelfAddress));
end;

begin
l := 42;
Writeln(hexstr(l.GetSelfAddress));
TestProc(l);
end.

=== code end ===

=== output begin ===

0040B000
0140FE4C
0040B000

=== output end ===

Post by Sven Barth
There is no other language as FreePascal and it would be wrong to
introduce something stupid to such an important system functions. If
my thinking is wrong, please, any hint of an alternative. Without it,
I'm completely stuck.

Regards,
Sven

[Marco van de Voort]

Post by Sven Barth

Post by Maciej Izak
https://code.google.com/p/fpc-generics-collections/
SVN
http://fpc-generics-collections.googlecode.com/svn/trunk/

Nice. Now I know where all those bug reports come from :P

While playing a bit with this code using some minor stuff I have on top of
delphi containers, I noticed something small:

TList<T> obscures TList if generics.collections is imported after
classes. It doesn't in Delphi. I used tthreadlist in generics.collections
using code, and needed to declare a local (normal) tlist for it.

The code itself didn't compile because of a lot of not really clear "gendef"
errors.

[Sven Barth]

Post by Marco van de Voort

Post by Sven Barth

Post by Maciej Izak
https://code.google.com/p/fpc-generics-collections/
SVN
http://fpc-generics-collections.googlecode.com/svn/trunk/

Nice. Now I know where all those bug reports come from :P

While playing a bit with this code using some minor stuff I have on top of
TList<T> obscures TList if generics.collections is imported after
classes. It doesn't in Delphi. I used tthreadlist in generics.collections
using code, and needed to declare a local (normal) tlist for it.

Yes, cross unit "type overloading" is still a problem in FPC. I've done
some preparations to solve this (the compiler now keeps track whether a
symtable contains a generic), but I've yet to implement the final lookup
system for this.

Post by Marco van de Voort
The code itself didn't compile because of a lot of not really clear "gendef"
errors.

I already have fixed the gendef problems you reported locally, but I
need to find the time to write a nice commit message, because I've
changed the complete implementation of constraints.

Regards,
Sven