Merging of label trees

[mzur]

Implement a procedure that allows merging of label trees. Merging should be done automatically if possible. A UI should be implemented that allows approval of automatic merge suggestions and resolving of conflicts. Maybe Git can help here, too (like in #31)?

[mzur]

I think this should be the (easier) way to go:

Label tree B should be merged into label tree A. Parse both label trees into a simple text format. Labels are ordered alphabetically (grouped by parent) in this format. Example:

First parent
- First child
- Second child
Second Parent
- First child
- Second child

Keep a map of line number to label ID. Now a simple diff can be performed between the textual representations of A and B. This should show all labels of B that are not present in A, all labels of A that are not present in B and all changed label names. The diff can be displayed in a view like this (from MELD): These cases can exist:

• A label exists in A but not in B: Offer deletion of the label in A (if it can be deleted/is unused).
• A label exists in B but not in A: Offer creation of the label in A.
• A label has a similar but slightly different name between A and B (see screenshot): Offer to keep the name of A or to take the name of B.

[mzur]

Packages to check out for this:

• https://github.com/sebastianbergmann/diff
• https://github.com/wmde/Diff

[mzur]

The textual representation for the diff is not well suited for this. Neither are the two PHP packages. But the diff can be computed with this algorithm:

Input are two lists (A and B) of label objects, sorted by name. Example:

[
   {
      "name": "First Parent",
      "children": [
         {
            "name": "First Child",
            "children": []
         }
      ]
   }
]

The algorithm works recursively as follows.

1. Compare the names of the first elements of A and B.
   • If the names match perform the algorithm on the two lists of children as new A and B, remove (shift) both elements and append them as well as the diff result for the children to the diff list (see below).
   • If the names don't match and the name of the label in A is lexicographically smaller than the name of the label in B, remove (shift) the element from A and append it to the diff list (as left).
   • If the names don't match and the name of the label in A is lexicographically larger than the name of the label in B, remove (shift) the element from B and append it to the diff list (as right).
2. If A or B have elements left, go to 1., else stop.

The diff list consists of entries like these:

{
   "left": {...},
   "right": {...},
   "diff": [...]
}

If left and right are set, both labels are identical and diff contains the diff list of their children. If only left is set, the label and all its children do not exist in the label tree (B) that is merged (into A). If only right is set, the label and all its children were added in the label tree (B) that is merged (into A).

This can be implemented interactively in JavaScript.

[mzur]

Todo:

• [x] Merge UI
• [x] View to select a label tree to merge
• [x] API endpoint to save a merge
• [x] Manual