commit d377a885a98d4a6281b3edd0aa6a0c610cf5e1a6
author Shawn Pearce <spearce@spearce.org> Sat Apr 29 08:27:41 2017 -0700
committer Shawn Pearce <spearce@spearce.org> Tue May 02 11:38:59 2017 -0700
tree 12cdd74ac6d99754117c2ef00bfa49789e919557
parent 005e5feb4ecd08c4e4d141a38b9e7942accb3212

Fix stack overflow in MergeBaseGenerator

Some repository topologies can cause carryOntoHistory to overflow the
thread stack, due to its strategy of recursing into the 2nd+ parents
of a merge commit.  This can easily happen if a project maintains a
local fork, and frequently pulls from the upstream repository, which
itself may have a branchy history.

Rewrite the carryOntoHistory algorithm to use a fixed amount of thread
stack, pushing the save points onto the heap.  By using heap space the
thread stack depth is no longer a concern.  Repositories are instead
limited by available memory.

The algorithm is now structured as two loops:

  carryOntoHistory: This outer loop pops saved commits off the top of
  the stack, allowing the inner loop algorithm to dive down that path
  and carry bits onto commits along that part of the graph.  The loop
  ends when there are no more stack elements.

  carryOntoHistoryInner: The inner loop walks along a single path of
  the graph. For a string of pearls (commits with one parent each)

    r <- s <- t <- u

  the algorithm walks backwards from u to r by iteratively updating
  its local variable 'c'.  This avoids heap allocation along a simple
  path that does not require remembering state.

  The inner loop breaks in the HAVE_ALL case, when all bits have been
  found to be previously set on the commit.  This occurs when a prior
  iteration of the outer loop (carryOntoHistory) explored a different
  path to this same commit, and copied the bits onto it.

  When the inner loop encounters a merge commit, it pushes all parents
  onto the heap based stack by allocating individual CarryStack
  elements for each parent.  Parents are pushed in order, allowing
  side branches to be explored first.

  A small optimization is taken for the last parent, avoiding pushing
  it and instead updating 'c', allowing the side branch to be entered
  without allocating a CarryStack.

Change-Id: Ib7b67d90f141c497fbdc61a31b0caa832e4b3c04