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

[TopGit PATCH] pre-commit: check .topdeps for valid branches

[Bert Wesarg]

Signed-off-by: Bert Wesarg <bert.wesarg@googlemail.com>

---
 hooks/pre-commit.sh |    6 +++---
 1 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/hooks/pre-commit.sh b/hooks/pre-commit.sh
index fd960a4..f6901e4 100644 hooks/pre-commit.sh
--- a/hooks/pre-commit.sh
+++ b/hooks/pre-commit.sh
@@ -52,6 +52,9 @@ BEGIN      { in_hunk = 0; }
 /^[^@ +-]/ { in_hunk = 0; }
 ' |
 	while read newly_added; do
+		ref_exists "$newly_added" ||
+			die "Invalid branch as dependent: $newly_added"
+
 		# check for self as dep
 		[ "$head_" != "$newly_added" ] ||
 			die "Can't have myself as dep"
@@ -64,6 +67,3 @@ BEGIN      { in_hunk = 0; }
 		# 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: (d4c1eaf..) bw/check-valid-deps (depends on: bw/check-for-dep-cycle)

[TopGit PATCH] hooks/pre-commit: check for deps repititions

[Bert Wesarg]

A dep should only be listed once in .topdeps, force this.

Signed-off-by: Bert Wesarg <bert.wesarg@googlemail.com>

---
 hooks/pre-commit.sh |   12 ++++++++++++
 1 files changed, 12 insertions(+), 0 deletions(-)

diff --git a/hooks/pre-commit.sh b/hooks/pre-commit.sh
index f6901e4..e8986d6 100644 hooks/pre-commit.sh
--- a/hooks/pre-commit.sh
+++ b/hooks/pre-commit.sh
@@ -67,3 +67,15 @@ BEGIN      { in_hunk = 0; }
 		# therefore no endless loop in the cycle-check
 		no_remotes=1 recurse_deps check_cycle_name "$newly_added"
 	done
+
+# check for repititions of deps
+depdir="$(mktemp -t -d tg-depdir.XXXXXX)" ||
+	die "Can't check for mulitple occurrences of deps"
+trap "rm -rf '$depdir'" 0
+cat_file "(i):.topdeps" |
+	while read dep; do
+		[ ! -d "$depdir/$dep" ] ||
+			die "Mulitple occurrences of the same dep: $dep"
+		mkdir -p "$depdir/$dep" ||
+			die "Can't check for mulitple occurrences of deps"
+	done
-- 
tg: (a2bfc32..) bw/check-for-repetitions (depends on: bw/check-valid-deps)