Note this line:

 ancestor fdedead1b396 local fdedead1b396+ remote fdedead1b396

The trouble here is really that we're updating from revision 'tip+' in the
working directory to revision 'tip'. That is, we're going backwards in time. And
the merge logic for going backwards is very different from the logic going
forward. If we go backwards in time, it's quite natural to reinstate deleted
files and so we do.

So the problem seems to actually be that we shouldn't try to update in this
case, not that there's anything wrong with the merge logic itself.

Updating title.

ThomasAH: How is this related at all? The files in question are under hg
control. Your example is not equivalent, both foo and bar were modified outside
hg, not the case gabrielgi described.

ThomasAH: Fair enough, although I'd consider it a "bad practice" to do rm
instead of hg rm
within a Mercurial workspace unless we're talking about a file that's in
.hgignore (e.g., .pyc).
I chatted about this issue some weeks ago and one of the main developers
acknowledged the bug and actually found where it was. Not sure about the details
myself though.

ThomasAH: except that hg remove records R in dirstate. Since hg update without
-C keeps all dirstate changes, it shouldn't remove that, either.

The behaviour is similar to making manual changes:
touch foo
rm bar
hg update
-> foo is still there, bar is revived.

But yes, this somehow looks like needing some thought about what is the correct way.

Better explain this with an example:
---cut---
$ hg update
0 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ hg remove test.txt 
$ hg status
R test.txt
$ hg --debug update
resolving manifests
 overwrite False partial False
 ancestor fdedead1b396 local fdedead1b396+ remote fdedead1b396
 test.txt: recreating -> g
getting test.txt
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ hg status
$
---cut---

Originally, I spotted this while doing a rename:
---cut---
$ hg update
0 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ hg rename test.txt test1.txt
$ hg status
A test1.txt
R test.txt
$ hg --debug update
resolving manifests
 overwrite False partial False
 ancestor fdedead1b396 local fdedead1b396+ remote fdedead1b396
 test.txt: recreating -> g
getting test.txt
1 files updated, 0 files merged, 0 files removed, 0 files unresolved
$ hg status
A test1.txt
$
---cut---

Thanks!