Incrementally Re-Evaluating OCL Expressions Using the Impact Analyzer

Incrementally Re-Evaluating OCL Expressions Using the Impact Analyzer

When Ecore metamodels use many OCL invariants and the models constrained by these invariants grow large, re-evaluating the invariants becomes a performance challenge. As OCL expressions can navigate freely across resource boundaries, changes to a model element in one resource can easily affect invariants for model elements in other resources. To reliably catch all invalidated constraints after a change it would be necessary to re-evaluate all invariants on all their context objects regardless their resource. This does not scale sufficiently well.

The ImpactAnalyzerFactory interface allows tool builders to efficiently determine a much smaller set of model elements on which re-evaluation of expressions is necessary after a change.

Given an OCL expression, the factory can be used to create an impact analyzer for a single expression as follows:

final OCLExpression e = ...;
final ImpactAnalyzer impactAnalyzer =
     e,      // the expression to re-evaluate incrementally
     false,  // whether to re-evaluate when new context objects appear

The impact analyzer obtained this way can create a change notification filter which can then be used to register for notifications that indicate a change which may affect the value of the expression. Consider the following example:

ResourceSet myResourceSet = ...;
EventFilter filter = impactAnalyzer.createFilterForExpression();
EventManager eventManager =
eventManager.subscribe(filter, new AdapterImpl() {
    public void notifyChanged(Notification notification) {
        Collection<EObject> valueMayHaveChangedOn =
        for (EObject eo : valueMayHaveChangedOn) {
         // ... perform some re-evaluation action of e for context eo here

The event manager can be used to register the event filters of several OCL expressions with their respective adapters. The adapters for different expressions do not have to be distinct but may optionally be shared. The following figure shows how the classes relate, as a UML class diagram:

For each OCL expression a new impact analyzer is used. The event filters produced by them can be registered with the same event manager. The following figure shows a typical instance collaboration diagram in UML notation.

The event manager factory and the event managers it produces lay the scalable foundation for the re-evaluation process. Even if it has to manage many subscriptions, its performance does not degrade as it would if the change notification filters were evaluated one after the other. With this it becomes possible to register many OCL expressions for change impact analysis as shown above. The figure below shows a typical default configuration of an event manager, as a UML instance collaboration diagram.

The event manager in the figure is configured to listen to the change events coming from anything inside the resource set. In this example it is shown with three different event filters, each coming with its own adapter handling those change notifications matches by the respective filter.

As described in more detail in the Javadoc, event managers may be re-used, temporarily deactivated and new ones may be created specifically upon request. This way it is possible to have several event managers, e.g., listening for changes during different phases of a model’s life cycle without having to create and initialize the event managers again and again. Also, an event manager is not restricted to listen to the changes of exactly one resource set. The following figure shows a not so typical configuration, again as a UML instance collaboration diagram.

Using the Impact Analyzer in EMF Editors

The org.eclipse.ocl.examples.impactanalyzer.ui package provides experimental support for embedding the impact analyzer in EMF editors. Adding the lines

@SuppressWarnings("unused")  // not read; just used to avoid GC  
private Revalidator revalidator; //  from collecting re-validator

to the field declarations of an editor class, and adding the lines

revalidator = new Revalidator(editingDomain, OCLFactory.INSTANCE,

at the end of the editor class’s createModel() method turns on this experimental support for the respective editors. Consequently, changes in the editor’s ResourceSet will trigger the re-evaluation of the affected invariants on the set of context objects determined by the impact analyzer. Error markers of successfully validated constraints will be removed, markers for invalid constraints are produced. As is obvious also from the examples part of the package name, this is not yet production-ready code. It may change or disappear without notice.

Algorithm Outline

The basic idea on which the impact analyzer’s algorithm is based is this: take the EMF change notification and see which elementary subexpressions, such as property call expressions, are immediately affected by the change. From these pairs of (subexpression, model element) it is possible to walk the expression tree and navigate “backwards” from the model element to the candidates for the self variable for which the subexpression may evaluate to the model element indicated by the notification. Recursive operation calls and general ->iterate(...) expressions complicate matters and lead to a recursive algorithm for the impact analysis.

It is permissible to use calls to OCL-specified operations. The impact analyzer will trace changes considering the called operation’s body expression.

The use of allInstances inside an expression may be nasty for analyzing the impact of a change because then it may no longer be possible to trace the change back to the possible values for self. In those cases the impact analyzer will simply “give up” and return a collection of all instances of the expression’s context type and its subtypes.

Impact Analyzer Configuration, Scopes

The impact analyzer can be created in several different configurations as explained in detail in the Javadocs . Particularly noteworthy is the relationship between the OppositeEndFinder and the way an allInstance expression is evaluated. Both depend on a notion of lookup scope. EMF does not provide any particular rules or conventions in this regard other than assuming that what has been loaded into a ResourceSet is what tools can see. While this is a working procedure for forward navigation, it doesn’t help in defining a scope for allInstances and reverse navigation when there is no explicit opposite property.

For this purpose, Eclipse OCL has introduced the OppositeEndFinder interface through which reverse navigations of references and allInstances lookups can be performed. Its default implementation is based on the EMF default which is to consider the contents of a ResourceSet the universe. Other implementations are possible, however, such as one that uses EMF Query2 to perform the necessary lookups.

A default OCL evaluator will always use the current ResourceSet to determine the set of all instances of a type. If a client has used an opposite end finder that implements a certain lookup strategy then the default allInstances evaluation is most likely inconsistent with the scope definitions of that opposite end finder. To avoid such problems, a specific OCL factory can create OCL instances that ensure consistency between opposite navigation and allInstances evaluation.

Other configuration options (see ActivationOption concern the specific algorithm used for tracing back from a change notification to the set of context objects for which the expression may have changed its value. The default selection has proven to be the fastest for a set of benchmarks. However, mileage may vary, and we’d like to encourage users to experiment also with the non-default configurations.