Like
OCL,
Xtend (a sublanguage as part of the Xpand project for model queries) provides some really powerful collection operations. These operations allow to easily retrieve elements from arbitrary models, i.e. graphs. Searching a single element in a graph is often very simple with these operation. However, when a collection is to be returned (which is not stored in some attribute), this might be a little bit more complicated, especially if the order matters. In the following, I have assembled some examples showing how to traverse a directed acyclic graph (DAG) with some common traversal strategies:
1) unsorted search traversing directed connections
2) depth-first search traversing directed connections
3) breadth-first search traversing directed connections
4) traverse a directed connection in counter-direction
5) unsorted search, traversing directed connections in counter-direction
6) depth-first search traversing directed connections in counter-direction
7) breadth-first search traversing directed connections in counter-direction
Actually, traversing a connection in counter-direction is not really possible. What I mean by that is, that the query is to return the element of the non-navigable end of the connection. E.g., for a given directed connection x->y, x is to be returned for a given y.
Example: a type hierarchy.
For the examples, I use a "real" world example: a type hierarchy. Our (very simple) model looks like that (in pseudo Java code):
Type {
String name;
Collection<Type> super;
}Let's also assume a container in which all types are stored, e.g.
Collection<Type> allTypes;
In OCL, you can even retrieve all types by a simple query, however we often have some type of container defined in our model anyway (and we use Xtend here ;-) ).
For testing the code, I have defined a concrete example. The following type hierarchy visualizes some type instances, the super types attributes are drawn as connections:
That is, we have a base type
A.
B,
C, and
D are direct subtypes of
A.
E is a subtype of
B.
F is a subtype of
B and
C (we allow multi inheritance ;-) ), and so on.
Preliminary remarks:
- I haven't looked into any algorithm book to find the best algorithm (what ever "best" means). The solutions below are simply the one I implemented when I needed it, without much thinking about the algorithm. If you know a better solution, please let me know!
- I'm using
create extensions for simplicity and performance reasons here. If you have small (or mid sized) models, I'd assume this would be ok.
- Although Xtend is quite similar to OCL, the algorithms will probably not work with OCL, as OCL is side effect free (and I modify collections in the algorithms, which will not work that way with OCL).
Super type queries (or: traverse directed connection)
Since we store the super types in the model, the easiest query is to retrieve the direct super types of a type. E.g., A.super returns an empty list; F.super returns B, C. Now, lets calculate the transitive closure of super types. This is very easy with Xtend:
1) Transitive closure of super types, unsorted:
create Set[Type] superTypesTransitive(Type type):
this.addAll(type.supers) ->
this.addAll(type.supers.superTypesTransitive());
We use a set in order to avoid duplicates, which would be added in case of multi-inheritance. This solution is straight forward. If you are not used to OCL syntax, you may be a little bit confused by the implicit syntax for the collect operation: type.supers.superTypesTransitive() returns superTypesTransitive() for all type.supers elements.
J.superTypesTransitive() will return F,B,C,A, just as expected. (J.superTypesTransitive() is just more OO-like way for writing superTypesTransitive(J). Frankly, I don't know if this is better readable, but it definitely looks cooler ;-)). The returned collection is not ordered, and often enough this is sufficient. However, sometimes we need the collection to be ordered. There are two often used strategies for traversing a tree or DAG: depth first search and breadth first search. We will implement both.
2) Transitive closure of super types with depth first search order:
create List[Type] superTypesTransitiveDFS(Type type):
type.supers.forAll(s|
this.add(s)->
this.addAll(s.superTypesTransitiveDFS().reject(e|this.contains(e)))
!=null);
As we need a sorted collection, we have to use a list instead of a set. However, we have to reject duplicates in our code now. Since Xtend does not provide a loop statement, I have used the collection operation forAll here. Since the forAll operation expects a boolean expression inside, the !=null part "casts" our chained expression into a boolean expressions. If you know of a nicer solution, please let me know.
J.superTypesTransitiveDFS() will return F,B,A,C.
3) Transitive closure of super types with breadth first search order:
create List[Type] superTypesTransitiveBFS(Type type):
let todo = new java::util::ArrayList :
todo.addAll(type.supers) ->
bfsSuper(this, todo);
private Void bfsSuper(List[Type] result, List[Type] todo):
if todo.isEmpty then
Void
else
result.add(todo.first()) ->
todo.addAll(todo.first().supers.reject(e|todo.contains(e) || result.contains(e))) ->
todo.remove(todo.first()) ->
bfsSuper(result, todo);
The breadth first search is a little bit more complicated, as we need a helper list, and a helper method. Note that we cannot create an Xtend type of List here, instead we have to use the Java ArrayList, which is available when we use the JavaBeans Metamodel in the project's Xpand/Xtend settings.
J.superTypesTransitiveBFS() will return F,B,C,A.
Sub type queries (or: traverse connections in counter direction)
So, we have three different queries for super types. Now we want to write the very same queries for sub types. Unfortunately, the sub type information is not directly stored in the model but must be derived instead. First, we write a simple query for the direct sub types:
4) Computes direct sub types (navigate in counter-direction):
create Set[Type] subTypes(Type type, Collection[Type] allTypes):
this.addAll(allTypes.select(k|k.supers.contains(type)));
This solution relies on the afore described queries. Frankly, I needed some time to figure it out (as I'm more an imperative and OO guy ;-) ) and I was really surprised how short (one line) it is. If you have to write that with Java, you will need a lot more lines. So, if you ever wondered why to use a special transformation language -- this is at least one argument.
Now, let's compute the transitive closure:
5) Transitive closure of sub types, unsorted:
create Set[Type] subTypesTransitive(Type type, Collection[Type] allTypes):
this.addAll(allTypes.select(k|k.superTypesTransitive().contains(type)));
Note that this query does not rely on the subTypes extension, but only on the super type queries. Since we use a Set, we do not have to take care of duplicates. Again: A Java solution would be much longer.
A.superTypesTransitive(allTypes) will return B,C,E,G,H,I,J,D,F
Now, let's implement the depth first search for sub types:
6) Transitive closure of sub types with depth first search order:
create List[Type] subTypesTransitiveDFS(Type type, Collection[Type] allTypes):
type.subTypes(allTypes).forAll(s|
this.add(s)->
this.addAll(s.subTypesTransitiveDFS(allTypes).reject(e|this.contains(e)))
!=null);
Since we have implemented an extension for subTypes, the solution is quite similar to the super kind depth first search algorithm.
A.subTypesTransitiveDFS(allTypes) will return B,E,F,I,J,C,D,G,H. Note that we cannot simply use the unsorted solution with a list instead of a set, as this will not result in a depth first search order (in our case, it would return something like B,C,D,E,F,I,J,G,H). The same is true for superTypesTransitiveDFS, by the way. Last but not least the breadth first search for sub types.
7) Transitive closure of sub types with breadth first search order:
create List[Type] subTypesTransitiveBFS(Type type, Collection[Type] allTypes):
let todo = new java::util::ArrayList :
todo.addAll(type.subTypes(allTypes)) ->
bfsSub(this, todo, allTypes);
private Void bfsSub(List[Type] result, List[Type] todo, Collection[Type] allTypes):
if todo.isEmpty then
Void
else
result.add(todo.first()) ->
todo.addAll(
todo.first().subTypes(allTypes).
reject(e|todo.contains(e) || result.contains(e))) ->
todo.remove(todo.first()) ->
bfsSub(result, todo, allTypes);
This algorithm also resembles the one for super types. By the way: I didn't find the let expression explained in the documentation of Xtend (however, some examples use it). Did I miss it or is there really more OCL in Xtend as told in the docs?
A.subTypesTransitiveBFS(allKinds) will return B,C,D,E,F,G,H,I,J, which is easily validated as this is the order of the types as shown in the little figure.
A couple of years ago I left the world of industrial software projects, and joined the academic world of computer science. I already had used models, I knew quite a few things about UML, even had programmed a graphical UML editor using GEF, in other words, I felt prepared to explore the universe of modeling. However, as my former boss and tutor Prof. Dr. Hans-Werner Six correctly diagnosed, I soon got infected with a terrible illness, widely spread in that area: modelitis. Actually, depending on how hard this disease hits you, you may call it meta-modelitis.
A special characteristic of this disease is that the patient himself is more or less unaware of it, actually, he or she often thinks it's great fun. So did I, and frankly, I doubt that I will ever be completely cured -- particularly since there are so many other victims of modelitis doing great and funny things. E.g., inventing one TLA (for non-modelitis afflicted readers: three letter acronym) after the other, such as MDA, MDD, DSL, MOF, ATL, EMF, ETL, GEF, GMF, OCL -- you name it. I was no better, I even tried certain variations, such as CAT, GEF3D, or Mitra (my own M2M-transformation language).
You may have noticed that "computer-assisted transformation" is abbreviated to CAT :-) This is the abstract of my thesis (in english, the thesis itself is written in german):
In the context of model driven development, fully automated model transformations are used to release developers from recurring and error-prone tasks, thus improving efficiency. However, these transformations cannot always be applied, or at least not without introducing new problems. By exploring semi-automated techniques, this work tries to eliminate some of these problems while preserving the positive effects. First, a modeling theory is developed for describing model driven approaches. This theory is used to analyze a typical problem of these approaches, the so called "semantic gap". The need to add semantics when transforming models is identified as a fundamental problem. Computer-assisted transformations are a semi-automated approach, which allow to combine manual transformation parts with automated parts. In order to define and execute this kind of transformations, a model-to-model transformation language called Mitra is designed. Due to the manual nature the approach, the models need to be visualized and a user- interface is to be provided. The basic idea of the proposed solution is the visualization of graphical models by means of two-dimensional diagrams projected onto planes in a three-dimensional scene. This permits not only the visualization of inter-model relations, but also semi-automated transformation of model elements with computer-assisted transformations employing the common drag-and-drop interaction pattern. With GEF3D, a framework is presented, which enables the combination of existing graphical editors in a three-dimensional scene. Three well-known transformation problems, among others the robustness analysis, are solved with the created tools in order to evaluate the proposed concepts.
Without the great software, particularly in the modeling project, and without the great support (when I had problems with the great software ;-) ), I wouldn't had been able to actually implement software realizing my ideas and by that proof the concepts. And it wouldn't had been so much fun.
