hooks/pre-commit: check for cycles in dependencies

We need only to consider newly added dependencies.  For each of these deps we
need to check if there is a path from this dep to the current HEAD.

We use recursive_dep() for this task.  Even if recursive_dep() uses a DFS
traversal it will not run into an endless loop if there would be a cycle,
because recursive_dep() takes .topdeps only from committed trees.  And we
require that the committed dependency graph has no cycles.

Signed-off-by: Bert Wesarg <bert.wesarg@googlemail.com>
Signed-off-by: Uwe Kleine-König <u.kleine-koenig@pengutronix.de>

diff --git a/hooks/pre-commit.sh b/hooks/pre-commit.sh
index 8ac913f6479d86af2a64e2dea1e0aff39f347cd4..b6361c52a024e58721ddda8275f3a7d56ce524f5 100644 (file)
--- a/hooks/pre-commit.sh
+++ b/hooks/pre-commit.sh
@@ -20,7 +20,8 @@ tg_util
 if head_=$(git symbolic-ref -q HEAD); then
        case "$head_" in
                refs/heads/*)
-                       git rev-parse -q --verify "refs/top-bases${head_#refs/heads}" >/dev/null || exit 0;;
+                       head_="${head_#refs/heads/}"
+                       git rev-parse -q --verify "refs/top-bases/$head_" >/dev/null || exit 0;;
                *)
                        exit 0;;
        esac
@@ -61,4 +62,34 @@ tree=$(git write-tree) ||
 check_topfile "$tree" ".topdeps"
 check_topfile "$tree" ".topmsg"
 
-# TODO: Verify .topdeps for valid branch names and against cycles
+check_cycle_name()
+{
+       [ "$head_" != "$_dep" ] ||
+               die "TopGit dependencies form a cycle: perpetrator is $_name"
+}
+
+# we only need to check newly added deps and for these if a path exists to the
+# current HEAD
+git diff --cached "$root_dir/.topdeps" |
+       awk '
+BEGIN      { in_hunk = 0; }
+/^@@ /     { in_hunk = 1; }
+/^\+/      { if (in_hunk == 1) printf("%s\n", substr($0, 2)); }
+/^[^@ +-]/ { in_hunk = 0; }
+' |
+       while read newly_added; do
+               # check for self as dep
+               [ "$head_" != "$newly_added" ] ||
+                       die "Can't have myself as dep"
+
+               # deps can be non-tgish but we can't run recurse_deps() on them
+               ref_exists "refs/top-bases/$newly_added" ||
+                       continue
+
+               # recurse_deps uses dfs but takes the .topdeps from the tree,
+               # therefore no endless loop in the cycle-check
+               no_remotes=1 recurse_deps check_cycle_name "$newly_added"
+       done
+
+
+# TODO: Verify .topdeps for valid branch names