Another caveat here is that if you destroy commits directly in Phabricator's working copy in certain states, it's possible it won't be able to trace ancestry to find all the commits you destroyed in order to mark them unreachable. However, this window is narrow. For Git, you can bin/repository mark-reachable to rebuild reachability if you know you've done a bunch of dangerous mutations to the on-disk state.

Does this refer to when multiple dependent commits are pushed and then stripped from the on-disk state? Or does "in certain states" refer to something like the commits being destroyed while daemon workers are in the process of discovering/importing them?

Does this refer to when multiple dependent commits are pushed and then stripped from the on-disk state?

Basically, yes.

Commits are discovered in ancestry order, from oldest ancestors to newest descendant (i.e., all parents of a commit are discovered before it is discovered).

If you push commits A, B, and C (where C depends on B depends on A) to newref1 and then let the daemons run for a bit and kill -9 them, you might get into a state where A and B have been discovered, but C has not. Normally this is fine and desirable: when you restart the daemons, they'll pick up where they left off, discover C, and converge to the right state.

However, if you destroy newref1 and C on disk while the daemons are stopped and then restart them, they won't be able to discover C. Here's the problem: they also won't be able to mark A and B as unreachable, because they can't learn anything about the commit that newref1 pointed at (C, now destroyed) and don't have a record of its parent commits (since it was never discovered).

That is, the operation used to mark commits as unreachable is "select all commits which were ancestors of the last known set of refs, and are not ancestors of the current set of refs" ("the fast way"), rather than "select all known commits which are not ancestors of any current ref" ("the thorough way"). We do it the fast way since it's almost always O(number of refs) rather than O(number of commits), but we get into trouble if we can no longer compute "ancestors of the last known set of refs" because some necessary data was destroyed on disk before we read it into the database state.

The bin/repository mark-reachable command implements "the thorough way", and checks that every commit is an ancestor of some ref.

This window to get into trouble is virtually nonexistent in git because commit C won't actually be removed from the disk for two weeks under default configuration, even if you delete newref1 immediately. In any normal/reasonable configuration, C will be discovered in that time and its ancestors can then be marked unreachable. But you might be able to hit the window if you go onto the server and explicitly prune/gc things, or configure the GC behavior to be aggressive.

In Mercurial, I'm not exactly sure how wide this window is. Since you normally can't strip commits in the remote by pushing (AFAIK?) I think it's also quite narrow: as with Git, you have to go onto the server and start stripping commits to hit it. But we could perhaps imagine some kind of process like "strip build branches automatically every night" that would be more dangerous in Mercurial (since "strip" takes effect immediately) than in Git (since deleting a ref takes effect ~two weeks later).

I think it's reasonable to require users to bin/repository mark-reachable to repair things if they get into an inconsistent state with aggressive server-side data destruction commands and I'm not overly worried about weird automated scripts that destroy things -- and I don't see any real ways around this. This window is more of a "for completeness" issue than a real problem.

(D21715 is still a draft, but I left a couple of more specific comments there.)

In Mercurial, I'm not exactly sure how wide this window is. Since you normally can't strip commits in the remote by pushing (AFAIK?)

This is true, though it does change a bit if we enable evolve server-side. Then when commits/branches are pruned when pushing/pulling those obsolete markers will also be transferred, allowing similar disappearing commits (retrievable via —hidden). However I believe by default mercurial does not allow pruning public changesets (would require forcibly changing phases on client/server, or running a server/branch in non-publishing mode). Supporting evolve/topics server-side is probably large enough that it would be its own big project. So I think this assumption holds up well.