2 марта 2013 в 13:34

Автоматическая генерация типизированных структур данных для Си из песочницы

Если Вы программируете на Си и Вам не хватает типизированных контейнеров, которые есть в языках высокого уровня, добро пожаловать под кат:

Всем привет!

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

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

Существующие библиотеки контейнеров для Си, например из состава GLib, оперируют единственным типом — нетипизированными указателями gpointer, поскольку «честное» решение этой задачи на Си возможно только с привлечением препроцессора и будет представлять собой жуткую мешанину из макросов, трудную в понимании и отладке, что продемонстрировано существующими подобными проектами. То есть, ничего подобного по стройности и удобству контейнеров STL для Си++ и коллекций Явы и Шарпа штатными средствами Си построить не получится.

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

Генератор кода написан на Руби. Подготавливаемая пользователем спецификация структур данных представляет собой Руби-скрипт. Результатом работы генератора является исходный код на Си, оформленный в виде модуля (файл заголовка и файл реализации). Файл заголовка включается в пользовательский код, использующий эти структуры; файл реализации компилируется и связывается с остальными модулями, составляющими программу.

На момент написания статьи поддерживаются следующие структуры данных:

  • Вектор Vector (Си++/Ява аналоги: std::vector и java.util.ArrayList).
  • Односвязный список List (ближайшие Си++/Ява аналоги представляют собой двухсвязные списки: std::list и java.util.LinkedList).
  • Набор на основе хешей HashSet (Си++/Ява аналоги: std::unordered_set и java.util.HashSet).
  • Отображение на основе хешей HashMap (Си++/Ява аналоги: std::unordered_map и java.util.HashMap).


Для каждой специализации контейнера создается свой независимый исходный код; собственно, это именно то, что делает Си++ «за сценой» при генерации специализаций своих шаблонных типов (например, для
std::list и std::list генерируются два независимых набора машинного кода).

Генерируемые структуры могут оперировать как типами, передаваемыми по значению, так и ссылочными типами. Для последних может быть задействовано контролируемое пользователем управление памятью, например, с совмещением имен и счетчиком ссылок, copy-on-write и т.д. Обеспечивается множество операций, ожидаемых от подобных структур данных - вставка, удаление, поиск, перебор элементов и т.д.

В качестве примера приведу простой пример работы с AutoC для создания и применения структуры данных, соответствующей типу std::unordered_set для Си++.

Полный текст входного задания для генерации структуры данных типа набор (set), оперирующего целыми числами:
require "autoc" CodeBuilder::CModule.generate!("containers") do |m| m << DataStructBuilder::HashSet.new("IntSet", {:type=>"int"}) end


Вырезка из интерфейсной части модуля для IntSet:
...
typedef struct IntSet IntSet;
struct IntSet {...}
...
void IntSetCtor(IntSet*);
void IntSetDtor(IntSet*);
void IntSetPut(IntSet*, int);
...


Полный текст тестового примера для IntSet:
#include <stdio.h>

#include "containers_auto.h"

int main(int argc, char** argv) {
	IntSet set;
	IntSetCtor(&set);
	IntSetPut(&set, 0);
	IntSetPut(&set, 1);
	IntSetPut(&set, 0);
	printf("size(set)=%d\n", IntSetSize(&set));
	printf("contains(1)==%d\n", IntSetContains(&set, 1));
	IntSetDtor(&set);
	return 0;
}


Работа над пакетом еще не завершена; основные пробелы находятся, как водится, в части документации (краткое описание генерируемых API в наличии). Тем не менее, содержательная часть уже довольно стабильна, функциональна и готова к использованию.
Более полное представление о возможностях и способах применения можно получить из тестового примера, входящего в состав пакета.

P.S.
Идеи и конструктивная критика приветствуются.
@fougas
карма
3,0
рейтинг 0,0
Самое читаемое Разработка

Комментарии (35)

  • +2
    А есть ли что -нибудь типа Meta C языка, где расширены возможности для метапрограммирования, но на выходе обычный си? Вообще интересно увидеть обзор подобных проектов
    • +1
      Навскидку, cos.sourceforge.net, ooc-lang.org, ooc-coding.sourceforge.net.
      Также есть целая книга по ООП для Си.
      • 0
        Судя по вступлению, вещь невероятно полезная, спасибо!
    • +1
      Си-подобная Vala и питонообразный Genie (они родственники). Интересное направление…
      • +1
        Тогда уж сюда можно написать целую кучу языков с реализациями, транслирующими в Си :)
    • 0
      есть, но закрытый

      www.maier-komor.de/metac/

      Я в свое время намучился с openC++ и понял, что ООП для метапрограммирования слабо подходит.
      Вообще была идея 10 лет назад (и даже почти стартовал проект) — сделлать метазамыкание для С.
      Т.е. фактически препроцессор (метаобъектный компилятор), который может менять или дополнять синтаксис на лету, а поскольку сам препроцессор предполагалось сделать на подмножестве языка С — то он мог менять и свой синтаксис.
      Идея была хороша тем, что ядро получалось общее для любых языков, включая естественный, т.к. для прототипа предполагался Earley parser — с его возможностью разбора неоднозначных грамматик.

      Потенциально, при небольшой удаче, да высокой скорости обработки — такая штука могла бы убить существующее вавилонское столпотворение языков, особенно учитывая, что даже сегодня С остается lingua franca в программировании.
      Ну и минималистичность базового языка здесь дает огромный плюс в гибкости.

      До сих пор жалею, что не прошло, очень полезная штука была бы.
      • 0
        Сейчас в подобной роли есть haXe — только на практике он юзабелен в основном при компиляции в ActionScript…
        • 0
          Насколько я понял из доки, у haXe нет возможности модифицировать свой синтаксис на лету.
          Т.е. это просто code transformation из одного языка в другие.
          С этой точки зрения даже старый добрый ADF+SDF гибче был бы, если бы не вымер.
          Хотя HaXe конечно практичнее выглядит.

          Меня больше интересовало что-то близкое к openC++ (тоже правда мертвому), но для С.

          А структурки с типизацией генерировать — это и без таких средств не проблема. Подключаем m4 в качестве пре(пре)процессора и вперед. Или даже перл.
          Главное — чем проще синтаксис, тем лучше.
          • 0
            Очень расплывчатая на самом деле задача. Если понимать возможность модифицировать свой синтаксис на лету как возможность итеративно заглядывать в AST, модифицировать парсер, модифицировать кодогенератор и продолжать далее, то:

            (a) на практике это толком никому не нужно,
            (b) если и нужно — то *гораздо* проще оформить свои изменения в четко выделенном плагине к компилятору, а все эти итеративные изыскания выделить в систему сборки (а ля makefiles)

            Если все то же самое, но без изменения парсера — то по сути любой язык, в котором есть какие-то code blocks и closures можно считать языком метапрограммирования, в котором на пустом месте можно сделать любые управляющие структуры — хоть if-then, хоть exceptions, хоть guarded commands, хоть что. Чемпионом на этом поле лет 10 назад был Perl, сейчас вроде как все активно любят Scala или в крайнем случае Ruby (хотя там парсер куда более примитивный, чем в Scala).

            Если рассматривать с точки зрения правильного lingua franca — то, боюсь, путь code transformation а ля haXe (или тот же pyrb) — единственно практически разумный. Говорить о том, что «каждый пишет на своем языке, а потом все это работает вместе» — можно, но на практике нужно не это. Нужно, чтобы не машины понимали друг друга (с этим, внезапно, фактически-то проблем и нет уже лет 30 как), а чтобы люди понимали — а эта проблема — она не в средствах, а в головах.

            У haXe, надо отметить, тоже проблем практических мильён. Основная — в stdlibs, которые очень так себе map'ятся в многообразие стандартных структур и библиотек во всех поддерживаемых таргетах.
            • 0
              Groovy тоже вполне себе подходит, хотя он где-то на уровне Ruby по поддержке метапрограммирования.
            • 0
              Очень расплывчатая на самом деле задача.


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

              Например одним из требований был уход от графической репрезентации UML диаграмм в сторону принципиально другого процесса разработки и проектирования.
              Т.е. вначале должен строиться язык предметной области, фактически DSL, но не в том, урезанном виде, как то сегодня понимается.
              И только потом проблема должна была быть описана в рамках этого конкретного DSL и эффективно оттранслирована в исполняемый код.

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

              Там много было, амбициозная штука была.

              В качестве примера приведу одно предложение по финальному тесту.

              #include "NLP2SQL.h"
              #include "Война и Мир"
              


              В результате должен был быть проанализирован текст на естественном языке, существительные выделены как сущности, глаголы как отношения, прилагательные как атрибуты-модификаторы и в случае нахождения противоречий или неопределенностей — печать их списка.
              А в случае ненахождения таковых — печать SQL схемы.
              :-)

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

              Опять таки, описание задачи в виде DSL позволяло довести безбажность вплоть до формальной верификации на самом раннем уровне. А наличие транслятора из DSL в реальный язык программирования сохраняло безбажность далее на всех этапах.
              В теории конечно, но выглядело на тот момент крайне заманчиво.

              (a) на практике это толком никому не нужно,


              Ну, нам в тех проектах это было точно нужно.
              Тем более, что тогда С++ с его темплейтами (крайне убогими по сравнению с этой техникой) продвигался в том числе и как средство создания DSL.
              А темплейтов нам точно было недостаточно, особенно учитывая их возможности верификации.

              (b) если и нужно — то *гораздо* проще оформить свои изменения в четко выделенном плагине к компилятору, а все эти итеративные изыскания выделить в систему сборки (а ля makefiles)

              Не, это проще, но для одного проекта.
              Когда проекты идут потоком — это придется делать каждый раз для каждого нового DSL.
              А программист, который владеет препроцессором и который может написать плагин — стоят разных денег.
              :-)

              Если все то же самое, но без изменения парсера — то по сути любой язык, в котором есть какие-то code blocks и closures можно считать языком метапрограммирования, в котором на пустом месте можно сделать любые управляющие структуры — хоть if-then, хоть exceptions, хоть guarded commands, хоть что. Чемпионом на этом поле лет 10 назад был Perl, сейчас вроде как все активно любят Scala или в крайнем случае Ruby (хотя там парсер куда более примитивный, чем в Scala).


              Да, разумеется.
              Но нас интересовала возможность универсального решения, не зависящего от языка (хотя основная ниша планировалась на С).
              Ядро — средство работы с AST, универсальное.
              Подставив в ядро начальную грамматику Perl — мы дальше пишем все на Perl (дав, в середине кода #include «java» — перейдя на другой язык).
              Опять же, на тот момент для нас была критична производительность, что опять приводило к С, даже не к С++ — если кто помнит, у ранних компиляторов С++ была например веселая привычка прятать скрытый try/catch в конструктор, что несколько тормозило результирующую программу — аж в 40 раз бывало.
              Версию правда сказать не могу, но не позже g++ 3.х
              Но было.

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

              Если рассматривать с точки зрения правильного lingua franca — то, боюсь, путь code transformation а ля haXe (или тот же pyrb) — единственно практически разумный.


              Хз, когда-то ADF+SDF считался единственно разумным, с его помощью COBOL на С++ массово переводили.
              Сейчас многое не имеет смысла просто потому, что критерии поменялись, стоимость проекта уже не так критична, зато более критична документация, поддержка. Стабильность уже не так играет — код, который живет 10 лет без переделок никому не нужен.
              Фактически тот, что придумает робота-программиста убъет индустрию.
              Ну если индустрия не убьет его самого.
              :-)

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

              Говорить о том, что «каждый пишет на своем языке, а потом все это работает вместе» — можно, но на практике нужно не это.


              При наличии частичной верифицируемости и зафиксированных интерфейсов — почему нет?
              Они ведь все равно пишут каждый по своему, бангалорец или пекинец.
              И ревью кода не так уж и сильно ведь помогает, а времени кушает. Ценного между прочим времени.

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

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

              Внезапно, большинство современных технологий — UI-driven.
              Языковой интерфейс может понять и человек и робот, и робот может передать информацию другому роботу по цепочке, складывая из мелких строительных блоков более крупные конструкции.
              На конце UI всегда стоит человек. И, следовательно, для создания более крупных вещей он всегда там будет стоять, тормозя всю систему и внося ошибки.

              В web 1.0 контент выделялся роботом без проблем.
              А сейчас — пишут интеллектуальные программки, которые по лейауту определяют баннеры, рекламные блоки и вырезают их.

              Не то чтобы я агитировал за web 1.0…
              :-)

              У haXe, надо отметить, тоже проблем практических мильён. Основная — в stdlibs, которые очень так себе map'ятся в многообразие стандартных структур и библиотек во всех поддерживаемых таргетах.


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

              Ну и опять-же, дать возможность программисту создавать свой язык под задачу с такой же легкостью, с какой он создает bash-скрипт — имхо многого бы стоило.
              Правда что бы получилось в результате и насколько бы это было практично — никто не знает, т.к. начальное R&D было свернуто, даже до пилота не дошло.
              MetaC который появился позже чем-то похож на этот проект, только у него ядро заточено под С, а не универсальное.
              Это все-таки больше препроцессор, судя по той документации.
              Но даже для MetaC я вижу применение сегодня, не массовое конечно, но есть.
  • 0
    Попыток использовать ASN.1 не было?
    • 0
      Не было. AutoC выделился из другого проекта, в котором активно используется автоматическая генерация; его код писался, скажем так, стихийно, без какой-либо формализации.
  • 0
    > нетривиальная программа с большой долей вероятности предполагает работу с нетривиальными структурами данных
    Нетривиальная программа предполагает разработку нетривиальных функций, а структурами можно и простым обойтись.
  • 0
    Симпатичный синтаксис получается :)
    Но я думаю вам надо бы поглубже взяться за это. Кроме структур данных есть еще и управляющие конструкции, системы типов. Тут уже язык свой получается. Сейчас таких много, которые в С транслируются, или в какой то другой язык (для некоторых даже высокоабстрактный Haskell является backend'ом).
    • +1
      Не думаю, что мир ждет не дождется 100501 языка программирования, полного по Тьюрингу :)
      Скорее, требуется аккуратная реализация функциональности, которой трудно или вообще невозможно достичь с использованием штатных средств Си.
      • 0
        Я с вами полностью согласен…
        Но, немного пофантазировав, можно быть на 100% уверенным, что еще не один несуществующий сегодня язык прорвется когда-то в мейнстрим.
  • 0
    Чем препроцессор не устроил?
    • +1
      В данном случае, например, нужно генерировать разный код для целых и структур (вторые логичнее передавать по указателю). Препроцессор тут не поможет. Впрочем, и идея библиотеки на Ruby для решения этой задачи мне кажется весьма странной. По мне, так проекты типа OOC тут более уместны.
      • 0
        Поможет.
        • 0
          Покажите пример кода, который при помощи препроцессора определяет, чем является аргумент макроса — числом или структурой.
          • 0
            Этого не делается даже в STL, потому что не задача это библиотеки, выбирать между vector и vector<int*>. Легко можно сделать код вида

            #define NAME IntSet
            #define TYPE int
            #define POD_TYPE 1
            #define REFERENCE_COUNTING 0
            #include set_template.h

            Недостаток тут — типичный для препроцессора недостаток в виде отсутствия рекурсии, но я не думаю, что в ruby-решении шаблонизатор лучше, чем cpp.
            • 0
              Недостаток макро-подхода — сложность отладки. Это верно даже для более мощного М4 — достаточно вспомнить приснопамятные Auto{conf,make}, что уж там говорить про унылый препроцессор Си и его «тесную» интеграцию с собственно компилятором.
              Кроме того, подобные решения плохо масштабируются — очень скоро настает момент, когда сложность макро-кода начинает препятствовать добавлению новой функциональности.
  • +4
    Было бы логично генератор написать на си, это позволило бы таскать его вместе с проектами написаными на си и поддерживать теми же програмистами.
    • 0
      Да ещё потом переписать генератор с использованием самого себя.
  • –1
    Эти же поделки из stl-я практически невозможно использовать. Особенно list (если учесть хотя бы, что size() занимает O(N), а удалить элемент из списка так просто не выйдет без знания начала списка). Зачем для использования этого убожества что-то еще лепить, когда можно написать что-то свое с нормальными интерфейсом и предсказуемым временем работы.
    • 0
      По стандарту size() должен работать за O(1). Проблема в реализации GNU libstdc++. Баг там висит давно, но его не исправляют под предлогом, что это нарушит бинарную совместимость.
    • 0
      А зачем вам list.size() вообще? Или ::iterator вам не по зубам?
  • –1
    В С++ уже есть односвязный список. Называется std::forward_list.
    • 0
      С чего минусы? В статье:
      Односвязный список List (ближайшие Си++/Ява аналоги представляют собой двухсвязные списки: std::list и java.util.LinkedList)

      Ближайший аналог в C++11 это не std::list, а именно std::forward_list.
      • 0
        Да, именно это я и хотел сказать. Спасибо!
  • –1
    И в чем нетривиальность вашего метода, кроме того, что видимо вы делаете на руби то, что делает компилятор с темплейтом на си++??? Похоже на удаление зуба через… ну вы знаете.

    Вот к примеру решен ли баг списка list при добавлении класса, точнее даже не баг, слабое место, но так как до него не каждый дойдет своим умом часто порождает ошибки.

    #include <list>
    #include
    using namespace std;

    class MyClass{
    public:
    MyClass(){
    cout << «constructor\n»;
    }
    ~MyClass(){
    cout << «destructor\n»;
    }
    };

    int main(){
    list <MyClass> mylist;
    mylist.push_back(MyClass());
    cout << "--- after push back ---\n";
    return 0;
    }

    если запустить этот код, получим следующее:

    constructor
    desturctor
    — after push back — desturctor

    Тоесть, код создания объекта вызван 1 раз а удаления 2 раза, если конструктор создавал динамический данные а деструктор удалял, то удалить их второй раз не получится и система выдаст ошибку.

    Обычно тут все матом кроют STL, вроде ее баг, STL мастдай, даешь руби, жабу, шарп и уборщики мусора, но ошибка в описании класса, так как мы не переопределил оператор = лист тупо делает прямую копию и у нас получается 2 экземпляра класса указывающих на одно и тоже.

    Вот вопрос, решает ли ваш скрипт подобные нестыковки и как ???
    • 0
      В вашем примере вызывается конструктор MyClass(), а также, неявно, конструктор копий MyClass(const MyClass &), т.к. при помещении объекта в контейнер создаётся его копия (которая фактически и попадает в контейнер). Нет в C++ такого понятия, как «код создания объекта», есть конструкторы — обычные и копирующие. Переопределять нужно конструктор копий, а не operator=(). И это — не слабое место контейнера std::list или ещё какого-нибудь, а особенность языка, которую описывают в любом нормальном учебнике по C++, и которую должен знать любой плюсовик. И компилятор никак не может знать, что у вас лам лежит по указателю, так что в любом случае забота о динамической памяти, выделенной в конструкторе, лежит на плечах программиста. В языке, дающем возможность работы с указателями, по-другому и быть не может — не вижу в этом проблемы.

      То же касается C: добавляешь структуру в список — будь любезен позаботиться о её корректном копировании. Например, пиши функцию T *clone(const T *prototype) и в ней копируй всю динамическую память, как положено. А дальше есть два варианта:
      1) Самостоятельно вызывать clone() перед добавлением экземпляра структуры в список.
      2) Передавать указатель на clone() в функцию создания списка для того, чтобы функция добавления элемента в список вызывала clone() автоматически.

      Второй вариант (callback-функция) проще и надёжнее. Так или иначе, повторюсь: в C и C++ корректная работа с динамической памятью в классах — забота не контейнеров, а разработчика.
      • 0
        Да вы правы, не равно, а конструктор (ведь знал и почему то одно на другой наложилось, старею =( )
        Но я то в комментарии не о том, я о другом, о том, что стандартные контейнеры ругают обычно из-за вот таких вот непонимании особенностей языка или сути самого контейнера.

        и тут до меня доперло, что речь идет о просто Си а не С++…
        даю себе зарок не комментировать спросони =)
      • 0
        Собственно, в пакете так и делается — пользовательский тип дополняется (опциональными) функциями, выполняющими роль конструктора/конструктора копирования/деструктора. В случае их отсутствия генерируется замещающий код, соответствующий простому типу, передаваемому по значению.

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