{"thread":{"id":"19140","subject":"detecting cycles in Git's commit graph","startedAt":"2009-04-30T19:18:57Z","lastAt":"2009-05-03T11:36:18Z","messageCount":3,"participants":["Michael Hendricks","Shawn O. Pearce","Stephen R. van den Berg"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"112783","messageId":"20090430191857.GA55192@ginosko.grantstreet.com","threadId":"19140","inReplyTo":null,"subject":"detecting cycles in Git's commit graph","fromName":"Michael Hendricks","fromEmail":"michael@ndrix.org","sentAt":"2009-04-30T19:18:57Z","receivedAt":"2009-04-30T19:18:57Z","isPatch":false,"sender":{"key":"michael@ndrix.org","avatar":"https://gravatar.com/avatar/315311e6daa79f24e5648f9534420c24ec48eada42efd4110f1d17167ff44fa8?d=mp&s=160"},"body":"Are there any tools for detecting cycles in the commit graph which\nhave been caused by grafts? I thought 'git fsck' might do it, but it\ndoesn't seem to.\n\nWhile importing some historic code into a new Git repository, my\nimport scripts accidentally created a cycle in the commit graph by\nusing grafts. Essentially, I had commits like:\n\n A -- B -- C\n\nI accidentally created a graft marking commit C as commit B's second\nparent. There were 15,000 grafts so it took me a while to track down\nthe one causing the cycle. The initial symptom was that 'git log\n--graph B' produced no output.\n\nI wasn't able to find any existing tools to locate these kinds of\nfaulty grafts.\n\nThanks for any pointers.\n\n-- \nMichael\n"},{"id":"112785","messageId":"20090430192714.GT23604@spearce.org","threadId":"19140","inReplyTo":"20090430191857.GA55192@ginosko.grantstreet.com","subject":"Re: detecting cycles in Git's commit graph","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-04-30T19:27:14Z","receivedAt":"2009-04-30T19:27:14Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Michael Hendricks wrote:\n> Are there any tools for detecting cycles in the commit graph which\n> have been caused by grafts? I thought 'git fsck' might do it, but it\n> doesn't seem to.\n\nNope. Cycles don't happen in a DAG. So nobody has created tools\nfor it. :-)\n\nYes, grafts are impure and can be used to cause a cycle, which is\none reason among many we don't encourage them being used.\n \n-- \nShawn.\n"},{"id":"112916","messageId":"20090503113618.GA27798@cuci.nl","threadId":"19140","inReplyTo":"20090430191857.GA55192@ginosko.grantstreet.com","subject":"Re: detecting cycles in Git's commit graph","fromName":"Stephen R. van den Berg","fromEmail":"srb@cuci.nl","sentAt":"2009-05-03T11:36:18Z","receivedAt":"2009-05-03T11:36:18Z","isPatch":false,"sender":{"key":"srb@cuci.nl","avatar":"https://gravatar.com/avatar/f75389059e827634d38e9df2a9b6ecbd50028b5a454442efa1c7205b7ff29c6a?d=mp&s=160"},"body":"Michael Hendricks wrote:\n>Are there any tools for detecting cycles in the commit graph which\n>have been caused by grafts? I thought 'git fsck' might do it, but it\n>doesn't seem to.\n\nI submitted this patch some time ago, it didn't make it in. It doesn't really\ncost any performance (the extra overhead is lost in the cache-misses from\nmain memory). I use it myself to quickly check for cyclic references.\nIt doesn't tell you where you went wrong, it just checks the specified\nparts of the repository for circular references.\n\ncommit 0ab90c05f2255a66c1f71f35e2532dca6947fa7e\nAuthor: Stephen R. van den Berg \nDate: Thu Apr 3 06:48:38 2008 +0200\n\n Check for circular references causing 'lost' nodes\n \n The most likely cause for circular references are bad entries in the\n grafts file; since basically noone tells you where you went wrong, it\n can be a bit puzzling to find out that part of your tree goes dark\n sometimes, depending on which tool/options you pick to walk the\n commit-tree (most notably, things go wrong when using --topo-order even\n though things *seem* allright without that option).\n \n Signed-off-by: Stephen R. van den Berg \n\ndiff --git a/commit.c b/commit.c\nindex aa3b35b..523bb01 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -428,6 +428,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)\n \tstruct commit_list *next, *orig = *list;\n \tstruct commit_list *work, **insert;\n \tstruct commit_list **pptr;\n+\tint nelements = 0;\n \n \tif (!orig)\n \t\treturn;\n@@ -437,6 +438,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)\n \tfor (next = orig; next; next = next->next) {\n \t\tstruct commit *commit = next->item;\n \t\tcommit->indegree = 1;\n+\t\tnelements++;\n \t}\n \n \t/* update the indegree */\n@@ -507,7 +509,12 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)\n \t\tcommit->indegree = 0;\n \t\t*pptr = work_item;\n \t\tpptr = &work_item->next;\n+\t\tnelements--;\n \t}\n+\tif (nelements)\n+\t\tfprintf(stderr,\n+\t\t \"Circular references resulting in %d suppressed nodes\\n\",\n+\t\t nelements);\n }\n \n /* merge-base stuff */\n-- \nSincerely,\n Stephen R. van den Berg.\n\"Hence we are back to stenography...\"\n\"Is that shorthand for steganography?\"\n"}]}