кодогенерация как высшая форма сopy/paste
Несколько лет назад в одной беседе о технических горизонтах мой собеседник затронул тему кодогенерации. При этом демонстрировалась книга, привезенная из дальнего зарубежья.
Второе упоминание попалось двумя годами позднее, в уже ставшей классической книге Эрика Реймонда "Дао программирования в Unix".
Оба этих случая осели на задворках сознания, но я продолжал считать что кодогенерация - удел богов, трансцендентные техники просветленных гуру.
вводная
Не поминай гуру всуе. Однажды я оказался в Индии, в одной из крупных софтопроизводящих контор на стажировке. После некоторого периода обучения нас разбросали по существующим проектам. Проект, в который попали двое моих сотоварищей и ваш покорный слуга, находился в состоянии "мы работаем 14 часов в день без выходных, потому что совсем не укладываемся в сроки". Или, говоря более образно — часть филея, что чуть ниже спины, уже ярко вставала на горизонте. И мы пахали. Аминь.
постановка задачи
В один из дней октября к нам приходит техлид. И говорит потрясающую вещь:
— Ребята, у нас через день начинается фаза Unit-тестирования. А мы только сейчас поняли, что у нас нет совсем ничего, кроме кода, совсем-совсем. Потом пауза и жалобно-тоскливый взгляд (см.сцену с котом из "Шрек-2").
— Сделайте как-нибудь и что-нибудь. Нам нужен framework.
Итак — исходные данные. UnitTesting — это процесс запуска функций с параметрами. Самое нудное и трудоемкое — это заполнение параметров. Более 100 разнотипных вложенных структур с десятками разномастных полей. Нам надо автоматизировать процесс заполнения структур, имея текстовые файлы с данными и заголовочные файлы с определениями типов. Язык исходных текстов проекта — С. Операционная система — Solaris.
Местные программисты всегда делали copy/paste. Теперь надо его автоматизировать.
ода copy/paste (лирическое отступление)
Что такое программирование в Индии? Это броуновский процесс безостановочного внесения изменений. Любимый способ их внесения — copy/paste. У тебя проблемы? Сделай copy/paste у себя, у соседки, у коллег из соседнего отдела. Об этом тебе говорят программисты, техлиды и менеджеры.
дизайн
На дизайн ушло 3 (три) часа. Подошли прагматично, нам нужно иметь нечто, что в 80-90% случаев создаст корректный код заполнения типов. Отлично вписались классические методы проектирования Unix way — разбитие функционала на мелкие простые узкоспециализированные утилиты. Метод передачи данных - Unix-pipe, формат — форматированный plain-text.
Stage1 — получает на вход Си-код, вырезает из него все объявления функций, разбирает списки параметров и извлекает типы параметров. Выводит полученные типы, один за другим.
Stage2 — на вход получает список типов. Выполняет разбор всех объявлений из заголовочных файлов с типами. Определяются все типы, имеющие отношение к исходным (как поля структур, enums, unions, либо простые typedef из типа в тип). Выводится описание найденных зависимых типов в упрощенном формате, типа:
struct name_st
<tab>field1_t field1
<tab>field2_un field2
<blank line>
raw field1_t
<blank line>
union field2_un
<tab>UU=1
<tab>BB
Stage3 — получает описания типов и генерирует по ним функции заполнения типов на Си.
Следующее проектное решение - есть библиотека базовых (raw) типов, которые не требуют заполнения. Для них функции уже написаны и подключаются к коду. Данное решение имело одно интересное следствие - пользователь может расширять библиотеку базовых типов любыми своими типами. В raw оказались такие типы как int, short, unsigned int, boolean.
fill_sometype() возвращает указатель на переменную типа sometype, выделенную и инициализированную указанным значением. Значение — строка (массив строк для структуры), задача функции - выделить память, привести строку к нужному типу и инициализировать значением. Интересным следствием введения системы базовых типов оказалось то, что преобразования из строк шли только в них, когда как производные типы просто вызывали соответсвующие функции заполнения.
И финальное решение — венец прагматизма. Нам навязали plain-структуру конфигурационных файлов для структур. То есть независимо от уровня вложенности — все возможные параметры записываются в строчку, никаких перекрестных ссылок. Итого — пользователь сам следит за корректностью индексов передаваемым функциям заполнения. Мы просто ставим их подряд.
Также была сделана обобщенная функция make_table(). Она получала на вход имя конфигурационного файла для структуры, и указатель на функцию заполнения для нее. Формат структуры не имел значение. Дизайн make_table() оказался настолько обобщённым, что она смогла переварить все наши 100 с небольшим структур. Выходным значением служил массив из массивов строк. Каждый массив строк - один набор значений для структуры. Коих может быть много.
Часть из вышеописанного обрела конкретные черты уже по ходу разработки, но базовые принципы были заложены изначально.
И, наконец, выбор инструментов:
- базовая библиотека и make_table() - на Си;
- кодогенерация и разбор текста - awk (nawk).
разработка
Разработка заняла 6 дней. С вечера понедельника до вечера субботы.
Мы узнали массу нового о коде наших коллег, об awk, приняли и отбросили массу тактических решений.
Краткий список граблей, которые были пройдены за неделю:
- выделение памяти на solaris с помощью malloc() давало SIGBUS . memalign() не давал;
- в исходниках наших коллег обнаружилось 3-4 различных стиля написания кода, что изрядно затруднило на начальном этапе разбор заголовочных файлов. Добавление каждого нового файла с типами ломало парсер с регулярными выражениями напрочь;
- было выявлено порядка 40 defines, влияющих на список членов структур;
- были найдены структуры и union's, объявляемые прямо в теле структур без предварительного объявления типа.
В субботу была реализована схема, которая решила проблемы 2 и 3. На массив заголовочных файлов натравливался препроцессор с передачей всех этих чудесных define, c предварительным вырезанием всех директив #include. Результат препроцессинга десяти h-файлов сбрасывался в preproc.h, по которому проходили с утюгом утилитой indent, приводя содержимое к чудесному единообразию и общности стиля.
Stage2 лихо разбирало preproc.h, создавая по ходу массу промежуточных файлов со справочной информацией по коду, например файл описания всех структур, всех enum и всех union.
Кодогенератор (stage3) писался последним, получился некрасивым, во многом дублирующим и совершенно неинтеллектуальным. Короче — именно таким, каким его и хотели видеть.
По ходу разработки выяснилось, что нужен интегратор для полученного набора утилит. Им стал make. Формат Makefile с его целями и зависимостями оказался удивительно удобен для извлечения пользы из различных сочетаний наших утилит, а также для демонстрации нашего прогресса в работе паникующим техлидам.
результат
И был вечер дня шестого, и фреймворк был готов. Мы посмотрели на результат усилий и сказали "это хорошо!" (С) Господь Бог.
Что же в итоге? Венец copy/paste. Масса функций, копирующих друг друга и различающихся лишь незначительно. Но появляющихся быстрее, чем за 2 секунды работы.
Если коротко и предметно:
- make modules - сгенерировать код для всех подмодулей системы;
- echo struct_type|make stage2 - сгенерировать описания структуры и всех типов, относящихся прямо и косвенно к структуре;
- echo struct_type|make stage2|make stage3 - сгенерировать код заполнения для структуры и всех зависимых типов;
- cat proto.h|make stage1 - список всех типов, использованных как параметры функций, объявленных в proto.h.
Пристальный взгляд на творение рук наших выявил одну ранее незамеченную вещь. У нас получился компилятор. Препроцессинг, таблицы символов, кодогенератор, оптимизатор и (sic!) обработчик неявных типов. Компилятор из Си в Си. Из описаний типов в h-файлах в функции заполнения типов.
после схватки
В понедельник начался production - началось Unit-тестирование. Поступило 3 или 4 баг-репорта, после этого поток их зачах. Разработчики научились пользоваться инструментом высшей формы copy/paste, данной им в руки, научились расширять библиотеку и править индексы внутри функций заполнения структур.
В заметках менеджера проекта появилась запись: "strong scripting ability".
На столах программистов - распечатки "файлов промежуточного формата". Внутреннее описание на выходе Stage2 оказалось удивительно удобным для быстрого просмотра объявлений структур.
выводы
Кодогенерация в сухом остатке - простой и надежный метод, решающий множество проблем с повторяющимся шаблонным текстом. В частности - ошибки ввода, копирования и однообразные изменения в копируемом шаблоне. Основная задача кодогенерации - подготовить данные в удобном для преобразования формате. И, конечно, адекватный выбор инструментальных средств.
После первого применения кодогенерации - постоянно ловишь себя на поиске паттернов, поддающиеся кодогенерации. И находишь. Следующий генератор был написан на shell и выдавал 501 строку менее чем за секунду. Это было три switch, в каждом из которых от 30 до 100 case. Весьма однообразных смею заметить.
Было сразу ясно, что нединамические языки для разбора заголовков и кодогенерации нам совершенно бесполезны. Скриптовый вариант дал скорость отладки и написания плюс превосходные средства обработки текста - регулярные выражения, вписанные в сам язык. Ruby отпал сразу - его не было на сервере, Perl чуть позднее - потому что автор этой статьи неважно им владеет. Степень владения awk была сопоставимой с Perl, но компенсировалась простотой nawk - полный мануал по нему занял 5.5 страниц текста, включая авторов, копирайты, полный синтаксис, библиотеку функций и список ошибок в реализации. Ставка на awk стала выигрышной стратегией. Знание хотя бы одного скриптового языка делает освоение awk делом одного вечера и первых 5 KB написанного кода. Владение shell, sed и ruby в качестве фона оказалось предостаточно. Слегка замусоленная распечатка man nawk с http://www.openbsd.org тому свидетельство.
Организация framework в стиле true unix way, как набора слабосвязанных узкоспециализированных утилит интегрированных через make — себя полностью оправдала. К самописным были добавлены стандартные, такие как sed, indent, shell, cpp. Комплекс не является монолитным, поэтому модификация отдельных частей не затрагивает прочие (если речь не идёт об изменении форматов данных).
Интересно также, что в связи с сложной ситуацией на проекте, у нашей команды были полностью развязаны руки, как в дизайне системы, так и в реализации и выборе инструментальных средств. Более 50 Kb кода на нескольких языках программирования (в основном Cи и awk, в промежуточном слое make, sed, shell)
Первое прикосновение к миру кодогенерации оказалось в высшей степени познавательным. Самый презренный способ кодирования, тупое копирование, автоматизированный должным образом, превращается в свою противоположность - кодогенерацию, почтенную и уважаемую технику.
благодарности
Стасу и Андрею - за плодотворное сотрудничество в этом захватывающем програмном квесте. И еще раз Стасу - за идею об awk.
Владимир "mend0za" Шахов
Второе упоминание попалось двумя годами позднее, в уже ставшей классической книге Эрика Реймонда "Дао программирования в Unix".
Оба этих случая осели на задворках сознания, но я продолжал считать что кодогенерация - удел богов, трансцендентные техники просветленных гуру.
вводная
Не поминай гуру всуе. Однажды я оказался в Индии, в одной из крупных софтопроизводящих контор на стажировке. После некоторого периода обучения нас разбросали по существующим проектам. Проект, в который попали двое моих сотоварищей и ваш покорный слуга, находился в состоянии "мы работаем 14 часов в день без выходных, потому что совсем не укладываемся в сроки". Или, говоря более образно — часть филея, что чуть ниже спины, уже ярко вставала на горизонте. И мы пахали. Аминь.
постановка задачи
В один из дней октября к нам приходит техлид. И говорит потрясающую вещь:
— Ребята, у нас через день начинается фаза Unit-тестирования. А мы только сейчас поняли, что у нас нет совсем ничего, кроме кода, совсем-совсем. Потом пауза и жалобно-тоскливый взгляд (см.сцену с котом из "Шрек-2").
— Сделайте как-нибудь и что-нибудь. Нам нужен framework.
Итак — исходные данные. UnitTesting — это процесс запуска функций с параметрами. Самое нудное и трудоемкое — это заполнение параметров. Более 100 разнотипных вложенных структур с десятками разномастных полей. Нам надо автоматизировать процесс заполнения структур, имея текстовые файлы с данными и заголовочные файлы с определениями типов. Язык исходных текстов проекта — С. Операционная система — Solaris.
Местные программисты всегда делали copy/paste. Теперь надо его автоматизировать.
ода copy/paste (лирическое отступление)
Что такое программирование в Индии? Это броуновский процесс безостановочного внесения изменений. Любимый способ их внесения — copy/paste. У тебя проблемы? Сделай copy/paste у себя, у соседки, у коллег из соседнего отдела. Об этом тебе говорят программисты, техлиды и менеджеры.
дизайн
На дизайн ушло 3 (три) часа. Подошли прагматично, нам нужно иметь нечто, что в 80-90% случаев создаст корректный код заполнения типов. Отлично вписались классические методы проектирования Unix way — разбитие функционала на мелкие простые узкоспециализированные утилиты. Метод передачи данных - Unix-pipe, формат — форматированный plain-text.
Stage1 — получает на вход Си-код, вырезает из него все объявления функций, разбирает списки параметров и извлекает типы параметров. Выводит полученные типы, один за другим.
Stage2 — на вход получает список типов. Выполняет разбор всех объявлений из заголовочных файлов с типами. Определяются все типы, имеющие отношение к исходным (как поля структур, enums, unions, либо простые typedef из типа в тип). Выводится описание найденных зависимых типов в упрощенном формате, типа:
struct name_st
<tab>field1_t field1
<tab>field2_un field2
<blank line>
raw field1_t
<blank line>
union field2_un
<tab>UU=1
<tab>BB
Stage3 — получает описания типов и генерирует по ним функции заполнения типов на Си.
Следующее проектное решение - есть библиотека базовых (raw) типов, которые не требуют заполнения. Для них функции уже написаны и подключаются к коду. Данное решение имело одно интересное следствие - пользователь может расширять библиотеку базовых типов любыми своими типами. В raw оказались такие типы как int, short, unsigned int, boolean.
fill_sometype() возвращает указатель на переменную типа sometype, выделенную и инициализированную указанным значением. Значение — строка (массив строк для структуры), задача функции - выделить память, привести строку к нужному типу и инициализировать значением. Интересным следствием введения системы базовых типов оказалось то, что преобразования из строк шли только в них, когда как производные типы просто вызывали соответсвующие функции заполнения.
И финальное решение — венец прагматизма. Нам навязали plain-структуру конфигурационных файлов для структур. То есть независимо от уровня вложенности — все возможные параметры записываются в строчку, никаких перекрестных ссылок. Итого — пользователь сам следит за корректностью индексов передаваемым функциям заполнения. Мы просто ставим их подряд.
Также была сделана обобщенная функция make_table(). Она получала на вход имя конфигурационного файла для структуры, и указатель на функцию заполнения для нее. Формат структуры не имел значение. Дизайн make_table() оказался настолько обобщённым, что она смогла переварить все наши 100 с небольшим структур. Выходным значением служил массив из массивов строк. Каждый массив строк - один набор значений для структуры. Коих может быть много.
Часть из вышеописанного обрела конкретные черты уже по ходу разработки, но базовые принципы были заложены изначально.
И, наконец, выбор инструментов:
- базовая библиотека и make_table() - на Си;
- кодогенерация и разбор текста - awk (nawk).
разработка
Разработка заняла 6 дней. С вечера понедельника до вечера субботы.
Мы узнали массу нового о коде наших коллег, об awk, приняли и отбросили массу тактических решений.
Краткий список граблей, которые были пройдены за неделю:
- выделение памяти на solaris с помощью malloc() давало SIGBUS . memalign() не давал;
- в исходниках наших коллег обнаружилось 3-4 различных стиля написания кода, что изрядно затруднило на начальном этапе разбор заголовочных файлов. Добавление каждого нового файла с типами ломало парсер с регулярными выражениями напрочь;
- было выявлено порядка 40 defines, влияющих на список членов структур;
- были найдены структуры и union's, объявляемые прямо в теле структур без предварительного объявления типа.
В субботу была реализована схема, которая решила проблемы 2 и 3. На массив заголовочных файлов натравливался препроцессор с передачей всех этих чудесных define, c предварительным вырезанием всех директив #include. Результат препроцессинга десяти h-файлов сбрасывался в preproc.h, по которому проходили с утюгом утилитой indent, приводя содержимое к чудесному единообразию и общности стиля.
Stage2 лихо разбирало preproc.h, создавая по ходу массу промежуточных файлов со справочной информацией по коду, например файл описания всех структур, всех enum и всех union.
Кодогенератор (stage3) писался последним, получился некрасивым, во многом дублирующим и совершенно неинтеллектуальным. Короче — именно таким, каким его и хотели видеть.
По ходу разработки выяснилось, что нужен интегратор для полученного набора утилит. Им стал make. Формат Makefile с его целями и зависимостями оказался удивительно удобен для извлечения пользы из различных сочетаний наших утилит, а также для демонстрации нашего прогресса в работе паникующим техлидам.
результат
И был вечер дня шестого, и фреймворк был готов. Мы посмотрели на результат усилий и сказали "это хорошо!" (С) Господь Бог.
Что же в итоге? Венец copy/paste. Масса функций, копирующих друг друга и различающихся лишь незначительно. Но появляющихся быстрее, чем за 2 секунды работы.
Если коротко и предметно:
- make modules - сгенерировать код для всех подмодулей системы;
- echo struct_type|make stage2 - сгенерировать описания структуры и всех типов, относящихся прямо и косвенно к структуре;
- echo struct_type|make stage2|make stage3 - сгенерировать код заполнения для структуры и всех зависимых типов;
- cat proto.h|make stage1 - список всех типов, использованных как параметры функций, объявленных в proto.h.
Пристальный взгляд на творение рук наших выявил одну ранее незамеченную вещь. У нас получился компилятор. Препроцессинг, таблицы символов, кодогенератор, оптимизатор и (sic!) обработчик неявных типов. Компилятор из Си в Си. Из описаний типов в h-файлах в функции заполнения типов.
после схватки
В понедельник начался production - началось Unit-тестирование. Поступило 3 или 4 баг-репорта, после этого поток их зачах. Разработчики научились пользоваться инструментом высшей формы copy/paste, данной им в руки, научились расширять библиотеку и править индексы внутри функций заполнения структур.
В заметках менеджера проекта появилась запись: "strong scripting ability".
На столах программистов - распечатки "файлов промежуточного формата". Внутреннее описание на выходе Stage2 оказалось удивительно удобным для быстрого просмотра объявлений структур.
выводы
Кодогенерация в сухом остатке - простой и надежный метод, решающий множество проблем с повторяющимся шаблонным текстом. В частности - ошибки ввода, копирования и однообразные изменения в копируемом шаблоне. Основная задача кодогенерации - подготовить данные в удобном для преобразования формате. И, конечно, адекватный выбор инструментальных средств.
После первого применения кодогенерации - постоянно ловишь себя на поиске паттернов, поддающиеся кодогенерации. И находишь. Следующий генератор был написан на shell и выдавал 501 строку менее чем за секунду. Это было три switch, в каждом из которых от 30 до 100 case. Весьма однообразных смею заметить.
Было сразу ясно, что нединамические языки для разбора заголовков и кодогенерации нам совершенно бесполезны. Скриптовый вариант дал скорость отладки и написания плюс превосходные средства обработки текста - регулярные выражения, вписанные в сам язык. Ruby отпал сразу - его не было на сервере, Perl чуть позднее - потому что автор этой статьи неважно им владеет. Степень владения awk была сопоставимой с Perl, но компенсировалась простотой nawk - полный мануал по нему занял 5.5 страниц текста, включая авторов, копирайты, полный синтаксис, библиотеку функций и список ошибок в реализации. Ставка на awk стала выигрышной стратегией. Знание хотя бы одного скриптового языка делает освоение awk делом одного вечера и первых 5 KB написанного кода. Владение shell, sed и ruby в качестве фона оказалось предостаточно. Слегка замусоленная распечатка man nawk с http://www.openbsd.org тому свидетельство.
Организация framework в стиле true unix way, как набора слабосвязанных узкоспециализированных утилит интегрированных через make — себя полностью оправдала. К самописным были добавлены стандартные, такие как sed, indent, shell, cpp. Комплекс не является монолитным, поэтому модификация отдельных частей не затрагивает прочие (если речь не идёт об изменении форматов данных).
Интересно также, что в связи с сложной ситуацией на проекте, у нашей команды были полностью развязаны руки, как в дизайне системы, так и в реализации и выборе инструментальных средств. Более 50 Kb кода на нескольких языках программирования (в основном Cи и awk, в промежуточном слое make, sed, shell)
Первое прикосновение к миру кодогенерации оказалось в высшей степени познавательным. Самый презренный способ кодирования, тупое копирование, автоматизированный должным образом, превращается в свою противоположность - кодогенерацию, почтенную и уважаемую технику.
благодарности
Стасу и Андрею - за плодотворное сотрудничество в этом захватывающем програмном квесте. И еще раз Стасу - за идею об awk.
Владимир "mend0za" Шахов
Сетевые решения. Статья была опубликована в номере 08 за 2008 год в рубрике success story
