Рус Eng Cn Перевести страницу на:  
Please select your language to translate the article


You can just close the window to don't translate
Библиотека
ваш профиль

Вернуться к содержанию

Кибернетика и программирование
Правильная ссылка на статью:

Инструментальное средство автоматизированного рефакторинга UML-диаграмм классов по заданным критериям качества

Дерюгина Ольга Александровна

преподаватель, кафедра управления и моделирования систем, Московский технологический университет (МИРЭА)

119454, Россия, г. Москва, проспект Вернадского, 78

Deryugina Olga

Lecturer, Department of Control and Modeling Systems, Moscow Technological University (MIREA)

119454, Russia, g. Moscow, ul. Prospekt Vernadskogo, 78

o.a.derugina@yandex.ru
Никульчев Евгений Витальевич

доктор технических наук

проректор по научной работе, Московский технологический институт; профессор, Московский технологический университет (МИРЭА)

119334, Россия, г. Москва, Ленинский проспект, 38А

Nikulchev Evgeny

Doctor of Technical Science

Vice-rector for scientific work, Moscow Technological Institute; Professor, Moscow Technological University (MIREA)

119334, Russia, g. Moscow, ul. Leninskii Prospekt, 38A

nikulchev@mail.ru

DOI:

10.7256/2306-4196.2017.1.21934

Дата направления статьи в редакцию:

07-02-2017


Дата публикации:

22-03-2017


Аннотация: В статье раскрываются вопросы, связанные с задачей автоматизированного рефакторинга UML-диаграмм классов, которая важна для разработки инструментальных средств трансформации UML-моделей в рамках подхода MDA. Формулируется формальная постановка задачи автоматизированного рефакторинга UML-диаграмм классов. Предлагается абстрактная структура данных, удобная для анализа и трансформации UML-диаграмм классов. Приводятся алгоритмы поиска элементов диаграммы классов, применение к которым трансформаций «Стратегия» и «Введение интерфейса» снижает значение целевой функции. В качестве примера целевой функции предложена метрика структурной сложности UML-диаграмм классов. В ходе вычислительного эксперимента вычислительная сложность предложенных алгоритмов в зависимости от размеров UML-диаграммы классов определена как O(n). Предложенные алгоритмы легли в основу представленного в статье инструментального средства автоматизированного рефакторинга UML-диаграмм классов UML Refactoring. Данное инструментальное средство позволяет пользователю импортировать UML-диаграммы классов, представленные в XMI-формате, анализировать их (рассчитывать метрики, получать рекомендации по трансформациям), трансформировать, а затем экспортировать в XMI-формат.


Ключевые слова:

UML, UML-диаграммы классов, рефакторинг UML-диаграмм, MDA, проектирование программного обеспечения, архитектура программного обеспечения, MDE, рефакторинг моделей, UML Refactoring, XMI

УДК:

004.4

Abstract: The article is devoted to the task of the automated UML class diagram refactoring, which is important for the development of tools for transforming UML models in the framework of the MDA approach. The authors formulate the problem of the automated UML class diagram refactoring, introduce the abstract UML Map data structure storing hash maps of the UML class diagram elements. This data structure allows analyzing and transforming UML class diagrams in a convenient way. The paper presents algorithms of UML class diagram analysis in order to apply Strategy and Interface Insertion transformations. Computational experiment demonstrated that the computational complexity of these algorithms is O(n). The proposed algorithms became a part of the UML Refactoring Tool, which allows user to import UML class diagrams from XMI format, to analyze and transform it (calculate metrics, receive transformation recommendations) and to export it back to the XMI format.


Keywords:

UML, UML class diagrams, UML class diagram refactoring, MDA, software design, software architecture, MDE, model refactoring, UML Refactoring, XMI

Введение

Концепция MDA [1], предложенная Object Management Group (OMG), предполагает разработку сложной программной системы на высоком уровне абстрагирования – PIM (Platform Independent Model), а затем автоматической генерации одной или нескольких PSM (Platform Specific Model).

Таким образом, группой OMG была предложена исследовательская программа, связанная с вопросами создания, трансформации, анализа, хранения и передачи моделей программных систем. Основными стандартами, предложенными в рамках MDA, являются MOF [2], UML[3], XMI [4] и др.

MOF спецификация, разработана для описания метамоделей языков MDA. В основе MOF лежит подмножество языка UML 2.

XMI специально разработан для обмена моделями между инструментальными средствами.

Как указывается в документе, XMI предоставляет:

  • представление объектов в терминах XML элементов и атрибутов;
  • стандартные механизмы связи объектов в одном файле или между несколькими файлами;
  • валидацию XMI документов с использованием XML схем;
  • идентификацию объектов посредством обращения к ним через ID или UUID.

Синтаксис XMI-документа описан в спецификации при помощи EBNF.

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

Для моделирования системы при помощи UML используются следующие диаграммы:

  • диаграммадеятельности (Activity Diagram);
  • диаграмма классов (Class Diagram);
  • диаграмма коммуникации (Communication Diagram);
  • диаграмма компонентов (Component Diagram);
  • диаграмма составной структуры (Composite Structure Diagram);
  • диаграмма развёртывания (Deployment Diagram);
  • диаграмма общего взаимодействия (Interaction Overview Diagram);
  • диаграмма объектов (Object Diagram);
  • диаграмма пакетов (Package Diagram);
  • диаграмма профилей (Profile Diagram);
  • диаграммасостояний (State Machine Diagram);
  • диаграмма прецедентов (Use Case Diagram).

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

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

На сегодняшний день существует два основных подхода к рефакторингу UML-модели программного обеспечения.

Первый связан с поисковой программной инженерией [5] (SBSE), интерес к которой все возрастает в последнее время. В SBSE задачи программной инженерии формулируются как задачи оптимизации, которые затем решаются поисковыми алгоритмами (ГА, симуляция отжига, алгоритмы роевого интеллекта и т.д.) SBSE используется для решения задачи рефакторинга UML-диаграмм классов в работах [6-11].

К инструментам, разрабатываемым в рамках данного подхода, можно отнести Dearthóir [12], Darwin [8], CODe-Imp [13], Bunch tool [14] и др.

Недостатком подхода является произвольное, зачастую лишенное смысла применение трансформаций к элементам диаграммы классов. Кроме того, авторы используют в том числе и паттерны, применение которых на этапе проектирования вызывает сомнения (например, применение паттерна Адаптер).

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

Цель данной работы — предложить абстрактную структуру данных UMLMap, удобную для анализа и трансформации UML-диаграмм классов; алгоритмы анализа UML-диаграмм классов, необходимые для решения задачи автоматизированного рефакторинга UML-диаграмм классов; а также представить инструментальное средство автоматизированного рефакторинга UML-диаграмм классов UML Refactoring Tool [15].

Формальная постановка задачи автоматизированного рефакторинга

Пусть `d` ­— это UML -диаграмма классов `d={C,I,R}` , где `C` — множество классов `C={x_(0),...c_(k)}` , `I` — множество интерфейсов `I={i_(0),...i_(1)}` , `R` — множество отношений `R={r_(0),...r_(g)}.`

Пусть `c_(i)` ­— это класс `c_(i)={A_(i),M_(i),F_(i)}` , где `A_(i)` — множество атрибутов `A_(i)={a_(0)^(i),a_(1)^(i),...,a_(n)^(i)},` `M_(i)` — множество методов `M_(i)={m_(0)^(i),m_(1)^(i),...,m_(m)^(i)}` , `F_(i)` — множество свойств `F_(i)={st_(i), v_(i),abs_(i),...}, st_(i) in{0,1}` — признак статичности, `v_(i)` — параметр видимости `v_(i) in {public,private,protected}` , `abs_(i)` — признак абстрактности `abs_(i) in {0,1}.`

Пусть `i_(i)` ­— интерфейс, описывающий множество методов `M_(i)={m_(0)^(i),m_(1)^(i),...m_(m)^(i)}.`

Определение 1

Трансформацией UML-диаграммы классов назовём функцию отображения следующего вида:

`t(d,E): d-> d'`

где `E` – множество элементов диаграммы` e_(i) in d, e_(i) in {C,R,I}.`

Определение 2

Трансформация UML-диаграммы классов `t(d,E): d -> d'` является семантически эквивалентной, если :

`S(d)` ~ `S(d')` ,

где ­`S(d)` — значение структурной семантики диаграммы `d` , которое может быть описано следующим образом:

`S_(i)={{c_(1)^(i)={...},c_(2)^(i)={...},...,c_(k)^(i)={...}}, {i_(2)^(i)={...},...i_(l)^(i)={...}},{r_(1)^(i),r_(2)^(i),...,r_(m)^(i)}},`

где `c_(1),...,c_(k) in d_(i)` — классы диаграммы `d_(i)` ;`i_(1),...,i_(l)` — интерфейсы диаграммы `d_(i)` ; `r_(1),...,r_(m) in d_(i)` — отношения диаграммы `d_(i)`.

Тогда задача автоматического рефакторинга может быть сформулирована следующим образом:

Пусть дана UML-диаграмма классов `d` , множество семантически эквивалентных трансформаций `T `и целевая функция `f(d).`

Требуется найти такое множество пар `{t,E}` , что:

`d'=t(d,E), ` `f(d) < 0.`

Абстрактная структура данных UML Map

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

К примеру, сложность поиска класса с xmi:id = “X” в XMIдокументе оценивается как `O(n)` , в то время, как в хеш-таблице, хранящей пары {ключ, значение}, сложность поиска оценивается как `O(1).`

1

Рис. 1. Сокращённая диаграмма классов для абстрактной структуры данных UMLMap

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

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

Алгоритм анализа UML-диаграммы классов для поиска элементов диаграммы для применения трансформации

Трансформация «Стратегия» означает инкапсуляцию нескольких алгоритмов для обеспечения их взаимозаменяемости (см. рис. 2 и рис. 3).

2

Рис. 2. Предпосылки к применению трансформации «Стратегия»

Алгоритм поиска множеств элементов диаграммы `E` , к которым может быть применена трансформация «Стратегия», описывается следующим образом:

1. Для каждого класса диаграммы найти те, у которых есть потомки, и добавить их в хеш-таблицу <Class, List<Class>> `l_(1)={c_(i),{c_(i1),c_(i2),...},...}.`

2. Для каждого класса из `l_(1)` проверить, реализуют ли его потомки какие-либо интерфейсы. Если да — добавить их в хеш-таблицу <Class,List<Class>> `l_(2)={c_(i),{i_(i1),i_(i2),...},...}.`

3. Для каждого класса из `l_(2)` рассчитать `f(d)` . Если `f(d)<0` добавить в список `l_(3) ` = {parent_id, {child_classes_ids}, {interfaces_ids}}.

4. Вернуть `l_(3)` .

3

Рис. 3. Результат применения трансформации «Стратегия»

Для абстрактной структуры данных UML Map алгоритм может быть описан следующим образом:

strategy

График, отображающий зависимость времени работы алгоритма от размера UML-диаграммы классов показан на рис. 4. Время было рассчитано как среднее арифметическое времени, измеренного на 100 запусках алгоритма для UML-диаграмм классов размером 10, 20, 40, 100, 150, 200, 250, 300 классов. Из графика следует, что сложность алгоритма по времени выполнения оценивается `O(n).`

4

Рис. 4. Зависимость времени работы алгоритма анализа для трансформации «Стратегия» от размера UML-диаграммы классов

Алгоритм анализа UML-диаграмм классов для поиска элементов диаграммы для применения трансформации

Трансформация «Введение интерфейса» предполагает создание промежуточного слоя между классами, которые реализуют множество методов `M` и классами, которые вызывают данные методы посредством отношений типа dependency `r_(i)` .

Алгоритм поиска множеств элементов диаграммы `E` , к которым может быть применена трансформация «Введение интерфейса», может быть описан следующим образом:

1. Найти все классы `c_(i) in d` ,которые не реализуют ни одного интерфейса, и добавить их к списку `l_(1)`.

2. Среди классов из списка `l_(1)` найти те `c_(i)` , которые участвуют в отношениях dependency вида: `c_(j) -> c_(i)` и добавить их в список `l(2)` .

3. Для каждого класса `c_(i)` вычислить `f(d)` .

4. Вернуть все `c_(i)` , для которых `f(d)<0` .

Для абстрактной структуры данных UML Map алгоритм может быть описан следующим образом:

interface

График, отображающий зависимость времени работы алгоритма от размера UML-диаграммы классов показан на рис. 5. Время было рассчитано как среднее арифметическое времени, измеренного на 100 запусках алгоритма для UML-диаграмм классов размером 10, 20, 40, 100, 150, 200, 250, 300 классов. Из графика следует, что сложность алгоритма по времени выполнения оценивается `O(n).`

5

Рис. 5. Зависимость времени работы алгоритма анализа для трансформации «Введение интерфейса» от размера UML-диаграммы классов

Структурная сложность UML-диаграмм классов

В качестве примера целевой функции рефакторинга UML-диаграмм классов рассмотрим метрику структурной сложности UML-диаграмм классов `K(d)`:

`K(d)=k_(1)*|C|+k_(2)*|I|+k_(3)*|R|+k_(4)*sum_(i=0)^n|A_(i)|+k_(5)*sum_(i=0)^n|M_(i)|+k_(6)*sum_(j=0)^m|M_(j)'|,`

где `K(d)` структурная сложность диаграммы `d;` `|C|` число классов `c_(i)in d;` `|I|` — число интерфейсов `i_(i) in d` ; `|R|` — число отношений `r_(i) in d`; `A_(i)` — множество атрибутов `a_(j) in c_(i), c_(i) in d`; `M_(i)` — множество методов классов (за исключением методов, которые принадлежат интерфейсам, имплементируемым классами) `m_(i) in c_(i), c_(i) in d`; `M_(j)'` — множество методов интерфейсов `m_(j) in i_(i), i_(i) in d` ; `k_(1), k_(2), k_(3), k_(4), k_(5), k_(6)` — веса для каждой группы элементов диаграммы.

Инструментальное средство автоматизированного рефакторинга UML-диаграмм классов

Для решения задачи автоматизированного рефакторинга UML-диаграмм классов было разработано инструментальное средство UML Refactoring.

Основные функциональные элементы представлены на рис. 6.

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

После открытия файла диаграмма классов представляется в оперативной памяти в форме АСД UMLMap, основанной на хеш-таблицах. Затем OOMCalculator производит расчет объектно-ориентированных метрик и выводит результат на экране. Analyzer производит поиск трансформаций, снижающих значение целевой функции. Выбранная пользователем трансформация применяется к диаграмме классом Transformer. После чего заново производится расчет метрик и поиск трансформаций.

6

Рис. 6. Функциональные элементы программы UMLRefactoring

Пусть дана UMLдиаграмма (см. рис. 7).

7

Рис. 7. UML-диаграмма классов `d_(1)`

Результат анализа диаграммы `d_(1)` показан на рис. 8. В диаграмме 150 классов, 9 интерфейсов, 197 отношений. Значение метрики Diagram Structural Complexity (DSC) = 198.86.

После применения к диаграмме `d_(1)` одной из предложенных трансформация значение метрики DSC становится равно 187.9.

8

Рис. 8. Результат анализа диаграммы `d_(1)` при помощи инструментального средства UML Refactoring Tool

Результат применения трансформации «Стратегия» показан на рис. 9.

9

Рис. 9. Результат применения трансформации «Стратегия» к диаграмме классов `d_(1)`

Заключение

Для удобства трансформации и анализа UML-диаграмм классов в работе предложена абстрактная структура данных UMLMap, хранящая основные элементы UML-диаграмм классов в хеш-таблицах.

Кроме того, сформулированы алгоритмы анализа UML-диаграммы классов для применения трансформаций «Стратегия» и «Введение интерфейса», определяющие те элементы диаграммы, применение трансформаций к которым снижает значение целевой функции `f(d)` .

В ходе вычислительного эксперимента установлено, что вычислительная сложность предложенных алгоритмов оценивается

Кроме того, в работе представлено инструментальное средство автоматизированного рефакторинга UML-диаграмм классов UML Refactoring Tool, позволяющее экспортировать диаграммы классов в программу из XMI-документов, производить расчет основных объектно-ориентированных метрик. Кроме того, пользователю формируется таблица трансформаций, применение которых снижает значение целевой функции. При выборе одной из трансформаций, она автоматически применяется к диаграмме. Существует возможность сохранения диаграмм во внутреннем формате инструментального средства или экспорта их в формат XMI.

Библиография
1. OMG Model Driven Architecture [Электронный ресурс] Режим доступа URL: http://www.omg.org/mda - Свободный.
2. OMG Meta Object Facility Core Specification. Version 2.5.1. [Электронный ресурс] Режим доступа URL: http://www.omg.org/spec/MOF/2.5.1 - Свободный.
3. OMG Unified Modelling Language UML. Version 2.5 [Электронный ресурс] Режим доступа http://www.omg.org/spec/UML/2.5 - Свободный.
4. XML Metadata Interchange (XMI) Specification. Version 2.4.2 [Электронный ресурс] Режим доступа URL: http://www.omg.org/spec/XMI/2.4.2 - Свободный.
5. Harman M., Mansouri S., Zhang Y., Search-based software engineering: Trends, techniques and applications // ACM Computing Surveys. 2012. Vol. 45. No. 1.
6. Amoui M., Mirarab S., Ansari S., Lucas C. A genetic algorithm approach to design evolution using design pattern transformation // International Journal of Information Technology and Intelligent Computing. 2006. Vol. 1. P. 235 – 245.
7. Bowman M., Briand L.C., Labiche Y. Solving the class responsibility assignment problem in object-oriented analysis with multi-objective genetic algorithms // IEEE Transactions on Software Engineering. 2010. Vol. 36. No. 6. P. 817-837.
8. Vathsavayi S., Raiha O., Koskimies K. Tool support for software architecture design with genetic algorithms // 010 Fifth International Conference on Software Engineering Advances (ICSEA). – IEEE CS Publ., 2010. P. 359–366.
9. Lutz R. Evolving good hierarchical decompositions of complex systems // Journal of Systems Architecture. 2001. Vol. 47. P. 613 – 634
10. Simons C., Parmee I. Single and multi-objective genetic operators in object-oriented conceptual software design // Proceedings of the Genetic and Evolutionary Computation Conference (GECCO’07). - ACM, 2007. P. 1957–1958.
11. Deryugina O. Improving the structural quality of UML class diagrams with the genetic algorithm // ITM Web of Conference. 2016. Vol. 6. P. 03003.
12. O’Keeffe M., Cinnéide M.Ó. Towards automated design improvements through combinatorial optimization // Proc.Workshop on Directions in Software Engineering and Environments (WoDiSEE’04), W2S International Conference on Software Engineering. - Edinburgh, 2004. P. 75–82.
13. O'Keeffe M., Cinnéide M. O. Search-based software maintenance // Proceedings of the 10th European Conference on Software Maintenance and Reengineering, 2006. CSMR 2006. – IEEE, 2006. P. 249-260.
14. Mancoridis S., Mitchell B.S., Rorres C., Chen Y., Gansner E.R. Using automatic clustering to produce high-level system organizations of source code // Proc. International Workshop on Program Comprehension (IWPC 98). - USA, 1998. P. 45–53.
15. Nikulchev E., Deryugina O. Model and Criteria for the Automated Refactoring of the UML Class Diagrams // International Journal of Advanced Computer Science and Applications. 2016. Vol. 7. No. 12. P. 76–79.
References
1. OMG Model Driven Architecture [Elektronnyi resurs] Rezhim dostupa URL: http://www.omg.org/mda - Svobodnyi.
2. OMG Meta Object Facility Core Specification. Version 2.5.1. [Elektronnyi resurs] Rezhim dostupa URL: http://www.omg.org/spec/MOF/2.5.1 - Svobodnyi.
3. OMG Unified Modelling Language UML. Version 2.5 [Elektronnyi resurs] Rezhim dostupa http://www.omg.org/spec/UML/2.5 - Svobodnyi.
4. XML Metadata Interchange (XMI) Specification. Version 2.4.2 [Elektronnyi resurs] Rezhim dostupa URL: http://www.omg.org/spec/XMI/2.4.2 - Svobodnyi.
5. Harman M., Mansouri S., Zhang Y., Search-based software engineering: Trends, techniques and applications // ACM Computing Surveys. 2012. Vol. 45. No. 1.
6. Amoui M., Mirarab S., Ansari S., Lucas C. A genetic algorithm approach to design evolution using design pattern transformation // International Journal of Information Technology and Intelligent Computing. 2006. Vol. 1. P. 235 – 245.
7. Bowman M., Briand L.C., Labiche Y. Solving the class responsibility assignment problem in object-oriented analysis with multi-objective genetic algorithms // IEEE Transactions on Software Engineering. 2010. Vol. 36. No. 6. P. 817-837.
8. Vathsavayi S., Raiha O., Koskimies K. Tool support for software architecture design with genetic algorithms // 010 Fifth International Conference on Software Engineering Advances (ICSEA). – IEEE CS Publ., 2010. P. 359–366.
9. Lutz R. Evolving good hierarchical decompositions of complex systems // Journal of Systems Architecture. 2001. Vol. 47. P. 613 – 634
10. Simons C., Parmee I. Single and multi-objective genetic operators in object-oriented conceptual software design // Proceedings of the Genetic and Evolutionary Computation Conference (GECCO’07). - ACM, 2007. P. 1957–1958.
11. Deryugina O. Improving the structural quality of UML class diagrams with the genetic algorithm // ITM Web of Conference. 2016. Vol. 6. P. 03003.
12. O’Keeffe M., Cinnéide M.Ó. Towards automated design improvements through combinatorial optimization // Proc.Workshop on Directions in Software Engineering and Environments (WoDiSEE’04), W2S International Conference on Software Engineering. - Edinburgh, 2004. P. 75–82.
13. O'Keeffe M., Cinnéide M. O. Search-based software maintenance // Proceedings of the 10th European Conference on Software Maintenance and Reengineering, 2006. CSMR 2006. – IEEE, 2006. P. 249-260.
14. Mancoridis S., Mitchell B.S., Rorres C., Chen Y., Gansner E.R. Using automatic clustering to produce high-level system organizations of source code // Proc. International Workshop on Program Comprehension (IWPC 98). - USA, 1998. P. 45–53.
15. Nikulchev E., Deryugina O. Model and Criteria for the Automated Refactoring of the UML Class Diagrams // International Journal of Advanced Computer Science and Applications. 2016. Vol. 7. No. 12. P. 76–79.