Teamworking
Contents
Overview
Modelling can be used to address large-scale business problems, where teams of individuals collaborate to produce different parts of a model. Teamworking raises the issue of model management: managing different versions of a model and merging different versions into a single coherent whole.This chapter describes an approach to model based teamworking that allows models to be distributed across different development teams. Each team can work independently on their version of the model. The approach then allows the different versions to be compared for consistency. Inconsistencies are identified and can be offered up for conflict resolution. Once the versions are consistent then the approach allows them to be merged into a single model.
The approach uses a meta-description of modelling data and therefore does not depend on the language that has been used for modelling. This is attractive because model comparison engines can be constructed once and then used throughout an organisation.
Systems that support teamworking, such as CVS and SVN provide functionality that is shown in figure . A root system is modified independently by two or more teams. The modifications are referred to as deltas leading to two or more new versions.
Once satisfied that their independent versions are OK, the teams want to merge. To do this the versions must be compared for inconsistencies which must be resolved. Inconsistencies may occur because each team has modified an element in the root in a different way. Resolution may involve one team changing their version so that it is consistent with the other or may involve both teams removing the conflicting parts.
Once the conflicts have been resolved, the versions can be merged to provide a new baseline of the system. This process can be performed any number of times and allows multiple teams to work concurrently on a large system.
Conventional technologies for teamworking, such as CVS and SVN, work with files. They compare the contents of the files on a character-and-line basis. Conflicts arise when two versions of the same file have differing changes at the same position.
Modelling technologies have a similar requirement to teamworking as a file-content based approach. It is worth comparing the basic features of the technologies, since the key aspects are similar whilst the implementation details are different. When comparing files the following features are important:
- Files have unique identifiers: their names within the file-system. These identifiers are used by the teamworking technology when comparing files for potential conflicts, and when merging files.
- Files have an internal structure: the lines and characters. The internal structure of a file is used by the teamworking technology when comparing files for potential conflicts. The internal structure is also used when merging files.
- Model elements must have unique identifiers. These may be automatically imposed by the system or may be supplied by the user. For example, when a model element is created it may be tagged with the unique combination of the user's details and the current time and date. Alternatively, a naming scheme within the model may be used to uniquely identify elements. In practice it may be necessary to use a combination of system and user supplied identifiers.
- Models have internal structure. At the meta-level, all model elements are just objects with named slots. Conflicts arise when the same slot of a uniquely tagged object is changed by both development teams. Also, when merging models, changes to different slots of the same object can be merged providing that it is uniquely tagged.
let counter = 0
in @Operation newTag()
counter := counter + 1;
counter
end
end
@Class TaggedObject
@Attribute tag : Integer = newTag() (?,!) end
end
As noted above, model elements are just objects. Provided that they are uniquely tagged and the structure of the data is known, model-based teamworking technology can be applied to any model. The example data forms binary trees where the elements are all uniquely tagged and the leaves of the tree have arbitrary data elements attached to them.
The Approach
The following figure shows an overview of the proposed tool support for teamworking:
If the two versions produce inconsistencies then they must be rationalized. An inconsistency involves an element from each version and the slot that has been modified. An inconsistency is rationalized when one of the modifications (or both) is removed from the corresponding delta. Once removed, the process is performed again, producing fewer inconsistencies.
The rationalization process continues until no inconsistencies arise. In this case the deltas are independent and can be performed in any order to produce a final merged model.
The Delta Machine
Teamworking produces two or more versions based on a shared root. Each version adds new elements and makes modifications to the root. Large parts of the root will be left unchanged and can be ignored when the versions are compared and merged. It is therefore useful to be able to isolate the changes or deltas that have been applied by each team to the shared root. This section describes a language and its execution engine used to model deltas.Model elements are uniquely tagged objects. An object consists of slots; each slot has a name and a value. A value is either atomic (such as an integer or a string) or is an object. Models are arranged as graphs where the nodes in the graph are values and the edges are slots. A model-graph may have cycles, i.e. an object can refer directly or indirectly to itself.
A delta is a modification to a model. A delta can change a slot value. The new value may be atomic, may introduce a reference to an existing object or may create a completely new object. Imagine a machine that takes as input a model and a delta and runs the delta producing a new model. The delta machine is shown below:
A delta is a sequence of instructions, the machine is defined by a class called Update. The delta machine execution engine is defined below:
@Operation run1(instr)
@Case instr of
(1) Push(v) do
stack.push(v)
end
(2) Pop() do
stack.pop()
end
(3) Dot(n) do
stack.push(stack.top().get(n))
end
(4) Set(n) do
stack.top().set(n,stack.pop())
end
(5) Ref(c,i) do
stack.push(table.get(i))
end
(6) New(c,i) do
let o = c()
in o.setTag(i);
table.put(i,o);
stack.push(o)
end
end
else self.error("Unknown instr: " + instr.toString())
end
end
The machine executes by case analysis on the instructions. Each instruction is popped from the instruction stack and performed by the operation run1. Case (1) pushes an atomic value v onto the stack. Case (2) pops the value at the head of the stack. Case (3) expects an object at the head of the stack and pushes the value of slot n onto the stack. Case (4) expects a value above an object on the stack. The value is popped and the slot named n is updated. Case (5) pushes an existing element in the model (held in the table) onto the stack. Case (6) creates a new object of type c with tag i and pushes it onto the stack.
The tree before the modification is:
and after modification:
The delta machine instructions that perform the change are as follows:
Dot(left)
Dot(data)
Pop()
Push(E)
Set(data)
Set(left)
Dot(right)
Dot(data)
Pop()
Push(D)
Set(data)
Set(right)
Dot(left)
Push(E)
Set(data)
Set(left)
Dot(right)
Push(D)
Set(data)
Set(right)
Model Comparison
Teamworking involves a root model and two or more versions. Given a root and a version, a delta is a machine program that is produced by comparing the root and version. The result is a machine program that captures exactly the steps necessary to transform the root into the version. This section describes a model comparator that is used to produce a delta.Consider the before and after snapshots shown above. Suppose that the before model is the root and the after model is a version produced in a teamworking scenario. What steps are necessary to produce the delta that transforms the root into the increment?
Starting with the root element of both models, compare the objects. They both have the same tag and therefore at this stage no changes have taken place. Now compare slots from each object. Start with the left slot: traverse the slot, emit a Dot instruction, compare the values found there, and emit a Set instruction. At this stage the delta is:
Dot(left),...,Set(left),...
Dot(left),Dot(data),...,Set(data),Set(left),...
Dot(left),Dot(data),Pop(),Push(E),Set(data),Set(left),...
The code below shows the operation which is the entry point for the object comparison:
@Operation compareObjects(new,old,oldDB,compared)
if tag(new) = tag(old)
then
if compared.hasKey(tag(new))
then Seq{}
else
compared.put(tag(new),tag(old));
compareSlots(slots(new),slots(old),oldDB,compared)
end
elseif oldDB.hasKey(tag(new))
then
let oldSlots = slots(oldDB.get(tag(new)))
in Seq{Pop(),Ref(new.of(),tag(new))} +
compareSlots(slots(new),oldSlots,oldDB,compared)
end
else Seq{Pop()} + newObject(new,oldDB,compared)
end
end
The second part of the compareObjects operation has not been covered by the running example. If the tags of the new and old objects are not the same then this means that the old object has been replaced with the new object. In this case, either some existing element from the root model has been linked into the model, or the new model contains a completely new object. This is determined using the oldDB which contains associations for all the tags in the root model.
Slot comparison is handled as follows:
@Operation compareSlots(newSlots,oldSlots,oldDB,compared)
if newSlots->isEmpty
then Seq{}
else
let newSlot = newSlots->head then
name = slotName(newSlot)
in @Find(oldSlot,oldSlots)
when slotName(oldSlot) = name
do let newSlots = newSlots->tail;
oldSlots = oldSlots->excluding(oldSlot)
in compareSlot(newSlot,oldSlot,oldDB,compared) +
compareSlots(newSlots,oldSlots,oldDB,compared)
end
end
end
end
@Operation compareSlot(newSlot,oldSlot,oldDB,compared)
let name = slotName(newSlot);
newValue = slotValue(newSlot);
oldValue = slotValue(oldSlot)
in if newValue.isReallyKindOf(Object)
then
Seq{DotObj(name,value.of(),tag(newValue))} +
compareObjects(newValue,oldValue,oldDB,compared) +
Seq{Set(name)}
else
Seq{Dot(name)} +
compareValues(value,oldValue,oldDB,compared) +
Seq{Set(name)}
end
end
end
The following operation:
@Operation newObject(new,oldDB,compared)
if compared.hasKey(tag(new))
then Seq{Ref(new.of(),tag(new))}
else
compared.put(tag(new),null);
Seq{New(new.of(),tag(new))} +
newSlots(slots(new),oldDB,compared)
end
end
Checking new slots is defined below:
@Operation newSlots(slots,oldDB,compared)
if slots->isEmpty
then Seq{}
else
let slot = slots->head
in newSlot(slot,oldDB,compared) +
newSlots(slots->tail,oldDB,compared)
end
end
end
@Operation newSlot(slot,oldDB,compared)
if value.isReallyKindOf(Object)
then
if oldDB.hasKey(tag(slotValue(slot)))
then
Seq{Ref(slotValue(slot).of(),tag(slotValue(slot)))} +
compareObjects(new,oldDB.get(tag(new)),oldDB,compared)
else newObject(slotValue(slot),oldDB,compared)
end
else Seq{Push(slotValue(slot))}
end +
Seq{Set(slotName(slot))}
end
If the slot value is an object that also occurs in the old model then a Ref instruction is emitted and the two objects are compared. Otherwise, if the value is an object it must be new, so further instructions are produced by newObject. Otherwise the value must be atomic so it is simply pushed. In all cases the last instruction emitted is a Set instruction to modify the newly created object at the head of the machine stack.
modify to produce:
Dot(left)
New(<Class Branch>,14)
New(<Class Leaf>,12)
Push(G)
Set(data)
Set(left)
New(<Class Leaf>,13)
Push(H)
Set(data)
Set(right)
Set(right)
Set(left)
Ref(<Class Branch>,14)
Set(right)
Model Slices
Teamworking involves a root model and two or more version models. The version models are produced by independent teams making modifications to the same root model. Many of the elements in the root models may be unchanged in the increments. When comparing the two versions for consistency it is useful to be able to ignore the unchanged elements. A model that describes just the changed elements in a version is called a slice. Two slices can be easily compared since they just contain the elements that have changed. Two models are inconsistent if the same elements have been changed in different ways; slices make consistency checking easy. This section describes how to slice a model with respect to a delta.The following model:
shows a slicing engine. Running a delta against a model using the slicing engine produces a slice; the engine is like the delta machine except that it interprets the delta instructions differently. To slice a model with respect to a delta, the model is pushed onto the slicing engine, the delta is loaded onto the machine and the instructions are performed. The result at the head of the stack is an instance of the sliced object model; only those things that are changed are contained in the slice.
The engine runs a slicing interpreter:
@Operation slice(instr)
@Case instr of
(1) DotObj(n,c,i) do
if table.hasKey(i)
then stack.push(table.get(i))
else
let o = Object(c,i)
in table.put(i,o);
stack.push(o)
end
end
end
(2) New(c,i) do
let o = Object(c,i)
in stack.push(o);
table.put(i,o)
end
end
(3) Set(n) do
let value = stack.pop() then
obj = stack.top();
slot = Slot(n,value)
in obj.addToSlots(slot)
end
end
(4) Push(v) do
stack.push(Atom(v))
end
else self.error("Unknown instr: " + instr.toString())
end
end
Case (2) records the creation of a new object. Case (3) records the update of a slot; the value is at the head of the stack. Case (4) pushes some atomic data onto the stack ready for updating a slot.
created by running the delta against the starting snapshot:
The slice clearly shows that the changed slots are the data of the left hand branch and the data of the right hand branch.
Conflicts
Given two slices that arise from the same root model, it remains to compare them to see if the changes are compatible. Since slices just contain the changes that have occurred, conflict detection involves determining whether the same slots have changed differently in the two slices. This section defines an operation that takes two slices and produces a set of conflicts; a conflict records two objects, a slot and two incompatible values.The main conflict detection mechanism is as follows:
@Operation objectConflicts(o1,db1,o2,db2)
let S1 = o1.slots().name;
S2 = o2.slots().name then
common = S1->intersection(S2);
C1 = slotChanges(o1,S1 - S2,db1,db2);
C2 = slotChanges(o2,S2 - S1,db1,db2) then
Conflicts = C1 + C2
in @For name in common do
let s1 = o1.slot(name);
s2 = o2.slot(name) then
C = conflictingSlots(o1,s1,db1,o2,s2,db2)
in Conflicts := Conflicts + C
end
end;
Conflicts
end
end
The slot changes are calculated using the following operation:
@Operation slotChanges(o1,slots,db1,db2)
let C = Set{};
v = s.value()
in @For name in slots do
let s = o1.slot(name)
in if v.isKindOf(Object)
then
if db2.hasKey(v.id())
then
let o2 = db2.get(v.id())
in C := C + objectConflicts(v,db1,o2,db2)
end
else C := C + slotChanges(v,slots(v),db1,db2)
end
end
end;
C
end
end
end
Slots with the same name may conflict as described by the following operation:
@Operation conflictingSlots(o1,s1,db1,o2,s2,db2)
let n = s1.name();
v1 = s1.value();
v2 = s2.value()
in if v1.equal(v2)
then
if v1.isKindOf(Object)
then objectConflicts(v1,db1,v2,db2)
elese Set{}
end
else Set{Conflict(n,o1,v1,o2,v2)}
end
end