This transformation presents a basic example where a tree is transformed into a list. This kind of transformation is usually made by an imperative Depth First Traversal algorithm. Moreover with this example, the following ATL concepts will be encountered:
- matched rules (one with a guard)
- helper functions (one being recursive)
- collection related functions
- an enumeration
- ATL resolve algorithm
The Tree Metamodel
This metamodel is pretty simple and represents a tree whose elements have a name and nodes' leaves can be of small, medium or big size. The root element should be a Node.
The Element List Metamodel
The ElementList metamodel aims to represent an ordered list of elements, each element having a name. The root element should be a RootElement.
The Tree to ElementList Transformation: Step by step
1 - The principles and goals
Let MMTree be the tree metamodel's name and MMElementList be the ElementList metamodels' name.
In this transformation, we want:
- the tree root (of type MMTree!Node) to be transformed into the Element list "root" (of type MMElementList!RootElement)
- a MMTree!Leaf element should be transformed into an MMElementList!CommonElement element
- the root element's elements reference should contain an ordered set composed of the "transformed equivalent" of the leaves such as:
- all big sized leaves comes first (in the tree's DFS order)
- then all medium sized leaves (still in the tree's DFS order)
- then the small sized one (still in the tree's DFS order)
The figure below instantiates a transformation example. The nodes' names are represented by an integer and the tree root is named "0".
Tree2List Big Picture
We can easily see the biggest part of this transformation is to "build" the "elements" reference of the MMElementList!RootElement concept. One additional goal of this example will be to match to the main ATL philosophy as much as we can. I.e, we will avoid to use imperative part and we will try to be the most modular as possible.
2 - Writing the first rule
We start this example with the matched rule Tree Node to Root Element where a Tree Node is transformed into a Root Element. A matched rule enables to match some of the model elements of a source model, and to generate from them a number of distinct target model elements.
3 - Filtering the tree node root
With the rule above, for each Tree Node in the source model a Root Element is created in the target model. This does not match exactly with our requirements. Here we want to catch only the tree node root. For only filtering the root, we should add a guard to this rule.
In order to clear our transformation code as much as possible, we will use an helper to define the guard. An helper is an auxiliary function that computes a result needed in a rule. See below the code of the guard isTreeNodeRoot:
We can now call this helper in the guard of the rule Tree Node Root to Root Element (NB: rule name has been updated from TreeNode2RootElement to TreeNodeRoot2RootElement).
4 - Applying the ATL philosophy
The first idea to complete our transformation is to add a second rule to transform a Leaf into a List Element. The corresponding code is:
5 - Getting all the tree root children and filling the containment reference
Executing the previous transformation will create the list root element from one side and the elements from other side. At this step of the transformation, there is no link between the list root and the elements of this list. Hence, one point should be solved:
- How to put the created elements in the containment reference (called elements) of the concept MMElementList!RootElement ?
First of all, we need to create an helper to retrieve and to return all the children of a node.
This helper proceeds to a Depth First Traversal (DFS) algorithm and returns the list of all leaves encountered during the search. We use a recursive function on the tree root's children which would build a MMElementList!CommonElement list corresponding to the leaves encountered during the DFS. Briefly, the algorithm:
- iterates on the current node children
- tests the current child type (node or leaf)
- if it is a node, a recursive call is made,
- else the current child is added to the children list
To solve our containment problem, we can use the following code:
With this solution, the rule Leaf2CommonElement (created in the previous step) is now useless and must be deleted. The transformation is done with only one matched rule. For each element of its elements reference, we create a MMElementList!CommonElement. Each element of this list is computed via a distinct keyword which creates a CommonElement for each Leaf of a list we compute via an helper.
6 - Using the ATL Resolve Algorithm
In this example, we want to follow as much as possible the ATL convention. So in this step, our goal is to make more "modular" our transformation. This could be done by using the ATL Resolve Algorithm.
Execution Semantics of Matched Rules and ATL Resolve Algorithm
Matched rules are executed over matches of their source pattern. For a given match the target elements of the specified types are created in the target model and are initialized using the bindings. Executing a rule on a match additionally creates a traceability link in the internal structures of the transformation engine. This link relates three components: the rule, the match (i.e. source elements) and the newly created target elements. Actual feature initialization uses a specific value resolution algorithm, called ATL resolve algorithm. After the expression of a binding has been evaluated, the resulting value is first resolved before being assigned to the corresponding target feature. Resolution depends on the type of the value. If the type is primitive, then the value is simply assigned to the corresponding feature. If its type is a metamodel type there are two possibilities:
With the ATL Resolve Algorithm, the transformation could be updated as follow:
7 - Sorting leafs by size
In this final step, we will sort elements list by the corresponding leaf size.
To respect this requirement, we will create an helper to get leaves in the following order: big, medium, and small.
This helper uses another recursive helper (getAllChildren) defined previously which proceeds to a DFS and returns the list of all leaves encountered during the search. Let "leaves" being the list of leaves, we compute a 3 set partition of leaves : one "big leaves" list, one "medium leaves" list and one "small leaves" list. We then make an union of these 3 lists which gives us the well ordered leave list used by the distinct keyword of the main rule.
|Source code for the scenario Tree to List|