Re: git pull fails with merge conflicts. How can this possibly happen?

[David Kastrup]

"Stephen J. Turnbull" <address@hidden> writes:

> This "confusion" I still don't get.  Git semantics are singly-linked
> list semantics: commit ~ cons (object), tree ~ array of tree-or-blob,
> blob ~ atom, ref ~ list-valued symbol, branch = ref where the commit
> command has push (cl-macro) semantics, tag = ref where the commit
> command has cons (primitive function) semantics.  Everything else
> follows from list-traversing semantics, rather than the array
> reference semantics that svn and bzr provide with refnos.  Only merges
> ("cons with multiple parents") fail to follow the pattern, but I've
> never heard anyone complain that merges are particularly hard to
> understand.[1]
>
> What's so hard about list semantics for an Emacs developer?

A list is a high-level concept.  This high-level concept as a sequence
of items does not result in semantics like the support of shared tails.
Indeed, only singly-forward-linked lists with individually
reference-managed list members support these particular semantics
seamlessly: they are not "list semantics" but are emergent semantics
from a very particular set of list implementations.

The Git reference system can be described in terms of non-circular
versions of LISP lists.  But in reality we are not talking about "list
semantics" here.  What you call "list semantics" are "finite directed
graph" semantics, and Git uses the subset of "finite directed acyclical
graph" semantics.

That LISP uses directed acyclical graphs for representing finite lists
is an implementation detail, not a high-level description of what lists
are, namely a sequence of items.  And LISP lists are a subset, since
they are either a _finite_ or a terminally cyclical sequence of items.
LISP cannot represent things like the list of natural numbers.

So LISP's _implementation_ of lists can be mapped somewhat comfortably
to Git's use of finite directed acyclical graphs.  That's an
isomorphism.  Which is nice if you want to map a Git repository to Emacs
data structures.

It does not mean that Git uses "list semantics", however.  Nor does it
mean that Git's behavior can well be described or even implemented in
terms of _lists_ rather than of a particularly organized tree of conses.

Try, for example, describing the structure of a Git repository in terms
of a C++ STL list type rather than of LISP "lists".  Doesn't work.

The talk about "list semantics" is a red herring even though any
traversal along the edges of a finite directed acyclical graph ends up
being a list.

-- 
David Kastrup