Commit e51c8b99be1fc35bd3db30ae629cc404942cdc24
2012-12-09T21:24:47
Fix mark_parents() to account for bad luck traversals If commit timestamps are off, we're more likely to hit a traversal where the first path ends up traversing past the root commit of the tree. If that happens, it's possible that the loop will complete before the second path marks some of those final parents. This fix keeps track of the root nodes that are encountered in the traversal, and verify that they are properly marked. In the best case, with accurate timestamps, the traversal will continue to terminate when all the commits are STALE (parents of a merge-base), as it did before. In the worst case, where one path makes a complete traversal past a root commit, we will continue the loop until the root commit itself is marked.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
diff --git a/src/graph.c b/src/graph.c
index ee4fee7..2fc50ea 100644
--- a/src/graph.c
+++ b/src/graph.c
@@ -10,7 +10,7 @@
#include "merge.h"
#include "git2/graph.h"
-static int interesting(git_pqueue *list)
+static int interesting(git_pqueue *list, git_commit_list *roots)
{
unsigned int i;
/* element 0 isn't used - we need to start at 1 */
@@ -20,6 +20,12 @@ static int interesting(git_pqueue *list)
return 1;
}
+ while(roots) {
+ if ((roots->item->flags & STALE) == 0)
+ return 1;
+ roots = roots->next;
+ }
+
return 0;
}
@@ -28,6 +34,7 @@ static int mark_parents(git_revwalk *walk, git_commit_list_node *one,
{
int error;
unsigned int i;
+ git_commit_list *roots = NULL;
git_pqueue list;
/* if the commit is repeated, we have a our merge base already */
@@ -52,11 +59,13 @@ static int mark_parents(git_revwalk *walk, git_commit_list_node *one,
return -1;
/* as long as there are non-STALE commits */
- while (interesting(&list)) {
+ while (interesting(&list, roots)) {
git_commit_list_node *commit;
int flags;
commit = git_pqueue_pop(&list);
+ if (commit == NULL)
+ break;
flags = commit->flags & (PARENT1 | PARENT2 | STALE);
if (flags == (PARENT1 | PARENT2)) {
@@ -78,8 +87,15 @@ static int mark_parents(git_revwalk *walk, git_commit_list_node *one,
if (git_pqueue_insert(&list, p) < 0)
return -1;
}
+
+ if (commit->out_degree == 0) {
+ if (git_commit_list_insert(commit, &roots) == NULL)
+ return -1;
+ }
}
+ if (roots)
+ git_commit_list_free(&roots);
git_pqueue_free(&list);
return 0;