On the Quality Properties of Model Transformations: Performance and Correctness

On the Quality Properties of Model Transformations: Performance and Correctness Loli Burgueño Departamento de Lenguajes y Ciencias de la Computación University of Malaga Supervised by Antonio Vallecillo and Manuel Wimmer April 2016 AUTOR: Dolores Burgueño Caballero http://orcid.org/0000-0002-7779-8810 EDITA: Publicaciones y Divulgación Científica. Universidad de Málaga Esta obra está bajo una licencia de Creative Commons Reconocimiento-NoComercialSinObraDerivada 4.0 Internacional: http://creativecommons.org/licenses/by-nc-nd/4.0/legalcode Cualquier parte de esta obra se puede reproducir sin autorización pero con el reconocimiento y atribución de los autores. No se puede hacer uso comercial de la obra y no se puede alterar, transformar o hacer obras derivadas. Esta Tesis Doctoral está depositada en el Repositorio Institucional de la Universidad de Málaga (RIUMA): riuma.uma.es To those I love. To those who love me. El Dr. Antonio Vallecillo Moreno, Catedrático de Universidad del Departamento de Lenguajes y Ciencias de la Computación de la E.T.S. de Ingeniería Informática de la Universidad de Málaga, y el Dr. Manuel Wimmer, profesor perteneciente al Business Informatics Group en la Universidad Tecnológica de Viena, Certifican que Dña. Dolores Burgueño Caballero, Ingeniera Informática, ha realizado en el Departamento de Lenguajes y Ciencias de la Computación de la Universidad de Málaga, bajo su dirección, el trabajo de investigación correspondiente a su Tesis Doctoral titulada: On the Quality Properties of Model Transformations: Performance and Correctness Revisado el presente trabajo, estimamos que puede ser presentado al tribunal que ha de juzgarlo, y autorizamos la presentación de esta Tesis Doctoral en la Universidad de Málaga. Málaga, abril de 2015 Fdo. Antonio Vallecillo Fdo. Manuel Wimmer Catedrático de Universidad Associate Profesor Dpto. Leng. y Ciencias de la Computación Bussiness Informatics Group Universidad de Málaga Vienna University of Technology Acknowledgements This thesis has been supported by the fellowship BES-2012-057064 granted by the Programme for the Training of Researchers of the Ministry of Economy and Competitiveness of Spain and the Spanish research projects TIN2011-23795 and TIN2014-52034-R. Special Acknowledgements Mucha gente me ha acompañado durante el desarrollo de esta tesis doctoral, tanto en el ámbito académico como en el personal. Algunos llevan conmigo tanto tiempo que no recuerdo la vida sin ellos. Otros llegaron más tarde y aun así supieron hacerse notar. A todos y cada uno, gracias. En primer lugar me gustaría mostrar mis agradecimientos a mis directores de tesis, Antonio Vallecillo y Manuel Wimmer. Antonio, gracias por depositar tu confianza en mí y ofrecerme la posibilidad de realizar esta tesis doctoral, espero no haberte defraudado. Gracias por dedicarme parte de tu tiempo aun estando tan ocupado, gracias por tus buenos consejos e ideas y gracias por darme un trato tan agradable. Gracias por tener siempre una sonrisa en la cara y por ser tan entusiasta y optimista, son cosas que se transmiten. Sinceramente, no creo que hubiera podido tener un mejor director de tesis. Manuel, although your stay in Málaga was short (a year and a half is short) and the distance makes the communication difficult, thank you for helping me so much, for always being willing to share your ideas with me, for your advice, for finding the way to work together, for inviting me to Vienna, and a long etcetera. I wish you could have stayed longer in Málaga. We miss you. También tengo que dar las gracias a todos los miembros de Atenea y en especial a Javi Troya. Javi, gracias por prestarme tanta ayuda y por tu paciencia, sobre todo al principio que era cuando más lo necesitaba. Gracias también a todos mis compañeros del 3.3.3. por ayudarme en la medida de lo posible, por hacer amenos tantos almuerzos y por los buenos ratos que hemos pasado fuera de las cuatro paredes del laboratorio. Las largas horas de trabajo se hacen más pasajeras cuando la compañía es buena. Gracias a Lola y Jose Luis Reyes por vuestra eficiencia y amabilidad a la hora de resolver los temas administrativos. 6.2.3 Evaluation Procedure . . . . . . . . . . . . . . . . . . 143 6.2.4 Results .......................... 143 6.3 RelatedWork........................... 145 6.4 Summary ............................. 148 7 Conclusions and Future Work 149 7.1 Summary and Conclusions . . . . . . . . . . . . . . . . . . . . 150 7.2 Publications............................ 151 7.2.1 Publications Supporting this Dissertation . . . . . . . 152 7.2.2 Further Publications . . . . . . . . . . . . . . . . . . . 154 7.3 FutureWork ........................... 155 References 159 Appendix A Similarity Matrixes 173 Appendix B Resumen 187 Appendix C Conclusiones y Contribuciones 189 List of figures 2.1 Organization in four layers proposed by the OMG. . . . . . . 13 2.2 Overview of the elements involved in a MT. . . . . . . . . . . 14 2.3 Building Blocks of a Tract [56]. . . . . . . . . . . . . . . . . . 19 2.4 The Family and Person metamodels. . . . . . . . . . . . . . . 20 3.1 LinTra architecture . . . . . . . . . . . . . . . . . . . . . . . . 28 3.2 LinTra interface. . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.3 BibTeXML metamodel excerpt. . . . . . . . . . . . . . . . . . . 34 3.4 DBLPMetamodel......................... 46 3.5 AuthorInfo Metamodel. . . . . . . . . . . . . . . . . . . . . . 47 3.6 IMDbMetamodel. ........................ 48 3.7 Prefuse Graph Metamodel. . . . . . . . . . . . . . . . . . . . 50 3.8 Comparative chart for the DBLP case study. . . . . . . . . . 55 3.9 Comparative chart for the IMDb-Identity case study. . . . . . 55 3.10 Comparative chart for the IMDb-FindCouples case study. . . 56 3.11 Comparative chart for the Java Refactoring case study. . . . . 56 3.12 Comparative chart for the Java-to-Graph case study. . . . . . 57 3.13 Comparative chart for the IMDb-Identity using RAM memory andharddisk. .......................... 60 5.1 Heterogeneities and Commonalities between Constraints and Rules. ............................... 90 5.2 Possible overlaps for Ciand Rj.................. 95 5.3 Situations with differently sized rule/constraint footprints. . . 97 5.4 The UML and ER metamodels. . . . . . . . . . . . . . . . . . 99 xvii 5.5 Matching process. . . . . . . . . . . . . . . . . . . . . . . . . 105 6.1 Metamodel for representing text artifacts and repositories. . . 132 6.2 Exemplary folder structure and corresponding text model. . . 133 6.3 Exemplary file content and corresponding text model. . . . . 133 6.4 A simplified metamodel for UML class diagrams. . . . . . . . 134 A.1 Similarity Matrix for the ATOM2XML example. . . . . . . . 174 A.2 Similarity Matrix for the ATL2Problem example. . . . . . . . 174 A.3 Similarity Matrix for the ATOM2RSS example. . . . . . . . . 174 A.4 Similarity Matrix for the BibTex2DocBook example. . . . . . 175 A.5 Similarity Matrix for the CPL2SPL example. . . . . . . . . . 175 A.6 Similarity Matrix for the ECORE2USE example. . . . . . . . 176 A.7 Similarity Matrix for the IEEE14712MoDAF example. . . . . 176 A.8 Similarity Matrix for the KM32OWLF example. . . . . . . . 177 A.9 Similarity Matrix for the KM32Problem example. . . . . . . . 177 A.10 Similarity Matrix for the Measure2Table example. . . . . . . 178 A.11 Similarity Matrix for the Measure2XHTML example. . . . . . 178 A.12 Similarity Matrix for the MySQL2KM3 example. . . . . . . . 178 A.13 Similarity Matrix for the PathExp2PetriNet example. . . . . 179 A.14 Similarity Matrix for the PathExp2TextualPath example. . . 179 A.15 Similarity Matrix for the PetriNet2Grafcet example. . . . . . 179 A.16 Similarity Matrix for the PetriNet2PathExp example. . . . . 180 A.17 Similarity Matrix for the PetriNet2PNML example. . . . . . . 180 A.18 Similarity Matrix for the PetriNet2XML example. . . . . . . 180 A.19 Similarity Matrix for the PNML2PetriNet example. . . . . . . 181 A.20 Similarity Matrix for the PNML2XML example. . . . . . . . 181 A.21 Similarity Matrix for the R2ML2WSDL example. . . . . . . . 181 A.22 Similarity Matrix for the RSS2ATOM example. . . . . . . . . 182 A.23 Similarity Matrix for the RSS2XML example. . . . . . . . . . 182 A.24 Similarity Matrix for the UML2ER example. . . . . . . . . . 182 A.25 Similarity Matrix for the XML2MySQL example. . . . . . . . 183 A.26 Similarity Matrix for the WSDL2R2ML example. . . . . . . . 183 A.27 Similarity Matrix for the XML2ATOM example. . . . . . . . 184 A.28 Similarity Matrix for the XML2PetriNet example. . . . . . . 184 A.29 Similarity Matrix for the XML2PNML example. . . . . . . . 185 A.30 Similarity Matrix for the XML2RSS example. . . . . . . . . . 185 A.31 Similarity Matrix for the XML2WSDL example. . . . . . . . 186 A.32 Similarity Matrix for the XSLT2XQuery example. . . . . . . 186 List of tables 3.1 Example uses of trace function . . . . . . . . . . . . . . . . . 35 3.2 Data management middleware comparison . . . . . . . . . . . 42 3.3 Results for the DBLP case study. . . . . . . . . . . . . . . . . 53 3.4 Results for the IMDb-Identity transformation. . . . . . . . . . 53 3.5 Results for the IMDb-FindCouples transformation. . . . . . . 53 3.6 Results for the Java Refactoring transformation. . . . . . . . 54 3.7 Results for the Java-to-Graph transformation. . . . . . . . . . 54 3.8 Average speed-up of jLinTra w.r.t. the rest of the transformationengines............................. 57 3.9 Results for the Java-to-Graph-to-ReducedGraph transformationchain.............................. 69 3.10 Results for IMDb-Identity using RAM memory and HDD. . . 69 4.1 Execution results and speedups. . . . . . . . . . . . . . . . . . 81 5.1 Footprints for the Families2Persons example. . . . . . . . . . 93 5.2 Families2Persons matching tables. . . . . . . . . . . . . . . . 98 5.3 Matching table using CC metric. . . . . . . . . . . . . . . . . 101 5.4 Matching table using RC metric. . . . . . . . . . . . . . . . . 102 5.5 Matching table using RCR metric. . . . . . . . . . . . . . . . 102 5.6 Transformation Metrics Overview. . . . . . . . . . . . . . . . 112 5.7 Metamodel Metrics Overview. . . . . . . . . . . . . . . . . . . 112 5.8 Expected alignments for the UML2ER transformation. . . . . 114 5.9 Accuracy of case studies. . . . . . . . . . . . . . . . . . . . . . 116 5.10 Similarity Matrix for the Rules in UML2ER. ......... 117 5.11 Summary of Similarity Matrixes. . . . . . . . . . . . . . . . . 119 xxi 5.12 Possible Mutations for ATL Transformations (from [13]). . . . 120 5.13 Summary of mutations and fault localization results (CPL2SPL project)............................... 121 6.1 Evaluation results . . . . . . . . . . . . . . . . . . . . . . . . 144 Acronyms MDE Model-Driven Engineering MDA Model-Driven Architecture MT Model Transformation M2M Model-to-Model M2T Model-to-Text T2M Text-to-Model MM Metamodel HOT High-Order Model Transformation CASE Computer-Aided Software Engineering OMG Object Management Group ATL ATLAS Transformation Language QVT Query/View/Transformation ETL Epsilon Transformation Language EMF Eclipse Modeling Framework RQ Research Question CC Constraint Coverage RC Rule Coverage RCR Relatedness of Constraints and Rules CT Classifying Term USE UML-based Specification Environment OCL Object Constraint Language xxiii Chapter 1 Introduction There is no doubt that software currently plays an essential role in our society. The needs that we humans have for software are increasing. The more present software is in our daily life, the more we demand from it. Therefore, the problems it has to solve are increasingly complex. Software as we now understand it, i.e., instructions that are executed in digital machines, first appeared in the late 1940s and its instructions were written directly in binary code. Since then, we have placed several abstraction layers on top of the binary code to facilitate the writing of more complex programs—nowadays, it is not only a matter of easing the writing but of making it possible. One of these attempts has led to Model Driven Engineering (MDE). MDE is an approach for software development that was developed with the intention of manipulating the complexity of large software systems by considering only those aspects that were useful for a specific purpose and leaving out superfluous details. All this is achieved through dedicated models. Models capture the aspects of interest of systems and behave as an abstraction of them, representing reality for a given purpose. Thus, models are simpler, safer and/or cheaper than reality and allow users to deal with the interesting parts of the real systems in a simplified and more focused way. This helps avoid the complexity, danger and irreversibility of real scenarios. Alongside models, Model Transformations (MT) play a central role in all model-driven software engineering processes [ 16 ]. They manipulate these 1 Chapter 1. Introduction Appendix C. Conclusiones y Contribuciones This appendix reports our conclusions, the list of contributions of this dissertation and discusses future lines of work in Spanish. 8 Chapter 2 Background 9 Chapter 2. Background 2.1 Model-Driven Engineering In the field of software engineering, abstractions are a key element for success. Abstraction enables understanding and/or analyzing complex domains of concern, such as programs, software systems, and their application domains, which contain a plethora of detail. In this regard, a model is a simplified and generalized representation of a real world system or concept created to facilitate its understanding. Model-Driven Engineering is a methodology that advocates the use of models as first class entities throughout the software engineering life cycle. It is meant to increase productivity by maximizing compatibility between systems, simplifying the process of design and promoting communication between individuals and teams working on the system. 2.1.1 History Over the past five decades, software engineers have been creating abstractions that help them program, focusing only on their design intent and leaving out details from the underlying computing environment such as CPU, memory, etc. and their complexities. For instance, languages such as C (released in the early 1970s) raised the level of abstraction over assembly languages so that programmers did not need to worry about low level details related to memory position access. Similarly, early operating system platforms, such as OS/360 (released in 1967) and Unix (originally developed in 1969), shielded developers from the complexities of programming directly with hardware devices [125]. Historically, Computer-Aided Software Engineering (CASE) tools developed in the 80s were considered to be the first tools to support MDE. These tools aimed to provide a graphical means of simplifying software development, whilst also generating implementation artifacts. However, they lacked standardization. In the past two decades, the advances in programming languages and platforms have raised the level of software abstractions available to developers. Examples of this are object-oriented languages such as C++, Java, or C#, 10 2.1 Model-Driven Engineering which offered a higher level of abstraction than Fortran or C. However, they still had a distinct computing-oriented focus that was a problem when the size of software as well as its complexity increased. When we talk about complexity we mean both accidental and essential complexity. Accidental complexity is caused by the specific solution that the engineer developed and the problems that that solution might carry. On the other hand, the essential complexity, named by Brooks et al. in [ 17 ], is given by the problem to be solved itself. New problems have appeared, related to the semantic gap between the software design and its implementation—which requires an unacceptable number of lines of code. This leads to the fact that developers need to pay attention to so many programming details that it becomes difficult to focus on strategic architectural issues such as system correctness and performance. Model-Driven Engineering is a relatively new methodology that applies lessons learnt from earlier attempts to develop higher-level platform and language abstractions. MDE tools also help detect and prevent many errors throughout the software development life cycle. 2.1.2 Models and Metamodels A key concept in model-driven approaches is that of models. Ludewig claims in [ 95 ] that they were not invented but rather we have been using them since we have existed. Therefore, it is difficult to find a consensus of what they are, or in other words to find, a definition for the concept of “model”. Endless discussions have proved that there is no common understanding of them. Nevertheless, most people seem to support the idea that the particular strength of models is based on the idea of abstraction and promotion of simpler models with a greater focus on the problem space. This combined with executable semantics elevates the total level of automation possible. According to Stachowiak a model needs to possess three features [ 130 ]: (i) mapping: a model is a representation of an original, (ii) reduction: not all the properties of the subject are mapped onto the model, (iii) pragmatic: a model needs to be usable in place of the original with respect to some purpose. 11 Chapter 2. Background The Object Management Group (OMG) developed a set of standards called Model-Driven Architecture (MDA), thereby creating the foundation for this advanced architecture-focused approach. In different documents, the OMG gives different definitions. In [ 104 ] it is defined as the representation of a part of the functionality, structure and/or behavior of a system. In [ 105 ], the OMG defines a model as the description or specification of a system and its environment defined for a specific purpose. Finally, in [ 107 ] the OMG states that a model captures a view of a physical system, with a specific purpose. The purpose determines what is to be included in the model and what is irrelevant. Consequently, the model describes those aspects of the physical system which are relevant to the model’s purpose, and at the right level of abstraction. From a software engineering perspective, engineers build models principally to better understand the useful characteristics of an existing or desired system and its environment, to predict the characteristics of a system by analyzing its models, to communicate their understanding and design intent to others and to specify the implementation of the system among others. Apart from the definition and the purpose of models and modeling, there is a need to identify the main functions of models. According to Gérard and Selic in a keynote 1 given in 2010, a model must have the following characteristics in order to be useful: (i) purposeful, (ii) abstract, (iii) understandable, (iv) accurate, (v) predictive and (vi) cost-effective. Related to models there are metamodels. A metamodel is a model that is used to describe another model. It specifies the concepts of the language, the relationships between these concepts, the structural rules that restrict the possible elements in the valid models and those combinations between elements with respect to the domain semantic rules. As a metamodel is also a model, the term “meta” is therefore relative—depending on the perspective, a model is either a model or a metamodel. Each model is described in the language defined by its metamodel, so there is a conformance relation between a model and its metamodel. A metamodel 1 http://www.artist-embedded.org/docs/Events/2010/FESA/slides/1_ Keynote_Gerard+Selic.pdf 12 2.1 Model-Driven Engineering Fig. 2.1 Organization in four layers proposed by the OMG. is in itself a model and, consequently, it is written in the language defined by its meta-metamodel. The recursive process for defining models which conform to models at a higher level of abstraction ends when a level where a model conforms to itself, is reached. The OMG supports the four-level architecture, called Meta-Object Facility (MOF), that was illustrated by Bézivin in [ 14 ] and presented in Figure 2.1. The M0 layer refers to the system in the real world. A model represents those systems at level M1 . This model conforms to its metamodel defined at level M2 and the metamodel itself conforms to the meta-metamodel at level M3 . Nevertheless, OMG’s standard is currently being challenged by multilevel modeling [ 5 , 89 ]. Multilevel modeling tries to overcome the limitation of only four meta-levels by allowing an arbitrary number of meta-levels. This results in the concept of clabjet which is a model element that has properties of classes and objects. In a multilevel architecture, this dual type/instance nature makes some metamodeling facilities available at each meta-level, which can be beneficial in some situations. A key difference between a software engineer and other engineers is that the medium in which models are built is very different. Software engineers share the same medium which is the computer, while for other engineers it could be buildings, bridges, aeroplanes, and so on. This unique feature of 13 Chapter 2. Background Fig. 2.2 Overview of the elements involved in a MT. software allows automatic transformations to be defined capable of generating implementations from higher level models. This is something which is much more expensive in other disciplines. Consequently, the purpose of MDE is to make the implementation of systems as automatable as possible, achievable thanks to model transformations. 2.1.3 Model Transformations In the field of Model-Driven Engineering, a Model Transformation (MT) allows a model to be manipulated and transformed. In the same way that there is no universal definition for the concept of model, there is no universal definition for the concept of model transformation. For instance, a highly extended definition of model transformation is the one given by Kleppe et al. [ 79 ] which states that “a transformation is the automatic generation of a target model from a source model, according to a transformation definition”. On the other hand, we have tried to be more general and in [ 143 ] we state that “a model transformation is an algorithmic specification of the relationship between two or more models, and more specifically, of the mapping from one model to another”. Fig. 2.2 illustrates an overview of the main concepts involved in a model transformation. There are two metamodels and two models, both of which conform to their respective metamodels. The model transformation is defined with respect to the metamodels and is executed on specific models. As we have said, this is extensible to other domains (metamodels) and models or there may be only one metamodel (this would be the case of inplace model transformations). Model Transformations can be classified according to different criteria: 14 2.1 Model-Driven Engineering •Directionality :Unidirectional transformations are those that are defined and executed in just one direction, i.e., establishing which is/are the source and target metamodel(s) and model(s). Typical unidirectional MT languages are ATL [ 75 ], QVT Operational [ OMG ], etc. Bidirectional [ 68 ] the transformation can be executed either forwards (from source to target) or backwards (from target to source). The most extended bidirectional MT language is QVT Relations [ 58 ]. Direction neutral transformations are those for which the direction has not been established and they only define the relationship between the metamodels/models. An example of this kind of MT is what we call transformation models and are defined by means of OCL expressions in [69]. •Metamodels involved in the MT :Exogenous transformations are transformations defined between different metamodels while endogenous transformations are transformations between models that conform to the same metamodel. •Number of Models Involved :Out-place MTs create model elements in a model based on properties of another model. Contraryly, inplace MTs only involve one model being evolved. Note that exogenous transformations are always out-place and that in-place transformations are a type of endogenous transformation. •MT Language : There are different types of MT languages: declarative, imperative and hybrid which combine declarative and imperative parts. •Type of MT : Text artifacts might be involved in one of the domains of model transformations which result in a further two kinds of MTs. Modelto-Model transformations where only models are involved as input(s) and output(s), Model-to-Text transformations where text artifacts are generated from a model or a set of models, and Text-to-Model transformations where models are created from text artifacts/repositories—for instance, MTs that reverse engineering code into models. 15 Chapter 2. Background Listing 2.1 Example of Linda pseudocode. 1 write ( " circumference " , 3 , 47 , 53) 2 write ( " circumference " , 7 , 20 , 21) 3 write ( " square " , 5 , 20 , 30) 4 read ( ? , ? , 20 , ?) A particular kind of MT is the high-order model transformation (HOT) where a model transformation is itself a model or a so-called transformation model [ 15 ]. HOTs conform to a metamodel which is part of the model transformation language’s definition, i.e., they are transformations which have other transformations as input and/or output. 2.2 Linda Coordination Language Linda is a coordination model that uses a shared memory space as the only mean of communication among parallel processes. This model is implemented as a coordination language for parallel and distributed processing. It was first proposed by David Gelernter at Yale University in the mid-1980s [ 51 ] and in recent years there has been a resurgence in interest in it, particularly with regard to Java implementations of Linda [148, 149]. In distributed memory systems, such as networks of workstations, the shared memory, which is called tuple space, is usually distributed among the processing nodes. Independent from the implementation strategy employed, the tuple space is structured as a bag of tuples. An example of a tuple with four fields is (“circumference”, 3, 47, 53) , where 3 is the radius, and 47 and 53 indicate the position (x and y coordinates) of the circumference represented by this tuple. Another example is (“square”, 5, 20, 30) which represents a square whose side length is 5, whose position on the X-axis is 20 and 30 on the Y-axis. Linda provides operations, called primitives, to place tuples into tuple spaces ( write operations) and to retrieve tuples from them ( read operations). Read operations can be either blocking or non-blocking. A piece of Linda code with examples of these operations is shown in Listing 2.1. 16 2.3 Model Transformation Contracts. Tracts The specification of the tuple to be retrieved makes use of an associative matching technique whereby a subset of the fields in the tuple have their values specified. In our example, the read operation defines a pattern that matches all the tuples whose position on the X-axis is 20. Therefore, the tuples written in the second and third lines are retrieved. As a coordination language, the Linda primitives were conceived to be integrated with a programming language, which is called the host language. There are different Linda implementations for different host languages such as C-Linda [ 4 ] for C and JavaSpaces [ 96 ] for Java. Listing 2.2 shows a piece of Java code that, using the Linda implementation JavaSpaces, is able to read and write circumferences into the tuple space. For representing the circumferences a class implementing the Entry interface is needed (lines 2–13). The main program, after the configuration of the tuple space (lines 21–23), writes two circumferences into the tuple space (lines 25-29) and then reads the one that has radius 3 (lines 31-34). 2.3 Model Transformation Contracts. Tracts 2.3.1 Specifying Transformations with Tracts Tracts were introduced in [ 56 ] as a specification and black-box testing mechanism for model transformations. They provide modular pieces of specification, each one focusing on a particular transformation scenario. Thus each model transformation can be specified by means of a set of Tracts, each one covering a specific use case—which is defined in terms of specific input and output models and how they should be related by the transformation. In this way, Tracts allow partitioning the full input space of the transformation into smaller, more focused behavioral units, and to define specific tests for them. Commonly, what developers are expected to do with Tracts is to identify the scenarios of interest (each one defined by a Tract) and check whether the transformation behaves as expected in these scenarios. In a nutshell, a Tract defines a set of constraints on the source and target metamodels, a set of source-target constraints, and a test suite, i.e., a collection 17 Chapter 2. Background Listing 2.5 Test result for the Families2Persons example. 1−−−−−−−−−−−−−−−−−−−−−−−−−−− 2−− R e s u l t s f o r src_model001 3−−−−−−−−−−−−−−−−−−−−−−−−−−− 4 C1 :SRC_oneDaughterOneSon :OK 5... 6 C4 :SRC_TRG_FatherSon2Male :KO 7 Instances of src_model001 violating the constraint 8Set(Member001 ,Member002 , . . . ) 9... output model pairs. An example report for the Families2Persons example for an input test model called src_model001 produced by the TractsTool [ 26 , 21 ] is shown in Listing 2.5. This model is composed of 1250 model elements (250 families, each one with one father, one mother, one son and one daughter), and was generated by an ASSL [54] procedure (cf. [26]). In order to fix the transformation implementation to fulfil all constraints, the alignments between the transformation rules and the constraints are crucial in order to track the actual faults in the transformation rules from the observed constraint violations. While for the given example this may be achieved by just looking at the constraints and the rules (actually R 2misses the white space in the String concatenation), for larger examples automation support is essential due to the complexity of model transformations. Even in this example the alignment between the rules and the constraints is not trivial, and this is precisely where our proposed approach comes into play. 24 Chapter 3 Parallel Out-place Model Transformations A wide range of different transformation languages already exists, each of them comprising different characteristics [ 121 ]. However, the increasing size and complexity of models are challenging the existing model transformations languages and engines, whose performance and scalability need to be significantly improved as the industry is progressively adopting model-driven techniques [83]. In fact, current model transformation engines are mostly based on sequential and in-memory execution strategies and thus they have limited capabilities to transform very large models in acceptable time. This hinders the benefits of using models and model transformations in different application domains that use huge models, including biology, medicine and sociology. At the same time, parallel computing has become increasingly important as chipmakers are putting more and more processor cores on individual chips— which are mainly wasted if sequential engines are used. Similarly, distributed algorithms are gaining attention as computer communications are getting much faster, cheaper and more reliable, and the Cloud is taking over. 25 Chapter 3. Parallel Out-place Model Transformations In this chapter we present an approach to achieve parallel and distributed execution of transformations, providing the performance and scalability required to transform very large models in distributed environments. We introduce the LinTra approach and its Java implementation, jLinTra, which are based on the Linda [ 52 ] coordination language, and the use of data parallelism to achieve parallelization. LinTra offers concurrency and distribution mechanisms using the well known principles of separation of concerns [ 42 ], permitting concurrent access to distributed data in a transparent way. In LinTra, distribution is achieved using the blackboard [ 29 ] distributed shared memory approach, which also provides an abstraction over existing Java-based data space platforms. Scalability is addressed by using data management middleware platforms to implement the blackboards, which are able to deal with very large volumes of distributed data in an efficient way. Finally, the master-slave pattern [29] is used for achieving data parallelism. The contribution of this chapter is fourfold. First, we present a novel Java-based execution platform called jLinTra for the parallel execution of out-place transformations that may also be used as a target for high-level transformation language compilers. Second, we provide a mapping of model transformation concepts into the LinTra framework. In particular, we define the representation of models and metamodels and how those models are stored over a set of machines using a blackboard approach. Third, we demonstrate the performance and scalability of this platform by reporting the results of running a model transformation test set using different Java middleware platforms for presenting models, and by comparing it against several state-ofthe-art model transformation engines, including sequential and parallel ones. Finally, we discuss some implementation solutions for dealing with models that do not fit in memory or which are distributed over several machines, using highly distributed, scalable NoSQL databases [ 120 ] as underlying technologies. The structure of this chapter is as follows. Section 3.1 introduces the LinTra framework, how model transformations are embedded in this framework and jLinTra’s features for out-place transformations. Then Section 3.2 focuses on the execution of transformation chains where the output of a transformation is the input of the following. In Section 3.3 jLinTra is evaluated by using several 26 case studies where we investigate the execution performance of LinTra with respect to different Java-based middleware platforms used to store and retrieve models, and we compare jLinTra with other execution engines. Finally, in Section 3.4 we discuss related work and Section 3.5 summarizes the chapter. 27 Chapter 3. Parallel Out-place Model Transformations 3.1 LinTra and its Java Implementation jLinTra LinTra is a framework that allows the parallel execution of out-place model transformations, regardless of whether the models are located in a single machine or distributed over a set of nodes. We base our transformation approach on Linda [ 52 ], the mature coordination model for parallel processes that we introduced in Section 2.2. Fig. 3.1 shows the architecture of the LinTra approach. For running transformations on such architecture, we explored how model transformations fit into the Linda framework and we made the distinction between two independent layers. The middleware layer contains the concrete Linda implementation, while the jLinTra layer on top of it comprises the model transformation written in Java and the models and metamodels representations. We also decided how trace links are encoded to allow for efficient retrieval, and how the transformation rule execution is distributed over the available computational resources (machines, cores, etc.). InputModels (jLinTra format) OutputModels (jLinTra format) Transformation (jLinTra) ThreadNThread1 Thread2… InputMetamodels (jLinTra format) OutputMetamodels (jLinTra format) conforms to conforms to jLinTra BackendConnector (BlackboardInterface) Hazelcast OracleCoherence GigaSpaces XAP Ehcache … Model TS Linda TS Fig. 3.1 LinTra architecture 28 3.1 LinTra and its Java Implementation jLinTra 3.1.1 Linda and Existing Implementations There is a wide variety of pure Linda implementations written in different languages such as JavaSpaces [ 96 ] and TSpaces [ 91 ] in Java, C-Linda [ 4 ] in C, Rinda [127] in Ruby and PyLinda1in Python. In addition, there are other mature software solutions for data management based on in-memory data grids (IMDG) or on distributed caches that are not used as Linda implementations but that provide similar functionality and even more. They are a specific kind of NoSQL databases called key-value caches. In particular, they ( i )scale-out because every node (computer) adds its CPU and RAM to the cluster which can be used by all the nodes; ( ii )can store big data and enable fast access to it as it is manipulated in main memory; ( iii )permit dynamic scalability as nodes can dynamically join other nodes in a grid (cluster); ( iv )enable elastic main memory as every node adds its own RAM memory to the cluster’s memory pool; ( v )implement fault-tolerance mechanisms without data loss, and ( vi )implement a programming model to access the cluster as if it was a single machine. Some of these data management solutions are Hazelcast, Oracle Coherence, GigaSpaces XAP, Ehcache and Infinispan, to mention a few. In Section 3.3 we present a brief description for each particular solution we have worked with. 3.1.2 Building a Common Interface: The Blackboard Metaphor According to Linda [ 52 ], the data storage is called tuple space (or blackboard). This tuple space can be thought of as a distributed shared memory that follows the Blackboard architecture pattern [29]. Different Linda implementations provide different interfaces to access the blackboard. To make the jLinTra model transformations independent from the concrete Linda implementation, we have defined an interface reusing the Linda primitives to read and write elements, adapting them to our needs. In particular, we use identifiers for referring to model elements, and thus we provide specific methods to read and write them using these identifiers. 1https://code.google.com/p/pylinda/ 29 Chapter 3. Parallel Out-place Model Transformations Fig. 3.2 LinTra interface. We also permit partitioning the tuple space in areas. Finally, the interface provides methods to allow users to search for elements in the blackboard. Fig. 3.2 shows the interfaces we have defined to access the blackboard. Following the Linda approach, the jLinTra implementation is not aware of how the distribution is done, nor the synchronization mechanisms needed for providing concurrency to the solution. Both concepts are transparent to the jLinTra model transformations, and the middleware layer takes care of them. Focusing first on interface IBlackboard , we assume that the blackboard is composed of different areas (of type IArea ) having each one an specific access policy. LOCK_TO_READ policy means that no more than one thread can access at the same time the area to read (or read and delete) an element, thus the thread accessing takes the token while the rest of the threads trying to read are blocked until the token is released. LOCK_TO_WRITE policy implies that at most one thread can access the area to write an element simultaneously. ALWAYS_LOCK combines the two previous policies whereas NEVER_LOCK means that all threads can freely access the area. These policies are internally managed by the LinTra platform, depending on the kind of transformation (e.g., regular or chained) and also to implement some internal processes, such as the assignment of 30 3.1 LinTra and its Java Implementation jLinTra identifiers—for which a private area in the blackboard is used. Users do not need to care about these policies. Interface IBlackboard is shown in Listing 3.1. It offers methods to create, clear and destroy areas dynamically. It also offers the possibility to obtain a collection with the areas available with getAllAreas() . Method size(IArea area) returns the number of elements stored in the given area given and size() returns the number of elements stored in the blackboard (which is equivalent to the sum of the size of all the areas belonging to it). clear() deletes all the areas from the blackboard and their elements. Listing 3.1 IBlackboard interface 1public interface IBlackboard extends Serializable { 2public enum Policy {NEVER_LOCK ,LOCK_TO_READ ,LOCK_TO_WRITE , ,→ALWAYS_LOCK } ; 3public IArea createArea (String name ,Policy p) ; 4public boolean clearArea(IArea area ) ; 5public boolean destroyArea(IArea area ) ; 6public Collection<IArea>getAllAreas ( ) ; 7public int size ( ) ; 8public int size(IArea area ) ; 9public boolean clear ( ) ; 10 } In our approach, we consider that every element stored in the tuple space is an object with a unique identifier of type String , and thus, it must implement the interface IdentifiableElement shown in Listing 3.2. Listing 3.2 IdentifiableElement interface 1public interface IdentifiableElement extends Serializable { 2public String getId ( ) ; 3public void setId (String id) ; 4} Regarding the interface IArea that is presented in Listing 3.3, its method read(String id) reads without deleting and returns the element with identifier id or null if the element does not exist in the area. Method readAll(Collection<String> ids) reads without deleting and returns the collection of elements whose identifiers are contained in ids , while method read(int n) reads n elements from the area and method read(ISearch searchMethod) receives as parameter 31 Chapter 3. Parallel Out-place Model Transformations a search method implementing interface ISearch —which requires to have a method called search(IArea) . This search method establishes the criteria for which elements are retrieved from the area. Equivalent to the read methods, the take methods have a similar behavior with the only difference that they delete the elements from the area. Methods write(IdentifiableElement elem) and writeAll(Collection<IdentifiableElement> elems) write the given elements into the area, size() returns the number of elements in the area and clear() removes all the elements stored in the area. Listing 3.3 IArea interface 1public interface IArea extends Serializable { 2public IdentifiableElement read(String id) ; 3public Collection<IdentifiableElement>readAll(Collection<String>ids ,→) ; 4public Collection<IdentifiableElement>read(int n) ; 5public Collection<IdentifiableElement>read(ISearch searchMethod) ; 6public IdentifiableElement take(String id) ; 7public Collection<IdentifiableElement>takeAll(Collection<String>ids ,→) ; 8public Collection<IdentifiableElement>take(int n) ; 9public Collection<IdentifiableElement>take(ISearch searchMethod) ; 10 public boolean write (IdentifiableElement elem) ; 11 public boolean writeAll (Collection<IdentifiableElement>elems ) ; 12 public int size ( ) ; 13 public boolean clear ( ) ; 14 } To illustrate how the previously mentioned search method can be implemented and how it works, Listing 3.4 provides a possible implementation. Assuming that identifiers represent integers, it obtains the set of elements whose identifiers are in the range given by min and max . Another possible implementation of the search method could retrieve elements by type. This decision may have an impact on the performance. We recommend to keep the search method as simple as possible—i.e., avoid unnecessary accesses to the area and complex computations. For clarity, in all the listings we have omitted that the methods throw BlackboardException when an Exception occurs. 32 3.1 LinTra and its Java Implementation jLinTra Listing 3.4 Search method 1public class SearchByIdRange implements ISearch { 2int min ,max ; 3public SearchRange(int min ,int max ) { 4this .min =min ;this .max =max ; } 5public Collection<IdentifiableElement>search(IArea area ) { 6 List<IdentifiableElement>elems = 7new LinkedList<IdentifiableElement >() ; 8for (int i=min ;i<=max ;i++){ 9 IdentifiableElement e =area .read(Integer .parseInt (i) ) ; 10 i f (e!= null ) { elems .add (e) ; } 11 } 12 return elems ; 13 } 14 } 3.1.3 Models and Metamodels in LinTra In order to represent metamodels and models in Java so that they can be used by jLinTra, we need to identify the mappings between the metamodeling concepts and Java. In our approach we have worked with Eclipse Modeling Framework (EMF) models and thus we have built a bridge between Ecore (i.e., the metamodeling language of EMF) and jLinTra. Every class in an Ecorebased metamodel is mapped to a Java class that implements the Serializable and IdentifiableElement interfaces. Attributes belonging to the Ecore classes become Java fields, as well as the references that store the identifiers of the target element(s). As we shall later see, this is an important design decision in order to be able to write and execute transformation rules more independently than using explicit object pointers in Java. However, it also introduces additional challenges, e.g., when it comes to navigating between objects. Single inheritance is represented by Java inheritance and multiple inheritance is simulated with single inheritance and interface implementations. Java classes also need a constructor that receives as arguments the values of the attributes and references, and the getter and setter methods for all its fields. Models in jLinTra are composed by the set of Java objects that instantiate the Java classes. Note that, although we have implemented the bridge between Ecore and jLinTra, we do not provide support for all the features of EMF such as its operations (e.g. eContainer(), eContent(), etc.). 33 Chapter 3. Parallel Out-place Model Transformations 3 Collection<IdentifiableElement>elems ) { 4 List<IdentifiableElement>out = 5new LinkedList<IdentifiableElement >() ; 6for (IdentifiableElement e :elems ) { 7i f (einstanceof Article) { 8 Article a = ( Article)e;out .add (article2Section(a) ) ; 9} 10 else i f (einstanceof Author) { 11 Author a = ( Author)e;out .add (author2Paragraph(a) ) ; 12 } 13 } 14 return out ; 15 } 16 private Section article2Section (Article a) { 17 return new Section( 18 TraceFuntion .create(a.getId ( ) , Rules .Art2Sec) , a.getTitle ( ) , 19 TraceFunction .resolveAll (a.getAuthorsIds ( ) , RuleNames .Auth2Par ) ) ; 20 } 21 private Paragraph author2Paragraph(Author a) { 22 return new Paragraph( 23 TraceFunction .create(a.getId ( ) , Rules .Auth2Par ) , a.getAuthor ( ) ) ; 24 } 25 } Note as well the use of the TraceFunction class not only to store the traces but also to resolve the references to other elements regardless of whether they have already been transformed or not. This is how relationships between transformation rules are naturally managed in our approach. 3.1.7 Distributed Models One of the benefits of the Linda approach lies on its independence from data size and distribution, given that it uses a shared-memory architecture. Such separation of concerns is also key in LinTra, which then permits dealing with model storage and distribution in an independent manner. In fact, our architecture clearly separates those aspects (see Fig. 3.1). We have studied different technological solutions for implementing the data management layer. In the first case we have one in-memory solution, when the models fit into the computer memory, and we want just to use the parallel features of jLinTra. It uses the Java HashMap collection type to implement the Tuple spaces (i.e., the blackboard) and all its areas. This is the 40 3.1 LinTra and its Java Implementation jLinTra technological solution we have used to compare the performance of jLinTra with existing model transformation engines (ATL, QVT-O, ETL, etc.) since all of them only support in-memory implementations. Our approach also supports dealing with models that do not fit in memory, or that are distributed over several machines, using in-memory data grids that can be connected to distributed, scalable NoSQL databases [ 120 ] as underlying technologies. Examples of NoSQL databases include Cassandra, neo4j, FoundationDB and MongoDB. These new database technologies achieve scalability through horizontally distributing data, and replace normalized data models, strong data consistency guarantees, and SQL queries with schema-less data models, weak consistency guarantees, and proprietary APIs. We tested five different commercial solutions for key-value in-memory data grids and/or caches that permit distribution and connection to NoSQL databases: •Oracle Coherence2is an in-memory data grid from Oracle. •Hazelcast3is an in-memory open source data grid based on Java. •Ehcache4is an open source distributed cache. •GigaSpaces XAP (eXtreme Application Platform) 5 is an in-memory computing software platform provided by GigaSpaces. •Infinispan6 is a open source data grid platform and key-value data store. Table 3.2 shows the results of running the same jLinTra transformation on different Java-based data management solutions for several models of increasing size. The number in the leftmost column indicates the number of 2 http://www.oracle.com/technetwork/middleware/coherence/overview/ index.html 3http://hazelcast.com/ 4http://ehcache.org/ 5 http://www.gigaspaces.com/xap-in-memory-computing-event-processing/ Meet-XAP 6http://infinispan.org/ 41 Chapter 3. Parallel Out-place Model Transformations No. elements HashMap Coherence Hazelcast Ehcache XAP Infinispan 0.1×1060,138 2,133 19,654 0,299 8,757 0,189 0.2×1060,138 2,971 39,335 0,424 16,542 0,313 0.5×1060,385 8,298 99,740 0,276 38,796 0,877 1.0×1060,969 16,164 300,105 0,795 78,810 1,688 1.5×1061,732 26,701 451,701 1,817 121,527 3,094 2.0×1063,034 35,561 590,760 4,431 159,862 5,353 2.5×1065,105 44,142 724,658 11,811 177,273 6,536 3.0×1066,990 56,144 870,705 14,280 −9,527 3.5×1067,975 75,321 1016,626 20,329 −13,202 Table 3.2 Data management middleware comparison model elements in the input model. Since we are only interested in how the read and write operations perform, we have applied the identity transformation (more precisely, we used the IMDb Movie Database transformation presented in Section 3.3.2). All execution times are shown in seconds. Cells with a dash “ − ” mean that the model cannot be transformed due to a memory allocation problem. Among them, Infinispan was the one that offered more features. In addition, its integration with the LevelDB database 7 was easy and provided us with all the functionality we required for implementing persistence (i.e., disk storage) and distribution for large models. Although a detailed performance comparison between the different NoSQL databases is out of scope for this work and therefore left for future work, our initial experiments show that the key-value data stores are the solutions which perform best and they all present similar performance. Hence, in this thesis we have used Infinispan (with LevelDB as persistent database) to implement the blackboard layer of jLinTra in case an in-memory solution was not enough to store and transform models. Otherwise, the Java HashMap implementation of the blackboard is used. 7http://leveldb.org/ 42 3.2 Model Transformation Chains 3.2 Model Transformation Chains As more complex problems are tackled in industry, the number of transformations involved in MDE solutions has increased. In fact, most real-world MDE scenarios do not involve a single transformation from one source model to one target model, but multiple model transformations organized in chains, with the output of some transformations serving as input to others [ 146 ]. Thus, smaller transformations can focus on specific concerns, are easier to develop and maintain, and together constitute a more modular, extensible and maintainable architecture. Integrating them into chains is no longer an issue, with domain specific languages for specifying and executing model transformation chains [ 118 ]. The number of transformations in a chain depends on the domain and in the particular application, but they can normally range between 5 and 12 in industrial projects [ 48 ]. Hence the importance of considering the parallel execution of transformation chains. Given the architecture of our platform, implementing the parallel execution of chained transformations is rather natural. It was a matter of extending our approach with ( i )synchronization mechanisms between the transformations, and (ii)pairs of element identifiers. Synchronization between the different transformations is naturally implemented by the use of the master-slave pattern and by the way in which jobs are assigned to slaves. Thus, the slaves in charge of implementing the second transformation will wait until they have jobs to do. These will be generated by the master of the second transformation as soon as the output elements of the first transformation are produced. Unlike regular model transformations—where a complete source model is available at the beginning of the transformation—transformation chains involve streaming models [ 37 ]— i.e., those whose elements are not all present in disk or memory, but rather arrive as one or more continuous data streams—that cause dependencies when a rule needs to access an element that is not available yet. jLinTra uses the synchronization mechanisms that Java provides. When a slave finds a dependency, it invokes the wait() method and all the resources are released for the use of other slaves until the master invokes the notify() method informing 43 Chapter 3. Parallel Out-place Model Transformations that there are new elements are available in the model. The master and slaves of a transformation know when the model has been totally loaded because an EOF flag indicates when all the elements are already available. Regarding the pairs of element identifiers, we previously mentioned that model elements have unique identifiers, which were used to implement the traces in an efficient manner by means of a bidirectional function. For that, the identifiers of the output elements had a special form too (see, e.g., Table 3.1). In order for these elements to become the input elements of another transformation, while still maintaining the tracing information, we need to assign them other identifiers, which allow them to act as source elements of the next transformation. Thus, our transformations always generate two identifiers for all output elements. The one explained in Section 3.1.4 plus a new one representing an integer which is the one used in case the target model needs to be used as source of another transformation. A Hashtable is also generated with the two identifiers, in order to optimize the search for elements using their first identifier. Such a table is also stored in the blackboard, as another artifact of the transformation itself. 3.3 Evaluation and Performance Analysis In this section, we discuss the performance and scalability of jLinTra by performing a set of case studies [ 90 ] based on a set of exemplar transformations. The discussion follows the guidelines for conducting empirical explanatory case studies by Roneson and Hörst [ 119 ]. Detailed information on the metamodels and input models used in these examples (number of elements, file size on hard disk, etc.), and on the transformations themselves, is available from our project’s website. 3.3.1 Research Questions We have defined two research questions that compare the performance and scalability of jLinTra with respect to state-of-the-art sequential transformation engines and emerging parallel transformation engines, one about the parallel 44 3.3 Evaluation and Performance Analysis execution of transformation chains, and a final one about the effect on the performance when models are stored in disk, and not in memory. More specifically, we aimed at answering the following research questions (RQs): RQ1. How does jLinTra perform compared to existing sequential execution engines? One main goal of jLinTra is to improve the performance and scalability of current sequential execution engines. Thus, we evaluate the achieved speedup compared to such approaches. RQ2. How does jLinTra perform compared to other emerging parallel execution engines? jLinTra is also compared against other existing parallel execution engines w.r.t. performance and scalability. RQ3. How does jLinTra model transformation chains perform? The performance of running a model transformation chain in jLinTra is compared to the performance of running the same transformation sequentially one after the other. RQ4. How is the performance of jLinTra affected when models do not reside in memory? jLinTra provides an abstraction from data management middleware solutions, permitting transparent access to data independently from where it resides (in-memory, on-disk, distributed). It is important to evaluate the costs of dealing with models that do not reside in memory (because of their size or their origin) and how this affects the performance of jLinTra model transformations in terms of speed degradation, scalability, etc. 3.3.2 Case Studies This section describes five examples that have been used to evaluate jLinTra and compare it with other model transformation languages and engines. These examples were chosen to capture different relevant features of model matching, navigation and element traceability involved in most commonly used model transformations. 45 Chapter 3. Parallel Out-place Model Transformations Fig. 3.4 DBLP Metamodel. DBLP—Model queries The first example uses the complete DBLP database 8 as source model. It has 5 , 654 , 916 elements when stored as a model. Its metamodel is shown in Fig. 3.4. This is an example of model queries over a large model. This case study defines four different transformations, covering four types of queries which exercise different accesses to model elements. Those transformations 8http://dblp.uni-trier.de/xml/ 46 3.3 Evaluation and Performance Analysis Fig. 3.5 AuthorInfo Metamodel. extract information using the AuthorInfo metamodel as transformation target (Fig. 3.5). • Find all the authors that have published at the International Conference on Model Transformation (ICMT) conference and their number of papers. • Find if those ICMT authors are still publishing (active) or if they are inactive (active means that they have published in the last 5years). • Find the conferences where people who stopped publishing at ICMT are now publishing. • Find all journals where people who are actively publishing at the Information & Software Technology (IST) journal (i.e., have published something in the last 10 years) are also publishing. IMDb Movie Database—Model copy and traversal The second example uses the “Movie Database” (IMDb) proposed in the Transformation Tool Contest (TTC) 2014 [ 70 ], whose metamodel is shown in Fig. 3.6. The first transformation is the identity, which checks how fast the complete model graph can be traversed and copied. The second one copies all the elements in the input model (movies, actors and actresses—3 . 5million elements) and finds all pairs of people who played together in at least in three movies. This second transformation involves navigating the source elements 47 Chapter 3. Parallel Out-place Model Transformations Fig. 3.6 IMDb Metamodel. before transforming the elements (this model transformation uses same source and target metamodels). In this case we run the transformations over a set of 9 different models, emulating different sizes of the database model to check how different model transformations engines scale up (from 100 , 000 elements to the complete model with 3.5million elements). Java Refactoring—Model modification This case study is taken from the 2015 edition of TTC 9 . This is an example of program transformation rules for code refactoring, where all the @Singleton annotations are removed from Java programs and their implicit behavior is replaced with the actual Java code they represent. More precisely, given an annotated Java program, all classes annotated with the @Singleton keyword must be modified as follows: the annotation is removed; all constructors are set to private; a public and static variable named instance whose type coincides with the class type is created; and a getInstance method is created for each constructor that initializes the variable instance in case it was not already initialized, and then returns it. Each getInstance method has the 9http://www.transformation-tool-contest.eu/solutions_refactoring.html 48 3.3 Evaluation and Performance Analysis Listing 3.10 Code to be refactored 1 @Singleton 2public class ContextDataFilter extends ViewerFilter { 3private String pattern ; 4public ContextDataFilter(String pattern ) { 5this .pattern =pattern ; 6} 7} Listing 3.11 Refactored code 1public class ContextDataFilter extends ViewerFilter { 2private static ContextDataFilter instance ; 3private String pattern ; 4private ContextDataFilter(String pattern ) { 5this .pattern =pattern ; 6} 7public ContextDataFilter getInstance (String pattern ) { 8i f (instance==null ) { 9 instance =new ContextDataFilter(pattern) ; 10 } 11 return instance ; 12 } 13 } same parameters as the corresponding constructor. This is an example where strong dependencies between the transformation rules exist. An illustrated example of a Java class annotated is shown in Listing 3.10 while Listing 3.11 shows the code after having applied the transformation. The input models are obtained from Java code using MoDISCO [ 19 ]. The Java metamodel has a total of 125 classes from which 15 are abstract, 166 relationships among them and 5 enumeration types. As source model we have selected the complete Eclipse project, containing 4 , 357 , 774 entities. In order to assess how the transformation scales up with this kind of input, we generated 11 smaller sample source models (with subsets of the Eclipse project) ranging from 100,000 elements to the complete model. Java to Prefuse Graph—Model transformations This case study is taken from the model visualization domain. Tools for the analysis of large models that use visualization techniques require efficient 49 Chapter 3. Parallel Out-place Model Transformations Fig. 3.10 Comparative chart for the IMDb-FindCouples case study. Fig. 3.11 Comparative chart for the Java Refactoring case study. The Java Refactoring transformation shows with a logarithmic scale that jLinTra beats the rest of the execution engines. It is followed by p-ATL and QVT-O—although QVT-O is not able to transform models with 3 millions of elements or more. The next best option is ETL followed by ATL-VM and ATL which present very similar results. The Java-to-Graph case study shows a weakness of LinTra. When a transformation needs to navigate through relationships, LinTra needs to access the data layer in each hop to get the corresponding element, given its identifier. In this particular case, the navigation path for the rule that 56 3.3 Evaluation and Performance Analysis Fig. 3.12 Comparative chart for the Java-to-Graph case study. transforms classes to nodes needs 1 + depthclass hops, where depthclass is the depth of the class with respect to its root package; and the rule to create the edges from attributes needs 5 + depthtype + depthabsT ypeDecl hops where depthtype and depthabsT ypeDecl are the corresponding depths of the attribute type and the class that contains the attribute with respect their root packages. As this transformation requires long navigation paths, the jLinTra performance is affected and p-ATL is slightly faster. The less successful languages are QVT-O and ETL. ATL ATL-VM QVT-O ETL p-ATL DBLPv1 1,300 2,347 7,169 467,863 1,210 DBLPv2 1,368 3,343 8,139 467,100 1,283 DBLPv3 2,518 3,186 3,656 411,477 2,549 DBLPv4 1,746 1,537 2,507 293,648 1,676 IMDb-Identity 17,350 9,754 27,367 12,311 16,486 IMDb-FindCouples 17,960 33,375 367,936*29,904 18,123 Java Refactoring 749,678 616,913 17,500 243,059 9,276 Java-to-Graph 1,334 1,179 3,656 5,837 0,808 Table 3.8 Average speed-up of jLinTra w.r.t. the rest of the transformation engines. 57 Chapter 3. Parallel Out-place Model Transformations Table 3.8 summarizes the results previously discussed by showing the average speed-ups for jLinTra with respect to each engine and model transformation. The speed-up for the engine Ei and the transformation Tj is computed as: speed-upij =PN n=1 time(Ei,Tj,Mn) time(jLinT ra,Tj,Mn) N N being the number of input models for which the transformation has been executed and Mn the nth model. Cells marked with an asterisk (“*”) in Table 3.8 indicate that not all the executions finished because the largest models did not fit into memory. We can conclude that jLinTra is the one that performs better in all but one case, running an average of 97 times faster than the rest of the model transformation engines in the conducted case studies. The only case in which jLinTra was beaten corresponds to its worst-case scenario, when heavy navigation through relationships is required for each element to transform. And even in this case the only engine that beat jLinTra was p-ATL, also because in this case the number of rules was large in the transformation and hence p-ATL could make use of all the machine cores. In summary, jLinTra is between 1 . 5and 749 times faster than ATL; between 1 . 5and 616 times faster than ATL-VM; between 2 . 5and 367 times faster than QVT-O; between 6and 467 times faster than ETL, and between 0 . 8and 18 times faster than parallel ATL. Results concerning RQ3. None of the engines with which we are comparing jLinTra permits the parallel execution of model transformation chains but the transformations must be executed sequentially one after the other. In our case, we can start executing the second transformation as soon as the first one produces elements. This is why we conducted this last experiment, in which we compare the performance of jLinTra executing the two transformations in order (the second one starts its execution once the first one has finished and the intermediate model is 58 3.3 Evaluation and Performance Analysis available) versus executing them in parallel (the second one starts as soon as there are elements in the intermediate model). Table 3.9 shows the comparison results. These results show that the execution times are similar no matter if the transformations are executed in parallel or not. This makes sense because LinTra follows a data-parallelism approach which means that as long as there are elements to transform available, all the cores are working on the transformation all the time. So all the computing resources are maximally used all the time. In fact, there is a very slight increase of time when the two transformations are executed in parallel (1% in average). This is due to the synchronization mechanisms needed to execute the two transformations in parallel. Nevertheless, this extra time is justified when the priority is not the overall time but having results in the output model as soon as possible. Results concerning RQ4. One of the issues we address in this chapter is the transformation of very large models that do not fit into a single machine memory. Given that all the previous models fit into our machine memory, we have created synthetic models for the IMDb case study according to the procedure described in the TTC case [ 70 ]. It explains that the synthetic models must be built by replicating N times a given pattern which has 20 elements and 32 references. In order to easily see the influence on the access time to a database and the storage latency, we decided to execute the identity transformation, which has a linear complexity. We executed the transformation on our machine until we ran out of memory space. Models with 8million of elements and less were executed using only RAM memory. Larger models started using the hard disk drive to store the parts that could not fit into memory, using Infinispan with a LevelDB database. The execution times (in seconds) obtained for the different models as well as the amount of hard disk space used are shown in Table 3.10. 59 Chapter 3. Parallel Out-place Model Transformations Fig. 3.13 Comparative chart for the IMDb-Identity using RAM memory and hard disk. Considering only the times obtained for models which needed only RAM memory and applying an interpolation process, the data fit a straight line whose equation is 11 . 729 x− 7 . 91 with a coefficient of determination ( R2 ) of 0 . 9911 ( x represents the size of the models, expressed in millions of elements). We have used that function to predict the execution times we could obtain for the models that do not fit into memory should our machine have more RAM. All the curves are depicted in Fig. 3.13 where the X-axis represents the number of model elements expressed in millions and the Y-axis represents the time taken by the transformation in seconds. Then, we have computed the speed-up between that values and the times obtained experimentally. The results for the models shown in Table 3.10 starting from the model with 10 million of elements are: 3 . 632,3 . 515,3 . 687,3 . 847,3 . 736 and 3 . 929. The average speed-up is 3 . 724 which means that the penalty introduced by the hard disk leads to executions 3.7times slower. Fig. 3.13 also shows that the disk storage solution is slower, but still linear (46 . 48 x− 107 . 08 with R2 = 0 . 999). The fact that the introduction of disk does not change the growth model of the runtime function, only changes the constants, is probably the most important aspect for RQ4. 60 3.3 Evaluation and Performance Analysis We also wanted to see the impact of using a solid-state drive (SSD) instead of a hard disk drive (HDD). We run the same experiments changing the storage medium and the results showed that the transformations were executed 1 . 5 times faster when the SSD was used (as expected). 3.3.5 Discussion Based on the reported results, let’s answer the four research questions. •Answering RQ1 . The results presented in Subsection 3.3.4 show clearly that jLinTra is always much faster than any sequential engine that we have evaluated. Of course, this is expected because concurrent solutions usually perform faster than sequential ones. •Answering RQ2 . The comparison between p-ATL and jLinTra is more interesting as both approaches execute transformations in parallel, although each one uses a different model: data parallelism in jLinTra vs. process parallelism in p-ATL (each rule is executed in one processor). The results obtained in Subsection 3.3.4 show a significant speed-up of jLinTra with respect to p-ATL in all cases but one. Analyzing these speed-ups, we can draw two conclusions. First, and as we expected, the use of navigation paths is more expensive in jLinTra than in p-ATL. This seems to be the only weakness of jLinTra with respect to p-ATL (we also outline the way in which this problem can be addressed later in Section 7.3). In every other case, jLinTra performs better. And second, the size of the input model does not seem to have a significant impact on the performance difference. •Answering RQ3 . For practical purposes, jLinTra transformation chains perform basically in the same way when they are executed in parallel as if the transformations are executed sequentially one after the other. That means that no price must be paid when data in the output model is needed as soon as possible, although the output model is not complete. 61 Chapter 3. Parallel Out-place Model Transformations •Answering RQ4 . Once the models are large enough to not fit in memory, parts of them are kept in a database in the file storage. The experimental results shown in Subsection 3.3.4 suggest that using a SSD or HDD in combination with RAM memory works well and with only a small delay (between 2 . 5and 3 . 7times slower respectively), but that all solutions (memory, HDD, SSD) scale equally. 3.3.6 Threats to Validity In this subsection, we elaborate on several factors that may hinder the validity of our results. Internal validity—are there factors which might affect the results in the context the case study? Concerning the measurement approach we used in our case study, we have to note that Eclipse is a multi-threaded application. Thus, other ongoing threads within Eclipse could affect our performance measurements. To address this issue, we stopped all additional tasks that might be automatically started, e.g., build processes. Another threat to validity is the internal representation of the models. For instance, while ATL uses standard EMF, jLinTra uses their own internal format. Thus, there may be differences on how the specifics of EMF are supported and represented. Finally, we refrained from performing example-specific low-level optimizations that would be possible on the Java code level, in order to compete with ATL and QVT-O in similar conditions. External validity—to what extent is it possible to generalize the findings for out-place transformations in general? So far, we cannot claim any performance results outside the context of the presented case study. Nevertheless, the evaluation method used in the case study can indeed be applied on other out-place transformation examples as well. Thus, replaying the presented experiments for those transformation cases should enable the possibility of reasoning about the performance of those cases as well by using the provided infrastructure available on our website. However, for transformations going beyond out-place transformations, dedicated evaluation methods and 62 3.4 Related Work infrastructures may be needed. Finally, the case study may be repeated on other hardware platforms to see, e.g., the impact of the number of cores on the performance. 3.4 Related Work With respect to the contribution of this chapter, we first elaborate on related approaches which are dedicated to storing and retrieving very large models. Second we discuss closely related work considering the performance of model transformations in general and concerning their parallel execution in particular. Third we discuss different categories of coordination languages and their relation to model transformations. Finally, we relate to other model transformation types going beyond unidirectional out-place transformations. 3.4.1 Persisting Very Large Models The scalability problems of loading large models represented by XMI documents into memory has been already recognized several years ago. One of the first solutions for EMF models is the Connected Data Objects (CDO) 13 model repository which enables to store models in all kinds of database back-ends such as traditional relational databases or emerging NoSQL databases. CDO supports the ability to store and access large-sized models due to the transparent loading single objects on demand and caching them. If objects are no longer referenced, they are automatically garbage collected. There are also several projects for storing very large EMF models, like MongoEMF 14 and Morsa [ 45 , 46 ]. Both approaches are built on top of MongoDB. Furthermore, graph-based databases as well as map-based databases are also exploited for model storage such as done in Neo4EMF [ 9 , 59 ] where also different unloading strategies for partial models are explored [ 40 ]. In [ 35 ], Clasen et al. elaborate on strategies for storing models in a distributed manner by horizontal and vertical partitioning in Cloud environments. A similar idea is explored 13http://projects.eclipse.org/projects/modeling.emf.cdo 14http://code.google.com/a/eclipselabs.org/p/mongo-emf 63 Chapter 3. Parallel Out-place Model Transformations in [ 41 ] where different automatic partitioning algorithms are discussed for graph-based models. Compared to these existing approaches, we use standard data management solutions for storing unstructured information and a Linda-based approach for organizing and accessing the data as we have discussed in Section 3.3. 3.4.2 Transforming Very Large Models Several lines of research consider the transformation of large models. In this paper, we focus on out-place model transformations running in batch mode or streaming mode. However, to deal with large models, orthogonal techniques may be applied as well. Especially, two scenarios have been discussed in the past in the context of speeding-up model transformation executions, which benefit from alternative execution strategies. First, if an output model already exists from a previous transformation run for a given input model, only the changes in the input model are propagated to the output model. Second, if only a part of the output model is needed by a consumer, only this part is produced while other elements are produced just-in-time. For the former scenario, incremental transformations [ 77 , 114 , 134 ] have been introduced, while for the latter lazy transformations [138] have been proposed. Another interesting line of research for executing transformations in parallel is the work on critical pair analysis [ 66 ] from the field of graph transformations. This work has been originally targeted to transformation formalisms that do have some freedom for choosing in which order to apply the rules. Rules that are not in an explicit ordering are considered to be executed in parallel if no conflict, e.g., add/forbid conflict (one rule is producing an element which blocks the execution of another rule) or delete/use conflict (one rule is deleting an element which is required to exists for the execution of another rule), is statically computed. However, execution engines follow a pseudo-parallel execution of the rules. But the general notion of critical pairs may be also a valid input for distributing transformation rules. In particular, having nonconflicting transformation rules allows for distributing them without having negative side-effects. 64 3.4 Related Work The performance of model transformations is now considered as an integral research challenge in MDE [ 83 ]. For instance, Amstel et al. [ 144 ] considered the runtime performance of transformations written in ATL and in QVT. In [ 151 ], several implementation variants using ATL, e.g., using either imperative constructs or declarative constructs, of the same transformation scenario have been considered and their different runtime performance has been compared. However, these works only consider the traditional execution engines following a sequential rule application approach. One line of work we are aware of dealing with the parallel execution of ATL transformations is [ 35 ] where Clasen et al. outlined several research challenges when transforming models in the cloud. In particular, they discussed how to distribute transformations and elaborated on the possibility to use the Map/Reduce paradigm for implementing and distributing model transformations which has been realized in a follow-up work [ 10 ]. In addition, Tisi et al. [ 137 ] present a parallel transformation engine for ATL. This implementation is used as reference in the evaluation section (cf. Section 3.3) for parallel model transformation engines. 3.4.3 Coordination Models and Languages A wide variety of models, formalisms and mechanisms were defined in the 90’s for describing concurrent and distributed computations based on the concept of coordination [ 52 ]. The purpose of such models and their corresponding languages was to explicitly deal with the concurrency of cooperation among very large numbers of possibly heterogeneous active entities that comprise a single application, and that can live in distributed settings. There are different approaches to coordination, which can be broadly classified in data-driven and process-driven [109]. From the range of coordination languages available, we realized that the execution of transformation rules mainly depends on the available data in the trace and output models. Thus, rule executions seem to be mostly data dependent. Therefore, we decided to use a data-driven coordination approach instead of a process-driven one (such as the one used for p-ATL, in which each process takes care of a rule [ 137 ]). From the data-driven proposals, we 65 Chapter 4. Parallel In-place Model Transformations This chapter is structured as follows. Section 4.1 shortly introduces our reference non-recursive in-place semantics. Section 4.2 shows how LinTra realizes its in-place semantics, while Section 4.3 illustrates the benefits of parallel in-place transformations. Finally, Section 4.4 discusses related work before we summarize the work in Section 4.5. 72 4.1 Background 4.1 Background In-place transformations specify how the input model evolves to obtain the output one, i.e., how the input model has to change. There are two kinds of inplace model transformation strategies, non-recursive and recursive, depending on whether recursive matching takes place or not. By recursive matching we understand that the matches of rules are not solely computed based on the initial input model but on the current model state which probably has been modified by previous application of rules. This is the typical strategy followed in graph or rewriting systems, where a set of rules modifies the state of a configuration of objects (representing the model) one-by-one. Thus, after the application of each rule, the state of the system is changed, and subsequent rules will be applied on the system on this new state. Therefore, the transformation navigates the target model, which is continuously updated by every executed rule. Regarding non-recursive matching, it shares some characteristics with out-place transformations. In this strategy, there is one input model which is used to directly compute the output model without considering intermediate steps. We chose to follow a non-recursive approach for the LinTra in-place mode. Our decision was also inspired by the ATL refining mode [ 136 , 147 ], used to implement in-place transformations. ATL supports both out-place and in-place modes. In both execution modes, source models are read-only and target models are write-only. This is an important detail that significantly affects the way in which ATL works in refining mode. Indeed, ATL in-place mode does not execute transformations as these are executed in graph or rewriting systems, as explained in detail in [ 141 ]. Thus, we follow as well nonrecursive matching in LinTra where rules always read (i.e., navigate) the state of the source model, which remains unchanged during all the transformation execution. 73 Chapter 4. Parallel In-place Model Transformations 4.2 Approach and Semantic Issues LinTra follows a non-recursive approach for executing in-place transformations, as the ATL refining mode does. In this section we discuss some semantic issues that might occur in rule-based in-place model transformations in general as they are indeed highly relevant for the parallel execution of in-place transformations. 4.2.1 Atomic Transformation Actions When executing a non-recursive in-place transformation, the first decision concerns the elements for which the transformation does not specify what to do. We could either decide to exclude them from the target model or to include them as they are. In jLinTra we decided for the second option, which implies that if we want to exclude objects in the target model, the transformation will have to explicitly remove them. Thus, after the input model is loaded, and once the transformation phase starts, an initialization phase is needed where the identity transformation is applied so that the target area contains a copy of the input model. After the model is copied, in the following we explain the three operations that may be applied to it: deletion of elements, creation of new elements, and modification of existing elements. Elements Deletion. When an element is deleted, the outgoing relationships from such element to others are deleted too, since such information is stored as attributes in the deleted element. However, the situation is different when the deleted element has incoming relationships. In such case, the information about relationships to the deleted element is stored in the attributes of other elements. In this case, we can distinguish two different semantics. Either all the incoming relationships are deleted, for which the engine needs to traverse the whole model searching for relationships pointing to the deleted element, or they are not deleted, causing dangling references and, consequently, an inconsistent model. In the former option, we need to keep track of all the deleted elements, so that the traversal is realized only 74 4.2 Approach and Semantic Issues once as the last step of the transformation. The latter option is useful in order to make the user aware that he/she is removing an element by mistake. LinTra permits both behaviors, since it is aimed at offering a flexible implementation. When the deleted element is the parent of a containment relationships, all its descendant are also deleted recursively. Elements Creation. If the developer wants to create a new element, he/she has to create the instance and set its attributes and relationships. In case of bidirectional relationships, there are two alternatives: (i) the opposite reference is created automatically, or (ii) the creation of the opposite relationship must be explicitly specified by the developer. We permit both behaviors. Elements Updates. Updating an attribute or an ongoing unidirectional relationship of an element is trivial, since the transformation only has to change the corresponding attribute of the updated element. However, there are again two choices when updating a relationship which is bidirectional, since the previous target element of the relationship would still have a relationship to the updated element unless something is done. Thus, (i) the relationship from the previous target element should be automatically removed and a new relationship from the new pointed element to the updated element should be automatically created, or (ii) the developer has to specify explicitly in the transformation that the corresponding relationships are removed and created respectively. Again, we permit both alternative behaviors. 4.2.2 Confluence Conflicts Confluence conflicts typically occur when two rules are applied to the same part of the model and they treat it differently [ 66 ]. Thus, the resulting model may vary depending on the order in which those rules are applied. The application of a rule can conflict with the application of another rule in four different ways. Let us explain them for the ATL refining mode which acts as blueprint for the LinTra in-place transformation strategy. For the explanations, let us imagine a transformation for reverse engineering Java code. 75 Chapter 4. Parallel In-place Model Transformations Update/Update . Imagine that a rule sets the public variables to private and capitalizes the name of the ones that are private. This case is not a problem for the confluence of non-recursive in-place transformations since only the source model provided by the user is read—the changes done by the rule that changes the visibility are not visible to the rule that capitalizes the names of the variables. On the contrary, if a rule sets the visibility of the variables to private and another rule sets them to public, the transformation may not be confluent. A possible way to prevent this situation is to force the precondition of the rules to be exclusive, which leads to non-overlapping matches. This was the solution adopted by ATL concerning the declarative part. Nevertheless, it is easy to fool ATL by using the imperative part, which is executed after the declarative part of the rule. Delete/Update . Suppose that a rule sets the visibility of the variables to private and another rule removes all the variables. The situation is similar to the second case we presented for the conflict Update/Update. The two rules are a conflicting pair, thus the language should prevent this situation from happening or should establish the behavior of the transformation. Again, it is possible to produce this case in ATL by using the imperative part to set the visibility and writing a declarative rule that removes the variables. Both rules are executed so that the visibility is changed and the variables are removed. As a result, the variables are not present in the resulting model. Apparently, the objects are removed in a later execution phase, after having done all the updates and creations specified in the declarative and imperative parts. Produce/Forbid . Imagine that a rule adds a variable to a class and another rule removes all the empty classes (classes with no variables) from the model. The first rule is producing an additional structure that is forbidden by the precondition of the second rule. Once again, the order in which the rules are executed influences the result. This time, if we try to implement this transformation with ATL using the imperative part of a rule to add the variables and a declarative rule to remove the empty classes, both rules are applied but the transformation does not fulfil the purpose for which it was written (since only the source model is read). As a result, the classes are 76 4.3 Evaluation removed but the newly created variables remain in the model without any container. Delete/Use . This conflict appears when a rule deletes elements that produce a match with another rule. Thus, it is the opposite case to Produce/Forbid. Depending on the order in which the rules are executed, the transformation is able to execute a higher or lower number of rules. We have illustrated the conflicts that may appear between rules and how ATL tries to solve them using non-overlapping matches, how they can be avoided or produced, and which is the final result of the execution. Enforcing to have non-overlapping rules is not the only solution; another possibility is to statically detect the conflicting rules using the critical pair analysis approach [ 99 ], and subsequently, to deal with the conflicts making use of layers which is also implicitly done in ATL by using different phases in the transformation execution. As jLinTra is realized as an internal transformation language embedded in Java, we have opted for not imposing any restriction. Thus, our solution is completely flexible with respect to rule executions. The idea is that highlevel model transformation languages (such as ATL [ 75 ], ETL [ 82 ], or QVTO [ OMG ]) are automatically compiled to jLinTra. In case that the critical pair analysis is needed, it can be done statically during the compilation process from the high-level model transformation language to LinTra. 4.3 Evaluation To evaluate our approach we performed an experimental study concerning a transformation which, in reverse engineered Java applications, removes all the comments, changes the attributes from public to private and creates the getters and setters. 77 Chapter 4. Parallel In-place Model Transformations 4.3.1 Research Questions The study was performed to quantitatively assess the quality of our approach by measuring the runtime performance of the transformations. We aimed to answer the following research questions (RQs): 1. RQ1—Parallel vs. sequential in-place transformations: Is the parallel execution of in-place transformations faster in terms of execution times compared to using the state-of-the-art sequential execution engines? And if there is a positive impact, what is the speedup with respect to the used number of cores for the parallel transformation executions? 2. RQ2—Parallel in-place vs. parallel out-place transformations: Is the parallel execution of in-place transformations faster in terms of execution time compared to using their equivalent out-place transformations? 4.3.2 Experiment Setup To evaluate our approach, we have used the same Java models we used in Section 3.3.2. We apply an extended version of the Public2Private transformation— the original one is available in the ATL Zoo [ 61 ]—that changes the visibility of every public variable to private and creates the corresponding getter and setter methods. In addition, the transformation also removes all the comments contained in the code. All artifacts can be downloaded from our website [27]. Let us show the effects of this transformation with an example. Listing 4.1 shows the Java code that declares a class called MyClass , a public attribute name and the class’s constructor. The code contains some comments too. After applying the transformation, the Java code that the model represents should look like the fragment presented in Listing 4.2. An excerpt of the code corresponding to the rules in jLinTra is shown in Listing 4.3. As stated in Section 3.1, every slave is in charge of transforming a chunk of the model. For efficiency reasons the changes are made permanent once the whole chunk has been transformed. In order to keep the temporary 78 4.3 Evaluation Listing 4.1 Code to be refactored 1public class MyClass { 2// Declaration of variable called name 3public String name ;/* This variable contains the name */ 4public MyClass () { 5/* Description @param ... */ 6... 7} 8} Listing 4.2 Refactored code 1public class MyClass { 2private String name ; 3public String getName () { return name ; } 4public void setName(String name ) { this .name =name ; } 5public MyClass () { . . . } 6} changes the structures deletedElems , modifiedElems and createdElems (lines 2, 8 and 9) are needed. We have run all our experiments on a machine whose operating system is Ubuntu 12.04 64 bits with 11.7 Gb of RAM and 2 processors with 4 hyperthreaded cores (8 threads) of 2.67GHz each. We discuss the results obtained for the different transformations after executing each one 10 times for every input model and having discarded the first 5 executions as the VM has a warm-up phase where the results might not be optimal. The Eclipse version is Luna. The Java version is 8, where the JVM memory has been increased with the parameter -Xmx11000m in order to be able to allocate larger models in memory. 4.3.3 Performance Experiments The in-place transformation described before has been implemented and executed in jLinTra and in ATL, for which we have used the EMFTVM [ 147 ]. We have also developed an out-place transformation version in jLinTra in order to compare its performance with the proposed in-place version. Table 4.1 shows in its left-most column the number of entities of the source models of 79 Chapter 4. Parallel In-place Model Transformations Listing 4.3 jLinTra transformation 1i f (ie instanceof Comment) { 2// Delete Comment 3 deletedElems .add (ie ) ; 4}else i f (ie instanceof FieldDeclaration) { 5 String modId = (( FieldDeclaration)ie ) . getModifier ( ) ; 6 Modifier mod = ( Modifier )srcArea .read(modId ) ; 7 String visibility =mod .getVisibility ( ) ; 8i f (visibility .equals(PUBLIC) ) { 9// Modify visibility 10 mod .setVisibility(PRIVATE) ; modifiedElems .add (mod ) ; 11 ... 12 // Create getters and setters 13 createdElems .add (...) ; 14 } 15 } the transformation. The second, third, and fourth columns correspond to the execution times (in seconds) obtained for ATL and jLinTra (using the in-place and out-place modes), respectively. Note that we have only taken into account the time of the execution of the transformation, meaning that we do not consider the time used for loading the models into memory, nor the time used to serialize them to the disk. The fifth column presents the speedup of jLinTra with respect to ATL. We can see that the speedup is not constant: it grows with the size of the model, reaching a value of 955 . 23 for the complete model, meaning that value that jLinTra is 955 . 23 times faster than ATL for this concrete case. Finally, column six shows the speedup of the in-place and out-place modes of LinTra, where we can see that the in-place model transformation is on average 1.81 times faster than its out-place version. We already mentioned in Section 4.2 that an initialization phase where the input model is copied to the target area is needed. However, if we moved that process to the loading phase so that both the source and target areas were loaded at the same time, we would only pay a minimum price (an overhead of 5% in the loading phase) and the performance in the transformation phase would be improved reaching a speedup of 3 . 89 w.r.t. the out-place mode and speedup of 1,195 w.r.t. ATL. 80 4.3 Evaluation ATL LinTra Speedups No. elements EMFTVM In-place (LI) Out-place (LO) LI–EMFTVM LI–LO 0.1×1062.40 0.11 0.19 21.23 1.72 0.2×10612.04 0.29 0.36 41.88 1.25 0.5×10665.06 0.73 0.98 89.06 1.34 1.0×106371.41 1.29 2.38 287.34 1.84 1.5×1061042.41 2.06 2.61 506.71 1.27 2.0×1062030.82 2.99 5.63 678.16 1.88 2.5×1062952.46 3.92 9.64 754.14 2.46 3.0×1064156.69 5.13 8.82 809.92 1.72 3.5×1065527.96 6.26 13.77 883.37 2.20 4.0×1066737.97 7.57 15.20 890.70 2.01 Complete 7238.70 7.58 17.18 955.23 2.27 Table 4.1 Execution results and speedups. Regarding the gain of in-place MTs in LinTra w.r.t. the number of cores involved in the transformation, the speedups of using only one core w.r.t. using four, eight, twelve and sixteen are 1.19,1.62,1.97,3.24, respectively. We also planned to execute and compare this transformation with the original ATL virtual machine. However, although it supports the refining mode it does not support the imperative block, which is applied in the particular transformation used in this study. Regarding the out-place transformation developed in LinTra, it explicitly specifies that all elements that are not modified must be copied, together with their properties. The out-place transformation counts on 3 , 302 lines of Java code (we generated the code for the identity transformation using Xtend 1 and adapted the corresponding code to fit the needs of the Public2Private transformation), while the in-place transformation has only 194 lines. For answering the two research questions stated above, we can first conclude that the parallel execution of in-place transformations reduces the execution time compared to using sequential execution and that the execution time can be further improved by adding more cores. Second, for typical in-place transformation problems, parallel in-place transformation executions are more efficient than executing their equivalent out-place transformations. 1https://eclipse.org/xtend/ 81 Chapter 5. Testing Model-to-Model Transformations 5.1 Matching Tables 5.1.1 Motivation and Challenges As discussed in Section 2.3, Tracts allow us to define constraints for specifying model transformations. Regarding the model transformation implementation, our approach could be applied to any MT language that uses the metamodel footprints, independently if it is a high-level model transformation language (such as ATL [ 75 ], ETL [ 82 ], QVT-O [ OMG ], etc.), or an intermediate language that will be compiled to a high-level language (such as QVT Core [ OMG ] or LinTra). For readability reasons and because it is one of the most popular languages in which model transformations are written, we have chosen ATL. Having independent artifacts for the specification and implementation of model transformations permits choosing which formalism to use for each level. However, the following questions cannot be answered without a thorough analysis of both artifact types: •Which transformation rule(s) implement(s) which constraint(s)? •Are all constraints covered by the transformation rules? •Are all transformation rules covered by the constraints? In order to establish the relation between the constraints and the rules that might make them fail, two approaches can be followed: dynamic or static. Dynamic approaches are based on a concrete model transformation execution over a model or set of models. The procedure consists of tracking the transformation process and storing information about each executed step and the specific instances. Once the transformation has finished and the failures and the objects that caused them are known, it is necessary to go backwards over the trace information stored during the transformation execution to find the errors. In these approaches, an input model needs to be available to execute the transformation, and the environment where the transformation is to be executed must be provided too. 88 5.1 Matching Tables Static approaches, on the other hand, do not make use of executions. They obtain the relation between the constraints and the rules by means of an algorithm. The only inputs for this process are the transformation implementation and the specification constraints. Dynamic approaches normally give more precise results, although, as mentioned before, they are dependent on the particular input model and transformation execution, while static ones can compute more general alignments. In this chapter, we target the challenge of finding “guilty” transformation rules following a static approach. Since there is no direct relation between the rules and the constraints (constraints are created independently of any transformation implementation), our work computes for each pair (constraint, rule) the probability that the constraint failure comes from the rule making use of the common denominator that both have: the structural elements belonging to the metamodels. It can also be considered a white-box approach, because it takes into account the internal structure and details of the tract constraints and of the transformation implementation. 5.1.2 Methodological Approach Given a set of OCL constraints (from the Tracts) and a set of ATL rules, Fig. 5.1 summarizes the commonalities between them (in the figure, relationships ≪ c2 ≫ and ≪ u ≫ stand, respectively, for “conforms to” and “uses”). There is also a direct relation between the ATL and the OCL metamodels, because the former embeds the latter. This may simplify the alignments between ATL and OCL, although it is also true that the OCL constraints and the ATL rules are written differently. First, the former impose conditions on the relationship between the source and target models, while the latter describe how the target model should be built from the elements of the source model. Second, specifications and implementations are normally written by different people, at different times, with different goals in mind, and using different styles (e.g., they may use different navigation paths to refer to the same elements, because the starting contexts are not the same, or use different OCL operators 89 Chapter 5. Testing Model-to-Model Transformations OCL Constraints ATL Rules Source Metamodel(s) Target Metamodel(s) «c2» «c2» «u» «u»«u» «u» OCL Metamodel ATL Metamodel Fig. 5.1 Heterogeneities and Commonalities between Constraints and Rules. for querying elements). Finally, there are slight differences between OCL and ATL, e.g., ATL introduces additional operations which are of particular interest for transformations and which are not available in OCL. In any case, the OCL constraints and the ATL rules make use of the same source and target metamodels. As we have seen for the Families2Persons example in Chapter 2, the same types and features are used in the specification and in the implementation of the transformation. Thus, we use these commonalities to indirectly match the constraints and the rules by matching their footprints concerning the source and target metamodels used. Our approach focuses on the construction and interpretation of the socalled matching tables with the alignments we have discussed before. Thus, our approach builds on the following steps: 1. Footprint Extraction . The structural elements (henceforth referred to as footprints or types and features) of both model transformation and constraints are extracted, as explained later in Section 5.1.3. 2. Footprint Matching . The footprints extracted in the previous step are compared for each rule and constraint. 3. Matching Tables Calculation . The percentage of footprints overlapping, so-called alignment, for each transformation rule and constraint is calculated. This information is used to produce the matching tables (cf. Section 5.1.4). 90 5.1 Matching Tables 4. Matching Tables Interpretation . The resulting tables are analyzed for identifying the guilty rules for each constraint. Guidelines for this analysis, exemplified with a case study, are described in Section 5.1.5. 5.1.3 Footprint Extraction Now we present how we extract footprints from OCL constraints and ATL rules. Constraints There are several possibilities for the footprints extraction of OCL constraints. For example, we could take into consideration all types and features that appear in the OCL expressions, just because they are mentioned. We could even assign weights to these types and features according to their number of occurrences in the constraints, giving less importance (a lower value) to those that appear less often. However, due to the nature of OCL, nesting is necessary to implement correct restrictions in order to isolate the information which is really relevant for our purposes thus, it is important to distinguish between two different kinds of elements that appear in the OCL expressions: those that we want the constraint to refer to, and those which are used for navigation purposes only. Since metamodels are graphs, OCL expressions are heavily dependent on their contexts (i.e., the starting class) [ 31 ] and also on the path used to navigate to the final type, which is precisely the one we want the constraint to refer to, i.e., starting from a specific class several navigation paths can lead to the same target class, which is the one that really matters from the constraint perspective, whereas all other classes in the navigation can be considered as mere implementation details. Thus we need to isolate the target features of the constraint from the ones used to reach it. This is why we only consider as relevant the last elements of the OCL expressions. For example, if we have Family.mother.firstName , then we will only consider mother.firstName whose footprints are Member and Member.firstName. 91 Chapter 5. Testing Model-to-Model Transformations When an OCL expression contains operations on collections, we take into account only the types inside the body of the deepest (in the sense of nesting) iterators (forAll,exists, etc.) to extract just the relevant footprints and not those used for navigation purposes only. After doing some experiments, we realized that this decision helps introduce less noise, i.e., it does not extract types which are not representative for the constraint (since they are used for navigation purposes, and not for model element transformation), what in turn contributes to the modularization and independence of the types extracted in the constraints. Similarly, primitive types and constants are not considered. Types like Integer or Boolean, or constants like true or false can appear frequently, but this does not mean that each appearance provides relevant information for locating a fault. On the contrary, taking them into consideration only introduces more confusion, when precisely our goal is to isolate those elements that are more relevant for locating the faults. Rules In this chapter we deal with ATL as proof of concept, although any transformation language based on rules and that uses OCL could be used. For each rule, we obtain the footprints in the left-hand side, right-hand side and imperative part, and build all navigation paths. Then, as in the OCL constraints, we only consider the last part of these paths. Regarding helpers, they can appear in any part of a navigation path. For this reason, when there is a helper in a path, we simply obtain the type it returns. If it is a collection type, we obtain the type of the collection. We apply the same approach for calls of ATL (unique) lazy rules and called rules. In these cases, we return the type of the first element created by these rules (since this is what ATL actually returns). With all this, the footprints extracted for the Families2Persons example presented in Section 2.3.2 are shown in Table 5.1, for each rule and constraint. 92 5.1 Matching Tables Constraint Considered Types and Features C1 Member, Family, Family.daughters, Family.sons C2 Member, Family, Female, Member.firstName, Family.lastName Female.fullName C3 Member, Family, Female, Family.lastName, Member.firstName Female.fullName C4 Member, Family, Male, Member.firstName, Family.lastName Male.fullName C5 Member, Family, Female, Family.lastName, Female.fullName Member.firstName C6 Member, Family, Male, Family.lastName, Male.fullName Member.firstName C7 Member, Person C8 Person, Person.fullName Rule Considered Types and Features R1 Member, Male, Member.firstName, Male.fullName R2 Member, Female, Member.firstName, Female.fullName Table 5.1 Footprints for the Families2Persons example. 5.1.4 Footprint Matching and Matching Tables A tabular representation (called matching tables) is used to depict the alignment between constraints and rules. We apply three different matching functions to automatically obtain the values for filling the tabular representations. Each function provides a certain viewpoint on the alignment. This allows us to interpret the results and provides an answer to the questions presented in Section 5.1.1. In these tables, rows represent constraints and columns represent rules. Each cell links a constraint and a rule with a specific value between 0 and 1. Let Ci be the set of types and features extracted from constraint i and Rj from rule j. Let |·|represent the size of a set. Matching Tables: Three Different Viewpoints The constraint coverage (CC) metric focuses on constraints. This metric measures the coverage for constraint i by a given rule j . For this metric, the value for the cell [i, j]is given by the following formula. 93 Chapter 5. Testing Model-to-Model Transformations CCi,j =|Ci∩Rj| |Ci|(5.1) Since the denominator is the number of types and features in Ci , the result is relative to constraint i and we interpret this value for rule traceability, i.e., to find the rules related to the given constraint. This is, if a constraint fails, the CC table tells us which rule or rules are more likely to have caused the faulty behavior (i.e., be “guilty"). Thus, the CC table is to be consulted by rows. The rule coverage (RC) metric focuses on rules. This metric calculates the coverage for rule j by a given constraint i . We use the RC table to express constraint traceability, i.e., to find the constraints more closely related to a given rule, and therefore it is to be read by columns. The metric is calculated as follows. RCi,j =|Ci∩Rj| |Rj|(5.2) The last metric is relative to both constraints and rules, so the RCR table can be consulted by rows and by columns. Thus, it provides information about the relatedness of both rules and constraints, without defining a direction for interpreting the values. The relatedness of constraints and rules (RCR) metric is computed as follows. RCRi,j =|Ci∩Rj| |Ci∪Rj|(5.3) The overlap between the elements extracted from the constraints and the rules gives rise to five different cases which are reflected by the previous metrics. They are depicted in Fig. 5.2 using Venn diagrams. In case (a), each element present in the constraint is contained in the set of elements in the rule: Ci⊆Rj . Consequently, the value for the CC metric is 94 5.1 Matching Tables Fig. 5.2 Possible overlaps for Ciand Rj. 1, meaning that the constraint is fully covered by the rule. The other metrics have a value lower than 1. In case (b), all the elements in the rule are contained in the elements of the constraint, Rj⊆Ci. RC metric is 1. In case (c), Ci and Rj are disjoint sets. Thus, the three metrics are 0, which means that the given constraint and the given rule are completely independent. In case (d), each metric will have a value between 0 and 1. The specific value depends on the size of the sets and on the number of common elements. Thus, the bigger the common part for Ci is, the closer to 1 the value for metric CC will be. Similarly for Rj and metric RC. Regarding the RCR metric, its value only depends on the size of the common part (for a specific size of the footprints); the bigger it is, the closer to 1 the value will be. In case (e), both constraints and rules have the same elements set, so all metrics are 1. Considering subtyping. In the three formulas presented above, we consider the intersection Ci∩Rj as the common elements present in constraint Ci and rule Rj . But we should also take subtyping into account. Its consideration is important because some OCL operators used in the Tract constraints and in the ATL rules (such as allInstances ) retrieve all instances of a certain class, as well as the instances of all its subclasses, and therefore we can have types in a constraint and in a rule that are not directly related (since they are not the same type), but are related via subtyping (when one type is a sub/super-type of the other). Thus, the fault may be due to a problem not only in a class but also in any of its superclasses. To take this into consideration, we assign 95 Chapter 5. Testing Model-to-Model Transformations a weight to the parent classes, given by the number of its structural features (attributes and references) divided by the number of features of the child class—both sets comprise the class’s own features as well as the inherited features from all its superclasses. Thus, the more similar the parent and the child are, the closer to 1 the weight is. Similarly, if the child class incorporates many new features w.r.t. the parent class, the weight assigned to the parent will be closer to 0. Setting a threshold value. Before going any further, let us explain the need for setting a threshold for cell values in the matching tables. Such a threshold is meant to establish a boundary under which alignments are ignored. It is needed to be able to disregard those situations where a constraint and a rule are minimally related, and thus should not be considered as relevant for locating the fault. Moreover, if a value in a cell is below the threshold in table RCR, then the value in the equivalent cells in the other two tables must be disregarded too, even if their value is above the threshold, to avoid considering irrelevant information. Fig. 5.3 helps explain this situation. Assume that the elements extracted from constraint Ci are a subset of the elements extracted from rule Rj , as shown in Fig. 5.3(a). In this case, the CC metric for this pair is 1. However, since the set of common elements is very small in comparison with the size of the set of rule elements, the RCR metric is also very small. Despite there being some common elements in the rule and in the constraint, it does not mean that, in this case, the rule is covering the constraint. In most cases where the set of common elements is much smaller than the set of rule elements (even if the CC metric is 1), it is normally because our metamodels are small and the same element may be present in several rules and constraints, and not because there is a relevant relationship. In such cases, when a value is lower than the threshold, we consider that it is not relevant and therefore we do not take it into account. In Fig. 5.3(b), all the elements in the set Ci are also a subset of the elements in rule Rk . The difference lies in the fact that the ratio |Ci|/|Rk| is higher and thus, a relevant value. This means that it is more likely that the rule Rk is implementing the use case that constraint Ci is specifying and, therefore, we should consider the alignment between 96 5.1 Matching Tables Fig. 5.3 Situations with differently sized rule/constraint footprints. them as being relevant for our purposes. In fact, in order for the constraint to be properly covered, there should exist a rule that covers the constraint with a large portion. In such a case, the RCR metric would be higher than the threshold and the CC metric shall be considered. Similarly for metric RC, let us suppose that rule Rj is completely covered by constraint Ci , as in Fig. 5.3(c). In this case, the RC metric is 1, since all the elements of Rj are included in Ci . However, as very few elements of Ci are present in Rj , the RCR metric is very small, so the RC metric should not be taken into account. There should exist, consequently, a constraint that has a larger portion of its elements in common with Rj . Fig. 5.3(d) shows an example where the value of RCR is above the threshold and, thus, metric RC is considered. In summary, this threshold is needed to eliminate the consideration of matches with very low probability, which only cause interferences when looking for the rules that cause the fault. The need for this threshold is based on our experiments with the tables. The current value for the threshold is 0 . 1. This means that, at least, 10% of the elements that appear in a rule must be present in a constraint in order to consider the CC metric between both. Similarly, at least 10% of the elements in a constraint must be covered by a rule in order to take their RC metric into account. This value has proved to be the most effective threshold for obtaining the highest recall and precision in all the case studies we have analyzed. Research is currently in progress to provide a theoretical justification for such a value. In any case, this value is currently a configuration parameter in our toolkit to allow easy tuning. Example. Table 5.2 shows the metrics computed for the Families2Persons example, presented in Section 2.3. Note that, for a small example like this, the metrics provide information that can be easily interpreted by just looking 97 Chapter 5. Testing Model-to-Model Transformations case of implementations). This is particularly true in the case of specification methods that use precise and formal notations, and require specialized skills. Once the specifications and the implementation are in place, the debugging process starts [ 67 ]. In our view, formal specifications and implementation should be debugged at the same time, assuming that both are complex artifacts and therefore potential subject to errors. The first step would be to discard as soon as possible all small mistakes (in one or the other) in a quick and cost-effective manner, something that can be done with the aid of the appropriate tools [ 153 ], before diving into more expensive and complex tests (such as model checking, formal validation, dynamic tests, etc.). And this is precisely where our approach represents a valuable asset. The first step is to check, using the a-priori applicability test (Section 5.3.4), if our approach will work with the transformation. In the case it is amenable to be analyzed with it, it is a matter of building the matching tables with our toolkit. The next step is to execute the transformation with the input models provided by the Tract test suites, using the TractsTool environment. In case a constraint is not fulfilled, our tool will provide the list of ATL rules that may have caused the faulty behavior, ordered according to the chances they have of being blamed. The developer can then look for errors on these rules, until one that can explain the constraint violation is found. But it may also be the case that the specifications are wrong, as it is often the case when they have not been tested before (cf. [ 143 ]). In any case, what we have now is a tool that is able to uncover, in a quick and easy manner, many of the errors that happen during the early stage of the testing process, and to help locate the rules that cause the faults. This process will continue until the transformation works, respecting all the Tracts defined for it, which means that the implementation works for (at least) all the constraints and conditions that specify (at this level) its behavior. Then it will be the moment to start going through a more detailed and thorough testing phase, that will help uncover more subtle errors in the transformation—but at a most expensive cost, both time and resource-wise. 104 5.2 Implementation 5.2 Implementation In order to extract the footprints of constraints and rules, as well as to build the matching tables, having automation support is essential because this is a rather complex and error-prone task, especially in the case of large model transformations. Fig. 5.5 shows a UML activity diagram that depicts each step of the matching process until the matching tables are obtained. Fig. 5.5 Matching process. 105 Chapter 5. Testing Model-to-Model Transformations 5.2.1 Footprint Extraction from OCL Constraints The first step is to extract the footprints for each OCL constraint. This is achieved by using the API of the USE (UML based Specification Environment) tool [115]. Firstly, we translate the input and output metamodels to the USE representation by means of a model-to-text transformation. As both the Ecore and the USE meta-metamodels are similar, the translation is quite straightforward. The relevant differences between both languages are the requirement that all relationships must be bidirectional in USE, and its lack of packages. Furthermore, USE only accepts one metamodel and one model, so we have to merge the input and output metamodels. This limitation implies the need to modify the name of each class and association in order to guarantee unique names. We have done so by adding a prefix to the name of the element: src_ if it belongs to the source metamodel, and trg_ if it belongs to the target metamodel. Once both metamodels have been merged into a single file, we add to it the OCL expressions that compose the constraints and load the file into USE. For every OCL expression, USE builds a parse tree representing each subexpression with an explicit node which also provides the return type for each subexpression. To take advantage of this, we have built a small program that uses the aforementioned API. This API allows navigation through the parse tree and extracts the relevant information about the footprints, as explained in Section 5.1.3. 5.2.2 Footprint Extraction from ATL Rules The first step in the footprints extraction is to inject the textual ATL transformation into a model-based representation. It is done automatically by means of a text-to-model transformation. The obtained model conforms to the ATL metamodel, which is in turn made up of three packages: ATL, OCL and PrimitiveTypes. Then, an ATL transformation (in fact, a so-called Higher-Order Transformation) takes the obtained model, as well as the input and target metamodels of the original transformation, and generates a model 106 5.2 Implementation with information of the footprints used in each and every rule. We decided to implement a Higher-Order Transformation [ 135 , 145 ] for extracting the footprints from the ATL rules, because the cost of building and maintaining two individual tools (one for ATL and one for OCL) was less than for developing one common tool. Focusing on a rule, it is quite straightforward to obtain the footprints of the elements in the left-hand side (LHS, the input part) of the rules as well as those created in the righ-hand side (RHS, the output part). To do so, we need to navigate those objects of type InPattern, OutPattern and Binding of the ATL package1. The most challenging part is to extract the types from the OCL expressions. Contrarily to the OCL constraints in USE, ATL does not offer any support nor API to do the extraction. Furthermore, there are slight variations between the versions of OCL used by USE and by ATL concerning predefined types and operations and due to the fact that in ATL the OCL expressions allow references to variables which are bound by the rules. Although those variations do not affect the footprints, they make impossible to apply the same procedure for extracting the footprints from the OCL expressions in USE and the OCL expressions present in ATL. OCL expressions in ATL can be present in the filter part (of the LHS), local variables, the RHS and the imperative part. These textual expressions are built conforming to the OCL package 2 of the ATL metamodel. The extraction of the types in the OCL expressions is a three-step process. In the first step, we only need information of the ATL transformation (expressed as a model, as explained before), while in the second and third steps we need information of the source and target metamodels of the transformation in order to be able to navigate them. An OCL expression can be made up of iterators (in a model level, they are objects of type IteratorExp), such us collect and select. The first step of the footprints extraction consists of taking every OCL expression and removing the iterators. When doing so, from 1 A snapshot of the ATL package is available from http://atenea.lcc.uma.es/ Descargas/ATL.png (the references to the OCL package are not displayed) 2 A snapshot of the OCL package is available from http://atenea.lcc.uma.es/ Descargas/OCL.png (the references to the ATL package are not displayed) 107 Chapter 5. Testing Model-to-Model Transformations each OCL expression (that may contain iterators), one or more navigation paths are obtained. 5.2.3 Matching Function Once we have the types and features used in the constraints ( C ) and the rules ( R ), we apply the matching functions to obtain the measures explained in Section 5.1.4. Algorithm 1 shows the function intersectionSubtypes that computes Ci∩Rj considering subtyping. Given it, Algorithms 2, 3 and 4 present the computation of the values CCi,j , RCi,j , RCRi,j corresponding to the three metrics. These functions have been implemented in Java. The output of the computation for every pair [ Ci, Rj ]is represented in a csv (comma-separated value) format, so that it can be read by spreadsheet-based applications. Input: C,R Output: v 1v= 0 // Find full matches 2for c∈Cdo 3if R.contains(c)then 4v=v+ 1 5R.remove(c) 6end 7end // Find sub-/supertype matches 8for c∈Cdo 9subSuperType =R.containsAny(subSuperType(c)) 10 if subSuperType <> null then 11 v=v+weight(c,subSuperType) 12 R.remove(subSuperType) 13 end 14 end 15 return v Algorithm 1: Function that computes Ci∩Rj 108 5.3 Evaluation Input: C,R Output: vCC 1vCC =intersectionSubtypes(C,R)/size(C) 2vRCR =intersectionSubtypes(C,R)/union(C,R) 3if vCC >threshold and vRCR >threshold then 4return vCC 5end 6else 7return 0 8end Algorithm 2: Function that computes the CC metric for Ciand Rj Input: C,R Output: vRC 1vRC =intersectionSubtypes(C,R)/size(R) 2vRCR =intersectionSubtypes(C,R)/union(C,R) 3if vRC >threshold and vRCR >threshold then 4return vRC 5end 6else 7return 0 8end Algorithm 3: Function that computes the RC metric for Ciand Rj 5.3 Evaluation In this section, we discuss the accuracy and limitations of our approach, and introduce a method for checking if a transformation is amenable to be used with it, based on the concept of footprint similarity matrix. To evaluate the accuracy of our approach we performed a case study [ 90 ] by following the guidelines for conducting empirical explanatory case studies by Roneson and Hörst [ 119 ]. In particular, we report on applying our approach to detect the alignments between Tracts and ATL transformations for four different transformation projects. In addition, we also present the results of a controlled experiment for locating faults in faulty transformations by applying mutations to the four different transformation projects. 109 Chapter 5. Testing Model-to-Model Transformations Input: C,R Output: vRCR 1vRCR =intersectionSubtypes(C,R)/size(union(C,R)) 2if vRCR >threshold then 3return vRCR 4end 5else 6return 0 7end Algorithm 4: Function that computes the RCR metric for Ciand Rj 5.3.1 Research Questions The study was performed to quantitatively assess the completeness, correctness, and usefulness of our approach when applied to a real-world scenario. More specifically, we aimed to answer the following research questions (RQs): 1. RQ1—Correctness: Are the detected alignments between constraints and rules correct in the sense that all reported alignments are representing real alignments? If our approach reports incorrect alignments, what is the reason for this? 2. RQ2—Completeness: Are the detected alignments complete in the sense that all expected alignments are correctly detected? If the set of detected alignments is incomplete, what is the reason for missed alignments? 3. RQ3—Usefulness: In those cases where more than one alignment is reported for a constraint or a rule, are the correctly identified alignments outperforming the falsely identified alignments in terms of the calculated similarity value? We provide this additional question, because the first two questions only consider the evaluation of alignments as true/false, but they do not take the weights of the alignments into account. 5.3.2 Case Study Design Before we present the results of our case study, let us elaborate on its design. 110 5.3 Evaluation Requirements As appropriate inputs we require transformation projects that consist of a set of constraints and a set of rules. We also need the source and target metamodels in order to extract the footprints of constraints and rules. Apart from these artifacts, we further require the alignments between the constraints and the rules given by transformation engineers; otherwise, we would not be able to compare the results obtained by our approach with the expected correct set of alignments. To accomplish an appropriate coverage of different scenarios, the transformations should comprise different intrinsic properties, e.g., having different design complexity measures. Setup We analyzed the alignments between transformation requirements and implementations in four different real-world transformation projects. First, and as already presented in Section 5.1.4, we selected the transformation project dealing with the generation of Entity Relationship (ER) Diagrams from UML Class Diagram Models (UML2ER for short). Second, we selected a transformation project that deals with behavioral models. Models conforming to CPL (Call Processing Language) [ 92 ] are transformed into models conforming to SPL (Session Processing Language) [ 28 ]. The CPL2SPL transformation [ 76 ] is a relatively complex example available from the ATL zoo [61]. Third, we considered a model transformation project that does not operate on modeling languages but rather on markup languages. More specifically, we considered the BT2DB transformation of BibTeX documents into DocBook documents, also available from the ATL zoo. BibTeXML is an XML-based format for the BibTeX bibliographic tool. DocBook, in turn, is an XML-based format for document composition. Finally, we experimented with a very large transformation called Ecore2Maude (or E2M for short) which is used by a tool called e-Motions [ 116 ]. It converts models conforming to the Ecore metamodel into models that conform to the 111 Chapter 5. Testing Model-to-Model Transformations Metric UML2ER CPL2SPL BT2DB Ecore2Maude ATL LoC 77 348 286 1397 #Elements 86 497 449 2403 #Links 201 1114 1052 5270 #Rules 8 15 9 40 #Helpers 0 6 4 40 #Bindings 5 73 25 329 Table 5.6 Transformation Metrics Overview. Metric UML ER CPL SPL BT DB Ecore Maude #Class 4 8 31 77 21 8 18 45 #Atts 3 1 42 33 10 1 31 17 #Refs 4 2 16 62 2 5 34 46 #Inhs 3 6 32 76 31 4 16 38 Table 5.7 Metamodel Metrics Overview. Maude [ 36 ] metamodel, in order to apply some formal reasoning on them afterwards. Tables 5.6 and 5.7 summarize the main size metrics for the ATL transformations and the corresponding metamodels. We developed the Tracts for the given transformations. Constraints were written by a member of our team who was familiar with OCL but was unaware of the ATL implementations. They have been written based on the natural language specification of the transformations. For example, the UML2ER case study comprises 10 constraints (previously shown in Listing 5.1) of two different kinds: one for comparing the number of instances of certain source and target classes, and one for checking equivalent elements based on containment relationships and value correspondences. There are 16 constraints in the CPL2SPL case study, checking that the proper object types in SPL are created from specific object types in CPL. Furthermore, they check that the number of objects in the target model is correct, and that the URIs are correctly created. The 16 constraints in the BT2DB case study make sure that the proper book is created for the different possible entries in BibTeX, 112 5.3 Evaluation and that all entries are properly transformed. Finally, for the E2M case study, three kinds of constraints have been developed to check that the number of elements in the output model is correct, that the Operation entities in the output model have been created from the appropriate input elements, and that from each Class entity, the corresponding Sort has been created in the target model. The input data including the Tracts constraints, the ATL transformations, the alignments between them, the results and the accuracy of these four projects (and several others) are available on our project’s website [23]. Measures To assess the accuracy of our approach, we compute the precision and recall measures originally defined in the area of information retrieval [ 97 ]. In the context of our study, precision denotes the fraction of correctly detected alignments among the set of all detected alignments (i.e., how many detected alignments are in fact correct). Recall indicates the fraction of correctly detected alignments among the set of all actually occurring alignments (i.e., how many alignments have not been missed). These two measures may also be thought of as probabilities: the precision denotes the probability that a detected alignment is correct and the recall is the probability that an actually occurring alignment is detected. Thus, both values range from 0 to 1. Precision is used to answer RQ1 and recall to answer RQ2. There is a natural trade-off between precision and recall. Thus, these two metrics may be further combined inside the so-called f-measure to avoid having only isolated views on both aspects [ 97 ]. To answer RQ3, we use the utility-average metric, which serves to reason about the relative difference between false positives and true positives for one row (in the CC and RCR tables) or for one column (in the RC and RCR tables). To check whether or not our approach is accurate for a given model transformation and a given set of constraints, we have manually obtained the alignments between rules and constraints, reflected in a table called expected alignment table. An example is shown in Table 5.8 for the UML2ER 113 Chapter 5. Testing Model-to-Model Transformations Concept Mutation Operators Concept Mutation Operators Matched Rule Addition Filter Addition Deletion Deletion Name Change Condition Change In/Out Pattern Element Addition Binding Addition Deletion Deletion Type Change Feature Change Name Change Value Change Table 5.12 Possible Mutations for ATL Transformations (from [13]). 5.3.5 Experimenting with Faulty Transformations So far, we have illustrated our approach with correct model transformations. However, given that it has been devised to detect errors in faulty transformations, it is essential to test its effectiveness when the transformations are indeed faulty. Setup . For this reason we have used mutation analysis [ 74 ] to systematically inject faults into model transformations [ 101 ], and then used our approach to locate the bugs. The purpose of a mutated transformation is to emulate a transformation that contains bugs, and then see if our approach detects them. To define the possible mutations of ATL transformations, we use the list of transformation change types presented in [ 13 ], which are summarized in Table 5.12. For more information on the precise mutations and the results obtained for the case studies presented in this paper we kindly refer to [ 140 ]. Example . As an example, we have applied the following mutations for the CPL2SPL transformation mentioned above: 1. Addition of an OutPatternElement in R 1, which results in the creation of unexpected additional elements in the target model. 2. Modification of the feature of a binding in R 3, resulting in incorrectly initialized features in the target model. 120 5.3 Evaluation Mutation Constraints Violated Guilty Rule Located? Number of Steps CPL2SPL_1 C1 X1 C2 ✓1 C3 ✗- C11 ✓1 CPL2SPL_2 C4 ✓1 CPL2SPL_3 C5 X1 C6 ✓1 C14 ✓1 CPL2SPL_4 C12 ✓1 CPL2SPL_5 C15 ✓2 CPL2SPL_6 C5 ✓3 C13 ✓3 CPL2SPL_7 C10 ✓1 Table 5.13 Summary of mutations and fault localization results (CPL2SPL project). 3. Modification of the condition of the filter in R 5, changing the amount of produced target model elements. 4. Modification of a binding and addition of OutPatternElement in R 6, thus producing more target model elements. 5. Deletion of a binding and an OutPatternElement, along with its binding, in R 8; emulating the circumstance in which a transformation produces not enough target elements. 6. Addition of a filter in R 9, making the application of the rule more restricted, thus creating less elements in the target model. 7. Feature modification in a binding and deletion of a binding in R 11, resulting in wrongly assigned values and missing values in the target model. Measures For each mutation, we collect: (i) the constraints violated when the mutation is applied; (ii) if the user was able to find the guilty rule using our approach; and (iii) the number of steps needed for finding the guilty 121 Chapter 5. Testing Model-to-Model Transformations rule. By number of steps we mean the number of rules that the user needs to check in order to find the one that was mutated (including that one). Results . The results in Table 5.13 show that all mutations were detected by our approach for the given example. Each mutation caused one or more constraints to fail, and the guilty rule was correctly identified for all constraints but one ( C 3). This happened because of false negatives, given that the relation between rule CPL2SPL_1 and constraint C 3was quite loose. However, the mutation caused several constraints to fail and our approach was able to identify the mutated rule in the rest of the cases, so the guilty rule was eventually identified. The overall results obtained for all four projects, described in our technical report [ 140 ], show similar effectiveness. We injected a total of 21 mutations, causing 48 constraints to fail. All mutants were killed, i.e., all guilty rules were correctly identified by our approach. Only for three constraints that failed we could not identify the rule causing it but, in all cases, these rules caused the violation of several constraints, and the guilty rule was already identified as the one responsible for the violation of a different constraint that failed with the same mutation, such is the case with C 3in CPL2SPL_1, so the guilty rule was eventually identified. Regarding how many rules need to be checked before identifying the guilty one, our proposed approach needed an average of 1.78 rules to be checked. 5.3.6 Threats to Validity In this subsection, we elaborate on several factors that may jeopardize the validity of our results. Internal validity—Are there factors which might affect the results of this case study? The quality of the data appearing in the matching tables, as well as the usefulness and accuracy of these, are crucial for the internal validity due to three main factors. First, the Tracts need to be manually defined. If they do not contain valuable restrictions, then the matching tables are not useful. Defining constraints is not a trivial task, and the person responsible 122 5.3 Evaluation for doing so needs to have knowledge of OCL, of the transformation to check, and of what should be checked. Second, the way in which footprints are extracted is crucial for building the tables. As explained in Section 5.1.3, there may be very long navigation paths expressed in OCL both in the Tracts and in the rules. From them, we extract the types and features discarding some elements because they are not considered as relevant by giving a higher priority to the results than to the paths used in the computations. Third, in order to study the accuracy of our tables, we have manually defined the expected alignment tables. Should we have failed to properly identify these alignments, the value of precision and recall would have been incorrectly calculated. In any case, they were written by a member of the team and double-checked by another, in order to minimize this risk. We have also made some assumptions in the implementation of our approach. For instance, we have chosen 0 . 1as the threshold value for considering alignments relevant, as mentioned in Section 5.1.4. We also decided not to take constants and primitive types into account (Section 5.1.3). Although our experiences have shown that these decisions seem to be correct, they need to be further validated with more experiments and case studies. Fourth, different styles of Tracts definition may have an effect on the outcomes. As mentioned in Section 5.3.2, the Tracts constraints were written by a member of our team. Of course, should they had been written by other people, or by the developers of the transformations themselves, the results presented here may have been slightly different. Here we assumed the underlying hypothesis that the constraints and rules are more heterogenous if they are developed by different persons, thus resulting in a more difficult matching problem. Finally, concerning the experiment with faulty transformations, we relied on the state-of-the-art of mutation operators for model transformations, but further operators may be required in the future to deal with more fine-grained OCL expression mutations. Thus, these additional operators may have an impact on the results gained in our experiments. 123 Chapter 5. Testing Model-to-Model Transformations External validity—To what extent is it possible to generalize the findings? As a proof of concept of our approach, we have extracted the matching tables for model transformations written in the ATL language. The metamodel of ATL comprises, amongst others, a package for OCL. Currently, the footprint extraction operates on this representation, and thus, it works only for ATL transformations. Nevertheless, it would be possible to reuse parts of the ATL footprint extraction for other rule-based transformation languages that also integrate OCL as a sublanguage. Another threat to external validity would be considering further features of model transformations, such as reflection [ 85 ]. Finally, our studies are focussing for out-place transformation scenarios, and thus, additional studies are needed for in-place transformation scenarios. As part of our future work we plan to investigate these issues, and also try to define a minimal set of requirements on the kinds of specification notations and implementation languages which are amenable to be directly addressed by our approach. 5.4 Related Work The need for systematic verification of model transformations has been documented by the research community by several publications outlining the challenges to be tackled [ 7 , 8 , 47 , 132 ]. As a response, a plethora of approaches ranging from lightweight certification to full verification have been proposed to reason about different kinds of properties of M2M transformations [ 1 , 143 ]. With respect to the contribution of this chapter, three threads of related work are discussed: (i) general traceability approaches in software engineering as well as specific approaches for tracking “guilty” transformation rules, i.e., those whose behavior violates the transformation specifications, (ii) approaches for generating test cases for model transformations, and (iii) approaches that build on model footprints as does our approach. 124 5.4 Related Work 5.4.1 Tracing Faults in Model Transformations IEEE [ 71 ] defines traceability as the degree to which a relationship between two or more artifacts can be established. Most tracing approaches are dedicated to establishing traceability links between artifacts that are in a predecessor/successor relationship with respect to their creation time in the software development process, e.g., between requirements, features, design, architecture, and code. Our approach for automatically finding the alignments between constraints and transformation rules is in the spirit of traceability rules as presented in [ 112 , 111 ]. A survey dedicated to traceability in the field of MDE is presented in [ 49 ], where the possibilities of using trace links established by model transformations are discussed. However, this survey does not report on tracing approaches between transformation specifications and implementations. Tracking guilty transformation rules using a dynamic approach, i.e., by executing the model transformation under testing, has been subject to investigations. Hibberd et al. [ 67 ] present forensic debugging techniques for model transformations based on the trace information of model transformation executions for determining the relationship between source elements, target elements, and the transformation logic involved. With the help of such trace information, it is possible to answer debugging questions implemented as queries. In [ 150 ], we used OCL-based queries for the backwards debugging of model transformations using an explicit runtime model based on the trace model between the source and target models. Aranega et al. [ 3 ] present an approach for locating transformations errors by also exploiting the traces between the source and target models. The dynamic approach is also used in [ 142 ] to build slices of model transformations and in [ 60 ] following a whitebox testing approach. A complementary approach to model transformation testing has been proposed by Kessentini et al. [ 78 ], using a generic oracle function. The idea of this approach is that the traces between the source and target models of a transformation should be similar to existing example traces. Specifically, the oracle function checks how large a derivation there is of the generated traces of a model transformation from existing traces in the example 125 Chapter 5. Testing Model-to-Model Transformations base. While all these approaches track transformation rules using specific test input models, our aim is to statically build more general traceability models between transformations’ specifications and their implementations for enabling static analysis (the pros and cons of dynamic vs. static approaches have already been discussed in Section 5.1.1). In addition to Tracts, other approaches have been proposed that build on the notion of transformation contracts to specify transformation specifications [ 143 ]. While other OCL-based specification approaches, e.g., [ 32 ], are obviously supported by the approach presented in this paper, for non OCL-based approaches, e.g., [ 65 ], additional transformations for computing the metamodel footprints may be developed or these specifications may be internally translated to OCL to reuse the existing footprint computation. Analogously, if other transformation implementation languages such as RubyTL [ 122 ], ETL [ 82 ], or QVT [ OMG ] need to be supported, additional higher-order transformations like those for ATL need to be developed. There are some other transformation testing approaches that directly annotate assertions inside transformation implementations [ 53 , 34 ]. Thus, these approaches have no need to compute the alignments between the specification and the implementation, as they are already provided by the transformation engineer. However, the specification and implementation of the transformation is intermingled, and thus, specifications are specific to a certain transformation implementation. There are several approaches that define contracts for model transformations by defining a set of input/output model pairs and employing model comparison techniques to look for differences between the expected output models (provided by the engineer) and the actual outputs of the transformation [ 94 , 50 ]. In this context, basic support for a failure trace is provided, since the different elements (added, updated, and deleted elements) between an actual target model and an expected target model may be calculated, but the tracing to the corresponding source model elements as well as to the transformation rules is left open. 126 5.4 Related Work 5.4.2 Test Generation for Model Transformations For tracking guilty rules, the availability of appropriate test input models is assumed in our approach. In [ 57 ] we proposed a technique for test case generation. Nevertheless, we give an overview of the research efforts that have been investigated in this area so far. They include black-box, gray-box and white-box approaches. Küster et al. [ 88 ], Gonzalez and Cabot [ 60 ], and Sánchez Cuadrado et al. [ 123 ] focus on white-box methods. In the former, the existence of a high-level design of model transformations, consisting of conceptual transformation rules, is assumed. In [ 60 ], a white-box based testing approach for ATL transformations is provided by extracting OCL constraints and using a model finder to compute test input models fulfilling certain path conditions. Finally, Sánchez Cuadrado et al. discuss the generation of test input models for confirming and explaining errors reported by a static checker for ATL transformations. Many approaches have been proposed for black-box testing, whereby test source models are generated either on the basis of the source metamodel (e.g. [ 18 , 44 , 128 ]) or on the basis of specified requirements [ 53 , 62 ]. For the actual test source model generation, most of these approaches rely on constraint satisfaction, e.g., by means of SAT solvers. Furthermore, an approach has been proposed, which allows automatically completing test input models, i.e., the transformation engineer has to specify an intention by defining a model fragment only, and an algorithm complements this fragment for a valid test input model [129]. 5.4.3 Model Transformation Footprinting Recently, some approaches for computing and utilizing model footprints have been presented. In [ 73 ], the footprints of model operations are statically computed by introducing the idea of metamodel footprints. We pursue this idea of computing metamodel footprints from transformation specifications and implementations for establishing traceability links instead of reasoning solely on model footprints. Mottu et al. [ 103 ] compute the input metamodel 127 Chapter 5. Testing Model-to-Model Transformations footprints for ATL transformations in order to slice the input metamodels as a prerequisite step for computing test input models for the transformations being studied with Alloy. Compared to our work, the work of Mottu et al. is orthogonal in the sense that their approach could complement ours. While we focus on fault localization, Mottu et al. are concerned with test model generation. 5.5 Summary In this chapter we have presented a static approach to trace errors in model transformations. Taking as input elements an ATL model transformation and a set of constraints that specify its expected behavior, our approach automatically extracts the footprints of both artifacts and compares transformation rules and constraints one by one, obtaining the overlap of common footprints. Subsequently, it returns three matching tables where the alignments between rules and constraints are recorded. By using these tables, the transformation engineer is able to trace the rules that can be the cause of broken constraints due to faulty behavior. Our evaluation shows that the presented approach is expected to be accurate for a large set of model transformations. By using the similarity matrixes, an automated and instant fitness test is available to check a-priori whether the approach will be helpful for a given transformation. Several executables of our approach are available on our website [23]. 128 Chapter 6 Extending Tracts for Model-to-Text and Text-to-Model Transformations Much effort has been put into the establishment of model-to-model (M2M) transformation testing techniques in the past years [ 1 , 143 ]. As we have mentioned in the previous chapter, several approaches have been developed for defining contracts for M2M transformations that act as specifications for model transformation implementations [ 32 , 56 ], as oracle functions to validate the output of transformations [ 56 , 63 ], and as drivers for generating test cases [ 63 ]. In particular, constraints for input models, output models and for the relationship between both may be specified. Besides M2M transformations, model-to-text (M2T) and text-to-model (T2M) transformations are of major importance in Model-Driven Engineering [ 39 ]. M2T transformations are typically used to bridge the gap between modeling languages and programming languages by defining code generators but may be employed in a generic manner to produce text from models such as documentation or textual representations of a model’s content. T2M transformations are typically used for reverse engineering [ 20 ], e.g., transforming legacy applications to models in the case of model-driven software moderniza129