MC2 merging algorithm
Last updated at 4:57 am UTC on 22 June 2007
By Avi Bryant:
In MC2, merging is done with each element independently. So, let's say you're loading a package with three methods: A,B, C. The image has a version of each method, call them Ai, Bi, Ci. The version of the package you're loading also has a version of each method, call these Ap, Bp, Cp. The job of the merging algorithm is to decide which of Ap, Bp, Cp to load, which to ignore, and which to declare to be conflicts.
To make this decision, we need some extra information: for each method version, which other method versions does it supercede? Every method version carries around a set of references to the method versions it supercedes. Both the versions in the image and those in the package version you're loading will have this information.
Back to the example, as well as the image and package versions, which we have in full, let's also assume some earlier set of methods Ao, Bo, Co which we don't have available but can refer to through their UUIDs ("hashstamps" in MC2).
Let us say that Ai supercedes (Ao, Ap), Bi supercedes nothing (), Ci supercedes only (Co). Ap supercedes (Ao), Bp supercedes (Bi, Bo), Cp supercedes (Co).
Ok, now for the algorithm.
- If the version in the image supercedes the version you are loading, do nothing. This is the case with method A, because Ai supercedes Ap.
- If the version you are loading supercedes the version in the image, load that version, and it becomes the new image version. This is the case with method B, because Bp supercedes Bi.
- If neither case 1 nor case 2 applies, you have a conflict. This must be manually resolved by the user, who will create a new version. This new version becomes the image version, and supercedes the two conflicting versions as well as everything they superceded. This is the case with method C. The user will need to create a new version, Cn, perhaps by choosing the source of Ci or Cp or perhaps by combining them and editing them in some way. Cn will then supercede (Ci, Cp, Co).
The new state of the image is Ai, Bp, Cn.