detecting cycles in Git's commit graph

Michael Hendricks· Apr 30, 2009, 19:18 UTC · lore

Are there any tools for detecting cycles in the commit graph which have been caused by grafts? I thought 'git fsck' might do it, but it doesn't seem to.

While importing some historic code into a new Git repository, my import scripts accidentally created a cycle in the commit graph by using grafts. Essentially, I had commits like:

    A -- B -- C

I accidentally created a graft marking commit C as commit B's second parent. There were 15,000 grafts so it took me a while to track down the one causing the cycle. The initial symptom was that 'git log --graph B' produced no output.

I wasn't able to find any existing tools to locate these kinds of faulty grafts.

Thanks for any pointers.

-- 
Michael

Shawn O. Pearce· Apr 30, 2009, 19:27 UTC · re: Michael Hendricks · lore

Re: detecting cycles in Git's commit graph

Michael Hendricks <michael@ndrix.org> wrote:

> Are there any tools for detecting cycles in the commit graph which
> have been caused by grafts?  I thought 'git fsck' might do it, but it
> doesn't seem to.

Nope. Cycles don't happen in a DAG. So nobody has created tools for it. :-)

Yes, grafts are impure and can be used to cause a cycle, which is
one reason among many we don't encourage them being used.

-- 
Shawn.

Stephen R. van den Berg· May 3, 2009, 11:36 UTC · re: Michael Hendricks · lore

Re: detecting cycles in Git's commit graph

Michael Hendricks wrote:

>Are there any tools for detecting cycles in the commit graph which
>have been caused by grafts?  I thought 'git fsck' might do it, but it
>doesn't seem to.

I submitted this patch some time ago, it didn't make it in. It doesn't really cost any performance (the extra overhead is lost in the cache-misses from main memory). I use it myself to quickly check for cyclic references. It doesn't tell you where you went wrong, it just checks the specified parts of the repository for circular references.

commit 0ab90c05f2255a66c1f71f35e2532dca6947fa7e
Author: Stephen R. van den Berg <srb@cuci.nl>
Date:   Thu Apr 3 06:48:38 2008 +0200

    Check for circular references causing 'lost' nodes
    
    The most likely cause for circular references are bad entries in the
    grafts file; since basically noone tells you where you went wrong, it
    can be a bit puzzling to find out that part of your tree goes dark
    sometimes, depending on which tool/options you pick to walk the
    commit-tree (most notably, things go wrong when using --topo-order even
    though things *seem* allright without that option).
    
    Signed-off-by: Stephen R. van den Berg <srb@cuci.nl>

diff --git a/commit.c b/commit.c
index aa3b35b..523bb01 100644
--- a/commit.c
+++ b/commit.c
@@ -428,6 +428,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 	struct commit_list *next, *orig = *list;
 	struct commit_list *work, **insert;
 	struct commit_list **pptr;
+	int nelements = 0;
 
 	if (!orig)
 		return;
@@ -437,6 +438,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 	for (next = orig; next; next = next->next) {
 		struct commit *commit = next->item;
 		commit->indegree = 1;
+		nelements++;
 	}
 
 	/* update the indegree */
@@ -507,7 +509,12 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 		commit->indegree = 0;
 		*pptr = work_item;
 		pptr = &work_item->next;
+		nelements--;
 	}
+	if (nelements)
+		fprintf(stderr,
+		 "Circular references resulting in %d suppressed nodes\n",
+		 nelements);
 }
 
 /* merge-base stuff */

-- 
Sincerely,
           Stephen R. van den Berg.
"Hence we are back to stenography..."
"Is that shorthand for steganography?"