What actually happens does matter. You can't understand how lots of git commands work if you don't understand that the git commit tree is an append-only data structure and that branches are just labels of leaves in the tree.

Let me see if I can clarify. Here is a summary of the situation you described before any push or pull.

    origin repo: M (master)
    your repo:   M---C1 (master)
    other repo:  M---C2 (master)
    
 If other pushes `master` to origin we have:
 
    origin repo: M---C2 (master)
    your repo:   M---C1 (master)
    other repo:  M---C2 (master)

If you then run, from master, `pull --rebase` we have:

    origin repo: M---C2 (master)
    your repo:   M---C1
                  \
                   C2---C1' (master)
    other repo:  M---C2 (master)
 

Your master branch will be positioned at C1'. As you can see from the diagram, the `pull --rebase` didn't change any existing commits, it just added C2 (same SHA as in the origin and other repos) and added C1', which are the changes in C1 applied to C2 instead of M. If those changes can't be made automatically, you'll get a conflict that has to be resolved before C1' can be created.

I don't think it is helpful to describe this as adjusting the order of commits or re-writing history or any similar language that suggests some sort of mutation to the commit tree. The only thing that has happened here is that additional commits have been added to the tree and the label `master` has been moved to a new leaf commit.

I realize some other commenters have said I'm being pedantic but I would instead say that I'm being accurate. You can't really understand how rebase, rebase -i, rebase --onto, fixups, reflog manipulations, and so on work if you don't have the correct mental model of the git commit tree.

Sure, but lots of people using git don't really understand that commits are immutable or that the commit tree is an append-only data structure. The pervasive use of the phrase 'rewrite history' hinders this understanding.

Nope, parent is correct. If you use hg's changeset evolution and run rebase, and then do a hg log --graph --hidden you can see that your original commits have not been touched, other than to mark them as hidden and obsolete.