This implies that:
- you rewrote your commit history reachable from
foo, and/or
- someone rewrote the commit history reachable from
master over on origin.
In general, the way to recover from this is to rebase the commits that are strictly yours, excluding all commits that were theirs, --onto the appropriate commit in their updated master. That is, suppose they are the ones who rewrote commit history. You ran:
git clone <url>
and got:
A--B--...--R <-- master (HEAD), origin/master
You then created your branch foo pointing to original commit R (each uppercase letter here stands in for some hash ID):
A--B--...--R <-- foo (HEAD), master, origin/master
You then created a series of new commits:
A--B--...--R <-- master, origin/master
\
S--T <-- foo (HEAD)
(but probably longer than this). Meanwhile someone else, who controls the origin repository, decided that for some reason, they hate something about commit A and they needed to replace commit A with a new-and-improved A' (different hash ID, and probably a different snapshot). This made it necessary for them to replace B with a new and improved B' that sits atop A', and so on, all the way down to R.
You then use git fetch (perhaps via git pull) to bring in their new commits; your Git updates your origin/master to point to the last of the new commits, and in the meantime they added one new commit U:
A'-B'-...--R'-U <-- origin/master
A--B--...--R <-- master
\
S--T <-- foo (HEAD)
Your branch's history—the history that ends at T on foo—begins with commit A and runs all the way to commit T. Their branch's history for master, which ends at U, now starts at A', which has no relationship to commit A. So git merge cannot do anything as there is no common starting point.
To recover from this, you would want to copy your commits S and T—those being the ones you made, not the ones you got with your initial git clone—to new-and-improved S' and T'. These may fit easily after U, which could be your final end goal, but they are more likely to fit easily after R', origin's replacement for R. So you would now run:
git switch foo # if / as needed
git rebase --onto origin/master <hash-of-R>
or:
git rebase --onto origin/master master
(if you have not changed where your own name master points, so that your master still remembers which commit you started with as you began to make new commits on foo).
Assuming this works—though it may have a few merge conflicts along the way for you to solve—you'll end up with this in your own repository:
S'-T' <-- foo (HEAD)
/
A'-B'-...--R'-U <-- origin/master
A--B--...--R <-- master
\
S--T <-- origin/foo [since you had pushed foo earlier]
You can now git push --force-with-lease origin foo to force their foo (your origin/foo) to move so that it points to T', abandoning your original S-T chain of commits entirely. Now their branch tip U and your branch tip T' have a common starting point, namely commit R', and now you can make a PR on GitHub.
(If you're the one who rewrote history, perhaps through an inappropriate filter-branch or filter-repo or just an inappropriate git rebase, the process is still essentially the same: you need to figure out which commits are yours and copy just those commits. Use git log --graph and/or see Pretty Git branch graphs for ways for helping figure out which commits those are, if the simple "my master branch name" trick is no longer usable.)
