bvt's backtrace

The vpatch presented in this article packs together fixes for quite a lot of errors, which were discovered by Diana Coman using the eucrypt vtree. It also betrays insufficient testing on my side: had I tested v.sh with full eucrypt vtree, or at least came up with a synthetic vtree that has conflicting press heads, I would have caught this myself. So while there was always an intention to support such vtrees, the mismatching assumptions between different components accumulated until this use-case got broken. Clearly, this is one of the areas where improvement is necessary.

diff -uNr a/vtools/Makefile b/vtools/Makefile
--- a/vtools/Makefile 67cefb8f1983138b975a6ec3402c6718e3fa8855201d2c41f4f4cd68284a21fc853cc56ce1d03b61a1d93df3ddcde48979b1a7ede00d077e31f39bd647daf1ed
+++ b/vtools/Makefile false
@@ -1,14 +0,0 @@
-
-vdiff:
-	gprbuild -Pvdiff.gpr
-
-vpatch:
-	gprbuild -Pvpatch.gpr
-
-vflow:
-	gprbuild -Pvflow.gpr
-
-clean:
-	gprclean -Pvdiff.gpr
-	gprclean -Pvpatch.gpr
-	gprclean -Pvflow.gpr

As requested, the makefile is removed.

diff -uNr a/vtools/src/vflow.adb b/vtools/src/vflow.adb
--- a/vtools/src/vflow.adb e6faf838d6886b05028f7483b7ff738584217d570a2a894fbe91380614a576f25952120f7fa5c1dff3bd6b16e53364cb5859ed2407412ab121c1c76d0826044c
+++ b/vtools/src/vflow.adb 5ee6bcb685f193971ff5990bf189e36b52cd113e289cf46248fcd29da401a00114e4e22235f2f4d492a202546c6622a73976ed524ba9cd1f0f9dce8a6fcf3a11
@@ -221,9 +221,46 @@
       N_Selected     : Natural     := 0;
       Finished       : Boolean     := False;
       Has_Loops      : Boolean     := False;
+
+      DFS_Stack      : Vpatch_List := (others => 0);
+      Stack_Head     : Natural     := 0;
+
+      procedure Push (V : Vpatch_Index) is
+      begin
+	 DFS_Stack(Stack_Head) := V;
+	 Stack_Head            := Stack_Head + 1;
+      end Push;
+
+      function Pop return Boolean is
+      begin
+	 if Stack_Head = 0 then
+	    return False;
+	 end if;
+	 Stack_Head := Stack_Head - 1;
+	 DFS_Stack(Stack_Head) := 0;
+	 return True;
+      end Pop;
+
+      function Matches_Last_Added (V : Vpatch_Index) return Boolean is
+      begin
+	 if Stack_Head = 0 then
+	    return True;
+	 else
+	    return Vpatch_Dependencies(V, DFS_Stack(Stack_Head - 1)) = True;
+	 end if;
+      end Matches_Last_Added;
+
+      procedure Add_Vpatch (V : Vpatch_Index) is
+      begin
+	 Free_Vpatches(V)         := False;
+	 Vpatch_Order(N_Selected) := V;
+	 N_Selected               := N_Selected + 1;
+	 Finished                 := False;
+      end Add_Vpatch;
    begin
       while not Finished loop
 	 Finished := True;
+
 	 for I in Free_Vpatches'Range loop
 	    if Free_Vpatches(I) then
 	       declare
@@ -237,16 +274,20 @@
 		     end if;
 		  end loop;

-		  -- All dependencies present, can add this vpatch:
-		  if All_Satisfied then
-		     Free_Vpatches(I)         := False;
-		     Vpatch_Order(N_Selected) := I;
-		     N_Selected               := N_Selected + 1;
-		     Finished                 := False;
+		  -- All dependencies present, can add this vpatch, if the last
+		  -- vpatch added is in the antecedent set.
+		  if All_Satisfied and Matches_Last_Added(I) then
+		     Add_Vpatch(I);
+		     Push(I);
 		  end if;
 	       end;
 	    end if;
 	 end loop;
+
+	 -- If this branch is exhausted, search the siblings.
+	 if Finished then
+	    Finished := not Pop;
+	 end if;
       end loop;

       -- Check if there are still free vpatches (there is a loop):

This change introduces a DFS-based toposort. Instead of adding any vpatch to the flow that has all its antecedents present, now the algorithm specifically searches for a vpatch that depends on the latest vpatch added. The logic is also refactored so that DFS stack updates are not mixed with adding vpatch to the flow.

DFS-based toposort is necessary for vtree command, which benefits a lot from displaying vpatches close to their antecedents, while the old code would put them, well, in ~random places, as long as the flow was preserved.

@@ -346,7 +387,6 @@
       end Add_Dependencies;

       procedure Print_Flow_Or_Conflicts is
-	 Has_Conflicts : Boolean := False;
       begin
 	 for I in Vpatch_Conflicts'Range(1) loop
 	    for J in Vpatch_Conflicts'Range(2) loop
@@ -354,15 +394,10 @@
 		 and Vpatch_Conflicts(I,J) then
 		  Put_Line("C " & Integer'Image(I));
 		  Put_Line("C " & Integer'Image(J));
-		  Has_Conflicts := True;
 	       end if;
 	    end loop;
 	 end loop;

-	 if Has_Conflicts then
-	    return;
-	 end if;
-
 	 for I in Vpatch_Order'Range loop
 	    if Selected_Vpatches(Vpatch_Order(I)) then
 	       Put_Line("P " & Integer'Image(Vpatch_Order(I)));

Bugfix part inside vflow.adb: the requirement of v.sh is that in case of conflicts, vflow still prints the flow. However, vflow violated this requirement. Now the logic that disabled the printing is gone.

Now, for v.sh:

diff -uNr a/vtools/v.sh b/vtools/v.sh
--- a/vtools/v.sh ba8feba74997e15453711dd8c414240605d87674dabd3feac0fdba6a97cb2beefbf0ef03b28b02d4b1d9ae251c58c9400b02f6359c1a3d76ad351e31c6f4caae
+++ b/vtools/v.sh e64bb2725e055aaa4e7ce33a909209d55686fb42e4105fb0d383cf5d80145104333673486cf1dfbb2a42e6e2743cf9466d17fe7f799b40aaa708b5421afd854e
@@ -140,19 +140,25 @@
 }

 vpatchflowerr() {
+    set +e
     awk 'BEGIN {err=0; ok=0;}
 err == 0 && $1 == "C" {err=1; ech=$1;}
 err == 0 && $1 == "L" {err=2; ech=$1;}
 err == 0 && $1 == "P" {ok=1;}
 END {if (err != 0) exit err; if (ok != 1) exit 3; exit 0;}' <"$topo"
     exitcode="$?"
+    set -e
     if [ "$exitcode" -eq "1" ]; then
-	    >&2 printf "\nConflicting leaves selected:\n"
-	    >&2 awk '$1 == "C" {print $2}' < "$topo" | vpatchnames | sort | uniq
+	    >&2 printf "Conflicting leaves selected:\n"
+	    awk '$1 == "C" {print $2}' < "$topo" | vpatchnames | sort | uniq >&2
+	    >&2 printf "Available heads:\n"
+	    awk '
+($1 == "I" || $1 == "d" ) {non_terminals[$3]=1;}
+($1 == "P") {if (!($2 in non_terminals)) {print $2;}}' < "$topo" | vpatchnames >&2
 	    fail
     elif [ "$exitcode" -eq "2" ]; then
-	    >&2 printf "\nConflicting leaves selected:\n"
-	    >&2 awk '{print $2}' < "$topo" | vpatchnames
+	    >&2 printf "Loop among vpatches:\n"
+	    awk '{print $2}' < "$topo" | vpatchnames >&2
 	    fail
     elif [ "$exitcode" -eq "3" ]; then
 	    >&2 echo "Unknown error. Investigate in $vgpgdir:"

Lots of fixes go into the error handling. I have used the return value from an awk script to convey information about the errors in the flow to v.sh. The problem is, with set -e, returning nonzero exit code terminates execution immediately, so subsequent commands were never executed. I get around this now with set +e - set -e before and after the awk script invocation.

The flow command in case of eucrypt's tree was still working in a shitty way, because it reported only the conflicting vpatches, which was not a usable UI. Now, the heads are also printed to stderr.

Another set of fixes goes to placement of redirections to stderr and the error message for the case of loops among vpatches.

@@ -276,17 +282,23 @@

 	vpatchflow "$@"
 	awk -v VF="$vpatches" '
+function max(a,b) { return (a > b) ? a : b;}
 function repeat(s,n) {i=0; while (i++ < n) {printf("%s",s);}}
-FILENAME==VF {n[$2]=$1}
-FILENAME=="-" && ($1 == "I" || $1 == "d" ) {a[$2]++;b[$3]=1;}
+FILENAME==VF {names[$2]=$1}
+FILENAME=="-" && ($1 == "I" || $1 == "d" ) {non_terminals[$3]=1;}
+FILENAME=="-" && ($1 == "d") {if (!($2 in n_ante)) n_ante[$2] = 0; dir_ante[$2][n_ante[$2]] = $3; n_ante[$2]++;}
 FILENAME=="-" && ($1 == "P" || $1 == "p") {
-   if (!($2 in a)) {a[$2]=0};
-   repeat(" ", a[$2]);
-   printf("%s%s%s\n",n[$2], ($2 in b) ? "" : " (*)", ($1 == "P") ? " +" : "" );
+   level[$2] = 0;
+   if ($2 in n_ante) {
+      for (i = 0; i < n_ante[$2]; i++) {
+        level[$2] = max(level[$2], level[dir_ante[$2][i]]+1);
+      }
+   }
+   repeat(" ", level[$2]);
+   printf("%s%s%s\n",names[$2], ($2 in non_terminals) ? "" : " (*)", ($1 == "P") ? " +" : "" );
 }' "$vpatches" - <"$topo"
 	exit_success
 fi

-
 >&2 echo "Unknown command: $1"
 fail

Finally, I updated the logic of vtree command. With DFS-based toposort, the vpatches that form antecedent-descendant chain are close to each other, but I have also decided to fix the indentation logic too. Instead of indenting each vpatch with the number of spaces equal to the number of transitive antecedents, the logic now is: the indentation level of vpatch is one greater than maximum indentation level of its direct antecedents, with genesis at indentation level 0. This makes vtree formatting much more pleasant. However, the complexity increased in this case beyond the point where variables like a or b are usable, so all variable names are updated to be meaningful.

The vpatch and seal:

curl 'http://bvt-trace.net/vpatches/vtools_vsh_ascii_fix2.vpatch' > vtools_vsh_ascii_fix2.vpatch
curl 'http://bvt-trace.net/vpatches/vtools_vsh_ascii_fix2.vpatch.bvt.sig' > vtools_vsh_ascii_fix2.vpatch.bvt.sig

This article was published on Friday, March 13th, 2020 at 18:50 and is filed under Ada. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.