]> source.dussan.org Git - jgit.git/commit
Fix StackOverflowError in RevCommit.carryFlags on deep side graphs 51/23351/2
authorShawn Pearce <spearce@spearce.org>
Thu, 13 Mar 2014 19:45:57 +0000 (12:45 -0700)
committerShawn Pearce <spearce@spearce.org>
Thu, 13 Mar 2014 19:59:46 +0000 (12:59 -0700)
commitf716ad6d54ac74f9445b869f3fdd2b46256d1259
tree793a68fd2a534f88bc3dc1c54f38970ad01b9b58
parent4c3e7931ed1eb2c686e6e90a57e9122cf603d68c
Fix StackOverflowError in RevCommit.carryFlags on deep side graphs

Copying flags through a graph with deep side branches can cause
StackOverflowError. The recursive step to visit the 2nd parent of
a merge commit can overflow the stack if these are themselves very
deep histories with many branches.

Rewrite the loop to iterate up to 500 recursive steps deep before
unwinding the stack and running the remaining parts of the graph
using a dynamically allocated FIFORevQueue.

This approach still allows simple graphs that mostly merge short
lived topic branches into master to copy flags with no dynamic
memory allocation, relying only on temporary stack extensions.
Larger more complex graphs only pay the allocation penalities
if copying has to extend outwards "very far" in the graph, which
is unlikely for many coloring based algorithms.

Change-Id: I1882e6832c916e27dd5f6b7602d9caf66fb39c84
org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevCommit.java