# Re: [TopGit PATCH] hooks/pre-commit: check for cycles in dependencies 5 messages from 2009-06-04 to 2009-06-08. Participants: Bert Wesarg, Uwe Kleine-König. Thread: https://gitlist.dev/t/19664 ## Bert Wesarg, 2009-06-04 20:41 Subject: [TopGit PATCH] hooks/pre-commit: check for cycles in dependencies Message-ID: <1244148073-2313-1-git-send-email-bert.wesarg@googlemail.com> URL: https://gitlist.dev/e/1244148073-2313-1-git-send-email-bert.wesarg%40googlemail.com ``` 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 --- 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) ``` ## Bert Wesarg, 2009-06-04 21:33 Subject: Re: [TopGit PATCH] hooks/pre-commit: check for cycles in dependencies Message-ID: <36ca99e90906041433je1b4ce8ob121b70a2ed5e669@mail.gmail.com> URL: https://gitlist.dev/e/36ca99e90906041433je1b4ce8ob121b70a2ed5e669%40mail.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 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 > > --- >  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) > ``` ## Uwe Kleine-König, 2009-06-05 20:25 Subject: Re: [TopGit PATCH] hooks/pre-commit: check for cycles in dependencies Message-ID: <20090605202526.GB671@pengutronix.de> URL: https://gitlist.dev/e/20090605202526.GB671%40pengutronix.de In-Reply-To: <1244148073-2313-1-git-send-email-bert.wesarg@googlemail.com> ``` 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/ | ``` ## Bert Wesarg, 2009-06-08 07:31 Subject: Re: [TopGit PATCH] hooks/pre-commit: check for cycles in dependencies Message-ID: <36ca99e90906080031r3f5f545eo26c077e1966bf67@mail.gmail.com> URL: https://gitlist.dev/e/36ca99e90906080031r3f5f545eo26c077e1966bf67%40mail.gmail.com In-Reply-To: <20090605202526.GB671@pengutronix.de> ``` 2009/6/5 Uwe Kleine-König : > 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/  | > ``` ## Uwe Kleine-König, 2009-06-08 07:44 Subject: TopGit successor Message-ID: <20090608074437.GA12109@pengutronix.de> URL: https://gitlist.dev/e/20090608074437.GA12109%40pengutronix.de In-Reply-To: <36ca99e90906080031r3f5f545eo26c077e1966bf67@mail.gmail.com> ``` 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/ | ```