Библиотека сайта rus-linux.net
Contingent: Динамическая система сборки
Оригинал: Contingent: A Fully Dynamic Build System
Авторы: Brandon Rhodes, Daniel Rocco
Дата публикации: July 12, 2016
Перевод: Н.Ромоданов
Дата перевода: январь 2017 г.
Системы сборки и согласованность
Проблема, описанная выше, характерна не только для системы Sphinx. Мало того, что она присутствует в других системах, таких как LaTeX, она может поразить даже такие проекты, в которых в случае, если в них определенным образом сформировать перекрестные ссылки, с помощью почтенной утилиты make выполняется обычная компиляция.
Поскольку проблема является старой и всеобъемлющей, ее решение также уже давно известно:
$ rm -r _build/ $ make html
Если вы удалите все выходные данные, то вы гарантируете полную пересборку! В некоторых проектах для команды rm -r даже есть алиас, который называется clean, так что для того, чтобы выполнить согласованную пересборку, достаточно лишь запустить команду make clean.
За счет того, что стираются все копии всех промежуточных или результирующих данных, команда rm -r может заставить выполнить сборку с самого начала и не использовать закешированные данные — не использовать запомненное в памяти предыдущее состояние, что могло бы привести к неправильным результатам.
Но можно ли разработать более лучший подход?
А что если ваша система сборки пользуется долговременным хранилищем данных (например, базами данных — прим.пер.) и при пересборке результата оттуда берутся названия всех глав, всех разделов и и все перекрестные ссылки, которые могут быть между отдельными фразами? Желательно, чтобы решение относительно того, следует ли пересобирать другие документы после изменения в одном исходном файле, было бы точным, а не полагалось на простых догадках, и правильным, а не выдавало бы нам несогласованные данные.
Можно было бы воспользоваться системой, похожей на старый добрый статический make, но которая бы анализировала зависимости между файлами по мере того, как они пересобирались, и которая бы динамически добавляла и удаляла зависимостей по мере того, как добавлялись, обновлялись или удалялись перекрестные ссылки.
В далее в настоящей главе мы сконструируем на языке Python такую систему, которая будет называться системой Contingent. Система Contingent гарантирует корректность сборки при наличии динамических зависимостей и при этом выполняет минимально возможное количество действий по пересборке документов. Хотя ее можно использовать в любой предметной области, мы будем ее применять для решения одного из вариантов маленькой задачи, которая была описана выше.
Соединяем задачи и создаем граф
В любая система сборки нужен способ связывать между собой входные и выходные данные. Например, в нашем обсуждении, приведенном выше, по каждому из трех текстовых файлов с разметками создается соответствующий выходной файл в формате HTML. Самым естественным способом представить эти отношения в виде наборов прямоугольников и стрелок или, в математической терминологии, вершин и ребер, т.е. сформировать граф (рис. 4.1).
Рис.4.1. По результатам анализа трех входных файлов создаются три результирующи файла.
В каждом из языков, на котором программист может решить написать систему сборки, будут предлагаться различные структуры данных, с помощью которых можно будет представить такой граф, состоящий из вершин и ребер.
Как мы бы могли представить такой граф на языке Python?
В языке Python приоритет отдается четырем базовым структурам данных поскольку они обеспечены непосредственной поддержкой в самом синтаксисе языка. Вы можете создавать новые экземпляры этих больших-четырех структур данных просто набрав в вашем исходном коде их литеральное представление и эти четыре типа объектов доступны в виде встроенных символов, которые можно использовать не импортируя.
Тип кортеж (tuple) представляет собой последовательность элементов, которую можно только читать и элементы которой используются для хранения разнородных данных; каждый элемент в кортеж обычно означает что-то другое. Ниже кортеж объединяет имя хоста и номер порта, и он становится бессмысленным в случае, если элементы будут перепределены:
('dropbox.com', 443)
Тип список (list) является изменяемой последовательностью, используемой для хранения данных одного и того же типа; каждый элемент этого типа, как правило, имеет ту же самую структуру и смысл, как все остальные элементы. Списки можно использовать либо для хранения данных в их исходном порядке, либо их можно переупорядочить или отсортировать для создания новой и более удобной в использовании последовательности данных.
['C', 'Awk', 'TCL', 'Python', 'JavaScript']
В типе данных множество (set) понятие порядок отсутствует. В множестве запоминается только то, было ли добавлено данное значение, а не то, сколько раз оно было добавлено, и, следовательно, их можно рассматривать как структуры данных, предназначенные для удаления дубликатов из потока данных. Например, в следующих двух множествах будет по три элемента:
{3, 4, 5}
{3, 4, 5, 4, 4, 3, 5, 4, 5, 3, 4, 5}
Тип данных словарь (dict) представляет собой ассоциативную структуру данных, предназначенную для хранения значений, доступных с помощью ключа. Словари позволяют программисту выбрать ключ, с помощью которого индексируется каждое значение, а не использовать для этого автоматическую целочисленную индексацию, которая имеется в кортежах и списках. Поиск поддерживается с помощью хэш-таблицы, а это значит, что поиск по ключу работает с той же самой скоростью независимо от того, хранится ли в словаре десяток или миллион ключей.
{'ssh': 22, 'telnet': 23, 'domain': 53, 'http': 80}
Ключевой особенностью языка Python является то, что эти четыре структуры данных можно объединять друг с другом любым образом. Программист может произвольным образом их вкладывать внутри друг друга для того, чтобы создавать более сложные хранилища данных, правила работы с которыми и их синтаксис остаются простыми как и у данных, лежащих в их основе - кортежей, списков, множеств и словарей.
Учитывая, что в каждом из наших ребер графа нужно знать, по крайней мере, его начальный узел и его конечный узел, то простейшим представлением будет кортеж. Верхнее ребро, изображенное на рис.4.1 может выглядеть следующим образом:
('tutorial.rst', 'tutorial.html')
Как можно запомнить несколько ребер? Хотя нашим первоначальный решением может быть просто сохранить все наши кортежи с ребрами в списке, оно будет иметь недостатки. Список чувствителен к порядку хранящихся в нем элементов, но о порядке ребер в графе говорить абсолютно не имеет смысла. И в списке можно без всяких проблем хранить несколько копий одного и того же ребра несмотря на то, что нам нужно, чтобы можно было нарисовать только одну стрелку между файлами tutorial.rst и tutorial.html. Поэтому правильным выбором будет множество, которое для рис.4.1. будет представлено как:
{('tutorial.rst', 'tutorial.html'),
('index.rst', 'index.html'),
('api.rst', 'api.html')}
Такое представление позволяет быстро перебирать все ребра графа, быстро выполнять обреации добавления и удаления каждого и иметь возможность быстро проверить, имеется или отсутствуеь то или иное ребро.
К сожалению, это не единственные операции, которые нам нужны.
Система сборки, такая как Contingent, должна уметь определять связь между данной вершиной и всеми вершинами, подсоединенными к нему. Например, когда изменяется файл api.rst, система Contingent для того, чтобы свести к минимуму выполняемую работу и, в то же время, гарантировать полную пересборку, должна знать, какие другие вершины, если таковые имеются, зависят от этого изменения. Чтобы ответить на этот вопрос, на какие вершины влияет изменение вершины api.rst, нам нужно найти ребра, исходящие (outgoing) из вершины api.rst.
Но создание графа зависимостей потребует от системы Contingent также уметь работать со входящими вершинами (inputs). Например, какие входные вершины были использованы, когда система сборки пересобирала результирующий документ tutorial.html? Благодаря тому, что система Contingent может определить входные ребра для каждой вершины, она может узнать, что файл api.html зависит от файла api.rst, а файл tutorial.html от него не зависит. По мере того, как меняются файлы с исходным кодом и возникает необходимость в пересборке, система Contingent заново перебирает входящие ребра каждой измененной вершины с тем, чтобы удалить потенциально устаревшее ребро, а также снова определить, какие на это раз ресурсы использует задача.
Наше множество, состоящее из кортежей, не дает простого ответа на любой из этих вопросов. Если нам потребуется знать о взаимосвязи между файлом api.html и остальной частью графа, то нам нужно будет пройти по всем множеству в поисках ребер, которые могут начинаться или заканчиваться в вершине api.html.
Ассоциативная структура данных, такая как словарь dict языка Python, позволила бы упростить все эти хлопоты за счет прямого поиска всех ребер, отходящих от конкретной вершины:
{'tutorial.rst': {('tutorial.rst', 'tutorial.html')},
'tutorial.html': {('tutorial.rst', 'tutorial.html')},
'index.rst': {('index.rst', 'index.html')},
'index.html': {('index.rst', 'index.html')},
'api.rst': {('api.rst', 'api.html')},
'api.html': {('api.rst', 'api.html')}}
Поиск ребер для конкретной вершины теперь выполнялся бы невероятно быстро за счет того, что каждое ребро запоминается дважды: один раз в наборе входящих ребер, и один раз в наборе исходящих ребер. Но для того, чтобы увидеть, какие ребра являются входящими и какие — исходящими, их в каждом наборе потребуется просматривать дополнительно. Кроме того, немного лишним будет повторяющееся запоминание названия вершине в его множестве ребер.
Решение обоих этих недостатков заключается в размещении входящих и исходящих ребер в своих собственных отдельных структурах данных, которые также освобождают нас от повторного запоминания названий вершин для каждого из ребер, в которых они присутствуют.
incoming = {
'tutorial.html': {'tutorial.rst'},
'index.html': {'index.rst'},
'api.html': {'api.rst'},
}
outgoing = {
'tutorial.rst': {'tutorial.html'},
'index.rst': {'index.html'},
'api.rst': {'api.html'},
}
Обратите внимание на то, что структура с исходящими ребрами outgoing представлена непосредственно с помощью синтаксиса языка Python, причем именно так, как мы это выше изобразили на рис.4.1: исходные документы, изображаемые в левой части, будут преобразованы системой сборки в выходные документы, показанные в правой части. В данном простом примере для каждого исходного документа указывается только один выдаваемый документ - все выходные наборы данных имеют только по одному элементу - но скоро мы покажем примеры, когда один входной узел может иметь несколько результирующих вершин.
Каждое ребро в этой структуре данных, представляющей собой словарь из множеств, действительно представлено дважды, один раз как ребро, исходящее от этой вершины (tutorial.rst → tutorial.html) , и снова как ребро, входящее в этот узел (tutorial.html ← tutorial.rst). Эти два представления описывают одно и то же соотношение, но если его рассматривать с противоположных точек из двух вершин, расположенных на различных концах ребра. Но в обмен на эту избыточность, структура данных поддерживает быстрый поиск, что необходимо в системе Contingent.
Перейти к следующей части статьи.
Перейти к началу статьи.