Variability Mining: Consistent Semiautomatic Detection of Product-Line Features

Оригинал: Christian Kästner, Alexander Dreiling, and Klaus Ostermann, 2013
https://www.cs.cmu.edu/~ckaestne/pdf/tse_fm.pdf

SPLE(SOFTWARE PRODUCT LINE ENGINEERING) является эффективным средством для создания набора связанных продуктов ПО. Варианты продуктов разделены по их отличительным признакам. Разработчики реализовывают линейки продуктов таким образом, что они могут получить продукт для каждой комбинации признаков. Мы предлагаем систему, которая полуавтоматически обнаруживает признаки в коде и извлекает их. Мы называем этот процесс variability mining(добыча изменчивости), поскольку мы вводим изменчивость в линейку продуктов, размещая признаки и делая их переменными.

Variability Mining - процесс выявления особенностей в старом коде и переписывания их в качестве дополнительных(или альтернативных) функций в продуктовой линейке. Процесс состоит из 4 шагов:

1. Специалист моделирует предметную область и описывает соответствующие функции и их отношения в модели изменчивости.
2. Специалист, разработчик, или какой-то инструмент идентифицирует начальные seeds для каждой функции в коде. Seeds
3. Фрагменты кода, которые, непосредственно принадлежат функции.
4. Для каждой функции, разработчики итеративно расширяют начальный код, пока они не посчитают, что функция является последовательной и полной.
5. Разработчики или инструменты переписывают(извлекают) локализованные фрагменты кода, так что варианты c(без) этими(этих) фрагментами(ов) кода работают.
   

Ниже приведена схема процесса Variability Mining:

Ниже описаны характеристики контекста линейки продуктов и соответствующие цели проектирования для подхода Variability Mining:

• Бинарное и постоянное отображение: для данной функции, генератор продуктовой линии автоматически получает соответствующую реализацию путем составления или удаления фрагментов кода, связанных с функциями. Отображение должно быть двоичным в том смысле, что отображение между элементами и фрагментами кода обозначает отношение принадлежности. Отображение является постоянным, т.к. оно является неотъемлемой частью реализации продуктовой линейки.
• Согласованность: при извлечении функции все варианты с и без этой функции должны выполняться корректно.
• Зернистость: необходимо предоставить фрагменты кода на тонком уровне детализации.
• Базовые знания: о том, что одна функция требует другой или что две функции являются взаимоисключающими.

Для представления фрагментов кода и их отношения, мы используем стандартное графическое представление структуры и зависимостей исходного кода.

Обозначим множество всех элементов кода программы E. Между элементами кода введем отношение R ⊆ E×E. Containment отношения описывают иерархическую структуру кода: модуль компиляции содержит объявления импорта и типы, тип содержит поля и методы, а метод содержит операторы. References охватывают вызовы методов, доступ к полям, а также ссылки на типы. Usage охватывают дополнительные отношения, когда два элемента непосредственно не ссылаются друг на друга, но используются вместе.

Мы определяем базовые знания, как набор функций F и отношений между этими функциями, извлеченными из модели изменчивости VM. Нас интересуют два вида отношений:

• Взаимное исключение, M ⊆ F×F, позволяет отбросить фрагменты кода, которые уже принадлежат к взаимоисключающим функциям.
• Импликация, ⇒ ⊆ F×F, позволяет не пересматривать элементы кода, которые уже аннотированы.
  

Аннотации сопоставляют элементы кода признакам (А ⊆ E×F), также может использоваться отрицательная аннотация (N ⊆ E×F) для отмены рекомендации. Для рассмотрения аннотаций между несколькими признаками введем два определения:

• Extent признака f - это множество элементов, для которых мы знаем из аннотации или из базовых знаний, что они прямо или косвенно принадлежат f.
  
• Exclusion признака f - это множество элементов, для которых мы знаем из отрицательной аннотации или базовых знаний, что они не относятся к f.

extent(f) = {e| (e, f) ∈ A_⇒}
exclusion(f) = {e| (e, f) ∈ N_⇒} U Объединение(extent(g)) по всем (g, f) ∈ M.
В итоге мы формируем каждую рекомендацию, как множество (e, f, w): элемент кода e ∈ E, относящийся к признаку(функции) f ∈ F, с приоритетом w ∈ [0, 1]. Любой механизм рекомендации возвращает множество рекомендаций с приоритетами ⊆ E×F×[0, 1].

Type system - это ключевой рекомендательный механизм, который обеспечивает согласованность, работает на тонкой зернистости(granularity), и включает в себя знания предметной области об отношениях между функциями. Вообще говоря, это функция, которая принимает на вход отношения типа R в программе и возвращает рекомендации с приоритетом 1 для всех элементов кода е и признаков f, на которые ссылаются другие аннотированные элементы:
recommended_TS = {(e,f,1)| (e, e')∈R ∧ e∉extent(f) ∧ e'∉extent(f)}

Идея анализа топологии - следовать графическому представлению системы от текущей степени до всех структурных соседей, таких как методы или связанных с ними переменных. Затем алгоритм выводит приоритеты и ранжирует результаты с помощью показателей specificity(элементам, которые ссылаются только на один элемент, присваивается высокий ранг) и reinforcement(элементам, которые ссылаются на много аннотированных элементов, присваивается высокий ранг).
recommended_TA = {(e, f, w)| e ∈ neighbors(extent(f)), w = weight_TA(e, extent(f)) − weight_TA(e, exclusion(f))}, где weight_TA вычисляется по формуле:

Сравнение текста позволяет выводить рекомендации между объявлениями методов, полей, локальных переменных и типов.
recommend_TC = {(e, f, weight_TC(e, vocb(extent(f)), vocb(exclusion(f))))}, где weight_TС вычисляется по формуле:

Для элемента, рекомендованного время тремя методами, вычисляется приоритет по формуле ниже:

Наша цель состоит в том, чтобы оценить, какую долю рекомендаций наших разработчиков нужно рассмотреть, чтобы найти фрагмент кода, куда можно встроить новый признак(функцию).Для этого мы встроили в нашу модель LEADT(Location, Expansion, And Documentation Tool) алгоритм.
Ниже приведены оценки для Variability-Mining метода:

В среднем, алгоритму удается найти 97% всего кода, со средней точностью 42%. Результаты стабильны независимо от вида анализируемого кода (академический или промышленный, унаследованное приложение или существующая продуктовая линейка), т.е. мы можем найти большинство функций почти полностью. Механизмы рекомендаций вносят разный вклад в итоговый результат. Type system и сравнение текста не очень эффективны по отдельности. Как и предполагалось, механизмы дополняют друг друга, их объединение повышает производительность.
Это продемонстрировано на графике:

Variability mining метод может эффективно выявить особенности в коде и переписать их в качестве дополнительных(или альтернативных) функций благодаря наличию и комбинации различных рекомендательных механизмов.

1. Ordered List ItemB. Adams, W. De Meuter, H. Tromp, and A. E. Hassan. Can We Refactor Conditional Compilation into Aspects? In Proc. Int’l Conf. Aspect-Oriented Software Development (AOSD), pages 243–254. 2009.
2. S. Apel, C. Kästner, and C. Lengauer. FeatureHouse: Language- Independent, Automated Software Composition. In Proc. Int’l Conf. Software Engineering (ICSE), pages 221–231. 2009.