[TopGit PATCH] hooks/pre-commit: check for cycles in dependencies

[TopGit PATCH] hooks/pre-commit: check for cycles in dependencies

[Bert Wesarg]

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
+		# 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)

Re: [TopGit PATCH] hooks/pre-commit: check for cycles in dependencies

[Bert Wesarg]

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)
>

Re: [TopGit PATCH] hooks/pre-commit: check for cycles in dependencies

[Uwe Kleine-König]

Hi Bert,

On Thu, Jun 04, 2009 at 10:41:13PM +0200, Bert Wesarg 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
I'm not sure how understandable this is.  After some thinking I
understood DFS.  Up to now I thought infty is just the LaTeX macro name
for "infinity", but apart of this, is this really the right term here?
endless loop?

> recursive_dep() takes .topdeps only from committed trees.  And it is required
> that the committed dependency graph is acyclic.

I didn't check the implementation deeply.  But all in all I don't have
the usual warm and fuzzy feeling about it.  What happens during a remote
update if only the merged dependency graph has a cycle[1]?

Best regards
Uwe

[1] The question is a bit theoretic because remote updating is broken
here.  If you are my remote and changed a .topdep file, my update simply
discards your change.

-- 
Pengutronix e.K.                              | Uwe Kleine-König            |
Industrial Linux Solutions                    | http://www.pengutronix.de/  |

Re: [TopGit PATCH] hooks/pre-commit: check for cycles in dependencies

[Bert Wesarg]

2009/6/5 Uwe Kleine-König <u.kleine-koenig@pengutronix.de>:
> Hi Bert,
Hi, Uwe,

>
> On Thu, Jun 04, 2009 at 10:41:13PM +0200, Bert Wesarg 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
> I'm not sure how understandable this is.  After some thinking I
> understood DFS.  Up to now I thought infty is just the LaTeX macro name
> for "infinity", but apart of this, is this really the right term here?
> endless loop?
Yeah, 'endless loop' is the right term here.

>
>> recursive_dep() takes .topdeps only from committed trees.  And it is required
>> that the committed dependency graph is acyclic.
>
> I didn't check the implementation deeply.  But all in all I don't have
> the usual warm and fuzzy feeling about it.  What happens during a remote
> update if only the merged dependency graph has a cycle[1]?
I suspect the merge commit, which would introduce this cycle, will abort.

BTW: Do you have any infos or need help on your TopGit successor?

Bye,
Bert

>
> Best regards
> Uwe
>
> [1] The question is a bit theoretic because remote updating is broken
> here.  If you are my remote and changed a .topdep file, my update simply
> discards your change.
>
> --
> Pengutronix e.K.                              | Uwe Kleine-König            |
> Industrial Linux Solutions                    | http://www.pengutronix.de/  |
>

TopGit successor

[Uwe Kleine-König]

Hello Bert,

On Mon, Jun 08, 2009 at 09:31:01AM +0200, Bert Wesarg wrote:
> BTW: Do you have any infos or need help on your TopGit successor?
I want to get running at least the patch command, then I'm willing to
share it.  The key difference to topgit is that it doesn't use branches
to track dependencies only commits.  I hope this will make some things
easier and cleaner.

Best regards
Uwe

-- 
Pengutronix e.K.                              | Uwe Kleine-König            |
Industrial Linux Solutions                    | http://www.pengutronix.de/  |

[TopGit PATCH] hooks/pre-commit: check for cycles in dependencies

[Bert Wesarg]

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>

---

Note, the dependency on bw/tred is only historical, it only depends on master.

 hooks/pre-commit.sh |   35 +++++++++++++++++++++++++++++++++--
 1 files changed, 33 insertions(+), 2 deletions(-)

diff --git a/hooks/pre-commit.sh b/hooks/pre-commit.sh
index 9d677e9..fd960a4 100644 hooks/pre-commit.sh
--- 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,34 @@ 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"
+}
+
+# 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
-- 
tg: (550c37a..) bw/check-for-dep-cycle (depends on: bw/tred)