Issue IDs

(Another way to see whether a branch has been merged would be to look at the code and check the changes in the other branch are present in yours. This is what people sometimes had to resort to in older version control systems without change tracking, or which were not distributed, or indeed if they had no VCS at all. Both approaches have their advantages, but often we prefer the cleaner one based on explicitly tracking commit history.)

Now moving from whole branches to individual changes. You could try to work out whether a cherry-pick has been applied by looking at the current state of the code, or going back over the branch history to see if a similar-looking diff has been applied in the past. But as you say that falls down if there were conflicts or for other reasons the patch wasn’t applied exactly.

Instead, I suggest a metadata-based approach where you can create a “disembodied commit” which has a patch to apply but no ancestor commits. Merging this commit into your branch is usually simpler than merging a whole other branch, which may have unrelated changes (unless your programmers are very disciplined about always creating “daggy fixes” where the commit fixing a bug is an immediate child of the one that introduced it). Indeed merging this disembodied commit is the same as cherry-picking it, as far as the code goes. But unlike cherry-picking, the disembodied commit keeps the same SHA, and is now an ancestor of your branch. That would make it easy to ask “has this fix been applied?” without having to match the file contents, and even when the fix is only given as a text diff against some slightly different version of the codebase.

The SHA of the disembodied commit could be the hash of the original set of changes (or textual diff) but that same SHA would still be used even if you had to resolve conflicts on merging. Again, just as happens for regular branches and regular merges.

Edge cases:

* If a commit has yet to make it into the central repo, then it has no ID, or perhaps only an unstable ID that might change or become invalid in the future. This does not matter, because these commits are considered "unfinished" and should not be used for any serious purpose (other than asking people to review them so that they can become final).
* Once a commit is in the central repo, history rewrites are forbidden (allowing for a few exceptional cases when some sensitive item gets improperly committed). The need to support that exceptional use case is one of the stronger arguments for using a non-DVCS system (which can simply assign numeric commit IDs by fiat rather than having to do this whole Merkle tree business, so you can rewrite history without changing subsequent IDs).
* When something is cherry picked, there is some notion of a "primary" or "original" commit, which will at the very least be mentioned in the commit message of the cherry pick. Good tooling can use this to resolve the original commit when given a cherry pick ID (not every org has good tooling).
* Linear history is usually enforced. When a commit becomes final, it is rebased on top of the intended branch. For some systems like Perforce, this is usually a trivial operation (Perforce's data model is that each individual file is a series of snapshots with associated numeric commit IDs, so all history is inherently linear, and "rebasing" just means "check to make sure that nobody else has edited any of the same files as us").

Obviously this would not work very well for Linux's use case, but it is the sort of thing that the MITRE people were probably expecting when they set some of these rules around stable IDs.

Of course, such a string without context is not very useful so we should prefix it with something, perhaps the capital letter I. That would make it easily recognisable and searchable.

Finally, it should not be bare, but it could be added to the commit message under Change-ID or some such.

Oops, now it looks like Gerrit changelog ID and we couldn't possibly do that...

All this talk of diff algorithms and automatic patch matching, the amount of cycles and discussion going in this, all to solve a problem that is trivially solved with a git hook. I don't understand it at all.

We can replace the I with a K and call it Kernel-Change-Id, maybe then people would accept it?