18 ноября 2010

(std::max)

Как-то давно я советовал бороться с макросами min/max из windows.h таким образом:
#include <windows.h>

#ifdef min
#undef min
#endif

#ifdef max
#undef max
#endif
Напомню в чем суть проблемы: после включения windows.h уже нельзя писать std::max(a,b). Оказывается все гораздо проще: можно писать (std::max)(a,b). Препроцессор обойдет такую запись стороной. Тогда не нужны undef-ы (актуально если потом вдруг нужно включить что-нибудь типа atl*.h).

16 сентября 2010

Local functions in C++

В Pascal есть замечательная вещь - локальные функции. Иногда они ну ооочень удобны. Если кто с Паскалем не знаком, на C++ это бы выглядело примерно так:
int foo(int x)
{
int y = 0;

void bar(int z)
{
y += x*z;
}

bar(1);
bar(2);

return y;
}
То есть тело такой функции пишется внутри другой функции, и она может ссылать на ее переменные.
В C++ такого счастья нет. Может такого не сделали из-за того, что в Сях стек устроен немного по-другому, нежели в Паскале (в любом случае - не оправдание), может Бьярн счел это "не тру". Конечно, можно написать локальный класс, у которого будет нужная функция, но которому придется вручную передавать нужные переменные - но это неудобно, да и выглядит ужасно. Вот как-то так:
int foo(int x)
{
int y = 0;

class foobar
{
public:
bar(int &y, int x) : y(y), x(x)
{
}

void operator ()(int z)
{
y += x*z;
}

private:
int &y, x;
} bar(y, x);

bar(1);
bar(2);

return y;
}
Но с новым стандартом этот способ стал гораздо короче в записи:
int foo(int x)
{
int y = 0;

auto bar = [&](int z)
{
y += x*z;
};

bar(1);
bar(2);

return y;
}
Если сравнить с кодом, приведенным в начале - отличия минимальны! А уж если оно выглядит как утка, плавает как утка и крякает как утка - то чем не утка локальная функция?!

16 июля 2010

Mini HTTP server

Понадобился в приложении мини http сервер и http клиент. С клиентом все просто - можно просто воспользоваться функциями WinInet, написав к ним немного C++-оберток.

Сервер можно довольно просто написать на Boost.Asio, но оказалось все уже изобретено - хорошо подошла cpp-netlib, вот пример кода сервера из документации:
struct hello_world;
typedef http::server server;

struct hello_world {
void operator() (server::request const &request,
server::response &response) {
response = server::response::stock_reply(
server::response::ok, "Hello, World!");
}
void log(...) {
// do nothing
}
};

hello_world handler;
http::server server_("0.0.0.0", "80", handler);
server_.run();

Библиотека, правда, довольно сырая - пришлось немного допиливать напильником чтобы скомпилировалась под VC++10. Но зато в комплекте идут приятные бонусы типа url_decode, которые вполне пригодились.

PS. Забавно было когда сделал и запустил простейший сервер - FireFox грузил http://localhost/ очень долго, дольше чем http://www.yandex.ru/. Я уж было стал грешить на cpp-netlib и boost.asio, но оказалось IE открывал localhost мгновенно. Как я понял, FF долго ресолвит адрес localhost (причем каждый раз видимо заново), а http://127.0.0.1/ открывает мгновенно.

21 июня 2010

Lexical_cast using Spirit

Если хочется быстро заменить lexical_cast на парсеры из Spirit-а (для увеличения скорости парсинга, например):
template <class T>
inline T spirit_cast(std::string const & input)
{
T value;

std::string::const_iterator begin = input.begin();
bool result = boost::spirit::qi::parse(begin, input.end(), value);

if (!result || begin != input.end())
throw std::bad_cast();

return value;
};

11 мая 2010

News: good one and bad one

Новая Visual Studio 2010 огорчила: CRT поддерживает операционные системы не ниже WinXP SP2 и Win2003 SP1. Забудьте про Win2000 и даже WinXP без SP2. Это весьма печально.

А новый Boost 1.43 порадовал: наконец-то добавили RangeEx. Это очень радует. Да что уж там - это будет мой следующий любимый релиз после 1.39, где был добавлен ForEach. ;)

01 мая 2010

Comma operator returns

RAII в C++ - замечательная вещь. Количество кода сокращается на порядок (ну, если мыслить в двоичной системе исчисления, то в 2 раза - это на порядок, в 4 раза - уже на два порядка).

Например, следующий код дает нам возможность показать курсорчик "думаем..." и убрать его когда мы додумаем:
{
WTL::CWaitCursor WaitCursor;
SomeOperation();
}
Не нужно руками восстанавливать курсор ни в случае если операция завершится успешно, ни в случае если кинет исключение. Все сделает деструктор класса CWaitCursor.

Но вот такой случай заставляет нас вручную восстанавливать курсор:
{
WTL::CWaitCursor WaitCursor;
if (!SomeOperation())
{
WaitCursor.Restore();
MessageBox("не получилось :(");
}
}
Обидно, да? А не восстановим - получим MessageBox не с тем курсором.

Вот тут-то и приходит на помощь старый добрый оператор запятая. Трюк в чем: при вычислении выражения все его аргументы живут до конца вычисления всего выражения. Построим выражение, где у нас будет "думающий" курсор и наша операция:
if (WTL::CWaitCursor(), !SomeOperation())
MessageBox("не получилось :(");

09 марта 2010

Boost.Spirit in practice

Я заметил, у разработчиков совершенно полярное отношение к библиотеке Boost.Spirit: либо она им жутко не нравится, либо они фанатеют от нее. Конечно, описывать грамматику на C++ – занятие на любителя. Таким любителем оказался и я, когда познакомился со Спиритом. Хочу показать, как с помощью Спирита можно довольно просто решать повседневные задачи разбора текста.

Простая задача – как два пальца

На Спирите очень удобно писать маленькие парсеры «не отходя от кассы» – прямо в C++ коде. Вот например, как вы поступите если нужно распарсить строку вида «число-число», которая задает диапазон страниц для печати? На Спирите – одна строчка:

bool ok = parse(First, Last, (uint_ >> L".." >> uint_), MinMax) && (First == Last));

Посложнее…

Более того – можно ненамного сложнее создавать и парсеры побольше. В качестве примера рассмотрю парсер мини-языка, который я делал для API Яндекс.Бара. Задача была такова: для облегчения загрузки плагинов в баре используется XML, который довольно избыточный сам по себе. Но зато XML легче грузить из JavaScript-а, чем парсить произвольный формат (на JS пишутся расширения под FireFox, в том числе и Я.Бар).

Итак, что мне было нужно – имея на входе обычную инфиксную нотацию:

Hello * Interval * 60 + xpath("number(//hello[id='" # id # "')", World)

получить на выходе обычное AST в XML-формате:

<add>
<mul>
<value-of name="Hello"/>
<value-of name="Interval"/>
<value type="number">60</value>
</mul>
<xpath>
<concat>
number(//hello[id='<value-of name="id"/>')
</concat>
<value-of name="World"/>
</xpath>
</add>

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

root
child1: текст
@attribute1: text
@attribute2 = формула
grandchild
grand-grand-child
child2 = формула

То есть вложенность задается количеством табуляций, далее идет имя XML-ноды (элемента или атрибута). За ним - определенный символ, определяющий что идет далее: текст или формула. Текст нужно передавать на выход в «голом» виде, формулы – в виде AST.

Итого у меня два парсера – один разбирает строку чтобы получить имя ноды и текст или формулу. Второй – разбирает формулы, генерируя AST. Обработку количества табов я провожу снаружи старым добрым std::find_if.

Парсинг строки. Semantic actions – через Boost.Bind

Начну с более простого – разбора строк. Строки могут быть такие:

tag
tag: тест
tag = формула
= формула
name :: (instance|widget) (setting|variable)
name := формула

Парсер получается очень простой:

bool parse_definition(string::const_iterator &iter, string::const_iterator end, mini_xml &root)
{
qi::rule<string::const_iterator, string(), space_type> id, any_string, scope, type;
id %= raw[lexeme[-char_('@') >> alpha >> *(alnum | '_' | '-' | (':' >> alnum))]];
any_string %= lexeme[+char_];
scope %= raw[lit("widget") | lit("instance")];
type %= raw[lit("setting") | lit("variable")];

return phrase_parse(iter, end,
(
(id >> "::" >> scope >> type) [bind(&add_identifier, ref(root), _1)] |
(id >> ":=" >> any_string) [bind(&add_definition, ref(root), _1)] |
(id >> ':' >> any_string) [bind(&add_raw, ref(root), _1)] |
(id >> '=' >> any_string) [bind(&add_calculated, ref(root), _1)] |
( '=' >> any_string) [bind(&add_expression, ref(root), _1)] |
id [bind(&add_subnode, ref(root), _1)]
),
space) && (iter == end);
}

Использование phrase_parse() вместо parse() позволило мне переложить на Спирит обработку white space (пробелов, табуляций и т.п.) внутри выражений. Это позволит писать как «tag:text», так и «tag : text». Причем мой код, как видно, освобожден от обработки пробелов – все делает phrase_parse(). Мне остается только использовать lexeme[] там, где я хочу отключить такое поведение, и raw[] там, где я хочу получить исходный текст без вырезания пробелов.

Кстати, напомню что синтаксис правил у Spirit-а такой:

rule [semantic_action]

То есть после каждого правила можно в квадратных скобках задать действие, которое будет выполняться, если правило «сработало».

В моем случае на каждый тип строки – свое поведение, плюс в самом начале для упрощения последующего кода я ввел отдельные правила типа id, any_string. Код, вызываемый при соответствии строки определенному правилу – указан через лямбда-функции, создаваемые с помощью boost::bind. Синтаксис bind-а очень прост:

boost::bind(функция, аргумент, аргумент, ...)

В качестве аргументов можно указывать специальные placeholder-ы (вида _1, _2, …), указывающие куда вставлять аргументы лямбда-функции. На выходе каждого парсера получается одно значение, его и передаем в качестве аргумента нашей функции. Например, парсер

id >> '=' >> any_string

сгенерирует на выходе пару строк (в виде boost::fusion::vector<string, string>), которую я передаю в качестве второго параметра моей функции add_calculated, которая имеет такой вот интерфейс:

void add_calculated(mini_xml &root, fusion::vector<string, string> const &);

Первый параметр, который мне нужно передать этой функции – это ссылка на root, поэтому вызов boost::bind выглядит так:

bind(&add_calculated, ref(root), _1)

Суммируя вместе правило и семантическое действие:

(id >> '=' >> any_string) [bind(&add_calculated, ref(root), _1)]

Парсинг формулы. Semantic actions – через Boost.Phoenix

Напомню какого вида функции мне нуно парсить:

Hello * Interval * 60 + xpath("number(//hello[id='" # id # "')", World)

При разборе формул могут встретиться:

  • числа
  • булевы константы (true, false)
  • строки (в кавычках)
  • идентификаторы
  • вызовы функций
  • операции

Для обработки результатов парсинга я создал один большой функтор и во всех семантических действиях использую его с помощью Booost.Phoenix. Как и у всех функторов, действия различаются не по именам, а по количеству и типам параметров.

struct compiler
{
// метки нужны для того, чтобы отличать друг от друга функции с одинаковыми аргументами
struct identifier{}; // метка «идентификатор»
struct function{}; // метка «функция»
struct parameter{}; // метка «параметр»
struct assignment{}; // метка «присваивание»

void operator()(mini_xml &node, std::string const &id, identifier) const; // идентификатор
void operator()(mini_xml &node, std::string const &id, function) const; // функция
void operator()(mini_xml &node, std::string const &id, parameter) const; // параметр функции
void operator()(mini_xml &node, std::string const &id, assignment) const; // присваивание
void operator()(mini_xml &node, std::string const &value, char const *type) const; // <value>
void operator()(mini_xml &node, mini_xml const &subnode) const;
void operator()(mini_xml &node, mini_xml const &subnode, std::string const &id, bool allow_join = false) const;
};

Внутри своей грамматики я добавил член класса - тот самый мой функтор:

template <typename Iterator>
struct expression_grammar : grammar<Iterator, mini_xml(), space_type>
{
expression_grammar() : expression_grammar::base_type(expressions)
{
expressions = ...;
}

rule<Iterator, mini_xml(), space_type> expressions, ...;
boost::phoenix::function<compiler> op;
}

PS. Тип mini_xml – это генерируемый XML.

Правила для парсинга идентификаторов, строк, чисел и булевых констант очень просты:

id %= raw[lexeme[alpha >> *(alnum | '_' | ('-' >> alnum))]];
quoted_string %= lexeme['"' >> *(char_ - '"') >> '"'];
numeric_value %= raw[lexeme[-(char_('+') | char_('-')) >> +digit >> -(char_('.') >> +digit)]];
boolean_value %= raw[lit("true") | lit("false")];

Все эти правила на выходе выдают строку (например, название идентификатора). Оператор %= в конструкции “правило %= парсер” позволяет сгенерированное парсером значение передать прямо на выход парсера. Далее можно прямо в других правилах использовать их результаты:

string = quoted_string [op(_val, _1, "string")];
number = numeric_value [op(_val, _1, "number")];
boolean = boolean_value [op(_val, _1, "bool")];
empty = lit("empty") [op(_val, std::string(), "empty")];
identifier = id [op(_val, _1, compiler::identifier())];

Как видно, здесь в каждом случае вызывается парсер, например, quoted_string, а далее его значение используется для вызова функтора op. В первом случае (правило string) на вход функтора придет: в качестве первого аргумента – то значение, которое формируется (в моем случае – элемент дерева XML), в качестве второго – результат работы парсера quoted_string, в третьем – срока “string”. И уже функтор сделает все необходимые действия с XML-деревом.

Определение функции не намного сложнее – в частности брагодаря тому, что я генерирую XML. Параметры функции достаточно просто «прикрепить» к xml-узлу функции в качестве «детей»:

function =
id [op(_val, _1, compiler::function())]
>> '('
>> -(parameter [op(_val, _1)] % ',')
>> ')';

Выражение «parameter [op(_val, _1)]» как раз прикрепляет детей к функции: в функтор op передается родитель (узел функции, который только что заполнен с помощью «op(_val, _1, compiler::function())») и «ребенок» (узел параметра, который сгенерировал парсер parameter).

Итого, без учета бинарных и тернарных операций (операций с 2 и 3 аргументами, такие как */+-?:) получается следующее правило:

factor =
function [_val = _1]
| boolean [_val = _1]
| empty [_val = _1]
| identifier [_val = _1]
| string [_val = _1]
| number [_val = _1]
| ('(' >> expression [_val = _1] >> ')')
| (lit('!') [op(_val, "not", compiler::function())] >> factor [op(_val, _1)])
| (lit('-') [op(_val, "neg", compiler::function())] >> factor [op(_val, _1)])
| ('+' >> factor [_val = _1])
;

При обработке операций не следует забывать об их приоритете. Его легко реализовать «вкладывая» определения одной операции в определение другой:

addition =
multiplication [_val = _1]
>> *( ('+' >> multiplication [op(_val, _1, "add", true)])
| ('-' >> multiplication [op(_val, _1, "sub", true)])
)
;

multiplication =
factor [_val = _1]
>> *( ('*' >> factor [op(_val, _1, "mul", true)])
| ('/' >> factor [op(_val, _1, "div", true)])
)
;

В данном случае функции умножения и деления распарсятся раньше, чем сложение и вычитание, так как умножение «вложено» в сложение. Это произойдет потому, что для сложения нужно разобрать сначала все внутренние правила, в том числе умножение, которое я вложил внутрь. Собственно, что и требовалось.

Суммируя все вместе

Весь исходный код можно взять здесь: http://download.yandex.ru/bar/tools/easierxb-src.zip (внутри архива – проект для сборки под Windows и MacOS).

Пример входного файла: http://download.yandex.ru/bar/tools/easierxb-example.zip