Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Is there a category of patches that looks roughly like this:
I'm interested in these questions:
As pointed by Martin, there is some work on the categorical representation of patches. Mimram and Di Giusto's "A Categorical Theory of Patches" being the most extensive categorical approach to edit-scripts as used by the UNIX diff.
In their sense, you have what you want. The objects are finite sequences of words over an alphabet $L$, seen as a mapping $A : [n] \rightarrow L$, where $[n]$ denotes the set with $n$ elements. An arrow between $A : [n] \rightarrow L$ and $B : [m] \rightarrow L$ is an injective partial increasing mapping $f : [n] \rightarrow [m]$. Injectivity and increasing are there to indicate that copies never cross over each other. You can find all the details on the paper.
Yes, merging is seen as the pushout on the free cocompletion of the above category. We need the cocompletion to make sure we add merge conflicts to our construction. It is not the case that a merge always exists.
Onto your second question, there is no categorical notion of minimal edit script for two main reasons.
Edit-scripts come in all shapes and forms. Some authors consider insertions, deletions and copies, some authors like to add substitutions as an operation too. When you generalize from strings to trees, then, a plethora of other operations become feasible.
More importantly, though, minimal-cost edit-scripts are not unique. Take the file $ab$, and write a patch that transforms it into $ba$. What is the minimal edit script that does this? There are two! Once again, when generalizing into trees one can find even more situations where a notion of "minimality" is doubtful.
There has been a lot of work on generalizing edit scripts to trees. This has been split in two main bodies of work:
Untyped Trees: Think of s-expressions only. The tree-edit-distance between two trees is the string-edit-distance between the preorder traversal of said trees. You can check some bibliography by Demaine et al. or Pawlik and Augsten, for example.
Typed Trees: Patches over Abstract Syntax Trees that are guaranteed to preserve the well-typedness of the object, ie, applying a patch will always yield a valid AST. Under the typed umbrella, there are less edit operations one can consider. Substitution, for example, doesn't make sense. Nevertheless, there exists a diff over the preorder traversal of the trees by Lempsink et al., which was later extended by Vassena. I am currently focusing on approaches that distance themselves from edit scripts for the very problems I pointed earlier, such as our latest work or some earlier work which tries to take advantage of the structure of the type of the values being "patched".
In either of those cases I have not seen a careful categorical interpretation of tree-structured patches.
diff finds the minimal, but the model will consider any edit script as an arrow between $A$ and $B$. Composition is another problem, for example. Composition of minimal edit scripts is not guaranteed to be minimal. On the other comment, yes, we could say some merges don't exist. But diff3 does compute them. This would remove conflict handling from the model altogether.
$\endgroup$
Jul 5, 2019 at 13:56
There is quite a bit of work in this direction. You could start by looking at [1, 2], but they don't exhaust the topic.
S. Mimram, C. Di Giusto, A Categorical Theory of Patches.
C. Angiuli, E. Morehouse, D. R. Licata, R. Harper, Homotopical Patch Theory.
