Weird in more ways than one

To illustrate an annoying limitation of Delphi generics regarding typed pointers, Lars Fosdal has recently posted some code that provides a half-working generic double linked list implementation (link). The fact it only half works is at least half the point (so to speak), but I’m not sure the limitations of Delphi generics are the only thing making the code ‘weird’ as Lars calls it.

To illustrate, here’s how I would write it – I’ve tried to keep the code as similar to Lars’ version as possible, though the semantics are inevitably slightly different:

program Project1;

{$APPTYPE CONSOLE}

type
  TLinkVisitor<T> = reference to procedure(const Item: T);

  TDoubleLinked<T> = record
    Prev: ^TDoubleLinked<T>;
    Next: ^TDoubleLinked<T>;
    Value: T;
    class function Create(const aValue: T): Pointer; static;
    function Add(const aValue: T): Pointer;
    procedure Delete;
    procedure DeleteAll;
    function First: Pointer;
    function Last: Pointer;
    procedure ForEach(const Proc: TLinkVisitor<T>);
  end;

{ TDoubleLinked<T> }

class function TDoubleLinked<T>.Create(const aValue: T): Pointer;
var
  Node: ^TDoubleLinked<T>;
begin
  Node := AllocMem(SizeOf(TDoubleLinked<T>));
  Node.Value := aValue;
  Result := Node;
end;

function TDoubleLinked<T>.Add(const aValue: T): Pointer;
var
  NewNode: ^TDoubleLinked<T>;
begin
  NewNode := AllocMem(SizeOf(TDoubleLinked<T>));
  NewNode.Value := aValue;
  NewNode.Prev := @Self;
  if Next <> nil then
  begin
    NewNode.Next := Next;
    Next.Prev := Pointer(NewNode);
  end;
  Result := NewNode;
  Next := Result;
end;

procedure TDoubleLinked<T>.Delete;
begin
  if Prev <> nil then Prev.Next := Next;
  if Next <> nil then Next.Prev := Prev;
  Finalize(Self);
  FreeMem(@Self);
end;

procedure TDoubleLinked<T>.DeleteAll;
var
  Node, Next: ^TDoubleLinked<T>;
begin
  Node := First;
  repeat
    Next := Pointer(Node.Next);
    Finalize(Node^);
    FreeMem(Node);
    Node := Next;
  until Node = nil;
end;

function TDoubleLinked<T>.First: Pointer;
var
  Node: ^TDoubleLinked<T>;
begin
  Node := @Self;
  while Node.Prev <> nil do Node := Pointer(Node.Prev);
  Result := Node;
end;

function TDoubleLinked<T>.Last: Pointer;
var
  Node: ^TDoubleLinked<T>;
begin
  Node := @Self;
  while Node.Next <> nil do Node := Pointer(Node.Next);
  Result := Node;
end;

procedure TDoubleLinked<T>.ForEach(const Proc: TLinkVisitor<T>);
var
  Node: ^TDoubleLinked<T>;
begin
  Node := First;
  repeat
    Proc(Node.Value);
    Node := Pointer(Node.Next);
  until Node = nil;
end;

var
  List, Node, SavedNode: ^TDoubleLinked<String>;
begin
  List := TDoubleLinked<String>.Create('One');
  Node := List.Add('Two');
  Node := Node.Add('Three');
  SavedNode := Node;
  Node := Node.Add('Four');
  SavedNode.Add('ThreeAndAHalf');

  List.ForEach(
    procedure(const Value:String)
    begin
      WriteLn('List: ' + Value)
    end);

  Node.ForEach(
    procedure(const Value:String)
    begin
      WriteLn('Node: ' + Value)
    end);

  List.DeleteAll;
  Write('Press ENTER to exit...');
  ReadLn;
end.

OK, so there are some workarounds here that shouldn’t be necessary. In particular, we have to return a raw Pointer for Create, Add, First and Last, and since New and Dispose don’t work correctly with generic record types (that’s an outright bug BTW), AllocMem and Finalize/FreeMem pairs must be used instead. Despite that, the code isn’t radically different to how you would write a non-generic equivalent.

Advertisements

10 thoughts on “Weird in more ways than one

  1. According to Barry Kelly, the bug is that ^Type<T> is allowed when it shouldn’t be. Generic pointers are not officially supported. The whole point about Generics is type safety. If you expose raw pointers, you no longer have type safety. That’s why I went for weird.

    • ‘the bug is that ^Type is allowed when it shouldn’t be’

      Sure. I’m not entirely convinced that’s the whole story however – generic metaclass types aren’t supported either (TMyClass = class of TMyObject). IMO, we’re talking about limitations whose original rational (strict compatibility with what Delphi.NET needed to support C#2.0 constructs) is strictly historical.

      ‘The whole point about Generics is type safety. If you expose raw pointers, you no longer have type safety.’

      Sorry, but I disagree to the extent pointers *as such* shouldn’t be used if a person is ultra-concerned about ‘type safety’, especially given the way Delphi’s default settings relax traditional Pascal typing rules when pointers are used. If a person understands what a linked list is, I don’t see how the necessary workarounds for the generic version particularly complicate matters – it was your way of trying to implement the list in the first place that did that IMO…

      • Class references are basically strongly typed pointers, or?

        The lack of generic metaclasses can also be worked around, although I really did miss using them at first.

        I agree that my construct is ugly – and it should not have been possible in the first place. Hence the conclusion that generics and pointers don’t mix well.

      • ‘Class references are basically strongly typed pointers, or?’

        A bit like class instances then!

        ‘I agree that my construct is ugly – and it should not have been possible in the first place. Hence the conclusion that generics and pointers don’t mix well.’

        That your conclusion doesn’t follow is the point of my alternative code. Do you find that ugly too…?

  2. Isn’t TLinkVisitor misnommed? or should ne TItemVisitor since it visits items, a TLinkVisitor would have to visit the links in the double linked list.
    Such misnommings can turn any good implementations into effective spaghetti generators, and are alas way too common.

    • Well, the naming is from Lars’ original code. That said, I think your ‘spaghetti’ claim is way out of proportion, since you visit a link only to visit the value held by the link. If I visit Paris, it is not wrong to say I am visiting France.

  3. @John – I agree that good naming is important. It should have been named TLinkValueVisitor… or TFoo.

    @Chris – I was thinking class instance references when I wrote class references. My bad.

    > That your conclusion doesn’t follow is the point of my alternative code. Do you find that ugly too…?
    I am pragmatic. If it fills a purpose, I’ll use it. Ugly or not.

    • ‘I am pragmatic. If it fills a purpose, I’ll use it. Ugly or not.’

      Which doesn’t really answer my question 😉

  4. Pingback: Generic linked lists redux « Delphi Haven

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s