Здравствуйте!

Вот и пришло время для нового сезона выпусков рассылки, с чем я вас и поздравляю!
В новом сезоне рассылка продолжит публиковать самые интересные материалы сайта RSDN - в первую очередь, конечно, статьи, связанные с программированием на Visual C++. И как и раньше, мы будем касаться некоторых других интересных для разработчиков тем.

Демонстрационный проект MMDemo

Введение

Создатель С++ Бьерн Страуструп в своей книге "Дизайн и эволюция С++" упоминал мультиметоды как одно из перспективных направлений в развитии языка. Однако в настоящее время мультиметоды в С++ не реализованы. В этой статье будет сделана попытка пролить свет на суть мультиметодов, особенности их использования в С++ и возможную реализацию.

Рассуждение

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

// базовый (абстрактный) класс геометрических объектов
struct GObject 
{
  virtual void draw(Graphics & gfx)  = 0; // виртуальная функция отрисовки
};

// точка
struct GPoint : GObject 
{
  virtual void draw(Graphics & gfx);
};

// отрезок
struct GFin : GObject 
{
  virtual void draw(Graphics & gfx);
};

extern GObject * p; // точка или отрезок

void test(Graphics & gfx) 
{
// вызывается GFin::draw или GPoint::draw
  p->draw(gfx);
};

Классы GPoint и GFin в приведённом примере содержат виртуальный метод draw. Известно, что в каждый нестатический метод класса неявным образом передается указатель на обьект: this. Воспользуемся неким Си-подобным псевдокодом и запишем метод draw следующим образом, обозначив this явно:

struct GObject { };

struct GPoint : GObject { };

struct GFin : GObject { };

// виртуальные функции записанные псевдокоде
void draw(virtual GObject * this, Graphics & gfx) = 0;
void draw(virtual GPoint * this, Graphics & gfx);
void draw(virtual GFin * this, Graphics & gfx);

extern GObject * p; // точка или отрезок

void test() 
{
  // виртуальный вызов функции void draw(virtual GPoint * p) 
  // или void draw(virtual GFin * p)
  draw(p);
}

С помощью псевдокода мы фактически вынесли объявления методов за пределы класса, а ключевое слово virtual перед первым аргументом показывает, что эти функции виртуальные, а не перегруженные, и поиск функции выполняется во время выполнения по vtable первого аргумента this. Давайте так же немного изменим свою точку зрения и скажем, что draw - это глобальная функция с одним виртуальным аргументом. Назовем мультиметодом функцию, в которой несколько виртуальных аргументов. И введем для дальнейшего рассуждения мультиметод join, задачей которого является объединение двух геометрических объектов в фигуру:

struct Figure;

// мультиметоды для создания Фигуры из двух объектов

// абстрактный мультиметод:
Figure * join(virtual GObject * a, virtual GObject * b) = 0;
// создает отрезок через две точки
Figure * join(virtual GPoint  * a, virtual GPoint  * b);
// объединяет точку и отрезок в треугольник
Figure * join(virtual GPoint  * a, virtual GFin    * b);
// соединяет линиями концы отрезков и создает четырехугольник
Figure * join(virtual GFin    * a, virtual GFin    * b);

extern GObject * a; // точка или отрезок
extern GObject * b; // точка или отрезок

void test() {
// вызывается один из трех мультиметодв
  Figure * f = join(a, b);
}

В примере оба аргумента a и b имеют статический тип GObject, но во время выполнения под a и b могут скрываться объекты типов GFin и GPoint, и поиск нужной функции происходит по типам аргументов во время выполнения, т.к. мы обозначили эти аргументы как "виртуальные".

Используя псевдокод, можно также объявить мультиметод и другим способом:

struct GPoint 
{
  virtual Figure* join(virtual GFin *fin);
};

Такая форма записи как бы говорит нам: мультиметод принадлежит классу GPoint и имеет виртуальный аргумент GFin * fin. Но, чтобы не выделять какой-либо класс в качестве владельца мультиметода, будем всегда использовать первый вариант, в котором все классы равны:

Figure * join(virtual GPoint * a, virtual GFin * b);

Еще раз взглянем на прототипы join, чтобы осознать первоначальное определение мультиметодов: виртуальные функции, принадлежащие сразу нескольким классам. Может возникнуть вопрос, почему выбрано именно это определение, а не уже озвученное: глобальные функции с несколькими виртуальными аргументами. Дело в том, что на уровне реализации должна существовать одна общая таблица мультиметодов (mvtable), разделяемая между несколькими классами (в данном случае GObject, GPoint и GFin). Синтаксически же мультиметоды проще объявлять как функции с виртуальными аргументами. Но давайте выберем определение, более близкое к реализации, нежели синтаксису.

Попробуем теперь найти ситуацию, в которой мультиметоды существенно облегчают жизнь программиста. Рассмотрим следующий сценарий (здесь и далее будет подразумеваться, что пользователь работает в некой графической среде): пользователь выделяет два объекта и выбирает операцию "соединить". Понятно, что применить обычную перегрузку мы не можем т.к. тип объектов, выбираемых пользователем, известен только во время выполнения. Зато мы можем воспользоваться мультиметодом join, который и вызовем в функции-обработчике:

// обработчик
void join_onClick(Selection * sel) 
{
  Figure * f = join(sel->item_get(0), sel->item_get(1));
}

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

// создает треугольник из трех точек
Figure * join(virtual GPoint * a, virtual GPoint * b, virtual GPoint * c);
// четырехугольник из отрезка и двух точек
Figure * join(virtual GFin * a, virtual GPoint * b, virtual GPoint * c);

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

void join_onClick (Selection * sel) 
{
  Figure * f = NULL;
  switch (sel->item_count()) 
  {
  case 2: 
    f = join(sel->item_get(0), sel->item_get(1));
    break;
  case 3:
    f = join(sel->item_get(0), sel->item_get(1), sel->item_get(2));
    break;
  }
}

Что же мы видим? Удобства использования мультиметодов сведены на нет фиксированным списком аргументов. Т.е. для вызова мультиметода было бы удобно использовать прототип:

Figure * join(virtual GObject * argList[], size_t argc);

А для реализации мультиметодов удобны прототипы:

Figure * join(virtual GPoint * a, virtual GPoint * b, virtual GPoint * c);

Figure * join(virtual GPoint * a, virtual GFin * b);

Так как порядок следования аргументов, передаваемых через массив argList[], непредсказуем, будем считать, что и в объявлении мультиметода порядок следования аргументов значения не имеет. Т.е. следующие прототипы эквивалентны:

Figure * join(virtual GPoint * a, virtual GFin * b);

Figure * join(virtual GFin * a, virtual GPoint * b);

В этом случае устраняются все препятствия для использования мультиметодов:

void join_onClick (GObject * selection[], size_t n) 
{
  // чудесным образом вызывается join(GPoint *, GPoint *, GPoint *),
  // join(GPoint *, GFin *) или другой
  Figure * f = join(selection, n);
}

Теперь задумаемся над еще одной проблемой из реальной жизни. Обратим внимание на мультиметод:

Figure * join(virtual GFin * a, virtual GFin * b);

Он создает четырехугольник путем соединения концов двух отрезков. Рисунок показывает, что соединить концы можно двумя способами:

Т.е. под одним прототипом может скрываться сразу несколько функций. Попробуем написать две реализации для одного прототипа:

Figure * join(virtual GFin *, virtual GFin *)
{
  // эта реализация создает обычный четырехугольник
  // ...
}
Figure * join(virtual GFin *, virtual GFin *)
{
  // а эта - необычный
  // ...
}

Это выглядит абсурдно, и из-за неоднозначности такой мультиметод невозможно вызвать. Почему? Вспомним, что мы привыкли считать вызов виртуальной функции в С++ атомарной операцией (единой и неделимой), но по сути она состоит из двух частей: поиск по vtable и непосредственно вызов. В данном случае в результате поиска может быть найдено несколько функций, и однозначного вызова быть не может. Поскольку отказываться от удобств нет смысла, откажемся от атомарности и введем следующий сценарий для вызова мультиметодов: поиск функций; принятие решения о вызове; и, наконец, вызов. В реальной жизни это позволило бы создавать программы, работающие по следующему сценарию: пользователь выделяет произвольное число объектов; по этому списку производится поиск методов; программист помещает доступные операции на инструментальную панель; пользователь выбирает среди возможных, нажимает кнопку - и вызывается нужный мультиметод. Чем вам не "программирование будущего"?

Реализация

Теперь попробуем собрать рассуждения в кучу и начнем приближаться к реалиям С++. Итак, мультиметоды - это виртуальные функции, принадлежащие сразу нескольким классам. Что же у них общего? Если просмотреть мультиметоды, приведенные выше, можно сказать, что, во-первых, все аргументы мультиметодов унаследованы от одного общего базового класса GObject. Во-вторых, все приведённые выше мультиметоды относятся к одному виду операции - join. Таким образом, мультиметоды могут быть сгруппированы в семейства по базовому классу аргументов и типу операции:

family Join<GObject> 
{
  // семейство мультиметодов Join для класса GObject
  // == method declarations =======================
};

Так как семейство создает область видимости, то мультиметодам можно давать более осмысленные имена:

family Join<GObject> {
  Figure * line_from_pp(GPoint * a, GPoint * b);
  Figure * triangle_from_ppp(GPoint * a, GPoint * b, GPoint * c);
  Figure * triangle_from_fp(GFin * a, GPoint * b);
  Figure * box_from_ff(GFin * a, GFin * b);
  Figure * box_x_from_ff(GFin * a, GFin * b);
};

Чтобы осуществилась задуманная стратегия вызова мультиметодов (поиск-решение-вызов), введем следующие "операции" для семейства:

// первая часть вызова - задаем список аргументов argList
void Join<GObject>::args_set(GObject * argList[], size_t argc);
// число найденных мультиметодов для заданного argList
size_t Join<GObject>::method_count();
// некая информация об найденном мультиметоде
method_info& Join<GObject>::method_info(size_t index);
// вызов мультиметода - argList разврачивается 
// в список параметров конкретного метода
Figure * Join<GObject>::invoke(size_t index);

Пример использования:

// пользователь выделил объекты
void selection_onChange(GObject * selection[], size_t n) 
{
  // задаем список аргументов для мультиметода
  Join<GObject>::args_set(selection, n);
  // помещаем на тулбар кнопки, соотвествующие разрешенному набору действий
  for (size_t i = 0; i < Join<GObject>::method_count(); i++)
    toolbar_button_add(Join<GObject>::method_info(i));
}

// пользователь нажал кнопку на тулбаре
void toolbar_button_onClick(size_t methodIndex) 
{
  // вызываем нужный мультиметод
  Figure * f = Join<GObject>::invoke(methodIndex);
}

Теперь, когда с теоретической точки зрения всё стало ясно, можно подумать и о реализации. Необходимо реализовать поддержку семейств мультиметодов так, чтобы их можно было удобно использовать в С++. Как семейство может быть реализовано физически? Очевидно, что семейству соответствует некая ассоциативная mvtable (multimethod-vtable), ключом для поиска функций в которой является список типов аргументов. В С++ работу по созданию обычной vtable берет на себя компилятор. Чтобы избавить программиста от необходимости создания mvtable вручную, я написал утилиту xmmdc - MultiMethod Description Compiler (см. MMDemo\XMMDC) которая генерирует готовый шаблон mvtable на основе XML-описания.

Описание mvtable в формате XML (MMDemo\MyMVT.xml):

<mvtable name ='MyMVTBase'>

  <method name ='ppp_link' dsc='Make Triangle'>
    <arg type='GPoint'/>
    <arg type='GPoint'/>
    <arg type='GPoint'/>
  </method>

  <method name ='ppp_link' dsc='Make Line'>
    <arg type='GPoint'/>
    <arg type='GPoint'/>
  </method>

  <method name ='pf_link' dsc='Make Triangle'>
    <arg type='GPoint'/>
    <arg type='GFin'/>
  </method>

  <method name ='ffx_link' dsc='Make X-Box'>
    <arg type='GFin'/>
    <arg type='GFin'/>
  </method>

  <method name ='ff_link' dsc='Make Box'>
    <arg type='GFin'/>
    <arg type='GFin'/>
  </method>

</mvtable>

На основе этого описания xmmdc создает заголовочный файл, содержащий реализацию таблицы мультиметодов (MMDemo\MyMVTBase.h):

#ifndef _MyMVTBase_h_
#define _MyMVTBase_h_
// базовый класс для mvtable (MMDemo\XMMDC\XMVTable.h)
#include "XMVTable.h" 

template <class Owner, class T>
class MyMVTBase : public XMVTable<Owner,T> 
{
// Прототипы мультиметодов
public:
  
  void ppp_link(GPoint *,GPoint *,GPoint *) {}
  void pp_link(GPoint *,GPoint *) {}
  void pf_link(GPoint *,GFin *) {}
  void ffx_link(GFin *,GFin *) {}
  void ff_link(GFin *,GFin *) {}

// код реализации 
protected:
  // код для работы мультиметода ppp_link
  struct X_ppp_link : XMethod<Owner,T> 
  {
    enum { argc = 3 };
    
    int * argList_get(bool fc, int &ac) 
    {
      ac = argc;
      static int lst[] = { GPoint::typeId,GPoint::typeId,GPoint::typeId };
      if(fc)
        std::sort(lst, lst + argc);
      return lst;
    }

    void call(Owner &o, T * objs[]) 
    {
      int i = argc-1;
      T * args[argc];
      std::copy(objs, objs+argc, args);
      o.ppp_link((GPoint *)_arg_pop(args, i, GPoint::typeId),
        (GPoint *)_arg_pop(args, i, GPoint::typeId),
        (GPoint *)_arg_pop(args, i, GPoint::typeId));
    }

    const char * dsc_get()
    {
      return "Make Triangle";
    }
  } x_ppp_link;

// Остальная часть опущена
// ....................
};

#endif // _MyMVTBase_h_

Сгенерированная mvtable поддерживает следующие операции (в подробностях реализации mvtable легко разобраться по исходному тексту):

// Базовый класс для mvtable. Детали реализации опущены
template <
  class Owner,  // Класс реализации мультиметодов
  class T  // базовый класс аргументов
>
class XMVTable
{
public:
  // задает список аргументов
  void args_set(T * argList [], size_t n);
  // возвращает число найденных мультиметодов для последнего argList
  size_t  method_count() const;
  // получает информацию о найденном мультиметоде
  Method * method_get(int idx); // описание см. ниже
  // вызывает мультиметод с сохраненным списком аргументов argList
  void  invoke(Method * m);
};

// класс, возвращаемый функцией XMVTable:: method_get
// приведены только необходимые пользователю функции 
template <class Owner, class T>
struct XMethod
{
  // описание мультиметода или ключ
  // фактически, значение аттрибута dsc из XML файла
  virtual const char * dsc_get() = 0;
public:
  // Пользовательские данные. 
  // Программист может связать с мультиметодом дополнительные данные,
  // используя эту переменную.
  void * userData;
};

Использование

А нам теперь остается только унаследоваться от этого класса и реализовать нужные методы (см. MMDemo\MyMVT.h):

#ifndef _MYMVT_h_
#define _MYMVT_h_

#include "GObject.h"
#include "MyMVTBase.h"

// реализация семейства мультиметодов Join<GObject>
class MyMVT : public MyMVTBase<MyMVT,GObject> {
public:

  GFigure    figure;

// overrides
public:

    void ppp_link(GPoint *,GPoint *,GPoint *);
    void pp_link(GPoint *,GPoint *);
    void pf_link(GPoint *,GFin *);
    void ffx_link(GFin *,GFin *);
    void ff_link(GFin *,GFin *);

};

//реализация одного из мультиметодов
void MyMVT::ppp_link(GPoint * a, GPoint * b, GPoint * c) {
  figure.line_add(a->A, b->A);
  figure.line_add(b->A, c->A);
  figure.line_add(c->A, a->A);
}

#endif // _MYMVT_h_

Чтобы все это работало, к классам аргументов предъявляются определённые требования. Эти классы должны содержать статическую переменную typeId, уникальную в рамках иерархии классов, и виртуальную функцию typeId_get для определения типа во время исполнения.

struct GObject 
{
  virtual int typeId_get()  = 0;
};

struct GPoint : GObject 
{
  enum { typeId = 1 };
  int typeId_get() 
  {
    return typeId; 
  }
};

struct GFin : GObject
{
  enum { typeId = 2 };
  int typeId_get()
  {
    return typeId;
  }
};

Пример использования мультиметодов рассматривается в демо-проекте MMDemo. В нем реализована описанная выше стратегия, то есть выбор объектов, поиск мультиметодов по списку аргументов, вывод доступных операций пользователю и вызов выбранного мультиметода. Следующие функции показывают эту стратегию в действии:

class CMMDemoDlg : public CDialog 
{
  MyMVT _mvt; // таблица мультиметодов в классе диалога
  // ...
};

// пользователь выбрал объекты
LRESULT CMMDemoDlg::canvas_onSel(WPARAM,LPARAM) 
{
  int i, c = 0;
  GObject * objs[5];
  
  // формируем список аргументов
  for (i = 0; i < _canvas.object_count(); i++) 
  {
    GObject * o = _canvas.object_get(i);
    if (o->selected_is())
      objs[c++] = o;
  }
  // передаем список в mvtable
  _mvt.args_set(objs, c);

  _mmList.ResetContent();
  // выдаем пользователю список доступных операций
  for (i = 0; i < _mvt.method_count(); i++) 
  {
    MyMVT::Method * mm = _mvt.method_get(i);
    int idx = _mmList.AddString(mm->dsc_get());
    _mmList.SetItemDataPtr(idx, mm);
  }
  return 0;
}

// пользователь выбрал операцию
void CMMDemoDlg::invoke_onClick() 
{
  int idx = _mmList.GetCurSel();
  if(LB_ERR == idx)
    return;

  _mvt.figure.pts.clear();
  // вызываем выбранный метод
  MyMVT::Method * mm = (MyMVT::Method *)_mmList.GetItemDataPtr(idx);
  _mvt.invoke(mm);
  // выводим результат
  _canvas.object_add(&_mvt.figure);
}

Еще раз напомню, что порядок следования аргументов в мультиметоде значения не имеет. Для поиска мультиметодов важно лишь число аргументов и их run-time типы. Также стоит обратить внимание на то, что в данной реализации не поддерживаются невиртуальные аргументы мультиметодов, но, поскольку реализация мультиметодов осуществляется в отдельном классе, это несущественно, так как невиртуальные аргументы можно передавать через атрибуты класса.

extern MyMultimethodVTable mvt;

void test(MyObject * argv[], size_t argc, MyNonVirtualArg & arg)
{
  mvt.nonVirtualArg = arg;
  mvt.args_set(argv, argc);
  mvt.invoke(mvt.method_get(0));
}

Работа программы показана на скриншотах:

И, в заключение, систематизируем процесс добавления в проект мультиметодов. Процесс должен состоять из следующих шагов:

• Подготовить XML файл с описанием mvtable, имя класса и заголовочного файла указывается в тэге mvtable:

<mvtable name='ClassAndHeaderName'>

• Сгенерировать заголовочный файл с помощью xmmdc

xmmdc test.xml

• Создать класс, производный от сгенерированного, и реализовать в нем мультиметоды

Области применения мультиметодов

Как уже было сказано выше, выгодно применять их в случае, когда нужно найти операцию, применимую к списку объектов. Например, в компьютерных играх мультиметоды помогут скрестить бульдога с носорогом или же определить возможность\невозможность такой операции. Так же, например, может выбираться определенная стратегия поведения персонажа в зависимости от надетых на него доспехов:

class Hero : public GameObject
{
// ...
};

class Frodo : public Hero
{
// ...
};

class Item : public GameObject
{
// ...
};

class RingOfPower : public Item
{
// ...
};

Behaviour* behaviour_create(virtual Hero *hero, virtual Item *item);
Behaviour* behaviour_create(virtual Frodo *frodo, virtual RingOfPower *ring);

Весьма полезными окажутся мультиметоды для реализации drag-n-drop операций, так как Drag-n-drop операция разделяется между двумя классами (DropTarget и DropObject) и является мультиметодом в чистом виде:

void DragDrop(virtual SomeView*, virtual SomeItem*);

Описанный выше пример с операцией join показывает, что их можно использовать для создания интеллектуального пользовательского интерфейса, в котором доступные операции предлагаются в зависимости от выделения, контекста, окружения и т.д.

Приведенные примеры показывают, что хотя мультиметоды еще и не освоены массами, но могут существенно упростить решение задач программирования во многих областях.

Ведущий рассылки: Алекс Jenter   jenter@rsdn.ru
Публикуемые в рассылке материалы принадлежат сайту RSDN.

| Предыдущие выпуски     | Статистика рассылки