The Generator Algorithm

Defining the Generators Involved

To define the required generators, MPS examines the input model and determines which languages are used in it. Doing this job MPS doesn't make use of 'Used Languages' specified in the model properties dialog. Instead MPS examines each node in the model and gathers languages that are actually used.

From each 'used language' MPS obtains its generator module. If there are more than one generator module in a language, MPS chooses the first one (multiple generators for the same language are not fully supported in the current version of MPS). If any generator in this list depends on other generators (as specified in the 'depends on generators' property), then those generators are added to the list as well.

After MPS obtains the initial list of generators, it begins to scan the generator's templates in order to determine what languages will be used in intermediate (transient) models. The languages detected this way are handled in the same manner as the languages used in the original input model. This procedure is repeated until no more 'used languages' can be detected.

Dependency scope/kind - 'Generation Target' and 'Design'.

'Generation Target' replaces 'Extends' relation between two languages (L2 extends L1), when one needed to specify that Generator of L2 generates into L1 and thus needs its runtime dependencies. Now, when a language (L2) is translated to another language (L1), and L1 has runtime dependencies, use L1 as 'Generation Target' of L2. Though this approach is much better than 'Extends', it's still not perfect as it's rather an attribute of a generator than of a language. Once Generators become fully independent from their languages, we might need to fix this approach (different generators may target different languages, thus target has to be specified for a generator, not the source language).

'Design' dependency replaces 'Extends' between two generators. Use it when you need to reference another generator to specify priority rules (though consider if you indeed need these priorities, see changes in the Generator Plan, below)

Defining the Order of Priorities

As we discussed earlier, a generator module contains generator models, and generator models contain mapping configurations. Mapping configuration (mapping for short) is a set of generator rules. It is often required that some mappings must be applied before (or not later than, or together with) some other mappings. The language developer specifies such a relationship between mappings by means of mapping constraints in the generator properties dialog.

After MPS builds the list of involved generators, it divides all mappings into groups, according to the mapping priorities specified. All mappings for which no priority has been specified fall into the last (least-priority) group.

tip

You can check the mapping partitioning for any (input) model by selecting Show Generation Plan action in the model's popup menu.

The result of partitioning will be shown in the MPS Output View.

Optimized Generation Plan

When planning the generation phase, MPS prefers to keep every generator as lonely as possible. Eventually, you'll see many relatively small and fast to process generation steps. Of course, the generators forced to run together with priority rules still run at the same step. Handling several unrelated generators at the same generation step (MPS prior to 3.2) proved to be inefficient, since it imposed a lot of unnecessary checking for rule applicability across other generators from the same step. With in-place transformation in 3.2 and later, the performance penalty for each extra generation steps is negligible.

Ignored priority rules

In addition to conflicting priorities, there are rules that get ignored during the generation plan. This might happen if an input model doesn't have any concept of a language participating in a priority rule. Since there's no actual use of a language, the rule is ignored, and the 'Show Generation Plan' action reports them along with conflicting rules. Previous MPS versions used to include generators of otherwise unused languages into the generation process, now these generators get no chance to jump in.

Implicit priorities

Target languages (languages produced by templates) are considered as implicit 'not later than' rules. You don't need to specify these priorities manually. MPS automatically inserts "not later than" rules for all generator models in the source and target languages. It is important to understand that priority rules work on the model granularity level.

tip

This implicit priority rule between two generator models is ignored if an explicit priority rule is defined for these two models, one from the language that generates into the other language and one from the other language.

Model Transformation

Each group of mappings is applied in a separate generation step. The entire generation session consists of as many generation steps as there were mapping groups formed during the mapping partitioning. A generation step includes three phases:

• Executing pre-mapping scripts

• Template-based model transformation

• Executing post-mapping scripts

The template-based model transformation phase consists of one or more micro-steps. A micro-step is a single-pass model transformation of an input model into a transient (output) model.

While executing micro-step MPS follows the next procedure:

1. Apply conditional root rules (only once - on the 1-st micro-step)

2. Apply root mapping rules

3. Copy input roots for which no explicit root mapping is specified (this can be overridden by means of the 'keep input root' option in root mapping rules and by the 'abandon root' rules)

4. Apply weaving rules

5. Apply delayed mappings (from MAP_SRC macro)

6. Revalidate references in the output model (all reference-macro are executed here)

There is no separate stage for the application of reduction and pattern rules. Instead, every time MPS copies an input node into the output model, it attempts to find an applicable reduction (or pattern) rule. MPS performs the node copying when it is either copying a root node or executing a COPY_SRC-macro. Therefore, the reduction can occur at either stage of the model transformation.

MPS uses the same rule set (mapping group) for all micro-steps within the generation step. After a micro-step is completed and some transformations have taken place during its execution, MPS starts the next micro-step and passes the output model of the previous micro-step as input to the next micro-step. The whole generation step is considered completed if no transformations have occurred during the execution of the last micro-step, that is, when there are no more rules in the current rule set that are applicable to nodes in the current input model.

The next generation step (if any) will receive the output model of previous generation step as its input.

tip

Intermediate models (transient models) that are the output/input of generation steps and micro-steps are normally destroyed immediately after their transformation to the next model is completed.

To keep transient models, enable the following option:

Settings-> Generator Settings-> Save transient models on generation

See also:

• Saving Transient Models

• Using Generation Tracer Tool

Handling of node attributes during generation

Node attributes constitute generic extension mechanism, thus Generator shall preserve attributes along the transformation process (unless attribute designer opts not to keep them) without explicit support in any template. When an input node is transformed to another node, Generator copies attributes of the input node to the output. Copy is controlled by newly introduced drop attribute rule only, and happens regardless of @attribute info specification (i.e. its attributed concept or multiple restrictions). The fact that transformation rule may have produced attribute node itself is not taken into account (i.e. if a reduction rule explicitly copies node attributes to a newly created output node, the attributes would get duplicated due to automatic copy of attributes. However, it's rare for a reduction rule to copy node attributes, and the issue, if ever shows up, is easy to mitigate with drop rules).

While copying attributes of a node, Generator consults drop attribute rules(newly introduced in MPS 3.3, reside next to abandon root rules) to see if language designer don't need these attributes to survive transformation process. This rules are quite similar to abandon root rules - when any rule is triggered, attribute is not copied into output model.

With the growing adoption of attributes and their increasing complexity, we enabled the generator to transform the attribute contents using the regular template processing rules:

• references to nodes in the same model get updated to point to the respective nodes in the output model

• reduction rules are applied in order to transform children of the attribute node.

In-place transformation

Generators for languages employed in a model are applied sequentially (aka Generation Plan). Effectively, each generation step modifies just a fraction of original model, and the rest of the model is copied as-is. With huge models and numerous generation steps this approach proves to be quite ineffective. In-place transformation tries to address this with a well-known 'delta' approach, where changes only are collected and applied to original model to alter it in-place.

In version 3.1 in-place transformation is left as an option, enabled by default and configurable through the Project settings -> Generator. Clients are encouraged to fix their templates that fail in the in-place mode, as in-place generation is likely to become the only generation mode later down the road.

Use of in-place transformation brings certain limitations or might even break patterns that used to work in the previous MPS versions:

• Most notable and important - there's no output model at the moment when rule's queries/conditions are executed. To consult the output model during the transformation process is a bad practice, and in-place transformation enforces removing it. Access to the output model from a transformation rule implies certain order of execution, thus effectively limiting the set of optimizations applicable by the MPS generator. The contract of a transformation rule, with a complete input and a fraction of the output that this particular rule is responsible for, is more rigorous than "a complete input model" and "an output model in some uncertain state".

• The output model is indeed there for weaving rules, as their purpose is to deal with output nodes.

• The process of delta building requires the generator to know about the nodes being added to the model. Thus, any implicit changes in the output model that used to work would fail with in-place generation enabled. As an example, consider MAP-SRC  with a post-process function, which replaces the node with a new one:postprocess: if (node.someCondition()) node.replace with new(AnotherNode);. Generator records a new node produced by MAP-SRC, schedules it for addition, and delays post-processing. Once post-processing is over, there's no way for the generator to figure out the node it tracks as 'addition to output model' is no longer valid and there's another node which should be used instead. Of course, the post-process can safely alter anything below the node produced by MAP-SRC, but an attempt to go out from the sandbox of the node would lead to an error.

• Presence of active weaving rules prevents in-place transformation as these rule require both input and output models.

Generation trace

Much like in-place transformation, the updated generation trace is inspired by the idea to track actual changes only. Now it's much less demanding, as only the transformed nodes are being tracked. Besides, various presentation options are available to give different perspective on the transformation process.