Taming Multi-Variability of Software Product Line Transformations

Software product line engineering [1] enables systematic reuse of software artifacts through the explicit management of variability. Representing a software product line (SPL) in terms of functionality increments called features, and mapping these features to development artifacts such as domain models and code allows to generate custom-tailored products on demand, by retrieving the corresponding artifacts for a given feature selection. Companies such as Bosch, Boeing, and Philips use SPLs to deliver tailor-made products to their customers [2].

Despite these benefits, a growing amount of variability leads to combinatorial explosions of the product space and, consequently, to severe challenges. Notably, this applies to software engineering tasks such as refactorings [3], refinements [4], and evolution steps [5], which, to support systematic management, are often expressed as model transformations. When applying a given model transformation to a SPL, a key challenge is to avoid enumerating and considering all possible products individually. To this end, Salay et al. [6] have proposed an algorithm that “lifts” regular transformation rules to a whole product line. The algorithm transforms the SPL, represented as a variability-annotated domain model, in such way as if each product had been considered individually.

Yet, in complex transformation scenarios as increasingly found in practice [7], not only the considered models include variations: The transformation system can contain variability as well, for example, due to desired optional behavior of rules, or for rule variants arising from the sheer complexity of the involved meta-models. While a number of works [8‐10] support systematic reuse to improve maintainability, variability-based model transformation (VB) [11, 12] also aims to improve the performance when a transformation system with many similar rules is executed. To this end, these rules are represented as a single rule with variability annotations, called VB rule. During rule applications, a special VB rule application technique [13] saves redundant effort by considering common rule parts only once. In summary, for cases where either the model or the transformation system alone contains variability, solid approaches are available.

However, a more challenging case occurs when a variability-intensive transformation is applied to an SPL. In this multi-variability setting, where both the input model and the specification of a transformation contain variability, the existing approaches fall short to deal with the resulting complexity: One can either consider all rules, so they can be “lifted” to the product line, or consider all products, so they become amenable to VB model transformation. Both approaches are undesirable, as they require enumerating an exponentially growing number of artifacts and, therefore, threaten the feasibility of the transformation.

In this paper, we introduce a methodology for SPL transformations inspired by the uniformity principle [14], a tenet that suggests to handle variability consistently throughout all software artifacts. We propose to capture variability of SPLs and transformations using variability-annotated domain models and rules. Model and rule elements are annotated with presence conditions, specifying the conditions under which the annotated elements are present. The presence conditions of model and rule elements are specified over two separate sets of features, representing SPL and rule variability. Annotated domain models and rules can be created manually using available editor support [15, 16], or automatically from existing products and rules by using merge-refactoring techniques [17, 18].

Given an SPL and a VB rule, as shown in Fig. 1, we provide a staged rule application technique (black arrow) for applying a VB rule to a SPL. In contrast to the state of the art (shown in gray), enumerating products or rules upfront is not required. By adopting this technique, existing tools that use transformation technology, such as refactoring engines, may benefit from improved performance.

Specifically, we make the following contributions:

Our work builds on the underlying framework of algebraic graph transformation (AGT) [19]. AGT is one of the standard model transformation language paradigms [20]; in addition, it has recently gained momentum as an analysis paradigm for other widespread paradigms and languages such as ATL [21]. We focus on the annotative paradigm to variability. Suitable converters to and from alternative paradigms, such as the composition-based one [22], may allow our technique to be used in other cases as well.

The rest of this paper is structured as follows: We motivate and explain our contribution using a running example in Sect. 2. Section 3 revisits the necessary background. Section 4 introduces the formalization of our new rule application technique. The algorithm and its evaluation are presented in Sects. 5 and 6, respectively. In Sect. 7 we discuss related work, before we conclude in Sect. 8.

In this section, we introduce SPLs and variability-based model transformation by example, and motivate and explain our contribution in the light of this example.

Software Product Lines. An SPL represents a collection of models that are similar, but different to each other. Figure 2 shows a washing machine controller SPL in an annotative representation, comprising an annotated domain model and a feature model. The feature model [23] specifies a root feature Wash with three optional children Heat, Delay, and Dry, where Heat and Delay are mutually exclusive. The domain model is a statechart diagram specifying the behavior of the controller SPL based on states Locking, Waiting, Washing, Drying, and UnLocking with transitions between them. Presence conditions, shown in gray labels, denote the condition under which an annotated element is present. These conditions are used to specify variations in the execution behavior.

Concrete products can be obtained from configurations, in which each optional feature is set to either true or false. A product arises by removing those elements whose presence condition evaluates to false in the given configuration. For instance, selecting Delay and deselecting Heat and Dry yields the product shown in the right of Fig. 2. The SPL has six configurations and products in total, since Wash is non-optional and Delay excludes Heat.

Variability-Based (VB) Model Transformation. In complex model transformation scenarios, developers often create rules that are similar, but different to each other. As an example, consider two rules foldEntryActions and foldExitActions (Fig. 3), called A and B in short. These rules express a “fold” refactoring for statechart diagrams: if a state has two incoming or outgoing transitions with the same action, these actions are to be replaced by an entry or exit action of the state. The rules have a left- and a right-hand side (LHS, RHS). The LHS specifies a pattern to be matched to an input graph, and the difference between the LHS and the RHS specifies a change to be performed for each match, like the removing of transition actions, and the adding of exit and entry actions.

Rules A and B are simple; however, in a realistic transformation system, the number of required rules can grow exponentially with the number of variation points in the rules. To avoid combinatorial explosion, a set of variability-intensive rules can be encoded into a single representation using a VB rule [12, 18]. A VB rule consist of a LHS, a RHS, a feature model specifying a set of interrelated features, and presence conditions annotating LHS and RHS elements with a condition under which they are present. Individual “flat” rules are obtained via configuration, i.e., binding each feature to either true or false. In the VB rule \(A+B\), the feature model specifies a root feature refactor with alternative child features foldEntry and foldExit. Since exactly one child feature has to be active at one time, two possible configurations exist. The two rules arising from these configurations are isomorphic to rules A and B.

Problem Statement. Model transformations such as foldActions are usually designed for applications to a concrete software product, represented by a single model. However, in various situations, it is desirable to extend the usage context to a set of models collected in an SPL. For example, during the batch refactoring of an SPL, all products should be refactored in a uniform way.

Variability is challenging for model transformation technologies. As illustrated in Table 1, products and rules need to be considered in manifold combinations. In our example, without dedicated variability support, the user needs to specify 6 products and 2 rules individually and trigger a rule application for each of the 12 combinations. A better strategy is enabled by VB model transformation: by applying the VB rule \(A+B\), only 6 combinations need to be considered. Another strategy is to apply rules A and B to the SPL by lifting [6] them, leading to 2 combinations and the biggest improvement so far. Still, in more complex cases, all of these strategies are insufficient. Since none of them avoids an exponential growth along the number of optional SPL features (\(\#F_P\)) or optional rule features (\(\#F_r\)), the feasibility of the transformation is threatened.

Solution Overview. To address this situation, we propose a staged rule application technique for applying a VB rule to an SPL. As shown in Fig. 4, this technique proceeds in three steps: In step 1, we consider the base rule, that is, the common portion of rules encoded in the VB rule, and match its LHS to the full domain model, temporarily ignoring its presence conditions. For example, considering rule A + B, the LHS of the base rule contains precisely states x1, x2, and x. A match to the domain model is indicated by dashed arrows. Using the presence conditions, we determine if the match can be mapped to any specific product. In step 2, we extend the identified base matches to identify full matches of the rules encoded in the VB rule. In the example, we would derive rules A and B; in general, to avoid fully flattening all involved rules, one can incrementally consider common subrules. An example match is denoted in terms of dashed lines for the mappings of transitions and actions. In step 3, to perform rule applications based on identified matches, we use lifting to apply the rule for which the match was found. Lifting transforms the domain model and its presence condition in such way as if each product was considered individually. In the example, only products for the configuration {Delay = true; Heat = false} are amenable to the foldAction refactoring. Consequently, the new entry action startWash has the presence condition Delay, and other presence conditions are adjusted accordingly. Failure to find suitable matches and to fulfill a certain condition during lifting (discussed later) allows early termination of the process.

Performance-wise, the main benefit of this technique is twofold: First, using the termination criteria, we can exit the matching process early without considering specifics of products and rule variants. This is particularly beneficial in situations where none or only few rules of a larger rule set are applicable most of the time, which is typically the case, for example, in translators. Second, even if we have to enumerate some rules in step 2, we do not have to start the matching process from scratch, since we can save redundant effort by extending the available base matches. Consequently, Table 1 gives the number of independent combinations (in the sense that rule applications are started from scratch) as 1.

We now introduce the necessary prerequisites of our methodology, starting with the double-pushout approach to algebraic graph transformation [19]. As the underlying structure, we assume the category of graphs with graph morphisms (referred to as morphisms from here), although all considerations are likely compatible with additional graph features such as typing and attributes.

A rule application exists iff the match m fulfills the gluing condition, which, in the category of graphs boils down to the dangling condition: all adjacent edges of a deleted node in m’s image m[L] must have a preimage in L.

Product Lines. Our formalization represents product lines on the semantic level by considering interrelations between the included graphs. The domain model is a “maximal” graph of which all products are sub-graphs. The presence-condition function maps sub-graphs (rather than elements, as done on the syntactic level) to terms in the boolean term algebra over features, written \(T_{BOOL}(F_P)\). The set of all sub-graphs of the domain model is written \(\mathcal {P}(M_P)\).

Salay et al. [6] provide an algorithm for which it is shown that the properties required in Definition 3 apply. The algorithm extends a rule application to the domain model by a check that the match can be mapped to at least one product, and by dedicated presence condition handling during additions and deletions. A more declarative treatment is offered by Taentzer et al. [25]’s product line pushout construction, which is designed to support lifted rule application as a special case.

Variability-Based Transformation. VB rules are defined similarly to product lines, with a “maximal” rule instead of a domain model, and a notion of subrules instead of subgraphs. A subrule is a rule that can be embedded into a larger rule injectively s.t. the actions of rule elements are preserved [12], e.g., deletions are mapped to deletions. The set of all subrules of a rule r is written \(\mathcal {P}(r)\).

To later consider the base rule, that is, a maximal subrule of multiple flat rules, we define the flattening of VB rules in terms of consecutive intersection and union constructions, expressed as multi-pullbacks and -pushouts [12]. The multi-pullback \(r_0\) gives the base rule, over which the flat rule arises by multi-pushout.

In the example, \(r_{\check{r}}\) is the rule \(A+B\), ignoring presence conditions. Given the configuration c = {foldEntry = true, foldExit = false}, the multi-pullback over each subrule whose presence condition satisfies c yields as the base rule \(r_0\) precisely the part of rule \(A+B\) without presence conditions (i.e., only the states). The resulting flat rule \(r_c\) is isomorphic to rule A.

As a prerequisite for achieving efficiency during staged application, we revisit VB rule application. The key idea is that matches of a flat rule are composed from matches of all of its subrules. By considering the subrules during matching, we can reuse matches over several rules and identify early-exit opportunities.

In the example, a VB match family is obtained: Step 1 collects matches of the LHS \(L_0\). Step 2 reuses these matches to match the flat rules: according to the compatibility condition, we may extend the matches rather than start from scratch. The set of VB rule applications for a rule \(\check{r}\) to a model G is equivalent to the set of rule applications of all flat rules in Flat(\(\check{r}\)) to G [12, Theorem 2].

A variability-based rule represents a set of similar transformation rules, while a product line represents a set of similar models. We consider the application of a variability-based rule to a product line from a formal perspective. Our idea is to combine two principles of maximality, which, up to now, were considered in isolation: First, by applying a rule to a “maximum” of all products, the rule can be lifted efficiently to a product line (Definition 3). Second, by reusing matches of a maximal subrule, several rules can be applied efficiently to a single model (Definition 6).

We study three strategies for applying a variability-based rule \(\check{r}\) to a product line \(P\); the third one leads to the notion of staged rule application as introduced in Sect. 2. First, we consider the naive case of flattening \(\check{r}\) and \(P\) and applying each rule to each product. Second, we take the two maximality principles into account to avoid the flattening of \(\check{r}\). Third, we use additional aspects from the first principle to avoid the flattening of \(P\) as well. We show that all strategies are equivalent in the sense that they change all of \(P\)’s products in the same way.

We present an algorithm for implementing the staged application of a VB rule \(\check{r}\) to a product line P. Following the overview in Sect. 2 and the treatment in Sect. 4, the main idea is to proceed in three steps: First, we match the base rule of \(\check{r}\) to the domain model, ignoring presence conditions. Second, we consider individual rules as far as necessary to obtain matches to the domain model. Third, based on the matches, we perform the actual rule application by using the lifting algorithm from [6] in a black-box manner.

Algorithm 1 shows the computation in more detail. In line 1, \(\check{r}\)’s base rule \(r_0\) is matched to the domain model \(\textit{Model}_P\), leading to a set of base matches. If this set is empty, we have reached the first exit criterion and can stop directly. Otherwise, given a match m, in line 2, we check if at least one product \(P_i\) exists that m can be rerouted onto (Definition 8). To this end, in lines 3–4, we use a SAT solver to check if there is a valid configuration of P’s feature model for which all presence conditions of matched elements evaluate to true. In this case, we iterate over the valid configurations of \(\check{r}\) in line 5 (we may proceed more fine-grainedly by using partial configurations; this optimization is omitted for simplicity). In line 6, a flat rule is obtained by removing all elements from the rule whose presence condition evaluates to false. We match this rule to the domain model in line 7; to save redundant effort, we restrict the search to matches that extend the current base match. Absence of such a match is the second stopping criterion. Otherwise, we feed the flat rule and the set of matches to lifting in line 8. Handling dangling conditions is left to lifting; in the positive case, P is transformed afterwards.

For illustration, consider the base match \(m_1\) = {Looking, Waiting, Washing} from Fig. 4. First we calculate \(\varPhi _{pc}\). As none of the states in the domain model has a presence condition, \(\varPhi _{pc}\) is set to true and is identified as satisfiable. Two valid configurations exist, \(c_1 = \{foldEntry=true,foldExit=false\}\) and \(c_2 = \{foldEntry=false,foldExit=true\}\). Considering \(c_1\), the presence condition foldExit evaluates to false; removing the corresponding elements yield a rule isomorphic to Rule A in Fig. 3. Match \(m_1\) is now extended using this rule, leading to a match as shown in step 2 of Fig. 4. and then lifted, as discussed in the earlier explanation of the example. Step 2 is repeated for configuration \(c_2\); yet, as no suitable match in \(c_2\) exists, the shown transformation is the only possible one.

This algorithm benefits from the correctness results shown in Sect. 4. Specifically, it computes staged rule applications as per Definition 11: A configuration c is determined in line 5, and values for match \(m_c\) are collected in the set Matches. Via Corollary 1 and Theorem 1, the effect of the rule application to the products is the same as if each product had been considered individually.

In terms of performance, two limiting factors are the use of a graph matcher and a SAT solver; both of them perform an NP-complete task. Still, we expect practical improvements from our strategy of reusing shared portions of the involved rules and graphs, and from the availability of efficient SAT solvers that scale up to millions of variables [26]. This hypothesis is studied in Sect. 6.

To evaluate our technique, we implemented it for Henshin [27, 28], a graph-based model transformation language, and applied it to a transformation scenario with product lines and transformation variability. The goal of our evaluation was to study if our technique indeed produces the expected performance benefits.

Setup. The transformation is concerned with the detection of applied editing operations during model differencing [29]. This setting is particularly interesting for a performance evaluation: Since differencing is a routine software development task, low latency of the used tools is a prerequisite for developer effectiveness. The rule set, called UmlRecog, is tailored to the detection of UML edit operations. Each rule detects a specific edit operation, such as “move method to superclass”, based on a pair of model versions and a low-level difference trace. UmlRecog comprises 1404 rules, which, as shown in Table 2, fall in three main categories: Create/Set, Change/Move, and Delete/Unset. To study the effect of our technique on performance, an encoding of the rules into VB rules was required. We obtained this encoding using RuleMerger [18], a tool for generating VB rules from classic ones based on clustering and clone detection [30]. We obtained 504 VB rules; each of them representing between 1 and 71 classic rules. UmlRecog is publicly available as part of a benchmark transformation set [31].

We applied this transformation to the 6 UML-based product lines specified in Table 3. The product lines came from diverse sources and include manually designed ones (1–2), and reverse-engineered ones from open-source projects (3–6). Each product line was available as an UML model annotated with presence conditions over a feature model. To produce the model version pairs used by UmlRecog, we automatically simulated development steps by nondeterministically applying rules from a set of edit rules to the product lines, using the lifting algorithm to account for presence conditions during the simulated editing step.

Results. Table 4 gives an overview of the results of our experiments. The total execution times for our technique were between 1.5 and 3.3 s, compared to 9.4 and 10.6 s for lifting, yielding a speedup by factors between 2.8 and 6.5. For both techniques, all execution times are in the same order of magnitude across product lines. A possible explanation is that the amount of applicable rules was small: if the vast majority of rules can be discarded early in the matching process, the execution time is constant with the number of rules.

The greatest speedups were observed for the Change/Move category, in which rule variability was the greatest as well, indicated by the ratio between rules and VB rules in Table 2. This observation is in line with our rationale of reusing shared matches between rules. Regarding the number of products, a trend regarding better scalability is not apparent, thus demonstrating that lifting is sufficient for controlling product-line variability. Still, based on the overall results, the hypothesis that our technique improves performance in situations with significant product-line and transformation variability can be confirmed.

During an SPL’s lifecycle, not only the domain model, but also the feature model evolves [32, 33]. To support the combined transformation of domain and feature models, Taentzer et al. [25] propose a unifying formal framework which generalizes Salay et al.’s notion of lifting [6], yet in a different direction than us: focusing on combined changes, this approach is not geared for internal variability of rules; similar rules are considered separately. Both works could be combined using a rule concept with separate feature models for rule and SPL variability.

Beyond transformations of SPLs, transformations have been used to implement SPLs. Feature-oriented development [34] supports the implementation of features as additive changes to a base product. Delta-oriented programming [35] adds flexibility to this approach: changes are specified using deltas that support deletions and modifications as well. Impact analysis in an evolving SPL can be performed by transforming deltas using higher-order deltas that encapsulate certain evolution operators [5]. For increased flexibility regarding inter-product reuse, deltas can be combined with traits [36]. Sijtema [8] introduced the concept of variability rules to develop SPLs using ATL. Conversely, SPL techniques have been applied to certain problems in transformation development. Xiao et al. [37] propose to capture variability in the backwards propagation of bidirectional transformations by turning the left-hand-side model into a SPL. Hussein et al. [10] present a notion of rule templates for generating groups of similar rules based on a data provenance model. These works address only one dimension of variability, either of a SPL or a transformation system.

In the domain of graph transformation reuse, rule refinement [9] and amalgamation [38] focus on reuse at the rule level; graph variability is not in their scope. Rensink and Ghamarian propose a solution for rule and graph decomposition based a certain accommodation condition, under which the effect of the original rule application is preserved [39, 40]. In our approach, by matching against the full domain model rather than decomposing it, we trade off compositionality for the benefit of imposing fewer restrictions on graphs and rules.

We propose a methodology for software product line transformations in which not only the input product line, but also the transformation system contains variability. At the heart of our methodology a staged rule application technique exploits reuse potential with regard to shared portions of the involved products and rules. We showed the correctness of our technique and demonstrated its benefit by applying it to a practical software engineering task.

In the future, we aim to explore further variability dimensions, e.g., meta-model variability as considered in [41], and to extend our work to advanced transformation features, such as application conditions. We aim to address additional variability mechanisms and to perform a broader evaluation.