{"thread":{"id":"25348","subject":"[TopGit PATCH 1/4] provide fan-in and -out traversal interface","startedAt":"2010-10-04T22:28:17Z","lastAt":"2010-10-05T19:31:02Z","messageCount":7,"participants":["Bert Wesarg","Uwe Kleine-König"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"152608","messageId":"1286231300-29268-1-git-send-email-bert.wesarg@googlemail.com","threadId":"25348","inReplyTo":null,"subject":"[TopGit PATCH 1/4] provide fan-in and -out traversal interface","fromName":"Bert Wesarg","fromEmail":"bert.wesarg@googlemail.com","sentAt":"2010-10-04T22:28:17Z","receivedAt":"2010-10-04T22:28:17Z","isPatch":true,"sender":{"key":"bert.wesarg@googlemail.com","avatar":"https://avatars.githubusercontent.com/u/111934?v=4"},"body":"This adds general functions to get the list of all offending branches for\na given one. Either which depends on the given branch (fan-in) or all\ndependencies (fan-out).\n\nTwo simple users are provided which just lists the names or generates dot\ninput.\n\nSigned-off-by: Bert Wesarg <bert.wesarg@googlemail.com>\n\n---\n tg.sh |  170 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n 1 files changed, 170 insertions(+), 0 deletions(-)\n\ndiff --git a/tg.sh b/tg.sh\nindex 3718702..926b31b 100644 tg.sh\n--- a/tg.sh\n+++ b/tg.sh\n@@ -351,6 +351,176 @@ setup_pager()\n \ttrap \"exec >&-; rm \\\"$_pager_fifo\\\"; rmdir \\\"$_pager_fifo_dir\\\"; wait\" EXIT\n }\n \n+# traverse_fan_out(for_each_name, for_each_dep, name, head_deps)\n+#\n+# traverse the dependencies of @name in bfs order and call @for_each_name\n+# on each dep (i.e. node) and @for_each_dep on all dependencies (i.e. edge)\n+# with source and dest as arguments.\n+#\n+# @name' needs to be a TopGit controlled branch\n+#\n+# @head_deps specifies where to take the .topdeps from for the HEAD branch\n+# empty - from the committed tree\n+# '(i)' - from the index\n+# '(w)' - from the working dir\n+#\n+traverse_fan_out()\n+{\n+\tlocal for_each_name=$1\n+\tlocal for_each_dep=$2\n+\tlocal name=$3\n+\tlocal head_deps=$4 || :\n+\tlocal deps_src\n+\tlocal head=\"$(git symbolic-ref HEAD | sed 's#^refs/\\(heads\\|top-bases\\)/##')\" || :\n+\n+\tbranchq=\"$(mktemp -t tg-fan-out.XXXXXX)\"\n+\tallbranches=\"$(mktemp -t -d tg-fan-out-all.XXXXXX)\"\n+\ttrap \"rm -rf \\\"$branchq\\\" \\\"$allbranches\\\"\" 0\n+\n+\t# fill queue with root name\n+\techo \"$name\" > \"$branchq\"\n+\n+\twhile [ -s \"$branchq\" ]; do\n+\t\t# dequeue\n+\t\t{\n+\t\t\tread name\n+\t\t\tcat > \"$branchq.headless\"\n+\t\t} < \"$branchq\"\n+\t\tmv -f \"$branchq.headless\" \"$branchq\"\n+\n+\t\t# eval name\n+\t\teval \"$for_each_name \\\"$name\\\"\"\n+\n+\t\t# don't travers non-tgish branches\n+\t\tref_exists \"refs/top-bases/$name\" ||\n+\t\t\tcontinue\n+\n+\t\tdeps_src=$name\n+\t\t# select .topdeps source for HEAD branch\n+\t\t[ \"x$name\" = \"x$head\" -a -n \"$head_deps\" ] &&\n+\t\t\tdeps_src=$head_deps\n+\n+\t\told_IFS=\"$IFS\"\n+\t\tIFS=\"\"\n+\t\tcat_file \"$deps_src:.topdeps\" |\n+\t\twhile read dep; do\n+\n+\t\t\t# eval dep\n+\t\t\teval \"$for_each_dep \\\"$name\\\" \\\"$dep\\\"\"\n+\n+\t\t\t[ -d \"$allbranches/$dep\" ] || {\n+\t\t\t\tmkdir -p \"$allbranches/$dep\"\n+\t\t\t\techo \"$dep\" >> \"$branchq\"\n+\t\t\t}\n+\t\tdone\n+\t\tIFS=\"$old_IFS\"\n+\n+\tdone\n+}\n+\n+_graph_dep_edge()\n+{\n+\tprintf \"\\t\\\"%s\\\" -> \\\"%s\\\";\\n\" \"$1\" \"$2\"\n+}\n+\n+# prints the fan-out as a dot graph with edges\n+graph_fan_out()\n+{\n+\tprintf \"digraph G {\\n\"\n+\n+\ttraverse_fan_out : _graph_dep_edge \"$1\" $2\n+\n+\tprintf \"}\\n\"\n+}\n+\n+# prints the fan-out as name per line\n+list_fan_out()\n+{\n+\ttraverse_fan_out echo : \"$1\" $2\n+}\n+\n+# traverse_fan_in(for_each_name, for_each_dep, name, head_deps)\n+#\n+# traverse all branches which depends on @name in bfs order and call\n+# @for_each_name on each (i.e. node) and @for_each_dep on all dependencies\n+# (i.e. edge) with source and dest as arguments.\n+#\n+# @name' needs not to be a TopGit controlled branch\n+#\n+# @head_deps specifies where to take the .topdeps from for the HEAD branch\n+# empty - from the committed tree\n+# '(i)' - from the index\n+# '(w)' - from the working dir\n+#\n+traverse_fan_in()\n+{\n+\tlocal for_each_name=$1\n+\tlocal for_each_dep=$2\n+\tlocal name=$3\n+\tlocal head_deps=$4 || :\n+\tlocal deps_src\n+\tlocal head=\"$(git symbolic-ref HEAD | sed 's#^refs/\\(heads\\|top-bases\\)/##')\" || :\n+\n+\tbranchq=\"$(mktemp -t tg-fan-in.XXXXXX)\"\n+\tallbranches=\"$(mktemp -t -d tg-fan-in-all.XXXXXX)\"\n+\ttrap \"rm -rf \\\"$branchq\\\" \\\"$allbranches\\\"\" 0\n+\n+\techo \"$name\" > \"$branchq\"\n+\n+\twhile [ -s \"$branchq\" ]; do\n+\t\t# dequeue\n+\t\t{\n+\t\t\tread name\n+\t\t\tcat > \"$branchq.headless\"\n+\t\t} < \"$branchq\"\n+\t\tmv -f \"$branchq.headless\" \"$branchq\"\n+\n+\t\t[ ! -d \"$allbranches/$name\" ] ||\n+\t\t\tcontinue;\n+\t\tmkdir -p \"$allbranches/$name\"\n+\n+\t\t# eval branch\n+\t\teval \"$for_each_name \\\"$name\\\"\"\n+\n+\t\told_IFS=\"$IFS\"\n+\t\tIFS=\"\"\n+\t\tgit for-each-ref --format='%(refname)' refs/top-bases |\n+\t\t\twhile read ref; do\n+\t\t\t\tparent=\"${ref#refs/top-bases/}\"\n+\n+\t\t\t\tdeps_src=$parent\n+\t\t\t\t# select branch/index/worktree for HEAD branch\n+\t\t\t\t[ \"x$parent\" = \"x$head\" -a -n \"$head_deps\" ] &&\n+\t\t\t\t\tdeps_src=$head_deps\n+\t\t\t\tcat_file \"$deps_src:.topdeps\" | fgrep -qx \"$name\" ||\n+\t\t\t\t\tcontinue\n+\n+\t\t\t\t# eval dep\n+\t\t\t\teval \"$for_each_dep \\\"$parent\\\" \\\"$name\\\"\"\n+\n+\t\t\t\techo \"$parent\" >> \"$branchq\"\n+\t\t\tdone\n+\t\tIFS=\"$old_IFS\"\n+\n+\tdone\n+}\n+\n+# prints the fan-in as a dot graph with edges\n+graph_fan_in()\n+{\n+\tprintf \"digraph G {\\n\"\n+\n+\ttraverse_fan_in : _graph_dep_edge \"$1\" $2\n+\n+\tprintf \"}\\n\"\n+}\n+\n+# prints the fan-in as name per line\n+list_fan_in()\n+{\n+\ttraverse_fan_in echo : \"$1\" $2\n+}\n+\n ## Startup\n \n [ -d \"@cmddir@\" ] ||\n-- \ntg: (ff59ac7..) bw/fan-in-out (depends on: master)\n"},{"id":"152609","messageId":"1286231300-29268-2-git-send-email-bert.wesarg@googlemail.com","threadId":"25348","inReplyTo":"1286231300-29268-1-git-send-email-bert.wesarg@googlemail.com","subject":"[TopGit PATCH 2/4] tg-depend: reduce: apply transitive reduction to the dependecies","fromName":"Bert Wesarg","fromEmail":"bert.wesarg@googlemail.com","sentAt":"2010-10-04T22:28:18Z","receivedAt":"2010-10-04T22:28:18Z","isPatch":true,"sender":{"key":"bert.wesarg@googlemail.com","avatar":"https://avatars.githubusercontent.com/u/111934?v=4"},"body":"This uses the tred(1) and gvpr(1) programs from the graphviz package to reduce\nthe dependencies of the given TopGit branch.\n\nIt provides a also a new subcommand (tg tred) to play with it.\n\nSigned-off-by: Bert Wesarg <bert.wesarg@googlemail.com>\n---\n\n .gitignore                 |    2 +\n README                     |   42 +++++++++++++++++-\n contrib/tg-completion.bash |   36 ++++++++++++++--\n tg-depend.sh               |  103 +++++++++++++++++++++++++++++--------------\n tg-tred.sh                 |   53 ++++++++++++++++++++++\n 5 files changed, 196 insertions(+), 40 deletions(-)\n\ndiff --git a/.gitignore b/.gitignore\nindex 3298889..290cfdc 100644 .gitignore\n--- a/.gitignore\n+++ b/.gitignore\n@@ -38,5 +38,7 @@\n /tg-remote.txt\n /tg-summary\n /tg-summary.txt\n+/tg-tred\n+/tg-tred.txt\n /tg-update\n /tg-update.txt\ndiff --git a/README b/README\nindex ce0c3a6..4f49015 100644 README\n--- a/README\n+++ b/README\n@@ -260,8 +260,8 @@ tg delete\n tg depend\n ~~~~~~~~~\n \tChange dependencies of a TopGit-controlled topic branch.\n-\tThis should have several subcommands, but only 'add' is\n-\tsupported right now.\n+\tThis should have several subcommands, but only 'add' and\n+\t'reduce' is supported right now.\n \n \tThe 'add' subcommand takes an argument of a topic branch\n \tto be added, adds it to '.topdeps', performs a commit and\n@@ -270,6 +270,9 @@ tg depend\n \tadjusting '.topmsg', prepare them in the index before\n \tcalling 'tg depend add'.\n \n+\tThe 'reduce' subcommand uses 'tg tred' to reduce the dependency\n+\tlist of the current.\n+\n \tTODO: Subcommand for removing dependencies, obviously\n \n tg info\n@@ -528,6 +531,41 @@ tg log\n ~~~~~~\n \tPrints the git log of the named topgit branch.\n \n+tg tred\n+~~~~~~~\n+\tPrints the transitive reduction of the dependecies for the current\n+\tor named TopGit branch.\n+\n+\tTo actually use this reduced dependency list, feed the output into\n+\tthe .topdeps file, commit and run tg update, like:\n+\n+\t$ tg tred > .topdeps\n+\t$ git add -f .topdeps\n+\t$ git commit -m \"transitive reduced TopGit dependencies\"\n+\t$ tg update\n+\n+\tIf you want to see the differences to the current dependencies, run\n+\tthis:\n+\n+\t# against HEAD\n+\t$ diff -u -L current -L tred <(git show HEAD:.topdeps) <(tg tred)\n+\n+\t# against the index\n+\t$ diff -u -L current -L tred <(git show     :.topdeps) <(tg tred -i)\n+\n+\t# against the working dir\n+\t$ diff -u -L current -L tred <(cat           .topdeps) <(tg tred -w)\n+\n+\tTo see the reduced dependency graph of all topics run this:\n+\n+\t$ diff -u -L current -L tred \\\n+\t\t<(tg summary --graphviz | nop) \\\n+\t\t<(tg summary --graphviz | tred)\n+\n+\tTODO: tg tred -a for reducing all branches\n+\tTODO: tg tred -r for reducing recursive all from the current/named\n+\t      branch\n+\n TODO: tg rename\n \n \ndiff --git a/contrib/tg-completion.bash b/contrib/tg-completion.bash\nindex ccf1a32..026b9fd 100755 contrib/tg-completion.bash\n--- a/contrib/tg-completion.bash\n+++ b/contrib/tg-completion.bash\n@@ -267,16 +267,27 @@ _tg_delete ()\n \n _tg_depend ()\n {\n-\tlocal subcommands=\"add\"\n+\tlocal cur=\"${COMP_WORDS[COMP_CWORD]}\"\n+\n+\tlocal subcommands=\"add reduce\"\n \tlocal subcommand=\"$(__git_find_subcommand \"$subcommands\")\"\n \tif [ -z \"$subcommand\" ]; then\n \t\t__tgcomp \"$subcommands\"\n \t\treturn\n \tfi\n \n-\tcase \"$subcommand\" in\n-\tadd)\n-\t\t__tgcomp \"$(__tg_refs)\"\n+\tcase \"$subcommand:$cur\" in\n+\tadd:-*)\n+\t\t__tgcomp \"\n+\t\t\t--stage-only\n+\t\t\";;\n+\tadd:*)\n+\t\t__tgcomp \"$(__tg_refs)\";;\n+\treduce:-*)\n+\t\t__tgcomp \"\n+\t\t\t--stage-only\n+\t\t\t--staged\n+\t\t\";;\n \tesac\n }\n \n@@ -431,6 +442,22 @@ _tg_summary ()\n \tesac\n }\n \n+_tg_tred ()\n+{\n+\tlocal cur=\"${COMP_WORDS[COMP_CWORD]}\"\n+\n+\tcase \"$cur\" in\n+\t-*)\n+\t\t__tgcomp \"\n+\t\t\t-i\n+\t\t\t-w\n+\t\t\"\n+\t\t;;\n+\t*)\n+\t\t__tgcomp \"$(__tg_topics)\"\n+\tesac\n+}\n+\n _tg_update ()\n {\n \tlocal cur=\"${COMP_WORDS[COMP_CWORD]}\"\n@@ -491,6 +518,7 @@ _tg ()\n \tpush)        _tg_push ;;\n \tremote)      _tg_remote ;;\n \tsummary)     _tg_summary ;;\n+\ttred)        _tg_tred ;;\n \tupdate)      _tg_update ;;\n \t*)           COMPREPLY=() ;;\n \tesac\ndiff --git a/tg-depend.sh b/tg-depend.sh\nindex 474ccda..413cde2 100644 tg-depend.sh\n--- a/tg-depend.sh\n+++ b/tg-depend.sh\n@@ -3,53 +3,51 @@\n # (c) Petr Baudis <pasky@suse.cz>  2008\n # GPLv2\n \n-name=\n-\n-\n usage()\n {\n-    echo \"Usage: tg [...] depend add NAME\" >&2\n-    exit 1\n+\techo \"Usage: tg [...] depend add    [--stage-only] NAME\" >&2\n+\techo \"   or: tg [...] depend reduce [--stage-only] [--staged]\" >&2\n+\texit 1\n }\n \n-## Parse options\n-\n+## Get command\n subcmd=\"$1\"; shift || :\n case \"$subcmd\" in\n \t-h|\"\")\n \t\tusage;;\n-\tadd)\n+\tadd|reduce)\n \t\t;;\n \t*)\n \t\tdie \"unknown subcommand ($subcmd)\";;\n esac\n \n-while [ -n \"$1\" ]; do\n-\targ=\"$1\"; shift\n-\tcase \"$arg\" in\n-\t-*)\n-\t\tusage;;\n-\t*)\n-\t\t[ -z \"$name\" ] || die \"name already specified ($name)\"\n-\t\tname=\"$arg\";;\n-\tesac\n-done\n-\n-\n-## Sanity checks\n-\n-[ -n \"$name\" ] || die \"no branch name specified\"\n-branchrev=\"$(git rev-parse --verify \"$name\" 2>/dev/null)\" ||\n-\tdie \"invalid branch name: $name\"\n-\n-# Check that we are on a TopGit branch.\n-current_name=\"$(git symbolic-ref HEAD | sed 's#^refs/\\(heads\\|top-bases\\)/##')\"\n-current_base_rev=\"$(git rev-parse --short --verify \"refs/top-bases/$current_name\" 2>/dev/null)\" ||\n-\tdie \"not a TopGit-controlled branch\"\n-\n ## Record new dependency\n depend_add()\n {\n+\tlocal name=\n+\tlocal do_commit=true\n+\n+\t## Parse options\n+\n+\twhile [ -n \"$1\" ]; do\n+\t\targ=\"$1\"; shift\n+\t\tcase \"$arg\" in\n+\t\t--stage-only)\n+\t\t\tdo_commit=false;;\n+\t\t-*)\n+\t\t\tusage;;\n+\t\t*)\n+\t\t\t[ -z \"$name\" ] || die \"name already specified ($name)\"\n+\t\t\tname=\"$arg\";;\n+\t\tesac\n+\tdone\n+\n+\t## Sanity checks\n+\n+\t[ -n \"$name\" ] || die \"no branch name specified\"\n+\tbranchrev=\"$(git rev-parse --verify \"$name\" 2>/dev/null)\" ||\n+\t\tdie \"invalid branch name: $name\"\n+\n \t[ \"$name\" = \"$current_name\" ] &&\n \t\tdie \"$name cannot depend on itself.\"\n \n@@ -62,10 +60,47 @@ depend_add()\n \n \techo \"$name\" >>\"$root_dir/.topdeps\"\n \tgit add -f \"$root_dir/.topdeps\"\n-\tgit commit -m\"New TopGit dependency: $name\"\n-\t$tg update\n+\t$do_commit && {\n+\t\tgit commit -m\"New TopGit dependency: $name\"\n+\t\t$tg update\n+\t} ||\n+\t\techo \"New TopGit dependency: $name\" >> \"$git_dir/PREPARE_COMMIT_MSG\"\n+}\n+\n+## Reduce dependencies\n+depend_reduce()\n+{\n+\tlocal do_commit=true\n+\tlocal tred_mode=\n+\n+\t## Parse options\n+\n+\twhile [ -n \"$1\" ]; do\n+\t\targ=\"$1\"; shift\n+\t\tcase \"$arg\" in\n+\t\t--stage-only)\n+\t\t\tdo_commit=false;;\n+\t\t--staged)\n+\t\t\ttred_mode=-i;;\n+\t\t*)\n+\t\t\tusage;;\n+\t\tesac\n+\tdone\n+\n+\t$tg tred $tred_mode >\"$root_dir/.topdeps\"\n+\tgit add -f \"$root_dir/.topdeps\"\n+\t$do_commit && {\n+\t\tgit commit -m\"transitive reduced TopGit dependencies\"\n+\t\t$tg update\n+\t} ||\n+\t\techo \"transitive reduced TopGit dependencies\" >> \"$git_dir/PREPARE_COMMIT_MSG\"\n }\n \n-depend_$subcmd\n+# Check that we are on a TopGit branch.\n+current_name=\"$(git symbolic-ref HEAD | sed 's#^refs/\\(heads\\|top-bases\\)/##')\"\n+current_base_rev=\"$(git rev-parse --short --verify \"refs/top-bases/$current_name\" 2>/dev/null)\" ||\n+\tdie \"not a TopGit-controlled branch\"\n+\n+depend_$subcmd \"$@\"\n \n # vim:noet\ndiff --git a/tg-tred.sh b/tg-tred.sh\nnew file mode 100644\nindex 0000000..577bc26 tg-tred.sh\n--- /dev/null\n+++ b/tg-tred.sh\n@@ -0,0 +1,53 @@\n+#!/bin/sh\n+# TopGit - A different patch queue manager\n+# (c) Petr Baudis <pasky@suse.cz>              2008\n+# (c) Bert Wesarg <bert.wesarg@googlemail.com> 2009\n+# GPLv2\n+\n+name=\n+topic=\n+\n+\n+## Parse options\n+\n+while [ -n \"$1\" ]; do\n+\targ=\"$1\"; shift\n+\tcase \"$arg\" in\n+\t-i)\n+\t\ttopic='(i)';;\n+\t-w)\n+\t\ttopic='(w)';;\n+\t-*)\n+\t\techo \"Usage: tg [...] tred [-i | -w] [NAME]\" >&2\n+\t\texit 1;;\n+\t*)\n+\t\t[ -z \"$name\" ] || die \"name already specified ($name)\"\n+\t\tname=\"$arg\";;\n+\tesac\n+done\n+\n+[ -n \"$name\" ] || name=\"$(git symbolic-ref HEAD | sed 's#^refs/\\(heads\\|top-bases\\)/##')\"\n+base_rev=\"$(git rev-parse --short --verify \"refs/top-bases/$name\" 2>/dev/null)\" ||\n+\tdie \"not a TopGit-controlled branch\"\n+\n+type tred >/dev/null 2>&1 ||\n+\tdie \"need the tred(1) tool from the graphviz package\"\n+type gvpr >/dev/null 2>&1 ||\n+\tdie \"need the gvpr(1) tool from the graphviz package\"\n+\n+graph_fan_out \"$name\" $topic |\n+\ttred |\n+\tgvpr -a \"\\\"${name}\\\"\" '\n+BEG_G {\n+    node_t n;\n+    edge_t e;\n+\n+    n = isNode($, ARGV[0]);\n+    if (n == NULL) {\n+        printf(2, \"tg tred: %s is not a known branch\", ARGV[0]);\n+        exit(1);\n+    }\n+    for (e = fstout(n); e; e = nxtout(e))\n+        printf(\"%s\\n\", e.head.name);\n+}\n+'\n-- \ntg: (06b6e18..) bw/tred (depends on: bw/fan-in-out)\n"},{"id":"152610","messageId":"1286231300-29268-3-git-send-email-bert.wesarg@googlemail.com","threadId":"25348","inReplyTo":"1286231300-29268-2-git-send-email-bert.wesarg@googlemail.com","subject":"[TopGit PATCH 3/4] tg-prev/tg-next: --all option","fromName":"Bert Wesarg","fromEmail":"bert.wesarg@googlemail.com","sentAt":"2010-10-04T22:28:19Z","receivedAt":"2010-10-04T22:28:19Z","isPatch":true,"sender":{"key":"bert.wesarg@googlemail.com","avatar":"https://avatars.githubusercontent.com/u/111934?v=4"},"body":"This adds an --all option to tg-prev and tg-next, to show all offenders.\n\nSigned-off-by: Bert Wesarg <bert.wesarg@googlemail.com>\n\n\n---\n\nNote the dependency on bw/tred is only historical, it depends only bw/fan-in-out.\n\n README                     |    2 ++\n contrib/tg-completion.bash |    2 ++\n tg-next.sh                 |   11 ++++++++++-\n tg-prev.sh                 |   11 ++++++++++-\n 4 files changed, 24 insertions(+), 2 deletions(-)\n\ndiff --git a/README b/README\nindex 49f7b10..b1dc45a 100644 README\n--- a/README\n+++ b/README\n@@ -573,6 +573,7 @@ tg prev\n \tOptions:\n \t  -i\t\tshow dependencies based on index instead of branch\n \t  -w\t\tshow dependencies based on working tree instead of branch\n+\t --all\t\tshow not only the direct but all dependencies\n \n tg next\n ~~~~~~~\n@@ -582,6 +583,7 @@ tg next\n \tOptions:\n \t  -i\t\tshow dependencies based on index instead of branch\n \t  -w\t\tshow dependencies based on working tree instead of branch\n+\t --all\t\tshow not only the direct but all dependencies\n \n TODO: tg rename\n \ndiff --git a/contrib/tg-completion.bash b/contrib/tg-completion.bash\nindex d319828..d18f564 100755 contrib/tg-completion.bash\n--- a/contrib/tg-completion.bash\n+++ b/contrib/tg-completion.bash\n@@ -475,6 +475,7 @@ _tg_next ()\n \tcase \"$cur\" in\n \t-*)\n \t\t__tgcomp \"\n+\t\t\t--all\n \t\t\t-i\n \t\t\t-w\n \t\t\"\n@@ -491,6 +492,7 @@ _tg_prev ()\n \tcase \"$cur\" in\n \t-*)\n \t\t__tgcomp \"\n+\t\t\t--all\n \t\t\t-i\n \t\t\t-w\n \t\t\"\ndiff --git a/tg-next.sh b/tg-next.sh\nindex 9b352b3..abb9a53 100644 tg-next.sh\n--- a/tg-next.sh\n+++ b/tg-next.sh\n@@ -5,6 +5,7 @@\n # GPLv2\n \n name=\n+all=false\n head_deps=\n \n \n@@ -17,8 +18,10 @@ while [ -n \"$1\" ]; do\n \t\thead_deps='(i)';;\n \t-w)\n \t\thead_deps='(w)';;\n+\t--all)\n+\t\tall=true;;\n \t-*)\n-\t\techo \"Usage: tg next [-i | -w] [NAME]\" >&2\n+\t\techo \"Usage: tg next [--all] [-i | -w] [NAME]\" >&2\n \t\texit 1;;\n \t*)\n \t\t[ -z \"$name\" ] || die \"name already specified ($name)\"\n@@ -29,6 +32,12 @@ done\n head=\"$(git symbolic-ref HEAD | sed 's#^refs/\\(heads\\|top-bases\\)/##')\"\n [ -n \"$name\" ] || name=$head\n \n+if $all; then\n+\t# ignore first line, which is $name\n+\tlist_fan_in \"$name\" $head_deps | tail --lines=+2\n+\texit $?\n+fi\n+\n git for-each-ref --format='%(refname)' refs/top-bases |\n \twhile read ref; do\n \t\tparent=\"${ref#refs/top-bases/}\"\ndiff --git a/tg-prev.sh b/tg-prev.sh\nindex efef410..63f71bd 100644 tg-prev.sh\n--- a/tg-prev.sh\n+++ b/tg-prev.sh\n@@ -5,6 +5,7 @@\n # GPLv2\n \n name=\n+all=false\n head_deps=\n \n \n@@ -17,8 +18,10 @@ while [ -n \"$1\" ]; do\n \t\thead_deps='(i)';;\n \t-w)\n \t\thead_deps='(w)';;\n+\t--all)\n+\t\tall=true;;\n \t-*)\n-\t\techo \"Usage: tg next [-i | -w] [NAME]\" >&2\n+\t\techo \"Usage: tg next [--all] [-i | -w] [NAME]\" >&2\n \t\texit 1;;\n \t*)\n \t\t[ -z \"$name\" ] || die \"name already specified ($name)\"\n@@ -31,6 +34,12 @@ head=\"$(git symbolic-ref HEAD | sed 's#^refs/\\(heads\\|top-bases\\)/##')\"\n base_rev=\"$(git rev-parse --short --verify \"refs/top-bases/$name\" 2>/dev/null)\" ||\n \tdie \"not a TopGit-controlled branch\"\n \n+if $all; then\n+\t# ignore first line, which is $name\n+\tlist_fan_out \"$name\" $head_deps | tail --lines=+2\n+\texit $?\n+fi\n+\n deps_src=$name\n # select .topdeps source for HEAD branch\n [ \"x$name\" = \"x$head\" -a -n \"$head_deps\" ] &&\n-- \ntg: (bf1dfaa..) bw/next-prev (depends on: bw/tred bw/next-prev-base)\n"},{"id":"152611","messageId":"1286231300-29268-4-git-send-email-bert.wesarg@googlemail.com","threadId":"25348","inReplyTo":"1286231300-29268-3-git-send-email-bert.wesarg@googlemail.com","subject":"[TopGit PATCH v4 4/4] tg-graph: print dependency graph like git log --graph","fromName":"Bert Wesarg","fromEmail":"bert.wesarg@googlemail.com","sentAt":"2010-10-04T22:28:20Z","receivedAt":"2010-10-04T22:28:20Z","isPatch":true,"sender":{"key":"bert.wesarg@googlemail.com","avatar":"https://avatars.githubusercontent.com/u/111934?v=4"},"body":"Just want to send it out again. I'm not pushing this for 0.9.\n\nThe graph engine comes from the git projects graph.c file, which was written by\nAdam Simpkins.\n\nThanks,\nBert\n\nSigned-off-by: Bert Wesarg <bert.wesarg@googlemail.com>\n\n---\n\nNote the dependency on bw/tred is only historical, it depends only bw/fan-in-out.\n\nChangeLog:\n v4:\n   * --fan-in and --fan-out option\n   * --subject option\n   * color tips dep chain on other color\n\n v3:\n   * option to ignore tip-topics\n\n v2:\n   * fix rename bug which caused random segfaults in gvpr\n   * add --decorate option, to print horizontal line from graph node to patch\n     name (like gitk do it for commits with tags or branch decorations)\n   * in dfs mode we should maintain the order given by the input\n   * make dfs mode the default\n\n .gitignore                 |    2 +\n Makefile                   |    1 +\n README                     |    7 +\n contrib/tg-completion.bash |   37 ++\n share/graph.gvpr           | 1100 ++++++++++++++++++++++++++++++++++++++++++++\n tg-graph.sh                |  108 +++++\n tg-summary.sh              |   37 ++-\n tg.sh                      |   64 +++-\n 8 files changed, 1344 insertions(+), 12 deletions(-)\n\ndiff --git a/.gitignore b/.gitignore\nindex 290cfdc..b79ab0e 100644 .gitignore\n--- a/.gitignore\n+++ b/.gitignore\n@@ -22,6 +22,8 @@\n /tg-depend.txt\n /tg-export\n /tg-export.txt\n+/tg-graph\n+/tg-graph.txt\n /tg-import\n /tg-import.txt\n /tg-info\ndiff --git a/Makefile b/Makefile\nindex 3ce39a5..0de1277 100644 Makefile\n--- a/Makefile\n+++ b/Makefile\n@@ -38,6 +38,7 @@ install:: all\n \tinstall $(hooks_out) \"$(DESTDIR)$(hooksdir)\"\n \tinstall -d -m 755 \"$(DESTDIR)$(sharedir)\"\n \tinstall -m 644 $(help_out) \"$(DESTDIR)$(sharedir)\"\n+\tinstall -m 644 share/graph.gvpr \"$(DESTDIR)$(sharedir)\"\n \n clean::\n \trm -f tg $(commands_out) $(hooks_out) $(help_out)\ndiff --git a/README b/README\nindex 4f49015..3ba8c35 100644 README\n--- a/README\n+++ b/README\n@@ -566,6 +566,13 @@ tg tred\n \tTODO: tg tred -r for reducing recursive all from the current/named\n \t      branch\n \n+tg graph\n+~~~~~~~~\n+\tPrints the dependency graph like git log --graph to the console.\n+\n+\tTODO: document options\n+\tTODO: -i/-w options\n+\n TODO: tg rename\n \n \ndiff --git a/contrib/tg-completion.bash b/contrib/tg-completion.bash\nindex 026b9fd..d8e3e02 100755 contrib/tg-completion.bash\n--- a/contrib/tg-completion.bash\n+++ b/contrib/tg-completion.bash\n@@ -313,6 +313,38 @@ _tg_export ()\n \tesac\n }\n \n+_tg_graph ()\n+{\n+\tlocal cur=\"${COMP_WORDS[COMP_CWORD]}\"\n+\n+\tcase \"$cur\" in\n+\t-*)\n+\t\t__tgcomp \"\n+\t\t\t--fan-out\n+\t\t\t--fan-in\n+\t\t\t--color\n+\t\t\t--no-color\n+\t\t\t--bfs\n+\t\t\t--dfs\n+\t\t\t--reverse\n+\t\t\t--no-reverse\n+\t\t\t--subject\n+\t\t\t--no-subject\n+\t\t\t--header\n+\t\t\t--no-header\n+\t\t\t--body\n+\t\t\t--no-body\n+\t\t\t--decorate\n+\t\t\t--no-decorate\n+\t\t\t--ignore-tips\n+\t\t\t--no-ignore-tips\n+\t\t\"\n+\t\t;;\n+\t*)\n+\t\t__tgcomp \"$(__tg_refs)\"\n+\tesac\n+}\n+\n _tg_help ()\n {\n \tlocal cur=\"${COMP_WORDS[COMP_CWORD]}\"\n@@ -434,9 +466,13 @@ _tg_summary ()\n \tlocal cur=\"${COMP_WORDS[COMP_CWORD]}\"\n \n \tcase \"$cur\" in\n+\t--graphviz=*)\n+\t\t__tgcomp \"verbose\" \"\" \"${cur##--graphviz=}\"\n+\t\t;;\n \t*)\n \t\t__tgcomp \"\n \t\t\t--graphviz\n+\t\t\t--graphviz=\n \t\t\t-t\n \t\t\"\n \tesac\n@@ -509,6 +545,7 @@ _tg ()\n \tdelete)      _tg_delete ;;\n \tdepend)      _tg_depend ;;\n \texport)      _tg_export ;;\n+\tgraph)       _tg_graph ;;\n \thelp)        _tg_help ;;\n \timport)      _tg_import ;;\n \tinfo)        _tg_info ;;\ndiff --git a/share/graph.gvpr b/share/graph.gvpr\nnew file mode 100755\nindex 0000000..457ff0b share/graph.gvpr\n--- /dev/null\n+++ b/share/graph.gvpr\n@@ -0,0 +1,1100 @@\n+BEGIN {\n+    int use_stack = 1;\n+    int use_color = 1;\n+    int rev_order = 0;\n+    int use_subject = 0;\n+    int show_header = 0;\n+    int show_body = 0;\n+    int point_at_node = 0;\n+    int ignore_tips = 0;\n+\n+    int argi;\n+    for (argi = 0; argi < ARGC; argi++) {\n+        if      (ARGV[argi] == \"color\")\n+            use_color = 1;\n+        else if (ARGV[argi] == \"no-color\")\n+            use_color = 0;\n+        else if (ARGV[argi] == \"stack\")\n+            use_stack = 1;\n+        else if (ARGV[argi] == \"no-stack\")\n+            use_stack = 0;\n+        else if (ARGV[argi] == \"reverse\")\n+            rev_order = 1;\n+        else if (ARGV[argi] == \"no-reverse\")\n+            rev_order = 0;\n+        else if (ARGV[argi] == \"subject\")\n+            use_subject = 1;\n+        else if (ARGV[argi] == \"no-subject\")\n+            use_subject = 0;\n+        else if (ARGV[argi] == \"header\")\n+            show_header = 1;\n+        else if (ARGV[argi] == \"no-header\")\n+            show_header = 0;\n+        else if (ARGV[argi] == \"body\")\n+            show_body = 1;\n+        else if (ARGV[argi] == \"no-body\")\n+            show_body = 0;\n+        else if (ARGV[argi] == \"pointer\")\n+            point_at_node = 1;\n+        else if (ARGV[argi] == \"no-pointer\")\n+            point_at_node = 0;\n+        else if (ARGV[argi] == \"ignore-tips\")\n+            ignore_tips = 1;\n+        else if (ARGV[argi] == \"no-ignore-tips\")\n+            ignore_tips = 0;\n+    }\n+\n+    edge_t first_edge(node_t fe_n)\n+    {\n+        edge_t fe;\n+\n+        if (!rev_order) {\n+            fe = fstout(fe_n);\n+        } else {\n+            fe = fstin(fe_n);\n+        }\n+\n+        return fe;\n+    }\n+\n+    edge_t next_edge(edge_t ne_e)\n+    {\n+        edge_t ne;\n+\n+        if (!rev_order) {\n+            ne = nxtout(ne_e);\n+        } else {\n+            ne = nxtin(ne_e);\n+        }\n+\n+        return ne;\n+    }\n+\n+    node_t adj_node(edge_t an_e)\n+    {\n+        node_t an;\n+\n+        if (!rev_order) {\n+            an = an_e.head;\n+        } else {\n+            an = an_e.tail;\n+        }\n+\n+        return an;\n+    }\n+\n+    int node_deg(node_t nd_n)\n+    {\n+        int nd;\n+\n+        if (!rev_order) {\n+            nd = nd_n.indegree;\n+        } else {\n+            nd = nd_n.outdegree;\n+        }\n+\n+        return nd;\n+    }\n+\n+    int node_num_parents(node_t nnp_n)\n+    {\n+        int nnp;\n+\n+        if (!rev_order) {\n+            nnp = nnp_n.outdegree;\n+        } else {\n+            nnp = nnp_n.indegree;\n+        }\n+\n+        return nnp;\n+    }\n+\n+    void assert(int assert_a) {\n+        if (!assert_a)\n+            exit(1);\n+    }\n+\n+    /* enum graph_state */\n+    int GRAPH_PADDING    = 0;\n+    int GRAPH_SKIP       = 1;\n+    int GRAPH_PRE_COMMIT = 2;\n+    int GRAPH_COMMIT     = 3;\n+    int GRAPH_POST_MERGE = 4;\n+    int GRAPH_COLLAPSING = 5;\n+\n+    /*\n+     * The list of available column colors.\n+     */\n+    string GIT_COLOR_NORMAL     = \"\";\n+    string GIT_COLOR_RESET      = \"\\033[m\";\n+    string GIT_COLOR_BOLD       = \"\\033[1m\";\n+    string GIT_COLOR_RED        = \"\\033[31m\";\n+    string GIT_COLOR_GREEN      = \"\\033[32m\";\n+    string GIT_COLOR_YELLOW     = \"\\033[33m\";\n+    string GIT_COLOR_BLUE       = \"\\033[34m\";\n+    string GIT_COLOR_MAGENTA    = \"\\033[35m\";\n+    string GIT_COLOR_CYAN       = \"\\033[36m\";\n+    string GIT_COLOR_BG_RED     = \"\\033[41m\";\n+\n+    string gg_column_colors[];\n+    gg_column_colors[ 0] = GIT_COLOR_RED;\n+    gg_column_colors[ 1] = GIT_COLOR_GREEN;\n+    gg_column_colors[ 2] = GIT_COLOR_YELLOW;\n+    gg_column_colors[ 3] = GIT_COLOR_BLUE;\n+    gg_column_colors[ 4] = GIT_COLOR_MAGENTA;\n+    gg_column_colors[ 5] = GIT_COLOR_CYAN;\n+    gg_column_colors[ 6] = GIT_COLOR_BOLD + GIT_COLOR_RED;\n+    gg_column_colors[ 7] = GIT_COLOR_BOLD + GIT_COLOR_GREEN;\n+    gg_column_colors[ 8] = GIT_COLOR_BOLD + GIT_COLOR_YELLOW;\n+    gg_column_colors[ 9] = GIT_COLOR_BOLD + GIT_COLOR_BLUE;\n+    gg_column_colors[10] = GIT_COLOR_BOLD + GIT_COLOR_MAGENTA;\n+    gg_column_colors[11] = GIT_COLOR_BOLD + GIT_COLOR_CYAN;\n+    int COLUMN_COLORS_MAX = 12;\n+\n+    /*\n+     * The node currently being processed\n+     */\n+    node_t gg_n;\n+    /*\n+     * The number of interesting parents that this commit has.\n+     */\n+    int gg_num_parents;\n+    /*\n+     * The width of the graph output for this commit.\n+     * All rows for this commit are padded to this width, so that\n+     * messages printed after the graph output are aligned.\n+     */\n+    int gg_width;\n+    /*\n+     * The next expansion row to print\n+     * when state is GRAPH_PRE_COMMIT\n+     */\n+    int gg_expansion_row;\n+    /*\n+     * The current output state.\n+     * This tells us what kind of line graph_next_line() should output.\n+     */\n+    int gg_state;\n+    /*\n+     * The output state for the previous line of output.\n+     * This is primarily used to determine how the first merge line\n+     * should appear, based on the last line of the previous commit.\n+     */\n+    int gg_prev_state;\n+    /*\n+     * The index of the column that refers to this commit.\n+     *\n+     * If none of the incoming columns refer to this commit,\n+     * this will be equal to num_columns.\n+     */\n+    int gg_n_index;\n+    /*\n+     * The commit_index for the previously displayed commit.\n+     *\n+     * This is used to determine how the first line of a merge\n+     * graph output should appear, based on the last line of the\n+     * previous commit.\n+     */\n+    int gg_prev_n_index;\n+    /*\n+     * The number of columns (also called \"branch lines\" in some places)\n+     */\n+    int gg_num_columns;\n+    /*\n+     * The number of columns in the new_columns array\n+     */\n+    int gg_num_new_columns;\n+    /*\n+     * The number of entries in the mapping array\n+     */\n+    int gg_mapping_size;\n+    /*\n+     * The column state before we output the current commit.\n+     */\n+    node_t gg_columns[];\n+    /*\n+     * The new column state after we output the current commit.\n+     * Only valid when state is GRAPH_COLLAPSING.\n+     */\n+    node_t gg_new_columns[];\n+    /*\n+     * An array that tracks the current state of each\n+     * character in the output line during state GRAPH_COLLAPSING.\n+     * Each entry is -1 if this character is empty, or a non-negative\n+     * integer if the character contains a branch line.  The value of\n+     * the integer indicates the target position for this branch line.\n+     * (I.e., this array maps the current column positions to their\n+     * desired positions.)\n+     *\n+     * The maximum capacity of this array is always\n+     * sizeof(int) * 2 * column_capacity.\n+     */\n+    int gg_mapping[];\n+    /*\n+     * A temporary array for computing the next mapping state\n+     * while we are outputting a mapping line.  This is stored as part\n+     * of the git_graph simply so we dont have to allocate a new\n+     * temporary array each time we have to output a collapsing line.\n+     */\n+    int gg_new_mapping[];\n+    /*\n+     * The current default column color being used.  This is\n+     * stored as an index into the array column_colors.\n+     */\n+    unsigned gg_default_column_color;\n+\n+    string gg_write_column(node_t gg_wc_n, string gg_wc_col_char)\n+    {\n+        assert(gg_wc_n);\n+        return gg_wc_n.col_color + gg_wc_col_char + gg_wc_n.col_color_end;\n+    }\n+\n+    void graph_set_current_column_color(node_t gg_ccc_n)\n+    {\n+        if (!use_color) {\n+            gg_ccc_n.col_color     = \"\";\n+            gg_ccc_n.col_color_end = \"\";\n+        } else {\n+            gg_ccc_n.col_color     = gg_column_colors[gg_default_column_color];\n+            gg_ccc_n.col_color_end = GIT_COLOR_RESET;\n+        }\n+    }\n+\n+    /*\n+     * Update the graph's default column color.\n+     */\n+    void graph_increment_column_color(void)\n+    {\n+        gg_default_column_color = (gg_default_column_color + 1) %\n+                COLUMN_COLORS_MAX;\n+    }\n+\n+    void graph_set_commit_color(node_t gg_scc_n)\n+    {\n+        if (gg_scc_n.need_col_color == \"yes\")\n+            graph_set_current_column_color(gg_scc_n);\n+        gg_scc_n.need_col_color = \"no\";\n+    }\n+\n+    int graph_insert_into_new_columns(node_t gg_iinc_n, int gg_iinc_mapping_index)\n+    {\n+        int gg_iinc_i;\n+\n+        /*\n+         * If the commit is already in the new_columns list, we do not need to\n+         * add it.  Just update the mapping correctly.\n+         */\n+        for (gg_iinc_i = 0; gg_iinc_i < gg_num_new_columns; gg_iinc_i++) {\n+            if (gg_new_columns[gg_iinc_i] == gg_iinc_n) {\n+                gg_mapping[gg_iinc_mapping_index] = gg_iinc_i;\n+                return gg_iinc_mapping_index + 2;\n+            }\n+        }\n+\n+        /*\n+         * This commit is not already in new_columns.  Add it.\n+         */\n+        gg_new_columns[gg_num_new_columns] = gg_iinc_n;\n+        graph_set_commit_color(gg_iinc_n);\n+        gg_mapping[gg_iinc_mapping_index] = gg_num_new_columns;\n+        gg_num_new_columns++;\n+\n+        return gg_iinc_mapping_index + 2;\n+    }\n+\n+    void graph_update_width(int gg_uw_is_commit_in_existing_columns)\n+    {\n+        /*\n+         * Compute the width needed to display the graph for this commit.\n+         * This is the maximum width needed for any row.  All other rows\n+         * will be padded to this width.\n+         *\n+         * Compute the number of columns in the widest row:\n+         * Count each existing column (gg_num_columns), and each new\n+         * column added by this commit.\n+         */\n+        int gg_uw_max_cols = gg_num_columns + gg_num_parents;\n+\n+        /*\n+         * Even if the current commit has no parents to be printed, it\n+         * still takes up a column for itself.\n+         */\n+        if (gg_num_parents < 1)\n+            gg_uw_max_cols++;\n+\n+        /*\n+         * We added a column for the the current commit as part of\n+         * gg_num_parents.  If the current commit was already in\n+         * gg_columns, then we have double counted it.\n+         */\n+        if (gg_uw_is_commit_in_existing_columns)\n+            gg_uw_max_cols--;\n+\n+        /*\n+         * Each column takes up 2 spaces\n+         */\n+        gg_width = gg_uw_max_cols * 2;\n+    }\n+\n+    void graph_update_columns(void)\n+    {\n+        edge_t gg_uc_e;\n+        int gg_uc_mapping_idx;\n+        int gg_uc_i, gg_uc_seen_this, gg_uc_is_commit_in_columns;\n+\n+        /*\n+         * Swap gg_columns with gg_new_columns\n+         * gg_columns contains the state for the previous commit,\n+         * and new_columns now contains the state for our commit.\n+         */\n+        for (gg_uc_i = 0; gg_uc_i < gg_num_new_columns; gg_uc_i++)\n+            gg_columns[gg_uc_i] = gg_new_columns[gg_uc_i];\n+        gg_num_columns = gg_num_new_columns;\n+        gg_num_new_columns = 0;\n+\n+        /*\n+         * Clear out gg_mapping\n+         */\n+        gg_mapping_size = 2 * (gg_num_columns + gg_num_parents);\n+        for (gg_uc_i = 0; gg_uc_i < gg_mapping_size; gg_uc_i++)\n+            gg_mapping[gg_uc_i] = -1;\n+\n+        /*\n+         * Populate gg_new_columns and gg_mapping\n+         *\n+         * Some of the parents of this commit may already be in\n+         * gg_columns.  If so, gg_new_columns should only contain a\n+         * single entry for each such commit.  gg_mapping should\n+         * contain information about where each current branch line is\n+         * supposed to end up after the collapsing is performed.\n+         */\n+        gg_uc_seen_this = 0;\n+        gg_uc_mapping_idx = 0;\n+        gg_uc_is_commit_in_columns = 1;\n+        for (gg_uc_i = 0; gg_uc_i <= gg_num_columns; gg_uc_i++) {\n+            node_t gg_uc_col_n;\n+\n+            if (gg_uc_i == gg_num_columns) {\n+                if (gg_uc_seen_this)\n+                    break;\n+                gg_uc_is_commit_in_columns = 0;\n+                gg_uc_col_n = gg_n;\n+            } else {\n+                gg_uc_col_n = gg_columns[gg_uc_i];\n+            }\n+\n+            if (gg_uc_col_n == gg_n) {\n+                int gg_uc_old_mapping_idx = gg_uc_mapping_idx;\n+                gg_uc_seen_this = 1;\n+                gg_n_index = gg_uc_i;\n+                for (gg_uc_e = first_edge(gg_n); gg_uc_e; gg_uc_e = next_edge(gg_uc_e)) {\n+                    /*\n+                     * If this is a merge increment the current\n+                     * color.\n+                     */\n+                    if (gg_num_parents > 1)\n+                             graph_increment_column_color();\n+\n+                    gg_uc_mapping_idx = graph_insert_into_new_columns(\n+                            adj_node(gg_uc_e), gg_uc_mapping_idx);\n+                }\n+                /*\n+                 * We always need to increment mapping_idx by at\n+                 * least 2, even if it has no interesting parents.\n+                 * The current commit always takes up at least 2\n+                 * spaces.\n+                 */\n+                if (gg_uc_mapping_idx == gg_uc_old_mapping_idx)\n+                    gg_uc_mapping_idx += 2;\n+            } else {\n+                gg_uc_mapping_idx = graph_insert_into_new_columns(gg_uc_col_n,\n+                        gg_uc_mapping_idx);\n+            }\n+        }\n+\n+        /*\n+         * Shrink mapping_size to be the minimum necessary\n+         */\n+        while (gg_mapping_size > 1 &&\n+               gg_mapping[gg_mapping_size - 1] < 0)\n+            gg_mapping_size--;\n+\n+        /*\n+         * Compute gg_width for this commit\n+         */\n+        graph_update_width(gg_uc_is_commit_in_columns);\n+    }\n+\n+    void graph_update_state(int gg_us_s)\n+    {\n+        gg_prev_state = gg_state;\n+        gg_state = gg_us_s;\n+    }\n+\n+    void graph_update(node_t gg_u_n) {\n+        gg_n = gg_u_n;\n+        gg_num_parents = node_num_parents(gg_u_n);\n+        gg_prev_n_index = gg_n_index;\n+        graph_update_columns();\n+        gg_expansion_row = 0;\n+        if (gg_state != GRAPH_PADDING)\n+            gg_state = GRAPH_SKIP;\n+        else if (gg_num_parents >= 3 &&\n+                 gg_n_index < (gg_num_columns - 1))\n+            gg_state = GRAPH_PRE_COMMIT;\n+        else\n+            gg_state = GRAPH_COMMIT;\n+    }\n+\n+    string graph_pad_horizontally(int gg_ph_chars_written)\n+    {\n+        int gg_ph_extra, gg_ph_i;\n+        string gg_ph_sb = \"\";\n+\n+        if (gg_ph_chars_written >= gg_width)\n+            return gg_ph_sb;\n+\n+        gg_ph_extra = gg_width - gg_ph_chars_written;\n+        for (gg_ph_i = 0; gg_ph_i < gg_ph_extra; gg_ph_i++)\n+            gg_ph_sb += \" \";\n+\n+        return gg_ph_sb;\n+    }\n+\n+    string graph_output_padding_line(void)\n+    {\n+        int gg_opl_i;\n+        string gg_opl_sb = \"\";\n+\n+        for (gg_opl_i = 0; gg_opl_i < gg_num_new_columns; gg_opl_i++) {\n+            gg_opl_sb += gg_write_column(gg_new_columns[gg_opl_i], \"|\");\n+            gg_opl_sb += \" \";\n+        }\n+\n+        gg_opl_sb += graph_pad_horizontally(gg_num_new_columns * 2);\n+\n+        return gg_opl_sb;\n+    }\n+\n+    string graph_output_skip_line(void)\n+    {\n+        string gg_osl_sb = \"\";\n+        /*\n+         * Output an ellipsis to indicate that a portion\n+         * of the graph is missing.\n+         */\n+        gg_osl_sb += \"...\";\n+        gg_osl_sb += graph_pad_horizontally(3);\n+\n+        if (gg_num_parents >= 3 && gg_n_index < (gg_num_columns - 1))\n+            graph_update_state(GRAPH_PRE_COMMIT);\n+        else\n+            graph_update_state(GRAPH_COMMIT);\n+\n+        return gg_osl_sb;\n+    }\n+\n+    string graph_output_pre_commit_line(void)\n+    {\n+        int gg_opcl_num_expansion_rows;\n+        int gg_opcl_i, gg_opcl_j, gg_opcl_seen_this;\n+        int gg_opcl_chars_written;\n+        string gg_opcl_sb = \"\";\n+\n+        /*\n+         * This function formats a row that increases the space around a commit\n+         * with multiple parents, to make room for it.  It should only be\n+         * called when there are 3 or more parents.\n+         *\n+         * We need 2 extra rows for every parent over 2.\n+         */\n+        assert(gg_num_parents >= 3);\n+        gg_opcl_num_expansion_rows = (gg_num_parents - 2) * 2;\n+\n+        /*\n+         * gg_expansion_row tracks the current expansion row we are on.\n+         * It should be in the range [0, gg_opcl_num_expansion_rows - 1]\n+         */\n+        assert(0 <= gg_expansion_row &&\n+               gg_expansion_row < gg_opcl_num_expansion_rows);\n+\n+        /*\n+         * Output the row\n+         */\n+        gg_opcl_seen_this = 0;\n+        gg_opcl_chars_written = 0;\n+        for (gg_opcl_i = 0; gg_opcl_i < gg_num_columns; gg_opcl_i++) {\n+            if (gg_columns[gg_opcl_i] == gg_n) {\n+                gg_opcl_seen_this = 1;\n+                gg_opcl_sb += gg_write_column(gg_columns[gg_opcl_i], \"|\");\n+                for (gg_opcl_j = 0; gg_opcl_j < gg_expansion_row; gg_opcl_j++)\n+                    gg_opcl_sb += \" \";\n+                gg_opcl_chars_written += 1 + gg_expansion_row;\n+            } else if (gg_opcl_seen_this && (gg_expansion_row == 0)) {\n+                /*\n+                 * This is the first line of the pre-commit output.\n+                 * If the previous commit was a merge commit and\n+                 * ended in the GRAPH_POST_MERGE state, all branch\n+                 * lines after gg_prev_commit_index were\n+                 * printed as \"\\\" on the previous line.  Continue\n+                 * to print them as \"\\\" on this line.  Otherwise,\n+                 * print the branch lines as \"|\".\n+                 */\n+                if (gg_prev_state == GRAPH_POST_MERGE &&\n+                    gg_prev_n_index < gg_opcl_i)\n+                    gg_opcl_sb += gg_write_column(gg_columns[gg_opcl_i], \"\\\\\");\n+                else\n+                    gg_opcl_sb += gg_write_column(gg_columns[gg_opcl_i], \"|\");\n+                gg_opcl_chars_written++;\n+            } else if (gg_opcl_seen_this && (gg_expansion_row > 0)) {\n+                gg_opcl_sb += gg_write_column(gg_columns[gg_opcl_i], \"\\\\\");\n+                gg_opcl_chars_written++;\n+            } else {\n+                gg_opcl_sb += gg_write_column(gg_columns[gg_opcl_i], \"|\");\n+                gg_opcl_chars_written++;\n+            }\n+            gg_opcl_sb += \" \";\n+            gg_opcl_chars_written++;\n+        }\n+\n+        gg_opcl_sb += graph_pad_horizontally(gg_opcl_chars_written);\n+\n+        /*\n+         * Increment gg_expansion_row,\n+         * and move to state GRAPH_COMMIT if necessary\n+         */\n+        gg_expansion_row++;\n+        if (gg_expansion_row >= gg_opcl_num_expansion_rows)\n+            graph_update_state(GRAPH_COMMIT);\n+\n+        return gg_opcl_sb;\n+    }\n+\n+    /*\n+     * Here dashless_commits represents the number of parents\n+     * which do not need to have dashes (because their edges fit\n+     * neatly under the commit).\n+     */\n+    int gg_dom_dashless_commits = 2;\n+    int graph_draw_octopus_merge_width(void)\n+    {\n+        return ((gg_num_parents - gg_dom_dashless_commits) * 2);\n+    }\n+\n+    string graph_draw_octopus_merge(void)\n+    {\n+        int gg_dom_i;\n+        int gg_dom_col_num;\n+        string gg_dom_sb = \"\";\n+        int gg_dom_num_dashes = graph_draw_octopus_merge_width() - 1;\n+\n+        for (gg_dom_i = 0; gg_dom_i < gg_dom_num_dashes; gg_dom_i++) {\n+            gg_dom_col_num = (gg_dom_i / 2) + gg_dom_dashless_commits;\n+            gg_dom_sb += gg_write_column(gg_new_columns[gg_dom_col_num], \"-\");\n+        }\n+        gg_dom_col_num = (gg_dom_i / 2) + gg_dom_dashless_commits;\n+        gg_dom_sb += gg_write_column(gg_new_columns[gg_dom_col_num], \".\");\n+\n+        return gg_dom_sb;\n+    }\n+\n+    int graph_is_mapping_correct(void)\n+    {\n+        int gg_imc_i;\n+\n+        /*\n+         * The mapping is up to date if each entry is at its target,\n+         * or is 1 greater than its target.\n+         * (If it is 1 greater than the target, '/' will be printed, so it\n+         * will look correct on the next row.)\n+         */\n+        for (gg_imc_i = 0; gg_imc_i < gg_mapping_size; gg_imc_i++) {\n+            int gg_imc_target = gg_mapping[gg_imc_i];\n+            if (gg_imc_target < 0)\n+                continue;\n+            if (gg_imc_target == (gg_imc_i / 2))\n+                continue;\n+            return 0;\n+        }\n+\n+        return 1;\n+    }\n+\n+    string graph_output_commit_line(void)\n+    {\n+        int gg_ocl_seen_this = 0;\n+        int gg_ocl_i, gg_ocl_chars_written;\n+        string gg_ocl_sb = \"\";\n+\n+        /*\n+         * Output the row containing this commit\n+         * Iterate up to and including gg_num_columns,\n+         * since the current commit may not be in any of the existing\n+         * columns.  (This happens when the current commit does not have any\n+         * children that we have already processed.)\n+         */\n+        gg_ocl_seen_this = 0;\n+        gg_ocl_chars_written = 0;\n+        for (gg_ocl_i = 0; gg_ocl_i <= gg_num_columns; gg_ocl_i++) {\n+            node_t gg_ocl_n;\n+\n+            if (gg_ocl_i == gg_num_columns) {\n+                if (gg_ocl_seen_this)\n+                    break;\n+                gg_ocl_n = gg_n;\n+                gg_ocl_seen_this = 1;\n+            } else {\n+                gg_ocl_n = gg_columns[gg_ocl_i];\n+            }\n+\n+            if (gg_ocl_n == gg_n) {\n+                gg_ocl_seen_this = 1;\n+                gg_ocl_sb += \"*\";\n+                gg_ocl_chars_written++;\n+\n+                if (gg_num_parents > 2) {\n+                    gg_ocl_sb            += graph_draw_octopus_merge();\n+                    gg_ocl_chars_written += graph_draw_octopus_merge_width();\n+                }\n+            } else if (gg_ocl_seen_this && (gg_num_parents > 2)) {\n+                gg_ocl_sb += gg_write_column(gg_columns[gg_ocl_i], \"\\\\\");\n+                gg_ocl_chars_written++;\n+            } else if (gg_ocl_seen_this && (gg_num_parents == 2)) {\n+                /*\n+                 * This is a 2-way merge commit.\n+                 * There is no GRAPH_PRE_COMMIT stage for 2-way\n+                 * merges, so this is the first line of output\n+                 * for this commit.  Check to see what the previous\n+                 * line of output was.\n+                 */\n+                if (gg_prev_state == GRAPH_POST_MERGE &&\n+                    gg_prev_n_index < gg_ocl_i)\n+                    gg_ocl_sb += gg_write_column(gg_columns[gg_ocl_i], \"\\\\\");\n+                else\n+                    gg_ocl_sb += gg_write_column(gg_columns[gg_ocl_i], \"|\");\n+                gg_ocl_chars_written++;\n+            } else {\n+                gg_ocl_sb += gg_write_column(gg_columns[gg_ocl_i], \"|\");\n+                gg_ocl_chars_written++;\n+            }\n+            if (point_at_node && gg_ocl_seen_this)\n+                gg_ocl_sb += \"-\";\n+            else\n+                gg_ocl_sb += \" \";\n+            gg_ocl_chars_written++;\n+        }\n+\n+        gg_ocl_sb += graph_pad_horizontally(gg_ocl_chars_written);\n+\n+        /*\n+         * Update gg_state\n+         */\n+        if (gg_num_parents > 1)\n+            graph_update_state(GRAPH_POST_MERGE);\n+        else if (graph_is_mapping_correct())\n+            graph_update_state(GRAPH_PADDING);\n+        else\n+            graph_update_state(GRAPH_COLLAPSING);\n+\n+        return gg_ocl_sb;\n+    }\n+\n+    string graph_output_post_merge_line(void)\n+    {\n+        int gg_opml_seen_this = 0;\n+        int gg_opml_i, gg_opml_j, gg_opml_chars_written;\n+        string gg_opml_sb = \"\";\n+\n+        /*\n+         * Output the post-merge row\n+         */\n+        gg_opml_chars_written = 0;\n+        for (gg_opml_i = 0; gg_opml_i <= gg_num_columns; gg_opml_i++) {\n+            node_t gg_opml_col_n;\n+\n+            if (gg_opml_i == gg_num_columns) {\n+                if (gg_opml_seen_this)\n+                    break;\n+                gg_opml_col_n = gg_n;\n+            } else {\n+                gg_opml_col_n = gg_columns[gg_opml_i];\n+            }\n+\n+            if (gg_opml_col_n == gg_n) {\n+                edge_t gg_opml_edge;\n+                node_t gg_opml_par_column;\n+                /*\n+                 * Since the current commit is a merge find\n+                 * the columns for the parent commits in\n+                 * new_columns and use those to format the\n+                 * edges.\n+                 */\n+                gg_opml_seen_this = 1;\n+\n+                gg_opml_edge = first_edge(gg_n);\n+                gg_opml_par_column = adj_node(gg_opml_edge);\n+\n+                gg_opml_sb += gg_write_column(gg_opml_par_column, \"|\");\n+                gg_opml_chars_written++;\n+                for (gg_opml_j = 0; gg_opml_j < gg_num_parents - 1; gg_opml_j++) {\n+                    gg_opml_edge = next_edge(gg_opml_edge);\n+                    gg_opml_par_column = adj_node(gg_opml_edge);\n+                    gg_opml_sb += gg_write_column(gg_opml_par_column, \"\\\\\");\n+                    gg_opml_sb += \" \";\n+                }\n+                gg_opml_chars_written += gg_opml_j * 2;\n+\n+            } else if (gg_opml_seen_this) {\n+                gg_opml_sb += gg_write_column(gg_columns[gg_opml_i], \"\\\\\");\n+                gg_opml_sb += \" \";\n+                gg_opml_chars_written += 2;\n+\n+            } else {\n+                gg_opml_sb += gg_write_column(gg_columns[gg_opml_i], \"|\");\n+                gg_opml_sb += \" \";\n+                gg_opml_chars_written += 2;\n+            }\n+        }\n+\n+        gg_opml_sb += graph_pad_horizontally(gg_opml_chars_written);\n+\n+        /*\n+         * Update gg_state\n+         */\n+        if (graph_is_mapping_correct())\n+            graph_update_state(GRAPH_PADDING);\n+        else\n+            graph_update_state(GRAPH_COLLAPSING);\n+\n+        return gg_opml_sb;\n+    }\n+\n+    string graph_output_collapsing_line(void)\n+    {\n+        int gg_oCl_i;\n+        int gg_oCl_target;\n+        int gg_oCl_used_horizontal = 0;\n+        int gg_oCl_horizontal_edge = -1;\n+        int gg_oCl_horizontal_edge_target = -1;\n+        string gg_oCl_sb = \"\";\n+\n+        /*\n+         * Clear out the new_mapping array\n+         */\n+        for (gg_oCl_i = 0; gg_oCl_i < gg_mapping_size; gg_oCl_i++)\n+            gg_new_mapping[gg_oCl_i] = -1;\n+\n+        for (gg_oCl_i = 0; gg_oCl_i < gg_mapping_size; gg_oCl_i++) {\n+            gg_oCl_target = gg_mapping[gg_oCl_i];\n+            if (gg_oCl_target < 0)\n+                continue;\n+\n+            /*\n+             * Since update_columns() always inserts the leftmost\n+             * column first, each branch's target location should\n+             * always be either its current location or to the left of\n+             * its current location.\n+             *\n+             * We never have to move branches to the right.  This makes\n+             * the graph much more legible, since whenever branches\n+             * cross, only one is moving directions.\n+             */\n+            assert(gg_oCl_target * 2 <= gg_oCl_i);\n+\n+            if (gg_oCl_target * 2 == gg_oCl_i) {\n+                /*\n+                 * This column is already in the\n+                 * correct place\n+                 */\n+                assert(gg_new_mapping[gg_oCl_i] == -1);\n+                gg_new_mapping[gg_oCl_i] = gg_oCl_target;\n+            } else if (gg_new_mapping[gg_oCl_i - 1] < 0) {\n+                /*\n+                 * Nothing is to the left.\n+                 * Move to the left by one\n+                 */\n+                gg_new_mapping[gg_oCl_i - 1] = gg_oCl_target;\n+                /*\n+                 * If there isn't already an edge moving horizontally\n+                 * select this one.\n+                 */\n+                if (gg_oCl_horizontal_edge == -1) {\n+                        int gg_oCl_j;\n+                        gg_oCl_horizontal_edge = gg_oCl_i;\n+                        gg_oCl_horizontal_edge_target = gg_oCl_target;\n+                        /*\n+                         * The variable target is the index of the graph\n+                         * column, and therefore target*2+3 is the\n+                         * actual screen column of the first horizontal\n+                         * line.\n+                         */\n+                        for (gg_oCl_j = (gg_oCl_target * 2) + 3;\n+                             gg_oCl_j < (gg_oCl_i - 2);\n+                             gg_oCl_j += 2)\n+                                gg_new_mapping[gg_oCl_j] = gg_oCl_target;\n+                }\n+            } else if (gg_new_mapping[gg_oCl_i - 1] == gg_oCl_target) {\n+                /*\n+                 * There is a branch line to our left\n+                 * already, and it is our target.  We\n+                 * combine with this line, since we share\n+                 * the same parent commit.\n+                 *\n+                 * We don't have to add anything to the\n+                 * output or new_mapping, since the\n+                 * existing branch line has already taken\n+                 * care of it.\n+                 */\n+            } else {\n+                /*\n+                 * There is a branch line to our left,\n+                 * but it isn't our target.  We need to\n+                 * cross over it.\n+                 *\n+                 * The space just to the left of this\n+                 * branch should always be empty.\n+                 *\n+                 * The branch to the left of that space\n+                 * should be our eventual target.\n+                 */\n+                assert(gg_new_mapping[gg_oCl_i - 1] > gg_oCl_target);\n+                assert(gg_new_mapping[gg_oCl_i - 2] < 0);\n+                assert(gg_new_mapping[gg_oCl_i - 3] == gg_oCl_target);\n+                gg_new_mapping[gg_oCl_i - 2] = gg_oCl_target;\n+                /*\n+                 * Mark this branch as the horizontal edge to\n+                 * prevent any other edges from moving\n+                 * horizontally.\n+                 */\n+                if (gg_oCl_horizontal_edge == -1)\n+                    gg_oCl_horizontal_edge = gg_oCl_i;\n+            }\n+        }\n+\n+        /*\n+         * The new mapping may be 1 smaller than the old mapping\n+         */\n+        if (gg_new_mapping[gg_mapping_size - 1] < 0)\n+            gg_mapping_size--;\n+\n+        /*\n+         * Output out a line based on the new mapping info\n+         */\n+        for (gg_oCl_i = 0; gg_oCl_i < gg_mapping_size; gg_oCl_i++) {\n+            gg_oCl_target = gg_new_mapping[gg_oCl_i];\n+            if (gg_oCl_target < 0)\n+                gg_oCl_sb += \" \";\n+            else if (gg_oCl_target * 2 == gg_oCl_i)\n+                gg_oCl_sb += gg_write_column(gg_new_columns[gg_oCl_target], \"|\");\n+            else if (gg_oCl_target == gg_oCl_horizontal_edge_target &&\n+                     gg_oCl_i != gg_oCl_horizontal_edge - 1) {\n+                /*\n+                 * Set the mappings for all but the\n+                 * first segment to -1 so that they\n+                 * won't continue into the next line.\n+                 */\n+                if (gg_oCl_i != (gg_oCl_target * 2) + 3)\n+                        gg_new_mapping[gg_oCl_i] = -1;\n+                gg_oCl_used_horizontal = 1;\n+                gg_oCl_sb += gg_write_column(gg_new_columns[gg_oCl_target], \"_\");\n+            } else {\n+                if (gg_oCl_used_horizontal && gg_oCl_i < gg_oCl_horizontal_edge)\n+                        gg_new_mapping[gg_oCl_i] = -1;\n+                gg_oCl_sb += gg_write_column(gg_new_columns[gg_oCl_target], \"/\");\n+            }\n+        }\n+\n+        gg_oCl_sb += graph_pad_horizontally(gg_mapping_size);\n+\n+        /*\n+         * Swap mapping and new_mapping\n+         */\n+        for (gg_oCl_i = 0; gg_oCl_i < gg_mapping_size; gg_oCl_i++) {\n+            int gg_oCl_tmp = gg_mapping[gg_oCl_i];\n+            gg_mapping[gg_oCl_i] = gg_new_mapping[gg_oCl_i];\n+            gg_new_mapping[gg_oCl_i] = gg_oCl_tmp;\n+        }\n+\n+        /*\n+         * If gg_mapping indicates that all of the branch lines\n+         * are already in the correct positions, we are done.\n+         * Otherwise, we need to collapse some branch lines together.\n+         */\n+        if (graph_is_mapping_correct())\n+            graph_update_state(GRAPH_PADDING);\n+\n+        return gg_oCl_sb;\n+    }\n+\n+    string graph_next_line(void)\n+    {\n+        string gg_nl_ret = \"\";\n+\n+        if        (gg_state == GRAPH_PADDING) {\n+            gg_nl_ret += graph_output_padding_line();\n+        } else if (gg_state == GRAPH_SKIP) {\n+            gg_nl_ret += graph_output_skip_line();\n+        } else if (gg_state == GRAPH_PRE_COMMIT) {\n+            gg_nl_ret += graph_output_pre_commit_line();\n+        } else if (gg_state == GRAPH_COMMIT) {\n+            gg_nl_ret += graph_output_commit_line();\n+        } else if (gg_state == GRAPH_POST_MERGE) {\n+            gg_nl_ret += graph_output_post_merge_line();\n+        } else if (gg_state == GRAPH_COLLAPSING) {\n+            gg_nl_ret += graph_output_collapsing_line();\n+        }\n+\n+        return gg_nl_ret;\n+    }\n+\n+}\n+BEG_G {\n+    node_t ts_empty_deg[];\n+    int ts_head = 0, ts_tail = 0;\n+    int ts_nedges = 0;\n+    $tvtype = TV_ne;\n+\n+    gg_n = NULL;\n+    gg_num_parents = 0;\n+    gg_width = 0;\n+    gg_expansion_row = 0;\n+    gg_state = GRAPH_PADDING;\n+    gg_prev_state = GRAPH_PADDING;\n+    gg_n_index = 0;\n+    gg_prev_n_index = 0;\n+    gg_num_columns = 0;\n+    gg_num_new_columns = 0;\n+    gg_mapping_size = 0;\n+    gg_default_column_color = 0;\n+}\n+N {\n+    $.ts_deg = node_deg($);\n+    $.tg_tip_deg = node_deg($);\n+    if ((int)$.ts_deg == 0)  {\n+        ts_empty_deg[ts_tail] = $;\n+        ts_tail++;\n+    }\n+    $.need_col_color = \"yes\";\n+    $.tg_in_tips = \"\";\n+}\n+E {\n+    $.ts_deleted = \"false\";\n+}\n+END_G {\n+    int i, j;\n+    node_t switch_node;\n+\n+    /* reverse initial entries to maintain a somewhat stable order */\n+    if (use_stack) {\n+        i = 0;\n+        j = ts_tail - 1;\n+        while (i < j) {\n+            switch_node = ts_empty_deg[i];\n+            ts_empty_deg[i++]  = ts_empty_deg[j];\n+            ts_empty_deg[j--]  = switch_node;\n+        }\n+    }\n+\n+    while (use_stack ? ts_tail > 0 : ts_head < ts_tail) {\n+        string label;\n+        node_t n;\n+        edge_t e;\n+        int lines;\n+        int remove_tip_deps;\n+\n+        if (use_stack) {\n+            n = ts_empty_deg[--ts_tail];\n+        } else {\n+            n = ts_empty_deg[ts_head];\n+            ts_head++;\n+        }\n+\n+        remove_tip_deps = 0;\n+        if (ignore_tips && n.tg_tip_deg == 0 && aget(n, \"tg_is_tip\")) {\n+            remove_tip_deps = 1;\n+        }\n+\n+        if (use_stack)\n+            i = ts_tail;\n+\n+        for (e = first_edge(n); e; e = next_edge(e)) {\n+            if (e.ts_deleted == \"false\") {\n+                node_t d = adj_node(e);\n+\n+                d.ts_deg = (int)d.ts_deg - 1;\n+\n+                if (remove_tip_deps) {\n+                    label = n.name;\n+                    if (aget(n, \"label\")) {\n+                        label = aget(n, \"label\");\n+                    }\n+                    d.tg_tip_deg = (int)d.tg_tip_deg - 1;\n+                    d.tg_in_tips = \" <- \" + label + n.tg_in_tips;\n+                }\n+\n+                if ((int)d.ts_deg == 0)  {\n+                    ts_empty_deg[ts_tail] = d;\n+                    ts_tail++;\n+                }\n+\n+                e.ts_deleted = \"true\";\n+            }\n+        }\n+\n+        /* reverse new entries to maintain a somewhat stable order */\n+        if (use_stack) {\n+            j = ts_tail - 1;\n+            while (i < j) {\n+                switch_node = ts_empty_deg[i];\n+                ts_empty_deg[i++]  = ts_empty_deg[j];\n+                ts_empty_deg[j--]  = switch_node;\n+            }\n+        }\n+\n+        if (remove_tip_deps)\n+            continue;\n+\n+        graph_update(n);\n+\n+        /* print lines till commit line */\n+        while (gg_state != GRAPH_COMMIT) {\n+            printf(\"%s\\n\", graph_next_line());\n+        }\n+\n+        /* print 'commit message'  */\n+        label = n.name;\n+        if (use_subject && aget(n, \"tg_subject\")) {\n+            label = label + \": \" + aget(n, \"tg_subject\");\n+        } else if (aget(n, \"label\")) {\n+            label = aget(n, \"label\");\n+        }\n+        if (use_color) {\n+            printf(\"%s%s%s%s%s%s%s\\n\", graph_next_line(),\n+                                 GIT_COLOR_YELLOW, label, GIT_COLOR_RESET,\n+                                 GIT_COLOR_CYAN, n.tg_in_tips, GIT_COLOR_RESET);\n+        } else {\n+            printf(\"%s%s\\n\", graph_next_line(), label);\n+        }\n+\n+        if (show_header && aget(n, \"tg_header_lines\")) {\n+            lines = aget(n, \"tg_header_lines\");\n+            for (i = 0; i < lines; i++) {\n+                printf(\"%s%s\\n\", graph_next_line(), aget(n, sprintf(\"tg_header_%d\", i)));\n+            }\n+            printf(\"%s\\n\", graph_next_line());\n+        }\n+\n+        if (show_body && aget(n, \"tg_body_lines\")) {\n+            lines = aget(n, \"tg_body_lines\");\n+            for (i = 0; i < lines; i++) {\n+                printf(\"%s    %s\\n\", graph_next_line(), aget(n, sprintf(\"tg_body_%d\", i)));\n+            }\n+            printf(\"%s\\n\", graph_next_line());\n+        }\n+\n+        /* print remaining graph lines */\n+        while (gg_state != GRAPH_PADDING) {\n+            printf(\"%s\\n\", graph_next_line());\n+        }\n+    }\n+}\ndiff --git a/tg-graph.sh b/tg-graph.sh\nnew file mode 100644\nindex 0000000..d013a6f tg-graph.sh\n--- /dev/null\n+++ b/tg-graph.sh\n@@ -0,0 +1,108 @@\n+#!/bin/sh\n+# TopGit - A different patch queue manager\n+# (c) Petr Baudis <pasky@suse.cz>  2008\n+# (c) Bert Wesarg <Bert.Wesarg@googlemail.com>  2009\n+# GPLv2\n+\n+color=\n+do_dfs=false\n+do_bfs=false\n+stack=\n+reverse=\n+subject=\n+header=\n+body=\n+pointer=\n+ignore_tips=\n+graph_mode=full\n+\n+_graph_verbose=\n+\n+# a wrapper around tg summary --graphviz\n+graph_full()\n+{\n+\tlocal summary_graphviz=--graphviz\n+\t[ -z \"$_graph_verbose\" ] ||\n+\t\tsummary_graphviz=--graphviz=verbose\n+\t$tg summary $summary_graphviz | ccomps -x\n+}\n+\n+name=\n+\n+while [ -n \"$1\" ]; do\n+\targ=\"$1\"; shift\n+\tcase \"$arg\" in\n+\t--fan-out)\n+\t\tgraph_mode=fan_out;;\n+\t--fan-in)\n+\t\tgraph_mode=fan_in;;\n+\t--color)\n+\t\tcolor=\"color\";;\n+\t--no-color)\n+\t\tcolor=\"no-color\";;\n+\t--dfs)\n+\t\tdo_dfs=true;;\n+\t--bfs)\n+\t\tdo_bfs=true;;\n+\t--reverse)\n+\t\treverse=\"reverse\";;\n+\t--no-reverse)\n+\t\treverse=\"no-reverse\";;\n+\t--subject)\n+\t\tsubject=\"subject\";;\n+\t--no-subject)\n+\t\tsubject=\"no-subject\";;\n+\t--header)\n+\t\theader=\"header\";;\n+\t--no-header)\n+\t\theader=\"no-header\";;\n+\t--body)\n+\t\tbody=\"body\";;\n+\t--no-body)\n+\t\tbody=\"no-body\";;\n+\t--decorate)\n+\t\tpointer=\"pointer\";;\n+\t--no-decorate)\n+\t\tpointer=\"no-pointer\";;\n+\t--ignore-tips)\n+\t\tignore_tips=\"ignore-tips\";;\n+\t--no-ignore-tips)\n+\t\tignore_tips=\"no-ignore-tips\";;\n+\t-*)\n+\t\techo >&2 \"Usage: tg [...] graph [--color] [--bfs|--dfs] [--reverse] [--ignore-tips]\"\n+\t\techo >&2 \"                      [--header] [--body] [--fan-out | --fan-in] [NAME]\" >&2\n+\t\texit 1;;\n+\t*)\n+\t\t[ -z \"$name\" ] ||\n+\t\t\tdie \"branch already specified ($branch)\"\n+\t\tname=\"$arg\";;\n+\tesac\n+done\n+\n+[ -n \"$name\" ] || name=\"$(git symbolic-ref HEAD | sed 's#^refs/\\(heads\\|top-bases\\)/##')\"\n+\n+[ -r \"@sharedir@\"/graph.gvpr ] || \n+\tdie \"Can't find graph.gvpr file in \\`@sharedir@'\"\n+\n+[ \"$subject$header$body$ignore_tips\" != \"no-subjectno-headerno-bodyno-ignore_tips\" ] &&\n+\t_graph_verbose=1\n+\n+$do_dfs && $do_bfs &&\n+\tdie \"--bfs and --dfs options are mutual exclusive\"\n+$do_bfs && stack=\"no-stack\"\n+$do_dfs && stack=\"stack\"\n+\n+type ccomps >/dev/null 2>&1 ||\n+\tdie \"need the ccomps(1) tool from the graphviz package\"\n+type gvpr >/dev/null 2>&1 ||\n+\tdie \"need the gvpr(1) tool from the graphviz package\"\n+\n+setup_pager\n+\n+# disable color output if pager is not active\n+[ \"x$GIT_PAGER_IN_USE\" = \"x1\" ] ||\n+\tcolor=\"no-color\"\n+\n+graph_$graph_mode \"$name\" |\n+\tgvpr -a \"$color $stack $reverse $subject $header $body $pointer $ignore_tips\" \\\n+\t     -f \"@sharedir@\"/graph.gvpr\ndiff --git a/tg-summary.sh b/tg-summary.sh\nindex af16888..9650c8a 100644 tg-summary.sh\n--- a/tg-summary.sh\n+++ b/tg-summary.sh\n@@ -7,7 +7,7 @@ terse=\n graphviz=\n sort=\n deps=\n-\n+graphviz_verbose=\n \n ## Parse options\n \n@@ -18,6 +18,9 @@ while [ -n \"$1\" ]; do\n \t\tterse=1;;\n \t--graphviz)\n \t\tgraphviz=1;;\n+\t--graphviz=verbose)\n+\t\tgraphviz=1\n+\t\tgraphviz_verbose=1;;\n \t--sort)\n \t\tsort=1;;\n \t--deps)\n@@ -43,13 +46,13 @@ if [ -n \"$graphviz\" ]; then\n \n digraph G {\n \n-graph [\n-  rankdir = \"TB\"\n-  label=\"TopGit Layout\\n\\n\\n\"\n-  fontsize = 14\n-  labelloc=top\n-  pad = \"0.5,0.5\"\n-];\n+\tgraph [\n+\t\trankdir = \"TB\"\n+\t\tlabel=\"TopGit Layout\\n\\n\\n\"\n+\t\tfontsize = 14\n+\t\tlabelloc=top\n+\t\tpad = \"0.5,0.5\"\n+\t];\n \n EOT\n fi\n@@ -121,8 +124,10 @@ git for-each-ref refs/top-bases |\n \t\t\t\tif ! \"$dep_is_tgish\" || ! branch_annihilated $dep; then\n \t\t\t\t\tif [ -n \"$graphviz\" ]; then\n \t\t\t\t\t\techo \"\\\"$name\\\" -> \\\"$dep\\\";\"\n-\t\t\t\t\t\tif [ \"$name\" = \"$curname\" ] || [ \"$dep\" = \"$curname\" ]; then\n-\t\t\t\t\t\t\techo \"\\\"$curname\\\" [style=filled,fillcolor=yellow];\"\n+\t\t\t\t\t\tif [ -z \"$graphviz_verbose\" ]; then\n+\t\t\t\t\t\t\tif [ \"$name\" = \"$curname\" ] || [ \"$dep\" = \"$curname\" ]; then\n+\t\t\t\t\t\t\t\techo \"\\\"$curname\\\" [style=filled,fillcolor=yellow];\"\n+\t\t\t\t\t\t\tfi\n \t\t\t\t\t\tfi\n \t\t\t\t\telse\n \t\t\t\t\t\techo \"$name $dep\" >&4\n@@ -135,6 +140,18 @@ git for-each-ref refs/top-bases |\n \tdone\n \n if [ -n \"$graphviz\" ]; then\n+\t# for-each-ref gives us a sorting order\n+\t# thats why we put the node attributes after the edges\n+\t# to somewhat keep the implied order stabel\n+\t[ -n \"$graphviz_verbose\" ] && {\n+\t\t_graph_topmsg=\"$(mktemp -t tg-summary.XXXXXX)\"\n+\t\ttrap 'rm -f \"$_graph_topmsg\"' 0\n+\t\tgit for-each-ref refs/top-bases |\n+\t\t\twhile read rev type ref; do\n+\t\t\t\tname=\"${ref#refs/top-bases/}\"\n+\t\t\t\t_graph_verbose=1 _graph_dep_branch \"$name\"\n+\t\t\tdone\n+\t}\n \techo '}'\n fi\n \ndiff --git a/tg.sh b/tg.sh\nindex b85fdd7..460ca6c 100644 tg.sh\n--- a/tg.sh\n+++ b/tg.sh\n@@ -418,17 +418,73 @@ traverse_fan_out()\n \tdone\n }\n \n+# uses the global temp file in $_graph_topmsg\n+_graph_dep_branch()\n+{\n+\tlocal name=$1\n+\n+\t[ -n \"$_graph_verbose\" ] ||\n+\t\treturn 0\n+\n+\t# don't travers non-tgish branches\n+\tref_exists \"refs/top-bases/$name\" ||\n+\t\treturn 0\n+\n+\tprintf \"\\t\\\"%s\\\" [\\n\" \"$name\"\n+\n+\tlocal type=\"header\"\n+\tlocal lines=0\n+\n+\t# TODO: honor -i and -w options\n+\tgit cat-file blob \"$name:.topmsg\" > \"$_graph_topmsg\"\n+\n+\tif [ ! -s \"$_graph_topmsg\" ]; then\n+\t\t# short-cut if topic has empty .topmsg\n+\t\tprintf \"\\t\\ttg_is_tip = \\\"true\\\"\\n\"\n+\t\tprintf \"\\t];\\n\"\n+\t\treturn 0\n+\tfi\n+\n+\told_IFS=\"$IFS\"\n+\tIFS=\"\"\n+\twhile read line; do\n+\t\t# escape double-quotes\n+\t\tl=\"$(echo \"$line\" | sed -e 's/\"/\\\\\"/g')\"\n+\t\t[ -z \"$line\" -a \"$type\" = \"header\" ] && {\n+\t\t\ttype=\"body\"\n+\t\t\tprintf \"\\t\\ttg_header_lines = \\\"%s\\\"\\n\" \"$lines\"\n+\t\t\tlines=0\n+\t\t\tcontinue\n+\t\t}\n+\t\tprintf \"\\t\\ttg_%s_%s = \\\"%s\\\"\\n\" \"$type\" \"$lines\" \"$l\"\n+\t\tlines=`expr $lines + 1`\n+\tdone < \"$_graph_topmsg\"\n+\tIFS=\"$old_IFS\"\n+\n+\t[ $lines -gt 0 ] &&\n+\t\tprintf \"\\t\\ttg_%s_lines = \\\"%s\\\"\\n\" \"$type\" \"$lines\"\n+\n+\t# extract subject\n+\tsed -n -e 's/^Subject: \\(.*\\)$/\t\ttg_subject = \"\\1\"/g p' < \"$_graph_topmsg\"\n+\n+\tprintf \"\\t];\\n\"\n+}\n+\n _graph_dep_edge()\n {\n \tprintf \"\\t\\\"%s\\\" -> \\\"%s\\\";\\n\" \"$1\" \"$2\"\n }\n \n # prints the fan-out as a dot graph with edges\n+# set $_graph_verbose to get verbose branch infos in node attributes\n graph_fan_out()\n {\n \tprintf \"digraph G {\\n\"\n \n-\ttraverse_fan_out : _graph_dep_edge \"$1\" $2\n+\t_graph_topmsg=\"$(mktemp -t tg-summary.XXXXXX)\"\n+\ttrap 'rm -f \"$_graph_topmsg\"' 0\n+\n+\ttraverse_fan_out _graph_dep_branch _graph_dep_edge \"$1\" $2\n \n \tprintf \"}\\n\"\n }\n@@ -506,11 +562,15 @@ traverse_fan_in()\n }\n \n # prints the fan-in as a dot graph with edges\n+# set $_graph_verbose to get verbose branch infos in node attributes\n graph_fan_in()\n {\n \tprintf \"digraph G {\\n\"\n \n-\ttraverse_fan_in : _graph_dep_edge \"$1\" $2\n+\t_graph_topmsg=\"$(mktemp -t tg-summary.XXXXXX)\"\n+\ttrap 'rm -f \"$_graph_topmsg\"' 0\n+\n+\ttraverse_fan_in _graph_dep_branch _graph_dep_edge \"$1\" $2\n \n \tprintf \"}\\n\"\n }\n-- \ntg: (73b09ef..) bw/graph (depends on: bw/fix-echo_-e-in-dash bw/tred)\n"},{"id":"152644","messageId":"20101005071334.GF11737@pengutronix.de","threadId":"25348","inReplyTo":"1286231300-29268-1-git-send-email-bert.wesarg@googlemail.com","subject":"Re: [TopGit PATCH 1/4] provide fan-in and -out traversal interface","fromName":"Uwe Kleine-König","fromEmail":"u.kleine-koenig@pengutronix.de","sentAt":"2010-10-05T07:13:34Z","receivedAt":"2010-10-05T07:13:34Z","isPatch":true,"sender":{"key":"u.kleine-koenig@pengutronix.de","avatar":"https://gravatar.com/avatar/354b5e3ceb2806a2f1e1e382ac29ddbdad18288654da62b61eb13583a857eee7?d=mp&s=160"},"body":"On Tue, Oct 05, 2010 at 12:28:17AM +0200, Bert Wesarg wrote:\n> This adds general functions to get the list of all offending branches for\nIs offending the right word here?  I don't understand that.\n\n> a given one. Either which depends on the given branch (fan-in) or all\n> dependencies (fan-out).\n> \n> Two simple users are provided which just lists the names or generates dot\n> input.\nThis should then be used for tg summary --graphviz, too, doesn't it?\n\n> \n> Signed-off-by: Bert Wesarg <bert.wesarg@googlemail.com>\n> \n> ---\n>  tg.sh |  170 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n>  1 files changed, 170 insertions(+), 0 deletions(-)\n> \n> diff --git a/tg.sh b/tg.sh\n> index 3718702..926b31b 100644 tg.sh\n> --- a/tg.sh\n> +++ b/tg.sh\n> @@ -351,6 +351,176 @@ setup_pager()\n>  \ttrap \"exec >&-; rm \\\"$_pager_fifo\\\"; rmdir \\\"$_pager_fifo_dir\\\"; wait\" EXIT\n>  }\n>  \n> +# traverse_fan_out(for_each_name, for_each_dep, name, head_deps)\nThis uses an unusual format.\n\nplease make it\n\n# traverse_fan_out FOR_EACH_NAME FOR_EACH_DEP NAME HEAD_DEPS\n\n> +#\n> +# traverse the dependencies of @name in bfs order and call @for_each_name\n> +# on each dep (i.e. node) and @for_each_dep on all dependencies (i.e. edge)\n> +# with source and dest as arguments.\n> +#\n> +# @name' needs to be a TopGit controlled branch\n> +#\n> +# @head_deps specifies where to take the .topdeps from for the HEAD branch\n> +# empty - from the committed tree\n> +# '(i)' - from the index\n> +# '(w)' - from the working dir\n> +#\n> +traverse_fan_out()\n> +{\n> +\tlocal for_each_name=$1\n> +\tlocal for_each_dep=$2\n> +\tlocal name=$3\n> +\tlocal head_deps=$4 || :\n> +\tlocal deps_src\n> +\tlocal head=\"$(git symbolic-ref HEAD | sed 's#^refs/\\(heads\\|top-bases\\)/##')\" || :\nI don't remember the exact problems, but some shells get using local and\nassignment in a single command wrong.  Can you please fix that up?  (I\nfixed that up for one of your commits.)\n\n> +\n> +\tbranchq=\"$(mktemp -t tg-fan-out.XXXXXX)\"\n> +\tallbranches=\"$(mktemp -t -d tg-fan-out-all.XXXXXX)\"\n> +\ttrap \"rm -rf \\\"$branchq\\\" \\\"$allbranches\\\"\" 0\n> +\n> +\t# fill queue with root name\n> +\techo \"$name\" > \"$branchq\"\n> +\n> +\twhile [ -s \"$branchq\" ]; do\n> +\t\t# dequeue\n> +\t\t{\n> +\t\t\tread name\n> +\t\t\tcat > \"$branchq.headless\"\n> +\t\t} < \"$branchq\"\n> +\t\tmv -f \"$branchq.headless\" \"$branchq\"\n> +\n> +\t\t# eval name\n> +\t\teval \"$for_each_name \\\"$name\\\"\"\n> +\n> +\t\t# don't travers non-tgish branches\n> +\t\tref_exists \"refs/top-bases/$name\" ||\n> +\t\t\tcontinue\n> +\n> +\t\tdeps_src=$name\n> +\t\t# select .topdeps source for HEAD branch\n> +\t\t[ \"x$name\" = \"x$head\" -a -n \"$head_deps\" ] &&\n> +\t\t\tdeps_src=$head_deps\n> +\n> +\t\told_IFS=\"$IFS\"\n> +\t\tIFS=\"\"\n> +\t\tcat_file \"$deps_src:.topdeps\" |\n> +\t\twhile read dep; do\n> +\n> +\t\t\t# eval dep\n> +\t\t\teval \"$for_each_dep \\\"$name\\\" \\\"$dep\\\"\"\n> +\n> +\t\t\t[ -d \"$allbranches/$dep\" ] || {\n> +\t\t\t\tmkdir -p \"$allbranches/$dep\"\n> +\t\t\t\techo \"$dep\" >> \"$branchq\"\n> +\t\t\t}\n> +\t\tdone\n> +\t\tIFS=\"$old_IFS\"\n> +\n> +\tdone\n> +}\n> +\n> +_graph_dep_edge()\n> +{\n> +\tprintf \"\\t\\\"%s\\\" -> \\\"%s\\\";\\n\" \"$1\" \"$2\"\n> +}\n> +\n> +# prints the fan-out as a dot graph with edges\n> +graph_fan_out()\n> +{\n> +\tprintf \"digraph G {\\n\"\n> +\n> +\ttraverse_fan_out : _graph_dep_edge \"$1\" $2\n> +\n> +\tprintf \"}\\n\"\n> +}\n> +\n> +# prints the fan-out as name per line\n> +list_fan_out()\n> +{\n> +\ttraverse_fan_out echo : \"$1\" $2\n> +}\n> +\n> +# traverse_fan_in(for_each_name, for_each_dep, name, head_deps)\n> +#\n> +# traverse all branches which depends on @name in bfs order and call\n> +# @for_each_name on each (i.e. node) and @for_each_dep on all dependencies\n> +# (i.e. edge) with source and dest as arguments.\n> +#\n> +# @name' needs not to be a TopGit controlled branch\n> +#\n> +# @head_deps specifies where to take the .topdeps from for the HEAD branch\n> +# empty - from the committed tree\n> +# '(i)' - from the index\n> +# '(w)' - from the working dir\n> +#\n> +traverse_fan_in()\n> +{\n> +\tlocal for_each_name=$1\n> +\tlocal for_each_dep=$2\n> +\tlocal name=$3\n> +\tlocal head_deps=$4 || :\n> +\tlocal deps_src\n> +\tlocal head=\"$(git symbolic-ref HEAD | sed 's#^refs/\\(heads\\|top-bases\\)/##')\" || :\n> +\n> +\tbranchq=\"$(mktemp -t tg-fan-in.XXXXXX)\"\n> +\tallbranches=\"$(mktemp -t -d tg-fan-in-all.XXXXXX)\"\n> +\ttrap \"rm -rf \\\"$branchq\\\" \\\"$allbranches\\\"\" 0\n> +\n> +\techo \"$name\" > \"$branchq\"\n> +\n> +\twhile [ -s \"$branchq\" ]; do\n> +\t\t# dequeue\n> +\t\t{\n> +\t\t\tread name\n> +\t\t\tcat > \"$branchq.headless\"\n> +\t\t} < \"$branchq\"\n> +\t\tmv -f \"$branchq.headless\" \"$branchq\"\n> +\n> +\t\t[ ! -d \"$allbranches/$name\" ] ||\n> +\t\t\tcontinue;\n> +\t\tmkdir -p \"$allbranches/$name\"\n> +\n> +\t\t# eval branch\n> +\t\teval \"$for_each_name \\\"$name\\\"\"\n> +\n> +\t\told_IFS=\"$IFS\"\n> +\t\tIFS=\"\"\n> +\t\tgit for-each-ref --format='%(refname)' refs/top-bases |\n> +\t\t\twhile read ref; do\n> +\t\t\t\tparent=\"${ref#refs/top-bases/}\"\n> +\n> +\t\t\t\tdeps_src=$parent\n> +\t\t\t\t# select branch/index/worktree for HEAD branch\n> +\t\t\t\t[ \"x$parent\" = \"x$head\" -a -n \"$head_deps\" ] &&\n> +\t\t\t\t\tdeps_src=$head_deps\n> +\t\t\t\tcat_file \"$deps_src:.topdeps\" | fgrep -qx \"$name\" ||\n> +\t\t\t\t\tcontinue\n> +\n> +\t\t\t\t# eval dep\n> +\t\t\t\teval \"$for_each_dep \\\"$parent\\\" \\\"$name\\\"\"\n> +\n> +\t\t\t\techo \"$parent\" >> \"$branchq\"\n> +\t\t\tdone\n> +\t\tIFS=\"$old_IFS\"\n> +\n> +\tdone\n> +}\n> +\n> +# prints the fan-in as a dot graph with edges\n> +graph_fan_in()\n> +{\n> +\tprintf \"digraph G {\\n\"\n> +\n> +\ttraverse_fan_in : _graph_dep_edge \"$1\" $2\n> +\n> +\tprintf \"}\\n\"\n> +}\n> +\n> +# prints the fan-in as name per line\n> +list_fan_in()\n> +{\n> +\ttraverse_fan_in echo : \"$1\" $2\n> +}\n> +\n>  ## Startup\n>  \n>  [ -d \"@cmddir@\" ] ||\n> -- \n> tg: (ff59ac7..) bw/fan-in-out (depends on: master)\n> \n\n-- \nPengutronix e.K.                           | Uwe Kleine-König            |\nIndustrial Linux Solutions                 | http://www.pengutronix.de/  |\n"},{"id":"152651","messageId":"AANLkTi=wZUc0GnB8p0=3Hkd1xPsvqqdEMHn80GKsHUj6@mail.gmail.com","threadId":"25348","inReplyTo":"20101005071334.GF11737@pengutronix.de","subject":"Re: [TopGit PATCH 1/4] provide fan-in and -out traversal interface","fromName":"Bert Wesarg","fromEmail":"bert.wesarg@googlemail.com","sentAt":"2010-10-05T07:54:48Z","receivedAt":"2010-10-05T07:54:48Z","isPatch":true,"sender":{"key":"bert.wesarg@googlemail.com","avatar":"https://avatars.githubusercontent.com/u/111934?v=4"},"body":"2010/10/5 Uwe Kleine-König <u.kleine-koenig@pengutronix.de>:\n> On Tue, Oct 05, 2010 at 12:28:17AM +0200, Bert Wesarg wrote:\n>> This adds general functions to get the list of all offending branches for\n> Is offending the right word here?  I don't understand that.\n\nI'm unsure about the right wording here too. 'offending' is definitive\nthe wrong word here. Somethink like this may be better:\n\nThis adds general functions to get the list of all branches which\neither depends on a given one (fan-in), or all dependencies of a given\none (fan-out).\n\n>\n>> a given one. Either which depends on the given branch (fan-in) or all\n>> dependencies (fan-out).\n>>\n>> Two simple users are provided which just lists the names or generates dot\n>> input.\n> This should then be used for tg summary --graphviz, too, doesn't it?\n\nNo. tg summary --graphviz outputs the whole graph. These will generate\nonly a subgraph based on a given topic. tg summary does not take a\ntopic as argument.\n\n>\n>>\n>> Signed-off-by: Bert Wesarg <bert.wesarg@googlemail.com>\n>>\n>> ---\n>>  tg.sh |  170 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n>>  1 files changed, 170 insertions(+), 0 deletions(-)\n>>\n>> diff --git a/tg.sh b/tg.sh\n>> index 3718702..926b31b 100644 tg.sh\n>> --- a/tg.sh\n>> +++ b/tg.sh\n>> @@ -351,6 +351,176 @@ setup_pager()\n>>       trap \"exec >&-; rm \\\"$_pager_fifo\\\"; rmdir \\\"$_pager_fifo_dir\\\"; wait\" EXIT\n>>  }\n>>\n>> +# traverse_fan_out(for_each_name, for_each_dep, name, head_deps)\n> This uses an unusual format.\n>\n> please make it\n>\n> # traverse_fan_out FOR_EACH_NAME FOR_EACH_DEP NAME HEAD_DEPS\n>\n\nYes. this makes it more consistent.\n\n>> +#\n>> +# traverse the dependencies of @name in bfs order and call @for_each_name\n>> +# on each dep (i.e. node) and @for_each_dep on all dependencies (i.e. edge)\n>> +# with source and dest as arguments.\n>> +#\n>> +# @name' needs to be a TopGit controlled branch\n>> +#\n>> +# @head_deps specifies where to take the .topdeps from for the HEAD branch\n>> +# empty - from the committed tree\n>> +# '(i)' - from the index\n>> +# '(w)' - from the working dir\n>> +#\n>> +traverse_fan_out()\n>> +{\n>> +     local for_each_name=$1\n>> +     local for_each_dep=$2\n>> +     local name=$3\n>> +     local head_deps=$4 || :\n>> +     local deps_src\n>> +     local head=\"$(git symbolic-ref HEAD | sed 's#^refs/\\(heads\\|top-bases\\)/##')\" || :\n> I don't remember the exact problems, but some shells get using local and\n> assignment in a single command wrong.  Can you please fix that up?  (I\n> fixed that up for one of your commits.)\n\nYes, that should be the right thing to do.\n\nBert\n"},{"id":"152704","messageId":"1286307062-30325-1-git-send-email-bert.wesarg@googlemail.com","threadId":"25348","inReplyTo":"AANLkTi=wZUc0GnB8p0=3Hkd1xPsvqqdEMHn80GKsHUj6@mail.gmail.com","subject":"[TopGit PATCH v2] provide fan-in and -out traversal interface","fromName":"Bert Wesarg","fromEmail":"bert.wesarg@googlemail.com","sentAt":"2010-10-05T19:31:02Z","receivedAt":"2010-10-05T19:31:02Z","isPatch":true,"sender":{"key":"bert.wesarg@googlemail.com","avatar":"https://avatars.githubusercontent.com/u/111934?v=4"},"body":"This adds general functions to get the list of all branches which\neither depends on a given one (fan-in), or all dependencies of a given\none (fan-out).\n\nTwo simple users are provided which just lists the names of generates dot\ninput.\n\nSigned-off-by: Bert Wesarg <bert.wesarg@googlemail.com>\n\n---\n\nNote for v3: I should probably use the list_deps function, but that needs to\nhonor -i/-w first.\n\nChanges:\n v2:\n  * make doc consistent\n  * provide $_name to FOR_EACH-commands\n  * don't assign values to local variables at declaration time\n\n tg.sh |  184 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n 1 files changed, 184 insertions(+), 0 deletions(-)\n\ndiff --git a/tg.sh b/tg.sh\nindex 3718702..8fa06d3 100644 tg.sh\n--- a/tg.sh\n+++ b/tg.sh\n@@ -351,6 +351,190 @@ setup_pager()\n \ttrap \"exec >&-; rm \\\"$_pager_fifo\\\"; rmdir \\\"$_pager_fifo_dir\\\"; wait\" EXIT\n }\n \n+# traverse_fan_out FOR_EACH_NAME FOR_EACH_DEP NAME HEAD_DEPS\n+#\n+# traverse the dependencies of NAME in bfs order and call FOR_EACH_NAME\n+# on each dep (i.e. node) and FOR_EACH_DEP on all dependencies (i.e. edge)\n+# with source and dest as arguments.\n+#\n+# FOR_EACH_NAME and FOR_EACH_DEP can refer to $_name for queried branch NAME\n+#\n+# NAME needs to be a TopGit controlled branch\n+#\n+# HEAD_DEPS specifies where to take the .topdeps from for the HEAD branch\n+# empty - from the committed tree\n+# '(i)' - from the index\n+# '(w)' - from the working dir\n+#\n+traverse_fan_out()\n+{\n+\tlocal for_each_name for_each_dep name head_deps deps_src head\n+\n+\t_name=\"$3\"\n+\tfor_each_name=\"$1\"\n+\tfor_each_dep=\"$2\"\n+\thead_deps=$4 || :\n+\thead=\"$(git symbolic-ref HEAD | sed 's#^refs/\\(heads\\|top-bases\\)/##')\" || :\n+\n+\tbranchq=\"$(mktemp -t tg-fan-out.XXXXXX)\"\n+\tallbranches=\"$(mktemp -t -d tg-fan-out-all.XXXXXX)\"\n+\ttrap \"rm -rf \\\"$branchq\\\" \\\"$allbranches\\\"\" 0\n+\n+\t# fill queue with root name\n+\techo \"$_name\" > \"$branchq\"\n+\n+\twhile [ -s \"$branchq\" ]; do\n+\t\t# dequeue\n+\t\t{\n+\t\t\tread name\n+\t\t\tcat > \"$branchq.headless\"\n+\t\t} < \"$branchq\"\n+\t\tmv -f \"$branchq.headless\" \"$branchq\"\n+\n+\t\t# eval name\n+\t\teval \"$for_each_name \\\"$name\\\"\"\n+\n+\t\t# don't travers non-tgish branches\n+\t\tref_exists \"refs/top-bases/$name\" ||\n+\t\t\tcontinue\n+\n+\t\tdeps_src=$name\n+\t\t# select .topdeps source for HEAD branch\n+\t\t[ \"x$name\" = \"x$head\" -a -n \"$head_deps\" ] &&\n+\t\t\tdeps_src=$head_deps\n+\n+\t\told_IFS=\"$IFS\"\n+\t\tIFS=\"\"\n+\t\tcat_file \"$deps_src:.topdeps\" |\n+\t\twhile read dep; do\n+\n+\t\t\t# eval dep\n+\t\t\teval \"$for_each_dep \\\"$name\\\" \\\"$dep\\\"\"\n+\n+\t\t\t[ -d \"$allbranches/$dep\" ] || {\n+\t\t\t\tmkdir -p \"$allbranches/$dep\"\n+\t\t\t\techo \"$dep\" >> \"$branchq\"\n+\t\t\t}\n+\t\tdone\n+\t\tIFS=\"$old_IFS\"\n+\n+\tdone\n+}\n+\n+_graph_dep_edge()\n+{\n+\tprintf \"\\t\\\"%s\\\" -> \\\"%s\\\";\\n\" \"$1\" \"$2\"\n+}\n+\n+# prints the fan-out as a dot graph with edges\n+graph_fan_out()\n+{\n+\tprintf \"digraph G {\\n\"\n+\n+\ttraverse_fan_out : _graph_dep_edge \"$1\" $2\n+\n+\tprintf \"}\\n\"\n+}\n+\n+_list_fan()\n+{\n+\t# only print the deps\n+\t[ \"$_name\" = \"$1 \"] ||\n+\t\techo \"$1\"\n+}\n+\n+# prints the fan-out as name per line\n+list_fan_out()\n+{\n+\ttraverse_fan_out _list_fan : \"$1\" $2\n+}\n+\n+# traverse_fan_in FOR_EACH_NAME FOR_EACH_DEP NAME HEAD_DEPS\n+#\n+# traverse all branches which depends on NAME in bfs order and call\n+# FOR_EACH_NAME on each (i.e. node) and FOR_EACH_DEP on all dependencies\n+# (i.e. edge) with source and dest as arguments.\n+#\n+# FOR_EACH_NAME and FOR_EACH_DEP can refer to $_name for queried branch NAME\n+#\n+# NAME needs not to be a TopGit controlled branch\n+#\n+# HEAD_DEPS specifies where to take the .topdeps from for the HEAD branch\n+# empty - from the committed tree\n+# '(i)' - from the index\n+# '(w)' - from the working dir\n+#\n+traverse_fan_in()\n+{\n+\tlocal for_each_name for_each_dep name head_deps deps_src head\n+\n+\t_name=\"$3\"\n+\tfor_each_name=\"$1\"\n+\tfor_each_dep=\"$2\"\n+\thead_deps=\"$4\" || :\n+\thead=\"$(git symbolic-ref HEAD | sed 's#^refs/\\(heads\\|top-bases\\)/##')\" || :\n+\n+\tbranchq=\"$(mktemp -t tg-fan-in.XXXXXX)\"\n+\tallbranches=\"$(mktemp -t -d tg-fan-in-all.XXXXXX)\"\n+\ttrap \"rm -rf \\\"$branchq\\\" \\\"$allbranches\\\"\" 0\n+\n+\t# fill queue with root name\n+\techo \"$_name\" > \"$branchq\"\n+\n+\twhile [ -s \"$branchq\" ]; do\n+\t\t# dequeue\n+\t\t{\n+\t\t\tread name\n+\t\t\tcat > \"$branchq.headless\"\n+\t\t} < \"$branchq\"\n+\t\tmv -f \"$branchq.headless\" \"$branchq\"\n+\n+\t\t[ ! -d \"$allbranches/$name\" ] ||\n+\t\t\tcontinue;\n+\t\tmkdir -p \"$allbranches/$name\"\n+\n+\t\t# eval branch\n+\t\teval \"$for_each_name \\\"$name\\\"\"\n+\n+\t\told_IFS=\"$IFS\"\n+\t\tIFS=\"\"\n+\t\tgit for-each-ref --format='%(refname)' refs/top-bases |\n+\t\t\twhile read ref; do\n+\t\t\t\tparent=\"${ref#refs/top-bases/}\"\n+\n+\t\t\t\tdeps_src=$parent\n+\t\t\t\t# select branch/index/worktree for HEAD branch\n+\t\t\t\t[ \"x$parent\" = \"x$head\" -a -n \"$head_deps\" ] &&\n+\t\t\t\t\tdeps_src=$head_deps\n+\t\t\t\tcat_file \"$deps_src:.topdeps\" | fgrep -qx \"$name\" ||\n+\t\t\t\t\tcontinue\n+\n+\t\t\t\t# eval dep\n+\t\t\t\teval \"$for_each_dep \\\"$parent\\\" \\\"$name\\\"\"\n+\n+\t\t\t\techo \"$parent\" >> \"$branchq\"\n+\t\t\tdone\n+\t\tIFS=\"$old_IFS\"\n+\n+\tdone\n+}\n+\n+# prints the fan-in as a dot graph with edges\n+graph_fan_in()\n+{\n+\tprintf \"digraph G {\\n\"\n+\n+\ttraverse_fan_in : _graph_dep_edge \"$1\" $2\n+\n+\tprintf \"}\\n\"\n+}\n+\n+# prints the fan-in as name per line\n+list_fan_in()\n+{\n+\ttraverse_fan_in _list_fan : \"$1\" $2\n+}\n+\n ## Startup\n \n [ -d \"@cmddir@\" ] ||\n-- \ntg: (ff59ac7..) bw/fan-in-out (depends on: master)\n"}]}