From: Bert Wesarg <bert.wesarg@googlemail.com>
Date: Thu, 04 Jun 2009 21:33:19 GMT
Subject: Re: [TopGit PATCH] hooks/pre-commit: check for cycles in dependencies
Message-ID: <36ca99e90906041433je1b4ce8ob121b70a2ed5e669@mail.gmail.com>
In-Reply-To: <1244148073-2313-1-git-send-email-bert.wesarg@googlemail.com>

On Thu, Jun 4, 2009 at 22:41, Bert Wesarg <bert.wesarg@googlemail.com> wrote:
> Only newly added dependencies needs to be considered.  For each of these deps
> check if there is a path from this dep to the current HEAD.
>
> Use recursive_dep() for this task.  Even if recursive_dep() uses a DFS-like
> traversal it will not run into an infty-loop if there would be a cycle, because
> recursive_dep() takes .topdeps only from committed trees.  And it is required
> that the committed dependency graph is acyclic.
>
> Signed-off-by: Bert Wesarg <bert.wesarg@googlemail.com>
>
> ---
>  hooks/pre-commit.sh |   30 ++++++++++++++++++++++++++++--
>  1 files changed, 28 insertions(+), 2 deletions(-)
>
> diff --git a/hooks/pre-commit.sh b/hooks/pre-commit.sh
> index 9d677e9..8e05a4e 100644
> --- 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
> @@ -35,4 +36,29 @@ fi
>  [ -s "$root_dir/.topmsg" ] ||
>        die ".topmsg is missing"
>
> -# TODO: Verify .topdeps for valid branch names and against cycles
> +check_cycle_name()
> +{
> +       [ "$head_" != "$_dep" ] ||
> +               die "TopGit dependencies form a cycle: perpetrator is $_name"
> +}
> +
> +# only check newly added deps
> +# check 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
> +               # deps can be non-tgish but we can't run recurse_deps() on them
> +               ref_exists "refs/top-bases/$newly_added" ||
> +                       continue
I think we need also a test to check against self-loops, i.e.:
                     [ "$head_" != "$newly_added" ] ||
                         die "Can't have myself as dep"

Can you please squash this in.

> +               # recurse_deps uses dfs but takes the .topdeps from the tree,
> +               # therefor no infty-loop in the cycle-check
> +               no_remotes=1 recurse_deps check_cycle_name "$newly_added"
> +       done
> +
> +
> +# TODO: Verify .topdeps for valid branch names
> --
> tg: (99f2ef6..) bw/check-for-dep-cycle (depends on: master)
>