Reworked construct-tree.sh

This version constructs layers of the bisect graph by merging
nodes of layer N-1 to produce nodes of layer N.  The number of
layers is equal to number of files.

1 files changed, 88 insertions, 33 deletions

diff --git a/construct-tree.sh b/construct-tree.sh
index 4298f93..7affd16 100755
--- a/construct-tree.sh
+++ b/construct-tree.sh
@@ -1,15 +1,12 @@
 #!/bin/bash
 
 set -e
-
-files=()
 verbose=""
-verbose_opt=""
 
 OPTS="`getopt -o v -l verbose -- "$@"`"
 while [ $# -gt 0 ]; do
     case $1 in
-	-v|--verbose) verbose="set -x"; verbose_opt="$1" ;;
+	-v|--verbose) verbose="set -x" ;;
 	*) break ;;
     esac
     shift
@@ -17,49 +14,107 @@ done
 
 $verbose
 
-if [ $# -gt 1 ]; then
-    echo "ERROR: wrong arguments: $@"
+if [ $# -gt 0 ]; then
+    echo "ERROR: extra arguments: $@"
+    exit 1
 fi
     
 declare -a files
 declare -A indices
 . ./file-index.map
 
-for file in "${files[@]}"; do
-    if [ x"$(git diff -- $file | wc -l)" = x"0" ]; then
-	continue
-    fi
+build_depth_1 () {
+    set -e
+    $verbose
 
-    orig_tag=$(git rev-parse HEAD)
+    local file
 
-    index=${indices["$file"]}
-    tag=$(echo "${index}_$@" | tr "_" "\n" | sort -n | tr "\n" "_" \
-		 | sed -e "s/^_//g" -e "s/__/_/g" -e "s/_\$/\n/")
-    echo "Starting $tag"
+    for file in "${files[@]}"; do
+	if [ x"$(git diff -- $file | wc -l)" = x"0" ]; then
+	    echo "ERROR: no difference in $file"
+	    exit 1
+	fi
 
-    if git rev-parse --verify $tag >/dev/null 2>&1; then
-	git stash >/dev/null
-	parents="$(git rev-list --parents -n 1 $tag | cut -d" " -f 2-)"
-	echo "Merging $parents"
-	git merge -m $tag $parents >/dev/null
-	git stash pop >/dev/null
+	local index=${indices["$file"]}
+	local tag=$index
 
-	for branch in $(git br --contains $tag | grep -v "^*"); do
-	    echo "Deleting branch: $branch"
-	    git br -D $branch >/dev/null
-	done
-    else
-	echo "Committing $file"
 	git add $file
 	git ci -m $tag >/dev/null
+
+	echo "Committing 1/$tag: $file"
+	git br 1/$tag
+
+	git reset HEAD^ >/dev/null
+    done
+}
+
+build_depth () {
+    set -e
+    $verbose
+
+    local depth="$1"
+
+    if [ x"$depth" = x"1" ]; then
+	build_depth_1
+	return
     fi
 
-    git br $tag
+    echo "Starting depth: $depth"
 
-    echo "Recursing into $tag: $(git rev-parse $tag)"
-    
-    $0 $verbose_opt $tag
+    local depth_1=$(($depth-1))
+    local -a branches
+    local br1
+    local br2
+
+    branches=($(git br --list "$depth_1/*"))
+
+    br1=0
+    while [ $br1 -lt ${#branches[@]} ]; do
+	br2=$(($br1+1))
+	while [ $br2 -lt ${#branches[@]} ]; do
+	    local orig_tag=$(git rev-parse HEAD)
+
+	    local br1_tag=$(echo ${branches[$br1]} | cut -d/ -f 2)
+	    local br2_tag=$(echo ${branches[$br2]} | cut -d/ -f 2)
+
+	    local tag
+	    tag=$(echo "${br1_tag}_${br2_tag}" \
+			 | tr "_" "\n" \
+			 | sort -nu | tr "\n" "_" \
+			 | sed -e "s/^_//g" -e "s/__/_/g" -e "s/_\$/\n/")
+
+	    local tag_len
+	    tag_len=$(echo $tag | tr "_" "\n" | wc -l)
+	    if [ x"$tag_len" != x"$depth" ]; then
+		continue
+	    fi
+
+	    local parents=""
+	    if git rev-parse --verify $depth/$tag >/dev/null 2>&1; then
+		parents="$(git rev-list --parents -n 1 $depth/$tag | cut -d" " -f 2-)"
+		git br -D $depth/$tag
+	    fi
+
+	    parents="$parents ${depth_1}/$br1_tag ${depth_1}/$br2_tag"
+
+	    git stash >/dev/null
+	    git merge -m $tag $parents >/dev/null
+	    git stash pop >/dev/null
+
+	    echo "Creating $depth/$tag from $parents"
+	    git br $depth/$tag
+	    git reset $orig_tag >/dev/null
+
+	    br2=$((br2+1))
+	done
+	br1=$((br1+1))
+    done
+
+    echo "Finished depth: $depth"
+}
 
-    echo "Finished $tag: $(git rev-parse $tag)"
-    git reset $orig_tag >/dev/null
+depth="1"
+while [ $depth -le "${#files[@]}" ]; do
+    build_depth $depth
+    depth=$(($depth+1))
 done