Sign in Join

Live chat for Free Pascal, Lazarus, Delphi and every Pascal programmer.

Mailing lists / fpc-devel / 2026-04

crash with TCuckooD2<string, string>

4 messages · 2 people · –

Reply by email Subscribe to this list Your subscription

Read-only archive. Use j and k to move between messages.

Martin Frb

is TCuckooD2<string, string> allowed?

See the code below. It's brute force testing some of the dictionaries.

Testing with 2.2.3 and 3.3.1 (both from early this year) I get a crash for    TCuckooD2<string, string>
  (not tested any of those that follow later in the list).

The crash happens after "Run2" did
   Dict.clear;

when it attempts to add a new element.

program test_dict;
{$mode objfpc}{$H+}
uses Generics.Collections, SysUtils;
generic procedure Run<T>;
var
   Dict: T;
   i: Integer;
   GotExcept: Boolean;
   procedure Add(ATestVal: integer);
   begin
     Dict.Add(IntToStr(ATestVal), 'Val'+IntToStr(ATestVal));
   end;
   function TryAdd(ATestVal: integer): boolean;
   begin
     result := Dict.TryAdd(IntToStr(ATestVal), 'Val'+IntToStr(ATestVal));
   end;
   procedure Del(ATestVal: integer);
   begin
     Dict.Remove(IntToStr(ATestVal));
   end;
   procedure Check(ATestVal: integer);
   var
     ValGotten: string;
   begin
     if not Dict.ContainsKey(IntToStr(ATestVal)) then
       raise Exception.Create('missing key');
     if Dict[IntToStr(ATestVal)]  'Val'+IntToStr(ATestVal) then
       raise Exception.Create('wrong value');
     if not Dict.TryGetValue(IntToStr(ATestVal), ValGotten) then
       raise Exception.Create('TryGetValue failed');
     if ValGotten  'Val'+IntToStr(ATestVal) then
       raise Exception.Create('wrong tried value');
   end;
   procedure CheckNot(ATestVal: integer);
   var
     ValGotten: string;
   begin
     if  Dict.ContainsKey(IntToStr(ATestVal)) then
       raise Exception.Create('unexpected key');
     if Dict.TryGetValue(IntToStr(ATestVal), ValGotten) then
       raise Exception.Create('TryGetValue unexpected');
   end;
   procedure CheckCount(AnExp: integer);
   begin
     if not Dict.Count = AnExp then
       raise Exception.Create('wrong count');
   end;
begin
   RandSeed := 1; // make the test reproducible
   Dict := T.Create;
   CheckNot(0);
   CheckNot(1);
   CheckCount(0);
   Add(-999);
   Check(-999);
   CheckNot(0);
   CheckNot(1);
   CheckCount(1);
   Del(-999);
   CheckNot(-999);
   CheckNot(0);
   CheckNot(1);
   CheckCount(0);
   // re-add
   Add(-999);
   Check(-999);
   CheckNot(0);
   CheckNot(1);
   CheckCount(1);
   if not TryAdd(-998) then raise Exception.Create('try add failed');
   Check(-998);
   Check(-999);
   CheckCount(2);
   if TryAdd(-999) then raise Exception.Create('try add unexpected');
   if TryAdd(-998) then raise Exception.Create('try add unexpected');
   Check(-998);
   Check(-999);
   CheckCount(2);
   for i :=   0 to  99 do Add(i);
   for i :=   0 to  99 do Check(i);
   for i := 100 to 199 do CheckNot(i);
   for i := -99 to  -1 do CheckNot(i);
   CheckCount(102);
   Del(99);
   CheckCount(101);
   for i := 200 to 999 do Add(i);
   for i := 200 to 999 do Check(i);
   for i :=   0 to  98 do Check(i);
   for i :=  99 to 199 do CheckNot(i);
   for i := -99 to  -1 do CheckNot(i);
   for i :=1000 to 9999 do Add(i);
   for i := 200 to 9999 do Check(i);
   for i :=   0 to  98 do Check(i);
   for i :=  99 to 199 do CheckNot(i);
   for i := -99 to  -1 do CheckNot(i);
   Dict.TrimExcess;
   for i := 200 to 9999 do Check(i);
   for i :=   0 to  98 do Check(i);
   for i :=  99 to 199 do CheckNot(i);
   for i := -99 to  -1 do CheckNot(i);
   Dict.Clear;
   CheckCount(101);
   for i :=   0 to  999 do CheckNot(i);
   GotExcept := False;
   Add(-999);
   try
     Add(-999);
   except
     GotExcept := True;
   end;
   if not GotExcept then
     raise exception.Create('did not reject dup');
   Check(-999);
   CheckNot(0);
   CheckNot(1);
   CheckCount(1);
   Dict.AddOrSetValue('998', 'B');
   if Dict['998']  'B' then
     raise Exception.Create('TryOrSet failed');
   Check(-999);
   CheckCount(2);
   Dict.AddOrSetValue('999', 'A');
   if Dict['999']  'A' then
     raise Exception.Create('TryOrSet failed');
   if Dict['998']  'B' then
     raise Exception.Create('TryOrSet failed');
   CheckCount(2);
   Dict.Destroy;
end;
generic procedure Run2<T>;
var
   Dict: T;
   i: Integer;
   GotExcept: Boolean;
   procedure Add(ATestVal: integer);
   begin
     Dict.Add(IntToStr(ATestVal), 'Val'+IntToStr(ATestVal));
   end;
   procedure Del(ATestVal: integer);
   begin
     Dict.Remove(IntToStr(ATestVal));
   end;
   procedure Check(ATestVal: integer);
   var
     ValGotten: string;
   begin
     if not Dict.ContainsKey(IntToStr(ATestVal)) then
       raise Exception.Create('missing key');
     if Dict[IntToStr(ATestVal)]  'Val'+IntToStr(ATestVal) then
       raise Exception.Create('wrong value');
     if not Dict.TryGetValue(IntToStr(ATestVal), ValGotten) then
       raise Exception.Create('TryGetValue failed');
     if ValGotten  'Val'+IntToStr(ATestVal) then
       raise Exception.Create('wrong tried value');
   end;
   procedure CheckNot(ATestVal: integer);
   var
     ValGotten: string;
   begin
     if  Dict.ContainsKey(IntToStr(ATestVal)) then
       raise Exception.Create('unexpected key');
     if Dict.TryGetValue(IntToStr(ATestVal), ValGotten) then
       raise Exception.Create('TryGetValue unexpected');
   end;
   procedure CheckCount(AnExp: integer);
   begin
     if not Dict.Count = AnExp then
       raise Exception.Create('wrong count');
   end;
begin
   RandSeed := 1; // make the test reproducible
   Dict := T.Create;
   CheckNot(0);
   CheckNot(1);
   CheckCount(0);
   Add(-999);
   Check(-999);
   CheckNot(0);
   CheckNot(1);
   CheckCount(1);
   Del(-999);
   CheckNot(-999);
   CheckNot(0);
   CheckNot(1);
   CheckCount(0);
   // re-add
   Add(-999);
   Check(-999);
   CheckNot(0);
   CheckNot(1);
   CheckCount(1);
   Add(-998); // TryAdd not avail
   Check(-998);
   Check(-999);
   CheckCount(2);
   for i :=   0 to  99 do Add(i);
   for i :=   0 to  99 do Check(i);
   for i := 100 to 199 do CheckNot(i);
   for i := -99 to  -1 do CheckNot(i);
   CheckCount(102);
   Del(99);
   CheckCount(101);
   for i := 200 to 999 do Add(i);
   for i := 200 to 999 do Check(i);
   for i :=   0 to  98 do Check(i);
   for i :=  99 to 199 do CheckNot(i);
   for i := -99 to  -1 do CheckNot(i);
   for i :=1000 to 9999 do Add(i);
   for i := 200 to 9999 do Check(i);
   for i :=   0 to  98 do Check(i);
   for i :=  99 to 199 do CheckNot(i);
   for i := -99 to  -1 do CheckNot(i);
   Dict.TrimExcess;
   for i := 200 to 9999 do Check(i);
   for i :=   0 to  98 do Check(i);
   for i :=  99 to 199 do CheckNot(i);
   for i := -99 to  -1 do CheckNot(i);
   Dict.Clear;
   CheckCount(101);
   for i :=   0 to  999 do CheckNot(i);
   GotExcept := False;
//exit; // //////////////////////////////// NEXT LINE CRASH
   Add(-999);  // fails for TCuckooD2
   try
     Add(-999);
   except
     GotExcept := True;
   end;
   if not GotExcept then
     raise exception.Create('did not reject dup');
   Check(-999);
   CheckNot(0);
   CheckNot(1);
   CheckCount(1);
   Dict.AddOrSetValue('998', 'B');
   if Dict['998']  'B' then
     raise Exception.Create('TryOrSet failed');
   Check(-999);
   CheckCount(2);
   Dict.AddOrSetValue('999', 'A');
   if Dict['999']  'A' then
     raise Exception.Create('TryOrSet failed');
   if Dict['998']  'B' then
     raise Exception.Create('TryOrSet failed');
   CheckCount(2);
   Dict.Destroy;
end;
begin
   specialize Run<specialize TDictionary<string, string> >();
   specialize Run<specialize TObjectOpenAddressingLP<string, string> >();
   specialize Run<specialize TOpenAddressingLPT<string, string> >();
   specialize Run<specialize TOpenAddressingQP<string, string> >();
   specialize Run<specialize TOpenAddressingDH<string, string> >();
   specialize Run2<specialize TCuckooD2<string, string> >();
   specialize Run2<specialize TCuckooD4<string, string> >();
   specialize Run2<specialize TCuckooD6<string, string> >();
   specialize Run2<specialize TFastHashMap<string, string> >();
   specialize Run2<specialize THashMap<string, string> >();
end.

Reply by email

Unknown author
to Martin Frb
Martin Frb wrote 5 lines
The crash happens after "Run2" did   Dict.clear; when it attempts to add a new element.

Funny that, I hit a similar problem. I've found and fixed the issue:

Merge Request created here:
https://gitlab.com/freepascal.org/fpc/source/-/merge_requests/1422

Saying that, there were also a few issues in your test program:

1. My line numbers might not match your exactly. in the test at line 54/201: if not
Dict.Count = AnExp is evaluated as (not Dict.Count) = AnExp (bitwise NOT, not
logical) due to Pascal operator precedence, so CheckCount never actually detects
a wrong count. That's a test bug unrelated to the crash, but worth noting.

Both CheckCount procedures have the same bug:

- test_dict.pas:54 (in Run)
- test_dict.pas:201 (in Run2)

   if not Dict.Count = AnExp then
                                          should be:
   if Dict.Count  AnExp then

2. The test itself has wrong expected values in the CheckCount calls immediately after Dict.Clear — they were always silently passing due to the not bug. Lines 125 and 267 both pass 101 but the count should be 0 after a clear:

  122    for i := -99 to  -1 do CheckNot(i);
  123
  124    Dict.Clear;
  125 -  CheckCount(101);
  125 +  CheckCount(0);
  264    for i := -99 to  -1 do CheckNot(i);
  265
  266    Dict.Clear;
  267 -  CheckCount(101);
  267 +  CheckCount(0);

3. Line 154: after AddOrSetValue('999', 'A'), the dictionary has 3 entries (-999, 998, 999), not 2. The AddOrSetValue for '999' adds a new key (the dict was cleared). Same issue in Run2.

  151      raise Exception.Create('TryOrSet failed');
  152    if Dict['998']  'B' then
  153      raise Exception.Create('TryOrSet failed');
  154 -  CheckCount(2);
  154 +  CheckCount(3);
  293      raise Exception.Create('TryOrSet failed');
  294    if Dict['998']  'B' then
  295      raise Exception.Create('TryOrSet failed');
  296 -  CheckCount(2);
  296 +  CheckCount(3);

After that, the test program runs without any crash or failures. :-)

Regards,
Graeme

Reply by email

Martin Frb
to Unknown author
Graeme Geldenhuys wrote 15 lines
On 2026-04-08 13:10, Martin Frb via fpc-devel wrote: > > The crash happens after "Run2" did >   Dict.clear; > > when it attempts to add a new element. Funny that, I hit a similar problem. I've found and fixed the issue: Merge Request created here: https://gitlab.com/freepascal.org/fpc/source/-/merge_requests/1422 Saying that, there were also a few issues in your test program:

Thanks for looking into it, and great to know the issue is addressed.

I noted the stuff in my test... Latest version at
https://gitlab.com/freepascal.org/fpc/source/-/merge_requests/988

Since you got some background into the code, could I ask you to review the changes I suggest? Maybe it helps the MR.
Thanks

Reply by email