I have a git repo with quite some history by now. I was trying to do some changes on early commits and found weird conflicts.
I found out that if I do a git rebase COMMIT^ and choose one of the early ones, but then on the list I don't touch anything, like pick all commits, it still goes through the motions, replays all commits, and unexplainable to me, fails on some.
How is this possible? If the history is not altered because all the commits are picked, how can it be failing?
A rebase works by "playing back" the changes in each diff, making new commits (leaving the old ones intact, but hidden, and subject to eventual expiration). The method by which a commit is "played back" is available more directly as git cherry-pick, so I'll describe this first.
Doing a cherry-pick involves extracting the changes made in a commit. The resulting diff can then be applied to ("patched into") some other (different) commit, by using the context included in the diff. But, because a commit is not stored as changes—each commit is a complete "snapshot" of the source—a cherry-pick has to compute the changes provided by a commit. It does so by comparing the commit to its parent commit.
This works fine for linear history, but not so well when there are merges. In particular a merge commit has, by definition, at least two parents (merges with more than two parents are unusual but git allows them). Given a commit with two parents, and no obvious way to choose which parent to consider when making a diff, git cherry-pick simply halts with a complaint. It makes you provide, with the -m option, the parent you care about when cherry-picking a merge commit.
The rebase command takes a different approach: by default, it eliminates merges entirely, hoping that they were not necessary. If the merges matter (as apparently they do here) this will result in failing cherry-picks.
The rebase command does have a -p (aka --preserve-merges) option. In this case, it attempts to keep the merges. In this particular case, where you're replaying a commit sequence onto the original base commit, a merge-preserving rebase should work.
See the documentation for more details.