Анализ больших массивов исходных текстов программ
Алексей Демаков (demakov@ispras.ru), ИСП РАНАннотация
Ключевые слова
Mining software repositories (MSR), Source code repositories (SCR), code clones detection
Введение
Развитие открытого программного обеспечения и вычислительных мощностей привело к тому, что современным исследователям для изучения и анализа доступен большой объем исходных текстов программ. Репозитории исходных текстов находятся в таких хранилищах программных проектов как GitHub и SourceForge. Кроме текущего состояния в репозитории хранится история изменений исходных текстов. К истории изменений часто привязана дополнительная информация --- информация о задачах, с которыми связаны изменения.
Анализ исходных текстов большого количества программных проектов позволяет выявлять закономерности и связи не только внутри одного проекта, но и между проектами. По истории изменений можно анализировать динамику развития проектов.
Варианты использования
- Поиск совпадающих или похожих фрагментов внутри одного проекта или между проектами.
Результаты внутри проекта могут использоваться для рефакторинга. Результаты заимствований между проектами могут использоваться для проверки лицензионной чистоты кода. - Частота использования различных конструкций языка или библиотечных вызовов. Может использоваться для оценки необходимости поддержки устарвеших версий языковых и библиотечных возможностей. Может использоваться для оценки широты проникновения новых возможностей и востребованности языков и библиотек.
- Динамика разработки программных проектов --- скорость увеличения кодовой базы, связь с количеством задач и ошибок. Сравнение скорости разработки проектов, использующих различные языки программирования.
- Статистическая зависимость метрик исходного кода (например, размера функций) и количества дефектов.
Цели и задачи
Создание любого анализатора больших массивов исходных текстов программ осложняется необхоимостью разработки инфраструктуры поддержки. Эта инфраструктура мало зависит от вида самого анализа и может быть выделена в качестве общей части. Наличие такой инфраструкты заметно снижает трудоемкость разработки каждого отдельного анализатора.
Целью работы является исследование методов анализа больших массивов исходных текстов программ.
Задачи работы:
- Создание платформы, позволяющей разрабатывать различные виды анализаторов больших массивов исходных текстов программ.
- Апробация этой платформы путем разработки нескольких анализаторов.
Работы
- Разработка эскиза архитектуры платформы анализа больших массивов исходных текстов программ, включающего:
* подсистему хранения информации об исходных текстах;
* подключаемые модули сканирования хранилищ программных проектов и создания локальной копии репозиториев исходных текстов;
* подключаемые модули индексирования исходных текстов и сохранения результатов;
* подключаемые модули анализаторов и построения отчетов. - Определение программных интерфейсов необходимых подсистем.
- Реализация подключаемого модуля сканирования хранилищ программных проектов --- например, для GitHub.
- Реализация подсистемы хранения информации об исходных текстах.
- Реализация одного подключаемого модуля индексирования исходных текстов --- например, дайджестов (хэшей) для фрагментов исходных текстов как описано в статье [1].
- Реализация одного подключаемого модуля анализа --- например, для поиска совпадающих дайджестов/последовательностей дайджестов, то есть поиска совпадающих или похожих фрагментов исходных текстов, как описано в статье [1].
- Реализация генератора веб-страниц, содержащих отчет о найденных совпадающих или похожих фрагментах исходных текстов.
Предполагаемый объем программной реализации --- 3000 строк на языке Java.
Компетенции
Для выполнения работы Исполнителю потребуются следующие основные компетенции:
- Разработка архитектуры программных систем --- для разработки архитектуры платформы анализа больших массивов исходных текстов программ.
- Использование сетевых API хранилищ программных проектов --- для получения списка репозиториев и дополнительной информации.
- Использование систем контроля версий (SCM) таких как Git, Mercurial, Subversion --- для получения локальной копии репозитория исходных текстов.
- Использование или разработка анализаторов исходных текстов на различных языках программирования --- для извлечения необходимой информации из исходных текстов. Например, для синтаксического анализа исходных текстов на языке Java может использоваться Eclipse JDT, содержащий возможность построения дерева абстрактного синтаксиса Java.
- Использование хэш-функций и разработка алгоритмов построения дайджестов для фрагментов кода.
- Разработка схем баз данных и запросов --- для хранения и последующего использования информации, извлеченной из исходных текстов.
- Использование языка программирования общего назначения или специализированного языка программирования --- для разработки анализаторов информации, сохраненной в базе данных.
- Использование параллельных вычислений --- для ускорения анализа.
- Использование API (например, командной строки) существующих анализаторов исходных текстов для подключения их к анализу.
- Использование средств построения отчетов или средств создания веб-страниц --- для построения отчетов о результатах анализа.
Литература
- Michel Chilowicz, Etienne Duris and Gilles Roussel. Syntax tree fingerprinting: a foundation for source code similarity detection. DOI: 10.1109/ICPC.2009.5090050 Conference: The 17th IEEE International Conference on Program Comprehension, ICPC 2009, Vancouver, British Columbia, Canada, May 17-19, 2009.
http://igm.univ-mlv.fr/~chilowi/research/syntax_tree_fingerprinting/syntax_tree_fingerprinting_ICPC09.pdf
Весьма популярна задача поиска кода, заимствованного проектом, которую можно обобщить как задачу поиска похожих фрагментов кода. Один из достаточно эффективных методов её решения описан в этой статье.
Метод заключается в сборе цифровых отпечатков для операторов программного кода и поиске совпадающих последовательносей отпечаков. Управлять степенью близости находимых результатов можно изменяя способ формирования отпечатков – делая их более или менее зависимыми от деталей. - Huzefa Kagd, Michael L. Collard and Jonathan I. Maletic. A survey and taxonomy of approaches for mining software repositories in the context of software evolution. JOURNAL OF SOFTWARE MAINTENANCE AND EVOLUTION: RESEARCH AND PRACTICE J. Softw. Maint. Evol.: Res. Pract. 2007; 19:77–131 Published online in Wiley InterScience (www.interscience.wiley.com). DOI: 10.1002/smr.344.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.142.4190&rep=rep1&type=pdf
Список литературы этого обзора насчитывает 106 пунктов. Он охватывает только исследования, изучающие вопросы развития программных проектов (то есть, множество ревизий программного кода и связанной с ним информации одного проекта для различных моментов времени). - R. Dyer, Hoan Anh Nguyen, H. Rajan, T.N. Nguyen. Boa: A language and infrastructure for analyzing ultra-large-scale software repositories. Software Engineering (ICSE), 2013 35th International Conference on; 01/2013.
http://web.cs.iastate.edu/~design/papers/ICSE-13/icse13.pdf
В статье описан языка запросов и необходимая инфраструктура для получения информации из больших репозиториев программных проектов. Это удобный инструмент для проверки различных гипотез, относящихся к анализу больших программных репозиториев. Реализация использует методы параллельной обработки запросов. - Scheidgen M., Fischer J. (2014) Model-Based Mining of Source Code Repositories. In: Amyot D., Fonseca i Casas P., Mussbacher G. (eds) System Analysis and Modeling: Models and Reusability. SAM 2014. Lecture Notes in Computer Science, vol 8769. Springer, Cham
http://www.markus-scheidgen.de/wp-content/uploads/2014/09/ScheidgenFischer_cameraReady.pdf