Algorithms and software tool for building equivalent representations of source codes

Full Text

Задача статического анализа программных систем является одной из традиционных способов улучшения программ [1]. В предшествующих разработках [2] было предложено и реализовано универсальное промежуточное представление (УПП) открытого исходного текста, предназначенное для последующего преобразования, анализа и извлечения информации из исходного кода программ. На основе этого набора данных был построен прототип генератора системы эквивалентных представлений, предназначенных для решения некоторой совокупности задач над исходным текстом. Рассмотренный прототип позволяет получать эквивалентные представления исходного текста путем линейных и нелинейных преобразований его УПП, выполнять анализы над этими представлениями и получать срезы этих представлений [3]. Помимо известных, возможно получение объединенных представлений с заданными общими параметрами среза. Правила построения представлений задаются в конфигурационном файле. Разработанный прототип не является законченным пользовательским продуктом статического анализа, которыми являются соответствующие пакеты и плагины сред разработки (например, Microsoft Visual Studio и IntelliJ IDEA). Однако функциональные возможности прототипа на данный момент покрывают де-факто или в перспективе большинство широко используемых функций статического анализа (анализы потока управления, потока данных, диаграмма классов в различных аспектах). Например, функция поиска использования переменной (или поля объекта) в IntelliJ IDEA уже входит в базовый комплект фильтров прототипа, а функция иерархии вызовов в Visual Studio легко может быть реализована поверх соответствующего представления. В данном прототипе эти функции усилены за счет использования дополнительных правил и сложных условий параметризации выборки: заданием контекста при поиске использования поля объекта можно исключить 90% ненужной информации и оставить, например, только те вхождения, которые лежат в условиях циклов определенного класса. Прототип допускает произвольные объединения известных представлений, которые являются не изученными ранее. Возможность задания своих представлений в прототипе практически не ограничена за счет полного доступа к дереву синтаксического разбора (AST) через УПП и достаточной гибкости правил, формирующих выборку. Это позволяет выполнять специфичные анализы, которым в пакетах статического анализа не нашлось места. Например, в различного рода анализах потока управления учитываются неявные вызовы перегруженных операторов и конструкторов копирования. Пользовательский запрос для описания требуемого анализа (преобразования) Пользователь вводит запрос в инструмент со стандартного ввода. Запрос представляет собой комбинацию доступных в конфигурационном файле фильтров с дополнительными параметрами и правилами их совмещения, а также анализ, выполняемый над полученным представлением. Результатом применения любого фильтра является подмножество элементов УПП. Результатом комбинации двух и более фильтров считается объединение соответствующих подмножеств элементов УПП. Формальный вид запроса: <имя фильтра> [<имя фильтра>] [<условие> [<логический бинарный оператор> <условие>]] Синтаксис условий: <параметр><оператор><значение> <параметр> - параметр фильтра, например, ParentClass - имя родительского класса, ContextClass - имя класса, в контексте которого находится фильтруемый узел УПП. <значение> - значение, с которым сравнивается параметр. Может быть строкой символов или именем другого параметра. <оператор> - оператор сравнения со значением параметра, например, равенство «=» или «!=» - неравенство. <логический бинарный оператор> - бинарный оператор совмещения условий. Может быть: «AND» и «OR». Также условия могут обособляться круглыми скобками. Для проработки возможных вариантов использования инструмента был разработан тестовый набор фильтров и анализов, а также базовый набор параметров для задания срезов. Так, фильтр o_modify_f позволяет получить выборку модифицирующих операций для заданного множества полей. Множество можно задать принадлежностью классу параметр SelfClass, а также через имя поля FieldName. Фильтр o_share_f позволяет найти места в исходном тексте, где поля объектов из заданного множества передаются по ссылке или через указатель. Фильтр ucr выдает диаграмму классов со всеми методами и полям. Задать срез такой диаграммы можно с помощью определения родительского класса ParentClass или самого класса через параметр ContextClass. Множество вызовов в определенном контексте позволяет получить фильтр calls. Контекстом может быть имя вызываемого метода MethodName, контекстный метод ContextMethod, в котором производится вызов, а также же класс определения метода SelfClass. Через фильтры cf и df с указанием желаемого контекста можно получить соответственно поток управления и поток данных. При этом доступна любая комбинация фильтров. Конфигурационный файл программного инструмента Существует в виде текстового XML-файла, формат которого позволяет задавать как линейные, так и нелинейные (со сложными зависимостями) условия фильтрации и трансформации УПП. В корневом теге <analysises> перечисляются фильтры, каждый из которых задается иерархичным набором тегов из множества тегов УПП с указанием правил фильтрации в их атрибутах, и обособляется тегом <analysis> с атрибутом «name», задающим имя фильтра. Перечень основных правил: contexted (bool=true) - если true, узел фильтруется, если в УПП он представлен в контексте такого же родительского узла как в фильтре; если false, то ведется рекурсивный поиск вниз по иерархии дерева документа; strict (bool=false) - если true, то узел выводится только, если он и все дочерние узлы удовлетворили условиям фильтра; если false, то узел выводится, если он и хотя бы один дочерний узел (если такой есть) удовлетворили условиям фильтра; all_in (bool=false) - если true, то, если данный узел не соответствует сложному условию, поиск в данной ветке дерева документа прекращается. Конфигурационный файл [4] считывается при запуске. Проверка тега на соответствие правилам фильтра производится рекурсивным обходом иерархии узлов фильтра по иерархии узлов дерева XML документа. Тестирование Для контроля правильности функционирования инструмента было произведено функциональное тестирование на УПП проекта с открытым исходным кодом pugixml [5] - библиотеке для разбора XML документов. Набор тестов был получен выполнением множества пользовательских запросов, которое было сгенерировано путем комбинирования всех возможных различных пар из перечня доступных фильтров. Из тестового перечня фильтров было получено 136 эквивалентных представлений. В соответствии с поставленными задачами были реализованы некоторые из анализов. 1) Поток управления для конкретного класса и метода. Распространенный вид анализа с дополнительной фильтрацией. Командная строка: cf ContextClass=xml_text AND ContextMethod =as_string Результат в файле cf.xml [4]. 2) Запрос комбинации потока управления и потока данных при тех же параметрах. Данная комбинация позволяет строить анализ потока данных в контексте потока управления [3]. Рис. 1. Диаграмма классов-наследников класса xml_write Командная строка: cf df ContextClass=xml_text AND ContextMethod=as_string Результат в файле dcf.xml [4]. 3) Диаграмма классов, в которую должны попасть только классы-наследники «xml_writer». Командная строка: ucr ParentClass=xml_writer Результат в файле ucr.xml [4] (рис. 1). 4) Поиск модификаций и передачи по ссылке и указателю полей всех объектов заданного типа «xml_attribute_struct», учитывать только вхождения за пределами данного класса. Позволяет отследить явную и неявную модификацию членов класса. В отличие от обычного текстового поиска исключаются вхождения, не принадлежащие заданному классу, но совпадающие по именам; также исключаются вхождения, в которых модификации полей объекта не производятся (чтение или копирование). Результат фильтрации выдает вхождения для всех членов сразу, чего не позволяет получить обычный текстовый поиск. Данный фильтр полезен для отладки, задачи рефакторинга и выявления проблемных точек взаимодействия с классом через поля объектов. Командная строка: modify_f share_f SelfClass=xml_attribute_struct AND ContextClass!=SelfClass Результат в файле modify.xml [4]. Строка исходного текста 3867 в файле «pugixml.cpp» [5] содержит вызов метода «strcpy_insitu», который определен в строке 1526. Первым и вторым аргументом вызова по ссылке передаются два поля («name» и «header») объекта «_attr» заданного типа «xml_attribute_struct». Вызов метода: strcpy_insitu(_attr->name, _attr->header, …); Сам вызов происходит в контексте метода «set_name» принадлежащего классу «xml_attribute». Данный результат соответствует составленному запросу. 5) Поиск вызовов метода с именем «next_sibling» в контексте классов, не являющихся классом определения данного метода. Позволяет осуществлять контроль и рефакторинг точек вызовов заданного метода. Фильтр исключает вхождения, которые текстовый поиск не способен отфильтровать, когда классы не разбиты по отдельным файлам, а именно - вхождения вызовов метода в классе его определения. Командная строка: calls MethodName=next_sibling AND ContextClass!=SelfClass Результат в файле calls.xml [4]. Строка исходного текста 5122 в файле «pugixml.cpp» [5] содержит вызов метода «next_sibling». Вызов находится внутри определения метода «reset», который принадлежит классу «xml_document». Рис. 2. Иллюстрация вызова метода за пределами его класса определения Сам метод «next_sibling» определен в строке 4055 и принадлежит классу «xml_node» (см. рис. 2). Такой результат соответствует составленному запросу. Температурная диаграмма исходного текста для любого эквивалентного представления Температурной диаграммой исходного текста будем считать диаграмму зависимости условного количественного параметра (температуры) от номера строки исходного текста. Пользователь задает вес для выбранных элементов УПП в соответствующем фильтре конфигурационного файла. В соответствии с весом фильтруемого элемента УПП для каждой строки вычисляется ее суммарная температура, которую формируют: - температура основания - вес структуры AST, в которую вложен первый взвешенный элемент строки; - собственная температура строки - суммарный вес всех входящих в нее взвешенных элементов. Результат анализа записывается в XML-файл, формат которого представляет собой последовательность тегов <Line> соответствующих строкам исходного текста с заданной в атрибуте «weight» температурой. Тела методов выделяются блоками <Method>, которые атрибутированы максимальной среди строк метода температурой. Так как имеется возможность произвольного назначения весов каждому фильтруемому элементу УПП, а значит и каждой синтаксической конструкции исходного текста, можно получить большое число разнообразных метрик исходного текста в виде температурных диаграмм. «Температуризация» может быть использована для эквивалентных представлений, например, для построения температурной карты диаграммы классов. В соответствии с поставленными задачами был предложен «температурный» анализ синтаксической перегруженности строк и сложности блоков исходного текста в контексте потока управления. Может быть использован для полуавтоматического поиска участков кода, которые вероятно имеет смысл подвергнуть процессу рефакторинга. Могут быть выявлены потенциально «медленные» участки кода. Методика ранжирования весов тех или иных синтаксических конструкций лежит на операторе. Благодаря тому, что в анализ попадают и перегруженные операторы, которые по смыслу и весу равнозначны методам, оценка сложности исходного кода в данном случае будет более точно соответствовать коду исполняемому. Командная строка: cf_w CT ContextMethod=find_node Результат в файлах ct_ir.xml, ct.xml, ct.html [4]. Строка 514 исходного текста в файле «pugixml.hpp» [5] имеет «температуру» 16 (рис. 3), которая складывается из следующих составляющих: - температура основания - 5, складывается из вложенности в цикл «while» (вес 3, 506 строка), в условный оператор «if» (вес 1, 510 строка) и еще один «if» (вес 1, 511 строка); - cобственная температура строки - 11, складывается из весов конструкций: цикл «while» (3), вызов «next_sibling» (2), неявный вызов «operator!» (2), вызов «parent» (2), неявный вызов «operator=» (2). Наличие операторов «operator!» и «operator=» обусловлено тем, что они перегружены для типа «xml_node», которому принадлежит объект «cur» (см. 504 строка). Рис. 3. Температурная диаграмма фрагмента исходного текста Рис. 4. Дерево разбора 514 строки исходного текста в контексте потока управления Выводы Рассмотренный инструмент позволяет получать линейные и нелинейные эквивалентные представления исходного текста из его УПП, выполнять анализы над этими представлениями и получать срезы этих представлений, а также получать объединения выбранных представлений с заданными общими параметрами среза. Таким образом, появляются поле для исследования ранее не изученных представлений исходных текстов, а также база для сведения к универсальному виду давно известных.

About the authors

Aleksey Anatolevich Kovalevskiy

Chelyabinsk State University

Email: morskoyzmey@gmail.com

Aleksey Nikolaevich Pustygin

Chelyabinsk State University

Email: p2008an@rambler.ru

References

Supplementary files