C++: Строки в доспехах

В статье рассматривается частный случай применения Концепции Разделяемых Преобразований (Separable Transformation Concept, STC). Описываемый подход позволяет компактно записывать нетривиальные преобразования символьных последовательностей (строк), независимо от их типа. Предлагается практическая реализация методики на языке C++.

Введение.

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

Безусловно, знакомство с регулярными выражениями и возможность их применения (здорово, когда она есть!) позволяет разработчику по-новому и с большим оптимизмом взглянуть на насущные проблемы — регулярные выражения позволяют сделать код компактнее, привнося дополнительную полезную управляемость: в отличие от реализаций алгоритмов, паттерны не привязываются к программе жёстким образом, их можно хранить отдельно, например, в настройках программы. Другое дело, стоит ли применения регулярных выражений каждая пустяковая задачка синтаксического разбора параметров командной строки, системного пути или сетевого адреса? У многих программистов этот вопрос вызвал бы сомнения. Да, технология сама по себе может быть очень эффективной, но одного этого недостаточно — нужно эффективно её применять!

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

Идея о том, как создать себе более комфортные условия для работы со строками в мире разных библиотек, кодировок и форматов данных была навеяна большой обзорной статьей Александра Александровича Степанова «Notes on Programming», содержащей (впрочем, как и другие его работы) фундаментально важные идеи, составляющие основы обобщённого и концептуального программирования.

Пересматривать свои взгляды на привычные вещи — дело нелёгкое, но ещё сложнее понять, в какой момент стоит этим заняться. К сожалению, не сразу стало очевидным, что для создания универсальной по отношению к типам и при этом неограниченно расширяемой функционально библиотеки обработки строк, требуется всего пять тривиальных первичных шаблонов, специализируемых по мере необходимости для каждого конкретного типа. Любые сколь угодно «хитрые» операции со строками могут быть обобщённо описаны, опираясь только на эти специализации.

Хорошо, проблема с тем, каким образом организовать библиотеку, подходящую для любых типов, вроде бы, решена. Второй важнейший вопрос — какие элементы (функции, шаблоны, классы) стоит в неё включить? Хотелось бы сделать эту библиотеку как можно меньше, ведь мало кто любит тратить время на изучение документации, да и само написание документации есть нечто, до чего руки могут просто не дойти. Слишком общие функции не позволяют компактно решать частные задачи, а функций, ориентированных на частные задачи — несчётное множество. Здесь оказывается полезным обратить внимание на структуру операций, выполняемых со строками.

Оказывается, что все операции, выполняемые со строками, можно разделить на две группы — операции поиска и операции преобразования. Естественно, раздельное описание этих групп займёт гораздо меньше места, чем описание некоторого подмножества из их произведения. На практике чаще всего требуются операции, сочетающие в себе как поиск, так и преобразование, например, операции «замена» или «разбиение». Остаётся подобрать удобную языковую конструкцию, которая бы позволяла разработчику эффективно комбинировать операции поиска и преобразования в том месте кода, где это требуется. В одной из первых версий библиотеки CSF/Strings, о которой пойдет речь далее, было реализовано 40 операций позиционирования (поиска) и 11 операций преобразования, что позволяло использовать 440 готовых сложных преобразований, с избытком покрывая большинство возникавших задач, размер библиотеки при этом оставался сравнительно небольшим — около сотни килобайт в исходном коде на С++, и это притом, что более половины кода составлял так называемый «синтаксический сахар».

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

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

Листинг 1. Пример применения технологии.
#include #include #include <csf/strings/strings.h>
// подключение специализаций первичных шаблонов для std::basic_string<...>
#include <csf/strings/support/stl.h>

// оборачивание std::string в "доспехи"
typedef strings::shell<std::string, strings::case_sensitive<char> > shell_t;

int main (const int argc, const char** argv)
{
    std::string t(
        "Some of the words  in this text have been marked out\n"
        "by enclosing between special  tags.  The code\n"
        "below  will  extract  all  of      the  marked  out  words,\n"
        "strip the tags and normalize        spaces in the text."
    );

    shell_t s = t;

// вывод всех слов, заключенных между тегами
    s. Collect( std::ostream_iterator<std::string>( std::cout, "\n" ) )
        . between_each( "", "" );

// удаление тегов
    s. Erase(). each( "" ). Erase(). each( "");

// нормализация пробелов в тексте путем замены групп пробельных символов одним пробелом
    s. Replace( '\x20' ). each_group_of( strings::symbols<char>::spacers() );

// строка в доспехах все еще может вести себя как обычная строка...
    std::cout << s->c_str() << std::endl;

    return 0;
}

Как видно из примера, технология позволяет наращивать функционал произвольного типа (в данном случае речь идет об std::string), сохраняя при этом его исконные свойства. Единственным условием применимости технологии к некоторому типу является специализация для данного типа пяти первичных шаблонов.

Три основные идеи.

Итак, перейдем к более конкретному описанию основных идей, из которых выводится концепция библиотеки компактных форм записи строковых преобразований.

Идея первая: все преобразования строк должны осуществляться посредством ограниченного набора тривиальных первичных шаблонов, специализируемых по мере необходимости для каждого конкретного типа. Легко проверить, что любое преобразование строки может быть выражено при помощи операций измерения длины «length», получения доступа к отдельному символу «at», выделения подстроки «capture», удаления подстроки «erase» и вставки подстроки «insert». Таким образом, специализируя перечисленные шаблоны для произвольного стороннего типа, мы получаем возможность использовать для этого типа все преобразования, описываемые библиотекой.

Идея вторая: сложные операции должны представляться комбинациями простых операций, описываемых независимо друг от друга, в частности, операции позиционирования (поиска) и преобразования должны быть разделены. Определим позиционирование (P) как операцию выделения в исходной строке некоторого произвольного подмножества символов, а преобразование (T) как операцию на выделенном подмножестве. Синтаксически сложное преобразование, являющееся комбинацией P и T удобно записывать в функциональной форме
T( исходная строка, параметры преобразования ).T( параметры позиционирования )

или в объектной форме
(исходная строка).T( параметры преобразования ).T( параметры позиционирования )

Объектная форма записи удобна тем, что позволяет комбинировать несколько сложных преобразований:
(исходная строка).T1( ... ).P1( ... ).T2( ... ).P2( ... ). ... Tn( ... ).Pn( ... )

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

Идея третья: не нужно создавать копии строки без явной необходимости. В самом деле, далеко не всегда нужны промежуточные стадии многоэтапных преобразований, нередко актуальность теряет даже исходное значение и важен только результат. Ввиду сказанного, будем считать, что все преобразования являются действиями, то есть изменяют исходную строку. Для случаев, когда исходное значение следует сохранить, вводится специальный метод создания копии:
(результирующая строка) = (исходная строка).Copy().T( ... ).P( ... );


Шаблоны преобразования.

Из всего множества операций преобразования было выбрано 11 наиболее общих и востребованных на практике, их краткое описание приводится в Таблице 1. Функциональная форма записи преобразований, в отличие от объектной, требует двух дополнительных параметров — входной строки «in» и функтора «cmp», производящего сравнение отдельных символов. Каждый из приведенных вызовов является генератором класса positioning, предоставляющего доступ к шаблонам позиционирования.

Таблица 1. Шаблоны преобразования.

Вызов (генератор):	Действие:	Аргументы:
Capture(in, out, cmp)	Захват.	out — возвращаемое значение по-умолчанию;
Erase(in, cmp)	Удаление.
Keep(in, cmp)	Сохранение.
Insert(in, sub, bs, cmp)	Вставка.	sub — вставляемая подстрока; bs — положение вставки;
Replace(in, rep, cmp)	Замена.	rep — заменяющая подстрока;
Enclose(in, left, right, cmp)	Заключение.	left и right — левый и правый заключающий символы;
Pad(in, pattern, pad_length, cmp)	Выравнивание.	pattern — шаблон выравнивающего заполнения; pad_length — длина выравнивания;
Fill(in, pattern, cmp)	Заполнение.	pattern — шаблон заполнения;
Collect(in, iterator, cmp)	Сбор.	iterator — итератор вывода;
Cut(in, iterator, cmp)	Изъятие.	iterator — итератор вывода;
Transform(in, out, agent, cmp)	Произвольное преобразование.	out — возвращаемое значение по-умолчанию; agent — функтор произвольного преобразования;
Общие аргументы: in — входная строка; cmp — функтор посимвольного сравнения.

Шаблоны позиционирования.

Операций позиционирования, часто применяемых на практике оказывается гораздо больше — всего 40. Впрочем, эти операции легко поддаются интуитивной классификации, что существенно упрощает запоминание их наименований. Операции позиционирования можно разделить на две первичные группы — абсолютные, оперирующие с координатами в последовательности и относительные, производящие поиск отдельных элементов. К абсолютным относятся операции operator(), from_to, all, char_at, fisrt_char, last_char, from и to. Остальные операции относятся к относительным, их можно разделить на однократные, выделяющие одну область в строке, и многократные, перечисляющие несколько областей. Дальнейшая классификация выводится из Таблицы 2.

Таблица 2. Методы объекта позиционирования.

Метод:	Действие:
1. Абсолютные операции.
operator()( from, count )	Выделяет область длиной в count символов, начиная со смещения from.
from_to( from, to )	Выделяет область [from, to).
all()	Вылеляет всю строку.
char_at( pos )	Выделяет единственный символ по смещению pos.
first_char()	Выделяет первый символ.
last_char()	Выделяет последний символ.
from( pos )	Выделяет всё до конца строки, начиная со смещения pos.
to( pos )	Выделяет всё от начала строки, заканчивая (не включительно) смещением pos.
2. Однократные операции «от первого включения и до конца».
from_first( subject, bounds, after)	Выделяет всё до конца строки, начиная с первого после смещения after включения подстроки subject.
from_first_of( subject, bounds, after)	Выделяет всё до конца строки, начиная с первого после смещения after включения любого из символов, входящего в subject.
from_first_not_of( subject, bounds, after)	Выделяет всё до конца строки, начиная с первого после смещения after включения любого из символов, не входящего в subject.
3. Однократные операции «от последнего включения и до конца».
from_last( subject, bounds, before)	Выделяет всё до конца строки, начиная с последнего до смещения before включения подстроки subject.
from_last_of( subject, bounds, before)	Выделяет всё до конца строки, начиная с последнего до смещения before включения любого из символов, входящего в subject.
from_last_not_of( subject, bounds, before)	Выделяет всё до конца строки, начиная с последнего до смещения before включения любого из символов, не входящего в subject.
4. Однократные операции «от начала и до первого включения».
to_first( subject, bounds, after)	Выделяет всё от начала строки, заканчивая первым после смещения after включением подстроки subject.
to_first_of( subject, bounds, after)	Выделяет всё от начала строки, заканчивая первым после смещения after включением любого из символов, входящего в subject.
to_first_not_of( subject, bounds, after)	Выделяет всё от начала строки, заканчивая первым после смещения after включением любого из символов, не входящего в subject.
5. Однократные операции «от начала и до последнего включения».
to_last( subject, bounds, before)	Выделяет всё от начала строки, заканчивая последним до смещения before включением подстроки subject.
to_last_of( subject, bounds, before)	Выделяет всё от начала строки, заканчивая последним до смещения before включением любого из символов, входящего в subject.
to_last_not_of( subject, bounds, before)	Выделяет всё от начала строки, заканчивая последним до смещения before включением любого из символов, не входящего в subject.
6. Однократные операции «выбора первого включения».
first( subject, after )	Выделяет первое после смещения after включение подстроки subject.
first_of( subject, after )	Выделяет первое после смещения after включение любого символа, входящего в subject.
first_not_of( subject, after )	Выделяет первое после смещения after включение любого символа, не входящего в subject.
7. Однократные операции «выбора последнего включения».
last( subject, before )	Выделяет последнее до смещения before включение подстроки subject.
last_of( subject, before )	Выделяет последнее до смещения before включение любого символа, входящего в subject.
last_not_of( subject, before )	Выделяет последнее до смещения before включение любого символа, не входящего в subject.
8. Однократные операции «выбора между включениями».
between_first( left, right, bounds, after)	Выделяет область, заключенную между первой парой включений left и right.
between_last( left, right, bounds, before)	Выделяет область, заключенную между последней парой включений left и right.
between( left, right, bounds )	Выделяет область, заключенную между первым включением left и последним включением right.
9. Многократные операции «перечисления включений».
each( subject )	Перечисляет все включения subject.
each_of( subject )	Перечисляет по отдельности все символы, входящие в subject.
each_not_of( subject )	Перечисляет по отдельности все символы, не входящие в subject.
each_group_of( subject )	Перечисляет группами все символы, входящие в subject.
each_group_not_of( subject )	Перечисляет группами все символы, не входящие в subject.
10. Многократные операции «разделения по включениям».
split_by( subject, accept_empty )	Перечисляет все области, разделяемые включениями subject.
split_by_any_of( subject, accept_empty )	Перечисляет все области, разделяемые включениями групп символов, входящих в subject.
split_by_any_not_of( subject, accept_empty )	Перечисляет все области, разделяемые включениями групп символов, не входящих в subject.
11. Специальные относительные операции.
between_each( left, right, accept_empty, bounds )	Перечисляет все области, заключенные между парами включений left и right.
first_token( spacers, quotes, escapers, accept_empty, after )	Выделяет первый знак*.
each_token( spacers, quotes, escapers, accept_empty)	Перечисляет все знаки*.
Общие агрументы: bounds - определяет выполнение операции на границе области (включает или исключает); accept_empty - флаг, определяющий, должны ли обрабатываться выделенные области нулевой длины. *Под знаком понимается последовательность символов, не входящих в число разделительных (spacers) или произвольная последовательность символов, заключенная в кавычки (quotes). Последовательность символов, заключенная в кавычки, может также содержать сами символы кавычек, при условии, что они экранированы специальными экранирующими символами (escapers). Экранирующие символы могут экранировать друг друга и, таким образом, также могут входить в состав знака.

Заключительное замечание о специализациях в C++.

Наряду с возможностью применения обобщенных преобразований к произвольным типам строк было бы неплохо получить эту возможность также и для шаблонов строковых типов, каковым является стандартный шаблон std::basic_string, имеющий три параметра Char, Traits и Allocator. Объявления тривиальных первичных шаблонов для std::basic_string могли бы выглядеть как показано в Листинге 2:

Листинг 2. Перегрузка тривиального первичного шаблона «length» для std::basic_string.
template <typename _Char, typename _Traits, typename _Allocator>
int length (const std::basic_string<_Char, _Traits, _Allocator>& s)
{
    return (int) s. size();
}

И это даже могло бы нормально работать, но при одном очень неудобном условии: чтобы участвовать в выборе первичного шаблона при инстанцировании любого ссылающегося на него шаблона-преобразования, все подобные объявления должны находится в том же контексте, что и сам шаблон-преобразование, то есть перед его объявлением. Дело в том, что приведенное выше определение является не специализацией, а перегрузкой первичного шаблона length<_Sequence>, поскольку в C++ нет понятия частичной специализации шаблонов функций. Частичной специализации шаблонов функций нет, зато есть частичная специализация шаблонов классов, следовательно, для тривиальных первичных шаблонов можно использовать классы-адаптеры со статическими методами, как показано в Листинге 3:

Листинг 3. Объявление и специализация тривиального первичного шаблона «length».
// Спецификация класса-адаптера.
template <typename _Sequence>
struct adapter_length
{
    static int f (const _Sequence& s);
};
// ...
// Объявление первичного шаблона.
template <typename _Sequence>
inline int length (const _Sequence& s)
{
    return adapter_length<_Sequence>::f( s );
}
// ...
// Частичная специализация для std::basic_string.
template <typename _CharT, typename _Traits, typename _Alloc>
struct adapter_length<std::basic_string<_CharT,_Traits,_Alloc> >
{
    static int f (const std::basic_string<_CharT,_Traits,_Alloc>& s)
    {
        return (int) s. size();
    }
};


Ознакомительная версия.

В настоящий момент ознакомительная версия библиотеки CSF/Strings вместе с кое-как сгенерированной справкой доступна по ссылке. Не смотря на то, что несколько программ устойчиво работают с использованием этой версии, она, скорее всего, содержит ошибки. Версия тестировалась с несколькими компиляторами, но не исключено, что с некоторыми она работать откажется. Актуальная версия библиотеки с полным набором тестов будет доступна как из репозитория, так и в виде архива. Принимаются вопросы и предложения.