Category Archives: Software

Conar 6: Parser — окончание

Начало

Предыдущая часть

Последнее, что осталось «дописать» — собственно организация процесса разбора, а именно: поиск ключей и выборка параметров. При поиске ключей проверяем четыре варианта: «ключ» «…» «другой ключ», «ключ=значение», «-ключключ…ключ» и «ключзначение» (именно в таком порядке). Третий вариант применяется только для однобуквенных ключей.

Все нижеприведённые функции являются членами класса Parser.

Функция, проверяющая параметр на удовлетворение первому варианту («ключ»):

bool is_direct_key(const std::string &param) const
{
  return mapper.count(param) != 0;
}

Функция, проверяющая параметр на удовлетворение второму варианту («ключ=значение»), возвращает позицию знака «=»:

size_t is_key_equals(const std::string &param) const
{
  const auto eq_pos = param.find('=');
  if (eq_pos == std::string::npos)
    return 0;

  return is_direct_key(param.substr(0, eq_pos))? eq_pos: 0;
}

Функция, проверяющая параметр на удовлетворение третьему варианту («-ключключ…ключ»):

bool is_key_sequence(const std::string &param) const
{
  const auto psz = param.size();
  if (psz < 3 || param[0] != '-')
    return false;

  char key[3] {'-'};
  for (size_t i = 1; i < psz; ++i)
  {
    key[1] = param[i];
    if (mapper.count(key) == 0)
      return false;
  }

  return true;
}

Наконец, функция, проверяющая параметр на удовлетворение четвёртому варианту («ключзначение»), возвращает позицию первого символа значения:

size_t is_key_value(std::string param) const
{
  while (!param.empty())
  {
    param.pop_back();
    if (is_direct_key(param))
      return param.size();
  }

  return 0;
}

Данная функция проверяет «с конца», пытаясь подобрать самый длинный ключ, что может быть нежелаемым поведением (например, мы хотим использовать в такой манере только однобуквенные ключи — такую опцию я хочу добавить позже).

Используя определённые выше функции можно набросать скелет цикла обработки последовательности параметров:

  Unparsed_parameters unparsed;
  Parameters params(from, to);
  for (auto key = begin(params), params_end = end(params),
            prev_key = params_end;
    key != params_end;)
  {
    // Check all possible variants one by one.
    if (is_direct_key(*key))
    {
      // The only situation in which we may have a sequence
      // of argument parameters after the key.

      prev_key = key;
    }
    else if (const auto eq_pos = is_key_equals(*key))
    {    }
    else if (is_key_sequence(*key))
    {    }
    else if (const auto val_pos = is_key_value(*key))
    {    }
    else
    {
      // Nope, this is not a valid parameter of any form.
      unparsed.emplace_back(move(*key));
      ++key; // next...
    }
  }
  return unparsed;

Если сработало условие is_direct_key(*key), то надо найти следующий ключ, а всё что между передать диапазоном обработчику опции, соответствующей *key. Первая мысль: запоминать последнюю такую позицию (итератор prev_key) и вызывать обработчик, когда был найден правый конец. Недостаток: это надо делать под каждым if’ом, хотелось бы избежать такого дублирования кода…

Подумав, как можно разобраться с данной ситуацией, я остановился на варианте «умного» кода (здесь «умный» — не комплимент), а именно, использовать приём, известный как «хэширование»:

    size_t pos;
    if
    (
      int situation =
        is_direct_key(*key)?          1
      : (pos = is_key_equals(*key))?  2
      : is_key_sequence(*key)?        3
      : (pos = is_key_value(*key))?   4
      : 0 // --> else
    )
    {   }
    else
    {
      // Nope, this is not a valid parameter of any form.
      unparsed.emplace_back(move(*key));
      ++key; // next...
    }

Теперь я могу избежать дублирования кода, а необходимая информация о случае хранится в situation и pos. Хотя нет, есть ещё случай, когда ключ — последний, дальше до конца идут только его аргументы… Продублировать вызов обработчика после цикла? Думаю, лучше ситуацию «конец параметров» тоже занести в situation:

  for (auto key = begin(params), params_end = end(params),
            prev_key = params_end;;)
  {
    size_t pos;
    if
    (
      int situation =
        key == params_end?            1
      : is_direct_key(*key)?          2
      : (pos = is_key_equals(*key))?  3
      : is_key_sequence(*key)?        4
      : (pos = is_key_value(*key))?   5
      : 0 // --> else
    )

Интересно, как можно было бы записать то же самое чище и без дублирования кода…

Определим для удобства записи функцию, «вытаскивающая» ссылку обработчик по ключу:

template <class Key>
Handler& handler_of(const Key &key)
{
  return std::get<0>(options[mapper.at(key)]);
}

Теперь я могу, наконец, записать, что делается под if’ом:

  if (prev_key != params_end)
  {
    for (auto last = handler_of(*prev_key)
                     (prev_key + 1, key);
         last != key; ++last)
    { unparsed.emplace_back(move(*last)); }
    prev_key = params_end;
  }

  switch (situation)
  {
  case 1:
    return unparsed;

  case 2:
    prev_key = key;
    break;

  case 3: case 5:
    {
      const int has_equals = situation == 3;
      auto k = key->substr(0, pos);
      key->erase(0, pos + has_equals);
      if (handler_of(k)(key, key + 1) == key)
        unparsed.emplace_back(move(*key));
    }
    break;

  case 4:
    for (size_t i = 1, sz = key->size(); i < sz; ++i)
    {
      char k[3] { '-', (*key)[i] };
      handler_of(k)(params_end, params_end);
    }
  }

Красотой этот код не отличается, увы. И надо написать для него тесты.

В результате тестирования была исправлена ветка else:

    else
    {
      // Nope, this is not a valid parameter of any form.
      if (prev_key == params_end)
        unparsed.emplace_back(move(*key));
    }

При тестировании со строковыми параметрами обнаружилась старая ошибка: оператор >> читает «словами», однако в случае строковых параметров их надо не «читать» (с пробельными символами-разделителями, да), а просто «отдавать» целиком. Для этого я заменю явное чтение с помощью >> на вызов новой функции impl::read_value:

/// Tries to read a generic val from string str.
template <class S, class T>
inline bool read_value
  (std::istringstream &reader, S &&str, T &val)
{
  reader.str(std::forward<S>(str));
  return reader >> val;
}

/// Forwards a string instead of reading it.
inline bool read_value
  (std::istringstream&, std::string &&str, std::string &val)
{
  val = std::move(str);
  return true;
}

Забавно, что после этой замены сработал тест value_out (код ошибки 7) — из-за того, что теперь «чтение» забирает строки с помощью move, а не копирует их.

Вместе с тестами таки вылезло за пределы 1000 строк. В итоге, я не решился использовать C++17 (только static_assert без сообщения, а можно было декомпозиционное определение и string_view, например).

Код данного варианта целиком.

Conar 5: структура данных Parser

Начало

Предыдущая часть

Займёмся классом Parser.

При добавлении опции требуется строить отображение ключ -> (обработчик, инфо). Чтобы не дублировать пары (обработчик, инфо) (что важно для «обработчика», который может хранить изменяемое состояние), можно или оборачивать их в shared_ptr и отображать ключ в shared_ptr, или складывать в отдельный контейнер и отображать ключ в индекс или итератор. Второй вариант мне нравится больше.

Обработчик будем приводить к типу Handler, объявленному следующим образом:

using Parameters = std::vector<std::string>;
using PIt = Parameters::iterator;
using Handler = std::function<PIt(PIt, PIt)>;

Теперь определим собственно структуры данных, содержащиеся в объекте Parser. Mapper отображает ключи в индексы вектора Options.

using Option = std::tuple<Handler, Option_info>;
using Options = std::vector<Option>;
using Mapper = std::map<std::string, std::size_t>;
Options options;
Mapper mapper;

Напишем код, добавляющий опцию (тройку «обработчик, ключи, инфо«).

/// Add an option description.
/// Use functions flag, value and seq to make an option.
template <class Opt>
Parser& operator()(Opt option)
{
  using namespace std;
  static_assert(tuple_size<Opt>::value == 3);

  // Add the option to options.
  const auto index = options.size();
  options.emplace_back(move(get<0>(option)),
                       move(get<2>(option)));

  // Register keys of the option.
  for (auto &key: get<1>(option))
    mapper.emplace(key_prep(move(key)), index);

  return *this;
}

Функция key_prep добавляет знаки «-» в начало строки:

static std::string key_prep(std::string &&key)
{
  if (!key.empty() && std::isalnum(key[0]))
  {
    if (key.size() == 1)
      key.insert(0, 1, '-');
    else
      key.insert(0, "--");
  }

  return move(key);
}

Теперь можно заполнить тело функции help, которую можно использовать и в целях тестирования. Подумав, я решил убрать параметр «ширина строки», поскольку это не очень нужное усложнение. Реальную ширину строки консоли нельзя получить стандартными методами, а насильная вставка перевода строки может приводить к появлению избыточных пустых строк. Функция получилась длинная, но простая:

/// Construct a help message.
std::string help(
  std::size_t key_column_width = 20,
  const char *line_sep = "\n\n") const
{
  using namespace std;
  ostringstream write;
  write.setf(ios::left);

  // Option index -> first key (iterator).
  vector<Mapper::const_iterator> key_by_index(options.size());
  for (auto p = mapper.end(), b = mapper.begin();;)
  {
    --p;
    key_by_index.at(p->second) = p;
    if (p == b)
      break;
  }

  // Make the text.
  for (auto p = mapper.begin(), e = mapper.end(); p != e; ++p)
  {
    if (p->first.size() < key_column_width)
    {
      write.width(key_column_width);
      write << p->first;
    }
    else
    {
      write.width(0);
      write << p->first << '\n';
    }

    const auto pivot = key_by_index[p->second];
    if (pivot == p)
      write << get<1>(options[p->second]);
    else
      write << ("See " + pivot->first + ".");
    write << line_sep;
  }

  return write.str();
}

Самую сложную часть парсера — собственно разбор списка параметров — из-за недостатка времени в данный момент я оставил для следующей части.

Код данного варианта целиком.

Продолжение следует…

Conar 4: больше SFINAE

Начало

Предыдущая часть

Займёмся функциями, обеспечивающими чтение последовательностей. Первой такой функцией у меня будет не seq, а вариант value, который записывает каждое распознанное значение по итератору вывода.

template <class T, class OutIt> inline
auto value(OutIt dest,
  Possible_keys keys, Option_info info = {},
  std::enable_if_t<
    std::is_base_of<
      std::output_iterator_tag,
    typename std::iterator_traits<OutIt>::iterator_category>
      ::value, int> = 0)
{
  using std::move;
  return value_parser<T>(
    [dest](T val) mutable { *dest++ = std::move(val); },
    move(keys), move(info));
}

Мелкая неприятность: пользователь должен явно указывать тип считываемых значений T. В принципе, можно сделать два варианта: аналогичный приведённому выше и выводящий тип значения с помощью iterator_traits::value_type. К сожалению, стандартные итераторы вывода, реализующие вставку в контейнеры, определяют value_type как void, делая тип элементов контейнера невыводимым для функции value. Кроме того, заметим, что forward_iterator_tag наследует от input_iterator_tag, но не от output_iterator_tag.

Введём простенькие вспомогательные определения.

/// Check if iterator It is compatible with category Cat.
template <class It, class Cat>
using Has_iterator_category =
  is_base_of<Cat,
    typename iterator_traits<It>::iterator_category>;

/// Check if iterator It is an output iterator.
template <class It>
using Is_output_iterator =
  Has_iterator_category<It,
    output_iterator_tag>;

/// Check if iterator It is a forward iterator.
template <class It>
using Is_forward_iterator =
  Has_iterator_category<It,
    forward_iterator_tag>;

/// Check if iterator It declares void as its value type.
template <class It>
using Has_void_value =
  is_same<void,
    typename iterator_traits<It>::value_type>;

Теперь два варианта value, пишущих через итераторы можно определить следующим образом:

/// Construct a value option, which writes values through an iterator.
/// Explicitly typed variant when the type is not derivable from OutIt.
template <class T, class OutIt> inline
auto value(OutIt dest,
  Possible_keys keys, Option_info info = {},
  std::enable_if_t<
    impl::Is_output_iterator<OutIt>::value &&
    impl::Has_void_value<OutIt>::value,
    int> = 0)
{
  using std::move;
  return value_parser<T>(
    [dest](T val) mutable { *dest++ = std::move(val); },
    move(keys), move(info));
}

/// Construct a value option, which writes values through an iterator.
template <class OutIt> inline
auto value(OutIt dest,
  Possible_keys keys, Option_info info = {},
  std::enable_if_t<
    (impl::Is_output_iterator<OutIt>::value ||
     impl::Is_forward_iterator<OutIt>::value) &&
    !impl::Has_void_value<OutIt>::value,
    int> = 0)
{
  using std::move;
  using T = typename std::iterator_traits<OutIt>::value_type;
  return value_parser<T>(
    [dest](T val) mutable { *dest++ = std::move(val); },
    move(keys), move(info));
}

Тестирование этих определений вскрыло небольшое упущение: value_parser также должна создавать mutable-замыкание, если мы хотим упаковать в него своё mutable-замыкание, что требуется, в свою очередь, из-за необходимости передвигать итератор на каждом вызове и сохранять его изменённую версию между вызовами. Соответственно, я также добавил mutable в flag_parser и seq_parser.

Теперь можно перейти к seq.

Вариант seq, заполняющий условно бесконечную последовательность по итератору, написать не составит большого труда. Полная аналогия с вариантами value, указанными выше. Как и в случае с value, предполагается, что «места хватит» (интересно, сколько параметров командной строки можно скормить в распространённых ОС/интерпретаторах?).

Приведу одну из них. Вторая абсолютно аналогична.

template <class T, class OutIt> inline
auto seq(OutIt dest,
  Possible_keys keys, Option_info info = {},
  std::enable_if_t<
    impl::Is_output_iterator<OutIt>::value &&
    impl::Has_void_value<OutIt>::value,
    int> = 0)
{
  using std::move;
  return seq_parser<T>(
    [dest](T *from, T *to) mutable
    {
      while (from != to)
        *dest++ = std::move(*from++);
    },
    move(keys), move(info));
}

Для удобства пользователя можно добавить ещё три варианта seq, которые принимают непосредственно контейнеры, извлекают тип элементов через вложенное объявление value_type и выбирают способ вставки (push_back, insert или push) в зависимости от того, какой подходит. Для различения между push_back и insert (линейными и ассоциативными контейнерами) нам в качестве заготовки пригодится SFINAE-костыль Is_incrementable. Последний вариант seq подразумевает вставку в адаптер вроде std::stack с помощью вызова push.

/// Check if container C supports push_back(T&&).
template <class C, class T>
struct Supports_push_back
{
  template <class Y>
  static true_type check(decltype((void)(
    declval<Y>().push_back(declval<T>())
  ), 1));

  template <class Y>
  static false_type check(unsigned);

  using type = decltype(check<C&>(1));
  static constexpr bool value = type::value;
};

Два других детектора (Supports_insert и Supports_push) полностью аналогичны (да, макрос сюда так и просится). Вспомогательные определения для краткости записи сигнатур функций seq:

template <class C>
using Use_push_back =
  Supports_push_back<C, typename C::value_type>;

template <class C>
using Use_insert = bool_constant<
  Supports_insert<C, typename C::value_type>::value &&
  !Use_push_back<C>::value>;

template <class C>
using Use_push = bool_constant<
  Supports_push<C, typename C::value_type>::value &&
  !Use_push_back<C>::value &&
  !Use_insert<C>::value>;

Теперь вариант seq, который заполняет контейнер, предоставляющий функцию push_back, может быть записан следующим образом:

/// Construct a seq option,
/// which appends a "push_back" container.
template <class Container> inline
auto seq(Container &cont,
  Possible_keys keys, Option_info info = {},
  std::enable_if_t<
    impl::Use_push_back<Container>::value,
    int> = 0)
{
  using std::move;
  using T = typename Container::value_type;
  return seq_parser<T>(
    [&cont](T *from, T *to) mutable
    {
      while (from != to)
        cont.push_back(std::move(*from++));
    },
    move(keys), move(info));
}

Ещё два варианта seq полностью аналогичны.

Код данного варианта целиком.

Продолжение следует.

Conar 3: перегрузка функций и SFINAE

Часть 1

Часть 2

Написанный к данному моменту код всё ещё ничего не делает. Попробуем сделать функции-«упаковщики», создающие опции на основе заданных обработчиков и значений Possible_keys и Option_info. Роль DTO будет выполнять std::tuple<Обработчик, Possible_keys, Option_info>. Всего предполагается три семейства функций, отвечающих трём видам опций (ранее трём классам): flag, value и seq.

Предполагается, что данные функции будут перегружены. Для «выключения» ненужных шаблонов, вызывающих проблемы с неединственностью возможного варианта вызова перегруженной функции, C++11 и новее предлагает std::enable_if. Однако здесь нам неудобно ставить enable_if «впереди» (в возвращаемом типе), т.к. функции возвращают кортеж, включающий член анонимного типа. Впрочем, enable_if всегда можно поставить последним параметром.

Базовые функции имеют следующий вид:

/// Create a flag option with a custom handler.
template <class FlagHandler> inline
auto flag(FlagHandler handler,
  Possible_keys keys, Option_info info = {},
  std::enable_if_t<
    impl::Is_flag_handler<FlagHandler>::value, int> = 0)
{
  using std::move;
  return std::make_tuple(
    [f = move(handler)](auto from, auto to)
    {
      f();
      return from;
    },
    move(keys), move(info));
}

/// Create a value option with a custom handler.
template <class T, class ValueHandler> inline
auto value(ValueHandler handler,
  Possible_keys keys, Option_info info = {},
  std::enable_if_t<
impl::Is_value_handler_for<ValueHandler, T>::value, int> = 0)
{
  using std::move;
  return std::make_tuple(
    [f = move(handler)](auto from, auto to)
    {
      if (from == to)
        return from;

      std::istringstream reader(*from);
      T val {};
      if (reader >> val)
      {
        f(std::move(val));
        ++from;
      }

      return from;
    },
    move(keys), move(info));
}

/// Create a value sequence option with a custom handler.
template <class T, class SeqHandler> inline
auto seq(SeqHandler handler,
  Possible_keys keys, Option_info info = {},
  std::enable_if_t<
    impl::Is_seq_handler_for<SeqHandler, T>::value, int> = 0)
{
  using std::move;
  return std::make_tuple(
    [f = move(handler)](auto from, auto to)
    {
      std::vector<T> values;
      for (std::istringstream reader; from != to; ++from)
      {
        reader.str(*from);
        T val {};
        if (!(reader >> val))
          break;

        values.emplace_back(std::move(val));
        reader.clear();
      }

      f(values.data(), values.data() + values.size());
      return from;
    },
    move(keys), move(info));
}

Теперь определим их перегруженные варианты для конкретных простых случаев.

Простейший случай — установка булевской переменной в соответствии с присутствием заданного флага в опциях.

/// Construct a flag option, which sets a Boolean variable.
inline auto flag(bool &flag_var,
  Possible_keys keys, Option_info info = {})
{
  using std::move;
  return flag(
    [&flag_var]() { flag_var = true; },
    move(keys), move(info));
}

Более хитрый случай — подсчёт количества повторения заданного флага среди набора аргументов командной строки. Для этого будем передавать объект, для которого определён инкремент. Чтобы определить, доступна ли операция инкремента, воспользуемся стандартным костылём: SFINAE (принцип действия std::enable_if тоже основан на SFINAE). Вид этого костыля вызывает стойкое желание оформить соответствующий макрос…

template <class C>
struct Is_incrementable
{
  template <class Y>
  static true_type check(decltype(
    (void)(++declval<add_lvalue_reference_t<Y>>()), 1));

  template <class Y>
  static false_type check(unsigned);

  using type = decltype(check<C>(1));
  static constexpr bool value = type::value;
};

Собственно, код-«детектор» это ++declval<add_lvalue_reference_t<Y>>(), всё остальное — «boilerplate code». std::declval<Y> по умолчанию возвращает rvalue-ссылку, для которой ++ не определён, поэтому здесь следует предварительно сформировать «обычную» (lvalue) ссылку.

/// Construct a flag option, which increments a variable.
template <class C> inline
auto flag(C &counter,
  Possible_keys keys, Option_info info = {},
  std::enable_if_t<
    impl::Is_incrementable<C>::value &&
    !impl::Is_flag_handler<C>::value, int> = 0)
{
  return flag(
    [&counter]() { ++counter; },
    move(keys), move(info));
}

С Concepts этих корявеньких enable_if бы не было, да и прочие SFINAE-обороты можно было бы привести к менее костыльному виду. Но Concepts всё никак не принимают в стандарт…

Теперь займёмся value.
Запись прочитанного значения в заданную переменную могла бы иметь примерно такой вид:

/// Construct a value option, which sets a variable.
template <class T> inline
auto value(T &var,
  Possible_keys keys, Option_info info = {})
{
  return value<T>(/* что-то */);
}

Но данная сигнатура недостаточно хорошо «отличима» от сигнатуры базовой версии функции value… Я вижу три варианта решения проблемы: а) заставить пользователя указывать тип считываемого значения явно и проверять приводимость к T; б) ввести специальную функцию var, порождающую объект-обёртку переменной; в) проверять «читабельность» значений T из потока ввода (написать SFINAE-детектор аналогичный Is_incrementable и воспользоваться enable_if).

Вариант (б) менее интуитивен и вообще не очень мне нравится. Вариант (в) технически менее изящен, но более удобен для пользователя — не надо указывать тип явно.

Наконец, можно просто дать особые имена базовым функциям flag, value и seq, удалив их из набора перегруженных «удобных» функций прямого использования. Именно так я и поступлю. Теперь базовые версии flag, value и seq носят имена flag_parser, value_parser и seq_parser.

/// Construct a value option, which sets a variable.
template <class T> inline
auto value(T &var,
  Possible_keys keys, Option_info info = {})
{
  using std::move;
  return value_parser<T>(
    [&var](T val) { var = std::move(val); },
    move(keys), move(info));
}

В принципе, сейчас уже можно написать простенькие тесты на введённые выше «удобные» функции. Тесты добавлены в namespace test заголовочного файла conar.hpp. Тесты возвращают 0 в случае успеха. Объём кода тихонечко перевалил за 300 строчек. Интересно, в 1000 строк полная версия влезет?

Код данного варианта целиком.

Продолжение следует.

Conar 2: классы за борт!

Начало

Вторая «серия» планировалась через два дня после первой. Получилось — через две недели. Лень-матушка вперёд нас родилась…

Синтаксис вызова парсера

Предложенный ранее синтаксис для Parser несколько избыточен по части скобок :)

Новый синтаксис:

auto parser = parse(опция_1, опция_2, ...);
auto unparsed = parser(argc, argv);
cout << parser.help(...) << endl;

С помощью шаблона с переменным числом параметров данный синтаксис легко добавить к тому, что уже есть:

namespace impl
{
  /// A stub for parse with more parameters.
  inline void parse(Parser&) {}

  /// Add all options to the parser in one recursive call.
  template <class Opt1, class... Other> inline
  void parse(Parser &parser, Opt1 &&option_1,
               Other&&... other_options)
  {
    parser(forward<Opt1>(option_1));
    parse(parser, forward<Other>(other_options)...);
  }
}

/// Make a parser with all options in one call.
template <class... Options>
Parser parse(Options&&... options)
{
  Parser parser;
  impl::parse(parser, forward<Options>(options)...);
  return parser;
}

Представление опций

Объединение общего описания possible_keys и info (фактически, это DTO) с типозависимым поведением (handler) не есть хорошо. Можно было бы сделать из Option чисто абстрактный класс («интерфейс»), наследники которого определяли бы вызов обработчика (handler) и, вероятно, распознавание текста (собственно параметров) — пара виртуальных функций.

Но зачем парсеру знать эти подробности? Фактически, с точки зрения парсера всё поведение «опции» сконцентрировано в одном действии — распознавании текста. Какие там в процессе значения получаются, и как они затем обрабатываются, парсеру всё равно. Поэтому соблазнительно определить это одним замыканием (функциональным объектом), который «скармливается» парсеру. Надо только придумать интерфейс вызова…

Представим, что парсер распознал ключ. То, что после ключа может быть параметром (параметрами) соответствующей ключу опции. Как их передать и как понять, что было успешно принято (распознано)?

Вариант ключа 1, ключ t, time

-t5, --time=5 — только одно значение может быть параметром — то, что идёт сразу за ключом или после знака =. Это часть («хвост») аргумента командной строки. Все прочие аргументы к делу не относятся.

Вариант ключа 2, ключ times

--times 10 start 20 finish — произвольное число параметров — аргументы командной строки за аргументом, содержащим ключ, и до конца или следующего аргумента, содержащего ключ.

Вариант ключа 1 можно рассматривать как частный случай варианта ключа 2. Для разбора в какой-то форме можно передавать массив строк. А возвращать, например, количество успешно распознанных строк. Но как сообщать другие ошибки: неверный формат, недостаточное количество параметров? В конце концов, этот вопрос можно отдать на откуп обработчику, а не решать его на уровне парсера.

Итого, получаем STL-подобный интерфейс:

template <class FwdIt>
FwdIt option_parse(FwdIt from, FwdIt to);
// iterator_traits<FwdIt>::value_type = string

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

template <class FlagHandler>
using Is_flag_handler = std::is_convertible<
	FlagHandler, std::function<void()>>;

template <class ValueHandler, class T>
using Is_value_handler_for = std::is_convertible<
	ValueHandler, std::function<void(T)>>;

template <class SeqHandler, class T>
using Is_seq_handler_for = std::is_convertible<
	SeqHandler, std::function<void(T*, T*)>>;

Код данного варианта целиком.

Продолжение следует.

Conar: минипарсер параметров командной строки

Как известно, задача распознавания параметров командной строки давно и неоднократно решена. Примеры (список далеко не полон): Boost.Program_options (навороченная, и, увы, требует сборки), TCLAP, ezOptionParser, AnyOption, The Lean Mean C++ Option Parser. Обзора я делать не буду, напишу лишь, что ознакомление с данными библиотеками не отбило у меня желание сделать свою :)

Я хочу библиотеку: header-only (вообще полностью определённую в одном заголовочном файле), C++ (поддержка STL-контейнеров, анонимных функций), никакого (L)GPL (Boost-лицензия лучшая же), использование только Стандартной библиотеки C++ (пусть с элементами ещё не принятого C++17), действительно простая схема использования, не требующая писать каскады if-else или switch-case и явно использовать механизмы type-erasure (void*, any и т.п.). Производительность же не играет особого значения. Особая универсальность также мне не нужна.

Такая библиотека может быть достаточно маленькой для ad hoc программирования (без проектирования). Однако это не самое простое упражнение в программировании. Попробую описать её разработку (начата на момент написания этих строк) «в ходе процесса» в нескольких постах.

Итак, с чего начать? Начнём с названия :) У меня это будет conar.hpp («console arguments»).

#ifndef CONAR_HPP_INCLUDED_N98K2U
#define CONAR_HPP_INCLUDED_N98K2U

namespace conar
{
  // ...
}

#endif//CONAR_HPP_INCLUDED_N98K2U

Далее весь код размещается внутри пространства имён conar. Необходимые #include подразумеваются и в тексте не упоминаются.

Ключ — имя опции (параметра командной строки). Опции может соответствовать несколько ключей. Если ключ состоит из одной буквы, то предполагается, что перед ним ставится один дефис («минус»). Если ключ состоит из нескольких букв (и, возможно, цифр), то перед ним ставится два дефиса (предполагаемое автоматическое дополнение пользовательских ключей). Если хочется иной формулировки, например, на дробь / как принято в Windows, то достаточно будет явно указать этот знак. Предполагается, что ключи чувствительны к регистру (в Windows принято иначе, да…). При поиске соответствия будем пытаться подобрать наиболее длинное возможное совпадение. Навскидку наивный алгоритм даёт в худшем случае время разбора O(N L log K + S), где N — количество параметров, L — длина наиболее длинного ключа, K — общее количество ключей, S — суммарное количество символов во всех параметрах.

Опция вида -abc интерпретируется как последовательность трёх опций -a -b -c, если не заданы явно ключи -abc или -ab. В последнем случае возможна попытка прочитать это как -ab c, успешность которой зависит от того, принимает ли -ab строку или символ.

Итак, базовый класс Option для различных классов опций. Нужно ли здесь вообще наследование с виртуальными функциями? Не уверен, посмотрим.

  /// Basic description of a command line option.
  struct Option
  {
    using Possible_keys = std::vector<std::string>;
    using Info = std::string;

    /// Keys corresponding to this option.
    Possible_keys possible_keys;
    /// Information about this option (for help).
    Info info;

    virtual ~Option() {}
    // This class may be extended later.
  };

Классы опций. Наследники класса Option. Объекты этих классов хранят обработчики (handler) распознанных параметров.

Флаг — опция без параметров, соответственно, обработчик имеет сигнатуру void().

  struct Flag_option: Option
  {
    using Handler = std::function<void()>;
    Handler handler;
  };

Значение — опция с одним параметром заданного типа T. Посему это шаблон. Обработчик имеет сигнатуру void(T) и будет вызываться для каждого удачно распознанного ключа с параметром.

Пример (-t, --time, T = int)

-t1 --time=2 -t 3 6 7 --time 4 8 9 даст четыре вызова обработчика с параметрами 1, 2, 3 и 4.

  template <class T>
  struct Value_option: Option
  {
    using Handler = std::function<void(T)>;
    Handler handler;
  };

Последовательность — опция, предполагающая передачу последовательности значений заданного типа (T) после ключа. Обработчик имеет сигнатуру void(T*, T*) и принимает диапазон массива с очередной успешно считанной последовательностью значений (их может быть несколько — для каждого упоминания ключа).

Пример (-i, --input, T = string)

-i "a b c" d e --input "next time" do this даст два вызова с массивами { «a b c», «d», «e» } и { «next time», «do», «this» }.

  template <class T>
  struct Seq_option: Option
  {
    using Handler = std::function<void(T*, T*)>;
    Handler handler;
  };

Парсер. Главный компонент библиотеки. Опции будем регистрировать, передавая объекты классов-наследников Option с помощью оператора (), который возвращает ссылку на объект парсера. Параметры функции main для распознавания (после регистрации всех опций) также передадим оператором (). Т.е. предполагается использование вроде

Parser{}(опция 1)(опция 2)(опция 3)(argc, argv);

результат вызова — список (вектор) нераспознанных параметров (в текстовой форме «как есть»).

На практике, однако, может быть удобнее всё же определить переменную типа Parser. Ну хотя бы чтобы можно было извлечь автоматически созданное описание зарегистрированных опций для хелпа (функция help).

Итак, заготовка Parser.

  class Parser
  {
  public:
    /// Construct a help message part that describes all the options known to the parser.
    std::string help(int key_column_width = 20, int line_width = 80, const char *line_sep = "\n") const
    {
      std::string result;
      // TODO
      return result;
    }

    /// Add an option description. Use functions flag and value for this.
    template <class Opt>
    Parser& operator()(Opt option)
    {
      static_assert(std::is_base_of<Option, Opt>::value);
      // TODO
      return *this;
    }

    /// A list of unparsed parameters.
    using Unparsed_parameters = std::vector<std::string>;

    /// Finally parse the command-line parameters given by an iterator range (of strings).
    template <class InIt>
    Unparsed_parameters operator()(InIt from, InIt to)
    {
      static_assert(std::is_convertible<
        typename std::iterator_traits<InIt>::iterator_category,
        std::input_iterator_tag>::value);

      Unparsed_parameters unparsed;
      // TODO
      return unparsed;
    }

    /// Parse arguments as they are passed to main, argv[0] is ignored.
    Unparsed_parameters operator()(int argc, char *argv[])
    {
      return (*this)(argv + 1, argv + argc);
    }
  };

Вот так, раз-два и готов файлик в сотню строк. Которые, впрочем, пока абсолютно бесполезны…

Продолжение следует.

Perfect Hashing of Very Short Strings

This post is a (bit modified) translation of my older post in Russian.

Let a small set of very short strings (1—4 bytes here) is given and we want to construct a dictionary with strings from this set being used as keys. A simple solution is to use a universal hash table with a generic hash function (usually the one provided by the library implementing the hash table, e.g. C++ Standard library provides some std::hash implementation for strings) such as Murmur or FNV hashes.

However such a solution is a heavyweight one in some cases, for example when keys are known in advance and are short enough. This is the case when a generic array may handle the job. For this to be true we have to find a hash function that suffers no collisions for inputs from the set of our keys, so called perfect hash function.

Another feature I want is high hash computation speed, so I am not going to use complex and costly hash functions. For example Pearson hashing is too complex for me (plus I am considering CPUs capable of fast integer hardware multiplication). Finally, I am not going to use division or remainder operations. Instead I will use an array having size equal to some power of 2 (I am OK with some cells left unused).

For strings no longer than four bytes I can use 32-bit words as keys, «NUL» character is not used in texts so one-character strings have only the least significant byte being non-zero and the other three bytes being zero, two-character strings have the least significant half non-zero and the other half zero and so on. The function casting strings to integers that way may be written in C++ as follows.

inline uint32_t to_number(const std::string &word)
{
  register uint32_t result = 0;
  switch (word.size())
  {
  case 4: result  = (uint32_t)word[3] << 24;
  case 3: result |= (uint32_t)word[2] << 16;
  case 2: result |= (uint32_t)word[1] << 8;
  case 1: result |= word[0];
  default: return result;
  }
}

The hash function I am going to construct belongs to the family defined by the following template (one has to find N and b for the given set of keys).

template <uint32_t N, unsigned b>
uint32_t ssphash(uint32_t word)
{
  return (word * N) >> b;
}

Of course, there is no guarantee that for the given set of keys this family of functions contains a perfect hash function. But due to its simplicity and small combinatorial size of the problem (for modern computers) we can try to brute-force N and b (the software was written for MSVC and uses _alloca from malloc.h and intrinsic __lzcnt from intrin.h, some CPUs do not support the latter). The size of the array (our hash table) is taken as the smallest power of 2 not less than quantity of keys.

For examples for the following set of keys (operator and punctuation lexemes of C++)

+ - ! ~ # % ^ & * ( ) / // /* */ [ ] { } | ? : ; , . && || ++ -- < > " ' <= >= = == -> .* ->* << >>

I have got N == 242653, b == 17.

Совершенное хэширование сверхкоротких строк

Пусть заранее задан небольшой набор сверхкоротких строк и надо сделать словарь, ключами которого могут быть эти строки. Обычным решением для произвольных строк является использование универсальной хэш-таблицы с достаточно универсальной хэш-функцией (например, Murmur или FNV) из той или иной библиотеки (например, std::unordered_map).

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

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

Сверхкороткие строки можно хранить в одном машинном слове. Четыре байта — 32-битное целое. Пусть, при этом, строки единичной длины соответствуют ненулевому младшему байту (три остальных — нули), строки длины два — двум младшим ненулевым байтам (два остальных — нули) и так далее. Функция приведения строки к числу такого вида может быть записана следующим образом:

inline uint32_t to_number(const std::string &word)
{
  register uint32_t result = 0;
  switch (word.size())
  {
  case 4: result  = (uint32_t)word[3] << 24;
  case 3: result |= (uint32_t)word[2] << 16;
  case 2: result |= (uint32_t)word[1] << 8;
  case 1: result |= word[0];
  default: return result;
  }
}

Хэш будем искать вида

template <uint32_t N, unsigned b>
uint32_t ssphash(uint32_t word)
{
  return (word * N) >> b;
}

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

Данная программа позволяет ввести набор строк и перебором ищет подходящие N и b. Размер хэш-таблицы выбирается как степень двойки не меньшая числа строк-ключей. Например, для лексем (операторы и пунктуация) C++

+ - ! ~ # % ^ & * ( ) / // /* */ [ ] { } | ? : ; , . && || ++ -- < > " ' <= >= = == -> .* ->* << >>

получены значения N == 242653, b == 17.

Поиск дублирующихся файлов

На днях мной была написана простенькая консольная утилита fdf (сборка под Windows x86-64, для запуска требуется Microsoft Visual C++ 2013 runtime).

Цели разработки

  • Получить минималистичную утилиту для поиска файлов-дубликатов или уникальных файлов в заданных директориях;
  • потренироваться в решении подобных задач;
  • опробовать SHA3 (Keccak).

Цель получить код, отвечающий каким-то специальным критериям (краткость, дидактическая ценность, высокая эффективность), не ставилась. Тем не менее, предполагается, что он может служить вспомогательным примером при изучении, например, многопоточного программирования на C++: вспомогательные компоненты LockedQueue, LockedLog и ThreadGroup вынесены в отдельные заголовочные файлы и являются довольно примитивными.

Исходники выложены на bitbucket. Для самостоятельной сборки требуется скачать референсную реализацию Keccak и (удобно при использовании Visual C++) распаковать её в папку проекта, так, чтобы папка KeccakReferenceAndOptimized была рядом с файлами исходного кода. За подключение нужных .c файлов отвечает файл FileHasher.cpp, связь кода fdf с Keccak обеспечивается файлом FileHasher.hpp. Оказалось, что использовать референсную оптимизированную (жаль только, что SIMD под Windows/x64 не используется) реализацию весьма просто, спасибо авторам!

Параметры командной строки

  • /? ? -help —help выводит краткую справку;
  • -tN задаёт количество рабочих потоков (всего параллельных потоков будет N+1), по умолчанию выбирается N = max(1, количество логических ядер / 2);
  • -u меняет поведение программы на противоположное: вместо дубликатов будут перечислены найденные уникальные (в заданной области поиска) файлы;
  • -size включает вывод размеров файлов (один размер на группу дубликатов);
  • -loN включает фильтр по размеру файла: рассматриваются только файлы размера не менее N мегабайт, при этом если N=0, fdf будет игнорировать пустые файлы;
  • -timing включает вывод в конце затраченного времени (в секундах);
  • другие параметры расцениваются как указания мест поиска файлов (пути директорий), они формируют общую область поиска (объединение), если ни один путь не указан, то поиск производится в текущей директории.

Результаты работы

  • в stderr: сообщения об ошибках (специально не форматируются, поэтому могут иметь заковыристый вид с лишними словами);
  • в stdout: результат работы, который оформляется как последовательность строк, завершающихся переводом строки, содержащих или полные пути найденных файлов или размеры в байтах или (последняя строчка при наличии параметра -timing) затраченное время; группы дубликатов отделяются друг от друга пустой строкой.

Принцип работы

Для обхода директорий используется библиотека boost::filesystem. Процесс работы разбит на три стадии:

  1. составление первичного списка файлов;
  2. объединение результатов первой стадии;
  3. проверка на дубликаты побайтовым сравнением найденных кандидатов в дубликаты.

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

На первой стадии основной поток раздаёт пути файлов, выполняя обход переданных директорий поиском в ширину (это приводит к большему расходу памяти, чем традиционный обход поиском в глубину, но позволяет паралелльно нагрузить произвольное число носителей данных), в то время как рабочие потоки вычисляют хэши файлов (целиком для файлов меньше 16 Мб и для выборки в 16 Мб для остальных, размер в 16 Мб взят «с потолка»), и в конце сортируют свои наборы файлов (лексикографически: размер, хэш, имя).

На второй стадии основной поток выполняет восходящее слияние результатов работы рабочих потоков.

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

Замечание. Вместо трёх стадий и формирования отсортированного списка файлов можно было использовать какую-либо параллельную реализацию хэш-таблицы (аналог std::unordered_multiset). Впрочем, в моей практике с использованием HDD именно первая стадия занимает этак 98% времени работы, поэтому сложно надеяться на заметное ускорение при работе на HDD.

Xprer

Недавно возникла забавная задачка. Предположим, некий софт накапливает данные в файле. Иногда происходят сбои, и данные начинают записываться повторно в конец файла так, что результирующую структуру файла можно представить в виде трёх участков alpha alpha beta, где alpha — дублирующаяся последовательность байт (префикс). Корректный файл выглядит как alpha beta. Итак, задача: отбросить максимальный дублирующийся префикс в заданном файле за приемлемое время (файл может быть размером в десяток гигабайт).

Для решения данной задачи я написал небольшую консольную утилиту xprer «maXimal PREfix Reduction» (сборка под Windows x86-64, Microsoft Visual C++ 2013 runtime), принимающую один или два параметра командной строки: имя исходного файла и необязательное имя результирующего файла. Если имя результирующего файла не задано, то результат записывается в файл xprer.out.имя исходного файла.

Реализация утилиты использует стандартную библиотеку C++. Исходный код доступен здесь. Для поиска совпадения префикса используется подход, аналогичный алгоритму поиска подстроки Рабина-Карпа. Используется кольцевой хэш на основе суммы и суммы сумм (похож на Adler32, но имеет длину 64 бита и вычисляется по модулю 232).

Поиск совпадения начинается со сравнения половин файла (случай alpha alpha приводится к alpha). Далее префикс уменьшается на один байт до тех пор, пока не будет найдено совпадение, либо не будет достигнуто начало файла. Для получения хорошего быстродействия понадобилось выполнять буферизацию вручную (при чтении назад стандартная буферизация только мешает, для решения этой задачи написан класс StreamBackBuffer). Дальнейшая оптимизация возможна при переходе на отображаемые в память файлы и использовании предварительного поиска коротких совпадений, но мне это уже не понадобилось.