{"thread":{"id":"19664","subject":"Re: [TopGit PATCH] hooks/pre-commit: check for cycles in dependencies","startedAt":"2009-06-04T20:41:13Z","lastAt":"2009-06-08T07:44:37Z","messageCount":5,"participants":["Bert Wesarg","Uwe Kleine-König"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"299108","messageId":"1244148073-2313-1-git-send-email-bert.wesarg@googlemail.com","threadId":"19664","inReplyTo":null,"subject":"[TopGit PATCH] hooks/pre-commit: check for cycles in dependencies","fromName":"Bert Wesarg","fromEmail":"bert.wesarg@googlemail.com","sentAt":"2009-06-04T20:41:13Z","receivedAt":"2009-06-04T20:41:13Z","isPatch":true,"sender":{"key":"bert.wesarg@googlemail.com","avatar":"https://avatars.githubusercontent.com/u/111934?v=4"},"body":"Only newly added dependencies needs to be considered.  For each of these deps\ncheck if there is a path from this dep to the current HEAD.\n\nUse recursive_dep() for this task.  Even if recursive_dep() uses a DFS-like\ntraversal it will not run into an infty-loop if there would be a cycle, because\nrecursive_dep() takes .topdeps only from committed trees.  And it is required\nthat the committed dependency graph is acyclic.\n\nSigned-off-by: Bert Wesarg <bert.wesarg@googlemail.com>\n\n---\n hooks/pre-commit.sh |   30 ++++++++++++++++++++++++++++--\n 1 files changed, 28 insertions(+), 2 deletions(-)\n\ndiff --git a/hooks/pre-commit.sh b/hooks/pre-commit.sh\nindex 9d677e9..8e05a4e 100644\n--- a/hooks/pre-commit.sh\n+++ b/hooks/pre-commit.sh\n@@ -20,7 +20,8 @@ tg_util\n if head_=$(git symbolic-ref -q HEAD); then\n \tcase \"$head_\" in\n \t\trefs/heads/*)\n-\t\t\tgit rev-parse -q --verify \"refs/top-bases${head_#refs/heads}\" >/dev/null || exit 0;;\n+\t\t\thead_=\"${head_#refs/heads/}\"\n+\t\t\tgit rev-parse -q --verify \"refs/top-bases/$head_\" >/dev/null || exit 0;;\n \t\t*)\n \t\t\texit 0;;\n \tesac\n@@ -35,4 +36,29 @@ fi\n [ -s \"$root_dir/.topmsg\" ] ||\n \tdie \".topmsg is missing\"\n \n-# TODO: Verify .topdeps for valid branch names and against cycles\n+check_cycle_name()\n+{\n+\t[ \"$head_\" != \"$_dep\" ] ||\n+\t\tdie \"TopGit dependencies form a cycle: perpetrator is $_name\"\n+}\n+\n+# only check newly added deps\n+# check if a path exists to the current HEAD\n+git diff --cached \"$root_dir/.topdeps\" |\n+\tawk '\n+BEGIN      { in_hunk = 0; }\n+/^@@ /     { in_hunk = 1; }\n+/^\\+/      { if (in_hunk == 1) printf(\"%s\\n\", substr($0, 2)); }\n+/^[^@ +-]/ { in_hunk = 0; }\n+' |\n+\twhile read newly_added; do\n+\t\t# deps can be non-tgish but we can't run recurse_deps() on them\n+\t\tref_exists \"refs/top-bases/$newly_added\" ||\n+\t\t\tcontinue\n+\t\t# recurse_deps uses dfs but takes the .topdeps from the tree,\n+\t\t# therefor no infty-loop in the cycle-check\n+\t\tno_remotes=1 recurse_deps check_cycle_name \"$newly_added\"\n+\tdone\n+\n+\n+# TODO: Verify .topdeps for valid branch names\n-- \ntg: (99f2ef6..) bw/check-for-dep-cycle (depends on: master)\n"},{"id":"115446","messageId":"36ca99e90906041433je1b4ce8ob121b70a2ed5e669@mail.gmail.com","threadId":"19664","inReplyTo":"1244148073-2313-1-git-send-email-bert.wesarg@googlemail.com","subject":"Re: [TopGit PATCH] hooks/pre-commit: check for cycles in dependencies","fromName":"Bert Wesarg","fromEmail":"bert.wesarg@googlemail.com","sentAt":"2009-06-04T21:33:19Z","receivedAt":"2009-06-04T21:33:19Z","isPatch":true,"sender":{"key":"bert.wesarg@googlemail.com","avatar":"https://avatars.githubusercontent.com/u/111934?v=4"},"body":"On Thu, Jun 4, 2009 at 22:41, Bert Wesarg <bert.wesarg@googlemail.com> wrote:\n> Only newly added dependencies needs to be considered.  For each of these deps\n> check if there is a path from this dep to the current HEAD.\n>\n> Use recursive_dep() for this task.  Even if recursive_dep() uses a DFS-like\n> traversal it will not run into an infty-loop if there would be a cycle, because\n> recursive_dep() takes .topdeps only from committed trees.  And it is required\n> that the committed dependency graph is acyclic.\n>\n> Signed-off-by: Bert Wesarg <bert.wesarg@googlemail.com>\n>\n> ---\n>  hooks/pre-commit.sh |   30 ++++++++++++++++++++++++++++--\n>  1 files changed, 28 insertions(+), 2 deletions(-)\n>\n> diff --git a/hooks/pre-commit.sh b/hooks/pre-commit.sh\n> index 9d677e9..8e05a4e 100644\n> --- a/hooks/pre-commit.sh\n> +++ b/hooks/pre-commit.sh\n> @@ -20,7 +20,8 @@ tg_util\n>  if head_=$(git symbolic-ref -q HEAD); then\n>        case \"$head_\" in\n>                refs/heads/*)\n> -                       git rev-parse -q --verify \"refs/top-bases${head_#refs/heads}\" >/dev/null || exit 0;;\n> +                       head_=\"${head_#refs/heads/}\"\n> +                       git rev-parse -q --verify \"refs/top-bases/$head_\" >/dev/null || exit 0;;\n>                *)\n>                        exit 0;;\n>        esac\n> @@ -35,4 +36,29 @@ fi\n>  [ -s \"$root_dir/.topmsg\" ] ||\n>        die \".topmsg is missing\"\n>\n> -# TODO: Verify .topdeps for valid branch names and against cycles\n> +check_cycle_name()\n> +{\n> +       [ \"$head_\" != \"$_dep\" ] ||\n> +               die \"TopGit dependencies form a cycle: perpetrator is $_name\"\n> +}\n> +\n> +# only check newly added deps\n> +# check if a path exists to the current HEAD\n> +git diff --cached \"$root_dir/.topdeps\" |\n> +       awk '\n> +BEGIN      { in_hunk = 0; }\n> +/^@@ /     { in_hunk = 1; }\n> +/^\\+/      { if (in_hunk == 1) printf(\"%s\\n\", substr($0, 2)); }\n> +/^[^@ +-]/ { in_hunk = 0; }\n> +' |\n> +       while read newly_added; do\n> +               # deps can be non-tgish but we can't run recurse_deps() on them\n> +               ref_exists \"refs/top-bases/$newly_added\" ||\n> +                       continue\nI think we need also a test to check against self-loops, i.e.:\n                     [ \"$head_\" != \"$newly_added\" ] ||\n                         die \"Can't have myself as dep\"\n\nCan you please squash this in.\n\n> +               # recurse_deps uses dfs but takes the .topdeps from the tree,\n> +               # therefor no infty-loop in the cycle-check\n> +               no_remotes=1 recurse_deps check_cycle_name \"$newly_added\"\n> +       done\n> +\n> +\n> +# TODO: Verify .topdeps for valid branch names\n> --\n> tg: (99f2ef6..) bw/check-for-dep-cycle (depends on: master)\n>\n"},{"id":"115560","messageId":"20090605202526.GB671@pengutronix.de","threadId":"19664","inReplyTo":"1244148073-2313-1-git-send-email-bert.wesarg@googlemail.com","subject":"Re: [TopGit PATCH] hooks/pre-commit: check for cycles in dependencies","fromName":"Uwe Kleine-König","fromEmail":"u.kleine-koenig@pengutronix.de","sentAt":"2009-06-05T20:25:26Z","receivedAt":"2009-06-05T20:25:26Z","isPatch":true,"sender":{"key":"u.kleine-koenig@pengutronix.de","avatar":"https://gravatar.com/avatar/354b5e3ceb2806a2f1e1e382ac29ddbdad18288654da62b61eb13583a857eee7?d=mp&s=160"},"body":"Hi Bert,\n\nOn Thu, Jun 04, 2009 at 10:41:13PM +0200, Bert Wesarg wrote:\n> Only newly added dependencies needs to be considered.  For each of these deps\n> check if there is a path from this dep to the current HEAD.\n> \n> Use recursive_dep() for this task.  Even if recursive_dep() uses a DFS-like\n> traversal it will not run into an infty-loop if there would be a cycle, because\nI'm not sure how understandable this is.  After some thinking I\nunderstood DFS.  Up to now I thought infty is just the LaTeX macro name\nfor \"infinity\", but apart of this, is this really the right term here?\nendless loop?\n\n> recursive_dep() takes .topdeps only from committed trees.  And it is required\n> that the committed dependency graph is acyclic.\n\nI didn't check the implementation deeply.  But all in all I don't have\nthe usual warm and fuzzy feeling about it.  What happens during a remote\nupdate if only the merged dependency graph has a cycle[1]?\n\nBest regards\nUwe\n\n[1] The question is a bit theoretic because remote updating is broken\nhere.  If you are my remote and changed a .topdep file, my update simply\ndiscards your change.\n\n-- \nPengutronix e.K.                              | Uwe Kleine-König            |\nIndustrial Linux Solutions                    | http://www.pengutronix.de/  |\n"},{"id":"115776","messageId":"36ca99e90906080031r3f5f545eo26c077e1966bf67@mail.gmail.com","threadId":"19664","inReplyTo":"20090605202526.GB671@pengutronix.de","subject":"Re: [TopGit PATCH] hooks/pre-commit: check for cycles in dependencies","fromName":"Bert Wesarg","fromEmail":"bert.wesarg@googlemail.com","sentAt":"2009-06-08T07:31:01Z","receivedAt":"2009-06-08T07:31:01Z","isPatch":true,"sender":{"key":"bert.wesarg@googlemail.com","avatar":"https://avatars.githubusercontent.com/u/111934?v=4"},"body":"2009/6/5 Uwe Kleine-König <u.kleine-koenig@pengutronix.de>:\n> Hi Bert,\nHi, Uwe,\n\n>\n> On Thu, Jun 04, 2009 at 10:41:13PM +0200, Bert Wesarg wrote:\n>> Only newly added dependencies needs to be considered.  For each of these deps\n>> check if there is a path from this dep to the current HEAD.\n>>\n>> Use recursive_dep() for this task.  Even if recursive_dep() uses a DFS-like\n>> traversal it will not run into an infty-loop if there would be a cycle, because\n> I'm not sure how understandable this is.  After some thinking I\n> understood DFS.  Up to now I thought infty is just the LaTeX macro name\n> for \"infinity\", but apart of this, is this really the right term here?\n> endless loop?\nYeah, 'endless loop' is the right term here.\n\n>\n>> recursive_dep() takes .topdeps only from committed trees.  And it is required\n>> that the committed dependency graph is acyclic.\n>\n> I didn't check the implementation deeply.  But all in all I don't have\n> the usual warm and fuzzy feeling about it.  What happens during a remote\n> update if only the merged dependency graph has a cycle[1]?\nI suspect the merge commit, which would introduce this cycle, will abort.\n\nBTW: Do you have any infos or need help on your TopGit successor?\n\nBye,\nBert\n\n>\n> Best regards\n> Uwe\n>\n> [1] The question is a bit theoretic because remote updating is broken\n> here.  If you are my remote and changed a .topdep file, my update simply\n> discards your change.\n>\n> --\n> Pengutronix e.K.                              | Uwe Kleine-König            |\n> Industrial Linux Solutions                    | http://www.pengutronix.de/  |\n>\n"},{"id":"115778","messageId":"20090608074437.GA12109@pengutronix.de","threadId":"19664","inReplyTo":"36ca99e90906080031r3f5f545eo26c077e1966bf67@mail.gmail.com","subject":"TopGit successor","fromName":"Uwe Kleine-König","fromEmail":"u.kleine-koenig@pengutronix.de","sentAt":"2009-06-08T07:44:37Z","receivedAt":"2009-06-08T07:44:37Z","isPatch":false,"sender":{"key":"u.kleine-koenig@pengutronix.de","avatar":"https://gravatar.com/avatar/354b5e3ceb2806a2f1e1e382ac29ddbdad18288654da62b61eb13583a857eee7?d=mp&s=160"},"body":"Hello Bert,\n\nOn Mon, Jun 08, 2009 at 09:31:01AM +0200, Bert Wesarg wrote:\n> BTW: Do you have any infos or need help on your TopGit successor?\nI want to get running at least the patch command, then I'm willing to\nshare it.  The key difference to topgit is that it doesn't use branches\nto track dependencies only commits.  I hope this will make some things\neasier and cleaner.\n\nBest regards\nUwe\n\n-- \nPengutronix e.K.                              | Uwe Kleine-König            |\nIndustrial Linux Solutions                    | http://www.pengutronix.de/  |\n"}]}