parsing probably shouldn't crash

Let's start here -- this isn't a crash. What about the behavior makes you think that it is? How could we improve the error message or other behavior to make it clear that this is expected/normal behavior?

Oh wow! Thanks for looking at this on a Sunday morning!
If this is expected then I think there are a couple of things that are happening that could make it better:

1. It looks like an uncaught exception, which seems like a crash and definitely says "unexpected"
2. It gives no explanation of what's really going on here. All there is is Commit "191140" has been deleted: it is no longer reachable from any ref., but it's unclear what 191140 is, and it doesn't look like a valid commit, so at a glance, it looks like something isn't getting parsed right. It is also happening while parsing a commit that I can't find in my local copy, but it exists in Phabricator's local copy. An explanation on how that could happen would be useful, too.
3. Most importantly, it gives no way to get out of this state. There are now commits stuck in "Importing" state permanently, which leaves the entire repository in an unfinished state. Providing the user with a facility to resolve this (and pointing them to it in the error message) would go a long way here, even if it's something simple and brute force, like ignoring this commit, or marking the whole repository as imported (which is what I ended up doing).

Since it was super late and I should go to bed i decided i should try and figure out what it means.

In PhabricatorRepositoryDiscoveryEngine.php you will find this function which is doing most of the work.

<?php 

  private function markUnreachableCommits(PhabricatorRepository $repository) {
    // For now, this is only supported for Git.
    if (!$repository->isGit()) {
      return;
    }

    // Find older versions of refs which we haven't processed yet. We're going
    // to make sure their commits are still reachable.
    $old_refs = id(new PhabricatorRepositoryOldRef())->loadAllWhere(
      'repositoryPHID = %s',
      $repository->getPHID());

    // We can share a single graph stream across all the checks we need to do.
    $stream = new PhabricatorGitGraphStream($repository);

    foreach ($old_refs as $old_ref) {
      $identifier = $old_ref->getCommitIdentifier();
      $this->markUnreachableFrom($repository, $stream, $identifier);

      // If nothing threw an exception, we're all done with this ref.
      $old_ref->delete();
    }
  }

It looks like PhabricatorRepositoryOldRef is holding all the information that we are curious about.
Which is just a DAO so not all that useful but looking for places that new objects are created with that class shows that it's used in PhabricatorRepositoryRefEngine.php which is really not that helpful for what we want. But it does have this cool property called deadRefs that is likely of interest.

deadRefs looks like it has new entries appended via markRefDead which is used inside this function.

<?php

  private function updateCursors(
    array $cursors,
    array $new_refs,
    $ref_type,
    array $all_closing_heads) {
    $repository = $this->getRepository();

    // NOTE: Mercurial branches may have multiple branch heads; this logic
    // is complex primarily to account for that.

    // Group all the cursors by their ref name, like "master". Since Mercurial
    // branches may have multiple heads, there could be several cursors with
    // the same name.
    $cursor_groups = mgroup($cursors, 'getRefNameRaw');

    // Group all the new ref values by their name. As above, these groups may
    // have multiple members in Mercurial.
    $ref_groups = mgroup($new_refs, 'getShortName');

    foreach ($ref_groups as $name => $refs) {
      $new_commits = mpull($refs, 'getCommitIdentifier', 'getCommitIdentifier');

      $ref_cursors = idx($cursor_groups, $name, array());
      $old_commits = mpull($ref_cursors, null, 'getCommitIdentifier');

      // We're going to delete all the cursors pointing at commits which are
      // no longer associated with the refs. This primarily makes the Mercurial
      // multiple head case easier, and means that when we update a ref we
      // delete the old one and write a new one.
      foreach ($ref_cursors as $cursor) {
        if (isset($new_commits[$cursor->getCommitIdentifier()])) {
          // This ref previously pointed at this commit, and still does.
          $this->log(
            pht(
              'Ref %s "%s" still points at %s.',
              $ref_type,
              $name,
              $cursor->getCommitIdentifier()));
        } else {
          // This ref previously pointed at this commit, but no longer does.
          $this->log(
            pht(
              'Ref %s "%s" no longer points at %s.',
              $ref_type,
              $name,
              $cursor->getCommitIdentifier()));

          // Nuke the obsolete cursor.
          $this->markRefDead($cursor);
      }

      // Now, we're going to insert new cursors for all the commits which are
      // associated with this ref that don't currently have cursors.
      $added_commits = array_diff_key($new_commits, $old_commits);
      foreach ($added_commits as $identifier) {
        $this->log(
          pht(
            'Ref %s "%s" now points at %s.',
            $ref_type,
            $name,
            $identifier));
        $this->markRefNew(
          id(new PhabricatorRepositoryRefCursor())
            ->setRepositoryPHID($repository->getPHID())
            ->setRefType($ref_type)
            ->setRefName($name)
            ->setCommitIdentifier($identifier));
      }

      if ($this->shouldCloseRef($ref_type, $name)) {
        foreach ($added_commits as $identifier) {
          $new_identifiers = $this->loadNewCommitIdentifiers(
            $identifier,
            $all_closing_heads);

          $this->markCloseCommits($new_identifiers);
        }
      }
    }

    // Find any cursors for refs which no longer exist. This happens when a
    // branch, tag or bookmark is deleted.

    foreach ($cursor_groups as $name => $cursor_group) {
      if (idx($ref_groups, $name) === null) {
        foreach ($cursor_group as $cursor) {
          $this->log(
            pht(
              'Ref %s "%s" no longer exists.',
              $cursor->getRefType(),
              $cursor->getRefName()));
          $this->markRefDead($cursor);
        }
      }
    }
  }

This function is called from somewhere else in the same file like so...

<?php

    $all_cursors = id(new PhabricatorRepositoryRefCursorQuery())
      ->setViewer(PhabricatorUser::getOmnipotentUser())
      ->withRepositoryPHIDs(array($repository->getPHID()))
      ->execute();
    $cursor_groups = mgroup($all_cursors, 'getRefType');

    $this->hasNoCursors = (!$all_cursors);

    // Find all the heads of closing refs.
    $all_closing_heads = array();
    foreach ($all_cursors as $cursor) {
      if ($this->shouldCloseRef($cursor->getRefType(), $cursor->getRefName())) {
        $all_closing_heads[] = $cursor->getCommitIdentifier();
      }
    }
    $all_closing_heads = array_unique($all_closing_heads);
    $all_closing_heads = $this->removeMissingCommits($all_closing_heads);

    foreach ($maps as $type => $refs) {
      $cursor_group = idx($cursor_groups, $type, array());
      $this->updateCursors($cursor_group, $refs, $type, $all_closing_heads);
    }

...

If we go to the database now and find the table called *_repository with table repository_refcursor we can see what kind of data is saved here. Which may or may not be obvious based on your git knowledge.

From the function above we can see that the two instances that markRefDead get marked are when a ref is changed such as master is updated or when a tag/branch is deleted.

Does your repository not show as 100% imported? i'm actually a little curious about why this specific commit it being flagged as no longer reachable but i'm guessing you just deleted the only branch this merge commit was contained on.

P.S. Everything above could be completely wrong.

The above analysis is correct.

Broadly, in the "discovery" phase, we find all changes to refs (branches, tags, arbitrary refs) since the last time we looked at the repository. We record new refs (e.g., a branch was updated) and old/dead refs (where a branch used to point to before it was deleted or overwritten).

In the "refs" phase, we go through all the old/dead refs and check if they're still reachable in the repository (if any branch or tag points at a descendant of the commit they previously pointed at). In the common case where you update "master" by pushing one commit, the old "master" will still be reachable (it will be the parent of the new master) so we won't do anything interesting. But in the case where you deleted a branch (and no other branch or tag or ref contained the same commits), the old ref will no longer be reachable.

If a ref is no longer reachable, we walk backward to find all of its parents and mark all the parents that are now unreachable as unreachable. For example, if you delete a branch with 10 commits on it, we'll walk backward and mark all 10 as dead until we find a commit which is also on another branch (like "master"). That commit isn't dead (you can still reach it from "master") so we stop.

When the daemons go to process a commit, they check if it was previously marked dead. If it was, they throw a PhabricatorWorkerPermanentFailureException, which is caught and handled by the worker daemon. This exception means "just cancel this task, it can't be completed", and is a normal condition.

When we mark commits unreachable, we expect any currently-queued tasks to fail like this. You can reproduce this exception by doing this:

1. Stop the daemons.
2. Push a unique commit to a branch.
3. Run bin/repository update Rxxx to update the repository (this discovers your commit).
4. Delete the branch.
5. Run bin/repository update Rxxx to update the repository (this marks the commit unreachable).
6. Start the daemons or run bin/phd debug task to work through the task queue.

When step (3) discovered the commit, it queued a task to process it.

When step (6) actually runs that task, it sees that the commit has been deleted, so it cancels the task.

This is normal and expected. D16268 makes this behavior more obvious by using simpler and more explicit language to describe what is happening, why, and label the internal commit ID:

PhabricatorTaskmasterDaemon Task 1428658 was cancelled: Commit "R55:6c46b7d0fb82a859ca3f87a95dc8dcceef8088c9" (with internal ID "282161") is no longer reachable from any branch, tag, or ref in this repository, so it will not be imported. This usually means that the branch the commit was on was deleted or overwritten.

When moving a repository from "importing" to "imported", we check if any commits are marked as still needing to import.

We incorrectly counted unreachable commits, even though they can never import.

D16269 fixes this: we will no longer count unreachable commits as "importing" commits.

I wasn't able to identify any other unexpected behavior.

Thanks for the analysis and the change. It makes a lot of sense to me now and, to be fair, I wouldn't have even seen the exception had the repository finished importing, which is what the fix does.
Thanks again.