# Document Title
badmerge -- abstract version
See also the concrete example with real C code where darcs merge does the right thing and the others do the wrong thing. See also an attempted counter-example where darcs merge allegedly does the wrong thing, along with my argument that this is not actually a counter-example.
    a
   / \
  b1  c1
  |    
  b2
Now the task is to merge b2 and c1. As far as I know all revision control tools except for darcs, Codeville, SCCS, and perhaps BitKeeper treat this as a 3-merge of (a, b2, c1).
The git or svn 3-merge algorithm and the GNU diff3 algorithm apply the changed line from c1 to the wrong place in b2, resulting in an apparently clean but actually wrong result.
merged by SVN v1.2.0, GNU diff3 v3.8.1, or git v1.5.6.3
Whereas darcs applies the changed from from c1 to the right place in b2, resulting in a clean merge with the correct result.
merged by darcs v1
The difference between what svn does and what darcs does here is, contrary to popular belief, not that darcs makes a better or luckier guess as to where the line from c1 should go, but that darcs uses information that svn does not use -- namely the information contained in b1 -- to learn that the location has moved and precisely to where it has moved.
Any algorithm which merges c1 with b2 by examining (a, b2, c1) but without reference to the information in b1 is doomed to do worse than darcs does in this sort of case. (Where a silent but incorrect merge such as SVN currently does is worse than raising it to the user as a conflict, which is worse than merging it correctly.)
It is important to understand that darcs merge performs better in this example not because it is "luckier" or "more complicated" than 3-merge (indeed darcs merge is actually a much simpler algorithm than 3-merge is for this example) but because darcs merge takes advantage of more information -- information which is already present in other systems such as SVN but which is not used in the current SVN merge operation.
code listings
listing a, abstract
A
B
C
D
E
listing diff from a to b1, abstract
@@ -1,3 +1,6 @@
+G
+G
+G
 A
 B
 C
listing b1, abstract
G
G
G
A
B
C
D
E
listing diff from b1 to b2, abstract
@@ -1,3 +1,8 @@
+A
+B
+C
+D
+E
 G
 G
 G
listing b2, abstract
A
B
C
D
E
G
G
G
A
B
C
D
E
listing diff from a to c1, abstract
@@ -1,5 +1,5 @@
 A
 B
-C
+X
 D
 E
listing c1, abstract
A
B
X
D
E
listing 3-way merged, abstract
A
B
X
D
E
G
G
G
A
B
C
D
E
listing darcs merged, abstract
A
B
C
D
E
G
G
G
A
B
X
D
E
Thanks for Nathaniel J. Smith for help with this example.
Thanks for Ken Schalk for finding bugs in this web page.
zooko
Last modified: Sat Jan 10 15:04:11 MST 2009 

thanks for having me up here i am
matthew mccullough a frequent speaker on
git and when flying around i'm even
willing to
help people through the aisles fasten
their seat belts and know what they need
to do in the sake of an emergency i have
an octocat named after my daughter but
the trouble that we're talking about
here today takes two forms and it has a
name that trouble is named git
i apologize for having proliferated it
so much at this point because when
thinking about it in two forms when
thinking about it from the positive and
the negative side the happy people say
it has distributed capabilities and i
can work when the network is offline and
it's robust it saves to disk i can
independently version things i don't
need any connectivity at all to make
this function and at the surface that
sounds awesome but i remember back to
the time when i had to drive in and go
to a cubicle and sit down at that
specific terminal to check in code and
there's something nice about those
fluorescent lights and that wonderful
elevator music that played while i was
there and then the git proponents say
well it's fault tolerant and it's it's
network enabled in the sense that you
can easily work when it's online or it's
off it's like a mobile device it caches
your results and this simply means that
we can work whether or not we have the
network
but i find this in this hard economic
time that we have today to be a reason
to stop buying hardware which is sick
when this economy needs your help the
most
sometimes people
but when you think about the positive
side they then back again say it's low
maintenance you don't have to really do
much with it every five thousand objects
it automatically garbage collects so in
that sense it's beautiful it's hands-off
it seems like it just basically takes
care of itself
but what really that means is it's
taking away the opportunity of my friend
terence who hopes someday to graduate
with an svn admin job what's he going to
do when he graduates and there's no more
svn to maintain
i don't know think about terrence
they also claim the disblazing fast and
you can commit three thousand objects
watch this over my tethered device it
goes up into the cloud and seven seconds
later it's beautifully committed and
visible on github and the user interface
can you do that with your version
control system isn't that fantastic but
you know what
i remember when we could talk up for 30
minutes with clearcase about who was
gonna win survivor and i enjoyed that
bonding with guys like tad and ryan
i don't have it anymore
and in fact then they come back and say
it's still fine because it's open source
and free and it's all this liberty that
we have at a conference like open source
embodied in a tool that cross-cuts all
the possible languages that we might
talk about here at a conference like
this
but you know what if you don't fund
software development if you don't give
them your heart in dollars you might not
have clearcase in a few years and can
you imagine what it would be like to
live in a world without clearcase at
your disposal do you want to live in
that world
say it's disconservative it only takes a
small amount of hard disk to store every
version ever
of every branch that you've ever
committed to anyone on the team with any
tag
but you know what in my box is an
amazing hard disk a solid state flash
hard disk and another one in another box
with perpendicular bits and that r d
didn't come from not using disks like
wild so think about what your nest disc
will be and whether you're ruining that
chance with git
then i used to commit a lot of bugs and
one of the things from the proponents of
get they'd say you could search for bugs
and find where the regression happened
exactly what commit brought that into
existence isn't that wonderful you can
isolate and find what you did wrong but
i remember the days where my friends tad
and ryan would help support me with 150
comment commits to help drown that bug
so when that engineer wanted to go find
it hope of that was zero like i wanted
it to be
but then they still keep coming back and
saying it's like cats and dogs living
together the compatibility is wonderful
we can talk to clearcase and to
subversion and perforce with these
conversion back and forth and
round-tripping utilities subversion
being the special mark there but you
know what
this is a bridge for them to be using
tools covertly that are not approved by
the it organization and that leads to
all kinds of other havoc in every frame
soon we'll be using libraries you don't
even understand what they are
they claim it's free as in beer as their
last one to say it helps in hard times
with keeping a minimal budget and really
allowing to have a great tool at a small
cost that doesn't need maintenance and
that helps us all but i bet you if you
keep on this track one day somebody's
even going to take it to the edge saying
they're going to have a free operating
system and no my word i can't even think
what that all chaos that'll bring to the
table do you want that do you want a
free operating system i don't think so
so i ask you even though i've taught git
for this long reconsider
salvage it for the sake of the people in
college today stop using git you're
ruining their lives their hopes their
dreams their future and it needs to end
now
thank you
you

# Document Title
The most confusing git terminology
n.b. This blog post dates from 2012, so some of it may be out of date now.
To add my usual disclaimer to the start of these blog posts, I should say that I love git; I think it’s a beautiful and elegant system, and it saves me huge amounts of time in my daily work. However, I think it’s a fair criticism of the system that its terminology is very confusing for newcomers, and in particular those who have come from using CVS or Subversion.
This is a personal list of some of my “favourite” points of confusion, which I’ve seen arise time and time again, both in real life and when answering questions on Stack Overflow. To be fair to all the excellent people who have contributed to git’s development, in most cases it’s clear that they are well aware that these terms can be problematic, and are trying to improve the situation subject to compatibility constraints. The problems that seem most bizarre are those that reuse CVS and Subversion terms for completely different concepts – I speculate a bit about that at the bottom.
“update”
If you’ve used Subversion or CVS, you’re probably used to “update” being a command that goes to the remote repository, and incorporates changes from the remote version into your local copy – this is (very broadly) analogous to “git pull”.  So, when you see the following error message when using git:
foo.c: needs update
You might imagine that this means you need to run “git pull”. However, that’s wrong.  In fact, what “needs update” means is approximately: “there are local modifications to this file, which you should probably commit or stash”.
“track” and “tracking”
The word “track” is used in git in three senses that I’m aware of. This ambiguity is particularly nasty, because the latter two collide at a point in learning the system where newcomers to git are likely to be baffled anyway. Fortunately, this seems to have been recognized by git’s developers (see below).
1. “track” as in “untracked files”
To say that a file is tracked in the repository appears to mean that it is either present in the index or exists in the commit pointed to by HEAD.  You see this usage most often in the output of “git status”, where it will list “untracked files”:
# On branch master
# Untracked files:
#   (use "git add <file>..." to include in what will be committed)
#
#    .classpath
This sense is relatively intuitive, I think – it was only after complaining for a while about the next two senses of “track” that I even remembered that there was also this one :)
2. “track” as in “remote-tracking branch”
As a bit of background, you can think of a remote-tracking branch as a local cache of the state of a branch in a remote repository.  The most commonly seen example is origin/master, or, to name that ref in full, refs/remotes/origin/master.  Such branches are usually updated by git fetch (and thus also potentially by git pull).  They are also updated by a successful push to the branch in the remote repository that they correspond to.   You can merge from them, examine their history, etc. but you can’t work directly on them.
The sense of “track” in the phrase “remote-tracking branch” is indicating that the remote-tracking branch is tracking the state of the branch in the remote repository the last time that remote-tracking branch was updated.  So, you might say that refs/remotes/origin/master is tracking the state of the branch master in origin.
The “tracking” here is defined by the refspec in the config variable remote.<remote-name>.fetch and the URL in the config variable remote.<remote-name>.url.
3. “track” as in “git branch –track foo origin/bar” and “Branch foo set up to track remote branch bar from origin”
Again, if you want to do some work on a branch from a remote repository, but want to keep your work separate from everything else in your repository, you’ll typically use a command like the following (or one of its many “Do What I Mean” equivalents):
git checkout --track -b foo origin/bar
… which will result in the following messages:
Branch foo set up to track remote branch bar from origin
Switched to a new branch 'foo'
The sense of “track” both in the command and the output is distinct from the previous sense – it means that config options have been set that associate your new local branch with another branch in the remote repository. The documentation sometimes refers to this relationship as making bar in origin “upstream” of foo. This “upstream” association is very useful, in fact: it enables nice features like being able to just type git pull while you’re on branch foo in order to fetch from origin and then merge from origin/bar. It’s also how you get helpful messages about the state of your branch relative to the remote-tracking branch, like “Your branch foo is 24 commits ahead of origin/bar and can be fast-forwarded”.
The tracking here is defined by config variables branch.<branch-name>.remote and branch.<branch-name>.merge.
“tracking” Summary
Fortunately, the third sense of “tracking” seems to be being carefully deprecated – for example, one of the possible options for push.default used to be tracking, but this is now deprecated in favour of the option name upstream. The commit message for 53c403116 says:
    push.default: Rename ‘tracking’ to ‘upstream’
    Users are sometimes confused with two different types of “tracking” behavior in Git: “remote-tracking” branches (e.g. refs/remotes/*/*) versus the merge/rebase relationship between a local branch and its @{upstream} (controlled by branch.foo.remote and branch.foo.merge config settings).
    When the push.default is set to ‘tracking’, it specifies that a branch should be pushed to its @{upstream} branch. In other words, setting push.default to ‘tracking’ applies only to the latter of the above two types of “tracking” behavior.
    In order to make this more understandable to the user, we rename the push.default == ‘tracking’ option to push.default == ‘upstream’.
    push.default == ‘tracking’ is left as a deprecated synonym for ‘upstream’.
“commit”
In CVS and Subversion, “commit” means to send your changes to the remote repository. In git the action of committing (with “git commit”) is entirely local; the closest equivalent of “cvs commit” is “git push”. In addition, the word “commit” in git is used as both a verb and a noun (although frankly I’ve never found this confusing myself – when you commit, you create a commit).
“checkout”
In CVS and Subversion “checkout” creates a new local copy of the source code that is linked to that repository. The closest command in git is “git clone”. However, in git, “git checkout” is used for something completely distinct. In fact, it has two largely distinct modes of operation:
    To switch HEAD to point to a new branch or commit, in the usage git checkout <branch>. If <branch> is genuinely a local branch, this will switch to that branch (i.e. HEAD will point to the ref name) or if it otherwise resolves to a commit will detach HEAD and point it directly to the commit’s object name.
    To replace a file or multiple files in the working copy and the index with their content from a particular commit or the index. This is seen in the usages: git checkout -- (update from the index) and git checkout <tree-ish> -- (where <tree-ish> is typically a commit).
(git checkout is also frequently used with -b, to create a new branch, but that’s really a sub-case of usage 1.)
In my ideal world, these two modes of operation would have different verbs, and neither of them would be “checkout”.
Update in 2023: This has now happened – you can now use “git switch” for the former cases and “git restore” for the latter. This is a very welcome change :) 
“HEAD” and “head”
There are usually many “heads” (lower-case) in a git repository – the tip of each branch is a head. However, there is only one HEAD (upper-case) which is a symbolic ref which points to the current branch or commit.
“fetch” and “pull”
I wasn’t aware of this until Roy Badami pointed it out, but it seems that git and Mercurial have opposite meanings for “fetch” and “pull” – see the top two lines in this table of git / hg equivalences. I think it’s understandable that since git’s and Mercurial’s development were more or less concurrent, such unfortunate clashes in terminology might occur.
“push” and “pull”
“git pull” is not the opposite of “git push”; the closest there is to an opposite of “git push” is “git fetch”.
“hash”, “SHA1”, “SHA1sum”, “object name” and “object identifier”
These terms are often used synonymously to mean the 40 characters hexadecimal strings that uniquely identify objects in git. “object name” seems to be the most official, but the least used in general. Referring to an object name as a SHA1sum is potentially confusing, since the object name for a blob is not the same as the SHA1sum of the file.
“remote branch”
This term is only used occasionally in the git documentation, but it’s one that I would always try to avoid because it tends to be unclear whether you mean “a branch in a remote repository” or “a remote-tracking branch”. Whenever a git beginner uses this phrase, I think it’s worth clarifying this, since it can avoid later confusion.
“index”, “staging area” and “cache”
As nouns, these are all synonyms, which all exist for historical reasons. Personally, I like “staging area” the best since it seems to be the easiest concept to understand for git beginners, but the other two are used more commonly in the documentation.
When used as command options, --index and --cached have distinct and consistent meanings, as explained by Junio C. Hamano in this useful blog post.
Why are there so many of these points of confusion?
I would speculate that the most significant effect that contributed to these terminology confusions is that git was being actively used by an enthusiastic community from very early in its development, which means that early names for concepts have tended to persist for the sake of compatibility and consistency. That doesn’t necessarily account for the many conflicts with CVS / Subversion usage, however.
To be fair to git, thinking up verbs for particular commands in any software is tough, and there have been enough version control systems written that to completely avoid clashes would lead to some convoluted choices. However, it’s hard to see git’s use of CVS / Subversion terminology for completely different concepts as anything but perverse. Linus has made it very clear many times that he hated CVS, and joked that a design principle for git was WWCVSND (What Would CVS Never Do); I’m sympathetic to that, as I’m sure most are, especially after having switched to the DVCS mindset. However, could that attitude have extended to deliberately disregarding concerns about terminology that might make it actively harder for people to migrate to git from CVS / Subversion? I don’t know nearly enough about the early development of git to know. However, it wouldn’t have been tough to find better choices for commit, checkout and update in each of their various senses.
Posted
2012-05-07
in
git
by
mark
Tags:
Comments
21 responses to “The most confusing git terminology”
    Dmitriy Matrosov Avatar
    Dmitriy Matrosov
    2012-06-09
    Hi, Mark.
    Thanks for yor excellent explanation of “tracking” branches! This is exactly what i searched for.
    Also, i think, here is typo:
    You wrote “The documentation sometimes refers to this relationship as making foo in origin “upstream” of bar.”, but it should be “bar in origin upstream of foo”.
    Reply
        mark Avatar
        mark
        2012-06-11
        Hi Dimitriy: thanks for your kind comment and the correction. I’ve edited the post to fix that now.
        Reply
    harold Avatar
    harold
    2012-10-05
    Really good article – a lot of these terms are thrown about in git documentation/tutorials without much explanation and can certainly trip you up.
    Reply
    ahmet Avatar
    ahmet
    2012-11-26
    “Why are there so many of these points of confusion?”
    Probably beacuse Linus is a dictator and he probaby didn’t give shit about others’ opinions and past works for the terminology.
    Reply
        Bri Avatar
        Bri
        2014-08-14
        Right! He forgot to include the input of someone who knows an inkling about user-friendliness. Imagine how much easier GIT SWITCH would be to remember than GIT CHECKOUT. The whole system was made unnecessarily complicated just by having awfully named functions.
        Reply
        Alberto Fonseca Avatar
        Alberto Fonseca
        2018-03-22
        Good point. Another reason is probably the agile paradigm that tells us that only “working code” is important, so developers happily cast aside anything even remotely resembling logical, structured, conceptional work, which works only based on a precisely defined set of domain vocabulary (which is exactly what we’re missing here).
        Reply
    Jennifer Avatar
    Jennifer
    2013-02-05
    I find the term upstream confusing. You mention one usage in this article. However, GitHub help recommends To keep track of the original repo [you forked from], you need to add another remote named upstream. So when someone says to push upstream, it’s ambiguous. I’m not sure if this usage is typical of Git in general or just GitHub, but it sure left me confused for a while.
    Reply
    Ian Avatar
    Ian
    2013-11-21
    “remote branch”
    This term is only used occasionally in the git documentation, but it’s one that I would always try to avoid because it tends to be unclear whether you mean “a branch in a remote repository” or “a remote-tracking branch”. Whenever a git beginner uses this phrase, I think it’s worth clarifying this, since it can avoid later confusion.
    Doh! That’s exactly what I’m trying to find out, but then you don’t actually give us the answer!
    Reply
        admin Avatar
        admin
        2013-11-21
        Hi Ian, That’s the thing – you often can’t tell without context. Where did you see “remote branch” used, or in what context? (“a branch in a remote repository” is the more accurate interpretation, I think, but people who don’t understand remote-tracking branches might use the term differently.)
        Reply
    Oleh Avatar
    Oleh
    2014-05-28
    Thanks for the helpful git articles. I’m a git noob, and the more different sources I read, the closer my understanding converges on what’s really going on. It’s just a shame that numerous git commands have ended up being labels where one must simply memorize what they really do — might as well have called them things like “abc” and “xyz” instead of terms that initially lead one astray.
    If you’re motivated to write another one, here’s a suggestion. Maybe you could review all the places that git stores stuff, like working repository, index (aka cache or staging area), remote repository, local copy of remote repository (remote tracking branch?), stash (and stash versions), etc., and list the commands that transfer data in various ways among these places. I’ve had to gradually formulate and revise these ideas in my own mind as I’ve been reading about git, and if I had an up-front explanation of this at the outset, it would’ve saved me lots of time.
    Reply
        mark Avatar
        mark
        2014-06-03
        Thanks for the kind words and your suggestion Oleh. I’ll certainly consider it – there are quite a few good diagrammatic representations of the commands that change what’s stored in the index, working tree, etc., but maybe there’s something more to do. (You can find some good examples with an image search for git index diagram.)
        Reply
        bryan chance Avatar
        bryan chance
        2017-12-06
        Oleh, That would be a great write up. I think those are the rest of the most confusing git terminoloy. :p I’m new to git as well and I thought I was just stupid because I couldn’t get a handle on it. This is 2017 and yes git terminologies still baffle users.
        Reply
            Savanna Avatar
            Savanna
            2018-11-13
            I’ve been using git for years and I’m only just now diving into how it actually works and what the commands actually mean since I’m working at a place that has a rather complicated branching structure… in the past I simply worked on master since I was the only or one of few developers. git pull and git push were usually enough. Now I find myself often totally confused and realized I don’t actually know what the heck I’m doing with git, so I’m reading all these articles and watching videos. It’s been too long coming! Haha
            Reply
    Alistair Avatar
    Alistair
    2014-11-12
        The sense of “track” in the phrase “remote-tracking branch” is indicating that the remote-tracking branch is tracking the state of the branch in the remote repository the last time that remote-tracking branch was updated.
    In the light of your paragraph about “update”, maybe “fetched” would be a better word than “updated”?
        3. “track” as in “git branch –track foo origin/bar”
    I don’t understand how senses 2 and 3 are different. Specifically, sense 2 seems to be the special case of 3 where “foo” and “bar” coincide. I.e. the “upstream” of a remote-tracking branch is the branch of the same name on “origin”. Is that right?
        commit
        As a noun
    I agree. This terminology is fine, and not really confusing at all. The closest english word would be “commitment”, I think, but in the context it is good to have a slightly different word.
        “fetch” and “pull” […] “push” and “pull”
    This juxtaposition is hilarious. In the former you are very diplomatic in suggesting that git’s version is an arbitrary choice, made by historical accident, but then in the latter you immediately make it look like exactly the opposite choice would be better.
    Reply
        admin Avatar
        admin
        2014-12-30
            In the light of your paragraph about “update”, maybe “fetched” would be a better word than “updated”
        I see what you mean, but I think it would probably be more confusing to use “fetched”; the colloquial sense of update is what I mean and the “needs update” sense in git is surprising and wouldn’t make sense in this context anyway.
            I don’t understand how senses 2 and 3 are different. Specifically, sense 2 seems to be the special case of 3 where “foo” and “bar” coincide. I.e. the “upstream” of a remote-tracking branch is the branch of the same name on “origin”. Is that right?
        In sense 2 (“remote-tracking branch”) the tracking can only be about this special type of branch tracking the branch in a remote repository; very often there’s no corresponding “local” branch (as opposed to a remote-tracking branch). In sense 3 (“–track”) there must be a local branch, and the tracking is describing an association between the local branch and one in the remote repository (and usually to a corresponding remote-tracking branch).
        Reply
    Philip A Avatar
    Philip A
    2015-04-01
    Thanks so much for this really useful and informative blog post which I have only recently discovered. I think focusing in on the confusing aspects of Git is a great way to improve one’s general understanding. Particularly helpful are your explanations of ‘remote tracking branches’ compared with ‘branches which track branches on a remote’. One very minor thing which confused me was: “Your branch foo is 24 commits ahead of origin/bar and can be fast-forwarded”. Shouldn’t it be ‘behind’ instead of ‘ahead’ ? Apologies if I have misunderstood. Anyway, once again … really good post :-)
    Reply
    Matthew Astley Avatar
    Matthew Astley
    2016-02-17
    Thanks – good list, and several of us here misuse the jargon.
    When describing the state of the work tree: clean, up-to-date and unmodified are easily mixed up.
    Going by the command name, clean should mean no untracked files (aka. cruft) in the work tree.
    Unmodified should mean no changes to tracked files, but the command to do this is reset – another naming clash?
    Up-to-date is trickier to define. There may be copies elsewhere containing commits you can’t yet see. Is the HEAD (local branch) up-to-date with one remote at a point in time when the fetch ran? Should all local branches be up-to-date?
    Reply
    Mike Weilgart Avatar
    Mike Weilgart
    2016-04-16
    This is an excellent article; thank you!
    Particularly helpful was the explanation of the three senses in which the word “track” may be used.
    The light went on when I realized that there are actually *three* things going on when you deal with a remote, not just two:
    1. The branch on the remote repository;
    2. The remote tracking branch in your local repository;
    3. The local branch associated with the remote tracking branch.
    This clarified for me how I should go about instructing students in this aspect of Git; thank you!
    Reply
    Simon Bagley Avatar
    Simon Bagley
    2016-06-02
    Thank you for the very informative article. I am a complete novice with Git, and your article will help me understand the many vary confusing names of commands, options etc.
    It would be useful if you defined the terms ‘refs’, and ‘refspec’ before you used them.
    Reply
    Doug Kimzey Avatar
    Doug Kimzey
    2019-09-06
    I could not agree more. I have been using git for about 3 months now. Git is not a full blown language but a source control tool.
    The ambiguity of the git syntax contributes greatly to the confusion experienced by developers facing git for the first time. The concepts are not difficult. The ambiguity of the git syntax constantly forces you to reach for a cheat sheet. The commands do not clearly describe their corresponding actions. Source control is a crucial part of any software project. Source control is not an area that should be managed by confusing and ambiguous terminology and syntax. Confusion puts work at risk and adds time to projects.
    Commands that concisely describe actions taken with source control are very important.
    Thousands of developers use git. Millions of Americans use IRS Tax Forms. This does not mean that Millions of Americans find IRS Tax Forms clear and easy to understand. Git terminology unnecessarily costs time and effort in translation.
    Reply
    Doug Kimzey Avatar
    Doug Kimzey
    2023-04-11
    This is very well said. If the git syntax was concise:
    – There would be far fewer books on amazon.
    – The number of up votes on git questions on stackoverflow would be much smaller (some of these are literally in the thousands).
    – There would be fewer cheat sheets and diagrams.
    – The investment in time and effort would be much less.
    The git documentation is poor because one vague command is described in terms and several ambiguous and confusing commands.
    Grammar is not the only measure of the quality of documentation.
    I am adopting some of the rules in the Simplified Technical English standard (ASD-STE100) to the naming of commands used in console applications and utilities.
    The goals of this standard are:
    – Reduce ambiguity.
    – Improve clarity of the technical text.
    – Make user manuals more comprehensive for non-native speakers of English.
    – Create better conditions for both human and machine translation.
    These goals should be carried to command syntax.
    Reply

# Document Title
arXiv:1311.3903v1 [cs.LO] 13 Nov 2013
A Categorical Theory of Patches
Samuel Mimram Cinzia Di Giusto
CEA, LIST∗
Abstract
When working with distant collaborators on the same documents, one
often uses a version control system, which is a program tracking the history
of files and helping importing modifications brought by others as patches.
The implementation of such a system requires to handle lots of situations
depending on the operations performed by users on files, and it is thus
difficult to ensure that all the corner cases have been correctly addressed.
Here, instead of verifying the implementation of such a system, we adopt
a complementary approach: we introduce a theoretical model, which is
defined abstractly by the universal property that it should satisfy, and
work out a concrete description of it. We begin by defining a category of
files and patches, where the operation of merging the effect of two coinitial
patches is defined by pushout. Since two patches can be incompatible,
such a pushout does not necessarily exist in the category, which raises
the question of which is the correct category to represent and manipulate
files in conflicting state. We provide an answer by investigating the free
completion of the category of files under finite colimits, and give an explicit
description of this category: its objects are finite sets labeled by lines
equipped with a transitive relation and morphisms are partial functions
respecting labeling and relations.
1 Introduction
It is common nowadays, when working with distant collaborators on the same
files (multiple authors writing an article together for instance), to use a program
which will track the history of files and handle the operation of importing mod-
ifications of other participants. These software called version control systems
(vcs for short), like git or Darcs, implement two main operations. When a user
is happy with the changes it has brought to the files it can record those changes
in a patch (a file coding the differences between the current version and the last
recorded version) and commit them to a server, called a repository. The user
can also update its current version of the file by importing new patches added
by other users to the repository and applying the corresponding modifications
to the files. One of the main difficulties to address here is that there is no global
notion of “time”: patches are only partially ordered. For instance consider a
repository with one file A and two users u1 and u2. Suppose that u1 modifies
file A into B by committing a patch f , which is then imported by u2, and
∗This work was partially supported by the French project ANR-11-INSE-0007 REVER.
1
then u1 and u2 concurrently modify the file B into C (resp. D) by committing
a patch g (resp. h). The evolution of the file is depicted on the left and the
partial ordering of patches in the middle:
C D
B
g
`
`
❆❆❆ h
>
>
⑥⑥⑥
A
f O O
g h
f
]
]
✿✿✿ A A ✄✄✄
E
C
h/g > > ⑥⑥⑥ D
g/h``❆❆❆
B
g
`
`
❆❆❆ h
>
>
⑥⑥⑥
A
f O O
Now, suppose that u2 imports the patch g or that u1 imports the patch h.
Clearly, this file resulting from the merging of the two patches should be the
same in both cases, call it E. One way to compute this file, is to say that there
should be a patch h/g, the residual of h after g, which transforms C into E and
has the “same effect” as h once g has been applied, and similarly there should be
a patch g/h transforming D into E. Thus, after each user has imported changes
from the other, the evolution of the file is as pictured on the right above. In
this article, we introduce a category L whose objects are files and morphisms
are patches. Since residuals should be computed in the most general way, we
formally define them as the arrows of pushout cocones, i.e. the square in the
figure on the right should be a pushout.
However, as expected, not every pair of coinitial morphisms have a pushout
in the category L: this reflects the fact that two patches can be conflicting (for
instance if two users modify the same line of a file). Representing and handling
such conflicts in a coherent way is one of the most difficult part of implementing
a vcs (as witnessed for instance by the various proposals for Darcs: mergers,
conflictors, graphictors, etc. [10]). In order to be able to have a representation
for all conflicting files, we investigate the free completion of the category L
under all pushouts, this category being denoted P, which corresponds to adding
all conflicting files to the category, in the most general way as possible. This
category can easily be shown to exist for general abstract reasons, and one
of the main contributions of this work is to provide an explicit description by
applying the theory of presheaves. This approach paves the way towards the
implementation of a vcs whose correctness is deduced from universal categorical
properties.
Related work. The Darcs community has investigated a formalization of pat-
ches based on commutation properties [10]. Operational transformations tackle
essentially the same issues by axiomatizing the notion of residual patches [9].
In both cases, the fact that residual should form a pushout cocone is never
explicitly stated, excepting in informal sentences saying that “g/f should have
the same effect as g once f has been applied”. We should also mention another
interesting approach to the problem using inverse semigroups in [4]. Finally,
Houston has proposed a category with pushouts, similar to ours, in order to
model conflicting files [3], see Section 6.
Plan of the paper. We begin by defining a category L of files and patches in
Section 2. Then, in Section 3, we abstractly define the category P of conflicting
files obtained by free finite cocompletion. Section 4 provides a concrete descrip-
tion of the construction in the simpler case where patches can only insert lines.
2
We give some concrete examples in Section 5 and adapt the framework to the
general case in Section 6. We conclude in Section 7.
2 Categories of files and patches
In this section, we investigate a model for a simplified vcs: it handles only one
file and the only allowed operations are insertion and deletion of lines (modi-
fication of a line can be encoded by a deletion followed by an insertion). We
suppose fixed a set L = {a, b, . . .} of lines (typically words over an alphabet of
characters). A file A is a finite sequence of lines, which will be seen as a function
A : [n] → L for some number of lines n ∈ N, where the set [n] = {0, 1, . . . , n − 1}
indexes the lines of the files. For instance, a file A with three lines such that
A(0) = a, A(1) = b and A(2) = c models the file abc. Given a ∈ L, we some-
times simply write a for the file A : [1] → L such that A(0) = a. A morphism
between two files A : [m] → L and B : [n] → L is an injective increasing partial
function f : [m] → [n] such that ∀i ∈ [m], B ◦ f (i) = A(i) whenever f (i) is
defined. Such a morphism is called a patch.
Definition 1. The category L has files as objects and patches as morphisms.
Notice that the category L is strictly monoidal with [m] ⊗ [n] = [m + n] and
for every file A : [m] → L and B : [n] → L, (A ⊗ B)(i) = A(i) if i < m and
(A ⊗ B)(i) = B(i − m) otherwise, the unit being the empty file I : [0] → L, and
tensor being defined on morphisms in the obvious way. The following proposition
shows that patches are generated by the operations of inserting and deleting a
line:
Proposition 2. The category L is the free monoidal category containing L as
objects and containing, for every line a ∈ L, morphisms ηa : I → a (insertion
of a line a) and εa : a → I (deletion of a line a) such that εa ◦ ηa = idI (deleting
an inserted line amounts to do nothing).
Example 3. The patch corresponding to transforming the file abc into dadeb,
by deleting the line c and inserting the lines labeled by d and e, is modeled by
the partial function f : [3] → [5] such that f (0) = 1 and f (1) = 4 and f (2) is
undefined. Graphically,
a
b
c
d
a
d
e
b
The deleted line is the one on which f is not defined and the inserted lines are
those which are not in the image of f . In other words, f keeps track of the
unchanged lines.
In order to increase readability, we shall consider the particular case where L
is reduced to a single element. In this unlabeled case, the objects of L can be
identified with integers (the labeling function is trivial), and Proposition 2 can
be adapted to achieve the following description of the category, see also [6].
Proposition 4. If L is reduced to a singleton, the category L is the free category
whose objects are integers and morphisms are generated by sn
i : n → n + 1 and
3
dn
i : n + 1 → n for every n ∈ N and i ∈ [n + 1] (respectively corresponding to
insertion and deletion of a line at i-th position), subject to the relations
sn+1
i sn
j = sn+1
j+1 sn
i dn
i sn
i = idn dn
i dn+1
j = dn
j dn+1
i+1 (1)
whenever 0 ≤ i ≤ j < n.
We will also consider the subcategory L+ of L, with same objects, and to-
tal injective increasing functions as morphisms. This category models patches
where the only possible operation is the insertion of lines: Proposition 2 can be
adapted to show that L+ is the free monoidal category containing morphisms
ηa : I → a and, in the unlabeled case, Proposition 4 can be similarly adapted
to show that it is the free category generated by morphisms sn
i : n → n + 1
satisfying sn+1
i sn
j = sn+1
j+1 sn
i with 0 ≤ i ≤ j < n.
3 Towards a category of conflicting files
Suppose that A is a file which is edited by two users, respectively applying
patches f1 : A → A1 and f2 : A → A2 to the file. For instance,
a c c b f1
←− a b f2
−→ a b c d (2)
Now, each of the two users imports the modification from the other one. The
resulting file, after the import, should be the smallest file containing both mod-
ifications on the original file: accbcd. It is thus natural to state that it should
be a pushout of the diagram (2). Now, it can be noticed that not every diagram
in L has a pushout. For instance, the diagram
a c b f1
←− a b f2
−→ a d b (3)
does not admit a pushout in L. In this case, the two patches f1 and f2 are said
to be conflicting.
In order to represent the state of files after applying two conflicting patches,
we investigate the definition of a category P which is obtained by completing
the category L under all pushouts. Since, this completion should also contain
an initial object (i.e. the empty file), we are actually defining the category P as
the free completion of L under finite colimits: recall that a category is finitely
cocomplete (has all finite colimits) if and only if it has an initial object and is
closed under pushouts [6]. Intuitively, this category is obtained by adding files
whose lines are not linearly ordered, but only partially ordered, such as on the
left of a
   ❃❃❃
c

 ❁❁❁ d
✂✂✂
b
a
<<<<<<< HEAD
c
=======
d
>>>>>>> 5c55...
b
(4)
which would intuitively model the pushout of the diagram (3) if it existed,
indicating that the user has to choose between c and d for the second line.
Notice the similarities with the corresponding textual notation in git on the
right. The name of the category L reflects the facts that its objects are files
whose lines are linearly ordered, whereas the objects of P can be thought as files
whose lines are only partially ordered. More formally, the category is defined
as follows.
4
Definition 5. The category P is the free finite conservative cocompletion of L:
it is (up to equivalence of categories) the unique finitely cocomplete category
together with an embedding functor y : L → P preserving finite colimits, such
that for every finitely cocomplete category C and functor F : L → C preserv-
ing finite colimits, there exists, up to unique isomorphism, a unique functor
˜F : P → C preserving finite colimits and satisfying ˜F ◦ y = F :
L
y  
F / / C
P ˜F
?
?
Above, the term conservative refers to the fact that we preserve colimits which
already exist in L (we will only consider such completions here). The “standard”
way to characterize the category P, which always exists, is to use the following
folklore theorem, often attributed to Kelly [5, 1]:
Theorem 6. The conservative cocompletion of the category L is equivalent to
the full subcategory of ˆL whose objects are presheaves which preserve finite limits,
i.e. the image of a limit in Lop (or equivalently a colimit in L) is a limit in Set
(and limiting cones are transported to limiting cones). The finite conservative
cocompletion P can be obtained by further restricting to presheaves which are
finite colimits of representables.
Example 7. The category FinSet of finite sets and functions is the conservative
cocompletion of the terminal category 1.
We recall that the category ˆL of presheaves over L, is the category of functors
Lop → Set and natural transformations between them. The Yoneda functor
y : L → ˆL defined on objects n ∈ L by yn = L(−, n), and on morphisms
by postcomposition, provides a full and faithful embedding of L into the cor-
responding presheaf category, and can be shown to corestrict into a functor
y : L → P [1]. A presheaf of the form yn for some n ∈ L is called representable.
Extracting a concrete description of the category P from the above propo-
sition is a challenging task, because we a priori need to characterize firstly all
diagrams admitting a colimit in L, and secondly all presheaves in ˆL which pre-
serve those diagrams. This paper introduces a general methodology to build
such a category. In particular, perhaps a bit surprisingly, it turns out that
we have to “allow cycles” in the objects of the category P, which will be de-
scribed as the category whose objects are finite sets labeled by lines together with
a transitive relation and morphisms are partial functions respecting labels and
relations.
4 A cocompletion of files and insertions of lines
In order to make our presentation clearer, we shall begin our investigation of the
category P in a simpler case, which will be generalized in Section 6: we compute
the free finite cocompletion of the category L+ (patches can only insert lines)
in the case where the set of labels is a singleton. To further lighten notations,
in this section, we simply write L for this category.
We sometimes characterize the objects in L as finite colimits of objects in a
subcategory G of L. This category G is the full subcategory of L whose objects
5
are 1 and 2: it is the free category on the graph 1 / / / / 2 , the two arrows
being s1
0 and s1
1. The category ˆG of presheaves over G is the category of graphs:
a presheaf P ∈ ˆG is a graph with P (1) as vertices, P (2) as edges, the functions
P (s1
1) and P (s1
0) associate to a vertex its source and target respectively, and
morphisms correspond to usual morphisms of graphs. We denote by x ։ y a
path going from a vertex x to a vertex y in such a graph. The inclusion functor
I : G → L induces, by precomposition, a functor I∗ : ˆL → ˆG. The image
of a presheaf in ˆL under this functor is called its underlying graph. By well
known results about presheaves categories, this functor admits a right adjoint
I∗ : ˆG → ˆL: given a graph G ∈ ˆG, its image under the right adjoint is the
presheaf G∗ ∈ ˆL such that for every n ∈ N, G∗(n + 1) is the set of paths of
length n in the graph G, with the expected source maps, and G∗(0) is reduced
to one element.
Recall that every functor F : C → D induces a nerve functor NF : D → ˆC
defined on an object A ∈ C by NF (A) = D(F −, A) [7]. Here, we will consider
the nerve NI : L → ˆG associated to the inclusion functor I : G → L. An easy
computation shows that the image NI (n) of n ∈ L is a graph with n vertices,
so that its objects are isomorphic to [n], and there is an arrow i → j for every
i, j ∈ [n] such that i < j. For instance,
NI (3) = 0 / / 6 6 1 / / 2 NI (4) = 0 / / ( ( 4 4 1 / / ( ( 2 / / 3
It is, therefore, easy to check that this embedding is full and faithful, i.e. mor-
phisms in L correspond to natural transformations in ˆG. Moreover, since NI (1)
is the graph reduced to a vertex and NI (2) is the graph reduced to two vertices
and one arrow between them, every graph can be obtained as a finite colimit of
the graphs NI (1) and NI (2) by “gluing arrows along vertices”. For instance, the
initial graph NI (0) is the colimit of the empty diagram, and the graph NI (3) is
the colimit of the diagram
NI (2) NI (2)
NI (1)
NI (s1 ) , , ❳❳❳❳❳❳❳❳❳❳❳❳❳❳
NI (s1 ) 6 6❧❧❧❧ NI (1)
NI (s0 )hh❘❘❘❘ NI (s1) 6 6❧❧❧❧ NI (1)
NI (s0 )hh❘❘❘❘
NI (s0 )rr❢❢❢❢❢❢❢❢❢❢❢❢❢❢
NI (2)
which may also be drawn as on the left of
*
*
❯❯❯❯❯❯❯❯❯
:
: ✈✈✈✈ f f ◆◆◆◆ 8 8 ♣♣♣♣ d d ❍❍❍❍
t
t
✐✐✐✐✐✐✐✐✐
2 2
1
&
&
◆◆◆◆◆◆◆
@
@
✁✁✁ 1
^
^
❂❂❂ @ @ ✁✁✁ 1
^
^
❂❂❂
x
x
♣♣♣♣♣♣♣
2
by drawing the graphs NI (0) and NI (1). Notice, that the object 3 is the col-
imit of the corresponding diagram in L (on the right), and this is generally
true for all objects of L, moreover this diagram is described by the functor
El(NI (3)) π
−→ L. The notation El(P ) refers to the category of elements of a
presheaf P ∈ ˆC, whose objects are pairs (A, p) with A ∈ C and p ∈ P (A)
and morphisms f : (A, p) → (B, q) are morphisms f : A → B in C such that
P (f )(q) = p, and π is the first projection functor. The functor I : G → L is
thus a dense functor in the sense of Definition 9 below, see [7] for details.
6
Proposition 8. Given a functor F : C → D, with D cocomplete, the associated
nerve NF : D → ˆC admits a left adjoint RF : ˆC → D called the realization
along F . This functor is defined on objects P ∈ ˆC by
RF (P ) = colim(El(P ) π
−→ C F
−→ D)
Proof. Given a presheaf P ∈ ˆC and an object D, it can be checked directly that
morphisms P → NF D in ˆC with cocones from El(P ) D
−→ to D, which in turn
are in bijection with morphisms RF (P ) → D in D, see [7].
Definition 9. A functor F : C → D is dense if it satisfies one of the two
equivalent conditions:
(i) the associated nerve functor NF : D → ˆC is full and faithful,
(ii) every object of D is canonically a colimit of objects in C: for every D ∈ D,
D ∼= colim(El(NF D) π
−→ C F
−→ D) (5)
Since the functor I is dense, every object of L is a finite colimit of objects
in G, and G does not have any non-trivial colimit. One could expect the free
conservative finite cocompletion of L to be the free finite cocompletion P of G.
We will see that this is not the case because the image in L of a non-trivial
diagram in G might still have a colimit. By Theorem 6, the category P is the
full subcategory of ˆL of presheaves preserving limits, which we now describe
explicitly. This category will turn out to be equivalent to a full subcategory
of ˆG (Theorem 15). We should first remark that those presheaves satisfy the
following properties:
Proposition 10. Given a presheaf P ∈ ˆL which is an object of P,
1. the underlying graph of P is finite,
2. for each non-empty path x ։ y there exists exactly one edge x → y (in
particular there is at most one edge between two vertices),
3. P (n + 1) is the set of paths of length n in the underlying graph of P ,
and P (0) is reduced to one element.
Proof. We suppose given a presheaf P ∈ P, it preserves limits by Theorem 6.
The diagram on the left
3
2
s2
2 = = ③③③ 2
s2
0aa❉❉❉
1s1
0
a
a
❉❉❉ s1
1
=
=
③③③
P (3)
P (2)
x
x
P (s2
2)
qq
P (2)
&
&
P (s2
0 )▼▼
P (1)
&
&P (s1
0)
▼▼ x x P (s1
1 )
qq
is a pushout in L, or equivalently the dual diagram is a pullback in Lop. There-
fore, writing D for the diagram 2 1
s1
0
oo s1
1 / / 2 in L, a presheaf P ∈ P should satisfy
P ((colim D)op) ∼= lim P (Dop), i.e. the above pushout diagram in L should be
transported by P into the pullback diagram in Set depicted on the right of the
above figure. This condition can be summarized by saying that P should satisfy
7
the isomorphism P (3) ∼= P (2) ×P (1) P (2) (and this isomorphism should respect
obvious source and target maps given by the fact that the functor P should
send a limiting cone to a limiting cone). From this fact, one can deduce that
the elements α of P (3) are in bijection with the paths x → y → z of length 2
in the underlying graph of P going from x = P (s2
2s1
1)(α) to z = P (s2
0s1
0)(α). In
particular, this implies that for any path α = x → y → z of length 2 in the
underlying graph of P , there exists an edge x → z, which is P (s2
1)(α). More
generally, given any integer n > 1, the object n + 1 is the colimit in L of the
diagram
2 2 2 2
1
s1
1 ; ; ①①① 1
s1
0cc❋❋❋ s1
1 ; ; ①①① s1
0aa❈❈❈❈ . . .
s1
1 = = ④④④④ 1
s1
0cc❋❋❋ s1
1 ; ; ①①① 1
s1
0cc❋❋❋ (6)
with n + 1 occurrences of the object 1, and n occurrences of the object 2.
Therefore, for every n ∈ N, P (n+ 1) is isomorphic to the set of paths of length n
in the underlying graph. Moreover, since the diagram
2 2 2 2
1
s1
1 , , ❩❩❩❩❩❩❩❩❩❩❩❩❩❩❩❩❩❩❩
s1
1 < < ②②② 1
s1
0bb❊❊❊ s1
1 < < ②②② s1
0``❇❇❇ . . .
s1
1 > > ⑤⑤⑤ 1
s1
0bb❊❊❊ s1
1 < < ②②② 1
s1
0bb❊❊❊
s1
0
rr❞❞❞❞❞❞❞❞❞❞❞❞❞❞❞❞❞❞❞
2
(7)
with n + 1 occurrences of the object 1 also admits the object n + 1 as colimit,
we should have P (n + 1) ∼= P (n + 1) × P (2) between any two vertices x and y,
i.e. for every non-empty path x ։ y there exists exactly one edge x → y. Also,
since the object 0 is initial in L, it is the colimit of the empty diagram. The
set P (0) should thus be the terminal set, i.e. reduced to one element. Finally,
since I is dense, P should be a finite colimit of the representables NI (1) and
NI (2), the set P (1) is necessarily finite, as well as the set P (2) since there is at
most one edge between two vertices.
Conversely, we wish to show that the conditions mentioned in the above
proposition exactly characterize the presheaves in P among those in ˆL. In order
to prove so, by Theorem 6, we have to show that presheaves P satisfying these
conditions preserve finite limits in L, i.e. that for every finite diagram D : J → L
admitting a colimit we have P (colim D) ∼= lim(P ◦ Dop). It seems quite difficult
to characterize the diagrams admitting a colimit in L, however the following
lemma shows that it is enough to check diagrams “generated” by a graph which
admits a colimit.
Lemma 11. A presheaf P ∈ ˆL preserves finite limits if and only if it sends the
colimits of diagrams of the form
El(G) πG
−−→ G I
−→ L (8)
to limits in Set, where G ∈ ˆG is a finite graph such that the above diagram
admits a colimit. Such a diagram in L is said to be generated by the graph G.
Proof. In order to check that a presheaf P ∈ ˆL preserves finite limits, we have
to check that it sends colimits of finite diagrams in L which admit a colimit
to limits in Set, and therefore we have to characterize diagrams which admit
colimits in L. Suppose given a diagram K : J → L. Since I is dense, every
object of linear is a colimit of a diagram involving only the objects 1 and 2 (see
8
Definition 9). We can therefore suppose that this is the case in the diagram K.
Finally, it can be shown that diagram K admits the same colimits as a diagram
containing only s1
0 and s1
1 as arrows (these are the only non-trivial arrows in L
whose source and target are 1 or 2), in which every object 2 is the target of
exactly one arrow s1
0 and one arrow s1
1. For instance, the diagram in L below
on the left admits the same colimits as the diagram in the middle.
2 3
1s1
0
^
^
❂❂❂
s1
1
  ❂❂❂
s2
2 s1
1 @ @ ✁✁✁ 1
s1
0
✁✁✁
s2
0s1
0
^^❂❂❂
1
s1
0jj2
2 2 2
1
s1
1 @ @ ✁✁✁ 1
s1
0
^^❂❂❂
s1
1 @ @ ✁✁✁
s1
1 & & ◆◆◆◆◆◆◆ 1
s1
0
^^❂❂❂
s1
1 @ @ ✁✁✁ 1
s1
0
xx♣♣♣♣♣♣♣
s1
0
^^❂❂❂
2
0 / / 1 / / 6 6 2 / / 3
Any such diagram K is obtained by gluing a finite number of diagrams of the
form 1 s1
1 / / 2 1
s1
0
oo along objects 1, and is therefore of the form El(G) π
−→ G I
−→ L
for some finite graph G ∈ ˆG: the objects of G are the objects 1 in K, the edges of
G are the objects 2 in K and the source and target of an edge 2 are respectively
given by the sources of the corresponding arrows s1
1 and s1
0 admitting it as target.
For instance, the diagram in the middle above is generated by the graph on the
right. The fact that every diagram is generated by a presheaf (is a discrete
fibration) also follows more abstractly and generally from the construction of
the comprehensive factorization system on Cat [8, 11].
Among diagrams generated by graphs, those admitting a colimit can be
characterized using the following proposition:
Lemma 12. Given a graph G ∈ ˆG, the associated diagram (8) admits a colimit
in L if and only if there exists n ∈ L and a morphism f : G → NI n in ˆL
such that every morphism g : G → NI m in ˆL, with m ∈ L, factorizes uniquely
through NI n: G f/ /
g
2 2
NI n / / NI m
Proof. Follows from the existence of a partially defined left adjoint to NI , in
the sense of [8], given by the fact that I is dense (see Definition 9).
We finally arrive at the following concrete characterization of diagrams admit-
ting colimits:
Lemma 13. A finite graph G ∈ ˆG induces a diagram (8) in L which admits a
colimit if and only if it is “tree-shaped”, i.e. it is
1. acyclic: for any vertex x, the only path x ։ x is the empty path,
2. connected: for any pair of vertices x and y there exists a path x ։ y or a
path y ։ x.
Proof. Given an object n ∈ L, recall that NI n is the graph whose objects are
elements of [n] and there is an arrow i → j if and only if i < j. Given a finite
graph G, morphisms f : G → NI n are therefore in bijection with functions
f : VG → [n], where VG denotes the set of vertices of G, such that f (x) < f (y)
whenever there exists an edge x → y (or equivalently, there exists a non-empty
path x ։ y).
9
Consider a finite graph G ∈ ˆG, by Lemma 12, it induces a diagram (8)
admitting a colimit if there is a universal arrow f : G → NI n with n ∈ L. From
this it follows that the graph is acyclic: otherwise, we would have a non-empty
path x ։ x for some vertex x, which would imply f (x) < f (x). Similarly,
suppose that G is a graph with vertices x and y such that there is no path
x ։ y or y ։ x, and there is an universal morphism f : G → NI n for some
n ∈ L. Suppose that f (x) ≤ f (y) (the case where f (y) ≤ f (x) is similar). We
can define a morphism g : G → NI (n + 1) by g(z) = f (z) + 1 if there is a path
x ։ z, g(y) = f (x) and g(z) = f (z) otherwise. This morphism is easily checked
to be well-defined. Since we always have f (x) ≤ f (y) and g(x) > g(y), there is
no morphism h : NI n → NI (n + 1) such that h ◦ f = g.
Conversely, given a finite acyclic connected graph G, the relation ≤ defined
on morphisms by x ≤ y whenever there exists a path x ։ y is a total order.
Writing n for the number of vertices in G, the function f : G → NI n, which to
a vertex associates the number of vertices strictly below it wrt ≤, is universal
in the sense of Lemma 12.
Proposition 14. The free conservative finite cocompletion P of L is equiva-
lent to the full subcategory of ˆL whose objects are presheaves P satisfying the
conditions of Proposition 10.
Proof. By Lemma 11, the category P is equivalent to the full subcategory of ˆL
whose objects are presheaves preserving limits of diagrams of the form (8) gen-
erated by some graph G ∈ ˆG which admits a colimit, i.e. by Lemma 13 the finite
graphs which are acyclic and connected. We write Gn for the graph with [n]
as vertices and edges i → (i + 1) for 0 ≤ i < n − 1. It can be shown that any
acyclic and connected finite graph can be obtained from the graph Gn, for some
n ∈ N, by iteratively adding an edge x → y for some vertices x and y such
that there exists a non-empty path x ։ y. Namely, suppose given an acyclic
and connected finite graph G. The relation ≤ on its vertices, defined by x ≤ y
whenever there exists a path x ։ y, is a total order, and therefore the graph G
contains Gn, where n is the number of edges of G. An edge in G which is not
in Gn is necessarily of the form x → y with x ≤ y, otherwise it would not be
acyclic. Since by Proposition 10, see (7), the diagram generated by a graph of
the form . . .
is preserved by presheaves in P (which corresponds to adding an edge between
vertices at the source and target of a non-empty path), it is enough to show
that presheaves in P preserve diagrams generated by graphs Gn. This follows
again by Proposition 10, see (6).
One can notice that a presheaf P ∈ P is characterized by its underlying
graph since P (0) is reduced to one element and P (n) with n > 2 is the set of
paths of length n in this underlying graph: P ∼= I∗(I∗P ). We can therefore
simplify the description of the cocompletion of L as follows:
Theorem 15. The free conservative finite cocompletion P of L is equivalent to
the full subcategory of the category ˆG of graphs, whose objects are finite graphs
such that for every non-empty path x ։ y there exists exactly one edge x → y.
Equivalently, it can be described as the category whose objects are finite sets
equipped with a transitive relation <, and functions respecting relations.
10
In this category, pushouts can be explicitly described as follows:
Proposition 16. With the last above description, the pushout of a diagram in
P (B, <B ) f
←− (A, <A) g
−→ (C, <C ) is B ⊎ C/ ∼ with B ∋ b ∼ c ∈ C whenever
there exists a ∈ A with f (a) = b and f (a) = c, equipped with the transitive
closure of the relation inherited by <B and <C .
Lines with labels. The construction can be extended to the labeled case (i.e. L is
not necessarily a singleton). The forgetful functor ˆL → Set sending a presheaf P
to the set P (1) admits a right adjoint ! : Set → ˆL. Given n ∈ N∗ the elements
of !L(n) are words u of length n over L, with !L(sn−1
i )(u) being the word ob-
tained from u by removing the i-th letter. The free conservative finite cocomple-
tion P of L is the slice category L/!L, whose objects are pairs (P, ℓ) consisting
of a finite presheaf P ∈ ˆL together with a labeling morphism ℓ : P → !L of
presheaves. Alternatively, the description of Proposition 15 can be straightfor-
wardly adapted by labeling the elements of the objects by elements of L (labels
should be preserved by morphisms), thus justifying the use of labels for the
vertices in following examples.
5 Examples
In this section, we give some examples of merging (i.e. pushout) of patches.
Example 17. Suppose that starting from a file ab, one user inserts a line a′ at
the beginning and c in the middle, while another one inserts a line d in the
middle. After merging the two patches, the resulting file is the pushout of
a′
a
c
b
f1
←−
a
b
f2
−→
a
d
b
which is
a′
a
c d
b
Example 18. Write G1 for the graph with one vertex and no edges, and G2 for
the graph with two vertices and one edge between them. We write s, t : G1 → G2
for the two morphisms in P. Since P is finitely cocomplete, there is a coproduct
G1 + G1 which gives, by universal property, an arrow seq : G1 + G1 → G2:
G2
G1
s 8 8 rrrrr / / G1 + G1
seq O O
G1
oo
tff▲▲▲▲▲ or graphically s
< < ②②②②②②②② / /
seq
O
O
o
o t
b
b
❊❊❊❊❊❊❊❊
that we call the sequentialization morphism. This morphism corresponds to the
following patch: given two possibilities for a line, a user can decide to turn them
into two consecutive lines. We also write seq′ : G1 + G1 → G2 for the morphism
obtained similarly by exchanging s and t in the above cocone. Now, the pushout
of seq
←−− seq′
−−→ is
which illustrates how cyclic graphs appear in P during the cocompletion of L.
11
Example 19. With the notations of the previous example, by taking the co-
product of two copies of idG1 : G1 → G1, there is a universal morphism
G1 + G1 → G1, which illustrates how two independent lines can be merged
by a patch (in order to resolve conflicts).
id•
< < ②②②②②②②②② / /
merge
O
O
o
o id•
b
b
❊❊❊❊❊❊❊❊❊
6 Handling deletions of lines
All the steps performed in previous sections in order to compute the free con-
servative finite cocompletion of the category L+ can be adapted in order to
compute the cocompletion P of the category L as introduced in Definition 1,
thus adding support for deletion of lines in patches. In particular, the general-
ization of the description given by Theorem 15 turns out to be as follows.
Theorem 20. The free conservative finite cocompletion P of the category L
is the category whose objects are triples (A, <, ℓ) where A is a finite set of
lines, < is a transitive relation on A and ℓ : A → L associates a label to
each line, and morphisms f : (A, <A, ℓA) → (B, <B , ℓB ) are partial functions
f : A → B such that for every a, a′ ∈ A both admitting an image under f , we
have ℓB (f (a)) = ℓA(a), and a <A a′ implies f (a) <B f (a′).
Similarly, pushouts in this category can be computed as described in Proposi-
tion 16, generalized in the obvious way to partial functions.
Example 21. Suppose that starting from a file abc, one user inserts a line d
after a and the other one deletes the line b. The merging of the two patches
(in P′) is the pushout of
a
d
b
c
f1
←−
a
b
c
f2
−→
a
c
which is
a
d
c
i.e. the file adc. Notice that the morphism f2 is partial: b has no image.
Interestingly, a category very similar to the one we have described in The-
orem 20 was independently proposed by Houston [3] based on a construction
performed in [2] for modeling asynchronous processes. This category is not
equivalent to ours because morphisms are reversed partial functions: it is thus
not the most general model (in the sense of being the free finite cocomple-
tion). As a simplified explanation for this, consider the category FinSet which
is the finite cocompletion of 1. This category is finitely complete (in addition
to cocomplete), thus FinSetop is finitely cocomplete and 1 embeds fully and
faithfully in it. However, FinSetop is not the finite cocompletion of 1. Another
way to see this is that this category does not contain the “merging” morphism
of Example 19, but it contains a dual morphism “duplicating” lines.
12
7 Concluding remarks and future works
In this paper, we have detailed how we could derive from universal constructions
a category which suitably models files resulting from conflicting modifications.
It is finitely cocomplete, thus the merging of any modifications of the file is
well-defined.
We believe that the interest of our methodology lies in the fact that it adapts
easily to other more complicated base categories L than the two investigated
here: in future works, we should explain how to extend the model in order
to cope with multiple files (which can be moved, deleted, etc.), different file
types (containing text, or more structured data such as xml trees). Also, the
structure of repositories (partially ordered sets of patches) is naturally modeled
by event structures labeled by morphisms in P, which will be detailed in future
works, as well as how to model usual operations on repositories: cherry-picking
(importing only one patch from another repository), using branches, removing
a patch, etc. It would also be interesting to explore axiomatically the addition
of inverses for patches, following other works hinted at in the introduction.
Once the theoretical setting is clearly established, we plan to investigate
algorithmic issues (in particular, how to efficiently represent and manipulate the
conflicting files, which are objects in P). This should eventually serve as a basis
for the implementation of a theoretically sound and complete distributed version
control system (no unhandled corner-cases as in most current implementations
of vcs).
Acknowledgments. The authors would like to thank P.-A. Melli`es, E. Haucourt,
T. Heindel, T. Hirschowitz and the anonymous reviewers for their enlightening
comments and suggestions.
References
[1] J. Ad´amek and J. Rosicky. Locally presentable and accessible categories,
volume 189. Cambridge Univ. Press, 1994.
[2] R. Cockett and D. Spooner. Categories for synchrony and asynchrony.
Electronic Notes in Theoretical Computer Science, 1:66–90, 1995.
[3] R. Houston. On editing text. http://bosker.wordpress.com/2012/05/10/on-editing-text.
[4] J. Jacobson. A formalization of darcs patch theory using inverse semi-
groups. Technical report, CAM report 09-83, UCLA, 2009.
[5] M. Kelly. Basic concepts of enriched category theory, volume 64. Cambridge
Univ. Press, 1982.
[6] S. Mac Lane. Categories for the Working Mathematician, volume 5 of
Graduate Texts in Mathematics. Springer Verlag, 1971.
[7] S. Mac Lane and I. Moerdijk. Sheaves in geometry and logic: A first
introduction to topos theory. Springer, 1992.
[8] R. Par´e. Connected components and colimits. Journal of Pure and Applied
Algebra, 3(1):21–42, 1973.
13
[9] M. Ressel, D. Nitsche-Ruhland, and R. Gunzenh¨auser. An integrating,
transformation-oriented approach to concurrency control and undo in group
editors. In Proceedings of the 1996 ACM conference on Computer supported
cooperative work, pages 288–297. ACM, 1996.
[10] D. Roundy and al. The Darcs Theory. http://darcs.net/Theory.
[11] R. Street and R. Walters. The comprehensive factorization of a functor.
Bull. Amer. Math. Soc, 79(2):936–941, 1973.
14
A A geometric interpretation of presheaves on L+
Since presheaf categories are sometimes a bit difficult to grasp, we recall here the
geometric interpretation that can be done for presheaves in ˆL+. We forget about
labels of lines and for simplicity suppose that the empty file is not allowed (the
objects are strictly positive integers). In this section, we denote this category
by L. The same reasoning can be performed on the usual category L+, and
even L, but the geometrical explanation is a bit more involved to describe.
In this case, the presheaves in ˆL can easily be described in geometrical
terms: the elements P of ˆL are presimplicial sets. Recall from Proposition 4
that the category L is the free category whose objects are strictly positive
natural integers, containing for every integers n ∈ N∗ and i ∈ [n + 1] mor-
phisms sn
i : n → n + 1, subject to the relations sn+1
i sn
j = sn+1
j+1 sn
i when-
ever 0 ≤ i ≤ j < n. Writing y : L → ˆL for the Yoneda embedding, a repre-
sentable presheaf y(n + 1) ∈ ˆLfin
+ can be pictured geometrically as an n-simplex:
a 0-simplex is a point, a 1-simplex is a segment, a 2-simplex is a (filled) triangle,
a 3-simplex is a (filled) tetrahedron, etc.:
y(1) y(2) y(3) y(4)
Notice that the n-simplex has n faces which are (n − 1)-dimensional simplices,
and these are given by the image under y(sn
i ), with i ∈ [n], of the unique el-
ement of y(n + 1)(n + 1): the i-th face of an n-simplex is the (n − 1)-simplex
obtained by removing the i-th vertex from the simplex. More generally, a
a
b c
d
f
g
h
i
j α
presheaf P ∈ ˆLfin
+ (a finite presimplicial set) is a finite colimit
of representables: every such presheaf can be pictured as a glu-
ing of simplices. For instance, the half-filled square on the right
corresponds to the presimplicial set P with P (1) = {a, b, c, d},
P (2) = {f, g, h, i, j}, P (3) = {α} with faces P (s1
1)(f ) = a,
P (s1
0)(f ) = b, etc.
Similarly, in the labeled case, a labeled presheaf (P, ℓ) ∈ L/! can be pic-
tured as a presimplicial set whose vertices (0-simplices) are labeled by elements
a
b
c
ab
bc
acabc
of L. The word labeling of higher-dimensional simplices can then be
deduced by concatenating the labels of the vertices it has as iterated
faces. For instance, an edge (a 1-simplex) whose source is labeled
by a and target is labeled by b is necessarily labeled by the word
ab, etc.
More generally, presheaves in L+ can be pictured as augmented presimplicial
sets and presheaves in L as augmented simplicial sets, a description of those can
for instance be found in Hatcher’s book Algebraic Topology.
B Proofs of classical propositions
In this section, we briefly recall proofs of well-known propositions as our proofs
rely on a fine understanding of those. We refer the reader to [7] for further
details.
15
Proposition 8 Given a functor F : C → D, with D cocomplete, the associated
nerve NF : D → ˆC admits a left adjoint RF : ˆC → D called the realization
along F . This functor is defined on objects P ∈ ˆC by
RF (P ) = colim(El(P ) π
−→ C F
−→ D)
Proof. In order to show the adjunction, we have to construct a natural family of
isormorphisms D(RF (P ), D) ∼= ˆC(P, NF D) indexed by a presheaf P ∈ ˆC and an
object D ∈ D. A natural transformation θ ∈ ˆC(P, NF D) is a family of functions
(θC : P C → NF DC)C∈C such that for every morphism f : C′ → C in C the
diagram
P (C)
P (f )  
θC / / D(F C, D)
D(F f,D)
P (C′) θC′
/ / D(F C′, D)
commutes. It can also be seen as a family (θC (p) : F C → D)(C,p)∈El(P ) of
morphisms in D such that the diagram
F C θC (p)
#
#
●●●●
D
F C′
F f
O
O
θC′ (P (f )(p))
;
;
①①①
or equivalently
F πP (C, p) θC (p)
'
'
◆◆◆◆◆
D
F πP (C′, p′)
F πP f
O
O
θC′ (p′ )
7
7
♣♣♣♣♣
commutes for every morphism f : C′ → C in C. This thus defines a co-
cone from F πP : El(P ) → D to D, and those cocones are in bijection with
morphisms RF (P ) → D by definition of RF (P ) as a colimit: we have shown
D(RF (P ), D) ∼= ˆC(P, NF (D)), from which we conclude.
The equivalence between the two conditions of Definition 9 can be shown as
follows.
Proposition 22. Given a functor F : C → D, the two following conditions are
equivalent:
(i) the associated nerve functor NF : D → ˆC is full and faithful,
(ii) every object of D is canonically a colimit of objects in C: for every D ∈ D,
D ∼= colim(El(NF D) π
−→ C F
−→ D)
Proof. In the case where D is cocomplete, the nerve functor NF : D → ˆC admits
RF : ˆC → D as right adjoint, and the equivalence amounts to showing that the
right adjoint is full and faithful if and only if the counit is an isomorphism,
which is a classical theorem [6, Theorem IV.3.1]. The construction can be
adapted to the general case where D is not necessarily cocomplete by considering
colim(El(−) π
−→ C F
−→ D) : ˆC → D as a partially defined left adjoint (see [8]) and
generalizing the theorem.
16
C Proofs of the construction of the finite cocom-
pletion
Lemma 11 A presheaf P ∈ ˆL preserves finite limits, if and only if it sends the
colimits of diagrams of the form
El(G) πG
−−→ G I
−→ L
to limits in Set, where G ∈ ˆG is a finite graph such that the above diagram
admits a colimit. Such a diagram in L is said to be generated by the graph G.
Proof. In order to check that a presheaf P ∈ ˆL preserves finite limits, we have
to check that it sends colimits of finite diagrams in L which admit a colimit
to limits in Set, and therefore we have to characterize diagrams which admit
colimits in L. The number of diagrams to check can be reduced by using the
facts that limits commute with limits [6]. For instance, the inclusion functor
I : G → L is dense, which implies that every object n ∈ L is canonically a
colimit of the objects 1 and 2 by the formula n ∼= colim(El(NI n) π
−→ G I
−→ L),
see Definition 9. Thus, given a finite diagram K : J → L, we can replace any
object n different from 1 and 2 occurring in the diagram by the corresponding
diagram El(NI n) π
−→ G I
−→ L, thus obtaining a new diagram K′ : J → L which
admits the same colimit as K. This shows that P will preserve finite limits if
and only if it preserves limits of finite diagrams in L in which the only occurring
objects are 1 and 2. Since the only non-trivial arrows in L between the objects
1 and 2 are s1
0, s1
1 : 1 → 2, and removing an identity arrow in a diagram does
not change its colimit, the diagram K can thus be assimilated to a bipartite
graph with vertices labeled by 1 or 2 and edges labeled by s1
0 or s1
1, all edges
going from vertices 1 to vertices 2.
We can also reduce the number diagrams to check by remarking that some
pairs of diagrams are “equivalent” in the sense that their image under P have
the same limit, independently of P . For instance, consider a diagram in which
an object 2 is the target of two arrows labeled by s1
0 (on the left). The diagram
obtained by identifying the two arrows along with the objects 1 in their source
(on the right) can easily be checked to be equivalent by constructing a bijection
between cocones of the first and cocones of the second.
2 ... 2 2 2 ... 2
1
5
5 ...
O
O
@
@ 1
O
O
^
^
8
8 1
f
f
^
^ s1
0
@
@
✁✁✁ 1s1
0
^
^
❂❂❂ @ @ 8 8
1
f
f ...
O
O
@
@ 1
O
O
^
^
i
i
2 ... 2 2 2 ... 2
1
8
8 ...
O
O
@
@ 1
O
O
^
^
@
@ 1
f
f
^
^
s1
0
O
O @ @
8
8 1
^
^ ...
O
O
@
@ 1
O
O
^
^
f
f
More precisely, if we write K : J ′ → L and K : J → L for the two diagrams and
J : J ′ → J for the obvious functor, the canonical arrow colim(K◦J) → colim(K)
is an isomorphism, i.e. the functor J is final. The same reasoning of course also
holds with s1
1 instead of s1
0. We can therefore restrict ourselves to considering
diagrams in which 2 is the target of at most one arrow s1
0, and of at most one
arrow s1
1. Conversely, if an object 2 is the target of no arrow s1
0 (on the left),
then we can add a new object 1 and a new arrow from this object to the object
2 (on the right) and obtain an equivalent diagram:
2 2 ... 2
1
^
^ ...
O
O
@
@ 1
f
f
O
O
^
^
2 2 ... 2
1
s1
0
O O 1
^
^ ...
O
O
@
@ 1
f
f
O
O
^
^
17
The same reasoning holds with s1
1 instead of s1
0 and we can therefore restrict
ourselves to diagrams in which every object 2 is the target of exactly one arrow s1
0
and one arrow s1
1.
Any such diagram K is obtained by gluing a finite number of diagrams of
the form
2
1
s1
1 @ @ ✁✁✁ 1
s1
0
^^❂❂❂
along objects 1, and is therefore of the form El(G) π
−→ G I
−→ L for some finite
graph G ∈ ˆG: the objects of G are the objects 1 in K, the edges of G are the
objects 2 in K and the source and target of an edge 2 are respectively given by
the sources of the corresponding arrows s1
1 and s1
0 admitting it as target. For
instance, the diagram on the left
2 2 2
1
s1
1 @ @ ✁✁✁ 1
s1
0
^^❂❂❂
s1
1 @ @ ✁✁✁
s1
1 & & ◆◆◆◆◆◆◆ 1
s1
0
^^❂❂❂
s1
1 @ @ ✁✁✁ 1
s1
0
xx♣♣♣♣♣♣♣
s1
0
^^❂❂❂
2
0 / / 1 / / 6 6 2 / / 3
is generated by the graph on the right.
Lemma 12 Given a graph G ∈ ˆG, the associated diagram (8) admits a colimit
in L if and only if there exists n ∈ L and a morphism f : G → NI n in ˆL
such that every morphism g : G → NI m in ˆL, with m ∈ L, factorizes uniquely
through NI n:
G f/ /
g
2 2
NI n / / NI m
Proof. We have seen in proof of Proposition 8 that morphisms in ˆL(G, NI n) are
in bijection with cocones in L from El(G) πG
−−→ G I
−→ L to n, and moreover given
a morphism h : n → m in G the morphism ˆL(G, NI n) → ˆL(G, NI m) induced by
post-composition with NI h is easily checked to correspond to the usual notion of
morphism between n-cocones and m-cocones induced by NI h (every morphism
NI n → NI m is of this form since NI is full and faithful). We can finally conclude
using the universal property defining colimiting cocones.
D Proofs for deletions of lines
In this section, we detail proofs of properties mentioned in Section 6.
D.1 Sets and partial functions
Before considering the conservative finite cocompletion of the category L, as
introduced in Definition 1, it is enlightening to study the category PSet of sets
and partial functions. A partial function f : A → B can always be seen
1. as a total function f : A → B ⊎ {⊥A} where ⊥A is a fresh element wrt A,
where given a ∈ A, f (a) = ⊥A means that the partial function is undefined
on A,
18
2. alternatively, as a total function f : A ⊎ {⊥A} → B ⊎ {⊥B} such that
f (⊥A) = ⊥B .
This thus suggests to consider the following category:
Definition 23. The category pSet of pointed sets has pairs (A, a) where A
is a set and a ∈ A as objects, and morphisms f : (A, a) → (B, b) are (total)
functions f : A → B such that f (a) = b.
Point (ii) of the preceding discussion can be summarized by saying that a partial
function can be seen as a pointed function and conversely:
Proposition 24. The category PSet of sets and partial functions is equivalent
to the category pSet of pointed sets.
It is easily shown that the forgetful functor U : pSet → Set, sending a
pointed set (A, a) to the underlying set A, admits a left adjoint F : Set → pSet,
defined on objects by F A = (A ⊎ {⊥A}, ⊥A). This adjunction induces a monad
T = U F on Set, from which point (i) can be formalized:
Proposition 25. The category PSet is equivalent to the Kleisli category SetT
associated to the monad T : Set → Set.
Finally, it turns out that the category pSet of pointed sets might have been
discovered from PSet using “presheaf thinking” as follows. We write G for the
full subcategory of PSet containing two objects: the empty set 0 = ∅ and a
set 1 = {∗} with only one element, and two non-trivial arrows ⋆ : 0 → 1 and
⊥ : 1 → 0 (the undefined function) such that ⊥◦⋆ = id0. We write I : G → PSet
for the inclusion functor. Consider the associated nerve functor NI : PSet → ˆG.
Given a set A the presheaf NI A ∈ ˆG is such that:
• NI A0 = PSet(I0, A) ∼= {⋆}: the only morphism 0 → A in PSet is noted
⋆,
• NI A1 = PSet(I1, A) ∼= A ⊎ {⊥A}: a morphism 1 → A is characterized
by the image of ∗ ∈ A which is either an element of A or undefined,
• NI A⋆ : NI A1 → NI A0 is the constant function whose image is ⋆,
• NI A⊥ : NI A0 → NI A1 is the function such that the image of ⋆ is ⊥A.
Moreover, given A, B ∈ PSet a natural transformation from NI A to NI B is a
pair of functions f : A ⊎ {⊥A} → B ⊎ {⊥B} and g : {⋆} → {⋆} such that the
diagrams
A ⊎ {⊥A} f / /
NI A⋆  
B ⊎ {⊥B}
NI B⋆
{⋆} g / / {⋆}
and
A ⊎ {⊥A} f / / ⊎{⊥B }
{⋆} g / /
NI A⊥ O O
{⋆}
NI B⊥
O
O
commutes. Since {⋆} is the terminal set, such a natural transformation is char-
acterized by a function f : A ⊎ {⊥A} → B ⊎ {⊥B} such that f (⊥A) = ⊥B . The
functor NI : PSet → ˆG is thus dense and its image is equivalent to pSet.
19
D.2 A cocompletion of L
The situation with regards to the category L is very similar. We follow the
plan of Section 4 and first investigate the unlabeled case: L is the category with
integers as objects and partial injective increasing functions f : [m] → [n] as
morphisms f : m → n.
We write G for the full subcategory of L whose objects are 0, 1 and 2. This
is the free category on the graph
0 s0
0 / / 1
d0
0
o
o
s1
0 / /
s1
1 / / 2d1
0
oo
d1
1
o
o
subject to the relations
s1
0s0
0 = s1
1s0
0 d0
0s0
0 = id1 d1
0s1
0 = id2 d1
1s1
1 = id2 d0
0d1
0 = d0
0d1
1 (9)
(see Proposition 4). We write I : G → L for the embedding and consider the
associated nerve functor NI : L → ˆG. Suppose given an object n ∈ L, the
associated presheaf NI n can be described as follows. Its sets are
• NI n0 = L(I0, n) ∼= {⋆},
• NI n1 = L(I1, n) ∼= [n] ⊎ {⊥},
• NI n2 = L(I2, n) ∼=
{(i, j) ∈ [n] × [n] | i < j} ⊎ {(⊥, i) | i ∈ [n]} ⊎ {(i, ⊥) | i ∈ [n]} ⊎ {(⊥, ⊥)}:
a partial function f : 2 → n is characterized by the pair of images
(f (0), f (1)) of 0, 1 ∈ [n], where ⊥ means undefined.
and morphisms are
• NI ns0
0 : NI n1 → NI n0 is the constant function whose image is ⋆,
• NI nd0
0 : NI n0 → NI n1 is the function whose image is ⊥,
• NI ns1
0 : NI n2 → NI n1 is the second projection,
• NI ns1
1 : NI n2 → NI n1 is the first projection,
• NI nd1
0 : NI n1 → NI n2 sends i ∈ [n] ⊎ {⊥} to (⊥, i)
• NI nd1
1 : NI n1 → NI n2 sends i ∈ [n] ⊎ {⊥} to (i, ⊥)
Such a presheaf can be pictured as a graph with NI n1 as set of vertices, NI n2 as
set of edges, source and target being respectively given by the functions NI ns1
1
and NI ns1
0:
⊥
0 1 2
. . .
n − 1
Its vertices are elements of [n] ⊎ {⊥} and edges are of the form
20
• i → j with i, j ∈ [n] such that i < j,
• i → ⊥ for i ∈ [n]
• ⊥ → i for i ∈ [n]
• ⊥ → ⊥
Morphisms are usual graphs morphisms which preserve the vertex ⊥. We are
thus naturally lead to define the following categories of pointed graphs and
graphs with partial functions. We recall that a graph G = (V, s, t, E) consists of
a set V of vertices, a set E of edges and two functions s, t : E → V associating
to each edge its source and its target respectively.
Definition 26. We define the category pGraph of pointed graphs as the cat-
egory whose objects are pairs (G, x) with G = (V, E) and x ∈ V such that for
every vertex there is exactly one edge from and to the distinguished vertex x,
and morphisms f : G → G′ are usual graph morphisms consisting of a pair
(fV , fE ) of functions fV : VG → VG′ and fE : EG → EG′ such that for every
edge e ∈ EG, fV (s(e)) = s(fE (e)) and fV (t(e)) = t(fE (e)), which are such that
the distinguished vertex is preserved by fV .
Definition 27. We define the category PGraph of graphs and partial mor-
phisms as the category whose objects are graphs and morphisms f : G → G′
are pairs (fV , fE ) of partial functions fV : VG → VG′ and fE : EG → EG′ such
that
• for every edge e ∈ EG such that fE (e) is defined, fV (s(e)) and fV (t(e))
are both defined and satisfy fV (s(e)) = s(fE (e)) and fV (t(e)) = t(fE (e)),
• for every edge e ∈ EG such that fV (s(e)) and fV (t(e)) are both defined,
fE (e) is also defined.
More briefly: a morphism is defined on an edge if and only it is defined on its
source and on its target.
Similarly to previous section, a partial morphism of graph can be seen as a
pointed morphism of graph and conversely:
Proposition 28. The categories pGraph and PGraph are equivalent.
Now, notice that the category L is isomorphic to the full subcategory of PGraph
whose objects are the graphs whose set of objects is [n] for some n ∈ N, and
such that there is an edge i → j precisely when i < j. Also notice that the
full subcategory of pGraph whose objects are the graphs NI n (with ⊥ as
distinguished vertex) with n ∈ N is isomorphic to the full subcategory of ˆG
whose objects are the NI n with n ∈ N. And finally, the two categories are
equivalent via the isomorphism of Proposition 28. From this, we immediately
deduce that the functor NI : L → ˆG is full and faithful, i.e.
Proposition 29. The functor I : G → L is dense.
We can now follow Section 4 step by step, adapting each proposition as nec-
essary. The conditions satisfied by presheaves in P introduced in Proposition 10
are still valid in our new case:
21
Proposition 30. Given a presheaf P ∈ ˆL which is an object of P,
1. the underlying graph of P is finite,
2. for each non-empty path x ։ y there exists exactly one edge x → y,
3. P (n + 1) is the set of paths of length n in the underlying graph of P ,
and P (0) is reduced to one element.
Proof. The diagrams of the form (6) and (7) used in proof of Proposition 10
still admit the same colimit n + 1 with the new definition of L and 0 is still
initial. It can be checked that the limit of the image under a presheaf P ∈ ˆL
of a diagram (6) is still the set of paths of length n in the underlying graph
of P .
Lemma 11 is also still valid:
Lemma 31. A presheaf P ∈ ˆL preserves finite limits, if and only if it sends the
colimits of diagrams of the form
El(G) πG
−−→ G I
−→ L
to limits in Set, where G ∈ ˆG is a finite pointed graph such that the above
diagram admits a colimit. Such a diagram in L is said to be generated by the
pointed graph G.
Proof. The proof of Lemma 11 was done “by hand”, but we mentioned a more
abstract alternative proof. In the present case, a similar proof can be done but
would be really tedious, so we provide the abstract one. In order to illustrate
why we have to do so, one can consider the category of elements associated to
the presheaves representable by 0 and 1, which are clearly much bigger than in
the case of Section 4:
El(NI 0) ∼= ⋆ s0
0 / / ⊥
d0
0
o
o
s1
0 / /
s1
1 / / (⊥, ⊥)d1
0
oo
d1
1
o
o
and
El(NI 1) ∼=
(⊥, ⊥)
d1
0
rrrr
y
y
rrrrrr d1
1
rrrr
y
y
rrrrrr
⊥
d0
0
✈✈✈✈✈
{
{
✈✈✈✈✈
s1
0
9 9 rrrrrrrrrrr s1
1rrrrrr
9
9
rrrr
s1
1 / /
s1
0
▲▲▲▲▲▲
%
%
▲▲▲▲
(⊥, 1)
d1
0
rrrrr
y
y
rrrrr
⋆
s0
0
;
; ✈✈✈✈✈✈✈✈✈✈✈
s0
0
/
/ 1
s1
0rrrrrrr
9
9
rrrr
s1
1 / / (1, ⊥)
d1
1
o
o
subject to relations which follow directly from (9).
Before going on with the proof, we need to introduce a few notions. A func-
tor F : C → D is called final if for every category E and diagram G : D → E
the canonical morphism colim(G ◦ F ) → colim(G) is an isomorphism [6]: re-
stricting a diagram along F does not change its colimit. Alternatively, these
22
functors can be characterized as functors such that for every object D ∈ D the
category is non-empty and connected (there is a zig-zag of morphisms between
any two objects). A functor F : C → D is called a discrete fibration if for any
object C ∈ C and morphism g : D → F C in D there exists a unique mor-
phism f : C′ → C in C such that F f = g called the lifting of g. To any such
discrete fibration one can associate a presheaf P ∈ ˆD defined on any D ∈ D
by P D = F −1(D) = {C ∈ C | F C = D} and on morphisms g : D′ → D
as the function P g which to C ∈ P D associates the source of the lifting of g
with codomain C. Conversely, any presheaf P ∈ ˆD induces a discrete fibration
El(P ) π
−→ D, and these two operations induce an equivalence of categories be-
tween the category ˆD and the category of discrete fibrations over D. It was
shown by Par´e, Street and Walters [8, 11] that any functor F : C → D factorizes
as final functor J : C → E followed by a discrete fibration K : E → D, and
this factorization is essentially unique: this is called the comprehensive factor-
ization of a functor. More explicitly, the functor K can be defined as follows.
The inclusion functor Set → Cat which send a set to the corresponding dis-
crete category admits a left adjoint Π0 : Cat → Set, sending a category to its
connected components (its set of objects quotiented by the relation identifying
two objects linked by a zig-zag of morphisms). The discrete fibration part K
above can be defined as El(P ) π
−→ D where P ∈ ˆD is the presheaf defined by
P = Π0(−/F ). In this precise sense, every diagram F in D is “equivalent” to
one which is “generated” by a presheaf P on D (we adopted this informal termi-
nology in the article in order to avoid having to introduce too many categorical
notions).
In our case, we can thus restrict to diagrams in L generated by presheaves
on L. Finally, since I : G → L is dense, we can further restrict to diagrams
generated by presheaves on G by interchange of colimits.
Lemma 13 applies almost as in Section 4: since the morphism f : G → NI n (seen
as a partial functions between graphs) has to satisfy the universal property of
Lemma 12, by choosing for every vertex x of G a partial function gx : G → NI m
which is defined on x (such a partial function always exists), it can be shown
that the function f has to be total. The rest of the proof can be kept unchanged.
Similarly, Proposition 14 applies with proof unchanged.
Finally, we have that
Theorem 32. The free conservative finite cocompletion P of L is equivalent to
the full subcategory of ˆL whose objects are presheaves P satisfying the conditions
of Proposition 30. Since its objects P satisfy I∗I∗(P ) ∼= P , it can equivalently
be characterized as the full subcategory of ˆG whose objects P are
1. finite,
2. transitive: for each non-empty path x ։ y there exists exactly one edge
x → y,
3. pointed: P (0) is reduced to one element.
From this characterization (which can easily be extended to the labeled case),
along with the correspondence between pointed graphs and graphs with par-
tial functions (Proposition 28), the category is shown to be equivalent to the
23
category described in Theorem 20: the relation is defined on vertices x, y of a
graph G by x < y whenever there exists a path x ։ y.
As in case of previous section, the forgetful functor pGraph → Graph
admits a left adjoint, thus inducing a monad on Graph. The category pGraph
is equivalent to the Kleisli category associated to this monad, which is closely
related to the exception monad as discussed in [3].
E Modeling repositories
We briefly detail here the modeling of repositories evoked in Section 7. As
explained in the introduction, repositories can be modeled as partially ordered
sets of patches, i.e. morphisms in L. Since some of them can be incompatible,
it is natural to model them as particular labeled event structures.
Definition 33. An event structure (E, ≤, #) consists of a set E of events, a
partial order relation ≤ on E and incompatibility relation on events. We require
that
1. for any event e, the downward closure of {e} is finite and
2. given e1, e′
1 and e2 such that e1 ≤ e′
1 and e1#e2, we have e′
1#e2.
Two events e1 and e2 are compatible when they are not incompatible, and
independent when they are compatible and neither e1 ≤ e2 nor e2 ≤ e1. A
configuration x is a finite downward-closed set of compatible events. An event
e2 is a successor of an event e1 when e1 ≤ e2 and there is no event in between.
Given an event e we write ↓e for the configuration, called the cause of e, obtained
as the downward closure of {e} from which e was removed. A morphism of
event structures f : (E, ≤, #) → (E′, ≤′, #′) is an injective function f : E → E′
such that the image of a configuration is a configuration. We write ES for the
category of event structures.
To every event structure E, we can associate a trace graph T (E) whose
vertices are configurations and edges are of the form x e
−→ x ⊎ {e} where x
is a configuration such that e 6 ∈ x and x ⊎ {e} is a configuration. A trace is
a path x ։ y in this graph. Notice that two paths x ։ y are of the same
length. Moreover, given two configurations x and y such that x ⊆ y, there
exists necessarily a path x ։ y. It can be shown that this operation provides a
faithful embedding T : ES → Graph from the category of event structures to
the category of graphs, which admits a right adjoint.
Example 34. An event structure with five events is pictured on the left (arrows
represent causal dependencies and ∼ incompatibilities). The associated trace
graph is pictured on the right.
d
&
f & f & f & f
b
A
A
✄✄✄ c
]
]
❀❀❀❀ / o
c′
a
^
^
❂❂❂ @ @ ✁✁✁
7
7 ♣♣♣♣♣♣♣
{a, b, c, d}
{a, b, c}
d O O
{a, b, c′} {a, b}
c′
o
o c 7 7 ♦♦♦♦♦ {a, c}
bgg❖❖❖❖
{a, c′}
b
f
f
◆◆◆◆
{a}
c′
o
o
bgg❖❖❖❖❖❖ c
7
7 ♦♦♦♦♦
∅
a O O
24
Definition 35. A categorical event structure (E, λ) in a category C with an
initial object consists of an event structure equipped with a labeling functor
λ : (T E)∗ → C, where (T E)∗ is the free category generated by the graph T E,
such that λ∅ is the initial object of C and the image under λ of every square
z
y1
e2 = = ⑤⑤⑤⑤ y2
e1aa❇❇❇❇
x
e1
a
a
❇❇❇ e2
=
=
⑤⑤⑤
in T E is a pushout in C.
The following proposition shows that a categorical event structure is char-
acterized by a suitable labeling of events of E by morphisms of C.
Proposition 36. The functor λ is characterized, up to isomorphism, by the
image of the transitions ↓e e
−→ ↓e ⊎ {e}.
We can now define a repository to be simply a finite categorical event struc-
ture (E, ≤, #, λ : T (E) → L). Such a repository extends to a categorical event
structure (E, ≤, #0, I ◦ λ : T (E) → P), where #0 is the empty conflict rela-
tion. The state S of such an event structure is the file obtained as the image
S = I ◦ λ(E) of the maximal configuration: this is the file that the users is
currently editing given his repository. Usual operations on repositories can be
modeled in this context, for instance importing the patches of another reposi-
tory is obtained by a pushout construction (the category of repositories is finitely
cocomplete).
25

# Document Title
Skip to content
Duck Rowing
Duck Rowing
by Fred McCann
    Home
    About
    Microblog
    Mastodon
    Search
    RSS
Bzr Init: A Bazaar Tutorial
Posted On December 26, 2013	
Around seven years ago I made the leap from Subversion to distributed version control. The problem I was trying to solve was simple- I used to commute which meant 2-3 hours of my days were spent on a train. To pass the time, I would learn new programming languages or frameworks. Eventually I became very productive in spite of the fact that a train is a hard place to work and battery technology was very poor.
I’d been a Subversion user, but there was no way I could work offline on the train. While this wasn’t the only reason I considered switching to distributed version control, it was the straw that broke the camel’s back.
Why Bazaar?
Bazaar is perhaps the least popular option of the big three, open source DVCS: Git, Mercurial, and Bazaar. At this point, I think you can make the case that Git is by far the most commonly used option. In fact, when I was experimenting on the train Git was the first tool I tried. After a few weeks with Git, it was clear things weren’t working out.
I still use Git, though not as often as other systems. Because of Github and Git’s popularity, it’s hard not to use Git. I also use Mercurial almost every day to collaborate on some projects that have chosen Mercurial. And obviously I’m a Bazaar user. The majority of the projects I work on are tracked by Bazaar.
I’m advocating for Bazaar, or that you should at least learn more about it. Unlike the infamous Why Git Is Better Than X site, I’m going to do my best to stay away from focusing on minor differences that don’t matter or blatantly inflammatory misinformation. A lot of DVCS advocacy focuses on the benefits of DVCS in general, and attributes these benefits to one tool. In reality, Git, Mercurial, and Bazaar are all completely distributed systems and all share the same basic benefits of DVCS.
In that spirit, I’d like to get a few things out of the way:
    Developers successfully use Git, Mercurial, and Bazaar on projects both large and small.
    Git, Mercurial, and Bazaar are basically feature equivalent.
    Git, Mercurial, and Bazaar are all fast.
What I will focus on is how much friction a tool introduces, that is how easy it is to get work done, and the philosophies and design decisions, which have an impact on how the tools are used.
What makes Bazaar the best choice is it’s by far the easiest tool to use, but more important, it gets the DVCS model right.
An Ideal Model of Distributed Version Control
I assume anyone reading this likely already uses a DVCS or at least is aware of the benefits. In a nutshell, when you have a number of people both collaborating and working independently on the same codebase, you essentially have a number of concurrent branches, or lines of development. A DVCS tool makes creating and merging these branches easy, something that was a problem with Subversion or CVS. This is the core aspect of DVCS from which all the benefits flow.
The most visible consequence of this is that sharing code is divorced from saving snapshots. This is what solved my working offline problem, but in general it gives people a lot more control over how they can model their workflows with their tools.
The most important aspect of a DVCS is how well it models and tracks branches and the ease with which we can fork branches and merge branches.
Before examining why I think Bazaar gets the DVCS model correct, I’m going to present an ideal view of a project history. What I’m presenting here should be uncontroversial, and I’m going to present it in tool neutral language.
Assume the following scenario:
    (trunk a) Steve creates an initial state as the beginning of a “trunk” branch
    (trunk b) Steve implements feature 0 in a mirror of trunk and pushes upstream
    (branch1 a) Duane branches into branch1 and commits work
    (branch1 b) Duane commits work in branch1
    (trunk c) Duane lands his work into trunk by merging branch1 and pushing upstream
    (branch3 a) Pete branches into branch3 and commits
    (branch2 a) Jerry branches into branch2 and commits
    (branch3 b) Pete commits work in branch3
    (branch2 b) Jerry commits work in branch2
    (branch2 c) Jerry commits work in branch2
    (branch3 c) Pete commits work in branch3
    (trunk d) Jerry lands feature 2 into trunk by merging branch2 and pushing upstream
    (trunk e) Pete lands feature 3 into trunk by merging branch3 and pushing upstream
We have four branches: Trunk, Branch 1, Branch 2, and Branch 3. A branch is a line development. We could also think of it as a thread of history.
Ideal
The dots on the diagram represent snapshots. The snapshots represent the state of our project as recorded in history. The ordered set of all snapshots is:
Project = {A, B, 1A, 1B, C, 2A, 2B, 2C, D, 3A, 3B, 3C, E}
This is the complete set of snapshots. You could call this ordering the project history across all branches. Note that this is not ordered by the time the work done, but rather the time work arrived in the trunk. Ordering either by merge time or actual time could be valid, but this ordering is more beneficial for understanding the project.
Also, snapshots have parents. The parent of a snapshot is the set of immediately preceding snapshots in the graph. For example, the parent of snapshot 3B is snapshot 3A. The parent of snapshot D is {C, 2C}.
A snapshot that has two parents represents the point at which two branches were merged.
We can further define the snapshots that define the branches:
Trunk = {A, B, C, D, E}
Branch 1 = {1A, 1B}
Branch 2 = {2A, 2B, 2C}
Branch 3 = {3A, 3B, 3C}
Furthermore we can define the concept of a head. A head, generally, is the most recent snapshot in a branch, after which new snapshots are appended.
Trunk head = E
Branch 1 head = 1B
Branch 2 head = 2C
Branch 3 head = 3C
With this ideal view of history, there are a number of questions we can answer such as:
What is the history of a branch?
The history of branch X is the set of snapshots that compose the branch.
What is the common ancestor of two branches (i.e. when did two branches diverge)?
This can be answered by traversing the graphs of the branches, starting at the head then working backwards through the graph to find a common ancestor.
When did two branches merge?
To answer this we find a snapshot that has two parents, one from each branch.
In which branch was a snapshot a added?
This is a question we’d ask when we want to determine which branch, or line of development, introduced a change. We can determine this because a snapshot is a member of only one of the branches’s set of snapshots.
Like I said, nothing here is controversial. The qualities I’m describing is what makes it possible to make sense of our project’s history.
When looking at the project above, we’d most often want to talk about the history of the trunk branch. If we made the assumption that branches were feature branches, a view of the trunk would look like this:
E [Merge] Implement Feature 3
D [Merge] Implement Feature 2
C [Merge] Implement Feature 1
B Implement Feature 0
A Initial State
The view of the trunk is the “big picture” of the project. The merge badges are an indicator that there is more history available in the associated feature branch’s history. For example, Branch 2 might look like:
2C Completion of Feature 2
2B Partial Completion of Feature 2
2A Start work on Feature 2
The branches don’t have to be features- they could represent individual developers, teams, etc. The distinction is that branches are lines of development with histories, and we want to see different levels of detail in the history depending on what branch we’re examining.
Git
Git is by far the most popular of the big three open source DVCS. It is also an order of magnitude harder to learn and to use than either Mercurial or Bazaar. I’ve expounded on this in my post on the Jenkins incident and one on Cocoapods.
At this point, I don’t think it’s inflammatory to point out that Git is difficult to use. A simple Google search will turn up enough detail on this point that I won’t address it here. Git’s interface is a very leaky abstraction, so anyone who’s going to be very successful using Git will eventually have to learn about Git’s implementation details to make sense of it.
This introduces a lot of cognitive overhead. More plainly, a user of Git has to expend a significant amount of focus and attention on using Git that would otherwise be spent on their actual work.
This overhead is inherent in a lot of Git commands as the metaphors are fuzzy and a lot of commands have bad defaults.
While Git’s interface is more complicated than is necessary, it certainly isn’t a large enough concern to stop people from successfully using it, or other UIs built on top of it.
The core problem with Git is that it gets the branching model wrong.
The first problem with Git is that it uses colocated branches by default. A Git repository has a single working directory for all branches, and you have to switch between them using the git checkout command.
This is just one source of cognitive overhead. You only have a single working tree at a time, so you lack cues as to which branch you’re operating in. It also makes it difficult to work in more than one branch at a time as you have to manage intermediate changes in your working directory manually before you can perform the switch with git stash.
A better default would be to have a directory per branch. In this simpler scenario, there’s never a concern about collisions between changes in the working directory and you can take advantage of all the cues from working in separate directories and take advantage of every tool that’s been developed over the years that understands files and directories.
Colocated branches essentially make directories modal, which requires more of your attention.
Of course, you could make the case that collocated branches take up less space, but considering how cheap storage is, this doesn’t impact most projects, which is why it’s an odd default behavior.
Another case you could make is that you can share intermediate products, such as compiled object files. While this seems like a good rationale, a better, simpler solution would to use a shared directory for build products.
While colocated branches aren’t a deal breaker, there is a more fundamental flaw in Git’s branch model. As I described in the ideal DVCS model, a branch is a line of development or a thread of history. Git in fact does not track this history. In Git, a branch is merely the head pointer, not the history.
In Git, branch 3 = 3C, not {3A, 3B, 3C}
What we would consider the history only exists in the reflog, which will eventually be garbage collected.
By default, when we send our work up to a remote repository, not only is the reflog information not sent, the head pointer is also discarded, so any notion of a branch is lost.
This means that Git does not match the ideal model I’ve put forth, and is not able to answer certain questions such as, in which branch was a snapshot a added?
Let’s take the example in the ideal model. We’ll assume each branch is a feature, and that a separate developer is working on each in their local repository. We’ll also assume that our “trunk” branch is the master branch on some remote repository.
If we use the default behavior in Git, and make all the snapshots as defined in the ideal model in the same chronological order, this is what our graph looks like:
Git
$ git log
commit 314397941825fb0df325601519694102f3e4a25b
Merge: 56faf98 a12bd9e
Author: Pete
    E  Implement Feature 3
commit 56faf98989a059a6c13315695c17704668b98bda
Author: Jerry
    2C  Complete Feature 2
commit a12bd9ea51e781cdc37cd6bce8a3966f2b5ee952
Author: Pete
    3C  Complete Feature 3
commit 4e36f12f1a7dd01aa5887944bc984c316167f4a9
Author: Jerry
    2B  Partial Completion of Feature 2
commit 2a3543e74c32a7cdca7e9805545f8e7cef5ca717
Author: Pete
    3B  Partial Completion of Feature 3
commit 5b72cf35d4648ac37face270ee2de944ac2d5710
Author: Jerry
    2A  Start work on Feature 2
commit 842dbf12c8c69df9b4386c5f862e0d338bde3e01
Author: Pete
    3A  Start work on Feature 3
commit b6ca5293b79e3c37341392faac031af281d25205
Author: Duane
    1B  Complete Feature 1
commit 684d006bfb4b9579e7ad81efdbe9145efba0e4eb
Author: Duane
    1A  Start work on Feature 1
commit ad79f582156dafacbfc9e2ffe1e1408c21766578
Author: Steve
    B  Implement Feature 0
commit 268de6f5563dd3d9683d307e9ab0be382eafc278
Author: Steve
    A  Initial State
Git has completely mangled our branch history.
This is not a bug, this is a fundamental design decision in Git. For lack of a better term, I’d differentiate Git from other DVCS systems by saying it’s patch oriented. The goal of Git is to arrive at some patch that describes the next state in a project- tracking history is viewed as not as important as tracking the patch or the content.
This means we don’t have a good way of figuring out what’s going on with our conceptual trunk branch. Only one branch was recorded (incorrectly), and everything is shoved into master in chronological order. We also don’t have a good way to see the history of any particular branch, nor which branch a branch was forked from or when it was merged back in.
If you’ve ever had to figure out how some change entered the system or whether some branch is cleared to be released, you’ll know that this matters.
Git’s broken branching model means the burden of correctly recording or interpreting history is thrust upon the user.
The safest workaround is to do all branch merging with the –no-ff option. This step will correct the object graph since it will memorialize all merges. The default Git graph loses snapshots {C,D}, but preventing fast forward merges will fix that.
The second problem is that Git doesn’t capture enough information in each snapshot to remember the branch. To get around this, we have to manually insert that information, in-band, in the commit message.
So, when a developer commits work, they’ll manually tag the commit with branch metadata. Then we can at least use git log’s grep option to see work clearly:
$ git log --grep="\[Trunk\]"
commit 5d155c1d81b9c2803f2f2de890298ca442597535
Merge: 6a4ba95 0ed512b
Author: Pete
    E [Trunk][Merge] Implement Feature 3
commit 6a4ba950c807d9cb8fe55236e8d787b4fd4a663a
Merge: f355800 36ef31b
Author: Jerry
    D [Trunk][Merge] Implement Feature 2
commit f3558008a174e56735d95432b5d27cf0a26db030
Merge: df9f0df 3bdf920
Author: Duane
    C [Trunk][Merge] Implement Feature 1
commit df9f0df24faf0de5e8653626b9eb8c780086fc28
Author: Steve
    B [Trunk] Implement Feature 0
commit 67ba4b110a8cb45ba4f5a4fc72d97ddffafd7db0
Author: Steve
    A [Trunk] Initial State
$ git log --grep="\[Branch1\]"
commit 4b327621647987c6e8c34d844068e48dab82a6ab
Author: Duane
    1B [Branch1] Complete Feature 1
commit 469a850c458179914f4a79c804b778e2d3f1bfbe
Author: Duane
    1A [Branch1] Start work on Feature 1
This is sort of a clunky and error-prone approach, but tagging commit messages is a common way to compensate for Git’s lack of branch support.
There is a more drastic and dangerous approach which is to use a Git rebase workflow, potentially with squashing commits.
In this scenario, rather than adding more information to commits, you actively rewrite history to store even less data than Git captures by default. In the rebase workflow, rather than getting the mangled Git graph produced by the normal Git process, we get a straight line:
Rebase
It’s ironic that the rebase workflow, a reaction to Git not storing enough information to model or make sense of project history, is to erase even more information. While the straight line graph is easier to read, it’s completely unable to answer questions laid out in the ideal model.
This is what a Git user might refer to as a “clean” history. Your average Mercurial or Bazaar user is confused by this because both of the other tools correctly model branches, and neither one would consider the butchered object graph “clean”. The rebase workflow conflates readable logs with “clean” histories.
Rebasing is significantly worse than the –no-ff work around as you can squash commits that might actually matter. Another problem with rebasing, beyond that you might accidentally select the wrong commits, is that it prevents collaboration.
In order to use a rebase workflow, you have to adopt byzantine notions of “private” and “public” history. If you rebase away (i.e. discard) commits that have been shared with others, it leads to complicated cascading rebases. So, if I’m working on a feature, and I intend to use the rebase workflow, I’m not going to be able to make ad-hoc merges with colleagues because no one can count on my snapshots sticking around. Basically, sharing my work becomes difficult. One of the benefits of DVCS is that collaborating should be easy.
It’s very hard to recommend Git. It’s the most difficult tool to use, and its broken branch model gives rise to Git specific solutions to Git inflicted problems that Git users may think are best practices rather than kludges.
44354577
Mercurial
Mercurial is much easier to use than Git. This is not to say that there aren’t some UI concerns. The biggest gripe I have with Mercurial is that it separates pulling changes into a repository from merging changes, which can lead to a pending merge situation where you have multiple heads on the same branch as they have not yet been merged. Normally this isn’t a problem, but if you’re careless, you can end up with three or four heads in a repository before catching it.
I’ve never understood if the manual multiple heads pull/merge pattern was considered a feature in Mercurial, or if it was an implementation detail leaking through. It certainly feels like that latter just as does Git’s “feature” of exposing the index to users.
That said, the gulf between Mercurial usability and Git usability is akin to the distance between New York City and Los Angeles. While Mercurial’s UI is more complicated than Bazaar’s, that difference is more like the distance between New York City and Boston, so I won’t belabor the point.
Mercurial has two popular models for branching (though I believe there are technically four). The first and most common model is to branch by cloning. You can think of this as a euphemism for not branching at all.
In Mercurial, all work happens in a branch, but by default, all work happens in the same branch, called the “default” branch. The primary advantage branching by cloning has is that it’s easier than the alternatives. There’s fewer commands to know and call and there’s a working directory per branch. However, if we apply all of the commits in the same chronological order as I described in the ideal model example, here’s what our changeset graph looks like:
Murky
$ hg log
changeset:   10:d21a419a293e
tag:         tip
parent:      9:53d61d1605f9
parent:      6:7129c383aa3b
user:        Pete
summary:     E Implement Feature 3
changeset:   9:53d61d1605f9
user:        Pete
summary:     3C Complete Feature 3
changeset:   8:fb340c4eb013
user:        Pete
summary:     3B Partial Completion of Feature 3
changeset:   7:2a35bc51a28d
parent:      3:e9292c14c2b2
user:        Pete
summary:     3A Start work on Feature 3
changeset:   6:7129c383aa3b
user:        Jerry
summary:     2C Complete Feature 2
changeset:   5:b13281f66a25
user:        Jerry
summary:     2B Partial Completion of Feature 2
changeset:   4:187abbd1b3c4
user:        Jerry
summary:     2A Start work on Feature 2
changeset:   3:e9292c14c2b2
user:        Jerry
summary:     1B Complete Feature 1
changeset:   2:a5e8ccb38d38
user:        Duane
summary:     1A Start work on Feature 1
changeset:   1:b60a08bf46c7
user:        Steve
summary:     B Implement Feature 0
changeset:   0:747376f7cfb9
user:        Steve
summary:     A Initial State
Mercurial has completely mangled our branch history. Well, to be fair, this is what happens when we don’t actually use branches.
Mercurial fared a bit better than Git on the logging front- at least the order of changesets reflects the order they were merged, though I’ve seen projects where either the complexity of the merges or perhaps because of an older version of Mercurial, the log looked nearly identical to Git’s.
Unlike Git, Mercurial has no equivalent to the –no-ff option for merging. This means that with this clone-as-branch model, we can’t get snapshots {C,D}.
While Git discards branch histories, Mercurial remembers them. So, if we use the named branches workflow, we have a different story:
Murky2
$ hg log
changeset:   15:5495a79dbe2b
tag:         tip
parent:      10:ab972541c15e
parent:      14:f524ef255a5d
user:        Pete
summary:     E Implement Feature 3
changeset:   14:f524ef255a5d
branch:      branch3
user:        Pete
summary:     3D Close Branch3
changeset:   13:90ea24b0f0e1
branch:      branch3
user:        Pete
summary:     3C Complete Feature 3
changeset:   12:82bef28d0849
branch:      branch3
user:        Pete
summary:     3B Partial Completion of Feature 3
changeset:   11:d26ae37169a3
branch:      branch3
parent:      5:7f7c35f66937
user:        Pete
summary:     3A Start work on Feature 3
changeset:   10:ab972541c15e
parent:      5:7f7c35f66937
parent:      9:4282cb9c4a23
user:        Jerry
summary:     D Implement Feature 2
changeset:   9:4282cb9c4a23
branch:      branch2
user:        Jerry
summary:     2D Close Branch2
changeset:   8:0d7edbb59c8d
branch:      branch2
user:        Jerry
summary:     2C Complete Feature 2
changeset:   7:30bec7ee5bd2
branch:      branch2
user:        Jerry
summary:     2B Partial Completion of Feature 2
changeset:   6:bd7eb7ed40a4
branch:      branch2
user:        Jerry
summary:     2A Start work on Feature 2
changeset:   5:7f7c35f66937
parent:      1:635e85109055
parent:      4:52a27ea04f94
user:        Duane
summary:     C Implement Feature 1
changeset:   4:52a27ea04f94
branch:      branch1
user:        Duane
summary:     1C Close Branch1
changeset:   3:ceb303533965
branch:      branch1
user:        Duane
summary:     1B Complete Feature 1
changeset:   2:a6f29e9917eb
branch:      branch1
user:        Duane
summary:     1A Start work on Feature 1
changeset:   1:635e85109055
user:        Steve
summary:     B Implement Feature 0
changeset:   0:918345ee8664
user:        Steve
summary:     A Initial State
The hg log command is going to show us something that looks very similar to the previous log with a few changes. First off, all of the merge changesets are present. Second, every changeset is associated with a branch (default is assumed if not listed). The last thing to notice is we have an extra changeset per branch to “close” the branch.
Also, we can now easily show the history of a branch:
$ hg log -b default
changeset:   15:5495a79dbe2b
tag:         tip
parent:      10:ab972541c15e
parent:      14:f524ef255a5d
user:        Pete
summary:     E Implement Feature 3
changeset:   10:ab972541c15e
parent:      5:7f7c35f66937
parent:      9:4282cb9c4a23
user:        Jerry
summary:     D Implement Feature 2
changeset:   5:7f7c35f66937
parent:      1:635e85109055
parent:      4:52a27ea04f94
user:        Duane
summary:     C Implement Feature 1
changeset:   1:635e85109055
user:        Steve
summary:     B Implement Feature 0
changeset:   0:918345ee8664
user:        Steve
summary:     A Initial State
$ hg log -b branch1
changeset:   4:52a27ea04f94
branch:      branch1
user:        Duane
summary:     1C Close Branch1
changeset:   3:ceb303533965
branch:      branch1
user:        Duane
summary:     1B Complete Feature 1
changeset:   2:a6f29e9917eb
branch:      branch1
user:        Duane
summary:     1A Start work on Feature 1
When we take advantage of Mercurial’s branching support, you can see how the Git notion of “cleaning” history is ridiculous.
There are some costs to using the named branches workflow. The first one is there’s more manual work to set up and tear down branches. We ended up with additional commits to “close” branches, which is a bit of bookkeeping Mercurial pushes off on the user. It’s possible with planning to make the final commit in a brach and close it at the same time, but in practice you may not actually land a branch in the trunk until after a review or a QA process, so you may not know when it’s time to close the branch until that happens.
Another problem with Mercurial’s implementation is it uses colocated branches with a single working directory by default. The additional cognitive overhead imposed by this choice is what I suspect is the reason more Mercurial users use the clone as a branch approach.
Also, using named branches means your repository will have multiple heads most of the time (one per branch). For intermediate and advanced Mercurial users that have a good mental model of what’s going on, this is no big deal. But beginning Mercurial users are often trained to see multiple heads as a sign of a pending merge, and a situation to be rectified.
In general, the named branch approach, while fully supported and completely functional, feels like an afterthought. Calling the hg branch command to create a new branch issues a warning as though it was advising you against using branches:
$ hg branch branch1
marked working directory as branch branch1
(branches are permanent and global, did you want a bookmark?)
Just for clarification, you do not want a bookmark.
Similarly, when pushing work to an upstream repository, you have to tell Mercurial that yes, you intended to push a new branch:
hg push --new-branch
If I had to sum up Mercurial, I’d call it repository oriented. Unlike Git, it fully tracks history, but it treats the repository as the most prominent metaphor in the system at the expense of the branch. Key Mercurial commands such as clone, pull, push, and log operate on repositories, while it has a separate branch command to operate on branches.
If you’re willing to put up with a bit of extra work and some odd warnings from Mercurial, the named branches workflow meets the ideal model I’ve presented. Even if you choose the clone as a branch model, you’d still have a lot less cognitive overhead than using Git, so while I find it hard to recommend Git, if you’re already a Mercurial user, I’d urge you to consider using named branches.
5pqqp
Bazaar
Bazaar is the simplest of the three systems to use. Common use of Bazaar is much like the clone as a branch approach of Mercurial without exposing the user directly to head pointers or multiple heads. As I said in the Mercurial section, Git is an order of magnitude harder to use than either Mercurial or Bazaar. Bazaar is unquestionably simpler from a UI perspective than Mercurial, especially compared to the named branches workflow, but it’s nothing compared to the gulf between Git and the others in usability.
Also, Bazaar by default uses a directory per branch, so each branch gets its own working directory, meaning you don’t have to use kludges like stashing working directory changes when switching branches. Switching branches is as easy as changing directories. Bazaar does support a method for colocated branches, but it is not the default and it’s rarely needed. As I pointed out in the Git section, there are easy ways to tackle the problems that colocated branches are supposed to solve.
Let’s repeat the experiment with the normal Bazaar workflow and see how it compares to the ideal model:
Bazaar
Bazaar, by default, exactly matches the ideal model. Now, I know my more cynical readers will assume that this is because I picked Bazaar’s model as the “ideal” model, but they would be incorrect. Bazaar is not the first DVCS I used, nor did my ideal model derive from Bazaar. The ideal model is what I think should happen when branching and merging. As I said earlier, I don’t think the model I laid out is controversial. I use Bazaar because it meets the model, not the other way around.
In fact, I think a lot of users get confused by Git and Mercurial’s branch by clone workflow precisely because the history graph that they record does not resemble user’s mental model.
Let’s take a look at the log:
$ bzr log
------------------------------------------------------------
revno: 5 [merge]
committer: Pete
branch nick: trunk
message:
  E Implement Feature 3
------------------------------------------------------------
revno: 4 [merge]
committer: Jerry
branch nick: trunk
message:
  D Implement Feature 2
------------------------------------------------------------
revno: 3 [merge]
committer: Duane
branch nick: trunk
message:
  C Implement Feature 1
------------------------------------------------------------
revno: 2
committer: Steve
branch nick: trunk
message:
  B Implement Feature 0
------------------------------------------------------------
revno: 1
committer: Steve
branch nick: trunk
message:
  A Initial State
------------------------------------------------------------
Use --include-merged or -n0 to see merged revisions.
This is very different than the logs presented by either Mercurial or Git. Each of the logs I’ve shown were taken from the upstream “authoritative” repository. Unlike the others, bzr log does not operate on a repository, it operates on a branch. So by default, we see the history of the project from the perspective of the trunk branch.
Another distinction with Bazaar’s logs is that they are nested. To show the complete log, we can set the nesting level to 0, which will show an infinite level of nesting:
$ bzr log -n0
------------------------------------------------------------
revno: 5 [merge]
committer: Pete
branch nick: trunk
message:
  E Implement Feature 3
    ------------------------------------------------------------
    revno: 3.2.3
    committer: Pete
    branch nick: branch3
    message:
      3C Complete Feature 3
    ------------------------------------------------------------
    revno: 3.2.2
    committer: Pete
    branch nick: branch3
    message:
      3B Partial Completion of Feature 3
    ------------------------------------------------------------
    revno: 3.2.1
    committer: Pete
    branch nick: branch3
    message:
      3A Start work on Feature 3
------------------------------------------------------------
revno: 4 [merge]
committer: Jerry
branch nick: trunk
message:
  D Implement Feature 2
    ------------------------------------------------------------
    revno: 3.1.3
    committer: Jerry
    branch nick: branch2
    message:
      2C Complete Feature 2
    ------------------------------------------------------------
    revno: 3.1.2
    committer: Jerry
    branch nick: branch2
    message:
      2B Partial Completion of Feature 2
    ------------------------------------------------------------
    revno: 3.1.1
    committer: Jerry
    branch nick: branch2
    message:
      2A Start work on Feature 2
------------------------------------------------------------
revno: 3 [merge]
committer: Duane
branch nick: trunk
message:
  C Implement Feature 1
    ------------------------------------------------------------
    revno: 2.1.2
    committer: Duane
    branch nick: branch1
    message:
      1B Complete Feature 1
    ------------------------------------------------------------
    revno: 2.1.1
    committer: Duane
    branch nick: branch1
    message:
      1A Start work on Feature 1
------------------------------------------------------------
revno: 2
committer: Steve
branch nick: trunk
message:
  B Implement Feature 0
------------------------------------------------------------
revno: 1
committer: Steve
branch nick: trunk
message:
  A Initial State
Nested logs is a simple but incredibly useful innovation. We don’t really need a graphical tool to visualize history. Also, it’s clear that the Git notion of “cleaning” history is equally as ludicrous as it was when looking at Mercurial’s logs, perhaps even more so.
There is a real advantage though as compared to Mercurial’s named branches workflow. For lack of a better term, Bazaar is branch oriented. Both git init and hg init create new repositories. However, bzr init creates a new branch. Both git clone and hg clone create copies of repositories. The equivalent command in Bazaar, bzr branch forks a new branch. Both git log and hg log examine the history of the repository. The bzr log command shows branch history.
It’s a very subtle change in point of view. Bazaar elevates branches to the primary metaphor, relegating the concept of repository to more of a background player role.
The result is that the basic Bazaar workflow is to always branch and to always accurately track branch history. It accomplishes this with a cognitive overhead that is comparable to working with a centralized system like Subversion or Mercurial’s clone as a branch method.
Bazaar does have some downsides. The most significant one is it has the smallest user base of the big three open source DVCS. This means it will be a little harder to find answers to your questions in blog postings and Stack Exchange answers. Also, commercial hosting companies like Bitbucket aren’t going to offer Bazaar support. Nor is it as actively developed as Mercurial and Git.
However, Bazaar’s positives so strongly outweigh the negatives that you’d be crazy to not consider Bazaar.
44354687
Branching is the Secret Sauce in DVCS
What makes DVCS work is the ability to handle branches from creation to merging, and to do it in the least intrusive way possible so we can get our work done.
Bazaar gets branching right, by default. It’s also the easiest system to learn and use. You don’t have to expend nearly as much focus and attention on Bazaar as Mercurial and Git, which means you have more attention to devote to your actual work.
I did not go into detail showing the commands used to create the graphs and logs presented in this post because rather than getting bogged down in the syntax and the details, I want to make the big picture clear. I leave the commands as an exercise to motivated readers so they can prove to themselves that their favorite tool just might not be recording history as they visualize it.
Bzr Init: A Bazaar Tutorial
At this point, you might be wondering where the actual tutorial is. First I wanted to convince you why Bazaar is a good choice, if not the best choice.
The actual tutorial is much longer than this rant, so I gave it it’s own site:
Bzr Init: A Bazaar Tutorial
This tutorial is not meant to be exhaustive; it exists to show you how easy Bazaar is and how it can be easily adapted to your workflow. It’s inspired by (let’s say ripped off from) Joel Spolsky’s Mercurial Tutorial- HgInit. Hginit is not only one of the best Mercurial tutorials, it’s one of the best DVCS tutorials. I’d recommend you read it even if you’re not a Mercurial user.
Hopefully you’d get the same experience from the Bzr Init tutorial. In any case, if I’ve piqued your interest, read on!
Categories: Programming
Tagged: bazaar, bzr, dvcs, git, hg, mercurial, vcs, version control
Post navigation
Previous Post‹
Not That There’s Anything Wrong With That, 1952 Edition
›Next Post
Chromebook Boom?
© 2024 Duck Rowing |
Footer Menu
Privacy Policy
    Home About Microblog Mastodon Search RSS 

thank
you you haven't even heard what I have
to say yet um okay so since we're a nice
cozy audience I mean the material I've
prepared is introductory um mostly
anyway so to the idea is to give a
flavor of what darks is about why it
exists um how it works at at a fairly
high level um but I do know that at
least a third of the audience is quite
familiar with darks and I don't know
about the rest of the audience but I'm
happy to sort of you know dive into more
details in terms of questions and so
forth if if people would like that um so
um yeah so in when I get to the demo for
example if everybody feels that they
know exactly what dark stars and so
forth I can skip that and um instead you
can ask difficult questions about some
of the other
slides um so I guess does does anybody
not know what darks
is has anybody here not used
dos okay so then at least some
introductory material is
worthwhile um
sorry that one right okay so what is um
so I guess from a point of view of um a
Haso programmer you probably only come
across dark you may I mean these days
you probably only come across darks
occasionally um a lot you know five
years ago most high school projects were
um were in dark were hosted in darks and
now roughly speaking get as one and um
there are only a few hard projects that
are still using darks
um so what is it exactly well I mean in
like get material and so forth it is
it's a distributed version control
system and historically it was one of
the very early ones to be around um
after T and what's now Arch and um
things in some ancient stuff in that
mold um so in other words it's
distributed it's not like subversion in
CVS it doesn't have one Central server
or at least you're not forced to have
one Central server but I think the
concept of distributed version control
is now pretty familiar to people um
unlike other distributed systems or in
fact any other version control system um
the first class objects in darks are
patches um so in most Version Control
Systems what you try to do what really
what the Version Control System cares
about is storing trees of um your Source
tree and you change it a bit and it
stores another copy of your Source tree
probably with a lot of sharing and um
optimization so that it's not it's not
storing an entire copy each time um but
as far as the version control system is
concerned its job really is just to give
you back uh Source tree at a particular
revision um and keep track of all that
for you um darks tries to in its sort of
fundamental model keep um use patches um
so the changes between trees rather than
the actual trees themselves and I'll go
into more about that
later um so why bother um and by the way
I just add that it is I'm very happy to
have heckling from G users who think
that g is the be all and end all we can
have a nice argument
um so but why bother keeping darks going
um I mean we could basically stop say to
tell everybody who's using darks you
might as well stop you might as well
switch to GitHub right now um so those
of us who are still working on it think
that it does actually this this idea of
using first class patches is actually
important it does actually give you a
kind of power um and a different a
different kind of model for working with
um working with Version Control that
makes um that that really does give you
some something that get and mural and so
forth don't give you
um and the other way of the other aspect
of this is that I mean in practice most
projects are are hosted in git nowadays
and we need um we're working on uh on
having a bridge to get so that you know
people will be able to say host their
projects and get and um some people are
able to use darks or some people might
have their Central host be in darks and
allow people to submit git patches um so
that's kind of in progress but um you
mention gives the impression of being
based on
in what way does it I
mean well no what you what you see um
what you see in the git user interface
is are commits right so there are and so
those are that's that's a specific
specific state of a repository right so
if you know if you say bring up if you
bring up the git user interface and you
look at you will see a tree of um or
graph really of of revisions and each of
those revisions will correspond to a
specific sourc tree um so whereas in
darks when you look at the changes in a
repository each of those changes really
does correspond to the changes from the
previous date and that's that's how dark
stores them and that's how darks lets
you manipulate them that that would be
my I'm sure you know what I mean really
here but um that that would be my Spiel
for that that
question okay um so what what does it
really mean to have first class patches
um well I guess part of part of this is
really just is is really just a
philosophical difference I
mean hasal has first class functions so
does c right um but it's it's fairly
clear which you'd prefer to use if you
actually if you really want to write
functional programs um and that's that's
the same kind of thing with darks you
know you could if you look if you look
at gear to M or whatever through the
right glasses um you could think of you
could think of the diff to the previous
revision as being the first class
objects in that system but really um it
doesn't make it easy to work with it in
that way um darks does its very best to
um to make it easy as possible to treat
Pat patches as the as the real unit of
work in a in a dark
repository um so what does it actually
mean in practice um so one of the really
key benefits that you get from using
darks is that cherry picking changes so
is very easy very it's encouraged by the
user interface um it's very cheap um and
once you've done it um once you've
Cherry Picked a change and you decide
you want the you know the changes that
you skipped over when you did the cherry
picking you pull those back into your
repository and you've got exactly the
same thing as you would have had if you
pull them in the normal order okay so
darks kind of gives you and I'll show
you um I'll show you that a bit more uh
in My
Demo um and whereas if you did that in
git you'd end up having to um you'd end
up with two different two different
repositories you'd have to merge the two
to get get back to the same
state um the other thing about darks is
that merges a deterministic so anytime
you do a merge in darks um it will give
you exactly the same result wherever you
are in the world whatever version of
darks you're using um if it would the
and the behavior of the merge will just
depend on um what what darks chose to
record at the time you actually saved
your
patches um from the point of view of
user of darks we like to think that we
have a simple intuitive user model if
you just sort of start using darks um
without knowing how to do so you know we
hope that you'll quick quickly get to
grips with what what's going on behind
the scenes enough to understand how to
use it but not not really need to
understand the the guts too much um and
you I think that's that's a criticism
that a lot of people make of git that
it's it's very hard to use it well
without having expert level knowledge of
um of a large portion of the um of a
large portion of how git works and how
you're expected to interact with it um
so by contrast again darks tries to have
a simple command set um another thing
another philosophical point about darks
is that we try to make commands
interactive by default so you know when
you've got got some options about how to
about how the what you could do with a
command and rather than having to pass
some Flags to figure out exactly you
know to get that behavior um darks will
try to ask you questions I mean not it
it that's not entirely the case but it
will it will ask you questions about um
what would you um how how much of this
would you commit would you like to make
for example that kind of
thing so what doesn't darks have um well
a whole load really um so the features
that people tend to find missing most
more and more are um multi multiple head
repositories so in darks you you have to
have one directory per um per checkout
basically per Branch so if you want to
branch and have two different things in
flight and switch between them you need
to just use two different directories in
your file system um hopefully we'll fix
that at some point but it's not not
trivial um and some people argue that we
shouldn't do it but I think we've most
of us most of dark developers concluded
that we should um darks makes a mess of
conflict handling if you have
complicated conflict so simple conflicts
aren't particularly problematic um but
when you start having conflicts with
conflicts and that kind of thing the
both the user interface and the
internals of darks tend to get a little
bit upset um I mean so you know in
practice people don't run into this very
often I mean darks works fine with small
to mediumsized repositories it doesn't
really work brilliantly with really huge
repositories um and another part of that
is another point on here that it doesn't
it's not all that
fast um it doesn't have unique um
revision identifiers for a particular
particular state of the repository which
really annoys some people cuz you know
things like G to even subversion you
just say here this number represents an
exact state of the repository you give
that to somebody else and if they've got
enough State they'll be able to
reproduce that exactly what you
had
um and really these days what darks is
missing is is not GitHub um and of
course it doesn't have the whole set of
tooling or in fact a large user
Community around it any well it never
did have a large user Community but it's
shrunk a
bit um and yeah it's not not all that
fast but
still what about code
complexity complexity for
what
um it okay without if there are no
conflicts involved then I mean that I
mean s emerge okay so emerge emerg in
DOS is more is ASM totically more
complex than emerg in git if you've got
a very large um if you've got a very
large history leading up to the merge so
if you if you've branched and you've
done you've made 100 changes on each
side and you've got say one one file
repository then in dark's emerge will
scale with the number of changes that
you've made um on each you know like the
product of the number of changes on each
side um whereas in get it would scale
with the number of um with these well
with the size of the tree roughly so
that that's kind of I mean it's you know
darks might be faster probably wouldn't
be but um it could in principle be with
you know just a single change well maybe
not is the word
do you mean with ter in with respect to
conflicts or with respect to just
merging in
general right so yes I mean so it is
quadratic yes it's the product if you've
got if you've got two branches 100
changes on each side of the branch that
are not that are unique to that side to
that Branch to the each separate Branch
then it will be 100 times 100 will be
the the amount of work dark has darks
has to do to merge those those
changes um I mean I
think I don't think that's such a big
big problem in practice
um
sorry yeah I mean so if you get
conflicts then that is a real problem um
but if you don't get if it's just if
it's a clean merge um yeah I mean I
think I mean that is a significant point
that it does it does do these merges one
step at a time um but I don't I
personally I don't think you run into it
that that often with sort of at least
mediumsized
repositories um
okay so I'll dive into a demo now um so
there are some people who haven't seen
darks so I I guess I'll go into it
properly
um okay
so um I'm going to start by making a
dark's reposit a directory to hold my
repository um can everyone read this
okay I think I checked from the back
earlier so I think it should be all
right okay so I'm going to keep my
repository in this directory and the
first thing I do is do a dark in it um
do well just get get the basic metadata
in place get this make this be an in
make this be an empty
repository um and then I'm going to copy
in a um a simple source file that I
prepared earlier for the purpose sorry
um so just to show you what's in that
file for now um it's just sort of a very
basic high school program that I shall
make make a few changes
to okay and so the next thing I need to
do is tell darks that this file exists
in my repository and it's something that
it should
track so darks
add and so in darks um there is a um the
command the equivalent of what might be
called commit in many other Version
Control Systems is called record um so
which means record a patch um so I'm
going to run that
command
and uh it scrolled
confusingly because I've zoomed in too
much now I can't find my mouse pointer
sorry
okay
um is it going to be okay if I make the
font a bit smaller so I can actually see
the full
width right is that still readable for
everybody
okay um all right so dark is just going
to um now is this is what I was saying
about it being interactive before it's
just going to ask me about what I've
done and what I've done is I've I've
added the file and I've put some
contents in the file so um I'm just
going to record this
initial um this initial patch so this is
just the in initial
version okay so then dark asks me some
stuff about um just confirms for sure
that I want to record exactly what I
said I wanted to say record and asks me
what the name of the commit name of the
patch is going to be and if I wanted to
it would bring far up an editor and let
me edit um put a longer comment than a
single line yep question the first CH
was adding the file yeah second was
adding the content that's right yes
um so you only need to do the ad once
file that's right yes I mean it's
exactly the same as tracking a file in
any other system you just it's so that's
otherwise it I mean there is also I
could have also done this by saying
darks record- L which says looked for
ads and it would have then gone off and
looked for every file in the repository
and let me add that so um it's just it's
a trade-off between whether you want to
have untracked files to worry about or
not okay so I'm not going to add a long
comment okay so now I'm going to edit
that file
um okay so I'm going to make a couple of
changes to this file um so firstly I'm
going
to I'm going to just add one more um one
more thing that the this program is
going to
do and secondly I'm going to change one
of these messages that it's already um
that it's already printing
out
okay and then I'm going to come back and
record that changes so um darks allow
accepts prefixes of any command that it
normally um that it that that are unique
so I can use wreck as a synonym for
record which I at least personally find
quite useful
blast
um okay sorry my Demo's just g a bit
wrong
um so what what I was okay so what I was
hoping at that point was that dark
actually I can no this is fine I can
still do this um so what I was intending
for at this point when I did um was that
darks would ask would give me those two
changes as separate um as separate
changes to the repository but what it's
done is it's decided that it's decided
um it's decided that the diff that this
all lives in one part of the diff so
it's showing me showing me two changes I
made at once and since I actually want
to show you how it will treat those to a
separate changes that's a bit
inconvenient um there going to sorry
there is still going to be a second
change yes but it's not going to make
semantic sense when I start making other
changes to the patch so what I'm going
to do actually is bring up something I
wasn't intending to show you um which is
the interactive um interactive editor
for um for CH for changes that you make
that for um for patches that you're
recording so what I actually wanted the
darks to do was say Okay I want I want
the addition of the exclamation mark to
be to be one change and I want this say
goodbye to be a different change so what
I'm going to do here is just edit this
kind of intermediate state that darks
has presented me with to say okay well
the first change I want you to show me
is that addition of the exclamation mark
and then the second change you can show
me will be the addition of goodbye
um okay so um oh actually yeah sorry and
what I actually wanted to do was so I've
gone I've used K to go back um because
what I actually wanted to do was record
the addition of the text first and then
the addition of the message for reasons
I'll explain in a minute change this
message so I shall say no to this one
and I'll I'll
blast
[Music]
all right fine let's
um okay I'm going to I'm going to start
again with this so this actually works
out properly so I'm going to so now I'm
jumping around in what I was actually
intending to do um us usually this kind
of thing doesn't I mean this you know
this this kind of problem where darks
wants to show you changes that you
didn't um that are stuck together in
ways you didn't quite expect um is less
likely when you're working with bigger
repositories because the changes that
you make are more likely to be widely
spread across the you know AC um either
inside a single file or between or
between different files um what's
happened here is I've tried to make a
very small demo um and as a result
everything's um the diffs that it's
asked me about are not not quite the
ones I wanted um put in
before um so what what I'm actually
going to do is just go back and put some
lines in so that it doesn't it
definitely gives me the diff I want just
to cheat a bit really um just to make
this demo work quick at least reasonably
quickly okay so I'm I'm using a called
Dark revert now which um that's what rev
is short for um which just offers me the
changes that I've made locally in my
repository and says do you want to throw
these changes away um and again it's
offering them to me one at a time so I
can just um but in this case I want to
get rid of all of
them okay so what I'm going to do is
um sorry supposed to be high
school
sorry can't use y
either
okay okay so now I'm going to do those
make those same changes again and
hopefully this time it won't it will
offer me those changes
independently if I can work by which I
apparently can't
um excuse
me oh yeah thanks I wasn't actually
going to run the program so it doesn't
really matter matter
but I like I like people to think that I
write valid
hasal okay so that's one of the changes
I could um that I could record which is
the addition of the exclamation mark and
the addition of the goodbye message is
the other change that I can record um
and what I'm going to do and I mean
clearly I could record any of these I
could record any subset of these three
things that I chose to yes sorry my
question is chain yeah say that now the
line between the changes has some has
some content in the previous case it was
an empty
but okay so the only reason it's
different is because the um is because
it's a heuristic Andi it's a heuristic
in diff so at the point so I mean I
guess this is jumping ahead a little bit
in some sense but if you um when when
you do a three-way merge in any Version
Control System what will happen is that
the Version Control System will will run
diff between the between the between the
base of your merge and the two the two
options and then it will try to merge
those changes and at the point where it
runs the diff um there are usually a
there are usually multiple choices for
what kind of diff you can
get right and so the what what's
happened here is that because there are
two blank lines in the file um the
choice about whether to line up the
blank lines with each in in the old file
in the new F in the old file there was
one blank line in between the say hello
and the um and Main and in the new one
there was a blank line between say hello
and goodby and say goodbye and there's
another blank line between say goodbye
and
Main so how diff has chosen to line up
the blank line between those between the
old version and the new version of the
file is what has affected the what's
been presented to
me and so what I did was I changed one
of those blank lines to be something a
bit more than just a blank line thus
forcing it which meant that it couldn't
possibly line those two
up for
me
really the Reas so the difference is
that that line with content when I added
the when I added the first I didn't copy
that content I put a blank line in so
the blank line is different from the
content that was that was there
before so if you so if I um so if you
look at
um yeah yeah it's it's really just it's
really just blank lines getting it diff
getting a little bit confused about it's
always istic that that diff
applies yes exactly so it's just all the
dark is doing at this point is get
making a diff and presenting me with the
individual pieces of that
diff doesn't make
the uh the number of chain sets too
large if you're just editing the P not
subsequent lines but just having one
line one line one line
this part of the line but this is n
Chang for me mhm so it will darks will
offer you all nine changes individually
um if yeah um if you've if you made
changes that are separated in the file
um and you do have so this this
interactive prompt actually has a bunch
of um a bunch of commands that bunch of
keys that you can use at this point to
to choose you don't have to say yes or
no to every single um to every single
change so the the standard thing you use
in that case is you if you know you want
everything that you've done into that
file then you just press F to say record
all changes to that file um or record
all further changes to this file so you
can you know for example if you've made
some change that you didn't want to
record you'd say no at the beginning um
and then you can say or a for example to
record everything that it's going to
offer
um okay so yeah so right now I'm going
to record I'm going to record this the
addition of say goodbye and the call to
say goodbye together so that those those
live live together with an atomic change
set an atomic
patch once you recorded those two
together kind of like stuck together
forever yes um yeah pretty much
y you two up three yeah what happens to
the original file that the the file in
the the file in your direct when you're
doing a record the file in your
directory doesn't get touched at all um
all you're doing is recording is
changing the sort of you know the
current version controlled state so
there's always an implicit diff between
what you've done in your direct your
working directory and what's what the
what the state of the very last Revision
in the repository was and so that diff
has now got smaller but the actual file
hasn't
changed um so on the other hand if I'd
use revert which is about changing the
changing the state of your working copy
then I could have reverted some of these
changes and not others and then the file
would have been put back into some you
know some sort of State a little bit
closer to the work to the to the
recorded copy
but okay so I've
I've recorded a
change that's called i' say goodbye
which has that change in it and now I'm
going to record Another patch
that that incorporates the last change
that I had and nothing
else okay so now what I've recorded is
apart from the initial setup of the
repository I've recorded the change to
um I've I've recorded two different two
different changes firstly I've added say
goodbye and secondly I've changed the um
I've changed the text of
hello okay now I just remembered that I
forgot to clone this repository at the
time I intended to um so I'm going to
well I'm going to do it now anyway um so
I'm going to clone I'm going to clone
the repository that I made um into
another one um and that's dark's get is
the um standard command for doing that
and you can use that with remote remote
repositories as well um and because I
forgot to do this at the time I intended
to which was before I recorded that
change I'm going to delete a couple of
changes from this repository using um
the obliterate
command Okay so and now I'll get back to
what I actually intended to do at this
point which is to show the pull command
which is about moving patches between
repositories and now this is the point
where I'm going to show you how cherry
picking Works in darks in a sort of
simple intuitive way so if I try to pull
from repository one it's going to offer
me the changes that I made to um that I
made to that repository um in the order
that they exist in that repository so
this is a set of changes that are in the
other repository not in my present one
um and it's going to show me them in the
order that that they would live in that
one you got comment there that's the one
comment yeah you see the code um
yes um so X will give me a summary of it
and V will show me the code um though
there's a little bit of metadata that
probably would be more user friendly to
have to have Allied but
[Applause]
yeah okay so at this point I'm going to
I don't want to I don't want to say
goodbye yet I just want to make that I
just want that hello change but that was
the second change I made so I'm going to
say no to this and it's still going to
offer me to offer me offer me the Hello
message pull
so I'm going to pull
that and um there we are and if I have a
look at the contents of demo. HS now
it's got that change to it's got that
change to hello but it hasn't got the
change to goodbye even though that was
never one of the recorded states that I
made in the previous
repository
is I disconect this CH no okay no it's
not um it's no it's not available
locally so if if you wanted that then
what you would need to do is clone the
Clone the entire repository and then
into a different directory and then
start pulling from that yes
um and in fact that's the way I
typically use dos if I'm when I'm I work
on the train a lot I I will just do a
pull from from the Upstream repository
to somewhere and then work work from
that
locally okay so yeah so I've got this um
I've got this change that was um that
was one of the two changes I made but
not in the order that I made it now I'm
going to go back to the other repository
and I'm going to use um I'm going to use
a command called darks
replace so darks replace is a search and
replace operation on your Repository it
takes um so what if I show you demo. HS
I've decided I want to rename the print
message function to something different
so I'm going to I'm going to do darks
replace print message output
message repo1 um not repo one sorry
demo.
HS okay now so firstly i' to emphasize
that this is a pretty dumb search in
replace right it doesn't take any
account of language semantics or
anything like that so if I had if I had
a variable called print message
somewhere else in scope then it would
happily rename that that as well
um okay so now I've done this
replace um it's changed my file for me
but it hasn't actually recorded a patch
to say this is um this is a change I
made so I'll just I'll just do that um
and the change is actually expressed as
this replacement
operation and yes I want to record
that okay so just looking at demo. again
you know that there's been there have
been a couple of occurrences of output
message of what word print message that
are now output message that have been
changed by this replace operation now if
I go back to repository
2 that doesn't actually have all those
call all those call sites for print
message because I didn't pull the change
where I said called say goodbye as well
um but if I pull from repository one I
can still ignore the say goodbye change
and I can pull the print message
change and what's it done to my file um
sorry okay well it's it hasn't pulled to
say goodbye so there's no there's no
change there um but it has um but it has
renamed print message to Output message
correctly and finally if I pull again
from repository
one and I bring back the say goodbye
change I could also shown you that patch
I did it it's pulled back say goodbye
this say goodbye change which was
originally recorded as an additional
print message um but now in the context
that it's just been pulled it's an ADD
of output message because that's what
that that's what makes your program make
sense um now that's only true because
the replace was a safe thing to do on my
repository um but nonetheless it's still
it's um it's done the right
thing um and so the other point about
this is that now this repository is
pretty much identical to that first one
there's no other changes I can pull from
the other one if if I sort of ask darks
you know are there any differences
between these two repositories it won't
there won't really be any um
sure okay
so darks Chang so darks changes is just
a list of um list of what patches you
have in your repository in reverse order
um and as you can see in this repository
it's this way around and in the other
repository it's um you've got them in
the order that I originally recorded
them mhm something which has the print
message inside
yeah and I want the print message to be
there and then put that change
into you want to keep the print message
you mean yes
um so is this
side okay so if I was to take if I was
to um now start editing after this
rename operation and put a new print
message in there right then that will be
that will be safe because it comes after
the replace but if you've if you've got
if you work in a repository that hasn't
seen the replace already but you have
the yeah but I mean so either repository
it doesn't make it doesn't really make
any difference now but if I I mean I can
I can safely change demo. HS now and put
in um no no no what I mean is if you the
change set which
had well it was originally recorded with
the print message change yes
CH which
hading message the
result and and you put it on top of your
already
replaced yeah still it's saying that
it's
message um well that I mean I I think
that's I mean that that was what was
expected to happen because the if you
look at it from the other repositories
point of view the replace was operating
on both print
messages
so um so so in the of the first Chang
the first one uh uh replace the names
and a change which is change uh which is
explicit have message
inside um so in so that I mean that
that's the that's the point of what
darks has done here is that it's decided
to it's it's changed the behavior of
that it's changed the contents of that
patch because of the order in which it's
put them um
so
um in which repository in repo 2
okay
so so there so the patch itself has been
changed by this op by the by the fact
that we've reordered it to say this
patch says this patch is an addition of
output
message it doesn't have the exactly the
same text in it and that's exactly the
point of having first class patches that
your um that dark will change the patch
so the point is that darks has tried to
preserve the meaning of the patch
right so the the meaning of the
repository that we
had
um so I mean that's that's the point of
using replace right you're you're you're
kind of asking darks to do that you're
saying that so looking at it from
another point of view right you've so
let's let's say that I've been
developing a program um with print
message in it and then I decide I'm
going to rename print message to Output
message okay and in parallel to that
somebody else decides that they're going
to add a call to print
message okay I'm
just I just don't know I
like y fair enough well
okay yeah so I mean I think I mean
otherwise if if they if pulling the say
goodbye had resulted in print message at
the end of repo 2 that would have been
tot that would have been incorrect right
I mean it wouldn't have actually been a
functioning program so if you want this
property about cherry picking and so
forth where you can get patches out of
order and then pull the other ones back
it has to do
that guess that's another way of
justifying what I did if you don't like
it but um
anyway kind of I put it in yes I think I
think of outut message and then kind of
like and out the
re take
that so if you um if you add if I now
added an output me a call to Output
message in my repository afterwards and
then I and then I unpulled the replace
um removed the replace patch it would
change that to print message and that
would be correct but the name capture
point that I I thought maybe you were
asking was that if I had say a local
variable called print message or output
message depending on where I in which
state I added it then the replace patch
is going to do the wrong thing with that
so you know if somebody else in another
branch has decided to write a function
that internally uses a print message
variable of its own yes I
supp it won't it w't if you do that it
won't let you do it so there there so
part part of the darks user interface is
that it will detect detect things that
don't make sense like from
a yes
and repl is global I
it's file by
file um there is no patch type for
moving code between different between
places in files um it's something that
we would like to add um but yeah we
haven't done it
yet okay
um
okay so I was um I've already shown you
rever actually no I'll show you a bit
more of that um so if I just edit demo.
HS a little bit more
um just add some garbage in two places
and I confused
by
okay so I've just added a couple of
lines um and now I want to get rid of
those lines and again as I showed you
before darks offered those independently
so I can say revert just the Wibble bit
and then I'll be left with wobble in the
file and then I can revert that as well
and that's gone um darks also has an
inverse of revert so darks tries to make
most operations undoable there are cases
where you that's not really feasible but
um for example darks has this
unreversed um but not the one before
that so I can't get Wibble back
anymore
um okay I'm going to change some the
file this time and keep the changes
um so I'm going to change this text
to
and I'm going to record Another change
with that that in it oops I forgot to
get rid of that never mind I'll do that
in a
minute
uh sorry my laptop's frozen
up
um I think it's frozen solid this what
you get for running
Windows um I'm going to have to reboot
it so
[Music]
I think it I think actually this I think
it may have Hardware problems of some
kind it's
occasionally well I mean all I can say
is that my dark my laptop does lock up a
lot and I do run darks in it a lot
but I I think it's a hardware problem
I'm not entirely certain I'm sorry about
this um so what I was about to do then
was just record that patch and then I
was going to show you how you can use a
command called aend record what the
okay I'll give it a little bit of time
to
[Applause]
um yeah so what what I was going to show
you at that point was um editing a um
editing a patch that you've already
recorded to add add some extra changes
to it um and I'll I'll just do that next
just to um is there kind of longm to
extend yes um but that that's
particularly difficult so the problem
with the with extending it to know about
syntax trees is that you have
to um you have to fix your paa um you
have to decide that you know this this
one paa that that exists right now is
the one that's actually going to we're
going to um we're going to use to pause
the codee um so you know if if the
language changes a bit it become you you
end up having to version
things so that's probably a reasonable
way down the
line um
actually uh yes sorry but you you have
to keep you you still have to keep the
old one around so that you can read old
patches
so yes you can record new patches with a
new paer um but then you have to figure
out how you merge between the patches
that were recorded with the different
paers um and you have
to
[Music]
you kind of imagine you're creating your
P by recording MH and then you've got at
some point
patches yeah you
need no no yes you're ask you need to
have the paer at recording stage but you
do need to the kind of meaning of that
tra so the pretty printer you do need to
have everywhere you need to be able to
invert that you need to be able to
invert what you recorded to to actually
you know show the user what the real
Source would be if I really wanted
to
and literally just Tex so us it four
times it might L change treat that as
yeah so absolutely so so then and then
you won't get that nice that nice
behavior I showed you where it break
start yeah so it will f it will refuse
to it will refuse to let your cherry
pick around that then
um okay let me record this change as I
was trying to do not that one I
can't exactly
okay and I'm going to revert that other
change that I forgot to revert
before
um okay and now I'm going to make
another change to this
file um
just
okay I won't bother calling it that'll
do okay so now this time instead of
recording a separate change for this um
for that edit I've just made I want to
actually incorporate it into this other
patch because I think that the two
belong together for some reason I mean
in this case they don't really
but and so the command I can use for
that is dark amend record and that says
that will go that will go back and say
okay here's a here's a here's the patch
that you just recorded would you like to
change that um sorry I was going to do
that with a flag saying edit allow me to
edit the message as
well so should iend this patch um yes
and then here's here's the change that
I've just made to my repository and
shall I add this change to the patch
that you've already record that I've
already recorded yes um and also give me
a chance to edit the message so I
say
add okay um so that's you know that's
use if you're kind of working with draft
patches as you go um and then you start
you want to sort of keep adding changes
to them um and then eventually you're
done with it and then you say okay I'm
going to send this off to other people
and at that point you should stop
amending
iten
you so if you if you make a change P it
to the other repository then amend the
change and pull it again it will look
like a different change and it will be a
conflict yes so you then have to go man
un pulling the other
one okay um so okay let me just go back
to my slides for a
second
that work
yes okay so I've shown you quite I've
shown you a sort of bunch of the a bit
of the basic command set of darks and
just sort of what the what the sort of
model is um a new command that we're
adding to Dos in the in the next release
that will come out in probably the next
few months is a rebase command um and
rebas is a concept that exists um in in
systems like git and so forth and it
hasn't existed in darks before um and in
part that's because some many of the
things that you'd want to use rebase for
in git aren't really necessary in darks
um because you don't you don't you don't
have all these merge commits with darks
um that are about that you know you
where you want to um because whenever
you do a merge you always get the same
results so dark doesn't have to present
you with a merge commit um and you don't
need to use um rebase to do cherry
picking which is another thing that um
it's used when git but nonetheless there
are things where there are cases where
you do want to use you do want to do a
rebase you want to change
a whole sequence of patches in your
history so that they're maybe more up to
date or so forth so um we're adding a
rebase
command
um and so the basic so the way that the
rebase command works is it kind of puts
your repository into a temporary state
where you're doing some you're doing
some work on some patches and some other
patches have been sort of suspended um
and then you can bring those patches
back into your repository with an
unsuspend command so I'll just show you
that
now uh except for
that what
happened okay so I'm just going to um
I'm just going to throw away my that
change I just recorded and do the same
thing again um but with with a slight
twist to
it which I can
use
never mind about the typo um and I'm
going to make a second change on top of
that um which is that I want
to
I also want to write this to standard I
want this to go to standard error as
well so here's my second change which is
use standard error okay so now I want to
do that amend that I did before I want
to add that extra I'm going to put that
call to say we back
in and like to change that patch that I
wrote before the one where I where I
changed the message I want to CH I want
to insert this say we into that that
patch again so I don't want to edit the
standard error patch so I say no to that
um oh but then darks isn't going to let
me do um do that amend record on the um
on the update message patch which is
what I actually want to change um
because I've made a patch on top of that
that depends on that patch there's no
way that those two patches can be
logically untangled from each other
because darks is a line by line has made
a line by line diff and this the diff
for the standard error lives directly on
top of the diff where I change say to
wants to say um so I'm out of luck if I
want to amend it and that's where rebase
comes in so rebase will say okay well
this standard error patch is in the way
now let's let's push it out of the way
for a bit
um okay so that's that's disappeared
from our repository and it's now
suspended so if I just look at the
changes in the repository you can't see
it anymore um but darks will keep
reminding of the fact that it's still
around if you um and that you can get it
back okay so now I
can now I can amend this patch
um okay great um so done that now I want
my suspended patch back now how's dark
going to deal with that because well I
mean it's we haven't magically got
around the fact that the um that the
change the second change I made that to
insert standard error really does depend
on that first change I made sorry will
you wait no
um okay so well okay it's going to let
me unsuspend it it's going to offer it
to me we
are okay now that's I think there's a
bug in the development version I just
used because it should have told me that
it actually had a conflict um
huh oh right sorry now I got this demo a
bit wrong that's fine this is so this is
that that that bed was actually supposed
to happen and it was it was just not not
quite what I ended to do with the demo
um so what happened here was that I
didn't um I didn't when I when I changed
that patch I didn't change anything
about the line that was actually a
problem right so the con there should
have been if i' if I tried to do
anything to the output message text then
darks really would not have been able to
figure out how to bring that patch back
un suspend that patch into my repository
but because all I want all I did was
added say we to that change that was
fine that um it was able to do that now
because of some technical technicalities
to way the internals of darks works it
still has brought this patch back with a
different identity so it will actually
clash with other patches in other
repositories even though it's it looks
like exactly the same patch but now let
me just show you what would have
happened if i' done what I intended to
do there um okay so I'll suspend that
one again and this time I'm going to
edit HS to also say something different
here so
um can't make up my mind which editor I
want to use okay so I'd like to do that
instead okay and now I can I can change
this update message so that it's now now
a patch that does
this okay and now if I um if I unsuspend
this patch okay then it tells me that
that things have gone a bit wrong that
it can't quite it can't quite unsuspend
this patch and have it have it be a same
patch
locally and it's also um inserted some
conflict markers into my repository
which is dark's unique style of doing
conflicts um to tell me to to to give me
the local changes that have gone wrong s
go it just well it's I mean yeah it
marks up your repository like like most
systems would it um it lets you do the
operation but says there's a conflict
and here's and this is what the conflict
is in terms of
I the uh in this case is the fact which
complet be
your changes support mhm is still in
your
yes so the the original one that was the
cause of the conflict is still there I'm
fine and this one is in a slightly
conflicted state that I'm now going to
I'm now going to fix the conflict
and yes um okay so sorry um I haven't
shown you conflicts in the normal case
of merging and in that case it really is
another patch on top of it when you're
using rebase the normal thing to do is
to fix your conflict and then amend that
into the patch you just unsuspended so
um I won't bother doing it here because
it um I've I've already spent quite a
while in this demo that I didn't intend
to but um what's so what this conflict
is telling us is that well the first
line is the base of the conflict before
the equals so um that was the original
state and then there are two different
changes that are conflicting with each
other one of which is to insert the
standard error and the other of which is
to change wants to sat to would like to
say so our job is to you know see that
and do do the do the change for
ourselves and then then edit the patch
that we just unsuspended to to bring all
that um to bring that into
line okay
um let me go back to my talk I did that
bit of the demo um this is just a quick
slide just to show you that the main
sort of set of
command oh sorry wrong way around um
thank you that would be a
good yes in fact so another re another
place you wouldn't another way we thing
we could do that would mean you wouldn't
get a conflict there is if we did
patches to us to the characters of a
line rather than to rather than a line
by line thing and that's probably more
more in reach as
well okay so just just to give you a
very brief overview of the sets of
commands that you you can do with darks
um you know how they how they all fit
together so one interesting thing is the
sort of specific kinds of patch types up
here um so I already showed you replace
and add um and move um moving a file
around is also a kind of operation that
nicely with and merges nicely with other
patches um that you know also add files
and so forth um some standard remote
operations get in its mirror put pull
and push um obliterate which is to
remove a patch which used to be called
unpo and still has the
Alias um there is a staging area called
pending which we tried we we do our
absolute best to hide from you unlike
git um so pending is used for things
like in fact things like replace um so
something that can't be something that
really can't be represented in the
repository um then we put it in the
staging area so you know if we if you've
made that semantic statement that you're
making a change to your repository that
you you can't just infer that from the
files then we'll then we put that into
pending um otherwise it will be just in
otherwise you just record what's in your
working
directory it doesn't make sense
because the way how
you changes is actually uh so what when
you assembling your your story is
exactly what when you are just saying
this is record changes
yeah yeah I think I think that I think
that so the mixture of that and also the
fact that amend record is designed to be
fairly user friendly are two things that
make it I think unnecessary to have that
index have that equivalent
um okay and yeah there's some functions
for quering a repository you know just
but there's you know to for basic
operation with a darks reposit you don't
need to know um all that many commands I
hope I'm getting across with
that okay so um let's just go into um a
bit more technical detail about um
what's inside a dark's repository um so
dark's patches are semantic descriptions
of what should um what should happen to
the previous tree to give you the new
tree um so example of um an example of a
darks patch is remove the text X that
starts at line three in in a particular
file and put text Y in there
instead um another kind of dark patch
would be add file a or rename file C or
replace token x with token Y in a
particular
file um an important property of darks
Patches from the point of view of the
internals of darks is that the patches
are invertible um so any anything that
you can record um in darks darks has to
know how to undo it as well so that it
can kind of get back to the old tree um
that was before that um so for example
so it is actually important that you say
remove X from the patch at line three
you can't just say remove one line um
the internals of darks were actually
record the fact that the old version was
X it won't be able to use
what World card um that's correct yes
yeah um I mean that's not to I mean it
it can't but that's not totally I mean
if you if you had a linear regular
expression it would be possible it would
be technically possible we just have we
haven't done that and it would probably
be quite confusing but yeah as long as
long as you're sort of replace was was
invertible in some way you could you
could Implement
that um so yeah so that I mean I'm not
going to go into the details of why
that's important but it it is it is one
of the features of you know getting this
reversible cherry picking operation kind
of requires that you're you're able to
manipulate patches um in that kind of
way and inverting them is one of those
properties um I guess another Point
that's worth about how darks patches
work in general is in most Version
Control Systems you're kind of committed
to this this series of changes that you
made in a particular order whereas darks
lets you sort of pull out random random
changes from the middle if there's no
textual conflict um and that means that
of course you can write you can pull out
changes that really doesn't make sense
to pull out um because you know for
example if in one patch you add a
function and then in another patch you a
call site to that function and then you
try to cherry-pick the call site of that
function on its own darks will probably
let you do that if they weren't weren't
right next to each other um but you're
not going to have a meaningful
repository um but that's some power that
it gives you that you can you have you
have to decide how to use
it um yeah so I've already kind of
alluded to some of this stuff before so
and merges in dark are deterministic so
every single time every time you do
emerge anywhere with two darks patches
that were recorded at the same um that
the original darks patches then you'll
get exactly the same result and that
means that darks doesn't create merge
commits when you actually when you do a
merge okay so if you get a conflict then
you have to record a new patch to
resolve the conflict and then you've
kind of got an equivalent to merge
commit um but there is no explicit sort
of marker in darks in general for a
merge happened
here um
and merging is associative so say you've
got three repositories and you decide to
merge two of them together and then you
merge it with a third one um you will
always get the same result as if you
merged the second two as your first
operation and then merged it with the
third with the initial with the first
repository um so I mean that that's
that's I guess it's kind of part of the
intuitive user model that we're trying
to get with darks that you don't really
have to think about what audit what what
things happen you you just when with the
darks user interface it tries it tries
to make that implicit that that you can
expect that to happen without having to
think about it and it's it's kind of
important that that it actually is true
you don't get nasty surprises that
way
um okay so going a bit more into the
internals of What's um of of how this
all works
um
so on the left I've got the kind of sort
of diagram that represents what happens
when you have a merge operation so we've
got two different repositories with
patch a and Patch B in them that's the
difference between them and so the base
of the merg is um the bottom leftand
corner and in two different in the two
different repositories we're going to
end up with two different two different
states of the reposit
and the the point of a merge operation
in any version control system is to
figure out what should that question
mark be um and then do do the
appropriate thing with
that um and in darks what we would do
when we do that merge is that um
supposing we were pulling B into a
repository that already had a um we
would compute what that we would compute
this alternative version of b b Prime um
that is so kind of the same effect as B
but in a different context it's now
living after a and if depending on what
depending on what A and B were we might
actually have to change B into something
slightly different for that to still
make
sense
um so the dark has this internally has
this concept called commuting which is
changing the order of two patches um and
that's what I'm trying to get across
with this diagram is that that really is
just the inverse of the merge operation
so um with a merge you have two patches
that start at the same place and you
want to figure out what how you how you
combine them and but an alternative way
of looking at what the sort of work
involved here is that you have two
patches that are already in the same
repository in sequence and you want to
figure out how to unpick that you want
to get back to two patches that are
totally separate from each other um so
if you already know A and B Prime then
what's
B okay and that's that's the fundamental
part of cherry picking because once you
can do that um if you can swap the order
of patches then if we don't if we've got
a repository with A and B Prime and we
don't want a we just want B Prime then
what we have to do is commute A and B
Prime to turn them into B and a prime
and then we can throw away a prime and
we've got a repository just has to
change B in it um and when we do the
merge again um because of all the stuff
that darks does behind the scenes it's
going to give you exactly the same
result B primed again so that's that's
why what I showed you um that's that's
kind of a flavor of what's behind what I
showed you it's not um there could be
many be
a there could be many so um in in the
merge diagram there have or in any of
these diagrams there has to be unique
darks that's one of the things darks
ensures so if you given a prime you
multiple ways of
facturing yes but they you have to um as
darks will to if you adding a new patch
type to darks that would define what
this commu would be you'd have to do it
in such a way way that um it would go
back to B Prim when you merged it again
so otherwise you'd break darks um
so
I
[Music]
a
will B Prime uh B primee yeah so it will
store them in a particular in the
particular order that's useful for that
working that repository per repository
yes
exactly okay so yeah this actually goes
into so I mean conceptually you can
think of a dark repository as being a
set of patches in most cases right so
the the set of patches you got in your
repository no matter what order you
brought them in in the end state of your
repository will be the same um but they
are they are actually stored in a
particular order that reflects how you
got them um and you know when you run
things like darks changes as as we
showed you that um that does show
up um there it's rare I mean I think it
there is a user demand for that kind of
thing because you know you want use
quite often want to see what's what the
changes in your repository are that it
isn't in a remote repository and it' be
useful to reorder the patches in your
repository so that just your local
patches are at the end of the repository
um so and we don't have a great command
set for doing that we do have one
command that lets you do that does some
of that for you um but it's
not uh that would be Overkill because it
would change the identity of your
patches so you you really wouldn't want
to use rebase for that and there's a
command called darks optimize reorder
which will do that up to the last tag in
the repository but it's not it's not
sort of General
um yeah so there's this um there's this
distinction in in darks in terms of well
I guess in terms of both the mental
model and in terms of the internals that
patches have an identity which is the
thing that you know they they retain
that as you pull them around between
repositories but as we saw the
representation of a patch can change as
you pull it around um and that you know
due to either merging or cherry pitting
depending on which way around you um how
you're pulling it
around
um so I mean there is this kind of
there's there's this kind of theory kind
of hiding at the uh hiding inside darks
and hiding very well because no none of
the people who really work work on darks
have managed to make a really formal
theory behind um behind what's happening
with these patches and it's that's a
real shame because it ought to be um it
ought to be possible to do um just
nobody's Managed IT um but we kind of I
mean I was sort of alluding to various
things that you have to get right
otherwise you'll otherwise you'll screw
up the behavior of darks and we kind of
intuitively know that the these things
have to behave this way and you know
there so there are some laws that we
believe are true about um all the dark
patch types that we have and that would
be true about any new ones that we added
so an important one for example is that
if you commute two patches if you if you
had a and you swap them around if you
swap them back again you're going to get
back to the same
result um so just the equivalent of
these two commutes um and also that if
you um if you kind of if you invert
patches and start commuting the inverses
then you get the same result as if you
were as if you left them uninverted to
begin with um I just put that up I don't
want to explain that that in
detail um another thing I'm used quite a
bit of time so I'm just going to go over
this very quickly is the um there's this
I said that merges have to be
associative um and the thing that
underlies that in terms of what your
patches have to do is that um if you
start commuting patches around so say
you have your patches in the order a b c
to begin with and then you start
changing some of those patches around um
and you keep doing that you can you kind
of tra you're kind of following a path
around this Cube if um picture and um
there's no absolute guarantee from any
sort of external source that you'll
actually get back to exactly the same
results when you've got to the end of
that because the commutes that you've
done in each case are are independent of
each other um but that's another law
that we expect to be true that you will
get back to the same result um and if
you look at think of that Cube as a kind
of merge that's about guaranteeing that
you will that you know that top right
hand corner of that Cube will always be
the same no matter what merges you
[Applause]
did um okay so I'll finish up um fairly
briefly by talking a little bit about
the internals of darks and one one
particular way we've used um H or to
good effect in the
internals um so one of the things that's
sort of I hope of what I've already said
about darks is that when you when the
code of darks is working with patches
it's going to do a lot of time it's
going to be moving patches around
between different contexts a lot it's
going to be um deciding that okay this
patch um this
patch have these patches before to now I
need to cherry pick commute it or merge
it and so that it's got some other
patches um leading up to that
patch um and a lot of the time when you
do that the representation of patch
doesn't change because you know for for
example if two P if you've got two
patches to two different files the order
in which they're in makes no difference
their representation but you've got two
patches to the same file the order in
which they're in you'll have to change
the line numbers of in the offsets of
the second the patch that's further down
the file um so it's it's quite easy to
get this um to firstly get start using
patches in the wrong context in darks
code in in the dark source and if you do
that you might not notice quickly
because a lot lot of the things you're
testing with won't actually have won't
actually trigger that um trigger this
being a
problem um so here's an example of um of
how you might actually um of some some
code you might want to write inside
darks um so supposing that we've
supposing we want to commute two patches
we've got um the patch C and we've got
the sort of sequential composition of
two other patches A and B that's the
intention of this bracketing so I want I
want to get to sort of C primed and then
a prime as the or a prime B Prime is the
alternative okay so if if we take an
imaginary patch type which is um either
a um a null patch or nothing or sort of
two patches stuck together and then
obviously there' be some more
Constructors for the real um for real
patch kinds in that um you might write a
functional commute that's um going to
have a case that's for about commuting
commuting this um a as one group with c
as the other group okay so how you going
to do I mean typical hasal you're going
to do this kind of operation by
decomposing it into its sub pieces um
commute you know commute one of these
two things with the other with the next
one and then um and then commute um
commute the results to get it all into
the right order um so that's that's one
reasonably plausible way of writing it
that happens to be totally wrong
um because what you should do is I mean
if you just look at the order of this it
makes sense to commute B and C
first um and then commute the result
you'll get um you'll get ACB and then
you commute the result A and C yeah this
order but what what I'm doing here is
I'm commuting a andc first and a andc
aren't next to each other originally so
it really doesn't make sense to do that
um but there's nothing in this code
that's going to stop me from doing
that um because dark doesn't GHC doesn't
know anything about the context of these
patches so um one thing we introduced in
darks quite some time ago now is um a
way of actually telling GHC at least to
some extent these are the this is the
context of a patch um don't um don't let
me screw up so instead of defining just
patches as being um so the these um so
what I've done is I've introduced a
couple of type variables here and these
type variables are Phantom types right
they don't have any reflection in
reality in terms of the ACT you know I
could even I it doesn't make sense for
me to say patch in Char or something
like that that's that's not what they're
about um they're about saying they're
about a sort of abstract representation
of the context that that patch lives in
and and it means that if I write some
certain low-level operations carefully
um and don't screw up the context in the
lowlevel operations then the high level
operations that I build on top of those
um I won't be able to um the type
Checker will actually stop me from
getting it wrong so the the key point of
this really is that this sequential
composition operator now operation now
um says the context must match up so a
patch AB is a patch that notionally goes
from an initial starting point initial
context a to a final context B okay so
the sequential composition of two
patches now goes from an initial context
a via an intermediate context B um so
the um to a final context C so the the
sequential composition is a patch from a
to c and it's made up of two indivi
independent individual patches that um
start at a and finish at B and start at
B and finish at
c um and so to actually to actually work
with this kind of stuff you you find
yourself having to redefine a whole load
of basic type so what used to be just a
tle um I've now had to make a witness a
tle with these extra witness types in it
um that says okay this this is a sequen
this is a pair of patches that I'm going
to want to commute um for the to be able
to write the type of commute so commute
is now talking about the fact that we've
got a pair of patches that goes from a
to c in total and I want another pair of
patches that goes from a to c in total
but is in the opposite order
internally so I can I can translate that
that incorrect code I wrote in the
previous slide into incorrect code using
the um using these Phantom types and GHC
will complain um now the downside of
using these Witnesses is that the GHC
complaint takes a little bit of getting
used
to um
so what with you know so with some
practice you kind of get used to
understanding what it's trying to tell
you here which is that well um there was
some other variable B1 that would have
had to existed for this to make sense
but it it doesn't really work um and
um and in particular really you know you
can see that this expected versus actual
B1 is different from B so you know that
you've got the intermediate context of
this this commute wrong but it certainly
makes um the darks code harder to get
into for newbies it also stops newbies
screwing up the darks code so um that's
that's a sort of two-edged
sword um yeah so that's um and these
contexts can't do everything you do have
to get the lowlevel operations right for
for the sort of stuff around it to make
sense and they don't um in some cases
you actually have to insert a assertions
that say I've thought about this I can't
convince the type Checker that this is
correct but I've thought about it and it
is it is correct and trust me please
um okay so that was just a sort of um
brief overview of all of that um stuff
so what are we going to do with darks
next um well 210 which is the upcoming
release we'll have rebase in it rebase
in it and it will also have a fast rer
take command if you've used dos before
you'd know that the dark annotate
command is one of the things that really
is very slow um and what we've done to
make that a lot better is introduced a
um what's called a patch index a look up
from the
um look up from lines of lines in a file
to what patches touch the line that line
in the file so you can um s Dart can
very quickly find out what patches are
um what patches affected a specific
file yes annotate is yeah
exactly
so what's
the you have V on the same
and yeah so annotate will give you a
different output depending on what order
those patches are in your repository
depends yes yeah so there there are
there are plenty of commands that will
depend on that and changes you know just
the list of changes the annotate um the
way that patches are presented to you
interactively all those things will be
different depending on the order of your
patches um yep so we're um we're
developing a um a bridge to get but it's
not really ready for prime time yet so
we want to um want to get that ready um
we don't have a great hosting story
though we do have um we do have a kind
of on um a standard host for darks
repositories that you can put online and
so forth but it's nowhere near as fully
featured as GitHub so we'd like to
improve that um we'd like to have better
most of interacting with darks is very
text based in fact all of it I mean the
darks command line is just a text tool
there are no standard graphical tools
for it um what we'd like to do is make
something web based that's um kind of
you know the the same the same code base
as the hosting um code that we have just
bring up a web browser locally and allow
you to interact with your repository
like that um but that's still in
progress um we'd love to have multi-head
repositories a bit of implementation
effort um conflict handling is a mess
for a couple of different reasons but
one of which is that we don't actually
have a good algorithm for figuring out
deeply nested conflicts and dealing
making them making them behave properly
and um we hope to improve that in the
future um more patch types that's I mean
that that's kind of the point of darks
right I mean what darks lets you do at
the moment is quite is nice useful and
it's still I I still personally find it
a lot more useable than get but really
we could we could make darks really nice
to use in terms of um you know by having
by having more patch types that let you
do things like moving around chunks of
text from one place to another um make
you know do indent a block of indent a
whole set of lines um by a certain
amount and have those things merge
nicely with other kinds of patches where
that makes
sense
that new is deping on the number of you
already have
so yes that's well it's not it's not
quite that bad because there are some
kinds of patches types that would never
that would never make sense to merge
with each other so for example if you
had a semantic patch that would you know
about um ch um treating a source file as
a pastry and doing stuff with that then
insert a patch that inserts lines in the
middle of that file is never going to
merge with that sensibly I think it we
just say that's a conflict um so you
you're kind of and the the other thing
is that um merging so you know files
that affect the internal contents of a
sorry patches that affect the internal
contents of a file are independent of
patches that say move around the things
in the file system and so on so the yes
you're right basically that that
quadratic explosion does happen will
happen but um there are some mitigating
factors and that but that's part of why
it's difficult to add new patch
types okay so um that was all I had to
say really um if you want to know more
about dos it's got a homepage and it's
got a hosting place um and we are um if
any of you students and interested in
doing some stuff for darks then we are
participating in G in some of code via
um h.org so please apply
[Applause]
um probably four or five some that sort
of um to move to syntax trees other than
um the complexity of the compiler how
conceptually how hard is
that um I don't know how to merge what
what the merge operations on what the
sort of basic patch types for two trees
would be so let's let's say that we've
paused a we've paused a sour file and
we've got a tree and we want to we need
to Define changes to that tree um and
it's not completely obvious to me how
you what those changes should be what
the actual patch Types on trees would be
um so I think that would and then and
given that it's not obvious you're also
going to need to have a good degree of
certainty that you actually that it's
all correct in all cases and so forth so
um probably probably want to bring in a
theor approver or something like that to
um to check it out that's quite hard
some
work
your demo on a single file
is so there are patch types that affect
an entire directory at a time so you can
you know rename a directory and all the
files within that will move and that
will merge and commute nicely with say
adding a new file to that directory on
an independent
Branch two files but if you edited two
files that's two separate patch well I
mean you can stick them together into
the same you know patch with name um you
wouldn't you wouldn't record them as
separate you wouldn't have to record
them as separate patches if I you know
if you if you make a change across your
sourc tree you can the interactive
record will ask you about all those
changes to all the files at once and you
can select some of them to be stuck
together into one patch I said
yes yes and then that will be an atomic
change set that will you know just kind
of BR to the next question which
is
small
um I think it varies quite a bit but um
you know varying from the quick typo fix
and so on which is worth recording as a
separate patch to you know maybe a few
hours work um
or yeah no you would so I
mean so the dark repository itself has
um about 10,000 changes in it and so
well
you know here here's a here's a very
simple one that I made that was just um
fixing a test
um this one looks quite a bit bigger um
that was you know not sure exactly what
it was about but um so you know it's you
you want to group together logically
work that belongs together logically
because otherwise there's not much point
in having Atomic change sets um you you
know you you want to stop being you want
to stop people cherry picking too much
as well you you want to encourage them
to cherry pick things that make sense
and not things that
are yes that's right
yeah how to um how complex is it to do
the transformation
for um not very um it's it's basically a
set of rules for so the the most
interesting cases come in for example
when you're um if you're say merging or
commuting two two hunk patches to you
know individual line changes to the same
file and then you have to make sure that
they it's safe to do it and that you
have to adjust the offsets appropriately
um similarly if you're doing that with
file renames and so forth you need to
make sure that you change the patches
that touch that file um but the the code
for doing that in itself is probably a
few a few pages um you know 00 that sort
of scale
thank you than
you