EMF Dos and Don’ts #11

EMF is a very powerful framework and with power comes…responsibility. You can achieve great things with minimum  effort using EMF, but if something goes wrong, you may also spend hours trying to figure out why. This blog post is part of a series on things you should do and things you should not do when using EMF. You can use the link to the series pilot to navigate to the start and the link below to navigate to the next blog once it is published.

EMF Dos #11: Carefully use EcoreUtil.delete()

This static helper methods is used in many projects, but often causes trouble. Before we talk about potential issues with this method, let us have a look at the JavaDoc to understand, what it is supposed to do:

“Deletes the object from its containing resource and/or its containing object as well as from any other feature that references it within the enclosing resource set, resource, or root object.”

As described before, EMF model instances are typically structured in a tree (containment tree), the root node of this tree is typically a Resource. Removing an EObject from this tree will de-facto delete it. As an example, it will not be serialized anymore. In the following example a call of EcoreUtil.delete() on EObject C will remove the containment reference from A to C. As there is no incoming reference to C anymore, the EObject is deleted.

image02

This sounds simple, but the second part of the description is the critical point. In the following example, C has two incoming references, the containment from A and a cross-reference from B. When deleting C, this cross-reference must also be deleted to keep a consistent model. Otherwise B would hold a dangling reference to an EObject, which is not part of the containment tree and which would not be serialized itself.

image00

For this reason, EcoreUtil.delete() takes care about removing incoming cross-references, too. While this is principally a good thing, it can cause two issues: Cross-References to Children

1. Cross-References to Children

EcoreUtil.delete() will only remove cross-references to the EObject you called the method on, but not its children. In the following example, deleting EObject C will still create a dangling reference from B to D (marked in blue). Only the red references are removed in this case.

image01

For that reason, there is a second method with a boolean parameter: EcoreUtil.delete(EObject toBeDeleted, boolean recursive), which will recursively visit all children of an EObject and remove incoming cross-references on them as well. While this keeps a consistent model, it can exaggerate the next issue.

2. Performance

To understand the potential performance problem of EcoreUtil.delete(), one has to understand how incoming cross-references pointing to the EObject to be deleted are identified. As the cross-references can be uni-directional, there is no efficient way to identify all other EObjects in a model instance, which hold a reference to the EObject to be deleted. That is the reason why all EObjects in the enclosing root EObjects, Resource or even Resource Set are visited and checked, regardless of whether they hold a cross-reference to the object to be deleted. If a cross-reference is found, it is removed. Therefore, the run-time of EcoreUtil.delete() is O(n), while n is the number of EObjects in a model instance. Even worse, this is only the case, if the model is already completely loaded in memory. If parts of the model are not yet loaded, the performance can be much worse, as those parts then need to be loaded during the delete operation. If you only deal with small models, this might never be a problem in your project, but models tend to grow over time.

There are two solutions for this issue. First, uni-directional references should be avoided completely, all references are bi-directional. In this case, you can implement a very efficient delete, as the cross-references can be removed from the side of the tree, which gets deleted (consider sub elements, too!). Second, the creation of a “cross-reference maps” in an additional data structure, which can help to find cross-references more efficiently. The cross-reference adapter, provided by EMF, helps to implement this, as it supports to be notified whenever a cross-references is added or removed. Model repositories such as CDO or EMFStore typically already implement a more efficient delete function like this. In both cases, using bi-directional references only and using cross-reference maps or a repository, you must not use EcoreUtil.delete.

By the way, the Delete Command, offered by the EMF framework shows the same behavior, meaning it searches recursively for cross-references and removes them.