bzr push raises RevisionNotPresent

Note that this is a critical bug because it's a regression from bzr 1.9

I can reproduce this locally with:

# Grab a copy of bzr.dev trunk
bzr branch lp:bzr

# Grab a copy of the brisbane branch
bzr branch lp:~bzr/bzr/brisbane-core

# Create a stacked branch of brisbane-core on top of bzr trunk
cd brisbane-core
bzr push --stacked-on ../bzr ../stack-test

Source format does not support stacking, using format: '1.6'
  Packs 5 (adds stacking support, requires bzr 1.6)

bzr: ERROR: Revision {('<email address hidden>',)} not present in
 "KnitVersionedFiles(_KnitGraphIndex(CombinedGraphIndex()), <bzrlib.knit._DirectPackAccess object at
 0x0270E4F0>)".

Note that not all branches trigger this error. I have a couple smaller branches which do not.
It seems to be triggering while trying to insert some Inventory texts, I don't have much more info than that right now.

But at least the brisbane-core versus trunk branches do seem to have whatever data is required to cause the problem.

I think I've sorted it out now, though something is still a bit weird.

What I'm seeing is that we are trying to insert a text for an inventory at revision "X" and trying to expand it to a fulltext. We then ask the target repository (with a fallback_vfs) to expand the basis "Y" into a fulltext.
It then finds the delta chain for Y, which includes a bunch of revisions which are in the stacked repository and not the basis. However, the tip of that chain is missing.

I'm not entirely sure how we got here, but imagine a chain of:
A-B-C-D-E
^^^-In base
   ^^^^^-only in new branch

We are trying to insert E, but we haven't seen C or D yet. Because the revisions are transmitted in "random" order, we see that E is a delta whose parent is not present in the target repository (yet), but we can't actually unpack it because we haven't gotten D yet.

This only happens when you are transmitting a lot of a changes, because otherwise your delta chains are short, and the likelyhood of getting them out-of-order is small.

I think the best fix is to just fetch in topological order if the target is going to be stacked, as it solves a bunch of other issues. And is a quicker fix.

So it turns out to be a little bit more complicated then that. I'll draw a new graph.
  base
    stacked
  A
  |\
  B C
  | |
  | D
   \|
    E

So at this point, we want to transmit the texts for C, D, E.

Imagine that we get them in the order D, E, C.

When we get D, we see that it *does* have a parent, which is not in the local
repository. But then we see that it is also not in the fallback repository, so
we go ahead and insert it as a delta.

We then get to E. And we see that
a) self._index.missing(parents) == B. The new stacked repository is missing the
merge parent.
b) self.missing(parents) == []. One parent (D) is in the target repo, and the
other parent (B) is in the base.

That triggers the code which says "it *is* in the base but not in the target.
Which causes us to try to extract it to a full-text.

However, this ends up being bogus, because we haven't seen C yet. Which means
we can't produce a fulltext.

There are 2 fixes for this, which I'll send to the mailing list

1) We don't get into this problem if we request things in topological order.
This is the "trivial" fix, though a bit of a sledgehammer. I like the fact that
it is likely to help us avoid having any other random errors pop up. I'll also
note that "PackRepository.get_record_stream(keys, 'unordered', False)" reads
and sends the records in truly random order (iter(dict) order), rather than
doing anything sensible like reading from one pack at a time in forward I/O
order.

2) We should only be checking the compression parent. We don't care that B is
in the stacked-on location but not in the target repository, because the actual
text delta is not against B.

The plot thickens further...

It turns out that the direct graph given above doesn't trigger the bug. The reason is that when we see D, we don't have its direct parent in this index or in the fallback, so we buffer the index record rather than adding it right away.
Which means that when we get to "E" we don't have "D" available so self._index.missing_keys([D]) == D.

However if we extend the graph slightly:
   A
   |\
   B C
   | |
   | D
   | |
   | E
    \|
     F

And then get the keys in E, D, F, C order.

What happens is that when D comes in, we assume that it is okay to add E to the
index, because we don't check if buffered=False. We just assume that we just
added this record, so it is okay to add any buffered children.

To further complicate things, all of C=>F need to be deltas, which means that the size of the compressed fulltext must be > than the size of 4 compressed deltas. So you have to have a fairly large fulltext that can't compress too well.

The fix in bzr.dev breaks the model for _fetch_order which is meant to be solely talking about physical capabilities. This interacts badly with RemoteRepository and further it sounds like there is simply a bug in the buffer checking code in knit.insert_record_stream.

I'll fix that, if someone familiar with the bug can confirm my understanding is correct.