[TopGit PATCH v2] provide fan-in and -out traversal interface

[Bert Wesarg <bert.wesarg@googlemail.com>]

This adds general functions to get the list of all branches which
either depends on a given one (fan-in), or all dependencies of a given
one (fan-out).

Two simple users are provided which just lists the names of generates dot
input.

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

---

Note for v3: I should probably use the list_deps function, but that needs to
honor -i/-w first.

Changes:
 v2:
  * make doc consistent
  * provide $_name to FOR_EACH-commands
  * don't assign values to local variables at declaration time

 tg.sh |  184 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 184 insertions(+), 0 deletions(-)

diff --git a/tg.sh b/tg.sh
index 3718702..8fa06d3 100644 tg.sh
--- a/tg.sh
+++ b/tg.sh
@@ -351,6 +351,190 @@ setup_pager()
 	trap "exec >&-; rm \"$_pager_fifo\"; rmdir \"$_pager_fifo_dir\"; wait" EXIT
 }
 
+# traverse_fan_out FOR_EACH_NAME FOR_EACH_DEP NAME HEAD_DEPS
+#
+# traverse the dependencies of NAME in bfs order and call FOR_EACH_NAME
+# on each dep (i.e. node) and FOR_EACH_DEP on all dependencies (i.e. edge)
+# with source and dest as arguments.
+#
+# FOR_EACH_NAME and FOR_EACH_DEP can refer to $_name for queried branch NAME
+#
+# NAME needs to be a TopGit controlled branch
+#
+# HEAD_DEPS specifies where to take the .topdeps from for the HEAD branch
+# empty - from the committed tree
+# '(i)' - from the index
+# '(w)' - from the working dir
+#
+traverse_fan_out()
+{
+	local for_each_name for_each_dep name head_deps deps_src head
+
+	_name="$3"
+	for_each_name="$1"
+	for_each_dep="$2"
+	head_deps=$4 || :
+	head="$(git symbolic-ref HEAD | sed 's#^refs/\(heads\|top-bases\)/##')" || :
+
+	branchq="$(mktemp -t tg-fan-out.XXXXXX)"
+	allbranches="$(mktemp -t -d tg-fan-out-all.XXXXXX)"
+	trap "rm -rf \"$branchq\" \"$allbranches\"" 0
+
+	# fill queue with root name
+	echo "$_name" > "$branchq"
+
+	while [ -s "$branchq" ]; do
+		# dequeue
+		{
+			read name
+			cat > "$branchq.headless"
+		} < "$branchq"
+		mv -f "$branchq.headless" "$branchq"
+
+		# eval name
+		eval "$for_each_name \"$name\""
+
+		# don't travers non-tgish branches
+		ref_exists "refs/top-bases/$name" ||
+			continue
+
+		deps_src=$name
+		# select .topdeps source for HEAD branch
+		[ "x$name" = "x$head" -a -n "$head_deps" ] &&
+			deps_src=$head_deps
+
+		old_IFS="$IFS"
+		IFS=""
+		cat_file "$deps_src:.topdeps" |
+		while read dep; do
+
+			# eval dep
+			eval "$for_each_dep \"$name\" \"$dep\""
+
+			[ -d "$allbranches/$dep" ] || {
+				mkdir -p "$allbranches/$dep"
+				echo "$dep" >> "$branchq"
+			}
+		done
+		IFS="$old_IFS"
+
+	done
+}
+
+_graph_dep_edge()
+{
+	printf "\t\"%s\" -> \"%s\";\n" "$1" "$2"
+}
+
+# prints the fan-out as a dot graph with edges
+graph_fan_out()
+{
+	printf "digraph G {\n"
+
+	traverse_fan_out : _graph_dep_edge "$1" $2
+
+	printf "}\n"
+}
+
+_list_fan()
+{
+	# only print the deps
+	[ "$_name" = "$1 "] ||
+		echo "$1"
+}
+
+# prints the fan-out as name per line
+list_fan_out()
+{
+	traverse_fan_out _list_fan : "$1" $2
+}
+
+# traverse_fan_in FOR_EACH_NAME FOR_EACH_DEP NAME HEAD_DEPS
+#
+# traverse all branches which depends on NAME in bfs order and call
+# FOR_EACH_NAME on each (i.e. node) and FOR_EACH_DEP on all dependencies
+# (i.e. edge) with source and dest as arguments.
+#
+# FOR_EACH_NAME and FOR_EACH_DEP can refer to $_name for queried branch NAME
+#
+# NAME needs not to be a TopGit controlled branch
+#
+# HEAD_DEPS specifies where to take the .topdeps from for the HEAD branch
+# empty - from the committed tree
+# '(i)' - from the index
+# '(w)' - from the working dir
+#
+traverse_fan_in()
+{
+	local for_each_name for_each_dep name head_deps deps_src head
+
+	_name="$3"
+	for_each_name="$1"
+	for_each_dep="$2"
+	head_deps="$4" || :
+	head="$(git symbolic-ref HEAD | sed 's#^refs/\(heads\|top-bases\)/##')" || :
+
+	branchq="$(mktemp -t tg-fan-in.XXXXXX)"
+	allbranches="$(mktemp -t -d tg-fan-in-all.XXXXXX)"
+	trap "rm -rf \"$branchq\" \"$allbranches\"" 0
+
+	# fill queue with root name
+	echo "$_name" > "$branchq"
+
+	while [ -s "$branchq" ]; do
+		# dequeue
+		{
+			read name
+			cat > "$branchq.headless"
+		} < "$branchq"
+		mv -f "$branchq.headless" "$branchq"
+
+		[ ! -d "$allbranches/$name" ] ||
+			continue;
+		mkdir -p "$allbranches/$name"
+
+		# eval branch
+		eval "$for_each_name \"$name\""
+
+		old_IFS="$IFS"
+		IFS=""
+		git for-each-ref --format='%(refname)' refs/top-bases |
+			while read ref; do
+				parent="${ref#refs/top-bases/}"
+
+				deps_src=$parent
+				# select branch/index/worktree for HEAD branch
+				[ "x$parent" = "x$head" -a -n "$head_deps" ] &&
+					deps_src=$head_deps
+				cat_file "$deps_src:.topdeps" | fgrep -qx "$name" ||
+					continue
+
+				# eval dep
+				eval "$for_each_dep \"$parent\" \"$name\""
+
+				echo "$parent" >> "$branchq"
+			done
+		IFS="$old_IFS"
+
+	done
+}
+
+# prints the fan-in as a dot graph with edges
+graph_fan_in()
+{
+	printf "digraph G {\n"
+
+	traverse_fan_in : _graph_dep_edge "$1" $2
+
+	printf "}\n"
+}
+
+# prints the fan-in as name per line
+list_fan_in()
+{
+	traverse_fan_in _list_fan : "$1" $2
+}
+
 ## Startup
 
 [ -d "@cmddir@" ] ||
-- 
tg: (ff59ac7..) bw/fan-in-out (depends on: master)