Strange word diff

Strange word diff

[Jean Abou Samra]

[-- Attachment #1.1: Type: text/plain, Size: 9067 bytes --]

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):

```
$ 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.
```

Is this a bug? It happens with all --diff-algorithm option values.

Best,
Jean

[-- Attachment #1.2: git-word-diff.tar --]
[-- Type: application/x-tar, Size: 10240 bytes --]

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 228 bytes --]

Re: Strange word diff

[Phillip Wood]

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