Git : detecting only missing parts, not those who have just moved

Viewed 43

I'm editing a markdown file, I'm using for learning.
It has the content:

AB
CDE
EFG
IJK
LM

At a time, I was unhappy with my understandings and redistributed my paragraphs and text differently to change the plan

CDE
AB
EG
LM

After having done that, I'm fearing: with all these cut-paste, didn't I lose some text?

Is there a way to make Git compare files, but ask it not to report moved blocks?
Displaying only blocks added to or deleted from somewhere
without being deleted from or added to somewhere else.

I'm searching options in the Git command that would:

  • detect that the line IJK is entirely missing,
    (ideally, detect that the F part is now missing in the line EFG)
  • but wouldn't report that AB and CDE have moved.
2 Answers

By committing the changes, Git will save a new version of the changed file not only changing data. to be concise git stores snapshots, not differences. (read this for more information)

When an application wants to create a diff log, based on the history of git, it will compare these two versions and create a display.

So how does an application display difference between two commits, it totally depends on the application and has nothing to do with how the git saves the data.

Git itself, internally, uses an algorithm1 in which each original line of text is turned into a single "symbol". You can think of these as roughly similar to using a symbol for an entire word, such as replacing the word "clock" with an emoji: . If you had three "clock" lines, they'd all become symbols.

Having done this substitution, the difference engine now compares the sequence of symbols. For instance, the "before" sequence might be and the "after" sequence might be . The symbols either match up, or they don't. If they don't match up, the diff engine searches for a minimum-length instruction sequence that consists of "delete" and "insert" instructions. In this case there's one obvious minimal sequence, which says "delete second clock, insert bell after first clock".

Note that there are no move instructions. In the algorithm Git uses, the only instructions are "delete" and "insert".2

Having found this sequence, Git now re-expands each line from its symbol to the original text. We still have the instructions, plus the line text for each line. This text can now be fed to various post-processing engines.

The default, in the old days, was to do very little in the way of post-processing. All you got was the + for inserted lines and the - for deleted lines, with one column taken up on the left for these characters, and the remaining text pushed one column rightwards. Optionally, you could have the - lines colored red and the + ones green.

This doesn't work well for non-line-oriented text, so git diff added "word diff" mode, where—having found these line-oriented changes—a post-processor would compare the words within the changed lines, and print them with {+...+} and [-...-] around inserted or deleted words. There's a flaw here in that a word might in effect span lines. The post-processor doesn't really handle these cases correctly. It can't, because the input is "lines".

People didn't think this was fancy enough so there are now many post-processors, some of which try to match up - lines with + lines and claim that these are "moved blocks of code". Feel free to write your own post-processor, and note that if you do write your own, you'll want to have git diff output the simplest possible text, preferably without the red-green (and/or other colors) color escape sequences that are annoying to parse out. To make sure you get predictable, machine-oriented text as output, do not run git diff. Run git diff-tree instead, or git diff-index or git diff-files for the cases where git diff would use those.

Your particular post-processor might look for "delete" sequences that have matching "insert" sequences and cancel these out. You could also discard any "insert" that doesn't cancel out an existing "delete", leaving only the unmatched "delete"s.


1Actually, it can use one of four, but they're all driven the same way here so the result is mostly the same.

2Other diff algorithms use a "change" instruction to represent delete-and-then-immediately-insert, but there's no need for a third instruction and having more instruction types just makes things harder for most post-processors anyway.


You have another option

In some cases, it might be easier not to post-process a textual diff, but rather to generate your own diff, using whatever algorithm you like. For instance, Python's difflib might be useful to you. To do this, instead of using git diff-tree to compare two trees,3 or one selected file in two trees, you would simply use git rev-parse to find the hash IDs of those files:

git rev-parse HEAD~:path/to/file
git rev-parse HEAD:path/to/file

and then have Git extract those files by their hash IDs:

git cat-file -p <hash1>

and:

git cat-file -p <hash2>

You now have the entire text of each file, and can run this text through your own algorithm. If you make your algorithm word oriented, rather than line oriented, that may work better for text input. Note that markdown is a little tricky though: it's partly reflowed or reflowable text, yet partly lines (a "line" of equals signs or dashes has a special meaning which can only be determined by examining the input as lines, for instance). So a two-pass algorithm that handles the mark-up/down and the text separately, might be appropriate here.

I illustrated the example above via hash IDs on purpose. You can write:

git cat-file -p HEAD~:path/to/file

to get that version of the given file from that commit, but if you use git rev-parse to find the hash ID of the file, you can get the same important short-cut that Git gets: if two hash IDs match, the file contents match byte-for-byte, and no diff-ing is required. Note, however, that the hash IDs work only with committed or staged files (which have hash IDs), not with working tree copies (which don't).


3A tree here means, roughly, the saved snapshot of some commit. Git stores each saved snapshot as an internal tree object, which is why the documentation uses the word "tree-ish" so often.

Related