From: Phillip Wood Date: Tue, 03 Nov 2026 16:38:03 GMT Subject: Re: Strange word diff Message-ID: <9fb1cf95-1cfb-4bc9-a722-e98d0a0664df@gmail.com> In-Reply-To: <4dd76eef8a2a355ba435e8c784c1e37f3fe47074.camel@abou-samra.fr> Hi Jean On 03/11/2026 14:14, Jean Abou Samra wrote: > Hi, > > Attached is an archive with three files. file2.txt differs from file1.txt > by just a few words, as correctly reported by git diff --word-diff (using > Git 2.56.0): > > Is this a bug? It happens with all --diff-algorithm option values. Yes and No! I think the diff is correct, but it is also pretty useless if one is interested in seeing the word-level changes. The problem is due to the way git calculates word diffs. To calculate the word diff, git first calculates the line by line diff which looks like diff --git a/file1.txt b/file3.txt index a9eaedc..81c3eb9 100644 --- a/file1.txt +++ b/file3.txt @@ -1,4 +1,5 @@ \subparagraph*{Context} -Our object of study is an extension of Turing degrees ... -While this game was introduced recently by Kihara +Our object of study is an extension of Turing degrees ... + +While Arthur–Nimue–Merlin games were introduced recently by Kihara... then, it splits the line diff whenever it sees a context line and diffs the words in the '-' and '+' lines it has seen up to that point. As git has chosen the first blank line as a context line, it looks like the entire first paragraph has been deleted which messes up the word diff. We had a similar report a few months ago. I think the solution is to feed whole hunks from the line diff into the word diff instead of splitting the hunk when we see a context line. As an aside my local git installation uses a modified implementation of the patience algorithm that removes the fallback to the Myers diff when it cannot find any context lines[1]. That algorithm cannot find any context lines in this example and so gives a sensible word-diff. Thanks Phillip [1] https://github.com/phillipwood/git/commit/7eda9d836c8db76ad49b6cc8b5760ff458d81e9c > ``` > $ git diff --no-index --word-diff file1.txt file2.txt > diff --git a/file1.txt b/file2.txt > index a9eaedc..a75008e 100644 > --- a/file1.txt > +++ b/file2.txt > @@ -1,4 +1,4 @@ > \subparagraph*{Context} > Our object of study is an extension of Turing degrees where the oracles can > feature certain forms of non-determinism, as in this riddle. We call these > generalized degrees the \emph{Arthur–Nimue–Merlin degrees}, owing to their > explicit description by Kihara using a three-player game whose players are > conventionally named Arthur, Nimue and > Merlin \cite{KiharaLT}.\footnote{In \cite{KiharaOracles}, Kihara uses the term > “extended Turing–Weihrauch degrees”. We prefer to eschew the association with > Weihrauch's name since we never deal with [-call-once oracles.}-]{+oracles that > can only be queried once.}+} Whereas Turing degrees are defined as a quotient of > oracles which are functions $\N \to \N$, Arthur–Nimue–Merlin degrees are a > quotient of a richer set of oracles, namely functions $\N \to \P(\P(\N))$. > Informally, when a program that uses $g : \N \to \P(\P(\N))$ as an oracle makes > a query $n \in \N$ to the oracle, a set $P \in g(n)$ is chosen in a benevolent > way (“angelic non-determinism”), then a value $v \in P$ is chosen in an > adversarial way (“demonic non-determinism”), and the program receives the answer > $v$. The mathematical meaning to “benevolent” and “adversarial” is made precise > by introducing a game where Arthur, a player restricted to computable > strategies, is allied to Nimue, the player choosing $P$, and both play against > Merlin, the player choosing $v$. (The details of the game are recalled in > \autoref{section-arthur-nimue-merlin-games}.) > > While [-this game was-]{+Arthur–Nimue–Merlin games were+} introduced recently by > Kihara, [-the concept-]{+they are a concrete description+} of [- > Arthur–Nimue–Merlin degrees is-]{+objects that arose+} much [-older, having > arised,-]{+earlier,+} in a different guise, in the study of realizability. To > reassure the reader unfamiliar with realizability from the outset, this paper is > meant to be accessible with only a background in basic computability theory, > except for \autoref{section-topos-theory} where we explain how the proof of our > main result can be understood from the point of view of realizability. > Nevertheless, let us recall the historical link. > ``` > > The only change between file2.txt and file3.txt is the addition of a > blank line: > > ``` > $ git diff --no-index file2.txt file3.txt > diff --git a/file2.txt b/file3.txt > index a75008e..81c3eb9 100644 > --- a/file2.txt > +++ b/file3.txt > @@ -1,4 +1,5 @@ > \subparagraph*{Context} > + > Our object of study is an extension of Turing degrees where the oracles can > feature certain forms of non-determinism, as in this riddle. We call these > generalized degrees the \emph{Arthur–Nimue–Merlin degrees}, owing to their > explicit description by Kihara using a three-player game whose players are > conventionally named Arthur, Nimue and > Merlin \cite{KiharaLT}.\footnote{In \cite{KiharaOracles}, Kihara uses the term > “extended Turing–Weihrauch degrees”. We prefer to eschew the association with > Weihrauch's name since we never deal with oracles that can only be queried > once.} Whereas Turing degrees are defined as a quotient of oracles which are > functions $\N \to \N$, Arthur–Nimue–Merlin degrees are a quotient of a richer > set of oracles, namely functions $\N \to \P(\P(\N))$. Informally, when a program > that uses $g : \N \to \P(\P(\N))$ as an oracle makes a query $n \in \N$ to the > oracle, a set $P \in g(n)$ is chosen in a benevolent way (“angelic non- > determinism”), then a value $v \in P$ is chosen in an adversarial way (“demonic > non-determinism”), and the program receives the answer $v$. The mathematical > meaning to “benevolent” and “adversarial” is made precise by introducing a game > where Arthur, a player restricted to computable strategies, is allied to Nimue, > the player choosing $P$, and both play against Merlin, the player choosing $v$. > (The details of the game are recalled in \autoref{section-arthur-nimue-merlin- > games}.) > > While Arthur–Nimue–Merlin games were introduced recently by Kihara, they are a > concrete description of objects that arose much earlier, in a different guise, > in the study of realizability. To reassure the reader unfamiliar with > realizability from the outset, this paper is meant to be accessible with only a > background in basic computability theory, except for \autoref{section-topos- > theory} where we explain how the proof of our main result can be understood from > the point of view of realizability. Nevertheless, let us recall the historical > link. > ``` > > And yet, comparing file1.txt with file3.txt with a word diff gives a strange > diff that matches a few words here and there while missing unchanged entire > long sentences: > > ``` > $ git diff --no-index --word-diff file1.txt file3.txt > diff --git a/file1.txt b/file3.txt > index a9eaedc..81c3eb9 100644 > --- a/file1.txt > +++ b/file3.txt > @@ -1,4 +1,5 @@ > \subparagraph*{Context} > [-Our object of study is an extension of Turing degrees where the oracles can > feature certain forms of non-determinism, as in this riddle. We call these > generalized degrees the \emph{Arthur–Nimue–Merlin degrees}, owing to their > explicit description by Kihara using a three-player game whose players are > conventionally named Arthur, Nimue and > Merlin \cite{KiharaLT}.\footnote{In \cite{KiharaOracles}, Kihara uses the term > “extended Turing–Weihrauch degrees”. We prefer to eschew the association with > Weihrauch's name since we never deal with call-once oracles.} Whereas Turing > degrees are defined as a quotient of oracles which are functions $\N \to \N$, > Arthur–Nimue–Merlin degrees are a quotient of a richer set of oracles, namely > functions $\N \to \P(\P(\N))$. Informally, when a program that uses $g : \N \to > \P(\P(\N))$ as an oracle makes a query $n \in \N$ to the oracle, a set $P \in > g(n)$ is chosen in a benevolent way (“angelic non-determinism”), then a value $v > \in P$ is chosen in an adversarial way (“demonic non-determinism”), and the > program receives the answer $v$. The mathematical meaning to “benevolent” and > “adversarial” is made precise by introducing a game where Arthur, a player > restricted to computable strategies, is allied to Nimue, the player choosing > $P$, and both play against Merlin, the player choosing $v$. (The details of the > game are recalled in \autoref{section-arthur-nimue-merlin-games}.)-] > > [-While-]{+Our object of study is an extension of Turing degrees where the > oracles can feature certain forms of non-determinism, as in+} this [-game was > introduced recently-]{+riddle. We call these generalized degrees the > \emph{Arthur–Nimue–Merlin degrees}, owing to their explicit description+} by [- > Kihara,-]{+Kihara using a three-player game whose players are conventionally > named Arthur, Nimue and > Merlin \cite{KiharaLT}.\footnote{In \cite{KiharaOracles}, Kihara uses+} the [- > concept-]{+term “extended Turing–Weihrauch degrees”. We prefer to eschew the > association with Weihrauch's name since we never deal with oracles that can only > be queried once.} Whereas Turing degrees are defined as a quotient+} of > {+oracles which are functions $\N \to \N$,+} Arthur–Nimue–Merlin degrees {+are a > quotient of a richer set of oracles, namely functions $\N \to \P(\P(\N))$. > Informally, when a program that uses $g : \N \to \P(\P(\N))$ as an oracle makes > a query $n \in \N$ to the oracle, a set $P \in g(n)$ is chosen in a benevolent > way (“angelic non-determinism”), then a value $v \in P$ is chosen in an > adversarial way (“demonic non-determinism”), and the program receives the answer > $v$. The mathematical meaning to “benevolent” and “adversarial”+} is {+made > precise by introducing a game where Arthur, a player restricted to computable > strategies, is allied to Nimue, the player choosing $P$, and both play against > Merlin, the player choosing $v$. (The details of the game are recalled in > \autoref{section-arthur-nimue-merlin-games}.)+} > > {+While Arthur–Nimue–Merlin games were introduced recently by Kihara, they are a > concrete description of objects that arose+} much [-older, having arised,- > ]{+earlier,+} in a different guise, in the study of realizability. To reassure > the reader unfamiliar with realizability from the outset, this paper is meant to > be accessible with only a background in basic computability theory, except for > \autoref{section-topos-theory} where we explain how the proof of our main result > can be understood from the point of view of realizability. Nevertheless, let us > recall the historical link. > ``` > > > Best, > Jean