As MDE is increasingly applied to larger and more complex systems, the models that MDE platforms need to manage can grow signi cantly in size. Additionally, model management programs that interact with such models become larger and more complicated, which introduces further challenges in ensuring their correctness and maintainability. This paper presents an automated static analysis and validation framework for languages of the Epsilon platform. By performing static analysis on model management programs written in the Epsilon languages, this framework aims to improve program correctness and development e ciency in MDE development processes. In addition, by applying analysis on model management programs, sub-optimal performance patterns can be detected early in the development process and feedback can be provided to the developers to enable e cient management of large models.
The Epsilon platform [
BigMDE ’14, July 24, 2014 York, UK static analyser for EOL and the languages that build atop it, implies that a wide range of genuine errors that could be detected at design time are only detected at runtime. Beyond detecting type-related errors, a static analyser could also be used to support advanced analysis capabilities, such as code detection, to improve the performance of model querying and transformation programs, particularly in the context of processing large models.
The remainder of the paper is organised as follows. In Section 2 we brie y motivate the need for static analysis capabilities in model management languages, in particular the Epsilon platform. In Section 3 we present the architecture of a static analysis framework for the Epsilon platform and a static analyser for the Epsilon Object Language. In Section 4 we present a sub-optimal code detection facility developed atop the static analysis framework. In Section 5 we discuss preliminary evaluation of our work. In Section 6 we discuss related work and in Section 7 we conclude and provide directions for further work.
MDE allows developers to construct models which abstract
away from technical details, using concepts closely related to
the domain of interest to reduce accidental complexity. The
constructed models are then transformed into part (or all) of
the target system under development. Whilst Model
Transformation is considered to be the heart and soul of Model
Driven Engineering [
Epsilon is a mature and well-established family of
interoperable languages for model management. Languages in
Epsilon can be used to manage models of diverse
metamodels and technologies. The architecture of the Epsilon
platform is depicted in Figure 1. At the core of Epsilon is the
Epsilon Object Language (EOL) [
EOL supports optional typing of variables, operations and
operation parameters. The listing below demonstrates the
exibility that this delivers using as an example, a program
that operates on an Ecore model. In line 1, an operation
called getName() is de ned, its context type is Any, which
means that the operation can be invoked on objects/model
elements of any type. In line 2, the keyword self refers
to the object on which the operation is called, for
example, in the statement o.getName(), self refers to o. Thus in
line 2, the operation checks if the object is an instance of
ENamedElement, if it is, it will return self.name. A
typical static analyser would complain in line 3 that "self.name"
does not exist because the type of self is declared as Any,
not Ecore!ENameElement. However, this will never be a
problem at run-time due to the if condition in line 2.
1 operation Any getName() {
2 if(self.isTypeOf(Ecore!ENamedElement))
3 return self.name;
4 else return "Unnamed";
5 }
1http://eclipse.org/epsilon/users/
On the other hand, some genuine errors can also remain
hidden until runtime without the help of static analysis.
The listing below demonstrates an example of a genuine
error. In line 1, a variable named o is de ned to be of type
Ecore!EClass, and in line 2, o is assigned the value of a
random EClass in the Ecore model. In line 3, the program
tries to print the value property of o which does not exist
according to the Ecore metamodel. As such, an error will
be thrown at runtime.
1 var o : Ecore!EClass;
2 o = Ecore!EClass.all.first();
3 o.value.println();
As the size of such programs grow, locating genuine errors
becomes an increasingly di cult task. For example, the
EOL program that underpins the widely-used EuGENia tool
[
Since model management programs interact with models, performing static analysis on model management programs can also help identify sub-optimal performance patterns in the process of accessing models. Analysis can also help comprehend the model management programs. For example, coverage analysis can be performed to nd out which parts of the metamodel of particular models are accessed, and test cases can be generated based on this comprehension to better test a model management program. With the potential bene ts mentioned above, we propose and implement a static analysis framework for Epsilon.
In this section we discuss the proposed static analysis framework in detail. The general idea of our approach can be illustrated by Figure 2. We rst transform the Homogeneous Abstract Syntax Tree of an EOL program into a Heterogeneous Abstract Syntax Tree, we then apply resolution algorithms (including variable resolution and type resolution) to derive a Heterogeneous Abstract Syntax Graph, with its elements connected to each other. We then perform pattern detection to detect sub-optimal code. The aim of the framework is to provide a generic static analysis facility for all languages of the Epsilon platform. Since the core language of the Epsilon platform is EOL, we rst develop a static analyser for EOL.
Currently, Epsilon provides an ANTLR [
Comparing with our current approach, an alternative approach would have been to rede ne EOL's grammar using a toolkit such as Xtext or EMFText which can automate the source-code to model transformation process but we have opted for an intermediate transformation instead in order to reuse Epsilon's robust and proven parsers. 3.2
With the EOL metamodel and the AST to EOL transformation de ned, the next step of the process involves linking elements of the EOL model (heterogeneous tree) constructed in the previous phase to derive an abstract syntax graph. We have created several facilities to achieve this.
To facilitate the traversal of di erent elements in the EOL model and to support extensibility, we developed a facility which generates Java visitor classes from Ecore metamodels. We then generated visitor classes from the EOL metamodel which provide a general mechanism to traverse all elements in an EOL model. The EOL Visitor serves as the infrastructure of the static analysis framework, as all other facilities in the static analysis framework extend the EOL visitors to implement functionalities. The EOL visitor also provides high extensibility as new analysis mechanisms can be implemented simply by extending the EOL visitor.
The rst phase of the static analysis on an EOL program involves resolving identi ers to their de nitions. Context-free identi ers in EOL can refer to 1) declared variables/operation parameters and 2) undeclared variables provided by the execution engine at run-time. For declared variables, the variable resolver establishes links between the variable declaration and its references. For example, in line 1 of the listing provided below, a variable named a is declared. In line 2, a is referenced. The variable resolver will establish a link between the reference in line 2 and the declaration in line 1. 1 var a : Integer; 2 a = 10; Variable resolution also applies to parameters in operation de nitions. In the following listing, the variable resolver will establish a link between the reference of the parameter toP rint in line 2 and its declaration in line 1. 1 operation definedPrint(toPrint: String) : String { 2 toPrint.println(); 3 } There are also some implicit variables which are not declared by the developer but are rather provided by the execution engine. For example, the keyword self in an operation definition refers to the object/model element on which the operation is invoked. The following listing demonstrates how self is used. The variable resolver will establish a link between self and the object on which printSelf is invoked. 1 operation Any printSelf() { 2 self.println(); 3 } It is important to note that at the stage of variable resolution, model element types are not resolved.
In EOL there are several built-in primitive types (Boolean, Integer, Real, String) and collection types (Set, Bag, Sequence and OrderedSet ). There is also a built-in Map type and the Any type. These types are all subclasses of Type in the EOL metamodel. The resolution of the above types is performed during the heterogeneous abstract syntax tree derivation. There is also a subclass of T ype in the EOL metamodel called M odelElementT ype which includes typing information regarding models de ned using di erent technologies. Such typing information should be determined by
accessing the corresponding models.
To support accessing metamodels at design-time, we introduced M odelDeclarationStatements, which are exible to support models de ned in di erent modelling technologies. A model declaration de nes the model's name, aliases, the modelling technology (driver) that the model conforms to, and a set of driver-speci c parameters. The listing below is an example of M odelDeclarationStatement; it declares a model named library with alias l and its driver to be EM F , it then speci es the EMF-speci c namespace URI (nsuri ) of the model so that the analyser knows how to locate and access its metamodel. 1 model library alias l driver EMF {nsuri = "http:// library/1.0"}; To facilitate uniform analysis of the structural information of models of diverse modelling technologies, the static analysis framework needs to convert type-related information from di erent modelling technologies into a common representation. Instead of inventing a new representation, we have decided to use EMF's Ecore. As such, the static analysis framework provides a modular architecture where pluggable components are responsible for transforming di erent types of model declarations into Ecore EPackages. For di erent modelling technologies:
For EMF models, return the registered EPackage by looking up the metamodel nsURI property of the model declaration.
For plain XML, construct an EPackage by analysing the contents of a sample model le speci ed by respective the model declaration parameter.
We have developed drivers for EMF models and plain XML les, and a common interface which allows new drivers for di erent modelling technologies to be integrated with the static analysis framework. By accessing models/metamodels, the type resolver is able to resolve types with regards to models/metamodels.
The variable resolver and type resolver constitute the infrastructure of the static analysis framework for the Epsilon languages. The infrastructure is depicted in Figure 4. The EOL Abstract Syntax Tree layer is provided by the EOL engine, the AST2EOL layer uses the AST and the EOL metamodel to translate the AST to an EOL model. The EOL Variable Resolver and the EOL Type Resolver, both make use of the EOL Visitor and the Metamodel Connectivity layer (which is used to read metamodels) to establish a fully type-resolved EOL model.
The static analysis infrastructure can be easily extended. As
proof of concept, we have also implemented all of the
aforementioned facilities for the Epsilon Transformation Language.
We extended the EOL metamodel to create an ETL
metamodel, with the ETL metamodel, we created the ETL visitor
facility; we extended the AST2EOL to create a AST2ETL
facility; we extended the EOL variable resolver and type
resolver to create ETL variable and type resolvers. The EOL
and ETL static analysers can be found under the Epsilon
Labs open-source project [
Rule-based model transformation languages usually rely on
query or navigation languages for traversing the source
models to feed transformation rules with the required model
elements. In [
The structure of this facility is depicted in Figure 5. The SubOptimalDetector has a EOLM odel as input to perform the detection; it makes use of the EP LEngine of the Epsilon platform to derive Abstract Syntax Trees, it has a set of de ned EP LP atterns (.epl scripts) using EPL, and a logging facility (LogBook) to keep the warning messages it generates for pattern matches.
In this section, we present the sub-optimal detection facility. We provide several examples that illustrate potential suboptimal performance patterns in the context of large scale model manipulation. We then present and explain a suboptimal performance pattern de ned in EPL. It should be noted that this facility targets EOL programs, however, it can be easily extended to cope with programs written in other Epsilon languages as discussed earlier.
The examples we present are all based on a simple Library metamodel illustrated in Figure 6. The Library metamodel contains two simple metaclasses, Author and Book. An Author has a rst name, a surname and a number of published Book s where a Book has a name and an Author. The association between Author and Book is bidirectional, they are books and authors respectively.
A frequent operation in EOL is to retrieve all model elements of a speci c type by using the :all property call which can be a computationally heavy operation to perform as models grow in size. By analysing the metamodel of the model under question, bidirectional relationships between model elements can be used to avoid such heavy computations. 1 var a = Author.all.first; 2 var books = Book.all.select(b|b.author = a); 3 var aBook = Book.all.selectOne(b|b.author = a); The listing above demonstrates a potential performance bottleneck. In line 1, an Author is retrieved from the model. In line 2, all instances of type Book are retrieved and then a conditional select is performed to nd the books that are written by Author 'a'. However, since the relationship between Author and Book is bidirectional, this can be replaced by the (more e cient) statement: 1 var books = a.books; Thus the complexity of the operation all is reduced from n to 1 given that n is the number of Books in the model under question. It is also the case for the selectOne operation in line 3, which can be rewritten as: 1 var aBook = a.books.first();
Another computationally-heavy pattern is the presence of compound select operations on the same collection. 1 var authors = Author.all.select(a|a.first_name = 2 'William').select(a|a.surname = 'Shakespeare'); Listing 1: a potential performance overhead using compound select operations Listing 1 demonstrates such operations. In line 1, all of the Authors are retrieved rst, then a select operation is performed to select all Authors whose rst names is W illiam, then another select operation is performed to select all Authors whose surname is Shakespeare. The complexity of this operation is n2 given that n is the number of Authors in the model under question. However, the condition of both the select operations can be put together to form a single select operation. And the statement above can be written as 1 var authors = Author.all.select(a|a.first_name = 2 'William' and a.surname = 'Shakespeare'); the complexity of this operation is therefore n as the collection of the Authors is only traversed once.
Performing select operations on unique collections (sets) can sometimes be ine cient depending on the condition of the select operation. 1 var authorOne = Author.all.first; 2 var authorTwo = Author.all.last; 3 var bookOne = authorOne.books.first; 4 var bookSet : Set(Book); 5 bookSet.addAll(authorTwo.books); 6 bookSet.select(b|b = bookOne);
Listing 2: Select operation on unique collection Listing 2 demonstrates an ine cient and computationally expensive select operation. In Line 1 and 2, two Authors are retrieved from the model; in line 3, a Book is retrieved from authorOne's publications; in line 4, a Set called bookSet is created and in line 5, all of the Books that authorT wo published are added to bookSet. In line 6 the select operation iterates through all of the books in the bookSet and nd the ones that match the bookOne. However, the bookSet is a unique collection, which means that all of the elements in it only appear once. Therefore, it is not necessary to perform a select operation but rather a selectOne operation, as the select operation would return at most one result eventually. The complexity of the select operation is n given that n is the number of books that authorT wo published; If the select operation is replaced with selectOne, the complexity of it would be 1 for the best case scenario and n for the worst case scenario (n=2 for the average case).
In some cases, checking existence of an element inside a collection can be written in ine cient ways. 1 if(Book.all.select(b|b.name = "EpsilonBook") 2 .size() > 0) { 3 "There is a book called EpsilonBook".println(); 4 }
Listing 3: Collection element existence Listing 3 demonstrates such a scenario. In line 1, the condition of the if statement retrieves all instances of Book, then selects the ones with the name EpsilonBook, and calculates the size of it then evaluates if the size is greater than 0. This operation eventually checks for the existence of a book named EpsilonBook. Thus, this operation can be more e ciently re-written as: 1 Book.all.exists(b|b.name = "EpsilonBook") 4.5
Listing 4 demonstrates another example of sub-optimal EOL code. 1 var anEpsilonBook = Book.all.select(b|b.name = 2 "EpsilonBook").first();
Listing 4: Select an element in a collection In line 1, a select operation is performed on all of the instances of Book to lter out the books with the name 'EpsilonBook', then a f irst operation is performed to select the rst one of the collection returned by select. This can be more e ciently re-written as: 1 var anEpsilonBook = Book.all.selectOne(b|b.name = 2 "EpsilonBook"); to avoid traversing all of the instances of Book.
In this section we present a sub-optimal performance pattern which is written in the Epsilon Pattern Language (EPL). To understand how this pattern works, it is rst important to understand what is contained in an EOL model for a certain EOL program.
Figure 7 illustrates a fragment of an EOL model which represents the statement below. 1 Book.all.select(b|b.author = a); Firstly, invocations of the select() operation in the EOL metamodel are represented by the F OLM ethodCallExpression (FirstOrderLogic method call) metaclass; it has a name (an instance of N ameExpression) and an iterator (an instance of V ariableExpression). In this case, the name is 'select' and the iterator is 'b'.
The select operation has a condition, in this case, it is an instance of EqualsOperatorExpression. The lhs (left hand side) of it is an instance of P ropertyCallExpression, whose target (an instance of NameExpression) is 'b' and property (an instance of NameExpression) is 'author'; the rhs (right hand side) of it is 'a' (an instance of NameExpression). Both the lhs and rhs of the EqualsOperatorExpression have resolvedTypes, in this case, they are both Author (instances of M odelElementT ypes).
The target of the F OLM ethodCallExpression is an instance of P ropertyCallExpression with its target as Book (an instance of NameExpression) and its property as all (an instance of NameExpression). The types of these expressions, altogether with some irrelevant details are omitted for the purpose of the discussion.
In Listing 5, we de ne an EPL pattern to match occurences of the pattern described above. In lines 2-6, a guard is dened to look for a F OLM ethodCallExpression the name of which is either 'select' or 'selectOne'; the type of the condition should be EqualsOperatorExpression; its target should be an instance of P ropertyCallExpression; and the property of the P ropertyCallExpression should be 'all'. In lines 8-10, a guard is de ned to look for an instance of EqualsOperatorExpression in the condition of the FOLMethodCallExpression found previously, the lhs of which should be an instance of P ropertyCallExpression. Lines 12-14 specify that the resolvedT ype of the lhs should be an instance of M odelElementT ype. In lines 16-18, it speci es that the resolvedT ype of the rhs should be an instance of M odelElementT ype. In lines 20-24, it speci es that the type of the lhs and the rhs should be the same. Lines 26-37 perform the match of the pattern. This part rstly fetches the ERef erence from the lhs of the condition (in this case, 'b.author', it is an ERef erence because as previously discussed, all metamodels are converted to EMF metamodels for uniformity). The EReference is then inspected; if it is not null and it has an eOpposite reference, the pattern continues to check if the type of the eOpposite of the reference is the type of the rhs of the condition (in this case, 'author').
In lines 39-47, a helper method is de ned to help look for an ERef erence given an EClass and a name; its implementation is straightforward. 1 pattern InverseNavigation 2 folcall : FOLMethodCallExpression 3 guard: (folcall.method.name = 'select' or folcall.
method.name = 'selectOne') 4 and folcall.conditions.isTypeOf(
EqualsOperatorExpression) and folcall.target.isTypeOf(PropertyCallExpression) and folcall.target.property.name = 'all', condition : EqualsOperatorExpression from: folcall.condition guard: condition.lhs.isTypeOf(
PropertyCallExpression)
Our original attempt to construct the sub-optimal performance detection facility was to de ne patterns using Java, we de ned a method in Java to achieve the same function described above. The equivalent Java implementation is 76 lines of code with a long chain of If statements which makes it very di cult to comprehend. With the EPL approach, the patterns are more comprehensible. Developers can contribute to the pattern pool by de ning their own EPL patterns and registering them with the framework through appropriate extension points.
The static analyser proposed in this paper is a pragmatic
static analyser. The exibility of EOL allows its users to
write code with optional typings that always work at
runtime. Reporting errors on such cases are not desirable for
EOL, especially on legacy EOL code that is proven to work
with extensive testing. Thus the design decision was to
allow such behaviour and delegate the resolution to the EOL
execution engine. We applied the static analyser on a large
EOL program (Ecore2GMF.eol) that underpins the
Eugenia tool [
After evaluating the static analyser, we evaluate the suboptimal performance detection facility. Figure 8 provides a screenshot of the editor we implemented by extending the existing EOL Eclipse-based editor. The lines of code with warnings represent matches of the patterns discussed above. The implementation of the editor is able to extract and display the warning messages generated by the detection facility. The sub-optimal performance detection facility is not only able to detect patterns that incur performance overheads, but also provide suggestions on how to rewrite the code. An example warning message is shown in line 8, the warning message suggests to rewrite the operation as: 1 Author.all.select(a|a.first_name = "William" and a.
surname = "Shakespeare") The rest of the patterns function as expected.
There are several automated analysis and validation tools for
model management programs. In [
Acceleo [
In [
In this paper we have reported on our work on designing and developing a static analysis framework for the core language of Epsilon (EOL). The focus of our report is mostly on the sub-optimal detection facility of the static analysis framework. However, it is to be noted that the static analysis framework is able to detect various type-related errors that may occur using EOL. The static analysis framework follows a pragmatic approach so as not to compromise the exibility of the Epsilon languages. As a result, it can generate false negatives (problems that exist but cannot be detected by the static analyser). To minimise the number of false negatives, a more strict coding style is encouraged - to avoid the use of Any type as much as possible, so that the static analyser can perform more accurate analysis. This is clearly a trade-o to make; to obtain better error reporting, developers need to write more boilerplate code with explicit type casting, while to obtain better exibility, developers need to bare with the fact that the analyser may produce false negatives that emerge at run-time.
It should be noted that the sub-optimal performance detection facility is only one application of the static analysis framework for Epsilon. In the future, we plan to look into facilities such as program comprehension, metamodel coverage analysis, impact analysis, etc. We will also look into the possibility of pre-loading models and look for more negrained performance patterns for EOL programs.