ПОЛУЧЕНИЕ ТИПОВ ДАННЫХ В ЯЗЫКАХ С ДИНАМИЧЕСКОЙ ТИПИЗАЦИЕЙ ДЛЯ СТАТИЧЕСКОГО АНАЛИЗА ИСХОДНОГО КОДА С ПОМОЩЬЮ УНИВЕРСАЛЬНОГО КЛАССОВОГО ПРЕДСТАВЛЕНИЯ
Аннотация и ключевые слова
Аннотация (русский):
Предлагается подход, позволяющий получить сведения о типах полей классов для объектно-ориентированных языков программирования с динамической типизацией, где эти сведения явно не указаны. В качестве целевого языка выбран Python. Это необходимо для расширения универсального классового промежуточного представления исходного кода. Используя данные о типах, можно будет выполнять более эффективный анализ, например получение связей агрегирования между классами. Для получения типов полей предлагается подход «утиной типизации», использующийся в Python во время исполнения. Для обоснования этого подхода предложена математическая модель, которая описывает типизацию, не накладывая ограничений на конкретный алгоритм поиска «кандидатов» в типы исследуемых полей. Предложена методика тестирования алгоритма на основе динамического анализа, позволяющая оценить его эффективность. Реализованный алгоритм вместе с методикой были проверены на ведущих крупных Python-проектах с открытым исходным кодом.

Ключевые слова:
статический анализ, динамическая типизация, динамический анализ, объектно-ориентированное программирование
Текст
Введение Важную роль в разработке программного обеспечения (ПО) играет статический анализ исходного кода. Для более эффективного анализа было предложено универсальное классовое представление [1]. Это представление было бы неполным без введения в него типов полей и методов классов [2]. В языках со статической типизацией, таких как Java или C++, типы указываются в коде. Для языков с динамической типизацией (Python) из кода такую информацию получить невозможно. Получение таких сведений является важной задачей, т. к. они позволяют создать инструментарий для получения связей агрегации [3]. В статье предлагается методика на основе статического анализа, позволяющая определять типы данных до исполнения, рассматривается связанная разработка из проекта PyLint [4]. Отношение агрегирования (агрегация) Отношением ассоциации между двумя классами называют структурное отношение, показывающее, что объекты одного типа неким образом связаны с объектами другого типа [3]. Отношение (связь) агрегирования между двумя классами – это особый вид ассоциации, демонстрирующий отношение «часть – целое». Он показывает, что внутри одного класса содержатся поля, в которых хранится объект, тип которого является другим классом. Под агрегирующим классом будем понимать класс, представляющий в связи агрегации целое. Под агрегируемым классом будем понимать класс, представляющий в связи агрегации часть целого. При агрегации на рис. 1 агрегируемый класс B входит в состав агрегирующего класса A как его поле. Рис. 1. Пример связи агрегации Для диаграммы классов проекта интересными являются только внутренние связи агрегации – связи между классами, определенными в проекте. Классы, не реализованные в проекте, но используемые в нем (например, системные или классы из внешних библиотек), на диаграмме классов проекта не изображаются. Указать агрегацию, связанную с ними, на диаграмме классов проекта невозможно. Таким образом, в рамках анализа интересна только внутрипроектная агрегация. Далее, для обозначения такого типа агрегации, будем использовать обозначение i-агрегация. Агрегирующий и агрегируемый классы, входящие в такую связь агрегации, будем называть соответственно i-агрегирующим и i-агрегируемым. Особенности статического анализа языка программирования Python Python является языком программирования с динамической типизацией [5, 6]. Python является объектно-ориентированным языком программирования. Но в отличие от многих объектно-ориентированных языков, в Python границы использования объекта определяются его текущим набором методов и полей, в противоположность наследованию от определённого класса. Подход, используемый в Python, называется термином «утиная типизация». Название термина пошло от английского «duck test» («тест на утку»), который в оригинале звучит как «If it looks like a duck, swims like a duck and quacks like a duck, then it probably is a duck» («Если это выглядит как утка, плавает как утка и крякает как утка, то, вероятно, это утка») [7]. В листинге 1 функция parse_node() принимает несколько параметров, типы параметров в Python не указываются. Обращение к методам параметров в теле функции будет корректно, если у объектов, переданных в качестве параметров, будут эти методы. Это означает, что если у класса объекта visitor определены методы prepare() и visit() (он «ведет себя как утка»), то обращение к ним будет успешным (считается, что «это и есть утка»). Если же у класса объекта не будет определен, например, метод visit(), то интерпретатором будет сгенерировано исключение AttributeError: A instance has no attribute 'visit', если visitor является объектом класса A. Листинг 1. Пример, демонстрирующий утиную типизацию в Python: def parse_node(node, visitor, state): next_state = node.get_next_state(state) visitor.prepare(next_state) visitor.visit(node) Применение подхода «утиной» типизации в Python затрудняет статический анализ классов проекта и получение связей агрегации [3], т. к. типы полей и методов в Python не могут быть получены в явном виде. Однако это необходимо для поддержания универсального представления в актуальном состоянии для всех языков, независимо от типизации, используемой в них (Java, C++, Python). В Python возможность применения того или иного объекта в качестве типа ограничивается набором полей и методов. В качестве него может быть использован любой тип, обладающий этими полями и методами. Однозначно этот набор может быть определен только в момент исполнения программы. Постановка задачи Математическая модель и терминология. Примем ряд обозначений: C – множество всех классов анализируемого проекта; T – множество всех типов данных. Класс проекта является типом данных F – множество всех возможных полей классов; M – множество всех возможных методов классов; – множество полей, имеющихся у классов рассматриваемого проекта ; – множество методов, имеющихся у классов рассматриваемого проекта . Определим отношение , в которое входят все пары «класс – поле, принадлежащее этому классу». является полем класса . Определим отношение , в которое входят все пары «класс – метод, принадлежащий этому классу». является методом класса . Определим отношение , в которое входят все тройки из класса проекта, его поля и типа данных, объект которого может храниться в этом поле. Так как каждая тройка содержит класс и его поле, то пара, образованная этими двумя элементами, входит в множество D. Если поле класса потенциально может быть нескольких типов, то для одних и тех же класса и поля в отношении будет несколько троек. – возможный тип поля f класса c, Определим отношение, в которое входят все тройки из класса проекта, его поля и i-агрегируемого класса для данного поля. Следует отметить, что в каждой тройке находятся по 2 элемента множества C. Это связано с тем, что i-агрегация описывает связи только между классами проекта, а любой класс проекта потенциально может быть i-агрегируем в любой другой, даже в самого себя. Как и в случае с G, пары класса и поля будут входить в множество D. Если поле i-агрегирует несколько классов (в Python такая ситуация вполне допустима), то в отношении I будет несколько троек для одних и тех же класса и поля. – i-агрегируемый класс в поле f класса c, Для того чтобы задача установления i-агрегации была выполнена полностью, необходимо найти все элементы, входящие в отношение . Предлагаемый подход для установления типов в Python на этапе статического анализа. Полное решение задачи установления i-агрегации является задачей полного перебора всех возможных сценариев выполнения программы. Предлагается на основе статического анализа подбирать кандидатов i-агрегируемых классов для полей классов проекта в соответствии с принципами «утиной» типизации. Все описанные в проекте классы проверяются на наличие у них определенного набора полей и методов, которые были определены алгоритмом как характеризующие i-агрегируемый этим полем класс. Под характеристической сигнатурой класса будем понимать пару множеств некоторых возможных полей и некоторых возможных методов. (1) где s – характеристическая сигнатура; FS – множество полей i-агрегируемого класса; MS – множество методов i-агрегируемого класса. Сигнатура s в формуле (1) характеризует некоторый класс, обладающий полями, составляющими множество FS, и методами, составляющими множество MS. Введем множество всех возможных сигнатур классов S: (2) где S – множество всех возможных сигнатур классов. Очевидно, что сигнатура любого класса (пара множеств его полей и методов) является элементом множества S. Назовем утиными полями все те поля классов в анализируемом проекте, для которых выполняется поиск подходящих типов. Под отношением утиных полей DD будем понимать отношение, в которое входят пары «класс – поле класса». Для этих пар делается предположение об i-агрегируемом классе . В отношение DD входят не все пары классов проекта и принадлежащих им полей, т. к. некоторые поля некоторых классов могут быть пропущены при анализе (например, если известно, что они хранят объекты системных или библиотечных классов). Под характеристической сигнатурой утиного поля будем понимать где – характеристическая сигнатура утиного поля; – множество полей i-агрегируемого класса; – множество методов i-агрегируемого класса. Характеристическая сигнатура утиного поля описывает некоторый класс, объект которого потенциально может храниться в этом поле. Следует отметить, что это описание может вообще не соответствовать никакому классу проекта (ни один класс не имеет такого набора полей и методов), это лишь пара множеств полей и методов, которые алгоритм подобрал на основании статического анализа как потенциально характеризующие i-агрегируемый класс. Предлагаемый алгоритм может иметь ложные срабатывания. Определим отношение , собирающее в себе тройки из классов, их утиных полей и сигнатур этих утиных полей. – характеристическая сигнатура утиного поля f класса c, (3) Формула (3) демонстрирует результат работы алгоритма подбора сигнатур утиных полей. В ходе своей работы предлагаемый алгоритм типизации для всех утиных полей классов подбирает не менее одной сигнатуры , что не накладывает дополнительных ограничений на этот алгоритм. Для каждого утиного поля необходимо подобрать кандидатов в i-агрегируемый класс. Определим отношение подобранных алгоритмом утиной типизации i-агрегируемых классов . Оно представляет собой множество всех троек из класса проекта, его поля и класса, подобранного «утиным» алгоритмом в качестве кандидата для данного поля. Аналогично формуле (2) и отношению I, на класс, соответствующий утиному полю, не накладывается никаких ограничений, т. е. это может быть любой класс проекта, даже тот, в котором поле описано. – кандидат в тип поля f класса c, Опишем, как формируется H алгоритмом подбора i-агрегируемых классов на основе отношений X, D и E. Для этого необходимо, чтобы совместно существовали характеристические сигнатуры класса и анализируемого утиного поля: , (4) где – характеристическая сигнатура класса; , (5) где – характеристическая сигнатура анализируемого утиного поля. Для этих сигнатур должно выполняться условие вхождения сигнатуры утиного поля в сигнатуру класса, т. е. множество полей должно включаться в множество полей и множество методов должно включаться в множество методов . (6) Таким образом, используя обозначения формул (4)–(6), можно записать формулу получения отношения H в символьном виде: . (7) Формула (7) определяет условие подбора классов-кандидатов. В качестве кандидатов подбираются те классы, которые содержат все поля и методы из характеристической сигнатуры данного поля. В результате работы алгоритма получается отношение, которое является некоторым приближением к отношению. Важно отметить, что в предложенном алгоритме не заданы какие-либо ограничения на то, каким образом получать отношение X. От этого напрямую зависит, насколько близко будет отношение к отношению, что определяет качество определения i-агрегируемых классов. Была выдвинута гипотеза, что тип утиных полей может быть с некоторой точностью определен на основе статического анализа, с использованием информации о том, к каким полям и методам хранимого в поле объекта происходило обращение. С помощью этой информации может быть сформировано множество сигнатур утиного поля. Эти сигнатуры являются некоторым приближением к наборам полей и методов объекта, хранимого в этом поле, при различных сценариях выполнения программы. Алгоритм формирования множества сигнатур утиных полей представляет отдельное направление в рамках предлагаемой методики. В представляемой реализации используется следующий способ формирования этого множества: 1. Сигнатуры утиных полей строятся только для полей, к которым обращались в методах класса. 2. Множество состоит из одного элемента. 3. В единственную сигнатуру из этого множества входят все поля и методы, к которым происходило обращение в методах класса. Основной предпосылкой для применения такого метода формирования множества сигнатур утиных полей была гипотеза о том, что в качестве поля класса используются объекты классов, являющиеся наследниками некоторого общего суперкласса. В языках со статической типизацией этот суперкласс явным образом указывается как тип поля, и агрегироваться полем могут только объекты суперкласса или унаследованные от него. Самым важным является то, что работа с объектом, хранимым в этом поле, происходит с использованием полей и методов суперкласса. Эта эвристика позволяет рассматривать множество сигнатур утиных полей как множество из одного элемента, включающего поля и методы суперкласса. Благодаря этому можно избежать дополнительного анализа потока управления методов класса, анализируя обращения к полям и методам агрегируемого класса безотносительно к потоку управления. Для демонстрации подхода обратимся к листингу 2. В нем приведен пример класса Documents, из множества утиных полей которого можно составить отношение ={(Documents, _spreadsheet), (Documents, _text)}. Первое поле инициализируется в явном виде, и становится понятно, объект какого класса с ним связан. О поле _text можно судить лишь косвенно, на основе сигнатуры этого утиного поля. У этого поля вызывается 3 метода, и идет обращение к одному полю, поэтому его сигнатура = ({readonly}, {set_author, set_modification_date, write_changes}), при этом ={readonly}, а= {set_author, set_modification_date, write_changes}. Листинг 2. Пример класса, содержащего утиные поля: from doc_types import XlsTable import doc_factory class Documents(object): _spreadsheet = None _text = None def _init_(self): self._spreadsheet = XlsTable() self._text = doc_factory.get_current_doc() def save(self): self._spreadsheet.write() self._text.set_author() self._text.set_modification_date() if(not self._text.readonly): self._text.write_changes() Для определения типа утиного поля _text необходимо среди всех классов проекта найти подходящих кандидатов. Таким кандидатом может быть класс OdtDocument из листинга 3. Множество полей этого класса в соответствии с его сигнатурой ={readonly}, методов – ={set_author, set_modification_date, _update_other, write_changes, delete}. Это удовлетворяет условию соответствия кандидата утиному полю (формула (6)), т. к. для указанного класса = Documents. Листинг 3. Пример класса, являющегося кандидатом в утиное поле. import AbstractDocument from datetime import datetime class OdtDocument(AbstractDocument): readonly = False def _init_(self, readonly): self._set_creation_date(datetime.now()) self.readonly = readonly def set_author(self): self._set_current_author() def set_modification_date(self): self._set_creation_date(datetime.now()) def _update_other(self): self._parent.update() def write_changes(self): self.save_to_disk() self._update_other() def delete(self): self._parent = None Работы, связанные с темой исследований При поиске публикаций по исследуемой нами проблеме мы обнаружили только одну сходную разработку. Это утилита pyreverse из набора утилит статического анализатора Python-кода PyLint [4], которая позволяет строить UML-диаграмму классов Python-проекта. В этой диаграмме для некоторых полей классов указываются типы данных, среди которых могут быть и классы проекта. Установление типов происходит на основе вывода типов [8], представляющего собой попытку установить тип данных из операций присвоения. В качестве недостатков разработки можно отметить некорректную реализацию этого алгоритма. При использовании разработки в существующем виде на некоторых проектах при генерации типов могут возникать ошибки исполнения, не позволяющие получить диаграмму классов. Ошибки происходят как раз на этапе определения типов. В качестве примеров таких проектов можно назвать Scons [9] или Bazaar [10]. В то время, когда эта статья готовилась к печати (март 2013 г.), ошибка не была исправлена. Реализация Общая логика работы. При анализе диаграммы классов проекта используется библиотека logilab-astng [11], позволяющая получать абстрактное синтаксическое дерево исходного кода на Python (AST) [12]. Анализ полей классов на тип данных выполняется в 2 прохода. 1. На первом проходе извлекается информация об обращении к атрибутам утиных полей (строится отношение X) с помощью обхода дерева с использованием шаблона проектирования Visitor [13]. 2. На втором проходе анализируется информация, полученная после первого. Классы проекта проверяются на соответствие с формулой (4). В результате это позволяет получить отношение H. Агрегация типа «многие-к-одному». Помимо простой агрегации, при которой между двумя классами устанавливается связь типа «один-к-одному», агрегация может устанавливать связь типа «один-ко-многим». В этом случае тип поля класса является коллекцией, например списком или словарем. В этом случае необходимо определить тип данной коллекции и тип составляющих ее объектов. Для Python можно выделить 3 основных сложных типа данных: список (List), кортеж (Tuple) и словарь (Dict). Другие сложные типы (например, множества) нашим инструментарием не анализируются. Аналогично анализу «один-к-одному», на основе AST ищутся классы, подходящие под сложный тип. Если сложный тип установлен, то подбираются кандидаты к его элементам на основе обращений к их атрибутам. Ищутся только сложные типы, состоящие из элементов одинакового класса. Этот случай достаточно распространен при использовании сложных типов данных, что позволяет провести поиск агрегируемого типа в связи «один-ко многим» аналогично поиску агрегируемого типа в связи «один-к-одному». Результаты построения универсального представления для различных проектов Для анализа были выбраны несколько наиболее популярных Python-проектов с открытым исходным кодом. Конфигурация системы, на которой выполнялась генерация: OC Archlinux, x86_64, CPU AMD Phenom(tm) II X4 955 Processor, 8 GB RAM. Результаты работы представлены в табл. 1. Таблица 1 Результаты поиска типов полей в различных проектах по предложенной методике Проект Logilab-astng 0.24.1+ logilab-common 0.58.3 PyLint 0.25.1 Bazaar 2.5.1 Twisted 12.3.0 Количество не пустых утиных полей 95 63 1 359 2 077 Количество утиных полей, для которых был подобран хотя бы 1 класс-кандидат 71 32 1 160 1 717 Процент успешного обнаружения 74,7 50,8 85,4 82,7 Общее количество полей в проектах класса 989 447 19 015 15 792 Процент 7,2 7,2 6,1 10,9 Общее количество классов проекта 249 64 3 989 4 175 Количество классов-кандидатов хотя бы для одного утиного поля 216 42 3 445 3 632 Процент 86,7 65,6 86,4 87 Время генерации 8 с 2 с 31 мин и 2 с 35 мин и 32 с Методика исследования полученных результатов После реализации подхода установления типов в Python необходимо проверить результаты, получаемые в промежуточном представлении, т. е. посчитать, насколько получаемое отношение H близко к эталонному I. Такую проверку можно выполнить на основе методики динамического анализа. Предлагается сравнивать результаты статического анализа с отдельными эмпирически выбранными сценариями исполнения программы. Недостатком такого подхода является то, что при конкретном сценарии исполнения некоторые классы проекта могут вообще не использоваться и отследить их жизненный цикл при таком сценарии исполнения невозможно. Это означает, что анализируются не полные H и I, а только некоторые Для реализации динамического анализа программы был использован доработанный стандартный Python-модуль для отладки bdb [14]. Он накапливал информацию о появлении в локальном пространстве имен [6] выполняемого участка кода объектов классов из рассматриваемого проекта. Для таких объектов проводился анализ полей, среди которых искались либо поля, хранящие объекты классов из рассматриваемого проекта, такие случаи фиксировались (это соответствует агрегации типа «один-к-одному»), либо поля типа кортеж, список или словарь (стандартные типы), которые хранили элементы одинакового класса, являющегося классом из рассматриваемого проекта (это соответствует агрегации типа «многие-к-одному»). В ходе разработки также были введены дополнительные эвристики. Далее результаты, являющиеся , накопленные отладчиком, сравнивались с тем, что получилось в представлении, созданном с помощью статического анализа. Для сравнения выбиралась только та часть , которая по множеству пар полей и классов соответствовала . Сценарии тестирования. При динамическом анализе важен был выбор сценария тестирования для конкретного проекта. Анализировались 3 различных проекта. В первую очередь анализу подвергался сам модуль logilab, используемый для работы с ASTNG-деревьями Python-проектов. Сценарием исполнения служил аналогичный запуск утилиты pyreverse из пакета PyLint для статического анализа Python-проектов. При запуске генерировалось дерево ASTNG для проекта lxml и выполнялась обработка для генерации диаграммы классов в виде dot. Было проведено также тестирование проекта PyLint. Сценарием служил стандартный запуск (без каких-либо дополнительных флагов) – анализ проекта на качество кода с обнаружением потенциальных ошибок. В качестве анализируемого проекта также использовался lxml. В качестве сценария тестирования для проекта Bazaar было задействовано копирование публичного Bazaar-репозитория проекта GRUB на локальный компьютер. Результаты исследований Полученные результаты динамического анализа представлены в табл. 2. Таблица 2 Результаты тестирования методики на основе динамического анализа Проект Корректно подобранные простые типы Не подобранные простые типы Корректно подобранные сложные типы Не подобранные сложные типы Успешное выполнение, % PyLint 8 32 0 4 18 Logilab 227 106 16 74 57 Bazaar 69 76 10 17 46 Заключение Таким образом, в ходе исследований была выдвинута гипотеза и построена математическая модель установления типов в языках с динамической типизацией. По этой модели был дополнен генератор универсального классового промежуточного представления. Для тестирования применимости подхода была разработана методика, основывающаяся на динамическом анализе, показавшая, что правильно определяется достаточно большой процент классов. Главным направлением развития является оптимизация методики, т. к. алгоритм работает достаточно медленно на крупных проектах, таких как Twisted и Bazaar. Одной из возможностей является представление классов в виде реляционной базы данных. Важным является также определение типов данных для аргументов методов классов
Список литературы

1. Зубов М. В. Подходы к статическому анализу открытого исходного кода / М. В. Зубов, Е. В. Старцев, А. Н. Пустыгин // Сб. материалов Восьмой Междунар. конф. разработчиков и пользователей свободного программного обеспечения Linux Vacation / Eastern Europe. – Брест: Альтернатива, 2012. – С. 36–40.

2. Зубов М. В. Выделение типов в универсальном классовом представлении для статического анализа исходного кода / М. В. Зубов, Е. В. Старцев, А. Н. Пустыгин // Восьмая конференция «Свободное программное обеспечение в высшей школе»: тез. докл. – М.: Альт-Линукс, 2013. – С. 53–58.

3. Буч Г. Язык UML Руководство пользователя / Г. Буч, Д. Рамбо, А. Джекобсон. – СПБ.: Питер, 2004. – 432 с.

4. PyLint (analyzes Python source code looking for bugs and signs of poor quality): http://www.logilab.org/857.

5. Полсон Л. Разработчики переходят на динамические языки / Л. Полсон: http://www.osp.ru/os/2007 /02/4108153.

6. Лутц М. Изучаем Python / М. Лутц. – М.: Символ-Плюс, 2010. – 1280 с.

7. Duck Typing in Python: http://www.voidspace.org.uk/python/articles/duck_typing.shtml.

8. Вывод типов, типизация – Энциклопедия языков программирования: http://progopedia.ru/typing/type-inference/.

9. SCons: A software construction tool: http://www.scons.org/.

10. Bazaar: http://bazaar.canonical.com/en/.

11. Logilab-astng (Python Abstract Syntax Tree New Generation): http://www.logilab.org/856.

12. Ахо А. Компиляторы: принципы, технологии и инструментарий / А. Ахо, М. Лам, Р. Сети, Д. Ульман. – М.: Вильямс, 2010. – 1184 с.

13. Гамма Э. Приемы объектно-ориентированного проектирования. Паттерны проектирования / Э. Гамма, Р. Хелм, Р. Джонсон, Дж. Влиссидес. – СПБ.: Питер, 2007. – 366 с.

14. Bdb – Debugger framework – Python v2.7.3 documentation: http://docs.python.org/2/library/bdb.html.