Итераторы в Delphi

[himself]

В ближайших нескольких постах я расскажу о занятных применениях новшеств языка Delphi. Большинство из этих новшеств появилось в предыдущих версиях, Delphi 2010 только добавила атрибуты и расширила поддержку шаблонов, но поскольку распространяются нововведения очень медленно, чуть осветить их никогда не поздно.

Итак, итераторы. Начиная, кажется, с версии 2007, в дополнение ко стандартному "for", Delphi поддерживается

следующий синтаксис...

следующий синтаксис:

for element in collection do command;

Документация говорит, что поддерживается итерация элементов массива, символов в строке, значений из набора (set), и, самое интересное, специальным образом подготовленных классов и записей. С массивами и символами всё очевидно, про наборы можно пояснить чуть подробнее:

type
  TConnectionFlag = (cfOpen, cfClientLoggedIn, cfServingRequest, cfSupportsKeepalive, cfRequiresKeepalive);
  TConnectionFlags = set of TConnectionFlag;

//Можно было сделать проще, с помощью RTTI, но пока обойдёмся так.
function FlagName(flag: TConnectionFlag): string;
begin
  case flag of
    cfOpen: Result := 'OPEN';
    cfClientLoggedIn: Result := 'LOGGED_IN';
    cfServingRequest: Result := 'SERVING_REQUEST';
    cfSupportsKeepalive: Result := 'SUPPORTS_KEEPALIVE';
    cfRequiresKeepalive: Result := 'REQUIRES_KEEPALIVE';
  else
    Result := 'UNKNOWN FLAG';
  end;
end;

procedure PrintConnectionFlags(flags: TConnectionFlags);
var flag: TConnectionFlag;
begin
  for flag in flags do
    writeln(FlagName(flag));
end;

Это пример типичного использования итерации по наборам. Без итерации пришлось бы поступать вот так:

procedure PrintConnectionFlags(flags: TConnectionFlags);
begin
  if cfOpen in flags then writeln(FlagName(cfOpen));
  if cfClientLoggedIn in flags then writeln(FlagName(cfClientLoggedIn));
  ...
end;

Мало того, что это неудобно, потребовалось бы добавлять новую строчку в процедуру всякий раз, как добавляется новый флаг в набор.

Теперь о более интересных возможностях итераторов. Допускается создавать итераторы собственным классам. Например, собственный список или TStringList могут поддерживать итерацию по элементам списка. Большинство стандартных классов её и поддерживают:

var
  d: TStringList;
  s: string;
begin
  d := TStringList.Create;
  try
    d.LoadFromFile('lines.txt');
    for s in d do
      writeln(s);
  finally
    FreeAndNil(d);
  end;
end.

Поддержку итерации можно добавить и собственному классу. Для этого нам потребуется вспомогательный класс, итератор (или енумератор, кому как больше нравится). Основной класс должен иметь функцию GetEnumerator, которая создаёт и возвращает экземпляр вспомогательного класса:

type
  TMyCollection = class
  protected
    Items: array of integer;
  public
    function GetEnumerator: TMyCollectionEnumerator;
  end;

function TMyCollection.GetEnumerator: TMyCollectionEnumerator;
begin
  Result := TMyCollectionEnumerator.Create(Self);
end;

Сам итератор должен содержать в себе функцию MoveNext, возвращающую False, если больше элементов нет, и свойство Current, возвращающее текущий элемент:

type
  TMyCollectionEnumerator = class
  protected
    Parent: TMyCollection;
    Position: integer;
  public
    constructor Create(AParent: TMyCollection);
    function MoveNext: boolean;
    function GetCurrent: integer;
    property Current: integer read GetCurrent;
  end;

constructor TMyCollectionEnumerator.Create(AParent: TMyCollection);
begin
  inherited Create;
  Parent := AParent; //сохраняем указатель на объект, который нас создал
  Position := -1;
end;

function TMyCollectionEnumerator.MoveNext: boolean;
begin
  Result := (Position < High(Parent.Items));
  if Result then Inc(Position);
end;

function TMyCollectionEnumerator.GetCurrent: integer;
begin
  Result := Parent.Items[Position];
end;

Вот и готов простейший итератор. Нельзя ли его как-нибудь улучшить? Например, любой опытный дельфист тут же заметит, что каждое использование итератора требует создания объекта, а создание объектов, мы помним, довольно медленная операция. Слава богу, можно сделать итератор рекордом. Всё, что потребуется изменить в нашем коде - убрать вызов к наследуемому Create:

type
  TMyCollectionEnumerator = record
    Parent: TMyCollection;
    Position: integer;
    constructor Create(AParent: TMyCollection);
    function MoveNext: boolean;
    function GetCurrent: integer;
    property Current: integer read GetCurrent;
  end;

constructor TMyCollectionEnumerator.Create(AParent: TMyCollection);
begin
//  inherited Create; //убрано - рекорды не поддерживают наследования
  Parent := AParent;
  Position := -1;
end;

Таким образом получаем довольно быструю итерацию по произвольному контейнеру. Можно и сам TMyCollection сделать рекордом. Особой выгоды в производительности это не даст, поскольку он создаётся лишь один раз, но если это нужно для других целей - всегда пожалуйста. На всякий случай напоминаю, как в дельфи реализованы ссылки крест-накрест. С классами:

type
  TClass1 = class;
  TClass2 = class
    MyClass1: TClass1;
  end;
  TClass1 = class
    MyClass2: TClass2;
  end;

С рекордами:

type
  PRecord1 = ^TRecord1;
  TRecord2 = record
    MyRecord1: PRecord1;
  end;
  PRecord2 = ^TRecord2;
  TRecord1 = record
    MyRecord2 = PRecord2;
  end;

Все объявления должны находиться в пределах одного блока type, при выходе за его пределы дельфи потребует разрешить не до конца определённые типы.

Очевидный вопрос: а нельзя ли вообще не создавать на итерацию ни объекта, ни рекорда? Нельзя ли просто возвращать в GetEnumerator ссылку на самого себя, если мы уверены, что итерацией будут пользоваться только по очереди?

type
  TMyCollection = class
  public
    function GetEnumerator: TMyCollection;
    function MoveNext: boolean;
    function GetCurrent: integer;
  end;

function TMyCollection.GetEnumerator: TMyCollection;
begin
  Result := Self;
end;

Правильный ответ: нет, нельзя. Дельфи автоматически уничтожает итератор после использования. Если в GetEnumerator вы вернёте основной объект, он и будет уничтожен. Сделать с этим ничего нельзя, переопределить Destroy нельзя.

Кто-то спросит, можно ли провернуть этот фокус с рекордами. Рекорды ведь не уничтожаются? Да, рекорды не уничтожаются, но с ними такие трюки и не имеют особого смысла. Не забывайте, что рекорды передаются по значению; это значит, что функция GetEnumerator возвращает не ссылку на рекорд, а целый блок данных, всё его содержимое. Вы можете, конечно, вернуть и сам вызываемый объект:

function TMyRecord.GetEnumerator: TMyRecord;
begin
  Result := Self;
end;

Это будет значить только, что вы создатите новый рекорд TMyRecord и скопируете в него всё содержимое старого. Такой подход, кстати, вполне может однажды пригодиться, например, если внутри вашего TMyRecord небольшое количество критической информации. При доступе из нескольких потоков иногда бывает выгодно не блокировать объект на всё время итерации, а скопировать его информацию для последующего перебора и сразу же освободить его.

Блокировки
Это были простые применения итераторов, а теперь перейдём к более сложным. Самое удобное в итераторах то, что они позволяют выполнять произвольный код в момент перебора. Этим мы и воспользуемся. Например, сделаем перебор потоко-безопасным. При работе с несколькими потоками любой программист выполняет перебор примерно так:

EnterCriticalSection(Sync);
try
  for i := 0 to Collection.Count - 1 do begin (* do something *) end;
finally
  LeaveCriticalSection(Sync);
end;

Упростим эту конструкцию!

function TMyCollectionEnumerator.Create(AParent: TMyCollection);
begin
  inherited Create; //положим, это класс: у рекордов нет деструкторов
  Parent := AParent;
  Position := -1;
  EnterCriticalSection(Parent.Sync);
end;

TMyCollectionEnumerator.Destroy;
begin
  LeaveCriticalSection(Parent.Sync);
  inherited;
end;

procedure EnumCollection(Collection: TCollection);
var i: integer;
begin 
  for i in Collection do begin (* do something *) end; //Collection блокируется автоматически!
end;

Здесь мы воспользовались медленными классами, поскольку нам требовался деструктор, в котором мы могли бы разблокировать объект. С рекордами сложнее, деструкторов у них нет. Можно было бы разблокировать Collection в MoveNext на последнем элементе, но нет гарантии, что итерация дойдёт до этого элемента - не забывайте, что пользователь всегда может сделать break. Таким образом, мы не можем оставлять блокировку на время жизни записи - как раз потому, что не знаем этого времени. Остаётся только делать рекорды с копированием состояния, как описано чуть выше.

function TMyCollection.GetEnumerator: TMyCollectionEnumerator;
begin
  EnterCriticalSection(Sync);
  try
    CopyStateTo(Result); //копирует состояние массива в Result. Мы сможем перебирать result, даже если сам объект к тому времени поменяется
  finally
    LeaveCriticalSection(Sync);
  end;
end;

Иногда такой подход, как я уже говорил, очень удобен - но не всегда. Часто для сохранения состояния требуется копировать весь массив, пусть даже указателей, а это крайне долго. Как жаль, что мы не можем узнать, когда Delphi уничтожает структуру... или можем?

То, что мы сейчас сделаем - это небольшое колдовство. Дельфи не вызывает деструкторов для рекордов, но она финализирует всё их содержимое, в том числе, вызывает _Release для интерфейсов. Поэтому мы создадим интерфейс, который будет освобождать блокировку по _Release.
Для начала нам потребуется переопределённая реализация IInterface:

type
  TMyGatekeeper = class(TObject, IInterface)
  protected
    Parent: TMyCollection;
    RefCnt: integer;
  public
    constructor Create(AParent: TMyCollection);
   //IInterface
    function QueryInterface(const IID: TGUID; out Obj): HResult; stdcall;
    function _AddRef: Integer; stdcall;
    function _Release: Integer; stdcall;
  end;

constructor TMyGatekeeper.Create(AParent: TMyCollection);
begin
  inherited Create;
  Parent := AParent;
  Refcnt := 0;
end;

function TMyGatekeeper.QueryInterface(const IID: TGUID; out Obj): HResult; stdcall;
begin
 //реализуем стандартно
  if GetInterface(IID, Obj) then
    Result := 0
  else
    Result := E_NOINTERFACE;
end;

function TMyGatekeeper._AddRef: Integer; stdcall;
begin
  EnterCriticalSection(Parent.Sync);
  Result := InterlockedIncrement(RefCnt); //можно было и не interlocked
end;

function TMyGatekeeper._Release: Integer; stdcall;
begin
  Result := InterlockedDecrement(RefCnt);
  LeaveCriticalSection(Parent.Sync);
 //не уничтожаем объект
end;

RefCnt мы оставили только для того, чтобы не сломать случайно какие-нибудь внутренние оптимизации Delphi, которые используют это значение. Вообще говоря, можно было бы всегда возвращать единицу. Наш объект не уничтожается с падением RefCnt до нуля; его время жизни задаётся, как для обычного дельфийского объекта, ручным уничтожением. При захвате ссылки на себя он блокирует перебираемый объект, при высвобождении - разблокирует.

Теперь сама коллекция:

type
  TMyCollectionEnumerator = record
    Parent: TMyCollection;
    Position: integer;
    Gatekeeper: IInterface;
    ...
  end;

  TMyCollection = class
  protected
    Sync: TRtlCriticalSection;
    Items: array of integer;
    Gatekeeper: TMyGatekeeper;
  public
    constructor Create;
    destructor Destroy; override;
    function GetEnumerator: TMyCollectionEnumerator;
  end;

constructor TMyCollection.Create;
begin
  inherited;
  InitializeCriticalSection(Sync);
  Gatekeeper := TMyGatekeeper.Create(Self);
end;

destructor TMyCollection.Destroy;
begin
  FreeAndNil(Gatekeeper);
  DeleteCriticalSection(Sync);
  inherited;
end;

function TMyCollection.GetEnumerator: TMyCollectionEnumerator;
begin
  Result := TMyCollectionEnumerator.Create(Self);
  Result.Gatekeeper := Gatekeeper as IInterface; //коллекция блокируется
end;

Обратите внимание, что мы храним Gatekeeper как объект. Если бы мы хранили его, как интерфейс, он постоянно пребывал бы захваченным. "Умные" указатели на интерфейсы в дельфи устроены так, что автоматически вызывают _AddRef при присваивании значения переменной интерфейсного типа, и автоматически вызывают _Release при очистке этого значения.

Когда у нас спрашивают TMyCollectionEnumerator, мы пользуемся этим свойством: мы возвращаем итератор, внутрь которого кладём переменную типа IInterface. Когда мы помещаем в неё наш Gatekeeper, дельфи автоматически выполняет _AddRef, блокируя коллекцию. Когда рекорд уничтожается, дельфи автоматически финализирует запись, очищает поле Gatekeeper, и, поскольку оно было интерфейсного типа, вызывает ему _Release - и коллекция разблокируется.

Это, несомненно, очень удобный и быстрый способ. Достаточно одного объекта типа Gatekeeper на любую коллекцию; можно использовать его во множестве итераторов сразу. Он создаётся однажды, при создании TMyCollection, и почти не добавляет накладных расходов. Однако здесь есть свои подводные камни. Хотя Delphi гарантирует уничтожение рекорда-итератора, а уничтожая его, гарантирует очистку интерфейса, неизвестно, когда она это сделает. В прилагающемся коде я выполнял некоторые эксперименты, и выяснил, например, что хотя в обычных функциях итератор уничтожается сразу же по выходу из "for ... in", в основном теле консольного приложения итераторы-рекорды не уничтожаются вообще. Так что этот приём следует использовать с осторожностью.

Фильтры
Ещё одно интересное применение итераторов - фильтры. Вместо того, чтобы писать:

for i := 0 to Collection.Length - 1 do
  if Collection.Items[i].Connected and Connection.Items[i].LoggedIn and (cfSupportsKeepalive in Connection.Items[i].Flags) then begin
    ....
  end;

Хотелось бы что-то такое:

for Connection in FilterKeepalive(Connections) do begin
  ...
end;

С итераторами это легко сделать, правда, за дополнительную цену - если вы пользуетесь рекордами. Эта дополнительная цена - создание ещё одного временного рекорда. Демонстрирую:

type TKeepaliveFilter = record
    Parent: TConnections;
    function MoveNext: boolean; //выбирает следующий подходящий по фильтрам элемент
    ...
  end;

  TKeepaliveFilterFactory = record
    Parent: TConnections;
    function GetEnumerator: TKeepaliveFilter;
  end;

function FilterKeepalive(Parent: TConnections): TKeepaliveFilterFactory;
begin
  Result.Parent := Parent;
end;

function TKeepaliveFilterFactory.GetEnumerator: TKeepaliveFilter;
begin
  Result := TKeepaliveFilter.Create(Parent);
end;

Проблема здесь в том, что синтаксис дельфи жёстко требует от объекта, стоящего в правой части "for ... in" реализовывать GetEnumerator. Функция-фильтр, которую мы пишем, должна уже сама по себе создать и вернуть какой-то объект, а этот объект затем должен будет создать ещё один - енумератор. Хотелось бы, чтобы можно было в качестве енумератора использовать этот самый, созданный в FilterKeepalive объект (в конце концов, он больше низачем не нужен!). Однако с рекордами это не пройдёт по уже упомянутой причине: если мы просто вернём в GetEnumerator "Result := Self", мы на самом деле скопируем рекорд, и ничем не улучшим положение.

Другое дело - классы. Здесь никакой дополнительной стоимости не налагается:

type TKeepaliveFilter = class
    Parent: TConnections;
    function MoveNext: boolean; //выбирает следующий подходящий по фильтрам элемент
    ...
    function GetEnumerator: TKeepaliveFilter;
  end;

function FilterKeepalive(Parent: TConnections): TKeepaliveFilter;
begin
  Result := TKeepaliveFilter.Create(Parent);
end;

function TKeepaliveFilterCreator.GetEnumerator: TKeepaliveFilter;
begin
  Result := Self;
end;

Класс просто возвращает ссылку на самого себя. Если помните, для коллекции это делать запрещалось, поскольку дельфи уничтожает итератор после использования. Однако здесь нам это не просто на руку, а жизненно необходимо: кто ещё уничтожит созданный в FilterKeepalive временный класс?

Генераторы
Ещё одно интересное применение итераторов связано с тем, что нам вовсе не обязательно перебирать уже существующие объекты. Итератор может перебирать элементы, вычисляемые им же на ходу. По ссылке в примерах есть генерация чисел фибоначчи, а мы решим более практическую задачу - и более быстро (уж разумеется, без классов-фабрик и интерфейсов, упаси меня господи).

Создадим итератор, который будет возвращать нам все окна старшего уровня в системе:

for WindowHandle in TopLevelWindows do
  ShowWindow(WindowHandle, SW_HIDE); //жаль, но десктоп скрыть не получится - он это игнорирует.

Никаких проблем с этим нет, но всё же приведу код. Вначале создадим сам итератор. Он очень простой, содержит в себе весь массив найденных окон и заполняется при создании хозяином:

type
  TWindowEnumerator = record
    Handles: array of HWND;
    Position: integer;
    function MoveNext: boolean;
    function GetCurrent: integer;
    property Current: integer read GetCurrent;
  end;
  PWindowEnumerator = ^TWindowEnumerator;

Очевидно, нам потребуется фабрика, которая его создаёт:

type
  TWindowEnumeratorFactory = record
    function GetEnumerator: TWindowEnumerator;
  end;

function EnumWindowsProc(hwnd: HWND; lParam: LPARAM): BOOL; stdcall;
begin
  with PWindowEnumerator(lParam)^ do begin
    SetLength(Handles, Length(Handles)+1); //в реальной жизни, конечно, лучше приращивать блоками по 10-15 элементов
    Handles[Length(Handles)-1] := hwnd;
  end;
  Result := true;
end;

function TWindowEnumeratorFactory.GetEnumerator: TWindowEnumerator;
begin
  EnumWindows(@EnumWindowsProc, integer(@Result));
  Result.Position := -1;
end;

Вот и всё. Функция TopLevelWindows возвращает фабрику, причём для этого не требуется делать вообще никаких операций (возвращаемый рекорд выделяется автоматически). Прилагаемая программа перебирает все окна и печатает их на экране (не скрывает, не бойтесь, я ещё не такой псих).

P.S. Вообще говоря, с окнами можно было и не извращаться. Обычные массивы работают ничуть не хуже:

type
  THwndArray = array of HWND;
  PHwndArray = ^THwndArray;

function EnumWindowsProc(hwnd: HWND; lParam: LPARAM): BOOL; stdcall;
var Handles: PHwndArray;
begin
  Handles := PHwndArray(lParam);
  SetLength(Handles^, Length(Handles^)+1);
  Handles^[Length(Handles^)-1] := hwnd;
  Result := true;
end;

function TWindowEnumeratorFactory.GetEnumerator: THwndArray;
begin
  EnumWindows(@EnumWindowsProc, integer(@Result));
end;

procedure HideTopLevelWindows;
begin
  for WindowHandle in TopLevelWindows do //точно так же
    ShowWindow(WindowHandle, SW_HIDE);
end;

Ну хорошо, хорошо, хотите - файлы?

for TargetFile in EnumFiles('C:\Windows\System32\*.exe') do
  InfectFile(TargetFile);

Тут тоже совершенно спокойно можно было обойтись массивом, но мы выгадываем на том, что если в середине енумерации нам захочется сделать break - мы не совершим лишних запросов к файловой системе. Ну и вообще, массивы лишний раз не выделять. Рекорд для итерации-то выделяется в стеке, насколько я понимаю.

Заключение
В качестве приложения даю код четырёх маленьких консольных программ, иллюстрирующих кое-что из вышесказанного. Для компиляции требуется Delphi 2010, который вы можете скачать на 30 дней с сайта embarcaderro. Может быть, скомпилится и на прежних версиях, не проверял.

И ещё немного материалов:
Документация на сайте борланд.
Большая статья на английском с примерами генераторов, внешних и внутренних фильтров.
Генераторы-рекорды с подробным сравнением получающегося ассемблерного кода.

@темы: Delphi, Компьютеры

Comments

[Гость]

никогда дельфями не занимался (турбопаскаль не в счёт, а с++ билдер мой любимый тоже не в счёт -- язык-то другой...), однако меня немножко радует введение шаблонов (которые в с++ уже были... или это другие шаблоны? О_о) и

фор что-то ин набор ду много_всего;

(а такое было в пхп).

// zHz

[himself]

Гость: Те же шаблоны, а ещё атрибуты и, офигенная штука, анонимные методы. Я про всё это потом напишу. Анонимные методы даже в исполняемых языках редко встречаются. Вернее, не сами анонимные методы, а замыкания... кхм, closures. Ещё хотелось бы расширенную поддержку рекордов (нормальные конструкторы-деструкторы, наследование) и доделки шаблонов (шаблон-пойнтеры).

[Гость]

himself
а чё такое атрибут -- можно на примере? (если напишешь позже -- так и скажи, буду ждать)

анонимные методы в пхп вроде есть... замыкание что не знаю.

тупой вопрос: чем в дельфях рекорд отличается от класса? тем же чем структура от класса в си++?

// zHz

[himself]

Гость: В принципе, я в прошлой записи показывал:

type
  [Table('Users')] TUserRecord = class
  protected
    [Field('Name')] Name: string;
    [Field('Age')] Age: integer;
  end;

Т.е. можно "помечать" классы, поля и свойства при помощи собственных меточек. Эти меточки тоже реализуются через классы.

Тем, что классы медленные, поддерживают наследование, конструкторы и деструкторы, поддерживают Class Types, кучу всякой тяжелой и иногда полезной функциональности. А рекорды не содержат ничего дополнительного, т.е. это просто голая структура, но с функциями и перегрузкой операторов. Наследования, конструкторов и деструкторов нет.