Optimistic versioning is a key component in supporting collaborative workflows. Text-based versioning has been widely adopted for versioning code, but in model-driven engineering, dealing with visual concrete syntaxes, new methods are required. In the case of blended modeling, a mixture of both textual and visual syntaxes, concurrently editable and synchronizable, introduces additional challenges. We propose a type of operation-based versioning to record not only user edits, but also bi-directional change propagations between concrete and abstract syntax. This way we can support blended modeling with layout continuity, and flexible handling of missing information (e. g., layout information) when rendering changes from abstract to concrete syntax. In addition, the proposed versioning approach enables collaborative conflict resolution by allowing partial conflict resolution, thus deferring a final resolution.
Model-driven engineering (MDE) has become widely accepted as prime enabler for the creation
of increasingly complex software-intensive systems. In addition to graphical models, various
model representations such as tabular or textual ones are typically used. The flexible use of
diferent representations (concrete syntax (CS)) for one and the same model (abstract syntax
(AS)) is also called blended modeling. The ability to switch between diferent representations
allows the user to choose the one that is most useful and eficient for the current task [
Complex systems are developed in teams in both asynchronous and synchronous collaborative
environments [
In addition to the complexity of concurrency in (a)synchronous collaboration (i.e. branching, merging, and dealing with conflicts), an orthogonal problem of blended modeling is the challenge of (multi-)CS and AS synchronization. For instance, there may be concurrency on the same l ivsau SC
S A initial version
:State initial version l tua S state {} txe C initial version
concurrent rse add rountangle a p
:State parent
:State readd state, parent link d n e r (omitted from example)
merge red remove rountangle n e r
no conflict :State rse remove state a p state {} erase text
:State merge parent
:State conflict (require-delete) merge (omitted from example)
Legend creation deletion or on diferent CSs that are being synchronized (see Figure 1 and Section 2). Another issue of blended modeling is that of missing information when switching between CS representations. For example, if an element is added in textual syntax, the position of the new corresponding element in a graphical syntax remains unknown.
Versioning systems for “code” (e.g. git [
To overcome this limitation, we propose to combine operation-based versioning with incremental bi-directional change propagation to enable (a) arbitrary mappings between CS and AS, with traceability between CS and AS, (b) blended modeling with layout continuity and flexible handling of missing (layout) information, and (c) reuse of CS editing environments for diferent languages. Additionally, as part of our operation-based versioning approach, we propose a new way to persist merge conflicts, to allow recording of the steps taken in conflict resolution.
Our approach should not be confused with projectional editing [
The remainder of the paper is structured as follows. In Section 2, we introduce a running example that is used to illustrate our proposed solution presented in Section 3. Section 4 discusses related work and Section 5 concludes with an outlook on future work.
To illustrate our approach, we introduce a (visual) CS and AS for a very limited subset of the Statecharts formalism. On the CS side, we have 2D drawings of rountangles (rounded rectangles) with geometries. On the AS side, we can have State objects, between which a “parent” association exists (every State can have 1 parent). The correspondence relation between CS and AS is as follows: There exists a one-to-one mapping between rountangles and State objects, and whenever a rountangle is geometrically inside another, a parent link between their Visual CS Editor
Visual CS Metamodel
Language-independent components depends on Versioning Data Structure
History Graph
Language-specific components Correspondence depends on AS Metamodel
Metamodel depends on depends on
Parser Renderer
Legend
Explained in this paper Future work Textual CS Editor
Textual CS Metamodel synchronize synchronize
Dependency Graph read append
Collaboration Service corresponding State objects must exist. Additionally, we assume that there is a textual CS, that we do not describe here as it does not add additional insight.
Figure 1 shows evolving CS and AS models. Initially, we have a version of a visual CS model with a single rountangle, of the corresponding AS model with a single State, and the corresponding textual CS model. Then, concurrently, a change happens to the visual and textual CS models. In the visual model, an inner rountangle is added (producing ′ ) and, concurrently, in the textual model, some text is erased (producing ′′ ). Both changes could be propagated (parsed) to the AS, and subsequently rendered to the other CS. How do we represent these changes, and how do we merge them? We intuitively understand that there will be a merge conflict, at least at the level of the AS: a State object is being deleted, while at the same time, it is the target of a newly created parent link.
There may be many meaningful ways to resolve such a conflict, but this is not our focus here. In this paper the main focus is on recording (concurrent) changes and (concurrent) change propagations, on and between CS and AS.
Note that in the remainder of this paper, we assume that text removal in ′′ has already been parsed to produce ′′. This way, we can focus on the visual CS and the AS, which are suficient to explain bi-directional change propagation (the main building block of blended modeling), combined with concurrency.
We introduce a set of components that can become part of a collaboration architecture. Their role in a possible architecture is shown in Figure 2.
We explicitly distinguish between language-specific and language-independent components.
In our approach, CS and AS are separate, evolving models, each conforming to their own
metamodel, as proposed by Van Tendeloo [
The language-independent component collaboration service is left underspecified. Among its Rountangle
1
Geometry + x: float + y: float + width: float + height: float
CorrState
2 CorrParent
State
parent 0..1
1 + constraint: "no parent link cycles" + constraint: "the parent link referred to by CorrParent must connect the 2 States referred to by the same CorrParent" many tasks is synchronization of CS editors with evolving CS models, (networked) synchronization between collaborators, and synchronization between CS and AS models. For the latter, it invokes the parser and renderer functions. This service uses the versioning data structure to record the edit history of models. We will explain this component, and why it is especially well suited for blended modeling.
The components presented in this paper are deployment-independent. For instance, the versioning data structure could be deployed centrally or decentrally.
A change to a CS may cause corresponding changes to the AS. Change propagation from CS to AS is called parsing. Subsequently, this change to the AS may cause changes to other CSs. Change propagation from AS to CS is called rendering1.
Parsing and rendering must happen incrementally for several reasons: The first reason is performance (not having to parse/render from scratch after every change). The second reason is layout continuity when rendering a visual update (not regenerating a new layout from scratch, which would be confusing to users familiar with an existing layout). The third reason is that in a multi-user collaboration scenario, propagating concurrent changes must cause new concurrent changes (instead of new concurrent models), that can be merged accurately and eficiently.
The user only interacts with a model through a CS, so any information (e. g., inconsistencies) from the AS or semantic level must also be visualized in the CS. CS and AS can relate to each other in nontrivial ways, and inferring this information a posteriori would be complex, and nondeterministic (more than one solution). We therefore persist traceability information between CS and AS elements, and keep it up-to-date, every time changes are propagated.
We persist traceability information between one CS and one AS model in a correspondence
model, an idea taken from triple graph grammars (TGGs) [
Running example: Figure 3 shows the metamodels (MM) for “the AS of the CS” ( , in blue), the AS ( , in red) and the correspondence ( ). The correspondence MM includes the elements of the CS and AS MMs, and defines two correspondence object types (CorrState and CorrParent). CorrState relates one CS rountangle to one AS State, and CorrParent relates two CS rountangles with geometrical enclosure to a parent link between their corresponding AS States.
Note that although we adopt some ideas from TGGs, we do not require change propagation rules to be specified as TGGs - our approach is neutral with respect to rule specicfiation, and rules may even be specified imperatively.
Instances of CS, AS, and correspondence models evolve. We rely on an underlying versioning
system (explained in Section 3.4) to persist every change in each of these models
(operationbased versioning [
Running example: Figure 4 shows the three metamodels from Figure 3 at the top. Below, we see a history graph of the model versions from Figure 1, and their conformance to the meta-level. We saw that ′ and ′′ were produced by concurrent user edits. In our history graph, we simply record these model versions, and the relation to their parent version ( and , respectively). Parsing and rendering only produces new model versions. Parsing ′ produces ′ and ′, and rendering ′′ produces ′′ and ′′. All pairs (′, ′′) are concurrent, and when merged, produce model ′′′ (with ∈ { , , }).
We will now explain our versioning approach in more detail. We will see what precisely makes up a model version, how we persist changes, how we relate changes to CS and AS to each other, and how we detect conflicts.
<<enumeration>> 1 type DependencyKind
In this section, we present a new and application-agnostic versioning approach. Our approach
can be classified as operation-based according to Brosch et al. [
Our versioning approach consists of two data structures, called History Graph and Delta Graph. We will first explain the Delta Graph, which consists of deltas and dependency links between them.
Deltas. A delta (colored in green) records a change to a model. A delta may be caused by a user edit, or a propagated change (model synchronization). We only record the efect of the change (i. e., atomic CRUD operations on model elements), as opposed to the cause (e.g. the edit command). Rcording the cause as well may have advantages for edit history comprehensibility and analysis [12, 13], but this is not our focus. Deltas are transactional, meaning that they are either fully applied to the model, or not at all.
Dependencies. Deltas can depend on the efect of other deltas. We persist these dependencies between deltas in a directed, acyclic and append-only Dependency Graph in order to eficiently detect conflicts between deltas, as we will discuss later. Dependencies can be of three diferent types: update, require, and delete.
Figure 6 shows the Dependency Graphs for CS, AS, and correspondence of our running example. Delta 1 results in the creation of the outer rountangle. Further, there is delta 2, that creates the inner rountangle. The two deltas do not depend on each other and can, therefore, be applied to the model in any order, producing ′ . However, delta 3 deletes the outer rountangle, and in consequence, 3 has a delete dependency on 1. If there were a delta (not part of our running example - only for illustrative purposes) that resizes the outer rountangle, it would have an update dependency on 1. The third type, require, occurs when a delta requires the existence of an element created by an other delta without updating the required element itself, e.g., when connecting an edge to an element, as in 2. <update>
<delete> : create outer rountangle : create inner rountangle : delete outer rountangle : resize outer rountangle <require> <delete> <require>
<delete> : create outer rountangle, state : create inner rountangle, state + parent link : delete outer rountangle, state : create outer state : create inner state + parent link to outer state : delete outer state Legend
Version
Conflicts. Two deltas that share a dependency on the same model element are conflicting if at
least one of the deltas alters that model element. Conflict types are update-update, update-delete,
and require-delete [
Continuing our running example, deltas 1 and 2 are independent and not conflicting, because they do not depend on a common delta. In consequence, they can both be part of the model state without any Conflict as it is the case in ′ . However, (update geometry of outer rountangle) and 3 (delete outer rountangle) depend concurrently on the same model element 1 and are, consequently, in an update-delete conflict as indicated in orange color in Figure 6 on the left.
While the Dependency Graph imposes a partial order on the execution of deltas to obtain a valid state, it does not contain any information about the actual order in which deltas were added (or omitted, explained later) by diferent collaborators, altering the model state. Moreover, we want to be able to point to specific model versions. We therefore introduce the History Graph, which contains versions and their (partial) order.
Versions. A version (colored in various shades of purple), is a (possibly empty) set of deltas, that when replayed, produces a model state. In a version, all dependencies of all contained deltas must also be contained, a property called left-closedness in the theory of Event Structures [14]. The order of versions is persisted in a History Graph, which is also directed, acyclic and append-only. Versions refer to their predecessor(s) by parent links, whose semantics are identical to parent links in git.
Figure 4 of our running example already showed a History Graph, with branching into :State OR
OR concurrent versions (′ and ′′) and merging (′′′). Figure 6 visualizes the diferent versions as sets of deltas.
The diference between any two versions and is simply a set of added deltas ( ∖ ) and a set of removed deltas ( ∖ ). Versions can be trivially merged by taking the union of their deltas, which preserves left-closedness.
Superpositions. Versions are allowed to contain conflicting deltas. This way, conflicting states are not just temporary, in-memory phenomena during the merge process, but persistent, which has two advantages: (1) We can record not just the occurence, but also steps taken in the resolution of the conflict (as a sequence of versions). This may be valueable information. (2) Conflicts are non-blocking, and the modeler can continue working on non-conflicting parts of the model.
We use the term superposition for versions containing conflict(s) (reference to quantum physics), because the version can be interpreted as containing all possible conflict resolutions. A conflict (= a pair of deltas) is resolved by excluding from the next version at least one of the conflicting deltas (and its dependants). Possibly a new delta is introduced, replacing both of the conflicting deltas.
In Figure 6, the version ′′′ is in a superposition, because it contains deltas 2 and 3 in a require-delete conflict. The possible (non-conflicting) versions contained in the superposition are {1} × { 2, 3, 1 , 2 , ...}, where is a new (e.g. manually added) delta that replaces both conflicting deltas.
Conflicts in versions can be visualized by presenting the efects of non-conflicting deltas in a side-by-side view. Figure 7 shows ′′ and in their the superposition.
We now define an interface for the parsing and rendering behavior. Parsing and rendering does not alter models in-place, and their only efect is that they produce new model versions. We specify their interfaces as pure functions (i.e. functions without side-efects, that only have read access to their inputs) that return the newly produced model versions. Purity keeps us honest, forcing us to be explicit about all inputs, and guaranteeing that results are repeatable, which has benefits in distributed environments: For instance, in live collaboration on the same CS model, all users could parse the model locally (to reduce latency), while guaranteeing that their results are identical.
In order to parse incrementally, the parsing and rendering functions need access to the most recent correspondence model, and to the respective CS or AS changes. As output, a new correspondence model is produced, which includes a new AS or CS model, respectively.
Running example: In our example, the inputs and outputs are as follows:
(, ( , ′ )) = (′, ′) (, (, ′′), * ) = (′′, ′′ ) where is the diference (i.e. added, removed elements) between two model versions, which we can easily compute from our deltas. In the rendering function, the asterisk * denotes the possibility of having additional parameters, which we will motivate in the next section.
The types of parsing errors that can occur are specific to both CS and AS, so we feel that they should be defined on the level of the correspondence metamodel. When a parsing error occurs, an object describing the error should be created in the returned correspondence model.
Rendering is usually non-deterministic in the sense that an AS model can be mapped correctly onto many CS models, due to missing information (e.g. about layout). An automated rendering function can however only produce a single result, which may not always match the user’s intention (which ultimately remains unknown to the computer). Therefore, we believe we must support human interaction in rendering. We see several complementary ways to support this.
First, the rendering function could have additional input parameters, such as a random seed or a layout heuristic to optimize, that tweak the result. We could further present a number of prerendered solutions to choose from, based on frequently chosen parameter values. Furthermore, after rendering, the user can make manual improvements in the CS model. Perhaps a feature in the CS editor to “freeze” the AS (guaranteeing that the user cannot accidentally alter the AS while altering the CS) could be beneficial here. This would be easy to implement since we know when a CS change causes a AS change. Finally, by relying on versioning to record everything, changes do not have to be rendered (or parsed) immediately. For instance, in a scenario where a Statechart is being edited through a textual syntax, (interactively) rendering the visual syntax may be postponed until the visual syntax is actually opened. In the end, empirical study should point out preferred workflows. Our work can become a basis for such study.
For space reasons, we limit ourselves in the following to model versioning approaches. A
comprehensive overview of this topic by Brosch et al. can be found in [
Brosch et al. present in [17, 18] a taxonomy of conflicts together with a visualization of the diferent conflicts (conflict diagram). In this taxonomy, conflicts are either “overlapping changes” (competing changes, similar to our “conflicts”) or (constraint) “violations”. The overall approach is based on a tight coupling between AS and CS, but is extensible with language-specific features. In the graph transformation rules applied for conflict detection and resolution, only the elements of the AS are considered and also only (abstract) elements of the conflict diagram are generated. Layout problems arising during the rendering process of the conflict diagram are partially solved using simple heuristics preserving layout continuity. Layout conflicts in the original model are only handled in the simplest way by just preserving the layout of the merging user. More complex layout problems are not considered (and even cannot due to the restriction to the level of AS).
In contrast to this approach, we explicitly distinguish between CS and AS and thus, are able to detect and handle conflicts more precisely. In addition, due to our loose coupling of CS and AS via a correspondence model, we directly support blended modeling environments which is not the case in the AMOR project [19]. The proposed “conflict-tolerant merging of models” [13] by Wieland et al. is enabled by design in our approach including the information about “how this conflict was resolved and who was responsible for the resolution decision” [ 13]. The persistence of all (conflicting) deltas together with meta-information of the delta author fulfills this requirement.
In [
The work of Pietron et al. [12] presents an operation-based versioning system propagating user-performed edit operations. Compared to the approach in the course of this paper, their work focuses mainly on the AS and does not support multiple CS and their synchronization. Some CS-related operations, such as updating the layout of an element, are supported but lack a clear distinction from AS-related operations.
We presented a set of components and interfaces for collaborative modeling environments supporting CS reuse and blended modeling through loose CS/AS coupling, and bi-directional synchronization. By explicitly versioning CS, AS, and their correspondence, we can distinguish between conflicts on each of these levels, and synchronizations can happen asynchronously or even be postponed, which is especially useful when dealing with missing information while rendering. By allowing versions with unresolved conflicts to be persisted, we support deferred resolution of merge conflicts in a collaborative way, as suggested by Wieland et al. [13].
Currently, we are working on a formal, yet abstract description of a conflict and inconsistency detection algorithm and its demonstration in a prototypical web-based implementation of such a modeling environment. Another future research direction is the consideration of multiple layers between CS and AS with increasing abstraction levels (insideness, connectedness relation, etc.), to allow even more CS reuse between languages.
Author J. Exelmans is an SB PhD fellow at FWO (1S70622N). Author J. Pietron is partly funded by the project GENIAL!, which is partly funded by the German Federal Ministry of Education and Research (BMBF) within the research programme ICT 2020 (reference number: 16ES0875). for Model-Driven Engineering, volume LNCS 7320, Springer, Berlin, Heidelberg, 2012, pp. 336–398. doi:10.1007/978-3-642-30982-3_10. [12] J. Pietron, F. Füg, M. Tichy, An operation-based versioning approach for synchronous and asynchronous collaboration in graphical modeling tools, in: L. Iovino, L. M. Kristensen (Eds.), STAF 2021 Workshop Proceedings, volume 2999 of CEUR Workshop Proceedings, CEUR-WS.org, 2021, pp. 88–89. URL: http://ceur-ws.org/Vol-2999/fpvmdata4mdepaper3. pdf. [13] K. Wieland, P. Langer, M. Seidl, M. Wimmer, G. Kappel, Turning Conflicts into Collaboration, Computer Supported Cooperative Work (CSCW) 22 (2013) 181–240. doi:10.1007/s10606-012-9172-4. [14] G. Winskel, An introduction to event structures, in: J. W. de Bakker, W. P. de Roever, G. Rozenberg (Eds.), Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency, School/Workshop, Noordwijkerhout, The Netherlands, May 30 - June 3, 1988, Proceedings, volume 354 of Lecture Notes in Computer Science, Springer, 1988, pp. 364–397. doi:10.1007/BFb0013026. [15] T. Mens, A state-of-the-art survey on software merging, IEEE Transactions on Software
Engineering 28 (2002) 449–462. doi:10.1109/TSE.2002.1000449. [16] G. Taentzer, C. Ermel, P. Langer, M. Wimmer, Conflict Detection for Model Versioning Based on Graph Modifications, in: H. Ehrig, A. Rensink, G. Rozenberg, A. Schürr (Eds.), Graph Transformations, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 2010, pp. 171–186. doi:10/dcjxkr. [17] P. Brosch, M. Seidl, M. Wimmer, G. Kappel, Conflict visualization for evolving UML models,
J. Object Technol. 11 (2012) 2: 1–30. doi:10.5381/jot.2012.11.3.a2. [18] P. Brosch, Conflict Resolution in Model Versioning, Ph.D. thesis, Vienna University of
Technology, Vienna, 2012. URL: https://publik.tuwien.ac.at/files/PubDat_208975.pdf. [19] AMOR — Adaptable Model Versioning, 2009. URL: http://modelversioning.org/, last visited: 10/05/2022. [20] L. Nachreiner, A. Raschke, M. Stegmaier, M. Tichy, CouchEdit: A Relaxed Conformance Editing Approach, in: Proceedings of the 23rd ACM/IEEE International Conference on Model Driven Engineering Languages and Systems: Companion Proceedings (MODELS-C), ACM, 2020, pp. 1–5. doi:10.1145/3417990.3421401.