A PROTOTYPE OF UNIVERSAL SOFTWARE TOOL FOR BUILDING MACHINE COMMENT AS A CLASS DIAGRAM SOURCE CODE

Abstract


This article describes using of source code intermediate representations for static analysis. It is proposed to extend using of generic and multi-level representations in one common. Software tool prototype that can make and process this kind of representation introduced.

Full Text

Введение. Статический анализ облегчает выполнение типовых задач разработки. Эти задачи могут быть связаны с поиском ошибок, улучшением качества кода, внутренним тестированием [1]. Перспективным направлением является извлечение информации по исходному коду (построение машинных комментариев [2]). Промежуточные представления Промежуточное представление (далее просто «представление») программного текста - это синтаксически и семантически эквивалентный исходному коду набор данных, над которым выполняется анализ [3]. Представление может быть выполнено в виде различных наборов данных. Самый простой и наиболее изученный в области компиляции вариант - абстрактное синтаксическое дерево AST, фактически, это результат синтаксического разбора. Более сложное, обеспечивающее увеличение скорости анализа - реляционная база данных. Однако затраты на получение такого представления растут. Один из наиболее эффективных видов представления - конечный автомат. Помимо AST в компиляции широкое применение нашло представление SSA (Single-State Assignment) и его развитие GSA [4]. Представления, описывающие только один входной язык, будем называть частными, а те, что пригодны для исходного кода на нескольких входных языках, - универсальными. К частным представлениям можно отнести уже упомянутое абстрактное синтаксическое дерево, описывающее исходный текст программы во всех деталях, свойственных конкретному языку программирования. К универсальным представлениям можно отнести SSA и GSA, с той оговоркой, что версии переменных будут описываться в терминах конкретного языка. Использование универсальных представлений сокращает общие затраты при анализе, так как общее количество требуемых функциональных модулей представления и реализации цели анализа для представления снижается. Пусть предполагается выполнение анализа для N исходных текстов, каждый из которых написан на языке высокого уровня, не совпадающим с языком любого из других текстов, и M целей анализа каждого текста. Тогда общее количество независимых функциональных модулей при использовании универсального представления составит N + M. Если предположить, что для выполнения анализа используется хотя бы синтаксическое дерево разбора (или другое частное представление), полученное с помощью транслятора, то отказ от универсального представления приведет к необходимости применить N*M независимых функциональных модулей. Уже для трех языков высокого уровня (например java, python, cpp) и двух целей анализа (например получение диаграммы классов и графа вызовов) появляется выигрыш по количеству не зависимых функциональных модулей в системе на основе универсального представления, так как N + M = 5, а NxM = 6. Из основного достоинства универсального представления следует и недостаток: универсальные представления не позволяют отразить все детали синтаксиса каждого из языков исходного текста программ. Универсальные многоуровневые представления Для выполнения анализа нам вовсе не обязательно иметь полную информацию обо всех деталях исходного текста. Самым простым уровнем является наиболее детализированный. Он полностью соответствует исходному коду. В различных проектах выделяют разное количество уровней. Так, например, в анализаторе PQL предлагается применять три уровня: модель глобального программного дизайна, модель структуры программы, модель детального программного дизайна [5]. А в Bauhaus Project имеется два уровня: низкоуровневый Inter Mediate Language, детализированный до операторов, и Resource Flow Graphs, описывающий архитектуру [6]. Нечто подобное наблюдается и в организации компилятора GCC, в котором используются представления GIMPLE, CFG(Control Flow Graph), RTL, помимо классического AST [7]. Как видно, различные подходы сходятся в том, что есть полностью соответствующее коду представление и описывающее глобальную структуру программы, архитектуру. Между этими двумя крайними уровнями можно выделить дополнительные уровни представлений. С точки зрения анализа основной интерес представляют структурные единицы используемой парадигмы программирования и языка. Например, для объектно-ориентированных языков это может быть представление уровня классов, их иерархии и взаимосвязей (похоже на диаграмму классов UML [8]). Извлекая лучшее из представленных идей классификации представлений, можно сделать вывод, что универсальные представления могут быть эффективны на более высоких уровнях абстракции. Так, например, программная архитектура в целом мало зависит от операторных возможностей конкретного языка. В качестве примера возьмем рассмотренный уровень классового представления. Для всех объектно-ориентированных языков характерны общие черты при работе с классами. Именно они отражены в диаграмме UML, и именно они были рассмотрены. «Инфокоммуникационные технологии» Том 11, № 1, 2013 50 Зубов М.В., Пустыгин А.Н., Старцев Е.В. Описание универсального классового представления Для прототипной реализации были выбраны весьма разные языки: Java и Python, со своими особенностями, предлагаемыми для ООП. Самое главное их отличие в том, что Java - это язык со строгой типизацией данных, а Python - с динамической. Это накладывает некоторые ограничения на получение связей агрегирования и композиции, потому что типы полей в Python определяются на этапе исполнения, а не на этапе компиляции, то есть они не могут быть получены напрямую из исходного кода. Для упрощения получения прототипа откажемся от получения типов и построения связей агрегирования. В Python присутствует множественное наследование, которого нет в Java. В Java есть интерфейсы, которых нет в Python, но в Java есть множественное наследование у интерфейсов, а также класс может реализовывать несколько интерфейсов. В данном случае самым простым решением будет приравнять интерфейсы к классам. Фактически так и есть, интерфейс - это абстрактный класс, который не содержит никаких реализаций. Таким образом, представление будет допускать множественное наследование для всех входных языков, даже для тех, где его нет. Отказываясь от интерфейсов, также приходится отказываться от отношений реализации. В Python^ такое отношение не может быть реализовано средствами языка так, чтобы оно отличалось от отношения обобщения. Однако оно может присутствовать на уровне логики. Для предлагаемого представления удобно использовать древовидные структуры. В качестве формата данных хорошо подойдет XML. В качестве основного тега выступает тег Class, описывающий отдельный класс, в качестве дочерних тегов используются теги: Attr - описывает поля класса, Method - описывает методы класса, Parent - описывает родителей класса. Графическое представление XML-схемы [9] изображено на рис. 1. Полный текст схемы можно получить из git-репозитория [10]. Реализация прототипа Реализованный прототип поддерживает два входных языка программирования - Java и Python. Для Python использовался генератор на основе библиотеки logilab-astng, что позволило сразу получать информацию о классах проекта. Для Java использовался генератор, использующий AST. Дерево разбора получалось из XML-документа, генерируемого доработанным ком пилятором Open JDK. Реализация прототипа выложена в git-репозитории на открытый ресурс GitHub под свободной лицензией. Рис. 1. Графическая XML-схема универсального классового представления По мере реализации генераторов промежуточного представления для других объектно-ориентированных языков можно использовать уже написанные анализаторы, так как они не привязаны непосредственно к исходному тексту, а обрабатывают промежуточное представление Использование построенного прототипа для визуализации иерархии классов Для тестирования предложенного промежуточного представления была получена визуализированная иерархия классов в dot -формате описания графов из пакета Graphviz, так как иерархия наследования может быть представлена в виде направленного графа. Для демонстрации универсальности представления и его полноты, независимо от входного языка, возьмем типовую реализацию шаблона проектирования «Посетитель» [11]. Были написаны две одинаковые по смыслу реализации на Java и Python. Полные тексты примеров доступны в git-репозитории [12]. Графические представления иерархии классов в UML-подобной форме для Python «Инфокоммуникационные технологии» Том 11, № 1, 2013 Зубов М.В., Пустыгин А.Н., Старцев Е.В. 51 на рис. 2, а для Java на рис. 3. Из рис. 2-3 видно, что несмотря на отличие стилей наименования классов и методов в Java и Python, диаграммы идентичны по смыслу. Использование построенного прототипа для анализа иерархии классов Объектная структура программного продукта в соответствии с современными представлениями должна удовлетворять определенным критериям, в том числе правильно построенным линиям наследования от базовых классов. С целью тестирования возможностей построенного прототипа было проверено выделение методов для групп объектов, которые могут быть вынесены в общий суперкласс. Таблица 1. Результаты анализа Python-проектов Проект Всего методов Проблемных методов Django 2079 334 Twisted 8651 1291 Logilab 491 110 Таблица 2. Результаты анализа Java-проектов Проект Всего методов Проблемных методов Javac 2076 397 FindBugs 5538 787 SQuirreL 7798 1324 ClassNode Attrs accept AsslgnmentNode VarlableNode Attrs Attrs name name Methods Methods accept accept X Node Z lineno strPos accept ReflexionModelAnalyser Attrs mapping visit_Class visit_Assignment visit_Variable Verificator Attrs specification visit_Class visit_Assignment visit_Variable Z NodeVisitor Methods visit.Class vlslt_Asslgnment visit Variable Рис. 2. UML-подобная диаграмма классов примера Python com.example.visitors.Analyser com .example.vlsltors.Verlflcator Attrs Attrs mapping specification Methods Methods visitClass visitClass vIsltAsslgnment vIsltAsslgnment visitVariable visitVariable com.example.Visitors.nodeVisitor Methods 5 Z vIsltAsslgnment visitVariable com.exam pie.Visitors. ClassNode Attrs name accept com.exam pie. nod es.AsslgnNode com.example.nodes.VariableNode Attrs Attrs name name Methods Methods accept accept X z com.example.nodes.Node accept Рис. 3. UML-подобная диаграмма классов примера Java «Инфокоммуникационные технологии» Том 11, № 1, 2013 52 Зубов М.В., Пустыгин А.Н., Старцев Е.В. Для анализа были выбраны несколько Python-и Java-проектов. На Python-библиотека для вебразработки Django версии 1.4.1, сетевая библиотека Twisted версии 12.0.0, Python-пакет logilab, который использовался для обработки AST-деревьев (компоненты logilab-astng версии 0.23.1 и logilab-common версии 0.58.0). Проблемными методами названы те, чьи имена совпадают в разных классах, но не унаследованы ими от общего суперкласса. На Java анализировались компилятор javac, из состава OpenJDK v6u20, статический анализатор FindBugs v2.0.1, SQL-клиент SquirreL. Результаты анализа проектов представлены в таблицах 1-2. Выводы В результате проделанного исследования была разработана и описана модель промежуточного представления, позволяющая универсальным инструментом выполнять статический анализ исходного кода Java и Python. Представлен прототип такого инструмента. Для другого языка следует только получить универсальное промежуточное представление по предлагаемому шаблону.

References

  1. Зубов М.В., Пустыгин А.Н., Старцев Е.В. Статический анализ ПО с помощью его промежуточных представлений и технологий с открытым исходным кодом. Львов: Львів, 2012. - С. 165-168.
  2. Пустыгин А.Н., Иванов А.И., Язов Ю.К., Соловьев С.В. Автоматический синтез комментариев к программным кодам: перспективы развития и применения // Программная инженерия. №3, 2012. - С. 30-34.
  3. Зубов М.В., Пустыгин А.Н., Старцев Е.В. Подходы к статическому анализу открытого исходного кода // Открытые технологии: Материалы VIII МК разработчиков и пользователей свободного программного обеспечения Linux Vacation / Eastern Europe 2012. Гродно, июнь 2012. Брест: Альтернатива, 2012. - С. 36-40.
  4. Cook J., Gottlieb D., Greskamp B., Kujoth R. The Formation and Simulation of a «Whole Program» Gated Singular Assignment Program Dependence Graph. Unconventional Computer Architecture Group, Final Report. - 2008. / http://iacoma.cs.uiuc.edu/~greskamp/pdfs/497f pdf.
  5. Jarzabek S. Design of Flexible Static Program Analyzers with PQL // IEEE Transactions on software engineering. Vol. 24. № 3, 1998. -Р. 197-215.
  6. Bauhaus project / mtc.epfl.ch/software-tools/ blast/index-epfl.php
  7. Basic gcc Intermediate Representation Dumps / http://www.cse.iitb.ac.in/~uday/courses/cs324-05/gccProjects/node4.html

Statistics

Views

Abstract - 23

PDF (Russian) - 5

Cited-By


Article Metrics

Metrics Loading ...

Copyright (c) 2013 Zubov M.V., Pustygin A.N., Startsev E.V.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies