detecting cycles in Git's commit graph

detecting cycles in Git's commit graph

[Michael Hendricks]

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

Re: detecting cycles in Git's commit graph

[Shawn O. Pearce]

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.

Re: detecting cycles in Git's commit graph

[Stephen R. van den Berg]

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?"