Звездные войны в исходном коде

У меня давно была идея реализовать что-нибудь интересное, связанное с квайнами. И наконец-то получилось довести это дело до конца. Когда-то увидел реализацию игры «Жизнь» в исходном коде: Self Printing Game of Life и мне захотелось сделать нечто похожее. Некоторое время поразмыслив, я вспомнил, что существует ASCII-графика. Но еще интересней и сложнее было бы сделать анимацию в ASCII-графике. Пример долго искать не пришлось, почти сразу же были найдена анимация «Звездных войн», а точнее 4 эпизода «Новая Надежда» под названием Asciimation. Работа японского программиста Yusuke Endoh «квайновая эстафета» также подстегнула меня к реализации этой идеи. В процесс реализации такого «фильма» пришлось решить множество других проблем, о чем, впрочем, жалеть не пришлось.

Получившийся исходник вот: gist. Для облегчения «просмотра» там также содержится скрипт, который и будет крутить всю анимацию. Исходники же всего проекта для его генерации, интерфейса и других утилит выложены на гитхабе: Freaky-Sources (Туда же включены квайны-палиндромы, о которых я уже писал). Понятное дело, что подобная вещь не несет в себе никакой практической пользы, это просто just for fun.

Введение

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

Вышеупомянутая «игра Жизнь» в качестве поля использует строки, которые инициализируются и выводятся в начале исходного кода программы. Такой подход допустим, если количество кода невелико, и в процессе компиляции он всегда будет виден. Однако в моем случае размер кода составляет несколько сотен килобайт, а значит выводить кадры нужно обязательно в конце, чтобы их можно было увидеть. Было решено выводить кадры не в виде настоящих строчек, а в виде однострочных комментариев (многострочные тоже можно использовать), что позволило выводить их без лишних хвостовых символов (конечной фигурной скобочки) и кавычек.

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

Этапы генерации квайна

Таким образом, я решил разбить процесс написания любого квайна на следующие этапы:

• Генерация кода.
• Генерация данных.
• Минификация кода.
• Форматирование кода.
• Генерация квайна.

Все эти этапы выполняются для специальным образом составленного шаблона. Под «кодом», применительно к звездным войнам, подразумевается код, который который распаковывает сжатые данные. А данными и является запакованный массив кадров анимации. Минификация нужна для того, чтобы сделать код нечитаемым уменьшить текстовый размер кода.

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

Для того, чтобы было легче ориентироваться в этих этапах, я написал интерфейс на WinForms.

• Слева вверху текстовое поле, в которое вводится шаблон квайна со всеми маркерами. Их предназначение рассматривается ниже. Первые четыре этапа выполняются именно в этом поле.
• Слева внизу различные параметры и кнопки для выполнения вышеупомянутых этапов. Также код шаблона или результирующего квайна можно сразу же проверить на ошибки с помощью компиляции.
• Справа вверху поле, которое заполняется кодом квайна, сгенерированном на последнем этапе.
• Справа вверху поле, в которые выводятся выводится следующая итерация квайна после компиляции. Также кнопка «Console Output -> Output» с количеством итераций нужна для того, чтобы зациклить процесс компиляции квайна и увидеть покадровую анимацию (ну или что-то еще).

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

Шаблон квайна

Шаблон является исходной точкой такого сложного квайна, и он может выглядеть следующим образом:

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

• /*#...*/… /*...#*/ — Код. Участки кода между этими маркерами ищутся по файлам из указанной директории.
• /*%...*/… /*...%*/ — Данные. Между этими маркерами вставляются сгенерированные с помощью определенных методов данные, которые должны быть представлены в строковой форме (ну т.е. обычная строка, массив строк, массив байт, целых чисел и т.д.). Вообще говоря, из маркеров данных можно извлекать информацию о методе, искать его в скомпилированной сборке и вызывать его с помощью рефлексии. Но я решил пока что ограничиться ручным вызовом нужных методов, потому что это более универсальный подход (так легче портировать на другие языки).
• /*$...*/… /*...$*/ — Параметры. Данные маркеры обозначают код, который меняется при каждой следующей итерации отображения квайна. Они указываются в специальной таблице, в которой указывается код для замены. В данном случае параметрами являются номер текущего кадра (он инкрементируется каждый раз) и поле вывода кадра внизу, реализованное с помощью однострочных комментариев. Некоторые параметры являются интронами, т.е. строчками, которые не влияют на код в следующей итерации. В данном случае интроном является поле вывода.
• /*@*/ — Печать. Это специальный маркер, в который собственно вставляется код для вывода всего квайна. Он существует только в единичном экземпляре. Замена происходит в самом конце, после генерации кода и данных на предыдущих этапах. Важно отметить, что для предотвращения дублирования секции данных (чтобы не печатать их в самом квайне и в данной строчке), на данном этапе происходит замена не на сами данные, а на параметры (т.е. вместо «asdf», содержащейся в output, выводится '"'+output+'"').

Таким образом, совмещая информацию об этапах и маркерах, можно построить следующую графическую схему:

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

Подробнее о всех этапах расписано ниже.

Генерация кода

При генерации кода анализируется все файлы исходных кодов из указанной папки. И код между маркерами /*#...*/… /*...#*/ копируется в соответствующие места в исходном шаблоне. Например, в следующем примере класс HuffmanRle2 целиком копируется в участок между /*#HuffmanRleDecode2*//*HuffmanRleDecode2#*/. Для того, чтобы игнорировать некоторые фрагменты кода внутри этих маркеров (например, методы .ToString() не нужны в квайне, они нужны для отладки) и не разбивать данный фрагмент на два, были введены маркеры /*#Ignore*//*Ignore#*/, которые позволяют игнорировать весь код внутри них.


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

Генерация данных

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

Frame:
0..3 — type:

• 000 — base:
  3..13 — chars count
  13… — huffman rle codes
• 001 — left:
  010 — top:
  011 — right:
  100 — bottom:
  101 — changed:
  3..10 — changes count
  10… — changes

Change:
0..2 — type:

• 00 — one char:
  2..12 — position
  12… — huffman code
• 01 — line horizontal:
  2..12 — position
  12..19 — chars count
  19… — huffman codes
• 10 — line vertical:
  2..12 — position
  12..16 — chars count
  16… — huffman codes

К сожалению, финальное сжатие получилось не таким большим, как хотелось бы, но вполне приемлемым. А хотелось бы на уровне lzma в 7-zip, т.е. меньше 100 Кб. Скорее всего, с помощью более продвинутых методов (интервального кодирования, словарных методов), удалось бы достичь еще большей степени сжатия.

Минификация кода

Минификация нужна для того, чтобы уменьшить размер кода в текстовом формате. Для обработки C# кода использовалась библиотека NRefactory. Ее преимуществом перед Roslyn является то, что дерево разбора можно изменять в процессе, что требуется в задачи минификатора.

Укорочение имен классов, методов, полей, локальных переменных

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

Для того, чтобы с одной стороны использовать минимальное количество идентификаторов, а с другой — чтобы они не пересекались и не приводили к ошибкам компиляции, алгоритм укорочения был разбит на следующие этапы:

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

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

Стоит отметить, что библиотека поддерживает игнорируемые идентификаторы, т.е. такие, которые по каким-то причинам не должны быть укорочены, что используется в данном проекте (параметры квайна).

Для получения списка всех ссылок на используемые идентификаторы (Find All References в Visual Studio), используется механизм ресолвинга NRefactory. Для этого сначала необходимо откомпилировать дерево (на каждом этапе: локальные переменные, члены типов, типы):

var unresolvedFile = SyntaxTree.ToTypeSystem();
var projectContent = projectContent.AddOrUpdateFiles(_unresolvedFile);
var compilation = projectContent.CreateCompilation();
var resolver = new CSharpAstResolver(_compilation, SyntaxTree, _unresolvedFile);

После чего можно искать ссылки следующим образом:

var resolveResult = resolver.Resolve(node);
var findReferences = new FindReferences();
...
findReferences.FindLocalReferences();
...
findReferences.FindReferencesInFile();

Другие минификации

Также были реализованы следующие небольшие минификации:

• Удаление ключевого слова private
• Удаление пространств имен
• Сокращение выражения инициализации переменных:
  

  • List<byte> a = new List<byte>() -> var a = new List<byte>()

  • var a = new b() -> b a = new b()

  
  Примечание: такую замену можно выполнить и с помощью шаблонного поиска, описанного в статье:
  Using NRefactory for analyzing Csharp code
  
• Удаление фигурных скобок, внутри которых только одно выражение: if (a) { b; } => if (a) b;
• Сокращение записи сравнения с булевым типом: if (a == true) => if (a); if (a == false) => if (!a)
• Удаление регионов и комментариев.

Удаление пробельных символов и переносов строк

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

Минификатор реализован отдельным проектом и его и можно скачать здесь: CSharp-Minifier. Он в первую очередь разрабатывался с нацелом на сокращения кода в квайнах, поэтому нет ничего удивительно в том, что он обладает немного странной функциональностью. Впрочем, я с радостью приму ваши замечания и/или пулл-риквесты.

Форматирование кода

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

Генерация квайна

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

1. Инициализация шаблона:
   template =
   

   class P
   {
   	static void Main()
   	{
   		var a = 6;
   		/*@*/
   		int b = 10;
   	}
   }
   

   
   
2. Генерация шаблона строки, используемой для печати квайна. Кавычки, обратные слеши и переносы строк необходимо экранировать, так что их представление идет отдельными параметрами при выводи форматированной строки.
   kernel = "var s = {1}{0}{1}; System.Console.Write(s,s,'{1}','{2}{2}',{1}{2}r{2}n{1});"
   
3. Замена в шаблоне маркера на строку, используемую для печати из предыдущего этапа. Т.к. в C# при выводе параметров используются фигурные скобки, то их также необходимо экранировать. Это делается путем их дублирования.
   str = template.Replace("{", "{{").Replace("}", "}}").Replace("/*@*/", kernel)
   str =
   

   class P
   {{
   	static void Main()
   	{{
   		var a = 6;
   		var s = {1}{0}{1}; System.Console.Write(s,s,'{1}','{2}{2}',{1}{2}r{2}n{1});
   		int b = 10;
   	}}
   }}
   

   
   
4. Генерация результирующей строки, использующейся для печати квайна:
   insertToResult = "var s=\"" + str + "\""
   insertToResult =
   

   var s="
   class P
   {{
   	static void Main()
   	{{
   		int a=6;
   		var s={1}{0}{1}; Console.Write(s,s,'{1}','{2}{2}',{1}{2}r{2}n{1});
   		int b=10;
   	}}
   }}";
   Console.Write(s,s,'"', '\\', "\r\n");
   

   
   
5. Замена маркера в исходном шаблоне на получившуюся строку:
   result = template.Replace("/*@*/", insertToResult)
   result =
   

   using System;
   class c
   {
   	static void Main()
   	{
   		int a=6;
   		var s="using System;class c{{static void Main(){{int a=6;var s={1}{0}{1};Console.Write(s,s,'{1}','{2}{2}',{1}{2}r{2}n{1});int b=10;}}}}";
   		Console.Write(s,s,'"', '\\', "\r\n");
   		int b=10;
   	}
   }
   

   
   

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

Запуск

После того, как квайн сгенерирован, его можно например сохранить в файл Asciimation.cs и вывести один кадр следующей командой:
"C:\Windows\Microsoft.NET\Framework64\v4.0.30319\csc.exe" Asciimation.cs && (Asciimation > Asciimation.cs) && Asciimation

А чтобы посмотреть весь сгенерированный «фильм», нужно воспользоваться следующим скриптом:

echo off
SET /a i=0
:LOOP
IF %i%==3591 GOTO END
"C:\Windows\Microsoft.NET\Framework64\v4.0.30319\csc.exe" Asciimation.cs && (Asciimation > Asciimation.cs) && Asciimation
SET /a i=%i%+1
GOTO LOOP
:END
pause

Заключение

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

Сгенерированные файлы и батники можно скачать здесь: AsciimationQuine_1_3.7z. В перспективе можно попробовать заняться цепными квайнами и, возможно, повторить подвиг Yusuke Endoh, только уже не вручную, а с автоматической генерацией.

Специально для тех, кто не имеет возможности скомпилировать, но хочет посмотреть процесс: