Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ОБРАЗОВАНИЯ

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»

Факультет информатики, математики и компьютерных наук

Программа подготовки бакалавров по направлению

09.03.04 Программная инженерия

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

Инструмент визуализации истории для системы контроля версий Git

Емельянова Светлана Леонидовна

Рецензент - Ведущий инженер исследователь А.И. Николаев

Научный руководитель - доцент О.Р. Набиуллин

Нижний Новгород

2020

• Содержание
• Глава 1. Обзор известных программ и решений в области визуализации систем контроля версий
• 1.1 Существующие программы и решения
• 1.1.1 Code Swarm
• 1.1.2 Gource
• 1.1.3 Github Visualizer
• 1.2 Обзор методов визуализации графов
• 1.2.1 Gephi
• Force Atlas 2
• 1.2.2 TouchGraph Google Browser
• Выводы по главе
• Глава 2. Архитектура, требования к системе и выбор инструментов
• 2.1 Требования к системе
• 2.1.1 Функциональные требования
• 2.1.2 Требования к удобству и простоте использования
• 2.1.3 Ограничения проектирования
• 2.2 Архитектура
• 2.3 Используемые языки программирования
• 2.4 Используемые библиотеки
• 2.4.1 С
• 2.4.1 GoLang
• Глава 3. Особенности реализации системы
• 3.1 Git API
• 3.2 Визуализации дерева файлов
• 3.2.1 Cиловая схема
• 3.2.2 Масштабирование и рендеринг
• 3.2.3 Обновление цветов
• 3.3 Автоматизация сборки
• 3.3.1 Go модули и вендоринг
• 3.3.2 Cmake и make
• Выводы по главе
• Заключение
• Список литературы
• Приложения

Введение

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

Современная система контроля версий предоставляет своим клиентам возможность создавать, отслеживать и изменять историю изменений в программных проектах и это дает им возможность удобной совместной работы над одним проектом. Как следствие, члены команды могут работать отдельно благодаря выполнению своих задач в собственных отдельных ветках, которые после окончания работы объединяются с основной.

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

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

Есть несколько инструментов визуализации, которые решают эту задачу, такие как Code Swarm, Gource и другие.

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

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

Для достижения этой цели были сформированы следующие этапы:

1. исследование существующих подходов и методов;

2. формирование требований к системе;

3. проектирование архитектуры системы;

4. разработка нового инструмента, отвечающего всем поставленным задачам.

Глава 1. Обзор известных программ и решений в области визуализации систем контроля версий

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

1.1 Существующие программы и решения

визуализация история проект

1.1.1 Code Swarm

В числе первых инструментов визуализации стоит упомянуть Code Swarm. Он был разработан Майклом Огава из Калифорнийского университета в Дэвисе. Используя этот инструмент, вы можете «видеть, как люди принимают участие в репозитории проекта и наблюдать за жизнью проекта как за неким биологическим организмом» (Simon, 2008).

Рисунок 1. Code Swarm

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

В данном решении заметны несколько недостатков:

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

2. Сложный интерфейс для интуитивного понимания происходящего на видео анимации. Без предварительного ознакомления, сложно понять.

Достоинства, которые хотелось бы отметить:

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

1.1.2 Gource

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



Рисунок 2. Gource

Рисунок 3. Gource

Достоинства:

1. Стоит отметить, что есть поддержка нескольких версионных систем: Git, Mercurial, Bazaar и SVN.

2. Простой, доступный интерфейс.

3. Иерархическая структура файлов.

4. Богатый набор опции для пользовательских настроек. В особенности хочется отметить опцию для выбора диапазона дат, можно отследить не всю полную историю проекта, а лишь часть, задав начальное и конечное положение.

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

Недостатки:

1. Недостаточно аналитической информации. Майкл Огава, автор Code Swarm, написал: «Code Swarm очень хорош. Но многие люди предпочитают более аналитическую концепцию данных - более постоянную».

1.1.3 Github Visualizer

Проект был задуман автором как улучшенная версия Code Swarm, оттого сильно похож на него.

Рисунок 4. Github Visualizer, коммиты

Здесь так же каждая частица это файл. Файлы перемещаются от программиста к программисту исходя из того, кто последний вносит изменения. Минусы такого подхода уже были описаны в обзоре Code Swarm.

В Github Visualizer-е этапы отрисовки регулируются не коммитами, как это обычно бывает в подобных системах, а временем: каждая секунда это один день.

Данная программа визуализирует огромное множество данных о проекте и его разработчиков:

1. Список репозиториев:

Рисунок 5. Github Visualizer, список репозиториев

? Круг - репозиторий;

? Возраста репозитория определяет размер круга;

? Дата последнего коммита влияет на прозрачность;

? Цвета определяются основным языков программирования в проекте, от этого зависит разбивка репозиториев на группы;

? Информация по языкам всех репозиториев представлена на гистограмме.

2. График истории последних n коммитов:



Рисунок 6. Github Visualizer, график n коммитов

? X содержит даты коммитов;

? Дуги показывают удаленные, модифицированные и добавленные файлы;

3. Диаграмма участников с активностью каждого:

Рисунок 7. Github Visualizer, диаграмма активности

1.2 Обзор методов визуализации графов

1.2.1 Gephi

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

Рисунок 8. Gephi

Gephi представлен в виде GUI приложения. Он содержит самые основные укладки (- алгоритмы сопоставления вершин графа с координатами плоскости или пространства), поэтому часто применяется в задачах с большими графами.



Рисунок 9. Gephi, 173 тыс. вершин.

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

Force Atlas 2

Одной из его ключевых функций Gephi является возможность отображать процесс локализации с целью преобразования сети в карту, а ForceAtlas2 является алгоритмом компоновки по умолчанию. Он разработан командой как универсальное решение для самых популярных сетей пользователей Gephi (без масштабирования, от 10 до 10000 узлов).

ForceAtlas2 - это силовая схема, близкая к другим алгоритмам, используемым для пространственного размещения сети. Алгоритм имеет много хорошей обратной связи и разработан для предоставления множество возможностей через его параметризацию. Алгоритм представлен в виде силовой - направленной (Force-directed) компоновки: имитируется физическая система графа. Заряженные узлы отталкиваются друг от друга, а ребра являются пружинам. Благодаря этим силам создается движение, которое впоследствии приводит систему к состоянию баланса.

1.2.2 TouchGraph Google Browser

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

На нем основано одно из приложений Touchgraph Facebook Browser, благодаря которому пользователи известной социальной сети могут получить список своих друзей и рекурсивно оценивать отношения между ними и их друзьями, друзьями друзей и т.д. Сервис имеет красивый интерактивный интерфейс, но он имеет серьезные проблемы с производительностью.

Рисунок 10. Touchgraph Facebook Browser

Приложение Friendster также использует TouchGraph движок. Оно визуализирует связи между пользователями, удобно использовать для определения “цепочки рукопожатий”.



Рисунок 11. Friendster

Выводы по главе

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

Глава 2. Архитектура, требования к системе и выбор инструментов

2.1 Требования к системе

Выдвинутые требования базируются на основе шаблона спецификаций требований Software requirements specification из стандарта ISO / IEC / IEEE 29148-2011.

2.1.1 Функциональные требования

1. Система должна уметь получать доступ к Github API и уметь взаимодействовать с ним.

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

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

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

5. Система должна отображать информацию в виде графа:

_ Кластеры должны быть ярко выраженными;

_ Вершины должны быть равномерно распределены;

_ Ребра по возможности должны быть непересекающимися;

_ Система постепенно должна приходить в состояние равновесия - должна быть сбалансирована.

_ Граф должен изменяться динамически.online

2.1.2 Требования к удобству и простоте использования

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

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

3. Должна быть пользовательская документация с инструкциями по установке и использованию, а также со всей спецификацией системы.

2.1.3 Ограничения проектирования

1. Операционные системы: Linux Ubuntu 18.04;

2. Языки: C (11), Go (1.14);

3. Дополнительные библиотеки:

? Общие:

_ Protobuf (3.12.0)

? Go:

_ Protobuf (1.4.2)

_ Go-git (5.0.0)

_ Go-diff (1.1.0)

_ Logrus (1.6.0)

_ Cobra (1.0.0)

? C:

_ SDL (2.0.12)

_ Protobuf-c (1.3.3)

2.2 Архитектура

Приложение состоит из двух основных частей:

1. Первая часть отвечает за работу с системой контроля версий. В ней происходит:

_ Чтение и обработка конфигурационного файла с параметрами пользователя;

_ Получение доступа к Github API с полученными параметрами;

_ Обработка данных репозитория и всех его коммитов;

_ Проверка на качество каждого коммита - подсчет ошибок при помощи линтеров;

_ Сохранение полученных результатов;

_ Запуск анимации;

_ Удаление всех временных файлов, созданных за время работы программы.

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

_ Обновление объектов графа;

_ Балансировка графа;

_ Масштабирование;

_ Отображение.

2.3 Используемые языки программирования

Выбор языка программирования, на котором будет написан весь продукт, один из основных и главных моментов при старте проекта. Бывает не легко сделать этот выбор, и к нему нужно подходить ответственно. Важно отметить, что сфера IT развивается очень стремительно и в ней нет места для передышки: новые языки программирования и новые стандарты существующих появляются с завидной частотой в мире информационных технологий. Разработчики не перестают искать новые подходы к разработке для поиска более простого и элегантного решения, которое отвечает их потребностям. В данной работе было предложено остановиться на двух: C и GoLang.

Таблица 1. Языки программирования

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

GoLang (также известный как Go) достаточно новый язык программирования, впервые был представлен в ноябре 2009 года. Как утверждают создатели, Go был разработан как замена C ++ и Java, взяв от них все самое лучшее. Он имеет небольшой, концептуально чистый и простой в освоении синтаксис. Поэтому каждый разработчик, знакомый с C / C ++, может легко освоить GoLang. Более того, Go - это кроссплатформенный язык. Разработчик может работать на одной платформе (OS-X, Linux или Windows) и компилировать код для любой операционной системы. Неудивительно, что многие ведущие компании используют Golang для разработки программного обеспечения (например, Google, YouTube, Uber, Adobe, BBC и т. д.).

Индекс TIOBE (TIOBE programming community index) показал, что C стал языком программирования года в прошедшем 2019 году, он показал рост на 2,4% по сравнению с 2018 г.

C часто применяется в системах, в которых важна максимальная производительность. Кроме того, язык C значительно проще С++ и благодаря отсутствию в нем многих практик, таких как ООП, метапрограммирование и прочих, в небольших проектах использование С++ неоправданно и ведет к усложнению понимания кода другими людьми. Благодаря своей прямолинейной простоте язык С намного более читаем. Главным недостатком С является отсутствие такой же обширной стандартной библиотеки, как в С++, что зачастую заставляет использовать сторонние библиотеки или реализовывать часть функционала STL самостоятельно. Тем не менее, в Git Stories выбор языка С оправдался, так как не было замечено никакой необходимости в STL и код получился максимально простым.

2.4 Используемые библиотеки

По архитектуре программа разделена на 2 части, для передачи данных между ними используется библиотека Protobuf от компании Google. Данная библиотека реализует Protocol Buffers - независимый от языка и платформы, расширяемый механизм для сериализации/десереализации. Пользователь определяет структуру данных в специальном формате. А затем с помощью данного инструмента генерирует код в разных поддерживаемых языках программирования (Java, Python, Objective-C, C++, Dart, Go, Ruby, C#), чтобы легко записывать и считывать данные с этой структурой, используя различные языки. C официально не поддерживается, но есть отдельная библиотека с C поддержкой.

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

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

2.4.1 С

SDL

Функционал рендера в Git Stories сводится к отрисовке окружностей на экране. Таким образом использование сложных библиотек рендеринга, таких как opengl и vulkan не оправданы.

Библиотека SDL напротив очень проста. Однако в стандартном API SDL нет отрисовки окружностей. Для этих целей существует отдельная библиотека SDL gfx, которая позволяет отрисовывать некоторые примитивы. В Git Stories используются обе эти библиотеки.

Кроме прочего, SDL использует OpenGL, что позволяет использовать hardware rendering. И оставляет возможность для написания своих шейдеров, если это когда-либо понадобится.

Таким образом, SDL используется в основном из-за того, что это крайне простая библиотека, а использование чего-то более сложного не оправдано.

Protobuf-c

Официально в protobuf C не поддерживается сообществом гугла, но, к счастью, есть сторонняя библиотека, которая реализует парсер Google Protocol Buffers для C. Она включает в себя libprotobuf-c, чистую C библиотеку, реализующую кодирование и декодирование protobuf, и protoc-c, генератор кода, преобразующий *.proto файлы.

2.4.1 GoLang

GoLang имеет хорошую базовую стандартную библиотеку, которая удовлетворяет все основные потребности разработчиков. Go практически не требует сторонних библиотек для многих вещей, таких как манипуляции со строками, файловый и сетевой ввод-вывод, тестирование, HTTP-серверы и многое другое. Однако, в разработке данного проекта все-таки появилась необходимость в использовании некоторых дополнительных модулей.

Protobuf

Модуль содержащий API для Go для протоколов сериализации компании Google.

Go-git

Расширяемая библиотека реализации git, написанная на чистом Go. Есть возможность использования для манипулирования git репозиториями на низком уровне или высоком уровне с помощью идиоматического API Go. Библиотека также поддерживает несколько типов хранилищ, таких как файловые системы в памяти или пользовательские реализации, благодаря интерфейсу Storer. Модуль go-git используется в Git Stories для получения доступа к Git API.

Go-diff

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

? Сравнение двух текстов и нахождение их различия;

? Выполнение сопоставления текстов;

? Применение патчев к тексту.

Данный модуль используется для сравнения двух коммитов и вычисления по ним измененных, новых добавленных и удаленных файлов.

Logrus

Модуль представляет структурированную систему логирования для Go, API полностью совместим со стандартной библиотекой логирования.

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

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

Cobra

Библиотека Cobra предоставляет простой интерфейс для создания мощных современных CLI (Command Line Interface) интерфейсных приложений, похожих на инструменты git и go. Многие популярные широко используемые проекты написанные на Go были созданы с использованием Cobra, например: Kubernetes, Hugo, Docker и другие.

Кобра построена на структуре команд, аргументов и флагов:

? Команды (Command) представляют собой действия;

? Аргументы (Args) - значения для действий;

? Флаги (Flags) являются модификаторами для действий.

Базовая структура похожа на простое предложение:

? APPNAME Command Args --Flags

? APPNAME Command --Flags Args

Выводы по главе

Во второй главе были сформулированы требования к системе, следуя стандарту ISO / IEC / IEEE 29148-2011. Кроме того, была описана архитектура приложения Git Stories, было уделено место выбранным инструментам разработки, были кратко описаны используемые языки программирования и библиотеки, а также рассмотрены их преимущества и недостатки. Следующая глава будет посвящена более подробным деталям реализации.

Глава 3. Особенности реализации системы

3.1 Git API

Основной частью Git Stories является обработка коммитов. Стороннее приложение может получить информацию о коммитах и репозиториях путем доступа к Git API. Для этого есть удобная библиотека для GoLang - go-git. Go-git является не только библиотекой, но и своеобразной заменой гита. Модуль полностью совместим с гит, в нем поддерживается большинство основных операции гита. Для получения информации с репозитория нам, во-первых, нужно авторизоваться, для этого требуется информация о пользователе гита: имя пользователя и пароль или персональный токен. Для авторизации используется BasicAuth структура, которая представляет базовую HTTP аутентификацию.

Рисунок 12. Структура http аутентификации

После авторизации идет подключение к самому репозиторию. Существует несколько вариантов подключения:

? по унифицированному указателю ресурса (англ. url - Uniform Resource Locator);

? по директории, в которой лежит уже заранее склонированный проект.

В Git Stories на разных этапах программы применяются оба подхода.

Всю необходимую для работы информацию, пользователь передает в специальном конфигурационном файле. Файл имеет json (англ. JavaScript Object Notation) структуру. Такой формат был выбран не случайно, так как он является легко читаемым и понимаемым для людей, и в то же время он легко воспроизводится машинами. В стандартной библиотеке Go есть модуль для работы с таким форматом данных.

Рисунок 13. Пример входного файла

Файл содержит:

? информацию о гит пользователе:

_ персональный токен или пароль;

_ имя пользователя - владельца репозитория;

_ название репозитория;

? информацию о линтерах, которыми должны проверятся все коммиты, их может быть несколько, каждый из них включает в себя:

_ имя линтера;

_ пользовательские параметры для запуска линтера;

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

Исходя из информации о линтерах, которые предоставил пользователь, в режиме выполнения программы генерируются экземпляры объектов - линтеров.

После того как был получен доступ к репозиторию, программа клонирует его во временную сгенерированную папку.

Путем обращения к Git API, Git Stories получает информацию о всех коммитах. Затем идет итерация по всем полученным коммитам, начиная с первого. Для каждого коммита запускаются линтеры, путем запуска внешних команд из под go проекта. В этом помогает модуль os/exec из стандартной GoLang библиотеки. В процессе запуска линтеров обрабатываются потоки вывода данных и диагностических сообщений (stdout и stderr). По заданному шаблону вычисляется результат каждого линтера. Затем, исходя из заданного пользователем порогового значения, вычисляется результат в процентном соотношении от заданного порога. Итоговый результат считается как среднее значение всех линтеров.

Кроме этого каждый коммит, исключая первый, сравнивается специальными алгоритмами, содержащимися в модуле go-diff, с предшествующим коммитом, чтобы вычислить, какие файлы были изменены, удалены или добавлены. Вся эта полученная информация, плюс итоговый результат линтеров и плюс имя автора коммита сохраняются в некоторую структуру, которая в последствии сереализуется в бинарный формат модулем protobuf и передается на отрисовку.

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

3.2 Визуализации дерева файлов

3.2.1 Cиловая схема

Важнейшей частью Git Stories является визуализация дерева файлов, так как это именно та часть, которую видит пользователь приложения. Дерево файлов в Git Stories представлено структурами GS_Folder и GS_File, где одна папка может содержать несколько файлов или других папок. У файлов и папок есть имя, поэтому существует возможность поиска узла с файлом или папкой от корня дерева, по полному имени.

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

Так как Git Stories предназначен в первую очередь для отображения изменений над деревом файлов, то он должен поддерживать динамическое обновление дерева файлов и динамическую отрисовку изменений, при чем, это должно выглядеть естественно для пользователя.

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

Этого удалось достичь путем использования force-based алгоритма визуализации графов. Его идея состоит в том, что для того, чтобы найти координаты объектов в следующий момент времени в графе симулируется физическая система, в которой в каждом узле графа находится заряд, а между всеми парами связанных между собой узлов находится пружина. Таким образом, в каждый момент времени на любую вершину действует сила Кулона и сила упругости пружины (закон Гука), считается равнодействующая сила.

На рисунке ниже, показана система из трех вершин. Черными линиями нарисованы пружины между папкой и ее файлами. Красными векторами показана сила упругости пружины, а синими - сила кулона.

Рисунок 14. Направление сил объектов

Для симуляции физики каждому объекту, кроме всего прочего, были присвоены масса и вектор скорости. Таким образом, зная массу и посчитав результирующую силу, действующую на объект, можно вычислить его ускорение.

А зная ускорение, время одного тика и текущую скорость, можно вычислить новую скорость.

Однако, при таком подходе система может оказаться неустойчивой и узлы будут хаотично двигаться и никогда не придут в состояние покоя. Чтобы это решить, каждую итерацию симуляции, скорость объекта умножается на константу, меньше единицы. Таким образом, колебания постепенно затухают и система приходит в состояние покоя.

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

Рисунок 15. Добавление обновления от второго коммита, две близкие ветки

Рисунок 16. Баланс двух коммитов



Рисунок 17. Полный баланс всей системы после завершения добавления всех коммитов

3.2.2 Масштабирование и рендеринг

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

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

Коэффициент 2 нужен так полученное расстояние нужно отложить с обеих сторон от середины.

SDL поддерживает масштабирование, но не поддерживает перемещение центра рендера. Таким образом, после масштабирования рендер происходит в левом верхнем углу экрана и все точки туда съезжают. Чтобы этого избежать, во время масштабирования также считается вектор между старой и новой позицией центра и при отрисовке, к координатам всех объектов прибавляется этот вектор.

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

Таким образом, отрисовка коммитов происходит следующим образом:

1. Фиксируется временной интервал одной итерации физики

2. Фиксируется временной интервал за который будут добавляться новые файлы

3. В цикле выполняется следующие действия:

_ Если пришло время добавлять файлы, считывается следующий коммит и добавляется в дерево

_ Если пришло время итерации физики, произвести итерацию физики

_ Если пришло время итерации цвета, произвести интерполярное обновление цвета

_ Каждую итерацию производится рендер следующего кадра

_ Каждую итерацию производится интерполяция изменения масштаба и цвета элементов

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

Все методы, которые могут завершиться с ошибкой возвращают объект Status. В отличие от используемого в языке C метода обработки ошибок путем возвращения числа, которое в зависимости от значения может трактоваться по разному, объект Status также хранит в себе сообщение об ошибки. Это позволяет изменять сообщение об ошибке в месте ее возврата в зависимости от контекста, например добавлять в сообщение название файла, который не удалось найти.

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

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

Чтобы избежать проблем с утечками памяти git stories поддерживает компиляцию с адрес санитайзером (address sanitizer), что позволяет найти большинство утечек за достаточно короткое время.

Опции компиляции -Wall -Werror не дают программе компилироваться при любом предупреждении компилятора.

Подобный подход хоть и не дает гарантии отсутствия неожиданного поведения в программе, но по крайней мере сводит шанс его появления к минимуму.

3.2.3 Обновление цветов

C часть программы получает уже полностью посчитанные сформированные данные, результат линтера приходит в процентном соотношении от порогового значения, которое было задано пользователем в специальном конфигурационном файле. Диапазон значения от 0 до 100. 0 - ошибок и предупреждений нет, 100 - количество ошибок равно или превышает значение порога. Диапазоны цветов задаются в RGB формате (RGB или КЗС -- аддитивная цветовая модель с тремя цветовыми компонентами) и варьируются от зеленого до красного. Соответственно, 0 - зеленый (0, 255, 0), 50 - желтый (255, 255, 0), 100 - красный (255, 0, 0). Промежуточные цвета высчитываются в соответствии с процентным содержанием красного и зеленого компонетов, синий всегда равен 0.

Для того, чтобы цвета менялись плавно, применяется интерполирование каждой компоненты. Интерполирование происходит с определенной константной частотой, такой что цвета меняются не слишком быстро для человеческого глаза, и в то же самое время успевают меняться к обновлению коммитов.

3.3 Автоматизация сборки

3.3.1 Go модули и вендоринг

Go имеет встроенную систему управления зависимостями, имеет поддержку модулей. Пакеты (packages) в Go - это логически связанные файлы исходного кода. Модуль представляет собой набор пакетов, хранящихся в проекте с файлом go.mod в его корне. Обычно одному проекту соответствует один модуль, хотя в редких исключениях бывает и больше.

Файл go.mod определяет путь к модулю, который также является путем импорта, используемым для корневого каталога. Также там содержатся все требования к зависимостям - другим модулям, необходимым для успешной сборки. Каждое требование к зависимости записывается в виде пути к модулю и конкретной семантической версии.

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

Единственное, go build по умолчанию не строит зависимости из каталога vendor, игнорирует их, поэтому следует явно указывать go build -mod vendor.

3.3.2 Cmake и make

Для сборки проекта используется программа cmake. Эта программа автоматически генерирует скрипты для сборки программы в зависимости от окружения пользователя.

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

Одним из главных достоинств cmake'а является то, что он очень хорошо кастомизируется и позволяет выстраивать сложные взаимосвязи между зависимостями, которые собирает.

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

Так как проект состоит из двух частей, написанных на разных языках в cmake был добавлены таргеты собирающие C и Go части. Кроме того, проект использует protobuf, поэтому так же был написан таргет генерирующий посредством protobuf'а файлы исходного кода для работы со структурой данных, описанной в /Git Stories/protobuf/config.proto. Эта структура данных используется для передачи информации между двумя частями проекта.

Для того, чтобы на этапе компиляции отлавливать большинство ошибок в коде, используются флаги -Wall -Werror. Но эти флаги не должны применяться на завендореную стороннюю библиотеку SDL gfx. Поэтому эта библиотека собирается в отдельном таргете и впоследствии статически линкуется к Git Stories.

Чтобы обеспечить возможность собирать проект на разных платформах, был позаимствован и немного изменен модуль cmake'а FindSDL.cmake. В нем описана логика поиска библиотеки SDL на разных платформах.

Выводы по главе

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

Заключение

Основной целью данной работы является разработка инструмента визуализации истории для системы контроля версий Git.

Для выполнения поставленной задачи были сформированы и выполнены несколько шагов:

? Был проведен анализ существующих инструментов при решении задачи визуализации систем контроля версий.

? Были рассмотрены самые известные и широко популярные подходы к визуализации структурированных данных.

? В ходе анализа существующих программ и приложений был выявлен общий недостаток всех визуализаторов. Таким образом, были сформированы требования к новому инструменту Git Stories, в основу которых легло исправление выявленного недостатка.

? Была разработана архитектура приложения.

? Были выбраны инструменты разработки: языки программирования и библиотеки.

? Были реализованы все компоненты системы.

Таким образом, был разработан новый инструмент визуализации Git Stories. Отличительной его особенностью является то, программа проверяет коммиты линтерами, считает итоговый результат линтеров и исходя из него задается цвет для отображения дерева файлов, что позволяет пользователям увидеть качество кода на каждом этапе проекта. Цвет динамически изменяется, что помогает зрительно отследить колебания качества кода на протяжении всего проекта.

Дальнейшие пути развития

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

Также стоит отметить улучшение визуализации со стороны дизайна, который сейчас значительно уступает конкурентам.

Список литературы

[1] Bar, M., Open Source Development with CVS 3RD EDITION / M. Bar, K. Fogel - Paraglyph Press, 2003.

[2] Barnes, J. A hierarchical o(n log n) force-calculation algorithm / J. Barnes, P. Hut - 1986

[3] Cui, W. Geometry-Based Edge Clustering for Graph Visualization / W. Cui, H. Zhou, Y. Qu, P. C. Wong, X. Li - 2008

[4] FLOWINGDATA, Software evolution storylines [Электронный ресурс] - https://flowingdata.com/2010/10/12/software-evolution-storylines/, 2010

[5] Git API V3 [Электронный ресурс] - https://developer.github.com/v3/

[6] Go [Электронный ресурс] - https://golang.org/

[7] Jacomy, M. ForceAtlas2, a Continuous Graph Layout Algorithm for Handy Network Visualization Designed for the Gephi Software / M. Jacomy, S. Heymann, T. Venturini, M. Bastian - 2014.

[8] Nies, T. D. Git2PROV: Exposing Version Control System Content as W3C PROV / T. D. Nies, P. Groth, S. Magliacane, E. Mannens, S. Coppens, R. Verborgh, R. W. Walle - 2013.

[9] Noack, A. Energy models for graph clustering / A. Noack - 2007

[10] Rochkind, M. The source code control system. Software Engineering / M. Rochkind - 1975.

[11] Sink, E. Version Control by Example / E. Sink- 2011

[12] Wu, X. Visualization of Version Control Information / X. Wu- 2003

[13] Галямова, О.Н. Визуализация и анализ связей пользователей социальных сетей / О. Н. Галямова - 2017.

[14] Домнин, Л. Н. Элементы теории графов / Л. Н. Домнин - 2007

[15] Записки программиста, Некоторые тонкости управления зависимостями Go [Электронный ресурс] - https://eax.me/go-mod/

[16] Хабр, Введение в систему модулей Go [Электронный ресурс] - https://habr.com/ru/post/421411/

Приложения

1. Github

С исходным кодом можно ознакомиться по ссылке:

https://github.com/bubblesupreme/git-stories

2. Инструкции по запуску

1. Установить любой компилятор с поддержкой C 11 стандарта

2. Установить компилятор для Go:

_ https://golang.org/doc/install

3. Установить SDL:

_ https://wiki.libsdl.org/Installation

4. Установить protobuf:

_ https://github.com/protocolbuffers/protobuf/blob/master/src/README.md

5. Установить protobuf-c:

_ https://github.com/protobuf-c/protobuf-c/wiki#compilation-and-installation

6. git clone https://github.com/bubblesupreme/git-stories.git

7. mkdir build && cd build

8. cmake ..

9. make

10. поправить конфиг ../examples/parameters.json

11. ./git_stories ../examples/parameters.json

Размещено на Allbest.ru

...