In model-driven software engineering, model transformations are used for the specification of model changes. Similar to programs also model transformations can exhibit bad smells which indicate possible weaknesses. In this paper, we address bad smells which can negatively affect the performance of the application of model transformations, particularly, model transformations defined in Henshin. Based on a description of the Henshin interpreter and its performance enhancing strategies, we describe a set of bad smells and corresponding detectors. We evaluate the detectors by applying them to the example rule set of Henshin.
Model transformations are a key part of model-driven software engineering
approaches as they define the changes on individual models or between models.
There exist many different languages for the specification of model
transformations, e.g., PMT [
Graph transformation based approaches, like the ones above, essentially define model transformations using rules consisting of a pre-condition graph, called the left-hand side (LHS), and a post-condition graph, called the right-hand side (RHS) of the rule. Informally, the execution of a model transformation requires that a matching of objects in the model (host graph) to the nodes and edges in the LHS is found and these matched objects are changed in such a way that the nodes and edges of the RHS match these objects.
The performance of graph transformation based model transformations are
mainly determined by the efficiency of the match finding of the LHS. Consequently,
model transformation languages offer different options to add constraints to the
LHS of model transformations to improve the performance of the matching. To be
efficient, graph transformation tools usually employ heuristics such as search plans
to provide good performance (e.g. [
The contribution of this paper is an informal description of bad smells in Henshin transformation rules which might negatively affect the execution performance. These bad smells are indicators for potential performance issues to be expected at runtime. Detectors of these bad smells are then formalized as Henshin rules (and in some cases utility code) on the Henshin meta model itself. Finally, we report on the amount of bad smells found in the examples provided with Henshin itself. We focus in this paper on static analysis on the transformation rules.
We introduce Henshin and its matching approach in the next section. Section 3 contains the description and formalization of the bad smells. The results of the execution of the bad smells detectors on the Henshin examples are shown in Section 4. After a short discussion of related work in Section 5, we conclude and present an outlook on future work in dynamic performance analysis of Henshin transformations. 2
Henshin is a high-level graph rewriting and model transformation language and
tool targeting models defined in the Eclipse Modeling Framework (EMF) [
The Henshin transformation language is defined by means of a meta model. Figure 1 shows a part of this meta model which is relevant for this paper. Graph transformation rules are modeled using instances of the Rule class. The Henshin meta model is closely aligned to the underlying formal model of double pushout (DPO) graph transformations. Thus, rules consist of a left-hand side and a right-hand side graph as instances of the Graph class. Rules further contain node mappings between the LHS and the RHS which are omitted here for better readability. Graphs consist of a set of Nodes and a set of Edges. Nodes can additionally contain a set of Attributes. These three kinds of model elements are typed by their corresponding concepts in the Ecore meta model of EMF (depicted in blue). Rule inherits from Unit and therefore can contain a number of Parameters. A typical use of parameters is to pass an attribute value (e.g. a name) of a node to be matched to the rule. To constrain the applicability of a multiRu0le.*s checkDanglinRguAle:AEBoolean AttributeCondition injectiveMatchingA:AEBoolean conditionTextA:AEString 0. * rule 1
attributeConditions 1 rhs lhs1 child Formula 0. 1 Graph 1 1formula
1left right UnaryFormula
BinaryFormula
NamedElement nameA:AEString descriptionA:AEString
Parameter
0. * parameters
0. 1
unit
rule, the meta model contains concepts for modeling nested graph conditions [
The graph pattern matching engine of Henshin solves this task by translating it into an equivalent constraint-solving problem (CSP) and by employing several heuristics to achieve efficiency in almost all practical scenarios. Every node in the LHS is considered as a variable in the CSP. For each of these variables, a corresponding domain slot is created which is essentially the solution space for this variable, i.e., all nodes in the host graph which are possible matches for this node. The graph pattern matching is realized by a recursive algorithm which i) removes impossible solutions for a variable by imposing constraints on their domain slot, and ii) locking variables to specific solutions and thereby constructing matches.
The efficiency of the pattern matching primarily depends on a) how much
the constraints reduce the solution space of variables and b) the order in which
the recursive algorithm locks variables. The order of variables can in Henshin be
either manually optimized or fully automatically using a heuristic which sorts the
variables on-the-fly based on the current host graph (enabled by default). The
used constraints in the CSP can be categorized into different groups. The most
basic kind of constraints are type constraints. They reduce the solution space to
objects which are instances of a given class (or a subclass of it). If there exists an
edge x !e y and the source variable x is locked already to a specific node X, the
solution space of y is restricted to all e-images of X. This kind of constraints is
referred to as reference constraints in Henshin. Similarly, so-called containment
constraints reduce domain slots to containment children or container nodes (cf.
containment references in EMF [
In the following, we present a set of bad smells which can negatively affect the performance of the matching of the LHS. Detecting an instance of such a bad small does not imply that it is a performance problem. It is merely an indicator that there might be a problem which can cause an unnecessary bad transformation execution performance. Furthermore, the presented detectors have false positives and false negatives due to the decision to specify the detection mainly using Henshin rules on Henshin rules. Due to space restrictions, we cannot show all detectors in the paper in detail. Instead, we refer the interested reader to the detection Henshin rule set and the supporting source code available at www.cse.chalmers.se/~tichy/henshin_bad_smells.zip 3.1
Description: If a LHS is not a connected graph, it is not possible to use the edges between nodes to constrain possible matches of nodes. This means (in general) that two independent subgraphs must be matched.
Detector: The detector computes all (weakly) connected components of a LHS by a loop, which starts by marking an unmarked node of the LHS with a distinct marker and then iteratively marks with the same marker all nodes which are reachable by an edge from a marked node. This loop is executed until all nodes are marked. If the rule contains more than one marker object, the LHS is not connected.
Notes: The detector currently computes only (weakly) connected components. By supporting strongly connected components, the detection would also correctly identify a LHS where one of the two subgraphs of the LHS are only connected by an edge directed from one subgraph to the other. In this case, reference constraints can only be exploited in one direction of the rule. 3.2
Description: If a node of the LHS is already known due to a rule parameter, matching of the other nodes of the LHS can start at a known point in the host graph. Hence, instead of searching the whole host graph for a matching only a local search must be performed. Consequently, the interpreter optimizes the matching order of the nodes by moving known objects to the front of the matching order.
Detector: The detector checks whether a rule parameter exists with the same name as a node in the LHS. If the rule of a graph can be divided into several connected components, the detector also checks for each connected components since a matched node in one connected component does not affect (in general) the matching of the other connected components. Figure 2(a) shows the main detector rule. Additionally, the detector ignores multi-rules since they typically contain mappings to the kernel rule.
Notes: Note, the user of the transformation decides whether this parameter is used as input for the matching of the LHS or only as an output. In the latter case, the undetected bad smell would be a false negative.
(a) Main part of the detector for rules without known node (b) Detector rule for too many nodes of the same type (c) Detector rule for binding a node over to-many edge before a node binding over to-one edge (d) Main part of the detector rule for nodes without incoming reference
Description: While the previous “no bound node” bad smell checks only whether a node in the LHS is known by a parameter, constraints on an attribute of the node is another option to restrict the number of possible objects to match. The interpreter also places nodes with an attribute constraint as much as possible to the front of the matching order but behind known nodes.
Detector: The detector is an extension of the detector of the previous sections. It detects an LHS (or similarly to above a connected component of the LHS) which neither contains a known node nor a node with an attribute constraint. The reason to extend the previous detector and only report an LHS which additionally does not contain a known node is that a known node already improves the matching process by itself. Again, multi-rules are ignored since they contain mappings to the kernel rule.
Notes: A future option to increase the execution performance of Henshin transformation rules would be to support Map-based references as in Fujaba. This would improve the matching of nodes with attribute constraints when the attribute constraint is used as an unique identifier. 3.4
Description: If a node has no incoming edge, all objects in the system of the same type are possible matches for this node since matches of other nodes cannot be used to restrict the number of potential objects for this node by reference constraints.
Detection: The major part of the detector for this bad smell is shown in Figure 2(d). Additionally, the detector checks that the node without incoming references does not already have a matching due to a parameter of the rule. 3.5
Description: As described above, Henshin supports the optimization of the node matching order to improve the performance of the matching. If this option is not used the order of the matching is defined by the order of the nodes in the graph of the LHS.
In this case, we detect a bad smell if a node is matched which is reachable by a to-many reference before a node is matched which is reachable by a to-one reference. The to-one referenced node is faster to match as only one possible object can be matched whereas the to-many referenced node might have multiple possible matching objects.
Detector: Figure 2(c) shows the detector of this bad smell. In addition, it checks whether node2 is matched before node3. For this, we exploit that the reference between Graph and Node is ordered and thus we can check the indices of the nodes in this reference using the newly implemented support for edge indices in Henshin. 3.6
Description: Henshin employs type constraints to restrict the possible matching of nodes to those objects of the correct type. If a lot of nodes in the LHS are typed over the same type, then the type constraints might lose their benefits. In the extreme case, if only one type is used, then type constraints do not restrict the matchings at all.
Detector: The detector checks whether the number of nodes with the same type exceeds a certain threshold. For our evaluation, we used a threshold of 3 nodes with the same type. Figure 2(b) shows the detector rule. 3.7
Description: If the typing used for the node in the LHS of a Henshin rule is too generic, the type constraints in the Henshin interpreter do not gain that much performance. An example would be the use of EObject, which is the supertype of all EMF generated classes, as type of a node.
Another case is the generic use of the Trace class provided by Henshin to specify tracing between objects in exogeneous model transformations. In order to improve the matching of the trace objects, it is beneficial to create and use different subclasses of Trace for each tracing information, such that type constraints on traces can be exploited in the interpreter.
Detector: The detector detects rules which include one node which is typed using EObject, Trace or an abstract class. 4
As an early evaluation, we executed the detectors on all examples delivered as part of Henshin, our own example file, and on the detector rules themselves. Figure 3 shows an overview of the results. The two first columns contain as reference the number of rules and connected components in each example file. Note that some rules do not include an LHS, i.e., they are always applicable. The number of connected components can be less than the number of rules in these cases.
Mostly, the bad smells “no bound node” and “node without incoming edges” have been detected in the evaluation examples. However, often these rules contain at least a node with an attribute constraint. Another aspect shown in the evaluation is that some of the examples are graph transformation benchmarks or generic examples like mutualexclusion.henshin and sierpinski.henshin where a number of performance bad smells are not surprising. The bad smell “preferring to many reference before to one reference” seems to be a known issue. Finally, when running the detectors on themselves, we are also guilty of some performance bad smells. 5
There exists some previous work in the area of model transformations and
performance. Varró et al. [
Another line of research is the definition of metrics for model
transformations [
Specifically for Henshin graph transformations, Taenzter et al. also define
bad smells and refactorings [
We presented performance bad smells in Henshin model transformation rules and corresponding detectors which were also specified as Henshin model transformations. The current version of the detection suffers from the design decision to specify the detectors also mostly with Henshin rules. Consequently, only an analysis on a syntactical level is possible which leads to false positives and false negatives.
Future evaluations of the bad smells will compare the performance of the presented detector rules with refactored rules which have less performance bad smells. Early investigations show that refactoring of rules to remove the bad smells is not a simple change but might require more extensive changes in several rules and how the rules interact. It remains to be seen whether these refactorings have a positive effect on performance but a negative effect on other qualities like readability.
We will investigate an extension of the Henshin interpreter engine in order to assess the impact of the identified bad smells at runtime. For example, we can measure and plot the number of possible matches for a node during the matching of the LHS in order to identify whether the bad smell “no bound node in LHS” for the analysed rule is really problematic or not.
Furthermore, the presented bad smells might be applicable and extended for other model transformation languages as well.
The research leading to these results has received partial funding from the European Union’s Seventh Framework Program (FP7/2007-2013) for CRYSTAL – Critical System Engineering Acceleration Joint Undertaking under grant agreement No 332830 and from Vinnova under DIARIENR 2012-04304. This work was also done in collaboration with the project ENSURE which is funded by the DFG (German Research Foundation) under the Priority Programme SPP1593: Design For Future – Managed Software Evolution.